操作系统原理笔记（3）

操作系统第五第六章知识点总结

第五章：虚拟存储器

虚拟储存器概述

特征

• 一次性：指必须一次性全部装入内存，
• 驻留性：指作业被装入内存后，整个作业都会一直驻留在内存中，不会换出任何部分

局部性原理

程序在执行时将呈现出局部性特征，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。表现为：

• 时间局限性
  • 如果程序中的某条指令一旦执行， 则不久以后该指令可能再次执行；如果某数据被访问过， 则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作
• 空间局限性
  • 一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

定义

指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统

特征

• 多次性
  • 指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征
• 对换性
  • 指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。
• 虚拟性
  • 指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

虚拟存储器的实现方式

请求分页存储管理方式

• 硬件
  • 请求页表机制
    • 格式：页号+物理块号+状态位P+访问字段A+修改位M+外存地址
  • 缺页中断机构
  • 地址变换机构（过程图很关键）

请求分页中的内存分配

• 最小物理块数
  • 即能保证进程正常运行所需的最小物理块数
• 内存分配策略
  • 固定分配局部置换：
  • 可变分配全局置换：
  • 可变分配局部置换：
• 物理块分配算法
  • 平均分配算法
  • 按比例分配算法
  • 考虑优先权的分配算法

页面调入策略

• 系统应在何时调入所需页面
  • 预调页策略（不能实现）
  • 请求调页策略（需要才给）
• 系统应该从何处调入这些页面
  • 对换区
  • 文件区
  • UNIX方式
• 页面调入过程（重点）
• 缺页率（出计算题）：f = F / A

  访问页面成功次数为S，访问失败为F，总页面访问次数为A = S + F

页面置换算法

最佳置换算法

需要预知后面进程需要用到的页面，所以不能实现

先进先出页面置换算法（FIFO）

选择在内存中驻留时间最久的页面予以淘汰

最近最久未使用置换算法（LRU）Recently

• 寄存器支持
• 特殊的栈结构

最少使用置换算法（LFU）Frequently

clock置换算法（对访问位A的判断）

• 改进型——增加对修改位M思维判断

页面缓冲算法（PBA,page buffering algorithm）

• 空闲页面链表
• 修改页面链表

抖动与工作集

抖动的概念

即刚被换出的页很快又要被访问，需要将它重新调入，此时又需要再选一页调出

请求分段系统

• 硬件支持
  • 请求分段的段表机构
  • 缺段中断机构
  • 地址变换机构

课后题

实现虚拟存储器需要哪几个关键技术？

（1）在分页请求系统中是在分页的基础上，增加了请求调页功能和页面置换功能所形成的
页式虚拟存储系统。允许只装入少数页面的程序（及数据），便启动运行。
（2）在请求分段系统中是在分段系统的基础上，增加了请求调段及分段置换功能后形成的
段式虚拟存储系统。允许只装入少数段（而非所有段）的用户程序和数据，即可启动运行。

在一个请求分页系统中，采用LRU 页面置换算法时，假如一个作业的页面走向为4 , 3 , 2 ,1 , 4 , 3 , 5 , 4 ,3 , 2 , 1 ,5，当分配给该作业的物理块数M分别为3和4时，试计算访问过程中所发生的缺页次数和缺页率 ? 比较所得结果?

答：当分配给该作业的物理块数M为3时，缺页9次，缺页率: 9/12=3/4；
当分配给该作业的物理块数M为4时，缺页10次，缺页率: 10/12=5/6.

页面缓冲算法的主要特点是什么？如何降低页面换进、换出频率的

