os4

10. Конкуренция: взаимно изключване и синхронизация
Взаимно изключване: софтуерен подход.

5.2 Взаимно изключване: софтуерен подход.
** Алгоритъм на Декер.
Първи опит:
int turn; /* =0 or =1 */

// PROCESS P0
...
while(turn!=0) nothing();
<critical section>
turn = 1;
... // PROCESS P1
...
while(turn!=1) nothing();
<critical section>
turn = 0;
...

    Щастлив сценарии - последователно влизане в КС:
P0 -> P1 -> P0 -> P1 -> P0 -> P1 -> ...
    Проблем - когато единия процес няма интерес за влизане в КС, т.е. P1 иска 2 пъти последователно да влезе в КС.
P0 -> P1 -> P1(чака, turn има стойност 1) -   P1 се блокира.
Това се случва и при грешка в единия процес

Втори опит:
bool flag[2] = {false, false};

// PROCESS P0
...
while(flag[1]) nothing();
flag[0] = true;
<critical section>
flag[0] = false;
... // PROCESS P1
...
while(flag[0]) nothing();
flag[1] = true;
<critical section>
flag[1] = false;
...

Щастлив сценарии:
P0(while)-> P0(=)-> P0(КС)-> P0(=)-> P0(while)-> P0(=)-> P0(КС)-> P0(=)->
P1(while)-> P1(=)-> P1(КС)-> P1(=)-> ...
Проблем при следния сценарии:
P0(while(flag[1]) намира го false)->
P1(while(flag[0]) намира го false)->
P0(flag[0]=true и влиза в КС) ->
P1(flag[1]=true и влиза в КС) -> BAD.
И двата процеса са в КС - няма ВИ.

Трети опит:
bool flag[2];

// PROCESS P0
...
flag[0] = true;
while(flag[1]) nothing();
<critical section>
flag[0] = false;
... // PROCESS P1
...
flag[1] = true;
while(flag[0]) nothing();
<critical section>
flag[1] = false;
...

Щастливи сценарии:
P0(=t)-> P0(while)-> P0(КС)-> P1(=t)-> P1(while,чака)-> P0(=f)-> P1(КС)-> P1(=f)-> P1(=t)-> P1(while)-> P0(КС)-> P0(=t,чака)-> P1(=f)-> P0(КС)-> ...
ВИ е гарантирано.

Проблем - възможно e МХ при следния сценарии:
P0(flag[0] = true)-> P1(flag[1] = true)-> P1(while)-> P0(while)-> MX.

** Алгоритъм на Петерсон - решение на задачата за ВИ.
bool flag[2] = {false,false};
int turn;

void P0()
{
while (true)
{
flag[0] = true;
turn = 1;
while (flag[1] && turn==1)
nothing();
<critical section>
flag[0] = false;
<remainder>
}
} void P1()
{
while (true)
{
flag[1] = true;
turn = 0;
while (flag[0] && turn==0)
nothing();
<critical section>
flag[1] = false;
<remainder>
}
}

void main()
{ flag[0] = false;
flag[1] = false;
parbegin(P0, P1);
}
Масивът flag показва заявка (интерес) за КС, променливата turn - кой в момента е в КС. Ето и всички възможности за стойности на тези променлива:

`flag[0]`	`flag[1]`	`turn`
`false`	`false`	`0, 1`	Няма интерес за КС.
`false`	`true`	`0, 1`	`P0` няма интерес за КС, `P1` в КС.
`true`	`false`	`0, 1`	`P0` в КС, `P1` няма интерес за КС.
`true`	`true`	`0`	`P0` в КС, `P1` чака за КС.
`true`	`true`	`1`	`P1` в КС, `P0` чака за КС.