计算机操作系统（叁）

本文章是关于计算机操作系统的学习笔记，笔记主要来自王道的操作系统课程，总共有五个章节：

• 第一章：计算机操作系统（壹）
• 第二章：计算机操作系统（贰）
• 第三章：计算机操作系统（叁）
• 第四章：计算机操作系统（肆）
• 第五章：计算机操作系统（伍）

一、内存基础知识

1、内存

内存：可以存放数据，程序运行前需要先放到内存中才能被CPU处理。

内存地址：为了找到数据在什么地方，需要给内存的存储单元编址。

存储单元：内存中分为很多个小房间，每个小房间就是一个存储单元。每个地址对应一个存储单元。

按字节编址：每个存储单元大小为1字节

按字编址：则根据计算机字长来判断存储单元大小（如32位计算机，存储单元为4字节）

2、进程运行的基本原理

指令的工作原理：指令通常由**操作码+若干参数（可能包含地址参数）**组成

逻辑地址 VS 物理地址：逻辑地址就是相对地址，而物理地址就是绝对地址，是真正在内存的地址

从写程序到程序运行

① 编辑源代码

② 编译，生成目标模块

③ 链接，生成装入模块

④ 装入，将装入模块装入内存，形成物理地址

三种链接方式

静态链接（在程序运行前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件）

装入时动态链接（将各目标模块装入内存时，边装入边链接的链接方式）

运行时动态链接（在程序执行中需要该模块时，才对它进行链接，其优点时便于修改和更新。）

三种装入方式

绝对装入（在编译的时候就知道程序放在内存的哪个位置）

静态重定位（装入内存时将逻辑地址转表为物理地址）

动态重定位（把地址转化推迟到程序真正要执行时才进行，需设置重定位寄存器）

二、内存管理基本概念

1、内存管理

操作系统作为系统资源的管理者，需要对内存进行管理，需要管理的内容如下；

• 内存空间的分配与回收 （第五节及后续章节）
• 内存空间的扩充 （第四节）
• 地址转换 （第一节）
• 内存保护 （这节简单讲）

2、内存空间的分配与回收

操作系统需要分配内存空间给进程，并且还要记录内存区域的状况，进程运行结束后还要进行内存回收

两种方式：

• 连续分配管理方式 （第五、六节）
• 非连续分配管理方式 （第七节）

3、内存空间的扩充

操作系统需要提供某种技术从逻辑上对内存空间进行扩充（内存的虚拟性）

三种技术：

• 覆盖技术

• 交换技术

• 虚拟存储技术

4、地址转换

操作系统需要提供地址转换功能，负责程序的逻辑地址和物理地址转换

三种方式：（就是上面一节讲的）

• 绝对装入

• 可重定位装入

• 动态运行时装入

5、内存保护

操作系统需要提供内存保护功能，保证各进程在各自存储空间内运行，互补干扰

两种方式：

• 设置上下限寄存器
• 采用重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）

三、进程的地址映像

下图展示了进程中各个代码存储的区域：

四、覆盖与交换

接下来学习内存空间扩充的两个技术：覆盖与交换

1、覆盖技术

将程序分为多个段，内存分为一个”固定区“和若干个”覆盖区“，需要常驻的放在”固定区“，调入后就不再调出，不常用的段放在”覆盖区“，需要用到时调入内存，用不到时调出内存

特点：必须由程序员声明覆盖结构，操作系统完成自动覆盖。缺点是对用户不透明，增加了用户编程的负担

2、交换技术

内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存。

磁盘分为“文件区”和”对换区“，换出的进程被放在“对换区”。

换出的进程会进入挂起状态，对应PCB会加入挂起队列（PCB会常驻内存，不会被换出）

3、两者区别

覆盖：在同一个程序或进程中

交换：不同进程（或作业）之间的

五、连续分配管理方式

1、概念

接下来学习内存空间的分配与回收的连续分配管理方式：

连续分配：指为用户进程分配的必须是一个连续的内存空间

该方式又分为三种方式：单一连续分配、固定分区分配、动态分区分配

2、单一连续分配

内存被分配为系统区和用户区，系统区在低地址，用户区是一个用户独享。内存中只能由一道用户程序，用户程序独占整个用户区空间。

优点：实现简单，无外部碎片

缺点：只能用于单用户单任务操作系统，而且有内部碎片

3、固定分区分配

将用户区分割为若干固定分区给各道程序，每个分区只装一道作业，分割策略有分区大小相等和分区大小不相等，可以建立一个分区说明表来管理各个分区

优点：实现简单，无外部碎片

