Операционные системы распределенных вычислительных систем (распределенные ос)

Вид материала

Содержание

Обмен сообщениями (message passing)
2.3 Планирование процессоров

Подобный материал:

1 2 3 4 5 6 7 8 9 ... 12

События.

Это переменные, показывающие, что произошли определенные события.

Для объявления события служит оператор 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 Планирование процессоров

Планирование процессоров очень сильно влияет на производительность мультипроцессорной системы. Можно выделить следующие главные причины деградации производительности:

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

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

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

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

Вопросы:

Имеется механизм двоичных семафоров. Опираясь на него, реализуйте P-операцию и V-операцию для общего (считающего) семафора. Активное ожидание освобождения семафора не допускается.
Имеется команда TSL и команда объявления прерывания указанному процессору. Опираясь на них, реализуйте на мультипроцессоре P-операцию и V-операцию для двоичного семафора. Активное ожидание освобождения семафора не допускается.
Имеется механизм двоичных семафоров. Опираясь на него, реализуйте операторы POST(имя переменной-события) и WAIT(имя переменной-события). Активное ожидание события не допускается. Оцените, во сколько раз нижеприведенный алгоритм метода последовательной верхней релаксации можно выполнить быстрее, чем последовательный, если число процессоров мультипроцессора = N, время выполнения одного оператора присваивания (A[i][j]=....) равно 1, временами выполнения остальных операторов можно пренебречь.

float A[ L1 ][ L2 ];

semaphore s[ L1 ][ L2 ]; /* массив двоичных семафоров с нулевым начальным значением */

for ( j = 0; j < L2; j++) { post( s[ 0 ][ j ]) }

parfor ( i = 1; i < L1-1; i++)

for ( j = 1; j < L2-1; j++)

{ wait( s[ i-1 ][ j ]);

A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1][ j ] + A[ i ][ j-1 ] + A[ i ][ j+1 ]) / 4;

post( s[ i ][ j ]);

}

Имеется механизм двоичных семафоров. Опираясь на него, реализуйте задачу читателей и писателей (алгоритмы предоставления прав доступа процессам-читателям и процессам-писателям):

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

Запросы на доступ должны удовлетворяться “справедливо” - в порядке их поступления (можно исходить из “справедливости“ удовлетворения запросов на двоичные семафоры).

Какие модели консистентности памяти удовлетворяют алгоритму Деккера (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.
Какие модели консистентности памяти удовлетворяют алгоритму Петерсона (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.

При решении задач по теме 2 обратить внимание на следующее.

Нельзя модифицировать общие переменные вне КС.
При наличии вложенных КС или запросов нескольких семафоров необходимо убедиться, что не могут возникнуть тупики.
Нельзя обращаться к семафорам и событиям обычными операторами – только посредством операций, которые определены над ними (P, V, POST, WAIT, CLEAR).
Нельзя освобождать свободный семафор и объявлять уже объявленное событие.
Определять начальные значения семафоров и событий, если они должны быть отличны от нуля (семафор занят, событие не объявлено).

Blog

Операционные системы распределенных вычислительных систем (распределенные ос)

Содержание

События.

2.3 Планирование процессоров