12 March 2014

非抢占方式


批处理系统:

先来先服务(FCFS)

基于时间片的轮转调度算法

将就绪进程按先来先服务的原则排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片(从几ms到几百ms)。当执行时间片用完时,由一个计数器发出时钟中断请求,调度进程便根据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片。

实时系统:

非抢占式最早截止时间优先EDF(Earliest Deadline First)

用于非周期实时任务,根据任务的截止时间来确定任务的优先级。如下图:

抢占方式


批处理系统:

短作业优先

高优先权优先:静态优先权、动态优先权(高响应比优先权:优先权=(等待时间+要求服务时间)/要求服务时间)

多级反馈队列:

如果处理机正在第i队列中为某进程服务时,有新进程进入优先权较高的队列,则此时新进程将抢占正在运行进程的处理机,调度程序将把正在运行的进程放回第i个队列的末尾。

实时系统:

抢占式最早截止时间优先EDF(Earliest Deadline First)

用于周期实时任务。例如:任务A的到达时间为0、20、40、…,对应的最后期限为20、40、60、…,任务B的到达时间为0、50、100、…,

任务 A B
到达时间 0、20、... 0、50、...
截止时间 20、40、... 50、100、...
周期时间 20ms 50ms
每个周期的处理时间 10ms 25ms

调度序列(序号表示程序的执行周期):

最低松弛度优先LLF(Least Laxity First)

任务松弛度 = 任务的最迟截止时间 - 任务的执行时间,值小的优先级高。

任务A和B每次必须完成的时间:

任务调度情况: