sile/amp-4-8.md

## amp-4-8.md

      
    Raw
  

              amp-4-8.md
            
          
    [5] Monitors and Blocking Synchronization

8.1 Introduction


モニター

データと同期処理を結合する構造化された方法
オブジェクト指向言語のクラスに同期処理の管理を追加したようなもの


なぜ有用か？

FIFOキューの例: モニターを使わないと次のような問題がある

キューが満杯の場合に、空きができるまでenq()をブロックする、というような処理の実現が難しい
キューとロックの組み合わせを別々に管理する必要がある

全てのスレッドがキューとロックのそれぞれを適切な場所で適切な手順にそって使用しないとプログラムが上手く動かない


モニターを使って、キュー内部でロックを管理したり、enq()のブロッキング処理を隠蔽してしまえば、使い手は簡単に使用できる


8.2 Monitor Locks and Conditions


モニターは、呼び出し直後にロックを獲得し返る前に解放する、といった挙動をとるメソッド群を提供する
呼び出しスレッドがすぐにロックを獲得できない場合は、以下のいずれかの方法で待機する

スピン: ロックが獲得できるようになったかを繰り返し確認するビジーループ
ブロック: ロック獲得をしばらくの間諦めて、プロセッサが他のスレッドを実行できるようにスリープする


スピンはロック獲得までの時間が短い(と期待できる)場合に効率が良く、ブロックはその逆

生産者/消費者パターンには一般にブロックの方が適している (消費者は生産者の行動を予測できないため)
スピンとブロックを組み合わせるのも良い

短い時間スピンして、ロックを獲得できなかったら、ブロックに移行する


ただし、スピンはシングルプロセッサ環境では、CPU資源を消費するだけで無意味


Pragma 8.2.1:
図8.1のLockインターフェースについての説明

lock(): ロックを獲得するまで呼び出し側をブロックする
lockInterruptibly(): lock()と同じだが、スレッドが割り込まれた場合に例外を投げる: (see Pragma 8.2.2)
unlock(): ロックを解放する
newCondition(): ロックに紐付いた__Condition__オブジェクトを生成する
tryLock(): ロックを獲得できなかった場合にブロックせずに呼び出し側に返る。タイムアウト時間指定可能版もある。

8.2.1 Conditions


FIFOキューの例

何かが起こるのを(例えば空のキューに要素が追加されるのを)待機する場合、ロックを解放しておくのが望ましい

解放しないと、他のスレッドが(ロック獲得して)要素の追加が行えない


ロックの再獲得してリトライを行うべきタイミングを通知される仕組みが必要


Javaならconcurrentパッケージの__Condition__オブジェクトがその役目を果たしている
Condition: 図8.2に使用例

ロック.newCondition() で生成
ロック獲得中に__コンディション.await()__を呼び出すことで、ロックを解放して待機状態に入る
待機状態から目覚めた場合は、再度ロックを獲得する (この際、他のスレッドと競合するかもしれない)


Pragma 8.2.2:
Javaのスレッドは他から割り込まれる可能性がある。

__await()__中に割り込まれると__InterruptedException__が送出される。

本書では、簡単のためにこの例外のハンドリングコードは省略してある。


ロック同様にコンディションも型にはまった方法で使用されなければならない
あるスレッドが特定の条件が成立するまで待機したいとして、

まず、ロックを獲得した後に条件が成立しているかをテストする
成立していない場合は__await()__を呼んで、他のスレッドに起こされるまでの間、ロックを解放して待機する
キーポイント: 起床した際に条件が成立している保証はない

理由なく起こされるかもしれないし、一度に多数のスレッドが起こされるかもしれない
起床後の再テストは必須。条件が成立していないなら再度__await()__


図8.3は__Condition__のインターフェース

await(), await(time, unit), awaitNanos(nanosTimeout), awaitUninterruptibly()
signal(), signalAll()


図8.4はモニターロックの実行例の図解
図8.5は上限付きFIFOキューの実装例

ロックには__java.util.concurrent.locks.ReentrantLock__を使用

再入可能。再帰的に使用してもデッドロックしない。8.4節に実装例あり。


二つのコンディションオブジェクト

notEmpty: キューが空ではなくなったことをdequeuerに伝えるためのコンディション
notFull: __notEmpty__の反対
一つのコンディションでも実装できるけど、二つ使った方が効率的

誤って起床させられるスレッドが少なくなる
ただし複雑度は増す


メソッド、相互排除ロック、コンディションオブジェクトを組み合わせを__モニター__と呼ぶ


8.2.2 The Lost-Wakeup Problem


ロックがデッドロックの危険性を孕んでいるのと同様に、コンディションには__lost wakeup__の危険性がある。

スレッドが、条件が成立しているのに気づかずに待機し続けてしまう問題


__lost wakeup__は気づきにくい方法で問題に成り得るのでやっかい


図8.6は__LockQueue__の間違った最適化の例

__enq()__内で、キューの要素数が 0 => 1 に変わった時にだけ__notEmpty__をシグナルするように変更
生産者/消費者がそれぞれ一人ずつの場合は、この最適化で上手く動く
複数だとダメ。次のシナリオを考えてみる:

