Концепция процесса

программ реального времени, повысить уровень представления;
на основе предложенных формализмов создать

высокоуровневые средства надежного программирования СРВ

при выполнении программы
Несколько процессов могут выполняться «машиной» параллельно во времени

На длительность процесса и скорость его развития не накладывается никаких ограничений («длинные процессы», «короткие процессы», быстротекущие, медленные .....)

Концепция процесса – систем взглядов, положенная в основу подхода к построению средств реализации СРВ

представление некоторой вычислительной среды
Si– программа на языке Si, (S1 –

ЯВУ, S2 – Assembler, S3 – машинный код)
Мi – виртуальная машина, реализующая эту программу - Paskal-машина, Assembler-машина, «железо»)

( Вейдерман, 1971 год – Иерархия виртуальных машин:

Концепция процесса (3)

.
«Виртуальная машина»
обеспечивает параллельное выполнение процессов
Процесс
описывется программой на некотором языке (например

– задача (task) для «ADA-машины» , нитка (thread) для «Java – машины», задача многозадачной ОС)

Parend;
S1
S2
S3
S4
Parbegin
begin
Parbegin

S1;S2;
Parend;
S3;
end;
S4;
Parend;

f(I: integer);
var C: integer;
while(true);

C:= A;
doSomething(C); { C:= C+I }
A:= C;
doSomethingElse();
endwhile;
endproc;

f(5)

f(7)

A

процессами
Процесс А

t
ta1
a1


ta1
Процесс B

t
tb1
b1


tb1

Синхронизация процессов (2)

B
Занять Y
Освободить X
Занять Y
Занять X
Освободить Y

Освободить Y

Ресурс X
Ресурс Y
1
2
3
4
5
6
7
8
4
3
2
1
5
6
7
8

А
В

выполнение критических секций КС1 и КС2;
б) ни одна из задач

не должна ждать входа в свою критическую секцию бесконечно долго (блокировка недопустима )
Попытка алгоритмического решения - Алгоритм Деккера

Задача взаимного исключения

1,2;
Очередь:= 1;

Parbegin
loop
while(Очередь = 2)

endwhile;
КС_1;
Очередь:= 2;
Остальное_1;
endloop;

loop
while(Очередь = 1)
endwhile;
КС_2;
Очередь:= 1;
Остальное_2;
endloop;
Parend.

задача не решена
а) при остановке одного из процессов второй процесс

блокируется; причина – разделяемая переменная Очередь.
Однако
б) одновременное выполнение критических секций невозможно, т.к. вход к КCi строго контролируется переменной Очередь
б’) следует обратить внимание на то, что выполнение процессов строго чередуется.

занят,свободен;
с1:= свободен; с2:= свободен

Parbegin
loop
с1:= занят; {*}

while(с2=занят)
endwhile;
КС_1;
с1:= свободен;
Остальное_1;
endloop;

loop
с2:= занят; {*}
while(с1=занят)
endwhile;
КС_2;
с2:= свободен;
Остальное_2;
endloop;
Parend.

одновременном выполнении действий {*} происходит блокировка
Однако
б) одновременное выполнение критических

секций невозможно, т.к. при входе одного процесса в свою КС второй будет остановлен в результате того, что переменная с примет запрещающее значение - схема надежна с точки зрения одновременного входа в КС

Алгоритм Деккера, вспомогательная схема 2

{*}
while(с2=занят)
if(Очередь=2)

с1:= свободен
endif;
while(c2=занят) endwhile;
с1:= занят;
endwhile;
КС_1;
с1:= свободен; Очередь:=2
Остальное_1;
endloop;

loop
с2:= занят; {*}
while(с1=занят)
if(Очередь=1)
с2:= свободен
endif;
while(c1=занят) endwhile;
с2:= занят;
endwhile;
КС_2;
с2:= свободен; Очередь:=1
Остальное_2;
endloop;
Parend.

{**}

{**}

{**} параметр цикла не изменяется, т.е. цикл {**} можно представить

как «занятое ожидание» -
while(c=занят) A endwhile.
В этих условиях рассматриваемый алгоритм аналогичен Схеме 2, которая обеспечивает взаимное исключение
б) При одновременном выполнении операторов {*} «работает» переменная Очередь, позволяющая разблокировать один из процессов. Недостаток Схемы 2 ликвидирован
в) Остановка одного из процессов вне критической секции не блокирует другой процесс. Ни один из процессов не будет ждать бесконечно долго входа в свою КС

взаимного исключения алгоритмическим путем, однако, практического значения представленное решение не

имеет
Необходимы МЕХАНИЗМЫ, позволяющие надежно (обеспечивая невозможность блокировки) решать проблемы синхронизации (надо усложнять «виртуальную машину»)
Для СРВ такие механизмы не должны влиять на предсказуемость поведения системы (например, Java-машина не удовлетворяет этому условию)