第三节    缓冲管理 缓冲技术实现基本思想 当一个进程执行写操作输出数据时，先向系统申请一个主存区域──缓冲区，然后，将数据高速送到缓冲区。若为顺序写请求，则不断把数据填到缓冲区，直到它被装满为止。此后，进程可以继续它的计算，同时，系统将缓冲区内容写到I/O设备上。 当一个进程执行操作输入数据时，先向系统申请一个主存区域──缓冲区，系统将一个物理记录的内容读到缓冲区域中，然后根据进程要求，把当前需要的逻辑记录从缓冲区中选出并传送给进程。

Presentation on theme: "第三节    缓冲管理 缓冲技术实现基本思想 当一个进程执行写操作输出数据时，先向系统申请一个主存区域──缓冲区，然后，将数据高速送到缓冲区。若为顺序写请求，则不断把数据填到缓冲区，直到它被装满为止。此后，进程可以继续它的计算，同时，系统将缓冲区内容写到I/O设备上。 当一个进程执行操作输入数据时，先向系统申请一个主存区域──缓冲区，系统将一个物理记录的内容读到缓冲区域中，然后根据进程要求，把当前需要的逻辑记录从缓冲区中选出并传送给进程。"— Presentation transcript:

1 第三节    缓冲管理 缓冲技术实现基本思想 当一个进程执行写操作输出数据时，先向系统申请一个主存区域──缓冲区，然后，将数据高速送到缓冲区。若为顺序写请求，则不断把数据填到缓冲区，直到它被装满为止。此后，进程可以继续它的计算，同时，系统将缓冲区内容写到I/O设备上。 当一个进程执行操作输入数据时，先向系统申请一个主存区域──缓冲区，系统将一个物理记录的内容读到缓冲区域中，然后根据进程要求，把当前需要的逻辑记录从缓冲区中选出并传送给进程。 一、缓冲的引入 1、缓和CPU与I/O设备间速度不匹配的矛盾 2、减少对CPU的中断频率，放宽对CPU中断响应时间的限制 3、提高CPU与I/O设备之间的并行性（解决DMA或通道方式的瓶颈问题） 4*、解决逻辑记录与物理记录大小不相匹配的矛盾

2 二、缓冲技术的实现 硬缓冲（专用硬件缓冲器）： 软缓冲（内存缓冲区）： 缓冲区：有一定容量、暂存信息的存贮装置。
在设备中设置缓冲区，由硬件实现----贵且容量小 软缓冲（内存缓冲区）： 在内存中开辟一个空间，用作缓冲区 凡是数据到达和离去速度不匹配的地方均可采用缓冲技术。 在操作系统中采用缓冲是为了实现数据的I/O操作，以缓解CPU与外部设备之间速度不匹配的矛盾，提高资源利用率 引入缓冲区的缺点： 在系统区要设置相当大的缓冲池才能满足所有的Ｉ／Ｏ请求。 从系统缓冲区传送数据到调用进程缓冲区要花费额外的时间，增加了系统的总开销。

3 三、缓冲的种类 根据缓冲区的数量及组织形式，缓冲分为： 1、单缓冲： 单缓冲、双缓冲、多缓冲、缓冲池等多种类型。
在内存与外设间设立一个缓冲区。输入数据时，外设往缓冲区传送数据，CPU从缓冲区取数据存入内存。只有CPU取走数据后，外设才能送数据；输出数据过程与输入数据过程相反。在单缓冲情况下，发送和接受只能串行，影响了效率。 用户进程 工作区 缓冲区 I/O设备 输入 传送

4 2、双缓冲 双缓冲则是设立两个缓冲区。 在双缓冲情况下，发送和接收可以并行操作，但在外设与CPU间速度很不匹配时，仍不能适应工作。
用户进程 工作区 缓冲区 I/O设备 双缓冲则是设立两个缓冲区。 在双缓冲情况下，发送和接收可以并行操作，但在外设与CPU间速度很不匹配时，仍不能适应工作。

