操作系统知识点总结——第三章内存管理

一、内存管理概念

（一）基本概念

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

1. 操作系统负责内存空间的分配与回收
2. 操作系统需要提供某种技术从逻辑上对内存空间进行扩充（虚拟内存）
3. 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换
   
4. 操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰
   方法一：设置一对上下限寄存器
   方法二：采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。

小节回顾

（二）覆盖与交换

1. 覆盖技术
   将程序分成多个段，分成一个固定区和多个覆盖区，将常驻内存的段放在固定区，调入后不再调出，不常用的段放到覆盖区，需要时调用不需要调出。
   
   必须由程序员声明覆盖结构，操作系统完成自动覆盖。
   缺点：对用户不透明，增加了用户编程的负担。⭐已淘汰⭐。

2. 交换技术
   内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度)，就是终极调度。
   暂时换出外存等待的进程状态为挂起状态（挂起态，suspend），挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态
   

3. 小节回顾
   

（三）连续分配管理方式

连续分配：指为用户进程分配的必须是一个连续的内存空间
⭐内部碎片⭐：分配给某进程的内存区域中，如果有些部分没有用上。
⭐外部碎片⭐：是指内存中的某些空闲分区由于太小而难以利用。

单一连续分配

内存被分为系统区和用户区，用户区存放用户进程相关数据，系统区存放操作系统。
内存中只能有一道用户程序，用户程序独占整个用户区空间，不支持多道程序。

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

⭐固定分区分配⭐

将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业。

分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合。
分区大小不等：灵活性增加，可以满足大小的进程需求。根据常在系统中运行的作业大小情况进行划分。

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

优点：实现简单，无外部碎片
缺点：用户进程过大没有合适分区，需要采用覆盖技术，会降低性能。会产生内部碎片，内存利用率低。

⭐动态分区分配⭐

又称为可变分区分配。这种分配方式不会像固定分区和单一分区方式一样预先划分好内存分区，而是在进程装入时，根据进程的大小动态地建立分区，并使分区的大小正好合适进程的需要。
⭐动态分区分配没有内部碎片，但是有外部碎片⭐

空闲分区表&空闲分区链

如何选择空闲分区需要用到空闲分区算法：首次适应、最佳适应、最坏适应、邻近适应

空闲分区回收
当进程从内存中移出后，如果该内存所在分区邻近有空闲分区，则进行空闲分区合并，否则则在空闲分区表中新增一条记录。

当需要装入的进程在内存中找不到合适大小的空闲分区后，可以通过紧凑技术，将小空闲分区合并得到合适的空闲分区。

小节回顾

⭐动态分区分配算法⭐

1. 首次适应算法
   算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
   如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表)，找到大小能满足要求的第一个空闲分区。

2. 最佳适应算法
   算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。
   如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
   ⭐缺点⭐：每次找最合适的空间，很容易产生很多小的难以使用的外部碎片。

3. 最坏适应算法
   又称最大适应算法( Largest Fit)
   算法思想：为了解决最佳适应算法的问题――即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
   如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表)，找到大小能满足要求的第一个空闲分区。
   ⭐缺点⭐:：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

4. 邻近适应算法
   算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
   如何实现：空闲分区以地址递增的顺序排列（可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

⭐综合看，首次适应算法是四种算法中最优的⭐

小节回顾

（四）⭐⭐基本分页存储管理⭐⭐（非连续分配管理方式）

⭐分页存储⭐

将内存空间分为一个个大小相等的分区，每个分区就是一个“ 页框 ”（页框=页帧=内存块=物理块=物理页面 ），每个页框有一个编号，即“页框号”（页框号=页帧号=内存块号=物理块号=物理页面号），页框号从0开始。
将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为**“页”或“页面”每个页面也有编号，称为“页号”，页号也从0开始**。
操作系统以页框为单位为进程分配内存空间，将每个进程的页面分别放入页框中。各个页面不必连续存放。

因为页框与页面有一一对应关系，需要一个数据结构建立一张页表存储这种关系。

⭐页号=逻辑地址/页面长度（取除法的整数部分）⭐
⭐页内偏移量=逻辑地址%页面长度（取除法的余数部分）⭐

结论：如果每个页面大小为2B，用二进制数表示逻辑地址,则末尾K位即为页内偏移量，其余部分就是页号

小节回顾

个人理解

• 进程所需的内存空间进行切割，每块和内存页框大小相等，形成页面
• 进程的页面会不连续的分散存储在各个页框中，这要找到对应地址的话，每个进程就需要一个页表来存储页面与页框的映射关系。
• 页表中记录的是进程的页面所在内存中的块号，而一个进程需要一个页表来与之呈现映射关系。
• 页内偏移量则是指在当前页框中的位置，则实际地址为内存块号*页框大小+页内偏移量。

⭐⭐基本地址变换机构⭐⭐

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。
通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

逻辑地址A中得到页号P，判断是否超过页表寄存器中的页表长度M，如果有则抛出越界中断，没有则通过页表始址和页号求和，计算错内存块号地址b所在位置，即其页表项所在内存地址，然后找到内存块号b，与页内偏移量相加得到物理地址。

小节回顾

需要访问两次内存，一次是访问页表，一次是访问实际的内存块地址。

