Управление процессами 3.Взаимодействие процессов: синхронизация, тупики 3.1.Разделение ресурсов 3.2.Взаимное исключение 3.2.1.Проблемы реализации взаимного. - презентация

1 Управление процессами 3.Взаимодействие процессов: синхронизация, тупики 3.1.Разделение ресурсов 3.2.Взаимное исключение Проблемы реализации взаимного исключения Способы реализации взаимного исключения Семафоры Дейкстры Мониторы Обмен сообщениями 3.3.Примеры

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

3 Разделение ресурсов Разделение ресурса совместное использование несколькими процессами ресурса ВС. Критические ресурсы разделяемые ресурсы, которые должны быть доступны в текущий момент времени только одному процессу. Критическая секция или критический интервал часть программы (фактически набор операций), в которой осуществляется работа с критическим ресурсом.

4 Процесс А input(in); output(in); X Y Y void echo () { char in; input ( in ) ; output ( in ) ; } Результат выполнения процессов не должен зависеть от порядка переключения выполнения между процессами. Требование мультипрограммирования Y Процесс B input(in); output(in); Гонки (race conditions) между процессами.

5 Взаимное исключение Тупики (deadlocks) Блокирование (дискриминация ) Тупик ситуация, при которой из-за некорректной организации доступа и разделения ресурсов происходит взаимоблокировка. Блокирование доступ одного из процессов к разделяемому ресурсу не обеспечивается из-за активности других, более приоритетных процессов. Взаимное исключение способ работы с разделяемым ресурсом, при котором в тот момент, когда один из процессов работает с разделяемым ресурсом, все остальные процессы не могут иметь к нему доступ.

6 Тупики (Deadlocks) Процесс A Процесс B Ресурс 1Ресурс 2 STOP Доступ закрыт

7 Способы реализации взаимного исключения Запрещение прерываний и специальные инструкции Алгоритм Петерсона Активное ожидание Семафоры Дейкстры Мониторы Хоара Обмен сообщениями Способы, которые позволяют работать с разделяемыми ресурсами. Существуют как аппаратные, так и алгоритмические модели.

8 Семафоры Дейкстры Down ( S ) или P ( S ) – Proberen (проверить) Up ( S ) или V ( S ) – Verhogen (увеличить) Семафоры Дейкстры формальная модель синхронизации, предложенная голландским учёным Эдсгером В. Дейкстрой Операции, определённые над семафорами

9 Использование двоичного семафора для организации взаимного исключения Двоичный семафор семафор, максимальное значение которого равно 1. процесс 1 int semaphore; … down ( semaphore ) ; /*критическая секция процесса 1*/ … up ( semaphore ) ; … процесс 2 int semaphore; … down ( semaphore ) ; /*критическая секция процесса 2*/ … up ( semaphore ) ; …

10 Мониторы Хоара Монитор Хоара совокупность процедур и структур данных, объединенных в программный модуль специального типа. Структуры данных монитора доступны только для процедур, входящих в этот монитор Процесс «входит» в монитор по вызову одной из его процедур В любой момент времени внутри монитора может находиться не более одного процесса

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

12 Обмен сообщениями Синхронизация send/receive блокирующие send/receive неблокирующими Адресация Прямая (ID процесса) Косвенная (почтовый ящик, или очередь сообщений)

13 Классические задачи синхронизации процессов 1.Обедающие философы 2.Задача о читателях и писателях 3.Задача о спящем парикмахере

14 «Обедающие философы» (доступ равноправных процессов к разделяемому ресурсу)

15 #define N 5 void philosopher ( int i ) { while (TRUE) { think () ; take_fork ( i ) ; take_fork ( ( i + 1 ) % N ) ; eat () ; put_fork ( i ) ; put_fork ( ( i + 1 ) % N ) ; } return; } «Обедающие философы» Простейшее решение

16 # define N 5 # define LEFT ( i – 1 ) % N # define RIGHT ( i + 1 ) % N # define THINKING 0 # define HUNGRY 1 # define EATING 2 typedef int semaphore ; int state [ N ] ; semaphore mutex = 1 ; semaphore s [ N ] ; «Обедающие философы» Правильное решение с использованием семафоров

17 void philosopher ( int i ) {while ( TRUE ) { think () ; take_forks ( i ) ; eat (); put_forks ( i ) ; } void take_forks ( int i ) { down ( & mutex ) ; state [ i ] = HUNGRY ; test ( i ) ; up( & mutex ) ; down ( & s [ i ] ) ; } «Обедающие философы» Правильное решение с использованием семафоров void test ( int i ) { if ( ( state [ i ] == HUNGRY ) && ( state [ LEFT ] != EATING ) && ( state [ RIGHT ] != EATING )) { state [ i ] = EATING ; up ( & s [ i ] ) ; } void put_forks ( int i ) { down ( & mutex ) ; state[i] = THINKING ; test ( LEFT ) ; test ( RIGHT ) ; up ( & mutex ) ; }

18 «Читатели и писатели» (задача резервирования ресурса)

19 typedef int semaphore ; int rc = 0 ; semaphore mutex = 1 ; semaphore db = 1 ; void reader ( void ) { while ( TRUE ) { down ( & mutex ) ; rc++ ; if ( rc == 1 ) down ( & db ) ; up ( & mutex ) ; read_data_base () ; down ( & mutex ) ; rc–– ; if ( rc ==0 ) up ( & db ) ; up ( & mutex ) ; use_data_read () ; } void writer ( void ) { while ( TRUE ) { think_up_data () ; down ( & db ) ; write_data_base () ; up ( & db ) ; }

20 «Спящий парикмахер» (клиент-сервер с ограничением на длину очереди)

21 #define CHAIRS 5 typedef int semaphore ; semaphore customers = 0 ; semaphore barbers = 0 ; semaphore mutex = 1 ; int waiting = 0 ; void barber ( void ) { while ( TRUE ) { down ( & customers ) ; down ( & mutex ) ; waiting = wating – 1 ; up ( & barbers ) ; up ( & mutex ) ; cut_hair () ; } void customer ( void ) { down ( & mutex ) ; if ( waiting < CHAIRS ) { waiting = waiting + 1 ; up ( & customers ) ; up ( & mutex ) ; down ( barbers ) ; get_haircut () ; } else { up ( & mutex ) ; }