1、Operating SystemOperating SystemPage 12022-5-30Operating SystemOperating SystemPage 22022-5-30q设备分配中的数据结构设备分配中的数据结构q设备分配时应考虑的因素设备分配时应考虑的因素q设备独立性设备独立性q独占设备的分配程序独占设备的分配程序qSPOOLing技术技术Operating SystemOperating SystemPage 32022-5-30q在多道程序环境下，系统中的设备所有进程共享，在多道程序环境下，系统中的设备所有进程共享，为为防止防止进程对系统资源的进程对系统资源的无序竞争无
2、序竞争，必须由系统，必须由系统统一分配统一分配设备设备q某进程向系统提出某进程向系统提出I/O请求时，设备分配程序按请求时，设备分配程序按一定策略一定策略分配设备、控制器和通道，形成一条数分配设备、控制器和通道，形成一条数据传输通路，以供主机和设备间信息交换据传输通路，以供主机和设备间信息交换q为实现设备分配，系统中应设置相应的数据结构，为实现设备分配，系统中应设置相应的数据结构，对每台设备、通道、控制器的情况进行登记对每台设备、通道、控制器的情况进行登记Operating SystemOperating SystemPage 42022-5-305.4.1 设备分配中的数据结构设备分配中的数
3、据结构 1. 设备控制表设备控制表DCT2. 控制器控制表控制器控制表COCT3. 通道控制表通道控制表CHCT4. 系统设备表系统设备表SDT Operating SystemOperating SystemPage 52022-5-301. 设备控制表设备控制表DCT设备类型设备类型 type设备标识符：设备标识符：deviceid设备状态：等待设备状态：等待/ /不等待不等待 忙忙/ /闲闲指向控制器表指向控制器表COCTCOCT的指针的指针重复执行次数或时间重复执行次数或时间设备队列的队首指针设备队列的队首指针DCT 1DCT 2DCT n设设备备控控制制表表集集合合每个设备一张，记录
4、本设备的情况每个设备一张，记录本设备的情况正使用，则忙标志正使用，则忙标志置置1；若与其相连的；若与其相连的控制器或通道忙，控制器或通道忙，则等待标志置则等待标志置1请求本设备未满请求本设备未满足的进程足的进程PCB队队列列Operating SystemOperating SystemPage 62022-5-302. 控制器控制表、控制器控制表、 通道控制表通道控制表控制器标识符：控制器标识符：controllerid控制器状态：忙控制器状态：忙/ /闲闲与控制器连接的通道表指针与控制器连接的通道表指针控制器队列的队首指针控制器队列的队首指针控制器队列的队尾指针控制器队列的队尾指针通道标识
5、符：通道标识符：channelid通道状态：忙通道状态：忙/ /闲闲与通道连接的控制器表首址与通道连接的控制器表首址通道队列的队首指针通道队列的队首指针通道队列的队尾指针通道队列的队尾指针(a) 控制器表控制器表COCT(b) 通道表通道表CHCT一个控制器一张一个控制器一张一个通道一张一个通道一张Operating SystemOperating SystemPage 72022-5-30q系统设备表系统设备表SDT 系统系统设备表设备表SDT表目表目 1表目表目 i设备类设备类设备标识符设备标识符DCT驱动程序入口驱动程序入口整个系统一张，记录已被连接到系统中的所有物理设备的情况整个系统一
6、张，记录已被连接到系统中的所有物理设备的情况Operating SystemOperating SystemPage 82022-5-30q设备分配中的数据结构设备分配中的数据结构q设备分配时应考虑的因素设备分配时应考虑的因素q设备独立性设备独立性q独占设备的分配程序独占设备的分配程序qSPOOLing技术技术Operating SystemOperating SystemPage 92022-5-305.4.2 设备分配时应考虑的因素设备分配时应考虑的因素 为了使系统有条不紊地工作，系统在进行设备为了使系统有条不紊地工作，系统在进行设备分配时，应考虑这样几个因素：分配时，应考虑这样几个因素：
7、（1）设备的固有属性；）设备的固有属性；（2）设备分配算法；）设备分配算法；（3）设备分配的安全性；）设备分配的安全性；（4）设备独立性。）设备独立性。Operating SystemOperating SystemPage 102022-5-301. 设备的固有属性设备的固有属性v独占性独占性一段时间内，只允许一个进程独占，大多数低度速一段时间内，只允许一个进程独占，大多数低度速/ /设备都属于独享设备设备都属于独享设备v共享性共享性允许多个进程同时共享，如磁盘、磁鼓之类的外存允许多个进程同时共享，如磁盘、磁鼓之类的外存储器，既具有很能大的存储容量，其定位操作的时储器，既具有很能大的存储容量
8、，其定位操作的时间又短间又短v可虚拟性可虚拟性独占设备经某种技术处理，改造成虚拟设备，把一独占设备经某种技术处理，改造成虚拟设备，把一台输入机虚拟为几台台输入机虚拟为几台“虚拟虚拟”的输入机。例如：为的输入机。例如：为了提高设备利用率引入了脱机输入输出或采用了提高设备利用率引入了脱机输入输出或采用SPOOLing技术，变一台为技术，变一台为“多台设备多台设备”缺点：设备得缺点：设备得不到充分利用，不到充分利用，可能产生死锁可能产生死锁Operating SystemOperating SystemPage 112022-5-30q设备分配策略设备分配策略v独占设备独占设备防止死锁防止死锁v共享
9、设备共享设备由于同时有多个进程同时访问，且访问频繁，就会由于同时有多个进程同时访问，且访问频繁，就会影响整个设备使用效率，影响系统效率。因此要考影响整个设备使用效率，影响系统效率。因此要考虑多个访问请求到达时服务的顺序，使平均服务时虑多个访问请求到达时服务的顺序，使平均服务时间越短越好。间越短越好。注意各进程的访问次序进行合理调度注意各进程的访问次序进行合理调度v虚拟设备虚拟设备Operating SystemOperating SystemPage 122022-5-302. 设备分配算法设备分配算法v先来先服务先来先服务v优先级高者优先优先级高者优先3. 设备分配中的安全性设备分配中的安全
10、性v安全分配方式安全分配方式每当进程发出每当进程发出I/O请求后，便进入阻塞状态，请求后，便进入阻塞状态，I/O操操作完成后唤醒作完成后唤醒优点：摒弃了优点：摒弃了 “请求和保持请求和保持”条件，不会产生死锁条件，不会产生死锁v不安全分配方式不安全分配方式 进程发出进程发出I/O请求后仍继续运行，继续申请请求后仍继续运行，继续申请I/O设备设备优点：可操作多个设备，推进迅速优点：可操作多个设备，推进迅速缺点：推进缺点：推进速度缓慢速度缓慢缺点：可能缺点：可能产生死锁产生死锁Operating SystemOperating SystemPage 132022-5-30q基本的设备分配程序基本的
11、设备分配程序v分配设备分配设备v分配控制器分配控制器v分配通道分配通道Operating SystemOperating SystemPage 142022-5-30设备设备1设备设备2设备设备3设备设备4设备设备5设备设备6设备设备7控制器控制器1控制器控制器2控制器控制器3控制器控制器4通道通道1通道通道2存储器存储器分配设备分配设备1分配控制器分配控制器1分配通道分配通道1申请设备申请设备1按设备物理名查按设备物理名查SDT设备忙？设备忙？根据安全策略进行分配根据安全策略进行分配由由DCT查查COCT分配控制器分配控制器由由COCT查查CHCT分配通道分配通道否是由由SDT查设备查设备
12、DCTOperating SystemOperating SystemPage 162022-5-30q设备分配程序的改进设备分配程序的改进v基本分配程序的问题基本分配程序的问题进程以物理设备名提出进程以物理设备名提出I/O请求请求采用单通路采用单通路I/O系统结构，容易产生瓶颈系统结构，容易产生瓶颈v改进方案改进方案增加设备独立性增加设备独立性 考虑多通路情况考虑多通路情况为进程为进程P P分配所需的分配所需的I/OI/O设备设备从从SDTSDT表查该类设备的控制表表查该类设备的控制表DCTDCT不忙不忙不安全不安全分配此设备给进程分配此设备给进程P P不忙不忙不忙不忙分配此控制器给进程分配
13、此控制器给进程P P分配此通道给进程分配此通道给进程P P启动启动I/O,I/O,进行进行具体的具体的I/OI/O操作操作忙忙进程进程P P的的PCBPCB放入放入此设备的等待队列此设备的等待队列YN忙忙进程进程 P P 的的 PCB PCB 放入放入此控制器的等待队列此控制器的等待队列YNY忙忙Y进程进程P P的的PCBPCB放入此放入此通道的等待队列通道的等待队列NYNN多通多通路设路设备分备分配流配流程示程示意图意图由由DCTDCT检查该设备忙否检查该设备忙否? ?检查分配此设备的安全性检查分配此设备的安全性? ?最后一个最后一个DCT?DCT?最后一个最后一个COCT?COCT?最后一
14、个最后一个DCT?DCT?此设备连接的此设备连接的COCTCOCT忙否忙否? ?此控制器连接的此控制器连接的CHCTCHCT忙否忙否? ?最后一个最后一个COCT?COCT?最后一个最后一个CHCT?CHCT?Operating SystemOperating SystemPage 182022-5-30q设备分配中的数据结构设备分配中的数据结构q设备分配时应考虑的因素设备分配时应考虑的因素q设备独立性设备独立性q独占设备的分配程序独占设备的分配程序qSPOOLing技术技术Operating SystemOperating SystemPage 192022-5-30硬件不断发展，硬件不断发
15、展，CPU速度的提高、系统规模扩大，人机速度的提高、系统规模扩大，人机矛盾严重，如何解决？矛盾严重，如何解决？输入设备外围机磁盘主机外围机输出设备磁带磁带磁带磁带Operating SystemOperating SystemPage 202022-5-301. 什么什么是是SPOOLing技术技术v为了缓和为了缓和CPU的高速性与的高速性与I/O设备低速性间的设备低速性间的矛盾而引入了矛盾而引入了脱机输入脱机输入、 脱机输出脱机输出技术技术v在多道程序环境下，其中的一道程序模拟脱在多道程序环境下，其中的一道程序模拟脱机输入时的外围控制机功能机输入时的外围控制机功能v在主机的直接控制下，实现脱
16、机输入、在主机的直接控制下，实现脱机输入、 输出输出功能，此时的外围操作与功能，此时的外围操作与CPU对数据的处理对数据的处理同时进行同时进行v把这种在联机情况下实现的同时外围操作称把这种在联机情况下实现的同时外围操作称为为SPOOLing(Simultaneaus Periphernal Operating On-Line)，或称为，或称为假脱机操作假脱机操作Operating SystemOperating SystemPage 212022-5-302. SPOOLing系统的组成系统的组成v输入井和输出井输入井和输出井在磁盘上的两个存储空间在磁盘上的两个存储空间输入井模拟脱机输入，暂存
17、输入数据输入井模拟脱机输入，暂存输入数据输出井模拟脱机输出，暂存输出数据输出井模拟脱机输出，暂存输出数据v输入缓冲区和输出缓冲区输入缓冲区和输出缓冲区用来缓和用来缓和CPU与磁盘之间的速度的矛盾与磁盘之间的速度的矛盾v输入进程输入进程SPi和输出进程和输出进程SPo模拟脱机模拟脱机I/O时的外围控制机时的外围控制机Operating SystemOperating SystemPage 222022-5-30输入进程 输入进程 SPi输入进程 输入进程 SPo输入缓冲区 输入缓冲区 Bi输出缓冲区 输出缓冲区 Bo输入井输入井输出井输出井磁盘磁盘输入设备输入设备输出设备输出设备Operatin
18、g SystemOperating SystemPage 232022-5-303. 共享打印机共享打印机v打印机为打印机为独占独占设备，利用设备，利用SPOOLing技术，技术，可将之改造为可将之改造为共享共享设备设备v用户请求打印时，用户请求打印时，SPOOLing系统处理如下系统处理如下由输出进程在输出井中为之申请一个空闲由输出进程在输出井中为之申请一个空闲磁盘块区，磁盘块区， 并将要打印的数据送入其中并将要打印的数据送入其中输出进程再为用户进程申请一张空白的用输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入户请求打印表，并将用户的打印要求填入其中，其中， 再再将
19、该表挂到请求打印队列上将该表挂到请求打印队列上Operating SystemOperating SystemPage 242022-5-304. SPOOLing系统特点系统特点v提高了提高了I/O的速度的速度v将独占设备改造为共享设备将独占设备改造为共享设备v实现了虚拟设备功能实现了虚拟设备功能Operating SystemOperating SystemPage 252022-5-30SPOOLing技术今天仍被广泛使用技术今天仍被广泛使用q网络文件传送网络文件传送 先把文件送到网络先把文件送到网络SPOOLing目录，然后网络值目录，然后网络值班进程把它取出并传递到目标地址班进程把它
20、取出并传递到目标地址qInternet电子邮件系统电子邮件系统 为了寄邮，调用电子邮件程序为了寄邮，调用电子邮件程序 待发信存在待发信存在SPOOLing中供以后传输中供以后传输q注意：注意：SPOOLing只提高设备利用率，缩短用户只提高设备利用率，缩短用户程序执行时间，并不提高程序执行时间，并不提高CPU利用率利用率Operating SystemOperating SystemPage 262022-5-30qI/O系统系统 qI/O控制方式控制方式 q缓冲管理缓冲管理 q设备分配设备分配q设备处理设备处理q磁盘存储器管理磁盘存储器管理Operating SystemOperating
21、SystemPage 272022-5-30q磁盘性能简述磁盘性能简述q磁盘调度磁盘调度q磁盘高速缓存磁盘高速缓存(Disk Cache)q提高磁盘提高磁盘I/O速度的其它方法速度的其它方法q廉价磁盘冗余阵列廉价磁盘冗余阵列现代操作系统的重要任务之一：设法改善磁盘系统的性能现代操作系统的重要任务之一：设法改善磁盘系统的性能Operating SystemOperating SystemPage 282022-5-30q磁盘存储器管理的主要任务磁盘存储器管理的主要任务v提高磁盘提高磁盘I/O速度，改善文件性能速度，改善文件性能v确保文件系统的确保文件系统的可靠性可靠性（备份）（备份）Operat
22、ing SystemOperating SystemPage 292022-5-305.6 磁盘存储器管理磁盘存储器管理5.6.1 磁盘性能简述磁盘性能简述 1. 数据的组织和格式数据的组织和格式图 5-22 磁盘的格式化 包括一个或多个包括一个或多个，每片分，每片分2面，每面可面，每面可分成若干条分成若干条，各磁道之间有间隙，每条磁道上，各磁道之间有间隙，每条磁道上可存储相同数目的二进制位，磁盘可存储相同数目的二进制位，磁盘即每英寸之即每英寸之中所存储的位数。显然内层磁道的密度较外层磁道中所存储的位数。显然内层磁道的密度较外层磁道的密度大。的密度大。Operating SystemOpera
23、ting SystemPage 302022-5-30盘片盘片扇区扇区磁头磁头磁道磁道Operating SystemOperating SystemPage 312022-5-30Operating SystemOperating SystemPage 322022-5-30Operating SystemOperating SystemPage 332022-5-30Operating SystemOperating SystemPage 342022-5-301. 数据的组织和格式数据的组织和格式v盘片盘片（1个或多个）、盘面、磁道、扇区个或多个）、盘面、磁道、扇区v扇区有扇区有标识符字
24、段标识符字段和和数据字段数据字段Gap102031292293Field Gap Field Gap Gap Field Gap Field Gap17741515201774151520IDDataIDDataGap1292293Field Gap Field1774151520IDDataSectorPhysical Sector 0Physical Sector 1Physical Sector 29BytesSynchByteTrack#Head#Sector#Bytes 1211CRC3SynchByteDataCRC15122600 Bytes/SectorGap存储相同数存储相同
25、数目的二进制目的二进制位位间隙间隙定界符定界符段校验段校验Operating SystemOperating SystemPage 352022-5-302. 磁盘的类型磁盘的类型 这种磁盘在，所有的磁头都被装在一刚性磁臂中。通过这些磁头可访问所有各磁道，并进行，有效地。这种结构的磁盘主要用于上。 ，也被装入磁臂中。为能访问该盘面上的所有磁道，该磁头必须能移动以进行寻道。可见，移动磁头仅能以，致使其；但由于其结构简单， 故仍广泛应用于设备中。 Operating SystemOperating SystemPage 362022-5-30访盘时间组成访盘时间组成 寻道寻道时间时间旋转旋转延迟延
26、迟时间时间传输传输时间时间Operating SystemOperating SystemPage 372022-5-303. 磁盘访问时间磁盘访问时间v寻道时间寻道时间Ts这是指把磁臂这是指把磁臂(磁头磁头)移动到指定磁道上所移动到指定磁道上所经历的时间。该时间是启动磁臂的时间经历的时间。该时间是启动磁臂的时间s与与磁头移动磁头移动n条磁道所花费的时间之和，条磁道所花费的时间之和， 即即Ts=mn+sv旋转延迟时间旋转延迟时间T这是指定扇区移动到磁头下面所经历的时这是指定扇区移动到磁头下面所经历的时间。如：间。如：7200r/min 每转每转=60000ms/7200r=8.33ms 平均旋
27、转延迟平均旋转延迟=（0+8.33)/2=4.16是一常数，是一常数，与磁盘驱动与磁盘驱动器的速度有器的速度有关关一般：一般：0.2高速：高速：=0.1启动磁臂时间启动磁臂时间2msOperating SystemOperating SystemPage 382022-5-30v传输时间传输时间Tt指把数据从磁盘读出或向磁盘写入数据所指把数据从磁盘读出或向磁盘写入数据所经历的时间。经历的时间。 其大小与每次所读其大小与每次所读/写的字写的字节数节数b和旋转速度有关和旋转速度有关r为磁盘每秒钟的转数；为磁盘每秒钟的转数；N为一条磁道上为一条磁道上的字节数的字节数vT和和Tt相同，则访问时间相同，
28、则访问时间=Ts + T+ Tt rNbTt12asbTTrrN如如b=N/2，则，则T=1/(2r)=Tt可见，寻道时间可见，寻道时间TS和旋转和旋转延迟时间延迟时间T基本上都与所基本上都与所读读/写数据的字节数无关，写数据的字节数无关，而且它通常占据了访问时而且它通常占据了访问时间中的大部分间中的大部分目前磁盘的传输速率已达到目前磁盘的传输速率已达到80MB/s以上，数据传输时间所占以上，数据传输时间所占的比例更低。可见，适当地集中数据传输，将有利于提高传输的比例更低。可见，适当地集中数据传输，将有利于提高传输效率效率Operating SystemOperating SystemPage
29、 392022-5-303. 磁盘访问时间磁盘访问时间 ：TS=m*n+S；：Tr1/2r：Ttb/rN Ta=Ts+1/2r+b/rNOperating SystemOperating SystemPage 402022-5-30q磁盘性能简述磁盘性能简述q磁盘调度磁盘调度q磁盘高速缓存磁盘高速缓存(Disk Cache)q提高磁盘提高磁盘I/O速度的其它方法速度的其它方法q廉价磁盘冗余阵列廉价磁盘冗余阵列在访问磁盘的时间中，主要是寻道时间，因此，磁在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标就是使磁盘的平均寻道时间最少。盘调度的目标就是使磁盘的平均寻道时间最少。Operatin
30、g SystemOperating SystemPage 412022-5-301. 先来先服务先来先服务FCFS(First-Come, First Served)v根据进程请求访问磁盘根据进程请求访问磁盘的先后次序进行调度的先后次序进行调度v优点：简单、公平，不优点：简单、公平，不会出现请求长期得不到会出现请求长期得不到满足满足v缺点：未优化，平均寻缺点：未优化，平均寻道时间长道时间长平均寻道长度：平均寻道长度：55.31461841123810150701607290211819393584555移动距离移动距离被访问的下一个被访问的下一个磁道磁道100道开始道开始55、58、39、18
31、、90、160、150、38、1840383955589010015016018418先来先服务先来先服务FCFS(First-Come, First Served)Operating SystemOperating SystemPage 432022-5-302. 最短寻道时间优先最短寻道时间优先SSTF(Shortest Seek Time First) v要求访问的磁道与当前要求访问的磁道与当前磁头所在的磁道距离最磁头所在的磁道距离最近近v优点：使每次寻道时间优点：使每次寻道时间最短最短v缺点：不能保证平均寻缺点：不能保证平均寻道时间最短；可能导致道时间最短；可能导致距离远的进程总也得不
32、距离远的进程总也得不到服务到服务平均寻道长度：平均寻道长度：27.524184101601321502018138163935532581090移动距离移动距离被访问的下一个被访问的下一个磁道磁道100道开始道开始55、58、39、18、90、160、150、38、1840383955589010015016018418最短寻道时间优先最短寻道时间优先STF(Shortest Seek Time First)Operating SystemOperating SystemPage 452022-5-30100道开始道开始被访问的下一个磁被访问的下一个磁道道移动距离移动距离55455833919
33、18219072160701501038112184146平均寻道长度：平均寻道长度：55.3100道开始道开始被访问的下一个磁被访问的下一个磁道道移动距离移动距离90105832553391638118201501321601018424平均寻道长度：平均寻道长度：27.5Operating SystemOperating SystemPage 462022-5-303. 扫描扫描(SCAN)算法算法 vSSTF算法虽然能获得较好的寻道性能，算法虽然能获得较好的寻道性能， 但但却可能导致某个进程发生却可能导致某个进程发生“饥饿饥饿”现象现象050160Operating SystemOper
34、ating SystemPage 472022-5-303. 扫描扫描(SCAN)算法算法v对对SSTF算法略加修改后所形成的算法略加修改后所形成的SCAN算法算法， 即可防止进程出现即可防止进程出现“饥饿饥饿”现象现象vSCAN算法不仅考虑欲访问的磁道与当前磁算法不仅考虑欲访问的磁道与当前磁道的距离，更优先考虑的是磁头当前的移动道的距离，更优先考虑的是磁头当前的移动方向方向v磁头移动：自里向外磁头移动：自里向外自外向里自外向里v又称为又称为 “电梯调度算法电梯调度算法”Operating SystemOperating SystemPage 482022-5-303. 扫描扫描(SCAN)算
35、法算法v对对SSTF算法略加修改算法略加修改后所形成的后所形成的SCAN算法算法， 即可防止进程出现即可防止进程出现“饥饥饿饿”现象现象vSCAN算法不仅考虑欲算法不仅考虑欲访问的磁道与当前磁道访问的磁道与当前磁道的距离，更优先考虑的的距离，更优先考虑的是磁头当前的移动方向是磁头当前的移动方向v磁头移动：自里向外磁头移动：自里向外自外向里自外向里v又称为又称为 “电梯调度算电梯调度算法法”平均寻道长度：平均寻道长度：27.82018138163935532589490241841016050150移动距离移动距离被访问的下一个被访问的下一个磁道磁道100道开始，增加方向道开始，增加方向55、5
36、8、39、18、90、160、150、38、184Operating SystemOperating SystemPage 492022-5-30100道开始道开始被访问的下一个磁被访问的下一个磁道道移动距离移动距离90105832553391638118201501321601018424平均寻道长度：平均寻道长度：27.5100道开始，增加方向道开始，增加方向被访问的下一个磁被访问的下一个磁道道移动距离移动距离1505016010184249094583255339163811820平均寻道长度：平均寻道长度：27.8Operating SystemOperating SystemPage
37、 502022-5-300383955589010015016018418v缺点：缺点：刚移过刚移过的磁道的等待时的磁道的等待时间长间长3. 扫描扫描(SCAN)算法算法Operating SystemOperating SystemPage 512022-5-304. 循环扫描循环扫描(CSCAN)算法算法 v规定磁头单向移动规定磁头单向移动v减少刚移过的磁道的减少刚移过的磁道的等待时间等待时间平均寻道长度：平均寻道长度：27.532903581655139203816618241841016050150移动距离移动距离被访问的下一个被访问的下一个磁道磁道100道开始，增加方向道开始，增加方
38、向55、58、39、18、90、160、150、38、184Operating SystemOperating SystemPage 522022-5-300383955589010015016018418Operating SystemOperating SystemPage 532022-5-30100道开始，增加方向道开始，增加方向被访问的下一个磁被访问的下一个磁道道移动距离移动距离1505016010184249094583255339163811820平均寻道长度：平均寻道长度：27.8100道开始，增加方向道开始，增加方向被访问的下一个磁被访问的下一个磁道道移动距离移动距离1505
39、0160101842418166382039155165839032平均寻道长度：平均寻道长度：27.5Operating SystemOperating SystemPage 542022-5-30100道开始，增加方向道开始，增加方向被访问的下一个磁被访问的下一个磁道道移动距离移动距离15050160101842418166382039155165839032平均寻道长度：平均寻道长度：27.5100道开始道开始被访问的下一个被访问的下一个磁道磁道移动距离移动距离90105832553391638118201501321601018424平均寻道长度：平均寻道长度：27.5Operatin
40、g SystemOperating SystemPage 552022-5-305. N-Step-SCAN和和FSCAN调度算法调度算法 vN-Step-SCAN算法算法在在SSTF、 SCAN及及CSCAN几种调度算法中，几种调度算法中， 都都可能出现磁臂停留在某处不动的情况，称为可能出现磁臂停留在某处不动的情况，称为“磁磁臂粘着臂粘着”(Armstickiness)N步步SCAN算法是将磁盘请求队列分成若干个长度算法是将磁盘请求队列分成若干个长度为为N的子队列，磁盘调度将按的子队列，磁盘调度将按FCFS算法依次处理算法依次处理这些子队列。这些子队列。 而每处理一个队列时又是按而每处理一个
41、队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列算法，对一个队列处理完后，再处理其他队列vFSCAN算法算法FSCAN算法是算法是N步步SCAN算法的简化，算法的简化， 即其只将即其只将磁盘请求队列分成两个子队列。一是由当前所有磁盘请求队列分成两个子队列。一是由当前所有请求请求I/O的进程形成的队列，由磁盘调度按的进程形成的队列，由磁盘调度按SCAN算法进行处理。在扫描期间，新出现的所有请求算法进行处理。在扫描期间，新出现的所有请求I/O的进程，的进程， 则放入另一个等待处理的请求队列则放入另一个等待处理的请求队列当当N值很大时，值很大时，N步扫步扫描性能接近于描性能接近于SCAN
42、性性能；能；N=1， N步扫描步扫描性能便退化为性能便退化为FCFSOperating SystemOperating SystemPage 562022-5-30q磁盘性能简述磁盘性能简述q磁盘调度磁盘调度q磁盘高速缓存磁盘高速缓存(Disk Cache)q提高磁盘提高磁盘I/O速度的其它方法速度的其它方法q廉价磁盘冗余阵列廉价磁盘冗余阵列Operating SystemOperating SystemPage 572022-5-301. 磁盘高速缓存的形式磁盘高速缓存的形式v利用利用内存内存中的存储空间，来暂存从中的存储空间，来暂存从磁盘磁盘中读中读出的一系列盘块中的信息出的一系列盘块中的
43、信息v高速缓存是一组在逻辑上属于磁盘，高速缓存是一组在逻辑上属于磁盘， 而物理而物理上是驻留在内存中的盘块上是驻留在内存中的盘块v高速缓存在内存中可分成两种形式高速缓存在内存中可分成两种形式在内存中开辟一个在内存中开辟一个单独的存储空间单独的存储空间来作为来作为磁盘高速缓存，其大小是固定的磁盘高速缓存，其大小是固定的把所有把所有未利用的内存空间变为一个缓冲池未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘供请求分页系统和磁盘I/O时时(作为磁盘高作为磁盘高速缓存速缓存)共享共享不受应用程序不受应用程序多少的限制多少的限制应用程序多时应用程序多时缓存可能很小缓存可能很小Operating S
44、ystemOperating SystemPage 582022-5-302. 数据交付方式数据交付方式v数据交付数据交付（Data Delivery）是指将磁盘高是指将磁盘高速缓存中的数据传送给请求者进程速缓存中的数据传送给请求者进程v当有进程请求访问某个盘块时，先查看磁盘当有进程请求访问某个盘块时，先查看磁盘高速缓存高速缓存v有两种方式交付数据给请求进程有两种方式交付数据给请求进程数据交付数据交付。这是直接将高速缓存中的数据，。这是直接将高速缓存中的数据， 传送到请求者进程的内存工作区中传送到请求者进程的内存工作区中指针交付指针交付。只将指向高速缓存中某区域的。只将指向高速缓存中某区域的指
45、针，交付给请求者进程指针，交付给请求者进程所传送的数据量少，所传送的数据量少，节省了数据从磁盘节省了数据从磁盘高速缓存存储空间高速缓存存储空间到到进程的内存工作进程的内存工作区的时间区的时间Operating SystemOperating SystemPage 592022-5-303. 置换算法置换算法v将磁盘中的盘块写入高速缓存时，会出现因将磁盘中的盘块写入高速缓存时，会出现因为高速缓存中已装满盘块而需要将高速缓存为高速缓存中已装满盘块而需要将高速缓存中的数据先换出的问题，常用算法有中的数据先换出的问题，常用算法有LRU、NRU、LFU等等v除了考虑除了考虑LRU外，还需考虑以下几点外，
46、还需考虑以下几点访问频率访问频率可预见性，如正在写数据的未满盘块可预见性，如正在写数据的未满盘块数据的一致性数据的一致性 内存中已修改数据要写回内存中已修改数据要写回磁盘磁盘可将高速缓存中的所有盘块数据构成一个可将高速缓存中的所有盘块数据构成一个LRU链，将会影链，将会影响到数据一致性的盘块和响到数据一致性的盘块和很久都不可能再用很久都不可能再用的盘块放在的盘块放在LRU链的链头，使其优先被写回磁盘，不久后还要再使用链的链头，使其优先被写回磁盘，不久后还要再使用的盘块放到链尾的盘块放到链尾最近最久未使用算法最近最久未使用算法LRU最近未使用算法最近未使用算法NRU最少使用算法最少使用算法LFU
47、Operating SystemOperating SystemPage 602022-5-304. 周期性写回磁盘周期性写回磁盘v在在LRU算法中，经常被访问的盘块数据可能算法中，经常被访问的盘块数据可能一直保留在高速缓存中，长期不被写回磁盘一直保留在高速缓存中，长期不被写回磁盘v在在UNIX系统中专门增设了一个系统中专门增设了一个修改修改(update)程序，程序， 使之在后台运行，该程序周期性地调使之在后台运行，该程序周期性地调用一个系统调用用一个系统调用SYNC。该调用的主要功能。该调用的主要功能是强制性地将所有在高速缓存中已修改的盘是强制性地将所有在高速缓存中已修改的盘块数据写回磁盘
48、块数据写回磁盘v在在MS-DOS中所采用的方法是：只要高速缓中所采用的方法是：只要高速缓存中的某盘块数据被修改，便立即将它写回存中的某盘块数据被修改，便立即将它写回磁盘，并将这种高速缓存称为磁盘，并将这种高速缓存称为“写穿透、高写穿透、高速缓存速缓存”(write-through cache)Operating SystemOperating SystemPage 612022-5-30q磁盘性能简述磁盘性能简述q磁盘调度磁盘调度q磁盘高速缓存磁盘高速缓存(Disk Cache)q提高磁盘提高磁盘I/O速度的其它方法速度的其它方法q廉价磁盘冗余阵列廉价磁盘冗余阵列Operating Syste
49、mOperating SystemPage 622022-5-301. 提前读（提前读（Read-Ahead）v在读当前块的同时，将下一盘块读入缓冲区在读当前块的同时，将下一盘块读入缓冲区2. 延迟写延迟写v缓冲区中的数据不立即写回磁盘，而挂在队尾缓冲区中的数据不立即写回磁盘，而挂在队尾3. 优化物理块分布优化物理块分布v使文件的物理块集中，减小磁头移动距离使文件的物理块集中，减小磁头移动距离v分配时以簇（若干个盘块分配时以簇（若干个盘块 ）为单位）为单位v磁盘碎片整理磁盘碎片整理4. 虚拟盘虚拟盘v利用内存空间仿真磁盘，又称为利用内存空间仿真磁盘，又称为RAM盘盘Operating Syst
50、emOperating SystemPage 632022-5-30q磁盘性能简述磁盘性能简述q磁盘调度磁盘调度q磁盘高速缓存磁盘高速缓存(Disk Cache)q提高磁盘提高磁盘I/O速度的其它方法速度的其它方法q廉价磁盘冗余阵列廉价磁盘冗余阵列Operating SystemOperating SystemPage 642022-5-30q廉价磁盘冗余阵列廉价磁盘冗余阵列RAID(Redundant Array of Inexpensive Disk)，1987年由美国加州大学年由美国加州大学提出提出q过去过去RAID是由许多小的便宜磁盘组成的，可作是由许多小的便宜磁盘组成的，可作为大的昂
