Главная
страница 1

“Системное программное обеспечение”


Лекционный курс в 6-7 семестрах для специальности 510200

Лекция 5



Глава 5. Синхронизация параллельных процессов на низком


уровне



  1. Параллельная обработка. Проблемы критических участков. Взаимоисключения.
  2. Синхронизация параллельных процессов на низком уровне.

Блокировка памяти. Алгоритм Деккера. Аппаратная реализация взаимоисключения: команда “проверка и установка” (testandset).


Литература


  • [Дейтел 87] Дейтел Г., Введение в операционные системы. М."Мир",1987.

  • [Кейлингерт 85] Кейлингерт П., Элементы операционных систем, М."Мир", 1985.

  • [Кейслер 86] Кейслер С., Проектирование операционных систем для малых ЭВМ, М."Мир", 1986.

  • [Колин 75] Колин А., Введение в операционные системы, М."Мир", 1975.

  • [Цикритзис 77] Цикритзис Д., Бернстайн Ф., Операционные системы, М."Мир", 1977.


Параллельная обработка


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

Если определенные операции логически можно выполнять параллельно, то для указания параллелизма воспользуемся парой операторов parbegin/parend, которые будут, соответственно, определять начало и конец параллельного выполнения, как рекомендует Дейкстра1. Конструкция для указания параллелизма будет выглядеть следующим образом:



Parbegin

оператор_1;

оператор_2;



оператор_n

Parend
В качестве примера рассмотрим вычисление площади треугольника по формуле Герона в системе, предусматривающей параллельную обработку:




S=p*(p-a)*(p-b)*(p-c), где p=(a+b+c)/2
1 p:=(a+b+c)/2;

2 Parbegin

x1:=p-a;

x2:=p-b;

x3:=p-c

Parend;

3 S:=Sqrt(p*x1*x2*x3);

Здесь три операции, входящие в конструкцию Parbegin/Parend выполняются параллельно, что дает возможность уменьшить реальное время решения задачи.



Проблемы критических участков. Взаимоисключения


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

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

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

Пример.

Пусть два процесса X и Y разделяют переменную СЧЕТ. Если оба процесса попытаются увеличить СЧЕТ на 1 одновременно, то окончательное значение этой переменной может оказаться неверным. Рассмотрим следующую последовательность событий:


  • процесс X запоминает значение переменной СЧЕТ в некоторой локальной переменной СЧЕТ_Х;

  • процесс Y запоминает значение переменной СЧЕТ в некоторой локальной переменной СЧЕТ_Y;

  • процесс Х увеличивает значение СЧЕТ_Х на 1 и записывает его в СЧЕТ;

  • процесс Y увеличивает значение СЧЕТ_Y на 1 и записывает его в СЧЕТ.

Заметим, что хотя каждый процесс увеличил значение СЧЕТ на 1, ее окончательное значение увеличилось только на 1, а не на 2. Чтобы избежать таких нежелательных явлений, увеличение разделяемой переменной СЧЕТ следует рассматривать как критический участок.

Рассмотрим несколько решений проблем синхронизации критических участков.


Синхронизация параллельных процессов на низком уровне


Большинство приемов, применяемых для синхронизации процессов, тесно связаны с аппаратными средствами. Это блокировка памяти, операция “проверка и установка” и семафоры.
Блокировка памяти

Взаимоисключения могут быть реализованы аппаратно, если сделать операции над памятью неделимыми. То есть, если каждый из процессов пытается поместить какие-либо значения в одну и ту же ячейку, то спор разрешается аппаратурой: если одному процессу разрешается выполнить операцию засылки немедленно, то другому приходится ждать пока первый не закончит операцию - такое разрешение спора и называется блокировкой памяти( storage interlock).

Попытаемся решить проблему критического участка для двух процессов X и Y с помощью некоторой переменной КЛЮЧ, которая будет принимать значение true, когда процесс находится в своем критическом участке, и значение false - в противном случае. Прежде, чем войти в критический участок, процесс X проверяет КЛЮЧ_Y другого процесса, чтобюы убедится, что можно войти безопасно. Затем он включает свой собственный КЛЮЧ_X и пользуется критическим участком.