主要特点：1显著地降低了页面换进、换出的频率,使磁盘I/O的操作次数大为减少,因而减少了页面换进、换出的开销;2正是由于换入换出的开销大幅度减小,才能使其采用一种较简单的置换策略。
需要内存中设置了如下两个链表: 一个是空闲页面链表，实际上该链表是一个空闲物理块链表,是系统掌握的空闲物理块,用于分配给频繁发生缺页的进程,以降低该进程的缺页率。当这样的进程需要读入一个页面时,便可利用空闲物理块链表中的第一个物理块来装入该页。当有一个未被修改的页要换出时,实际上并不将它换出到外存,而是把它们所在的物理块挂在空闲链表的末尾。 另一个是修改页面链表，它是由已修改的页面所形成的链表。设置该链表的目的是为了减少已修改页面换出的次数。当进程需要将一个已修改的页面换出时,系统并不立即把它换出到外存上,而是将它所在的物理块挂在修改页面链表的末尾。这样做的目的是:降低将已修该页面写回磁盘的频率,降低将磁盘内容读入内存的频率。

简答题、阐述题

1、虚拟存储器概述
（1）常规存储管理方式的特征和局部性原理
①常规存储管理方式的特征
传统：一次性、驻留性
②局部性原理
绝大部分顺序执行、调用进度不超过5、循环结构由少数指令构成.但多次执行、多对数据结构的处理.这些处理局限于很小的部分
时间、空间局限性
③虚拟存储器的基本工作情况
将少数页面或段先装入内存即可运行
（2）虚拟存储器的定义和特征
①虚拟存储器的定义
有请求调入功能和置换功能.能逻辑上对内存内容加以扩充的一种存储器系统
②虚拟存储器的特征
多次性、对换性、虚拟性
（3）虚拟存储器的实现方式
①分页请求系统
硬件支持：请求分页的页表机制、缺页中断机制、地址变换机制
实现请求分页的软件
②请求分段系统
硬件支持：请求分段的段表机制、缺段中断机构、地址变换机构
软件支持

2、请求分页存储管理方式
（1）请求分页中的硬件支持
①请求页表机制
②缺页中断机构
③地址变换机构
（2）请求分页中的内存分配
①最小物理块数的确定
②内存分配策略
策略：固定分配局部置换、可变分配全局置换、可变分配局部置换
③物理块分配算法
算法：平均分配算法、按比例分配算法、考虑优先权的分配算法
（3）页面调入策略
①何时调入页面
预调页策略：手动指出哪些页要调入内存、成功率偏低
请求调页策略：一次调入一页.须较大系统开销
②从何处调入页面
系统拥有足够的对换区空间：进程进行前就把进程相关的文件拷贝到对换区
系统缺少足够的对换区空间：未修改过的不到对换区.以后要用再从文件区调入
UNIX方式：从文件区入.出到对换区、允许页面共享
③页面调入过程
？？？
④缺页率
？？？

3、页面置换算法
抖动：一个进程在运行中把大部分时间都花费在页面置换工作上
（1）最佳置换算法和先进先出置换算法
①最佳置换算法
要知道未来需要哪页.实际上不可能
②先进先出页面置换算法
剔走最老的页
（2）最近最久未使用和最少使用置换算法
①最近最久未使用
看最近的n个，最老的踢走
②LRU置换算法的硬件支持
寄存器： 8位寄存器.R7~R0.R值最小的页被踢出
栈：最新访问的是栈顶
③最少使用置换算法
现实使用这个多.一旦访问就在最高位置一
（3）Clock置换算法
①简单的CLOCK置换算法
也叫最近未使用算法.就是有个访问位，1→0→换出
②改进型CLOCK置换算法
四类：A M = 0 0 ~ 1 1
第一步：先找 0 0
第二步：再找 0 1，并置所有页0 X
第三步：再找0 0，最后找0 1，一定找到
优点：减少I/O
缺点：增加系统开销
（4）页面缓冲算法
①影响页面换进换出效率的若干因素
页面置换算法、写回磁盘的频率、读入内存的频率
②页面缓冲算法PBA
显著降低页面换进、换出频率，减少页面换进换出的开销
换入换出的开销大幅减少，才能使用简单的置换策略，如FIFO
要在内存中设置：空闲页面链表、修改页面链表
（5）访问内存的有效时间
如果考虑快表的命中率和缺页率：EAT = …….
如果仅考虑缺页率：EAT =