5 3、多缓冲 循环缓冲的引入 循环缓冲的组成 循环缓冲的使用 在双缓冲的基础上发展了多缓冲，多缓冲通过设立多个缓冲区来实现。
同步进程速度不一致； 双缓冲无法完全解决。 多个缓冲按顺序构成环形，先进先出队列的形式，设头尾、指针指向同一个缓冲区。头、尾指针读写时不能相互超越。 循环缓冲的组成 多个缓冲区、多个指针 循环缓冲的使用 GetBuf( ) ReleaseBuf( ) 多缓冲提高了CPU与外设并行操作程度，但往往会因缓冲区使用的不全面而造成一定的空间浪费。 R G C

6 4、缓冲池 P159 缓冲池的引入 缓冲池的组成 1） 三种类型的缓冲区： 2） 三种队列： 3）四种工作缓冲区：
把专用循环缓冲变为公用缓冲区，以提高内存利用率。 缓冲池的组成 1）  三种类型的缓冲区： 空缓冲区 装满输入数据的缓冲 装满输出数据的缓冲区 2） 三种队列： 空缓冲队列emq 输入队列 inq 输出队列 outq 3）四种工作缓冲区： 4）Getbuf (type)和Putbuf(type,number)过程 P160

7 5）缓冲区的工作方式 160 缓冲区的四种工作方式 （1）收容输入：收容输入设备的输入数据 （2）提取输入：计算进程提取缓冲区中的数据使用
Getbuf(emq);输入数据到缓冲；putbuf(inq,hin) （2）提取输入：计算进程提取缓冲区中的数据使用 Getbuf(inq)；提取数据，处理数据；putbuf(emq,sin) （3）收容输出：计算进程输出结果数据到缓冲区 Getbuf(emq);输出数据入缓冲；putbuf(outq,hout) （4）提取输出：输出设备提取缓冲区中的数据 Getbuf(outq);输出数据；putbuf (emq,sout） 缓冲池 hin sout sin hout 收容输入 提取输出 用户程序 提取输入 收容输出

8 第四节 设备分配 161 设备分配中的数据结构 设备分配时应考虑的因素 设备独立性 独占设备的分配程序 SPOOLing技术
第四节    设备分配 161 设备分配中的数据结构 设备分配时应考虑的因素 设备独立性 独占设备的分配程序 SPOOLing技术 具有通道结构的计算机系统，在内存、通道、控制器及设备间，采用四级连接、实施三级控制的方式。

9 设备管理程序 设备管理按其功能可分为： I/O控制程序：监视系统中所有设备的状态。 解决3个问题： 有否用来为I/O请求服务的通路
是否有一条以上的通路可用 如果当前无通路可用，则何时通路空闲 2.设备分配程序：按一定算法分配设备 3.设备处理程序：处理外设的中断请求、解释执行控制命令及广义指令、驱动外设操作（设备驱动程序、中断处理程序等）

10 一. 设备管理中的数据结构 P161 设备控制表（ＤＣＴ） 每个设备一个 控制器控制表（ＣＯＣＴ） 每个控制器一个 通道控制表（ＣHＣＴ）
每个通道一个 系统设备表（ＳＤＴ） 整个系统一个

11 1 系统设备表SDT 整个系统一张表，记录系统中所有I/O设备的信息， 表目包括： 设备类型、设备标识符、进程标识符、DCT表指针等 …
表目1 … 表目2 设备类 设备标识符 DCT 驱动程序入口

12 2 设备控制表DCT 一台设备配置一张设备控制表，用于记录设备状态； 包含的字段： 设备类型 type 设备标识符 deviceid
设备状态：设备或与其相连的控制器/通道忙，状态为“1”； 设备队列队首指针：指向等待此设备的阻塞进程队列； 与设备连接的控制器表指针：多条通路则对应多个指针； 重复执行次数或时间：允许通信重试的次数或延迟时间。

13 3、控制器控制表COCT 4、通道控制表CHCT
表项字段：控制器标识符、控制器状态、与控制器相连的通道表指针、控制器队列的队首指针、控制器队列的队尾指针。 4、通道控制表CHCT 表项字段：通道标识符、通道状态、与通道连接的控制器表首址、通道队列的队首指针、通道队列的队尾指针。

14 5、各数据结构间的连接关系

15 二. 设备分配策略 P162 由于在多道程序系统中，进程数多于资源数，引起资源的竞争。因此，要有一套合理的分配原则 考虑的因素：
* I/O设备的固有属性 * I/O设备的分配算法 * 设备分配的安全性 * 与设备的无关性

16 1、 I/O设备的固有属性（独享、共享、虚拟分配技术）
独占设备: 独享分配方式 共享设备: 共享分配方式 虚拟设备: 虚拟分配方式:把一台输入机虚拟为几台“虚拟”的输入机。例如：为了提高设备利用率引入了脱机输入输出或采用ＳＰＯＯＬＩＮＧ技术，变一台为“多台设备”

17 2、Ｉ/Ｏ设备的分配算法 Ｉ/Ｏ设备的分配机制，除了与ＩＯ设备的固有属性有关外，还与系统所采用的分配策略有关。Ｉ/Ｏ设备的分配与进程调度很能相似，同样可采用如下的一些算法：
先请求先服务：当有多个进程对同一设备提出Ｉ/Ｏ请求时，该算法要求把所有发出Ｉ/Ｏ请求的进程，按其发出请求的先后次序排成一个等待该设备的队列。设备分配程序把Ｉ/Ｏ设备分配给队列中第一个进程。 优先权最高者优先。对于何必先权相同的ＩＯ请求，则按先请求先分配的原则排队。

18 3、 设备分配的安全性 P163 为了能同时操作多个Ｉ/Ｏ设备以加速进程的推进，应使得某进程以命令形式发出Ｉ/Ｏ请求后，仍可继续运行，需要时又可发出第二个、第三个Ｉ/Ｏ请求。多请求方式的缺点是，设备分配不安全，因为它具备请求和保持条件，因而有可能产生死锁的情况。由此可见，在多请求方式中，设备的分配程序应保证不发生进程死锁。 静态分配法 动态分配中采用一定的策略

19 4、 与设备无关性 P163 　　为实现程序与设备独立，在程序中引入逻辑设备概念，逻辑设备与物理设备的连接在进程运行时动态实现，这一特性称为设备无关性，也叫设备独立性 。 优点： （1）用户程序独立性增强 不因外设的变化而变化 （2）易对付I/O设备故障，从而提高系统可靠性 （3）增加外设分配的灵活性，更充分使用外设以实现多道程序设计 设备独立性软件 位于驱动程序之上，驱动程序与设备有关。 主要功能： 执行所有设备的公有操作：分配与回收、逻辑名到物理设备的映射、设备的保护、缓冲管理、差错控制等 向用户层（或文件层）软件提供统一接口

20 逻辑设备名到物理设备名映射的实现 逻辑设备表（Logical Unit Table LUT） 用于将应用程序所使用的逻辑设备名映射为物理设备名。 表项：逻辑设备名、物理设备名、设备驱动程序入口地址等 LUT的设置问题 整个系统一张LUT，逻辑设备名要具有唯一性。 为每个用户设置一张LUT，并将该表放入PCB中；与系统设备表联合作用。

21 三. 设备分配程序 当系统中已经设置了数据结构，且确定了一定的分配原则后，如果某进程提出了ＩＯ请求，便可按下述步骤进行设备分配：
根据用户请求的I/O设备的逻辑名，查找逻辑设备和物理设备的映射表；以物理设备为索引，查找SDT，找到该设备所连接的DCT；继续查找与该设备连接的COCT和CHCT，就找到了一条通路。即：分配设备 －>分配控制器->分配通道

22 设备分配程序的改进 原因：以物理设备名提出I/O请求，但通路的I/O结构，容易产生“瓶颈”现象。
增加设备的独立性：使用逻辑设备名请求I/O，依次查同类设备的DCT，仅当该类设备都忙时，才把进程挂在该类设备的等待队列上；如果有设备可用，继续分析安全性…… 考虑多通路情况：得到设备后，依次检查与此设备相连的各个控制器，直到找到一个可用的为止；然后，依次检查与此控制器相连的各个通道，直到确定一个可用的通道位置；否则，需要阻塞进程。

23 设备的分配过程各步骤的描述 1）分配设备 根据进程（或用户）的I/O请求，查SD T找到所需设备的DCT，查看DCT中的信息。若有空闲的设备且分配是安全的，则实施该设备分配，然后转第2）步进行控制器分配；如果设备忙或分配不安全，则进程加入此设备的等待队列等待设备空闲。 2）分配相应的控制器 根据DCT找到与设备连接的控制器的CUCB，查看CUCB中的信息。若有空闲的控制器，则分配控制器；否则根据实际，将进程加入等待队列或转第1）步重新开始。 3）分配通道 根据控制器的CUCB找到与该控制器连接的通道的CCB，查看CCB中的信息。若有空闲的通道则分配通道；否则根据实际将进程加入等待队列或转第2）步重新开始。 处于等待队列的进程，当所等待的事件结束后，再继续分配过程。

24 为进程P分配所需的I/O设备 从SDT表查该类设备的控制表DCT 由DCT检查该设备忙否? 检查分配此设备的安全性? 分配此设备给进程P
N 由DCT检查该设备忙否? 不忙 不安全 最后一个DCT? 检查分配此设备的安全性? Y 进程P的PCB放入 此设备的等待队列 分配此设备给进程P 忙 N 查此设备连接的COCT忙否? 最后一个COCT? 不忙 分配此控制器给进程P Y N 最后一个DCT? 忙 查此控制器连接的CHCT忙否? N Y 最后一个CHCT? 不忙 进程 P 的 PCB 放入 此控制器的等待队列 N Y 分配此通道给进程P 最后一个COCT? Y 启动I/O,进行具体的I/O操作 进程 P 的 PCB 放入 此通道的等待队列 多通路设备分配流程示意图

25 四、 SPOOLing技术 (Simultaneous Peripheral Operation On Line)也称同时联机的外围操作系统或是伪脱机系统。 虚设备 在一类设备上模拟另一类设备，常用共享设备模拟独占设备，用高速设备模拟低速设备，被模拟的设备称为虚设备 目的：将慢速的独占设备改造成多个用户可共享的设备，提高设备的利用率 （实例：SPOOLing技术，利用虚设备技术 ——用硬盘模拟输入输出设备）

26 （一）信息交换方式： I/O设备与CPU 间有三种信息交换方式： 1、联机输入输出方式： 2、脱机输入输出方式： 3、 SPOOLing方式（斯普林方式） ----上述两种信息交换方式的组合。 以联机输入输出方式获得脱机输入输出方式的优点 （假脱机） 联机的同时外围设备操作又称为假脱机操作。 斯普林系统 操作系统中用一类物理设备模拟另一类物理设备，使独占设备变成共享设备这一技术的功能模块。

27

28 （二）SPOOLING系统的设计与实现 一个完整的SPOOLING 系统中有硬件部分和软件部分，它们之间协调配合，共同实现了伪脱机技术。 1、硬件部分： “井”及缓冲区： 包含了在磁盘或磁鼓上设立的两区域：输入井和输出井，以及在主存中开辟出的两个缓冲区：输入缓冲区和输出缓冲区。  输入井：用来存放来自于输入设备的信息。  输出井：用来保存即将送到输出设备上的结果。  输入缓冲区：暂时保存外设准备送入输入井的信息。  输出缓冲区：暂时保存从输出井送出的结果。

29 2、 SPOOLING系统的主要功能： 1）将输入设备上的信息写到外存输入井上； 2）系统或用户程序从外存输入井中读出信息； 3）系统或用户程序将数据写到外存输出井上； 4）从外存输出井中将待输出数据交给慢速输出设备输出 3、软件部分： ●预输入程序（进程）：将用户要求的输入数据输入设备上，经通道和输入缓冲区送入输入井。 ●缓输出程序（进程）：将用户的输出结果在设备空闲时从输出井中，经输出缓冲区送上输入设备。 ●井管理程序： 井输入管理程序（进程） ：将输入井中的数读如内存。 井输出管理程序（进程） ：将内存中的结果送输出井中

30 第五节    设备处理（驱动） 设备驱动程序：驱动物理设备和DMA控制器或I/O控制器等直接进行I/O操作的子程序集合。

31 输入输出控制系统（IOCS） IOCS实质上类似于一个交通管制程序 校验请求的设备是否可用 必要时挂起请求的进程 启动设备驱动程序
LIOCS：执行用户定位和存取逻辑记录所需的许多功能 逻辑记录的成组与分解 双缓冲时，I/O缓冲区的转换 处理文件结束和卷结束条件 向PIOCS发出I/O请求 PIOCS：实现物理上数据传送的程序，是IOCS控制主存和外设进行数据传送的部分。监督通道程序的执行，按物理块传送数据，不涉及被传送文件的类型、逻辑记录的内容和格式。 I/O调度程序、I/O启动程序、I/O中断处理程序、外设错误处理程序

32 (1) 接收由I/O进程发来的命令和参数，并将命令中的抽象要求转换为具体要求，例如，将磁盘块号转换为磁盘的盘面、 磁道号及扇区号。
一. 设备驱动程序的功能和特点 1、 设备驱动程序的功能 (1) 接收由I/O进程发来的命令和参数，并将命令中的抽象要求转换为具体要求，例如，将磁盘块号转换为磁盘的盘面、 磁道号及扇区号。 (2) 检查用户I/O请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式。 (3) 发出I/O命令，如果设备空闲，便立即启动I/O设备去完成指定的I/O操作；如果设备处于忙碌状态，则将请求者的请求块挂在设备队列上等待。 (4) 及时响应由控制器或通道发来的中断请求，并根据其中断类型调用相应的中断处理程序进行处理。 (5) 对于设置有通道的计算机系统，驱动程序还应能够根据用户的I/O请求，自动地构成通道程序。

33 2、 设备处理方式 ●设备控制过程的实现方式 ●设备处理方式 (1) 为每一类设备设置一个进程，专门用于执行这类设备的I/O操作。
作为系统进程执行：每类设备一个进程，或整个系统一个进程处理各类设备 不设进程，作为OS核心中的设备驱动程序 ●设备处理方式 (1) 为每一类设备设置一个进程，专门用于执行这类设备的I/O操作。 (2) 在整个系统中设置一个I/O进程，专门用于执行系统中所有各类设备的I/O操作（分输入进程/输出进程） (3) 不设置专门的设备处理进程，而只为各类设备设置相应的设备处理程序(模块)，供用户进程或系统进程调用。

34 3、 设备驱动程序 设备驱动程序是一种低级的系统例程。它必须和系统的输入输出硬设备相互通信。使用特权Ｉ/Ｏ指令来访问硬件，它通常是用汇编语言或系统编程语言写的。 任务：主要负责接收和分析从设备分配转来的信息，并根据设备分配的结果，结合具体物理设备特性完成有关的具体工作。 管理----系统中设置有设备开关表DST（Device Switch Table）.含相应设备的各种操作子程序的入口地址（二维表结构------设备类型/驱动程序类型；是I/O进程的一个数据结构）；I/O控制过程为进程分配设备和缓冲区之后，可以使用设备开关表调用所需的驱动程序进行I/O操作。

35 设备驱动程序的特点P168 (2) 驱动程序与设备控制器和I/O设备的硬件特性紧密相关，因而对不同类型的设备应配置不同的驱动程序。
(3) 驱动程序与I/O设备所采用的I/O控制方式紧密相关。 (4) 由于驱动程序与硬件紧密相关，因而其中的一部分必须用汇编语言书写。

36 二. 设备驱动程序的处理过程 P169 启动过程：开动一个I/O操作 继续过程：I/O操作开始后的数据传送及负责处理中断
●检查设备的状态---设备是否可用 处理器与外设的接口中包含有几个内部寄存器 内部寄存器 数据寄存器 状态寄存器 操作方式寄存器（同步/异步） 命令寄存器 ●检测的实现： 将设备的状态寄存器内容读入到CPU，测试其不同的位来实现 ●启动I/O请求 向设备的控制寄存器写入控制字 将抽象要求转换为具体要求 2. 检查I/O请求的合法性 3. 读出和检查设备的状态 4. 传送必要的参数 5. 工作方式的设置 6. 启动I/O设备 启动过程：开动一个I/O操作 继续过程：I/O操作开始后的数据传送及负责处理中断

37 3、中断处理程序的处理过程 P170 唤醒被阻塞的驱动（程序）进程 保护被中断进程的CPU环境 转入相应的设备处理程序 中断处理
恢复被中断进程的现场 即：I/O请求完成后------驱动程序检测设备状态 正常结束----进程由等待态就绪态 非正常结束--- 重新执行此I/O操作； 中止调用进程，报告出错信息 将状态报知调用进程，由其处理

38 中断现场保护示意图 中断处理流程

39 I/O的操作全过程 4 1 2 5 3 用户程序 管理程序 通道程序 设备控制器和设备 程序P 保护现场 组织通道程序 保存通道程序
的始址于CAW 启动I/O指令 分析条件码 启动成功使 P阻塞, 另选 程序q运行 保护程序q的 现场 分析中断原因 处理I/O中断 选择可运行程序 执行规定 的操作 判断状态 执行通道程序 控制I/O设备 操作,执行情 况记录在CSW 出现中断事件 CSW=>主存通 道号, 设备号 送特定寄存器 4 1 请求 启动程序 2 5 3 程序q I/O的操作全过程

40 第六节    磁盘存储管理 磁盘性能简述 磁盘调度 磁盘高速缓存 提高磁盘I/O速度的其它方法 廉价磁盘冗余阵列

41 5.6.1 磁盘性能简述 1. 数据的组织和格式 P172 磁盘的格式化

42 2. 磁盘的类型 1) 固定头磁盘 这种磁盘在每条磁道上都有一读/写磁头，所有的磁头都被装在一刚性磁臂中。通过这些磁头可访问所有各磁道，并进行并行读/写，有效地提高了磁盘的I/O速度。这种结构的磁盘主要用于大容量磁盘上。 2) 移动头磁盘 每一个盘面仅配有一个磁头，也被装入磁臂中。为能访问该盘面上的所有磁道，该磁头必须能移动以进行寻道。可见，移动磁头仅能以串行方式读/写，致使其I/O速度较慢；但由于其结构简单，故仍广泛应用于中小型磁盘设备中。

