Средства взаимодействия процессов
Можно доказать, что использование двоичных семафоров позволяет корректно решить любые проблемы синхронизации процессов. Но вовсе не обязательно это решение окажется простым и удобным. В некоторых случаях использование семафоров должно все же сопровождаться нежелательным активным ожиданием.
За десятилетия, прошедшие после изобретения семафоров, были предложены различные средства синхронизации, более приспособленные для различных типовых задач. Рассмотрим некоторые из них.
Целочисленные семафоры
В упомянутой работе Дейкстры, помимо двоичных семафоров, принимающих значения 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) позволяет указать в качестве параметров несколько двоичных семафоров (или массив семафоров). Если хотя бы один из семафоров свободен, функция занимает его, в противном случае она ждет освобождения любого из семафоров.
Другой, не менее полезный вариант множественного ожидания, это ожидание момента, когда всеуказанные семафоры окажутся свободны. Это означает, что процесс может работать дальше только в том случае, если одновременно выполнены несколько условий, каждое из которых задано в виде двоичного семафора.
Сигналы
Сигнал — это нечто, что может быть послано процессу системой или другим процессом. С сигналом не связано никакой информации, кроме номера (кода), указывающего, какой именно тип сигнала посылается. При получении сигнала процесс прерывает свою текущую работу и переходит на выполнение функции, определенной как обработчик сигналов данного типа.
Таким образом, сигналы сильно похожи на прерывания, но только высокоуровневые, управляемые системой, а не аппаратурой.
Механизм сигналов позволяет решить, например, проблему критической секции иным способом, чем семафоры.
Подумайте самостоятельно, как это можно сделать.
Сообщения
Сообщения также посылаются процессу системой или другим процессом, однако отличаются от сигналов в двух отношениях.
Во-первых, сообщения не прерывают работу процесса-получателя. Вместо этого они становятся в очередь сообщений. Процесс должен сам вызвать функцию приема сообщения. Если очередь пуста, эта функция блокирует процесс до получения какого-нибудь сообщения.
Во-вторых, с сообщением, в отличие от сигнала, может быть связана информация, передаваемая получателю. Таким образом, сообщения — это средство не только синхронизации, но и обмена данными между процессами.
Общая память
Поговорим теперь еще об обмене данными. Самым простым и естественным способом такого обмена представляется возможность совместного доступа двух или более процессов к общей области памяти. Но поскольку обычно ОС стремится, наоборот, надежно разделить память разных процессов, то для выделения обшей памяти нужны специальные системные средства.
Общая память служит только средством обмена данными, но никак не решает проблем синхронизации. Участки программы, где происходит работа с общей памятью, часто следует рассматривать как критические секции и защищать семафорами.
Программные каналы
Другое часто используемое средство обмена данными — программный канал (pipe; иногда переводится как «трубопровод»). В этом случае для выполнения обмена используются не команды чтения/записи в память, а функции чтения/записи в файл. Программный канал «притворяется файлом», для работы с ним используются те же операции, что для последовательного доступа к файлу: открытие, чтение, запись, закрытие. Однако источником читаемых данных служит не файл на диске, а процесс, выполняющий запись «в другой конец трубы». Данные, записанные одним процессом, но пока не прочитанные другим, хранятся в системном буфере. Если же процесс пытается прочесть данные, которые пока не записаны другим процессом, то процесс-читатель блокируется до получения данных.
Проблема тупиков.
Проблема тупиков
Согласно определению, тупик — это состояние, в котором «некоторые процессы заблокированы в результате таких запросов на ресурсы, которые никогда не могут быть удовлетворены, если не будут предприняты чрезвычайные системные меры».
Как это прикажете понимать?
Прежде всего, давайте отметим, что процессу, действующему в одиночку, не под силам загнать приличную ОС в тупик. Требования процесса не будут удовлетворены, только если они превышают то, что есть у системы. Скажем, процесс требует 500 Мб оперативной памяти, когда у системы есть всего-то 256 Мб. Ну, так в этом случае процесс будет не блокирован, а беспощадно убит системой.
Иное дело, если в деле замешаны два или более процессов. Согласно другому определению, данному в /2/, «Группа процессов находится в тупиковой ситуации, если каждый процесс из группы ожидает события, которое может вызвать только другой процесс из той же группы».
Рассмотрим такой пример. Пусть каждый из процессов A и B собирается работать с двумя файлами, F1 и F2, причем не намерен разделять эти файлы с другим процессом. Программы же процессов слегка различаются, а именно:
| Процесс A: | Процесс B: |
| . . . Открыть(F1); Открыть(F2); (работа процесса A с файлами); Закрыть(F1); Закрыть(F2); . . . | . . . Открыть(F2); Открыть(F1); (работа процесса B с файлами); Закрыть(F1); Закрыть(F2); . . . |
В этой ситуации все может пройти благополучно. Пусть, например, процесс A успеет открыть оба файла к тому моменту, когда процесс B попытается открыть F2. Эта попытка не увенчается успехом: процесс B либо будет заблокирован до освобождения файлов, либо получит сообщение об ошибке при открытии файла и, если процесс умный, через какое-то время попытается еще раз. В конце концов оба процесса получат требуемые ресурсы (в данном случае открытые файлы), хотя и не оба сразу.
Совсем иное будет дело, если A успеет открыть только F1, после чего B откроет F2. Тут-то и получится тупик. Процесс A хочет открыть файл F2, но не сможет этого сделать раньше, чем B закроет этот файл. Но B не закроет F2 до того, как сумеет открыть файл F1, который занят процессом A. Каждый из процессов захватил один из ресурсов и не собирается его отдавать раньше, чем получит другой. Ситуация «двух баранов на мосту».
Подчеркнем: тупик — это не просто блокировка процесса, когда необходимый ему ресурс занят. Занят — ну и что, со временем, авось, освободится. Тупик — это взаимная блокировка, из которой нет выхода.
Еще пример. Пусть в системе имеется 100 Мб памяти, доступной для процессов. Процесс A при своем старте занимает 40 Мб, но позднее на короткое время требует еще 30 Мб, после чего завершается, освобождая всю память. Процесс B ведет себя точно таким же образом.
Каждый из процессов по отдельности не требует у системы ничего невозможного. В то же время понятно: если оба процесса сумеют стартовать и начать параллельную работу, то ни один из них никогда не получит дополнительные 30 Мб. Тупик.
Совсем грубый пример. Процесс A на каком-то этапе работы ждет сообщения от процесса B, после чего собирается послать ответное сообщение. В то же время процесс B ждет сообщения от A, чтобы потом ответить на него. Тупик неизбежен. В данном случае, в отличие от предыдущих, возникновение тупика связано с явной ошибкой в логике программы.
Может ли помочь в борьбе с тупиками использование семафоров и других подобных средств? Вряд ли, разве что в редких случаях. Семафор — это, скорее, дополнительный тормоз для процесса. Вещь полезная, но не способствующая продвижению.
Все известные способы борьбы с тупиками можно разделить на три группы:
исключение возможности тупиков путем анализа исходного текста программ;
предотвращение возникновения тупиков при работе ОС;
ликвидация возникших тупиков.
Что касается анализа текста — это, безусловно, нужная вещь, хотя и непростая. Определить по тексту программ процессов, могут ли они зайти в тупик — сложная задача. К тому же, если и могут, то совсем не обязательно зайдут, все может зависеть от конкретных исходных данных и от временных соотношений. Но главное — для анализа исходного текста программ нужно иметь в своем распоряжении этот текст. Реально ли это? Только в некоторых ситуациях. Например, при разработке встроенной системы исходные тексты всех прикладных программ обычно доступны разработчику ОС. Конечно, в этом случае анализ на возможность тупиков просто необходим. Другой пример — разработка сложного многопроцессного приложения, когда разработчик должен хотя бы выявить возможность взаимной блокировки между «своими» процессами.
Если тексты недоступны, то можно попытаться предотвращать тупики уже в ходе работы программ, отслеживая их запросы на ресурсы и блокируя либо прекращая те процессы, которые, по-видимому, «лезут в тупик».
Самый грубый из подобных подходов заключается в том, что каждый процесс должен захватывать все необходимые ему ресурсы сразу, при старте, после чего он может либо удерживать ресурсы в течение всего времени работы, либо освобождать ресурсы, которые больше не нужны. Такой подход, безусловно, в корне исключает возможность тупиков. К сожалению, на практике он почти исключает и многозадачную работу: многие ресурсы необходимы для работы большинства процессов (например, диски, принтер, системные файлы), поэтому пока один процесс удерживает все ресурсы, другие не смогут даже стартовать.
Чуть получше алгоритм нумерованных ресурсов. Он заключается в том, что все ресурсы, имеющиеся в системе, нумеруются целыми числами в произвольном порядке (хотя, вероятно, для повышения эффективности лучше всего пронумеровать их в порядке возрастания дефицитности ресурса). Далее применяется простое правило: запрос процесса на выделение ему ресурса с номеромK удовлетворяется только в том случае, если процесс в данный момент не владеет никаким другим ресурсом с номером N K. Другими словами, запрос ресурсов следует выполнять только в порядке возрастания номеров. Нетрудно показать, что это правило является достаточным условием отсутствия тупиков. Но это условие слишком ограничивающее, оно отсекает много ситуаций, когда тупик на самом деле не возник бы.
Наиболее изящен алгоритм банкира, предложенный тем же Дейкстрой. В нем предполагается, что каждый процесс при старте должен объявить системе, на какие ресурсы и в каком максимальном количестве он может в будущем претендовать. Далее, вводится понятие безопасного (в отношении тупиков) состояния системы. Текущее состояние, в котором имеется набор процессов, каждый из которых владеет некоторыми ресурсами, считается безопасным, если имеющихся в наличии свободных ресурсов достаточно для того, чтобы ОС смогла в определенной последовательности удовлетворить максимальные запросы каждого процесса.
Это определение проще понять, если рассмотреть, как проверяется безопасность заданного состояния. Согласно алгоритму, среди имеющихся процессов ищется такой, чьи максимальные заявленные запросы система может удовлетворить, используя имеющиеся свободные ресурсы. Если хотя бы один такой процесс найден, то он вычеркивается из общего списка и все ресурсы, которые он уже успел занять, считаются свободными (т.е. считается, что система смогла завершить этот процесс). Далее, при увеличившихся свободных ресурсах, ищется следующий процесс, чьи запросы система может удовлетворить, и т.д. Если в результате удается вычеркнуть все процессы, то анализируемое состояние системы является безопасным.
Сам же алгоритм банкира можно теперь сформулировать очень просто: любой запрос процесса на выделение ему дополнительных ресурсов должен удовлетворяться только в том случае, если состояние, в которое перейдет система после этого выделения, будет безопасным.
Название алгоритма навеяно, видимо, образом осторожного банкира, который выдает кредит только в том случае, если после этого сможет выполнить все свои обязательства даже в худшем случае. Явно не российский банкир.
Хотя данный алгоритм красив и логичен, у него есть, по меньшей мере, два недостатка. Во-первых, в современных ОС не принято требовать от процессов, чтобы те заранее объявляли свои будущие потребности в ресурсах. Во-вторых, выполнять проверку безопасности состояния при каждом запросе любого из процессов — слишком трудоемкое удовольствие.
Рассмотрим, наконец, третий подход — ликвидацию уже возникших тупиков, без попыток предотвратить их возникновение. В книге /2/ этот подход назван «алгоритмом страуса».
Здесь, прежде всего, возникает вопрос: как убедиться, что система действительно в тупике? Внешним признаком этого является длительное отсутствие какой-либо активности двух или более процессов. Но это недостоверный признак, процессы могли просто надолго задуматься над каким-нибудь трудоемким вычислением. Есть алгоритмы, которые анализируют текущее состояние процессов и ресурсов, наличие заблокированных запросов, и на этой основе ставят диагноз тупика. В принципе, такой алгоритм мог бы быть встроен в ОС. Однако в литературе нет сведений о том, чтобы это было осуществлено на практике. Обычно полагаются на волевое решение оператора или администратора системы.
Но пусть даже точно известно, что тупик есть. Как можно его устранить? Как «растащить баранов с моста»? Как правило, для этого применяется радикальное решение: принудительно прекратить один из тупиковых процессов (сбросить одного барана в реку). Если не помогло — утопить следующего барана. И т.д.
В литературе рассматриваются и более гуманные, но сложные способы. В принципе, можно регулярно запоминать состояние всех или только наиболее ответственных процессов в определенных контрольных точках или через определенные периоды времени. Тогда, вместо полного прекращения процесса, его можно вернуть к одной из последних контрольных точек и придержать там, пока другой баран не перейдет через реку.
Завершая рассмотрение проблемы тупиков, следует признать, что в настоящее время ее практическое значение значительно меньше, чем хотелось бы теоретикам. Во-первых, совсем не легко загнать в тупик современную ОС, работающую на компьютере с огромными ресурсами. В примере мы рассмотрели тупик, возникший из-за 100 Мб памяти, но если учесть еще несколько гигабайт, которые можно использовать в файле подкачки, то запросы процессов должны быть уж очень велики, чтобы привести к тупику. А, скажем, такое устройство, как принтер, в современных ОС вообще не может стать причиной тупика, т.к. система не отдает его во владение ни одному процессу даже на время.
Во-вторых, хотя тупик в принципе остается возможным, пользователь вряд ли даже заметит его. Скорее, он скажет «Опять Windows зависла!» и перезагрузит систему.
Предотвращение тупиков остается действительно важным, например, при разработке встроенной системы, которая должна длительное время безотказно работать без вмешательства человека.