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

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

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

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

Взаимное исключение Гонки (race conditions) между процессами. Взаимное исключение способ работы с разделяемым ресурсом, при котором в тот момент, когда один из процессов работает с разделяемым ресурсом, все остальные процессы не могут иметь к нему доступ.

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

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

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

Семафоры Дейкстры Down ( S ) (или P ( S )) Up ( S ) (или V ( S )) Семафоры Дейкстры формальная модель синхронизации, предложенная голландским учёным Дейкстрой, которая основывается на следующем предположении: имеется тип данных, именуемый семафором. Переменная типа семафор имеет целочисленные значения. Над семафорами определены две операции. Операции, определённые над семафорами Данные операции являются атомарными.

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

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

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

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

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

«Обедающие философы»

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

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

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 ) ; }

Задача: «Читатели и писатели»

typedef int semaphore ; semaphore mutex = 1 ; semaphore db = 1 ; int rc = 0 ; 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 ) ; }

Задача: «Спящий парикмахер»

#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 ) ; }