セマフォ
semaphore
とある構造体
複数のプロセスが共有資源にアクセスすることを制御する抽象データ型
使用される上限を示す構造体をglobal変数として共有する感じ
mutableな世界に慣れているとかなり気持ち悪く見える
構成
セマフォ変数
整数型
「セマフォ変数」という謎の単語を使うからわかりにくくなる
単純に「cnt」とかのほうがわかりやすい
このセマフォ構造体を使える残りのhogeの個数を表す
使われるたびに減っていき、0になったら新しく使われることはできない
待ち行列
セマフォ獲得待ちのプロセスのための待ち行列
セマフォ変数が0になったときに、新しく使われる場合に、ここに格納されて待ち状態になる
どういうデータ型 #??
なんでもいいのか
タスクの実体とか、PIDとか
V命令
wait() Verhoog命令
オランダ語で「高める」
セマフォ変数を1増やす
P命令
signal() Passeren命令
オランダ語で「通過を許す」
セマフォ変数を1減らす
「プロセス」みたいな、処理主体が、「残りどれぐらい処理を同時にできるよ」を管理するために、子として持つもの、なのかな
↓の
Process はこういう使い方をするのかはわからないsample.tstype Semaphore<T> = {
cnt: number; // セマフォ変数
queue: T[]; // 待ち行列
}
// 待ちが無ならcntを増やし、何か待っているなら1つ取り除く
const siglnalV = (s: Semaphore) => {
return s.queue.length == 0
? { ...s, cnt: s.cnt++ }
: { ...s, queue: s.queue.slice(1) }
}
// もう残りがないなら待ち行列に追加、まだ行けるならcntをへらす
const waitP = <T>(s: Semaphore, process: T) => {
return s.cnt == 0
? { ...s, queue: s.queue.push(process) }
: { ...s, cnt: s.cnt-- }
}利用する側.ts type Process = {
hogehoge: ... // なんらかのメインの処理
semaphore: Semaphore<Process> // 管理するものとしてセマフォを持つ
}
// 共通のセマフォを初期化
const semaphore: Semaphore<Process> = {
cnt: 2,
queue: []
}
// タスクたち。これらは共通のセマフォを持っている
const process1: Process = {
..,
semaphore
}
const process2: Process = {
..,
semaphore
}
const process3: Process = {
..,
semaphore
}
// ..セマフォ変数が
0|1 のセマフォそうでないものをカウンティングセマフォと言う
つまり、一つのものにしか使われない
「誰かに使われているかどうか」のflgを持っているのと同じ
この場合は型的にはbooleanの方が適切
hasUsedNow: boolean カウンティングセマフォの制限きつい版
セマフォの問題点
P命令とV命令の実行責任はユーザー側にある
ユーザーが適切な工程を踏まなければクリティカルセクションにアクセスできてしまう
ユーザーがV命令を適切に実行しないと、プロセス競合やリソース独占が起こりうる
参考