Главная страница

Содержание занятия


Скачать 0.66 Mb.
НазваниеСодержание занятия
Анкор14314421
Дата02.05.2023
Размер0.66 Mb.
Формат файлаrtf
Имя файла330383.rtf
ТипДокументы
#1103574
страница4 из 5
1   2   3   4   5

1.4 Семафоры



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

У семафора есть значение, которое представляется целым числом в диапазоне от 0 до 32767.

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

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

Описание перечисленных функций представлено в пример 8.31.

#include

int semget (key_t key, int nsems, int semflg);

int semop (int semid, struct sembuf *sops,

size_t nsops);

int semctl (int semid, int semnum,

int cmd, ...);

Листинг 8.31. Описание функций для работы с семафорами.

Структура semid_ds, ассоциированная с идентификатором набора семафоров, должна содержать по крайней мере следующие поля.

struct ipc_perm sem_perm;

/* Данные о правах доступа к

набору семафоров */

unsigned short sem_nsems;

/* Число семафоров в наборе */

time_t sem_otime;

/* Время последней операции semop() */

time_t sem_ctime;

/* Время последнего изменения

посредством semctl() */

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

unsigned short semval;

/* Значение семафора */

pid_t sempid;

/* Идентификатор процесса, выполнившего

последнюю операцию над семафором */

unsigned short semncnt;

/* Число процессов, ожидающих увеличения

текущего значения семафора */

unsigned short semzcnt;

/* Число процессов, ожидающих обнуления

значения семафора */

Функция semget() аналогична msgget(); аргумент nsems задает число семафоров в наборе. Структура semid_ds инициализируется так же, как msqid_ds. Безымянные структуры, соответствующие отдельным семафорам, функцией semget() не инициализируются.

Операции, выполняемые посредством функции semop(), задаются массивом sops с числом элементов nsops, состоящим из структур типа sembuf , каждая из которых содержит по крайней мере следующие поля.

unsigned short sem_num;

/* Номер семафора в наборе (нумерация с нуля) */

short sem_op;

/* Запрашиваемая операция над семафором */

short sem_flg;

/* Флаги операции */

Операция над семафором определяется значением поля sem_op: положительное значение предписывает увеличить значение семафора на указанную величину, отрицательное - уменьшить, нулевое - сравнить с нулем. Вторая операция не может быть успешно выполнена, если в результате значение семафора становится отрицательным, а третья - если значение семафора ненулевое.

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

sembuf [0].sem_num = 1;

sembuf [0].sem_flg = 0;

sembuf [0].sem_op = -2;

sembuf [1].sem_num = 0;

sembuf [1].sem_flg = IPC_NOWAIT;

sembuf [1].sem_op = 0;

Листинг 8.32. Пример задания массива операций над семафорами.

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

Аргументы semid (идентификатор набора семафоров) и semnum (номер семафора в наборе) определяют объект, над которым выполняется управляющее действие, задаваемое значением аргумента cmd. Если объектом является набор, значение semnum игнорируется.

Для некоторых действий задействован четвертый аргумент (пример 8.33).

union semun {

int val;

struct semid_ds *buf;

unsigned short *array;

} arg;

Листинг 8.33. Описание четвертого (дополнительного) аргумента функции semctl().

Среди допустимых действий - GETVAL (получить значение семафора и выдать его в качестве результата) и SETVAL (установить значение семафора равным arg.val). Имеются и аналогичные групповые действия - GETALL (прочитать значения всех семафоров набора и поместить их в массив arg.array) и SETALL (установить значения всех семафоров набора равными значениям элементов массива). Предусмотрены действия, позволяющие выяснить идентификатор процесса, выполнившего последнюю операцию над семафором (GETPID), а также число процессов, ожидающих увеличения/обнуления (GETNCNT/GETZCNT) значения семафора (информация о процессах выдается в качестве результата, пример 8.34).

val = semctl (semid, semnum, GETVAL);

arg.val = ...;

