第四章存储器管理

存储器的结构层次

主存储器与寄存器

CPU的控制部件只能从主存储器中取得指令和数据，数据能够从主存储器读取并将它们装入到寄存器中，或从寄存器存入到主存储器中
高速缓存和磁盘缓存
1. 高速缓存（Cache）：将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。
2. 磁盘缓存：利用主存中的存储空间，暂存从磁盘中读出（或写入）的信息。
内存管理的功能
1. 内存分配与回收
  - 根据分配时机的不同，可分为三种方式：
    - 直接分配：程序员采用物理内存地址编写程序
    - 静态分配：作业运行之前各目标模块连接后，把整个作业一次性装入内存，并在作业运行过程中，不允许作业再申请其他内存，或在内存中移动位置。
    - 动态分配：作业要求的基本内存空间是在模块装入内存时分配的，但在运行过程中允许作业申请附加的内存空间，或在内存中移动。即分配工作在作业运行前以及运行中逐步完成。
2. 地址转换：逻辑地址->物理地址
  - 把用户程序装入内存时对有关指令的地址部分的修改定义为从程序地址到内存地址的地址转换，或称为地址重定位。
  - 物理地址：内存地址，它是用于唯一标识一个内存单元的编号。所有的物理地址构成了物理空间。
  - 逻辑地址:程序地址/相对地址/虚地址。它是指在源程序经过汇编或编译后形成的目标代码中，用于反映目标代码中指令或数据的相对位置关系的地址。逻辑地址都是以“0”为基址顺序进行编址的，这样生成的目标程序占据一定的地址空间，称为程序的逻辑地址空间，简称逻辑空间。
  - 地址重定位原因：程序装入内存后，逻辑地址和内存地址不一致。
3. 内存保护：防止越界、非法访问
4. 内存共享：多个进程共享内存中的同一段信息
  1. 优点：节省内存空间，减少I/O量，提高性能。
  2. 实现：代码必须是可重入的（允许多个进程同时访问的代码）；必须设置共享的数据结构
5. 内存扩充：小内存运行大程序，逻辑扩充
  - 对内存进行逻辑上的扩充，现在普遍采用覆盖、对换和虚拟存储器技术。
  - 虚拟存储器的理论基础是程序的局部性原理：时间局部性、空间局部性
覆盖
1. 引入：目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。
2. 原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。
  - 将程序的必要部分（常用功能）的代码和数据常驻内存
  - 可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存
  - 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)
3. 缺点：编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度，增加用户不透明性；外存转入覆盖文件，时间换空间。
对换
1. 引入：多道程序环境下，某些进程由于事件尚未发生被阻塞，却占用大量内存；有着许多作业在外存上等待，
  因无内存而不能进入内存运行的情况。
2. 对换：将内存中暂时不能运行的进程或者暂时不用的程序和数据调到外村上，再把已经具备运行条件的进程或进程需要的数据调入内存。
3. 对换类型：整体（进程）对换：以进程为单位；部分（页面、分段）对换。
  
  为实现进程对换，系统必须实现三方面的功能：对换空间的管理、进程换入与换出
4. 对换空间的管理：OS将外存分为文件区（存放文件、离散分配）和对换区（存放从内存换出进程，连续分配以提高换入换出速度）
5. 进程的换入与换出：
  - 换出：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程
  - 换入：查看所有进程状态，找出就绪状态但已被换出的进程，将换出时间最久的进程换入

程序的装入和链接

用户源程序变为可执行程序过程：编译（源代码->目标模块）、链接（目标模块 + 库函数->装入模块）、装入（装入模块装入内存）
程序的装入方式
1. 绝对装入方式：编译时知道程序驻留主存的位置，编译程序直接产生绝对地址的目标代码。所以程序中逻辑地址与内存地址相同，无需进行修改。多道程序环境下，编译程序不知道目标模块放入内存何处，故只适用于单道程序环境。
2. 可重定位装入方式：多道程序环境下，目标模块起始地址为0，需要重定位。
  1. 静态重定位（装入即确定）：优点为无需硬件支持，缺点为必须占用连续内存空间，装入后无法移动。
  2. 动态重定位（装入的为相对地址；相对地址转换为物理地址的工作，被推迟到程序指令）：优点为内存空间动态可变，移动只需修改寄存器；缺点为需要硬件支持，实现存储管理软件算法复杂。
    
    寄存器BA：存放程序首地址，访问时地址位BA+相对偏移。
