Классические задачи синхронизации: “производители-потребители”, “проблема обедающих философов”, “проблема спящего брадобрея”.

Производители-потребители

Проблема обедающих философов

Формулировка задачи

Пять философов сидят вокруг круглого стола. Перед каждым стоит тарелка с бесконечной лапшой. Ещё на столе лежат пять вилок, каждая ровно посередине между двумя ближайшими тарелками. Чтобы есть лапшу, каждому философу нужно держать в руках две вилки.

Философ может либо есть, либо размышлять. За одно действие философ может взять одну вилку со стола в руку или положить её из руки на стол.

Из-за того, что они будут делать всё синхронно, они снова не смогут приступить к еде: они вечно будут поднимать и опускать левую вилку, пока не умрут от голода. Это - проблема ресурсного голодания, возникающая из-за отсутствия синхронизации.

В прошлый раз мы обсуждали, почему это задача не так тривиальна, как может показаться. Сейчас мы рассмотрим три разных способа решения задачи.

1. Официант

Есть некий внешний человек, который и говорит, можно ли взять вилку или нет. Если, допустим, четыре философа держат по одной вилке, то пятому официант запретит брать вилку, чтобы не заблокировать остальных.

2. Иерархия вилок

Нумеруем вилки от 1 до 5. Каждый раз философ берёт вилку с меньшим номером, а потом с большим, а кладёт — наоборот. Если вилки с наименьшим номером нет, то философ ничего не берёт. Тогда следующим шагом эту вилку возьмёт тот философ, который уже взял одну вилку.

3. Монитор

Философы, прежде чем начать брать вилки, проверяют, что их соседи не едят. Тогда сначала будут есть философы 1 и 3, потом — 2 и 4. Чтобы философ 5 (или любой другой философ) не остался голодным, можно ещё отслеживать, сколько раз голодный философ ел, прежде чем он возьмет первую вилку. Если философ ел больше раз, чем другие, он тоже не может приступить к еде.

Опишите последствия повреждения блока данных для заданного файла: а) для непрерывных, б) связанных, в) индексированных (основанных на использовании таблицы) схем размещения блоков).