第三章 内存管理

标签：第三章 管理 算法 地址 内存 页表 进程 页面

第三章 内存管理

3.1 无存储器抽象

最简单的存储器抽象就是根本没有抽象。 早期大型计算机（20世纪60年代之前） 、 小型计算机（20世纪70年代之前） 和个人计算机（20世纪80年代之前） 都没有存储器抽象。 每一个程序都直接访问物理内存。 当
一个程序执行如下指令：

MOV REGISTER1,1000

计算机会将位置为1000的物理内存中的内容移到REGISTER1中。 因此， 那时呈现给编程人员的存储器模型就是简单的物理内存： 从0到某个上限的地址集合， 每一个地址对应一个可容纳一定数目二进制位的存储单元， 通常是8个。

3.2 一种存储器抽象：地址空间

3.2.1 地址空间的概念

在最初系统中没有对内存的抽象，直接使用物理地址进行存储，这种方法会带来严重的问题：如果用户程序可以寻址内存的每个字节，它们就可以容易地破坏操作系统，从而使操作系统停止运行。想要同时运行多个程序很困难，因为使用物理地址很容易将数据覆盖。

要保证多个应用程序同时存在于内存并且不互相影响，要解决两个问题：保护和重定位。一个很好的解决方法是创造一个内存抽象：地址空间。地址空间为程序创造了一种抽象的内存，地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间，并且这个地址空间独立于其他进程的地址空间(在特殊情况下想要共享除外)。

3.2.2 交换技术

交换技术：将一个进程完整调入内存，使其运行一段时间后再存回硬盘。

1. 换入后使用硬件重定位
2. 产生空洞，需要内存紧缩
3. 现代程序需要内存较多，但是硬盘速度慢，交换时间长
4. 注意：进程大小如果增长，需要辅助手段。

解决方案：移入时分配额外内存，再次交换出去时不交换额外的。

3.2.3 空闲内存管理

1.位图存储：每个字需要1位位图

​ 优点：空间少

​ 缺点：分配内存时需要在位图里寻找指定长度的0串，费时。

2.链表管理：维护一个记录已分配内存段和空闲内存段的链表，每个链表的节点或包含一个进程，或者两进程之间的空闲区

• 优点：进程终止或者被换出是链表的更新非常直接

• 具体分配方法：

  • 首次适配first fit：沿列表搜索直到找到一个足够大的空间
  • 下次适配next fit：首次适配之后，从上次结束的地方开始搜索。（性能略低于首次适配）
  • 最佳适配best fit：搜索整个链表，找出能容纳进程的最小空闲区。

  （速度较慢，会产生大量无用的小空闲区）

  • 最差适配worst fit：分配最大的空闲区（也不好）
  • 为进程和空闲区保存单独链表
    • 优点：提高分配算法速度
    • 缺点：增加内存复杂度和内存释放速度变慢
  • 快速适配quick fit：为常用大小的空闲去维护单独的链表

3.3 虚拟内存

基本思想：每个程序拥有自己的地址空间，这个空间被分割成许多块，每一块称作一页page，page被映射到物理内存，但是只有某些页真正在内存中。操作系统调用不存在页面的时候，引发缺页中断。

3.3.1 分页

实际上存储在物理内存上（磁盘上），运行时一页一页读取

• 基本思想：用户程序的地址空间（虚拟地址空间）被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。
• 逻辑地址：系统将程序的逻辑空间按照同样大小也划分成若干页面，称为逻辑页面也称为页。程序的各个逻辑页面从0开始依次编号，称作逻辑页号或相对页号。每个页面内从0开始编址，称为页内地址。程序中的逻辑地址由两部分组成：页号P和页内位移量W。

若给定一个逻辑地址为A，页面大小为L，则页号P=INT[A/L]，页内地址W=A MOD L

3.3.2 页表

页表：分页系统中，允许将进程的每一页离散地存储在内存的任一物理块中，为了能在内存中找到每个页面对应的物理块，系统为每个进程建立一张页表，用于记录进程逻辑页面与内存物理页面之间的对应关系。页表的作用是实现从页号到物理块号的地址映射，地址空间有多少页，该页表里就登记多少行，且按逻辑页的顺序排列。

3.3.3 加速分页过程

1. 主要问题

   1. 虚拟地址到物理地址的映射必须非常快
   2. 如果虚拟地址很大，页表也会很大

2. 极端解决方案

   1. 页表全部在寄存器里
      1. 优点：简单，映射过程中不需要访问内存
      2. 缺点：页表很大时代价高昂，每一次上下文切换都必须装载整个页表，性能低
   2. 页表全在内存里
      1. 优点：上下文切换快
      2. 缺点：每条指令执行都需要访问内存

3. 现实解决方法

   1. 转换检测缓冲区translation lookaside buffer，TLB

      

      1. 本质：把虚拟地址直接映射成物理地址的小型硬件

      2. 使用：传入的虚拟页号并行匹配

      3. 未命中：MMU未检查到有效匹配项，则进行页表查询，从TLB淘汰一个表项，并用新页表项代替

      4. 软失效：页面不在TLB但是在内存：更新TLB，几纳秒

      硬失效：页面不在内存：缺页中断，磁盘IO，几毫秒