var КЛЮЧ_Х, КЛЮЧ_Y : boolean;

procedure Процесс_Х;

begin

while (true) do

begin

while (КЛЮЧ_Y) do;{ожидание, пока процесс Y не выйдет из критического участки}

КЛЮЧ_X:=true;

{Критический участок Х}


КЛЮЧ_Х:=false;{признак выхода процесса X из критического участка}
{Оставшаяся часть процесса Х}

end;

end;
procedure Процесс_Y;

begin

while (true) do

begin

while (КЛЮЧ_X) do;{ожидание пока процесс X не выйдет из критического участка}

КЛЮЧ_Y:=true;

{Критический участок Y}

КЛЮЧ_Y:=false;{признак выхода процесса Y из критического участка}

{Оставшаяся часть процесса Y}

end;

end;

begin

КЛЮЧ_X:=false;

КЛЮЧ_Y:=false;

Parbegin

Процесс_Х;

Процесс_Y

Parend

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

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


Рассмотреть этот вариант самостоятельно.

Если процесс Y заканчивает выполнение своего критического участка и устанавливает в переключателе КЛЮЧ_Y значение false,,тем самым допускает процесс Х к выполнению своего критического участка. Пусть процесс Y работает значительно быстрее процесса Х, настолько, что прежде чем процесс Х установит свой КЛЮЧ_Х в состояние true, свидетельствующее о входе этого процесса в критический участок, процесс Y уже выполнит оставшуюся часть процесса и, не обнаружив в переменной КЛЮЧ_Х значения true, также получает доступ к критическому участку. Таким образом предложенный алгоритм полностью не решает проблему критического участка.
Алгоритм Деккера (Dekker’s Algorithm)

Изящную программную реализацию механизма взаимоисключения предложил голландский математик Деккер (кроме того решению этой проблемы посвящены следующие статьи, где этот алгоритм был обобщен и для случая произвольного числа конкурирующих из-за критического ресурса процессов2 ).

var C1,C2,ОЧЕРЕДЬ:integer;

procedure Процесс_Х;

begin

C1:=1;

while (C2=1) do

begin

if ОЧЕРЕДЬ=2 then

begin

C1:=0;

while (ОЧЕРЕДЬ=2) do;

C1:=1;

end;

end;

{Критический участок процесса Х}

C1:=0;

ОЧЕРЕДЬ:=2;

{Оставшаяся часть процесса Х}

end;

procedure Процесс_Y;

begin

C2:=1;

while (C1=1) do

begin

if ОЧЕРЕДЬ=1 then

begin

C2:=0;

while (ОЧЕРЕДЬ=1) do;

C2:=1

end;

end;

{Критический участок процесса Y}

C2:=0;

ОЧЕРЕДЬ:=1;

{Оставшаяся часть процесса Y}

end;
Begin

C1:=0;

C2:=0;

ОЧЕРЕДЬ:=1;

Parbegin

Процесс_X;

Процесс_Y

Parend

end.
В этом решении С1=1, когда ПРОЦЕСС_Х хочет войти в свой критический участок. С2=1, когда ПРОЦЕСС_Y хочет войти в свой критический участок, а переменная ОЧЕРЕДЬ указывает, чья очередь попытаться войти, при условии, когда оба процесса хотят выполнить свои критические участки.

Самостоятельно проверить этот алгоритм с различными относительными скоростями процессов.

Аппаратная реализация взаимоисключения: команда “проверка и установка” (testandset)

Алгоритм Деккера представляет собой программное решение проблемы взаимоисключения. Рассмотрим вариант аппаратного решения данной проблемы. Наличие аппаратной команды testandset, которая осуществляет чтение переменной; запись ее значения в область сохранения и установку конкретного значения этой переменной, причем выполняет эти действия до конца без прерывания, значительно упрощает решение проблемы критического участка посредством блокировки памяти.


Рассмотрим выполнение команды testandset с параметрами ОБЩИЙ и ЛОКАЛЬНЫЙ. Операция читает значение параметра ОБЩИЙ и присваивает его переменной ЛОКАЛЬНЫЙ, а затем устанавливает в переменной ОБЩИЙ значение 1.

