В.А. Крюков - Операционные системы распределенных вычислительных систем, страница 2

Если не обеспечено взаимноеисключение критических интервалов, то недетерминизм, race condition (условия гонок).Процесс p1 выполняет оператор X = X+1,а процесс p2 - оператор X = X-1машинные коды выглядят так:Load R1,XLoad R1,XAdd R1,=”1”Sub R1, =”1”Store R1,XStore R1,XРезультат зависит от порядка выполнения этих команд.5Требуется взаимное исключение критических интервалов.Решение проблемы взаимного исключения должно удовлетворять требованиям:в любой момент времени только один процесс может находиться внутри критическогоинтервала;если ни один процесс не находится в критическом интервале, то любой процесс, желающийвойти в критический интервал, должен получить разрешение без какой либо задержки;ни один процесс не должен бесконечно долго ждать разрешения на вход в критическийинтервал (если ни один процесс не будет находиться внутри критического интервалабесконечно долго);не должно существовать никаких предположений о скоростях процессоров.Взаимное исключение критических интервалов в однопроцессорной ЭВМ.1.

Блокировка внешних прерываний (может нарушаться управление внешнимиустройствами, возможны внутренние прерывания при работе с виртуальной памятью).2. Блокировка переключения на другие процессы (MONO, MULTI).Взаимное исключение критических интервалов в многопроцессорной ЭВМ.Программные решения на основе неделимости операций записи и чтения из памяти (причтении переменной всегда читаем последнее присвоенное ей значение) .Алгоритм Деккера (1968).Два процесса (нити) с номерами i=0 и i=1интервал и выходят из него.int turn;boolean flag[2 ];proc( int i )в цикле регулярно входят в критический{while (TRUE){<вычисления>;enter_region( i );<критический интервал>;leave_region( i );}}void enter_region( int i ){try: flag[ i ]=TRUE;while (flag [( i+1 ) % 2]){if ( turn = = i ) continue;flag[ i ] = FALSE;while ( turn != i );goto try;}}6void leave_region( int i ){turn = ( i +1 ) % 2;flag[ i ] = FALSE;}turn = 0;flag[ 0 ] = FALSE;flag[ 1 ] = FALSE;proc( 0 ) AND proc( 1 ) /* запустили 2 процесса */Алгоритм Петерсона (1981)int turn;int flag[ 2 ];void enter_region( int i ){int other;/* номер другого процесса */other = 1 - i;flag[ i ] = TRUE;turn = i;while (turn = = i && flag[ other ] = = TRUE) /* пустой оператор */;}void leave_region( int i ){flag[ i ] = FALSE;}Использование неделимой операции TEST_and_SET_LOCK.Операция TSL(r,s):[r = s; s = 1]Квадратные скобки - используются для спецификации неделимости операций.enter_region:tsl reg, flagcmp reg, #0/* сравниваем с нулем */jnz enter_region/* если не нуль - повторяем попытку */retleave_region:mov flag, #0 /* присваиваем нуль*/retНедостатки такого "активного ожидания" при использовании команды TSL или алгоритмовДеккера или Петерсона - бесполезная трата времени, нагрузка на общую память, ивозможность фактически заблокировать работу процесса, находящегося в критическоминтервале.

