Sleeping barber problemとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Sleeping barber problemの意味・解説 

居眠り床屋問題

(Sleeping barber problem から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/08/25 15:42 UTC 版)

計算機科学における居眠り床屋問題(いねむりとこやもんだい、sleeping barber problem)とは、典型的なプロセス間通信およびプロセス間での同期に関する問題である。客がいる限り働いたまま、客がいなければ休んだままということを繰り返す理容師に例えられることからついた名称。理容師と客の挙動で、前述したプロセス間の問題を表現する。

問題

理容師が一人だけいる床屋を考えてみる。このには理容椅子が一脚あり、待合室には椅子がいくつか置かれている。理容師は整髪を終えると客を帰し、待合室で次の客が待っていないか調べる。もし客がいたら理容椅子に座らせ、髪を切り始める。客がいなかった場合は、理容師は昼寝を始める。一方、客は来店したらまず理容師が何をしているのか調べる。もしも理容師が昼寝をしていたら、理容師を起こして自分の髪を切らせる。理容師が他の客の髪を切っていたら、待合室の椅子に座る。ただし待合室に空きがなければ、客は髪を切らずに黙って帰る。

上記の挙動で床屋は順調に機能し、理容師は客がいなくなるまで髪を切っては、また客が来るまでは昼寝することができると思われる。しかし実際にはいくつもの潜在的な問題があり、それらはスケジューリングにおける一般的な問題の具体例となる。

問題は、理容師や客の挙動(待合室を調べる、理容師を調べる、待合室の椅子に座るなど)に要する時間が不明だということにある。たとえば、来店した客はまだ仕事中の理容師を見たら待合室に向かう。そしてその客が待合室の椅子に腰を下ろすまでの間に、理容師が髪を切り終えて待合室の様子を調べる。しかし厳密には待合室に客がいない(まだ誰も椅子に腰を下ろしていない)ので、理容師は昼寝を始めてしまう。理容師は客に起こされるのを待ち続け、一方で客は理容師に呼ばれるのを待ち続ける。そして二人め以降の客は、既に待合室に客がいるので、理容師が寝ているかどうかを調べようとせず、ついに床屋は機能しなくなってしまう。

また二人の客が同時に来店するケースでは、理容師がまだ仕事中かつ待合室に椅子がもともと一つしかない場合、二人とも椅子に座ろうとしてしまう。

居眠り床屋問題はエドガー・ダイクストラの考案であるという説がある。

解法

いくつかの解法が存在する。解決の鍵はミューテックス(mutex)で、これは登場人物のうちミューテックスを持つ一人だけが状態を変更できる(同時に二人以上の状態が変更しない)ことを保証するものである。理容師は待合室を調べるまえにミューテックスを得なければならず(そして別の客の髪を切り始めるか昼寝を始めるかする時にmutexを開放する)、一方で客は入店するときにミューテックスを得なければならない(そして理容椅子か待合室の椅子に座った時にミューテックスを開放する)。これにより先述の問題は両方とも解決する。また、システムの状態(待合室の人数や理髪椅子の状態)を変更するのにも、いくつかのセマフォが必須となる。

複数の居眠り床屋問題(multiple sleeping barbers problem)は、実装と注意点において類似するが、複数の理容師と待機する客との調整に関してさらなる複雑さがある。

実装

以下の擬似コードは理容師と客との同期を保証しデッドロックも起こらないが、客のリソーススタベーションは起こるかもしれない。PとVはセマフォが提供する関数。

  • 必要な変数(先述のとおり):
 + Semaphore Customers = 0
 + Semaphore Barber = 0
 + Semaphore accessSeats (mutex) = 1
 + int NumberOfFreeSeats = N //待合室の空席の数
  • 理容師のプロセス(またはスレッド):
 while(true) { //無限ループ
   P(Customers) //客を調べようとする - いなければ昼寝する
   P(accessSeats) //この時点で理容師は目を覚ましている - 空席の数を変更しようとする
   NumberOfFreeSeats++ //空席が一つできた
   V(Barber)  //髪を切り始める
   V(accessSeats) //もはやロックは必要としない
   //ここでは髪を切っている最中
 }
  • 客のプロセス(またはスレッド):
 while(true) { //無限ループ
   P(accessSeats) //待合室の椅子に座ろうとする
   if ( NumberOfFreeSeats > 0 ) { //空席がある場合
     NumberOfFreeSeats-- //空席を一つ埋める
     V(Customers) //理容師が仕事中か調べようとする
     V(accessSeats) //もはやロックを必要としない
     P(Barber) //自分に順番が回ってきたが、理容師が何かしていれば待つ
     //ここでは髪を切られている最中
   } else { //空席がない場合
     //残念でした
     V(accessSeats) //しかしロックを開放するのを忘れてはいけない
     //客は黙って帰る
   }
 }

参考文献

関連項目


「Sleeping barber problem」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「Sleeping barber problem」の関連用語

Sleeping barber problemのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Sleeping barber problemのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの居眠り床屋問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS