第六章 输入输出系统

操作系统五大部分之一，最复杂与硬件相关，主要管理:

• 打印进，扫描仪等IO设备
• 磁盘，磁带机等外部存储设备

6.1 I/O系统的功能，模型和接口

主要对象:I/O设备和相应的设备控制器
主要任务:完成用户提出的I/O请求；提高I/O速率,以及提高设备的利用率；为更高层的进程方便地使用

6.1.1 I/O系统的基本功能

为了方便用户使用I/O设备

①隐藏物理设备的细节
②与设备的无关性

为了提高CPU和I/O设备利用率

③提高处理机和IO设备的利用率
④对I/O设备进行控制

为用户在共享设备时提供方便

⑤确保对设备的正确共享
⑥错误处理

6.1.2 I/O系统的层次结构和模型

1. I/O系统为什么采用层次结构

   IO软件向下与硬件有关，向上与文件系统，VM，用户交互，复杂

   层次结构使IO结构清晰，可移植性适应性更好

   OS普通采用层次结构IO系统:

   • 将IO系统分为多层
   • 每层利用下层提供的服务，完成IO系统中的某些子功能，并屏蔽实现细节，向更高层提供服务

2. IO系统的层次结构

   ①I\O软件层次

   • 用户层IO软件:与用户交互，给用户操作设备提供了库函数(产生IO请求，格式化IO，Spooling)

   • 设备独立性软件:实现用户与设备驱动器的统一接口，设备命令，设备保护，分配释放，缓冲区管理

   • 设备驱动程序:与硬件直接想关，实现CPU向设备发出的操作命令，驱动IO设备工作

   • 中断处理程序:保存现场信息，转ISR，恢复现场，返回

     

     图1.IO系统层次示意图

②IO系统各模块层次示意图

图2.IO系统各模块层次示意图

6.1.3 I/O系统接口

IO系统与高层接口分类

根据设备类型可分3个接口:

• 块设备接口
• 流设备接口
• 网络通信接口

1. 块设备接口

   块设备与高层间接口

   • 数据存储和传输以块为单位的设备，磁盘，光盘
   • 速率高，可寻址，可随机访问，DMA传输

• 隐藏磁盘二维地址结构:磁道->扇区->逻辑块号
• 将上层抽象命令映射为底层操作，逻辑块号为具体磁盘地址
• 虚拟存储器利用块设备接口实现页面调入调出

2. 流设备接口

   流设备与高层之间的接口，也叫字符设备接口

   • 数据存储和传输以字符为单位的设备，键盘，打印机，鼠标
   • 速率低，不可寻址，中断传输

• 顺序写入/读出，采用缓冲区，put/get操作
• 字符设备种类多，差异大，流接口提供in-control设置设备参数
• 大多数流设备是独占设备，互斥访问，用open/close

3. 网络接口

   现在的操作系统都提供面向网络接口

   网络设备与上层间的接口

   • 网络设备:网卡等
   • OS提供网络软件和网络通信接口，计算机通过网络与其他计算机进行通信与数据访问

6.2 I/O设备和设备控制器

6.2.1 I/O设备

1. I/O设备类型

   ①按共享特性:独占设备和共享设备

   ②按传输特性:块设备和流设备(字符设备)

   ③按使用特性:存储设备和I/O设备

   ④按传输速率分类:低速，中速和高速设备

2. 设备与控制器之间的接口

   设备并不直接与CPU通信，而是与设备控制器通信

   

   图3.设备与控制器之间的接口

6.2.2 设备控制器

CPU与IO设备之间的接口，可以连接一个或多个设备

实现IO设备与CPU之间的数据交换

分类:字符设备控制器，块设备控制器，网络设备控制器

1. 设备控制器的基本功能

   ①接受和识别命令

   ②数据交换

   ③标识和报告设备状态

   ④地址识别

   ⑤数据缓冲区

   ⑥差错控制

2. 设备控制器的组成

   • 设备控制器与CPU之间的接口
   • 设备控制器与I/O设备之间的接口
   • I/O逻辑

   

   图4.设备控制器的组成

6.2.3 内存映像IO

设备控制器有数据R/命令R/状态R等，称为设备端口

• 每个端口都有地址，CPU通过端口地址控制设备控制器工作

