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

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

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

Умова

За круглим столом сидить 5 (чи в загальному випадку n, але в цій статті для простоти буде 5) філософів. Між ними лежить стільки ж вилок, тобто кожен має виделку зліва, і виделку справа. Філософи в кожен момент часу можуть займатись тільки двома речами - їсти, або думати. Коли філософ їсть - він не може думати, а коли думає - не може їсти. Їдять вони дуже довгі макарони, з якими важко, чи навіть зовсім неможливо справитись однією виделкою, тому кожному потрібні дві (інший варіант задачі описує рис, і китайські палички).

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

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

Розв'язки

Офіціант

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