4、“抖动”与工作集
（1）多道程序度与“抖动”
①现象
先增后减
②原因
进程太多，物理块不够分
（2）工作集
①工作集的基本概念
如果可以预知，就可以先调入内存，大大降低缺页率，从而显著提高处理机利用率
②工作集的定义
引用的集合，类似FIFO
（3）“抖动”的预防方法
①采取局部置换策略
“抖动”影响较小
②把工作集算法融入到处理机调度中
每个进程在内存的驻留页面是否足够多，如果是就调入新作业、否则增加新物理块
③利用L=S准则调节缺页率
缺页之间的平均时间= 平均缺页服务时间
④选择暂停的进程
先暂停优先级最低的进程、在选择并不重要，但较大的进程

5、请求分段存储管理方式
其实也类似于分页，要硬件和软件支持
（1）请求分段中的硬件支持
①请求段表机制
段表项：段名、段长、段基址、存取方式、访问字段A、修改位M、存在位P、增补位、外存始址
A、M：改进型CLOCK置换算法
P：本段是否调入内存
增补位：看是否做过动态增长
②缺段中断机制 （图5-12）
万一虚段S不在内存中，就阻塞请求进程。如果没有空闲区，就要拼接空闲区或者淘汰实段以形成空闲区
之后读入段S，修改段表及内存空区链
③地址变换机构
就是一个地址变换机构
（2）分段的共享和保护
①共享段表
共享进程计数count、存取控制字段、段号
②共享段的分配与回收
共享段的分配、共享段的回收
③分段保护
越界检查、存取控制检查、环保护机构

第六章：输入输出系统

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

I/O系统管理的对象是I/O设备和相应的设备控制器。

I/O系统的基本功能

• 隐藏物理设备的细节
• 与设备的无关性
• 提高处理机和I/O设备的利用率
• 对I/O设备进行控制
• 确保对设备的正确共享
• 错误处理

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

1. I/O软件的层次结构
   • 用户层I/O软件
   • 设备独立性软件
   • 设备驱动程序（厂家开发）
   • 中断处理程序
   • 硬件
2. I/O系统的分层
   • 中断处理程序
   • 设备驱动程序
   • 设备独立性软件

I/O系统接口

1. 块设备接口
   • 指以数据块为单位来组织和传送数据信息的设备
   • 典型的块设备是磁盘、光盘
   • 块设备的基本特征
     • ①传输速率较高，通常每秒钟为几兆位；
     • ②它是可寻址的，即可随机地读/写任意一块；
     • ③磁盘设备的I/O采用DMA方式。
2. 流设备接口
   • 又称字符设备指以单个字符为单位来传送数据信息的设备
   • 这类设备一般用于数据的输入和输出，有交互式终端、打印机
   • 字符设备的基本特征
     • ①传输速率较低；
     • ②不可寻址，即不能指定输入时的源地址或输出时的目标地址；
     • ③字符设备的I/O常采用中断驱动方式。
3. 网络通信接口
   • 提供网络接入功能，使计算机能通过网络与其他计算机进行通信或上网浏览。

I/O设备和设备控制器

I/O设备

• 使用特性分
  • 存储设备
  • I/O设备
• 传输速率分
  • 低速设备（几字节——几百字节）
    • 典型的设备有键盘、鼠标、语音的输入
  • 中速设备（数千——数万字节）
    • 典型的设备有行式打印机、激光打印机
  • 高速设备（数十万——千兆字节）
    • 典型的设备有磁带机、磁盘机、光盘机
• 设备与控制器之间的接口
  • 设备并不是直接与CPU进行通信，而是与设备控制器通信。在设备与设备控制器之间应该有一个接口。
  • 数据信号：控制器 ← 设备 ← 控制器
    • 传送数据信号，输入、输出bit
  • 控制信号: 控制器 → 设备
    • 执行读、写操作的信号
  • 状态信号：设备当前使用状态

设备控制器

