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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

Дата добавления: 2014-01-07