 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Задачи на работу с семафорами
|
|
1. Задача: написать процедуры, моделирующие семафорные примитивы для общего семафора (допускаются только неотрицательные значения целочисленной переменной, моделирующей считающий семафор). При написании процедур можно использовать бинарные семафоры. Ниже приведен код процедур PP и VP, которые моделируют работу семафорных примитивов для общего семафора в соответствии с поставленной задачей. Решена ли задача? Найти в приведенном ниже псевдокоде ошибки, объяснить и исправить их (привести примеры, иллюстрирующие возможные проблемы), если они есть.
1.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; 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;
1.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;
1.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;
1.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;
2. Задача: написать процедуры, моделирующие семафорные примитивы для общего семафора (допускаются любые значения целочисленной переменной, моделирующей считающий семафор). При написании процедур можно использовать бинарные семафоры. Ниже приведен код процедур PP и VP, которые моделируют работу семафорных примитивов для общего семафора в соответствии с поставленной задачей. Решена ли задача? Найти в приведенном ниже псевдокоде ошибки, объяснить и исправить их (привести примеры, иллюстрирующие возможные проблемы), если они есть.
2.1. Решение:
Init: proc (var S: integer; value: integer); begin S:=value end;
PP: procedure (var S: integer);
common binary semaphore B1, B2;
Begin P(B1); S:=S–1; if S<0 then begin V(B1); P(B2) end
Else V(B1) end;
VP: procedure (var S: integer);
common binary semaphore B1, B2;
Begin P(B1); S:=S+1; if S<=0 then V(B2); V(B1) end;
2.2. Решение:
Init: proc (var S: integer; value: integer);
common binary semaphore B1, B2;
begin B1:=1; B2:=0; S:=value end;
PP: procedure (var S: integer);
common binary semaphore B1, B2;
Begin P(B1); S:=S–1; P(B2) end;
VP: procedure (var S: integer);
common binary semaphore B1, B2;
Begin P(B2); S:=S+1; V(B1) end;
2.3. Решение:
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 if S>0 then begin P(B); S:=S–1; V(B) endend;
VP: procedure (var S: integer);
common binary semaphore B;
Begin P(B); S:=S+1; V(B) end;
2.4. Решение:
Init: proc (var S: integer; value: integer); begin S:=value end;
PP: procedure (var S: …); common binary semaphore B1, B2;
Begin P(B1); S:=S–1; if S<0 then P(B2) Else V(B1) end;
VP: procedure (var S: …); common binary semaphore B1, B2;
Begin P(B1); S:=S+1; if S<=0 then V(B2); V(B1) end;
2.5. Решение:
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(B1); S:=S–1; if S<0 then P(B2) Else V(B1) end;
VP: procedure (var S: integer);
common binary semaphore B1, B2;
Begin P(B1); S:=S+1; if S>0 then V(B2); V(B1) end;
3. Задача “обедающие философы” формулируется следующим образом: “Пять философов садятся обедать за круглый стол, в центре которого стоит одно блюдо со спагетти. На столе имеется пять тарелок и пять вилок между ними. Философ может начать есть, если у него есть тарелка и две вилки, которые он может взять с двух сторон от своей тарелки. Философ может отдать вилки соседям только после того, как он закончит обед”. О соображениях гигиены мы здесь умалчиваем. Может ли описанный ниже на псевдокоде процесс представить алгоритм поведения философа за столом (привести примеры, иллюстрирующие возможные проблемы)?
3.1. Решение:
Инициализация:
{ “Вилки”, которые используются философами – это разделяемые ресурсы,
защищенные бинарными семафорами: }
common B: array [0..4] of binary semaphore; { глобальный массив семафоров}
for I:=0 to 4 do B[I]:=1; { все “вилки” свободны }
process Философ(I: Integer);
{ Это процесс, описывающий поведение I-го философа. }
{ “Вилки”, которыми он ест, защищаются двумя бинарными семафорами. }
common B: array [0..4] of binary semaphore
begin { Пытается получить вилки: }
while (P(B[I])=0) or (P(B[(I+1) mod 5])=0) do;
{ Ест спагетти, используя вилки, находящиеся слева и справа } …
{ Освобождает вилки: } V(B[(I+1) mod 5]); V(B[I]);
end;
3.2. Решение:
Инициализация:
{ “Вилки”, которые используются философами – это разделяемые ресурсы,
защищенные бинарными семафорами: }
common B: array [0..4] of binary semaphore; { глобальный массив семафоров}
for I:=0 to 4 do B[I]:=1; { все “вилки” свободны }
process Философ(I: Integer);
{ Это процесс, описывающий поведение I-го философа. }
{ “Вилки”, которыми он ест, защищаются двумя бинарными семафорами. }
common B: array [0..4] of binary semaphore
Begin
{ Пытается получить вилки: }
P(B[I]); P(B[(I+1) mod 5]);
{ Ест спагетти, используя вилки, находящиеся слева и справа } …
{ Освобождает вилки: }
V(B[(I+1) mod 5]); V(B[I]);
end;
Контрольная по теме «Синхронизация процессов»
Вариант 1
5. Задача: решить программным способом задачу взаимного исключения. Являются ли приведенные ниже процедуры решением поставленной задачи? Если нет, объясните, когда могут возникнуть ошибки?
Решение:
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;
6. Алгоритм Деккера можно сформулировать следующим образом:
| Процедура инициализации | Первый процесс | Второй процесс |
| 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; 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; 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 процессов.
7. Задача “обедающие философы” формулируется следующим образом: “Пять философов садятся обедать за круглый стол, в центре которого стоит одно блюдо со спагетти. На столе имеется пять тарелок и пять вилок между ними. Философ может начать есть, если у него есть тарелка и две вилки, которые он может взять с двух сторон от своей тарелки. Философ может отдать вилки соседям только после того, как он закончит обед”. О соображениях гигиены мы здесь умалчиваем. Может ли описанный ниже на псевдокоде процесс представить алгоритм поведения философа за столом (привести примеры, иллюстрирующие возможные проблемы)?
Инициализация:
{ “Вилки”, которые используются философами – это разделяемые ресурсы,
защищенные бинарными семафорами: }
common B: array [0..4] of binary semaphore; { глобальный массив семафоров}
for I:=0 to 4 do B[I]:=1; { все “вилки” свободны }
process Философ(I: Integer);
{ Это процесс, описывающий поведение I-го философа. }
{ “Вилки”, которыми он ест, защищаются двумя бинарными семафорами. }
common B: array [0..4] of binary semaphore
Begin
{ Пытается получить вилки: }
P(B[I]); P(B[(I+1) mod 5]);
{ Ест спагетти, используя вилки, находящиеся слева и справа } …
{ Освобождает вилки: } V(B[(I+1) mod 5]); V(B[I]);
end;
8. Задача: написать процедуры, моделирующие семафорные примитивы для общего семафора (допускаются любые значения целочисленной переменной, моделирующей считающий семафор). При написании процедур можно использовать бинарные семафоры. Ниже приведен код процедур PP и VP, которые моделируют работу семафорных примитивов для общего семафора в соответствии с поставленной задачей. Решена ли задача? Найти в приведенном ниже псевдокоде ошибки, объяснить и исправить их (привести примеры, иллюстрирующие возможные проблемы), если они есть.
Решение:
Init: proc (var S: integer; value: integer); begin S:=value end;
PP: procedure (var S: integer);
common binary semaphore B1, B2;
Begin P(B1); S:=S–1; if S<0 then begin V(B1); P(B2) end
Else V(B1) end;
VP: procedure (var S: integer);
common binary semaphore B1, B2;
Begin P(B1); S:=S+1; if S<=0 then V(B2); V(B1) end;
Вариант 2
9. Решается ли в приведенных ниже программах проблема взаимного исключения (random – процедура, генерирующая случайное число, delay (T) – процедура задержки процесса на время T, в течение которого процесс не будет конкурировать за время процессора)?
process INIT; common boolean C1. C2; common integer N; common real T1, T2;
begin С1:= false;С2:= false; T1:= random; T1:= 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;
10. Алгоритм Деккера можно сформулировать следующим образом:
| Процедура инициализации | Первый процесс | Второй процесс |
| 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; 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; 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 процессов.
11. Задача “обедающие философы” формулируется следующим образом: “Пять философов садятся обедать за круглый стол, в центре которого стоит одно блюдо со спагетти. На столе имеется пять тарелок и пять вилок между ними. Философ может начать есть, если у него есть тарелка и две вилки, которые он может взять с двух сторон от своей тарелки. Философ может отдать вилки соседям только после того, как он закончит обед”. О соображениях гигиены мы здесь умалчиваем. Может ли описанный ниже на псевдокоде процесс представить алгоритм поведения философа за столом (привести примеры, иллюстрирующие возможные проблемы)?
Решение:
Инициализация:
{ “Вилки”, которые используются философами – это разделяемые ресурсы,
защищенные бинарными семафорами: }
common B: array [0..4] of binary semaphore; { глобальный массив семафоров}
for I:=0 to 4 do B[I]:=1; { все “вилки” свободны }
process Философ(I: Integer);
{ Это процесс, описывающий поведение I-го философа. }
{ “Вилки”, которыми он ест, защищаются двумя бинарными семафорами. }
common B: array [0..4] of binary semaphore
begin { Пытается получить вилки: }
while (P(B[I])=0) or (P(B[(I+1) mod 5])=0) do;
{ Ест спагетти, используя вилки, находящиеся слева и справа } …
{ Освобождает вилки: } V(B[(I+1) mod 5]); V(B[I]);
end;
12. Задача: написать процедуры, моделирующие семафорные примитивы для общего семафора (допускаются любые значения целочисленной переменной, моделирующей считающий семафор). При написании процедур можно использовать бинарные семафоры. Ниже приведен код процедур PP и VP, которые моделируют работу семафорных примитивов для общего семафора в соответствии с поставленной задачей. Решена ли задача? Найти в приведенном ниже псевдокоде ошибки, объяснить и исправить их (привести примеры, иллюстрирующие возможные проблемы), если они есть.
Решение:
Init: proc (var S: integer; value: integer); begin S:=value end;
PP: procedure (var S: …); common binary semaphore B1, B2;
Begin P(B1); S:=S–1; if S<0 then P(B2) Else V(B1) end;
VP: procedure (var S: …); common binary semaphore B1, B2;
Begin P(B1); S:=S+1; if S<=0 then V(B2); V(B1) end;
Задания по теме «Тупики»
Задачи на анализ состояний системы
для выявления тупиков
13. Пусть в системе есть два процесса P1 и P2 и два единичных повторно используемых ресурса R1 и R2. Процессы имеют следующее описание:
| Процесс 1 | Процесс 2 |
| process P1; begin... While true do begin … request (R1, 1); ... request (R2, 1); ... release (R2, 1); ... release (R1, 1); ... end ... end. | process P2; begin... While true do begin … request (R2, 1); ... request (R1, 1); ... release (R2, 1); ... release (R1, 1); ... end ... end. |
Построить граф состояний системы. Возможны ли в системе тупиковые состояния?
14. Пусть в системе есть два процесса P1 и P2 и два потребляемых ресурса R1 и R2, используемых этими процессами. Ресурс R1 производится процессом P1, а R2 – P2. Процессы имеют следующее описание:
| Процесс 1 | Процесс 2 |
| process P1; begin... While true do begin … request (R2, 1); ... release (R1, 1); ... end ... end. | process P2; begin... While true do begin … request (R1, 1); ... release (R2, 1); ... end ... end. |
Построить граф состояний системы. Возможны ли в системе тупиковые состояния?
Дата публикования: 2014-11-29; Прочитано: 420 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
