操作系统学习记录5-输入输出管理

I/O管理基础

设备的分类

按使用特性：

存储设备：又称为外存、辅存

I/O设备：输入设备（键盘、鼠标、扫描仪、视频摄像等）、输出设备（打印机、绘图仪）、交互式设备（显示器）

按传输速率：

低速设备：键盘鼠标

中速设备：行式打印机、激光打印机

高速设备：磁带机、磁盘机、光盘机

按信息交换的单位分类：

块设备（传输快，可寻址）

字符设备（传输慢，不可寻址，常采用中断控制方式）

I/O设备的电子部件（控制器）又称设备控制器。

功能有：

接受和识别CPU发来的命令。CPU发来的读写命令，I/O控制器会有相应的控制寄存器存放命令和参数

向CPU报告设备的状态。I/O控制器中会有相应的状态管理器，用于记录I/O设备的当前状况，1表空闲，0表忙碌

数据交换。I/O控制器会设置相应的数据寄存器。输出时，数据寄存器用于暂存CPU发来的数据，之后再由控制器传送设备。输入时，数据寄存器用于暂存设备发来的数据，之后CPU从数据寄存器中取走数据。

地址识别。为了区分设备控制器中的各个寄存器，也需要给每个寄存器设置一个特定的地址。I/O控制器通过CPU提供的地址来判断CPU要读/写的时哪个寄存器。

组成有CPU与控制器的接口，如寄存器。I/O逻辑，负责接受和识别CPU的各种命令，并负责对设备发出命令。控制器与设备的接口。用于实现控制器与设备之间的通信。

Notice：

一个I/O控制器可能会对应多个设备

数据寄存器、控制寄存器、状态寄存器可能有多个，且这些寄存器都要有相应的地址，才能方便CPU操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O。另外有一些计算机采用I/O专用地址，即寄存器独立编址。

内存映像I/O：

控制器中的寄存器与内存地址统一编址。优点时简化了命令，可以采用对内存进行操作的指令来对控制器进行操作。

寄存器独立编址：

控制器中的寄存器使用单独地址。缺点L需要设置专门的指令来实现对控制器的操作，不仅要指明寄存器的地址，还要指明控制器的编号。

I/O系统接口

