Асинхронное выполнение задач

cвоевременную реакцию на асинхронные события.
События


2
1
2
1

1
T

T

T

1
T
T

T
Задача 1
Задача 2
Задача T
Прерывание от

таймера – запуск периодической задачи Т
Событие «1» - прерывается Т, активизируется задача 1
Событие «2» - прерывается 1, активизируется задача 2
Задача 2 заканчивается, возобновляется задача 1
И т. д. . . . . .

История вопроса, «Концепция процесса» Дейкстра «Взаимодействующие последовательные процессы»
«Языки программирования» под ред. Ф. Женюи, М., "Мир", 1972
Дейкстра Эдсгер 1930-2002

6. «Вдаимодействующие последовательные процессы» 2015 v.01

машина» –вычислительная среда – процессоры + ОС
Число процессоров

М > N; M < N; M=N

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

Условия реализации :

6. «Вдаимодействующие последовательные процессы» 2015 v.01

Процессор 1

Процессор М

Parbegin
S1;S2;
Parend;

S3;
end;
S4;
Parend;

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

6. «Вдаимодействующие последовательные процессы» 2015 v.01

диаграммы
6. «Вдаимодействующие последовательные процессы» 2015 v.01
Синхронизация

Захватить R1



3
2
1
5
6
7
8

А
В
2 Захватить R2
3 Освободить R1
4 Освободить R2

5 Захватить R2
4
Задача

А

Задача В

R1

R2

6. «Вдаимодействующие последовательные процессы» 2015 v.01

КС1 и КС2;
б) ни одна из задач не должна ждать

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

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

6. «Вдаимодействующие последовательные процессы» 2015 v.01

while(true){
while(Очередь == 2){}
КС_1;

Очередь = 2;
Остальное_1;
}

while(true){
while(Очередь == 1){}
КС_2;
Очередь = 1;
Остальное_2;
}
Parend.

6. «Вдаимодействующие последовательные процессы» 2015 v.01

при остановке одного из процессов второй процесс блокируется; причина –

разделяемая переменная Очередь.

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

6. «Вдаимодействующие последовательные процессы» 2015 v.01

с2 = 0; //свободен;

Parbegin
while(true){
с1=

1; {*}
while(с2==1){}
КС_1;
с1 = 0;
Остальное_1;
}

while(true){
с2:= 1; {*}
while(с1==1){}
КС_2;
с2 = 0;
Остальное_2;
};
Parend.

6. «Вдаимодействующие последовательные процессы» 2015 v.01

{*} происходит блокировка

Однако
б) одновременное выполнение критических секций невозможно, т.к.

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

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

6. «Вдаимодействующие последовательные процессы» 2015 v.01

if(Очередь == 2){
с1

= 0;
}
while(c2 == 1){}
с1 = 1;
};
КС_1;
с1 = 0; Очередь = 2
Остальное_1;
};

while(true){
с2:= 1; {*}
while(с1==1){
if(Очередь == 1){
с2 = 0
}
while(c1 == 1){};
с2 = 1;
}
КС_2;
с2 = 0; Очередь = 1
Остальное_2;
};
Parend.

{**}

{**}

6. «Вдаимодействующие последовательные процессы» 2015 v.01

с1 = 1; с2 = 0; Очередь = 1

цикл {**} можно представить как «занятое ожидание» -
while(c=занят) A

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

Алгоритм Деккера, реализация

6. «Вдаимодействующие последовательные процессы» 2015 v.01

1;
void P{
if(значение = =

0) then
ждать(значение>0);
значение = 0;
}
void V{
значение = 1;
}
}

Конструкция динамическая:
ДвСемафор S =
new ДвСемафор();

6. «Вдаимодействующие последовательные процессы» 2015 v.01

заблокированных процессов; очередь обслуживается в соответствии с определенной дисциплиной, не

допускающей бесконечного ожидания процесса (например, FIFO)
При значение=0 операция ждать(значение>0) блокирует процесс, вызвавший P–операцию и и ставит его в очередь до момента выполнения условия значение>0;
При выполнении V–операции активизируется первый процесс из очереди; продолжение этого процесса происходит с действия S=0 приостановленной P–операции
P и V операции над семафором S являются неделимыми (могут выполняться только одним процессом)

