本系列文章为408考研操作系统知识点整理仅涉及到一些重要的考研知识点并不是完全系统全面的知识，参考书目和视频资料：汤小丹 计算机操作系统（第四版），操作系统考研复习指导，B站王道考研操作系统视频课。

3.1.1 内存管理的基本原理和要求

基本概念

内存：内存又称之为主存。是一种硬件设备，作为CPU和硬盘的缓冲区，用于解决其速度不匹配的问题，提高整机性能。程序执行前需要放入内存才能运行

内存地址：为了标识数据在内存中的存放位置，我们可以为内存编写地址，内存内地址从0开始，每一个地址对应一个存储单元

逻辑地址：程序员视角中看到的地址
物理地址：数据在主存中真实的地址

程序运行基本原理

创建进程首先要将程序和数据装入内存，一般需要以下几个步骤
编译：由编译程序将用户源代码编译成为若干目标模块
链接：由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起，形成一个完整的装入模块
装入：由装入程序将装入模块装入内存运行

其中程序的链接有如下三种方式
静态链接：在程序运行开始之前，先将各目标模块及他们所需要的库函数链接成一个完整的可执行的程序，以后不再拆开
动态链接：将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式
运行时动态链接：对于某些模块的链接，是在程序执行中需要该目标模块时才进行的。其优点是便于修改和更新，便于实现对目标模块的共享

然后装入模块在装入内存时有如下三种方式
绝对装入：在编译时，若知道程序将驻留在内存的某个位置，则编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。由于程序中的逻辑地址与实际内存地址完全相同，因比不需对程序和数据的地址进行修改。绝对装入方式只适用于单道程序环境。另外，程序中所用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。而通常情况下在程序中采用的是符号地址，编译或汇编时再转换为绝对地址。
可重定位装入：在多道程序环境下，多个目标模块的起始地位通常都是从0开始的，程序中其他地址都是相对于起始地址的，然后根据内存的情况，将装入模块装入内存的适当位置。装入时对目标程序中指令和数据的修改过程称之为重定位（由于地址变化通常是在装入时一次完成的，所以又称之为静态重定位)。
动态运行时装入：也称之为动态重定位。程序在内存中发生移动时，需要采用动态方式。装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转化为绝对地址，而是把这种地址转换推迟到程序真正要开始执行时才进行。因此，装入内存后的所有地址均为相对地址

内存保护

所谓内存保护，就是保证个各个进程在各自的存储空间内运行，互不干扰

实现内存保护的方法
方法一：在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令在访问地址时，CPU进行越界检查。

方法二：采用重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址；界地址寄存器存放的是进程的最大逻辑地址。内存管理机构动态地将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元。

实现内存保护需要重定位寄存器和界地址寄存器，因此要注意两者的区别。重定位寄存器是用来“加”的，逻辑地址加上重定位寄存器中的值就能得到物理地址；界地址寄存器是用来“比”的，通过比较界地址寄存器中的值与逻辑地址的值来判断是否越界。
加载重定位寄存器和界地址寄存器时必须使用特权指令，只有操作系统内核才可以加载这两个存储器。这种方案允许操作系统内核修改这两个寄存器的值，而不允许用户程序修改。

3.1.2 连续分配管理方式

单一连续分配

单一连续分配：内存被分为系统区和用户区。系统区位于内存低地址处，用于存放操作系统相关数据：用户区位于内存高地址处，用于存放用户进程相关数据。并且内存中仅有一道用户程序，用户程序独占整个用户区空间。

优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护
缺点：只能用于单用户、单任务的操作系统；有内部碎片；存储器利用率低

固定分区分配

固定分区分配：为了能在内存中装入多道程序，且保证这些程序间互不干扰。所以将整个用户空间划分为若干固定大小的分区，在每个分区中只装入一道作业
优点：实现简单，无外部碎片
缺点：当用户程序太大时，可能所有分区都无法满足，因此不得不采用覆盖解决，但是又会降低性能；会产生内部碎片内存利用率低

划分分区时有两种不同的方法：
分区大小相等：用于一台计算机控制多个相同的场合，缺乏灵活性
分区大小不等：划分为多个较小的区分、适量的中等分区和少量大分区。增加了灵活性，可以满足不同大小的进程需求

动态分区分配

动态分区分配：又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，因此系统分区的大小和数目是可变的。

空闲分区表：每个空闲分区对应一个表项；表项包含分区号、分区大小、分区起始地址等信息

