Жизнь философа состоит из чередующихся периодов поглощения пищи и размышлений. (Разумеется, это абстракция, даже применительно к философам, но остальные процессы жизнедеятельности для нашей задачи несущественны.) Когда философ голоден, он пытается получить две вилки, левую и правую, в любом порядке. Если ему удалось завладеть двумя вилками, он некоторое время ест, затем кладет вилки обратно и продолжает размышления. Вопрос состоит в следующем: можно ли написать алгоритм, который моделирует эти действия для каждого философа и никогда не застревает? (Кое-кто считает, что необходимость двух вилок выглядит несколько искусственно. Возможно, нам следует заменить итальянскую пищу блюдами китайской кухни, спагетти - рисом, а вилки - соответствующими палочками.)

В листинге 2.8 представлено очевидное решение проблемы. Процедура take fork ждет, пока указанная вилка не освободится, и берет ее. К сожалению, это решение неверно - представьте себе, что все пять философов возьмут одновременно свои левые вилки. Каждый останется без правой вилки, и произойдет взаимоблокировка.

Листинг 2.8. Неверное решение проблемы обедающих философов

#define N 5 /* Количество философов */

void philosospher(int i) /* i - номер философа, от О до 4 */

while(TRUE) {

thinkO: /* Философ размышляет */

take fогк(i): /* Берет левую вилку */

take fork((i+l) * N): /* Берет правую вилку */ eatO: /* Спагетти, ням-ням */

put fork(i): /* Кладет на стол левую вилку */

put fork((i+l) * N): /* Кладет на стол правую вилку */

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

Вы можете подумать: Если философы будут размышлять в течение некоторого случайно выбранного промежутка времени после неудачной попытки взять правую вилку, вероятность того, что все процессы будут продолжать топтаться на месте хотя бы в течение часа, невелика . Это правильно, и для большинства приложений повторение попытки спустя некоторое время снимает проблему. Например, в локальной сети Ethernet в ситуации, когда два компьютера посылают пакеты одновременно, каждый должен подождать случайно заданное время и повторить попытку - на практике это решение хорошо работает. Тем не менее

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

В листинг 2.8 можно внести улучшение, исключающее взаимоблокировку и зависание процесса: защитить пять операторов, следующих за запросом think, бинарным семафором. Тогда философ должен будет выполнить операцию down на переменной mutex прежде, чем потянуться к вилкам. А после возврата вилок на место ему следует выполнить операцию up на переменной mutex. С теоретической точки зрения решение вполне подходит. С позиций практики возникают проблемы с эффективностью: в каждый момент времени может есть спагетти только один философ. Но вилок пять, поэтому необходимо разрешить есть в каждый момент времени двум философам.

Решение, представленное в листинге 2.9, исключает взаимоблокировку и позволяет реализовать максимально возможный параллелизм для любого числа философов. Здесь используется массив state для отслеживания душевного состояния каждого философа: он либо ест, либо размышляет, либо голодает (пытаясь получить вилки). Философ может начать есть, только если ни один из его соседей не ест. Соседи философа г определяются макросами LEFT и RIGHT (то есть если i = 2, то LEinr = 1 и RIGHT = 3).

Листинг 2.9. Решение задачи обедающих философов

#define N #define LEFT #define RIGHT #define THINKING #define HUNGRY #define EATING

(i+N.l)*N

(i+l)*N

/* Количество философов */

/* Номер левого соседа философа с номером i */

/* Номер правого соседа философа с номером i */

typedef int semaphore:

int state[N]:

semaphore mutex - 1: semaphore s[N]:

void philosopher(int i) {

while (TRUE) { thinkO: take forks(i): eatO:

put forks(i):

Философ размышляет */ Философ пытается получить вилки */ Философ ест */

Семафоры - особый вид целочисленных переменных */

Массив для отслеживания состояния каждого /* философа */

/* Взаимоисключение для критических областей */ /* Каждому философу по семафору */

/* i - номер философа, от О до N-1 */

/* Повторять до бесконечности */

/* Философ размышляет */

/* Получает две вилки или блокируется */

/* Спагетти, ням-ням */

/* Кладет на стол обе вилки */

void take forks(int i) {

downC&mutex): state:i] = HUNGRY: test(i): up(&mutex): down(&s[i]):

/* i - номер философа, от О до N-l*/

/* Вход в критическую область */

/* Фиксация наличия голодного философа */

/* Попытка получить две вилки */

/* Выход из критической области */

/* Блокировка, если вилок не досталось */

void put forks(i) {

down(&mutex); stateCi] = THINKING: test(LEFT): test(RIGHT): upC&mutex):

/* 1 - номер философа, от О до N-1*/

/* Вход в критическую область */

/* Философ перестал есть */

/* Проверить, может ли есть сосед слева */

/* Проверить, может ли есть сосед справа */

/* Выход из критической области */

void test(i)

/* i - номер философа, от О до N-1*/

state[RIGHT] != EATING) {

if (state[i] == HUNGRY && state[LEFT] != EATING state[i] = EATING: up(&s[i]):

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

2.3.2. Проблема читателей и писателей

Проблема обедающих философов полезна для моделирования процессов, соревнующихся за монопольный доступ к офаниченному количеству ресурсов, например к устройствам ввода/вывода. Другой известной задачей является проблема читателей и писателей [17], моделирующая доступ к базе данных. Представьте себе базу данных бронирования билетов на самолет, к которой пытается получить доступ множество клиентов. Можно разрешить одновременное считывание данных из базы, но если процесс записывает информацию в базу, доступ остальных процессов должен быть прекращен, даже доступ на чтение. Как запрограммировать читателей и писателей? Одно из решений представлено в листинге 2.10.

Листинг 2.10. Решение проблемы читателей и писателей

typedef int semaphore; semaphore mutex = 1: semaphore db = 1: int rc = 0:

/* Воспользуйтесь своим воображением */

/* Контроль доступа к гс */

/* Контроль доступа к базе данных */

/* Количество процессов, читающих или желающих */

/* читать */

void reader(void) {

while (TRUE) { down(&mutex): rc = rc+1:

if (rc == 1) down(&db): up(&mutex): read data base(): down(&mutex):

/* Повторять до бесконечности */

/* Получение монопольного доступа к гс */

/* Одним читающим процессом больше */

/* Если этот читающий процесс - первый... */

/* Отказ от монопольного доступа к гс */

/* Доступ к данным */

/* Получение монопольного доступа к гс */