操作系统-第5章-输入输出管理

操作系统

第五章输入输出管理

设备管理概述和I/O控制方式

Categoriesof1/0Devices

HumanreadabIe

MachinereadabIe

Communication

DifferencesinI/ODevices

■DataTransferRate（数据传输速率）

AppIication（应用）

CompIexityofControI（控制复杂性）

DataTransferUnit（数据传输单位）

DataRepresentation（数据表示）

ErrorConditions（错误条件）

I/O接口

■设备控制器与CPU

■设备控制器与设备

■I/O逻辑

I/O端口

TechniquesforPerforming1/0

■Programmed1/0（程序控制I/O）

■Interrupt-Driven（中断驱动）

■DMAControI（DMA控制）

Programmed1/0

■Theprocessorissuesan1/0commandtoan1/0

moduIeF1/0moduIeperformstheI/O.

■Setsappropriatebitsinthe1/0status

register.

■Nointerruptsoccur.

■ProcessorchecksstatusuntiIoperationis

compIete.

■Processisbusy-waitingfortheoperationto

compIete.

Error

condition

memory

Y八

NextInstruction

<a>l^noiframmedI/O

Iinterrupt-DrivenI/0

■Processorisiinterruptedwhen1/0moduIe

readytoexchangedata.

■Processorisfreetodootherwork.

■Noneedlesswaiting.

■Consumesalotofprocessortimebecause

everywordreadorwrittenpassesthroughthe

processor.

IssueReadWTPC*—>I/O

I>|coiTUiiandtt>

I►eIXlse'sonicUiini*

modiUc

Read5，》nJ

fromVO|1/C）一

Module

DirectMemoryAccess(DMA)

■TransfersabIockofdatadirectlytoorfrommemory.

■AninterruptissentwhenthetaskiscompIete.

■TheprocessorisonIyinvoIvedatthebeginningand

endofthetransfer.

IssueRead『卬TDMA

NockcommandIDosomething

to1A)module卜一else

Readstatus

ofDMA

moduleDMAtCPU

Nextinstruction

(c)Directmemoryaccess

DirectMemoryAccess

■TakescontrolofthesystemfromtheCPUto

transferdatatoandfrommemoryoverthe

systembus.

■Cyclestealingisusedtotransferdataonthe

systembus.

■Theinstructioncycleissuspendedsodatacan

betransferred.

■TheCPUpausesonebuseyeIe.

■Nointerruptsoccur

•Donotsavecontext.

Timr

BivakpirfntsHrvakpiMnt

11JDMAaixlInterruptBreakiM>intsDuringanInstructionC

DMA控制器的工作原理⑴

■当CPU将一块数据从某I/O设备读入内存某处或把

一块数据从内存某处写入某I/0设备时

•CPU将把相关数据次的长度通过DMA的"DataLines”

脚写入DMA的“DataCountT寄存器

•把内存起始地址和I/O设备地址通过DMA的"Data

Lines"脚写入DMA的uAdresRegisteP^寄存器

•通过DMA的“Read”脚或“Write”脚向DMA发出读或

写命令

DMA控制器的工作原理⑵

■DMA通过"DMARequest"脚和"DMAAcknowledge"脚控制相关的

I/O设备

■通过“DataLines"脚与I/O设备以及内存交换数据

■通过"AddressLines”脚寻址内存

DMA控制器的工作原理⑶

■工作完毕，DAM将通过“Interrupt”脚向CPU发出中断，CPU对本次数据传输进行善后处理。

■DMA将通过窃取CPU总线周期的方式获得总线控制权。

DMA

(a)Nln^kr-bus.DMA

Figure11.4AlternativeDMAConfigurations

DMA

