一覧OS-08-4 · 同期と資源競合

優先度逆転とメモリ順序

CPUを得られない待ちと、他スレッドの書込みを観測する条件を別々に調べます。

説明

並行処理が進まない原因には、CPUを割り当てられないこと、ロックが解放されないこと、共有状態の受渡し手順が適切でないことなどがあります。優先度を上げる対策と、メモリの順序を保証する対策はそれぞれ対象が違います。

前半はH・M・Lの優先度とロック所有者を表にし、優先度継承が次の実行対象をどう変えるかを計算します。後半はC++のatomicを使う公開処理について、relaxedとrelease/acquireが許す観測結果を比較します。後半のPythonは規則に照らした候補の分類で、CPU上の発生頻度を測るものではありません。

1高優先度でも実行可能とは限らない

H=3、M=2、L=1とし、HはLが持つmutexを待っています。MとLだけが実行可能です。

base = {'H':3,'M':2,'L':1}基底優先度; runnable = ['M','L']実行可能な二つ; owner = 'L'; waiter = 'H'ロックの所有者と待ち手; print(max(runnable,key=base.get))選ばれる仕事

固定優先度ではMが選ばれます。H自身の優先度は高くてもロック待ちなので実行可能な列にいません。Lが進まない間はロックが解放されず、Hも待ち続けます。

2所有者へ優先度を引き継ぐ

mutexの所有者Lの有効優先度を、待ち手Hの値まで引き上げます。

effective = dict(base)有効優先度を用意; effective[owner] = max(base[owner],base[waiter])待ち手の優先度を継承; print(effective)変更後; print(max(runnable,key=effective.get))次の実行対象

Lの有効優先度が3になり、Mより先にLが選ばれます。Hがロックを横取りするのではなく、Lの解放処理を進める対策です。基底優先度1と継承した有効優先度3を分けて管理します。

3解放後に優先度を戻す

Lがロックを解放し、ほかに継承元となる待ち手がないとします。Hを実行可能へ戻し、Lの優先度を元へ戻します。

effective['L'] = base['L']この継承を解除; runnable.append('H')待ちから復帰; print(effective)復帰後の優先度; print(max(runnable,key=effective.get))Hが選ばれる

今度はHが選ばれます。複数のロックを保持している場合には別の待ち手からの継承が残ることもあるため、常に無条件で基底値へ戻す単純な処理にはできません。このモデルは一つのmutexに限定しています。

4共有データを公開する二つの書込み

後半ではdataとreadyを別々のatomic変数とし、初期値は両方0です。書き手はdataへ42、readyへ1の順にstoreします。読み手はready、dataの順にloadします。

writer = [('data.store',42,'relaxed'),('ready.store',1,'relaxed')]書き手の順序; reader = [('ready.load','relaxed'),('data.load','relaxed')]読み手の順序; print(writer); print(reader)各操作のメモリオーダー

同じ変数のatomic操作には原子性がありますが、relaxedだけでは別のatomic変数をまたぐ同期関係を作りません。この例でdataもatomicにしているのは、非atomicの競合による未定義動作と、atomicの順序保証を混同しないためです。

5relaxedで除外できない観測

(readyの値,dataの値)の候補を列挙します。すべてrelaxedではready=1を読んだことだけからdata=42を保証できません。

observations = [(0,0),(0,42),(1,0),(1,42)]観測候補; print([pair for pair in observations if pair[0]==1])公開フラグが1の場合

ready=1の候補にはdata=0と42があります。これはC++の規則上除外できない組を並べたもので、実機が必ず両方を発生させるという意味ではありません。特定CPUで何度試しても0が出ないことだけでは、言語仕様上の保証を追加できません。

6releaseとacquireで公開を対応させる

readyへのstoreをrelease、readyのloadをacquireへ変えます。acquireがこのreleaseの書いた1を読むことが同期の条件です。

writer[1] = ('ready.store',1,'release')公開側; reader[0] = ('ready.load','acquire')受取り側; print(writer); print(reader)対応する操作

この対応が成立すると、releaseより前のdataの書込みが、acquireより後のdataの読取りに対してhappens-beforeになります。この例にはdataを後で上書きする書き手がないため、ready=1を読んだ後のdataは42です。

7同期が成立した場合だけ候補を絞る

同期が成立するready=1のときだけdata=0の組を除外します。ready=0では今回のreleaseを観測したことになりません。

allowed = [pair for pair in observations if not (pair[0]==1 and pair[1]!=42)]同期成立時の規則を適用; print(allowed)許される候補

残る組は(0,0)、(0,42)、(1,42)です。フラグが0の読取りからは公開完了を判断できません。acquireという名前を付けるだけで、対応するreleaseを読まずにすべての書込みが届く保証ができるわけではありません。

8同期関係を経路として確認

書き手内の順序、releaseからacquireへの同期、読み手内の順序をつなぎます。これがdataの書込みから読取りへの関係です。

edges = {'write data':'release ready','release ready':'acquire ready=1','acquire ready=1':'read data'}順序と同期の辺; route = ['write data']データ書込みから開始; route.append(edges[route[-1]]); route.append(edges[route[-1]]); route.append(edges[route[-1]])関係をたどる; print(' -> '.join(route))読取りまでの経路

write dataからread dataまでつながります。優先度継承はCPUを得てロックを解放する問題へ働き、release/acquireは共有データの受渡し順序へ働きます。片方の設定で他方の保証を代用することはできません。

まとめ

優先度継承はロック所有者の実行を進め、待ち手を間接的に進める仕組みです。

atomicの原子性と、複数変数にまたがる公開順序の保証は別です。

releaseを書いた値をacquireが読むという対応と、前後の処理順序から共有データの可視性を判断します。

操作履歴と解説を振り返れます。

Python 3

1
base = {'H':3,'M':2,'L':1}; runnable = ['M','L']; owner = 'L'; waiter = 'H'; print(max(runnable,key=base.get))
M
2
effective = dict(base); effective[owner] = max(base[owner],base[waiter]); print(effective); print(max(runnable,key=effective.get))
{'H': 3, 'M': 2, 'L': 3}
L
3
effective['L'] = base['L']; runnable.append('H'); print(effective); print(max(runnable,key=effective.get))
{'H': 3, 'M': 2, 'L': 1}
H
4
writer = [('data.store',42,'relaxed'),('ready.store',1,'relaxed')]; reader = [('ready.load','relaxed'),('data.load','relaxed')]; print(writer); print(reader)
[('data.store', 42, 'relaxed'), ('ready.store', 1, 'relaxed')]
[('ready.load', 'relaxed'), ('data.load', 'relaxed')]
5
observations = [(0,0),(0,42),(1,0),(1,42)]; print([pair for pair in observations if pair[0]==1])
[(1, 0), (1, 42)]
6
writer[1] = ('ready.store',1,'release'); reader[0] = ('ready.load','acquire'); print(writer); print(reader)
[('data.store', 42, 'relaxed'), ('ready.store', 1, 'release')]
[('ready.load', 'acquire'), ('data.load', 'relaxed')]
7
allowed = [pair for pair in observations if not (pair[0]==1 and pair[1]!=42)]; print(allowed)
[(0, 0), (0, 42), (1, 42)]
8
edges = {'write data':'release ready','release ready':'acquire ready=1','acquire ready=1':'read data'}; route = ['write data']; route.append(edges[route[-1]]); route.append(edges[route[-1]]); route.append(edges[route[-1]]); print(' -> '.join(route))
write data -> release ready -> acquire ready=1 -> read data

演習完了