• 主要功能：控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换
• 基本功能
  • 接收和识别命令
    • 控制寄存器、命令译码器
  • 数据交换
    • 实现CPU与控制器，控制器与设备间的数据交换
  • 标识和报告设备的状态
  • 地址识别
    • 配置地址译码器，识别不同的设备
  • 数据缓冲区
  • 差错控制
• 设备控制器的组成
  • 设备控制器与处理机（CPU）的接口
    • 实现CPU与设备控制器之间的通信
  • 设备控制器与设备的接口
    • 控制器可连接多个设备
  • I/O逻辑
    • 实现对设备的控制
    • CPU利用该逻辑向控制器发送I/O命令
    • 命令、地址译码

内存映像I/O

驱动程序将抽象I/O命令转换出的一系列具体的命令，参数等数据装入设备控制器的相应寄存器，由控制器来执行这些命令，具体实施对I/O设备的操作

I/O通道

• 目的：建立独立的I/O操作(组织, 管理和结束)，使由CPU处理的I/O工作转由通道完成（解放CPU，实现并行）
• 什么是I/O通道？
  • 是一种特殊的处理机，具有通过执行通道程序完成I/O操作的指令
  • 特点：指令单一(局限于与I/O操作相关的指令)，与CPU共享内存
• 基本过程：
  • CPU向通道发出I/O指令->通道接收指令->从内存取出通道程序处理I/O->向CPU发出中断
• 通道类型
  • 字节多路通道
    • 低中速连接子通道时间片轮转方式共享主通道
    • 字节多路通道不适于连接高速设备，这推动了按数组方式进行数据传送的数组选择通道的形成。
  • 数组选择通道
    • 这种通道可以连接多台高速设备，但只含有一个分配型子通道，在一段时间内只能执行一道通道程序， 控制一台设备进行数据传送， 直至该设备传送完毕释放该通道。这种通道的利用率很低。
  • 数组多路通道
    • 含有多个非分配型子通道，前两种通道的组合，通道利用率较好
• 瓶颈问题
  • 原因;通道不足
  • 解决办法：增加设备到主机间的通路，而不增加通道（结果类似RS触发器）

中断机构和中断处理程序

中断

• 分类
  • 中断（外部触发）
    • 对外部I/O设备发出的中断信号的响应
  • 陷入（内部原因：除0）
    • 由CPU内部事件引起的中断
• 中断向量表（类比51单片机）
  • 中断程序的入口地址表
• 中断优先级
  • 对紧急程度不同的中断处理方式
• 对多中断源的处理方式
  • 屏蔽中断
  • 嵌套中断

中断处理程序

1. 测定是否有未响应的中断信号
2. 保护被中断进程的CPU环境
3. 转入相应的设备处理程序
4. 中断处理
5. 恢复CPU 的现场并退出中断

设备驱动程序

• 是I/O进程与设备控制器之间的通信程序，又由于它常以进程的形式存在，故以后就简称为设备驱动进程
• 主要任务是接受来自它上一层的与设备无关软件的抽象请求，并执行这个请求。

功能

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

设备驱动程序的处理过程

• 将用户和上层软件对设备控制的抽象要求转换成对设备的具体要求，如对抽象要求的盘块号转换为磁盘的盘面、磁道及扇区。
• 检查I/O请求的合理性，比如拒绝从打印机读入数据的操作。
• 读出和检查设备的状态，确保设备处于就绪态。
• 传送必要的参数，如传送的字节数，数据在主存的首址等。
• 工作方式的设置。
• 启动I/O设备，并检查启动是否成功，如成功则将控制返回给I/O控制系统，在I/O设备忙于传送数据时，该用户进程把自己阻塞，直至中断到来才将它唤醒，而CPU可干别的事。

对I/O设备的控制方式

• I/O控制的宗旨
  • 减少CPU对I/O控制的干预
  • 充分利用CPU完成数据处理工作
• I/O 控制方式
  • 轮询的可编程I/O方式
  • 中断的可编程I/O方式
  • 直接储存器访问（DMA）控制方式
  • I/O通道控制方式

DMA控制器组成

• 主机与DMA控制器的接口
• DMA控制器与块设备的接口
• I/O控制逻辑

与设备无关的I/O软件

含义： 应用程序所使用的设备，不局限于使用某个具体的物理设备。

基本概念

• 以物理设备名使用设备
• 引入了逻辑设备名
• 逻辑设备名称到物理设备名称的转换（易于实现I/O重定向）

与设备无关的软件

• 设备驱动程序的统一接口
• 缓存管理
• 差错控制
• 对独立设备的分配与回收
• 独立于设备的逻辑数据块

设备分配中的数据结构

• 设备控制表DCT
• 控制器控制表COCT
• 通道控制表CHCT
• 显然，在有通道的系统中，一个进程只有获得了通道，控制器和所需设备三者之后，才具备了进行I/O操作的物理条件
• 系统设备表SDT
• 逻辑设备表LUT
• 分配的流程，从资源多的到资源紧张的:LUT->SDT->DCT->COCT->CHCT
• 在申请设备的过程中，根据用户请求的I/O设备的逻辑名，查找逻辑设备和物理设备的映射表；以物理设备为索引，查找SDT，找到该设备所连接的DCT；继续查找与该设备连接的COCT和CHCT，就找到了一条通路。

用户层的I/O软件

系统调用与库函数

• OS向用户提供的所有功能，用户进程都必须通过系统调用来获取
• 在C语言以及UNIX系统中，系统调用（如read）与各系统调用所使用的库函数（如read）之间几乎是一一对应的。而微软的叫Win32API

假脱机系统（spooling）

• spooling技术是对脱机输入/输出系统的模拟
• 主要组成
  • 输入/输出井
  • 输入/输出缓冲区
  • 输入/输出进程
  • 井管理程序
• 特点（体现操作系统的虚拟性）
  • 提高了I/O的速度
    • 对数据所进行的I/O操作，已从对低速设备演变为对输入井或输出井中的数据存取。
  • 将独占设备改造为共享设备
    • 实际分给用户进程的不是打印设备，而是共享输出井中的存储区域
  • 实现了虚拟设备功能
    • 将独占设备变成多台独占的虚拟设备。

缓冲区管理

缓冲的引入（原因）

• 缓和CPU与I/O设备间速度不匹配的矛盾
• 减少对CPU的中断频率，放宽对CPU中断响应时间的限制
• 提高CPU和I/O设备之间的并行性
• 解决数据粒度不匹配的问题

单缓冲区

即在CPU计算的时候，将数据数据输入到缓冲区(大小取决与T和C的大小)

双缓冲区

即允许CPU连续工作（T不断）

环形缓冲区（专为生产者和消费者打造）

• 组成
  • 多个缓冲区
  • 多个指针
• 使用
  • Getbuf过程
  • Releasebuf过程
• 同步问题

缓冲池(理解为更大的缓冲区)

• 组成
  • 空白缓冲队列（emq）
    • 由空缓冲区链接而成F(emq)，L(emq)分别指向该队列首尾缓冲区
  • 输入队列（inq）
    • 由装满输入数据的缓冲区链接而成F(inq)，L(inq)分别指向该队列首尾缓冲区
  • 输出队列（outq）
    • 由装满输出数据的缓冲区链接而成F(outq)， L(outq)分别指向该队列首尾缓冲
• Getbuf和Putbuf过程
  • 收容：缓冲池接收外界数据
  • 提取：外界从缓冲池获得数据
• 缓冲区工作方式（从缓冲区的角度来看）
  • 收容输入
  • 提取输入
  • 收容输出
  • 提取输出

磁盘存储器的性能和调度

数据的组织和格式

磁盘的类型

• 固定头磁盘（贵）
• 移动头磁盘

磁盘访问的时间（关键）

• 寻道时间Ts=m*n+s
  • s：启动时间，m：移动一条磁道的时间，n：n条磁道
• 旋转延迟时间Tr
• 传输时间Tt=b/rN
  • b：每次读写字节数，r：转速，N：一条磁道上的字节数