6. «Вдаимодействующие последовательные процессы» 2015 v.01

loop
S.P();

КС_I;
S.V();
Остальное_I;
endloop;

Parbegin
R1;. . .Rn;
Parend.

P и V операции неделимы; т.е. выполнять S.P() может только один процесс ;
Если один из процессов выполнил S.P() и вошел в свою КС, то S.значение = 0 и все остальные процессы, выполняющие S.P(), будут блокироваться. Т.е взаимное исключение обеспечено
При выполнении S.V() соблюдается очередность, т.е. никто не будет ждать бесконечно долго

6. «Вдаимодействующие последовательные процессы» 2015 v.01

private integer maxЗначение;
ОбСемафор(integer n, m) {

значение = n; maxЗначение = m;
}
void P(){
if(значение = = 0) then
ждать(значение>0);
значение--;
}
void V(){
if(значение }
}

Конструкция динамическая:
ОбСемафор S =
new ОбСемафор(N,M);

6. «Вдаимодействующие последовательные процессы» 2015 v.01

А, размер которого N
Потребитель: читает и обрабатывает информацию из буфера

А
Требуется реализовать процессы Поставщик и Потребитель таким образом, чтобы выполнялись условия:
а) Поставщик не может записывать в полный буфер;
б) Потребитель не может читать из пустого буфера;
в) одновременные запись и чтение недопустимы

6. «Вдаимодействующие последовательные процессы» 2015 v.01

Полон.P();
(**) Доступ.P();
Запись_в_буфер;
Доступ.V();

Пуст.V();
endloop.

«Поставщик-Потребитель» - реализация

ДвСемафор Доступ = new ДвСемафор();
ОбСемафор Полон = new ОбСемафор(N,N);
ОбСемафор Пуст = new ОбСемафор(0,N);

Потребитель:
loop
Пуст.P();
Доступ.P();
Чтение_из_буфера;
Доступ.V();
Полон.V();
Обработка;
endloop.

6. «Вдаимодействующие последовательные процессы» 2015 v.01

уровень, слабая защищенность от ошибок при программировании
Возможность использования P() и

V() над одним семафором из разных задач (семафор S может быть установлен в 0 в одной задаче, а в 1 – в другой, см. задачу «Поставщик-Потребитель»)
Возможность вызова V-операции над семафором без предварительного вызова P-операции
Не позволяет реализовать протокол наследования приоритетов, т. к. не определен процесс-«владелец» семафора

семафоры в RTEK
KC_CloseSema – end the use of

dynamic semaphore
KC_DefSemaCount – define a semaphore count
KC_DefSemaName – define the name of a previously
opened dynamic semaphore
KC_GetSemaCount – get the current semaphore count
KC_GetSemaName – get the name of a semaphore
KC_GetSemaProp - get the properties of a semaphore
KC_GetSemaWaiters – get the number and list of tasks
waiting on semaphore
KC_InitSemaClassProp – initialize the semaphore object
class properties

look up a semaphore’s name to get its

handle
KC_OpenSema – allocate and name a dynamic semaphore
KC_SignalSema – signal a semaphore
KC_SignalSemaM – signal multiply semaphores
KC_TestSema – test a semaphore
KC_TestSemaT – test a semaphore and wait for a specified
time if the semaphore is not DONE
KC_TestSemaW - test a semaphore and wait if the
semaphore is not DONE

Пример сервисов, поддерживающих семафоры в RTEK

семафоры

#include
(sem_t mySem;)

int sem_init( sem_t * sem, int

pshared, unsigned value );
*sem – указатель на объект, который мы хотим инициировать
pshared – не «0», если мы хотим, чтобы sem разделялся процессами через разделяемую память
value – значение семафора (> 0, если «0», то семафор блокирован)
int sem_destroy( sem_t * sem );
int sem_wait( sem_t * sem );
int sem_post( sem_t * sem ) – инкремент значения семафора;
int sem_trywait( sem_t * sem ) - неблокирующий декремент значения семафора

Именованные семафоры – межпроцессная и сетевая поддержка; примитивы другие.