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

Решение:

process INIT; common boolean C1. C2;

begin С1:=false; С2:=false; start(P1); start(P2); end;

process P1;

Begin

while true do

begin BEFORE1; C1:=true; while C2 do ; CS1; C1:=false; AFTER1; end

end;

process P2;

Begin

while true do

begin BEFORE2; while C1 do ; C2:=true; CS1; C2:=false; AFTER2; end

end;

Ответ:

Пусть в начальный момент времени С1=false тогда, процесс P2 прошел цикл «while C1 do» и остановился. В это же время процесс P1 проходит путь «BEFORE1; C1:=true; while C2 do ; ». Затем процесс P2 присваивает «C2:=true;» и в итоге получаем что оба процесса готовы войти в критическую секцию одновременно. Следовательно данный алгоритм не является решением поставленной задачи

2. Решить задачу взаимного исключения, используя логические переменные и процедуру перевода процесса в состояние задержки (приостановки) Delay(T), где параметр T задает время задержки процесса (время, на которое он выводится из конкуренции за время процессора).

3. Алгоритм Деккера можно сформулировать следующим образом:

Процедура инициализации	Первый процесс	Второй процесс
procedure INIT; common boolean C1,C2 ; common integer N ; begin C1 := false ; C2 := false ; N := 1 ; start(P1) ; start(P2) end INIT .	process P1; common boolean C1,C2 ; common integer N ; begin while true do begin BEFORE1 ; C1 := true ; while C2 do begin if N<>1 then begin C1 := false ; while N<>1 do ; C1 := true ; end end ; CS1 ; C1 := false; N := 2; AFTER1 ; end end P1 .	process P2; common boolean C1,C2 ; common integer N ; begin while true do begin BEFORE2 ; C2 := true ; while C1 do begin if N<>2 then begin C2 := false ; while N<>2 do ; C2 := true ; end end ; CS2 ; C2 := false; N:=1; AFTER2 ; end end P2 .

Написать алгоритм Деккера для N процессов.

Процедура инициализации	Первый процесс
procedure INIT; common Boolean[] C; common integer N ; begin for (i=1;i<=n;i++) C[i]:=false N := 1 ; for (i=1;i<=n;i++) start(Pi) ; end INIT .	process Pi; common Boolean[] C; common integer N ; begin while true do begin BEFOREi ; C[i] := true ; while (C[1])or(C[2]) or … or (C[i-1]) or (C[i+1]) or … or (C[n]) do begin if N<>i then begin C[i] := false ; while N<>i do ; C[i] := true ; end end ; CSi ; C[i] := false; If i<N then N := i+1; Else N=1; AFTERi ; end end Pi .

4. Решается ли в приведенных ниже программах проблема взаимного исключения (random – процедура, генерирующая случайное число, delay(T) – процедура задержки процесса на время T, в течение которого процесс не будет конкурировать за время процессора)?

process INIT; common boolean C1. C2; common integer N; common real T1, T2;

begin С1:=false; С2:=false; T1:= random; T2:= random; N:=1; start(P1); start(P2); end;

process P1;

Begin while true do

begin BEFORE1;

C1:=true;

while C2 and (N<>1) do delay(T1);

CS1;

C1:=false; N:=2;

AFTER1;

end

end;

process P2;

Begin while true do

begin BEFORE2;

C2:=true;

while C1 and (N<>2) do delay(T2);

CS2;

C2:=false; N:=1;

AFTER2;

end

end;

Ответ:

Нет, не решается.

• Пусть N=1 при входе в P1.

• Процесс Р1 запускается и останавливается где то внутри Before1.

• В это время процесс P2 проходит «BEFORE2; С2:=true;» и т.к. С1=false пропускает цикл «while C1 and (N<>2) do delay(T2);» и заходит в критическую секцию.

• Далее процесс Р1 выходит из «Before1» проходит до цикла и т.к. N=1 пропускает цикл и входит в критическую секцию. В итоге получили 2 процесса одновременно зашедшие в критическую секцию.

5. Задача: написать процедуры, моделирующие семафорные примитивы для общего семафора (допускаются только неотрицательные значения целочисленной переменной, моделирующей считающий семафор). При написании процедур можно использовать бинарные семафоры. Ниже приведен код процедур PP и VP, которые моделируют работу семафорных примитивов для общего семафора в соответствии с поставленной задачей. Решена ли задача? Найти в приведенном ниже псевдокоде ошибки, объяснить и исправить их, если они есть.

1. Решение:

Init: proc (var S: integer; value: integer);

common binary semaphore B1, B2;

begin

B1:=1; B2:=1; S:=value

end;

PP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin

P(B2);

P(B1);

S:=S–1; S может стать отрицательным

Нужно добавить что то вроде

If s>0 then

S:=S-1;

if S>0 then

V(B2);

V(B1)

end;

VP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin

P(B1);

S:=S+1;

V(B1);

V(B2)

end;

// если S не будет инициироваться значением <=0 то PP и PV будут работать правильно

//иначе S будет уменьшаться (при первом вызове PP) даже если свободных (или вообще) ресурсов нет

2. Решение:

Init: proc (var S: integer; value: integer);

common binary semaphore B1, B2;

begin B1:=1; B2:=1; S:=value end;

PP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin

P(B2); P(B1); S:=S–1; V(B1)

end;

VP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin

P(B1); S:=S+1; V(B1); V(B2);

end;

//здесь вообще не учитывается то, что S должно быть >=0 и может быть >1

//если процесс занимает ресурс то другие процессы не могут получить ресурсы даже если они остались в системе т.к.

//семафор B2 освободится только после того как будет освобождён ресурс

//исправить можно до варианта a(исправленного)

3. Решение:

Init: proc (var S: integer; value: integer);

common binary semaphore B1, B2;

begin B1:=1; B2:=1; S:=value end;

PP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin P(B2); while S<=0 do; P(B1); S:=S–1; V(B1); V(B2) end;

VP: procedure (var S: integer);

common binary semaphore B1, B2;

Begin P(B1); S:=S+1; V(B1); V(B2 ) end;

Пусть ресурсов K, процессов N>K

1)каждый процесс заходит в РР, а потом в VР, где остановится на «V(B2)»

Затем вызовет РР, пройдет Р(В2), завершая VP пройдет условие while и остановится возле «P(B1);»

В итоге получим что все процессы собрались перед «P(B1);» и пройдя до конца PP делают S отрицательным

// для решения можно сослаться на «а», но достаточно убрать v(b2) из VP

4. Решение:

Init: proc (var S: integer; value: integer);

common binary semaphore B;

begin B:=1; S:=value end;

PP: procedure (var S: integer);

common binary semaphore B;

Begin P(B); if S>0 then S:=S–1; V(B) end;

VP: procedure (var S: integer);

common binary semaphore B;

Begin P(B); S:=S+1; V(B) end;

Не соответствует принципам работы общего семафора. Т.к. PP должен дождаться освобождения ресурса, а вместо этого просто завершает работу.

6. Задача: написать процедуры, моделирующие семафорные примитивы для общего семафора (допускаются любые значения целочисленной переменной, моделирующей считающий семафор). При написании процедур можно использовать бинарные семафоры. Ниже приведен код процедур PP и VP, которые моделируют работу семафорных примитивов для общего семафора в соответствии с поставленной задачей. Решена ли задача? Найти в приведенном ниже псевдокоде ошибки, объяснить и исправить их, если они есть.