相关概念

从写程序到程序运行

• 编辑源代码文件
• 编译：由源代码文件生成目标模块(高级语言“翻译“为机器语言)
• 链接：由目标模块生成装入模块，链接后形成完整的逻辑地址
• 装入：将装入模块装入内存，装入后形成物理地址

程序经过编译、链接后生成的指令中指明的是逻辑地址（相对地址），即：相对于进程的起始地址而言的地址。在装入运行后，才会将逻辑地址转换为物理地址。

链接的三种方式

• 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开。
• 装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式。
• 运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。

装入（装载）的三种方式

• 绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。绝对装入只适用于单道程序环境。
• 静态重定位：又称可重定位装入。编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的）。
  • 静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。
• 动态重定位：又称动态运行时装入。编译、链接后的装入模块的地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。采用动态重定位时允许程序在内存中发生移动。
  • 可将程序分配到不连续的存储区中；在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。

存储管理的功能

• 定位(存储分配)：为具体的程序和数据等分配存储单元或存储区工作。
• 地址映射：将逻辑地址转换为相应的物理地址。地址空间是程序用来访问信息所用地址单元的集合。
• 存储共享：两个或多个进程共用内存中相同区域。目的：节省内存空间，提高内存利用率、实现进程通信(数据共享)。
• 存储保护：各道程序只能访问自己的内存区而不能互相干扰，必须对内存中的程序和数据进行保护，以免受到其他程序有意或无意的破坏。可对进程执行时所产生的所有内存访问地址进行检查，确保进程仅访问它自己的内存区，这就是地址越界保护，越界保护依赖于硬件设施，常用的有：界地址寄存器和存储键。
• 存储扩充：用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来“扩充”内存的容量，使用户得到比实际内存容量大的多的内存空间。
  • 覆盖技术：将程序分为多个段(多个模块)。常用的段常驻内存，不常用的段在需要时调入内存。内存中分为一个“固定区”和若干个“覆盖区”。需要常驻内存的段放在“固定区”中，调入后就不再调出(除非运行结束)。这种实现方式需要程序员手动声明覆盖区，不便于实现。
  • 交换技术：交换(对换)技术的设计思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)，换到外存中的进程就称为挂起态，即使进程被换出内存，PCB必须常驻内存。
  • 虚拟存储技术：具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用。

具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式；对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式。总之，对换区的I/O速度比文件区的更快。

实存管理

连续分配管理方式（分区）

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

单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。

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

固定分区分配

20世纪60年代出现了支持多道程序的系统，为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。

可分为大小相同的分区和大小不同的分区，但依然缺乏灵活性。

固定分区分配会产生内部碎片：

内部碎片，分配给某进程的内存区域中，有些部分没有用上。
外部碎片，是指内存中的某些空闲分区由于太小而难以利用。

操作系统需要建立一个数据结构——分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态(是否已分配)

动态分区分配

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

分配与回收方案：
+ 当作业装入内存时：
+ 若有足够空间，分割一个分区给该作业（具体选择策略由分配算法决定）
+ 若没有足够空间，等待内存资源
+ 空间回收：若两端有空闲区，和空闲区合并

动态分区会产生外部碎片：

动态分区分配算法：

• 首次适应算法：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。会出现低地址空闲区用得较频繁的情况，内存各区域使用频率不均。但优点是通常能保留高地址区域的较大分区，更不容易产生外部碎片。
  • 为了解决首次适应算法的缺点，可以使用改进后的“下次适应算法”，它会接着上一次扫描到的位置继续往下扫描，不会导致各区域使用频率不均。
• 最佳适应算法：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。缺点：会产生较多外部碎片。
• 最坏适应算法：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

非连续分配管理方式（分页）

程序存放到若不相邻的空间块中。

将内存空间分为一个个大小相等的分区(比如：每个分区4KB)，每个分区就是一个“页框”，或称“页帧”、“内存块”、“物理块”。每个页框有一个编号，即“页框号”(或者“内存块号”、“页帧号”、“物理块号”)。页框号从0开始。

将用户进程的地址空间也分为与页框大小相等的一个个区域，称为“页”或“页面”。每个页面也有一个编号，即“页号”，页号也是从0开始。

逻辑地址由页号（逻辑地址/页的大小）和页内偏移（逻辑地址%页的大小）构成，物理地址=页号对应的页框号×块长+页内地址。为了方便计算页号、页内偏移量，页面大小一般设为2的整数幂

