内存管理 & 文件管理 & IO 管理

内存管理

==问题：缓和 CPU 和磁盘之间的速度矛盾==

解决：引入内存

==为什么需要内存管理？==

为了更好的支持多道程序并发执行。引入多道程序的并发执行之后，进程之间共享的不仅仅是处理机，还有内存。若不对内存进行管理，容易导致内存数据混乱。限制程序的并发性。

内存管理的主要功能：内存分配、 内存保护、 地址映射和内存扩充。

主要任务：

• 内存分配：为每道程序分配内存
• 内存保护：确保每道用户程序都只能在自己的内存空间里运行，彼此互不干扰。
• 地址映射：将地址空间的逻辑地址转换为内存空间与相对应的物理地址。
• 内存扩充：用于实现请求调用功能，置换功能等

程序的执行过程

预处理 -> 编译 -> 汇编 -> 链接（形成完成的逻辑地址） -> 装入

装入

• 绝对装入

  在编译时，直接产生绝对地址

  缺点：只适用于单道程序环境

• 静态重定位 可重定位装入

  编译和链接的时候，都是用的是相对地址。在装入时，产生绝对地址

  缺点：

  • 装入内存时，就需要分配程序所要求的全部内存空间。没有足够内存时，不能分配
  • 运行时不能移动

• 动态重定位 动态运行时装入

  程序运行时，产生绝对地址。需要重定位寄存器的支持

  优点：允许程序在内存中发生移动，可以实现紧凑

链接

• 静态链接

  在链接程序中，直接完成链接

• 装入时动态链接

  边装入边链接

• 运行时动态链接

  程序执行时动态链接，以段为基础

内存分配方式

• 连续分配
  • 单一连续分配
  • 固定分区分配
  • 动态分区分配
    • 首次适应
    • 循环首次适应
    • 最佳适应
    • 最坏适应
    • 快速适应
    • 伙伴系统
• 对换
• 离散分配
  • 基本分页存储管理
  • 基本分段存储管理
  • 请求分页存储管理
  • 请求分段存储管理

连续分配

单一连续分配

内存被分为系统区和用户区。系统区在低地址部分，用户区在高地址部分。

优点：

• 实现简单
• 无外部碎片
• 可以采用覆盖技术扩充内存
• 不一定需要内存保护

缺点：

• 只能用于当用户、单任务操作系统
• 有内部碎片
• 存储器利用效率极低

固定分区分配

一个进程只能选择一个分区

分区方式：

• 分区大小相等：缺乏灵活性
• 分区大小不等：增加了灵活性，可以满足不同大小进程需求

优点：

• 实现简单

缺点：

• 当用户程序过大时，可能所有分区都不能满足需求
• 产生内部碎片，内存利用率低

动态分区分配 PPT P55

• 用什么数据结构记录空闲分区情况

  • 空闲分区表
  • 空闲分区链

• 分配算法

  • 首次适应
    • 空闲分区表以地址递增的次序排列
    • 优点：优先利用内存低址部分的内存空间,保留了高址部分的大空闲区
    • 缺点：
      • 低址部分不断划分，产生小碎片（内存碎块、零头）；
      • 每次查找从低址部分开始，增加了查找的开销
  • 循环首次适应
    • 从上次找到的空闲分区的下一个空闲分区开始查找
    • 优点：使内存空闲分区分布均匀，减少查找的开销
    • 缺点：缺乏大的空闲分区
  • 最佳适应
    • 按其容量以从小到大的顺序
    • 缺点：产生许多难以利用的小空闲区
  • 最坏适应
    • 按其容量以从大到小的顺序形成一空闲分区链
    • 优点：剩下的空闲区还可以利用，同时查找效率很高。
    • 缺点：缺乏大的空闲分区。
  • 快速适应（基于索引）
    • 问题：基于顺序搜索的动态分区分配算法，不适用于大型的系统。
    • 引入：索引
    • 根据其容量大小进行分类
    • 优点：查找效率高，也不会产生内存碎片。
    • 缺点：在分区归还主存时算法复杂，系统开销较大。
  • 伙伴系统（基于索引）
    • 按照 2 的整数幂将空闲分区分类
    • 初始：整一个空间都是一块
    • 分配：
      • 如果存在空闲分区，则分配
      • 不然，向上查找分区，并且分裂
  • 哈希算法
    • 通过 hash 实现，快速计算在 hash 表中的位置。

  总结：

  

