OS学習メモ(MINIX本2.1-2.4章)
２章 プロセス
2.1 プロセス概念
「プロセス」は、あらゆるOSにおいて最も中心となる概念で、これは実行中のプログラムを抽象化したものである。近年のコンピュータは同時にいくつかのことを行うことができるが、厳密にはどの瞬間もCPUは一つのプログラムを(いくつかのプロセスを切り替えながら)実行していて、１秒間に複数のプログラムを処理することで並列処理のように見せている。
2.1.2 プロセスの生成
OSは必要となるプロセスを確実に生成するなにかしらの方法が要求される。単純なシステムでは、必要なプロセスを起動時に全て用意することができるが、汎用システムでは動作中に必要に応じてプロセスを生成（及び終了）しなければならない。
プロセス生成には以下の4つの事象が存在する
・システムの初期化
・実行中プロセスによるプロセス生成システムコール発行
・ユーザからの新たなプロセス生成要求
・バッチジョブの開始
(”システムの初期化”に関して、)OS起動時に生成されるプロセスは「フォアグラウンドプロセス」と「バッググラウンドプロセス」の２つに分かれる。前者はユーザとやり取りをしてユーザのために仕事をするもので、後者に関しては決まったユーザに関連付けられているわけではないが特定の機能を持っているプロセスである。ウェブページへの要求を受け付けたり、印刷処理のためにバックグラウンドで常駐しているプロセスのことを”デーモン”と呼ぶ。
2.1.3 プロセス終了
プロセスの終了条件は以下のようなものがある
通常終了/エラー終了/致命的なエラーが発生した場合/他のプロセスによるkill命令
2.1.4 プロセス階層
いくつかのシステムでは、親プロセスがforkによって子プロセスを生成した時にそれらが何らかの関係で関連付けられている場合がある。この子プロセスがさらにプロセスを生成することで、階層構造ができていく。
2.1.5 プロセスの状態
プロセスはそれぞれプログラムカウンタやレジスタ,スタックなどの内部情報を持って独立しているが、場合によっては相互で作用,通信,同期する必要がある。この時、プロセスの実行速度の相違によっては「必要な入力データが存在しない」ということも起こり得る。この場合、入力データが利用可能になるまで他方の処理はブロックされる。プロセスがとり得る状態は実行状態/実行可能状態/ブロック状態の３つ。
プロセスモデル: 「OSの最下層にスケジューラがあって、その上に様々なプロセスが存在している」という基本構造のこと。
--------------------
| p1 | p2| p3 | ←プロセス
--------------------
| スケジューラ |
--------------------
2.1.6 プロセスの実装
プロセスモデルを実現するために、OSはプロセステーブルと呼ばれる構造体配列(エントリテーブルという)を管理する。プロセスを”実行中”→”実行可能状態”に切り替える際、エントリに「プロセスの状態に関する情報、プログラムカウンタ、スタックポインタ、開いているプロセスに関する情報,etc...」といった、プロセス実行を再開するために必要な全ての情報を格納する。
個々のI/Oデバイス(ハードディスクや大麻など)に関連付けられたテーブル上のデータ構造体を”割り込みディスクリプタテーブル”と呼ぶ。このテーブルの個々のエントリ（キーと値の組）の中で最も重要な部分は割り込みベクタと呼ばれ、割り込みサービス手続きのアドレスを格納している。割り込みサービス手続きは、まず最初に実行中のプロセスのプロセステーブルのエントリに全レジスタを保存する。
割り込み発生時にOSが行う処理の概要(上から順番)
・ハードウェアがプログラムカウンタ等をスタックに積む
・ハードウェアが割り込みベクタの値をプログラムカウンタにロード
・アセンブリ言語の手続きがレジスタを保存
・アセンブリ言語の手続きが新しいスタックを設定する
・C言語の割り込みサービスルーチンがメッセージを作って送信
・メッセージ渡しコードが、メッセージを待つ受信側プロセスを”実行可能”にする
・スケジューラが次に実行するプロセスを決定する
・C言語の手続きがアセンブリコードにリターンする
・アセンブリ言語の手続きが、次に実行するプロセスの実行を開始する
2.1.7 スレッド
プロセスの持つ別の概念として、単にスレッドと呼ばれる制御の流れがある。
スレッドはプロセス中の実行単位であると言える。詳しくは別の所で。
2.2 プロセス間通信
プロセスは他のプロセスと頻繁に通信する必要がある。プロセス間通信における3つの問題は、どのように伝達するか/重大な作業をしている時にプロセスが互いの処理を妨害しあわないことを保証すること/依存関係が存在する場合の適切な実行順序をどう決定するか である。
2.2.1 競合状態
OSではいくつかのプロセスが共通の記憶領域を共有することがある。２つ以上のプロセスが共有データを読み書きし、誰が(厳密に)先に実行したのかによって最終結果が異なってしまう状態を競合状態と呼ぶ。
2.2.2 クリティカルセクション
競合状態の回避に必要なのは相互排除、つまりあるプロセスが共有変数やファイル利用を使っている時に、別のプロセスが同じ作業を行わないようにすることである。共有メモリにアクセスするプログラム部分を危険領域/クリティカルセクションと呼ぶ。どの2つのプロセスも危険領域に同時に入らなければ競合状態は回避できる。
これによって競合状態は回避できるけれども、効率的に共有データを利用するためにはこれだけでは不十分なので、よりよい解決方法を得るためには更に３つの条件が必要になる
・処理速度やCPUの個数に関する仮定を作らない
・危険領域以外を実行しているプロセスは他のプロセスをブロックしない
・危険領域に入るために無期限に待たない
2.2.3 ビジーウエイトによる相互排除
相互排除を実現するためのいくつかの方式
割り込み禁止方式
一番手っ取り早いのがこれ。あるプロセスが危険領域に入ったら全ての割り込みを禁止して、危険領域から出る時に割り込みを許可し直す。ただ、ユーザに割り込み禁止権限を与えるのは良くない（ユーザプロセスが割り込みを禁止して二度と割り込みを許可しなかったらシステムはどうなってしまうのやら）。しかしカーネルにとっては、変数やリスト更新のための数命令の間だけ割り込みを禁止するのは都合がいい。まとめると、割り込み禁止はOS内で用いるには便利だけれどもユーザプロセスが使用する一般的な相互排除の仕組みとしては適さない。
ロック変数方式
危険領域に入っているプロセスの[ある/ない]を[0/1]の変数で管理する。
しかしこれにも問題もある。プロセスがロック変数を読み込んで0であることを認識し、そのプロセスがロックを１に設定しようとする前に別のプロセスがスケジュールされて実行して…なんてことが起こってしまうと２つのプロセスが同時に危険領域に入ることになる。
その他
厳密な相互実行方式
Petersonの解法
TSLを用いた解法 など
2.2.4 スリープとウェイクアップ
Pertersonの解法もTSLを用いた解法も本質は同じで、「プロセスが危険領域に入る前に進入が許可されているかを検査し、されていなければ許可されるまで検査を繰り返す」ということ（ビジーウエイト）。
2.2.5 セマフォ
ダイクストラによってセマフォと呼ばれる新たな変数の型が導入された。簡単に言うと、セマフォは利用可能な資源の数を表すための変数で、0ならば利用可能な資源がない状態で、1以上であればその数だけ資源が使えるといった具合になっている。セマフォ変数に対してはdownとupという２つの操作があって、down操作は”セマフォ変数の値がが0より大きければ値を1減らして処理を続行する”もので、仮にセマフォ変数が０であればプロセスはスリープする。反対にup操作はセマフォ変数を1増加させるもので、downを完了出来ずにスリープしている処理があればそれをシステムが選択してdownの完了を許可する。
少し飛んで…
2.4 スケジューリング
2.4.1 スケジューリング概論
２つ以上のプロセスが実行可能状態にあってCPUが１つしか利用できない場合、OSの中のスケジューラと呼ばれる部分がスケジューリングアルゴリズムを使って、どのプロセスを先に実行するかを決定する。
まず、スケジューリングが必ず必要になるのは以下の２つの場合
・プロセスが終了する時
・プロセスがI/Oやセマフォ待ちによってブロックする時
（これらの場合、最後に実行していたプロセスが実行可能状態にならないので、当然次に実行する他のプロセスを選ばなければならない。）
そして（これは必ずではないが）通常は以下の３つの場合でもスケジューリングが行われる。
・新しいプロセスが生成された時
・I/O割り込みが発生した時
・クロック割り込みが発生した時
クロック割り込みについて取り上げる。クロック割り込みは現在実行中のプロセスを長く実行し続けたかどうかを判断する機会になる。スケジューリングアルゴリズムは、クロック割り込みをどのように扱うかによって2つに分けられる。非プリエンプティブなスケジューリングアルゴリズムでは、実行中のプロセスがブロックするか自発的にCPUを手放すまでは実行を続ける。これに対してプリエンプティブなスケジューリングアルゴリズムでは、ある決まった時間の最大限までプロセスの実行を続ける。許される限界までの時間を実行し続けている場合プロセスは中断されスケジューラは他のプロセスを実行する。
異なる環境には当然異なるスケジューリングアルゴリズムが必要で、バッチシステム/対話型システム/リアルタイムシステムの３つの環境は区別すべきである。
バッチシステムには端末からの素早い応答を待っているユーザがいないため非プリエンプティブなアルゴリズム(かそれぞれのプロセスに長い時間間隔を与えるプリエンプティブなアルゴリズム）が適している。対話型なユーザがいる環境ではひとつのプロセスがCPUを独占して他のプロセスへのサービスを阻害しないようにするためにプリエンプティブなスケジューリングが必須。リアルタイムシステムでは、プロセスがそれほど長く実行しないことが分かっているためプリエンプティブなスケジューリングが必要とされない場合もある。
2.4.2 バッチシステムのスケジューリング
（到着順/最短ジョブ優先/残余処理時間順などの詳しい説明がありましたが情報処理技術者試験で結構詳しく勉強したのでさらっと目を通して次に行きました）
三段階のスケジューリング
バッチシステムは異なる３つの段階からなるスケジューリングと捉えることができる。
1.まずジョブが到着したら入力待ち行列に入り、受け入れスケジューラがどのジョブをシステムに受け入れるかを決める（残りは選択されるまで待ち行列に入ったまま）。
2.ジョブが受け入れられても、プロセスが多くて全てのプロセスを格納するだけの十分なメモリがなければ、いくつかのプロセスをディスクにスワップアウトする必要があり、これを決めるメモリスケジューラ。
3.主記憶にある実行可能状態のプロセスから、次に実行するものを選択する。これはしばしばCPUスケジューラと呼ばれ、スケジューラといえば通常はこれを意味することが多い。
2.4.3 対話型システムのスケジューリング
(対話型システムに用いられるアルゴリズム。これも流し読み..)
ラウンドロビン,優先度,複数キューなど
2.4.4 リアルタイムシステムのスケジューリング
リアルタイムシステムでは時間が重要な役割を果たしている。
一般的に、守らなければならない絶対的な時間制約があるハードリアルタイムと、ある程度ならば許容できるソフトリアルタイムに分類されるが、両方の場合において、プログラムを多数のプロセスに分割してそれぞれの動作を予測可能かつ事前にわかるようにすることで実現している
2.4.6 スレッドスケジューリング
複数のスレッドを持つプロセスがいくつかある場合、プロセスとスレッドという二段階の並列性が存在する。このようなシステムではユーザレベルのスレッドをサポートするかカーネルレベルのスレッドをサポートするかによってスケジューリングは大きく異なる。
ユーザレベルのスレッドスケジューリング
カーネルはスレッドの存在を感知しないので通常の処理を行う。つまりあるプロセスAを選択し、Aにクォンタム分の制御を与える(クォンタム:各プロセスに与えられる最大限の実行時間のこと)。クォンタムを使い切れば、プロセスAの内部で何が起こっているのかに関わらず（例えばプロセスAのスレッドA1だけが全てのクォンタムを消費するなど）、スケジューラは他のプロセスを実行する。
カーネルレベルのスレッドスケジューリング
スレッドにはクォンタムが与えられ、これを超過したスレッドは強制的に中断されるというもの
