Взаимодействие процессов: синхронизация, тупики. Параллельные процессы Параллельные процессы – процессы, выполнение которых хотя бы частично перекрывается. - презентация

1 Взаимодействие процессов: синхронизация, тупики

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

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

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

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

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

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

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

9 Семафоры Дейкстры S – целочисленная переменная целого семафор Операции над S Down(S) (или P(S) – proberen) Up(S) (или V(S) - verhogen)

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

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

12 Обмен сообщениями для однопроцессорных систем и систем с общей памятью, для систем с распределенной систем с распределенной памятью

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

14 Классические задачи синхронизации процессов

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

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

17 # 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 void philosopher (int i) { } void take_forks(int i) { } while (TRUE) { } think(); take_forks(i); eat(); put_forks(i); down(&mutex); state[i] = HUNGRY; test(i); up(&mutex); down(&s[i]);

19 void put_forks(int i) { } void test(int i) { } if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) { state[i] = EATING; up (&s[i]); down(&mutex); state[i] = THINKING; test(LEFT); test(RIGHT); up(&mutex);

20 Задача «читателей и писателей»

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

22 Задача о «спящем парикмахере»

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