• 回收算法

  4 种情况

优点：无内部碎片，有外部碎片

覆盖

==问题：在小的内存空间运行大作业==

覆盖是由程序员实现的，操作系统根据程序员提供的覆盖结构来完成程序段之间的覆盖。

子程序 C 运行完成之后，子程序 B 将其覆盖。

优点：扩充内存

缺点：对用户不透明，增加了用户负担。

对换（交换）

==问题：在内存非常小的计算机上运行多道程序==

条件：需要 IO 速度较高的外存

将内存中暂时不能运行或者暂时不用的数据和程序换出到外存上面。

类型

1. 整体对换：以进程为单位对换
2. 部分对换：以页或者段为单位对换

外存划分为：文件区、对换区

优点：扩充内存

覆盖与对换的区别

• 覆盖可减少一个进程运行所需的空间。对换可让整个进程暂存于外存中，让出内存空间。
• 覆盖是由程序员实现的，操作系统根据程序员提供的覆盖结构来完成程序段之间的覆盖。对换技术不要求程序员给出程序段之间的覆盖结构。
• 覆盖技术主要在同一个作业或进程中进行。对换主要在作业或进程之间进行。

离散分配

分页存储管理方式

==问题：固定分区分配会产生内部碎片，动态分区分配会产生外部碎片。对内存的利用率较低。同时希望尽量避免碎片的产生。==

什么是基本分页存储管理方式

• 不具备页面对换功能

• 不具有支持实现虚拟存储器的功能

• 要求把每个作业全部装入内存后方能运行

页面大小的选择

小：

• 内碎片小，内存利用率高
• 页表过长，占大量内存，管理开销大

大：

• 页表短，管理开销小
• 内碎片大，内存利用率低

页面大小应当适中

地址变换机构

1. 基本地址变换机构

   需要页表寄存器 PTR

   1. 判断页号是否越界
   2. 计算实际物理地址

   通过硬件自动完成

   缺点：

   1. 每次访存都需要进行地址变换（查询页表），降低速度 -> TLB
   2. 每个进程引入页表，页表不能太大 -> 多级页表

2. 具有快表的变换机构

   需要快表（联想寄存器）

   原理：程序的局部性

3. 两级页表

   ==问题：大页表占用大的连续存储空间==

   顶级页表 = 页目录表 = 外层页表

   ==问题：没有必要让整个页表常驻内存，因为进程在一段时 间内可能只需要访问某几个特定的页面。==

   解决：类似于虚拟存储器，增加一位，是否在内存中。

优缺点

优点：分页从根本上克服了外零头（地址空间、物理空间都分割）。内存利用率提高。

缺点：逻辑完整的信息分到不同的页面，执行速度降低

分段存储器

问题：克服分页的缺点

目的：满足用户的需求

优点

• 便于编程

  用户常把自己的作业按逻辑关系划分成若干个段，每段都有自己的名字，且都从零开始编址。

• 信息共享

  两个作业的段表项指向同一个共享的段。可重入代码可以共享（不属于临界资源）。

• 分段保护

  • 存取控制保护
  • 地址越界保护

• 动态链接

• 动态增长

特点

段式的地址空间是二维的，因为没有办法给出一个整数便确定对应的物理地址。而需要显示的给出（段号，段内偏移量）

分段与分页的主要区别

相同点：

• 采用离散分配方式，通过地址映射机构实现地址变换

不同点：

• 页是信息的物理单位，分页是为了满足系统的需要；段是信息的逻辑单位，含有意义相对完整的信息，是为了满足用户的需要。
• 页的大小固定且由系统确定，由系统把逻辑地址分为页号和页内地址，由机器硬件实现；段的长度不固定，取决于用户程序，编译程序对源程序编译时根据信息的性质划分。
• 分页的作业地址空间是一维的；分段的作业地址空间是二维的,需要给出段名和段内地址。