43

44 3. 磁盘访问时间 为了访问磁盘上的一个物理记录，必须给出三个参数：柱面号、磁头号、块号。
寻道时间Ts （‘查找时间’，平均需20毫秒左右 ） 把磁臂（磁头）移动到指定磁道上所经历的时间，包含启动磁臂和磁头移动n条磁道所花费的时间。 旋转延迟时间T（“搜索延迟”，平均要10毫秒 ） 指定扇区移动到磁头下面所经历的时间。与盘面的旋转速度有关。 5400转--5.55ms；7200转—4.16ms 传输时间Tt 把数据从磁盘读出或向磁盘写入数据所经历的时间。与旋转速度和一次读写的数据量有关。

45 5.6.2 磁盘调度 P173 先来先服务FCFS 最短寻道时间优先SSTF 扫描（Scan）算法 循环扫描（CScan）算法
来自不同进程的磁盘I/O请求构成一个随机分布的请求队列。磁盘I/O调度的主要目标就是减少请求队列对应的平均柱面定位时间。 影响I/O请求服务效率的因素： （1）I/O请求的次序 （2）信息在外存的存放次序 （3）存储空间的分配方法 先来先服务FCFS 最短寻道时间优先SSTF 扫描（Scan）算法 循环扫描（CScan）算法 *N-Step-Scan和FSCAN算法