那么如何知道页号对应的页框号？为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。

进程的页表在进程运行的时候也会被装载到页框中。

1. 进程的每一页对应一个页表项
2. 每个页表项由“页号”和“块号”（页框号）组成
3. 页表记录进程页面和实际存放的内存块之间的对应关系

基本地址变换机构

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

通常会在系统中设置一个页表寄存器(PTR)，存放页表在内存中的起始地址F和页表长度M。

进程未执行时，页表的始址和页表长度放在进程控制块(PCB) 中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

地址变换过程：
1. 根据逻辑地址计算出页号、页内偏移量
2. 判断页号是否越界，如果越界会触发越界中断（如果页号大于或等于页表长度）
3. 查询页表，找到页号对应的页表项，确定页面存放的内存块号
4. 用内存块号和页内偏移量得到物理地址

由于页表中的页表项都是连续存储的，而页表项的大小是相等的，因此页号可以隐含（从0开始的连续计数），只存储块号。

翻译快表

由上述内容我们可以知道，访问进程中的一个逻辑地址需要经过两次访存（第一次查询页表，第二次才是真正的访问逻辑地址对应的物理地址），那有没有办法减少访存次数呢？

快表（TLB）是一种特殊的高速缓冲存储器（Cache），内容是页表中的一部分或全部内容。在操作系统中引入快表是为了加快地址映射速度。

地址变换过程：
1. 根据逻辑地址计算出页号、页内偏移量
2. 判断页号是否越界，如果越界会触发越界中断（如果页号大于或等于页表长度）
3. 查询快表
1. 若快表中没有目标页表项，则需要查询内存中的页表，并将查询到的页表项放入快表
2. 若查询快表命中，就获取了页号对应的页表项
4. 用内存块号和页内偏移量得到物理地址

因此，如果查询快表命中，则访问某个逻辑地址仅需一次访存即可。有的系统还支持快表和慢表（对应内存中的页表）同时查找，减少平均耗时。

多级页表

如果程序使用空间很大，它的页表也会很大，需要占用很多个连续的页框。我们可以利用索引的思想，为页表也建立索引，使其可以离散存储于内存的各个页框中，称为多级页表。

系统为每个进程建一张页目录表，它的每个表项对应一个页表页，而页表页的每个表项给出了页面和页框的对应关系，页目录表是一级页表，页表页是二级页表。

使用二级页表后的逻辑地址结构由三部分组成：一级页号、二级页号和页内偏移

注意：各级页表的大小不能超过一个页面。

基本分段存储管理

与“分页”最大的区别就是离散分配时所分配地址空间的基本单位不同

分页存储管理是一维地址结构，分段存储管理是二维地址结构。

进程的地址空间按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名(在低级语言中，程序员使用段名来编程)，每段从0开始编址。

分段系统的逻辑地址结构由段号(段名)和段内地址(段内偏移量)所组成。段号的位数决定了每个进程最多可以分几个段，段内地址位数决定了每个段的最大长度是多少。

段表：程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称段表。每个段对应一个段表项，其中记录了该段在内存中的起始位置(又称“基址”)和段的长度。

分页和分段的区别：
+ 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
+ 段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。

段页式存储管理

段页式存储管理结合了分页管理和分段管理的优缺点，将进程按逻辑模块分段，再将各段分页(如每个页面4KB)。内存依然按页的大小分为各个页框。

段页式系统的逻辑地址结构由段号、页号、页内地址(页内偏移量)组成。段号的位数决定了每个进程最多可以分几个段，页号位数决定了每个段最大有多少页，页内偏移量决定了页面大小、内存块大小是多少

因此段页式管理的地址结构也是二维的。

段页式管理中的段表存储的就不是基址了，而是页表长度和页表的存放块号。地址转换时先查询段表，再查询页表。

虚存管理

相关概念

有的时候可以在进程运行时实时将所需要的页装入内存，而不需要一次性全部装入，称为部分装入。当内存已满而又有新的“部分”需要装入时，要把已在内存的某一“部分”换出去，称为部分对换

程序局部性原理：
+ 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)
+ 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的)

基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。

分页虚存系统的硬件支撑：内存管理单元MMU完成逻辑地址到物理地址的转换功能，它接受逻辑地址作为输入，物理地址作为输出，直接送到总线上，对内存单元进行寻址。 MMU的主要功能：
1. 管理硬件页表基址寄存器。
2. 分解逻辑地址。
3. 管理快表TLB。
4. 访问页表。
5. 发出缺页中断或越界中断，并将控制权交给内核存储管理处理。
6. 设置和检查页表中各个特征位。