段页式存储器

特点

优点：

• 分散存储，内存利用率较高
• 很好的满足用户需求，便于代码或数据共享，支持动态链接等

缺点：

• 一次访问转换成了三次访问

虚拟存储器

传统分配方式的特点

• 一次性：作业必须一次性全部装入内存后才能开始运行
  • 作业很大的时候，没有办法装入内存 -> 覆盖
  • 大量作业要求运行时，无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。 -> 对换
• 驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。浪费内存资源

思想 – 局部性原理

TLB，cache 的思想

• 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行
• 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。

虚拟存储器

定义：指具有请求调入（不在内存中）功能和置换（内存满了）功能，能从逻辑上对内存容量加以扩充的一种存储器系统。 -> 建立在离散分配的基础上

特点：

• 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
• 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
• 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大 于实际的容量。

容量

• 虚拟内存的最大容量是由计算机的地址结构（CPU寻址范围）确定的
• 虚拟内存的实际容量 =min（内存 + 外存，CPU寻址范围）

硬件支持 P168 PPT P14

1. 表机制

   

   

   段式具有增补位，用于表示该段是否动态增长。

2. 缺页/段中断机构

3. 地址变换机构

4. 段的共享与保护 PPT P70

   1. 共享：类似于索引节点的 DAG 图

   2. 保护

      1. 越界检查

      2. 存取控制检查

      3. 环保护机构

         OS 位于 0 环

         

内存分配策略 P171

• 最小物理块数的确定：保证进程正常运行所需的最小物理块数

• 物理块分配策略：

  • 固定分配局部置换

    为进程分配的物理块数在整个运行期间都不再改变。

    缺点：难以确定每个进程分配的物理块数，太少导致频繁缺页中断；太多，导致资源利用率下降

  • 可变分配全局置换

    当进程发生缺页，若系统中有 空闲的物理块，则分配一个物理块并装入缺页；

    优点：可以动态增加物理块数

    缺点：盲目增加物理块，导致并发能力下降；被选中的进程缺页率增加

  • 可变分配局部置换

    若某个进程发生缺页，则只能将自己的某个内存页换出。OS 根据缺页率进行物理块分配的调整

• 物理块的分配算法：

  • 平均分配算法
    • 将系统中所有可供分配的物理块，平均分配给各个进程。
    • 缺点: 未考虑各进程本身的大小
  • 按比例分配算法
    • 根据进程的大小按比例分配物理块。
  • 考虑优先权的分配算法
    • 在实际应用中，为了照顾重要的、急迫的作业尽快完成，应为它分配较多的内存空间
    • 算法：
      • 一部分按比例分配给各进程；
      • 一部分则根据各进程的优先权，适当地增加其相应份额，分配给各进程

页面调入策略

何时调入页面

• 预调页策略
  • 主要用于进程的首次调入时，由程序员指出应该先调入哪些页。
• 请求调页策略
  • 当程序在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求
  • 优点：由请求调页策略所确定调入的页，一定会被访问；请求调页策略比较容易实现
  • 缺点：每次仅调入一页，需花费较大的系统开销，增加了磁盘 I/O的启动频率。

何处调入页面

• 系统拥有足够的对换区空间：可以全部从对换区调入所需页面，以提高调页速度

  

• 系统缺少足够的对换区空间：

  • 不会被修改的文件（不放入对换区），直接从文件区调入；当换出这些页面时，因为未修改不用换出，再调入时仍从文件区调入。
  • 可能被修改的部分（放入对换区），换出时需调到对换区，换入时从对换区调入；

  

• UNIX 方式：

  • 第一次从文件区调入
  • 再次使用的时候，从对换区调入

  

页面置换算法

• OPT
  • 算法无法实现，但可评价其他算法
  • 优点：保证获得最低的缺页率
  • 缺点：无法预知一个进程在内存的若干个页面，哪个在未来最长时间内不再被访问。
• FIFO
  • Belady 异常——当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
  • 只有 FIFO 会产生 Belady 异常
