Операционные системы. Управление ресурсами
       

Семафоры



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 }

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

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

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

Выполнение операций над семафором может обеспечиваться системным вызовом вида: flag = semaphoreOp(semaphorId, opCode, waitOption); где semaphorId - манипулятор семафора, opCode - код операции, waitOption - опция ожидания, flag - возвращаемое значение, признак успешного выполнения операции или код ошибки.

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

Во многих современных ОС наряду с семафорами "в чистом виде" API представляет те же семафоры и в виде "прикладных" объектов - объектов взаимного исключения и событий. Хотя содержание этих объектов одно и то же - семафор, ОС в отношении этих объектов представляет для прикладных процессов специфическую семантику API, соответствующую задачам взаимного исключения и синхронизации.

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

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



Содержание раздела