Operating System Lecture 12/04

Menu Menu

先週の復習

Process Synchronization

Lock and Transaction

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

Decd lock 閉塞

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

問題ある町のホテルの空室数をX、この町にいく飛行機の空席数をYとする。 以下のような操作を考えよう。

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

一般的に複数のリソースを使うトランザクションでは、すべてをロックしてから処理をおこない、不要になったリソースからアンロックすることにより、矛盾を避けることができる。これを2 phase lock (2相ロック)という。しかし、2相ロックだけでは、デッドロックは、避けることはできない。

読みだしの場合は、複数のプロセスから読みだしがあってもよい。これを利用して並列度を上げることが考えられる。これを可能にするにはロックに段階をもうける。

shared lock どうしは、複数同時にかかる。しかし、exclusive lockは、shared lock , exclusive lock ともにlockする。

select/client/server

ロックは結構難しい概念なので、より簡単な方法として、クライアント・サーバモデルというのを使う場合がある。この場合は、サーバと呼ばれるプロセスを立ち上げ、サービスの要求はすべて、そこに転送される。サービスは要求が到着した順に処理される。この時に、Unix ではtcp socket とselect というシステム・コールによりメッセージの選択が行われる。

この方法では、メッセージの到着順序により整合性が保たれる。しかし、クライアント間の並列性がなくなるため、パフォーマンスは劣化する。

さらにこの欠点を緩和するために、サーバをマルチスレッド化することが行われている。この場合は、サーバ内部で同期機構をまた別に使う必要がある。同期機構としてはセマフォやロックが使われる。

アボート

多数のユーザがデータベースにアクセスする時に、2相ロックを使うとデータベースの矛盾を防ぐことができる。しかし、デッドロックは防ぐことができない。ロックするデータに順序付けをすればデッドロックは防ぐことができるが、平行実行の制限が大きくなるのと、データの順序づけが難しいので、あまり好まれない。

実際には、トランザクション一つにつきロックを一つだけとるような方法が簡単であり効果的だ。しかし、この方法は一度にたくさんのアクセスが来る場合には適さない。

もし、データのアクセス頻度が大きく、デッドロックは稀にしか起きないのならば、「取りあえずロックしていく。ロックがとれないようだったら、しばらく待って、あきらめる」という方法がある。(楽観的平行制御 Optimistic Concurrency Control)

この場合、あきらめたトランザクションは、今まで行った作業の取り消しをおこなう必要がある。これをトランザクションの アボート(abort)という。アボートは、ディスクアクセスなどに失敗した場合、その他、アプリケーションの都合によっても起きる。

例前の例題で、飛行機だけ予約が取れても、ほてるだけ予約が取れても、役にたたない。もし、それぞれの残りが一つの場合、SとTが飛行機とホテルを別々に予約できてしまう。(そして、お互いにキャンセル待ちに入る...) そうしないためには、飛行機とホテルをセットにすれば良かった。

セットにしない場合でも、飛行機とホテルの予約をとって、どちらかが取れなかったらアボートするという方法でも良い。この時にも、予約の順序を決めると、それぞれが一つづつ残っているのに誰も予約できなかったというようなこと防ぐことができる。

カスケーディングアボート

一つのトランザクションがアボートしたとする。もし、そのトランザクションのデータを他のトランザクションが使っていたとすると、そのトランザクションはだめになってしまう。つまり、そのトランザクションもアボートしなければならない。このようにアボートが連鎖的に起こることをカスケーディングアボート(Cascading Abort)という。

2相ロックを使っていれば、通常はロックによるアボートでは、カスケーディングアボートは起こらない。しかし、その他の要因によるアボートではカスケーディングアボートが無制限に起きる可能性がある。

これを防ぐには、2相ロックの解除を徐々にではなく、一度に行えば良い。(狭義の2相ロック)しかし、この方法もアクセス頻度が大きい場合には並列度を下げるので嫌われることが多い。

コミットとログ

アボートは、トランザクション自身が指示することもできる。SQL文では、という操作によって行う。

普通、データベースシステムは、どのトランザクションがコミットしたかを記録している。これはログ(log)と呼ばれる。 何もしなければログはどんどん大きくなっていく。カスケーディングアボートに備えるために、ずーとログを取っておかなくてはならないからである。

ある時点で、データベースの状態をとっておき、それを正規の状態と決めれば、その時点より前のログを取っておく必要はない。それはバックアップ(backup)と呼ばれる。バックアップの後は、明示的にトランザクションログを消さなくてはならないデータベースも多い。<P>

Unix には、sync というコミットに近い動作がある。これは、アプリケーションからは書き込みは終わっているが、OSはディスクにデータを書き込んでいない状態を解消する。したがって、Unix上のファイルシステムをもとにしたデータベースは本当の意味で安全になることはない。多くのデータベースではファイルシステムを経由せずに直接ディスクを操作することでこれを回避している。

Unixでのロック

問題

C で書いたflock_test.c または、 Perlで書いた,flock_test.pl を 用いて、この授業のデッドロックを2相ロックで再現してみよ。また、2相ロックでない場合に矛盾が生じる例を示せ。(注) sleep などを使わないとうまくdead lock しないことがある。

宿題

情報工学実験Iのプロセスの同期 (5,6) を再来週までに行うこと。レポートはメールで 

    Subject: Report Operating System Lecture 12/04
というように、課題を出した日付をサブジェクトに入れたメールで提出して下さい。

Shinji KONO / Tue Dec 4 13:15:53 2001