• LRU
  • 硬件实现：寄存器（最小值）、栈（栈顶）
• CLOCK
  • 最近未用算法（NRU，Not Recently Used）
  • 算法：扫描访问位
  • 操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。

抖动 & 工作集 P184 PPT P60

定义：刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。

原因：进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）

预防方法

• 采取可变分配局部置换
• 把工作集算法融入到处理机调度中
• 利用“L=S”准则调节缺页率
• 选择暂停的进程

文件系统

文件系统的主要功能：

• 对文件的基本操作
• 文件共享
• 文件保护
• 管理与磁盘的信息交换
• 完成逻辑结构 -> 物理结构的转变

文件系统结构：

文件系统的基本概念

文件

文件是存储在硬盘上的信息集合

文件的组成：

• 数据项
  • 基本数据项
  • 组合数据项
• 记录：数据项的集合
• 文件：
  • 记录式文件：由相似的记录组成
  • 流式文件：字符流文件

文件的属性

1. 文件名
2. 标识符
3. 类型
4. 位置

文件操作

1. 文件的打开和关闭

   将该文件的属性从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号返回给用户。当用户需要操作的时候，可以利用系统返回的索引号向系统提出操作请求。关闭即关闭文件描述符

2. read write delete create

文件的逻辑结构

无结构文件（流式文件）

只能通过穷举搜索的方式。对基本信息单位操作不多的文件较适用于采用无结构文件。源程序文件、目标代码文件。

有结构文件（记录式文件）

1. 顺序文件

   记录定长，顺序排列

   1. 存储方式：顺序存储、链式存储
   2. 结构：串结构、顺序结构（排序）

2. 索引文件

   解决：顺序文件存储可变长记录效率低的文件

3. 索引顺序文件

   解决：索引文件中一个记录对应一个表项，占用过多的额外空间

   改进为：一个索引对应一组记录

   可以优化查询效率

4. 多级索引顺序文件

文件的物理结构

文件分配方式（磁盘非空闲区的管理）

连续分配

优点：1. 实现简单 2. 存取速度快

缺点：1. 文件长度不宜动态增长 2. 产生外部碎片

链接分配

==问题：外部碎片和文件大小==

• 隐式链接：

  • 优点：方便文件的拓展，不会出现外部碎片。外存利用率高。
  • 缺点：只支持顺序访问，不支持随机访问，查找效率低

• 显式链接

  • 问题1：需要将物理块读入内存，查找效率低
  • 解决1：引入 FAT，一个磁盘只有一个 FAT，开机的时候读入 FAT，常驻内存
  • 问题2：指针需要消耗内存
  • 解决2：将多个块并在一起，形成一个簇
  • 缺点：文件分配表需要消耗一定的内存
  • 优点：支持随机访问和顺序访问。

索引分配

问题：

• 不能支持高效的随机存取，需要在 FAT 中顺序查找
• FAT 需要占用较大的内存空间

优点：支持随机访问，文件拓展容易实现

缺点：索引表需要占用比较多的空间

1. 单级索引分配
2. 多级索引分配
   1. 解决：单级索引分配索引表过大的问题
3. 混合索引分配

文件存储空间管理（磁盘空闲区的管理）

• 空闲表法

• 空闲链表法

  • 空闲盘块法
  • 空闲盘区法

• 位示图法

• 成组链接法

  问题：空闲表法、空闲链表法不适用于大型文件系统。

  解决：引入超级块

  • 需要读入内存，并且保持数据一致性

目录

解决：对文件实施有效的管理

• 实现 “按名存取” 基本功能
• 提高对目录的检索速度
• 文件共享
• 允许文件重名

文件控制块 FDB

用于描述和控制文件的数据结构。

描述了文件的文件名、物理地址、逻辑结构和物理结构。存取控制信息、使用信息

目录结构

1. 单级目录结构

   优点：实现按名存取

   缺点：不适用于多用户操作系统、查找速度慢、不允许重名

2. 两级目录结构

   优点：提高检索目录的速度、不同的用户目录中文件可以同名

   缺点：无法文件共享

