Литература по операционным системам содержит множество интересных проблем, которые широко обсуждались и анализировались с применением различных методов синхронизации. В этом разделе мы рассмотрим три наиболее известные проблемы.
Проблема обедающих философов
В 1965 году Дейкстра сформулировал и решил проблему синхронизации, названную им проблемой обедающих философов. С тех пор каждый, кто изобретал еще один новый примитив синхронизации, считал своим долгом продемонстрировать достоинства нового примитива на примере проблемы обедающих философов. Проблему можно сформулировать следующим образом: пять философов сидят за круглым столом, и у каждого есть тарелка со спагетти. Спагетти настолько скользкие, что каждому философу нужно две вилки, чтобы с ними управиться. Между каждыми двумя тарелками лежит одна вилк .
Жизнь философа состоит из чередующихся периодов поглощения пищи и размышлений. (Разумеется, это абстракция, даже применительно к философам, но остальные процессы жизнедеятельности для нашей задачи несущественны.) Когда философ голоден, он пытается получить две вилки, левую и правую, в любом порядке. Если ему удалось получить две вилки, он некоторое время ест, затем кладет вилки обратно и продолжает размышления. Вопрос состоит в следующем: можно ли написать алгоритм, который моделирует эти действия для каждого философа и никогда не застревает? (Кое-кто считает, что необходимость двух вилок выглядит несколько искусственно. Возможно, нам следует заменить итальянскую пищу блюдами китайской кухни, спагетти — рисом, а вилки — соответствующими палочками.)
Можно изменить программу так, чтобы после получения левой вилки проверялась доступность правой. Если правая вилка недоступна, философ отдает левую обратно, ждет некоторое время и повторяет весь процесс. Этот подход также не будет работать, хотя и по другой причине. Если не повезет, все пять философов могут начать процесс одновременно, взять левую вилку, обнаружить отсутствие правой, положить левую обратно на стол, одновременно взять левую вилку, и так до бесконечности. Ситуация, в которой все программы продолжают работать сколь угодно долго, но не могут добиться хоть какого-то прогресса, называется зависанием процесса (по-английски starvation, буквально «умирание от голода». Этот термин применяется даже в том случае, когда проблема возникает не в итальянском или китайском ресторане, а на компьютерах).
Вы можете подумать: «Если философы будут размышлять в течение некоторого случайно выбранного промежутка времени после неудачной попытки взять правую вилку, вероятность того, что все процессы будут продолжать топтаться на месте хотя бы в течение часа, невелика». Это правильно, и для большинства приложений повторение попытки спустя некоторое время не является проблемой. Например, в локальной сети Ethernet в ситуации, когда два компьютера посылают пакеты одновременно, каждый должен подождать случайно заданное время и повторить попытку — на практике это решение хорошо работает. Тем не менее в некоторых приложениях предпочтительным является другое решение, работающее всегда и не зависящее от случайных чисел (например, в приложении для обеспечения безопасности на атомных электростанциях).
Внести улучшение, исключающее взаимоблокировку и зависание процесса: защитить пять операторов, следующих за запросом think, бинарным семафором. Тогда философ должен будет выполнить операцию Down на переменной mutex прежде, чем потянуться к вилкам. А после возврата вилок на место ему следует выполнить операцию Up на переменной mutex. С теоретической точки зрения решение вполне подходит. С точки зрения практики возникают проблемы с эффективностью: в каждый момент времени может есть спагетти только один философ. Но вилок пять, поэтому необходимо разрешить есть в каждый момент времени двум философам.
Решение, исключает взаимоблокировку и позволяет реализовать максимально возможный параллелизм для любого числа философов. Здесь используется массив state для отслеживания душевного состояния каждого философа: он либо ест, либо размышляет, либо голодает (пытаясь получить вилки). Философ может начать есть, только если ни один из его соседей не ест. Соседи философа с номером i определяются макросами LEFT и RIGHT.
Проблема читателей и писателей
Проблема обедающих философов полезна для моделирования процессов, соревнующихся за монопольный доступ к ограниченному количеству ресурсов, например к устройствам ввода-вывода. Другой известной задачей является проблема читателей и писателей, моделирующая доступ к базе данных. Представьте себе базу данных бронирования билетов на самолет, к которой пытается получить доступ множество процессов. Можно разрешить одновременное считывание данных из базы, но если процесс записывает информацию в базу, доступ остальных процессов должен быть прекращен, даже доступ на чтение. Как запрограммировать читателей и писателей?
Чтобы избежать такой ситуации, нужно немного изменить программу: если пишущий процесс ждет доступа к базе, новый читающий процесс доступа не получает, а становится в очередь за пишущим процессом. Теперь пишущему процессу нужно подождать, пока базу покинут уже находящиеся в ней читающие процессы, но не нужно пропускать вперед читающие процессы, пришедшие к базе после него. Недостаток этого решения заключается в снижении производительности, вызванном уменьшением конкуренции. В представлено решение, в котором пишущим процессам предоставляется более высокий приоритет.
Проблема спящего брадобрея
Действие еще одной классической проблемной ситуации межпроцессного взаимодействия разворачивается в парикмахерской. В парикмахерской есть один брадобрей, его кресло и п стульев для посетителей. Если желающих воспользоваться его услугами нет, брадобрей сидит в своем кресле и спит .Если в парикмахерскую приходит клиент, он должен разбудить брадобрея. Если клиент приходит и видит, что брадобрей занят, он либо садится на стул (если есть место), либо уходит (если места нет). Необходимо запрограммировать брадобрея и посетителей так, чтобы избежать состояния состязания. У этой задачи существует много аналогов в сфере массового обслуживания, например информационная служба, обрабатывающая одновременно ограниченное количество запросов, с компьютеризированной системой ожидания для запросов.
В предлагаемом решении используются три семафора: customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается — он уже не ждет); barbers, количество брадобреев (0 или 1), простаивающих в ожидании клиента, и mutex для реализации взаимного исключения. Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей.
Она является копией переменной customers. Присутствие в программе этой переменной связано с тем фактом, что прочитать текущее значение семафора невозможно. В этом решении посетитель, заглядывающий в парикмахерскую, должен сосчитать количество ожидающих посетителей. Если посетителей меньше, чем стульев, новый посетитель остается, в противном случае он уходит.
Когда брадобрей приходит утром на работу, он выполняет процедуру barber, блокируясь на семафоре customers, поскольку значение семафора равно 0. Затем брадобрей засыпает, и спит, пока не придет первый клиент.
Приходя в парикмахерскую, посетитель выполняет процедуру customer, запрашивая доступ к mutex для входа в критическую область. Если вслед за ним появится еще один посетитель, ему не удастся что-либо сделать, пока первый посетитель не освободит доступ к mutex. Затем посетитель проверяет наличие свободных стульев, в случае неудачи освобождает доступ к mutex и уходит.
Если свободный стул есть, посетитель увеличивает значение целочисленной переменной waiting. Затем он выполняет процедуру up на семафоре customers, тем
Самым активизируя поток брадобрея. В этот момент оба — посетитель и брадобрей — активны. Когда посетитель освобождает доступ к mutex, брадобрей захватывает его, проделывает некоторые служебные операции и начинает стричь клиента.
По окончании стрижки посетитель выходит из процедуры и покидает парикмахерскую. В отличие от предыдущих программ, цикла посетителя нет, поскольку каждого посетителя стригут только один раз. Цикл брадобрея существует, и брадобрей пытается найти следующего посетителя. Если ему это удается, он стрижет следующего посетителя, в противном случае брадобрей засыпает.
Стоит отметить, что, несмотря на отсутствие передачи данных в проблеме читателей и писателей и в проблеме спящего брадобрея, обе эти проблемы относятся к проблемам межпроцессного взаимодействия, поскольку требуют синхронизации нескольких процессов.
