第4章-IO设备管理课件.ppt

1、操作系统操作系统Operating Systems谌卫军谌卫军 清华大学软件学院清华大学软件学院 进程管理21.I/O硬件硬件2.I/O控制方式控制方式3.I/O软件软件4.磁盘磁盘第第四四章章 I/OI/O设备管理设备管理 进程管理3 在现代计算机系统中，有大量的输入输在现代计算机系统中，有大量的输入输出设备，其种类繁多，差异大。而且随着技出设备，其种类繁多，差异大。而且随着技术的发展，新设备也不断地出现。因此，如术的发展，新设备也不断地出现。因此，如何管理好这些设备，使资源得以合理的利用，何管理好这些设备，使资源得以合理的利用，是操作系统的一个主要功能。是操作系统的一个主要功能。I/O（I

2、nput/Output）设备）设备 进程管理44.1 I/O硬件硬件 对于对于I/O硬件，硬件，操作系统操作系统所关心的并不是所关心的并不是硬件自身的设计、制造和维护，而是如何来硬件自身的设计、制造和维护，而是如何来对它进行编程，即该设备给软件提供的接口对它进行编程，即该设备给软件提供的接口是什么，包括它所接受的控制命令、所完成是什么，包括它所接受的控制命令、所完成的功能，以及所返回的出错报告。的功能，以及所返回的出错报告。进程管理5按交互方向分类：按交互方向分类：-输入设备：键盘、鼠标、扫描仪；输入设备：键盘、鼠标、扫描仪；-输出设备：显示器、打印机；输出设备：显示器、打印机；-输入输入/输

3、出：磁盘、网卡。输出：磁盘、网卡。4.1.1 I/O设备设备的类型的类型 进程管理6按数据组织分类：按数据组织分类：-块设备块设备：以数据块作为信息的存储和传：以数据块作为信息的存储和传输单位，每个数据块都有一个地址，数输单位，每个数据块都有一个地址，数据块之间的读写操作是相互独立的，如据块之间的读写操作是相互独立的，如磁盘；磁盘；-字符设备字符设备：以字符作为信息存储和传输：以字符作为信息存储和传输单位，数据即字符流，无定位无寻址，单位，数据即字符流，无定位无寻址，如鼠标；如鼠标；进程管理7 有了有了I/O设备，是否就能完成设备，是否就能完成I/O功能呢？功能呢？进程管理84.1.2 设备设

4、备控制器控制器 机械部分机械部分 电子部分电子部分 一个一个I/O单元由两部分组成：单元由两部分组成：机械部分机械部分和和电子部分（电子部分（设备控制器设备控制器或或适配器适配器）。进程管理9机械部分即为机械部分即为I/O设备本身；设备本身；电子部分称为：电子部分称为：设备控制器设备控制器（device controller）或）或适配器适配器（adapter）。）。适配器的形式通常是印刷电路卡，可以适配器的形式通常是印刷电路卡，可以插入到主板的扩充槽中；控制器的形式插入到主板的扩充槽中；控制器的形式是一组芯片；是一组芯片；完成设备与主机间的连接和通讯。完成设备与主机间的连接和通讯。进程管理1

5、04.1.3 I/O地址地址 每个设备控制器都有一些寄存器用来与每个设备控制器都有一些寄存器用来与CPU通信。通通信。通过往这些寄存器中写入不同的值，过往这些寄存器中写入不同的值，OS能命令该设备去能命令该设备去执行发送数据、接收数据、打开、关闭等操作；执行发送数据、接收数据、打开、关闭等操作；OS也也能通过读取这些寄存器的值来了解设备的当前状态。能通过读取这些寄存器的值来了解设备的当前状态。此外，许多控制器还有一个数据缓冲区供此外，许多控制器还有一个数据缓冲区供OS读写。读写。CPU外外部部设设备备控控制制逻逻辑辑电电路路控制寄存器控制寄存器 状态寄存器状态寄存器 数据寄存器数据寄存器 如何