3. 树形目录结构

   引入相对路径的概念，减少了磁盘 IO 的次数

   优点：可以很方便地对文件进行分类，层次结构清晰， 也能够更有效地进行文件的管理和保护。

   缺点：不能实现文件共享

4. 无环图目录结构

   方面用户共享

索引节点

问题：文件很多的时候，目录文件占用盘块

解决：文件名 + 文件描述信息，文件描述信息单独构成索引节点

使用 stat filename 或者 ls -i 可以查看索引节点

文件共享

• 基于索引节点的共享方式（硬链接）

• 基于符号链的共享方式（软连接）

文件保护

• 口令保护：设置密码
• 加密保护：对文件加密，eg：异或加密
• 访问控制：chmod

磁盘调度

• 磁盘、磁道、扇区（块）
• 盘面、柱面(相对位置相同的磁道)

磁盘读写时间 = 寻道时间 + 延迟时间 + 传输时间

• 寻道时间 = 启动磁头时间 + 移动磁头的时间 （时间最长）
• 延迟时间 = $\frac{1}{2r} = \frac{T}{2}$
• 传出时间 = $\frac{b}{N} \times \frac{1}{r}$

1. 先来先服务 FCFS

   优点：公平

   缺点：FCFS 的性能很差

2. 最短寻找时间优先 SSTF

   优点：性能较好，平均寻道时间短

   缺点：可能产生饥饿现象

3. 扫描算法 SCAN 电梯算法

   优点：性能较好，平均寻道时间较短，不会产生饥饿。

   缺点：1. 只有到达需要访问的边界才能改变方向 2. 对各个位置响应的频率不平均

4. 循环扫描算法 C-SCAN

   优点：解决响应不平均的问题

   缺点：平均寻道时间更长

文件系统维护命令

• du: 查看文件磁盘使用情况 du [FILE]
• df: 查看文件所在磁盘剩余情况，df [FILE]
• free: 查看系统的物理村内和虚拟内存的使用情况

设备管理

IO 系统

IO 设备：可以将数据输入到计算机，或者可以接受计算机输出数据的外部设备，属于计算机中的硬件部件

UNIX 将外部设备抽象成文件，用户可以使用与文件操作相同的方式对外部设备进行操作

• write：向外部设备写出数据
• read：向外部设备读入数据

IO 系统的基本功能

• 隐藏物理设备的细节
• 与设备的无关性
• 提高处理及和 IO 设备的利用率
• 对 IO 设备进行控制：驱动
• 确保对设备的正确共享：独占设备（一段时间内一个）、共享设备（一个时刻一个）
• 错误处理

IO 软件的层次

1. 用户层软件：实现与用户交互的接口
2. 设备独立性软件：用户程序和驱动程序的统一接口
3. 设备驱动程序：实现环境对设备发出指令
4. 终端处理程序：保存 CPU 环境，装入中断处理

其中 2，3，4 属于操作系统的内核部分，即 IO 系统

用户层软件

功能：实现了与用户交互的接口（库函数），然后翻译成等价的系统调用

设备独立性软件

功能：与硬件特性无关的功能几乎都在这一层实现

• 向上提供统一的系统调用接口
• 设备保护：设置对设备文件的访问权限
• 差错处理：对设备的错误进行处理
• 设备的分配和回收
• 数据缓冲区管理
• 建立逻辑设备名到物理设备名的映射关系：逻辑设备表 LUT
  • 整个系统只设置一张 LUT，只适用与单用户操作系统，各个用户的逻辑设备名不能重复
  • 为每个用户设置一张 LUT，存放在用户管理进程的 pcb 中，逻辑设备名可以重复
  • 作用：记忆化进程使用的设备的映射关系

驱动程序

功能：将设备独立性软件的系统调用转化为具体操作

中断处理程序

计组中的中断处理程序

总结

• 设备管理：设备独立性软件
• 涉及硬件的具体细节：设备驱动程序

设备与 CPU 之间的接口 – IO 控制器

• 与 CPU：数据、地址、控制线
• 与 设备：数据、状态、控制

