JD(情報系大学生)雑記

JD-情報系大学生-

OS学習メモ1 (2.1-2.4章)

※この記事は...強い人が読んでも特に得られるものは無いのですよ..(恐)

Operating Systems Design and Implementation(今後MINIX本と呼びます)、2章の読み終えた所までまとめてみました...というよりも、要点を自分の言葉で書いてぽんぽん配置しただけって言った方が正しいのかな...まぁ備忘録的な意味合いも込めて(1章は全体的な概要説明で、さらっと読んですぐに先に進んだので今回のまとめ範囲から外してます)。

前半部分は翻訳版を読んでたんですけど、日本語訳がわかりにくいという理由で後半は原著で読んでます。間違っているところなどあってもおかしくなさそうなので、何か気づいた方がいらっしゃれば教えてもらえると非常に助かります。

2章 プロセス

2.1 プロセス概念

「プロセス」は、あらゆるOSにおいて最も中心となる概念で、これは実行中のプログラムを抽象化したものである。近年のコンピュータは同時にいくつかのことを行うことができるが、厳密にはどの瞬間もCPUは一つのプログラムを(いくつかのプロセスを切り替えながら)実行していて、1秒間に複数のプログラムを処理することで並列処理のように見せている。

 

2.1.2 プロセスの生成

OSは必要に応じてプロセスを生成しなければならない。単純なシステムでは必要なプロセスを起動時に用意することができるが,汎用システムでは動作中に必要に応じてプロセスを生成(及び終了)する必要がある。

以下の4つの主要な事象に際してプロセスが生成される

システム初期化/実行中プロセスによるプロセス生成システムコール発行

ユーザからの新たなプロセス生成要求/バッチジョブの開始

OS起動時に生成されるプロセスは「フォアグラウンドプロセス」と「バッググラウンドプロセス」の2つに分かれる。前者はユーザとやり取りをしてユーザのために仕事をするもので、後者に関しては決まったユーザに関連付けられているわけではないが特定の機能を持っているプロセスである。

 

2.1.3 プロセス終了

プロセスの終了条件は以下のようなものがある

通常終了/エラー終了/致命的なエラーが発生した場合/他のプロセスによるkill命令

2.1.4 プロセス階層

いくつかのシステムでは、親プロセスがforkによって子プロセスを生成した時にそれらが何らかの関係で関連付けられている場合がある。

ブートイメージの中には2つの特別なスレッド、reincarnation serverとinitが存在している。前者はドライバ/サーバの再起動を再起動するためのもの(後述)。initは/etc/rcスクリプトを実行して再生サーバに指令を発行して、ブートイメージに含まれないドライバ/サーバを起動させる。従って、ドライバ/サーバのいずれかが終了をした場合は再生サーバに通知が届き、再生サーバは終了したプロセスを再起動することができる。この処理を終えるとinitは存在する端末や仮想端末を調べるため設定ファイルetc/ttytabを読み込む。各端末について、initはgettyプロセスをforkしてプロンプトを表示し入力を待つ。入力があるとgettyは入力されたユーザー名を引数にとってloginプロセスを起動する。ユーザがログインに成功すればloginはユーザのシェルを起動する。

2.1.5 プロセスの状態

プロセスはそれぞれプログラムカウンタやレジスタ,スタックなどの内部情報を持って独立しているが、場合によっては相互で作用,通信,同期する必要がある。この時、プロセスの実行速度の相違によっては「必要な入力データが存在しない」ということも起こり得る。この場合、入力データが利用可能になるまで他方の処理はブロックされる。プロセスがとり得る状態は実行状態/実行可能状態/ブロック状態の3つ。

 

2.1.6 プロセスの実装

プロセスモデルを実現するために、OSはプロセステーブルと呼ばれる構造体配列を管理する。ここに格納される情報は、プログラムを「実行中→実行可能状態」に切り替える時のプロセスの状態に関する情報、プログラムカウンタ、スタックポインタ、開いているプロセスに関する情報などなど。

 

個々のI/Oデバイスに関連付けられたテーブル上のデータ構造体を割り込みディスクリプタと呼ぶ。このテーブルの個々のエントリ(キーと値の組)の中で最も重要な部分は割り込みベクタと呼ばれ、割り込みサービス手続きのアドレスを格納している

 

MINIX(今回扱っている、Tanenbaumによって作られた教育用のOS)ではメッセージを介してプロセス間通信を行っている。メッセージによって、割り込み発生を”ユーザプロセスからのディスクブロック読み込み命令”とは区別できるような形で伝える。ディスクプロセスの状態は「ブロック中→実行可能状態」に変更されてスケジューラ(後述)が呼び出される。

 