Избежать активного ожидания помогают семафоры.7Семафоры Дейкстры (1965).Семафор - неотрицательная целая переменная, которая может изменяться и проверятьсятолько посредством двух функций:Функция запроса семафора P(s):[if (s == 0) <заблокировать текущий процесс>; else s = s-1;]Замечание. Неделимость этой операции означает, что после разблокирования процесса онначнет ее выполнять заново.Функция освобождения семафора V(s):[if (s == 0) <разблокировать один из заблокированных процессов>;s = s+1;]Двоичные семафоры как частный случай общих (считающих).Использование семафоров для взаимного исключения критических интервалов и длякоординации в задаче производитель-потребитель.Задача производитель-потребитель (поставщик-потребитель, проблема ограниченногобуфера).semaphore s = 1;semaphore full = 0;semaphore empty = N;¦ consumer()¦ {¦int item;¦int item;while (TRUE)¦while (TRUE){¦{produce_item(&item);¦P(empty);¦P(full);P(s);¦P(s);enter_item(item);¦remove_item(&item);V(s);¦V(s);V(full);¦V(empty);¦consume_item(item);}¦}}¦ }¦producer() AND consumer() /* запустили 2 процесса */producer(){Реализация семафоров.Мультипрограммный режим.блокировка внешних прерываний;запрет переключения на другие процессы;переменная и очереди ожидающих процессов в ОС.Для многопроцессорной ЭВМ первые два способа не годятся.

Для реализации третьегоспособа достаточно команды TSL и возможности объявлять прерывание указанномупроцессору (чтобы сообщить другим процессорам, что разблокирован один из процессов).8Блокирование процесса и переключение на другой - не эффективно, если семафорзахватывается на очень короткое время. Можно ввести специальные семафоры, которыезахватываются на короткое время. Ожидание освобождения таких семафоров может бытьреализовано в ОС посредством циклического опроса значения семафора.**********Лекция 4Если произведенный объект используется многими, то семафоры не годятся.События.Это переменные, показывающие, что произошли определенные события.Для объявления события служит оператор POST(имя переменной), для ожидания события WAIT (имя переменной).

Для чистки (присваивания нулевого значения) - операторCLEAR(имя переменной).Варианты реализации не хранящие информацию (по оператору POST из ожиданиявыводятся только те процессы, которые уже выдали WAIT), однократно объявляемые (нетоператора чистки).Метод последовательной верхней релаксации (SOR) с использованием массива событий. Внем для вычисления элемента матрицы A[i][j] требуется предварительно вычислитьэлементы A[i-1][j] и A[i][j-1].

Нулевая строка и нулевой столбец матрицы заданыизначально и не вычисляются. Заголовок цикла parfor означает, что витки цикла можновыполнять параллельно.float A[ L1 ][ L2 ];struct event s[ L1 ][ L2 ];for ( i = 0; i < L1; i++)for ( j = 0; j < L2; j++) { clear( s[ i ][ j ]) };for ( j = 0; j < L2; j++) { post( s[ 0 ][ j ]) };for ( i = 0; i < L1; i++) { post( s[ i ][ 0 ]) };............................parfor ( i = 1; i < L1-1; i++)parfor ( j = 1; j < L2-1; j++){ wait( s[ i-1 ][ j ]);wait( s[ i ][ j-1 ]);A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1][ j ] + A[ i ][ j-1 ] + A[ i ][ j+1 ]) / 4;post( s[ i ][ j ]);}9Обмен сообщениями (message passing)Хоар (Xoare) 1978 год, "Взаимодействующие последовательные процессы". Цели - избавитьсяот проблем разделения памяти и предложить модель взаимодействия процессов дляраспределенных систем.send (destination, &message, msize);receive ([source], &message, msize);Адресат - процесс.

Отправитель - может не специфицироваться (любой).С буферизацией (почтовые ящики) или нет (рандеву - Ада, Оккам).Пайпы ОС UNIX - почтовые ящики, заменяют файлы и не хранят границы сообщений (всесообщения объединяются в одно большое, которое можно читать произвольными порциями).Пример использования буферизуемых сообщений.#define N 100/* максимальное число сообщений *//* в буфере*/#define msize 4/* размер сообщения*/typedef int message[msize];producer(){message m;int item;while (TRUE){produce_item(&item);receive(consumer, &m, msize);build_message(&m, item);send(consumer, &m, msize);/* получает пустой *//* "контейнер" *//* формирует сообщение */}}consumer(){message m;int item, i;for (i = 0; i < N; i ++)send (producer, &m, msize); /* посылает все пустые *./* "контейнеры" */while (TRUE){receive(producer, &m, msize);extract_item(&m, item);send(producer, &m, msize); /* возвращает "контейнер" */consume_item(item);}}producer() AND consumer() /* запустили 2 процесса */10Механизмы семафоров и обмена сообщениями взаимозаменяемы семантически и намультипроцессорах могут быть реализованы один через другой.

Другие классические задачивзаимодействия процессов – “проблема обедающих философов” и “читатели-писатели”.2.3Планирование процессоровПланирование процессоровоченьсильновлияетна производительностьмультипроцессорнойсистемы.Можновыделить следующие главные причиныдеградации производительности:1) Накладные расходы на переключение процессора. Они определяются не толькопереключениями контекстов процессов, но и (при переключении на процессы другогоприложения)перемещениями страниц виртуальной памяти, а также порчей кэша(информация в кэше другому приложению не нужна и будет заменена).2) Переключение на другой процесс в тот момент, когда текущий процесс выполнялкритическую секцию, а другие процессы активно ожидают входа в критическую секцию.В этом случае потери будут велики (хотя вероятность прерывания выполнениякоротких критических секций мала).Применяются следующие стратегии борьбы с деградацией производительности.1) Совместное планирование, при котором все процессы одного приложения(неблокированные)одновременновыбираются на процессоры и одновременноснимаются с них (для сокращения переключений контекста).2) Планирование, при котором находящиеся в критической секции процессы непрерываются, а активно ожидающие входа в критическую секцию процессы невыбираются до тех пор, пока вход в секцию не освободится.3) Процессы планируются на те процессоры, на которых они выполнялись в момент ихснятия (для борьбы с порчей кэша).

При этом может нарушаться балансировка загрузкипроцессоров.4) Планирование с учетом "советов" программы (во время ее выполнения). В ОС Machимеется два класса таких советов (hints) - указания (разной степени категоричности) оснятии текущего процесса с процессора, а также указания о том процессе, которыйдолжен быть выбран взамен текущего.11Лекция 53 Коммуникации в распределенных системахВсе компьютеры в распределенной системе связаны между собой коммуникационнойсетью.