岩波講座 ソフトウエア科学6「オペレーティングシステム」#6

並列プロセス

プロセスがCPUディスパッチャーにより同時実行されると、互いに作用し干渉し合う。例えば主記憶やI/Oを取り合うかもしれないし、同一のファイルに同時に書き込もうとするかもしれない。

相互作用や干渉は、意図的/偶発的、協調的/競合的に起こり得る。

プロセス間の相互干渉は、正しい制御化におかないと好ましくない状況を招く。

プロセス間の相互干渉は、
* プロセス間通信
* プロセス同期
* プロセス統合
などとして研究されている。

プロセス間の相互交渉は3種に分類できる。
(1) 協調
    複数のプロセスが相互に情報交換を行いながら、共通の目的のために処理を進める。
(2) 競合
    リソースを取り合うといったように互いに他のプロセスの存在を意識しなくてはいけないが、自分の処理のためには他のプロセスは不要な場合。
(3) 干渉
    相手のプロセスの中断など、はっきりと他のプロセスに影響を与える場合。

例えば、整合性を保ってクリティカルセクションまたはクリティカルリージョンは、分割不可能にする必要がある。

クリティカルセクションは混合して実行されることがないようにする。これにより、共通変数の読み書きは1つのプロセスしか実行できないようになる。

共通変数へのアクセスを同時に1つのプロセスに限ることを排他制御または相互排除と言う。

2つのプロセスがメッセージをやりとりする機構を、メッセージ転送またはメッセージ交換と言う。

タイムシェアリングシステムでもマルチプログラミングシステムでも、他のプロセスを一時停止させる必要が生じることがある。例えばメモリーコンパクション(主記憶内の小さな空き領域を大きな空き領域にするために、主記憶内でプログラムを動かすこと)や、スワップアウトする場合である。

排他制御はプロセスの競合を正しく行うのに必要であり、次の3つの要求を満たさなくてはならない。
(1) クリティカルセクションを実行しているプロセスが1つもない時、クリティカルセクションに入る要求をしたプロセスは、ただちに許可を与えられなければならない。
(2) 2つ以上のプロセスがクリティカルセクションに入ろうと争っているR時、その選択は無期限に延期されてはならない(デッドロック防止)。
(3) いかなるプロセスも、あるプロセスがそのクリティカルセクションに入るのを無期限に妨げることはできない。すなわち、プロセスは皆クリティカルセクションに入る機会を公平に与えられるべきである(公平条件)。

排他制御を実現する方法は、ハードウェアに依存する。

排他制御を実現する方法の1つは、誰からクリティカルセクションに入っているというフラグを用意する方法であるが、フラグの上げ下げが共通変数の読み書きと同じ排他制御を必要としうまく行かない。

このような排他制御が再帰的に必要になるのは、ハードウェアが提供する基本的な排他制御の仕組みがないと解決しない。

基本的な排他制御を得るためのDekkerのアルゴリズムは、2つのプロセッサー上で2つのプロセスが動いている場合だけではなく、同一プロセッサー上で動く2つのプロセスでもラウンドロビン的に切り替えられていれば利用できる。またn個のプロセスに拡張することもできる。これは、STORE命令は割り込まれなく完了することが保証されていることに依存している。

Dekkerのアルゴリズムは、優先度やCPU数を考慮すると、アルゴリズムがかなり複雑になる問題がある。

Dekkerのアルゴリズムは、ビジーウェイティングでクリティカルセクションに入るのを待つのがCPU時間を浪費するので大きな問題となる。

よってDekkerのアルゴリズムやその変型・拡張は、実際には利用されない。実際には違う排他制御の方法がとられる。

ユニプロセッサーシステムの場合には、プログラムの実行が中断されるのは、割り込みが生じた時だけである。よってクリティカルセクションを割り込み禁止にすれば良い。割り込み禁止中に生じた割り込みは、禁止の解除後まで待たされる。

マルチプロセッサーシステムの場合には、割り込み禁止だけでは、排他制御を実現できない。

Test and Set (TS)またはSwap (SW)と言うハードウェア命令が必要となる。

TS命令もSW命令も実行は分割不可能でなくてはいならない。つまり、TSもSWも同時に1個のCPUでしか実行されないと、ハードウェアとして保証されなくてはならない。

TSもSWも他の命令の組み合わせで実現することができない。

TSまたはSWにより、再帰的に必要となる排他制御を止められる。

TS M, Rは、主記憶の番地Mの内容をレジスターRに入れ、Mに1を入れる。これでフラグを上げたことになり、STORE ZERO MでMに0を入れフラグを下げる。

SW M, Rは、主記憶の番地Mの内容をレジスターRに、Rの内容をMに入れる。これで、M≠0ならばフラグを上げていることになる。

フラグを上げる前に割り込みを禁止し、クリティカルセクションを実行して、フラグを下げた後に割り込み禁止を解除するのは、疑似デッドロックを防止するためである。

疑似デッドロックとは。CPUの数がプロセスの数よりも小さいとき、CPUがクリティカルセクション内にいる優先度の低い優先度のプロセスから取り上げられて、優先度の高いプロセスの排他制御待ちのループに割り当てられるが、低い優先度のプロセスがクリティカルセクションを出てMを0にしない限り、優先度の高いプロセスの待ちのループは終了せず、永久に待ちが解消しない現象のことである。

階層的に排他制御を利用すると、最も小さな(最も短い時間間隔の)排他制御を用いて、より長い時間間隔の排他制御を実現することで、最も小さな排他制御以外では、ビジーウェイティングを必要としないようにできる。