Задача 4 (синхронная система вытесняемых задач)

Приложение с двоично-ранжированными периодами задач содержит пять рангов R₀, R₁, R₂, R₃, R₄ вытесняемых задач с ритмической активизацией. Задачи ранга R_i должны быть выполнены в рамках интервала времени, равного периоду T_i этого ранга (D_i =T_i).

Параметр	Ранги
	R0	R1	R2	R3	R4
Требуемый ресурс CPU	12	25	53	127	180
Период	65	265	465	865	1665

Отвечает ли такая модель приложения условию выполнимости?

Синхронная система с вытесняемыми задачами

Условие выполнимости :

 C_i / T_i  1

Решение задачи 4 (синхронная система вытесняемых задач)

1.  C_i / T_i  1

12/65 + 25/130 +53/260 +127/520 + 180 /1040 =

= ((1216) + (258) +(534) +(1272) + 180)/1040 =

= (192 + 200 +212 +254 +38)/1040 =

= 1038/1040 < 1;

Таким образом, рассматриваемая модель приложения отвечает условиям выполнимости.

Упражнение по задаче 4

Приложение с двоично-ранжированными периодами задач содержит пять рангов R₀, R₁, R₂, R₃, R₄ вытесняемых задач с ритмической активизацией. Задачи ранга R_i должны быть выполнены в рамках интервала времени, равного периоду T_i этого ранга (D_i =T_i).

Параметр	Ранги
	R0	R1	R2	R3	R4
Требуемый ресурс CPU	12	25	53	127	180
Период	64	264	464	864	1664

Отвечает ли такая модель приложения условию выполнимости?

Задача 5 (планируемость вытесняемых задач при D<T)

Программное приложение состоит из трех асинхронных вытесняемых задач  ₁,  ₂,  ₃ с параметрами, определенными в таблице:

Параметры задач (ед.времени)	Задачи
	 1	 2	 3
C i – требуемый ресурс CPU	8	6	7
D i – срок выполнения	10	28	15
P i – период	90	35	50

Проверить планируемость приложения. Если выполнимость приложения в целом не гарантируется никакой дисциплиной планирования, указать выполнимое подмножество задач.

Решение задачи 5 (планируемость вытесняемых задач при D<T)

Критическому сценарию для асинхронных вытесняемых задач соответствует одновременная активизация всех задач. (см. приведенную ниже диаграмму).

Своевременность выполнения задач приложения { ₁,  ₂,  ₃) гарантируется при дисциплине обслуживания, обеспечивающей выполнение неравенств pr( ₁)>pr( ₃)>pr( ₂).

Упражнение по задаче 5

Программное приложение состоит из трех асинхронных вытесняемых задач  ₁,  ₂,  ₃ с параметрами, определенными в таблице:

Параметры задач (ед.времени)	Задачи
	 1	 2	 3
C i – требуемый ресурс CPU	4	6	8
D i – срок выполнения	12	18	22
T i – период	16	24	32

Проверить планируемость приложения.

Задача 6 (время отклика вытесняемых задач при D<P)

Программное приложение состоит из пяти асинхронных вытесняемых задач  ₁,  ₂, … ,  ₅ с параметрами, определенными в таблице:

Параметры задач (ед.времени)	Задачи
	 1	 2	 3	 4	 5
C i – требуемый ресурс CPU	4	3	5	6	4
D i – срок выполнения	9	14	10	45	25
T i – период	15	20	28	45	60

Проверить планируемость планирования..

Решение задачи 6 (время отклика вытесняемых задач при D<P)

Оптимальной дисциплиной планирования является планирование, монотонное по предельным значениям относительных сроков выполнения задач (DMS – Deadline Monotonic Scheduling). Поэтому значения приоритетов задач надлежит назначать следующим образом:

pr( ₁)=5 (высший приоритет),

pr( ₃)=4,

pr( ₂)=3,

pr( ₅)=2,

pr( ₄)=1 (низший приоритет).

Время отклика R _i каждой из задач  _i определяется уравнением:

R _i = C_i + ∑ C_j R _i /T_j ,

где суммирование ведется по всем более приоритетным по отношению к  _i задачам. Решение уравнения ищется путем применения процедуры построения последовательных оценок R_i⁽⁰⁾, R_i⁽¹⁾, …, величины R _i:

R_i⁽⁰⁾ =0; R_i⁽ⁿ⁾ = C_i + ∑ C_j  R_i^(n-1) /T_j ,

При R_i⁽ⁿ⁾=R_i^(n-1), процесс останавливается – решение найдено. Ищем последовательно время отклика R_i для каждой из задач  _i и сравниваем его с предельным сроком выполнения D_i.

Для задачи  ₁:

R₁⁽⁰⁾=0;

R₁⁽¹⁾=С₁=4;

R₁⁽²⁾=С₁=4.

Время отклика R₁=4. Задача  ₁ выполнима, поскольку R₁< D₁=9.

Для задачи  ₃:

R₃⁽⁰⁾=0;

R₃⁽¹⁾=С₃=5;

R₃⁽²⁾=С₃+С₁=9;

R₃⁽³⁾=С₃+С₁=9;

R₃=9.

Время отклика R₃=9. Задача  ₃ выполнима, поскольку R₃< D₃=10.

Для задачи  ₂:

R₂⁽⁰⁾=0;

R₂⁽¹⁾=С₂=5;

R₂⁽²⁾=С₂+С₁+С₃=12;

R₂⁽³⁾=С₂+С₁+С₃=12;

R₂=12.

Время отклика R₂=12. Задача  ₂ выполнима, поскольку R₂< D₂=14.

Для задачи  ₅:

R₅⁽⁰⁾=0;

R₅⁽¹⁾=С₅=4;

R₅⁽²⁾=С₅+С₁+С₃+С₂=16;

R₅⁽³⁾=С₅+2С₁+С₃+С₂=20;

R₅⁽⁴⁾=С₅+2С₁+С₃+С₂=20;

R₅=20.

Время отклика R₅=20. Задача  ₅ выполнима, поскольку R₅< D₅=25.

Для задачи  ₄:

R₄⁽⁰⁾=0;

R₄⁽¹⁾=С₄=6;

R₄⁽²⁾=С₄+С₁+С₃+С₂+С₅=22;

R₄⁽³⁾=С₄+2С₁+С₃+2С₂+С₅=29;

R₄⁽⁴⁾=С₄+3С₁+2С₃+2С₂+С₅=38;

R₄⁽⁵⁾=С₄+3С₁+2С₃+2С₂+С₅=38;

R₄=38.

Время отклика R₄=38. Задача  ₄ выполнима, поскольку R₄< D₄=45.