Задача об обедающих философах

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

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

Простейшее решение – представить каждую палочку в виде семафора. Философ пытается захватить палочку выполнением операции wait, а освобождает ее с помощью операции signal.

var chopstick: array [0..4] of semaphore;

Каждый элемент массива первоначально инициализируется значением 1.

Схема работы i-го философа будет следующей:

Repeat

wait(chopstick[i]);

wait(chopstick[(i+1) mod 5]);

...

eat

...

signal(chopstick[i]);

signal(chopstick[(i+1) mod 5]);

...

think

...

until false;

Такое решение гарантирует, что два соседа не смогут одновременно есть. Но оно не может быть принято, так как может привести к тупику. Представим, что все пять философов проголодались одновременно и, успели взять по одной палочке. Вторую палочку они уже не смогут взять никогда, так как соответствующий семафор будет иметь значение 0.

Перечислим возможные решения проблемы:

­ разрешить не более, чем четырем философам одновременно садиться за стол;

­ разрешить философу брать палочки, только если обе палочки свободны (появится критический участок);

­ использовать асимметричное решение: нечетный философ сначала берет левую палочку, а четный – правую.

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

Двоичные семафоры

Двоичный семафор – это переменная, которая может принимать только два значения: 0 и 1. Такой семафор проще для реализации с точки зрения компьютерной системы. Однако такие семафоры сложнее для использования.

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

var s1,s2,s3: binary_semaphore;

c: integer;

Начальное значение семафоров s1 и s3 – 1, семафора s2 – 0, начальное значение переменной c равно начальному значению счетчика.

Тогда операцию wait можно выразить следующим образом:

wait(s3);

wait(s1);

с:= c - 1;

if c<0 then

Begin

signal(s1);

wait(s2);

End

Else

signal(s1);

signal(s3);

Операция signal будет описываться так:

wait(s1);

с:= c + 1;

if c<=0 then

signal(s2);

signal(s1);

Заметим, что двоичный семафор s2 влияет только на работу операции wait.

Сигналы

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

Примером асинхронного сигнала является сигнал с терминала. Во многих ОС предусматривается оперативное снятие процесса с выполнения. Для этого пользователь может нажать некоторую комбинацию клавиш (Ctrl+C, Ctrl+Break), в результате чего ОС вырабатывает сигнал и направляет его активному процессу. Сигнал может поступить в любой момент выполнения процесса, то есть он является асинхронным, требуя от процесса немедленного завершения работы. В данном случае реакцией на сигнал является безусловное завершение процесса.

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

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

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

Контрольные вопросы

1. Что такое состояние состязания?

2. Что означает термин «взаимное исключение»?

3. Что такое критический участок (секция)?

4. Почему для обеспечения взаимного исключения недостаточно логической переменной?

5. Как команда test and set помогает обеспечить взаимное исключение?

6. Что такое семафор? Как реализуются семафоры?

 

ТУПИКОВЫЕ СИТУАЦИИ

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