0X2A

848操作系统(三) 内存管理

2020-09-25 · 11 min read

内存管理

内存管理基础

内存管理概念

内存管理功能:

  1. 内存空间分配和回收
  2. 地址转换
  3. 内存空间扩充
  4. 存储保护

程序装入与链接

用户程序要在系统中运行,必须先装入内存,一般有如下步骤:

  1. 编译
  2. 链接
  3. 装入

链接有以下几种方式:

  1. 静态链接
    运行之前就把目标模块以及库函数连接成一个完整的装配模块,不再拆开。这种方式需要解决两个问题:
    • 对相对地址的修改
    • 变换外部调用符号
  2. 装入时动态链接
    装入内存的时候再进行链接。
  3. 运行时动态链接
    运行的时候需要该模块再调进内存并连接。

装入有以下方式:

  1. 绝对装入方式
    装入的是绝对地址,一般适用于单道程序的环境。
  2. 可重定位装入方式
    装入的相对地址,装入时对目标程序指令和数据修改的过程叫重定位
    地址通常是装入时一次完成的,故也称为静态重定位。一旦作业装入内存,则必须分配要求的所有内存空间。(毕竟要给所有指令和数据编址)故又称为静态重定位。
  3. 动态运行时装入
    也成为动态重定位。程序装入内存后,并不把所有地址都转换成绝对地址,而是推迟到程序真正要执行的时候才执行重定位。这种方式需要一个重定位寄存器实现。

逻辑地址与物理地址空间

逻辑地址指的是编译后每个模块都从0开始的相对地址
物理地址空间指的是内存中的物理党员集合。是地址转换的最终地址,最后都要根据物理地址从主存中获得数据。

内存保护

内存保护一般可以采用两种方法

  1. 设置一对上下限寄存器
    每当CPU要访问一个地址时,将该地址和寄存器的值进行对比。
  2. 使用重定位寄存器和界地址寄存器
    重定位寄存器存储的是最小的物理地址值,界地址寄存器存储的是逻辑地址的最大值。
    对于CPU要访问的地址先和界地址值比对,如果符合要求再加上重定位寄存器的值获得物理地址。

交换与覆盖

交换主要是用作与多道程序,覆盖用作于单道程序。
交换中的交换空间通常作为磁盘的一整块,且独立于文件系统。

连续分配管理方式

单一连续分配

这种方式会分为系统区和用户区,这种方式不需要内存保护,但同时只能给单个程序使用。有内部碎片 无外部碎片

固定分区连续

又根据分区大小是否相等分为两种。需要一张内存分区表,程序需要转入时,查询表是否有可用内存,无法满足则不分配内存。
有内部碎片 无外部碎片

动态分区分配

主要分为四种:

  1. 首次适应算法。总体效果最好
  2. 最佳适应算法。会产生最多的外部碎片
  3. 最坏适应算法。又称最大适应,对大程序不友好。
  4. 临近适应。

非连续分配管理方式

分页管理方式

分页管理方式没有外部碎片,有内部碎片
分页存储的几个概念

  1. 页面和页面大小
    进程中的块称为内存中的块称为页框,外存的块就成为块。
    进程执行的时候会申请空间,对应着页和页框。
  2. 地址结构
    地质结构包含页号和页内偏移量
  3. 页表
    每个进程拥有一个页表。页表一般存放在内存。

PTR 每个系统只有一个。记录页表开始地址和长度。
快表就是在高速缓存存储器中存一部分的页表拷贝,可以提速。快表找不到再去页表找。当然有些系统快慢一起找,快表找到了就停止慢表的查找。

分段管理方式

段式管理结构根据用户进程的自然段划分逻辑空间。段内要求地址连续,段间不要求连续。
每个进程都有一张逻辑空间与内存映射的段表,记录着段号、段长、以及本段在主存的起址。

分段式管理方式有以下优点:

  1. 方便编程
  2. 信息共享
  3. 信息保护
  4. 动态增长
  5. 动态链接

段页式管理方式

即将分段式和分页式结合,先将程序分成若干个段,再把每个段分为若干个页。
在段页式系统中,为了实现地址转换,需要同时配置段表和页表。和分段式不同的是,段表中记载的不是内存始址和段长,而是页表始址和页表长度。
在一个进程中,段表只有一个,页表可以有很多个(有多少段就多少个)

虚拟内存管理

虚拟内存的基本概念

传统存储管理的特征:

  1. 一次性
  2. 驻留性

虚拟内存的特征:

  1. 多次行
  2. 对换性
  3. 虚拟性

请求分页管理方式