• 端口地址有两种编址方式

  ①设备独立编址方式(利用特定I/O指令方式)

  ②与内存统一编址(内存映像方式)

1. 利用特定I/O指令

   用于独立编址，端口地址与内存地址不可重叠，读端口和读内存用不同的指令，通过IO指令控制设备端口读写，如微机:IN/OUT/MOV

2. 内存映像IO

   用于统一编址中，端口地址与内存地址统一编制，作为内存地址空间的一部分，读端口和读内存用相同指令，简化IO编程

   

   图5.设备寻址形式

6.2.4 I/O通道

1. I/O通道设备的引入

   • 设备控制器减少了CPU对IO设备的干预

   • 大型机增设IO通道

   • IO通道是一种特殊处理机:只执行IO指令，与CPU共享内存

   • 把CPU从繁重IO任务解脱

     ①数据传输由通道完成

     ②IO操作组织，管理及结束工作尽量独立由通道完成

     ③CPU专注数据计算

• 通道是一种特殊的处理机:
  • 与处理机又不同:
    • 通道没有自己的内存
    • 通道指令类型单一

2. 通道类型

   ①字节多路通道:以字节交叉方式工作，连接多个低速设备，按时间片轮转方式为多个设备服务

   ②数组选择通道:可连接多个高速设备，一次只服务一个设备，通道利用率低

   ③数组多路通道:将数组选择通道传输速率高和字节多路通道能使各子通道(设备)分时并行操作相结合，按数组方式传输，速率高，通道利用率高

3. 通道传输瓶颈问题

   由于通道价格昂贵，即必然数量少，这往往成为了IO的瓶颈，进而导致系统吞吐量下降。

   • 解决办法:增设通路而不增加通道，一个设备连接多个控制器，一个控制器连接多个设备

   

   图6.单通路IO系统示意图

图7.多通路IO系统示意图

6.3 中断机构和中断处理程序

6.3.1 中断简介

1. 中断和陷入

   中断:IO设备向CPU发出的信号，又称外部中断。CPU暂停正在执行的程序，保留CPU环境后，自动地转去执行该IO设备的中断处理程序。

   陷入:由CPU内部事件所引起的中断，又称内中断。例如:运算溢出，程序出错，如非法指令，地址越界。

2. 中断向量表和中断优先级

   中断向量表:

   • OS为每个中断都配备一个中断号和中断处理程序(ISR)

   • ISR在内存的首地址称为中断向量

   • 系统所有中断向量放在一起构成表格称为中断向量表IVT

     过程:中断号查IVT，得到向量转ISR执行

     微机系统:IVT=1KB,每个中断向量4B，共256个中断

   中断优先级:

   • 根据中断紧迫程度为中断安排优先级
   • 优先级越高越紧迫
   • 高优先级可打断低优先级的执行，中断嵌套

3. 对多级中断源的处理方式

   屏蔽(禁止)中断:处理中断时屏蔽所有中断

   简单，所有中断按顺序处理，不能满足实时性要求高的中断请求

   嵌套中断

   • 如果同时有多个中断发送，先处理优先级高的中断
   • 高优先级中断可抢占低优先级中断CPU

6.3.2 中断处理程序

• 进程请求I/O操作将被挂起

• I/O设备完成I/O操作后，设备控制器向CPU发出I/O中断请求

• CPU响应后转入中断处理程序

• 中断处理程序执行相应处理，处理完解除相应进程的阻塞状态

中断处理程序的处理过程

①测定是否有未响应的中断信号

②保护被中断进程的CPU环境

③转入相应的设备处理程序

④中断处理

⑤恢复CPU的现场并退出中断

图8.中断保护线程示意图

图9.中断处理流程图

6.4 设备驱动程序

• 设备处理程序又称设备驱动程序

• 是I/O系统的高层与设备控制器之间的通信程序，主要任务:

  ①接受上层软件抽象I/O命令，转换为具体参数发给设备控制器，启动设备执行

  ②由设备控制器发来的信号传送给上层软件

• 驱动程序与硬件密切相关，应为每类设备配置一种驱动程序

6.4.1 设备驱动程序概述

1. 设备驱动程序功能

   ① 接受设备无关层软件的命令和参数，将抽象命令转换为与设备相关的低层操作序列

   ② 检查I/O合法性，了解设备工作状态，传递与I/O设备有关的操作序列，设置设备工作方式

   ③发出I/O命令，若设备空闲便启动I/O设备完成操作；若设备忙碌则将请求块挂在设备队列上等待

   ④及时响应设备控制器的中断请求，根据中断类型调用相应中断处理程序