(b^Sini>k*-bus.Ink^ratedDMA-l/O

Figure11.4AlternativeDMAConfigurations

DMA

(c)I/Obwt

Figure11.4AlternativeDMACcHifiuurations

I/O软件层次结构

1.用户层I/O软件

2.设备独立性软件

3.设备驱动程序

4.中断处理程序

5.硬件

应用程序I/O接口

1.字符设备接口

2.块设备接口

3.网络设备接口

4.阻塞/非阻塞I/O

EvolutionoftheI/OFunction

■Processordirectlycontrolsaperipheral

device.

■ControlIerorI/OmoduIeisadded

■ProcessorusesprogramedI/Owithout

interrupts.

■ProcessordoesnotneedtohandIedetaiIsof

externaldevices.

EvolutionoftheI/OFunction

■ControIlerorI/OmoduIewithinterrupts

,ProcessordoesnotspendtimewaitingforanI/Ooperationtobeperformed.

・DirectMemoryAccess

,BlocksofdataaremovedintomemorywithoutinvoIvingtheprocessor.

,ProcessorinvoIvedatbeginningandendonly.

EvolutionoftheI/OFunction

I/OmoduIeisaseparateprocessor：//0channe/.

1/0processor

•I/OmoduIehasitsownIocaImemory.

•It'sacomputerinitsownright.

计算机I/O子系统的组成⑴

微型和小型计算机I/O子系统的组成

计算机I/O子系统的组成⑵

I/O控制器

OperatingSystemDesignIssues

■Efficiency

•MostI/Odevicesextremelyslowcomparedtomainmemory.

•UseofmuItiprogrammingaIlowsforsomeprocessestobewaiting

onI/OwhiIeanotherprocessexecutes.

•1/0cannotkeepupwithprocessorspeed.

•SwappingisusedtobringinadditionaIReadyprocesseswhich

isanI/Ooperation.

OperatingSystemDesignIssues

■GeneraIity

•DesirabIetohandIeaIII/Odevicesinauniformmanner.

•HidemostofthedetaiIsofdeviceI/0inIower-IeveI

routinessothatprocessesandupperIeveIsseedevicesin

generaItermssuchasread,write,open,close,lock,unlock.

DeviceIndependence（设备无关性）

即，应用软件所引用的用于实现I/O操作的设备与

计算机I/O子系统中实际安装的设备没有固定的联

系。

LogicaII/ODevice

应用软件引用的用于实现I/O操作的设备。

从应用软件的角度看，逻辑I/O设备是一类具有相同或相似属性的

物理I/O设备的抽象。

逻辑I/O设备的分类

■字符设备

■也叫面向流的设备(StreanrOrientedDevice)；

■应用软件以的物9单位读写此类逻辑I/O设备。

■块设备

■也叫面向块的设备(Block-OrientedDevice)；

■应用软件以次为单位读写此类逻辑I/O设备。

OS设备管理模块的分层结构

■为了实现“通用性”这一设计目标，大多数OS的设备管理模块采用分层

结构。

■在分层结构中，上层可以屏蔽下层的实现细节

OS设备管理模块的分层结构模型

■典型的两层结构：

•设备硬件无关层，实现设备映射功能,把逻辑

I/O设备映射到物理I/O设备

•设备硬件相关层，实现设备驱动功能,控制物

理I/0设备以便完成实际的I/0操作

OS设备管理模块的分层结构模型

■f

I

■M>

“<sontrv»l“<ac>ntrvil

<t»>pa.rt

urv11.SAIVIocWlofI/OOri*-uiiix4ati<»n

引例

■靛：一个用户进程将从磁带上读入若干块数据（每块100字节）;

数据块装入用户进程地址空间中的一个数据区，其虚拟地址为

1000^1099（100字节）

请问、如果从磁带上读进一块数据并直接把它送入用户进程的工

作区，会有什么问题？

NoBuffering

OperatingSj,stemUserProcess

In

I/ODeMce

(a)Nobuffering

Problems

■ProcessesmustwaitforI/OtocompIetebeforeproceeding。显

然，用户进程的运行速度将受制于磁带机的工作速度

■这种I/O方法会影响OS的交换策略。若OS决定挂起该用户进程，其虚地址

1000〜1099必须驻留在内存，否则，数据可能丢失，故进程不能被完整地交

换出内存

■可能会导致毕龙程死领

阻塞

提高用户进程运行效率的方法

许多OS通过引入//08"尸〃/他来提高用户进程的运行效率、缩短其周

转时间。

I/OBuffering

■核心思想：在内存中建立I/O缓冲区

■缓存从输入设备流入内存的数据

■缓存从内存流向输出设备的数据

I/OBuffering

■Block-oriented

■InformationisstoredinfixedsizedbIocks

■Transfersaremadeablockatatime

■Usedfordisksandtapes

■Stream-oriented

■Transferinformationasastreamofbytes

■byte：每个buffer缓存一个字符（字节），键盘输入等

■Iine：每个buffer缓存一个字符串或长度可变的多个字节，用于显示输出、

打印输出等

ReadAheadandWritePostponing

■ReadAhead（提前读）

'用户进程从I/O缓冲区取走前一个数据后立即发出对下一

个数据的输入请求；OS将在适当的时候响应该请求，把

需要的数据读入I/O缓冲区。

■WritePostponing（延后写）

-当用户进程请求输出数据时，。期务很快把用户进程请求

输出的数据从用户进程的工作区取走，将其暂存在I/O缓

冲区中；直到用户进程指定的输出设备空闲时，OS才把

暂存在I/O缓冲区中的数据写入用户进程指定的输出设备

±o

I/OBuffering

■SingIeBuffer（单缓冲区）

■DoubIeBuffer（双缓冲区）

■CircularBuffer（循环缓冲区）

SingIeBuffer

OperatingSystemIserProcw

I/ODeMce

(b)SinglehufTerlng

Figure11.6I/OBufTerinvSchemes(input)

SingIeBuffer

■Operatingsystemassignsabufferinmainmemoryforan

I/Orequest.

■Block-oriented

■Inputtransfersmadetobuffer

■Blockmovedtouserspacewhenneeded

■Anotherblockismovedintothebuffer

•Readahead

SingIeBuffer

■Block-oriented

•UserprocesscanprocessoneblockofdatawhiIenextblock

isreadin.

•SwappingcanoccursineeinputistakingpIaceinsystem

memory,notusermemory.

•Operatingsystemkeepstrackofassignmentofsystembuffers

touserprocesses.

SingIeBuffer

■Stream-oriented

•UsedaIineattime.

•UserinputfromaterminaIisoneIineatatimewith

carriagereturnsignaIingtheendoftheIine.

•OutputtotheterminaIisoneIineatatime.

若一块数据从外部设备输入到内存所花费的时

间为T,在内存中移动所花费的时间为M,被用

户进程加工处理所花费的时间为%则

■在没有使用I/O缓冲区的情况下，平均每块数据的

处理时间近似为：T+C

-在使用单I/O缓冲区的情况下，平均每块数据的处

理时间近似为：max(T,C)+M

■可见，相对于没有使用I/O缓冲区的情形，引入单I/O

缓冲区后，用户进程的运行效率得到了提高。

■然而，如果用户进程在对有关数据进行加工处理时并不

释放I/O缓冲区，那么用户进程的性能并不能得到改善。

■此外，如果T远远大于C,即外部设备的I/O速度比用

户进程的计算速度慢得多，那么即使引入单I/O缓冲区,

用户进程的性能也几乎没有得到改善。

DoubIeBuffer

■Usetwosystembuffersinsteadofone.

■AprocesscantransferdatatoorfromonebufferwhiIe

theoperatingsystememptiesorfiIIstheotherbuffer.

DoubIeBuffer

(c)DoublebufTerl华

DoubIeBuffer

■外部设备和应用进程常常交替引用DoubIeBuffer

■DoubIeBuffer也称为BufferSwapping（缓冲交换）

SingIeBuffervs.DoubIeBuffer

■使用双i/o缓冲区，即使用户进程在对有关数据进行加工处

理时不释放相关的i/o缓冲区，用户进程的性能也能得到改

善。

■与单I/O缓冲区类似,如果T远远大于C,即外部设备的I/O

速度比用户进程的计算速度慢得多，那么即使引入双I/O缓

冲区，用户进程的性能也几乎没有得到改善。

■缓和外部设备的I/O速度与用户进程的计算速度不匹配的一

种有效的办法是，在外部设备和用户进程之间设立多个I/O缓

冲区。

CircularBuffer

■Morethantwobuffersareused.

■EachindividuaIbufferisoneunitinacircuIarbuffer.

■Usedwhen1/0operationmustkeepupwithprocess.

CircularBuffer

OperatingSystemIserProcess

l/ODeilce

(d)Circularhuflcrlni*

Figure11.6I/OBufTerinvSchemes(input)

DiskCache

■Bufferinmainmemoryfordisksectors,不是一种硬件设施

■Contsinsacopyofsomeofthesectorsonthedisk.

■其组织形式基于程序引用的局部性原理。

工作原理

■当用户进程请求从磁盘读入一个扇区时，系统首

先在diskcache中寻找该扇区的副本

•如果能够找到，那么系统将从diskcache中取出该扇

区的副本并返给用户进程；

•否则，系统首先从磁盘上读入该扇区并在diskcache

中为其建立一个副本，然后将该副本返给用户进程。

工作原理（续）

■当用户进程请求向磁盘上写出一个扇区时，系统同样首先在disk

cache中寻找该扇区的副本

•如果能够找到，那么系统将根据用户进程的请求修改该扇区的副本；

•否则，系统同样首先从磁盘上读入该扇区并在diskcache中为其建立一个

副本，然后根据用户进程的请求修改该副本。

磁盘高速缓存的数据安全性

DiskCache中的数据写出到磁盘：

1.在系统空闲或需要淘汰被写的缓存空间时进行写。

2.周期性地进行写。

3.立即写回，称为“写穿透高速缓存"(writethrough),相当于只有

读缓存而没有写缓存。

设计问题

■当用户进程请求从磁盘上读入一个扇区时，如果系统能够

在diskcache中找到该扇区的副本,那么系统如何把该副本

提交给用户进程？

■当系统需要从磁盘上读入一个扇区并在diskcache中为其建

立一个副本时,如果diskcache没有空闲空间,那么系统使

用何种策略从diskcache中选择一个被置换扇区？

向用户进程提交扇区副本的方法

■如果系统不允许用户进程访问diskcache,那么系统将把

用户进程需要的扇区从diskcache中复制到用户进程的工

作区。

■如果系统允许用户进程访问diskcache,那么系统将把

用户进程需要的扇区副本在diskcache中的位置指针传递

给用户进程。

扇区置换算法

■LeastRecentlyUsed（LRU置换算法）

•Theblockthathasbeeninthecachethe

Iongestwithnoreferencetoitisreplaced

■LeastFrequentlyUsed（LFU置换算法）

•Theblockthathasexperiencedthefewest

referencesisreplaced

LeastRecentIyUsed

■Thecacheconsistsofastackofblocks.

■MostrecentIyreferencedbIockisonthetopofthestack.

■WhenabIockisreferencedorbroughtintothecache,it

isplacedonthetopofthestack.

LeastRecentIyUsed

■Theblockonthebottomofthestackisremovedwhena

newblockisbroughtin.

■Blocksdon'tactuaIlymovearoundinmainmemory.

■Astackofpointersisused.

LeastFrequentlyUsed

■Acounterisassociatedwitheachblock.

■CounterisincrementedeachtimebIockaccessed.

■BlockwithsmaIIestcountisseIectedforrepIacement.

■SomebIocksmaybereferencedmanytimesinashortperiodoftimeandthennot

neededanymore.

Frequency-BasedRepIacement

AIgorithm

■系统把diskcache中的所有扇区组成一个栈：位于栈顶的扇区最近才被访

问过；而位于栈底的扇区最久没有被访问过。

■系统从中间某个位置把diskcache中的栈分成两个部分：靠近栈顶的部分

称为NewSection,靠近栈底的部分称为0IdSectiono

■系统为diskcache中的每个扇区设置一个引用计数器。

Frequency-BasedRepIacement

AIgorithm

■当系统从磁盘上把一个新扇区读入diskcache中时,

把该扇区放在diskcache的栈顶，并把该扇区的引用

计数器置1。

■当diskcache中的某个扇区被用户进程访问时，系统

将把该扇区从其原来的位置移到diskcache的栈顶，同

时判断该扇区原来是否位于栈的NewSection：若是,

该扇区的引用计数器的值保持不变；否则，该扇区的引

用计数器的值被加1。

NewSectionOldSection

A<

Frequency-BasedRepIacement

AIgorithm

■当需要从diskcache中选择一个被置换扇区时，系统将从位于栈的0IdSection中的所有扇区中

选择引用计数器值最小的那个扇区。

■如果位于栈的0IdSection中的所有扇区其引用计数器的值均相等,那么系统将选择位于disk

cache栈底的那个扇区。

基于频率置换算法的不足

■一个新的扇区被读入diskcache时，它将被置于栈的NewSection中,其引用计数器被置1。

■只要该扇区不离开NewSection,它的引用计数器的值就一直保持为1。

■当该扇区最终离开NewSection时，它的引用计数器的值仍然为1。

基于频率置换算法的不足（续）

■如果此时该扇区不能在系统进行扇区置换之前很快地被

用户进程引用，那么该扇区很可能被置换出去。

■这意味着，一个在离开NewSection时不能很快被引用

的扇区（即使是一个经常被引用的扇区）根本没有机会

增加自己的引用计数。

■显然，这对一个经常被引用但在离开NewSection时不

能很快被引用的扇区是不合理的。

基于频率置换算法的改进

把diskcache中的栈分成三个部分

■NewSection

■MiddIeSection

■0IdSection

MiddleSection

SPOOLing技术

核心思想是：在快速辅助存储设备中建立I/O缓冲

区，用于缓存从慢速输入设备流入内存的数据，

或缓存从内存流向慢速输出设备的数据。

用户进程注：►数据流

<—>控制流

逻辑设备管理模块

输入程序输出程序

SPOOLing技术实现原理示意图

DiskI/O

■大容量磁盘

-每条磁道上都有一个读/写磁头，可以并行读/写

■中小型磁盘设备

-每个盘面配置一个磁头，只能串行读/写

-为了读/写某磁道、某扇区的数据，首先让磁头伸/缩寻找指定磁道,

再旋转磁盘，将相应扇区定位到磁头下面

DiskPerformanceParameters

■Toreadorwrite,thediskheadmustbe

positionedatthedesiredtrackandatthe

beginningofthedesiredsector.

•Seektime（寻道时间）.

•RotationaIdelayorrotationaIlatency（®^$^延

迟）.

•Accesstime（访问时间），sumofseektimeand

rotationaIdelay,thetimeittakestogetin

positiontoreadorwrite.

•Datatransfer,occursasthesectormovesunder

thehead.

TimingofaDiskI/OTransfer

WaltforWaltforSeekRotationalData

DeviceChannelDela)Transfer

