複数のプロセス(process)は、単一のプロセッサ(Processor)、また は、複数のプロセッサ上で動作している。このプロセスがおたがい に協調して動作するためには、なんらかの形で、プロセス同士のタ イミングをとる必要がある。これを、プロセスの同期 (Sychronization) と呼ぶ。
プログラムが、要求された仕様を満たすことを 整合(consistent) という。 一般的な整合性(Consistency)は、並列に動作するプログラムが直列可能(Serializable)で ある場合にのみ得られる。並列環境下で直列可能性を保証するためには、 同期機構が必要となる。 (consitentの反対はinconsitent (矛盾)、従って、整合のことを無矛盾ともいう)
要求仕様の例
以下のような例を考えてみよう。
[操作A] a = count; [操作B] a += 1; [操作C] count = a;これを複数のユーザ が同時に行うと困ったことが起きる。もちろん、プロセスの内部 での実行順序はA,B,Cの順だが、それらはスケジューラによって 分割されて、他のプロセスのA,B,Cと混じる(Interleaving) されることがある。
count は 256 [操作A1] by User 1 count == 256 [操作B1] by User 1 count == 256 [操作C1] by User 1 count == 257 [操作A2] by User 2 count == 257 [操作B2] by User 2 count == 257 [操作C2] by User 2 count == 258もちろん、count は258になることが期待される。
同期は、いろいろなレベルで行われる。
前の例の 操作 ABCのようなデータの変更のまとまりをというトランザクション(transaction)という。 トランザクションは、それを順番にやったようになって欲しい。それが 普通の直感である。この場合は、「1を加える」を2回おこなったのだから、 2だけ値が増えてほしい。これを直列可能性(Serializability)という。
直列可能性が成立していれば、プログラムはトランザクション の変更の積み重ねとなる。これは、トランザクションの積み重ねか らプログラム全体ができていることを意味する。これをプログラム の無矛盾性(Consistency)という。ある条件のもとでConsistencyと Serializabilityは同値であることが証明されている。
前の人の値を上書きしているという単純なことだが、このよう に依存関係の矢印を書くことによって、より矛盾が明快になる。ま た、機械的に矛盾を見つける手順を提供することもできる。あたり 前のことを明確にすることがコンピュータサイエンスでは重要なこ とが多い。
並列システムでは、 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になっている。
BSD/OSのthreadでは、ロックを使って同期をおこなう。これはバイナリセマフォと 同じである。 セマフォには、P命令とV命令がある。このプログラム では、セマフォを以下のように用いる。
P命令
きわどい部分 (critical section)
V命令
pthreadのセマフォは、
P命令 pthread_mutex_lock(pthread_mutex_t *mutex);
V命令 pthread_mutex_unlock(pthread_mutex_t *mutex);
となってる。それぞれの引数は、初期化されたセマフォへのポインタ
である。
バイナリセマフォでは、P命令を実行して通過できるのはただ一つの process/thread だけである。しかし、資源がただ一つだけなく複数 ある時には、複数のプロセスがP命令を実行できても良いと考えられる。 この場合、P命令が消費に相当し、V命令が生産に相当する。 この場合は、P命令を実行した回数とV命令を実行した回数は、最大N 個の差まで容認される。このようなセマフォを計数セマフォ(counting semaphor) という。
例えば、最初にN個の資源があり、 生産者がN 個まで随時、資源を生成し、消費者がそれを消費していく とする。消費者は資源がある限り、それを同時に使用して良い という生産者消費者問題を考えよう。
生産者消費者問題は計数セマフォを使うことにより実現できるが、 pthread には残念ながら計数セマフォはない。その代わり条件付き 変数があるので、それを用いて計数セマフォを作成する。 条件付き変数というのは歴史的な 理由でそういう名前がついているのだが、これは同期を待ち合わせる process / thread のqueue (キュー)である。このキューには、
| pthread_cond_wait(&sem->cond,&sem->mutex); | 自分を待ち行列に加える。実行キューから取り除かれる |
| pthread_cond_signal(&sem->cond); | 待ち行列から一つ取り出し、実行キューに加える |
条件付き変数と、セマフォを組み合わせて計数セマフォを作る。cond は、 待ち合わせを行う軽量プロセスのキューがである。
typedef struct sem_t {
int value;
pthread_mutex_t mutex; /* セマフォの値の整合性を得るためのロック */
pthread_cond_t cond; /* 待ち合わせのキューを作るための条件付き変数 */
} sem_t,* sem_ptr;
void sem_init(sem_t *,int);
void sem_v(sem_t *);
void sem_p(sem_t *);
計数セマフォの初期化は、資源の量を指定する。
void
sem_init(sem_t *sem,int value)
{
pthread_mutex_init(&sem->mutex,NULL);
pthread_cond_init(&sem->cond,NULL);
sem->value = value;
}
P動作、バイナリセマフォと違って、複数の待ち合わせが行われる
ことがある。
void
sem_p(sem_t *sem)
{
/* まずvalueをみるためだけにlockする */
pthread_mutex_lock(&sem->mutex);
while(sem->value == 0) { /* もう、残ってない */
/* 条件付き変数に自分を登録して、ロックを解放して、他の
プロセスが資源を解放してくれるのを待つ */
pthread_cond_wait(&sem->cond,&sem->mutex);
}
/* 自分の分の資源があったので、それを確保する */
sem->value--;
pthread_mutex_unlock(&sem->mutex);
/* ロックを解放する */
}
V動作では、解放される資源は一つしかないので、一人だけしか起こす
必要はない。
void
sem_v(sem_t *sem)
{
/* まずvalueをみるためだけにlockする */
pthread_mutex_lock(&sem->mutex);
/* 資源を解放する */
sem->value++;
pthread_mutex_unlock(&sem->mutex);
/* 他に資源が待って寝ている人がいれば、その人を起こす */
pthread_cond_signal(&sem->cond);
}
このように共有資源と同時に使わなくてはならないPosix threadの
同期機構は非常にださい。計数セマフォのP/Vの処理に比べて非常に
複雑な印象を受ける。しかし、たぶん、作った人の意図は、これらを
用いて、より高度な同期機構を作って欲しいということなのだろう。
それならば、条件付き変数の内容をより進んだ形で処理したいが、
それは用意されていない。
OSの設計者は、良くそういう手抜きをする。しかし、本来は同期機構は、
その使い方といっしょに設計されるべきものである。
同期機構で実現したいのはConsistencyである。ただ、やみくもに同期機構を
使ってもConsistencyは得られない。例えば、lock によって直列可能性を
得るには、きまった方法によりlockをかける必要がある。一つのresource
(資源)しかない場合には、lock は自明であるが、複数のresourceがある場合には、
lock をかける順序を工夫する必要がある。この問題は、データベースの
理論と同じ問題である。
同期機構は、なんらかの待ちあわせを含む。この時に、いくつかのプロセスが 相互に待ちあわせてしまうことがある。これをDeck lockという。
問題
ある町のホテルの空室数を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相ロックでない場合に矛盾が生じる例を示せ。 (注) sleep などを使わないとうまくdead lock しないことがある。
情報工学実験Iの 4.4 相互排除と 4.5 プロセス間の同期問題を行うこと。 おこなうこと。この実験は nirai/kanai または、pw/nw でおこなうこと。 レポートはメールで
Subject: Report Operating System Lecture 6/5
というように、課題を出した日付をサブジェクトに入れたメールで
提出して下さい。締め切りは来週です。