6、让如何让I/O设备工作？设备工作？进程管理11问题：问题：CPU如何与设备控制器进行通信？如何与设备控制器进行通信？这这不是普通的内存访问！不是普通的内存访问！方法有三种：方法有三种：I/O独立编址；独立编址；内存映像编址；内存映像编址；混合编址。混合编址。进程管理121.I/O独立编址独立编址 w 基本思路：给控制器中的基本思路：给控制器中的每一个寄存器每一个寄存器分配一个唯分配一个唯一的一的I/O端口（端口（I/O port）编号，称为）编号，称为I/O端口地址，端口地址，然后用专门的然后用专门的I/O指令对端口进行操作；指令对端口进行操作；w 这些端口地址所构成的这些端口地址所构成的地址

7、空间是完全独立的，地址空间是完全独立的，与内存的地址空间没有与内存的地址空间没有关系。例如：关系。例如：IN R0 4 表示读入表示读入I/O端口地址为端口地址为4的内容；的内容；MOV R0 4 表示读入表示读入内存地址为内存地址为4的内容；的内容；进程管理13Linux0.11/boot/setup.smov al,#0 x11!initialization sequenceout#0 x20,al!send it to 8259A-1mov al,#0 x20 !start of hardware ints(0 x20)out#0 x21,almov al,#0 x28!start of

8、 hardware ints(0 x28)out#0 xA1,alin al,#0 x64 !8042 status port !键盘控制器状态寄存器键盘控制器状态寄存器test al,#2jnz empty_8042!is input buffer full?进程管理142.内存映像编址内存映像编址 w 基本思路：把所有控制器当中的每一个寄存器都映基本思路：把所有控制器当中的每一个寄存器都映射为一个内存地址，专门用于射为一个内存地址，专门用于I/O操作（功能上），操作（功能上），对这些单元的读写操作即为普通的内存访问操作。对这些单元的读写操作即为普通的内存访问操作。w 端口地址空间与内存的地

9、址空间统一编址，前者是端口地址空间与内存的地址空间统一编址，前者是后者的一部分，一般位于后者的顶端部分。后者的一部分，一般位于后者的顶端部分。进程管理15F 编程方便，无需专门的编程方便，无需专门的I/O指令指令(C vs.汇编汇编)；F 不能对控制寄存器的内容进行不能对控制寄存器的内容进行Cache，须关闭；，须关闭；F 每一次都要判断访问的是内存还是每一次都要判断访问的是内存还是I/O。进程管理163.混合编址混合编址 w 基本思路：对于设备控制器中的寄存器，采用独立基本思路：对于设备控制器中的寄存器，采用独立编址的方法；而对于设备的数据缓冲区，采用内存编址的方法；而对于设备的数据缓冲区，

10、采用内存映像编址的方法。映像编址的方法。进程管理17PC机上的部分机上的部分I/O端口地址端口地址（本图摘自（本图摘自Silberschatz,Galvin and Gagne：“Operating System Concepts”）进程管理18到目前为止，已经介绍了到目前为止，已经介绍了I/O设备的类型、设备的类型、设备的控制器、设备的控制器、I/O的端口地址。现在的的端口地址。现在的问题是：根据已有的这些知识，现在问题是：根据已有的这些知识，现在能否能否开始编程使用这些开始编程使用这些I/O设备，完成相应的输设备，完成相应的输入输出功能呢？入输出功能呢？进程管理194.2 I/O控制方式控

11、制方式程序循环检测方式程序循环检测方式(Programmed I/O)中断驱动方式中断驱动方式(Interrupt-driven I/O)直接内存访问方式直接内存访问方式(DMA,Direct Memory Access)进程管理204.2.1 程序循环检测方式程序循环检测方式 小宝宝在家吃饭小宝宝在家吃饭 如果宝宝的嘴巴没空（如上一口饭如果宝宝的嘴巴没空（如上一口饭菜尚未吃完），循环等待菜尚未吃完），循环等待 装一勺饭菜，喂到宝宝嘴里装一勺饭菜，喂到宝宝嘴里 重复上述步骤重复上述步骤 进程管理21w 基本思路基本思路：在程序（设备驱动程序）中通过不断地：在程序（设备驱动程序）中通过不断地检测