<DzkxBusy

Figure11.7TimingofaDiskI/OTransfer

SeekTime

Timeittakestopositiontheheadatthedesiredtrack.

假设

Ts为寻道时间，

s为磁盘启动时间，

m为与磁臂移动速度相关的常数，

n为当前磁道到指定磁道的距离（即磁臂移动所经过的磁道数）

那么Ts=mXn+s

RotationaIDelay

Timeittakesforthebeginningofthesectortoreach

thehead.

假设

Tr为旋转延迟，r为磁盘转速(转数/单位时间)

那么

Tr=1/(2r)

例：

1•对于一个转速为3600rpm的硬盘而言，其每旋转一周的时间为16.7ms,其

平均旋转延迟为8.3mso

2•对于一个转速为300rpm的软盘而言，其每旋转一周的时间为200ms,其平

均旋转延迟为100ms。

TransferTime

传输时间,指从磁盘上读数据或向磁盘上写数据所花费的时间

假设

T为传输时间，

b为传输的字节数，

N为每个磁道上存放的字节数，

r为磁盘转速(转数/单位时间)

那么

T=b/(rXN)

TotaIAverageAccessTime

Ta=Ts+Tr+T

RotationaIPositionaISensing（RPS,旋转定位感

知）

■磁盘驱动器发出寻道命令后便释放相关的通道控制器，以便系统用它来处

