内存管理
计算机不可能将所有用户进程和系统所需要的全部程序和数据放入主存，因此操作系统必须对内存
空间进行合理的划分和有效的动态分配。内存管理的概念就是操作系统对内存的划分和动态分配。
内存管理功能：
内存空间的分配与回收：由操作系统完成主存储器空间的分配和管理，是程序员摆脱存储分配
的麻烦，提高编程效率。
地址转换：将逻辑地址转换成相应的物理地址。
内存空间的扩充：利用虚拟存储技术或自动覆盖技术，从逻辑上扩充主存。
存储保护：保证各道作业在各自的存储空间内运行，互不干扰。
创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序，通常需要以下
几个步骤：
- 编译：由编译程序将用户源代码编译成若干目标模块（把高级语言翻译成机器语言）
- 链接：由链接程序将编译后形成的一组目标模块及所需的库函数连接在一起，形成一个完整的
装入模块（由目标模块生成装入模块，链接后形成完整的逻辑地址）
- 装入：由装入程序将装入模块装入内存运行，装入后形成物理地址
程序的链接有以下三种方式：
- 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文
件（装入模块），之后不再拆开。
- 装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式。
- 运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更
新，便于实现对目标模块的共享。
内存的装入模块在装入内存时，有以下三种方式：
重定位：根据内存的当前情况，将装入模块装入内存的适当位置，装入时对目标程序中的指令和数
据的修改过程称为重定位。
静态重定位：地址的变换通常是在装入时一次完成的。一个作业装入内存时，必须给它分配要求的全部内存空间，若没有足够的内存，则不能装入该作业。此外，作业一旦装入内存，整个运行期间就不能在内存中移动，也不能再申请内存空间。
动态重定位：需要重定位寄存器的支持。可以将程序分配到不连续的存储区中；在程序运行之前可以只装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内
存。
内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影
响。内存保护可采取如下两种方法：
- 在CPU中设置一对上、下限寄存器，存放用户作业在主存中的上限和下限地址，每当CPU要访
问一个地址时，分别和两个寄存器的值相比，判断有无越界。
- 采用重定位寄存器（或基址寄存器）和界地址寄存器（又称限长存储器）来实现这种保护。重
定位寄存器包含最小的物理地址值，界地址寄存器含逻辑地址的最大值。每个逻辑地址值必须
小于界地址寄存器；内存管理机构动态得将逻辑地址与界地址寄存器进行比较，若未发生地址
越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元。
覆盖与交换
覆盖与交换技术是在多道程序环境下用来扩充内存的两种方法，目的是减少程序占用的主存空间来
扩充内存。
覆盖是在同一个程序或进程中的，交换是在不同进程之间的。
覆盖技术的基本思想：将程序分为多个段，常用的段常驻内存，不常用的段在需要时调入内存。
特点 ：打破了必须将一个进程的全部信息装入主存后才能运行的限制，解决了程序大小超过物理
内存总和的问题。但对用户不透明，增加了编程的负担
交换技术的基本思想：内存空间紧张时，系统将内存中的某些进程暂时换出外存，把外存中某些已
具备运行条件的进程换入内存。
交换的时机选择的策略：
- 进程不用或很少再用的就换出
- 内存空间不够或者有不够的危险时，启动交换程序换出
连续分配管理方式
连续分配方式是指为一个用户程序分配一个连续的内存空间。主要包括单一连续分配、固定分区分
配和动态分区分配。
内部碎片 ：分配给某进程的内存区域中，有些部分没用上
外部碎片 ：是指内存中的某些空闲分区由于太小而难以利用
在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存
放操作系统相关数据;用户区用于存放用户进程相关数据。
内存中只能有一道用户程序，用户程序独占整个用户区空间。
优点 ：实现简单;无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护 。
缺点 ：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。
固定分区分配
固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小的分
区，每个分区只装入一道作业，当有空闲分区时，便可再从外存的后备队列中选择适当大小的作业
装入该分区。
分区大小相等：适用于利用一台计算机去控制多个相同对象的场合，缺乏灵活性。程序太小则
浪费内存，程序太大的分区装不下。
分区大小不等：划分多个较小的分区、适量的中等分区和少量的大分区，增加了灵活性。
动态分区分配不预先分配内存，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分
区的大小正好适合进程的需要。系统中分区的大小和数目是可变的。
动态分区分配会产生外部碎片，克服外部碎片可以采用紧凑技术来解决，即操作系统不时地对进程
进行移动和整理。但这需要重定位寄存器的支持，且相对费时。
动态分区分配的策略有以下几种算法：
- 首次适应算法 ：按地址从小到大为序，分配第一个符合条件的分区。
- 最佳适应算法 ：按空间从小到大为序，分配第一个符合条件的分区。
- 最坏适应算法 ：按空间从大到小为序，分配第一个符合条件的分区。
- 邻近适应算法 ：与首次适应相似，从上次查完的结束位置开始查找。
其中，首次适应算法不仅是最简单的，而且通常也是最好和最快的，但是会使得内存的低地址部分
出现很多小的空闲分区，每次分配查找时，都要经过这些分区，因此增加了查找的开销。邻近适应
算法试图解决这个问题，但实际上，它常常导致在内存的末尾分配空间分裂成小碎片，通常比首次
适应算法的效果要差。
最佳适应算法会产生最多的外部碎片。
最坏适应算法会很快导致没有可用的大内存块。
非连续分配管理方式
非连续分配允许一个程序分散地装入不相邻的内存分区，但这也需要额外的存储空间去存储它们的
索引，使得非连续分配方式的存储密度低于连续存储方式。
非连续分配管理方式根据分区的大小是否固定，分为分页存储管理方式和分段存储管理方式。在分
页存储管理方式中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行，分为基本分
页存储管理方式和请求分页存储管理方式。
基本分页存储管理方式
不会产生外部碎片，只会产生少量的内部碎片
分页的基本思想：把主存空间划分为大小相等的块，块相对较小，作为主存的基本单位。每个进程
也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。
分页存储的基本概念如下：
页面和页面大小。进程中的块称为页，内存中的块称为页框，外存也以同样的单位进行划分，
直接称为块。
页面大小应该适中，页面太小会使进程的页面数过多，这样页表就会过长，占用大量内存，而且也会增加硬件地址转换的开销，降低页面换入/换出的效率；页面太大又会使页内碎片增多，降低内存利用率。
地址结构。地址结构包含两部分，前一部分为页号P，后一部分为页内偏移量W。地址结构决定
了虚拟内存的寻址空间有多大。
页号 = 逻辑地址 / 页面长度
页内偏移量 = 逻辑地址 % 页面长度
页表。记录进程页面和实际存放的内存块之间的对应关系。页表由页表项构成，一般存放在内存中。页表的作用是实现从页号到物理块号的映射。页表项的作用是找到该页在内存中的位置。
页表寄存器。存放页表的起始地址和页表长度。
逻辑地址到物理地址的变换过程如下：
- 计算页号Р和页内偏移量W，P=A/L，W=A%L
- 比较页号P和页表长度M，若P≥M，则产生越界中断，否则继续执行。（注意：页号是从0开始的,而页表长度至少是1，因此 P=M时也会越界)
- 查询页表，找到页号对应的页表项，确定页面存放的内存块号
- 用内存块号和页内偏移量得到物理地址
- 访问目标内存单元
分页管理方式存在的两个主要问题：
- 每次访存操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访存速
度会降低。
- 每个进程引入页表，用于存储映射机制，页表不能太大，否则内存利用率会降低。
具有快表的地址变换机构：
时间局部性 ：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某
个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)
空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被
访问。（因为很多数据在内存中都是连续存放的)
若页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存，第一次是访问页表，确
定所存取的数据或指令的物理地址；第二次是根据该地址存取数据或指令。
在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器——快表，又称相联存储器
（TLB），用来存放当前访问的若干页表项，以加速地址变换过程。
引入快表后的地址变换过程如下：
- CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比
较。
- 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存
块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单
元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
- 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存
块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单
元。因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意:在找到页表项后，应同时
将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表
项进行替换)
两级页表
单级页表存在的问题：
- 所有的页表必须连续存放，页表过大时需要很大的连续空间
- 在一段时间并非所有的页面都用得到，因此没必要让整个页表常驻内存
为了压缩页表，采用二级页表机制。在进程执行时，只需要将这一页的上一级页表调入内存即可，
进程的页表和进程本身的页面可在后面的执行中再调入内存。
建立多级页表的目的在于建立索引，以便不用浪费主存空间去存储无用的页表项，也不用盲目地顺
序式查找页表项。若采用多级页表机制，则各项页表的大小不能超过一个页面。
不会产生内部碎片，会产生外部碎片
分页管理方式是从计算机地角度考虑设计的，目的是提高内存利用率，提升计算机的性能。分
页通过硬件机制实现，对用户完全透明。
分段管理方式的提出则考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及
动态链接等多方面的需要。
分段存储管理的相关概念如下：
分段
段式管理按照用户进程中的自然段划分逻辑空间，段内要求连续，段间不要求连续，整个作业的地
址空间是二维的，其逻辑地址由段号S和段内偏移量W两部分组成。
段号的位数决定了每个进程最多可以分为几个段，段内地址的位数决定了每个段的最大长度是多
少。
段表
每个进程都有一张逻辑空间与内存空间映射的段表，每个段表项对于进程的一段，段报项记录该段
在内存中的起始和长度，段表用于实现从逻辑段到物理内存区的映射。
地址变换机构
为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址F
和段表长度M。
地址变换过程如下所示：
段的共享与保护
在分段系统中，段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实
现的。不能修改的代码称为可重入代码（不属于临界资源），这样的代码和不能修改的数据可以共
享，而可修改的代码和数据不能共享。
分段管理的保护方法主要有两种，一种是存取控制保护，另一种是地址越界保护。地址越界保护将
段表寄存器中的段表长度与逻辑地址中的段号比较，若段号大于段表长度，则产生越界中断；再将
段表项中的段长与逻辑地址中的段内偏移进行比较，若段内偏移大于段长，也会产生越界中断。分
页管理中的越界保护只需要判断页号是否越界，页内偏移是不可能越界的。
分页与分段的对比：
- 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系
统管理上的需要，完全是系统行为，对用户是不可见的。段是信息的逻辑单位。分段的主要目
的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可
见的，用户编程时需要显式地给出段名。
- 页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
- 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。分段的用
户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
- 分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或可重入代码（不属
于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的
- 访问一个逻辑地址的访存次数分页（单级页表)︰第一次访存――查内存中的页表，第二次访存
――访问目标内存单元。总共两次访存分段:第一次访存――查内存中的段表，第二次访存――
访问目标内存单元。总共两次访存
段页式管理方式
页式管理方式能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共
享。将这两种存储管理方式结合起来，便形成了段页式存储管理方式。
在段页式系统中，作业的地址空间首先被分成若干逻辑段，每段有自己的段号，然后将每段分成若
干大小固定的页。对内存空间的管理仍然和分页存储管理一样，将其分成若干和页面大小相同的存
储块，对内存的分配以存储块为单位。
段页式系统中的作业逻辑地址分为三部分：段号、页号和页内偏移量。
段号的位数决定了每个进程最多可以分几个段页号位数决定了每个段最大有多少页，页内偏移量决定了页面大小、内存块大小是多少
其中，在一个进程中，段表只有一个，而页表可能有多个。进行一次访问需要查段表、查页表和访
问目标单元三次访存。
段页式系统的地址变换机构如下所示：
段页式管理方式
- 一次性：作业必须一次性全部装入内存后，才能开始运行。
- 驻留性：作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业结束
运行。
局部性原理
高速缓存技术利用的是局部性原理，将频繁使用的数据放到更高速的存储器中。
时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的)
基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统负
虚拟内存管理
虚拟内存的基本概念
传统存储管理方式的特征
责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂
时用不到的信息换出到外存。在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内
存，这就是虚拟内存。
虚拟存储器的最大容量由计算机的地址结构决定，实际容量 = min{内存和外存的容量之和，CPU的
寻址范围}。并不是简单的内外存容量相加。
虚拟存储器有以下三个特性：
- 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
- 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
- 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
虚拟内存技术的实现需要建立在离散分配的内存管理方式的基础上。
虚拟内存的实现有以下三种方式：
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
不管哪种实现方式，都需要硬件技术的支持。一般需要的支持有以下几个方面：
- 一定容量的内存和外出
- 页表机制（或段表机制）作为主要的数据结构
- 中断机构：当用户程序要访问的部分尚未调入内存时，则产生中断
- 地址变换机构：实现逻辑地址到物理地址的变换
请求分页产生内部碎片，请求分段产生外部碎片
请求分页系统建立在基本分页系统的基础之上，为了支持虚拟存储器功能而增加了请求调页和页面
置换功能。在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动程序运行。
虚拟内存技术的实现
请求分页管理方式
2022/7/22 13:03 内存 · 语雀
https://www.yuque.com/books/share/d9d6c020-67f9-457c-90da-6135ae1a2f5f/og650h 12/18
请求分页系统的页表机制不同于基本分页系统，请求分页系统在一个作业运行之前不要求全部一次
性调入内存，因此在作业运行过程中，必然会出现要访问的页面不在内存中的情况，如何发现和处
理这种情况是请求分页系统必须解决的两个基本问题。为此，在请求页表项中增加了4个字段，如
下图所示。
状态位：用于指示该页是否已调入内存，供程序访问时参考。
访问字段：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访
问，供置换算法换出页面时参考。
修改位：标识该页在调入内存后是否被修改过。
外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。
在请求分页系统中，每当要访问的页面不在内存中时，便产生一个缺页中断，请求操作系统将所缺
的页调入内存。此时应将缺页的进程阻塞（调页完成唤醒），若内存中有空闲块，则分配一个块，
将要调入的页装入该块，并修改页表中的相应页表项，若此时内存中没有空闲块，则要淘汰某页，
若被淘汰的页在内存期间被修改过，则要将其写回外存，采用页面置换算法。
缺页中断与一般中断的不同：
- 在指令执行期间而非一条指令执行完后产生和处理中断信号，属于内部中断。
- 一条指令在执行期间，可能产生多次缺页中断。
在进行地址变换时，先检索快表：
- 若找到要访问的页，则修改页表项中的访问位，然后利用页表项中给出的物理块号和页内地址
形成物理地址。
- 若未找到该页的页表项，则应到内存中去查找页表，再对比页表项中的状态位P，看该页是否已
调入内存，未调入内存则产生缺页中断，请求从外存把该页调入内存。
页表机制