• 总时间Ta=Ts+1/2r+b/rN

磁盘的调度算法（掌握图表）

• 先来先服务（FCFS）
  • 优点：公平，简单
  • 缺点：可能导致某些进程的请求长期得不到满足
• 最短寻道时间优先（SSTF）
  • 说明：要求访问的磁道和当前磁头所在的磁道距离最近，以使每次的寻道时间最短
• 扫描算法（SCAN）
  • 扫描算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁道当前的移动方向
  • 联想电梯的运行
  • 可防止低优先级进程出现“饥饿”的现象
• 循环扫描算法（CSCAN）
  • 算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描
• NStepScan算法
  • N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次这些子队列。
• FSCAN算法
  • 是Nstepscan算法的简化，将磁盘请求队列分成两个子队列

课后题

为了实现CPU与设备控制器间的通信，设备控制器应具备哪些功能？

答：应该具备以下功能：接收和识别命令、数据交换、标识和报告设备状态、地址识别、数据缓冲、差错控制。

有哪几种I/O控制方式？各适用于何种场合？

答：一共有四种I/O 控制方式。

• 程序I/O方式：早期计算机无中断机构，处理机对I/O设备的控制采用程序I/O方式或称忙等的方式。
• 中断驱动I/O 控制方式：适用于有中断机构的计算机系统中。
• 直接存储器访问（DMA）I/O 控制方式：适用于具有DMA控制器的计算机系统中。
• I/O 通道控制方式：具有通道程序的计算机系统中。

为何要引入设备独立性？如何实现设备独立性？

答：现代操作系统为了提高系统的可适应性和可拓展性，所以需要实现设备独立性。
为了实现设备的独立性，需要引入逻辑设备和物理设备的概念。

何谓设备虚拟？实现设备虚拟时所依赖的关键技术是什么？

答：设备虚拟指把独占的设备经过处理后改造成虚拟设备
所依赖的关键技术是：将设备分配给多个进程使用，并根据访问顺序对设备进行控制。

在实现后台打印时，SPOOLing 系统应为请求I/O的进程提供哪些服务？

答：提供以下服务
为输出进程申请一块空间，并将要打印的数据发往其中
输出进程为用户进程申请空白用户打印表，设置打印要求，将该表挂起到请求打印队列
打印机空闲猴从打印队列取首个打印表并根据打印要求送入内存缓存区进行打印。

引入缓冲的主要原因是什么？

答：主要原因是：匹配CPU和I/O之间的速度差、减少对CPU的中断频率、提高CPU和I/O设备之间的并行性

简述题

1、I/O系统的功能、模型和接口
（1）I/O系统的基本功能
①隐藏物理设备的细节
②与设备的无关性
自动安装并寻找驱动程序，即插即用
③提高处理机和I/O设备的利用率
让处理机和I/O设备并行操作
④对I/O设备进行控制
这是驱动程序的功能
⑤确保对设备的正确共享
独占设备：打印机、磁带机
共享设备：磁盘
⑥错误处理
低级能够解决就不向高级报告，请求高级软件解决
（2）I/O系统的层次结构和模型
①I/O软件的层次结构
用户层I/O软件
设备独立性软件：映射、保护、分块、缓冲、分配
设备驱动程序：设置设备寄存器、检查状态
中断处理程序
②I/O系统中各种模块之间的层次视图
I/O系统上下接口（图6-2）
I/O系统的分层：中断处理程序→设备驱动程序→设备独立性软件
（3）I/O系统接口
①块设备接口
块设备、隐藏磁盘二维结构、抽象命令映射为低层操作
②流设备接口（Unix的）
字符设备：效率低、不可寻址
get和put操作：有缓冲区
in-control指令：互斥方式实现共享
③网络通信接口