2. 设备驱动程序的特点

   driver属于低级系统例程，与应用程序及一般系统程序的差异

   ① 实现设备无关层软件与设备控制器的通信和转换程序

   ② 与设备控制器及I/O设备紧密相关

   ③ 与I/O设备所采用的I/O控制方式紧密相关，若中断驱动和DMA

   ④ 因为与设备的紧密相关，许多用汇编语言编写。目前很多驱动程序已经固化在ROM中

   ⑤ 驱动程序应允许可重入，一个正在运行的驱动程序常会在一次调用完成前再次被调用。

3. 设备处理方式

   ① 每类设置一个进程，专门执行该类设备I/O操作，如交互式中断进程。打印进程等，适合大型系统

   ② 系统中只有一个I/O进程，执行所有各类设备I/O操作

   ③ 不设置专门设备处理进程，只为各类设备设置相应设备驱动程序供调用，该方式最为普遍

6.4.2 设备驱动程序处理过程

driver主要任务:启动I/O设备，完成上层I/O软件指定工作

启动前先完成必须要准备的工作，然后向设备管理器发送启动命令

发出I/O操作后驱动程序阻塞，直到中断程序到来唤醒

具体操作由设备控制器完成，实现设备与CPU并行

①将抽象要求转换为具体要求:如逻辑块号转化为磁盘地址

②检查请求服务合法性

③检查设备状态:是否为就绪状态? 状态R

④传送必要参数:命令R，工作模式，如232的波特率，校验方式

⑤启动I/O设备

6.4.3 对I/O设备的控制方式

把CPU从繁杂的I/O事务中解脱，专注于数据处理

1. 轮询(查询)可编程方式

   • 最早出现的IO处理方式
   • 轮询查询I/O控制器中的状态R，busy=0/1?

   特点:

   ①CPU绝大部分时间查询设备状态，CPU忙等

   ②CPU主动,设备被动

2. 中断可编程方式

   • CPU向设备控制器发出I/O命令，然后继续返回执行原理命令
   • 设备控制器按命令要求去控制指定I/O设备。CPU与I/O设备并行操作
   • 完成后设备控制器由CPU发出中断，CPU中断处理读/写数据

   特点:

   ①设备主动

   ②CPU与I/O设备并行工作，CPU只需要极短时间处理中断

   ③提高资源利用率和吞吐量

   ④实时性好

3. 直接存储器访问(DMA)方式

   • 中断驱动I/O仍以字节为单位进行I/O，每传送1字节发送一次中断
   • 中断处理前后开销大，若用于块设备效率低，中断过于频繁
   • 为进一步减少IO对CPU的干预，引入直接存储器访问方式，也称DMA

   特点:

   ①传输单位是数据块，CPU和I/O设备每次至少传输一个数据块

   ②数据从设备直接送入内存，或者相反，不经过CPU

   ③仅在传送开始和结束才需CPU干预，整块数据传送是在DMA控制器的控制下完成的

   ④DMA比中断方式CPU和I/O设备并行度高

   DMA的组成

   • DMA控制器由三部分组成:主机与DMA控制器的接口，DMA控制器与块设备的接口；I/O控制逻辑

     命令/状态寄存器 CR,内存地址寄存器MAR,数据寄存器DR,数据计数器DC

     

     图10. DMA控制器的组成

   DMA的工作过程

   以磁盘为例:

   • CPU向设备控制器发出命令，并设置DR,MAR,DC,CR
   • 启动DMA控制器进行数据传送
   • 在DMA控制器控制下数据传至内存，CPU可做其他工作
   • 完成后DMA控制器发中断请求

   

   图11. DMA方式的工作流程

• 三种I/O方式流程图

  

  图12. 三种IO方式流程图

4. 通道方式

   • I/O通道方式的引入

     • 进一步减少CPU对I/O设备的干预

• 以多个块为单位进行数据传送

  • 一次传送多组数据到多个不同的内存区域

  • 通道程序

    • 通道程序通过执行通道程序并与设备控制器共同实现I/O设备的控制

    • 通道程序是一系列通道指令(通道命令)所构成

    • 通道指令通常与I/O操作有关，指令包含：

      ①操作码 ②内存地址 ③计数 ④通道结束位P:是否是最后一条指令 ⑤记录结束标志R:R=0:与上条记录相同，R=1:新纪录；

