Билет 29. Взаимодействие процессов: синхронизация, тупики

Параллельные процессы

Процессы, выполнение которых хотя бы частично перекрывается по времени, называются параллельными процессами.

Независимые процессы – процессы, использующие независимое множество ресурсов и на результат работы такого процесса не влияет работа независимого от него процесса.

Взаимодействующие процессы совместно используют ресурсы, и выполнение одного может оказывать влияние на результат другого.

Совместное использование несколькими процессами ресурса ВС, когда каждый из процессов одновременно владеет ресурсом называют разделением ресурса.

Разделению подлежат как аппаратные, так программные ресурсы.

Разделяемые ресурсы, которые должны быть доступны в текущий момент времени только одному процессу – это так называемые критические ресурсы. Таковыми ресурсами могут быть, как внешнее устройство, так и некая переменная, значение которой может изменяться разными процессами.

Важнейшим требованием мультипрограммирования с точки зрения распределения ресурсов является следующее: результат выполнения процесса не должен зависеть от порядка переключения выполнения между процессами, т.е. от соотношения скорости выполнения процесса со скоростями выполнения других процессов.

Рассмотрим пример ситуации, в которой нарушается требование мультипрограммирования:

 

Оба процесса выполняют некоторую условную функцию if, в которой есть условный input (ввод некоторого символа) и условный output. Видно, что при такой ситуации у нас получается, что процесс А считал в разделяемую переменную in некоторый символ, после чего управление было передано на процесс В, и процесс В затер значение, которое считал процесс А. После чего он вывел новое значение, управление опять было передано процессу А, и процесс А вывел значение, не то которое он считал, а то, которое было затерто уже процессом В.

Такие ситуации называются гонками (race conditions) между процессами, а процессы – конкурирующими.

Часть программы (фактически набор операций), в которой осуществляется работа с критическим ресурсом, называется критической секцией, или критическим интервалом.

 

Единственный способ избежать гонок при использовании разделяемых ресурсов – контролировать доступ к любым разделяемым ресурсам в системе. При этом необходимо организовать взаимное исключение – т.е. такой способ работы с разделяемым ресурсом, при котором постулируется, что в тот момент, когда один из процессов работает с разделяемым ресурсом, все остальные процессы не могут иметь к нему доступ.

Проблемы организации взаимного исключения

• Тупики (deadlocks)

При организации взаимного исключения могут возникнуть тупики (deadlocks), ситуации в которой конкурирующие за критический ресурс процессы вступают в клинч – безвозвратно блокируются. В тупике могут «участвовать» произвольное количество ресурсов.

• Блокирование (дискриминация)

Блокирование – это ситуация, когда один из процессов никогда не получит доступа к ресурсу, т.е. будет ожидать вечно. Эта проблема присуща многим алгоритмам синхронизации, поскольку в любом случае если несколько процессов желают получить доступ к критическому ресурсу, то в каждый конкретный момент выбирается один из них, при этом естественно возможна ситуация, что один из этих процессов не будет выполнен никогда, т.е. этот алгоритм не является справедливым, всякий раз выбирается другой процесс, он получает доступ к ресурсу, а наш некоторый процесс будет ожидать вечно. Вот эта ситуация очень плохая, и хороший алгоритм организации взаимного исключения должен не допускать дискриминации среди процессов, т.е. быть справедливым.

Билет 30. Способы реализации взаимного исключения

Семафоры Дейкстры

Семафор представляет собой переменную целого типа S, над которой определены две операции: down(s) (или P(S)) и up(S) (или V(S)). Оригинальные обозначения P и V, данные Дейкстрой.

down(S) проверяет значение семафора, и если оно больше нуля, то уменьшает его на 1. Если же это не так, процесс блокируется, причем операция down считается незавершенной. Вся операция является неделимой, т. е. проверка значения, его уменьшение и, возможно, блокирование процесса производится как одно атомарное действие, которое не может быть прервано.

up(S) увеличивает значение семафора на 1. При этом, если в системе присутствуют процессы, блокированные ранее при выполнении down на этом семафоре, ОС разблокирует один из них с тем, чтобы он завершил выполнение операции down, т. е. вновь уменьшил значение семафора.

Увеличение значения семафора и, возможно, разблокирование одного из процессов и уменьшение значения являются атомарной неделимой операцией.

Семафоры – это низкоуровневые средства синхронизации, для корректной практической реализации которых необходимо наличие специальных, атомарных семафорных машинных команд.

Мониторы

Идея монитора была впервые сформулирована в 1974 г. Хоаром. В отличие от других средств, монитор представляет собой языковую конструкцию, т. е. Некоторое средство, предоставляемое языком программирования и поддерживаемое компилятором. Монитор представляет собой совокупность процедур и структур данных, объединенных в программный модуль специального типа.

Три основных свойства монитора:

1. структуры данных, входящие в монитор, могут быть доступны только для процедур, входящих в этот монитор;

2. процесс «входит» в монитор путем вызова одной из его процедур;

3. в любой момент времени внутри монитора может находиться не более одного процесса. Если процесс пытается попасть в монитор, в котором уже находится другой процесс, он блокируется.

Обмен сообщениями

 

Следующий способ реализации взаимного исключения – это обмен сообщениями. Вообще обмен сообщениями – это программное средство, которое используется очень широко, не только для решения проблем синхронизации, но и для проблем синхронизации оно тоже может быть использовано.

Основная функциональность метода обеспечивается двумя примитивами:

send (destination, message), receive (source, message).

Основные особенности, которыми может обладать та или иная система обмена сообщениями:

• Синхронизация: не блокирующий Процесс – осуществляющий не блокирующий send, выходит сразу же; блокирующий Процесс – осуществляющий отправку данных, при осуществлении блокирующего send, он будет заблокирован до тех пор, пока данные не будут получены.

• Адресация: прямая – При отправки сообщений указывается непосредственно некоторый идентификатор процесса; косвенная – Т.е. когда сообщение отправляется не непосредственно процессу, а в почтовый ящик.

• Длина сообщения