Лекция 08 - chrislvt/OS GitHub Wiki
Взаимодействие параллельных процессов
Взаимодействие параллельных процессов это тема которая раскрывает базовые понятия, базовые проблемы связанные действительно с взаимодействием параллельных процессов. Очевидно что такие же проблемы возникают и при взаимодействии потоков, но здесь имеются отличия. Дело в том, что каждый процесс имеет собственное защищённое адресное пространство, потоки своих адресных пространств не имеют и выполняются в адресном пространстве процесса, поэтому потоки могут разделять глобальные переменные, процессы разделять глобальные переменные не могут.
Очевидно, что системы предоставляют соответствующие системные вызовы, для того чтобы процессы и потоки могли взаимодействовать, но прежде чем рассматривать IPC (Inter Process Communication) - это общее название средств взаимодействия параллельных процессов, мы должны рассмотреть саму проблему.
Рассмотрим самый простой пример, который встречается. Представим работу двух филиалов банков. В конце ддя каждый из филиалов должен перечислить на определённый счёт S всю выручку.
P2 перебивает процесс P1 и выполняет то же действие, при этом считывает старое значение S, далее квант получает первый процесс, но он уже сложил B1 и S, таким образом потеряна составляющая второго филиала.
Рассмотрим уровни наблюдения.
1. Последовательное выполнение.
От начала до конца выполняется процесс P1, потом от начала до конца выполняется процесс P2.
2. Квазипараллельное выполнение.
Квант времени выполняются команды процесса P1, потом происходит переключение и квант времени выполняются команды процесса P2. В общем то последовательное выполнение, но с точки зрения наблюдателя - параллельное. Такое выполнение называется квазипараллельным.
3. Реально параллельное выполнение.
Совпадение по времени выполнения команд процесса P1 и команд процесса P2.
Рассмотрим два варианта (квазипараллельное и реально параллельное выполнение):
Оба процесса выполняют одну и ту же последовательность команд.
P1: | P2:
mov eax, myvar | mov eax, myvar
inc eax | inc eax
mov myvar, eax | mov myvar, eax
Наши компьютеры имеют SMP-архитектуру (многоядерная архитектура, где каждое ядро это процессор со своими регистрами, в каждом ядре полный набор регистров)
Понятно что каждый процессор будет иметь свой регистр EAX. Все процессоры работают с одной памятью.
В начальный момент значение переменной myvar = 0, затем инициативу перехватывает первый процесс и выполняет "mov eax, myvar", соответственно в eax попадает 0. Далее расписывать не буду по картинке всё видно.
Мы потеряли данные.
Рассмотрим эту же ситуацию для однопроцессорной машины (Для двух потоков).
Здесь не может быть двух регистров eax, он один.
Ситуация повторилась, несмотря на то что это квазипараллельность, но мы видим что переключение связано с переключением контекста, с запоминанием содержимого регистров, соответсвенно мы получили тот же самый результат.
Подобные действия принято называть критическими.
Часть кода в котором выполняются такие действия принято называть критической секцией.
Myvar - разделяемая переменная.
Что же делать чтоб не терять данные? Для этого необходимо обеспечить монопольное использование разделяемых параллельными процессами ресурсов.
Т.е. каждый процесс должен владеть разделяемым ресурсом монопольно.
Монопольный доступ к разделяемому ресурсу обеспечивается методами взаимоисключения. Т.е. если один процесс находится в своей критической секции по некоторой переменной, то другой процесс не может войти в эту критическую секции по той же переменной до тех пор пока первый процесс не освободит её.
Существует ряд способов реализации взаимоисключения:
- Программный.
- Аппаратный.
- С использованием семафоров.
- С использованием мониторов.
В этой лекции рассмотрен только программный способ.
Рассмотрим классическое предложение - использование флага (неверное).
P1: | P2: | // Объявления и начальные установки
while(1) | while(1) | flagP1, flagP2: logical;
begin | begin | flagP1 = 0;
while(flagP2); // цикл активного ожидания | while(flagP1); | flagP2 = 0;
flagP1 = 1; | flagP2 = 1; | parbegin
CR1; // критическая секция | CR2; // критическая секция | P1; P2;
flagP1 = 0; | flagP2 = 0; | parend;
PR1; | PR2; |
end; | end; |
Наблюдаем потерю значения, т.к. while не проверяет второй раз условие.
Давайте поменяем последовательность действий, прежде чем проверять флаг другого процесса, сразу устанавливать свой флаг. (Спасибо конечно, но опять неправильно будет)
P1: | P2: | // Объявления и начальные установки
while(1) | while(1) | flagP1, flagP2: logical;
begin | begin | flagP1 = 0;
flagP1 = 1; | flagP2 = 1; | flagP2 = 0;
while(flagP2); // цикл активного ожидания | while(flagP1); | parbegin
CR1; // критическая секция | CR2; // критическая секция | P1; P2;
flagP1 = 0; | flagP2 = 0; | parend;
PR1; | PR2; |
end; | end; |
Оба процесса будут в цикле активного ожидания, тратя на это процессорное время. Ни один из процессов не сможет продолжить своё выполнение, они находятся в тупике (deadlock). Это классический пример тупиковой ситуации.
В системе 3 негативные ситуации:
- Бесконечное откладывание.
- Тупиковая ситуация.
- Захват и освобождение одних и тех же ресурсов.
Примером такой ситуации является trashing (когда процесс не может загрузить в память всё своё рабочее множество и в силу этого постоянно выгружаются и загружаются снова одни и те же страницы).
Алгоритм Декера.
Декер предложил решение чисто программным способом, алгоритм исключает те негативные ситуации которые мы рассмотрели, является надёжным, исключает попадание процессов в тупик, исключает бесконечное откладывание.
Но данную задачу Декер решил только для двух параллельных процессов.
Для того чтобы решить эту проблему Декер ввёл третью переменную, которую назвал "чья очередь", мы назовём "que".
P1: |P2: | // Объявления и начальные установки
while(1) | while(1) | flagP1, flagP2: logical;
begin | begin | que:int;
flagP1 = 1; | flagP2 = 1; | flagP1 = 0; flagP2 = 0;
while(flagP2); | while(flagP1); | que = 1;
begin | begin | parbegin
if (que == 2) then | if (que == 1) then | P1; P2;
begin | begin | parend;
flagP1 = 0; | flagP2 = 0; |
while(que == 2); | while(que == 1); |
flagP1 = 1; | flagP2 = 1; |
end; | end; |
end; | end; |
CR1; | CR2; |
flagP1 = 0; | flagP2 = 0; |
que = 2; | que = 1; |
PR1; | PR2; |
end; | end; |
Здесь мы видим следующее решение - введена дополнительная переменная "que", при этом мы видим что прежде чем войти в цикл проверки другого процесса, процесс устанавливает свой флаг. Если флаг другого процесса установлен то процесс проверяет переменную "que". Если очередь другого процесса, то процесс сбрасывает свой флаг и переходит в цикл активного ожидания по переменной "que". Выйдя из этого цикла, процесс устанавливает свой флаг и входит в свой критический участок. Выйдя из критического участка, процесс сбрасывает свой флаг и устанавливает, что следующим в критическую секцию войдёт другой процесс.
Как мы видим такое решение избавляет от deadlock-а, и поскольку процесс передаёт активность другому процессу, то исключается бесконечное откладывание.
К чисто программному решению относится так же известнейший алгоритм Лампорта (Lamport), который получил название "Булочная" ("Bakery").
Есть классическое изложение алгоритма Лампорта которое было предложено в статье "A new Solution of Dijkstra's concurrent programming problem".
Этот алгоритм решает проблему критической секции для n прикладных процессов.
Основная идея взята из работы булочной.
Потребители берут номера (устанавливается очередь), тот кто имеет наименьший номер обслуживается следующим (вхождение в критическую секцию).
Алгоритм прост и основан на методе, обычно используемом в булочных, где покупатель получает номер при входе, следующим обслуживается обладатель наименьшего номера, при этом может возникнуть такая ситуация, когда два покупателя одновременно входят в дверь. В этом случае они получают одинаковые номера, но первым будет обслужен покупать у которого меньший номер паспорта.
С точки зрения процессов: Если два процесса входят в так называемую дверь, то они получают одинаковые номера, но затем при обслуживании будет учитываться, например, идентификатор процесса. Т.е. возникает необходимость дополнительных данных.
Записывается алгоритм следующим образом:
1. var choosing: shared array[0: n - 1] of boolean;
2. number: shared array[0: n - 1] of integer;
3. repeat
4. choosing[i] := true;
5. number[i] := max(number[0], ..., number[n - 1]) + 1;
6. choosing[i] := false;
7. for j := 0 to n - 1 do begin
8. while choosing[j] do (*nothing*);
9. while number[j] <> 0 and (number[j], j) < (number[i], i) do (*nothing*);
10. end;
11. critical section;
12. number[i] = 0;
13. (*remaining section*);
14. until false;
// 1-2: Объявляются два массива.
// choosing[i] будет true если процесс Pi выбирает номер.
// Этот номер будет использоваться процессом для входа в критическую секцию.
// Если номер = 0, то процесс не пытается войти в критическую секцию.
// 4-6: Процесс выбирает номер (максимальный из выданных + 1)
// 7-12: Осуществляется выбор процесса, который входит в критический участок.
// Процесс P[i] ждёт, пока не отработают все процессы с меньшим номером. Если два
// процесса имеют один номер, используется лексиграфический порядок.