46 5.6.2 磁盘调度 根据进程请求访问磁盘的先后次序进行调度。 优点： 缺点： 公平、简单；
磁盘调度 1. 先来先服务FCFS(First-Come, First Served) FCFS调度算法 根据进程请求访问磁盘的先后次序进行调度。 优点： 公平、简单； 缺点： 平均寻道时间可能较长，仅适用于磁盘请求较少的场合。

47 (Shortest Seek Time First)
2. 最短寻道时间优先SSTF (Shortest Seek Time First) SSTF调度算法 选择要求访问的磁道与当前磁头所在的磁道距离最近的进程（磁盘请求），使每次的寻道时间最短。 该算法不能保证平均寻道时间最短。 可能导致“饥饿”现象。

48 3. 扫描(SCAN)算法 1) 进程“饥饿”现象 SSTF算法虽然能获得较好的寻道性能， 但却可能导致某个进程发生“饥饿”(Starvation)现象。因为只要不断有新进程的请求到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必须优先满足。对SSTF算法略加修改后所形成的SCAN算法，即可防止老进程出现“饥饿”现象。 磁头每次只作单方向移动，直到到达边缘磁道为止，然后再作反向移动。 下一次待访问的磁道只能在此头移动的前方，且选择磁头移动距离最近的一个磁盘请求响应。 又称为“电梯调度算法”。 消除了饥饿现象。

