同期機構で実現したいのはConsistencyである。ただ、やみくもに同期機構を
使ってもConsistencyは得られない。例えば、lock によって直列可能性を
得るには、きまった方法によりlockをかける必要がある。一つのresource
(資源)しかない場合には、lock は自明であるが、複数のresourceがある場合には、
lock をかける順序を工夫する必要がある。この問題は、データベースの
理論と同じ問題である。
同期機構は、なんらかの待ちあわせを含む。この時に、いくつかのプロセスが 相互に待ちあわせてしまうことがある。これをDeck lockという。
問題1:
ある町のホテルの空室数をX、この町にいく飛行機の空席数をYとする。
一般的に複数のリソースを使うトランザクションでは、すべてをロ ックしてから処理をおこない、不要になったリソースからアンロッ クすることにより、矛盾を避けることができる。これを2 phase lock (2相ロック)という。しかし、2相ロックだけでは、デッドロックは、 避けることはできない。
読みだしの場合は、複数のプロセスから読みだしが あってもよい。これを利用して並列度を上げることが考えられる。 これを可能にするにはロックに段階をもうける。
ロックは結構難しい概念なので、より簡単な方法として、クライアント・ サーバモデルというのを使う場合がある。この場合は、サーバと呼ばれる プロセスを立ち上げ、サービスの要求はすべて、そこに転送される。 サービスは要求が到着した順に処理される。この時に、Unix では tcp socket と select というシステム・コールによりメッセージの選択が行われる。 この実験は後期のinfo2で行う。
この方法では、メッセージの到着順序により整合性が保たれる。しかし、 クライアント間の並列性がなくなるため、パフォーマンスは劣化する。
さらにこの欠点を緩和するために、サーバをマルチスレッド化すること
が行われている。この場合は、サーバ内部で同期機構をまた別に使う
必要がある。同期機構としてはセマフォやロックが使われる。
実際には、トランザクション一つにつきロックを一つだけとるような方法が 簡単であり効果的だ。しかし、この方法は一度にたくさんのアクセスが来る 場合には適さない。
もし、データのアクセス頻度が大きく、デッドロックは稀にしか起きない のならば、「取りあえずロックしていく。 ロックがとれないようだったら、しばらく待って、あきらめる」という方法が ある。(楽観的平行制御 Optimistic Concurrency Control)
この場合、あきらめたトランザクションは、今まで行った作業の取り消し をおこなう必要がある。これをトランザクションの アボート(abort)という。 アボートは、ディスクアクセスなどに失敗した場合、その他、 アプリケーションの都合によっても起きる。
例
前の例題で、飛行機だけ予約が取れても、ほてるだけ予約が取れても、役に たたない。もし、それぞれの残りが一つの場合、SとTが飛行機とホテルを別々に 予約できてしまう。(そして、お互いにキャンセル待ちに入る...) そうしない ためには、飛行機とホテルをセットにすれば良かった。
セットにしない場合でも、飛行機とホテルの予約をとって、どちらかが
取れなかったらアボートするという方法でも良い。この時にも、予約の
順序を決めると、それぞれが一つづつ残っているのに誰も予約できなかった
というようなこと防ぐことができる。
2相ロックを使っていれば、通常はロックによるアボートでは、 カスケーディングアボートは起こらない。しかし、その他の要因による アボートではカスケーディングアボートが無制限に起きる可能性がある。
これを防ぐには、2相ロックの解除を徐々にではなく、一度に行えば 良い。(狭義の2相ロック) しかし、この方法もアクセス頻度が大きい場合には並列度を 下げるので嫌われることが多い。
普通、データベースシステムは、どのトランザクションがコミットしたか を記録している。これはログ(log)と呼ばれる。 何もしなければログは どんどん大きくなっていく。カスケーディングアボートに備えるために、 ずーとログを取っておかなくてはならないからである。
ある時点で、データベースの状態をとっておき、それを正規の状態 と決めれば、その時点より前のログを取っておく必要はない。それは バックアップ(backup)と呼ばれる。バックアップの後は、明示的に トランザクションログを消さなくてはならないデータベースも多い。
Unix には、sync というコミットに近い動作がある。これは、 アプリケーションからは書き込みは終わっているが、OSはディスクに データを書き込んでいない状態を解消する。したがって、Unix上の ファイルシステムをもとにしたデータベースは本当の意味で安全になることは ない。多くのデータベースではファイルシステムを経由せずに直接 ディスクを操作することでこれを回避している。
C で書いた flock_test.c または、 Perlで書いた, flock_test.pl を 用いて、この授業のデッドロックを再現してみよ。また、2相ロッ クに書き直して実行してみよ。また、2相ロックで、さらにデッドロック する例をリソースを3つ以上使って作ってみよ。
レポートはメールで
Subject: Report on Operating System Lecture 6/5
というように、課題を出した日付をサブジェクトに入れたメールで
提出して下さい。
6/12金曜日は、マルチメディア・フェアがあるので休講とします。 2年生はコンベンションセンタで行われるマルチメディア・フェアに 参加すること。