Проблема філософів що обідають — типова проблема синхронізації процесів, що може виникати при паралельних обчисленнях.
Умова
За круглим столом сидить п'ять філософів, які не спілкуються один з одним. Перед кожним стоїть одна тарілка спагеті, а також на столі лежить п'ять виделок, по одній зліва і по одній справа від тарілки. Кожен філософ в певний момент часу може або їсти, або думати. Щоб поїсти дуже довгі макарони, філософу під час їжі потрібно мати дві виделки (альтернативний варіант задачі описує рис і китайські палички).
Коли філософ їсть, він бере дві виделки зі столу, коли поїв — кладе виделки на стіл і починає думати. Через деякий час процес повторюється.
В результаті цього за столом може виникнути ситуація, при якій філософи одномоментно почали їсти і кожен взяв тільки одну виделку. Оскільки всі філософи тримають одну виделку, і чекають на іншу, це призводить до взаємного блокування. Навіть якщо кожен філософ буде класти на стіл взяту раніше одну виделку, після неможливості взяти іншу виделку через деякий час, а потім знову пробуватиме взяти спочатку одну, а потім іншу, це може також не допомогти їм пообідати, якщо вони повторно братимуть виделки одночасно.
Розв'язки
Офіціант
Відносно простим розв'язком є додавання офіціанта. Філософи мають просити в нього дозволу перед тим як взяти виделку. Офіціант знає які виделки використовуються, і не допускає взаємного блокування. Таким чином, якщо використовуються 4 виделки, він не дасть п'ятому філософу взяти виделку, і її візьме перший. Коли він поїсть, він відпустить обидві, і п'ятий та другий зможуть поїсти…
Ієрархія ресурсів
Іншим простим розв'язком є введення над виделками часткового порядку. Пронумеруємо їх від 1 до 5.
Після цього, введемо правило, що філософ має право брати спочатку виделку з меншим номером, і тільки після цього може брати виделку з більшим. Таким чином, якщо чотири філософи візьмуть виделки з меншим номером, на столі залишиться вільною тільки виделка 5. Філософ що знаходиться між 5 та 1 не зможе її взяти, бо він мусить спочатку взяти 1, яка вже зайнята, і тому її зможе взяти філософ що знаходиться між 5 та 4, і таким чином наїстись.
Цей розв'язок був запропонований Едсгером Дейкстрою.
Приклад розв'язку проблеми мовою ANI
philosopher = []{ id = [int\]; chopstick = [int\]; nextPhil = [philosopher\]; =; =[int newId] { [\newId] <->id; } getChopsticks = [--> ?] { \chopstick, \nextPhil.chopstick --> }; returnChopsticks = [int\ cs1, int\ cs2] { \cs1 ->chopstick; \cs2 ->nextPhil.chopstick; }; eat = [int\ cs1, int\ cs2 --> ?] { "Philosopher " + id + " eating...\n" ->std.out; \cs1, \cs2 -->; }; { std.randInt std.delay getChopsticks eat returnChopsticks <- }; }; numPhils = 5; philPool = [philosopher[numPhils]]; numPhils std.gen <| [int curId] { curId ->philPool.[curId]; \philPool.[(curId + 1) % numPhils] ->philPool.[curId].nextPhil; };
Цей розділ потребує доповнення. (серпень 2017) |
Див. також
Примітки
Посилання
- Java-аплет, Проблема філософів, що обідають (англ.) (фр.) (нім.)
Це незавершена стаття про програмування. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Nemaye perevirenih versij ciyeyi storinki jmovirno yiyi she ne pereviryali na vidpovidnist pravilam proektu Problema filosofiv sho obidayut tipova problema sinhronizaciyi procesiv sho mozhe vinikati pri paralelnih obchislennyah Ilyustraciya zadachi Zmist 1 Umova 2 Rozv yazki 2 1 Oficiant 2 2 Iyerarhiya resursiv 2 3 Priklad rozv yazku problemi movoyu ANI 1 3 Div takozh 4 Primitki 5 PosilannyaUmovared Za kruglim stolom sidit p yat filosofiv yaki ne spilkuyutsya odin z odnim Pered kozhnim stoyit odna tarilka spageti a takozh na stoli lezhit p yat videlok po odnij zliva i po odnij sprava vid tarilki Kozhen filosof v pevnij moment chasu mozhe abo yisti abo dumati Shob poyisti duzhe dovgi makaroni filosofu pid chas yizhi potribno mati dvi videlki alternativnij variant zadachi opisuye ris i kitajski palichki Koli filosof yist vin bere dvi videlki zi stolu koli poyiv klade videlki na stil i pochinaye dumati Cherez deyakij chas proces povtoryuyetsya V rezultati cogo za stolom mozhe viniknuti situaciya pri yakij filosofi odnomomentno pochali yisti i kozhen vzyav tilki odnu videlku Oskilki vsi filosofi trimayut odnu videlku i chekayut na inshu ce prizvodit do vzayemnogo blokuvannya Navit yaksho kozhen filosof bude klasti na stil vzyatu ranishe odnu videlku pislya nemozhlivosti vzyati inshu videlku cherez deyakij chas a potim znovu probuvatime vzyati spochatku odnu a potim inshu ce mozhe takozh ne dopomogti yim poobidati yaksho voni povtorno bratimut videlki odnochasno Rozv yazkired Oficiantred Vidnosno prostim rozv yazkom ye dodavannya oficianta Filosofi mayut prositi v nogo dozvolu pered tim yak vzyati videlku Oficiant znaye yaki videlki vikoristovuyutsya i ne dopuskaye vzayemnogo blokuvannya Takim chinom yaksho vikoristovuyutsya 4 videlki vin ne dast p yatomu filosofu vzyati videlku i yiyi vizme pershij Koli vin poyist vin vidpustit obidvi i p yatij ta drugij zmozhut poyisti Iyerarhiya resursivred Inshim prostim rozv yazkom ye vvedennya nad videlkami chastkovogo poryadku Pronumeruyemo yih vid 1 do 5 Pislya cogo vvedemo pravilo sho filosof maye pravo brati spochatku videlku z menshim nomerom i tilki pislya cogo mozhe brati videlku z bilshim Takim chinom yaksho chotiri filosofi vizmut videlki z menshim nomerom na stoli zalishitsya vilnoyu tilki videlka 5 Filosof sho znahoditsya mizh 5 ta 1 ne zmozhe yiyi vzyati bo vin musit spochatku vzyati 1 yaka vzhe zajnyata i tomu yiyi zmozhe vzyati filosof sho znahoditsya mizh 5 ta 4 i takim chinom nayistis Cej rozv yazok buv zaproponovanij Edsgerom Dejkstroyu Priklad rozv yazku problemi movoyu ANI 1 red philosopher id int chopstick int nextPhil philosopher int newId newId lt gt id getChopsticks gt chopstick nextPhil chopstick gt returnChopsticks int cs1 int cs2 cs1 gt chopstick cs2 gt nextPhil chopstick eat int cs1 int cs2 gt Philosopher id eating n gt std out cs1 cs2 gt std randInt std delay getChopsticks eat returnChopsticks lt numPhils 5 philPool philosopher numPhils numPhils std gen lt int curId curId gt philPool curId philPool curId 1 numPhils gt philPool curId nextPhil Cej rozdil potrebuye dopovnennya serpen 2017 Div takozhred Zadacha postachalnika spozhivachaPrimitkired http code google com p anic Posilannyared Java aplet Problema filosofiv sho obidayut angl fr nim nbsp Ce nezavershena stattya pro programuvannya Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org wiki Problema filosofiv sho obidayut