Разработчики первых программных систем, использующих взаимодействие параллельных процессов, не сразу осознали сложность проблемы взаимного исключения. Были испробованы различные программные решения, прежде чем удалось найти такое, которое удовлетворяло трем естественным условиям:
· в любой момент времени не более, чем один процесс может находиться в критической секции;
· если критическая секция свободна, то процесс может беспрепятственно войти в нее;
· все процессы равноправны.
Попробуйте сами найти такое решение. В книгах /3/ и /4/ можно найти несколько вариантов решения с анализом их ошибок.
В конце концов правильные алгоритмы решена задачи взаимного исключения предложили сначала Деккер (его алгоритм довольно запутанный, что часто случается с первыми решениями сложных задач), затем Питерсон, чей алгоритм проще и понятнее.
Для любознательных приводим решение Питерсона. В нем используются булевы переменные flagA, flagB, изначально равные false, и переменная перечисляемого типа turn: A..B.
| Процесс A: | Процесс B: |
| . . .flagA := true;turn := B;while flagB and turn = B do;(критическая секция A)flagA := false;. . . | . . .flagB := true;turn := A;while flagA and turn = A do;(критическая секция B)flagB := false;. . . |
Приведенный алгоритм действительно решает проблему, однако у него есть два существенных недостатка. Во-первых, если в конкуренции за критическую секцию участвуют не два процесса, а три или более, то программа становится очень громоздкой. Во-вторых, решение Питерсона основано на использовании активного ожидания.
Еще одним направлением в реализации взаимного исключения стало включение специальных машинных команд в наборы команд новых процессоров. Поскольку опасность, как мы видели, связана с разделением по времени операций проверки и присваивания, то были предложены команды, выполняющие одновременно проверку и присваивание. Такие команды есть, например, у процессоров Pentium. С их помощью действительно можно проще реализовать взаимное исключение, но для этого все равно требуется активное ожидание.
4.3.3. Двоичные семафоры Дейкстры
Совершенно иным образом подошел к проблеме взаимного исключения великий голландский ученый Э.Дейкстра (E.Dijkstra, 1966). Он предложил использовать новый вид программных объектов – семафоры. Здесь мы рассмотрим их простейший вариант – двоичные семафоры, они же мьютексы (mutex, от слов MUTualEXclusion – взаимное исключение).
Двоичным семафором называется переменная S, которая может принимать значения 0 и 1 и для которой определены только две операции.
· P(S) – операция занятия (закрытия) семафора. Она ожидает, пока значение S не станет равным 1, и, как только это случится, присваивает S значение 0 и завершает свое выполнение. Очень важно: операция Pпо определению неделима, т.е. между проверкой и присваиванием не может вклиниться другой процесс, который бы изменил значение S.
· V(S) – операция освобождения (открытия) семафора. Она просто присваивает S значение 0.
Чем переменная-семафор отличается от обычной булевой переменной? Тем, что для нее недопустимы никакие иные операции, кроме P и V. Нельзя написать в программе S:=1 или if(S)then ... , если S определена как семафор.
Чем операция P отличается от варианта с проверкой и присваиванием, который мы выше признали неудовлетворительным? Неделимостью. Но это «по определению», а как на практике добиться этой неделимости? Это отдельный, вполне решаемый вопрос.
Заслуга Дейкстры как раз в том, что он разделил проблему взаимного исключения на две независимые проблемы разных уровней:
· на уровне реализации: как обеспечить работу семафоров в соответствии с их определением;
· на уровне взаимодействия процессов: как написать корректно работающую программу, если в распоряжении программиста имеются семафоры.
Решать эти две задачи по отдельности легче, чем обе вместе, при этом решать их обычно должны разные люди: первую – разработчики ОС, а вторую – разработчики прикладной программы.
Рассмотрим сначала реализацию. Очевидно, функции P и V удобнее и надежнее один раз реализовать в ОС, чем каждый раз по-новому – в прикладных программах. (Названия этих функций могут в конкретных системах быть и иными, более выразительными.)
Системная функция P(S) должна проверить, свободен ли семафор S. Если свободен (S = 1), то система занимает его (S := 0) и на этом функция завершается. Если же семафор занят, то система блокирует процесс, вызвавший функцию P, и запоминает, что этот процесс блокирован по ожиданию освобождения семафора S. Таким образом, при реализации семафоров удается избежать активного ожидания.
Неделимость операции обеспечивается тем, что во время выполнения системой функции P переключение процессов запрещено. В крайнем случае, ОС имеет возможность для этого на короткое время запретить прерывания.
Системная функция V(S) – это, конечно, не просто присваивание S := 1. Кроме этого, система должна проверить, нет ли среди спящих процессов такого, который ожидает освобождения семафора S. Если такой процесс найдется, система разблокирует его, а переменная S в этом случае сохраняет значение 0 (семафор снова занят, теперь уже другим процессом).
Может ли случиться так, что несколько спящих процессов ждут освобождения одного и того же семафора? Да, так вполне может быть. Какой из этих процессов должен быть разбужен системой? С точки зрения корректности работы и соответствия определениям функций P и V – любой, но только один. С точки зрения эффективности работы – вероятно, надо разбудить самый приоритетный процесс, а в случае равенства приоритетов… ну, видимо, тот, который спит дольше.
Теперь, когда мы разобрались с реализацией семафоров, можно о ней забыть[9] и помнить только, что семафоры существуют и могут быть использованы при необходимости.
Рассмотрим теперь вторую половину задачи – использование семафоров для управления взаимодействием процессов. Как можно реализовать корректную работу процессов с критическими секциями, если использовать двоичный семафор? Да очень просто.
| Процесс A: | Процесс B: |
| . . .P(S);(критическая секция A)V(S);. . . | . . .P(S);(критическая секция B)V(S);. . . |
И все. Сложности ушли в реализацию семафоров. Надо только проследить, чтобы до начала работы процессов семафор S был открыт.
4.3.4. Средства взаимодействия процессов
Можно доказать, что использование двоичных семафоров позволяет корректно решить любые проблемы синхронизации процессов. Но вовсе не обязательно это решение окажется простым и удобным. В некоторых случаях использование семафоров должно все же сопровождаться нежелательным активным ожиданием.
За десятилетия, прошедшие после изобретения семафоров, были предложены различные средства синхронизации, более приспособленные для различных типовых задач. Рассмотрим некоторые из них.
В упомянутой работе Дейкстры, помимо двоичных семафоров, принимающих значения 0 и 1, был рассмотрен также более общий тип семафоров со значениями на интервале от 0 до некоторого N. Функция P(S) уменьшает положительное значение семафора на 1, а при нулевом значении переходит в ожидание, как и в случае двоичного семафора. Функция V(S) увеличивает значение семафора на 1, но не более N.
Область применения целочисленных семафоров несколько иная, чем у двоичных. Целочисленные семафоры применяются в задачах выделения ресурсов из ограниченного запаса. Величина N характеризует общее количество имеющихся единиц ресурса, а текущее значение переменной – количество свободных единиц. При запросе ресурса процесс вызывает функцию V(S), при освобождении – P(S).
Для целочисленных семафоров иногда удобно использовать модифицированную функцию V(S, k), вторым параметром которой является число одновременно запрашиваемых единиц ресурса. Такая функция блокирует процесс, если значение семафора меньше k.
Возможна ситуация, когда процесс может выбрать один из нескольких путей дальнейшей работы, но на каждом пути он может быть заблокирован закрытым семафором. Разумно было бы ждать освобождения любого из семафоров и только тогда выбрать свободный путь. Но как это сделать? Вызвав P(S) для одного из семафоров, процесс обречен ждать освобождения именно этого семафора, а не любого из имеющихся.
Житейская ситуация: покупатель в супермаркете, выбирающий, к какой из касс занять очередь. Хорошо бы угадать очередь, которая пройдет быстрее…
Функция множественного ожиданияP(S1, S2, … Sn) позволяет указать в качестве параметров несколько двоичных семафоров (или массив семафоров). Если хотя бы один из семафоров свободен, функция занимает его, в противном случае она ждет освобождения любого из семафоров.
Другой, не менее полезный вариант множественного ожидания, это ожидание момента, когда все указанные семафоры окажутся свободны. Это означает, что процесс может работать дальше только в том случае, если одновременно выполнены несколько условий, каждое из которых задано в виде двоичного семафора.
Сигнал – это нечто, что может быть послано процессу системой или другим процессом. С сигналом не связано никакой информации, кроме номера (кода), указывающего, какой именно тип сигнала посылается. При получении сигнала процесс прерывает свою текущую работу и переходит на выполнение функции, определенной как обработчик сигналов данного типа.
Таким образом, сигналы сильно похожи на прерывания, но только высокоуровневые, управляемые системой, а не аппаратурой.