„Problem pušača cigareta“ predstavio je Patil kako bi ukazao na problem sinkronizacije korištenjem semafora. U ovom labosu koristi se isti problem, ali različito rješenje radi ilustracije sinkronizacije u raspodijeljenom okruženju.
U ovom slučaju sustav se sastoji od tri procesa koje predstavljaju pušače te jednog procesa trgovca. Svaki od „pušača“ ima kod sebe u neograničenoj količini jedan od tri sastojka potrebnih da se napravi i zapali cigareta: papir, duhan ili šibice. Svaki pušač ima različiti sastojak, tj. jedan ima samo papir, drugi duhan i treći samo šibice. Trgovac ima sve tri komponente u neograničenim količinama. Trgovac nasumice odabire dvije različite komponente, stavlja ih na stol te signalizira pušačima da su sastojci na stolu. Jedino pušač kojemu nedostaju sastojci stavljeni na stol, smije uzeti oba sastojka, signalizirati trgovcu te potom saviti cigaretu i popušiti ju. Trgovac tada stavlja nova dva sastojka na stol i postupak se ponavlja.
Potrebno je pravilno sinkronizirati rad procesa trgovca i tri procesa pušača koristeći:
- Lamportov raspodijeljeni protokol (rješavaju studenti čija je predzadnja
znamenka JMBAG parna) ili
- protokol Ricarta i Agrawala (rješavaju studenti čija je predzadnja
znamenka JMBAG neparna).
Svi procesi ispisuju poruku koju šalju i poruku koju primaju.
Sve što u zadatku nije zadano, riješiti na proizvoljan način.