Проблема філософів, що обідають

Ілюстрація задачі

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

Умова

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

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

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

Розв'язки

Офіціант

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

Див. також

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

Посилання

• Java-аплет, Проблема філософів, що обідають (англ.) (фр.) (нім.)