Типы отношений между процессами :

− отношение предшествования (какой-то из двух процессов переходит в другое состояние раньше);

− отношение приоритетности (процесс с некоторым приоритетом может быть приведен в состояние выполнения при выполнении 2-ух условий: 1. в состоянии готовности нет процессов с более высоким приоритетом. 2. ресурс либо свободен, либо занят процессом с более низким приоритетом).

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

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

− отношение производитель – потребитель (используется для процессов с жёстко распределёнными функциями: одни процессы являются производителями, другие- потребителями (пример: ресурсы типа сообщений))

− отношение читатель – писатель (для файловых систем выделяются 2-а класса процессов: 1. только писатели. 2. только читатели)

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

Типичные задачи синхронизации параллельных процессов.

1. Задача взаимного исключения.

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

− одновременно внутри одного критического интервала находится не более одного процесса;

− критические интервалы не должны иметь приоритета в отношении друг друга;

− решение о вхождении процесса в их критические интервалы при одинаковом времени поступления запроса на такое вхождение не откладывается на неопределенный срок, а является конечным во времени решением, решения принимаются операционной системой;

− освобождение критического ресурса и выход из критического интервала должно быть произведено за конечное время;

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

2. Задачи производители – потребители.

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

− выполнить требования задачи взаимного исключения;

− учитывать состояния области памяти: попытка записи сообщения в память должна быть блокирована, если не считано предыдущее сообщение или если его там нет. При этом процессы должны быть оповещены о невозможности передачи сообщения.

Задача читатели – писатели.

Могут быть установлены приоритеты как для читателя, так и для писателя. Если установлена приоритетность писателя, то он осуществляет запись, решает задачу на основе взаимного исключения: он исключает и писателей, и читателей. Если приоритет читателя, то читатели могут исключить и тех, и других или только писателей.(эта задача наиб часто решается при построении файловых систем).

Задачи кругового распределения ресурса («обедающие философы»)

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

Могут возникнуть 2-е опасности:

1. Возникновение тупиковой ситуации.

2.

Необходимо согласовать работу процессов во избежание голодания и тупик ситуации

Для правильного развития процесса требуется ресурс

Возникновение ситуации голодания.

 

 

Чаще всего механизмы имеют программно-аппаратную форму синхронизации.

 

 

Вопрос 10. Дедлок(тупиковая ситуация). Условия возникновения.Стратегии предотвращения и обхода дедлоков.

Deadlock – тупиковая ситуация. Возникает в том случае, когда даже при наличии ресурсов ни один процесс системы не выполняется.

Условия возникновения дедлока:

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

2. Условие ожидания. Процесс, запросивший ресурс, будет ждать, пока запрос не будет удовлетворен, удерживая при этом те ресурсы, которые ему уже выделены.

3. Отсутствие перераспределения. Никакие ресурсы у процесса отнимать нельзя, если они ему уже выделены.

4. Условие кругового ожидания. Существует замкнутая цепь процессов, каждый из которых ждет ресурс, удерживаемый процессом-предшественником.

Решение проблемы дедлока.

1. Стратегия предотвращения тупиков.

Применяется, когда потери от тупиков очень высоки. Позволяет исключить саму возможность взаимоблокировки. Методы предотвращения блокировок можно разбить на 2 класса:

1) косвенный метод – предотвращение возникновения одного из первых 3-ёх условий возникновения дедлока;

2) прямой метод – предотвращение 4-го условия- циклического ожидания.

− Условия взаимного исключения можно подавить неограниченным выделением ресурсов – это слишком дорого.

− Условия ожидания можно подавить, предварительно распределяя ресурсы. В этом случае ресурсы выделяются процессу только все сразу. В этом случае процессу нужно заранее сформулировать запрос на все необх-е ресурсы, это возможно только при статическом выполнении запроса.

− Отсутствие перераспределения подавляется отниманием операционной системой ресурсов.

− Условие кругового ожидания можно подавить, предотвращая образование цепи: метод иерархического выделения ресурсов. Все ресурсы образуют иерархию; процесс, запросив ресурс на определенном уровне иерархии, после этого может запросить ресурс только с более высокого уровня. Процесс может освободить ресурс на данном уровне только после освобождения всех ресурсов на более высоких уровнях. Кругового ожидания не будет.

Стратегия обхода дедлоков.

Можно доказать, что если совокупность процессов находится в неопасном состоянии (отсутствуют дедлоки), то существует, по крайней мере, одна последовательность неопасных состояний процесса. Предполагает, что всегда анализируется, не приводит ли выделение ресурса к тупику. Решение данной задачи – алгоритм банкира. Алгоритм позволяет обходить опасные состояния.

Банкир клиентам выдает сумму денег. Каково должно быть поведение банкира, чтобы он не попал в тупиковую ситуацию: клиент пришёл за деньгами, а их у банкира нет? Поэтому: когда поступает запрос на сумму от клиента, банкир оценивает, может ли он после выдачи кредита удовлетворить хотя бы следующему минимальному запросу. Ограничение: мы должны заранее знать верхние границы мах запросов (границы запроса на ресурс).