Семафоры

8.5. Семафоры

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

Такая возможность обеспечивается:

введением специальных целочисленных общих переменных, которые называются семафорами;
добавлением к набору элементарных действий, из которых строятся процессы, операций над семафорами: V-операции и P-операции.

V-операция есть операция с одним операндом, который должен быть семафором. Выполнение операции состоит в увеличении значения аргумента на 1, это действие должно быть атомарным.

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

Атомарность P-операции и является потенциальной задержкой: если процесс пытается выполнить P-операцию над семафором, значение которого в данный момент нулевое, данная P-операция не может завершиться пока другой процесс не выполнит V-операцию над этим семафором. Несколько процессов могут начать одновременно P-операцию над одним и тем же семафором. Тогда при установке семафора в 1 только одна из P-операций завершится, какая именно - мы обсудим позже.

Защита разделяемых ресурсов теперь выглядит следующим образом. Каждый ресурс защищается своим семафором, значение которого может быть 1 - свободен или 0 - занят. Процесс, выполняющий доступ к ресурсу, инициирует P-операцию (эквивалент csBegin). Если ресурс занят - процесс задерживается в своей P-операции до освобождения ресурса. Когда ресурс освобождается, P-операция процесса завершается, и процесс занимает ресурс. При освобождении ресурса процесс выполняет V-операцию (эквивалент csEnd).

Э.Дейкстра [7], вводя семафорные примитивы для синхронизации и взаимного исключения, исходил из гипотезы о том, что P- и V-операции реализованы в нашей вычислительной системе аппаратно. На самом же деле, в составе любого набора команд таких операций нет - и это оправданно. Программная реализация семафоров позволяет нам включить в них блокировку и диспетчеризацию процессов, чего нельзя было бы делать на аппаратном уровне.

В соответствии с общей методикой нашего подхода, сосредотачивающей внимание на механизмах реализации взаимного исключения, рассмотрим реализацию семафоров и операций над ними. Сам семафор может быть представлен следующим образом: 1 typedef struct { 2 int value; 3 char mutEx; 4 process *waitList; 5 } semaphore;

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

Мы начинаем рассмотрение с, так называемых, двоичных семафоров, для которых допустимые значения - 0 и 1. Если семафор защищает критическую секцию, то начальное значение поля value = 1. Начальные значения других полей: mutEx = 0; waitList = NULL.

Операции над семафорами можно представить в виде следующих функций: 1 void P ( semaphore *s ) { 2 csBegin (&s->mutEx); 3 if (!s->value) block(s); 4 else { 5 s->value--; 6 csEnd (&s->mutEx); 7 } 8 } 9 void V ( semaphore *s ) { 10 csBegin (&s->mutEx); 11 if(s->waitList!= NULL) unBlock(s); 12 else s->value++; 13 csEnd (&s->mutEx); 14 }

В нашей реализации вы видите "скобки критической секции" как элементарные операции. Они обеспечивают атомарность выполнения семафоров и могут быть реализованы любым из описанных выше корректных способов. Здесь мы ориентируемся на команду testAndSet с использованием поля семафора mutEx в качестве замка, но это может быть и любая другая корректная реализация (в многопроцессорных версиях Unix, например, используется алгоритм Деккера). Вопрос: в чем же мы выигрываем, если в csBegin все равно используется занятое ожидание? Дело в том, что это занятое ожидание не может быть долгим. Этими "скобками критической секции" защищается не сам ресурс, а только связанный с ним семафор. Выполнение же семафорных операций происходит быстро, следовательно, и потери на занятое ожидание будут минимальными.

Если при выполнении P-операции оказывается, что значение семафора нулевое, выдается системный вызов block, который блокирует активный процесс - переводит его в список ожидающих, в тот самый список, который связан с данным семафором. Важно, что процесс прервется именно в контексте строки 3 своей P-операции и впоследствии он возобновится в том же контексте. Поскольку заблокированный таким образом процесс не успеет закончить критическую секцию, это должен сделать за него системный вызов block, чтобы другие процессы получили доступ к семафору.

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

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

Итак, общие свойства решения задачи взаимного исключения с помощью семафоров таковы:

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

Для решения задачи взаимного исключения достаточно двоичных семафоров. Мы, однако, описали тип поля value как целое число. В приведенном нами выше определении Дейкстры речь тоже идет о целочисленном, а не о двоичном значении. Семафор, который может принимать неотрицательные значения, большие 1, называется общим семафором. Такой семафор может быть очень удобен, например, при управлении не единичным ресурсом, а классом ресурсов. Начальное значение поля value для такого семафора устанавливается равным числу единиц ресурса в классе. Каждое выделение единицы ресурса процессу сопровождается P-операцией, уменьшающей значение семафора. Семафор, таким образом, играет роль счетчика свободных единиц ресурса. Когда этот счетчик достигнет нулевого значения, процесс, выдавший следующий запрос на ресурс, будет заблокирован в своей P-операции. Освобождение ресурса сопровождается V-операцией, которая разблокирует процесс, ожидающий ресурс, или наращивает счетчик ресурсов.

Общие семафоры могут быть использованы и для простого решения задачи синхронизации. В этом случае семафор связывается с каким-либо событием и имеет начальное значение 0. (Событие может рассматриваться как ресурс, и до наступления события этот ресурс недоступен). Процесс, ожидающий события, выполняет P-операцию и блокируется до установки семафора в 1. Процесс, сигнализирующий о событии, выполняет над семафором V-операцию. Для графа синхронизации, например, показанного на Рисунок 8.1, мы свяжем с каждым действием графа одноименный семафор. Тогда каждое действие (например, E) должно быть оформлено следующим образом: 1 procE () { 2 /*ожидание событий B и D*/ 3 P(B); P(D); 4 . . . 5 /* сигнализация о событии E для двух 6 ожидающих его действий (F и H) */ 7 V(E); V(E); 8 }

Ниже мы рассмотрим применение семафоров для более сложного варианта задачи синхронизации.

Содержание Назад Вперед