sleeping barber problem

Angol

Főnév

sleeping barber problem (tsz. sleeping barber problems)

1. (informatika) A Sleeping Barber Problem (Alvó borbély probléma) az operációs rendszerek és párhuzamos programozás klasszikus szinkronizációs problémája, amelyet Dijkstra fogalmazott meg. Célja annak modellezése, hogyan lehet folyamatokat (szálakat) úgy koordinálni, hogy ne történjenek versenyhelyzetek, holtpontok, vagy kliensvesztések.

---

🧠 A probléma leírása

Adott egy borbélyüzlet, amelyben:

• 1 borbély dolgozik,
• 1 borbélyszék van (egyszerre csak egy vendéget lehet kiszolgálni),
• N számú várószék van az üzletben.

A viselkedés:

1. Ha nincs vendég, a borbély alszik.
2. Ha jön egy vendég és a borbély alszik, a vendég felébreszti, és a borbély elkezdi nyírni.
3. Ha a borbély épp dolgozik, a vendég:
   • leül egy várószékre, ha van szabad,
   • vagy távozik, ha nincs szabad hely.

A cél: párhuzamos szálak (borbély + vendégek) viselkedésének biztonságos szinkronizálása.

---

🧩 Milyen problémákat modellez?

Ez egy klasszikus producer–consumer probléma, ahol:

• A vendégek a producerek (új munkát hoznak),
• A borbély a consumer (feldolgozza a munkát),
• A várószékek a bufferként (puffer) szolgálnak.

---

🔧 Megoldási eszközök

Az implementációk általában a következő szinkronizációs eszközöket használják:

• Mutex (zárolás): az erőforrás-hozzáférés kizárására,
• Szemaforok:
  • Jelzés vendég érkezéséről (customers),
  • Jelzés, hogy a borbély készen áll (barberReady vagy barbers),
  • Kritikus szakaszok védelme (mutex).

---

🔁 Algoritmus vázlata (pszeudokódban)

Inicializáció:

Semaphore customers = 0;   // számolja a várakozó vendégeket
Semaphore barbers = 0;     // borbély készen áll
Mutex mutex = 1;           // kritikus szakasz védelme
int waiting = 0;           // hányan várnak

---

Borbély szál:

while (true) {
    wait(customers);       // vár, míg jön vendég
    wait(mutex);           // kritikus szakasz
    waiting--;             // egy vendég bemegy
    signal(barbers);       // borbély kész
    signal(mutex);
    cutHair();             // hajvágás
}

---

Vendég szál:

wait(mutex);
if (waiting < N) {
    waiting++;
    signal(customers);     // vendég érkezett
    signal(mutex);
    wait(barbers);         // várja, hogy borbély kész legyen
    getHaircut();
} else {
    signal(mutex);
    leaveShop();           // nincs hely, vendég távozik
}

---

💡 Fontos megfigyelések

• A borbély blokkolva van, amikor nincs vendég – ez az „alvás”.
• A vendégek nem blokkolnak, ha nincs hely – egyszerűen elmennek.
• A szemaforok garantálják, hogy ne legyen versenyhelyzet a várakozó vendégek számlálásában.

---

🛠️ C++11 példa std::mutex és std::condition_variable használatával

std::mutex mtx;
std::condition_variable customer_ready, barber_ready;
int waiting = 0;
const int CHAIRS = 3;

void barber() {
    while (true) {
        std::unique_lock<std::mutex> lock(mtx);
        while (waiting == 0)
            customer_ready.wait(lock); // alvás

        waiting--;
        barber_ready.notify_one();     // jelez egy vendégnek
        lock.unlock();

        cutHair();
    }
}

void customer() {
    std::unique_lock<std::mutex> lock(mtx);
    if (waiting < CHAIRS) {
        waiting++;
        customer_ready.notify_one();   // jelez a borbélynak
        barber_ready.wait(lock);       // várja, hogy sorra kerüljön
        lock.unlock();

        getHaircut();
    } else {
        lock.unlock();
        leaveShop();
    }
}

---

🎯 Tanulságok, modellezési jelentőség

• A Sleeping Barber probléma kiváló példa arra, hogyan kell több szálat biztonságosan koordinálni.
• Megtanít az erőforráskezelésre, blokkolás kezelésére és szemaforok használatára.
• Nagyon hasonló más klasszikus problémákhoz: producer–consumer, olvasó–író probléma, dohányos probléma, stb.

---

✅ Összefoglalás

Elem	Leírás
Szereplők	1 borbély, több vendég
Probléma típusa	Szinkronizációs, versenyhelyzetek elkerülése
Eszközök	Szemafor, mutex, condition_variable
Modell	Producer–Consumer, bounded buffer (korlátozott váróhely)
Cél	Hatékony és biztonságos működés versengő szálak között

További információk

• sleeping barber problem - Szótár.net (en-hu)
• sleeping barber problem - Sztaki (en-hu)
• sleeping barber problem - Merriam–Webster
• sleeping barber problem - Cambridge
• sleeping barber problem - WordNet
• sleeping barber problem - Яндекс (en-ru)
• sleeping barber problem - Google (en-hu)
• sleeping barber problem - Wikidata
• sleeping barber problem - Wikipédia (angol)