功能 P197

组成：

• 与 CPU、设备的接口
• 数据寄存器：存储数据
  • CPU -> 设备时，存储 CPU 的数据
  • 设备 -> CPU时，存储设备的数据
• 控制寄存器：存储 CPU 发来的指令
• 状态寄存器
• IO 逻辑：负责接受和识别 CPU 各种命令，对设备发出命令

内存映像IO

问题：实现 CPU 和控制器交互

利用特定的 IO 指令 （寄存器独立编址）

使用不同的指令来对控制器操作

缺点：需要设置专门的 IO 指令来对控制器编址

内存映像 IO （统一编址）

将控制器和内存统一编址

优点：简化了指令。可以采用对进行操作的指令来对控制器操作

IO 通道

什么是通道

问题：虽然出现了控制器，但是 CPU 的负担依然很重

工作方式：CPU 向通道发送 IO 命令，通道执行通道程序，完成 IO 之后向 CPU 发出中断

与 CPU 的不同点：

• 命令类型单一，仅能执行 IO 命令
• 没有自己的内存，通道程序存放在主存中

类型 P201

• 字节多路通道（字节传输）：是一种字节交叉方式工作的通道，采用多路分时复用 – 按时间片轮转方式共享主通道

• 数组选择通道（数组传输）：

  • 问题：字节多路通道不适用于连接高速设备
  • 瓶颈：只有一个 IO 子通道，但是可以实现块传输
  • 缺点：容易被一台设备独占，利用率低

• 数组多路通道（数组传输）：

  将上述两个技术结合在一起。使用于中高速的 IO 设备

瓶颈

问题：由于通道价格昂贵，致使数量较少，使它成为I/O系统的瓶颈 ，进而造成系统吞吐量的下降

解决：增加设备到主机间的通路而不增加通道

IO 控制方式

问题：如何告诉设备，CPU 需要设备做什么

使用轮询的可编程 IO 方式

优点：实现简单

缺点：CPU 和 IO 设备只能串行工作，CPU 需要一直轮询检查长期处于忙等状态，CPU 利用率低。

中断驱动方式

解决：引入中断机制

优点：CPU 和 IO 设备可以并行工作

缺点：频繁的中断处理会消耗较多的 CPU 时间

DMA 方式 P211

解决：引入 DMA 控制器

优点：数据以块传输。CPU 和 IO 设备的并行得到提高

缺点：CPU 每发出一条 IO 指令，只能读写一个或多个连续的数据块。如果需要读取离散的数据块，则需要多条 IO 指令

通道控制方式

优点：每次读/写一组数据块；CPU、通道、I/O设备可并行工作，资源利用率很高

缺点：实现复杂，需要专门的通道硬件支持

指令格式：

• 操作码
• 内存地址 & 计数
• 通道程序结束位 P：1 表示这是最后一条指令
• 记录结束标志位 R：1 表示这是处理某记录的最后一条指令

总结

SPOOLing 技术

需要多道程序技术的支持，

问题：独占设备 -> 共享设备，缓和 CPU 和 IO 速度的不匹配

思想：空间换时间

脱机技术：纸带机 -> 外围控制机 -> 磁带机 -> CPU -> 磁带机 -> 外围控制机 -> 纸带机

假脱机技术：输入设备 -> 输入进程 -> 输入井 输出井 -> 输出进程 -> 输出设备

• 输入输出井 = 磁盘
• 输入输出进程 = 外围控制机
• 缓冲区用于暂存数据

模拟打印机

1. 在输出井中开辟一段空间，用于存放数据
2. 申请一张打印请求表（用于说明文件存放的位置），挂在文件队列上
3. 输出进程根据表上的信息，将数据从外存 -> 内存 -> 打印机

特点

1. 提高了 IO 速度：将 IO 操作变为对输入输出井的操作，提高了 IO 速度；缓和 CPU 和 IO 速度的不匹配
2. 将独占设备改造成了共享设备
3. 实现了虚拟设备功能

设备分配（设备独立性软件）

设备的分配和回收