程序的链接方式
1. 静态链接：运行之前先将目标模块与库函数链接为完整的装入模块，以后不拆开。
  1. 相对地址进行修改。
  2. 变换外部调用符号。
2. 装入时动态链接：用户源程序经编译后所得的目标模块，是在装入内存时边装入边链接的。即装入一个模块，如果发生一个外部模块调用事件，则引起装入程序找出外部模块并装入内存，并按静态链接的方式修改目标模块的相对地址。
  
  优点：
  - 便于修改更新。目标模块分开存放，修改、更新目标模块容易。
  - 便于目标模块共享。
3. 运行时动态链接（效率最高）：将对某些模块的链接推迟到程序执行时才进行链接。即在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。

下面的部分将解决如何为程序分配内存的问题

连续分配方式

单一连续分配：只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分
固定分区分配：将内存用户空间划分为若干个固定大小的区域，每个分区只装入一道作业。则允许几道作业并发进行。
1. 划分分区方法：
  - 所有内存分区大小相等。缺点：缺乏灵活性，程序太小浪费、太大装不下。
  - 分区大小不等，内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。
2. 内存分配：将分区按照大小排队，并建立一张分区使用表，包含每个分区起始地址、大小、状态。
3. 优点：相对于单一分区，存储利用率高，可实现多道
4. 缺点：内存利用率低，区经常未填满，存在碎片；存在分区过小无法装入情况；程序度数受到分区数所限；动态扩充需要付出移动代价；程序间不可共享。
动态分区分配：根据进程的实际需要，动态地为之分配内存空间。
1. 分区分配中的数据结构
  1. 空闲分区表：每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。
  2. 空闲分区链：将所有的空闲分区链接成一个双向链；分区尾部重复设置状态位和分区大小表目。当分区被分配出去以后，把状态位由“0”改为“1”
2. 分区分配算法
  1. 首次适应算法：要求空闲分区链以地址递增的次序链接。分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。
    - 倾向于优先利用内存中低址部分的空闲分区
    - 每次都从头找起，查找开销大，适合较大作业
  2. 循环首次适应算法：从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区
    - 使内存中的空闲分区分布得更均匀，但缺乏大的空闲分区
  3. 最佳适应算法：每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业
    - 将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链
    - 存储器中会留下许多难以利用的小空闲区
  4. 最坏适应算法：挑选一个最大的空闲区分割给作业使用
    - 产生碎片几率小
    - 使存储器中缺乏大的空闲分区
3. 分区回收算法：将相邻的空闲分区合并成一个空闲分区。
  1. 上邻空闲区：与上空闲区合并，修改长度
  2. 下邻空闲区：与下空闲区合并，修改其长度和首址。
  3. 上、下邻空闲区：与上、下空闲区合并，修改其长度和首址，从空闲区表中或空闲链表中删除下接的空闲项。
  4. 上下都不相邻空闲区：在空闲区表中或空闲链表中添加新项，添上被回收分区长度和首址。
可重定位分区分配：动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能，通常，在找不到足够大的空闲分区来满足用户需求时进行紧凑。

在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。

基本分页存储管理方式

页面
1. 页面实现：内存分为等长页面，称之为块/页帧；进程的地址空间划分成等长页，页与页面通常等长；程序在内存中存放时，页内连续、页见不一定连续。
2. 页内碎片：进程的最后一页经常装不满一块而形成了不可利用的碎片
1. 页面大小：应是2的幂，通常为512 B～8 KB
地址结构：分页地址中的地质结构如下：

它含有两部分：前一部分为页号P，后一部分为位移量W（或称为页内地址d）。图中的地址长度为32位，其中0～11位为页内地址，即每页的大小为4 KB；12～31位为页号，地址空间最多允许有1M页。
页表：记录了相应页在内存中对应的物理块号，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。
- 作用：实现从页号到物理块号的地址映射。
地址变换机构
1. 页表大多驻留在内存中，系统中只设置一个页表寄存器PTR，在其中存放页表在内存的始址和页表的长度。进程未执行，页表始址和长度存放在PCB中，调用时装入PTR
2. 快表（联想寄存器）：具有并行查寻能力的特殊高速缓冲寄存器
两级和多级页表：解决页表过大问题
1. 解决页表过大两种方法：
  - 离散分配方式解决难以找到一块连续大内存问题
  - 只将需要部分页表调入内存，不需要则驻留在硬盘上，需要再调入