理其它I/O操作。

■当磁臂（磁头）移到指定磁道时，磁盘驱动器驱动磁盘旋转，把指定扇区的

起始位置定位到磁臂（磁头）下。

■当指定扇区的起始位置定位到磁臂（磁头）下，磁盘驱动器重新申请通道控

制器，建立到主机的通路。如果请求失败，磁盘驱动器将驱动磁盘旋转一

周，再申请通道控制器。

ExampIe

■假定、一个硬盘的扇区长度为512个字节,磁道长度为

32个扇区,平均寻道时间为20nls,传输速率为1MB/s,

转速为3600rpm。显然,如果一个长度为128K个字节的

文件存放在该硬盘上，那么该文件将在该硬盘上占用256

个扇区。

■遗：如果系统从该硬盘上完整地读入该文件，将花

费多长时间？

若文件连续地存放在硬盘的8个相邻的磁道上，那么系统完整地读入该文

件需要花费的时间；

(20+8.3+16.7)+(8.3+16.7)X7=220ms

若文件随机地存放在硬盘的256个扇区上，那么读

入该文件需要花费的时间：

(20+8.3+0.5)X256=7373ms

比较与分析

比较前面两种结果可以发现：

■如果文件的存储方式不同，系统访问文件的效率就不同；即，文件

