Проблема філософів що обідають — типова проблема синхронізації процесів, що може виникати при паралельних обчисленнях.
Умова За круглим столом сидить п'ять філософів, які не спілкуються один з одним. Перед кожним стоїть одна тарілка спагеті, а також на столі лежить п'ять виделок, по одній зліва і по одній справа від тарілки. Кожен філософ в певний момент часу може або їсти, або думати. Щоб поїсти дуже довгі макарони, філософу під час їжі потрібно мати дві виделки (альтернативний варіант задачі описує рис і китайські палички).
Коли філософ їсть, він бере дві виделки зі столу, коли поїв — кладе виделки на стіл і починає думати. Через деякий час процес повторюється.
В результаті цього за столом може виникнути ситуація, при якій філософи одномоментно почали їсти і кожен взяв тільки одну виделку. Оскільки всі філософи тримають одну виделку, і чекають на іншу, це призводить до взаємного блокування. Навіть якщо кожен філософ буде класти на стіл взяту раніше одну виделку, після неможливості взяти іншу виделку через деякий час, а потім знову пробуватиме взяти спочатку одну, а потім іншу, це може також не допомогти їм пообідати, якщо вони повторно братимуть виделки одночасно.
Розв'язки
Офіціант Відносно простим розв'язком є додавання офіціанта. Філософи мають просити в нього дозволу перед тим як взяти виделку. Офіціант знає які виделки використовуються, і не допускає взаємного блокування. Таким чином, якщо використовуються 4 виделки, він не дасть п'ятому філософу взяти виделку, і її візьме перший. Коли він поїсть, він відпустить обидві, і п'ятий та другий зможуть поїсти…
Ієрархія ресурсів Іншим простим розв'язком є введення над виделками часткового порядку. Пронумеруємо їх від 1 до 5.
Після цього, введемо правило, що філософ має право брати спочатку виделку з меншим номером, і тільки після цього може брати виделку з більшим. Таким чином, якщо чотири філософи візьмуть виделки з меншим номером, на столі залишиться вільною тільки виделка 5. Філософ що знаходиться між 5 та 1 не зможе її взяти, бо він мусить спочатку взяти 1, яка вже зайнята, і тому її зможе взяти філософ що знаходиться між 5 та 4, і таким чином наїстись.
Цей розв'язок був запропонований Едсгером Дейкстрою.
Приклад розв'язку проблеми мовою ANIhttp://code.google.com/p/anic/ 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;
Див. також Задача постачальника-споживача
Примітки
Література
Dijkstra, E. W. (1971, June). Hierarchical ordering of sequential processes. Acta Informatica 1(2): 115–138. Lehmann, D. J., Rabin M. O, (1981). On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. Principles Of Programming Languages 1981 (POPL'81), pp. 133–138.
Посилання
Java-аплет, Проблема філософів, що обідають