Проблема філософів, що обідають
Проблема філософів що обідають — типова проблема синхронізації процесів, що може виникати при паралельних обчисленнях.
Умова
За круглим столом сидить п'ять філософів, які не спілкуються один з одним. Перед кожним стоїть одна тарілка спагеті, а також на столі лежить п'ять виделок, по одній зліва і по одній справа від тарілки. Кожен філософ в певний момент часу може або їсти, або думати. Щоб поїсти дуже довгі макарони, філософу під час їжі потрібно мати дві виделки (альтернативний варіант задачі описує рис і китайські палички).
Коли філософ їсть, він бере дві виделки зі столу, коли поїв — кладе виделки на стіл і починає думати. Через деякий час процес повторюється.
В результаті цього за столом може виникнути ситуація, при якій філософи одномоментно почали їсти і кожен взяв тільки одну виделку. Оскільки всі філософи тримають одну виделку, і чекають на іншу, це призводить до взаємного блокування. Навіть якщо кожен філософ буде класти на стіл взяту раніше одну виделку, після неможливості взяти іншу виделку через деякий час, а потім знову пробуватиме взяти спочатку одну, а потім іншу, це може також не допомогти їм пообідати, якщо вони повторно братимуть виделки одночасно.
Розв'язки
Офіціант
Відносно простим розв'язком є додавання офіціанта. Філософи мають просити в нього дозволу перед тим як взяти виделку. Офіціант знає які виделки використовуються, і не допускає взаємного блокування. Таким чином, якщо використовуються 4 виделки, він не дасть п'ятому філософу взяти виделку, і її візьме перший. Коли він поїсть, він відпустить обидві, і п'ятий та другий зможуть поїсти…
Ієрархія ресурсів
Іншим простим розв'язком є введення над виделками часткового порядку. Пронумеруємо їх від 1 до 5.
Після цього, введемо правило, що філософ має право брати спочатку виделку з меншим номером, і тільки після цього може брати виделку з більшим. Таким чином, якщо чотири філософи візьмуть виделки з меншим номером, на столі залишиться вільною тільки виделка 5. Філософ що знаходиться між 5 та 1 не зможе її взяти, бо він мусить спочатку взяти 1, яка вже зайнята, і тому її зможе взяти філософ що знаходиться між 5 та 4, і таким чином наїстись.
Цей розв'язок був запропонований Едсгером Дейкстрою.
Приклад розв'язку проблеми мовою ANI[1]
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;
};