3.3.4 针对大内存的页表

1. 多级页表：32位虚拟地址划分成页表1，页表2，偏移量三部分

   原因：避免全部页表一直在内存（一般程序只有少量的正文段，数据段和堆栈段，中间是大量空洞，访问空洞时强制缺页中断并发信号）

2. 倒排页表（inverted page table，64位机器）：每一个页框对应一个页面

   

   优点：节省空间

   缺点：从虚拟地址到物理地址的转换困难（必须搜索整个表项来寻找（进程， 虚拟页面）对）

   解决方案：建立一张散列表，用虚拟地址来散列，相同hash值的表链在一起

3.4 页面置换算法

程序运行过程中，有时要访问的页面不在内存中，而需要将其调入内存。但是内存已经无空闲空间存储页面，为保证程序正常运行，系统必须从内存中调出一页程序或数据送到磁盘对换区，此时需要一定的算法来决定到底需要调出那个页面。通常将这种算法称为“页面置换算法”。

3.4.1 最优页面置换算法

实现原理：每次选择未来长时间不被访问的或者以后永不使用的页面进行淘汰。从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。即被淘汰页面是以后永不使用或最长时间内不再访问的页面。

优点：最佳置换算法可以保证获得最低的缺页率

缺点：最佳置换算法是一种理想化算法，具有较好的性能，但是实际上无法实现（无法预知一个进程中的若干页面哪一个最长时间不被访问）

3.4.2 最近未使用页面置换算法

实现原理：为使操作系统能够收集有用的统计信息，在大部分具有虚拟内存的计算机中，系统为每一页面设置了两个状态位。当页面被访问（读或写）时设置访问位R位；当页面（即修改页面）被写入时设置修改位M位。用R位和M位来构造一个简单的页面置换算法：当启动一个进程时，它的所有页面的两个位都由操作系统设置成0，R位被定期地（比如在每次时钟中断时）清零，以区别最近没有被访问的页面和被访问的页面。

当发生缺页中断时，操作系统检查所有的页面并根据它们当前的R位和M位的值，把它们分为4类：

第0类：没有被访问，没有被修改 00

第1类：没有被访问，已被修改 01

第2类：已被访问，没有被修改 10

第3类：已被访问，已被修改 11

NRU算法随机地从类编号最小的非空类中挑选一个页面淘汰之。这个算法隐含的意思是，在最近一个时钟滴答中（典型的时间是大约20ms）淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的“干净”页面好。

**优点：**易于理解和能够有效地被实现，虽然它的性能不是最好的，但是已经够用了

3.4.3 先进先出页面置换算法

实现原理：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。 即优先淘汰最早进入内存的页面。

优点：先进先出算法实现简单，是最直观的一个算法

缺点：先进先出的性能最差，因为与通常页面的使用规则不符合，所以实际应用少

3.4.4 第二次机会页面置换算法

**实现原理：**FIFO算法可能会把经常使用的页面置换出去，为避免该问题，对该算法做一个简单的修改：检查最老页面的R位。如果R位是0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是1，就将R位清0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续搜索。

3.4.5 时钟页面置换算法

实现原理：尽管第二次机会算法是一个比较合理的算法，但它经常要在链表中移动页面，既降低了效率又不是很有必要。一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。

3.4.6 最近最少使用页面置换算法

实现原理：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。即淘汰最近最长时间未访问过的页面。

3.4.7 用软件模拟LRU

• 最不常用算法（NFU）：每个页面与软件计数器相连，每次时钟中断是操作系统扫描所有页面并将R位加到计数器上，置换计数器值最小的页面

  • 缺点：记忆太久，操作系统可能会置换有用的页面

• 老化算法aging：在R位加入之前，计数器右移一位（相当于过去访问次数*1/2）,然后把R加到计数器最左边。置换计数器值最小的页面。

  • 缺点：不能确定时钟滴答中哪个页面被先访问

    计数器只有有限位数，限制了其对以往页面的记录（实际中一般够用）

3.4.8 工作集页面置换算法

1. 定义：一个进程当前正在使用的页面的集合称为工作集

2. 分页系统会设法跟踪工作集，在进程运行之前就预先调页

3. 大多数进程不会均匀访问地址空间，而是一小部分页面

4. 缺页中断时，淘汰不在工作集的页面。

5. 近似：过去的t秒实际运行时间中进程所访问的页面的集合

6. 算法

   

3.4.9 工作集时钟页面置换算法

工作集时钟页面置换算法：工作集算法的时钟版本

3.4.10 页面置换算法小结

3.5 分页系统中的设计问题

3.5.1 局部分配策略与全局分配策略

1. 局部算法可以有效地为每个进程分配固定的内存片段

   例子：工作集, FIFO, LRU