2、I/O设备和设备控制器
（1）I/O设备
①I/O设备的类型
按使用特性：存储设备、I/O设备（输入输出交互的）
按传输速率：低速、中速、高速
②设备与控制器之间的接口
接口：数据信号线、控制信号线、状态信号线
（2）设备控制器
①设备控制器的基本功能
接收和识别命令、数据交换、标识和报告设备的状态、数据缓冲区、差错控制
②设备控制器的组成
设备控制器与处理机的接口、设备控制器与设备的接口、I/O逻辑
（3）内存映像I/O
①利用特定的I/O指令
缺点：访问内存和访问设备要两种不同的指令
②内存映像I/O
就是k为界限，0≤k≤n-1，就是内存地址；k≥n，就是寄存器地址。统一了对内存和对控制器的访问方法
（4）I/O通道
①I/O通道设备的引入
这是一种特殊的处理机，但只局限于I/O相关的指令、而且没有自己的内存
②通道类型
字节多路通道：一个大水喉，多条小水管；一个换头快，一个速率慢
数组选择通道：利用率低
数组多路通道：甚至可以并行操作
③“瓶颈”问题
增加通路即可解决

3、中断机构和中断处理程序
（1）中断简介
①中断和陷入
中断：由外部设备引起，暂停当前程序，执行中断处理程序
陷入：CPU内部事件引起的，多是出错故障
②中断向量表和中断优先级
中断向量表：asm有学
中断优先级：现实中有多个中断信号源，要规定不同优先级
③对多中断源的处理方式
屏蔽中断：顺序执行。优点简单；缺点无视实时中断请求
嵌套中断：有个优先级
（2）中断处理程序
测定是否有未响应中断信号；
保护被中断进程的CPU环境；
转入相应设备处理程序；
中断处理；
恢复CPU现场并退出中断

4、设备驱动程序
（1）设备驱动程序概述
①设备驱动程序的功能
接收命令和参数，并转换为低层操作序列
检查I/O合法性，了解I/O工作状态，传递I/O设备操作有关参数，设置设备工作方式
及时响应设备控制器发来的中断请求，并根据中断类型，调用响应中断处理程序
②设备驱动程序的特点
抽象的I/O请求转换成具体的I/O操作，反映给I/O进程
和硬件特性紧密相关，终端驱动程序可以只有一个
常用控制方式：中断驱动、DMA
一部分必须用汇编语言写，很多驱动程序基本部分已经固化在ROM
允许可重入
③设备处理方式
一类设备一个进程
一个I/O进程负责各类设备的I/O操作
只为各类设备设置相应的设备驱动程序，供用户或系统进程调用（目前用得最多）
（2）设备驱动程序的处理过程
①将抽象要求转换为具体要求
②对服务请求进行校验
譬如要求打印机输入数据
③检查设备的状态
检测寄存器中的不同位，了解设备的状态
④传送必要参数
波特率、奇偶校验等等参数
⑤启动I/O设备
了解数据是否到达
（3）对I/O设备的控制方式
①使用轮询的可编程I/O方式
无限等待，好浪费CPU
②使用中断的可编程I/O方式
百倍提高CPU利用率
③直接存储器访问方式
至少传送一个数据块，DMA方式提高CPU和I/O之间的并行程度
④I/O通道控制方式
使用通道程序完成CPU指定的I/O任务

5、与设备无关的I/O软件
（1）与设备无关软件的基本概念
①以物理设备名使用设备
以前应用程序与物理设备直接相关
②引入了逻辑设备名
通过更换逻辑设备表即可改变显示终端
③逻辑设备名称到物理设备名称的转换
要搞一张逻辑设备表
（2）与设备无关的软件
①设备驱动程序的统一接口
要有统一接口，同时抽象设备名要映射到适当的驱动程序上
②缓冲管理
设置缓冲区，缓和CPU和I/O设备之间的速度矛盾、提高CPU利用率
③差错控制
暂时性错误：只有连续多次出错才报告上层，否则由设备驱动程序自己处理
持久性错误：要查清发生错误的原因，避免以后再发生错误
④对独立设备的分配与回收
独占设备要先申请
⑤独立于设备的逻辑数据块