2.1.7 スレッド

プロセスの持つ別の概念として、単にスレッドと呼ばれる制御の流れがある。

スレッドはプロセス中の実行単位であると言える。詳しくは別の所で。

 

2.2 プロセス間通信

プロセスは他のプロセスと頻繁に通信する必要がある。プロセス間通信における3つの問題は、どのように伝達するか/重大な作業をしている時にプロセスが高いの処理を妨害しあわないことの保証に関係すること/依存関係が存在する場合の適切な実行順序をどう決定するか である。

 

2.2.1 競合状態

OSではいくつかのプロセスが共通の記憶領域を共有することがある。2つ以上のプロセスが共有データを読み書きし、誰が(厳密に)先に実行したのかによって最終結果が異なってしまう状態を競合状態と呼ぶ。

 

2.2.2 クリティカルセクション

競合状態の回避に必要なのは相互排除、つまりあるプロセスが共有変数やファイル利用を使っている時に、別のプロセスが同じ作業を行わないようにすることである。共有メモリにアクセスするプログラム部分を危険領域/クリティカルセクションと呼ぶ。どの2つのプロセスも危険領域に同時に入らなければ競合状態は回避できる。

 

これによって競合状態は回避できるけれども、効率的に共有データを利用するためにはこれだけでは不十分なので、よりよい解決方法を得るためには更に3つの条件が必要になる

 

・処理速度やCPUの個数に関する仮定を作らない

・危険領域以外を実行しているプロセスは他のプロセスをブロックしない

・危険領域に入るために無期限に待たない

 

2.2.3 ビジーウエイトによる相互排除

相互排除を実現するためのいくつかの方式

 

割り込み禁止方式

一番手っ取り早いのがこれ。あるプロセスが危険領域に入ったら全ての割り込みを禁止して、危険領域から出る時に割り込みを許可し直す。ただ、ユーザに割り込み禁止権限を与えるのは良くない(ユーザプロセスが割り込みを禁止して二度と割り込みを許可しなかったらシステムはどうなってしまうのやら)。しかしカーネルにとっては、変数やリスト更新のための数命令の間だけ割り込みを禁止するのは都合がいい。まとめると、割り込み禁止はOS内で用いるには便利だけれどもユーザプロセスが使用する一般的な相互排除の仕組みとしては適さない。

 

ロック変数方式

危険領域に入っているプロセスの[ある/ない]を[0/1]の変数で管理する。

しかしこれにも問題もある。プロセスがロック変数を読み込んで0であることを認識し、そのプロセスがロックを1に設定しようとする前に別のプロセスがスケジュールされて実行して…なんてことが起こってしまうと2つのプロセスが同時に危険領域に入ることになる。

 

その他

厳密な相互実行方式

Petersonの解法

TSLを用いた解法 など

 

2.2.4 スリープとウェイクアップ

Pertersonの解法もTSLを用いた解法も本質は同じで、「プロセスが危険領域に入る前に進入が許可されているかを検査し、されていなければ許可されるまで検査を繰り返す」ということ(ビジーウエイト)。

 

2.2.5 セマフォ

ダイクストラによってセマフォと呼ばれる新たな変数の型が導入された。簡単に言うと、セマフォは利用可能な資源の数を表すための変数で、0ならば利用可能な資源がない状態で、1以上であればその数だけ資源が使えるといった具合になっている。セマフォ変数に対してはdownとupという2つの操作があって、down操作は”セマフォ変数の値がが0より大きければ値を1減らして処理を続行する”もので、仮にセマフォ変数が0であればプロセスはスリープする。反対にup操作はセマフォ変数を1増加させるもので、downを完了出来ずにスリープしている処理があればそれをシステムが選択してdownの完了を許可する。

 

 

少し飛んで…

 

 

2.4 スケジューリング

2.4.1  スケジューリング概論

2つ以上のプロセスが実行可能状態にあってCPUが1つしか利用できない場合、OSの中のスケジューラと呼ばれる部分がスケジューリングアルゴリズムを使って、どのプロセスを先に実行するかを決定する。

 

まず、スケジューリングが必ず必要になるのは以下の2つの場合

・プロセスが終了する時

・プロセスがI/Oやセマフォ待ちによってブロックする時

(これらの場合、最後に実行していたプロセスが実行可能状態にならないので、当然次に実行する他のプロセスを選ばなければならない。)

 