2. 二级页表：将页表分页并离散分配到物理块中，并为离散分配的页表建立外层页表（存放下层页表的物理地址），于是逻辑地址变为：外层页号+外层页内地址+页内地址
  
  需为外层页表增加寄存器存放外层页表始址，并利用逻辑地址的外层页号作为外层页表的索引
3. 多级页表：对外层页表再进行分页。
页表特点：
1. 优点：分配和回收简单、消除“碎片”问题、可实现虚存、共享；
2. 缺点：页面划分不考虑程序逻辑结构、共享受限、二次访内，慢。

基本分段存储管理方式

分段方式满足的需求：
1. 方便编程：用户把作业按逻辑关系划分为若干段，每段都是从0开始编址。
2. 信息共享：对程序和数据共享都是以信息的逻辑单位为基础的。
3. 信息保护：对信息的逻辑单位进行保护。
4. 动态增长：其他存储方式难以应付数据段的增长，分段存储管理可以实现。
5. 动态链接：动态链接要求以段作为管理的单位。
基本原理
1. 分段：将用户程序空间按逻辑划分为几段，每个段内连续编址，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段段内也从0开始编址，段内地址是连续的，而段间是不一定连续编址的
  
  分段地址结构：
2. 以段为单位分配内存，段内连续完整，但各段之间可以不连续存放
3. 段式逻辑地址二维：段号+段内地址
4. 每个进程一张段表，实现地址转换、信息保护、共享、扩充、动态链接等
段表：为使程序能正常运行，要能从物理内存中找出每个逻辑段所对应的位置，系统中为每个进程建立一张段映射表，常见的是将段表放在内存中。
地址变换机构：
1. 段表寄存器，用于存放段表始址和段表长度TL
2. 检测段号越界中断、段内地址越界中断
3. 联想寄存器：保存最近常用的段表项，类似于快表
段式特点：
1. 优点：符合用户观点和程序逻辑，易于保护、共享、动态链接和动态扩充
2. 缺点：分配回收类似可变式分区策略，复杂；存在二次访内，慢；有外部碎片，可能需要移动开销
分段的信息共享

分页、分段主要区别

页是信息的物理单位，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
页的大小固定且由系统决定，段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
分页作业地址空间为1维，分段标住地址为二维，即段名+段内地址

段页式存储管理方式

段页式引入：
- 段式优点：便于共享和保护，动态伸缩和链接
- 页式优点：消除碎片问题，分配和回收简单
- 段页式：结合两者优点
段页式存储管理实现
1. 基本原理：先将用户程序分为若干个段（每个进程都有段表），再把每个段分成若干个页（每个段都有一张自己的页表），并为每一个段赋予段名。
2. 内存分页面、存储管理的分配单位是页
3. 逻辑地址：<段号 S，页号 P，页内偏移 W>
4. 段表基址寄存器：保存正在运行程序的段表首址
  
  段表限长寄存器：保存正在运行程序的段表长度
  
  快表：一组联想寄存器（快段表+快页表）
地址变换过程（须配置一个段表寄存器，其中存放段表始址和段表长TL）
1. 先通过逻辑地址的段号查段表，需要越界检查；
2. 通过段表查出页表首址，在使用页号获取块号，并与块内地址组成物理地址。
- 注：为了获取一条指令或数据，需要三次访存：段表、页表、取指令/数据。故地址变换机构设高速缓冲寄存器，需同时利用段号和页号检索高速缓存。
段页式特点：
1. 分配与回收（同页式）
2. 共享与保护、动态伸缩、动态链接（同段式）
3. 三次访内，必须提供联想寄存器支持
4. 碎片n倍于页式（n为程序段数）

虚拟存储器的基本概念

出现原因：
- 有的作业很大，超过了内存总量，作业不能全部装入内存导致作业无法运行
- 大量作业要求运行但内存容量不足，只能将少数作业装入内存先运行
常规存储器管理方式的特征：一次性（作业运行前需要一次性装入）、驻留性（作业装入后一直驻留直至结束）
虚拟存储器定义：基于局部性原理，应用程序在运行之前，没有必要全部装入内存，仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。
- 请求调页（段）：如果程序所要访问的页(段)尚未调入内存(称为缺页或缺段)，此时程序应利用OS所提供的请求调页(段)功能，将它们调入内存，以使进程能继续执行下去。
- 页面置换：如果此时内存已满，无法再装入新的页(段)，则还须再利用页(段)的置换功能，将内存中暂时不用的页(段)调至盘上，腾出足够的内存空间后，再将要访问的页(段)调入内存，使程序继续执行下去。
虚拟存储器的实现方法
1. 分页请求系统：在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。
  1. 硬件支持：请求分页的页表机制、缺页中断机构、地址变换机构
  2. 软件支持：实现请求调页的软件和实现页面置换的软件
2. 分段请求系统：在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统
  1. 硬件支持：请求分段的段表机制、缺段终端机构、地址变换机构
虚拟存储器的特征：多次性（一个作业被分成多次调入内存运行，虚拟存储器最重要的特征）、对换性（允许在作业的运行过程中进行换进、换出）、虚拟性（从逻辑上扩充内存容量）
离散分配 -> 多次性和对换性 -> 虚拟性

请求分页存储管理方式

页表机制：应用程序的一部分调入内存，还有一部分仍在盘上，故须在页表中再增加若干项，供程序(数据)在换进、换出时参考。

当没有虚存时只存页号和物理页号。

P：是否已经调入内存；A：本页在一段时间内访问了几次；M：本页调入后是否修改
缺页中断机构：访问的页面不在内存时，便产生一缺页中断
- 缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时所产生和处理的。
- 一条指令在执行期间，可能产生多次缺页中断。
  
  涉及6次缺页中断的指令：
地址变换机构：在分页系统地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能而形成的，如产生和处理缺页中断，以及从内存中换出一页的功能
- 地址变换时，先检索快表，找到则修改表项中的访问位，对于写指令还要设置修改位；
- 然后利用页表项中给出的物理块号和页内地址形成物理地址
内存分配策略和分配算法

在为进程分配内存时，涉及到三个问题：最小物理块数确定、物理块的分配策略、物理块分配算法
1. 最小物理块确定：
  - 单地址指令 + 直接寻址，最少需要两块（一块指令、一块数据）
  - 间接寻址，最少三块
  - 指令多于两个字节，需要更多
2. 物理块分配策略
  1. 固定分配局部置换：每个进程分配一定数目的物理块，置换从其中选择。困难：难以确定每个进程分配多少。
  2. 可变分配全局置换：某进程缺页时，系统从空闲物理块队列中取出一个物理块分配给该进程，并将调入的页装入。当空闲块用完后，OS从内存中选择一页调出，该页可能是任一进程的页。
  3. 可变分配局部置换：置换时只允许从该进程的页面中调出。缺页率过高时分配额外的块。
3. 物理块分配算法
  1. 平均分配：将可供分配的物理块平均分配给各进程
  2. 按比例分配：根据进程大小按比例分配物理块
  3. 考虑优先权的分配：把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。
调页策略
1. 调入页面时机：预调页策略、请求调页策略
2. 确定从何处调入页面
  - 系统拥有足够对换区，则全部从对换区调入
  - 缺少足够的对换区时，不会被修改的文件全从文件区调入，可能被修改的部分换出时换到对换区
3. 页面调入过程
  
  访问页面未在内存→向CPU发出缺页中断→中断处理程序保留CPU环境→转入缺页中断处理程序→查页表调入（如已满需要置换）
  
  整个页面的调入过程对用户是透明的。

页面置换算法

最佳置换算法：不可能实现，用于评价其他算法
FIFO置换算法（会产生Belady现象，即物理块越多，缺页率越高）
LRU置换算法：需要硬件支持（寄存器或栈）
Clock置换算法：设置一访问位，访问则置1，当置换时循环检查，如为1则置0，如为0则置换。
改进Clock置换算法：不但考虑使用情况，也考虑置换代价。由访问位A和修改位M共同决定。

请求分段存储管理方式

