进程调度算法
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每次必须完成的时间:
任务调度情况: