Электронный коспект лекций (1162752), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Избежать активногоожидания помогают семафоры.Семафоры Дейкстры (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 ивозможности объявлять прерывание указанному процессору(чтобы сообщить другим процессорам, что разблокирован один изпроцессов).Блокирование процесса и переключение на другой - неэффективно, если семафор захватывается на очень короткоевремя. Можно ввести специальные семафоры, которыезахватываются на короткое время. Ожидание освобождения такихсемафоров может быть реализовано в ОСпосредствомциклического опроса значения семафора.Лекция 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 ]);}Обмен сообщениями (message passing)Хоар (Xoare) 1978 год, "Взаимодействующие последовательныепроцессы".

Цели - избавиться от проблем разделения памяти ипредложитьмодельвзаимодействияпроцессовдляраспределенных систем.send (destination, &message, msize);receive ([source], &message, msize);Адресат - процесс. Отправитель - может не специфицироваться(любой).С буферизацией (почтовые ящики) или нет (рандеву - Ада, Оккам).Пайпы ОС UNIX - почтовые ящики, заменяют файлы и не хранятграницы сообщений (все сообщения объединяются в однобольшое, которое можно читать произвольными порциями).Пример использования буферизуемых сообщений.#define N 100сообщений */#define msize 4typedef 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 процесса */Механизмысемафоров и обмена сообщениямивзаимозаменяемы семантически и на мультипроцессорах могутбыть реализованы один через другой.

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

При этом может нарушаться балансировка загрузкипроцессоров.4) Планирование с учетом "советов" программы (во время еевыполнения). В ОС Mach имеется два класса таких советов(hints) - указания (разной степени категоричности) о снятиитекущего процесса с процессора, а также указания о томпроцессе, который должен быть выбран взамен текущего.Лекция 53 Коммуникации в распределенных системахВсе компьютеры в распределенной системе связаны междусобой коммуникационной сетью. Коммуникационныесетиподразделяются на широкомасштабные (Wide Area Networks,WANs) и локальные (Local Area Networks, LANs).Широкомасштабные сетиWAN состоит из коммуникационных ЭВМ, связанных междусобой коммуникационными линиями (телефонные линии,радиолинии,спутниковые каналы, оптоволокно)иобеспечивающих транспортировку сообщений.Обычно используется техникаstore-and-forward,когдасообщения передаются из одного компьютера в следующий спромежуточной буферизацией.Коммутация пакетов или коммутация линий.Коммутация линий(телефонныеразговоры)требуетрезервирования линий на время всего сеанса общения двухустройств.Пакетная коммутация основана на разбиении сообщений впункте отправления на порции (пакеты), посылке пакетов поадресу назначения, и сборке сообщения из пакетов в пунктеназначения.При этом линии используются эффективнее,сообщения могут передаваться быстрее, но требуется работа поразбиению и сборке сообщений, а также возможны задержки (дляпередачи речи или музыки такой метод не годится).Семиуровневая модель ISOISO OSI (International Standards Organizations»s Reference Model ofOpen Systems Interconnection) организует коммуникационныепротоколы в виде семи уровней и специфицирует функциикаждого уровня.Локальные сети.Особенности LAN: географическая область охвата невелика (здание илинесколько зданий); высокая скорость передачи (100-1000 Mbps); малая вероятность ошибок передачи.Свойственные многоуровневой модели ISO OSI накладныерасходы являются причиной того, что в LAN применяются болеепростые протоколы.Клиент-серверМожно избежать подтверждения получения сервером сообщениязапроса от клиента, если ответ сервера должен последовать скоро.Удаленный вызов процедурSend, receive - подход ввода/выводаБолее естественный подход, применяемый в централизованныхЭВМ - вызов процедур.Birrell and Nelson (1984) (независимо и раньше - ИлюшинА.И.,1978) предложили позволить вызывающей программенаходиться на другой ЭВМ.MPP с распределенной памятью может рассматриваться какчастный случай локальной сети.

Характеристики

Список файлов лекций