Проблема тупиков. Граф ожидания

При совместной работе нескольких процессов с несколькими ресурсами возможна ситуация при которой 2 или более участников оказываются в состоянии блокировки, из которой каждый мог бы выйти, если бы освободился ресурс, но другие не могут, тк находятся в заблокированном состоянии. Предполагается, что есть 5 философов и тарелка спагетти, 1 философ должен есть 2мя вилками => если все они одновременно возьмут по вилке, то остальные будут ждать другого, возникнет тупик. Для возникновения тупика достаточно и 2 процесса и 2 ресурса m1, m2. Если 1 процесс выполняет код lock(m1),Lock(m2), а второй те же вызовы только в обратном порядке. Оба процесса успеют сделать по одному вызову и войдут в состояние блокировки на 2м вызове.

Тупиковая ситуация без взаимоисключения Запуск команды ls для получения списка файлов в текущем каталоге.

Char buf [100]

Int rc; int[fd]; pipe(fd);

If (fork()==0) {dup2 (fd[1],1); Close (fd[1]);

Close (fd[0]); execlp(“ls”,”ls”,null);

Perror (“ls”); exit(1)}

Close (fd[1]);wait(null);

While (rc=read (fd{0},buf,sizeof(buf))>0) {…} Зависнуть программа может, если ls обрабатывает большой каталог. Запуск начинается в дочернем процессе программа ls, получаем дискриптор стандартного вывода, прежде чем завершиться ls будет писать в канал имена текущего каталога; родительский процесс выполняет вызов wait, в результате чего он блокируется до тех пор пока дочерний не завершится, только после этого родительский выполнит чтение из буфера канала. Можно переместить wait после while. Возникает тупик, когда родитель ждет, а дочерний заполняет буфер.

Реализация задачи 5 философов Создадим массив из 5 mutex, каждый m связан с определенной вилкой и назовем массив forks. Нумерация от 0 до 4. Есть 2 вспомогательных функций

Int left (int n)

Int right (int n) {return(n+1)%5}

Номер вилки лежащей слева от философа совпадает с номером самого философа. Тогда жизненный цикл философа

Void philosopher (int n){for{;;}{think(); lock(forks[n]); lock( forks[right(n)]); eat();

Unlock(fork[n]); unlock(forks[right(n)]; }}

При одновременном выполнении таких процедур взял-поел-положил для n=(0..4) возможна ситуация, когда все они успеют вып блокирование по первому lock, при этом все 5 вилок (m) окажутся блокированными, все процессы заблокируются на следующей строчке. Одно из решений это применение семафора (не позволять философам приступить к трапезе одновременно).

Заведем семафор sem.

void philosopher(int n){ for(i,i) {think(); down(sem); lock(forks[n]); lock(forks[right(n)]);

eaf(); unlock(forks[n]); unlock(forks[right(n)]); up(sem);}}

Семафор sem, начальное его значение 1, то одновременно употреблять спагетти сможет 1 философ. Если в начальное значение записать 2, ситуация тупика возможна. Максимальное возможное значение семафора 4, иначе теряется его смысл. При 4 3 философа взяли по 1й вилке, а один из них 2.

Понятие графа ожидания

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

		Простейший пример тупика