Проблема філософів що обідають типова проблема синхронізації процесів що може виникати при паралельних обчисленнях Ілюст

Проблема філософів що обідають — типова проблема синхронізації процесів, що може виникати при паралельних обчисленнях.

Умова

За круглим столом сидить п'ять філософів, які не спілкуються один з одним. Перед кожним стоїть одна тарілка спагеті, а також на столі лежить п'ять виделок, по одній зліва і по одній справа від тарілки. Кожен філософ в певний момент часу може або їсти, або думати. Щоб поїсти дуже довгі макарони, філософу під час їжі потрібно мати дві виделки (альтернативний варіант задачі описує рис і китайські палички).

Коли філософ їсть, він бере дві виделки зі столу, коли поїв — кладе виделки на стіл і починає думати. Через деякий час процес повторюється.

В результаті цього за столом може виникнути ситуація, при якій філософи одномоментно почали їсти і кожен взяв тільки одну виделку. Оскільки всі філософи тримають одну виделку, і чекають на іншу, це призводить до взаємного блокування. Навіть якщо кожен філософ буде класти на стіл взяту раніше одну виделку, після неможливості взяти іншу виделку через деякий час, а потім знову пробуватиме взяти спочатку одну, а потім іншу, це може також не допомогти їм пообідати, якщо вони повторно братимуть виделки одночасно.

Розв'язки

Офіціант

Відносно простим розв'язком є додавання офіціанта. Філософи мають просити в нього дозволу перед тим як взяти виделку. Офіціант знає які виделки використовуються, і не допускає взаємного блокування. Таким чином, якщо використовуються 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; };

Див. також

Задача постачальника-споживача

Примітки

http://code.google.com/p/anic/

Посилання

(англ.) (фр.) (нім.)

Це незавершена стаття про програмування.
Ви можете проєкту, виправивши або дописавши її.

[1] ttp://code.google.com/p/anic/