Principles of Concurrent and Distributed Programming

Chapter 4 Semaphores

4.1 Introduction
  • セマフォについて論議する。
  • Wait(S) : Sが0以上の場合、Sをデクリメントする。それ以外のとき、waitを実行したプロセスを一時停止する。
  • Signal(S) : このセマフォによって一時停止させられているプロセスがあった場合、そのうちの一つを起動させる。それ以外の場合、Sをインクリメントする。
    • 1.Wait(S)とSignal(S)はアトミックな操作である。比較の分とSの操作までに他の処理は入らない。
    • 2.セマフォは常に負でない値を与えられなければならない。
    • 3.Signal(S)は必ず一つのプロセスを起動させなければならない。どれを起動させるかは規定しない。
4.2 Semaphore Invariants

S≧0
S = S0 + #Signals - #Waits

4.3 Mutual Exclusion
  • mutexもS=1のセマフォによって表現することができる。
    • S=1のセマフォにおいて、
    • 4.3.1 mutexの属性は満たされる。
    • 4.3.2 デッドロックは起こりえない
    • 4.3.3 スタベーションは起こらない。
4.4 Semaphore Definitions
Blocked-set Semaphore
  • Wait(S) : Sが0以上の場合、Sをデクリメントする。それ以外のとき、waitを実行したプロセスと一時停止する。
  • Signal(S) : このセマフォによって一時停止させられているプロセスがあった場合、そのうちの一つを起動させる。それ以外の場合、Sをインクリメントする。
Blocked-queue Semaphore
  • Wait(S) : Sが0以上の場合、Sをデクリメントする。それ以外のとき、waitを実行したプロセスと一時停止し、FIFOキューの末尾に追加する。
  • Signal(S) : このセマフォによって一時停止させられているプロセスがあった場合、そのうちの一つを起動させる、その場合、キューの先頭から起動させる。それ以外の場合、Sをインクリメントする。
Busy-wait Semaphore
  • 一時停止ではなく、Busy-loopによって実現する。
  • Wait(S) : loop { if (S > 0) { S=S-1; Break;}}
  • Signal(S) : S=S+1;
Strongly-fair Semaphore, Weakly-fair Semaphore
  • これはもう一段大きな話でどちらに属するかということ
  • Busy-wait Semaphoreはスタベーションも起こりえるし、CPUも無駄遣いする。
  • Blocked-queue Semaphoreではスタベーションが起こりえない。
  • Blocked-set Semaphoreではスタベーションが起こりうる。
4.5 Producer-Consumer Problem
  • Producer-Consumer problemについて考える。
  • Producers:Consumerによって消費されるデータエレメントを作り続ける
  • Consumers:Producerによって作られたデータエレメントを消費し続ける。
  • この形はSemaphoreで表現することができる。
4.6 Infinite Buffers
  • 無限のバッファを想定して、Producer-Consumer problemについて考える。
  • すると、In-ptrとOut-ptrをつかって、考えることができる。
    • ProducerはIn_Ptrの位置にデータを入れて、In_Ptrをインクリメントする。
    • ConsumerはOut_Ptrの位置にあるデータを使い、Out_Ptrをインクリメントする。
    • そのとき、以下のことが成り立つ

#E≧0
#E = 0 + In_Ptr - Out_Ptr

4.7 Bounded Buffers
  • 有限のアーキテクチャ内で無限のバッファを作るやりかた。
    • Circular bufferとPool of bufferがある。
    • Circular bufferはリングリストみたいにして、その中をin_ptrとout_ptrが追いかけっこするような形になる。in_ptrからout_ptrまでがelementsでout_ptrからin_ptrまでがリソース。
    • Pool of buffersは必ずしも一直線上に並んでいなくともよい。アロケートとフリーみたいな感じ。
4.8 Producer-Consumer with Binary Semaphores
  • バイナリセマフォ(1しかないセマフォ)でどのようにProducer-Consumerモデルを実現するか。