空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可以记录分区大小等信息

动态分区分配算法：用于研究当很多个空闲分区都能满足需求时，应该选择哪个分区分配的问题。其实这个问题需要参照的动态分区分配算法，共有如下四种：
首次适应算法(First Fit)
最佳适应算法(Best Fit)
最坏适应算法(Vorst Fit)
邻近适应算法(Next Fit)

首次适应算法(First Fit)

算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区
具体操作：空闲分区以地址递增的次序排列，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区

缺点：每次都从链头开始查找，可能导致低地址培部分出现很多小的空闲区，而每次分配查找时，又需要经过这些分区，所以增加了查找的开销
优点：这种每次都需要从头查找的规侧，也决定了当低地址部分有更小的分区可以满足时，会更有可能用到小分区，而把大分区保留下来。也就是它隐含了最佳适应算法的优点

最佳适应算法(Best Fit)

算法思想：为了保证当大进程到来时能有连续的大片空间，所以可以优先使用更小的空闲区
具体操作：空闲分区按容量递增次序链接，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区，此时这个分区能满足要求目最小

缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。会产生很多外部碎片

最坏适应算法(Vorst Fit)

算法思想：为了解决Best Fit算法带来的外部碎片问题，可以在每次分配时优先使用最大连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用
具体操作：空闲分区按容量递减次序链接，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区

缺点：每次都选最大的分区进行分配，会导致较大的连续空闲区被快速用完，之后的大进程可能就没有空间了

邻近适应算法(Next Fit)

算法思想：基于First Fit算法，如果每次都从上次查找结束位置开始检索，就能解决First Fit算法的缺点
具体操作：空闲分区以地址递增的次序排列（可以排成一个循环链表），每次分配内存时从上次查找结束位置开始查找空闲分区链（或空闲分区表)，找到大小能满足要求的第一个空闲分区

缺点：无论低地址、高地址他们被使用的概率是相同的。这样就导致了高地址部分的大分区可能会被划分为小分区，最终又导致了无分区可用。也就是说它隐含了最佳适应算法的缺点。

动态分区分配没有内部碎片，但有外部碎片，要解决外部碎片，可以使用拼凑(Compaction)技术解决
内部碎片：分配给某进程的内存区域中，有些部分没有用上
外部碎片：指的是内存中某些空闲分区由于太小而难以利用

3.1.3 基本分页存储管理（内部碎片）

分页管理不会产生外部碎片，会产生内部碎片

分页存储的几个基本概念

页框：在计算机组成原理中我们说过，内存是按照块进行管理的，每个块的编号称之为块号。而在操作系统中需要换一种说法，称其为页框（页帧内存块），每个页框有一个编号，叫做页框号，页框号从0开始
页：对于用户进程，以页框为单位进行划分，称其为页（页面），每个页面也有一个编号，称其为页号，页号从0开始

操作系统以页框为单位为各个进程分配内存空间，进程的每个页面分别放入一个页框中，也即它们是一一对应的关系。各个页面不必连续存放，也不必遵循先后顺序，可以放到不相邻的各个页框中

分页地址转换

分页地址转换：可以把进程中所有的页看作一个个连续存放的模块，当页面分配到页框中后，虽然页面彼此之间是分散的，但是每个页面之内却是连续的。因此如果知道一个模块（一个页）的起始地址，并且知道某逻辑地址相对于该起始地址的偏移量，那么物理地址自然很容易得到。关键分为以下几步
1.要算出逻辑地址对应的页号
2.要算出某逻辑地址在页面内的偏移量
3.要知道该页号对应页面在内存中的起始地址
4.物理地址=页面的起始地址+偏移量

逻辑地址结构

分页存储管理逻辑地址结构：前一部分为页号，后一部分为页内偏移量
如果用k位表示页内偏移量，那么说明该系统一个页面的大小为2k个内存单元
如果用m位表示页号，那么说明该系统中一个进程最多允许有2m个页面

页表

页表：为了能获得每个页面在内存中存放的位置，操作系统会为每个进程建立一张页表。具体来说：
一个进程对应一张页表
进程的每一页对应一个页表项
每个页表项由页号和块号组成
页表记录进程页面和实际存放的内存块之间的对应关系

地址变换结构

地址变换结构：地址变换机构可以借助进程的页表将逻辑地址转化为物理地址。通常会在系统中设置一个页表寄存器(PTR),它存放了页表在内存中的起始地址F和页表长度M
进程未在执行时，页表的起始地址和页表长度存放在PCB中，当进程被调度时，系统内核会把它们放到PTR中

