Выполнять требования задачи взаимного исключения по отношению к критическому ресурсу – обобщенной памяти для хранения сообщения;
Учитывать состояние обобщенной области памяти, характеризующей возможность или невозможность посылки (принятия) очередного сообщения.
Попытка процесса–производителя поместить очередное сообщение в область, из которой не было считано предыдущее сообщение процессом–потребителем, должна быть блокирована.
Процесс–производитель должен быть:
либо должен быть оповещен о невозможности помещения сообщения,
либо должен быть переведен в состояние ожидания возможности поместить сообщение через некоторое время по мере освобождения памяти.
Аналогично должна быть блокирована попытка процесса–потребителя считать сообщение из области, когда процесс - производитель не поместил туда очередного сообщения.
Процесс-потребитель должен быть:
либо должен быть оповещен о невозможности считывания,
либо должен быть переведен в состояние ожидания поступления очередного сообщения.
Если используется вариант с ожиданиями изменения состояния обобщенной области, необходимо обеспечить перевод ожидающих процессов в состояние готовности всякий раз, когда изменится состояние области:
либо процесс-производитель поместит очередное сообщение в область, и оно может быть считано ожидающим процессом-потребителем
либо процесс-потребитель считал очередное сообщение из области и обеспечил возможность ожидающему процессу-производителю послать очередное сообщение
В общем случае число, как процессов-производителей, так и процессов - потребителей может быть большим одного.
Каждый из таких процессов может устанавливать не только одностороннюю, но и двухстороннюю связь через одну и ту же обобщенную область или другие области. Области могут хранить не одно, а большее количество сообщений.
Задача «читатели-писатели»
В отношении некоторой области внешней памяти, являющейся критическим ресурсом для параллельных процессов, работающих с ней, выделяется два типа процессов:
Первый тип – процессы-писатели. Они могут записывать информацию в область, и могут это делать, только исключая как друг друга, так и процессов-читателей (на основе решения задачи взаимного исключения)
Второй тип – процессы-читатели. Считывают информацию из области (могут одновременно, если это допускает соответствующее устройство)
Имеются различные варианты взаимодействия между писателями и читателями:
Устанавливается приоритетность в использовании критического ресурса процессам-читателям. Если хотя бы один процесс-читатель пользуется ресурсом, то он закрыт для всех писателей и доступен всем читателям.
Наоборот, больший приоритет у писателей. При появлении запроса от процесса-писателя ресурс закрывается для всех читателей.
Наиболее характерная область использования этой задачи – при построении файловых систем ОС.
Задача кругового распределения ресурсов (обедающие философы).
Pa, Pb, Pc – параллельные процессы
r1, r2, r3 – ресурсы
Особенность развития процессов такова, что:
для выполнения процесса Pa ему требуется выделить одновременно ресурсы r1 и r2 ,
для выполнения процесса Pb ему требуется выделить одновременно ресурсы r2 и r3 ,
для выполнения процесса Pc ему требуется выделить одновременно ресурсы r3 и r1 .
Скорости развития процессов произвольны. Переходы из выполняющегося состояния в другие происходят в непредсказуемые моменты.
Необходимо обеспечить максимально параллельное и правильное развитие процессов.
Синхронизация в данном случае заключается в определенном упорядочении действий процессов по захвату ресурсов во избежание возможных блокировок одними процессами других.
Две опасности:
- возникновение тупиковой ситуации при распределении ресурсов
- возникновение ситуации голодания в отношении некоторого процесса при распределении ресурса
Пример: задача об обедающих философах Э. Дейкстра (Взаимодействие последовательных процессов).
Большинство задач ОС по согласованию параллельных процессов можно решить либо с помощью этих типовых задач, либо с помощью их модификаций.
Пример реализации взаимного исключения в операционной системе Windows NT приведен на рис. 4.3.
Рис. 4.3. Реализация взаимного исключения в операционной системе Windows NT