操作系统 期末复习（八至十三章）

1-7章

详见期中复习

• [期中复习（一）](https://ichirinko.top/2023/10/20/操作系统 期中复习/)
• [期中复习（二）](https://ichirinko.top/2023/10/22/操作系统 期中复习（二）/)

---

第八章 内存管理

概述

程序需要从磁盘读到内容中，执行进程来运行

内存和寄存器是唯一能直接被CPU访问的

CPU内置寄存器通常在不大于一个CPU时钟周期内完成访问

但内存可能需要多个CPU时钟周期才能完成访问，所以CPU通常需要暂停

高速缓存Cache在CPU寄存器和内存之间

基地址与界限地址

基地址寄存器含有最小的合法的物理内存地址

界限地址寄存器指定范围大小

程序合法访问范围 = 基地址 + 界限地址

逻辑地址空间与物理地址空间

逻辑地址 - CPU生成的地址

物理地址 - 内存单元看到的地址（加载到内存地址寄存器的地址）

从逻辑地址到物理地址的映射由内存管理单元（MMU）的硬件管理设备完成

在一种方案（基地址寄存器）中，内存管理单元被称为重定位寄存器

一个程序在编译时和加载时的地址绑定方法生成相同的逻辑地址和物理地址，但在执行时生成不同的地址，程序只知道逻辑地址，不知道物理地址

动态加载

为了获得更好的内存利用率，一个程序只有在调用时才会加载

Why need 虚拟内存

如果直接使用物理内存，进程切换会造成程序物理内存的破坏

解决方案

交换

通过基址寄存器和界限寄存器生成地址空间，通过交换技术解决

虚拟内存

只将进程的部分调入内存中运行，如果内存已满，需要通过算法将新数据覆盖旧的数据

交换

进程必须在内存中才能运行，但进程可以暂时从内存交换到备份存储，再次执行时再调回到内存

交换可以让所有进程的总的物理地址超过真实系统的物理地址空间，增加了系统的多道程序调用

但是，当进程空间大于内存时，不能使用（因为它是完整地调入内存）

连续内存分配

动态存储分配问题

首次适应分配 first-fit

分配首个足够大的孔

查找可以从头开始，也可以从上次首次适应分配结束时开始，一旦找到足够大的孔就停止

最佳适应分配 best-fit

分配足够小的足够大的孔，产生最小剩余孔

最差适应分配 worst-fit

分配最大的孔，产生最大剩余孔

首次适应和最优适应在执行时间和利用空间方面都好于最差适应首次适应和最优适应在利用空间难分伯仲，但首次适应更快一点

碎片 Fragmentation

内部碎片 Internal Fragmentation

分配给应用的内存大于应用实际需要的内存，这部分称为内部碎片，无法利用

外部碎片 External Fragmentation

首次适应和最优适应都会产生

存储被多个进程分成了很多小的片段，可能可以利用

可以通过紧缩（compaction）来清理外部碎片，它通过移动内存内容使所有的空闲空间合并为一整块

但是，只有重定位是动态的才能使用紧缩，并且，紧缩的性能损耗较为昂贵

分段 segmentation

使用段对逻辑地址空间进行划分，每个段都有段编号与段偏移量

段的逻辑地址

段的逻辑地址由二维有序对构成

$$<段号，偏移量>$$

逻辑地址到物理地址

要通过二维的逻辑地址映射到一维的物理地址，需要段表

段表的结构如下：

$$[(段号)，段界限，基地址]$$

那么，一个逻辑地址作如下转换得到物理地址

$$物理地址 = 段表[逻辑地址.段号].基地址 + 逻辑地址.偏移量$$

如果偏移量大于段表中的界限值，就会触发寻址错误的系统陷阱异常

分段管理能很方便地按照逻辑模块实现信息的共享和保护，但是段长过大会导致为其分配很大的连续空间不方便。并且，段式管理会产生外部碎片

分页 Paging

分页是另外一种内存映射方法

将物理内存分为固定大小的块，称为帧（frame）

将逻辑内存也分为固定大小的块，称为页（page）

逻辑地址空间现在完全独立于物理地址空间

同样的，使用以下格式表示逻辑地址空间：

$$<页码，偏移量>$$

一般来说，逻辑地址空间的大小是2的幂次方，若逻辑地址空间为$2^m$，页大小为$2^n$，那么页码就有m-n位，能表示$2^{m-n}$页,偏移量有n位

页表表示为

$$[页码,页的物理内存基地址]$$

逻辑地址到物理地址

使用以下转换关系

$$物理地址 = 页表[逻辑地址.页码].基地址 + 逻辑地址.偏移量$$

分页管理内存空间利用率高，不会产生外部碎片，只有少量的内部碎片

但是不方便按照逻辑模块实现信息的共享和保护

TLB

TLB就是转换表缓冲区，搜索速度很快。

TLB只包含一定的页表信息，当TLB已满时，如果需要加入新的页表信息，需要使用如LRU，FIFO等置换页面的算法置换不需要的页面

有了TLB，系统访问物理页面的顺序如下

• 首先访问TLB
  • 如果TLB中有这个页表，可以直接访问物理地址
  • 如果没有，称为TLB未命中，需要访问内存中的页表，再通过页表访问物理地址

TLB中找到目标页表的概率称为命中率（hit radio）

由命中率可以计算出有效内存访问时间，计算公式为：

$$T = \alpha * t_{访问物理地址内存} + (1-\alpha)*(t_{访问物理地址内存}+t_{访问页表})$$

解答：分段/分页题目的做法

要求解这类题目，需要得知以下几个关键量：

• 页的大小
• 虚拟内存所占大小
• 物理内存所占大小

其中，页的大小提供了逻辑地址的总位数

有了以上三个信息，可以计算出虚拟内存和物理内存中有多少页，以此确定逻辑地址的页码所占位数，那么

$$总位数 - 页码位数 = 偏移量位数$$

题目中一般还会给出页表，此时就可以依据页表由当前逻辑地址剥离出页码，以此定位物理地址的基址，再加上偏移量就是实际的物理地址了。

当然，此时可能还需要TLB发挥作用。TLB中页表可能缺失页框号，此时需要根据置换算法（FIFO、LRU等），置换出一个页面，此时这个被置换出去的页面的页框号就是新页面所需的页框号。

---

第九章 虚拟内存

虚拟内存可以只让程序的一部分进入内存中，因此逻辑地址空间可能比物理地址空间大得多

这时候，虚拟内存允许多个进程共享同一个物理地址空间，尽管逻辑地址上他们是不相同的

标志位

可以使用一比特的空间表示页表项有无连接至一个实际的物理帧（也就是说这个帧在不在内存中）

通常使用

1 - 在内存中

0 - 不在内存中

当访问不在内存中的页表项时，会引发页面中断

操作系统会试图从存储中读入该帧，如果不存在会中止，否则会耗费一定时间将数据输入内存；

然后，会依据页表是否为满替换部分页面，然后从页面中断处重新开始运行

写时复制 Copy-on-write

当父进程使用fork()时，创建的子进程实际上与父进程共享内存页面。但是，如果其中一方对数据进行写操作，此时操作系统会从空闲的页面池中，按需添零（清除旧内容）一些页面后，将其作为共享页面的副本创建，供写操作的进程使用。此时，两个进程实际上已经在对不同页面进行操作。

页面置换算法

FIFO 先进先出页面置换算法

Optimal 最优页面置换

对未来的序列进行分析，选择最远的页进行替换

问题：执行前不知道后续序列

LRU 最近最少使用页面置换算法

看的是过去，把过去最近最少使用的页面置换

实际上，与FIFO算法的唯一差别就是LRU算法在帧中已有页面到来时，会重置计数器

实现方法

• 为每个页面设置一个计数器，根据计数器选择最早的替换

  问题：计数器计数可能精度不足

• 利用栈管理页面，让栈底作为被替换的页面，被命中的页面移到栈顶

• 使用引用位，利用比特0/1进行标注

二次机会（Clock）页面置换法

引用位和计数器结合使用

如果为1，置换为0，向下移动

如果为0，进行置换

如果到了最后一个页面还没出现0，就重新回到第一张页面继续流程

counting algorithms 计数器算法

有两种：LFU和MFU

LFU为计数器最小的置换，认为刚用的不容易再次使用

MFU为计数器最大的置换，认为刚用的容易再次使用

帧的分配

帧的分配空间可能会跨页

可变分配

• 平均分配

• 为每个进程的大小进行可变的分配

  $$s_i = size\ of\ process\ p_i\\ S=\sum s_i\\ m = total\ number\ of\ frames\\ a_i = allocation\ for\ p_i = \frac{s_i}{S}\times m$$

优先级分配

低优先级的先分配页

全局分配/局部分配

一个进程进行全局分配，就会对自己分配的全部帧进行置换

局部分配就部分置换

抖动 Thrashing

如果一个进程没有足够的页面，会导致页的置换率过高，导致

• 低CPU利用率
• 操作系统认为需要提高多道的道数
• 另外的进程添加到操作系统中

抖动就是一个进程忙于置换页面的结果

抖动发生原因

$\sum size\ of\ locality$ > total memory size

本地大小之和大于总的内存大小

具体的说是因为以下几个步骤造成的连续反应导致的：

• CPU利用率太低，操作系统通过向系统引入新的进程来增加多道程度
• 但是，使用全局置换算法会置换任何页面，也就是说有可能置换现有进程的页面
• 进程需要更多的帧，然而页面被置换，出现缺页错误，需要从其他进程获取帧
• 为此，需要使用调页设备将页面换进换出，此时会将就绪队列清空，等待调页设备，造成CPU利用率降低。
• 连锁反应导致CPU调度程序试图再次增加多道程度，却导致利用率继续下降，出现抖动

消除抖动的方法

• 使用局部置换算法或优先权置换算法，使缺页内存无法向另外进程获取帧

  但仍然会导致不再抖动的进程有效访问时间增加，因为他们要等待页的时间更长了

• 使用工作集（局部性模型）

• 降低多道程度（降低分页次数）

• 安装更多内存（降低分页次数）

• 安装更快的硬盘，或具有多个硬盘的多个控制器

• 为页面获取算法添加预先调页

增加页面大小不一定能够提高CPU利用率，因为如果页面是有序读入的，可以减少页面错误；但也有可能页面顺序随机，此时可能会导致重复页面置换次数增多，导致抖动

第十章 文件系统接口

文件概念

文件操作

• 创建文件
• 写文件
• 读文件
• 重定位
• 删除
• 截断

Open 与 Close

在首次调用文件前，系统调用open()，并添加到打开文件表

请求文件操作时，可从打开文件表获取文件索引，不需要搜索

如果文件不再使用，进程使用close()关闭，并将其索引从打开文件表删除

需要注意的是，create()和delete()是针对关闭文件而不是打开文件操作的

对于多个进程同时打开同一个文件的情况，操作系统采用两级表（每个进程表 - 整个系统表）

进程表负责跟踪一个进程打开的所有文件的使用信息，比如每个文件的当前文件指针和访问权限等等

系统表包含与进程无关的信息，如文件在磁盘上的位置，访问日期与大小。

系统表的工作流程如下

• 如果有进程打开了一个文件，就在系统表中包含该文件的条目

• 如果另一个进程使用open()，只需要在进程打开表增加一个条目，指向系统表的相应条目

  当然，可以使用打开计数，表示多少个进程打开这个文件

  每次open()增加一次，close()减少一次，若为零，则表示不再使用该文件，可以从系统表中删除

访问方法

顺序访问

read next // 指针后移
write next // 指针后移
reset // 重置到文件开始
no read after last write (rewrite)

直接访问

read n // 读取块号为n的块
write n // 写块号为n的块
position to n // 定位到块号为n的块
	read next
	write next
rewrite n
（n = relative block number）

其他访问方法

如索引访问等

目录结构

单级目录

最简单的结构，所有文件包含在同一目录中

两级目录

每个用户有自己的用户文件目录UFD（User File Directory），当一个用户开始活动时，需要先搜索系统的主文件目录，然后通过用户名索引MFD，指向该用户的UFD

• 每个用户只搜索自己的UFD
• 也就是说，不同用户可以有同名文件
• 对同名文件的操作不会影响其他用户的文件
• 通过路径名定位文件

为了能使用系统文件，可以先在UFD中查找文件，没有找到就在包含系统文件的目录下查找，其实就是环境变量

树形目录

• 更有查找效率
• 有分组能力
• 可以通过不同命令进入工作目录（cd，mkdir，rm）
• 删除目录需要先删除目录下的全部文件
• 不能共享文件和目录

无环图目录

允许公共子目录和文件的共享，此时一个共享的目录或文件可同时位于该系统的多个地方

可以使用 **链接（link）**的方式，保存另一文件或子目录的指针

删除文件时，可以通过删除全部的链接来实现，无法解析出文件地址的认为被删除。

另一种方法就是保留文件直到所有引用被删除，这需要建立一张引用列表来记录

缺点：搜索可能浪费时间；避免成环的代价较大

通用图目录

使用垃圾收集方案，决定何时最后引用被删除，可以重新分配磁盘空间。

---

第十一章 文件系统实现

文件系统结构

• 应用程序
• 逻辑文件系统
• 文件组织模块
• 基本文件系统
• I/O控制
• 设备

文件系统实现

磁盘上的文件系统包含以下信息：

• 每个卷的引导控制块

  包含从该卷引导操作系统的所需信息。如果不包含操作系统，这块内容为空。

  它通常为卷的第一块

  UFS中称其为引导块，NTFS称之为分区引导扇区

• 每个卷的卷控制块

  包含卷或分区的详细信息，如块数量，块大小，空闲块指针与数量，空闲的FCB数量和指针

• 每个文件系统的目录结构

• 每个文件的FCB

内存中的文件信息包括：

• 内存中的安装表，包含每个安装卷的有关信息
• 缓存最近访问目录的信息
• 整个系统的打开文件表（包含每个打开文件的FCB的副本）
• 每个进程的打开文件表（包含一个指向整个系统的打开文件表一些条目的指针）

FCB

• 文件权限
• 文件日期
• 文件所有者、组、ACL
• 文件大小
• 文件数据块或指针

文件名不一定是FCB的一部分，因为一旦完成FCB在磁盘上的定位，系统不再使用文件名，但他可以被缓存以提高文件的打开时间

文件分配方法

连续分配 contiguous allocation

文件不能变大

主要用于长期没有变化的东西：cd唱片，图书馆系统（电子书是连续分配的）

链接分配 linked allocation

通过链表解决了连续分配的所有问题

问题是不能直接访问，只能顺序访问，耗时长，效率差；并且，需要开辟额外空间存放指针

索引分配 indexed allocation

通过将索引放到一起（索引块），解决了链接分配无法高效访问的问题

随机读取

多级索引

多级索引能表示的范围取决于文件块与指针块有多大

空闲空间管理

位图/位向量

使用比特位的方式表示是否为空闲块

如果要依据此找到空闲块，对文件为连续分配的非常便利，但是对链接文件不太友好

链表

将所有空闲磁盘块用链表链接，入口保存在磁盘特殊位置上和内存中

组

在第1块空闲块中存储n块空闲块的地址，前n-1块为空块，最后一块包含下n块空闲块的地址

缓冲区

磁盘缓存

页面缓存

统一缓冲区缓存

缓存的目的是高效

第十二章 大容量存储结构

磁盘

概述

磁盘可以看作逻辑块的一维数组，依次映射到扇区。扇区0是最外面柱面的第一个磁道的第一个扇区

按以下顺序映射：

• 磁道内扇区顺序
• 柱面内磁道顺序
• 从外到内的柱面顺序

0道0扇区主要作为引导所在区使用，启动时读取

访问时间

$$T=t_{寻道时间}+t_{旋转延迟}+t_{磁盘带宽}$$

调度算法

FCFS 先来先服务

SSTF 最短寻道时间优先

选择需要最短寻道时间的请求，类似于SJF

可能会出现饥饿问题

SCAN 电梯调度算法

像电梯一样，从左到右，再从右到左来回扫描

可以处理饥饿问题

LOOK 电梯调度算法

像电梯一样，从左到右，再从右到左来回扫描

但是，边界选择当前存在的请求位置

可以处理饥饿问题

C-SCAN 循环电梯算法

像卷轴一样头尾扫描

C-LOOK算法

不是从头尾扫描，而是选择最靠近头尾的地址作为传送点

物理实现上比C-SCAN更难，但时间更短

一般的，选择SSTF或LOOK算法

---

磁盘管理 Disk Management

低级格式化 Low-level formatting

也叫做物理格式化，将磁盘分成扇区，以便磁盘控制器能够读写

引导块

引导程序存储在ROM中

簇

为了提高效率，操作系统可以将块组合在一起称为簇

磁盘I/O按块完成，文件系统I/O按簇完成，确保I/O具有更多的顺序访问和更少的随机访问

交换空间

采用磁盘空间作为内存的扩展

使用交换空间显著降低系统性能，它的设计目标是为虚拟内存提供最佳吞吐量

交换空间的位置

• 普通文件系统上
• 单独的磁盘分区
• 在单独的原始分区

RAID 磁盘冗余阵列

平均无故障时间越长，可靠性越高

---

第13章 I/O系统

轮询

一直读取状态寄存器，直到忙位被清除

中断

比轮询效率更高的是中断，采用中断向量表示一个地址，可以依据此从集合中选择一个特定的中断处理程序

直接内存访问 DMA

在CPU内存总线和PCI总线之间加入DMA控制器，加快传输速度

设备接口

块设备接口

磁盘等存储设备

字符流接口

键盘、鼠标、modem、打印机、声卡

假脱机 spool

如打印机，不能切换进程打印，可以把文本放在文件里，让系统调用文件打印，对用户看似脱机，实际上没有脱机，称为假脱机

保存设备输出的缓冲区，避免接受交叉的数据流

缓冲区

• 处理数据流的生产者和消费者之间的速度不匹配
• 协调传输大小不一数据的设备
• 支持应用程序I/O的复制语义

缓存

是保存数据副本的高速内存区域

与缓冲的区别：

• 缓冲可以保存数据项的唯一的现有副本
• 缓存只是提供了一个位于其他地方的数据项的更快存储副本