if (semctl (semid, semnum, SETVAL, arg) == -1) ...;

arg.array = (unsigned short *) malloc (nsems * sizeof (unsigned short));

err = semctl (semid, 0, GETALL, arg);

for (i = 0; i < nsems; i++) arg.array [i] = ...;

err = semctl (semid, 0, SETALL, arg);

lpid = semctl (semid, semnum, GETPID);

ncnt = semctl (semid, semnum, GETNCNT);

zcnt = semctl (semid, semnum, GETZCNT);

Листинг 8.34. Примеры управляющих действий над семафорами.

Наконец, для семафоров, как и для очередей сообщений, определены управляющие команды IPC_STAT (получить информацию о состоянии набора семафоров), IPC_SET (переустановить характеристики), IPC_RMID (удалить набор семафоров), представленные в пример 8.35.

arg.buf = (struct semid_ds *) malloc (sizeof (struct semid_ds);

err = semctl (semid, 0, IPC_STAT, arg);

arg.buf->sem_perm.mode = 0644;

err = semctl (semid, 0, IPC_SET, arg);

Листинг 8.35. Дополнительные примеры управляющих действий над семафорами.

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

Предлагаемое решение состоит из двух программ. Первая (пример 8.36) реализует процесс-монитор, который порождает набор семафоров (по одному семафору на каждую вилку), устанавливает начальные значения семафоров (занятой вилке будет соответствовать значение 0, свободной - 1), запускает несколько процессов, представляющих философов, указывая место за столом (в качестве одного из аргументов передается число от 1 до QPH), ожидает, пока все процессы завершатся (все философы съедят свой обед), и удаляет набор семафоров. Предполагается (для нужд функции ftok()), что исходный текст программы находится в файле phdin.c (точнее, что такой файл существует).

#include

#include

#include

#include

/* Программа-монитор обеда философов */

#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];

/* Создание и инициализация набора семафоров */

/* (по семафору на вилку) */

key = ftok ("phdin.c", 'C');

if ((semid = semget (key, QPH, 0600 | IPC_CREAT)) < 0) {

perror ("SEMGET");

return (1);

}

for (no = 0; no < QPH; no++) {

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);

execl ("./phil", "phil", ssemid, sqph, sno, (char *) 0);

perror ("EXEC");

return (4);

}

}
/* Ожидание завершения обеда */

for (no = 1; no <= QPH; no++) {

(void) wait (NULL);

}

/* Удаление набора семафоров */

if (semctl (semid, 0, IPC_RMID) < 0) {

perror ("SEMCTL");

return (5);

}

return 0;

}

Листинг 8.36. Процесс-монитор для обеда философов.

Вторая программа (пример 8.37) описывает обед каждого философа. Философ какое-то время беседует (случайное значение trnd), затем пытается взять вилки слева и справа от себя, когда ему это удается, некоторое время ест (случайное значение ernd), после чего освобождает вилки. Так продолжается до тех пор, пока не будет съеден весь обед. Предполагается, что выполнимый файл программы называется phil.

#include

#include

#include

#include

/* Процесс обеда одного философа */

#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];

if (argc != 4) {

fprintf (stderr, "Использование: %s идентификатор_набора_семафоров число_философов номер_философа \n", argv [0]);

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;

sembuf [1].sem_num = no % qph; /* Правая */

sembuf [1].sem_flg = 0;

while (fo > 0) { /* Обед */

/* Философ говорит */

printf ("Философ %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 ("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 ("SEMOP");

return (2);

}

}

printf ("Философ %d закончил обед\n", no);

return 0;

}

Листинг 8.37. Программа, описывающая обед одного философа.

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

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

/* Обедающие философы. Запуск:

mudrecProc [-a | -p | -I -V] [-t число_секунд] имя_философа ...

Опции:

-t число_секунд - сколько секунд моделируется

Стратегии захвата вилок:

-a - сначала захватывается вилка с меньшим номером;

-I - некорректная (но эффективная) интеллигентная стратегия: во время

ожидания уже захваченная вилка кладется;

-p - сначала захватывается нечетная вилка;

-V - использован групповой захват семафоров.

Пример запуска: mudrecProc -p -t 600 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

*/