问题：应用程序直接使用设备与系统中的物理设备直接相关，导致不灵活，给用户带来不便

解决：引入逻辑设备名

好处：

• 逻辑设备是抽象的设备名
• 可实现 IO 重定向

逻辑设备名到物理设备名的映射 – 逻辑设备表

• 逻辑设备名
• 物理设备名
• 驱动程序入口地址

设备的固有属性

• 独占设备
• 共享设备
• 虚拟设备：采用 spooling 技术将独占设备改造成共享设备

设备分配算法

• 先来先服务
• 优先级高者优先
• 短任务优先

分配的安全性 PPT P79

• 安全分配方式：为进程分配一个设备之后，将进程阻塞，本次 IO 完成之后将进程唤醒
  • 优点：不会死锁，破坏 请求和保持 条件
  • 缺点：串行工作
• 不安全分配方式：进程发出 IO 请求之后，可以继续执行
  • 优点：并行工作
  • 缺点：可能死锁

分配方式

• 静态分配：开始就得到全部资源

  破坏请求和保持条件，不会死锁

• 动态分配：动态申请

分配管理中的数据结构

设备控制表 DCT：

• 属性：类型、标识符、状态、指向控制器表的指针
• 运行相关：重复执行次数、设备任务队列的队首 PCB 指针

控制器控制表 COCT：

• 属性：控制器标识符、状态、指向通道表的指针
• 运行相关：等待控制器的队首和队尾 PCB 指针

通道控制表 CHCT：

• 属性：标识符、状态、指向 COCT 的指针
• 运行相关：等待控制器的队首和队尾 PCB 指针

系统设备表 SDT：

• 包含系统中全部的设备情况
  • 设备类型、标识符、驱动程序入口
  • DCT

设备分配步骤

1. 根据进程请求的物理设备名查找 SDT
2. 根据 SDT 找到 DCT，
   1. 忙碌：挂载进程 PCB 到设备等待队列
   2. 空闲：将设备分配给进程
3. 根据 DCT 找到 COCT，分配与上面相同
4. 根据 COCT 找到 CHCT，分配与上面相同

只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功

缺点 & 问题

1. 需要提供物理设备名，底层细节对用户不透明，不方便编程
2. 程序不方便移植
3. 同类型的设备利用率低

解决

引入逻辑设备名到物理设备名的映射。

1. 根据进程请求的逻辑设备名查找 SDT

2. 根据 SDT 找到 DCT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表（LUT）中新增一个表项。

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

   1. 忙碌：挂载进程 PCB 到设备等待队列
   2. 空闲：将设备分配给进程

3. 根据 DCT 找到 COCT，分配与上面相同

4. 根据 COCT 找到 CHCT，分配与上面相同

缓冲区管理

作用

1. 缓和 CPU 和 IO 设备之间速度不匹配的矛盾
2. 减少对 CPU 的中断频率，放宽对 CPU 中断对应时间的限制
3. 解决数据粒度不匹配的问题，CPU 一块一块输出，IO 设备一个字符输出
4. 提高 CPU 和 IO 设备之间的并行性

缓冲区管理策略

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

掌握计算处理一块数据的平均时间

C: CPU 处理时间

M：IO 设备 -> CPU 传送时间

T：IO 设备输入时间

单缓冲区

• T > C

• T < C

结论：max(C, T) + M

双缓冲区

• T > M + C

• T < M + C

  

结论：max(T, M + C)

使用单双缓冲区在通信时的区别

单缓冲区：半双工通信

双缓冲区：全双工通信

循环缓冲区

问题：当输入和输出的速度相差很大时，双缓冲效果不理想，但可增加缓冲 区的数量，改善情况

解决：引入循环队列逻辑结构的缓冲区

缓冲池

通过一系列缓冲区组成

缓冲区使用状况分类

• 空缓冲队列
• 输入队列
• 输出队列

缓冲区功能分类

• 用于收容输入数据的工作缓冲区（hin）
• 用于提取输入数据的工作缓冲区（sin）
• 用于收容输出数据的工作缓冲区（hout）
• 用于提取输出数据的工作缓冲区（sout）