図書室のたとえ
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/10/15 04:56 UTC 版)
ある図書室に学習室が10部屋あり、それぞれの学習室は一度に1人の学生が使用するとする。争奪戦が始まらないよう、学生は受付カウンターで学習室の使用を申し込むことになっている。学習室を使用し終えたら、学生は受付所に立ち寄ってその学習室が空いたことを知らせなければならない。全ての学習室が埋まっている場合、学生は受付所で学習室が空くのを待つ。 受付カウンターの図書係はどの学習室が空いているかは把握しておらず、単に空いている部屋数のみを知っている。学生が申し込んできたとき、図書係は空き部屋数から1を引く。学生が学習室の利用を終えたとき、図書係は空き部屋数に1を加える。学習室の使用許可が与えられたとき、その部屋は必要なだけ使い続けることができる。学習室は事前に予約することはできない。 このシナリオでは、受付カウンターがセマフォ、学習室が資源、学生が実行単位に相当する。また、セマフォの初期値は10になっている。学生が学習室の使用を申し込んで許可されたとき、セマフォ値から1が引かれて9になる。次の学生のときには8、さらに次は7となる。1を引くとセマフォ値が負になるという状態で学生が申し込んだ場合、その学生は待たされる。複数人の学生が待っているとき、彼らは待ち行列を形成するか、いずれかの学生が学習室の使用を終えて受付カウンターにやってきたときに空いた部屋を割り当てる。割り当て方式には、ラウンドロビン・スケジューリング方式等がある(セマフォが正しく制御されるよう実装されていれば、割り当て方式は妥当なものであればよい)。
※この「図書室のたとえ」の解説は、「セマフォ」の解説の一部です。
「図書室のたとえ」を含む「セマフォ」の記事については、「セマフォ」の概要を参照ください。
- 図書室のたとえのページへのリンク