static char rcsid[] __attribute__((unused)) = \

"$Id: mudrecProc.c,v 1.7 2003/11/11 13:14:07 sambor Exp $";

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

union semun {

int val;

struct semid_ds *buf;

unsigned short *array;

} arg;

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)>(b)?(b):(a))

struct mudrec {

long num;

char *name;

int left_fork, right_fork;

int eat_time, wait_time, think_time, max_wait_time;

int count;

};

int Stop; /* Семафор для синхронизации выхода */

/* Различные дескрипторы */

int protokol [2] = {-1, -1};

#define pFdIn (protokol [1])

#define pFdOut (protokol [0])

int semFork; /* Вилки */

int from_fil; /* Очередь для возврата результатов */

/* Разные алгоритмы захвата вилок */

static void get_forks_simple (struct mudrec *this);

static void get_forks_parity (struct mudrec *this);

static void get_forks_maybe_infinit_time (struct mudrec *this);

static void get_forks_use_groups (struct mudrec *this);

/* Используемый метод захвата вилок */

void (*get_forks) (struct mudrec *this) = get_forks_simple;

/* Возвращение вилок */

static void put_forks (struct mudrec *this);

/*

* Философы

*/

void filosof (struct mudrec this) {

char buffer [LINE_MAX];

int bytes;

if (fork ()) return;

srandom (getpid ()); /* Очень важно для процессов, иначе получим одно и то же! */

random (); random (); random (); random (); random ();

random (); random (); random (); random (); random ();

/* Пока семафор Stop не поднят */

while (!semctl (Stop, 0, GETVAL)) {

/* Пора подкрепиться */

{

int wait_time, tm;

sprintf (buffer, "%s: хочет есть\n", this.name);

bytes = write (pFdIn, buffer, strlen (buffer));

tm = time (0);

(*get_forks) (&this);

wait_time = time (0) - tm; /* Сколько времени получали вилки */

this.wait_time += wait_time;

this.max_wait_time = max (wait_time, this.max_wait_time);

sprintf (buffer, "%s: ждал вилок %d сек\n", this.name, wait_time);

bytes = write (pFdIn, buffer, strlen (buffer));

}

/* Может, обед уже закончился? */

if (semctl (Stop, 0, GETVAL)) {

put_forks (&this);

break;

}

/* Едим */

{

int eat_time = random () % 20 + 1;

sleep (eat_time);

this.eat_time += eat_time;

this.count++;

sprintf (buffer,"%s: ел %d сек\n", this.name, eat_time);

bytes = write (pFdIn, buffer, strlen (buffer));

}

/* Отдаем вилки */

put_forks (&this);

if (semctl (Stop, 0, GETVAL)) break;

/* Размышляем */

{

int think_time = random () % 10 + 1;

sleep (think_time);

this.think_time += think_time;

}

}

sprintf (buffer,"%s: уходит\n", this.name);

bytes = write (pFdIn, buffer, strlen (buffer));

msgsnd (from_fil, &this, sizeof (this), 0); /* Отослали статистику своего обеда */

_exit (0); /* ВАЖНО (_): Нам не нужны преждевременные вызовы cleanup_ipc */

}

/* Кладем вилки одну за другой */

static void put_forks (struct mudrec *this) {

struct sembuf tmp_buf;

tmp_buf.sem_flg = 0;

tmp_buf.sem_op = 1;

tmp_buf.sem_num = this->left_fork - 1;

semop (semFork, &tmp_buf, 1);

tmp_buf.sem_flg = 0;

tmp_buf.sem_op = 1;

tmp_buf.sem_num = this->right_fork - 1;

semop (semFork, &tmp_buf, 1);

}

/* Берем вилки по очереди в порядке номеров */