6.5 与设备无关的I/O软件

目的:方便用户和提高OS的可扩展性和可适应性

• 设备无关性含义

  应用程序所用设备不局限于某个具体的物理设备

  • 驱动程序与硬件紧密相连，为实现设备独立性，驱动程序上还需设备无关软件

6.5.1 与设备无关软件的基本概念

1. 以物理设备名使用设备

   • 早期OS应用程序使用物理设备名访问设备
   • 应用程序与设备直接相关

   特点：程序不灵活，用户不方便，设备利用率低

2. 引入逻辑设备名

   • 为实现设备无关性引入逻辑设备和物理设备概念
   • 逻辑设备名是抽象的物理，如/dev/printer
   • 应用程序使用逻辑设备名，该类设备只要有空闲就不阻塞
   • 设备无关系软件还可以实现I/O重定向
     • IO重定向:设备交换而不改变程序

3. 逻辑设备名到物理设备名的转换

   • 使用逻辑设备名需要方便用户，但操作设备需要物理设备名
   • I/O系统具有将逻辑设备名转为具体物理设备名的功能
   • 系统需要配置一张逻辑设备表(LUT)

6.5.2 与设备无关软件

设备无关软件是I/O系统最高层，下面是设备驱动程序

图13. 设备无关性的功能层次

• 设备无关软件包括执行所有设备公有设备操作

  1. 使所有设备驱动程序统一的接口

     a. 添加新设备驱动程序变得很容易

     b. 方便开发人员编写设备驱动程序

     c. 要将抽象设备名转为具体物理设备名，再找到驱动程序入口

  2. 缓冲管理

     a. 目的: 缓和CPU和I/O设备之间的矛盾，提高CPU利用率

     b. 缓冲区形式:单缓冲区，双缓冲区，循环缓冲区，公用缓冲池

  3. 差错控制

     a.设备有许多机械和电气部分，比CPU更容易出现故障，两类错误:

     • ①暂时性错误，重试操作纠正
     • ②持久性错误，向系统报错

     b.多数错误由driver处理，设备无关性软件只处理driver无法处理的错误

  4. 独占设备的分配和回收

     a. 两类设备:独占设备和共享设备

     b. 独占设备必须由I/O系统统一分配:空闲则分配；忙则进程阻塞并放于设备后备队列，空闲时唤醒

  5. 独立于设备的逻辑数据块

     a. 不同类型设备数据交换单位不同，如字符设备/块设备/扇区大小

     b. 设备独立性软件应隐藏这些差异被逻辑设备使用

6.5.3 设备分配

1. 设备分配中的数据结构

   为分配独占设备必须具有相应数据结构:

   ①设备控制表DCT

   ②控制器控制表COCT

   ③通道控制表CHCT

   ④系统设备表SDT

   • 设备控制表:为每个设备都配备一张设备控制表，记录设备情况:

     

   • 控制器控制表:每个设备控制器都配备一张设备控制器控制表:

   • 通道控制表:每个通道都有一个通道控制表

   • 系统设备表:

     a. 记录全部设备情况，整个系统一张

     b. 每设备一个表目：设备类型，设备标识符，设备控制表及设备驱动程序入口

     

