5.3_2_磁盘调度算法

专题讲解：I/O 管理与磁盘调度

SCAN 像电梯，不会服务一个请求就随意掉头

上一课文件块最终落到磁盘。磁头当前在柱面53，请求队列 [98,183,37,122,14,124,65,67]，柱面范围0～199，SCAN 初始向上。任务写服务顺序并计算总移动量。

def scan(requests,head,low,high,direction="up"):
    lower=sorted(x for x in requests if x<head)
    upper=sorted(x for x in requests if x>=head)
    if direction=="up": order=upper+[high]+lower[::-1]
    else: order=lower[::-1]+[low]+upper
    movement=0; current=head
    for x in order:
        movement+=abs(x-current); current=x
    return order,movement

order,movement=scan([98,183,37,122,14,124,65,67],53,0,199)
assert order==[65,67,98,122,124,183,199,37,14]
assert movement==331

向上依次服务65、67、98、122、124、183，并按 SCAN 规则走到端点199再反向服务37、14。移动量为 12+2+31+24+2+59+16+162+23=331。

为何正确：同一方向上按柱面递增服务不会回头；到边界才反向，所构造顺序正是电梯扫描定义。LOOK 的区别是走到该方向最远请求183就反向，不必到199，因此移动更少。

排序占 O(n log n) 时间、O(n) 空间。典型错误：把 LOOK 顺序当 SCAN；漏算到物理端点；SSTF 每次选最近请求，平均寻道短却可能让远端请求饥饿；磁盘访问时间还含旋转延迟与传输时间，不只有寻道。

迁移答案：本例 LOOK 顺序去掉199，总移动为 (183-53)+(183-14)=299；C-SCAN 到199后回0再向上，提供更均匀等待。

本章结束。下一章进入网络，继续使用状态机和时间线方法推演分层封装、可靠传输、路由与拥塞控制。

专题讲解：磁盘调度、寻道距离与I/O路径

新困难：SCAN 必须走到端点，LOOK 在最后请求处就反向

柱面0～199，磁头初始53，待服务请求 98,183,37,122,14,124,65,67，初始向柱面增大方向。比较 SCAN、LOOK、C-SCAN 的服务顺序和总移动距离。题目明确SCAN到物理端点，LOOK只看请求边界。

def schedule(requests,head,max_cylinder,kind):
    up=sorted(x for x in requests if x>=head)
    down=sorted((x for x in requests if x<head),reverse=True)
    if kind=='LOOK': path=up+down
    elif kind=='SCAN': path=up+[max_cylinder]+down
    elif kind=='C-SCAN': path=up+[max_cylinder,0]+sorted(down)
    else: raise ValueError(kind)
    movement=sum(abs(b-a) for a,b in zip([head]+path,path))
    service=[x for x in path if x in requests]
    return service,movement,path

req=[98,183,37,122,14,124,65,67]
assert schedule(req,53,199,'SCAN')[:2]==([65,67,98,122,124,183,37,14],331)
assert schedule(req,53,199,'LOOK')[:2]==([65,67,98,122,124,183,37,14],299)
assert schedule(req,53,199,'C-SCAN')[:2]==([65,67,98,122,124,183,14,37],382)

陪算SCAN：向上服务到183后仍走到199，距离 199-53=146；再反向服务37、14，最终到14，距离 199-14=185，总331。LOOK在183立刻反向，总距 (183-53)+(183-14)=299。C-SCAN到199后回卷到0，再向上服务14、37，总距 146+199+37=382，回卷也计磁头移动。

依据：电梯方向内请求按柱面单调顺序服务；SCAN边界由物理端点定义，LOOK边界由该方向最后请求定义；C-SCAN反向回卷时不服务，随后保持同一方向。路径中相邻柱面差绝对值之和是不重不漏的移动距离不变量。

排序时间 O(n log n)、路径空间 O(n)。错误反馈：SCAN与LOOK不能混名；总移动距离要含到端点与回卷；C-SCAN回卷期间不按降序服务；初始方向不同答案不同；寻道距离不是完整I/O时间，还可能含旋转等待和传输。

迁移答案：若题目规定SCAN在当前方向无请求时可立即反向，它实际采用的是LOOK式定义，应服从题设；若磁盘回卷由硬件特殊加速且题目说不计回卷，C-SCAN需从382减去199。