段表机制：应用程序的一部分调入内存，还有一部分仍在盘上，故须在段表中再增加若干项，供程序(数据)在换进、换出时参考。
缺段中断机构：在一条指令的执行期间，产生和处理中断，以及在一条指令执行期间，可能产生多次缺段中断。但由于分段是信息的逻辑单位，因而不可能出现一条指令被分割在两个分段中和一组信息被分割在两个分段中的情况。
地址变换机构：请求分段系统中的地址变换机构是在分段系统地址变换机构的基础上形成的。因为被访问的段并非全在内存，所以在地址变换时，若发现所要访问的段不在内存，必须先将所缺的段调入内存，并修改段表，然后才能再利用段表进行地址变换。为此，在地址变换机构中又增加了某些功能，如缺段中断的请求及处理等。
分段的共享与保护：
1. 共享段表：为了实现分段共享，可在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项。
2. 共享段的分配：由于共享段是供多个进程所共享的，因此，对共享段的内存分配方法与非共享段的内存分配方法有所不同。
  - 第一个请求使用该共享段进程，由系统为该共享段分配一物理区，再把共享段调入。同时填写共享段表。
  - 其他使用该共享段的进程，在调用进程的段表增加一表项，填写共享段的物理地址；共享段的段表中增加一表项并修改进程计数
3. 共享段的回收：撤销该进程段表中共享段对应的表项；修改进程计数，若为0则系统回收物理内存。
4. 分段保护：
  - 越界检查：段号是否大于段表长度；段内地址是否大于段长
  - 存取控制检查

总结与习题

静态重定位是在作业的(A)中进行的，动态重定位是在作业的(B)中进行的。
静态链接是在(A)中进行的，动态链接是在作业的(B)或©中进行的，且(B)进行链接，可以使内存利用率最高。
对重定位存储管理方式，应(A)，当程序执行时，是(B)与(A)中的©相加得到(D)。

A. (1) 在整个系统中设置一个重定位寄存器 (2) 为每道程序设置 (3) 为每道程序设置两个 (4) 为每个程序段和数据段都设置一个

B, C, D (1) 物理地址 (2) 有效地址 (3) 间接地址 (4) 起始地址
段页式虚拟地址空间是(A)维的。
一个计算机系统的虚拟存储器的最大容量是由(A)确定的，实际容量是由(B)确定的。

A, B (1)计算机字长 (2)内容容量 (3)硬盘容量 (4)内存容量与硬盘容量之和
在请求调页系统中，内存分配有(A)和(B)两种策略，(A)的缺点是可能导致频繁出现缺页中断造成CPU性能下降。

A, B (1) 首次适应 (2) 最佳适应 (3) 固定分配 (4) 可变分配
在虚拟存储器中，采用(A)提高(B)的速度。

A (1) 高速辅助存储器 (2) 高速光盘存储器 (3) 快速通道 (4) 高速缓冲存储器

B (1) 连接编辑 (2) 虚空间分配 (3) 动态地址翻译 (4) 动态链接

答案：

装入过程执行过程 2. A.装入程序之前 B.装入某段程序 C.调用某段程序
A.(1) B.(2) C.(4) D. (1) 4. A.2 5.A.(1) B.(4) 6.A.(3)B.(4) 7.A.(4) B.(3)

第五章设备管理

I/O系统

I/O系统的功能：设备分配与回收、设备启动、设备事件处理、设备缓冲区管理、实现虚拟设备、磁盘调度
外设分类图例
设备的分类：
1. 按设备使用类型分类：存储设备、输入输出设备
2. 按传输速率分类：低速、中速（打印机）、高速（磁盘）设备
3. 按信息交换单位：字符设备、块设备
4. 按共享属性：独占设备、共享设备、虚拟设备
5. 单通路I/O系统、多通路I/O系统

I/O控制方式

程序I/O方式（忙-等待方式）
中断驱动I/O控制方式
直接存储器访问（DMA）I/O控制方式
I/O通道控制方式

缓冲管理

