Operating System Lecture No.6
Menu
software pipeline
通信の読み込み、処理、書き出しと、さまざまな段階を平行に実行することにより、応答速度は変わらないが、スループットを上げることができる。
SEDA (staged event-driven architecture)
future
結果を本当に必要になったところで、まだ、結果が来てなかったら待ちに入る。
待ち状態の実現
待ち状態は CPU を使用しないので、Kernel にCPU資源を返す必要がある。これにはコストがかかる。
user level での同期
返さないで、その場でループしても良い。(busy wait) コストは安いし、応答は早いが、CPU資源を無駄にしてしまう。
CAS (check and set)
並行に動いている同士で同期するための primitive 。
check set __sync_fetch_and_add(&sem->value,1);
Kernel の中でのCASの実装
kernel 内部で CAS を実現しているところを調べる。
シングルプロセッサでは同期は、
割込み禁止 同期用データの変更 割込み許可で良い。システムコールをすると自動的に割込み禁止になるプロセッサが多い。
マルチプロセッサでは、プロセッサに付属する特殊命令を使う。
IA32 lock prefix inc などのread modify write 命令 test & set primitive
lock free data structure
終了判定
POSIX thread 上の synchronized queue
lock system call はセマフォとも呼ばれる。セマフォには、P命令とV命令がある。これに挟まれた部分は、自分だけで独占的に実行できる。
P命令 きわどい部分 (critical section) V命令pthreadのセマフォは、
P命令 pthread_mutex_lock(pthread_mutex_t *mutex); V命令 pthread_mutex_unlock(pthread_mutex_t *mutex);となってる。それぞれの引数は、初期化されたセマフォへのポインタである。
Binary Semaphor と条件付変数を使った Count Semaphor
バイナリセマフォでは、P命令を実行して通過できるのはただ一つのprocess/thread だけである。しかし、資源がただ一つだけなく複数ある時には、複数のプロセスがP命令を実行できても良いと考えられる。この場合、P命令が消費に相当し、V命令が生産に相当する。この場合は、P命令を実行した回数とV命令を実行した回数は、最大N 個の差まで容認される。このようなセマフォを計数セマフォ(counting semaphor)という。
問題6.1
Rustの並行実行問題6.2
golang で Semaphor を実装してみるDecd lock 閉塞
同期機構は、なんらかの待ちあわせを含む。この時に、いくつかのプロセスが相互に待ちあわせてしまうことがある。これをDeck lockという。問題ある町のホテルの空室数のデータベースをHotel、この町にいく飛行機の空席数のデータベースをPlaneとする。 以下のような操作を考えよう。
- S-reserve-Hotel --- Sがホテルの予約を取る
- T-reserve-Hotel --- Tがホテルの予約を取る
- S-reserve-Plane --- Sが飛行機の予約を取る
- T-reserve-Plane --- Tが飛行機の予約を取る
- S-lock-Hotel --- SがHotelをロックする
- T-lock-Hotel --- TがHotelをロックする
- S-lock-Plane --- SがPlaneをロックする
- T-lock-Plane --- TがPlaneをロックする
- S-releasse-Hotel --- SがHotelをロック解除する
- T-releasse-Hotel --- TがHotelをロック解除する
- S-releasse-Plane --- SがPlaneをロック解除する
- T-releasse-Plane --- TがPlaneをロック解除する
例えばTがHotel 予約するためには、
- T-lock-Hotel --- TがHotelをロックする
- T-reserve-Hotel --- Tがホテルの予約を取る
- T-releasse-Hotel --- TがHotelをロック解除する
質問: さてSとTは、両方とも「飛行機の切符とホテルの予約」を取るというのを一つトランザクション(transaction)を実行したい。(片方だけ成功しても意味がない...)
- (1) この二つのトランザクションがデッドロック(dead lock)する操作の順序を示せ
- (2) デットロックしないようにするには、うまく順序を付けてロックしてやれば良い。どうすれば良いか説明せよ。
- (3) デットロックしないtrivialでない実行例を示せ。
2相ロック
一般的に複数のリソースを使うトランザクションでは、すべてをロックしてから処理をおこない、不要になったリソースからアンロックすることにより、矛盾を避けることができる。これを2 phase lock (2相ロック)という。つまり
資源1を lock 資源2を lock ... 資源1を unlcok 資源2を unlockとするのが2相ロックである。
デッドロック
しかし、2相ロックだけでは、デッドロックは、避けることはできない。読みだしの場合は、複数のプロセスから読みだしがあってもよい。これを利用して並列度を上げることが考えられる。これを可能にするにはロックに段階をもうける。
- shared lock
- exclusive lock
select/client/server
ロックは結構難しい概念なので、より簡単な方法として、クライアント・サーバモデルというのを使う場合がある。この場合は、サーバと呼ばれるプロセスを立ち上げ、サービスの要求はすべて、そこに転送される。サービスは要求が到着した順に処理される。この時に、Unix ではtcp socket とselect というシステム・コールによりメッセージの選択が行われる。この方法では、メッセージの到着順序により整合性が保たれる。しかし、クライアント間の並列性がなくなるため、パフォーマンスは劣化する。
さらにこの欠点を緩和するために、サーバをマルチスレッド化することが行われている。この場合は、サーバ内部で同期機構をまた別に使う必要がある。同期機構としてはセマフォやロックが使われる。
アボート
多数のユーザがデータベースにアクセスする時に、2相ロックを使うとデータベースの矛盾を防ぐことができる。しかし、デッドロックは防ぐことができない。ロックするデータに順序付けをすればデッドロックは防ぐことができるが、平行実行の制限が大きくなるのと、データの順序づけが難しいので、あまり好まれない。実際には、トランザクション一つにつきロックを一つだけとるような方法が簡単であり効果的だ。しかし、この方法は一度にたくさんのアクセスが来る場合には適さない。
もし、データのアクセス頻度が大きく、デッドロックは稀にしか起きないのならば、「取りあえずロックしていく。ロックがとれないようだったら、しばらく待って、あきらめる」という方法がある。(楽観的平行制御 Optimistic Concurrency Control)
この場合、あきらめたトランザクションは、今まで行った作業の取り消しをおこなう必要がある。これをトランザクションの アボート(abort)という。アボートは、ディスクアクセスなどに失敗した場合、その他、アプリケーションの都合によっても起きる。
例前の例題で、飛行機だけ予約が取れても、ほてるだけ予約が取れても、役にたたない。もし、それぞれの残りが一つの場合、SとTが飛行機とホテルを別々に予約できてしまう。(そして、お互いにキャンセル待ちに入る...) そうしないためには、飛行機とホテルをセットにすれば良かった。
セットにしない場合でも、飛行機とホテルの予約をとって、どちらかが取れなかったらアボートするという方法でも良い。この時にも、予約の順序を決めると、それぞれが一つづつ残っているのに誰も予約できなかったというようなこと防ぐことができる。
カスケーディングアボート
一つのトランザクションがアボートしたとする。もし、そのトランザクションのデータを他のトランザクションが使っていたとすると、そのトランザクションはだめになってしまう。つまり、そのトランザクションもアボートしなければならない。このようにアボートが連鎖的に起こることをカスケーディングアボート(Cascading Abort)という。2相ロックを使っていれば、通常はロックによるアボートでは、カスケーディングアボートは起こらない。しかし、その他の要因によるアボートではカスケーディングアボートが無制限に起きる可能性がある。
これを防ぐには、2相ロックの解除を徐々にではなく、一度に行えば良い。(狭義の2相ロック)しかし、この方法もアクセス頻度が大きい場合には並列度を下げるので嫌われることが多い。
コミットとログ
アボートは、トランザクション自身が指示することもできる。SQL文では、- commit work (トランザクションがちゃんと終わったことを示す)
- rollback (トランザクションは失敗して、なかったことにする)
普通、データベースシステムは、どのトランザクションがコミットしたかを記録している。これはログ(log)と呼ばれる。 何もしなければログはどんどん大きくなっていく。カスケーディングアボートに備えるために、ずーとログを取っておかなくてはならないからである。
ある時点で、データベースの状態をとっておき、それを正規の状態と決めれば、その時点より前のログを取っておく必要はない。それはバックアップ(backup)と呼ばれる。バックアップの後は、明示的にトランザクションログを消さなくてはならないデータベースも多い。<P>
Unix には、sync というコミットに近い動作がある。これは、アプリケーションからは書き込みは終わっているが、OSはディスクにデータを書き込んでいない状態を解消する。したがって、Unix上のファイルシステムをもとにしたデータベースは本当の意味で安全になることはない。多くのデータベースではファイルシステムを経由せずに直接ディスクを操作することでこれを回避している。
Unixでのロック
- flock
- fcntl
- lockf
- Symbolic linkによるlock
問題6.3
flock_test.pl などのソースDeadLock の問題 さまざまな言語とAPIでデッドロックを実際に確認してみよう。