Ugrás a tartalomhoz

cigarette smokers problem

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

cigarette smokers problem (tsz. cigarette smokers problems)

  1. (informatika) A Cigarette Smokers Problem egy klasszikus szinkronizációs probléma, amelyet Su Yen és P. Brinch Hansen vezetett be az 1970-es években, és amit Tony Hoare is elemzett. A probléma célja: megérteni és demonstrálni a versenyhelyzetek, éhezés (starvation), és szinkronizáció komplexitását a konkurens programozásban.


🧠 A probléma lényege

Van három dohányos és egy ügynök (agent). Minden dohányosnak van egy adott végtelen készlete egy adott hozzávalóból, és csak akkor tud cigit sodorni és elszívni, ha a másik két összetevőt megkapja az ügynöktől.

A három hozzávaló:

  • Dohány
  • Papír
  • Gyufa

A szereplők:

  • Dohányos 1: csak dohánya van
  • Dohányos 2: csak papírja van
  • Dohányos 3: csak gyufája van

Az ügynök viselkedése:

  • Véletlenszerűen két összetevőt tesz ki az asztalra.
  • A dohányosok figyelik az asztalt, és az, aki a hiányzó harmadik összetevővel rendelkezik, az reagál, elkészíti a cigarettát, elszívja, majd jelzi, hogy kész van.


🧩 A szinkronizációs kihívás

  • Csak az a dohányos reagálhat, aki a megfelelő hozzávalóval rendelkezik.
  • A többieknek várakozniuk kell.
  • Az ügynöknek várnia kell, amíg az asztal üres nem lesz (a dohányos befejezte).
  • Éhezés (starvation) elkerülése: minden dohányos előbb-utóbb dohányozhasson.
  • Versenyhelyzetek megelőzése: egyszerre ne több dohányos reagáljon.


🔧 Klasszikus megoldás (semaphore-ral, pseudokód)

Változók:

  • mutex: kizárásra
  • agent: szignál az ügynöknek, hogy új kör indulhat
  • smoker_tobacco, smoker_paper, smoker_match: külön semafor a dohányosoknak
  • tobacco, paper, match: boolean flag-ek vagy semaforok

Ügynök (agent) pseudokód:

while (true) {
    wait(agent);  // csak akkor, ha az előző ciklus befejeződött
    pick two items at random;
    signal(semaphore for the smoker with the missing item);
}

Dohányos:

smoker_with_tobacco:
    while (true) {
        wait(smoker_tobacco); // jelet kap, ha papír + gyufa van az asztalon
        make cigarette;
        signal(agent);  // ügynök mehet újra
        smoke;
    }

Ez a logika minden dohányosnál hasonló, csak más hozzávalóra “vár”.


🧠 Alternatív megoldás: közös asztal + monitor

Használható monitor, amely kezeli az összetevőket és kizárja az egyidejű hozzáférést:

monitor Table {
    bool tobacco, paper, match;
    condition can_smoke[3]; // minden dohányos külön várakozhat

    procedure put(item1, item2) {
        // frissítjük az asztal állapotát
        set items true;
        signal appropriate smoker;
    }

    procedure take(int smoker_id) {
        // dohányos elveszi, amire szüksége van
        reset table;
        signal(agent);
    }
}

🎯 Kulcsproblémák

1. Fairness (méltányosság)

  • Nem lehet, hogy mindig ugyanaz a dohányos jut cigarettához → meg kell akadályozni az éhezést (starvation).

2. Mutual exclusion (kölcsönös kizárás)

  • Egyszerre csak egy dohányos dolgozhat az asztalon.

3. Deadlock avoidance (holtpont elkerülése)

  • Ne várakozzanak egymásra örökké.

4. Szinkronizáció helyessége

  • Az ügynöknek várnia kell, amíg az asztal üres.
  • A dohányosnak csak akkor szabad reagálnia, ha az ő kombinációja van kint.


🖥️ C++ megvalósítás vázlat (std::thread + semaphore mintával)

#include <thread>
#include <mutex>
#include <condition_variable>

std::mutex mtx;
std::condition_variable cv_agent, cv_smoker[3];
bool table_ready = false;
int available_items = 0; // 0: dohány, 1: papír, 2: gyufa (kettőt tárolunk)

void agent() {
    while (true) {
        std::unique_lock<std::mutex> lock(mtx);
        cv_agent.wait(lock, []{ return !table_ready; });

        // random két elem
        int i1 = rand() % 3;
        int i2 = (i1 + 1 + rand() % 2) % 3;
        table_ready = true;

        int smoker_id = 3 - i1 - i2; // hiányzó összetevő = dohányos id
        cv_smoker[smoker_id].notify_one();
    }
}

void smoker(int id) {
    while (true) {
        std::unique_lock<std::mutex> lock(mtx);
        cv_smoker[id].wait(lock);

        // cigaretta készítése
        table_ready = false;
        std::cout << "Smoker " << id << " is smoking\n";
        cv_agent.notify_one();
        lock.unlock();

        std::this_thread::sleep_for(std::chrono::milliseconds(500));
    }
}

📚 Fontos tanulságok

  • Egyértelmű példája a több szereplős szinkronizációs problémáknak
  • Nem-triviális vezérlés: a dohányosnak ki kell derítenie, mikor léphet
  • Kiváló oktatási példa a következőkre:
    • szemináriumok/semaforok használata
    • monitor szinkronizáció
    • holtpont és éhezés felismerése


🧠 Kapcsolódó problémák

  • Dining Philosophers Problem – hasonló, de filozófusok és evőpálcikák vannak benne
  • Readers-Writers Problem – olvasók és írók megosztott adat felett
  • Producer–Consumer Problem – pufferek és adatáramlás


🔚 Összegzés

A Cigarette Smokers Problem nemcsak szórakoztató, hanem mélyen oktató példa arra, hogyan lehet helyesen vezérelni több folyamat viselkedését, miközben konfliktusokat, éhezést és versenyhelyzeteket kerülünk el. A probléma különösen fontos a konkurens programozás oktatásában, hiszen világosan rámutat arra, hogy a szinkronizáció nem csupán zárolás, hanem gondos logikai tervezés kérdése.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=cigarette_smokers_problem&oldid=3503944”