调度算法学习卡片

先来先服务 (FCFS)

算法思想

按照作业/进程到达的先后顺序提供服务，类似排队机制

特点

• 非抢占式算法
• 实现简单，公平性强
• 对短作业不利（长作业后的短作业等待时间长）

计算公式

• 周转时间 = 完成时间 - 到达时间
• 带权周转时间 = 周转时间 / 运行时间
• 等待时间 = 周转时间 - 运行时间

缺点

可能导致短作业的带权周转时间过大

短作业优先 (SJF)

算法思想

优先服务要求服务时间最短的作业/进程

变体形式

• 非抢占式 (SJF/SPF) - 默认版本
• 抢占式 (SRTN，最短剩余时间优先)

特点

• 能获得"较短"的平均等待时间和周转时间
• 对长作业不利，可能导致饥饿现象
• 默认指非抢占式版本

重要细节

• "最短平均时间"需加"所有进程同时可运行"的前提条件
• 抢占式版本(SRTN)表现更优
• 依赖用户提供的运行时间数据，存在用户虚拟风险

高响应比优先 (HRRN)

算法思想

综合考虑等待时间和要求服务时间

响应比公式

响应比 = (等待时间 + 要求服务时间) / 要求服务时间

(该值总是 ≥1)

特点

• 非抢占式算法
• 不会导致饥饿现象
• 综合了FCFS和SJF的优点
• 长作业随着等待时间增加响应比会提高

调度过程示例

• 0时刻只有P1到达，直接执行7个单位
• 7时刻计算各进程响应比，选择最高者执行
• 当要求服务时间相同时，等待时间长的进程优先

三种算法对比

维度	FCFS	SJF	HRRN
公平性	最高	最低	中等
性能指标	一般	较好 (SRTN最优)	折中
饥饿问题	无	可能发生	无
考虑因素	等待时间	运行时间	两者兼顾