@@
lock( )の中で確保したい資源が「使用中」なら、一般的には、ビジーウェイ
トをするのではなくイベント待ち状態に入った(i.e.CPUを他のプロセスのた めに明け渡した)方がシステム全体の生産性が上がる。 (但し、待ちが短時間 で終わることが予め分かっている場合は、ディスパッチを伴う方法よりビジー ウェイトの方が効率的で用いられることもある。)
例 12.2 (排他制御の効率化) 例12.1において、確保したい資源が「使用中」の時イベン ト待ち状態に移る様にすると、次の様にデータ処理が進む。
共有データ (預金額)
プロセスA の遷移 プロセスB
(1)lock( ) ∼∼∼→ x
(2)預金額(x)の読み込み←−←− x
(3)預金引き落とし後の残 高を計算: y=x−d
⇓
(ディスパッチ) ⇓
⇓ ←∼∼∼(1)lock( )
⇓ (イベント待ち状態に)
(再開) ⇓
(4)共有データを更新 −→−→ y
(5)unlock( ) ∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼→ (再び実行可能状態に)
⇓ ←∼∼∼(2)再度 lock( )
⇓ −→−→(3)預金額(y)の読み込み
⇓ (4)預金預け入れ後の残高
を計算: z =y+a
z ←−←−(5)共有データを更新
(= x−d+a)
⇓ (6)unlock( )
...
処理効率も考慮に入れたlock( )とunlock( )の実装： 共有資源が使用中であることが判 明したら即座にイベント待ち状態に入り共有資源が空くのを待つ様にlock( )とunlock( ) を書き換えると次の様になる。
/* 大域変数 LOCK の初期設定 */
int LOCK = 0; /* LOCK==1 <==> 「使用中」 */
/* 関数 lock( ) の定義 */
void lock( ) {
if (LOCK != 0) { /* 資源が使用中なら即 */
make_block( ); /* イベント待ち状態へ */
}else if (compare_and_swap(LOCK) != 0) { /* atomic operationで */
make_block( ); /* 資源確保に失敗すると、イベント待ち状態へ */
12.4. 排他制御下でのシステムの効率的な運用 169
}else {
return; /* 資源確保に成功 */
} }
/* 関数 unlock( ) の定義 */
void unlock( ) {
LOCK = 0;
make_blocked_processes_ready( ); /* 資源が空くのを待っている */
} /* プロセスを実行可能状態に戻す */
'
&
$
% 注意：
高級言語風に処理の中身を書いたが、lock( )やunlock( )、もしくはこれと同 等以上の機能はOSがシステムコールとして提供するものである。
=⇒ • 実際にはlock( )やunlock( )はCS命令,TS命令,...等を用いて機械語で 実装される。
• 排他制御のために OS がどういうことを行っているかは、lock( )や unlock( )の処理の中身を通じて充分理解してほしい。
演習問題
□演習 12.3 プロセス間の排他制御が必要となる場合を例示せよ。
13 セマフォア — 同期制御の一般的・実際的な手法 —
• セマフォアを用いた排他制御(吉沢7.4.1–2節)
• デッドロックの回避(吉沢7.4.3–4節)
先の第12節においては共有資源が1個の場合にしぼって排他制御の基本的な考え方に ついて説明したが、ここでは共有資源が2 個以上の場合にも適用でき、実際に排他制御が 必要なときによく使われる、セマフォア(semaphore)と呼ばれる手法について説明する。
'
&
$
% 次の論文は
プロセス同期に関する古典的な文献で、その中でセマフォア,クリティカ ルセクションの問題,デッドロックの除去が議論されている。
E.W.Dijkstra(1968a), “Cooperating Sequential Processes,” in Program-ming Languages(F.Genuys, ed.), pp.43-112, Academic Press.
セマフォアの定義は次の論文の付録の中でも述べられている。
E.W.Dijkstra(1968b), “The Structure of the “THE”-Multiprogramming System,”Comm.ACMvol.11, No.5, pp.341-346.
補足：セマフォア· · · 鉄道で進入可能か否かを示す腕木信号機;
一般に旗・ライトなどによる信号装置;手旗信号
13.1 セマフォアとは何か
n吉沢7.4.1節, 前川3.3節, D.C.Tsichritzis
&P.A.Bernstein2.5.3節
o
次の2つの操作 P(sem), V(sem) によってのみ値が変更される、プロセス間に共通の
整数型変数を一般にセマフォア(semaphore)と呼ぶ。ここで、semはセマフォアで、空い ている共有資源の数を表す。
P(sem)操作： . . . (資源使用の申し出に対する処置) if (sem ≥ 1) {
(1)sem ← sem−1;
(2)return; /*P(sem)操作を呼んだ(i.e.今実行している)プロ*/
/*セスに資源を割当て、プロセスの処理を継続する*/
} else {
(1)このP(sem)操作を呼んだ(i.e.今実行している)プロセスを
(1.1)(semが関与する)共有資源の空きを待つ待ち行列に入れる;
(1.2)実行中から待ち状態に移す;
(2)制御をディスパッチャに渡す;
}
V(sem)操作： . . . (資源返却の申し出に対する処置)
if (共有資源の空きを待つプロセスがある) {
(1)その待ち行列からプロセスを1個取り出し実行可能状態にする;
/*返却された資源をこの取り出したプロセスに割り当てる*/
(2)V(sem)操作を呼んだ(i.e.今実行している)プロセスも 実行中から実行可能状態に移す;
(3)制御をディスパッチャに渡す;
} else {