Problem med cigarettrökare
Problemet med cigarettrökare är ett samtidighetsproblem inom datavetenskap , som ursprungligen beskrevs 1971 av Suhas Patil . Problemet har kritiserats för att ha "restriktioner som inte kan motiveras av praktiska överväganden".
Problembeskrivning
Patils problem inkluderar en "ganska godtycklig" "begränsning att processen som tillhandahåller ingredienserna inte kan ändras och att inga villkorliga uttalanden får användas."
Anta att en cigarett kräver tre ingredienser för att göra och röka: tobak, papper och tändstickor. Det finns tre rökare runt ett bord, som var och en har en oändlig tillgång på en av de tre ingredienserna - en rökare har oändlig tillgång på tobak, en annan har papper och den tredje har tändstickor.
Det finns också en icke-rökare som gör det möjligt för rökarna att göra sina cigaretter genom att godtyckligt ( icke-deterministiskt ) välja ut två av förnödenheterna att lägga på bordet. Rökaren som har den tredje förråden bör ta bort de två föremålen från bordet och använda dem (tillsammans med sin egen förråd) för att göra en cigarett, som de röker ett tag. När rökaren har avslutat sin cigarett lägger agenten två nya slumpmässiga föremål på bordet. Denna process fortsätter för alltid.
Tre semaforer används för att representera föremålen på bordet; agenten ökar den lämpliga semaforen för att signalera att ett föremål har lagts på bordet, och rökare minskar semaforen när de tar bort föremål. Varje rökare har också en tillhörande semafor som de använder för att signalera till agenten att den specifika rökaren har slutat röka; agenten har en process som väntar på varje rökares semafor för att låta agenten veta att den kan lägga de nya föremålen på bordet.
En enkel pseudokodimplementering av rökaren som har tillgång till tobak kan se ut så här:
def tobacco_smoker (): upprepa : papper . vänta () matchar . vänta () röka () tobacco_smoker_done . signal ()
Detta kan dock leda till dödläge; om agenten lägger papper och tobak på bordet, kan rökaren med tobak ta bort papperet och rökaren med tändstickor kan ta tobaken, vilket gör att båda inte kan göra sin cigarett. Lösningen är att definiera ytterligare processer och semaforer som förhindrar dödläge, utan att ändra agenten.
Kritik
Patil satte följande begränsningar på problemet med cigarettrökare:
- Agentkoden kan inte ändras.
- Lösningen är inte tillåten att använda villkorliga uttalanden.
Patil använde ett bevis i termer av Petri-nät för att hävda att en lösning på problemet med cigarettrökare med Edsger Dijkstras semaforprimitiv är omöjlig, och för att antyda att en mer kraftfull primitiv är nödvändig. David Parnas visade dock att Patils bevis är otillräckligt om arrayer av semaforer används, vilket erbjuder en lösning som använder hjälpprocesser som gör aritmetik för att signalera att lämplig rökare ska fortsätta.
Enligt Allen B. Downey är den första begränsningen vettig, för om agenten representerar ett operativsystem skulle det vara orimligt eller omöjligt att ändra det varje gång en ny applikation kom. Parnas hävdar dock att den andra begränsningen är omotiverad:
De begränsningar som rapporterats av Patil är begränsningar av hans primitiver, men de är inte begränsningar för de primitiver som beskrivs av Dijkstra. … Det är dock viktigt att en sådan undersökning [av Dijkstra-primitiver] inte undersöker kraften hos dessa primitiver under artificiella restriktioner. Med konstgjorda menar vi restriktioner som inte kan motiveras av praktiska överväganden. Enligt denna författares åsikt är restriktioner som förbjuder antingen villkors- eller semaformatriser konstgjorda.
Se även
| Allmän | |
|---|---|
| Processkalkyler | |
| Klassiska problem | |