static void get_forks_simple (struct mudrec *this) {

struct sembuf tmp_buf;

int first = min (this->left_fork, this->right_fork);

int last = max (this->left_fork, this->right_fork);

tmp_buf.sem_flg = SEM_UNDO;

tmp_buf.sem_op = -1;

tmp_buf.sem_num = first - 1;

semop (semFork, &tmp_buf, 1);

tmp_buf.sem_flg = SEM_UNDO;

tmp_buf.sem_op = -1;

tmp_buf.sem_num = last - 1;

semop (semFork, &tmp_buf, 1);

}

/* Берем сначала нечетную вилку (если обе нечетные - то с большим номером) */

static void get_forks_parity (struct mudrec *this) {

struct sembuf tmp_buf;

int left = this->left_fork, right = this->right_fork;

int first = max ((left & 1) * 1000 + left, (right & 1) * 1000 + right) % 1000;

int last = min ((left & 1) * 1000 + left, (right & 1) * 1000 + right) % 1000;

tmp_buf.sem_flg = SEM_UNDO;

tmp_buf.sem_op = -1;

tmp_buf.sem_num = first - 1;

semop (semFork, &tmp_buf, 1);

tmp_buf.sem_flg = SEM_UNDO;

tmp_buf.sem_op = -1;

tmp_buf.sem_num = last - 1;

semop (semFork, &tmp_buf, 1);

}

/* Берем вилки по очереди, в произвольном порядке.

* Но если вторая вилка не берется сразу, то кладем первую.

* То есть философ не расходует вилочное время впустую.

*/

static void get_forks_maybe_infinit_time (struct mudrec *this) {

struct sembuf tmp_buf;

int left = this->left_fork, right = this->right_fork;

for (;;) {

tmp_buf.sem_flg = SEM_UNDO; /* Первую вилку берем с ожиданием */

tmp_buf.sem_op = -1;

tmp_buf.sem_num = left - 1;

semop (semFork, &tmp_buf, 1);

tmp_buf.sem_flg = SEM_UNDO | IPC_NOWAIT; /* Вторую - без ожидания */

tmp_buf.sem_op = -1;

tmp_buf.sem_num = right - 1;

if (0 == semop (semFork, &tmp_buf, 1)) return; /* Успех */

tmp_buf.sem_flg = 0; /* Неуспех: возвращаем первую вилку */

tmp_buf.sem_op = 1;

tmp_buf.sem_num = left - 1;

semop(semFork,&tmp_buf,1);

tmp_buf.sem_flg = SEM_UNDO; /* Отдав первую, ждем вторую */

tmp_buf.sem_op = -1;

tmp_buf.sem_num = right - 1;

semop (semFork, &tmp_buf, 1);

tmp_buf.sem_flg = SEM_UNDO | IPC_NOWAIT; /* Берем первую вилку без ожидания */

tmp_buf.sem_op = -1;

tmp_buf.sem_num = left - 1;

if (0 == semop (semFork, &tmp_buf, 1)) return; /* Успех */
tmp_buf.sem_flg = 0; /* Неуспех: отдаем вторую вилку, */

tmp_buf.sem_op = 1; /* чтобы ждать первую */

tmp_buf.sem_num = right - 1;

semop (semFork, &tmp_buf, 1);

}

}

/* Хватаем обе вилки сразу, используя групповые операции */

static void get_forks_use_groups (struct mudrec *this) {

struct sembuf tmp_buf [2];

tmp_buf[0].sem_flg = SEM_UNDO;

tmp_buf[0].sem_op = -1;

tmp_buf[0].sem_num = this->left_fork - 1;

tmp_buf[1].sem_flg = SEM_UNDO;

tmp_buf[1].sem_op = -1;

tmp_buf[1].sem_num = this->right_fork - 1;

semop (semFork, tmp_buf, 2);

}

/*

* Мелкие служебные функции.

*/

static void stop (int dummy) {

struct sembuf tmp_buf;

tmp_buf.sem_flg = 0;

tmp_buf.sem_op = 1;

tmp_buf.sem_num = 0;

semop (Stop, &tmp_buf, 1);

}

