Основы операционных систем

Тема 6. Механизмы синхронизации

Недостатки программных алгоритмов Непроизводительная трата процессорного времени в циклах пролога Непроизводительная трата процессорного времени в циклах пролога Возможность возникновения тупиковых ситуаций при приоритетном планировании Возможность возникновения тупиковых ситуаций при приоритетном планировании while (some condition) { entry section critical section exit section remainder section } while (some condition) { entry section critical section exit section remainder section } LH

Семафоры Дейкстры (Dijkstra) Допустимые атомарные операции P(S): пока S == 0 процесс блокируется; P(S): пока S == 0 процесс блокируется; S = S - 1 S = S - 1 V(S): S = S + 1 V(S): S = S + 1 S – семафор – целая разделяемая переменная с неотрицательными значениями При создании может быть инициализирована любым неотрицательным значением

Проблема Producer-Consumer Producer: while (1) { } produce_item(); put_item(); Consumer: } get_item(); consume_item(); Информация передается через буфер конечного размера – N

Проблема Producer-Consumer Producer: while (1) { } produce_item(); put_item(); Consumer: Решение с помощью семафоров Semaphore mut_ex = 1; Semaphore full = 0; Semaphore empty = N; P(empty); P(mut_ex); V(full); V(mut_ex); while (1) { } consume_item(); get_item(); P(full); P(mut_ex); V(empty); V(mut_ex);

Мониторы Хора (Hoare) Monitor monitor_name { } Описание внутренних переменных; void m 1 (…) { … } void m 2 (…) { … } void m n (…) { … } … Блок инициализации переменных; Структура

Мониторы Хора (Hoare) Condition C; Выполнение операции signal приводит к разблокированию только одного процесса, ожидающего этого (если он существует) Процесс, выполнивший операцию wait над условной переменной, всегда блокируется Условные переменные (condition variables) C.wait C.wait C.signal C.signal Процесс, выполнивший операцию signal, немедленно покидает монитор

Проблема Producer-Consumer Producer: while (1) { } produce_item(); Consumer: Решение с помощью мониторов PC.put (); while (1) { } consume_item(); PC.get (); Monitor PC { } Condition full, empty; int count; void put () { if (count == N) full.wait; if (count == N) full.wait; put_item(); count++; put_item(); count++; if (count == 1) empty.signal; if (count == 1) empty.signal; } { count = 0; } void get () { if (count == 0) empty.wait; if (count == 0) empty.wait; get_item(); count--; get_item(); count--; if (count == N-1) full.signal; if (count == N-1) full.signal; }

Сообщения Примитивы для обмена информацией между процессорами Для передачи данных: Для передачи данных: send (address, message) send (address, message) блокируется при попытке записи в заполненный буфер блокируется при попытке записи в заполненный буфер Для приема данных Для приема данных receive (address, message) блокируется при попытке чтения из пустого буфера Обеспечивают взаимоисключения при работе с буфером

Проблема Producer-Consumer Producer: while (1) { } produce_item(); send (address, item) Решение с помощью сообщений Consumer: while (1) { } receive (address,item); consume_item()

Эквивалентность семафоров, мониторов и сообщений Реализация мониторов через семафоры Semaphore mut_ex = 1; /* Для организации взаимоисключения */ При входе в монитор При нормальном выходе из монитора void mon_enter (void){ P(mut_ex); P(mut_ex);} void mon_exit (void){ V(mut_ex); V(mut_ex);} Semaphore c i = 0; int f i = 0; /* Для каждой условной переменной */ Для операции wait void wait (i){ f i += 1; f i += 1; V(mut_ex); P(c i ); V(mut_ex); P(c i ); f i -= 1; f i -= 1;} Для операции signal void signal_exit (i){ if (f i ) V(c i ); if (f i ) V(c i ); else V(mut_ex); else V(mut_ex);}

Эквивалентность семафоров, мониторов и сообщений Реализация сообщений через семафоры буфер Для каждого процесса: Semaphore c i = 0; Очередь на чтение Очередь на запись Один на всех: Semaphore mut_ex = 1; Чтение P(mut_ex) Есть msg? – встать в очередь – V(mut_ex) – V(mut_ex) – P(c i ) – P(c i ) – прочитать – есть кто на запись? – есть кто на запись? – V(mut_ex) – удалить – V(c j ) – V(c j ) Semaphore c j = 0; Один на всех: Semaphore mut_ex = 0; -нет PiPiPiPi -да M1M1M1M1 -нет PjPjPjPj -да Semaphore c j = 1;

Эквивалентность семафоров, мониторов и сообщений Реализация сообщений через семафоры буфер Для каждого процесса: Semaphore c i = 0; Очередь на чтение Очередь на запись Один на всех: Semaphore mut_ex = 1; Запись P(mut_ex) Есть место? – встать в очередь – V(mut_ex) – V(mut_ex) – P(c i ) – P(c i ) – записать – есть кто на чтение? – есть кто на чтение? – V(mut_ex) – удалить – V(c j ) – V(c j ) Semaphore c j = 0; Один на всех: Semaphore mut_ex = 0; -нет PjPjPjPj -да M1M1M1M1 -нет PiPiPiPi -да Semaphore c j = 1; M2M2M2M2 M3M3M3M3 M4M4M4M4

Эквивалентность семафоров, мониторов и сообщений Реализация семафоров через мониторы Monitor sem { int count; int count; Condition c i ; /* для каждого процесса */ Condition c i ; /* для каждого процесса */ очередь для ожидающих процессов; очередь для ожидающих процессов; void P(void){ void P(void){ if (count == 0) { добавить себя в очередь; if (count == 0) { добавить себя в очередь; c i. wait; c i. wait; } count = count -1; count = count -1; } void V(void){ void V(void){ count = count+1; count = count+1; if(очередь не пуста) { удалить процесс P j из очереди; if(очередь не пуста) { удалить процесс P j из очереди; c j.signal; c j.signal; } } { count = N; } { count = N; }}

Эквивалентность семафоров, мониторов и сообщений Реализация семафоров через сообщения send (A, P, P1); send (A, P, P1); receive (P1, msg); receive (P1, msg); P1 Pm A int count = 1; P0P0P0P0 Для ожидания ожидания while(1) { while(1) { receive (A, msg); receive (A, msg); if(это P сообщение){ if(это P сообщение){ if(count > 0) {count = count -1; if(count > 0) {count = count -1; send (Pi, msg); } send (Pi, msg); } else добавить в очередь; else добавить в очередь; } else if(это V сообщение) { else if(это V сообщение) { P1P1P1P1 send (A, V,Pm); send (A, V,Pm); receive (Pm, msg); receive (Pm, msg); PmPmPmPm… send(Pi, msg); send(Pi, msg); if(есть ждущие){ if(есть ждущие){ удалить из очереди; удалить из очереди; send (Pk, msg); } send (Pk, msg); } else count = count+1; else count = count+1; }} P:V: P, P1 int count = 0; msg P1P1P1P1 V,Pm msg msg