Page 349 - 《软件学报》2020年第11期

3664 Journal of Software 软件学报 Vol.31, No.11, November 2020

χ
()
一个已知的作业集,可以根据公式(1)~公式(4)计算各作业的动态需求边界函数,其中, dt 的值取 0.相应地,可
i
以根据公式(5)计算作业的松弛时间,根据公式(6)计算关键级的松弛时间.从伪代码第 4 行开始进入运行时部分.
在每一个时间点,系统总是选取所有不小于 0 的关键级松弛时间中的最小值所对应的关键级作为系统关键级
(第 5 行).选择所有自身关键级不小于系统关键级的作业中具有最早时限的作业执行(第 7 行),如果这样的关键
级不存在,即所有的关键级松弛时间都小于 0,那么系统是不可调度的(第 6 行).在第 9 行,函数 EventHandle(⋅)是
算法中的核心函数,主要用于处理系统中的事件,如作业执行、作业完成、作业超时等,并根据系统的事件,更新
作业的需求边界与松弛时间.EventHandle(⋅)如算法 2 所示.
算法 2. 事件处理函数 EventHandle.
输入:作业集τ,当前时刻 t.
输出:更新作业的动态需求边界和关键级松弛时间.
1. getEventQueue(⋅); //获取事件队列
2. WHILE (EventQueue≠∅)
3. IF (event: J i 在关键级χ e 下执行)
4. FOR all χ χ < e ∨ d < k d i : d k χ ( )t + + ;
5. FOR all χ χ > i : dt + k χ ( ) + ;
6. END IF;
7. IF (event: J i 在关键级χ e 下完成)
χ
( )+=
8. FOR all χ ≥ χ e : dt C i (χ e ) C χ − i ( ) ;
k
i
9. END IF;
10. IF (event: J i 在关键级χ e 下超时)
11. χ e ++;
12. END IF;
13. END WHILE;
χ
χ
14. update all s and S ;
i
如算法 2 所示,EventHandle(⋅)函数用于处理系统事件并跟新系统状态.在第 3 行~第 6 行,当作业 J i 在关键
级χ e 下执行,所有低关键级、高优先级的需求边界的动态部分会受到影响.同样,由于作业 J i 的执行不会被包括
在所有高于其自身关键级χ i 的需求边界中,因此也需要累加.在算法 2 中,χ e 是作业的执行关键级,会根据作业的
实际情况不断增加(第 10 行~第 12 行).当作业在关键级χ e 完成,所有高于χ e 的需求边界会降低,增量为
C i (χ e )−C i (χ i ).当所有事件处理完成,更新所有的松弛时间,用于系统执行关键级的切换.
3.2 算法示例
考虑表 2 中由 3 个作业构成的具有 3 个关键级的作业集的调度.
(1) 在时刻 0,仅作业 J 1 就绪.由于 J 1 的关键级χ 1 =1,因此只考虑 ddbf 0 1 ()t 的取值.由公式(4)可知, ddbf 1 1 ()t =
C 1 (1)=3.在当前环境中,当 J 1 的时限 5 到达,J 1 的松弛时间为 s = d − 1 t = 1 1 3 ,显然,此时有 S = 1 s = 1 1 3 ,系
1
1
统关键级χ s =1,选择执行的作业为 J 1 .
(2) 在时刻 1,作业 J 2 到达.此时, ddbf 1 (1) 3 C= + (1) = 4,ddbf 1 (1) = 2,ddbf = 2 3 ,因此, s = 1 1,s = 1 2,s = 2 1. 此时
1 2 2 2 1 2 2
2
各关键级的松弛时间是: S = 1 min( , ) 1s s = 1 1 ,S =1.系统关键级χ s =2,选择执行的作业为 J 2 .
1 2
(3) 时刻 2,作业 J 3 到达,若 J 2 没有声明完成,J 2 的执行关键级增加至 2.此时,
ddbf 3 1 (2) = max( (1)C 1 + C 2 (1),2) C+ 3 (1) = 6,ddbf 3 2 (2) 5,ddbf= 3 3 (2) = a + 3 C 3 (3) = 6.
对应地, S = 1 s = 1 3 1,S = 2 s = 3 2 1,S = 3 s = 3 3 1 ,因此,系统关键级χ s =3,选择执行的作业为 J 3 .
(4) 在时刻 3,由于 J 3 执行但 d 3 >d 1 ,d 3 >d 2 ,因此,J 1 和 J 2 的需求边界受到影响. ddbf 1 1 (3) 5,ddbf= 2 1 (3) 3,=