目的：为了解决CPU与I/O设备速度不匹配的矛盾；减少对CPU的中断频率，放宽CPU中断响应时间的限制；提高CPU与I/O设备之间的并行性。
单缓冲：每当用户进程发出一I/O请求时，操作系统便在主存中为之分配一缓冲区，在块设备输入时，从磁盘把一块数据输入到缓冲区，之后操作系统将该缓冲区中的数据传送到用户区。
双缓冲：在设备输入时，先将数据送入第一缓冲区，装满后便转向第二缓冲区。此时操作系统可以从第一缓冲区中移出数据，并送入用户进程。接着由CPU对数据进行计算。
双机通讯时如果仅配置单缓冲，则同一时刻只能单方向数据传输。为实现双向数据传输，必须在两台机器中设置两个缓冲区，一个用来发送，一个用来接受。
循环缓冲的组成
1. 多个缓冲区。在循环缓冲中包括多个缓冲区，其每个缓冲区的大小相同。作为输入的多缓冲区可分为三种类型：用于装输入数据的空缓冲区R、已装满数据的缓冲区G以及计算进程正在使用的现行工作缓冲区C
2. 多个指针。作为输入的缓冲区可设置三个指针：用于指示计算进程下一个可用缓冲区G的指针Nextg、指示输入进程下次可用的空缓冲区R的指针Nexti，以及用于指示计算进程正在使用的缓冲区C的指针Current。
缓冲池
1. 组成：三个缓冲队列：空缓冲队列emq、输入队列inq和输出队列outq；四个工作缓冲区：用于收容输入数据的工作缓冲区hin、用于提取输入数据的工作缓冲区sin、用于收容输出数据的工作缓冲区hout、用于提取输出数据的工作缓冲区sout
2. 收容输入：输入进程需要输入数据时，调用Getbuf(emq)过程，从空缓冲队列emp队首摘下缓冲区作为收容输入工作缓冲区hin,然后输入数据，装满后调用Putbuf(inq, hin)过程，将缓冲区挂载在输入队列inq上。
3. 收容输出、提取输出、提取输入略。

I/O软件

目标：与具体设备无关；统一命名（所有软件都以逻辑名称访问设备）、对错误处理（低层软件能够解决的错误不让高层软件感知）、缓冲技术、设备分配和释放、I/O控制方式（屏蔽DMA等不同I/O控制方式的差异，向高层软件提供统一接口）
I/O软件四个层次：
1. 用户层软件（连接用户层）：实现用户交互接口，可以直接调用库函数（不在操作系统）
2. 设备独立性软件（将具体设备隔离）：应用程序独立于具体使用的物理设备。为了实现设备独立性而引入了逻辑设备（应用程序使用）和物理设备（实际执行使用）这两个概念。
  1. 实现设备独立性的好处：设备分配灵活、易于实现I/O重定向（I/O操作设备可以更还而不必改变应用程序）
  2. 设备独立性软件的主要功能：执行所有设备的公有操作、向用户层（或文件层）软件提供统一接口
  3. 逻辑设备名到物理设备名映射实现：逻辑设备表（LUT），左为系统使用，右为用户使用
3. 设备驱动程序
  1. 主要任务：接受上层软件发来的I/O要求并转化为具体要求，发送给设备控制器，启动设备并执行
  2. 功能：
    1. 接受由设备独立性软件发来的命令和参数，将抽象要求转化为具体要求
    2. 检查用户I/O请求合法性
    3. 发出I/O命令
    4. 及时响应由控制器或通道发来的中断请求
    5. 自动构建通道程序
  3. 设备驱动程序（属于低级的系统例程）的特点：
    1. 驱动程序主要是在请求I/O的进程与设备管理器之间的一个通信、转换程序
    2. 不同类型设备配置不同的驱动程序
    3. 驱动程序与I/O设备采用的I/O控制方式紧密相关
    4. 其中一部分必须用汇编语言书写
  4. 设备驱动程序处理过程
    1. 将抽象要求转换为具体要求
    2. 检查I/O请求的合法性
    3. 读出和检查设备状态
    4. 传递必要参数
    5. 工作方式设置
    6. 启动I/O设备
  - 注：驱动程序发出I/O命令以后，基本I/O操作是在设备控制器控制下完成的，需要一定时间，此时驱动程序将自己阻塞起来，直到中断到来唤醒。
4. 中断处理程序
  1. 处理过程：
    1. 唤醒被阻塞的驱动（程序）进程
    2. 保护被中断进程的CPU环境
      - 硬件自动将被中断进程的CPU现场信息(包括处理机状态字PSW、程序计数器(PC)和所有的CPU寄存器，如通用寄存器、段寄存器等内容)都压入中断栈中
    3. 转入相应设备处理程序
    4. 中断处理
    5. 恢复被中断进程的现场

