16. Понятие взаимного исключения. Критический участок.

Атомарное действие – действие, которое не может прерываться другим действием.

Активность – набор атомарных операций.

Процесс – набор атомарных команд.

Чередование операций при псевдопараллельном выполнении активностей приводит к состоянию гонки или состязания между активностями.

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

Условие Бернстайна:

Набор активностей p и q детерминированы, если выполняется следующее условие: множество входных данных p и выходной q не пересекаются, и выходные данные p и выходные q не пересекаются. Иначе набор активностей может быть недетерминированным.

I(p) ∩ O(q)=0; O(p) ∩ O(q)=0

Критический ресурс – ресурс, за обладание которым состязаются несколько процессов.

Критический участок (секция) – участок кода программы, в котором производятся действия с критическим ресурсом.

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

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

Условие Бернстайна слишком жесткие и описывают практически не взаимодействующие процессы. Для реализации детерминированности выполнения и во избежание состояния гонки, применяются алгоритмы взаимного исключения и механизмы синхронизации.

Общая структура алгоритмов синхронизации: пролог обеспечивает взаимное исключение, эпилог – прогресс конечного ожидания:

While ( true )

{

пролог

критическая секция

эпилог

остальная часть

}

Алгоритмы:

1) Запрет прерываний;

2) Переменная замок;

3) Строгое чередование;

4) Флаги готовности;

5) Алгоритм Деккера;

6) Алгоритм булочный.

17. Семафорные примитивы Дейкстры. Решение задачи производителя и потребителя с помощью семафоров.

Семафоры – целочисленная не отрицательная переменная, разделяемая между несколькими процессами, находящимися под управлением ОС, над которой доступны две примитивных операции:

a) probieren P(s): if (s==0) –> блок, s=s-1

уменьшение семафора на 1 если он был больше нуля, в противном случае блокирует процесс до тех пор, пока семафор не увеличится, после чего процесс выводится из состояния блокировки, а семафор уменьшается. Увеличен семафор может быть любым другим процессом, выполнившим операцию V(s).

b) verhogen V(s): s=s+1

Мьютекс – двоичный семафор. Обычно мьютекс связан с критическим ресурсом, если ресурс свободен, то мьютекс равен 1, если ресурс занят – мьютекс равен 0.

Задача: В системе есть несколько процессов производителей данных размещающих эти данные в буфере объемом N и несколько процессов потребителей читающих данные из этого буфера. Требуется организовать совместную работу всех процессов, удовлетворяющую следующим условиям:

a) никакие два процесса не могут одновременно работать с буфером;

b) нельзя читать из пустого буфера;

c) нельзя писать в полный буфер.

Решение:

Semaphore mutex=1; semaphore empty=N; semaphore full=0;

производитель потребитель

while (true) { while (true) {

P (empty); P (full);

P (mutex); P (mutex);

write; read;

V (mutex); V (mutex);

V (full); V (empty);

remainder; } remainder; }

Достоинства семафора: в отличие от алгоритмов синхронизации, процесс в ожидании события не занимает процессорное время, а переводится ядром ОС в состояние блокировки. Когда семафор будет увеличен, ядро ОС переведет заблокированные процесс в состояние готовности и уменьшит семафор.