缺点：当用户程序太大时，所有分区都不能满足需求，则不得不用覆盖技术解决，降低性能；而且会产生内部碎片，内存利用率低

4、动态分区分配

可变分区分配，不预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。内存回收时，如果相邻有空闲分区，则合并。

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

两种管理空闲分区的数据结构：空闲分区表、空闲分区链

将新作业装入内存中时，要按照一定的动态分区分配算法，从空闲分区中选一个分配给该作业。

5、内部碎片和外部碎片

内部碎片：分配给某进程的内存区域中，有些部分没有用上

外部碎片：是指内存中的某些空闲分区由于太小而难以利用（如果有外部碎片，可以采用紧凑技术）

六、动态分区分配算法

在动态分区分配方式中，当有很多个空闲分区都能满足需求时，选择哪个分区进行分配就是该算法的作用。

常见的算法有如下四种：

1、首次适应算法（First Fit)

算法思想：每次从低地址开始查找，找到第一个能满足大小的空闲分区

2、最佳适应算法(Best Fit)

算法思想：为了保证“大进程”到来时能有连续的大片区域，可以尽可能留下大片的空闲区，优先使用更小的空闲区。

空闲分区按容量递增次序排序，分配内存时顺序查找空闲分区链，找到第一个能满足大小的空闲分区

缺点：会留下小碎片，算法开销大（需要重新排序）

3、最坏适应算法(Worst Fit)

算法思想：和最佳适应算法相反，按容量递减次序排列，每次尽可能用大的分区

缺点：大分区容易被用完，算法开销大（需要重新排序）

4、邻近适应算法(Next Fit)

算法思想：由首次适应算法演变，每次从上次查找结束的位置开始检索

缺点：会使高地址大分区也被用完

七、基本分页存储管理

接下来学习内存空间的分配与回收的非连续分配管理方式中的基本分页存储管理。

1、概念

非连续分配：为用户进程分配分散的内存空间

页框：将内存空间分成大小相等的分区，每个分区就是一个“页框”（页帧、内存块、物理块、物理页面）

页框号：每个页框有一个编号，就是“页框号”（页帧号、内存块号、物理块号、物理页号，块号）

页面：进程的逻辑地址空间划分为与页框大小相等的分区，每个分区就是“页”（页面）

页号：每个页面有一个编号，就是“页号”，页号从0开始

页表：记录页号和块号的对应关系，通常存储在PCB中。

页表项：页表中每个对应关系就是一个页表项，一个页表项由页号和块号组成。其中页号是隐含的，不用存储（就类似数组的下标）

下图展示了上述各个概念的关系，一个进程对应一个页表，每个页进程的逻辑地址通过页表转换成真实的物理地址：

重点注意这些概念的区别（还有别名）：页面VS页框、页号VS页框号。

计算机中用2的整数倍表示页面的大小

2、计算

（1）每个页表项占多少个字节

下图中，内存大小为4GB，页面大小为4KB，那么内存块数量为4GB/4KB = 2^{20}个，则至少需要20bit来表示物理块号，而一个字节有8bit，因此3个字节就可以装下了，即每个页表项占3B。这里页号不必存储，因此不占空间（类比数组下标）

（2）地址转换

进程的各个页面虽然是离散存放的，但是页面内部是连续存放的，因此想要访问逻辑地址A，只需要：

• 确定逻辑地址A对应的页号P，和页内偏移量W
• 通过页表找到页号P对应的内存起始地址
• 逻辑地址A对应物理地址 = P号页面在内存的起始地址 + 页内偏移量W

假设逻辑地址空间大小200B，页面大小50B，则逻辑地址可以被划分成4个页面，每个页面50B。求逻辑地址110对应的页号和页内偏移量：

页号 = 110 / 50 = 2，页内偏移量 = 110 % 50 = 10

如果还有页表，那么将页号映射成对应物理号即可。

公式如下：

页号 = 逻辑地址 / 页面长度（整数部分）

页内偏移量 = 逻辑地址 \% 页面长度（余数部分）

如果页面大小是2的整数幂，那么就可以将地址的二进制位划分为两个部分，这样很方便的可以转换地址：页内偏移量部分不变，修改页号部分为映射的物理号即可：

如果不是2的整数次幂，只能用公式计算了，但绝大部分题目都是2的整数幂的。

八、基本地址变换机构

1、基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。

通常会有一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M，进程未执行时，页表的起始地址和页表的长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放在页表寄存器中。

地址变换流程如下：

① 计算页号P和页内偏移量W

② 比较页号P和页表长度M，若P >= M，则发生越界中断（页表范围[0,M-1]），否则继续执行