请求分页系统的页表机制不同于基本分页系统,需要在页表中添加以下字段:

  1. 状态位P:记录是否调入了内存
  2. 访问字段A:记录一段时间内被访问的次数
  3. 修改位M:记录是否被修改过
  4. 外存地址:记录在外存上的地址

页面置换算法

最佳(OPT)置换算法

被调出的是最长时间内不被调用的页面。但是无法预测未来时间的调用,因此无法实现。

####先进先出(FIFO)置换算法
优先淘汰最早装进内存的页面。
FIFO算法还会导致Belady异常,即分配的物理块增大,反而导致缺页故障变多的现象。
基于队列实现。

最近最久未使用(LRU)算法

选择最久未使用的算法进行淘汰。性能较好,但需要堆栈支持。

时钟(CLOCK)算法

时钟算法又称最近未用(NRU)算法。
简单的Clock算法只附加一个位:使用位。当某页首次装入内存时,将它使用位置为1,当该页再次被访问时,依旧置为1。需要页面置换的时候,操作系统扫描缓冲区,寻找使用位为0的页面,经过使用位为1的页面时,也会将使用位置0。

改进的Clock算法增加一个修改位,对于被修改过的页来说,需要重新写回到磁盘,而未修改过的页面不需要写回磁盘。那么修改过的页面置换代价更大,因此优先换出未修改过的页面
那么每一帧都会处于以下时钟状态之一:

  1. 未被访问,未被修改(A=0,M=0)最佳替换页
  2. 未被访问,已被修改(A=0,M=1)不算特别好的置换页
  3. 已被访问,未被修改(A=1,M=0),有可能被访问
  4. 已被访问,且被修改(A=1,M=1),可能被访问

这里可以看到的是,访问的优先级会比修改高,最近被访问的页面会偏向于不被换出,然后到未被访问但修改过的页面,最易于被换出的是未被访问未被修改。总体的步骤如下:

  1. 寻找A=0,M=0的页面,不修改任何标志位
  2. 寻找A=0,M=1的页面,将A=1的页面修改为A=0。
  3. 重复1 - 2

页面分配策略

驻留集大小

决定驻留集大小需要考虑:

  1. 分配给一个进程的存储越小,进程数目就越多,处理机使用率就越高
  2. 一个进程的页数越少,就会频繁缺页
  3. 页数过多,由于局部性原则,可能并不会提高太多的缺页率。
    基于上述考虑,内存分配策略有以下几种:
  4. 固定分配局部替换
    为每个进程分配一定数目的物理块,整个过程不变,如果缺页只能用自己的页面进行换出。这样的策略难点在于缺点固定分配的数目大小。
  5. 可变分配全局置换
    最容易实现的分配策略。为进程分配一定数量的物理块,同时也保留一部分空闲的物理块队列。缺页时,从空闲物理块分配给进程。
  6. 可变分配局部替换
    为每个进程分配一定数量的物理块,缺页时只能用自己的页面进行置换,频繁缺页操作系统则给他分配物理块,直至缺页率正常。反之,如果物理块过多,也会被剥削。

调入页面的时机

有两种调入策略:

  1. 预调页策略
    根据局部性原理,一次调度若干相邻页会比一次次调入更为高效。目前策略主要为首次预调入,由程序员决定应该先调入哪些页。
  2. 请求调页策略
    运行的时候需要的页面不在内存则提出请求。

从何处调入页面

外存一般会被分为两部分:连续的对换区和离散的文件区。
因此,从何处调入页面就有了三种情况:

  1. 系统拥有足够的对换区:直接全部从对换区调入
  2. 系统缺少足够的对换区:不会修改的文件从文件区调入,由于他们未被修改,换出的时候就不必换出来。对于被修改过的部分,则换出的时候放入对换区。
  3. Unix方式:和进程有关的文件都放在文件区,未运行过的页面都从文件区调入,曾经运行过的但被调出的放入对换区,下次调入从对换区调入。

工作集

工作集是指某段时间间隔内会访问到的页面集合。取决于窗口大小。
一般分配给进程的物理块数,要大于工作集大小。否则会出现抖动现象

抖动

刚被换出又要被换入,这种现象就叫做抖动。

易错点

  1. 若进程在IO操作,不能交换操作
  2. 内存保护需要操作系统和硬件一起完成
  3. 重定位寄存器系统只需要一个
  4. 存储管理目的:方便用户、提高内存利用率
  5. 虚拟存储只能基于非连续分配技术
  6. 虚拟存储容量只受寻址空间影响
  7. 造成LRU算法耗费高的原因是需要对页进行排序,需要硬件支持只是前者导致的
  8. 合法位信息决定是否发生缺页故障
  9. CPU使用率不高,外存使用率高,说明内存不够