49 2) SCAN算法 SCAN调度算法示例

50 4. 循环扫描(CSCAN)算法 磁头只作由内向外的单方向扫描，到达外边缘后，则返回最内侧的磁道重新进行下一轮扫描。
改进了对于边缘区磁道访问的不公平。 CSCAN调度算法示例 “单向扫描”算法。这是为适应不断有大量存取请求进入系统的情况而设计的一种扫描方式。移动臂总是从0号柱面至最大号柱面顺序扫描，然后直接返回0号柱面重复进行。在一柱面上，移动臂停留至磁盘旋转过一定圈数，然后再移向下一个柱面。这样能够缩短刚离开的柱面上又到达的大量I/O请求的等待时间，为了在磁盘转动每一圈的时间内执行更多的存取，必须考虑旋转优化问题。

51 5. N-Step-SCAN和FSCAN调度算法
在SSTF、SCAN及CSCAN几种调度算法中，都可能出现磁臂停留在某处不动的情况 “磁臂粘着”现象：一个或几个进程对某一磁道有较高的访问频率时，造成磁头的“不移动”现象。 N步扫描：把磁盘访问请求排成长度为N的多个队列。系统在处理完一个磁盘请求队列的工作后，再响应其它队列的请求。 处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。当正在处理某子队列时，如果又出现新的磁盘I/O请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。 当N值取得很大时，会使N步扫描法的性能接近于SCAN算法的性能； 当N=1时， N步SCAN算法便蜕化为FCFS算法。

