Chapter4 内存管理 - abowloflrf/os-note GitHub Wiki

概述

储存器的层次结构

沿着层次向下：价格下降，容量变大，速度变慢

内存管理目的

  • 有效利用内存空间
  • 考虑管理开销
  • 应用程序不必特别考虑内存大小

内存管理的功能

  • 记录内存的使用情况
  • 进程所占用内存空间的分配与回收
  • 内存不足时采取应对措施
  • 内存空间的共享与保护

程序的连接与装入

连接

多个目标文件和库文件连接成一个完整的可执行文件

  • 静态连接

静态，只连接一次，多次运行

  • 装入时连接

装入后为静态

  • 实际运行时连接

调用动态连接

装入

每个程序运行前必须要装入内存，不一定一次全部装入

  • 完全静态装入

程序装入时不作任何修改即装入内存的每个字节与其可执行文件完全相同

  • 静态重定位装入

程序装入时进行一次地址重定位（程序中的相对地址[逻辑地址]->绝对地址[物理地址]），运行时不变

  • 动态重定位装入

执行到一条指令要访问的某个内存地址时才进行重定位

实储存器管理

进程的大小不能超过可用内存空间的大小

连续分配

每个进程分配连续的内存空间

  1. 单一连续区分配

内存划分为两个区：系统区和用户区

只能用于单用户，单任务OS

  1. 固定分区

将内存的用户区预先划分为若干区，分区个数与每个分区大小固定，每个分区放一个进程

需要分区使用表，记录分区状态

问题：超过最大分区的程序无法装入；存在内存碎片无法得到使用，造成空间浪费

  1. 可变分区

或称动态分区，开始只有一个空闲分区，随之进程装入与退出，分区的个数与每个分区的大小动态变化

需要空闲分区表/链，已分配分区表

分区分配算法

  1. 最先适配法

从空闲分区链中按地址递增次序排列，选择第一个足够大小的分区

  1. 下次适配法

基于最先适配法，不过每次适配结束之后记录下寻找到的这个内存地址，下次从这个地址往后寻找空闲分区

  1. 最佳适配法

遍历整个分区表，选择能容纳进程的最小的空闲分区

  1. 最差适配法

空闲分区表按递减次序排列，从头开始选择第一个分区（一定是最大的）

碎片问题

内存紧凑，几种小碎片为大分区，但是涉及到程序在内存中的移动，开销大

产生大量碎片难以利用的根本原因是连续分配

分页

等分内存为物理块（页面）编号为0，1，2...

分页类似于固定分区，页较小，且大小相等，一个进程可以占据多个页，且不要求连续

OS为每一个进程建立一个页表，记录进程页号与物理块的对应关系

  • 页表寄存器PTR

系统设置一个页表寄存器，存放当前进程的页表起始地址和长度，平时放在PCB，进程被调度是放到PTR

  • 页大小选择

若小：碎片小，页表占用空间大

若大：页表小，但页内碎片大

通常大小为2的整数次幂

  • 地址转换

物理地址 = 块号 × 页大小 + 页内地址

CPU要存取一个数据时，需要访问内存两次，第一次访问页表找到该页对应的物理快号，拼接成物理地址，第二次访问这个物理地址取得其中的指令或数据

  • 引入快表（联想存储器）

具有并行查找能力的特殊高速缓冲存储器，用途：保存当前进程的页表的子集，如最近访问过的页表项，目的：提高地址变换速度

  • 二级页表

二级页表将页表进行分页，一级页表：第i项记录第i号二级页表所在的物理块号，二级页表：第i项记录第i页对应的物理块号

分段

将进程的逻辑地址空间分段，每一个段都是连续的，各个段长度不要求想等，内存分配以段为单位，各段不要求相邻

分段无内部碎片，但是有外部碎片

  • 管理

OS为每个进程建立一个段表

  • 地址变换

段表寄存器：存放当前进程的段表其实地址和长度，平时也是放在PCB中

31----段号s----12-11----段内地址w----0

已知逻辑地址12f0h(0001 0010 1111 0000)其低12位(0010 1111 0000)为段内地址，高位0001为段号 因此物理地址为段号1对应的基址+段内地址

CPU要存取一个数据时，需要访问两次内存，第一次访问段表，找到该段的基址，与段内地址相加得到物理地址，第二次访问这个物理地址得到其中的指令或数据

段页式（分页+分段）

结合分段与分页的有点，克服二者缺点

CPU需要存取一个数据时，需要访问三次内存，第一次：访问段表，获得该段的页表地址，第二次：访问页表获得物理块号，得到物理地址，第三次：访问物理地址

覆盖

将程序划分为若干功能相对独立的程序段，按照自身的逻辑结构是哪些不会同时执行的程序段共享同一块内存区域

覆盖快存放在磁盘上，一个程序执行结束，把后续程序段调入内存，覆盖前面的程序段

缺点：要求程序员划分程序，提供明确的覆盖结构，对用户不透明

虚拟储存管理

_进程的大小可以超过可用物理内存大小_OS把当前用到的部分留在内存，其余的放在外存

交换swap

换入：从磁盘移入内存，换出：从内存移出到磁盘

交换是实现虚拟储存器的基础

虚拟页式管理

在程序运行前不是装入全部页，而是装入部分，再根据需要动态装入其他页，当内存空间满时，又需要装入新的页，再根据算法装入新的页

缺页中断

地址变换过程中，访问页表时发现要访问的页不在内存，产生缺页中断

  1. 保护现场
  2. 根据页表给出的外存地址在外存中找到该页
  3. 若内存中无空闲的物理块则选择一页换出
  4. 分配一个空闲物理快将新调入页换入内存
  5. 修改页表中状态位，物理块号，修改空闲物理块表
  6. 恢复现场

置换算法

作用：选择换出页；目的减少缺页率；思路：以过去预测未来

  1. 最优置换算法OPT

淘汰以后永不使用，或者过最长时间后才会被访问的页

无法实现，它必须知道将来的情况，因此只是衡量其他算法优劣的标准

  1. 先进先出置换算法FIFO

淘汰最早进入内存的页

优点：开销小实现简单 缺点：与进程访问内存的动态特征不相适应，产生Belady现象，当分配给进程的物理块增加时，缺页数反而增加

  1. 最近最久未使用算法LRU

淘汰最近一次访问距离当前时间最长的页

计时器、移位寄存器、栈

  1. 最近未使用算法NRU

简单NRU算法

改进NRU算法

  1. 最少使用算法

选择最近访问次数最少的页淘汰

  1. 页缓冲算法

与上述算法配合使用提高效率

局部性原理

  • 时间局部性

一条指令被执行了，则在不久的将来它可能再次被执行；数据同理

  • 空间局部性

某一内存单元被访问，则一定时间内，与该储存单元邻近的单元可能被访问

抖动

页在内存中与外存之间频繁换入换出，以至于调度的时间比实际运行的时间还多，导致系统效率下降

原因
  • 页置换算法不合理
  • 分配给进程的物理块数太小

工作集

一个进程在时刻t参数为Δ的工作集W(t,Δ)，表示该进程在过去Δ时间单位中被访问到的页的集合

影响缺页次数的因素

  1. 分配给进程的物理块数
  2. 页大小
  3. 程序编写方法
  4. 页置换算法