计算机操作系统（第二版）课件：磁盘调度

教学内容：磁盘管理概述

磁盘调度算法

磁盘调度思考问题：

从磁盘上读一块数据，大约需要多长时间？所需时间主要包括哪几部分？

当同一时刻有多个磁盘访问请求时，如何安排访问顺序,以得到相对较短的平均访问时间？有哪些方法可以缩短磁盘读写时间？6.6.1磁盘管理概述：盘面、磁道、扇区的概念盘面号（磁头号）、柱面号（磁道号）、扇区号扇区两种编址方式：CHS方式、LBA方式LBA与CHS之间的互相转换磁盘访问时间：寻道时间、旋转延迟时间、数据传输时间的含义、各与哪些因素有关？6.6磁盘调度

6.6.1磁盘管理概述1.数据组织和格式盘面号（磁头号）：0～

M-1；柱面号（磁道号）：0～

L-1；扇区号：1～

N；

6.6磁盘调度扇区标识符字段数据字段校验字段

6.6.1磁盘管理概述1.数据组织和格式

（1）扇区编址方式CHS（Cylinder/Head/Sector，柱面/磁头/扇区）方式：

使用柱面号、磁头号和扇区号表示每个扇区，DOS中称

为“绝对扇区”表示法。

LBA（LogicalBlockAddressing，相对扇区号）方式：

相对扇区号标识扇区，以磁盘第一个扇区（0柱面、0磁头、

1扇区）作为LBA的0扇区。6.6磁盘调度

1.数据组织和格式（2）LBA与CHS的转换若L、M、N分别表示一个磁盘的柱面数（磁道数）、盘面数（磁头数）、扇区数，则第i柱面、j磁头、k扇区所对应的LBA扇区号为：若知道LBA扇区号，则对应的柱面号、磁头号、扇区号分别是：6.6磁盘调度LBA=(i*M*N)+(j*N)+k-1

柱面号：i=int(LBA

/(M*N))

磁头号：j=[LBAmod(M*N)]/N

扇区号：k=[LBAmod(M*N)]modN+1（3）存储容量

=磁头数×磁道（柱面）数×每道扇区数×每扇区字节数6.6.1磁盘管理概述

（4）LBA与CHS的转换举例6.6磁盘调度

假设一个磁盘共有100个柱面，每个柱面有8个磁道，每条磁道被分成4个扇区。若磁盘块大小与扇区大小相等，柱面、磁道、扇区的编号均从“0”开始，现用字长为16位的200个字（第0字到第199字）组成位示图来管理磁盘空间。请问：（1）文件系统发现位示图中第15字第7位为0而准备分配给某文件时，该文件会存放到磁盘的哪一块上？此块的物理位置（柱面号、磁头号、扇区号）如何？（2）删除某文件时，回收第56柱面第6盘面第3扇区的块，此时，位示图中第几字第几位应该由“1”改为“0”？答案：（1）柱面号7，磁头号5，扇区号3

（2）字号113，位号11

（4）LBA与CHS的转换讨论题解答：6.6磁盘调度