③ 计算页号P对应的页表项地址 = 页表起始地址F + 页号P × 页表项大小（块号大小）。取出该地址的内容b，即内存块号。

④ 若页面大小为L，则访问的目标地址E = b × L + W，当然计算机只需要拼接b和W的二进制形式即可。

上述过程中，查询页表和访问目标物理地址，共访问2次内存，而在下一节中，我们会尝试减少访问内存的次数，加快访问的流程。

2、对页表项大小的探讨

我们知道，页表是存在内存当中的，假设此时每个页面大小为4KB，即物理块大小为4KB，并且假设每个页表项只需要3字节就可以表示所有块号。那么一个物理块就可以存储4096 / 3 = 1365个页表项，但最终会留下4096 % 3 = 1B的页内碎片。此时这个物理块装不下一个页表项了，只能从下一个物理块开始装。这样每个页表项之间就不能保证都连续了，处理时必须经过复杂的计算。

因此，为了方便页表的查询，实际运用中一般都会让一个页表项占更多字节，让每个页面刚好能够装下整数个页表项，比如页表项大小增大到4B，这样就不会有页内碎片了。

九、具有快表的地址变换机构

1、快表

快表又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓冲存储器，用来存放最近访问的页表项副本，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

2、引入快表后的流程：（很像Cache）

① 计算页号P和页内偏移量W，检查是否越界中断，否则继续执行

② 匹配页号与快表中的页号，如果命中，则直接从快表中取出对应的内存块号，然后计算出对应物理地址并访问，这样只需一次访存

③ 如果未命中，则只能访问内存中的页表进行查找，访问时，还会把访问的页表项存入快表（如果满了则按照一定算法进行替换），这样需要两次访存

只要命中，就可以减少访存次数，节省很多时间，根据局部性原理，一般快表命中率可达90%以上

3、局部性原理

时间局部性：访问某个变量后，在不久的将来还会被访问（如程序中的循环）

空间局部性：程序访问了某个存储单元，不久之后，其附近的存储单元也很有可能被访问（如数组的数据在内存中连续存放）

由于局部性原理，可能连续多次查到的都是同一个页表项，因此命中率很高。

4、TLB与Cache区别

TLB只有页表项副本，而普通Cache可能会有其他各种数据副本

十、两级页表

1、单级页表的问题

① 所有页表项必须连续存放，页表过大时需要很大的连续空间

② 在一段时间内并非所有页面都用得到，因此没必要让整个页表常驻内存。

解决问题①需要二级页表，解决问题②则需要在完成二级页表的基础上，利用虚拟存储技术，需要访问时才调入内存，否则放在外存。

假设有32位逻辑地址空间，页表项大小为4B，页面大小为4KB（页内地址12位），那么就有剩下20位用于存储页号。那么内存中存储这个页表就需要2^{20}×4B=2^{22}B个存储空间，即需要2^{10}个页表框存储，而这么大的连续内存空间比较难分配，因此需要引入两级页表。

2、两级页表的原理、逻辑地址结构

按照之前的情形，单级页表中，一共有2^{20}个页表项要存储，而存储这些页表项要1024个连续的页表框。

这里我们其实可以用页表的思想，将这2^{20}个页表项分成组，每个组刚好可以塞进一个页表框中，比如1024个页表项作为一组。这样就可以将整个页表分成1024个组，每组叫做一个二级页表，各个二级页表可以分散存储在内存中。为了找到这些二级页表在内存中的位置，我们再引入一个页表，叫做页目录表（顶级页表、外层页表），通过页目录表可以找到各个二级页表的物理地址。

此时想要查找某个页号对应的块号，需要经过两步：先再页目录表中找到二级页表的位置，再从二级页表中找到对应的块号。

其实一句话来说就是：把整个班级（所有页表项组成的集合）分成各个小组，查找时先从组表（页目录表）里找小组（二级页表），再从小组里找人（块号）。

二级页表的结构如下图所示：

二级页表的逻辑地址结构如下图所示：

3、地址变换

① 按照地址结构将逻辑地址拆分成三部分

② 从PCB中读出页目录表始址，根据一级页号查页目录表，找到二级页表在内存中的存放位置

③ 根据二级页号查二级页表，找到最终想访问的内存块号

④ 根据页内偏移找到内存块中的实际物理位置

4、需要注意的几个细节

① 多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级

② 多级页表的访问次数（假设没有快表结构）—— N级页表访问一个逻辑地址需要N+1次访存

十一、基本分段存储管理

1、概念

将进程的地址空间，按照程序自身的逻辑关系划分为若干个段，每个段有一个段名，每段从0开始编址。

内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各个段之间可以不相邻。

2、分段存储的逻辑地址结构

