Operating System Lecture 5/30

Operating System Lecture 5/30

先週の復習 -- Scheduling

宿題

情報工学実験Iの4.3 軽量プロセスの生成 課題11,12,13,14 を おこなうこと。この実験は Sun で行います。desgin1 または、 fish1 に rlogin して実験して下さい。レポートはメールで 

    Subject: Operating System Lecture 5/30
というように、課題を出した日付をサブジェクトに入れたメールで 提出して下さい。しめきりは、2週間後(6/12)とします。既にレポートで 提出した人は、そのむね同じサブジェクトのメールで連絡して下さい。

Process Synchronization

複数のプロセス(process)は、単一のプロセッサ(Processor)、また は、複数のプロセッサ上で動作している。このプロセスがおたがい に協調して動作するためには、なんらかの形で、プロセス同士のタ イミングをとる必要がある。これを、プロセスの同期 (Sychronization) と呼ぶ。

同期は、いろいろなレベルで行われる。

これらはお互いに独立なわけではない。より高いレベルのものが、より 低いレベルのものにより実装されるのが普通である。さまざまなレベルの 同期機構を使っても、個々のレベルでの干渉がないことが保証される 必要がある。しかし、それは自動的に保証されるわけではない。これらの 機構のユーザが、それぞれを正しく使う必要がある。特に、低いレベルの 実装はシステム全体のユーザに影響するので、完全なものである必要がある。



何故、同期が必要なのか?

プログラムが、要求された仕様を満たすことを consistent という。 一般的なConsistency は、並列に動作するプログラムが直列可能(Serializable)で ある場合にのみ得られる。並列環境下で直列可能性を保証するためには、 同期機構が必要となる。

要求仕様の例

以下のような例を考えてみよう。 

[操作A] 
a = count;
[操作B] 
count += 1;
[操作C] 
count = a;
これを複数のユーザ が同時に行うと困ったことが起きる。実際、 
count は 256
[操作A1]  by User A
[操作A2]  by User B
[操作B1]  by User A
[操作B2]  by User B
[操作C1]  by User A
[操作C2]  by User B
count は ?
これは、明らかにAやBが予期していたAが単独で操作ABCを 行う結果とは異なる。

操作 ABCのようなデータの変更のまとまりをというトランザクション(transaction)という。 トランザクションは、それを順番にやったようになって欲しい。それが 普通の直感である。この場合は、「1を加える」を2回おこなったのだから、 2だけ値が増えてほしい。これを直列可能性(Serializability)という。

直列可能性が成立していれば、プログラムはトランザクション の変更の積み重ねとなる。これは、トランザクションの積み重ねか らプログラム全体ができていることを意味する。これをプログラム の無矛盾性(Consistency)という。ある条件のもとでConsistencyと Serializabilityは同値であることが証明されている。



これは、a1a2,b1b2 の二つのトランザクションが、s1→ s2の順序 に依存するb1b2→ a1a2 という順序と、s2→ s3 によって生じるa1a2 → b1b2 という順序が矛盾していることから生じている。

前の人の値を上書きしているという単純なことだが、このよう に依存関係の矢印を書くことによって、より矛盾が明快になる。ま た、機械的に矛盾を見つける手順を提供することもできる。あたり 前のことを明確にすることがコンピュータサイエンスでは重要なこ とが多い。



さまざまな同期機構

並列システムでは、 Test-and-set または、read-modify-write というのが、ハードウェア レベルでは用いられている。これは、自分が書き込んだ値が相手に読まれる ことを保証している。これは、単なるatomic read, atomic write では 実現できない。これらを用いて、Critical Section や Semaphor, Monitor を実現することができる。

逐次システム上の疑似並列システムでは、割り込まれない区間である を作れば同期機構を作ることができる。これは、例えば割り込み禁止 やcritical sectionにより実現する。

Test-and-set などでの待ち合わせは、CPUがそこを繰り返し読むことで 行っても良い。これはspin-lockと呼ばれる。CPUを無駄に消費するが、 同期待ちからの回復は、これが一番高速である。複数のCPUが、協調して spin-lock を行うのはBarrier と呼ばれる。これらの同期機構は、thread level で、並列プログラムのPerformance tuning を行う時に 重要になる。

spin-lockでは無駄が大きくなる時には、プロセスを一旦、退避させる。 この退避を抽象化した機構が、Semaphor である。Semaphor には P動作とV動作がある。これは、Critical section へ入ることと 出ることに相当する。さらに、これを Monitor という形でより柔軟な 処理をおこなうことができる。Java などは言語レベルでCritical Section を採用している。(なぜ、Monitor を採用しなかったかは 謎である) 並列オブジェクト指向言語では、オブジェクトをMonitor として扱う。

Guard は、lock や critical section などと異なり複数の条件を 同時に待つことにより同期をおこなう。この機構は、より複雑な 同期状況を実装するのにすぐれている。つまり表現能力が高い 方法である。Unix の system call としては、select/listen というのが あり、これは一種の限られたGuradになっている。



Lock and Transaction

同期機構で実現したいのはConsistencyである。ただ、やみくもに同期機構を 使ってもConsistencyは得られない。例えば、lock によって直列可能性を 得るには、きまった方法によりlockをかける必要がある。一つのresource (資源)しかない場合には、lock は自明であるが、複数のresourceがある場合には、 lock をかける順序を工夫する必要がある。この問題は、データベースの 理論と同じ問題である。


Decd lock 閉塞

同期機構は、なんらかの待ちあわせを含む。この時に、いくつかのプロセスが 相互に待ちあわせてしまうことがある。これをDeck lockという。

問題1:

ある町のホテルの空室数をX、この町にいく飛行機の空席数をYとする。


以下のような操作を考えよう。 質問: さてSとTは、両方とも「飛行機の切符とホテルの予約」を取るという トランザクション(transaction)を実行したい。