块设备接口(磁盘）、流设备接口（键盘）、网络通信接口（网络控制器）

阻塞I/O：应用程序发出I/O系统调用，进程需转为阻塞态等待。字符设备接口--从键盘读一个字符get

非阻塞I/O：应用程序发出I/O系统调用，系统调用可迅速返回，进程无需阻塞等待。块设备接口--往磁盘写数据

不同的操作系统，对设备驱动程序接口的标准不相同。设备厂商必须根据操作系统的要求，开发出相应的设备驱动程序，设备才能被使用。

 

I/O控制方式

轮询方式：过程简单，CPU利用率低

CPU发出命令后需要不断轮询，每次传输字。数据流向是从设备->CPU->内存、内存->CPU->设备。

中断驱动I/O方式：以字（节）为单位进行I/O，提高CPU利用率。

CPU发出I/O命令后可以做其他事，本次I/O完成后设备控制器发出中断信号。数据流向是从设备->CPU->内存、内存->CPU->设备。

 

DMA方式：在I/O设备和内存之间开辟直接数据通路，数据传输的基本单位是数据块，提高CPU和I/O设备的并行操作程序。

CPU发出I/O命令后可以做其他事，本次I/O完成后，DMA控制器发出中断信号。数据传输方向是设备->内存，内存->设备。

I/O通道方式：引入通道控制I/O设备，减少CPU的干扰

CPU发出I/O命令后可以做其他事。通道会执行通道程序完成I/O，完成后通道向CPU发出中断信号，数据传输单位是一组块。数据传输方向是设备->内存，内存->设备。

I/O软件层次结构

用户层I/O软件

用户层软件实现了与用户交互的接口，用户可以直接使用该层提供的、与I/O操作相关的库函数对设备进行操作。用户层软件将用户请求翻译成格式化的I/O请求，并通过“系统调用”请求操作系统内核的服务

设备独立软件

又称设备无关系软件。主要功能是向上层提供同一个调用接口（有点像是虚拟设备），实现设备的保护，差错处理，设备的分配与回收，数据缓冲区管理（可以通过缓冲技术屏蔽设备之间数据交换单位大小和传输速度的差异），建立逻辑设备名到物理设备名的映射关系。根据设备类型选择调用相应的驱动程序。逻辑设备名比如打印机1，打印机2等。设备独立性软件通过逻辑设备表（LUT），来确定逻辑设备对应的物理设备，并找到该设备对应的设备驱动程序。

操作系统可以采用2种方式管理逻辑设备表。

1.整个系统只设置一张LUT，意味着所有用户不能使用相同的逻辑设备名，因此只适应与单用户操作系统。

2.每个用户设置一张LUT，各个用户使用的逻辑设备名可以重复，适用于多用户操作系统。系统会在用户登录时建立一个用户管理进程，LUT就存放在用户管理进程的PCB中。

不同设备的内部硬件特性也不同，这些特性只有厂商才知道，因此厂家需提供与设备相对应的驱动程序，CPU执行驱动程序的指令序列，来完成设置设备寄存器，检查设备状态等工作。

设备驱动程序

主要负责对硬件设备的具体控制，将上层发出的一系列命令转化成特定设备能听得懂的一系列操作。包括设置设备寄存器，检查设备状态。

中断处理程序

I/O完成时，I/O控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。

 

硬件

越上面越接近用户，每一层会利用下层提供的服务，实现某些功能，并屏蔽实现的具体细节，向高层提供服务（“封装思想”）。

设备独立软件、设备驱动程序、中断处理程序属于操作系统的内核部分，也就是I/O系统。

需要重点理解和掌握的是：I/O调度、设备保护、假脱机技术（SPOOLing技术），设备分配与回收、缓冲区管理。

理解并记住I/O软件各个层次之间的顺序，要能够推理判断某个处理应该时在哪个层次完成的，最常考的时设备独立性软件、设备驱动程序。直接涉及到硬件具体细节，且与中断无关的操作肯定是在设备驱动程序层完成的。没有涉及到硬件的，对各种设备都需要进行管理的都是设备独立性软件层完成的。

 

 

设备独立软件

缓冲区分类

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，可以用内存。使用硬件的话成本高，容量也小。只用在对速度要求高的场合。一般情况下是利用内存作为缓冲区。

缓冲区的作用：缓和CPU和I/O设备之间速度不匹配的矛盾，减少对CPU的中断频率，放宽对CPU中断相应时间的限制，解决数据粒度不匹配的问题（输出进程每次可以生成一块数据，但I/O设备每次只能输出一个字符）。提高CPU与I/O设备之间的并行性。

设备输入时间T、缓冲区传输时间M、工作区处理时间C

缓冲区的大小一般为一个块

当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。

用户进程的内存空间中，会分出一片工作区来接受输入输出数据（一般也默认工作区大小与缓冲区相同）

计算没处理一块数据的平均需要多久，可以假定一个初始状态，分析下次到达相同状态需要多少时间，这就是处理一块数据平均所需时间。可以假设初始状态为工作区满，缓冲区空。

单缓冲区：处理一块数据的时间为max（C，T）+M

双缓冲区：处理一块数据的时间为max（C+M，T）

环形缓冲区：引入多缓冲机制

缓冲池：三个队列，四种工作缓冲区

缓冲池由系统中共用的缓冲区组成，按使用情况可以分为：空缓冲队列、装满输入数据的缓冲队列（输入队列），装满输出数据的缓冲队列（输出队列）

根据一个缓冲区再实际运算中扮演的功能不同，又设置了四种工作缓冲区，用于收容输入数据的工作缓冲区（hin）、用于提取输入数据的工作缓冲区（sin）、用于收容输出数据的工作缓冲区（hout）、用于提取输出数据的工作缓冲区（sout）

输入进程请求输入数据时，会从空缓冲队列取下一块缓冲区，放到hin中。装满后放回输入队列。

计算进程要取得一块数据时，从输入队列取下一块放入sin中，提取完后放回空缓冲队列中

计算进程想要将准备好的数据冲入缓冲区，从空缓冲队列中取下一块缓冲区，放入hout中，装满后放入输出队列中

输出进程请求输出数据时，从输出队列取下一块放入sout中，等输出完后放回空缓冲队列中。

 

两台机器之间通信时，可以配置缓冲区用于数据的发送和接受。a机缓冲区慢时就发出，b机缓冲区满时全部取走。

 

设备分配与回收

设备分配的时候应该考虑的因素：

设备的固有属性、设备分配算法、设备分配中的安全性

固有属性：独占设备、共享设备、虚拟设备

设备分配算法：先来先服务、优先级高者优先

设备分配的安全性：

安全性分配：为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒。（考虑进程请求打印机打印输出的例子）

优点：破坏了请求和保持条件，不会死锁。

缺点：对于一个进程来说，CPU和I/O设备只能串行工作

不安全分配方式：进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求，只有某个I/O请求得不到满足时才将进程阻塞。

优点：进程的计算任务和I/O任务可以并行处理，使进程迅速推进。缺点：有可能发生死锁。

静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源。破坏了请求和保持条件，不会发生死锁。

动态分配：进程运行过程中动态申请设备资源

设备分配数据结构：设备控制表、控制器控制表、通道控制表、系统设备表

一个通道可以控制多个设备控制器，每个设备控制器可控制多个设备。

设备控制表（DCT）系统为每个设备配置一张DCT，用于记录设备情况。

属性有设备类型（打印机）、设备标识符（物理设备名）、设备状态（忙碌）、指向控制器表的指针（每个设备由一个控制器控制，该指针可找到相应控制器的信息）、重复执行次数或时间（当重复执行多次I/O操作后仍不成功，才认为此次I/O失败）设备队列的队首指针（指向正在等待该设备的进程队列）

控制器控制表（COCT）每个设备控制器都会对应一张COCT，操作系统根据上面的信息对控制器进行操作和管理。

属性有控制器标识符（控制器唯一ID）、控制器状态（忙碌）、指向通道表的指针（每个控制器由一个通道控制，该指针可找到相应通道的信息）、控制器队列的队首指针和队尾指针（指向正在等待该控制器的进程队列）

通道控制表（CHCT）每个通道都会对应一张CHCT，操作系统根据CHCT的信息对通道进行操作和管理。

属性有通道标识符（各个通道唯一ID）、通道状态（忙碌）、与通道连接的控制器表首址（可通过该指针找到该通道管理的所有控制器相关信息）、通道队列的队首指针和队尾指针（指向等待该通道的进程队列）

系统设备表（SDT），记录了系统中全部设备的情况，每个设备对应一个表目。

表目属性有设备类型（打印机），设备标识符（物理名），DCT（设备控制表）、驱动程序入口

设备分配步骤：

1.根据进程请求的物理设备名查找SDT（系统设备表）

2.根据SDT找到DCT（设备控制表），若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌再将设备分配给进程。

3.根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列，不忙碌则将控制器分配给进程。

4.根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列，不忙碌则将通道分配给进程。

只有设备、控制器、通道三者都分配成功时，这次设备才算分配成功，之后便可启动I/O进行数据传输。

先系统设备表-》设备控制表-》控制器控制表-》通道控制表

缺点：

用户编程时必须使用物理设备名，底层细节对用户不透明，不方便编程。若更换看一个物理设备，程序无法运行，若进程请求的物理设备正在忙碌，即使系统中还有同类型的设备，进程也必须阻塞等待。

改进方法：建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名。

逻辑设备表建立了逻辑设备名与物理设备名之间的映射关系。如果之后用户进程再次通过相同的逻辑设备名请求使用设备，则操作系统通过LUT表即可知道用户进程实际要使用的是哪个物理设备了，并且也能知道该设备的驱动程序入口地址。

整个系统只有一张LUT，逻辑设备名不允许重复

每个用户一张LUT，不同用户的逻辑设备名可重复

 

设备的回收：回收占有设备、设备控制器、通道

假脱机技术（SPOOLing）

脱机技术：脱离主机的控制，缓解了CPU与慢速I/O设备的矛盾

假脱机技术（spooling）用软件的方式模拟脱机技术。

组成：输入/输出井（在磁盘内开辟两个存储区域）、输入/输出缓冲区（都在内存中）、输入/输出进程、井管理程序

输入井模拟脱机输入时的磁带，用于收容I/O设备输入的数据

输出井模拟推挤输出时的磁带，用于收容用户进程输出的数据

输入进程模拟脱机输入时的外围控制机，用于暂存从输入设备输入的数据，之后再转存到输入井中

输出进程模拟脱机输出时的外围控制机，用于暂存从输出井中送来的数据，之后再传送到输出设备上。

要实现spooling技术，必须要有多道程序技术的支持，系统会建立输入进程和输出进程。

特点：提高I/O速度，将独占设备改造成共享设备，实现虚拟设备功能。

独占式设备：只允许各个进程串行使用的设备。一段时间内只能满足一个进程的请求。

共享设备：允许多个进程同时使用的设备（宏观上同时使用，微观上可能时交替使用）

打印机可以利用spooling技术改造成共享设备。

多个用户进程提出输出打印的请求时，系统会做2件事

在磁盘输出井中为进程申请一个空闲缓冲区（在磁盘上），并将要打印的数据送入其中。

为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中，再将该表挂载假脱机文件队列上。当打印机空闲时，输出进程会取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。

Spooling技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享式设备

设备驱动程序接口

 

外存管理

磁盘

磁盘结构：磁盘设备可以包括一个或多个物理盘片（磁盘片），每个磁盘片分为一个或2个存储面（盘面），每个盘面上有若干个磁道，每个磁道又从逻辑上被划分成若干个扇区（盘块），各个扇区之间留有必要的间隙

可用柱面号，盘面号，扇区号来定位任意一个磁盘块。

可用根据该地址读取一个块

根据“柱面号”移动磁臂，让磁头指向指定柱面。

激活指定盘面对应的磁头

磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读写。

磁头可以移动的称为活动头磁盘，可以伸缩。磁头不可移动的称为固定磁头磁盘。这种磁盘中每个磁道有一个磁头。

盘片可以更换的称为可换盘磁盘，不可更换的称为固定盘磁盘。

 

低级格式化->分区->高级格式化

低级格式化（物理格式化），将磁盘的各个磁道划分为扇区。一个扇区可分为头、数据区域、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分。包括扇区校验码（奇偶校验、CRC冗余码）校验码校验扇区中的数据是否错误。

将磁盘分区，每个分区由若干个柱面组成（也就是C盘、D盘等）

进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（位视图、空闲分区表）

 

引导块

计算机开机时需要进行一系列初始化的工作，这些初始化工作是通过执行初始化程序（自举程序）完成的。初始化程序可以放在ROM中。ROM中的数据出厂时就写入，且不能再修改，一般是集成在主板上。不过ROM中只存放很小的自举装入程序。开机时先运行自举装入程序，通过执行该程序就可以找到引导块，并将完整的自举程序读入内存。完整的自举程序存放在磁盘的启动块（引导块/启动分区）上，启动块位于磁盘的固定位置。

 

对于坏块，也就是无法使用的扇区。应该将其标记出来。

在简单的磁盘中，使用FAT表表明，坏块对操作系统不透明。

在复杂的磁盘中。在出厂前进行低级格式化时就将坏块链进行初始化。会保留一些备用扇区，用于替换坏块，这种方案称为扇区备用，这种处理方式中，坏块对操作系统透明。

 

一次磁盘读写操作需要的时间

寻找时间、延迟时间、传输时间

寻找时间（寻道时间）：在读写之前，将磁头移动到指定磁道所花费的时间。包括启动磁头臂时间s+移动磁头时间=跨一个磁道时间m*跨过的磁道数n

延迟时间，通过旋转磁盘，使得磁头定位到目标扇区所需要的时间。设转速为r，1/r为转一圈的时间。平均所需时间为1/2r

传送时间，从磁盘读出或向磁盘写入数据所经历的时间，假设转速为r，此次读写的字节数为b，每个磁道上的字节数为n。传输时间=（1/r）*（b/n）

总的平均存取时间为寻道时间+1/2r+（1/r）*（b/n）

 

减少延迟时间的方法：

交替编号

让编号相邻的扇区在物理上不相邻。因为读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区

错位命名

让相邻盘面的扇区编号错位。与交替编号的原理相同。错位命名法可降低延迟时间。

磁盘地质结构设计

采用（柱面号、盘面号、扇区号）的结构的原因是在读取地址连续的磁盘块时，前者更不需要移动磁头。

 

磁盘调度算法：

先来先（FCFS）：按进程请求访问磁盘的先后次序调度

好处是公平，缺点是性能差

最短寻道时间优先（SSTF）：选择与当前磁头所在的磁道距离最近的磁道。贪心算法的思想，能保证眼前最优，但无法保证总的寻道时间最短，可能导致饥饿

扫描算法SCAN（电梯调度）：在磁头当前移动方向上选择与当前磁头所在的磁道距离最近的磁道。只有磁头移动到最边缘的磁道时才可以改变磁头的移动方向。缺点是对各个位置磁道的相应频率不均

LOOK算法（默认）：SCAN算法的改进，只要在磁头方向上不再有请求，就立即改变磁头方向，不用去最边边的磁道。

循环扫描算法（C-SCAN）：在扫描算法的基础上规定磁头单向移动，移动到边缘后立即让磁头返回起点（最边边的起点），返回途中不响应任何请求

C-LOOK调度算法（默认）：C-SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即让磁头返回，不用移到最边。

 

 

固态硬盘

优点：快速读写、质量小、体积小、能耗低

缺点：价格比较昂贵，容量较低，数据损坏时难恢复，耐用性差，寿命短。

磨损均衡：一种基于固态硬盘主控芯片的内置机制，分为静态磨损和动态磨损。

动态磨损：写入数据时，选择累计擦除次数少的新闪存块。

静态磨损：SSD监测并自动进行数据分配、迁移，让老旧的闪存块承担以读为主的存储任务，让新的闪存块承担更多的写任务。

操作系统笔记至此结束。