Классические задачи синхронизации процессов

«Обедающие философы»

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

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

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

void philosopher (int i) /* i – номер философа от 0 до 4*/

{

while (TRUE)

{

think(); /*философ думает*/

take_fork(i); /*берет левую вилку*/

take_fork((i+1)%N); /*берет правую вилку*/

eat(); /*ест*/

put_fork(i); /*кладет обратно левую вилку*/

put_fork((i+1)%N); /* кладет обратно правую вилку */

}

}

Функция take_fork() описывает поведение философа по захвату вилки: он ждет, пока указанная вилка не освободится, и забирает ее.

На первый взгляд, все просто, однако, данное решение может привести к тупиковой ситуации. Что произойдет, если все философы захотят есть в одно и то же время? Каждый из них получит доступ к своей левой вилке и будет находиться в состоянии ожидания второй вилки до бесконечности. Другим решением может быть алгоритм, который обеспечивает доступ к вилкам только четырем из пяти философов. Тогда всегда среди четырех философов по крайней мере один будет иметь доступ к двум вилкам. Данное решение не имеет тупиковой ситуации. Здесь определяется количество философов, далее идут макросы для определения номеров левой, правой вилки и три состояния философов: философ думает, философ голоден и философ ест. Определяется тип данных semaphore и массив состояний каждого из философов – массив state. Далее определяется один семафор для реализации критической секции и по одному семафору на каждого философа – это массив семафоров s. Вот, обратите внимание, они выделены цветом, и далее операции с этими семафорами тоже будут выделены цветом. Основная функция – это философы. Философ думает затем, когда он проголодается, он вызывает функцию take_forks(), затем происходит еда, и вызывается функция put_forks(). В функции take_forks() в первую очередь идет вход в критическую секцию одного конкретного философа. Критическая секция охраняется семафором mutex. В момент входа в критическую секцию семафор mutex охраняет массив состояний философа. Идет изменение состояния на голоден, и вызывается функция test(). Затем производится выход из критической секции: поднятие семафора mutex и опускание семафора конкретного философа. В функции test() происходит проверка: что делает левый сосед, и что делает правый сосед. Если состояние голоден и левый сосед не ест и правый сосед не ест, т.е. вилки свободны, то состояние философа меняется на состояние поедания и поднимается семафор этого философа. Итак опускание семафора происходит в take_forks(), а поднятие в test(). Т.е. если семафор не был поднят в test() (не выполнилось условие, что оба соседа не едят), то в момент down() на семафоре в функции take_forks() философ будет заблокирован и будет ожидать, пока один из соседей не освободит его состояние, что происходит в функции put_forks(). Здесь тоже самое: опускается семафор для хранения критической секции, которая охраняет массив состояний. Состояние изменяется на «думающий» и производится тест на левого и правого соседа. В этот момент, когда посылается тест для обоих соседей, если один из этих соседей был ранее заблокирован из-за того, что его вилка была занята нашим философом, то в этот момент он разблокируется и сможет взять вилку. Обращаю ваше внимание на то, что семафор mutex необходим для охраны массива состояний философов. Т.е. здесь массив состояний философов является разделяемым ресурсом, потому что эти состояния проверяются как самим философом так и его левым и правым соседом (функция test()). Поэтому необходимо охранять их, потому что если доступ к ним будет осуществляться со стороны двух или более процессов одновременно, то один из процессов может проверить это состояние, в то время как другой процесс будет его изменять. Чтобы такого не происходило необходимо сделать этот ресурс критическим и охранять его семафором, что и делает семафор mutex. Массив семафоров s используется для того, чтобы блокировать философов, которые не могут в данный момент взять вилку и разблокирование философов происходит в тот момент, когда сосед вилки освобождает. Т.е. это решение уже более сложное, однако, оно позволяет избежать тупиковых ситуаций, но не гарантирует отсутствие дискриминации, т.е. здесь возможно ситуация, что поскольку в момент когда разблокируется один из соседей всегда возможна ситуация, что вилку захватит другой сосед, соответственно второй сосед может остаться без вилок.

Алгоритм решения может быть представлен следующим образом:

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

# define LEFT (i-1)%N /* номер легого соседа для i-ого философа */

# define RIGHT (i+1)%N /* номер правого соседа для i-ого философа*/

# define THINKING 0 /* философ думает */

# define HUNGRY 1 /* философ голоден */

# define EATING 2 /* философ ест */

typedef int semaphore; /* тип данных «семафор» */

int state[N]={0,0,0,0,0}; /* массив состояний философов */

semaphore mutex=1; /* семафор для критической секции */

semaphore s[N]; /* по одному семафору на философа */

void philosopher (int i)

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

{

while (TRUE) /* бесконечный цикл */

{

think(); /* философ думает */

take_forks(i); /*философ берет обе вилки или блокируется */

eat(); /* философ ест */

put_forks(i); /* философ освобожает обе вилки */

}

}

void take_forks(int i)

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

{

down(mutex); /* вход в критическую секцию */

state[i] = HUNGRY; /*записываем, что i-ый философ голоден */

test(i); /* попытка взять обе вилки */

up(mutex); /* выход из критической секции */

down(s[i]); /* блокируемся, если вилок нет */

}

void put_forks(i)

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

{

down(mutex); /* вход в критическую секцию */

state[i] = THINKING; /* философ закончил есть */

test(LEFT);

/* проверить может ли левый сосед сейчас есть */

test(RIGHT);

/* проверить может ли правый сосед сейчас есть*/

up(mutex); /* выход из критической секции */

}

void test(i)

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

{if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING)

{state[i] = EATING;

up (s[i]);}

}