⭐具有快表的地址变换机构⭐

快表，又称联想寄存器（TLB，translation lookaside buffer )，是一种访问速度比内存快很多的高速缓存（TLB不是内存! )，用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的质表常称为慢表。其实就是类似于高速缓存。

1. 快表实际就是一个页表的副本，但是访问速度比存在内存中的页表快很多。目的就是为了提升访存速度。
2. 当进程切换时快表被清空。
3. 给出逻辑地址的时候，判断页号与页表寄存器中的页表长度比较，越界则中断异常。没越界则访问快表，查询相应页号在快表中是否存在。
4. 存在则直接与偏移量进行求和访问物理地址。
5. 不存在则页号与页表寄存器的页表地址进行求和，得到内存中的页表项地址，找到内存块号并将其存取快表中，然后拼接求和访问内存。

小节回顾

因为命中时直接通过快表找到内存地址，只需要一次访存，未命中则需要进入内存访问页表然后再访问目标内存地址，需要两次访存。

⭐两级页表⭐

单级页表存在的问题

1. 页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。
2. 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面（采用虚拟存储技术的页面置换算法）。

访址逻辑

1. 逻辑地址给出后会给出一级页号、二级页号以及页内偏移量。
2. 将页表按照内存块号大小进行分块，然后存入内存，每一块都有一个页表块号。存入内存后会将页表块号和内存块号存入一级页表中。
3. 根据一级页号找到页表块在内存块号的地址。即找到二级页表，然后根据二级页号，找到二级页表中对应的内存块号，找到内存所在位置，与页内偏移量求和得到实际物理地址。

注意

1. 若采用多级页表机制，则各级页表的大小不能超过一个页面
2. 两级页表的访存要3次（无快表机构）

小节回顾

基本分段存储管理

进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从o开始编址
内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

逻辑地址结构

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

段表
和页表一样，需要一个数据结构记录段的位置，这里因为段的大小不一，所以需要增加一个段长字段用于判断是否越界等情况。

地址变换

1. 逻辑相似，逻辑地址给出段号，段表寄存器进行判断段号是否越界，越界则中断。
2. 不越界则通过段表始址与段号进行求和得到段表项所在位置
3. 检查段内地址是否越界，越界就中断，否则计算得到物理地址。

⭐分段与分页管理的对比⭐

⭐分段比分页更容易实现信息的共享和保护⭐

小节回顾

⭐段页式管理方式⭐

分页、分段的优缺点

段页式逻辑

内存分页，进程分段，分段后再分成与内存中页面大小相同的页，存入内存。⭐分段这个过程是用户可见的，由程序员操作，而对段分页是对用户不可见的，操作系统自动操作。⭐

⭐地址转换过程⭐

1. 得到逻辑地址后，首先是根据段表寄存器中的段表长度判断段号是否越界，越界则中断。
2. 无越界则是与段表始址F相加计算，得到段表项再段表中的位置
3. 根据页表长度，判断逻辑地址中的页号P是否越界，越界则中断
4. 无越界则根据页表存放块号找到页表并根据页号找到对应页表项，找出内存块号。
5. 根据实际内存块号和页内偏移量，找到内存中的实际物理地址所指向的内容。

小节回顾

二、虚拟内存管理

（一）虚拟内存的基本概念

传统存储管理方式的特征

一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题:①作业很大时，不能全部装入内存，导致大作业无法运行;②当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。

⭐局部性原理⭐

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

虚拟内存的定义和特征

• 基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
• 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
• 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
• 虚拟内存的三个特征
  1、多次性
  2、对换性
  3、虚拟性

小节回顾

（二）请求分页管理方式

1、⭐ 页表机制⭐

2、缺页中断机构
缺页中断是因为当前执行的指令想要访问到目标页面未调入内存而产生的，因此属于内中断。

3、地址变换机构

逻辑相似，只是页表字段增多。

小节回顾

（三）⭐⭐页面置换算法⭐⭐

换入/换出页面都需要启动慢速I/O操作，如果换入换出太平凡，会有很大的开销。

最佳置换算法（OPT）

最佳置换算法（OPT，Optimal)：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，⭐最佳置换算法是无法实现的⭐。

先进先出置换算法（FIFO）

每次选择淘汰页面是最早进入内存的页面。

Belady异常――当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差。

最近最久未使用置换算法（LRU）

Least recently used ，每次淘汰的页面是最近最久未使用的页面

该算法的实现需要专门的硬件支持，虽然算法性能号，但是实现难。

⭐时钟置换算法（CLOCK||NRU）⭐

时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU，Not Recently Used )

改进的时钟置换算法

小节回顾

（四）页面分配策略

⭐驻留集⭐：指请求分页存储管理中给进程分配的物理块的集合。在虚拟存储技术中，驻留集大小一般小于进程的总大小。

固定分配：驻留集大小不变
可变分配：驻留集大小可动态改变。
局部置换：发生缺页时只能选进程自己的物理块进行置换。
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

预调页策略：根据局部性原理预先调入若干相邻页面。这种策略主要用于进程的首次调入。，由程序员指出先调入部分。
请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存。

⭐抖动⭐：刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够)

工作集：指在某段时间间隔里，进程实际访问页面的集合。⭐驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页⭐。

小节回顾