虚拟内存的实际容量= min(内存和外存容量之和，CPU寻址范围)

与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存。如果还没调入，那么也需要知道该页面在外存中存放的位置。当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面。有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。

于是，请求分页存储管理的页表除了对应的内存块号外，还记录了状态位（是否已调入内存，1为是，0为否）、引用位（可记录最近被访问过几次，或记录上次访问的时间，供置换算法参考）、修改位（页面调入内存后是否被修改过）、外存地址

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。

如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

页面置换算法

最佳页面置换算法OPT：调入一页而必须淘汰一个旧页时，所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页。最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

先进先出页面替换算法FIFO：基于程序总是按线性顺序来访问物理空间这一假设。算法淘汰最先调入内存的页，或者说在内存中驻留时间最长的页。该算法可以使用固定大小的队列实现，队列的大小为系统为进程分配的内存块数。并且该算法的性能不是很好，即使最先调入内存的页面也可能经常用到。

最近最少用页面替换算法LRU：算法淘汰的页面是在最近一段时间里较久未被访问的那页。 该算法的性能较好，最接近最佳页面置换算法。实现方法：
+ 该算法可以用固定大小的链表实现，当使用某个页的时候将其连接到链表的尾部。
+ 引用位法：每页设置一个引用位R，访问某页时，由硬件将页标志位R置1，隔一定时间t将所有页的标志R均清0。发生缺页中断时，从标志位R为0的页中挑选一页淘汰。挑选到要淘汰的页后，也将所有页的标志位R清0。
+ 计数法：每个页面设置一个多位计数器，又叫最不常用页面替换算法LFU。每当访问一页时，就使它对应的计数器加１。当发生缺页中断时，可选择计数值最小的对应页面淘汰，并将所有计数器全部清０。
+ 计时法：为每个页面设置一个多位计时器，每当页面被访问时，系统的绝对时间记入计时器。淘汰时比较各页面的计时器的值，选最小值的未使用的页面淘汰。
+ 老化算法：为每个页设置一个多位寄存器r。当页面被访问时，对应寄存器的最左边位置1；每隔时间t，将r寄存器右移一位；在发生缺页中断时，找最小数值的r寄存器对应的页面淘汰。

第二次机会页面替换算法SCR：改进FIFO算法，把FIFO与页表中的”引用位”结合起来使用：
+ 检查FIFO中的队首页面(最早进入内存页面)，如果它的”引用位”是0，这个页面既老又没有用，选择该页面淘汰；
+ 如果”引用位”是1，说明它进入内存较早，但最近仍在使用。把它的”引用位”清0，并把这个页面移到队尾，把它看作是一个新调入的页。

时钟页面替换算法Clock：一个页面首次装入内存，其“引用位”置1。内存中的任何页面被访问时， ”引用位”置1。淘汰页面时，从指针当前指向的页面开始扫描循环队列，把迁到的”引用位”是1的页面的”引用位”清0，跳过这个页面；把所迁到的”引用位”是0的页面淘汰掉，指针推进一步。扫描循环队列时，如果迁到的所有页面的”引用位”为1，指针就会绕整个循环队列一圈，把碰到的所有页面的”引用位”清0；指针停在起始位置，并淘汰掉这一页，然后，指针推进一步。
+ 可以结合修改位对时钟页面替换算法进行改进。若用(访问位，修改位)的形式表述，则
+ 第一轮：淘汰(0, 0)
+ 第二轮：淘汰(0, 1) ，并将扫描过的页面访问位都置为0
+ 第三轮：淘汰(0, 0)
+ 第四轮：淘汰(0, 1)

页面分配策略

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

在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少;驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

分配策略：

• 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变。只要有一个缺页中断产生,进程就会有一页被替换。
• 可变分配：先为每个进程分一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变。进程执行的某阶段缺页率较高,说明目前局部性较差，系统可多分些页框以降低缺页率，反之说明进程目前的局部性较好,可减少分给进程的页框数。

置换策略：

• 局部置换：发生缺页时只能选进程自己的物理块进行置换。
• 全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

从何处调入页面：

1. 系统拥有足够的对换区空间：页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区。
2. 系统缺少足够的对换区空间：凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的
   部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。
3. UNIX方式：运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。