Page 120 - 6571

ЛЕКЦІЯ 14

МЕХАНІЗМ ВЗАЄМНОГО ВИКЛЮЧЕННЯ ПРОЦЕСІВ

14.1 Задача про філософів, що обідають

Розглянемо дві класичні задачі: про філософів, що обідають

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

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

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

ілюстрації та порівняння різних механізмів синхронізації.
Формулювання даної задачі звучить наступним чином: п’ять
філософів сидять біля круглого столу. Вони проводять життя,

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

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

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

ки (наприклад, коли кожен із них тримає по одній вилці і не хоче
віддавати її іншим).
Описана вище задача проілюстрована на рис. 14.1. Зрозуміло,

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

119