12、检测I/O设备的当前状态，来控制设备的当前状态，来控制I/O操作的完成。操作的完成。具体来说，在进行具体来说，在进行I/O操作之前，要循环地检测设操作之前，要循环地检测设备是否就绪；在备是否就绪；在I/O操作进行之中，要循环地检测操作进行之中，要循环地检测设备是否已完成。从硬件来说，控制设备是否已完成。从硬件来说，控制I/O的所有工的所有工作均由作均由CPU来完成。来完成。w 也称为也称为繁忙等待繁忙等待方式（方式（busy waiting）或）或轮询轮询方式方式（polling）。）。1.1.I/OI/O控制与控制与I/OI/O操作操作2.2.缺点缺点.进程管理22一个例子一个例子已知已知I

13、/O地址采用内存映像编址的方式，现需要地址采用内存映像编址的方式，现需要在打印机上打印一个字符串在打印机上打印一个字符串“ABCDEFGH”。基本思路：把这基本思路：把这8个字符逐个送到打印机设备的个字符逐个送到打印机设备的I/O端口地址（内存地址）。端口地址（内存地址）。A B C D E F G H内存内存pprinter_status_regprinter_data_register 进程管理23for(i =0;i sys_read)；该函数又调用相应的设备驱动程序，驱动该函数又调用相应的设备驱动程序，驱动程序在启动程序在启动I/O操作后被阻塞操作后被阻塞(-driver_read)；

14、I/O操作完成后，将产生一个中断，然后中操作完成后，将产生一个中断，然后中断处理程序将接管断处理程序将接管CPU，并唤醒被阻塞的，并唤醒被阻塞的驱动程序。驱动程序。方案一方案一 进程管理54驱动程序以什么形式存在？单独的一个进驱动程序以什么形式存在？单独的一个进程吗？调用驱动时程吗？调用驱动时有无进程切换有无进程切换？中断处理程序是谁写的？中断处理程序是谁写的？OS or 厂商厂商？设备驱动程序与中断处理程序（两个设备驱动程序与中断处理程序（两个进程进程间）如何同步？间）如何同步？如果有多个进程同时都要访问该如果有多个进程同时都要访问该I/O设备，设备，该怎么办？该怎么办？问题问题 进程管理5

