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

       

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


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

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

· таблицы страниц (или сегментов);

·      дескрипторы файлов;

·      заказы на ввод-вывод;

·      регистры;

·      и т.п.

Большой объем этой информации делает дорогими  операции  создания процессов, их переключение.

Потребность в легковесных процессах,  нитях (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

Если произведенный объект используется многими,  то  семафоры  не годятся.


Содержание раздела