Операционные системы распределенных вычислительных систем
Процессы и нити
Процесс - это выполнение программы. Компоненты процесса - выполняющаяся программа, ее данные, ее ресурсы (например, память), и состояние выполнения.
Традиционно, процесс имеет собственное адресное пространство и его состояние характеризуется следующей информацией:
· таблицы страниц (или сегментов);
· дескрипторы файлов;
· заказы на ввод-вывод;
· регистры;
· и т.п.
Большой объем этой информации делает дорогими операции создания процессов, их переключение.
Потребность в легковесных процессах, нитях (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
Если произведенный объект используется многими, то семафоры не годятся.