Переменная ОБЩИЙ разделяется между процессами, которые подлежат синхронизации по отношению к некоторому критическому ресурсу. У каждого процесса есть своя собственная переменная ЛОКАЛЬНЫЙ_Х и ЛОКАЛЬНЫЙ_Y.

Рассмотрим решение проблемы взаимоисключения с помощью операции testandset.
var ОБЩИЙ: integer;

procedure Процесс_Х;

var ЛОКАЛЬНЫЙ_Х: integer;

begin

while (true) do

begin

ЛОКАЛЬНЫЙ_Х:=1;

while (ЛОКАЛЬНЫЙ_X=1) do

testandset(ЛОКАЛЬНЫЙ_Х, ОБЩИЙ);

{Критический участок процесса Х}

ОБЩИЙ:=0;

{Оставшаяся часть процесса Х}

end;

end;


procedure Процесс_Y;

var ЛОКАЛЬНЫЙ_Y: integer;

begin

while (true) do

begin

ЛОКАЛЬНЫЙ_Y:=1;

while (ЛОКАЛЬНЫЙ_Y=1) do

testandset(ЛОКАЛЬНЫЙ_Y, ОБЩИЙ);

{Критический участок процесса Y}

ОБЩИЙ:=0;

{Оставшаяся часть процесса Y}

end;
end;

begin

ОБЩИЙ:=0;

Parbegin

Процесс_Х;

Процесс_Y

Parend;

end.

Вопросы


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

Parbegin/Parend для обеспечения максимального параллелизма
3*a*b + 4/(c + d) ** (e-f);

(-b + (b ** 2 - 4 *a*c) **0.5) / (2*a).


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



  1. Проведите исчерпывающий временной анализ алгоритма Деккера.




  1. Объясните, как при помощи запрещения и разрешения прерываний можно достаточно эффективно реализовать примитивы взаимоисключения в однопроцессорной машине.




1 Dijkstra E.W. Cooperating Sequential Processes. Technological University, Eindhoven, Nitherlands,1965.

Эдсгер Дейкстра лауреат премии Тьюринга 1972 года. С 1984 года зав.кафедрой информатики в Университете штата Техас в Остине.



2 [Дейкстра-65] Dijkstra E.W. Solution to a Problem in Concurrent Programming Control, CACM, 8, No.9, 1965,c.569.

[Кнут-66] Knuth D. Additional Comments on a Problem in Concurrent Programming Control, CACM, 9,



No 5, 1966, c.321-322.



Смотрите также:
Лекция 5 Глава Синхронизация параллельных процессов на низком уровне
86.89kb.
1 стр.
Понятие и структура ос. Эволюция вычислительных и ос. Основные функции ос
765.68kb.
5 стр.
Министерство здравоохранения
68.1kb.
1 стр.
Книга Иисуса Навина 1 Глава 1 1 Глава 2 2 Глава 3 3 Глава 4 4 Глава 5 5 Глава 6 5 Глава 7 7 Глава 8 8
525.38kb.
10 стр.
Денежная система и денежный рынок
244.11kb.
1 стр.
Краткое содержание Глава Элементы пользовательского интерфейса 289 Глава Быстродействие и оптимизация 306
6132.18kb.
21 стр.
О. К. Тихомиров
11.24kb.
1 стр.
Книга Притчи Соломона 1 Глава 1 2 Глава 2 2 Глава 3 3 Глава 4 4 Глава 5 5 Глава 6 5 Глава 7 6 Глава 8 7
474.69kb.
9 стр.
Состояние запасов рыб Рыбинского водохранилища в 2012 г
190.49kb.
1 стр.
Лекция №1 2 Лекция №2 8 Лекция №3. 13 Лекция №4 14 Лекция №24 Лекция №7 24 Конспект лекций по курсу
316.67kb.
1 стр.
Если хочешь быть здоров – закаляйся! Закаливание
26.16kb.
1 стр.
Магистерские программы
18.28kb.
1 стр.