void cleanup_ipc (void) {

/*

* Уничтожение семафоров.

*/

semctl (semFork, 1, IPC_RMID);

semctl (Stop, 1, IPC_RMID);

/* То же с очередью */

msgctl (from_fil, IPC_RMID, NULL);

}

static void usage (char name []) {

fprintf (stderr,"Использование: %s [-a | -p | -I| -V] [-t число_секунд] имя_философа ...\n", name);

exit (1);

}

/*

* Точка входа демонстрационной программы.

*/

int main (int argc, char *argv[]) {

char buffer [LINE_MAX], *p;

int i, n, c;

int open_room_time = 300;

union semun tmp_arg;

int nMudr;

struct sigaction sact;

while ((c = getopt (argc, argv, "apIVt:")) != -1) {

switch (c) {

case 'a': get_forks = get_forks_simple; break;

case 'p': get_forks = get_forks_parity; break;

case 'I': get_forks = get_forks_maybe_infinit_time; break;

case 'V': get_forks = get_forks_use_groups; break;

case 't': open_room_time = strtol (optarg, &p, 0);

if (optarg [0] == 0 || *p != 0) usage (argv [0]);

break;

default: usage (argv [0]);

}

}

nMudr = argc - optind;

if (nMudr < 2) usage (argv [0]); /* Меньше двух философов неинтересно ... */

/*

* Создание канала для протокола обработки событий

*/

pipe (protokol);

/*

* Создадим семафоры для охраны вилок

*/

semFork = semget (ftok (argv [0], 2), nMudr, IPC_CREAT | 0777);

tmp_arg.val = 1;

for (i=1; i <= nMudr; i++)

semctl (semFork, i - 1, SETVAL, tmp_arg); /* Начальное значение 1 */

/* Прежде чем впускать философов, обеспечим окончание обеда */

Stop = semget (ftok (argv [0], 3), 1, IPC_CREAT | 0777);

tmp_arg.val = 0;

semctl (Stop, 0, SETVAL, tmp_arg); /* Начальное значение 0 */

/* Очередь для возврата результатов */

from_fil = msgget (ftok (argv [0], 4), IPC_CREAT | 0777);

atexit (cleanup_ipc); /* Запланировали уничтожение семафоров */

/* и других средств межпроцессного взаимодействия */

/*

* Философы входят в столовую

*/

for (i = 0; i < nMudr; i++, optind++) {

struct mudrec next;

memset (&next, 0, sizeof (next));

next.num = i + 1; /* Номер */

next.name = argv [optind]; /* Имя */

/* Указали, какими вилками пользоваться */

next.left_fork = i + 1;

next.right_fork = i + 2;

if (i == nMudr - 1)

next.right_fork = 1; /* Последний пользуется вилкой первого */

filosof (next);

}

/* Зададим реакцию на сигналы и установим будильник на конец обеда */

sact.sa_handler = stop;

(void) sigemptyset (&sact.sa_mask);

sact.sa_flags = 0;

(void) sigaction (SIGINT, &sact, (struct sigaction *) NULL);

(void) sigaction (SIGALRM, &sact, (struct sigaction *) NULL);

alarm (open_room_time);

/*

* Выдача сообщений на стандартный вывод и выход после окончания обеда.

*/

close (pFdIn); /* Сами должны закрыть, иначе из цикла не выйдем! */

for (;;) {

n = read (pFdOut, buffer, LINE_MAX);

if ((n == 0) || ((n == -1) && (errno != EINTR))) break;

for (i = 0; i < n; i++) putchar (buffer [i]);

}

close (pFdOut);

/* Распечатали сводную информацию */

{

int full_eating_time = 0;

int full_waiting_time = 0;

int full_thinking_time = 0;

for (i = 1; i <= nMudr; i++) {

struct mudrec this;

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

msgrcv (from_fil, &this, sizeof (this), i, 0); /* За счет i получаем */

/* строго по порядку */

full_eating_time += this.eat_time;

full_waiting_time += this.wait_time;

full_thinking_time += this.think_time;

if (this.count > 0) {

float count = this.count;

float think_time = this.think_time / count;

float eat_time = this.eat_time / count;

float wait_time = this.wait_time / count;

printf ("%s: ел %d раз в среднем: думал=%.1f ел=%.1f ждал=%.1f (максимум %d)\n",

this.name, this.count, think_time, eat_time, wait_time, this.max_wait_time);

}

else

printf("%s: не поел\n", this.name);

}

{

float total_time = (full_eating_time + full_waiting_time

+ full_thinking_time) / (float)nMudr;

printf (" Среднее число одновременно едящих = %.3f\n Среднее число одновременно ждущих = %.3f\n",

full_eating_time / total_time, full_waiting_time / total_time);

}

}

/* Сообщим об окончании работы */

printf ("Конец обеда\n");

return 0;

}

