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

Параллельные процессы

Параллельные процессы – процессы, выполнение которых хотя бы частично

Разделение ресурсов

Разделение ресурса – совместное использование несколькими процессами ресурса ВС, когда

Важнейшие задачи

Распределение ресурсов между процессами
Организация защиты ресурсов, выделенных определенному

(

(

Взаимное исключение

Гонки (race conditions) между процессами
Взаимное исключение – такой способ работы

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

Тупики (deadlocks)

Процесс A

Процесс B

Ресурс 1

Ресурс 2

STOP

STOP

Доступ закрыт

Доступ закрыт

Способы реализации взаимного исключения

Запрещение прерываний и специальные инструкции
Алгоритм Петерсона

Семафоры Дейкстры

S – переменная целого типа
Операции над S
Down(S) (или P(S))
Up(S) (или

Использование двоичного семафора для организации взаимного исключения

Двоичный семафор - семафор, начальное

Мониторы

Монитор - языковая конструкция, т.е. некоторое средство, предоставляемое языком программирования и

Обмен сообщениями

Средство, решающее проблему синхронизации
для однопроцессорных систем и систем с

Обмен сообщениями

send (destination, message)
receive (source, message)

Синхронизация
- Операции посылки/приема сообщения могут

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

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

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

# define N 5
# define LEFT (i-1)%N
# define RIGHT (i+1)%N
# define

void philosopher (int i)
{
}

void take_forks(int i)
{
}
while (TRUE) {
}
think();
take_forks(i);
eat();
put_forks(i);
down(&mutex);
state[i] =

void put_forks(int i)
{
}

void test(int i)
{
}
if (state[i] == HUNGRY &&
state[LEFT]

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

void reader (void)
{
}

typedef int semaphore;
semaphore mutex = 1;
semaphore

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