2. 设备分配时应考虑的因素

   • 设备固有属性

     ①独占设备分配策略:一个设备分配一个进程，独占到释放

     ②共享设备分配策略:可同时分配多个进程，需合理调度

     ③虚拟设备分配策略:属于可共享设备，可同时分配多个进程

   • 设备分配算法

     ①先来先服务算法

     ②优先级高优先算法

   • 设备分配安全性

     ①安全分配方式

     a. 发出I/O请求即阻塞直到I/O完成，阻塞时不能再请求资源

     b. 摒弃死锁"请求和保持"条件，系统不会发生死锁，CPU和I/O顺序发生，效率低

     ②不安全分配方式

     a. 发出I/O请求继续运行，仅当请求的设备被占用才阻塞

     b. 优点: 一个进程可操作多个设备，进程推进迅速

     c. 缺点:分配不安全，具备"具备请求和保持"条件，可能死锁

   • 独占设备分配程序

     ① 分配设备:由物理设备名查SDT，找到对应DCT，根据设备状态处理

     ② 分配控制器:由DCT转到COCT，根据控制器状态处理

     ③ 分配通道:由COCT找到CHCT，根据通道状态处理

     三者都分配成功才能启动程序

   • 设备分配程序的改进

     • 前例以物理设备名提出I/O请求，若指定设备忙则分配失败

     • 前例设备分配程序不具有与设备无关性

     • 为获得设备的独立性，进程应使用逻辑设备名请求I/O：

       ① 由逻辑设备名在SDT中找到一个该类设备DCT

       ② 若忙则找第二个DCT,依次类推，知道找到空闲设备表

       ③ 设备分配后再分配设备控制器和通道

   • 逻辑设备表(LUT)

     • 作用:将逻辑设备名映射为物理设备名

     • 逻辑设备表:

       表项:逻辑设备名，物理设备名，设备驱动程序入口地址

     • 用逻辑名分配物理设备后，字LUT上建立新表目，填写相关信息

     逻辑设备表设计问题

     ①整个系统只能有一张LUT

     不允许有相同逻辑设备名，所有进程不能使用相同逻辑设备名，主要用于单用户系统

     ② 每个用户设置一张LUT

     用户登陆时建立进程及LUT，LUT放于PCB中，LUT表目只有：逻辑设备名和系统设备表(SDT,多用户系统配置)指针

6.6 用户层I/O软件

大部分I/O软件放在OS内部，是I/O子系统的一部分

运行于用户层的I/O软件包括

① 与用户程序链接的库函数

② 假脱机系统

③ 网络通信中的守护进程

6.6.1 系统调用和库函数

1. 系统调用的引入

   ① 不允许用户态应用进程去直接调用核心态(系统态)的OS进程

   ② 应用进程在运行时又必须取得OS所提供的服务

   ③ 应用程序通过系统调用间接调用OS的中I/O进程，对I/O设备进行操作

   • OS向用户提供的功能都必须通过系统调用获取
   • 系统调用是应用程序获取OS服务的唯一途径
   • 汇编语言用系统调用，C语言用库函数调用

2. 系统调用执行过程

   ① 调用时将CPU状态改为核心态

   ② 执行具体I/O操作

   ③ 返回时将CPU状态改回用户态

   

   图14.系统调用执行过程

3. 库函数

   UNIX中C语言的系统调用与库函数一一对应

   微软定义WIN32 API应用程序接口，利用API取得OS服务，API与实际系统调用并不一一对应

   通过系统调用时，库函数与调用程序一一链接，嵌入可执行程序中

   内核与库函数关系:

   ① 内核提供OS基本功能

   ② 库函数提供OS扩展功能，用户通过库函数获取OS服务

6.6.2 假脱机系统

• 多程序技术将一个物理CPU虚拟出多个逻辑CPU
• 假脱机技术将一个物理设备虚拟出多个逻辑设备，供多用户共享
• 1950年代引入，脱机输出技术
  • 多道系统利用一道程序模拟脱机系统外围控制机功能，实现磁盘与低速I/O设备的传输，把这种在联机情况下实现额同时外围操作技术称为SPOOLING技术或假脱机技术

假脱机技术的组成

• SPOPLING技术是对脱机输入/输出的模拟

• 建立在通道技术和多道程序技术基础上，以高速磁盘为后援存储器

  由以下四部分组成：

  ①输入输出井:磁盘上开辟，井文件，连接成队列

  ②输入输出缓冲区:内存中开辟，CPU与磁盘速度矛盾

  ③输入进程和输出进程:预输入，缓输出

  ④井管理:向输入井读信息或向输出井写信息

  

  图15 .假脱机技术示意图

图16. 假脱机技术工作图

SPOOLING技术特点

①提高I/O速度，对低速设备操作转换为对磁盘缓冲区操作

②将独占设备改造为共享设备，没有为进程分配设备，只是在磁盘缓冲区分配空闲盘块和I/O请求表

③实现了虚拟设备功能，例如假脱机打印

假脱机打印系统

• 利用假脱机技术可将打印机改造为共享设备

• 共享打印机技术广泛用于多用户系统和局域网络