52 2) FSCAN算法 对N步扫描的简化。只排两个队列：当前队列、等待队列。
一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。 在扫描期间，将新出现的所有请求磁盘I/O的进程， 放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。

53 5.6.3 磁盘高速缓存(Disk Cache) 1. 磁盘高速缓存的形式
并非通常意义上的高速缓存，而是利用内存中的空闲空间，暂存从磁盘中读出的一系列盘块中的信息。逻辑上属于磁盘，物理上驻留内存的磁盘数据块区。 高速缓存在内存中可分成两种形式: 第一种:固定大小的磁盘高速缓存，不受应用程序多少影响。 (在内存中开辟一个单独的存储空间来作为磁盘高速缓存，其大小是固定的，不会受应用程序多少的影响) ； 第二种:可变大小的磁盘高速缓存——“缓冲池”形式(把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘I/O时(作为磁盘高速缓存)共享。此时高速缓存的大小，显然不再是固定的。当磁盘I/O的频繁程度较高时，该缓冲池可能包含更多的内存空间；而在应用程序运行得较多时，该缓冲池可能只剩下较少的内存空间。)

54 2. 数据交付方式 Data Delivery：将磁盘高速缓存中的数据传送给请求者进程。 系统可以采取两种方式：
(1) 数据交付。这是直接将高速缓存中的数据，传送到请求者进程的内存工作区中。 (2) 指针交付。只将指向高速缓存中某区域的指针， 交付给请求者进程。 后一种方式由于所传送的数据量少，因而节省了数据从磁盘高速缓存存储空间到进程的内存工作区的时间