Листинг 8.38. Второй вариант решения задачи об обедающих философах.

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

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

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

В пример 8.39 приведена статистика поведения пяти философов для всех четырех стратегий при времени моделирования 100 секунд. Эти результаты говорят в пользу групповых операций над семафорами.

-a:

A: ел 2 раза в среднем: думал=3.5 ел=11.5 ждал=36.5 (максимум 73)

B: ел 3 раза в среднем: думал=5.7 ел=7.7 ждал=20.0 (максимум 41)

C: ел 3 раза в среднем: думал=5.7 ел=11.3 ждал=17.0 (максимум 33)

D: ел 3 раза в среднем: думал=1.7 ел=16.7 ждал=15.7 (максимум 19)

E: ел 1 раз в среднем: думал=10.0 ел=20.0 ждал=73.0 (максимум 41)

Среднее число одновременно едящих = 1.471

Среднее число одновременно ждущих = 2.980

-p:

A: ел 3 раза в среднем: думал=3.7 ел=15.3 ждал=16.0 (максимум 34)

B: ел 4 раза в среднем: думал=5.0 ел=13.8 ждал=8.2 (максимум 15)

C: ел 3 раза в среднем: думал=6.7 ел=3.7 ждал=25.7 (максимум 27)

D: ел 4 раза в среднем: думал=5.8 ел=8.5 ждал=13.8 (максимум 28)

E: ел 3 раза в среднем: думал=5.3 ел=15.3 ждал=16.7 (максимум 29)

Среднее число одновременно едящих = 1.761

Среднее число одновременно ждущих = 2.413

-I:

A: ел 5 раз в среднем: думал=4.2 ел=9.4 ждал=6.6 (максимум 15)

B: ел 3 раза в среднем: думал=6.3 ел=10.3 ждал=17.0 (максимум 31)

C: ел 4 раза в среднем: думал=6.8 ел=7.0 ждал=12.2 (максимум 45)

D: ел 3 раза в среднем: думал=4.3 ел=16.0 ждал=13.0 (максимум 16)

E: ел 4 раза в среднем: думал=5.8 ел=8.5 ждал=10.8 (максимум 22)

Среднее число одновременно едящих = 1.858

Среднее число одновременно ждущих = 2.125

-V:

A: ел 5 раз в среднем: думал=5.6 ел=5.6 ждал=8.8 (максимум 17)

B: ел 3 раза в среднем: думал=6.3 ел=10.3 ждал=16.7 (максимум 20)

C: ел 4 раза в среднем: думал=4.8 ел=11.0 ждал=9.8 (максимум 18)

D: ел 4 раза в среднем: думал=5.2 ел=12.0 ждал=8.8 (максимум 15)

E: ел 4 раза в среднем: думал=5.2 ел=10.5 ждал=10.2 (максимум 20)

Среднее число одновременно едящих = 1.892

Среднее число одновременно ждущих = 2.049

Листинг 8.39. Результаты моделирования поведения философов.
    1. 1   2   3   4   5


написать администратору сайта