与设备无关软件功能：设备驱动程序的统一接口、缓冲、错误报告、分配与释放专用设备、提高与设备无关的块大小

（3）设备分配
①设备分配中的数据结构
系统设备表SDT→设备控制表DCT：类型、标识符、状态、设备队列队首指针、重复执行次数、指向控制器表的指针→控制其控制表COCT→通道控制表CHCT
②设备分配时应考虑的因素
设备固有属性：独占、共享、虚拟设备
设备分配算法：FCFS、优先级高优先
安全性：安全、不安全
③独占设备的分配程序
独占设备：分配设备、控制器、通道
如果要设备无关地找设备，就要从SDT找DCT，再逐个测试安全性
（4）逻辑设备名到物理设备名映射的实现
①逻辑设备表LUT
逻辑设备名、物理设备名、设备驱动程序的入口地址
②逻辑设备表设置问题
整个系统一张LUT
或每个用户一张LUT

6、用户层的I/O软件
（1）系统调用与库函数
①系统调用
使用系统调用I/O设备，用户态→内核态→用户态
②库函数
库函数与调用程序接在一起
（2）假脱机系统
①假脱机技术
利用专门的外围控制机，先将低速I/O设备上的设局传送到高速磁盘上，或相反
②SPOOLing的组成
输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程、井管理程序
③SPOOLing系统的特点
提高I/O速度、将独占设备改造为共享设备、实现虚拟设备功能
④假脱机打印机系统
磁盘缓冲区、打印缓冲区、假脱机管理进程和假脱机打印进程
⑤守护进程
有个假脱机目录，由守望进程按目录文件依次完成各个进程设备的请求，就可以将一个独占设备改为多个进程共享设备

7、缓冲区管理
（1）缓冲的引入
①缓和CPU与I/O设备间速度不匹配的矛盾
速度有差距，都可以设置缓冲区
②减少对CPU的中断频率
③解决数据粒度不匹配的问题
生产者生产的数量和消费者消费的数量差距
④提高CPU和I/O设备之间的并行性
CPU和打印机可以并行工作呢
（2）单缓冲区和双缓冲区
①单缓冲区
缓冲区也会阻塞
②双缓冲区
CPU执行第一行中的命令时，用户可以继续向第二缓冲区输入下一行数据
如果两台电脑只设置但缓冲，就要再设置一个接收缓冲区，一个发送缓冲区
（3）环形缓冲区
①环形缓冲区的组成
空区R，装满的区G，正在使用的现行工作缓冲区C；另外还有多个指针
②环形缓冲区的使用
Getbuf和Releasebuf
③进程之间的同步问题
Nexti赶上Nextg：输入速度＞处理速度
Nextg赶上Nexti：处理速度＞输入速度
（4）缓冲池
①缓冲池的组成
专为生产者-消费者设置的，包含一个管理数据结构和一组操作函数，管理多个缓冲区
包括空白缓冲队列、输入队列、输出队列
②Getbuf过程和Putbuf过程
设置MS(type)互斥访问缓冲池队列和RS(type)进程同步使用缓冲区
③缓冲区的工作方式
收容操作、提取输入、收容输出、提取输出

8、磁盘存储器的性能和调度
（1）磁盘性能简述
①数据的组织和格式
数据组织和格式：磁盘-双面可存储盘片（存储面）-扇区-磁道（柱面）
②磁盘的类型
固定头磁盘、移动头磁盘
③磁盘访问时间
（2）早期的磁盘调度算法
①先来先服务
就是先来的先找，很公平很简单，但平均寻道好长
②SSTF最短寻道时间优先
选择一个与磁头距离最近的磁道
（3）基于扫描的磁盘调度算法
①扫描算法SCAN
来回
②循环扫描算法CSCAN
单程
③NStepSCAN和FSCAN调度算法
N步扫描算法：将磁盘请求队列分成若干长度为N的子队列，再用FCFS依次处理这些子队列
FSCAN算法：只分两个队列，一个现在要扫描的，一个是扫描时新冒出来的