Problém kuřáků cigaret - Cigarette smokers problem

Tento článek je o problému počítačové vědy. Problémy, které mohou ovlivnit kuřáky cigaret, viz Účinky tabáku na zdraví.

The problém kuřáků cigaret je konkurence problém v počítačová věda, původně popsaný v roce 1971 autorem Suhas Patil.

Popis problému

Předpokládejme, že cigareta vyžaduje k výrobě a kouření tři přísady: tabák, papír a zápalky. Kolem stolu jsou tři kuřáci, z nichž každý má nekonečný přísun jeden ze tří ingrediencí - jeden kuřák má nekonečný přísun tabáku, další má papír a třetí má zápalky.

Existuje také nekuřácký agent, který umožňuje kuřákům libovolně si vyrábět cigarety (nedeterministicky ) výběrem dvou zásob, které umístíte na stůl. Kuřák, který má třetí zásobu, by měl tyto dvě věci vyjmout ze stolu a použít je (spolu s vlastní zásobou) k výrobě cigarety, kterou na chvíli kouří. Jakmile kuřák dopije cigaretu, agent položí na stůl dvě nové náhodné položky. Tento proces pokračuje navždy.

Tři semafory slouží k reprezentaci položek na stole; agent zvýší příslušný semafor, aby signalizoval, že položka byla umístěna na stůl, a kuřáci sníží semafor při odebírání položek. Každý kuřák má také přidružený semafor, který používá k signalizaci agentovi, že konkrétní kuřák kouří; agent má proces, který čeká na semaforu každého kuřáka, aby agenta informoval, že může umístit nové položky na stůl.

Jednoduchý pseudo kód implementace kuřáka, který dodává tabák, může vypadat takto:

def tabák_kouř():    opakovat:        papír.Počkejte()        zápasy.Počkejte()        kouř()        tabák_smoker_done.signál()

To však může vést k zablokování; pokud agent položí papír a tabák na stůl, kuřák s tabákem může papír odstranit a kuřák se zápalkami může vzít tabák, přičemž oba nebudou moci vyrobit cigaretu. Řešením je definovat další procesy a semafory, které zabraňují zablokování bez úpravy agenta.

Argument

Patil kladl na problém kuřáků cigaret následující omezení:

  1. Kód agenta nelze měnit.
  2. Řešení nesmí používat podmíněné příkazy.

Patil použil důkaz ve smyslu Petriho sítě tvrdit, že řešení problému kuřáků cigaret při používání Edsger Dijkstra Semaforové primitivy je nemožné a navrhnout, že je nutný silnější primitiv.[1] Nicméně, David Parnas prokázali, že Patilov důkaz je nedostatečný, pokud se použije pole semaforu, což nabízí řešení, které využívá pomocné procesy, které aritmeticky signalizují, aby příslušný kuřák pokračoval.[2]

Podle Allen B. Downey, první omezení má smysl, protože pokud agent představuje operační systém, bylo by nerozumné nebo nemožné jej upravit pokaždé, když přišla nová aplikace.[3] Parnas však tvrdí, že druhé omezení je neopodstatněné:

Omezení nahlášená Patilem jsou omezeními jeho primitiv, ale nejedná se o omezení primitiv popsaných Dijkstrou. … Je však důležité, aby takové vyšetřování [Dijkstra primitivů] nezkoumalo sílu těchto primitiv za umělých omezení. Pod pojmem umělý rozumíme omezení, která nelze z praktických důvodů ospravedlnit. Podle názoru tohoto autora jsou omezení zakazující podmíněná nebo semaforová pole umělá.[2]

Reference

  1. ^ Patil, Suhas S. (Únor 1971). Omezení a schopnosti Dijkstrových semaforových primitiv pro koordinaci mezi procesy (Technická zpráva). MIT, Projekt MAC, Skupina výpočetních struktur. Memo 57.
  2. ^ A b Parnas, David L. (Březen 1975). „K řešení problému kuřáků cigaret (bez podmíněných prohlášení)“ (PDF). Komunikace ACM. 18 (3): 181–183. doi:10.1145/360680.360709.
  3. ^ Downey, Allen B. Malá kniha semaforů (2. vyd.). Citováno 29. června 2015.