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の並行実行

Rustの並行実行

問題6.2

golang で Semaphor を実装してみる

Channelの実装

Decd lock 閉塞

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

問題ある町のホテルの空室数のデータベースをHotel、この町にいく飛行機の空席数のデータベースをPlaneとする。 以下のような操作を考えよう。

例えばTがHotel 予約するためには、

  1. T-lock-Hotel --- TがHotelをロックする
  2. T-reserve-Hotel --- Tがホテルの予約を取る
  3. T-releasse-Hotel --- TがHotelをロック解除する
という手順が必要である。これがひとつのトランザクションになる。

質問: さてSとTは、両方とも「飛行機の切符とホテルの予約」を取るというのを一つトランザクション(transaction)を実行したい。(片方だけ成功しても意味がない...)

2相ロック

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

つまり 

    資源1を lock
    資源2を lock
      ...
    資源1を unlcok
    資源2を unlock
とするのが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でのロック

問題6.3

flock_test.pl などのソース

DeadLock の問題 さまざまな言語とAPIでデッドロックを実際に確認してみよう。

Shinji KONO / Tue Jan 9 14:09:26 2024