设备分配

设备分配中的数据结构
1. 系统设备表（SDT，整个系统一张）
2. 设备控制表（DCT，每个设备一张）：记录本设备的情况，除指示设备类型与设备标识字段外，还包括：
  1. 设备队列队首指针：记录请求本设备但未得到满足的进程
  2. 设备状态
  3. 与设备连接的控制器表指针
  4. 重复执行次数（最大传送失败次数）
3. 控制器控制表（COCT，每个控制器一张）
4. 通道控制表（CHCT，每个通道一张）
设备的固有属性
1. 独占性（临界资源）
2. 共享性
3. 可虚拟设备（设备本身是独占设备，经过某种技术处理后改造成虚拟设备）
设备分配算法：先来先服务、优先级高者优先
独占设备的分配程序
1. 分配设备：根据I/O请求中的物理设备名，查找SDT，找出该设备的DCT，根据DCT状态字段，判断是否忙：忙则将进程PCB挂载到设备队列上；不忙则判断安全性。
2. 分配控制器
3. 分配通道
- 改进：欲增加设备独立性，进程使用逻辑设备名请求I/O，这样首先从SDT中找出第一个该类的DCT，若忙则找第二个。
- 改进：采用多通路I/O系统结构。
SPOOLing技术
1. SPOOLing技术可将一台物理I/O设备虚拟为多台逻辑I/O设备，允许多个用户共享一台物理I/O设备。
2. SPOOLing系统三个组成部分
  1. 输入井和输出井：在磁盘上开辟的两个大存储空间。输入井是模拟脱机输入时的磁盘设备，用于暂存I/O设备输入的数据；输出井是模拟脱机输出时的磁盘，用于暂存用户程序的输出数据。
  2. 输入缓冲区和输出缓冲区：缓和CPU和磁盘之间速度不匹配矛盾，在内存中开辟的两个缓冲区。
  3. 输入进程和输出进程：利用两个进程来模拟脱机I/O时的外围控制机。
3. 共享打印机
  1. 打印机是经常要用到的输出设备，属于独占设备。利用SPOOLing技术，可将之改造为一台可供多个用户共享的设备，从而提高设备的利用率，也方便了用户。
  2. 用户进程请求打印输出时，SPOOLing系统同意为它打印输出，但并不真正立即把打印机分配给该用户进程，而只为它做两件事：
    1. 由输出进程在输出井中为之申请一个空闲磁盘块区，并将要打印的数据送入其中；
    2. 输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到请求打印队列上。
    3. 如果还有进程要求打印输出，系统仍可接受该请求，也同样为该进程做上述两件事。
  3. 如果打印机空闲，输出进程将从请求打印队列的队首取出一张请求打印表，根据表中的要求将要打印的数据，从输出井传送到内存缓冲区，再由打印机进行打印。
4. SPOOLing技术的特点
  1. 提高了I/O的速度：从低速I/O设备进行的I/O操作，演变为对输入输出井中的数据存取。
  2. 将独占设备改造为共享设备。
  3. 实现了虚拟设备的功能。

磁盘存储器的管理

磁盘地址转换：三维地址（c 柱面号, h 磁头号, s 扇区号）↔ 一维地址（b 块号）
磁盘的类型：固定头磁盘（每条磁道都有读写头）、移动头磁盘（仅能以串行方式读/写）
磁盘访问时间：
1. 寻道时间 $T_s$ ：约几十毫秒
2. 旋转延迟时间 $T_r$ ：约十几毫秒
3. 数据传输时间 $T_t$ ：约几毫秒
对寻道时间进行优化：
1. FCFS
2. SSTF（每次找最近的）
3. SCAN（不但考虑最近的，还考虑方向）
磁盘高速缓存（一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块）
1. 数据交付方式：先查磁盘高速缓冲器，若未命中则查看磁盘
2. 置换算法：
  1. 考虑因素：访问频率、可预见性、一致性
  2. 对于那些会严重影响到数据一致性的盘块数据和很久都可能不再使用的盘块数据，都放在LRU链的头部，使它们能被优先写回磁盘