55 3.磁盘缓存置换算法 磁盘缓存置换算法也称为“访问频率替换算法”
由于请求调页中的联想存储器与高速缓存(磁盘I/O中)的工作情况不同，因而使得在置换算法中所应考虑的问题也有所差异。因此，现在不少系统在设计其高速缓存的置换算法时，除了考虑到最近最久未使用这一原则外，还考虑了以下几点： (1) 访问频率。 (2) 可预见性。 (3) 数据的一致性。 较常用的算法： 最近最久未使用LRU 最近未使用NRU（Clock） 最少使用LFU

56 4. 周期性地写回磁盘 后台专用程序: 定期自动保存
在UNIX系统中专门增设了一个修改(update)程序， 使之在后台运行，该程序周期性地调用一个系统调用SYNC。该调用的主要功能是强制性地将所有在高速缓存中已修改的盘块数据写回磁盘。一般是把两次调用SYNC的时间间隔定为30 s。这样，因系统故障所造成的工作损失不会超过30 s的劳动量。 在MS-DOS中所采用的方法是：只要高速缓存中的某盘块数据被修改，便立即将它写回磁盘，并将这种高速缓存称为“写穿透、高速缓存”(write-through cache)。MS-DOS所采用的写回方式，几乎不会造成数据的丢失， 但须频繁地启动磁盘。 定期自动保存 间隔一定时间，强制性地把所有缓存中的已修改的盘块数据写回磁盘。

