5.3.3 磁盘调度算法

教材导航 · 第5章

原书定位

印刷页P342起,对应PDF第353页。下文为目视整理的知识提要;完整内容见原书对照。

设磁头跨n条磁道,每条耗时m,启动耗时s,转速r转/秒,每磁道N字节,传输b字节,则:

Ts=mn+s,Tr=12r,Tt=brN,Ta=Ts+Tr+Tt.T_s=mn+s,\qquad T_r=\frac{1}{2r},\qquad T_t=\frac{b}{rN},\qquad T_a=T_s+T_r+T_t.

平均旋转延迟取半圈;rpm必须先除以60转换成转/秒。

算法选择规则易错点
FCFS按请求到达顺序公平简单,移动量可能大
SSTF选离当前磁头最近的请求局部最优,不保证总体最短,可能饥饿
SCAN沿一个方向扫描,到端点再反向需给定起始方向和磁道边界
C-SCAN单向服务,回程不服务回程移动是否计入按题意
LOOK只到该方向最远请求就反向与到物理端点的SCAN区分
C-LOOK单向服务,只在最远请求间回跳跳转仍有实际移动

原书在部分题中允许把SCAN/C-SCAN按LOOK/C-LOOK处理;计算前应明确采用的规则。总移动量为相邻位置差绝对值之和,平均除以请求数。交替编号、错位命名、缓存、预读、延迟写和优化块布局分别改善旋转等待或减少I/O请求。

FCFS调度

FCFS调度,原书P343。

SSTF调度

SSTF调度,原书P344。

SCAN调度

SCAN调度,原书P344。

C-SCAN调度

C-SCAN调度,原书P344。

LOOK调度

LOOK调度,原书P345。

C-LOOK调度

C-LOOK调度,原书P345。

调度算法比较

调度算法比较,原书P345。

交替编号

交替编号,原书P345。

错位命名

错位命名,原书P346。

对应练习

5.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P342,PDF第353页

原书对照,原书P343,PDF第354页

原书对照,原书P344,PDF第355页

原书对照,原书P345,PDF第356页

原书对照,原书P346,PDF第357页