Механизм сигналов позволяет решить, например, проблему критической секции иным способом, чем семафоры.
Подумайте самостоятельно, как это можно сделать.
Сообщения также посылаются процессу системой или другим процессом, однако отличаются от сигналов в двух отношениях.
Во-первых, сообщения не прерывают работу процесса-получателя. Вместо этого они становятся в очередь сообщений. Процесс должен сам вызвать функцию приема сообщения. Если очередь пуста, эта функция блокирует процесс до получения какого-нибудь сообщения.
Во-вторых, с сообщением, в отличие от сигнала, может быть связана информация, передаваемая получателю. Таким образом, сообщения – это средство не только синхронизации, но и обмена данными между процессами.
Поговорим теперь еще об обмене данными. Самым простым и естественным способом такого обмена представляется возможность совместного доступа двух или более процессов к общей области памяти. Но поскольку обычно ОС стремится, наоборот, надежно разделить память разных процессов, то для выделения обшей памяти нужны специальные системные средства.
Общая память служит только средством обмена данными, но никак не решает проблем синхронизации. Участки программы, где происходит работа с общей памятью, часто следует рассматривать как критические секции и защищать семафорами.
Другое часто используемое средство обмена данными – программный канал (pipe; иногда переводится как «трубопровод»). В этом случае для выполнения обмена используются не команды чтения/записи в память, а функции чтения/записи в файл. Программный канал «притворяется файлом», для работы с ним используются те же операции, что для последовательного доступа к файлу: открытие, чтение, запись, закрытие. Однако источником читаемых данных служит не файл на диске, а процесс, выполняющий запись «в другой конец трубы». Данные, записанные одним процессом, но пока не прочитанные другим, хранятся в системном буфере. Если же процесс пытается прочесть данные, которые пока не записаны другим процессом, то процесс-читатель блокируется до получения данных.
4.3.5. Проблема тупиков
Согласно определению из /7/, тупик – это состояние, в котором «некоторые процессы заблокированы в результате таких запросов на ресурсы, которые никогда не могут быть удовлетворены, если не будут предприняты чрезвычайные системные меры».
Как это прикажете понимать?
Прежде всего, давайте отметим, что процессу, действующему в одиночку, не под силам загнать приличную ОС в тупик. Требования процесса не будут удовлетворены, только если они превышают то, что есть у системы. Скажем, процесс требует 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. Другими словами, запрос ресурсов следует выполнять только в порядке возрастания номеров. Нетрудно показать, что это правило является достаточным условием отсутствия тупиков. Но это условие слишком ограничивающее, оно отсекает много ситуаций, когда тупик на самом деле не возник бы.
Наиболее изящен алгоритм банкира, предложенный тем же Дейкстрой. В нем предполагается, что каждый процесс при старте должен объявить системе, на какие ресурсы и в каком максимальном количестве он может в будущем претендовать. Далее, вводится понятие безопасного (в отношении тупиков) состояния системы. Текущее состояние, в котором имеется набор процессов, каждый из которых владеет некоторыми ресурсами, считается безопасным, если имеющихся в наличии свободных ресурсов достаточно для того, чтобы ОС смогла в определенной последовательности удовлетворить максимальные запросы каждого процесса.
Это определение проще понять, если рассмотреть, как проверяется безопасность заданного состояния. Согласно алгоритму, среди имеющихся процессов ищется такой, чьи максимальные заявленные запросы система может удовлетворить, используя имеющиеся свободные ресурсы. Если хотя бы один такой процесс найден, то он вычеркивается из общего списка и все ресурсы, которые он уже успел занять, считаются свободными (т.е. считается, что система смогла завершить этот процесс). Далее, при увеличившихся свободных ресурсах, ищется следующий процесс, чьи запросы система может удовлетворить, и т.д. Если в результате удается вычеркнуть все процессы, то анализируемое состояние системы является безопасным.
Сам же алгоритм банкира можно теперь сформулировать очень просто: любой запрос процесса на выделение ему дополнительных ресурсов должен удовлетворяться только в том случае, если состояние, в которое перейдет система после этого выделения, будет безопасным.