的存储方式影响着系统访问文件的效率。

■文件的存储方式对系统访问文件效率的影响主要在于:访问文件总

的寻道时间和总的旋转延迟。

结论

当系统访问一组磁盘扇区时，如果能够减少总的

寻道时间和总的旋转延迟，那么系统的访问效率

将得到提高。

DiskScheduIingPoIicies

■ForasingIedisktherewiIIbeanumberofI/Orequests.

■Ifrequestsareselectedrandomly,wewiIIgettheworst

possibIeperformance.

常见的磁盘调度策略

Table11.3DiskSchedulingAlgorithms[WIED87]

NameDescriptionRemarks

Selectionaccordingtorequestor

RSSRandomschedulingForanalysisandsimulation

FIFOFirstinfirstoutFairestofthemall

PRIPrioritybyprocessControloutsideofdiskqueue

management

LIFOLastinfirstoutMaximizelocalityand

resourceutilization

Selectionaccordingtorequesteditem:

SSTFShortestservicetimefirstHighutilization,smallqueues

SCANBackandforthoverdiskBetterservicedistribution

C-SCANOnewaywithfastreturnLowerservicevariability

N-»tep-SCANSCANofAArecordsatatimeServiceguarantee

FSCANN-rtep-SCANwithNgqueueLoad-sensitive

