Mis on söögifilosoofide probleem?

Söögifilosoofide probleem on arvutiteaduse valdkonnas kasutatav mõtteeksperiment või näide. Probleem kasutab analoogiat, et illustreerida sünkroonimisprobleeme, mis võivad tekkida, kui arvutid jagavad ressursse. Arvutiteadlased kasutavad söögifilosoofide probleeme, et õpetada õpilastele nende probleemide lahendamiseks kasutatavaid algoritme.

Söögifilosoofide probleemi stsenaarium on ümmargune laud, mille taga istub viis filosoofi. Laua keskel on kauss nuudlite või muu toiduga. Igal filosoofil on mõlemal küljel üks kahvel või söögipulk, mis tähendab, et kokku on viis kahvlit või söögipulka. Söömiseks vajab filosoof kahte riista. Iga filosoof peab kulutama ka mõnda aega mõtlemisele ega saa samal ajal mõelda ja süüa. Söögifilosoofide probleemi keskmes on ummikseisu ärahoidmise raskus.

Ummik selles probleemis tekib siis, kui filosoofid seavad end olukorda, kus nad ei suuda mõelda ega süüa. Näiteks kui iga filosoof tõstaks temast vasakul oleva riista, ei saaks keegi süüa, sest kõik riistad oleksid kasutusel, kuid ühelgi filosoofil poleks kahte. Et kõik filosoofid saaksid süüa, peab õpilane looma algoritmi, mis tagab, et osad filosoofid söövad, teised aga mõtlevad. See võimaldab nii söömist kui ka mõtlemist ilma seiskumiseta jätkata.

Söögifilosoofide probleemile on mitmeid võimalikke lahendusi. Üks lahendus hõlmab kuuenda tegelase, kelneri loomist, kes annab või keelab filosoofidel loa oma kahvleid korjata. Teised hõlmavad filosoofide kahvlite kättesaamise ja maha panemise järjekorra reguleerimist, et maksimeerida kättesaadavust. Teised kästavad filosoofidel enne sööma asumist kontrollida, kas nende naabrid söövad. Sisuliselt hõlmab iga lahendus reeglite komplekti, mida nimetatakse algoritmiks, väljatöötamist, mis määrab, millal filosoofid mõtlevad, söövad või oma riistad üles võtavad ja maha panevad.

Söögifilosoofide probleemi väljendas esmakordselt Hollandi arvutiteadlane Edsger Dijkstra 1965. aastal õpilastele mõeldud eksamiküsimusena. Sellest ajast peale on probleem läbi teinud mitmeid muudatusi. See ilmub mitmes veidi erinevas vormingus, millest mõned muudavad ainult loo üksikasju, kuid teised pakuvad probleemile täiendavaid piiranguid, et näidata keerulisi kontseptsioone. Kõige tavalisema kaasaegse versiooni lõi Tony Hoare.