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

Презентация на тему: " Управление процессами 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 «Обедающие философы» (доступ равноправных процессов к разделяемому ресурсу)

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 ] ; «Обедающие философы» Правильное решение с использованием семафоров

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

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