Двухпроцессное решение для задачи критического сечения - алгоритм 1 - PullRequest
Новая
       30

Двухпроцессное решение для задачи критического сечения - алгоритм 1

0 голосов
/ 30 января 2019

Я начал изучать проблему критических разделов и ее различные решения.Чтобы объяснить мой вопрос, позвольте мне сначала дать краткую справку об этом.

Общая структура для решения двух процессов для задачи критического сечения - алгоритм 1: 

turn = 0;
do
{
    while (turn != 0) ; //if not P0's turn , wait indefinitely 

    // critical section of Process P0

    turn = 1; //after P0 leaves critical section, lets P1 in

    //remainder section
} while (1); //loop again

Проблема сэтот алгоритм заключается в том, что он не поддерживает необходимое требование прогресса.Это заставляет критическую секцию в равных оборотах принадлежать P0 -> P1 -> P0 -> P1 -> ... Чтобы преодолеть эту проблему, используется алгоритм 2, где переменная переменная заменяется массивом flag[].Общая структура алгоритма 2: 

do
{
    flag[0] = T ; 
    while (flag[1]);//if flag[1] is true wait indefinitely 

    // critical section of Process P0

    flag [0] = F; //P0 indicated it no longer needs to be in critical section

    //remainder section
} while (1); //loop again

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

Теперь мой вопрос, почему мы не можем использовать переменную turn внутри цикла do-while в алгоритме 1 так же, как мы используем переменную flag[] в алгоритме 2?Ниже приведен код, объясняющий, что я имею в виду: для процесса 0: 

 do
    {
        turn = 0;
        while (turn != 0) ; //if not P0's turn , wait indefinitely 

    // critical section of Process P0

    turn = 1; //after P0 leaves critical section, lets P1 in

    //remainder section
} while (1); //loop again

для процесса 1: 

do
{
    turn = 1;
    while (turn != 1) ; //if not P0's turn , wait indefinitely 

    // critical section of Process P0

    turn = 0; //after P1 leaves critical section, lets P0 in

    //remainder section
} while (1); //loop again

Разве приведенный выше код не позволяет процессу многократно выполнять свою критическую секцию,если нужно и, следовательно, решить проблему в алгоритме 1?Я знаю, что здесь что-то не так, иначе это решение использовалось бы вообще, просто не знаю точно, что это такое.

1 Ответ

0 голосов
/ 15 марта 2019

Критическая секция больше не защищена.Среди произвольных последовательностей планирования есть одна (одна строка = исключительное выполнение в течение этого времени процессом X): 

process      action                     contents of 'turn'        critical section entered (by process)
  0          "turn = 1;"                              1               no   
  0          "} while(1);"                            1               no
  1          "while (turn != 1);"                     1               no
  1          "// critical section P1"                 1               yes (1)
  0          "do{"                                    1               yes (1)
  0          "turn = 0;"                              0               yes (1)
  0          "while (turn != 0);"                     0               yes (1)
  0          "// critical section P0"                 0               collision!
...