快表

快表(TLB):这是一种访问速度快于内存的高速缓冲器，用来存放当前访问的若干页表项，以加速地址变化过程。与之对应，内存中的页表就称之为慢表。引入快表后，地址变换过程如下
CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较
如果找到匹配的页号，说明要访问的页表在快表中有副本，则直接从中取出该页对应的内存块号，再将其与页内偏移量拼接形成物理地址访存；因此如果快表命中，则访问某个逻辑地址仅需一次访存即可
如果没有找到匹配的页号，则需要问内存中的页表，找到对应的页表项，得到页面存放的内存块号，再将其与页内偏移量拼接形成物理地址访存；因此，若快表未命中，则问某个逻辑地址需要两次访存
注意：如果快表未命中，在页表中找到页表项后，基于局部性原理，应同时将其存入快表，以便后面可能再次访问；同时如果页表已满，则必须按照一定的算法对旧的页表项进行替换（页面置换算法）

两级页表

原理：单级页表其最大的问题就在于存储了很多无用的页表项，并且查询页表时也是无脑式地顺序查询。如果不采用单级页表，那么我们可以像引入分页管理一样，为页表分页，从而形成多张页表，查询时我们还需要一张索引表来告诉系统第几张页表应该上哪里去找，这样就不需要把所有的页表都调入内存，只在需要它时查询调入。因此两级页表实则就是页表的页表。具体来说，将长长的页表分组，使每个内存块刚好放入一个分组。同时为离散分配的页表再建立一张页表，称之为页目录表（外层页表顶层页表）

我们规定，页目录表最多只能有一个页面，所以页目录表总共可以容纳4KB/4B=1K(占用10位)个页表项。这样在32位的结构中，低12位仍然是页内偏移量，高20位中更高的10位作为一级页号，更低的10位作为二级页号。一级页号用于查询小页表的存放位置，由一级页号查找到小页表后再由二级页号查询得到最终想要访问的块号

对于更高位系统，两级分页自然不够，就需要采用多级页表，但是不管是几级页表，必须满足各级页表的大小不能超过一个页面

3.1.4 基本分段管理方式（外部碎片）

基本思想：按照用户进程自身的逻辑关系划分为若干段。每个段有一个段名，每段从0开始编址。内存分配时，以段为单位进行分配，段内连续，段间可以不连续

分段存储管理逻辑地址结构：前一部分为段号，后一部分为段内地址

段表：为了能获得每个段在内存中存放的位置，操作系统会为每个进程建立一张段映射表，简称为段表。具体来说：
一个进程对应一张段表
进程的每一段对应一个段表项
每个段表项由段号、段长和基址组成
段表记录了每个段在内存中的起始位置和长度

分段与分页的对比

页是信息的物理单位，分页的目的是为了实现离散分配。分页仅仅是系统管理上的需要，完全是系统行为，对用户不可见。页的大小固定且由系统决定
段是信息的逻辑单位，分段的目的是为了更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息，对用户可见。段的长度不固定，用户编程时需要显式地给出段名

分页的用户进程地址空间是一维的，程序员只需要给出一个记忆符即可表示一个地址
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，又要给出段内地址

分段相较于分页来说更容易实现信息的保护和共享

3.1.5 段页式管理（内部碎片）

段页式管理：将进程先按照逻辑模块分段，再将各段分页。对内存空间的管理仍然和分页管理一样，将其分成若干和页面大小相同的存储块，对内存块的分配以存储块为单位

段页式存储管理逻辑地址结构：由段号、页号和页内地址（或页内偏移量）组成

在段页式管理中，根据段表可以获得该段对应的页表在内存中的存放位置，然后根据页表可以获得每一页对应的物理块号。每个进程只会对应一个段表，它拥有多个段，然后每个段又会对应一个页表，所以一个进程会对应多个页表
每个段对应一个段表项，每个段表项由段号、页表长度、页表存放的块号组成。由于段表项长度是固定的，所以段号可以隐含
每个页面对应一个页表项，每个页表项由页号，块号组成。由于页表项长度是固定的，所以页号可以隐含

注意：“分段”对用户是可见的，程序员编程时需要显示地给出段号、段内地址。而给各段“分页”的过程对用户却是不可见的，系统会自动进行。所以段页式管理的地址结构是二维的