（1）块号=15*字长+7=15*16+7=247柱面号=INT(块号/每个柱面的扇区数=INT(247/(4*8))=7磁头号=INT((块号MOD每个柱面的扇区数)/每条磁道扇区数）=INT((247MOD32)/4)=5扇区号=(块号MOD每个柱面扇区数)MOD每条磁道扇区数=（247MOD32）MOD4=3（2）块号=柱面号*每个柱面的扇区数+盘面号*每条磁道扇区数+扇区号=56*32+6*4+3=1819

字号=INT(块号/字长）=INT(1819/16)=113

位号=块号MOD字长=1819MOD16=11

6.6.1磁盘管理概述2.磁盘访问时间：移动头磁盘（1）寻道时间

磁头从当前位置移动到指定磁道所需要的时间Ts=m*n+ss：启动磁臂的时间，2ms～3msm：磁头每移动一条磁道所需要的时间一般磁盘：0.2～0.3；高速磁盘：m≤0.1n：移动的磁道数。6.6磁盘调度

6.6.1磁盘管理概述2.磁盘访问时间：移动头磁盘（2）旋转延迟时间Tr

欲访问扇区旋转到磁头下面所需要的时间，粗略的认为是磁盘旋转半周的时间：

Tr

=1/2r

这里r表示旋转速度（3）传输时间Tt：

把数据从磁盘读出或向磁盘写入所需要的时间6.6磁盘调度rNbTt=可将磁盘访问时间Ta表示为：

rNbrTTsa++=21

6.6.2磁盘调度算法

当有大量磁盘I/O请求时，降低磁盘I/O服务的总时间

移臂调度：当同时有多条磁道访问请求时，确定磁道访问顺序，以减少平均寻道时间

旋转调度：当一条磁道上有多个扇区访问请求时，确定扇区访问顺序，以减少旋转延迟时间6.6磁盘调度移臂调度算法（1）先来先服务算法（FCFS）（2）最短寻道时间优先算法（SSTF）（3）扫描算法（SCAN算法，又称为电梯算法）（4）循环扫描算法（CSCAN）（5）N-Step-SCAN算法（6）FSCAN算法（FairSCAN）6.6磁盘调度6.6.2磁盘调度算法基本概念实现思路性能分析如何改进（1）先来先服务FCFS(First-Come,FirstServed)

假设当前磁道在100号磁道，磁头正向磁道号增加的方向（由外向里）移动。现依次有如下磁盘请求队列：23，376，205，132，61，190，29，4，40则磁盘调度顺序和寻道距离为：23，376，205，132，61，190，29，4，40Ts=(100-23)+(376-23)+(376-205)+(205-132)+(132-61)+(190-61)+(190-29)+(29-4)+(40-4)平均寻道距离=Ts/96.6.2磁盘调度算法6.6磁盘调度假设当前磁道在100号磁道，磁头正向磁道号增加的方向（由外向里）移动。现依次有如下磁盘请求队列：23，376，205，132，61，190，29，4，40,则磁盘调度顺序和寻道距离为：23，376，205，132，61，190，29，4，40Ts=(132-100)+(190-132)+(205-190)+(205-61)+(61-40)+(40-29)+(29-23)+(23-4)+(376-4)问题：（1）不能保证平均寻道距离最短；（2）会产生饥饿现象；（3）影响磁盘的机械寿命。（2）最短寻道时间优先算法SSTF6.6.2磁盘调度算法6.6磁盘调度（3）扫描(SCAN)算法：（又称为电梯算法）（1）磁头当前的移动方向；（2）欲访问磁道与当前磁道的距离。假设当前磁道在100号磁道，磁头正向磁道号增加的方向（由外向里）移动。现依次有如下磁盘请求队列：23，376，205，132，61，190，29，4，40,则磁盘调度顺序和寻道距离为：23，376，205，132，61，190，29，4，40Ts=(132-100)+(190-132)+(205-190)+(376-205)+(376-61)+(61-40)+(40-29)+(29-23)+(23-4)6.6.2磁盘调度算法6.6磁盘调度（4）循环扫描(CSCAN)算法：（1）磁头单向移动方向访问磁道；如从外往里（2）欲访问磁道与当前磁道的距离。假设当前磁道在100号磁道，磁头正向磁道号增加的方向（由外向里）移动。现依次有如下磁盘请求队列：23，376，205，132，61，190，29，4，406.6.2磁盘调度算法6.6磁盘调度132,190,205,376，4,23,29,40,61（5）N-Step-SCAN算法

“磁臂粘着”现象算法思想：将磁盘请求队列分成若干个长度为N的子队列；按FCFS算法依次处理子队列；每个子队列采用SCAN算法。例如：23，376，205，132，61，190，29，4，40若子队列长度N=4，则分成3个队列：23,376,205,13261,190,29,404FCFSSCAN6.6.2磁盘调度算法6.6磁盘调度队列数量不固定；每个队列长度固定（6）FSCAN算法将磁盘请求队列分成两个子队列：

①队列1：由当前所有磁盘请求形成的队列，采用SCAN算法处理

②队列2：处理队列1期间，新出现的磁盘请求

23,376,205,132，61,190,29，40,4

6.6.2磁盘调度算法6.6磁盘调度队列数量固定：两个每个队列长度不固定13当同一磁道（柱面）上有多个扇区请求时，总是选取与当前读写头最近的I/O请求，使旋转圈数最少。例：对磁盘访问的5个请求，若磁头在1号柱面，先按SCAN算法做移臂调度，再进行旋转调度，则调度顺序如下：柱面号盘面号扇区号

27753852153540636.6.3旋转调度算法：减少旋转延迟时间柱面号盘面号扇区号

5215385354063277柱面号盘面号扇区号

27752153853540636.6磁盘调度移臂调度旋转调度13思考题：假定磁盘的存取臂现在处于6#柱面上，有如表所示的6个请求等待访问磁盘，试列出最省时间的响应顺序。6.6.3旋转调度算法：6.6磁盘调度序号柱面号磁头号块号17632