Документ взят из кэша поисковой машины. Адрес оригинального документа : http://sp.cs.msu.ru/courses/os43-4.doc Дата изменения: Mon Apr 23 22:23:26 2001 Дата индексирования: Mon Oct 1 20:01:53 2012 Кодировка: koi8-r

Лекция 3

2 Операционные системы мультипроцессорных ЭВМ

Организация ОС:

1. главный-подчиненный (master-slave, выделение одного процессора для ОС
упрощает ее, но этот процессор становится узким местом с точки зрения
загруженности и надежности);
2. симметричная (наиболее эффективная и сложная).

2.1 Процессы и нити

Процесс - это выполнение программы. Компоненты процесса -
выполняющаяся программа, ее данные, ее ресурсы (например, память), и
состояние выполнения.

Традиционно, процесс имеет собственное адресное пространство и его
состояние характеризуется следующей информацией:

3. таблицы страниц (или сегментов);
4. дескрипторы файлов;
5. заказы на ввод-вывод;
6. регистры;
7. и т.п.
Большой объем этой информации делает дорогими операции создания
процессов, их переключение.

Потребность в легковесных процессах, нитях (threads) возникла еще на
однопроцессорных ЭВМ (физические процессы или их моделирование,
совмещение обменов и счета), но для использования достоинств
многопроцессорных ЭВМ с общей памятью они просто необходимы.

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

2.2. Взаимодействие процессов

Если приложение реализовано в виде множества процессов (или нитей),
то эти процессы (нити) могут взаимодействовать двумя основными способами:

8. посредством разделения памяти (оперативной или внешней)
9. посредством передачи сообщений

При взаимодействии через общую память процессы должны синхронизовать свое
выполнение.
Различают два вида синхронизации - взаимное исключение критических
интервалов и координация процессов.
Критические секции. Недетерминизм, 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
Результат зависит от порядка выполнения этих команд.
Требуется взаимное исключение критических интервалов.
Решение проблемы взаимного исключения должно удовлетворять
требованиям:

10. в любой момент времени только один процесс может находиться внутри
критического интервала;
11. если ни один процесс не находится в критическом интервале, то любой
процесс, желающий войти в критический интервал, должен получить
разрешение без какой либо задержки;
12. ни один процесс не должен бесконечно долго ждать разрешения на вход в
критический интервал (если ни один процесс не будет находиться внутри
критического интервала бесконечно долго);
13. не должно существовать никаких предположений о скоростях процессоров.

Взаимное исключение критических интервалов в однопроцессорной ЭВМ.

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 процесса */

Реализация семафоров.
Мультипрограммный режим.
14. блокировка внешних прерываний;
15. запрет переключения на другие процессы;
16. переменная и очереди ожидающих процессов в ОС.

Для многопроцессорной ЭВМ первые два способа не годятся. Для реализации
третьего способа достаточно команды 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) -
указания (разной степени категоричности) о снятии текущего процесса с
процессора, а также указания о том процессе, который должен быть
выбран взамен текущего.