Principles of Concurrent and Distributed Programming
Chapter 4 Semaphores
4.1 Introduction
4.3 Mutual Exclusion
4.4 Semaphore Definitions
- いろいろなセマフォがある。
Blocked-set Semaphore
- Wait(S) : Sが0以上の場合、Sをデクリメントする。それ以外のとき、waitを実行したプロセスと一時停止する。
- Signal(S) : このセマフォによって一時停止させられているプロセスがあった場合、そのうちの一つを起動させる。それ以外の場合、Sをインクリメントする。
Blocked-queue Semaphore
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.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.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
- 食事をする哲学者の問題
- 哲学者ってところが、微妙にユーモアがあってよい。
- http://ja.wikipedia.org/wiki/%E9%A3%9F%E4%BA%8B%E3%81%99%E3%82%8B%E5%93%B2%E5%AD%A6%E8%80%85%E3%81%AE%E5%95%8F%E9%A1%8C
5人の哲学者が食事したり、考え事をしたりしている。かれらのいる大学には、真ん中にスパゲッティの入った大きなボールが置かれた丸い食卓がある。その食卓には5枚の皿が置かれ、皿と皿の間にフォークが1本ずつ置かれている。
スパゲッティをボールから取って自分の皿によそうには2本のフォークを必要とし、哲学者は一度に1本のフォークしかテーブルから取ることができない。(左右の手で同時に両側にある2本のフォークを取ることはできない、という意味。まずどちらかの側のフォークを取ってから、逆の側のフォークを取る。)哲学者同士は決して会話をしない。
6.2 Solutions using Semaphores
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
もっと読みたい人へ。