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


Процессы и нити - часть 2


Решение проблемы   взаимного   исключения   должно  удовлетворять требованиям:

·      в  любой  момент времени только один процесс может находиться внутри критического интервала;

·      если ни один процесс не находится в критическом интервале, то любой процесс, желающий войти в критический интервал,   должен получить разрешение без какой либо задержки;

·      ни  один процесс не должен бесконечно долго ждать разрешения на вход в критический интервал (если ни  один  процесс не будет находиться внутри критического интервала бесконечно долго);

·      не должно существовать никаких предположений о скоростях  процессоров.

 

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

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;




Начало  Назад  Вперед