段号的位数决定了每个进程最多可以分几个段，段内地址位数决定了每个段的最大长度是多少

3、段表

和页表一样，段表实现了逻辑地址到物理地址的转换。不同的是，每段长度是不一样的，因此段表还记录了段长。

每个段对应一个段表项，每个段表项长度是相同的，并且段号可以隐含，不占存储空间。

4、如何实现地址变换

和分页存储的地址变换机构几乎一样，唯一不同的是，由于记录了段长，分段存储方式还需要再判断一下段内地址是否越界。

当然，分段存储也可以引入快表。

5、分段、分页管理的对比

分页：信息的物理单位，对用户不可见，地址是一维的，访存两次

分段：信息的逻辑单位，对用户可见，地址是二维的，访存两次

分段比分页更容易实现信息的共享和保护（不能被修改的代码称为纯代码和可重入代码，不属于临界资源，可被共享）

十二、段页式存储管理

段页式存储其实就是把分段和分页存储结合起来了，先分段，每一段再分页，类似二级页表。

段页式存储的逻辑地址结构如下：

其实就是把段内地址分成了各个页，用一部分二进制代表页号，剩余代表页内偏移量

段页式访问一个逻辑地址需要访存3次，第1次查段表，第2次查页表，最后一次访问目标单元

十三、虚拟内存的基本概念

1、传统存储管理方式的缺点

传统的存储管理，即连续分配和非连续分配管理，这种管理方式作业必须一次性全部装入内存后才开始运行，当内存不足以装下一整个作业时，作业则无法运行；而且一旦作业被装入内存，就会一直驻留在内存中，内存利用率不高。

2、局部性原理

之前快表那章提到过，局部性分为时间局部性和空间局部性，即程序执行时，会倾向于访问近期访问过的地址附近的数据或指令。

高速缓存技术：频繁使用的数据放到更高速的存储器中

3、虚拟内存的定义和特征

定义：

① 基于局部性原理，让程序中很快会用的的部分装入内存，其余用不到的放在外存

② 访问的信息不在内存时，有操作系统将其从外存调入内存

③ 内存不足时，由操作系统负责将内存中暂时用不到的信息换到外存

特征：

① 多次性：无需一次性全部装入内存，允许多次调入内存

② 对换性：作业运行时无需一直常驻内存，而是允许作业运行过程中，将作业换入换出

③ 虚拟性：逻辑上扩充了内存容量，让用户看到远大于实际容量的内存容量

4、如何实现

在非连续分配存储管理方式的基础上，操作系统提供请求调页（请求调段）功能和页面置换（段置换）功能。

十四、请求分页管理方式

1、页表机制

请求分页管理相比基本分页存储管理的页表多了几个信息，如下图所示：

2、缺页中断机构

缺页中断：若访问的页面不在内存中（状态位为0），则产生一个缺页中断，缺页进程阻塞，进入阻塞队列，调页完成后唤醒，翻入就绪队列。由于缺页中断时由当前指令访问页面不在内存产生的，因此时内中断。

如果缺页时内存有空闲块，则分配给该进程一个空闲块，并修改页表的对应页表项。

如果没有空闲块，则由页面置换算法选择一个页面进行淘汰。若被淘汰的页面在内存期间修改过，还要写回外存。

3、地址变换机构

和基本分页的地址变换机构类似。不同的是如果找到对应的页表项后，若页面不在内存，则产生缺页中断。引入快表后，若页面被调到外存，则快表里的记录也要删除，即快表记录的页面一定在内存中。

十五、页面置换算法

页面换入换出需要磁盘I/O，开销较大，因此好的页面置换算法应该追求更少的缺页率
缺页率 = 缺页次数 / 访问页面次数

1、最佳置换算法（OPT）

每次淘汰以后永不使用，或长时间内不再被访问的页面。该算法的前提是我们已经知道后续会访问的页面序列，因此实际上最佳置换算法是无法实现的，是理想化的算法（性能最好） 。

每次置换时，从当前访问的页面依次往后查找，最后访问的页面被淘汰（即距离最远的）。

2、先进先出算法（FIFO）

每次淘汰最找进入内存的页面。每次置换时，选择内存块中最找进入内存的页面进行淘汰。

只有FIFO算法会产生Belady异常，实现简单但算法性能差。

Belady异常：当为进程分配的物理块增大时，缺页次数不减反增的异常现象

3、最近最久未使用算法（LRU）

每次淘汰最近最久未使用的页面。该算法需要赋予每个页面一个访问字段，记录了该页面上次访问以来经历的时间t。每次访问页面时都会更新访问时间，每次淘汰页面时，选择t值最大的进行淘汰。