そして(これは必ずではないが)通常は以下の3つの場合でもスケジューリングが行われる。

・新しいプロセスが生成された時

・I/O割り込みが発生した時

・クロック割り込みが発生した時

クロック割り込みについて取り上げる。クロック割り込みは現在実行中のプロセスを長く実行し続けたかどうかを判断する機会になる。スケジューリングアルゴリズムは、クロック割り込みをどのように扱うかによって2つに分けられる。非プリエンプティブなスケジューリングアルゴリズムでは、実行中のプロセスがブロックするか自発的にCPUを手放すまでは実行を続ける。これに対してプリエンプティブなスケジューリングアルゴリズムでは、ある決まった時間の最大限までプロセスの実行を続ける。許される限界までの時間を実行し続けている場合プロセスは中断されスケジューラは他のプロセスを実行する。

 

異なる環境には当然異なるスケジューリングアルゴリズムが必要で、バッチシステム/対話型システム/リアルタイムシステムの3つの環境は区別すべきである。

 

バッチシステムには端末からの素早い応答を待っているユーザがいないため非プリエンプティブなアルゴリズム(かそれぞれのプロセスに長い時間間隔を与えるプリエンプティブなアルゴリズム)が適している。対話型なユーザがいる環境ではひとつのプロセスがCPUを独占して他のプロセスへのサービスを阻害しないようにするためにプリエンプティブなスケジューリングが必須。リアルタイムシステムでは、プロセスがそれほど長く実行しないことが分かっているためプリエンプティブなスケジューリングが必要とされない場合もある。

 

2.4.2 バッチシステムのスケジューリング

(到着順/最短ジョブ優先/残余処理時間順などの詳しい説明がありましたが情報処理技術者試験で結構詳しく勉強したのでさらっと目を通して次に行きました)

 

三段階のスケジューリング

バッチシステムは異なる3つの段階からなるスケジューリングと捉えることができる。

1.まずジョブが到着したら入力待ち行列に入り、受け入れスケジューラがどのジョブをシステムに受け入れるかを決める(残りは選択されるまで待ち行列に入ったまま)。

2.ジョブが受け入れられても、プロセスが多くて全てのプロセスを格納するだけの十分なメモリがなければ、いくつかのプロセスをディスクにスワップアウトする必要があり、これを決めるメモリスケジューラ。

3.主記憶にある実行可能状態のプロセスから、次に実行するものを選択する。これはしばしばCPUスケジューラと呼ばれ、スケジューラといえば通常はこれを意味することが多い。

 

2.4.3 対話型システムのスケジューリング

(対話型システムに用いられるアルゴリズムこれも流し読み..)

ラウンドロビン,優先度,複数キューなど

 

2.4.4 リアルタイムシステムのスケジューリング

リアルタイムシステムでは時間が重要な役割を果たしている。

一般的に、守らなければならない絶対的な時間制約があるハードリアルタイムと、ある程度ならば許容できるソフトリアルタイムに分類されるが、両方の場合において、プログラムを多数のプロセスに分割してそれぞれの動作を予測可能かつ事前にわかるようにすることで実現している

 

2.4.6 スレッドスケジューリング

複数のスレッドを持つプロセスがいくつかある場合、プロセスとスレッドという二段階の並列性が存在する。このようなシステムではユーザレベルのスレッドをサポートするかカーネルレベルのスレッドをサポートするかによってスケジューリングは大きく異なる。

 

ユーザレベルのスレッドスケジューリング

カーネルはスレッドの存在を感知しないので通常の処理を行う。つまりあるプロセスAを選択し、Aにクォンタム分の制御を与える(クォンタム:各プロセスに与えられる最大限の実行時間のこと)。クォンタムを使い切れば、プロセスAの内部で何が起こっているのかに関わらず(例えばプロセスAのスレッドA1だけが全てのクォンタムを消費するなど)、スケジューラは他のプロセスを実行する。

 

 

カーネルレベルのスレッドスケジューリング

スレッドにはクォンタムが与えられ、これを超過したスレッドは強制的に中断されるというもの

------------------------------------

もっと先の方まで既に読んでますが、内容的にもここが一番区切りがいいかなって思ったので今回はここまで。まさかこの程度で5千字になるとは思ってませんでした。

2.5章の中のMINIX OSの起動(MINIX3 startup)という所なんかは、以前少しだけかじった30日OS本の内容と重なる部分があって、読んでいてとてもワクワクしてました。どんどん読み進めていきます。