Тема OS19асу. Средства коммуникации процессов. InterProcess Communications (IPC) - Межпроцессные взаимодействия. Основные классы комммуникации (передачи данных) процессов - объекты и механизмы синхронизации (сигналы, мьютексы, семафоры, ...); - разделяемая оперативная память (разделяемые сегменты, отображаемые файлы в ОП, конвееры, системные буферы Windows, каналы Unix/Linux, и др.); - разделяемая внешняя память (общие файлы, виртуальные диски, файлы реестра); - сообщения (широковещательные или адресуемые). - распределенные средства в глобальных и локальных сетях (Например, UDDI в SOA). Операционная система имеет набор средств, поддерживающих взаимодействие процессов. Одно из таких средств - Система Межпроцессного Взаимодействия IPC (InterProcess Communications). Суть этой системы заключается в следующем. Имеется некоторое количество ресурсов, которые называются в системе разделяемыми. К одному и тому же разделяемому ресурсу может быть организован доступ со стороны произвольного количества произвольных процессов. При этом возникает проблема именования этих разделяемых ресурсов. Если мы вспомним неименованные каналы, за счет того, что каналы передавались по родственному наследованию, всегда в процессе были известны дескрипторы, ассоциированные с каналом. Фактически, если процесс получал доступ к каналу, он уже знал, как именовать этот канал. Здесь использовалось свойство родственной связи, когда какая-то информация, какие-то средства передаются по наследству при формировании сыновьего процесса. В системе IPC ситуация другая. Есть некоторый ресурс, в общем случае произвольный, и к этому ресурсу могут добираться все, кто может именовать этот ресурс. Для именования такого рода ресурсов в системе предусмотрен механизм генерации т.н. ключей. Суть его заключается в следующем. По некоторым общеизвестным данным (это могут быть текстовые строки или цифровые комбинации) в системе генерируется уникальный ключ, который ассоциируется с разделяемым ресурсом. Если процесс подтверждает этот ключ и созданный разделяемый ресурс доступен для него, то после этого он может работать с указанным разделяемым ресурсом по своему усмотрению. Разделяемый ресурс создается некоторым процессом-автором. Автор определяет основные свойства ресурса (предположим, размер) и права доступа. Права доступа к ресурсу разделяются на три категории: 1. Права доступа самого автора. 2. Права доступ всех процессов, имеющих тот же идентификатор что и автор. 3. Права доступа остальных. Итак, система позволяет некоторому процессу создать разделяемый ресурс, защитить его некоторым ключом и забыть о его существовании. После этого все те, кто знают ключ, который открывает этот ресурс, могут работать с содержимым этого ресурса. Возникают проблемы синхронизации доступа к разделяемому ресурсу. Решение этих проблем и другие концептуальные возможности предоставляет система IPC. Система IPC поддерживает три разновидности разделяемых ресурсов: 1. Разделяемая память. Концептуально - это возможность нескольких процессов иметь общее поле оперативной памяти, и соответственно работать с этим полем, как с неким массивом, на который имеется указатель. Проблема синхронизации здесь стоит особенно остро, но базово средства работы с разделяемой памяти никакой синхронизации не предполагают. 2. Механизм передачи сообщений. Разделяемым ресурсом здесь является очередь сообщений. Эта очередь может содержать произвольное количество (в пределах разумного) сообщений разной длины и разного типа. Тип сообщения - это некоторый атрибут сообщения. Очередь сообщений может рассматриваться как единая очередь всех сообщений в хронологическом порядке, и как множество очередей, содержащих сообщения определенного типа, где в каждой очереди также есть хронологический порядок. Здесь также возникают проблемы синхронизации. 3. Семафоры. Семафоры - это нечто, что позволяет синхронизовать доступ к разделяемым ресурсам. Координация процессов Сообщения точка-точка (если известно, кто потребитель). Если неизвестно, кто потребитель, то: сообщения широковещательные; сообщения в ответ на запрос. Если неизвестно, кто потребляет и кто производит, то: сообщения и запросы через координатора: широковещательный запрос. Сигналы (UNIX) - программный механизм, информирующий процесс о наступлении асинхронного события, обеспечивает логическую связь между процессами, а также между процессами и пользователями. Сигналы подобны аппаратному прерыванию, но не использует систему приотритетов и все сигналы обрабатываются одинаково, различаясь по типу сигнала. Процессы могут посылать сигналы друг другу определенных типов. В обмене сигналами может принять участие и ядро ОС (перехват сигналов для трассировки и журналирования). Процесс может ответить на сигнал выполнением некоторых предопределенных действий (по умолчанию), либо выполнить определенную программистом функцию или проигнорировать сигнал. Доставка сигнала выполняется обновлением полей в таблице процесса, которому послан данный сигнал. Каждому типу сигнала соответствует поле в единственный бит, поэтому они не могут накапливаться. Примеры сигналов - нажатие клавиш клавиатуры или мыши (передать данные процессу), Ctrl-C/Ctrl-Break(завершить процесс), Ctrl-Alt-Del(перезагрузка ОС). Сообщения (UNIX) - блок текста определенного типа. Для передачи сообщений имеются системные вызовы msgsnd/msgrcv и очереди сообщений для каждого процесса, функционирующих по метафоре почтовых ящиков. Единственный механизм для диспетчеризации и синхронизации в распределенных системах. Каналы (pipes, UNIX) - канальная связь, использование поименованных каналов - очереди или циклические буферы для связи процессов, действующие по метафоре производитель/потребитель (первый вошел - первый вышел) и которым ОС обеспечивает взаимоисключения - одновременно к каналу имеет доступ только единственный процесс, остальные обращения блокируются. Разделяемая память (UNIX) - общий сегмент виртуальной памяти процессов с правами доступа (на чтение и запись) для каждого процесса в отдельности при отсутствии взаимоисключения. http://cad.narod.ru/methods/os_unix/unibas/ipc.html http://www.opennet.ru/soft/proc/2.html Под коммуникацией процессов в OS UNIX понимается реализация обмена данными между параллельно выполняющимися процессами. Наиболее очевидным способом такого взаимодействия процессов является обмен данными через файл, когда два или более процессов записывают данные в некоторый файл, выбранный по договоренности, другие процессы читают данные из этого файла. Для коммуникации процессов через файл характерны следующие проблемы. Ограничения по объему файла обмена. Ограничение прав доступа к файлу обмена. Отсутствие синхронизации при обмене. Возможность искажения или потери данных через в файле независимо от процессов, которые используют его для обмена. Время существования файла обмена не зависит от времени жизни использующих его процессов, поэтому данные в файле продолжают сохраняться и тогда, когда их никто не использует. Всилу необходимости решения указанных проблем, коммуникация процессов через файл применяется редко. С другой стороны, OS UNIX предоставляет более совершенные средства межпроцессной коммуникации, обычно именуемые IPC (Inter Process Communication). Средства IPC свободны от указанных выше недостатков межпроцессного обмена через файл. Традиционно, к средствам IPC в OS UNIX относятся: именованные и неименованные (обычные) программные каналы, разделяемая память, семафоры, очереди сообщений. Организация ОС: главный-подчиненный (master-slave, выделение одного процессора для ОС упрощает ее, но этот процессор становится узким местом с точки зрения загруженности и надежности); симметричная (наиболее эффективная и сложная). 2.1 Процессы и нити Процесс - это выполнение программы. Компоненты процесса - выполняющаяся программа, ее данные, ее ресурсы (например, память), и состояние выполнения. Процесс имеет собственное адресное пространство и его состояние характеризуется следующей информацией: " таблицы страниц (или сегментов); " дескрипторы файлов; " заказы на ввод-вывод; " регистры; " и т.п. Большой объем этой информации делает дорогими операции создания процессов, их переключение. Потребность в легковесных процессах, нитях (threads) возникла еще на однопроцессорных ЭВМ (физические процессы или их моделирование, совмещение обменов и счета), но для использования достоинств многопроцессорных ЭВМ с общей памятью они просто необходимы. Процессы могут быть независимыми, которые не требуют какой-либо синхронизации и обмена информацией (но могут конкурировать за ресурсы), либо взаимодействующими. 2.2. Взаимодействие процессов Если приложение реализовано в виде множества процессов (или нитей), то эти процессы (нити) могут взаимодействовать двумя основными способами: " посредством разделения памяти (оперативной или внешней) " посредством передачи сообщений При взаимодействии через общую память процессы должны синхронизовать свое выполнение. Различают два вида синхронизации - взаимное исключение критических интервалов и координация процессов. Критические секции. Недетерминизм, race condition (условия гонок). Процесс p1 выполняет оператор I = I+J, а процесс p2 - оператор I = I-K машинные коды выглядят так: Load R1,I Load R1,I Load R2,J Load R2,K Add R1,R2 Sub R1,R2 Store R1,I Store R1,I Результат зависит от порядка выполнения этих команд. Требуется взаимное исключение критических интервалов. Решение проблемы взаимного исключения должно удовлетворять требованиям: " в любой момент времени только один процесс может находиться внутри критического интервала; " если ни один процесс не находится в критическом интервале, то любой процесс, желающий войти в критический интервал, должен получить разрешение без какой либо задержки; " ни один процесс не должен бесконечно долго ждать разрешения на вход в критический интервал (если ни один процесс не будет находиться внутри критического интервала бесконечно долго); " не должно существовать никаких предположений о скоростях процессоров. Взаимное исключение критических интервалов в однопроцессорной ЭВМ. 1. Блокировка внешних прерываний (может нарушаться управление внешними устройствами, возможны внутренние прерывания при работе с виртуальной памятью). 2. Блокировка переключения на другие процессы (MONO, MULTI). Взаимное исключение критических интервалов в многопроцессорной ЭВМ. Программные решения на основе неделимости операций записи и чтения из памяти. Алгоритм Деккера (1968). 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; } } void 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, flag cmp reg, #0 /* сравниваем с нулем */ jnz enter_region /* если не нуль - цикл ожидания */ ret leave_region: mov flag, #0 /* присваиваем нуль*/ ret Семафоры Дейкстры (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; producer() ¦ 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 процесса */ Реализация семафоров. Мультипрограммный режим. " блокировка внешних прерываний; " запрет переключения на другие процессы; " переменная и очереди ожидающих процессов в ОС. Для многопроцессорной ЭВМ первые два способа не годятся. Для реализации третьего способа достаточно команды TSL и возможности объявлять прерывание указанному процессору. Блокирование процесса и переключение на другой - не эффективно, если семафор захватывается на очень короткое время. Ожидание освобождения таких семафоров может быть реализовано в ОС посредством циклического опроса значения семафора. Недостатки такого "активного ожидания" - бесполезная трата времени, нагрузка на общую память, и возможность фактически заблокировать работу процесса, находящегося в критическом интервале **********Лекция 4 Если произведенный объект используется многими, то семафоры не годятся. События. Это переменные, показывающие, что произошли определенные события. Для объявления события служит оператор POST(имя переменной), для ожидания события - WAIT (имя переменной). Для чистки (присваивания нулевого значения) - оператор CLEAR(имя переменной). Варианты реализации - не хранящие информацию (по оператору POST из ожидания выводятся только те процессы, которые уже выдали WAIT) , однократно объявляемые (нет оператора чистки). Метод последовательной верхней релаксации (SOR) с использованием массива событий. 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 ]); } Обмен сообщениями (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 процесса */ Механизмы семафоров и обмена сообщениями взаимозаменяемы семантически и на мультипроцессорах могут быть реализованы один через другой. Другие классические задачи взаимодействия процессов - проблема обедающих философов (Dijkstra) и "читатели-писатели". 2.3 Планирование процессоров Планирование процессоров очень сильно влияет на производительность мультипроцессорной системы. Можно выделить следующие главные причины деградации производительности: 1) Накладные расходы на переключение процессора. Они определяются не только переключениями контекстов процессов, но и (при переключении на процессы другого приложения) перемещениями страниц виртуальной памяти, а также порчей кэша (информация в кэше другому приложению не нужна и будет заменена). 2) Переключение на другой процесс в тот момент, когда текущий процесс выполнял критическую секцию, а другие процессы активно ожидают входа в критическую секцию. В этом случае потери будут велики (хотя вероятность прерывания выполнения коротких критических секций мала). Применяются следующие стратегии борьбы с деградацией производительности. 1) Совместное планирование, при котором все процессы одного приложения (неблокированные) одновременно выбираются на процессоры и одновременно снимаются с них (для сокращения переключений контекста). 2) Планирование, при котором находящиеся в критической секции процессы не прерываются, а активно ожидающие входа в критическую секцию процессы не выбираются до тех пор, пока вход в секцию не освободится. 3) Процессы планируются на те процессоры, на которых они выполнялись в момент их снятия (для борьбы с порчей кэша). При этом может нарушаться балансировка загрузки процессоров. 4) Планирование с учетом "советов" программы (во время ее выполнения). В ОС Mach имеется два класса таких советов (hints) - указания (разной степени категоричности) о снятии текущего процесса с процессора, а также указания о том процессе, который должен быть выбран взамен текущего. http://parallel.ru/krukov/lec4.html Синхронизация в распределенных системах Обычно децентрализованные алгоритмы имеют следующие свойства: Относящаяся к делу информация распределена среди ЭВМ. Процессы принимают решение на основе только локальной информации. Не должно быть единственной критической точки, выход из строя которой приводил бы к краху алгоритма. Не существует общих часов или другого источника точного глобального времени. Первые три пункта все говорят о недопустимости сбора всей информации для принятия решения в одно место. Обеспечение синхронизации без централизации требует подходов, отличных от используемых в традиционных ОС. Последний пункт также очень важен - в распределенных системах достигнуть согласия относительно времени совсем непросто. Важность наличия единого времени можно оценить на примере программы make в ОС UNIX. Главные теоретические проблемы - отсутствие глобальных часов и невозможность зафиксировать глобальное состояние (для анализа ситуации - обнаружения дедлоков, для организации промежуточного запоминания). -------------------------------------------------------------------------------- 4.1 Синхронизация времени Аппаратные часы (скорее таймер - счетчик временных сигналов и регистр с начальным значением счетчика) основаны на кварцевом генераторе и могут в разных ЭВМ различаться по частоте. В 1978 году Лэмпорт (Lamport) показал, что синхронизация времени возможна, и предложил алгоритм для такой синхронизации. При этом он указал, что абсолютной синхронизации не требуется. Если два процесса не взаимодействуют, то единого времени им не требуется. Кроме того, в большинстве случаев согласованное время может не иметь ничего общего с астрономическим временем, которое объявляется по радио. В таких случаях можно говорить о логических часах. Для синхронизации логических часов Lamport определил отношение "произошло до". Выражение a->b читается как "a произошло до b" и означает, что все процессы согласны, что сначала произошло событие "a", а затем "b". Это отношение может в двух случаях быть очевидным: Если оба события произошли в одном процессе. Если событие a есть операция SEND в одном процессе, а событие b - прием этого сообщения другим процессом. Отношение -> является транзитивным. Если два события x и y случились в различных процессах, которые не обмениваются сообщениями, то отношения x->y и y->x являются неверными, а эти события называют одновременными. Введем логическое время С таким образом, что если a->b, то C(a) < C(b) Алгоритм: Часы Ci увеличивают свое значение с каждым событием в процессе Pi: Ci=Ci+d (d > 0, обычно равно 1) Если событие a есть посылка сообщения m процессом Pi, тогда в это сообщение вписывается временная метка tm=Ci(a). В момент получения этого сообщения процессом Pj его время корректируется следующим образом: Cj = max(Cj,tm+d) Поясним на примере, как осуществляется эта коррекция. Логическое время без коррекции. Логическое время с коррекцией. 0 0 0 0 0 0 6 >- 8 10 6 >- 8 10 12 16 20 12 16 20 18 24 >- 30 18 24 >- 30 24 32 40 24 32 40 30 40 50 30 40 50 36 48 -< 60 36 48 -< 60 42 56 70 42 61 70 48 -< 64 80 48 -< 69 80 54 72 90 70 77 90 60 80 100 76 85 100 Для целей упорядочения всех событий удобно потребовать, чтобы их времена никогда не совпадали. Это можно сделать, добавляя в качестве дробной части к времени уникальный номер процесса (40.1, 40.2). Однако логических часов недостаточно для многих применений (системы управления в реальном времени). Физические часы. После изобретения в 17 веке механических часов время измерялось астрономически. Интервал между двумя последовательными достижениями солнцем наивысшей точки на небе называется солнечным днем. Солнечная секунда равняется 1/86400(24*3600) части солнечного дня. В 1940-х годах было установлено, что период вращения земли не постоянен - земля замедляет вращение из-за приливов и атмосферы. Геологи считают, что 300 миллионов лет назад в году было 400 дней. Происходят и изменения длительности дня по другим причинам. Поэтому стали вычислять за длительный период среднюю солнечную секунду. С изобретением в 1948 году атомных часов появилась возможность точно измерять время независимо от колебаний солнечного дня. В настоящее время 50 лабораторий в разных точках земли имеют часы, базирующиеся на частоте излучения Цезия-133. Среднее значение является международным атомным временем (TAI), исчисляемым с 1 июля 1958 года. Отставание TAI от солнечного времени компенсируется становится добавлением секунды тогда, когда разница больше 800 мксек. Это скорректированное время, называеемое UTC (Universal Coordinated Time), заменило прежний стандарт (Среднее время по Гринвичу - астрономическое время). При объявлении о добавлении секунды к UTC электрические компании меняют частоту с 60 Hz на 61 Hz (c 50 на 51) на период времени в 60 (50) секунд. Для обеспечения точного времени сигналы WWV передаются коротковолновым передатчиком (Fort Collins, Colorado) в начале каждой секунды UTC. Есть и другие службы времени. Алгоритмы синхронизации времени. Две проблемы - часы не должны ходить назад (надо ускорять или замедлять их для проведения коррекции) и ненулевое время прохождения сообщения о времени (можно многократно замерять время прохождения и брать среднее). -------------------------------------------------------------------------------- 4.2 Выбор координатора Многие распределенные алгоритмы требуют, чтобы один из процессов выполнял функции координатора, инициатора или некоторую другую специальную роль. Выбор такого специального процесса будем называть выбором координатора. При этом очень часто бывает не важно, какой именно процесс будет выбран. Можно считать, что обычно выбирается процесс с самым большим уникальным номером. Могут применяться разные алгоритмы, имеющие одну цель - если процедура выборов началась, то она должна закончиться согласием всех процессов относительно нового координатора. Алгоритм "задиры" Если процесс обнаружит, что координатор очень долго не отвечает, то инициирует выборы. Процесс P проводит выборы следующим образом: P посылает сообщение "ВЫБОРЫ" всем процессам с большими чем у него номерами. Если нет ни одного ответа, то P считается победителем и становится координатором. Если один из процессов с большим номером ответит, то он берет на себя проведение выборов. Участие процесса P в выборах заканчивается. В любой момент процесс может получить сообщение "ВЫБОРЫ" от одного из коллег с меньшим номером. В этом случае он посылает ответ "OK", чтобы сообщить, что он жив и берет проведение выборов на себя, а затем начинает выборы (если к этому моменту он уже их не вел). Следовательно, все процессы прекратят выборы, кроме одного - нового координатора. Он извещает всех о своей победе и вступлении в должность сообщением "КООРДИНАТОР". Если процесс выключился из работы, а затем захотел восстановить свое участие, то он проводит выборы (отсюда и название алгоритма). Круговой алгоритм. Алгоритм основан на использовании кольца (физического или логического), но без маркера. Каждый процесс знает следующего за ним в круговом списке. Когда процесс обнаруживает отсутствие координатора, он посылает следующему за ним процессу сообщение "ВЫБОРЫ" со своим номером. Если следующий процесс не отвечает, то сообщение посылается процессу, следующему за ним, и т.д., пока не найдется работающий процесс. Каждый работающий процесс добавляет в список работающих свой номер и переправляет сообщение дальше по кругу. Когда процесс обнаружит в списке свой собственный номер (круг пройден), он меняет тип сообщения на "КООРДИНАТОР" и оно проходит по кругу, извещая всех о списке работающих и координаторе (процессе с наибольшим номером в списке). После прохождения круга сообщение удаляется. -------------------------------------------------------------------------------- 4.3 Взаимное исключение Централизованный алгоритм Все процессы запрашивают у координатора разрешение на вход в критическую секцию и ждут этого разрешения. Координатор обслуживает запросы в порядке поступления. Получив разрешение процесс входит в критическую секцию. При выходе из нее он сообщает об этом координатору. Количество сообщений на одно прохождение критической секции - 3. Недостатки алгоритма - обычные недостатки централизованного алгоритма (крах координатора или его перегрузка сообщениями). Алгоритм с круговым маркером Все процессы составляют логическое кольцо, когда каждый знает, кто следует за ним. По кольцу циркулирует маркер, дающий право на вход в критическую секцию. Получив маркер (посредством сообщения точка-точка) процесс либо входит в критическую секцию (если он ждал разрешения) либо переправляет маркер дальше. После выхода из критической секции маркер переправляется дальше, повторный вход в секцию при том же маркере не разрешается. Проблемы: Если маркер потеряется, то его надо регенерировать. Обнаружить потерю тяжело (время прихода неизвестно). Если какой-то процесс перестанет функционировать, то алгоритм не работает. Однако восстановление проще, чем в других случаях. Наличие квитанций позволит обнаружить такой процесс в момент передачи маркера (если поломка произошла вне критического интервала). Переставший функционировать процесс должен быть исключен из логического кольца, для этого придется каждому знать текущую конфигурацию кольца. Алгоритм древовидный маркерный (Raymond) Все процессы представлены в виде сбалансированного двоичного дерева. Каждый процесс имеет очередь запросов от себя и соседних процессов (1-го, 2-х или 3-х) и указатель в направлении владельца маркера. Вход в критическую секцию: Если есть маркер, то процесс выполняет КС. Если нет маркера, то процесс: помещает свой запрос в очередь запросов посылает сообщение "ЗАПРОС" в направлении владельца маркера и ждет сообщений. Поведение процесса при приеме сообщений: Процесс, не находящийся внутри КС должен реагировать на сообщения двух видов -"МАРКЕР" и "ЗАПРОС". А) Пришло сообщение "МАРКЕР" М1. Взять 1-ый запрос из очереди и послать маркер его автору (концептуально, возможно себе); М2. Поменять значение указателя в сторону маркера; М3. Исключить запрос из очереди; М4. Если в очереди остались запросы, то послать сообщение "ЗАПРОС" в сторону маркера. Б) Пришло сообщение "ЗАПРОС". Поместить запрос в очередь Если нет маркера, то послать сообщение "ЗАПРОС" в сторону маркера, иначе (если есть маркер) - перейти на пункт М1. Выход из критической секции. Если очередь запросов пуста, то при выходе ничего не делается, иначе - перейти к пункту М1. Децентрализованный алгоритм на основе временных меток. Алгоритм носит имя Ricart-Agrawala и является улучшением алгоритма, который предлжил Lamport. Требуется глобальное упорядочение всех событий в системе по времени. Вход в критическую секцию: Когда процесс желает войти в критическую секцию, он посылает всем процессам сообщение-запрос, содержащее имя критической секции, номер процесса и текущее время. После посылки запроса процесс ждет, пока все дадут ему разрешение. После получения от всех разрешения, он входит в критическую секцию. Поведение процесса при приеме запроса: Когда процесс получает сообщение-запрос, в зависимости от своего состояния по отношению к указанной критической секции он действует одним из следующих способов. Если получатель не находится внутри критической секции и не запрашивал разрешение на вход в нее, то он посылает отправителю сообщение "OK". Если получатель находится внутри критической секции, то он не отвечает, а запоминает запрос. Если получатель выдал запрос на вхождение в эту секцию, но еще не вошел в нее, то он сравнивает временные метки своего запроса и чужого. Побеждает тот, чья метка меньше. Если чужой запрос победил, то процесс посылает сообщение "OK". Если у чужого запроса метка больше, то ответ не посылается, а чужой запрос запоминается. Выход из критической секции: После выхода из секции он посылает сообщение "OK" всем процессам, запросы от которых он запомнил, а затем стирает все запомненные запросы. Количество сообщений на одно прохождение секции - 2(n-1), где n - число процессов. Кроме того, одна критическая точка заменилась на n точек (если какой-то процесс перестанет функционировать, то отсутствие разрешения от него всех остановит). И, наконец, если в централизованном алгоритме есть опасность перегрузки координатора, то в этом алгоритме перегрузка любого процесса приведет к тем же последствиям. Некоторые улучшения алгоритма (например, ждать разрешения не от всех, а от большинства) требуют наличия неделимых широковещательных рассылок сообщений. Алгоритм широковещательный маркерный (Suzuki-Kasami). Маркер содержит: очередь запросов; массив LN[1...N] с номерами последних удовлетворенных запросов. Вход в критическую секцию: Если процесс Pk, запрашивающий критическую секцию, не имеет маркера, то он увеличивает порядковый номер своих запросов RNk[k] и посылает широковещательно сообщение "ЗАПРОС", содержащее номер процесса (k) и номер запроса (Sn=RNk[k]). Процесс Pk выполняет критическую секцию, если имеет (или когда получит) маркер. Поведение процесса при приеме запроса: Когда процесс Pj получит сообщение-запрос от процесса Pk, он устанавливает RNj[k]=max(RNj[k],Sn). Если Pj имеет свободный маркер, то он его посылает Pk только в том случае, когда RNj[k]=LN[k]+1 (запрос не старый). Выход из критической секции процесса Pk: Устанавливает LN[k] в маркере равным RNk[k]. Для каждого Pj, для которого RNk[j]=LN[j]+1, он добавляет его идентификатор в маркерную очередь запросов. Если маркерная очередь запросов не пуста, то из нее удаляется первый элемент, а маркер посылается соответствующему процессу (запрос которого был первым в очереди). Измерение производительности Введем следующие три метрики. MS/CS - количество операций приема сообщений, требуемое для одного прохождения критической секции. TR - время ответа, время от появления запроса до получения разрешения на вход. SD - синхронизационная задержка, время от выхода из критической секции одного процесса до входа в нее следующего процесса (другого!). При оценке производительности интересны две ситуации: низкая загрузка (LL), при которой вероятность запроса входа в занятую критическую секцию очень мала; высокая загрузка (HL), при которой всегда есть запросы на вход в занятую секцию. Для некоторых метрик интересно оценить наилучшее и наихудшее значение (которые часто достигаются при низкой или высокой загрузки). Сравнение алгоритмов. При оценке времен исходим из коммуникационной среды, в которой время одного сообщения (Т) равно времени широковещательного сообщения. Название алгоритма TR SD MS/CS (LL) MS/CS (HL) Централизованный 2T 2T 3 3 Круговой маркерный Древовидный маркерный Децентрализованный с временными метками NT T 2(N-1) 2(N-1) Широковещательный маркерный Все алгоритмы не устойчивы к крахам процессов (децентрализованные даже более чувствительны к ним, чем централизованный). Они в таком виде не годятся для отказоустойчивых систем. Коммуникация и синхронизация процессов в централизованных архитектурах. Основные понятия и определения. Синхронизация параллельных участков на низком уровне. Проблемы критических участков. Алгоритм Деккера. Аппаратная поддержка взаимоисключений. Крутящаяся блокировка. Блокировка с запретом прерываний. Семафоры (общий, двоичный). Взаимоисключение и синхронизация при помощи семафоров. Синхронизация процессов на высоком уровне. Мониторы. Команды wait() и signal(). Монитор, реализующий общий семафор. Рандеву в языке Ада. Решение задачи передачи данных между процессами "читатель-писатель". Тупики в централизованных операционных системах. Необходимые условия возникновения тупиков. Стратегии предотвращения необходимых условий возникновения тупиков. Алгоритм банкира. Модели для анализа свойств асинхронных процессов. Коммуникация процессов в сетях. Уровневые протоколы. Синхронизация процессов в распределенных системах. Основные подходы к синхронизации. Взаимные исключения в распределенных системах. Высокоуровневые средства синхронизации. Тупики в распределенных системах. Распределение процессоров в распределенных системах и планирование. + 2.2.1. Основные понятия и определения + 2.2.2. Алгоритм Деккера + 2.2.3. Аппаратная поддержка взаимоисключений + 2.2.4. Крутящаяся блокировка + 2.2.5. Блокировка с запретом прерываний + 2.2.6. Семафоры + 2.2.7. Мониторы + 2.2.8. Рандеву в языке программирования Ada + 2.2.9. Решение задачи передачи данных между процессами"читатель-писатель" + 2.2.10. Тупики + 2.2.11. Модели для анализа свойств асинхронных процессов + 2.2.12. Планирование и диспетчеризация процессов o 2.3. Коммуникация процессов в сетях + 2.3.1. Уровневые протоколы + 2.3.2. Адресация в сетях TCP/IP + 2.3.3. Транспортные протоколы + 2.3.4. Маршрутизация в сетях TCP/IP + 2.3.5. Формирование сети + 2.3.6. Средства коммуникации высокого уровня