消費者__A__と__B__から、空のキューから要素を取り出そうとしている
両者とも__notEmpty__コンディションを待ってブロック
生産者__C__がキューに要素を入れて__notEmpty__をシグナルする


__A__が起きる


__A__がロックを獲得する前に、生産者__D__がさらに要素を追加する


この際にキューは空ではないので__notEmpty__はシグナルされない


__A__がロックを獲得し、要素をキューから取り出す
B(__lost wakeup__の被害者)は、要素があるにも関わらず、延々と待機し続ける


注意深い熟考に代わるものではないけど、__lost wakeup__の危険性を最小限にするための簡単なプログラミングプラクティスがある

常に全てのプロセスにシグナルを送るようにする。signal()ではなく、signalAll()を。
待機する際にはタイムアウトを指定する


それぞれ若干の性能的な犠牲はあるが、__lost wakeup__による損失比べれば無視できる程度。


8.3 Readers-Writers Locks


多くの共有オブジェクトは以下の性質を備えている

状態を変更するメソッド呼び出し(writers)はまれで、情報を取得するだけのメソッド呼び出し(readers)がほとんど
__readers__が互いに同期する必要性はない
__writers__はロックが必要。他の__writers__と__readers__との両方に対して。


__readers-writers__ロック

複数のreader あるいは 単一のwriter がクリティカルセクションに入ることを許可するロック
インターフェース: readLock()、__writeLock()__メソッドを提供する

writeLock(): スレッドは、他のスレッドがreadロックあるいはwriteロックを保持している間は、writeロックを獲得できない
readLock(): スレッドは、他のスレッドがwriteロックを保持している間は、readロックを獲得できない


8.3.1 Simple Readers-Writers Lock

まず初めに簡単な__reader-writer__ロックの実装。

図8.7～図8.9
readerはカウンタで、writerはフラグで管理
Javaのinner classを使ってる
※ 図8.9の実装は間違い。__writer==true__のチェックを__while__に追加しないと複数__writer__に対応できない。

8.3.2 Fair Readers-Writers Lock


__SimpleReadWriteLock__には欠点がある

複数の__reader__が絶え間なくロックの獲得/解放を繰り替えしていると、__writer__がずっと締め出されてしまう


FifoReadWriteLock(図8.10～図8.12)はその点を解決している

一度__writer__がロックを試みたら、それ以降にロックを獲得しようとした__readers__はブロックされる


実装

__SimpleReadWriteLock__との主な違いは、こっちは__writer__が一度内部ロックを獲得したら__unlock()__呼び出しまで解放しないこと
疑問

英語の文章と実装が合っていない (あとバグがある)
カウンタを__readAcquires__と__readReleases__に分けた理由が良く分からない
別に__writer__の内部ロックの保持期間を長くする必要もなさそう

要は__reader__がロックを獲得しようとしている__writer__の存在を検出できれば良いだけ


修正版:
private class Readlock implements Lock { // SimpleReadWriteLockの実装と全く同じ
    public void lock() {
        lock.lock();
        try {
            while (writer) {
                condition.await();
            }
            readers++;  // readAcquires と readReleases は readers に統合。and インクリメントはwriteフラグのチェック後
        } finally {
            lock.unlock();
        }
    }
    public void unlock() {
        lock.lock();
        try {
            readers--;
            if (readers == 0)
                condition.signalAll();
        } finally {
            lock.unlock();
        }
    }
}

private class WriteLock implements Lock {
    public void lock() {
        lock.lock():
        writer = true;   // writerフラグは待機に入る前にtrueにしておく (readerにwriterの存在を通知)
        while (readers > 0 && writer)  // writerフラグのチェックも入れる
            condition.await();
        writer = true;   // ここでもwriterフラグをセット (書き手が複数の場合を考慮して)
    }

    public void unlock() {
        writer = false;
        condition.signalAll(); // unlock()内でシグナル発行
        lock.unlock();         // lock()で獲得した内部ロックを解放 (SimpleReadWriteLockと同様に、lock()とunlock()で毎回、ロックの獲得/解放を行っても問題ない)
    }
}
8.4 Our Own Reentrant Lock


二章や七章に出てきたロックは、再入可能ではない。

同じスレッドが既に獲得済みのロックを再度獲得しようとするとデッドロックに陥る


この節では、再入不可のロックから、再入可能なロックを構築する方法を説明する
図8.13: SimpleReentrantLock

再入不可ロックをラップして、所有者とネスト数の管理を追加
この実装も間違っているような... (デッドロックになりそう)

__lock()__内で内部ロックの解放が必要


8.5 Semaphores


セマフォ

相互排除ロックの一般化
__N__個のスレッドが同時にクリティカルセクションに入ることを許可する
同期処理の最初期の形の一つ


図8.14: 相互排除ロックを用いたセマフォの実装

相互排除ロックに、クリティカルセクションにいるスレッド数の管理とコンディションを加えたもの


8.6 Chapter Notes

省略
8.7 Exercises

省略