Вопрос 33. Необходимые условия возникновения тупика

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

1. Многопроцессность

2. Наличие ресурса, который необходимо монополизировать

3. Процессы не отказываются от ожидания ресурса

4. Ресурсы не перераспределяемы

5. Наличие циклического ожидания

Вопрос 34. Подходы к задаче о предотвращении тупика

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

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

Третий подход к решению задачи предотвращения тупика состоит в создании стратегии упорядочивания ресурсов. Все ресурсы делятся на классы К1,К2,К3,...,Кn так, что ресурс из класса Ki может быть выделен процессу тогда и только тогда, когда этому процессу не распределены ресурсы из классов Ki,K_i+1,…,Kn. Классификация ресурсов выполняется в соответствии с их свойствами и естественным порядком запросов на них от процессов. Самые дорогие ресурсы обычно ставятся в старшие классы. Например, К1-файлы, которые открывает процесс, К2-оперативная память системы, запрашиваемая динамически, К3-устройства ввода/вывода.

Вопрос 35. Определение графа повторно используемых ресурсов

Граф ПИР (SR-граф) – это ориентированный двудольный граф SR={N,E}, где N – это множество вершин , где -конечное множество вершин, представляющих процессы, -конечное множество вершин, представляющих ресурсы системы, ; Е- множество вершин графа .

Ri

лементы графа ПИР обладают следующими свойствами:

1. – вершина, которая представляет ПИР, имеет пометку (ci,ti), ci – емкость данного ресурса, а ti-количество доступного ресурса на данный момент.

   

   pj

2. - вершина, которая представляет процесс в системе.

3. - ребро с весом k, представляющее собой выполненный, но пока еще не ……………………………… удовлетворенный запрос на k единиц ПИР

pj

Ri

k

4. - ребро с весом k, представляющее собой все выполненные …………………………………распределения ресурса процессу по его удовлетворенным запросам.

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

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