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

–вычислительная среда – процессоры + ОС
Число процессоров М > N; M < N; M=N

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

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

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

Процессор 1

Процессор М

S3;
end;
S4;
Parend;

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

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

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

Синхронизация

R2

3 Освободить R1

4 Освободить R2

5 Захватить R2

4

Задача А

Задача В

R1

R2

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

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

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

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

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

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

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

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

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

= 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

с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

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

Остальное_I;
endloop;
Parbegin
R1;. . .Rn;
Parend.

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

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

ОбСемафор(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

Пуст.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-операции
Не позволяет реализовать протокол наследования приоритетов, т. к. не определен процесс-«владелец» семафора

– 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

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