多处理器实时调度的实时调度

全部展开

问题描述: 一组具有优先级关系的任务在m个处理器上运行. 任务优先级关系用“ <”表示，也就是说，如果两个任务（t1，t2）的优先级关系t1 多处理器调度，（t1，t3），（t1，t4），（t2，t6），（t3，t6），（t4，t5），（t5，t6）}}. 多处理调度是指找到最短的调度.

静态多处理器调度可以具有以下三个调度规范:

1）基本（或非抢先）调度BS（基本调度）. 在执行e799bee5baa6e997aee7ad94e58685e5aeb931333361303131的过程中不能中断任务.

2）可抢占式调度（PS），可以抢占任务，而不必基于优先级抢占.

3）通用调度（GS）. GS是一个理论概念，它允许处理器同时执行多个任务. 实际上，每个处理器一次最多只能执行一个任务. GS的前提是处理器可以在给定的时间段内将部分计算能力分配给任何任务. 并且规定同一任务不能同时在多个处理器上并行执行.

定义CA（G，k）表示用于调度A（BS，PS或GS）的k个计算图G的最小计算时间.

定理3: 抢占式调度和广义调度的最小计算时间等于任意k个处理器的计算图G，并且有

C_GS（G，k）= C_PS（G，k）

BS无法获得最短的时间表. 尽管GS可以获得最短的时间表，但这只是理论上的结果. 定理3表明PS和GS具有相同的最小计算时间，而PS在实践中是可以实现的.

一般的PS生成过程如下:

1）根据任务优先级关系绘制计算图G

2）按GS生成GS时间表（为什么？）

3）使用一种方法将GS计划替换为PS计划. 问题描述: n个任务具有不确定的到达时间，已知的计算时间c和期限D已确定动态调度的目标是使系统能够对变化的环境快速做出反应.

动态计划任务的状态可以在l-c空间中表示. 横坐标表示任务的空闲时间l（t），纵坐标表示任务的剩余时间c（t）. 任务空闲时间l（t）= D-c（t）. 图中的虚线间隔表示时间单位. 例如，t2的剩余计算时间为3，空闲时间为2，因此截止日期为3 + 2 = 5.

L-c空间将每隔一段时间刷新一次. 任务在LC空间中的位置变化具有不同的含义:

1）任务执行: 任务向下移动，c（t）变小

2）任务未执行: 任务向左移动，l（t）变小

3）任务尚未到达: 任务没有移动. 有些任务在到达之前已经得到确认，因此这些任务保留在l-c图表上，并在它们到达时被激活

4）新任务到来: 根据任务的计算时间c和空闲时间l，设置其在空间l-c中的位置

5）任务完成: 任务到达l轴多处理器调度，此时c（t）= 0

6）任务无法超时运行: 任务落在c轴的左侧，此时l（t）<0

任务期限的属性由l-c空间中的角度表示. 具有相同截止时间的任务位于称为125度的同一直线上，并且截止时间沿45度增加. t1和t3的截止时间相等，t2比t1和t3长.

在L-c空间中，可以根据EDF和LLF调度算法来调度任务. 但是，EDF和LLF并不是多处理器下的最佳算法.

定理4: 在多处理器下，如果无法预先确定任务计算时间，截止日期或到达时间，则不存在最佳调度算法.

定理4表明，基于l-c空间的多处理器动态调度算法没有最优解. 由于该算法不能保证所有任务的最后期限，因此属于软实时调度. （软硬实时调度: ）

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-186151-1.html