4.9 Further Reading
  • もっと読みたい人へ。
4.10 Exercises

Chapter 5 Monitors

5.1 Introduction
  • モニタとはセマフォをラップし、構造化することによって使いやすくしたデータ構造(オブジェクト)である。
  • このオブジェクトは複数のプロセスからアクセスされてもうまく動くことが保障される。
5.2 Producer-Consumer Problem
  • Producer-Consumer問題について
    • ProduceをAppend(I)とし、ConsumeをTake(I)としてラップし、構造化できる。
5.3 Emulation of Semaphores by Monitors
5.4 Emulation of Monitors by Semaphores
  • セマフォによるモニタのエミュレート
  • モニタの排他機構について作っている(?)
5.5 The Problem of the Readers and the Writers
  • Reader-Writer問題について
    • Readers 排他処理が必要ないプロセス。
    • Writers Readersを含めた排他処理が必要なプロセス
  • Producer-Consumer問題と違い、Reader-Writerの関係性が不平等である。
5.6 Correctness Proofs
  • 証明
5.7 Further Reading
  • もっと読みたい人へ
5.8 Exercises

Chapter 6 The Problem of the Dining Philosophers

6.1 Introduction

5人の哲学者が食事したり、考え事をしたりしている。かれらのいる大学には、真ん中にスパゲッティの入った大きなボールが置かれた丸い食卓がある。その食卓には5枚の皿が置かれ、皿と皿の間にフォークが1本ずつ置かれている。
スパゲッティをボールから取って自分の皿によそうには2本のフォークを必要とし、哲学者は一度に1本のフォークしかテーブルから取ることができない。(左右の手で同時に両側にある2本のフォークを取ることはできない、という意味。まずどちらかの側のフォークを取ってから、逆の側のフォークを取る。)哲学者同士は決して会話をしない。

6.2 Solutions using Semaphores
  • セマフォを使った解法
  • 二つの方法があり、Roomというセマフォを作って、人数制限をする方法がある。
  • もう一つは、一人だけが、フォークを逆順で取ろうとする方法がある。
6.3 Monitor Solutions to the Dining Philosophers
  • モニタを使った解法
  • モニタが管理者となって、5人の状態を管理する。
    • その証明
6.4 Further Reading
  • もっと読みたい人へ。
6.5 Exercises

Chapter 7 Distributed Programming Models

7.1 Introduction
  • 独立したプロセスでのプログラミングについて論議する。
7.2 Synchronous or Asynchronous Communication
  • メッセージを送るプロセスと受けるプロセスがある。
  • Synchronous Communication : メッセージのやり取りはatomic(一対一?)であり、レシーバが準備完了していなければ、センダーはレシーバがメッセージを受け付ける準備ができるまで一時停止して待つ。
  • Asynchronous Communication :レシーバの状態に関係なく、センダーはメッセージを任意に送り続けることができる。そのため、メッセージのバッファプールが必要となる。
  • たとえるなら、Synchronous -> 電話であり、Asynchronous -> 手紙である。
7.3 Process Identification
  • お互いのプロセスの識別方法について
  • occam お互いのプロセス間をつなぐ
  • Ada 名前に対してデータを送り自分は名乗らない
  • Linda 全員に送る
7.4 Data Flow
  • データの流れが、一方通行か、双方向かの話。
7.5 Process Creation
  • ダイナミックにプロセスを作ったり消したりする場合のメリット
  • Flexibility

システムは、いくつのプロセスが必要になるかがわからなくとも設計されプログラムされることができる。イニシャライズの間やリクエストの間にプロセスはallocateすることができる。
たとえば、OSはターミナルがいくつ立ったとしてもallocateして、freeすることができる。

  • Dynamic use of resources

システムは、異なった時間に異なった量のリソースを必要とするかもしれないので、それに最適化された形で、プロセスの数を制御することができる。

  • Load balancing

ロードのバランスをとることができる。

7.6 Further Reading

もっと読みたい人へ。