Условие возникновения тупиков

1) условие взаимоисключения

2) условие ожидания ресурса. Если процесс взял какой-то ресурс, а остальные ещё не получил, он ранее ожидаемые ресурсы удерживает.

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

4)условие кругового ожидания. Есть несколько процессов, которые захватили ресурс, но им его не хватает.

 

Математически строго показано, что для возникновения тупика необходимо выполнение всех 4-х условий.

 

Основные направления борьбы с тупиками

1) игнорировать проблему

2) обнаружение тупиков

3) восстановление после тупиков

4) обход тупиков за счет тщательного распределения ресурсов

5) предотвращение тупиков за счет нарушения любого из условий возникновения тупиков

Алгоритм Страуса

Обнаружение тупиков

необходимо установить, что возникла тупиковая ситуация

ресурс

нужно определить процессы и ресурсы, которые вовлечены в ситуацию

процесс

ресурс R

процесс

 

ресурс K

процесс А удерживает рес. R

 

E

G

B

D

F

C

A

P

S

W

V

V

T

Восстановление после тупиков.

предположим, что тупик обнаружен

восстановиться

откат назад, восстановление ситуации предшествующей возникновению тупика

при откатах данные теряются частично.

 

Сложность восстановления после тупиков:

1. по большей части в ОС отсутствуют механизмы эффективного восстановления

2. если даже такие средства есть, то они затратные

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

 

Восстановление с помощью перераспределения ресурсов

У ОС должна быть возможность изъять один ресурс и передать его другому процессу.

 

Восстановление через откат назад.

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

 

Восстановление через ликвидацию системных процессов

есть риск потери данных убитого процесса

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

 

7.8. Способы обхода тупиков путём распределения ресурсов

Цель: предотвращать условия возникновения тупиков, иначе говоря, ОС, предоставляющая ресурсы процессу должна быть уверена в безопасности этой операции.

А всегда ли возможно предусмотреть появление тупика, при выделении ресурса процессом?

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

 

Алгоритм банкира.

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

 

Пусть есть несколько n устройств. Ос принимает запрос от процесса, если максимальная потребность в ресурсе не превышает n.

пользователь гарантирует, что все устройства возвратит ОС за конечное время

текущее состояние системы называется надёжным, если ОС может обеспечить всем процессам выполнение в течении конечного времени

выделение ресурса возможно, если состояние системы останется надёжным.

 

устройство № пользователя	текущее количество	максимальная потребность

 

данное состояние надёжно.

Система удовлетворяет только те запросы, которые оставляют её в надёжном состоянии и отклоняет остальные.

 

Недостатки алгоритма банкира

1) алгоритм предполагает фиксированное количество ресурсов

3) алгоритм требует постоянное количество пользователей

4) алгоритм предполагает гарантированное удовлетворение запроса за конечное время

алгоритм требует чтоб клиенты вовремя возвращали ресурсы

5) необходимо чтобы пользователь указывал точную потребность в ресурсе.

 

Предотвращение тупиков за счет предотвращения условий их возникновения

ели нарушить одно из 4-х условий возникновения тупиков гарантировано, что тупика не будет