57 5.6.4 提高磁盘I/O速度的其它方法 提前读(Read-Ahead) 2. 延迟写 3. 优化物理块的分布 (****)
4. 虚拟盘 ：利用内存去仿真磁盘

58 优化物理块的分布 循环排序 : 考虑每一磁道保存4个记录的旋转型设备，假定收到四个输入输出请求并且存在一条到该设备的可用道路。
请示次序及记录号分别为：（1） 读记录4；（2） 读记录3； （3） 读记录2；（4） 读记录1 对这些输入输出请求有多种排序方法： l方法1：如果调度算法按照输入输出请求次序读记录4、3、2、1，假定平均要用1/2的周来定位，再加上1/4周读出记录，则总的处理时间等于3周，即60毫秒。 l方法2：如果调度算法决定的读入次序为读记录1、2、3、4。那么，总的处理时间等于1.5周，即30毫秒。 l方法3：如果我们知道当前读位置是记录3，则调度算法采用的次序为读记录4、1、2、3会更好。总的处理时间等于１周，即20毫秒。

59 优化物理块的分布 优化分布 信息在存储空间的排列方式也会影响存取等待时间。考虑10个逻辑记录A，B……，J被存于旋转型设备上，每道存放10个记录，可安排如下： 假定要经常顺序处理这些记录，而旋转速度为20毫秒，处理程序读出每个记录后花4毫秒进行处理。则读出并处理记录A之后将转到记录D的开始。所以，为了读出B，必须再转一周。于是，处理10个记录的总时间为：10毫秒(移动到记录A的平均时间)+ 2毫秒(读记录A)+4毫秒(处理记录A)+9×[16毫秒(访问下一记录) +2毫秒(读记录)+4毫秒(处理记录)]＝214毫秒

60 当读出记录A并处理结器束后，恰巧转至记录B的位置，立即就可读出并处理。按照这一方案，处理10个记录的总时间为：10毫秒(移动到记录A的平均时间)+10×[2毫秒（读记录）×4毫秒（处理记录）]=70毫秒 比原方案速度几乎快3倍，如果有众多记录需要处理，节省时间更可观了。

61 优化物理块的分布 交替地址 旋转型存储设备上的任意记录的存取时间主要由旋转速度来确定，对于给定地装置这一速度是常数。把每个记录重复记录在这台设备的多个区域，可以显著地减少存取时间。这样读相同的数据，不有几个交替地址，这种方法也称为多重副本或折迭。 让我们考虑一种设备。若每道有8个记录，则旋转速度20毫秒，如果记录A存于道1，记录1，存取记录A平均占半周，即10毫秒。如果记录A的副本存于道1，记录1和道1，记录5，那么，使用旋转位置测定，总是存取“最近”的副本，有效的平均存取时间可降为５毫秒。类似地，存储更多相同数据记录的副本，可以把存取时间进一步折半。这一技术的主要缺点是耗用较多存储空间，有效容量随副本个数增加而减少，如果每个记录有n个副本，存储空间就被“折迭”了n次。 此法成功与否取决于下列因素：数据记录总是读出使用，不需修改写入；数据记录占用的存储空间总量不太大；数据使用极为频繁。所以，通常对系统程序采用了这一技巧，它们能满足上述诸因素。

62 5.6.5 廉价磁盘冗余阵列 RAID(Reundant Array of Independent Disks)
利用一台磁盘阵列控制器，来统一管理和控制一组（几台到几十台）磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统 并行交叉存取 图 5-27 磁盘并行交叉存取方式 2、 RAID的分级

63 RAID的分级 RAID样式共有6级组成，RAID0至RAID5，最新又扩充了RAID6和RAID7，它们之间并不隐含层次关系，而是标明了不同的设计结构，并有三个共同特性: ①RAID是一组物理磁盘驱动器，可以被操作系统看作是单一的逻辑磁盘驱动器; ②数据被分布存储在阵列横跨的物理驱动器上; ③冗余磁盘的作用是保存奇偶校验信息，当磁盘出现失误时它能确保数据的恢复。