←講義のツボメニューへ
←ＯＳ論シラバスへ プロセス
【2001.10.22,10.26】【第７、８回】Ｐｅｔｅｒｓｏｎのアルゴリズム
・オランダの数学者Ｔ．ＤＥＫＫＥＲは、相互実行とロックのアイディアをあわせて、厳密な相互実行を必要としない方法を考案（１９６５）
・１９８１年、Ｇ．Ｌ．Ｐｅｔｅｒｓｏｎは、もっと簡単な解決方法を発見した
・クリティカルセクションに入る前にenter_regionを呼ぶ
・クリティカルセクションを出たらleave_regionを呼ぶ
#define FALSE 0
#define TRUE 1
#define N 2
int turn; /*誰の番か？*/
int interested[N]; /*初期値はすべて 0(FALSE)*/
void enter_region(int process)
/* processは、入るプロセスの番号 */
{
int other; /*他のプロセスの番号*/
other=1^precess; /*排他的論理和でビット反転*/
interested[process]=TRUE;
turn=process;
while(turn == process && interested[other] == TRUE);
}
void leave_region(int process)
{
ineterested[process]=FALSE;
/*クリティカルセクションから出る*/ }
Ｔｅｓｔ ａｎｄ Ｓｅｔ Ｌｏｃｋ命令（ＴＳＬ命令）
多くのコンピューター（特にマルチプロセッサを念頭において設計されたコンピューター）には
以下の動作をするＴＳＬ命令が用意されている
１、あるアドレスのメモリのワードの内容を１つのレジスタに読み込む。
２、非ゼロの値を、そのアドレスのメモリに格納する。
読み込みと格納の操作は分割されないことが保証される。
ＴＳＬ命令を使ったロック
架空の（だが典型的な）アセンブリ言語による方法
enter_region:
ts1 register, flag /* flagの内容をregisterへ読み取り、flagを1にセット */
cmp register, #0 /* flagが0か判定する */
jnz enter_region /* 0でなければ、ロックされているのでループする */
ret /* 呼び出し元に戻り、クリティカルセクションに入る */
leave_region:
mov flag, #0 /* flagに0を格納 */
ret /* 呼び出し元に戻る */
優先度逆転問題（ｐｒｉｏｒｉｔｙ ｉｎｖｅｒｓｉｏｎ ｐｒｏｂｌｅｍ）
ビジーウェイト＝密なループを実行しながら待機する。
●ＣＰＵ時間を消費する
●予期せぬ結果を生む・・・優先度逆転問題
仮定）プロセスＨは、プロセスＬよりもスケジュールの優先度が高いとする セマフォ（ｓｅｍａｐｈｏｒｅ）
↓
どちらもReady(or Running)ならば、プロセスＨをスケジュールする
↓
プロセスＨ プロセスＬ Block
ReadyRunning
↓
クリティカルセクション≪プロセス切り替え≫ Running
busy wait
プロセスＬがクリティカルセクションから
出るのを待ちつづけるReady
プロセスＨが優先度が高いので、
スケジュールされない。
よって、クリティカルセクションから出ない従ってこのままの状態で凍りつく。
Ｅ．Ｗ．Ｄｉｊｋｓｔｒａが導入（１９６５）
★セマフォ =ｗａｋｅｕｐすべきプロセスの個数を表す整数変数
二つの操作「ｕｐ］と「ｄｏｗｎ」（←ｗａｋｅｕｐとｓｌｅｅｐを一般化）
2章終了 レポート課題
１、競合状態とは何か。
２、使用中待機（ビジーウェイト）とブロックとの違いを説明せよ
３、割り込みを無効にできるＯＳでは、どのようにセマフォを実装するのか、その概略を説明せよ
４、ラウンド・ロビン・スケジューリングは、一般に実行可能なプロセスのリストを管理している。リストにはそれぞれのプロセスが１回しか出現しない。プロセスがリスト中に２回出現した場合には何が発生するか。これを可能にする理由としてなにが考えられるか。
５、たいていのラウンド・ロビン・スケジューラーは、クォンタムの大きさに一定のものを使用している。小さなクォンタムが有利である点、大きなクォンタムが有利である点を議論せよ。
６（この問題は必須ではない）
ＡからＥまでの５つのバッチジョブが、ほぼ同時にコンピューター・センターに到着する。各実行時間は、１０分、６分、２分、４分、８分と予想された。これらの優先順位はそれぞれ、３，５，２，１，４と指定されており、５が最も高い優先順位である。次に示すスケジューリング・アルゴリズムの、プロセス・ターンアラウンド・タイムの平均を求めよ。なお、プロセスの切り替えオーバーヘッドは無視せよ。
（ａ）ラウンド・ロビン
（ｂ）優先順位スケジューリング
（ｃ）到着順サービス
（ｄ）最短ジョブ優先
６ａではシステムは多重プログラミングであり、それぞれのジョブはＣＰＵを平等に共有するものとする。６ｂから６ｄについては、一度に１つのジョブのみを完了するまで実行するものとする。すべてのジョブは完全にＣＰＵがネックとなっているものとする。