进程调度算法

非抢占方式

---

批处理系统：

先来先服务（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每次必须完成的时间：

任务调度情况：