15、5我们要为一个简单的我们要为一个简单的字符输入设备字符输入设备实现相实现相应的设备驱动程序。应的设备驱动程序。当用户进程需要当用户进程需要I/O操作时，启动相应操作时，启动相应系统系统调用调用，最终执行各种设备统一的对外接口，最终执行各种设备统一的对外接口函数函数read(devID,buf,size)。设备驱动程序主要由两个函数组成：设备驱动程序主要由两个函数组成：foo_read()，该设备对，该设备对read接口函数的具体接口函数的具体实现。实现。foo_interrupt()，中断处理函数。，中断处理函数。一个例子一个例子 进程管理56size_t foo_read(struct fi

16、le*filp,char*buf,size_t count,loff_t*ppos)foo_dev_t*foo_dev=filp-private_data;if(down_interruptible(&foo_dev-sem)/互斥互斥 return-ERESTARTSYS;foo_dev-intr=0;/同步同步 outb(DEV_FOO_READ,DEV_FOO_CONTROL_PORT);wait_event_interruptible(foo_dev-wait,(foo_dev-intr=1);/被阻塞被阻塞 if(put_user(foo_dev-data,buf)return-EF

17、AULT;up(&foo_dev-sem);return 1;进程管理57void foo_interrupt(int irq,void*dev_id,struct pt_regs*regs)foo-data=inb(DEV_FOO_DATA_PORT);foo-intr=1;wake_up_interruptible(&foo-wait);用户进程用户进程A 系统调用系统调用 read foo_read 被阻塞被阻塞 用户进程用户进程B 被中断被中断 foo_interrupt A被唤醒被唤醒 进程管理58方案方案1只适合需要互斥访问的设备。只适合需要互斥访问的设备。块设备如何处理？块设备如

18、何处理？例如：例如：A进程访问磁盘的第进程访问磁盘的第i个数据块个数据块，B进程也要访问第进程也要访问第i个数据块，如何个数据块，如何优化，减少优化，减少I/O操作？操作？进程管理59数据结构：数据结构：请求队列请求队列（request queue）；）；块设备驱动程序：块设备驱动程序：上层函数上层函数，负责管理请，负责管理请求队列；求队列；底层函数底层函数，负责与硬件打交道，负责与硬件打交道，完成真正的完成真正的I/O；I/O请求的提交与真正实现是分离的。各个请求的提交与真正实现是分离的。各个用户进程（通过内核）调用上层函数，提用户进程（通过内核）调用上层函数，提交交I/O请求请求(mak_

19、request)，然后阻塞；底层函数，然后阻塞；底层函数则从队列中取出每个则从队列中取出每个I/O请求，并完成之。请求，并完成之。能对各能对各I/O请求进行优化，如数据块重组。请求进行优化，如数据块重组。方案二方案二 进程管理60Example:A scsi disk driver in UNIX sdstrategy:do error checking,if device is not busy,issue a start request for the specific unit(disk).sdustart:find the proper queue for this unit,put

20、the request on the queue,issue start.sdstart:request the resources needed for the request(scsi bus or DMA resources).sdgo:write the commands to the controller,set the interrupt vector,issue the start request to the controller.sdintr:called from I/O interrupt,finish the request(schedule the waiting p

21、rocess),issue a new request if there is one.进程管理61设备独立的设备独立的I/O软件是系统内核的一部分，它的基软件是系统内核的一部分，它的基本任务是实现所有设备都需要的一些通用的本任务是实现所有设备都需要的一些通用的I/O功功能，并向用户级软件提供一个统一的能，并向用户级软件提供一个统一的接口接口。实现的主要功能：实现的主要功能：给上层应用的统一接口；给上层应用的统一接口；与设备驱动程序的统一接口；与设备驱动程序的统一接口；提供与设备无关的数据块大小；提供与设备无关的数据块大小；缓冲缓冲技术（技术（36M、3、1）；）；设备独立的设备独立的I/O软

22、件软件 进程管理62v 库函数：如库函数：如C语言里与语言里与I/O有关的库函数有关的库函数write、read等，它们实质上只是将它们的参数再传递给等，它们实质上只是将它们的参数再传递给系统调用函数，并由后者来完成实际的系统调用函数，并由后者来完成实际的I/O操作；操作；v Spooling技术：在多道系统中，一种处理独占设技术：在多道系统中，一种处理独占设备的方法。备的方法。用户空间的用户空间的I/O软件软件 进程管理63w 利用利用假脱机技术假脱机技术（SPOOLing,Simultaneous Peripheral Operation On Line,也称虚拟设备技术）也称虚拟设备技术

23、）可把独占设备转变成具有共享特征的虚拟设备，从可把独占设备转变成具有共享特征的虚拟设备，从而提高设备利用率。而提高设备利用率。Application AApplication BSPOOLingProgramDeviceVirtual I/OActual I/O打印机打印机.进程管理644.4 磁盘磁盘4.4.1 磁盘硬件磁盘硬件 w 磁盘的硬件结构：磁盘（软盘和硬盘）由一个或多磁盘的硬件结构：磁盘（软盘和硬盘）由一个或多个金属盘片组成，这些盘片组合固定在一根旋转轴个金属盘片组成，这些盘片组合固定在一根旋转轴上，由同一个马达驱动。每个盘片有上下两个盘面，上，由同一个马达驱动。每个盘片有上下两个

24、盘面，在盘面上涂有磁性材料，信息就记录在这些盘面上。在盘面上涂有磁性材料，信息就记录在这些盘面上。在每个盘面上方，都有一个磁头，它固定在一个磁在每个盘面上方，都有一个磁头，它固定在一个磁头臂上，而磁头臂又固定在一个传动装置上。通过头臂上，而磁头臂又固定在一个传动装置上。通过磁头的读写装置，磁盘上的信息可以被写入、读出磁头的读写装置，磁盘上的信息可以被写入、读出和修改。和修改。进程管理65磁道磁道扇区扇区柱面柱面读写磁头读写磁头磁头臂磁头臂盘片盘片传动装置传动装置旋转轴旋转轴移动方向移动方向 进程管理66w 磁道磁道：当传动装置固定在某个位置时，若盘面旋转：当传动装置固定在某个位置时，若盘面旋转

25、一圈，磁头所能访问的圆环区域；一圈，磁头所能访问的圆环区域；w 柱面柱面：在所有盘面上，半径相同的所有磁道即组成：在所有盘面上，半径相同的所有磁道即组成一个柱面；一个柱面；w 扇区扇区：每一个磁道被划分为若干个扇区；：每一个磁道被划分为若干个扇区；w 磁盘的访问过程磁盘的访问过程：以扇区作为最小的寻址和存取单：以扇区作为最小的寻址和存取单位。首先移动传动装置，通过它来移动磁头，从而位。首先移动传动装置，通过它来移动磁头，从而定位正确的柱面。然后选中相应的磁头，等我们想定位正确的柱面。然后选中相应的磁头，等我们想要的扇区正好路过这个磁头正下方的时候，就可以要的扇区正好路过这个磁头正下方的时候，就

26、可以对它进行访问了。对它进行访问了。进程管理67w如何写一个字节？读修改写如何写一个字节？读修改写 读入包含该字节的扇区；读入包含该字节的扇区；修改该字节；修改该字节；把整个扇区写回到磁盘；把整个扇区写回到磁盘；进程管理68参数参数IBM 360-KB软盘软盘Barracuda 180硬盘硬盘柱面数柱面数4024247磁道数磁道数柱面柱面224扇区扇区磁道磁道9609(平均平均)扇区扇区磁盘磁盘72035742000字节数字节数扇区扇区512512磁盘容量磁盘容量360KB181GB柱面定位柱面定位(相邻相邻)6毫秒毫秒0.8毫秒毫秒柱面定位柱面定位(平均平均)77毫秒毫秒7.4毫秒毫秒旋转时

27、间旋转时间200毫秒毫秒8.33毫秒毫秒扇区传送时间扇区传送时间22毫秒毫秒17微秒微秒 进程管理69w 硬盘的格式化可分为三个步骤，即低级格式化、分硬盘的格式化可分为三个步骤，即低级格式化、分区和高级格式化。区和高级格式化。w 低级格式化：标出低级格式化：标出磁道磁道和和扇区扇区，在相邻的扇区之间，在相邻的扇区之间有狭窄的间隙隔开。一个扇区的格式是：相位编码有狭窄的间隙隔开。一个扇区的格式是：相位编码（preamble）数据区纠错码（）数据区纠错码（ECC）。）。F 相位编码：以某个特定的位组合模式开始，向相位编码：以某个特定的位组合模式开始，向硬件表明这是一个新扇区的开始。还包括柱面硬件表

28、明这是一个新扇区的开始。还包括柱面号、扇区号、扇区大小等类似信息；号、扇区号、扇区大小等类似信息；F 数据区：由格式化程序确定其大小，一般数据区：由格式化程序确定其大小，一般512；F 纠错码：包含冗余信息，用来纠正读取错误。纠错码：包含冗余信息，用来纠正读取错误。4.4.2 磁盘格式化磁盘格式化 进程管理70w 分区分区：用分区软件把整个硬盘划分为若干个逻辑分：用分区软件把整个硬盘划分为若干个逻辑分区，每个分区可视为一个独立的磁盘。在多数计算区，每个分区可视为一个独立的磁盘。在多数计算机上，用第机上，用第0个扇区来存放一些系统启动代码和一个扇区来存放一些系统启动代码和一个分区表，记录了每个分

29、区的起始扇区和大小。个分区表，记录了每个分区的起始扇区和大小。w 高级格式化高级格式化：对每一个逻辑分区，分别进行一种高：对每一个逻辑分区，分别进行一种高级格式化（即通常的格式化操作），生成一个引导级格式化（即通常的格式化操作），生成一个引导块、空闲存储管理结构、根目录和一个空白的文件块、空闲存储管理结构、根目录和一个空白的文件系统。对不同的分区，可以使用不同的文件系统，系统。对不同的分区，可以使用不同的文件系统，如如FAT16、FAT32、NTFS等。等。进程管理71磁盘的访问是以扇区作为最小的寻址和存取单位，磁盘的访问是以扇区作为最小的寻址和存取单位，在访问一个磁盘扇区时，所需的时间主要有

30、：在访问一个磁盘扇区时，所需的时间主要有：柱面定位时间：磁头在磁头臂牵引下，移动到指柱面定位时间：磁头在磁头臂牵引下，移动到指定柱面的机械运动时间；定柱面的机械运动时间；旋转延迟时间：等待指定的扇区旋转到磁头的正旋转延迟时间：等待指定的扇区旋转到磁头的正下方所需的机械运动时间；它与磁盘转速有关，下方所需的机械运动时间；它与磁盘转速有关，如：软盘转速可为如：软盘转速可为600rpm(每分钟转速每分钟转速)，硬盘可，硬盘可为为7,200rpm至至10,000rpm；数据传送时间：从指定扇区读写数据的时间。数据传送时间：从指定扇区读写数据的时间。4.4.3 磁盘调度算法磁盘调度算法 进程管理72方法

31、方法1：合理地组织磁盘数据的存储位置。：合理地组织磁盘数据的存储位置。例子：磁盘转速为例子：磁盘转速为10,000rpm，每个磁道有，每个磁道有300个扇区个扇区,每个扇区有每个扇区有512字节，现要读一个字节，现要读一个150KB的文件。假设的文件。假设柱面定位柱面定位(平均平均)时间为时间为6.9毫秒，旋转延迟毫秒，旋转延迟(平均平均)时间为时间为旋转时间的一半旋转时间的一半(3ms)，扇区数据传送时间，扇区数据传送时间17微秒；微秒；(1)文件由同一个磁道上的文件由同一个磁道上的300个连续扇区构成：个连续扇区构成：(2)文件由文件由300个随机分布的扇区构成：个随机分布的扇区构成：随机

32、分布时的访问时间为连续分布时的随机分布时的访问时间为连续分布时的187倍倍。如何提高磁盘访问速度？如何提高磁盘访问速度？6.9ms+3ms+6ms=15.9ms;(why?)(6.9ms+3ms+0.017ms)*300=2975.1ms;进程管理73如何提高磁盘访问速度？如何提高磁盘访问速度？方法方法2：磁盘调度。：磁盘调度。w 对于大多数磁盘来说，柱面定位时间（磁头移动时对于大多数磁盘来说，柱面定位时间（磁头移动时间）在访问时间中占主要部分，因此减少平均的柱间）在访问时间中占主要部分，因此减少平均的柱面定位时间将有效地改进系统的输入输出性能。面定位时间将有效地改进系统的输入输出性能。w 基

33、本思路：来自基本思路：来自不同进程不同进程的磁盘访问请求构成一个的磁盘访问请求构成一个随机分布的请求队列。磁盘调度的基本思路就是通随机分布的请求队列。磁盘调度的基本思路就是通过对这些过对这些I/O请求的执行顺序进行调整，来减少整请求的执行顺序进行调整，来减少整个请求队列所对应的平均柱面定位时间。个请求队列所对应的平均柱面定位时间。w 磁盘调度算法：磁盘调度程序所采用的算法。磁盘调度算法：磁盘调度程序所采用的算法。谁来做这件事情？谁来做这件事情？进程管理741.先来先服务算法先来先服务算法w 先来先服务先来先服务(First-Come First-Served,FCFS)：按访：按访问请求到达的

34、先后顺序来依次执行。问请求到达的先后顺序来依次执行。w 优点：简单、公平；优点：简单、公平；w 缺点：效率不高。相邻的两次访问请求可能相距甚缺点：效率不高。相邻的两次访问请求可能相距甚远，从而使磁头反复地移动较长的距离。远，从而使磁头反复地移动较长的距离。w 举例：假设一个磁盘总共有举例：假设一个磁盘总共有200个柱面，它们的编个柱面，它们的编号为号为0199，访问请求的到达顺序为（柱面号）：，访问请求的到达顺序为（柱面号）：98，183，37，122，14，124，65，67，磁头的起，磁头的起始位置在始位置在53，计算磁头移动总距离。，计算磁头移动总距离。进程管理75（本图摘自（本图摘自S

35、ilberschatz,Galvin and Gagne：“Operating System Concepts”）458514685108110592在在FCFSFCFS算法下，磁头总共移动距离为算法下，磁头总共移动距离为640640。进程管理762.最短定位时间优先最短定位时间优先w 最短定位时间优先最短定位时间优先(Shortest Seek Time First,SSTF)：从访问请求队列当中，选择从当前磁头位置出发，从访问请求队列当中，选择从当前磁头位置出发，移动最少的访问请求去执行。移动最少的访问请求去执行。w 该算法的目标是使每次磁头移动时间最少。它不一该算法的目标是使每次磁头移动

36、时间最少。它不一定是最短平均柱面定位时间，但比定是最短平均柱面定位时间，但比FCFS算法有更算法有更好的性能。好的性能。w 如果要访问的扇区位于磁盘中间的柱面上，则比较如果要访问的扇区位于磁盘中间的柱面上，则比较有利；如果要访问的扇区位于磁盘两侧的柱面上，有利；如果要访问的扇区位于磁盘两侧的柱面上，则不太有利，可能会处于饥饿状态。则不太有利，可能会处于饥饿状态。进程管理77在在SSTFSSTF算法下，访问请求的执行顺序是：算法下，访问请求的执行顺序是：6565、6767、3737、1414、9898、122122、124124、183183。在这。在这8 8次磁盘访问中，次磁盘访问中，磁头总共

37、移动的距离为磁头总共移动的距离为236236，平均的移动距离为，平均的移动距离为29.529.5。12230238424259 进程管理78w 电梯算法（电梯算法（elevator algorithm），也叫扫描算法），也叫扫描算法（SCAN）：磁头从当前的位置开始，往一个方向）：磁头从当前的位置开始，往一个方向移动，依次执行这条路径上的所有访问请求，直到移动，依次执行这条路径上的所有访问请求，直到前面已无任何访问请求，然后反转方向继续进行。前面已无任何访问请求，然后反转方向继续进行。w 优点：克服了优点：克服了SSTF的缺点，既考虑了距离，同时的缺点，既考虑了距离，同时又考虑了方向，不会有进

38、程处于饥饿状态；又考虑了方向，不会有进程处于饥饿状态；w 一个性质：对于任何一组访问请求，磁头移动的总一个性质：对于任何一组访问请求，磁头移动的总距离有一个固定的上界，即柱面总数的两倍。距离有一个固定的上界，即柱面总数的两倍。3.电梯算法电梯算法 进程管理79在电梯算法下，访问请求的执行顺序是：在电梯算法下，访问请求的执行顺序是：3737、1414、6565、6767、9898、122122、124124、183183。在这。在这8 8次磁盘访问中，次磁盘访问中，磁头总共移动的距离为磁头总共移动的距离为208208，平均的移动距离为，平均的移动距离为2626。16235123124259下下 课课 啦啦!