Лекции по операционным системам, страница 14

Лекция 10. (23.10.02)

Рассмотрим примеры образования тупиков:

Будем считать, что на момент времени t1 состояние системы описывается графом. Имеется 2 процесса P1 и  P2),чки означают количество единиц ресурса.) стрелки означают запрос единицы ресурса, стрелки к процессу - получение единицы ресурса. Допустим, что в момент времени t2 процесс P1 получит единицу ресурса R2. в результате образовался тупик, т. к процесс P1 ждет 2 ух ресурсов, а их ему не хватает, т.к 2 отданы процессу P2. процессу P2 не хватает R2. оба процесса будут ждать бесконечно долго.

    

 Замечание: Еслибы в момент t2 ресурс R2 был бы отдан процессу P2, тогда было бы все нормально, т.е. P2 работал бы т.к получил бы все необходимые ресурсы. А P1 ждал бы.   

Допустим, что имеются 3 процесса взаимодействующие через почтовые ящики.

 Допустим, что P1 является потребителем М1 через Р3. процесс Р2 получает сообщения М1 от Р1. А процесс Р3 сообщения М2 от Р2.

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

Р1:       послать сообщение (Р2,М1, на2)

            Ждать сообщение (Р3, М1 на 1)

Р2:       послать сообщение (Р3, М2 на 3)                    

            Ждать сообщение (Р1, М2 на 2)

Р3:       послать сообщение (Р1, М3 на 1)

            Ждать сообщение (Р2, М2 на 3)

При данном алгоритме реализация процессов будет нормальна функционировать.

Рассмотрим другой  алгоритм:

Р1:       Ждать сообщение (Р3, М1 на 1)

Послать сообщение (Р2,М1, на2)

Р2:       Ждать сообщение (Р1, М2 на 2)         

            Послать сообщение (Р3, М2 на 3)   

Р3:       Ждать сообщение (Р2, М2 на 3)

            Послать сообщение (Р1, М3 на 1)

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