sizeatbeginningofSCAN

cycle

基于请求者属性的磁盘调度策略

■RandomScheduIingStrategy（RSS,随机调度策略）

■FirstInFirstOutStrategy（FIFO,先进先出策略）

■Priority-BasedStrategy（PRI,基于优先级策略）

■LastInFirstOutStrategy（LIFO,后进先出策略）

RandomScheduIingStrategy

■随机地满足各个进程对磁盘的读写请求

■该策略性能最差。可用作评估其它磁盘调度策略

First-in,First-out(FIFO)

■ProcessrequestsequentiaIIy.

■FairtoaIIprocesses.

■ApproachesrandomscheduIingin

performanceiftherearemanyprocesses.

Priority-BasedStrategy

■GoaIisnottooptimizediskusebuttomeetother

objectives.

■Shortbatchjobsmayhavehigherpriority.

■Providegoodinteractiveresponsetime.

Last-in,First-out

■Goodfortransactionprocessingsystems.

■Thedeviceisgiventothemostrecent

usersothereshouIdbeIittIearm

movement.

■PossibiIityofstarvationsinceajobmay

neverregaintheheadoftheIine.

基于被请求扇区位置的磁盘调度策略

■SSTF算法

■SCAN算法

■C-SCAN算法

■N-step-SCAN算法