• 假脱机打印系统主要分为四部分:

  • 磁盘缓冲区:暂存用户输出数据，按队列来组织
  • 打印缓冲区:内存中，暂存从磁盘缓冲区来的数据
  • 假脱机管理进程:为用户建立假脱机文件，放入队列
  • 假脱机打印进程:读取假脱机文件队列中文件打印

  

  图17. 假脱机打印机系统的组成

守护进程

• 将独占设备改造成共享设备都需要一守护进程及假脱机文件队列
• 守护进程唯一使用设备
• 其他进程把设备使用要求放于假脱机文件队列，由守护进程依次完成进程请求

6.7 缓冲区管理

OS中所有I/O设备与CPU交换数据时都用的是缓冲区

缓冲区实现方式:

① 由硬件寄存器组成，成本高，容量小，速度快。如VM中的联想存储器；设备控制器中的数据缓冲区

② 利用内存做缓冲区

缓冲区管理主要功能:组织缓冲区，提供申请释放缓冲区的手段

6.7.1 缓冲的引入

引入缓冲区的原因：

① 缓解CPU与I/O设备之间速度不匹配

②减少对CPU的中断频率，放宽对CPU中断响应时间的限制

③解决数据粒度不匹配问题

④提高CPU与I/O设备之间的并行性

6.7.2 单缓冲区和双缓冲区

无缓冲，单缓冲，双缓冲
无缓冲:数据直接传给对方，互相限制
单缓冲:只有一个缓冲区
双缓冲:有两个缓冲区供通信无缓冲，单缓冲，双缓冲

无缓冲:数据直接传给对方，互相限制

单缓冲:只有一个缓冲区

双缓冲:有两个缓冲区供通信

图18.生产者消费者单缓冲区示意

图19.生产者消费者双缓冲区示意

图20.双机通信单缓冲和双缓冲区示意图

6.7.3 环形缓冲区

• 双方速度接近双缓冲区效果较好

• 速度相差甚远时双缓冲区效果不好，可增加缓冲区数量解决

• 环形缓冲区由多个缓冲区组成，并且构成环形

• 环形缓冲区的组成:

  多个大小相同缓冲区:输入缓冲区分类:空缓冲区R,满缓冲区G,当前缓冲区C

  多个指针:满指针nextg,空闲指针nexti，当前指针current

环形缓冲区同步问题

• 使用输入循环缓冲区，可使输入进程和计算进程并行执行

• 可能存在下述两种情况:

  Nexti指针追赶上Nextg指针:空缓冲区完，输入进程阻塞

  Nextg指针追赶上Nexti指针:满缓冲区完, 计算进程阻塞

6.7.4 缓冲池

缓冲池的引入

• 单缓冲，双缓冲，环形缓冲属于专用缓冲，为专门进程设置
• 缓冲池可用于输入和输出的公用缓冲池，可悲多进程共享使用

区别:

①普通缓冲区只是内存块链表

②缓冲池是包含数据结构和一组相关操作函数的管理机制

• 缓冲池管理者多个缓冲区，每个缓冲区由缓冲首部和缓冲体组成

• 首部:缓冲区号，设备号，数据块数量，信号量，队列链接指针

• 缓冲池主要过程(缓冲池是互斥资源，内含信号量操作):

  GetBuf过程:从缓冲池获得一个缓冲区

  PutBuf过程:将缓冲区还给缓冲池

6.8 磁盘存储器的性能和调度

6.8.1 磁盘性能简述

磁盘性能改善方法

• 磁盘是复杂机电设备，最重要存储设备，有大量文件

• 磁盘性能及可靠性极大影响系统性能

• 改善磁盘系统性能的途径:

  ① 选择好磁盘调度算法

  ② 提高磁盘I/O速度，提高文件访问速度

  ③ 采取冗余技术，提高磁盘系统可靠性，建立可靠文件系统

磁盘数据组织和格式

• 磁盘结构:盘片，盘面，磁道，扇区，柱面

• 一个扇区称为一个盘块，各扇区间保留一定间隙

• 磁盘信息存储在扇区中，读写以扇区为单位，每个盘面都有磁头

  

  图21. 磁盘结构和布局图

• 每条磁道存储相同容量的信息，内磁道比外磁道存储密度大

• 磁盘数据块数目由盘块数，每面磁道数和每磁道扇区数决定