每次置换时，往前看，距离最远的就是最近最久未访问的页面，进行淘汰。

该算法性能好，但需要专门硬件支持，实现困难、开销大。

4、时钟置换算法（CLOCK）

该算法也可以称为最近未使用算法（NRU）。

该算法需要赋予每个页面一个访问位，为1代表最近访问过，0则代表最近没有访问过。内存页面都通过链接指针链接成一个循环队列。某页被访问时，访问位设为1。当要淘汰页面时，从队首循环遍历页的访问位，如果为1，则设为0；如果是0，则淘汰。

这个访问位就类似倒计时，而且指针在循环队列里遍历（循环队列想象成一个圈）时，像时钟的指针转动。

若第一轮扫描发现都是1，那么所有页面访问位会设为0，并且再扫描一遍，此时肯定有0，可以置换了。因此简单的CLOCK算法最多只需要经过两轮扫描就可以淘汰页面。

5、改进型时钟置换算法

实际上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存，只有被淘汰的页面被修改过才需要写回外存。因此，在其他条件都相同时，应该优先淘汰没有没修改过的页面。

改进算法可以增加一个修改位，为1代表修改过，为0代表没有修改过。用**(访问位,修改位)**表示页面状态

访问时，第一轮先扫描(0,0)的，如果没有，再扫描(0,1)的。由于第两轮会将访问位设为0，因此当前如果没找到，再经过两轮，即再查找(0,0)和(0,1)，就一定能找到淘汰的。因此该算法最多进行四轮扫描。

十六、页面分配策略

1、驻留集

指请求分页存储管理中给进程分配的物理块的集合

2、页面分配

固定分配：进程运行期间驻留集大小不变

可变分配：进程运行期间驻留集大小可变

局部置换：发生缺页时只能选进程自己的物理块进行置换

全局变换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有物理块换到外存，再分配给缺页进程

3、置换策略

• 固定分配局部替换：驻留集大小不可改变，缺页时只能选择进程在内存中的一个页面进行置换
• 可变分配全局替换：可以将操作系统保留的空闲物理块分配给缺页进程，只要某进程发生缺页，就可以获得新的物理块；若没有空闲的物理块，则可以选择一个未锁定的页面换出内存（锁定的页面代表页面的内容不能换出外存，如内核数据）
• 可变分配局部替换：缺页时只能选择进程在内存中的一个页面进行置换，但是若发现运行中频繁缺页，则会为进程多分配部分物理块；若缺页率很低，则会回收部分物理块。

可变分配全局替换：只要缺页就分配新物理块

可变分配局部替换：根据缺页率动态增加或减少物理块

4、调入页面的时机

预调页策略：一次调用若干个相邻页面，运行前调入

请求调页策略：运行时动态调页，缺页时再调入

5、从何处调页

外存分为对换区和文件区

• 对换区：读写快，采用连续分配方式

• 文件区：读写慢，采用离散分配方式

对换区足够大：运行时将数据从文件区复制到对换区，之后页面调入调出都发生在内存与对换区

对换区不够大：不会修改的数据每次都从文件区调入，会修改的数据调出调入发生在对换区

UNIX方式：第一次使用的页面从文件区调入，之后调出时写回对换区，使用时从对换区调入

6、抖动（颠簸）现象

刚刚换出的又要换入，刚刚换入的又要换出，主要原因是物理块不够

7、工作集

指在某段时间间隔里，进程实际访问页面的集合。驻留集大小不能小于工作集大小

十七、内存映射文件

1、传统文件访问方式：

① open系统调用——打开文件

② seek系统调用——将读写指针移到某个位置

③ read系统调用——从读写指针所指位置读入数据，从磁盘读入内存

④ write系统调用——根据读写指针确定写回位置，将内存的指定数据写回磁盘

2、内存映射文件访问方式：

① open系统调用——打开文件

② mmap系统调用——将文件映射到进程的虚拟地址空间

③ 操作时，只需要以访问内存的方式访问文件数据，文件数据的读入写出由操作系统完成，并且关闭文件时，操作系统会自动将文件被修改的数据写回磁盘

3、对比

可以发现传统的方式很繁琐，而有了内存映射文件，程序员编程更简单，只需要按访问内存的方式读写即可，其他操作比如读入/写出操作，IO效率优化都由操作系统完成。

4、内存映射文件特性：

• 进程可使用系统调用，将文件映射到进程虚拟地址空间
• 以访问内存的方式读写文件
• 进程关闭文件时，操作系统自动将文件数据写回磁盘，接触内存映射
• 多个进程可以映射同一个文件，方便共享