Семафоры реального времени
Семафор реального времени - это эффективный механизм синхронизации процессов, представляющий собой общесистемный разделяемый ресурс, имеющий неотрицательное целочисленное значение.
Основными операциями над семафором являются захват и освобождение. Если делается попытка захвата семафора, когда его значение равно нулю, выполнение вызывающего потока управления приостанавливается и он добавляется к множеству потоков, ждущих на семафоре; в противном случае значение уменьшается.
Если при освобождении семафора множество ждущих потоков было непусто, один из них удаляется из этого множества и его выполнение возобновляется; в противном случае значение семафора просто увеличивается.
Семафоры бывают именованными и безымянными (неименованными). Первые именуются цепочками символов и создаются функцией sem_open() с флагом O_CREAT, вторые создаются функцией sem_init(). При прочих операциях семафор идентифицируется открытым дескриптором (который может быть унаследован у родительского процесса, вызвавшего fork()). Дескриптор реализуется как указатель на объект типа sem_t.
Перед выполнением операций семафор необходимо инициализировать, задав неотрицательное значение. Отрицательные значения (точнее, их абсолютная величина) могут использоваться реализацией для указания числа ждущих потоков управления.
Семафор сохраняет свое состояние после закрытия последней ссылки на него, то есть если позднее он будет вновь открыт, его значение окажется тем же, что и перед закрытием.
Детальное описание функций, обслуживающих семафоры, мы начнем, разумеется, с sem_open() и sem_init() (см. листинг 4.11), которые обеспечивают открытие, создание и инициализацию.
#include <semaphore.h>
sem_t *sem_open (const char *name, int oflag, ...);
int sem_init (sem_t *sem, int pshared, unsigned value);
Листинг 4.11. Описание функций sem_open() и sem_init(). (html, txt)
Имена семафоров (аргумент name функции sem_open()) устроены и трактуются так же, как и описанные выше имена очередей сообщений. Флагов (в аргументе oflag) может быть установлено два: O_CREAT и/или O_EXCL.
Если установлен флаг O_CREAT, то при вызове функции sem_open() необходимо задать два дополнительных аргумента: режим доступа (тип mode_t) и значение семафора (тип unsigned int).
В случае ошибки функция sem_open() возвращает значение SEM_FAILED, отличное от любого допустимого указателя на объект типа sem_t, а sem_init() "по старинке" возвращает -1.
Отметим, что нормальный результат для функции sem_init() в POSIX-2001 не стандартизован; вероятно, в будущих версиях им станет нуль. Инициализированный объект типа sem_t помещается по указателю sem. Аргумент value задает начальное значение создаваемого неименованного семафора. Если аргумент pshared отличен от нуля, семафор разделяется между процессами; в противном случае разделение возможно только между потоками управления вызывающего процесса.
Именованный семафор можно закрыть, обратившись к функции sem_close(), и удалить с помощью функции sem_unlink(); для ликвидации неименованных семафоров служит функция sem_destroy() (см. листинг 4.12). Нормальный результат этих функций равен нулю, в случае ошибки возвращается -1.
#include <semaphore.h>
int sem_close (sem_t *sem);
int sem_unlink (const char *name);
int sem_destroy (sem_t *sem);
Листинг 4.12. Описание функций закрытия и ликвидации семафоров. (html, txt)
Отметим, что эффект от вызова sem_close() для неименованного семафора, равно как и последствия вызова sem_destroy() для семафора именованного, не определены. Также не определен результат применения функции sem_destroy() к семафору, на котором имеются ждущие потоки управления.
Для захвата семафоров служат функции sem_wait(), sem_trywait() и sem_timedwait() (см. листинги 4.13 и 4.14).
#include <semaphore.h>
int sem_wait (sem_t *sem);
int sem_trywait (sem_t *sem);
Листинг 4.13. Описание функций захвата семафоров. (html, txt) #include <semaphore.h> #include <time.h> int sem_timedwait (sem_t *restrict sem, const struct timespec *restrict abstime);
Листинг 4.14. Описание функции захвата семафора с контролем времени ожидания. (html, txt)
Если значение семафора было положительным, все три перечисленные функции без каких-либо задержек завершаются успехом, уменьшая это значение до нуля и возвращая нулевой результат. В противном случае вызов sem_trywait() завершается неудачей, вызов sem_wait() блокируется до освобождения семафора, вызов sem_timedwait() также блокируется, но с контролем времени ожидания.
Освобождение семафора осуществляется функцией sem_post() (см. листинг 4.15). Для возобновления выполнения (если таковое имеет место) выбирается наиболее приоритетный поток управления, а среди потоков с равными приоритетами - тот, что ждал дольше других.
#include <semaphore.h> int sem_post (sem_t *sem);
Листинг 4.15. Описание функции sem_post(). (html, txt)
Функция sem_getvalue() (см. листинг 4.16) позволяет опросить значение семафора, не меняя его состояния.
#include <semaphore.h> int sem_getvalue (sem_t *restrict sem, int *restrict sval);
Листинг 4.16. Описание функции sem_getvalue(). (html, txt)
Значение семафора записывается по указателю sval. Если семафор был захвачен, это значение окажется нулевым или отрицательным.
Если сопоставить семафоры реального времени с теми, что были описаны в курсе [1], то можно сделать те же выводы, что и для очередей сообщений. Семафоры реального времени, согласно стандарту POSIX-2001, по сути являются бинарными. Они устроены проще и, следовательно, могут быть реализованы эффективнее. Главное - отсутствуют тяжеловесные, со сложной семантикой, трудные для реализации групповые операции.
Использование семафоров реального времени проиллюстрируем программой, реализующей взаимодействие поставщик/потребитель (см. листинг 4.17).
Листинг 4.17. Пример программы, реализующей взаимодействие поставщик/потребитель. (html, txt)
Применение неименованных семафоров в данном случае представляется вполне естественным. Поставщик захватывает семафор записи, заполняет буфер и освобождает семафор, разрешающий чтение. Потребитель действует симметричным образом.
Отметим, что семафоры ликвидируются после терминирования использующих их потоков управления, что, согласно стандарту POSIX-2001, является безопасным.
Поясним и обсудим сделанное выше замечание о том, что, согласно стандарту POSIX-2001, семафоры реального времени по сути являются бинарными. Такой вывод можно сделать по двум фразам из описания функции sem_trywait(). Во-первых, функция sem_trywait() захватывает семафор только в том случае, если он еще не захвачен, то есть если значение семафора положительно. Во-вторых, в случае успешного завершения семафор захватывается и должен оставаться в этом состоянии, пока не будет успешно выполнена функция sem_post().
Здесь ничего не говорится об уменьшении положительного значения без захвата семафора, зато намеки на это имеются в части, где приводятся детальное разъяснение положений стандарта и обоснование принятых решений. Смущает и то, что в описании функции sem_post() не запрещается освобождать свободный семафор, что, естественно, выливается в увеличение его значения. Далее, в разных местах семафоры называются то бинарными, то целочисленными. Наконец, автору не известно ни одной реализации, где семафоры реального времени не были бы целочисленными. В общем, сложное это дело - толкование внутренне противоречивых стандартов, вступающих в конфликт с реальной жизнью...
Если считать, что рассматриваемые семафоры являются целочисленными, приведенную выше программу можно усовершенствовать, сделав буфер кольцевым, с размером, большим единицы (см. листинг 4.18).
Листинг 4.18. Пример программы, реализующей взаимодействие поставщик/потребитель с помощью целочисленных семафоров. (html, txt)
Значение семафора w_sem равно числу элементов буфера, доступных для записи, r_sem - для чтения. Многопотоковым инвариантом программы является сумма этих величин, равная размеру буфера. В начальный момент буфер целиком доступен для записи. После этого вызовы sem_wait() и sem_post() уменьшают значение "своего" и увеличивают значение "чужого" семафора. Поток управления приостанавливается в sem_wait(), когда "свое" значение уменьшается до нуля, у нужно ждать, пока другой поток вызовом sem_post() не увеличит его, сделав положительным.
Разумеется, обсуждение темы семафоров было бы неполным без обеда философов. Мы приведем программу, написанную С.В. Самборским (см. листинг 4.19). В ней семафоры используются как бинарные, поэтому ее стандартность и мобильность не вызывают сомнений.
Листинг 4.19. Многопотоковый вариант решения задачи об обедающих философах с использованием семафоров реального времени. (html, txt)
/* Дадим потокам повыполняться */ sleep (10);
/* Терминируем потоки */ (void) pthread_cancel (w_ptid); (void) pthread_cancel (r_ptid);
/* Дождемся завершения потоков */ (void) pthread_join (w_ptid, NULL); (void) pthread_join (r_ptid, NULL); /* Ликвидируем семафоры */ if (sem_destroy (&w_sem) != 0) { perror ("SEM_DESTROY-W"); return (-1); } if (sem_destroy (&r_sem) != 0) { perror ("SEM_DESTROY-R"); return (-1); }
printf ("Сумма сгенерированных чисел: %d\n", sum);
return 0; }
Листинг 4.17. Пример программы, реализующей взаимодействие поставщик/потребитель.
Применение неименованных семафоров в данном случае представляется вполне естественным. Поставщик захватывает семафор записи, заполняет буфер и освобождает семафор, разрешающий чтение. Потребитель действует симметричным образом.
Отметим, что семафоры ликвидируются после терминирования использующих их потоков управления, что, согласно стандарту POSIX-2001, является безопасным.
Поясним и обсудим сделанное выше замечание о том, что, согласно стандарту POSIX-2001, семафоры реального времени по сути являются бинарными. Такой вывод можно сделать по двум фразам из описания функции sem_trywait(). Во-первых, функция sem_trywait() захватывает семафор только в том случае, если он еще не захвачен, то есть если значение семафора положительно. Во-вторых, в случае успешного завершения семафор захватывается и должен оставаться в этом состоянии, пока не будет успешно выполнена функция sem_post().
Здесь ничего не говорится об уменьшении положительного значения без захвата семафора, зато намеки на это имеются в части, где приводятся детальное разъяснение положений стандарта и обоснование принятых решений. Смущает и то, что в описании функции sem_post() не запрещается освобождать свободный семафор, что, естественно, выливается в увеличение его значения. Далее, в разных местах семафоры называются то бинарными, то целочисленными. Наконец, автору не известно ни одной реализации, где семафоры реального времени не были бы целочисленными.
В общем, сложное это дело - толкование внутренне противоречивых стандартов, вступающих в конфликт с реальной жизнью...
Если считать, что рассматриваемые семафоры являются целочисленными, приведенную выше программу можно усовершенствовать, сделав буфер кольцевым, с размером, большим единицы (см. листинг 4.18).
/* * * * * * * * * * * * * * * * * * * * * * * */ /* Программа реализует взаимодействие */ /* поставщик/потребитель (писатель/читатель). */ /* Поставщик генерирует случайные целые числа */ /* и помещает их в кольцевой буфер, */ /* потребитель извлекает их оттуда и суммирует.*/ /* Для синхронизации используются */ /* неименованные семафоры */ /* * * * * * * * * * * * * * * * * * * * * * * */
#include <unistd.h> #include <stdlib.h> #include <stdio.h> #include <semaphore.h> #include <pthread.h> #include <errno.h>
/* Буфер для хранения генерируемых данных */ static int my_buf [BUFSIZ];
/* Индекс, по которому можно записать очередной элемент */ static int w_ind = 0;
/* Индекс, по которому можно прочитать очередной элемент */ static int r_ind = 0;
/* Семафор, разрешающий записывать в буфер новые данные */ static sem_t w_sem;
/* Семафор, разрешающий читать данные из буфера */ static sem_t r_sem;
/* Общий результат суммирования */ static int sum = 0;
/* * * * * * * * * * * * * * * * * * * * * * * */ /* Стартовая функция потока, генерирующего числа*/ /* * * * * * * * * * * * * * * * * * * * * * * */ void *start_writer (void *dummy) { while (sem_wait (&w_sem) == 0) { my_buf [w_ind] = rand (); w_ind = (w_ind + 1) % BUFSIZ; if (sem_post (&r_sem) != 0) { perror ("SEM_POST-R"); return (NULL); } }
return (NULL); }
/* * * * * * * * * * * * * * * */ /* Стартовая функция потока, */ /* читающего и суммирующего числа*/ /* * * * * * * * * * * * * * * */ void *start_reader (void *dummy) { while (sem_wait (&r_sem) == 0) { sum += my_buf [r_ind]; r_ind = (r_ind + 1) % BUFSIZ; if (sem_post (&w_sem) != 0) { perror ("SEM_POST-W"); return (NULL); } }
return (NULL); }
/* * * * * * * * * * * * * * * * * * * * * * * */ /* Инициализация семафоров, */ /* создание и терминирование потоков управления*/ /* * * * * * * * * * * * * * * * * * * * * * * */ int main (void) { pthread_t w_ptid;/* Идентификатор потока-писателя */ pthread_t r_ptid;/* Идентификатор потока-читателя */
/* Инициализируем семафоры. */ /* Семафор записи будет свободен,*/ /* разрешая заполнить весь буфер,*/ /* семафор чтения - захвачен */ if (sem_init (&w_sem, 0, BUFSIZ) == -1) { perror ("SEM_INIT-W"); return (-1); } if (sem_init (&r_sem, 0, 0) == -1) { perror ("SEM_INIT-R"); return (-1); }
/* Создадим потоки управления - писателя и читателя */ if ((errno = pthread_create (&w_ptid, NULL, start_writer, NULL)) != 0) { perror ("PTHREAD_CREATE-W"); return (errno); } if ((errno = pthread_create (&r_ptid, NULL, start_reader, NULL)) != 0) { perror ("PTHREAD_CREATE-R"); return (errno); }
/* Дадим потокам повыполняться */ sleep (10);
/* Терминируем потоки */ (void) pthread_cancel (w_ptid); (void) pthread_cancel (r_ptid);
/* Дождемся завершения потоков */ (void) pthread_join (w_ptid, NULL); (void) pthread_join (r_ptid, NULL);
/* Ликвидируем семафоры */ if (sem_destroy (&w_sem) != 0) { perror ("SEM_DESTROY-W"); return (-1); }
if (sem_destroy (&r_sem) != 0) { perror ("SEM_DESTROY-R"); return (-1); }
printf ("Сумма сгенерированных чисел: %d\n", sum);
return 0; }
Листинг 4.18. Пример программы, реализующей взаимодействие поставщик/потребитель с помощью целочисленных семафоров.
Значение семафора w_sem равно числу элементов буфера, доступных для записи, r_sem - для чтения. Многопотоковым инвариантом программы является сумма этих величин, равная размеру буфера. В начальный момент буфер целиком доступен для записи. После этого вызовы sem_wait() и sem_post() уменьшают значение "своего" и увеличивают значение "чужого" семафора. Поток управления приостанавливается в sem_wait(), когда "свое" значение уменьшается до нуля, у нужно ждать, пока другой поток вызовом sem_post() не увеличит его, сделав положительным.
Разумеется, обсуждение темы семафоров было бы неполным без обеда философов. Мы приведем программу, написанную С.В. Самборским (см. листинг 4.19). В ней семафоры используются как бинарные, поэтому ее стандартность и мобильность не вызывают сомнений.
/* Обедающие философы. Многопотоковая реализация с помощью семафоров. Запуск: mudrecSem [-a | -p | -I] [-t число_секунд] имя_философа ...
Опции: -t число_секунд - сколько секунд моделируется
Стратегии захвата вилок: -a - сначала захватывается вилка с меньшим номером; -p - сначала захватывается нечетная вилка; -I - некорректная (но эффективная) интеллигентная стратегия: во время ожидания уже захваченная вилка кладется.
Пример запуска: mudrecSem -p -t 300 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: mudrecSem.c,v 1.2 2004/03/18 10:28:38 sambor Exp $";
#include <unistd.h> #include <stdlib.h> #include <stdio.h> #include <pthread.h> #include <semaphore.h> #include <signal.h> #include <string.h> #include <fcntl.h> #include <limits.h> #include <errno.h>
#define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)>(b)?(b):(a))
struct mudrec { char *name; int left_fork, right_fork; int eat_time, wait_time, think_time, max_wait_time; int count; pthread_t thread; int private_pFdIn; } *kafedra;
/* Глобальные счетчики и логические переменные */ int Stop = 0; /* Признак конца обеда */
/* Различные дескрипторы */ int protokol [2] = {-1, -1}; #define pFdIn (protokol [1]) #define pFdOut (protokol [0])
/* Массив семафоров для синхронизации доступа к вилкам */ sem_t *semFork;
/* Разные алгоритмы захвата вилок */ static void get_forks_simple (struct mudrec *this); static void get_forks_odd (struct mudrec *this); static void get_forks_maybe_infinit_time (struct mudrec *this);
/* Используемый метод захвата вилок */ void (*get_forks) (struct mudrec *this) = get_forks_simple;
/* Возвращение вилок */ static void put_forks (struct mudrec *this);
/* * Потоки-философы */ void *filosof (void *arg) { struct mudrec *this = arg; char buffer [LINE_MAX]; int bytes; int private_pFdIn = this->private_pFdIn;
while (!Stop) { /* Пора подкрепиться */ { int wait_time, tm = time (NULL);
sprintf (buffer, "%s: хочет есть\n", this->name); bytes = write (private_pFdIn, buffer, strlen (buffer));
(*get_forks) (this);
wait_time = time (NULL) - 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 (private_pFdIn, buffer, strlen (buffer)); }
/* Может, обед уже закончился? */ if (Stop) { put_forks (this); break; }
/* Ест */ { int eat_time = rand () % 20 + 1;
sleep (eat_time);
this->eat_time += eat_time; this->count++; sprintf (buffer,"%s: ел %d сек\n", this->name, eat_time); bytes = write (private_pFdIn, buffer, strlen (buffer)); }
/* Отдает вилки */ put_forks (this);
if (Stop) break;
/* Размышляет */ { int think_time = rand () % 10 + 1;
sleep (think_time); this->think_time += think_time; } } /* while (!Stop) */
sprintf (buffer,"%s: уходит\n", this->name); bytes = write (private_pFdIn, buffer, strlen (buffer));
close (private_pFdIn);
return (NULL); } /* Поток-философ */
/* Кладет вилки одну за другой */ static void put_forks (struct mudrec *this) { sem_post (&semFork [this->left_fork - 1]); sem_post (&semFork [this->right_fork - 1]); }
/* Берет вилки по очереди в порядке номеров */ static void get_forks_simple (struct mudrec *this) { int first = min (this->left_fork, this->right_fork); int last = max (this->left_fork, this->right_fork);
sem_wait (&semFork [first - 1]); sem_wait (&semFork [last - 1]); }
/* Берем сначала нечетную вилку */ /* (если обе нечетные - то с большим номером) */ static void get_forks_odd (struct mudrec *this) { int left = this->left_fork, right = this->right_fork;
int first; int last;
if ((left & 1) > (right & 1)) { first = left; last = right; } else if ((left & 1) < (right & 1)) { first = right; last = left; } else { first = max (left, right); last = min (left, right); }
sem_wait (&semFork [first - 1]); sem_wait (&semFork [last - 1]); }
/* Берем вилки по очереди, в произвольном порядке. * Но если вторая вилка не берется сразу, то кладем первую. * То есть философ не расходует вилочное время впустую. */ static void get_forks_maybe_infinit_time (struct mudrec *this) { int left = this->left_fork, right = this->right_fork;
for (;;) { sem_wait (&semFork [left - 1]); if (0 == sem_trywait (&semFork [right - 1])) return; sem_post (&semFork [left - 1]); sem_wait (&semFork [right - 1]); if (0 == sem_trywait (&semFork [left - 1])) return; sem_post (&semFork [right - 1]); } }
/* Мелкие служебные функции */ static void stop (int dummy) { Stop = 1; }
static void usage (char name []) { fprintf (stderr, "Использование: %s [-a | -p | -I] [-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; int nMudr; struct sigaction sact;
while ((c = getopt (argc, argv, "apIt:")) != -1) { switch (c) { case 'a': get_forks = get_forks_simple; break; case 'p': get_forks = get_forks_odd; break; case 'I': get_forks = get_forks_maybe_infinit_time; 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);
kafedra = calloc (sizeof (struct mudrec), nMudr);
/* Зачисление на кафедру */ for (i = 0; i < nMudr; i++, optind++) { kafedra [i].name = argv [optind]; /* Выдадим телефон */ kafedra [i].private_pFdIn = fcntl (pFdIn, F_DUPFD, 0); /* Укажем новичку, какими вилками пользоваться */ kafedra [i].left_fork = i + 1; kafedra [i].right_fork = i + 2; } kafedra [nMudr - 1].right_fork = 1; /* Последний*/ /* пользуется вилкой первого */
/* Зададим реакцию на сигналы и установим будильник */ /* на конец обеда */ 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);
/* Создадим семафоры для охраны вилок */ semFork = calloc (sizeof (sem_t), nMudr); for (i = 0; i < nMudr; i++) { sem_init (&semFork [i], 0, 1 /* На каждое место */ /* по одной вилке */); }
/* Философы входят в столовую */ for (i = 0; i < nMudr; i++) pthread_create (&kafedra [i].thread, NULL, &filosof, (void *) &kafedra [i]);
/* Выдача сообщений на стандартный вывод и выход */ /* после окончания всех задач */ close (pFdIn); while (1) { n = read (pFdOut, buffer, LINE_MAX); if (n == 0 || (n < 0 && errno != EINTR)) break; for (i = 0; i < n; i++) putchar (buffer [i]); } close (pFdOut);
/* Уничтожение семафоров */ for (i = 0; i < nMudr; i++) { sem_destroy (&semFork [i]); }
/* Выдача сводной информации */ { int full_eating_time = 0; int full_waiting_time = 0; int full_thinking_time = 0; for (i = 1; i <= nMudr; i++) { struct mudrec *this = &kafedra [i - 1];
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); } /* for */
{ float total_time = (full_eating_time + full_waiting_time + full_thinking_time) / (float) nMudr;
printf("Среднее число одновременно едящих = %.3f\n", full_eating_time / total_time); printf("Среднее число одновременно ждущих = %.3f\n", full_waiting_time / total_time); } } /* Выдача сводной информации */
free (semFork); free (kafedra);
/* Сообщим об окончании работы. */ printf ("Конец обеда\n");
return 0; }
Листинг 4.19. Многопотоковый вариант решения задачи об обедающих философах с использованием семафоров реального времени.