• 不同盘面上相同编号磁道构成一个柱面

• 现在磁盘每道扇区数可不同，OS提高虚拟逻辑扇区映射关系

磁盘格式化

• 磁盘格式化后才能存储数据
• 格式化分为高级格式化和低级格式化
• 低格式化后要对磁盘分区，每个分区就是一个独立逻辑磁盘
• 磁盘第0面0道0扇区为主引导记录分区表，记录各分区起始扇区及大小，活动分区可引导操作系统
• 高级格式化给分区设置一个引导块，空闲存储管理，根目录和一个空文件系统，并在为主引导记录分区表标记分区文件系统类型

磁盘格式化示意图

• 每道30扇区，没扇区600B(512B数据，其他为控制信息)

• 扇区信息包含:同步字符，地址信息，数据，CRC校验

  

  图22.磁盘格式化示意图

磁盘类型

• 硬盘和软盘，单片盘和多片盘，固定头磁盘和活动头(移动头)磁盘
• 固定头磁盘:每条道有磁头，并行读写，速度快，用于大容量磁盘
• 移动头磁盘:每个磁盘一个磁头，需寻道，串行方式读写，简单，用于中小型计算机如微机

磁盘访问时间

• 磁盘在工作时以恒定速率旋转
• 磁盘访问时间T_a=寻道时间T_S+旋转延迟时间T_d+传输时间T_T
• 传输时间T_t，与磁盘转速和数据量有关
• 读写b字节数据平均访问时间T_a=T_S+1/(2r)+b/(rN)
• 每秒转数r；读写数据字节b；每条磁道字节数N
• 寻道时间与旋转延迟和数据量无关，占大头
• 集中数据利于提高磁盘传输率

6.8.2 早期磁盘调度算法

磁盘调度的目的是使磁盘平均寻道时间最少

• 常见调度算法:

  ①先来先服务算法FCFS

  ②最短寻道时间算法SSTF

  ③扫描算法SCAN

  ④循环扫描算法

  ⑤NStepSCAN和FSCAN算法

先来先服务算法DCFS

• 最简单的调度算法

• 根据进程访问磁盘的先后次序进行调度

优点:公平，简单，不会出现进程长期得不到满足情况

确定:算法未优化，平均寻道时间长

• FCFS适合请求I/O较少的场合

图23. 先来先服务算法示例

最短寻道时间算法 SSTF

• 要求访问磁道与当前磁头所在的磁道距离最近

• 特点

  ① 使每次寻道时间最短，但不能保证总的平均寻道时间短

  ② 平均寻道时间低于FCFS

  ③ 可能有进程长期得不到服务

图24 .最短寻道时间算法示例

6.8.3 基于扫描的磁盘调度算法

扫描算法SCAN

• SSTF算法是基于优先级的调度算法，使低优先级进程“饥饿”
• SCAN算法不仅考虑访问磁道与当前磁道距离，更优先考虑磁头移动方向
• 选择进程标准:当前移动方向上距离当前磁头位置最近的请求
• 也称为“电梯算法”，特点：不会有“饥饿”现象

图25. 扫描算法SCAN

循环扫描算法CSCAN

• SCAN性能好，无饥饿现象，广泛用于大中小型机器和网络中的磁盘调度
• 存在问题:个别进程请求会被大大地推迟
• CSCAN算法规定磁头只能单向移动，最小磁道号与最大磁道号构成循环，进行循环扫描

图26. 循环扫描算法CSCAN

NStepSCAN算法

• SSTF，SCAN及CSCAN可能出现磁头停留不动的情况

• "磁壁黏着"现象，高密度磁盘上易出现

• N步算法SCAN算法NStepSCAN将磁盘请求队列分成若干长度为N的子队列，按照FCFS算法依次调度子队列，每个子队列内部采用SCAN算法。服务时新请求放入新队列

• N很大时接近SCAN算法

  N=1时蜕化为FCFS算法

FSCAN算法

• FSCAN算法实质上是N步SCAN算法的简化

• FSCAN算法只将磁盘请求队列分为两个子队列

  ①由当前所有请求磁盘I/O的进程形成的服务队列，按SCAN算法处理

  ②在扫描期间新出现的磁盘请求队列请求放入等待队列，新请求被推迟到下次扫描时处理

---

• 参考：计算机操作系统（第四版）（汤小丹)