Материал: 6262
161
В данном подразделе, на классическом примере «Задачи об обедающих философах», мы рассмотрим основные этапы подготовки и реализации проекта по синхронизации процессов, которые могут приводить к взаимным блокировкам.
4.5.1 Описание задачи
Класический вариант «Задачи об обедающих философах» демонстрируется рисунком 4.2 и следующим описанием:
•За круглым столом сидит несколько философов.
•В каждый момент времени каждый из них либо беседует, либо ест.
•Для процесса еды одновременно требуются две вилки. Поэтому, прежде чем
в очередной раз перейти от беседы к приему пищи, философу необходимо дождаться, пока освободятся обе вилки - слева и справа от него, и взять их в руки.
•Немного поев, философ кладет вилки на стол и вновь присоединяется к беседе.
•Требуется разработать программную модель обеда философов.
Рисунок 4.2 - Схема стола для задачи обедающих философов
Главная проблема в этой задаче, - корректная дисциплина захвата и освобождения вилок, иначе например, если каждый из философов, одновременно с другими, возьмется за вилку, лежащую слева от него, и будет ждать освобождения правой, то - обед не завершится никогда.
Прежде, чем приступить к реализации алгоритма синхронизаци процессов-фило- софов, определимся с общей стратегией решения задачи.
162
4.5.2 Выбор стратегии решения
Одним из общих подходов решения задач синхронизации множества асинхронно взаимодействующих процессов является разделение структуры всего алго-ритма на
два уровня иерархии:
•первый — нижний уровень реализует сами действующие процессы, выделяя те общие ресурсы, которые нужны ему для обеспечия функционирования;
•второй — верхний уровень (программа-монитор) обеспечивает нижний уро-
вень необходимыми данными, проводит первоначальную подготовку разделяемых ресурсов и, по возможности, устраняет возникающие проблемы синхронизации процессов нижнего уровня.
Для нашего случая:
•нижний уровень — программы процессов-философов, которые борятся за ресурс в виде двух вилок;
•верхний уровень — программа-монитор, которая подготавливает набор сема-
форов для синхронизации всех процессов-философов, создает и запускает эти процессы и отслеживает их завершение.
Далее, переходим к построению и реализации моделей каждого уровня.
4.5.3 Модель философа
Каждый философ ведет себя независимо от других: он ест и беседует, причем время, необходимое для беседы и поедания порции (части) своего обеда, не привязано к аналогичным действиям других философов.
Для моделирования такой независимости предполагаем, что:
•время одной порции разговора философа - случайное значение trnd;
•время одной порции поедания обеда философа - случайное значение ernd;
•общее время поедания всего обеда — ограничено, поэтому философ может завершить обед в несколько приемов.
Описание действий философа:
•философ какое-то время беседует (trnd), затем пытается взять вилки слева и справа от себя;
•когда ему это удается, он некоторое время ест (ernd), после чего освобождает вилки;
•так продолжается до тех пор, пока не будет съеден весь обед, после чего программа, моделирующая действия философа, закончит свою работу.
Таким образом, мы видим, что нормальной работы философа необходимы два ресурса, которые обеспечиваются двумя семафорами.
163
Чтобы реализовать корректную модель программы-философа, необходимо уточнить исходные данные, передаваемые ей в качестве аргументов.
Учитывая, что отдельный философ использует только два разделяемых ресурса из общего их колличества, равного общему числу философов, то для запуска программы достаточно только трех аргументов:
•argv[1] — идентификатор набора семафоров;
•argv[2] — общее число философов;
•argv[3] — порядковый номер конкретного философа за столом.
Замечание
Философы нумеруются, начиная с 1. Вилки нумеруются, начиная 0. Номер вилки — номер семафора.
Значение семафора = 1, когда вилка — свободна. Значение семафора = 0, когда вилка — занята.
В условиях такой модели, исходный текст программы-философа может быть представлен листингом 4.3.
Листинг 4.3 - Алгоритм, моделирующий действия философа за столом
#include <unistd.h> #include <stdlib.h> #include <stdio.h> #include <sys/sem.h>
// Процесс обеда одного философа |
|
|
||
#define ernd (rand () % 3 + 1) |
// Время еды |
философа |
||
#define trnd |
(rand () % 5 + 1) |
// Время беседы философа |
||
#define FO |
15 |
|
// Общее время |
обеда отдельного философа |
int main (int argc, char *argv []) { |
|
|||
int semid; |
// Идентификатор набора семафоров |
|||
int qph; |
// Число философов |
|
||
int no; |
|
// Номер философа |
|
|
int t; |
|
// Время очередного отрезка еды или беседы |
||
int fo; |
|
// Время до конца обеда |
|
|
// Массив из двух семафоров, соответствующих левой и правой вилке struct sembuf sembuf [2];
puts("Запущена программа: lab10.3"); if (argc != 4) {
puts ("Запусти: lab10.3 идентификатор_набора_семафоров число_философов номер_философа"); return (1);
} |
|
|
|
fo = FO; |
|
// Время до конца обеда |
|
sscanf (argv [1], "%d", |
&semid); |
// Идентификатор |
набора семафоров |
sscanf (argv [2], "%d", |
&qph); |
// Общее чило |
философов |
sscanf (argv [3], "%d", |
&no); |
// Номер данного |
философа |
// Выбор вилок |
|
|
|
sembuf [0].sem_num = no - 1; |
// Левая |
|
|
sembuf [0].sem_flg = 0; |
|
// Операция с блокировкой |
|
|
164 |
sembuf [1].sem_num = no % qph; |
// Правая |
sembuf [1].sem_flg = 0; |
// Операция с блокировкой |
while (fo > 0) { |
// Обед |
// Философ говорит
printf ("lab10.3: Философ %d беседует\n", no); t = trnd; sleep (t); fo -= t;
//Пытается взять вилки sembuf [0].sem_op = -1; sembuf [1].sem_op = -1;
if (semop (semid, sembuf, 2) < 0) { perror ("lab10.3: SEMOP():"); return (1);
}
//Ест
printf ("Философ %d ест\n", no); t = ernd; sleep (t); fo -= t;
// Отдает вилки
sembuf [0].sem_op = 1; sembuf [1].sem_op = 1;
if (semop (semid, sembuf, 2) < 0) { perror ("lab10.3: semop():"); return (2);
}
}
printf ("lab10.3: Философ %d закончил обед\n", no); return 0;
}
Замечание
Откомпилированную программу-философ следует поместить, например, в директорию /home/upk/bin, тогда она может быть запущена без указания абсолютного пути ее расположения.
4.5.4 Программа-монитор
Для рассматриваемой задачи, учитывая, что количество обедающих философов задано некоторой константой QPH, алгоритм работы достаточно прост:
•порождается набор семафоров QPH: по одному семафору на каждую вилку;
•устанавливаются начальные значения семафоров: занятой вилке будет соответствовать значение 0, свободной — 1;
•запускаются QPH процессов, каждый из которых представляет одного фило-
софа, передавая им в качестве аргументов: идентификатор набора семафоров, общее количество всех философов и место конкретного философа за столом: философы нумеруются от 1 до QPH;
•ожидается, завершение работы всех процессов: когда все философы съедят свой обед;
•удаляется весь набор семафоров.
Исходный текст такой программы-монитора демонстрируется на листинге 4.4.
165
Листинг 4.4 - Алгоритм программы-монитора, обеспечивающий работу процессов
#include <unistd.h> #include <stdio.h> #include <sys/sem.h> #include <sys/wait.h>
// Программа-монитор обеда философов
#define QPH 5 |
// Количество философов |
#define ARG_SIZE 20 |
// Размер читаемых аргументов |
int main (void) { |
|
int key; |
// Ключ набора семафоров |
int semid; |
// Идентификатор набора семафоров |
int no; |
// Номер философа и/или вилки |
// Строки для аргументов дочерних процессов
char ssemid [ARG_SIZE], sno [ARG_SIZE], sqph [ARG_SIZE];
puts("Запущена программа: lab10.4");
// Создание и инициализация набора семафоров: по семафору на вилку key = ftok ("/home/upk/lab10", 2);
if ((semid = semget (key, QPH, 0600 | IPC_CREAT)) < 0) { perror ("SEMGET");
return (1);
}
for (no = 0; no < QPH; no++) {
// Значение семафора устанавливается в 1 if (semctl (semid, no, SETVAL, 1) < 0) {
perror ("SETVAL"); return (2);
}
}
//Подготовка аргументов
sprintf (ssemid, |
"%d", semid); |
sprintf (sqph, |
"%d", QPH); |
// Все - к столу |
*/ |
for (no = 1; no <= QPH; no++) { switch (fork ()) {
case -1:
perror ("FORK"); return (3);
case 0:
sprintf (sno, "%d", no); //Подготовка аргументов
execlp ("lab10.3", "lab10.3", ssemid, sqph, sno, (char *) 0); perror ("EXEC");
return (4);
}
}
//Ожидание завершения обеда всех философов while (wait (NULL) > 0) ;
//Удаление набора семафоров
if (semctl (semid, 0, IPC_RMID) < 0) { perror ("SEMCTL");
return (5);
}
puts("lab10.4 - завершила работу..."); return 0;
}