3. 周期性写回磁盘：每隔一段时间强制写回磁盘
提高I/O速度的其他方法
1. 提前读：读当前块的同时，还要求将下一个盘块(提前读的块)中的数据也读入缓冲区
2. 延迟写：不立即将该缓冲区A中的数据写入磁盘，而是将它挂在空闲缓冲区队列的末尾
3. 优化物理块分布：先以磁道为单位进行写，连续分配读的快。

习题

第六章文件管理

文件及文件系统

文件的三大特点：可保存、具有标识名、逻辑相关且有完整意义
文件系统：OS中负责处理文件相关事宜的程序和数据结构。
文件的结构
1. 逻辑结构（用户的观点）：连续存储、独立实体
2. 物理结构（实现的观点）：驻存在存储介质上的文件结构，未必连续

逻辑结构

文件逻辑结构的类型
1. 有结构文件（记录文件）：由一个以上的记录类构成的文件。
  - 定长记录，所有记录长度相同，处理方便，但浪费空间
  - 不定长记录：记录长度不相同，节约空间
2. 无结构文件（流式文件）：无需多余的说明信息，长度以字节为单位。
  
  有结构文件：字节—>记录—>文件
  
  无结构文件：字节—>文件
逻辑结构下的文件存取方法：
1. 顺序存取：严格按照文件信息单位排列顺序存取
2. 随机存取：每次操作必须确定存取的位置，对于流式文件或定长记录文件容易确定，不定长不好确定。
3. 按键存取：根据记录关键字的值存取，常用于记录式文件。

物理结构

物理结构：文件在文件存储器中的存储方式
1. 连续结构：文件的全部信息存放在外存的一片连续编号的物理块中，也称连续文件。
  1. 优点：简单，支持顺序、随机存取，速度快，磁盘寻道速度时间最少；
  2. 缺点：不易动态增长，预留空间浪费；不利于文件插入删除；存在外部碎片问题。
2. 串联结构（链接结构）：存放文件信息的每一物理块中有一个指针，指向下一个物理块，这个指针的长度由物理设备的容量决定，通常放在该物理块的开头或结尾。
  1. 优点：提高磁盘空间利用率，不存在外部碎片问题；有利于文件插入删除和动态扩充；
  2. 缺点：存取速度慢，不适合随机存取；指针占用空间；可靠性问题，如指针出错。
3. 索引结构：一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构－索引表，一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块。
  1. 优点：保持链接结构优点，解决了缺点，能顺序和随机存取；
  2. 缺点：索引表本身带来开销。
  3. 多级索引

文件目录管理

目录管理要求：按名存取；提高目录检索速度；文件共享；允许重名（树状结构）。
目录项（文件控制块，FCB）：操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息。所有的目录项就构成了文件目录。
目录结构
1. 单级目录结构
  
  缺点：查找速度慢、不允许重名、不便于文件共享
2. 二级目录：为每一个用户建立单独用户文件目录UFD
  1. 优点：简单，解决重名问题
  2. 缺点：缺乏灵活性，不能反映现实世界多层次关系
3. 多级目录结构（树形目录结构）：由根目录和各级目录组成，为管理上的方便，除根目录外，其它各级目录均以文件的形式组成目录文件。
  
  根目录中的每个目录项可以对应一个目录文件，也可以对应一个数据文件，同样目录文件中的每个目录项可以对应一个目录文件。也可以对应一个数据文件。如此类推，就形成多级目录结构。

文件存储空间管理

解决重要问题：如何为新创建文件分配存储空间。分配方式：连续分配、离散分配
空闲表法：属于连续分配方式，每个文件分配一块连续的存储空间，外存的所有空闲区建立一张空闲表。
空闲链表法
1. 空闲盘块链：每一个空闲物理块上都有一个指针，把所有的空闲块通过该指针链接起来，形成一个链表，文件系统只需记住该链表的首结点指针；分配：从链首摘下空闲块分配；删除：插入末尾
2. 空闲盘区链：把所有的空闲盘区（每个盘区可包含多个盘块）链接起来。
位示图法
- 适合于小磁盘，适合找连续的空间
文件的存取控制
1. 存取控制矩阵
  - 逻辑简单，实现困难，二维矩阵大且验证耗时，可以按行或列分解
2. 存取控制表：把用户分成三类：文件主、同组用户和其它用户，每类用户的存取权限为可读、可写、可执行以及它们的组合；每个文件一张表存放在文件FCB中，列出所有用户对文件的访问权限。大部分系统采用。