2.3
相互排他を行う方法
相互排他を行う方法として、以下の5つがある。
割り込み（ハード）
割り込みを不許可にしてシステムクロックを止め、スケジューラが呼ばれないようにする。
少しでも間違えると、システムダウンを引き起こす。
ロック変数（ソフト）
ロック用に変数を用意したところで、タイミングによっては相互排他が行えないため、意味がない。
完全な交互実行（スピンロック）
LinuxではCPU間の排他制御を行うために、スピンロックが使用される。
待ち時間が短いのが特徴だが、時間がかかるような処理にはCPUが常にフルで動作してしまうので用いてはいけない。
Peterson
ロック変数と完全な交互実行を組み合わせたもの。
''TSL（Test and Set Lock）命令''
1回の命令で、比較と値のセットを行う。（atomic）
regをレジスタ、LOCKを適当なメモリのアドレスとした場合、ロックとアンロックのアセンブラによるコードは以下の通り。
ロック
lock:
tsl reg, [LOCK] # regにLOCKの値を代入し、LOCKに1を代入。アトミックな処理。
cmp reg, 0 # regと0を比較。
jne lock # regが0でなかったら、lockへ飛ぶ。（ロックを取得するまでループする。）
ret # ここまで来れたということは、ロックを取得できたということ。
アンロック
unlock:
mov [LOCK], 0 # LOCKに0を代入し、ロックを解放する
ret
sleep/wakeup
優先度が低いプロセスがビジーウェイトのために、優先度が高いプロセスよりもCPUパワーを消費してしまう「優先度逆転問題」が生じてしまうことがある。
さらにビジーウェイトは、無限ループを用いているためCPUに優しくない。
そこでシグナル機構を用いて、リソースを得たときと解放した時に、それぞれプロセスをsleep/wakeup方法を用いれば、CPU時間を消費せずに相互排他が行える。
しかしsleepする前に、タイミングが悪くスケジューラが起動して別のプロセスに切り替わり、wakeupしているプロセスに対してwakeupシグナルを送ってしまうと、シグナルを紛失してしまう可能性がある。
セマフォ
TSLもビジーウェイトの一種である。
そこで、TSLとsleep/wakeupの方法を組み合わせたセマフォと言う排他機構が考えられた。
セマフォはカウンタを持ち、リソースを要求するプロセスがdownシステムコールを呼び出した時にカウンタが0であれば、呼び出したプロセスはブロックされる。
リソースを解放するにはupシステムコールを呼び出す。
そしてupシステムコールの結果、カウンタが1以上になると、ブロックされていたプロセスに対してウェイクアップ処理が行われる。
セマフォの中でも、カウンタが0または1のみの値しか取らないものを、バイナリセマフォと言う。
セマフォには相互排除として使われるが、プロセス間の同期をとるためにも使われる。
mutex
mutexという、0以外の場合にロックを示す機構がある。
mutexは「スレッド間の排他制御」に使われるのに対し、セマフォは「プロセス間の排他制御」に使われる。
あるスレッドがビジーウェイトになっていると、セマフォを用いた場合ではプロセス全体がスケジュールされてしまい、実行できる他のスレッドの処理が行えないが、mutexであれば他のスレッドが実行権を得ることができる。
さらにmutexはユーザ空間に置かれるため、カーネル空間のコードを呼び出す必要がなく、処理が速い。
しかしアドレス空間が異なるプロセス間同士では、mutexによる排他制御は行えない。
セマフォとミューテックスの違いは、OSの実装により異なる。しかし共通して言えるのは、ミューテックスを扱うのはセマフォを扱うよりも簡単であると言うことである。
モニタ
Javaのsynchronizedように、コンパイラが相互排他の機構を用意しているもの。
セマフォを用いた時に比べて、メソッドや関数単位で相互排他できるので、並列プログラミング時の問題を少なくすることができる。
ただし、モニタをサポートしているプログラミング言語しか使用できない。
メッセージ通信
送信者はIDをつけてメッセージを送り、受信者はメッセージを受け取ったら、受信通知を送信者に送ることでメッセージの紛失をなくす。
セマフォやモニタに比べて、プロセス間でメッセージのコピーを行うため、重い処理となっている。
メッセージ通信の仕方としては、以下の3つの方法がある。
- プロセスごとにアドレスをつけ、このアドレスに対してメッセージを送る（書き込む）
- メールボックス（メールボックスが空のときには受信者はブロックされる）
- ランデブー（メールボックスなしで直接やり取りを行い、send()の前にreceive()が来たらブロックされる）
バリア
全てのプロセスがある特定の場所まで到着するのを待ち、全てのプロセス到着後に次の処理へ移る。（GPUの処理と似ている？）
2.4 古典的プロセス間通信問題
哲学者の食事問題
相互排他・デッドロックの理解をしやすくするためによく取り上げられる問題。
reader, writer問題
データベースのシステムでは、データの更新をしないreaderは何人いても大丈夫なので、何人でもアクセスすることができる。
しかしreaderが多いと、writerがアクセスする余地がなくなる。
これを、reader, writer問題と言う。
解決法としては、アクセスする人をqueueにpushしていき、writerがreaderに割り込まれないようにすることが挙げられる。
眠る理髪師問題
reader, writer問題と同様、IPC分野でよく取り上げられる問題。
2.5 スケジューリング
多くのシステムでは、プロセスの切り替え時にキャッシュを無効化するように実装されている。
プロセスの挙動
- CPUの処理が大部分を占める「CPUバウンド」
- 多数の入出力待ちが生じる「入出力バウンド」
スケジュールを行うタイミング
- プロセスの生成/終了
- セマフォなどでプロセスがブロックされた時
- 入出力割り込みが生じた時
スケジューリングの種類
横取りスケジューリング
時分割式でクロックが必要。
会話型/リアルタイム処理に対して使われる。
横取りなしスケジューリング
自発的に実行をやめるかブロックが中心。
バッチ処理に対して使われる。
スケジューリングアルゴリズムの目標
共通
公平性、バランス
バッチ
高スループット、高CPU使用率
会話型
高い応答性、ユーザの期待に応える
リアルタイム
デッドライン、予測が可能
データセンターなどの指標にCPU使用率（稼働率）を用いることはナンセンスである。
重要なのは、スループットとターンアラウンド時間（システムに処理要求を送ってから、結果が出力されてくるまでの時間）である。
また、要求する計算時間と応答時間の釣り合いが取れていることを示す、「比例制」も重要である。
バッチシステムでのスケジューリング
到着順
最短ジョブ優先
最小残り時間優先
3レベルスケジューリング
3段階のスケジューラから構成されている。
1段階目は「アドミッションスケジューラ」と呼ばれ、CPU/入出力バウンドをうまく区別して、効率よくプログラムの実行が行えるようにシステムに投入するジョブを決定する。
2段階目は「メモリスケジューラ」で、1段階目で採用したジョブの中から、メモリに置くプログラムを決定する。
3段階目は「CPUスケジューラ」で、2段階目でメモリに置かれたものから、実行すべきプロセスを決定する。
会話型システムのスケジューリング
2レベルスケジューリング
バッチシステムと違ってジョブの概念が無いため、「3レベルスケジューリング」の1段階目は不要になり、「2レベルスケジューリング」となる。
ラウンドロビン
一定時間（クォンタム）経過または他プロセスのブロックでプロセスが切り替わる。
優先度
複数キュー
ラウンドロビン方式にクォンタムの動的変更を加えたもの。
最短プロセス優先
保証
ユーザと事前に性能面で約束を決め、その約束に基づいたスケジューリングを行う。
富くじ
全プロセスに対して、CPUを利用することのできるチケットの抽選を行う。
各プロセスは、抽選で取得したチケット数に比例した時間だけ、CPU時間を使用することができる。
公平共有
ユーザごとにCPU利用可能時間を設定する。
リアルタイムシステムでのスケジューリング
ハードリアルタイム
期限を絶対に守る必要がある。
ソフトリアルタイム
期限を守らなくてもある程度は許容できる。
スレッドに対するスケジューリング
ユーザレベル
性能は◎、特定のスレッドがIO待ちになると、プロセス全体がサスペンド状態になってしまう。
特定のアプリに特化して性能を出す時に利用する。
カーネルレベル
性能は△、特定のスレッドがIO待ちになっても、動作可能な他のスレッドが実行できる。
最終更新：2013年03月07日 23:05