■FSCAN算法

ShortestServiceTimeFirst（最短寻道时间优先）

■SeIectthediskI/Orequestthatrequirestheleast

movementofthediskarmfromitscurrentposition.

■AIwayschoosetheminimumSeektime.

ShortestServiceTimeFirst

■保证在满足两次磁盘读写请求之间磁头移动距离最

小，但并不保证在满足一组磁盘读写请求时总的磁

头移动距离最小

■该算法的性能比FIFO策略的性能好

■当不断有新的磁盘读写请求被提交时，该算法可能

会导致饿死现象。

SCAN（扫描算法、电梯调度法）

■Armmovesinonedirectiononly,satisfyingaII

outstandingrequestsuntiIitreachesthelasttrackin

thatdirection.

■Directionisreversed.

SCAN

■该算法的性能与SSTF算法的性能非常接近；但与

SSTF算法相比，该算法避免了饿死现象

■如果当磁头刚刚从靠近磁盘某边的某个磁道上移

过并向磁盘另一边移动时，恰好有一个进程请求

访问该磁道，那么该请求将被严重推迟。

C-SCAN（单向扫描算法）

■RestrictsscanningtoonedirectiononIy.

■WhentheIasttrackhasbeenvisitedinonedirection,the

armisreturnedtotheoppositeendofthediskandthe

scanbeginsagain.

c-SCAN

如果当磁头刚刚从靠近磁盘某边的某个磁道上移过

并向磁盘另一边移动时，恰好有一个进程请求访问

该磁道，那么该请求将被延迟：

「若使用SCAN算法：2T

「使用C-SCANM法：T+Smax

其中，T为磁头从磁盘的一边扫描到另一边所花费的时间，

Smax为磁头从磁盘的一边直接返回另一边所花费的时间；通

常.T>>Smax<>

N-step-SCAN

■基于各个磁盘读写请求的提交次序把所有磁段读写请求组织在若干队列

中；其中，每个队列包含N个磁盘读写请求；

■如果存在一个长度小于N的磁盘读写请求队列，那么当一个新的磁盘读写

请求到达时系统将把它加入到该队列中；

N-step-SCAN(continue)

■如果不存在一个长度小于N的磁盘读写请求队列，那么当一个新的磁盘

读写请求到达时系统将为其建立一个新的队列；

■系统将使用FIFO策略依次处理每个磁盘读写请求队列；

■系统将使用SCAN算法处理每个队列中的磁盘读写请求。

■该算法避免了“磁臂粘着(ArmStickiness)”现象。

FSCAN

■Twoqueues,onequeueisemptyfornewrequest

■当前所有磁盘读写请求被组织在第一个队列中；系统将使用

SCAN算法处理该队列中的磁盘读写请求；

■在系统处理第一个队列中的磁盘读写请求时，如果有新的磁

盘读写请求到达，那么新的磁盘读写请求将被组织在第二个

队列中；

■一旦第一个队列中的磁盘读写请求被处理完毕，系统便转向

第二个队列以便使用SCAN算法处理其中的磁盘读写请求；

■上述第二步和第三步将被系统重复使用。

ExampIe

■侬：当前有9个磁盘读写请求；这9个磁盘读写请求要访问的

磁道号按照各个磁盘读写请求到达的次序依次为：55、58、39、

18、90、160、150、38、184。此外，磁头当前位于100号磁道

上。如果系统使用SCAN算法或C-SCAN算法，那么我们还假定磁

头当前的移动方向为磁道号增长的方向。

■跑如果系统分别使用FIFO策略、SSTF算法、SCAN算法、C-

SCAN算法调度磁盘，那么系统处理这9个磁盘读写请求时磁头

的平均寻道长度为多少？

FIFO

被访问的磁道号移动距离（磁道数）

5545

583

3919

1821

9072

16070

15010

38112

184146

总的寻道长度498

平均寻道长度553

SSTF

被访问的磁道号移动距离（磁道数）

9010

58