2. 全局算法在可运行进程之间动态分配页面，通常工作更好。

   例子：FIFO, LRU

   为进程分配相等的份额：不好，对大进程不公平，应该给每个进程分配最小的页框数

   PFF：监测缺页率，保证每个进程的PFF在可控范围内。

   

3.5.2 负载控制

负载控制：换成进程时考虑其特性（IO密集或者CPU密集）。

3.5.3 页面大小

小页面：更多页面更大页表，更多缺页中断，内部碎片少，分配时效率高

​ 大页面：反之

​ 计算公式： p = 2 ⋅ s ⋅ e p = \sqrt{2\cdot s\cdot e} p=2⋅s⋅e ​页面，s进程平均大小，e每个页表项大小

3.5.4 分离的指令空间和数据空间

独立分页

3.5.5 共享页面

1. 共享I空间页面

2. 共享页面时，换出进程不应换出共享页面：使用专门的数据结构记录共享页面

3. 共享数据：写时复制

3.5.6 共享库

1. windows：DLL文件，连接器没有加载函数，而是一小段可以在运行时绑定函数的存根里程stub routine
2. 优点：共享库中一个函数被修正：不需要重新编译程序
3. 问题：编译共享库时，不产生使用绝对地址的指令

3.5.7 内存映射文件

进程发起一个系统调用，把一个文件映射到虚拟地址的一部分。映射共享页面时不会实际读入页面，而在其访问页面时才会每次一页的读入。

3.5.8 清除策路

1. 分页守护进程：保证有足够空闲页框供给

2. 实现方法：双指针时钟，前指针由分页守护进程控制

3.5.9 虚拟内存接口

虚拟内存接口：允许程序员控制内存映射

1. 可以允许两个或多个进程共享一部分内存

2. 实现高性能的消息传递系统：发送进程清除映射，接收进程建立映射

3.6 有关实现的问题

3.6.1 与分页有关的工作

重置MMU，刷新TLB，装载页表

3.6.2 缺页中断处理

1. 陷入内核，保存程序计数器

2. 调用汇编例程保存其他寄存器

3. 操作系统查看寄存器或者分析指令判断所缺页面

4. 操作系统检查虚拟地址是否有效，若是则启动页面置换算法更换页面

5. 如果页面被修改过，启动IO，标记该页面，上下文切换

6. 启动IO装载缺失页面

7. 页表更新，恢复堆栈和寄存器，重启被中断进程

3.6.3 指令备份

使用隐藏的内部寄存器，在每条指令执行之前，把程序计数器的内容复制过来。

3.6.4 锁定内存中的页面

锁住正在进行IO的页面或者在内核缓冲区完成所有IO。

3.6.5 后备存储

1. UNIX：swap交换区：没有文件系统

2. 进程启动前必须初始化交换区

3. 实现方法

   1. 将整个进程复制到交换区：进程可能增长

   2. 直到换出时才分配交换区：内存中每个页面都要记录磁盘地址

      

      3.交换分区：windows使用大文件

      4.空间不足时抛弃程序正文或者共享库

3.6.6 策略和机制的分离

策略与机制分离：更多的模块化代码和更好的适应性，更多的陷入内核

1. 三部分：底层MMU处理程序，内核的缺页中断处理程序，用户空间的外部页面调度程序

   

2. 问题：外部调度程序无权访问页面的R位和M位

   1. 把相应数据映射到或者传递给外部调度程序
   2. 把页面置换算法放在内核

3.7 分段

分段：在机器上提供多个独立的地址空间，长度从0到某个整数，可以动态改变

1. 段是逻辑实体，不会同时包含不同类型的内容，不是定长的
2. 1维地址中，修改过程会影响其他无关地址的起始地址

3.7.1 纯分段的实现

可能会有碎片，需要内存紧缩

3.7.2 分段和分页结合

虚拟地址分为段号和段内地址，其中段内地址里有页号和页内偏移量

先找段—找页面—找虚拟地址

实例：奔腾处理器

虚拟内存的核心：局部描述符表LDT和全局描述符表GDT

利用选择子可以同时实现纯分页/分段和混合模式

保护环：越级调用

. 把相应数据映射到或者传递给外部调度程序
2. 把页面置换算法放在内核

3.7 分段

分段：在机器上提供多个独立的地址空间，长度从0到某个整数，可以动态改变

1. 段是逻辑实体，不会同时包含不同类型的内容，不是定长的
2. 1维地址中，修改过程会影响其他无关地址的起始地址

[外链图片转存中…(img-BBhkj0Q2-1722515899367)]

3.7.1 纯分段的实现

可能会有碎片，需要内存紧缩

3.7.2 分段和分页结合

虚拟地址分为段号和段内地址，其中段内地址里有页号和页内偏移量

先找段—找页面—找虚拟地址

实例：奔腾处理器

虚拟内存的核心：局部描述符表LDT和全局描述符表GDT

利用选择子可以同时实现纯分页/分段和混合模式

保护环：越级调用

标签：第三章,管理,算法,地址,内存,页表,进程,页面
From： https://blog.csdn.net/wgy17734894660/article/details/140856856