操作系统内存管理

MOKE 2019-09-05 PM 12℃ 0条

内存概述

什么是内存:
内存是用于存放数据的硬件,程序执行前需要先放到内存中才能被CPU处理。

存储单元
将内存分为一个一个的小区间,每个区间就是一个存储单元。

内存地址
给内存的存储单元编地址,有两种:

  • 按字节编址:每个存储单元的大小为1字节(8位)
  • 按字编址:字长为16位的计算机,每个存储单元的大小为1个字(16位)

逻辑地址和物理地址

  • 逻辑地址:编译生成的指令中是逻辑地址,是相对地址。
  • 物理地址:是数据实际存放在内存当中的地址,是绝对地址。

进程运行的基本原理

进程执行的流程:
在这里插入图片描述
装入方式

  • 绝对装入: 在编译时,如果直到程序将放到内存中的哪个位置,编译时将产生绝对地址的目标代码,装入程序按照装入模块中的地址,将程序和数据装入内存。
    缺点:只适合单道程序环境。
  • 静态重定位: 编译、链接后的装入模块的地址都是从0开始,指令中也是逻辑地址。在装入时对地址进行重定位,将逻辑地址变换为物理地址。
    缺点:内存必须有足够的空间才能装入该进程,且运行期间不能移动。
  • 动态重定位: 使用重定位寄存器,当该进程被调度运行时,才会获取寄存器中的信息,将逻辑地址转换为物理地址。
    优点:运行期间也可移动。

链接方式

  • 静态链接: 在程序运行前,将个目标模块链接成一个完整的装入模块,之后不可拆分。
  • 装入时动态链接: 将各目标模块装入内存时,边装入边链接。
  • 运行时动态链接: 在程序执行中需要该目标模块时,才对它进行链接。

内存管理*

内存管理的主要内容

  • 地址转换: 对应三种装入方式
  • 存储保护: 保证各进程在自己的内存空间内运行,不会越界访问,两种方式:
    1.设置上下限寄存器

2.重定位寄存器+界地址寄存器

  • 内存空间的扩充(虚拟)
  • 内存空间的分配与回收

内存空间的扩充

  • 覆盖技术:将程序分为多个段,常用的段常驻内存,不常用的段在需要时调入内存(固定区,覆盖区)。
  • 交换技术:内存空间紧张时,系统会将内存中某些进程暂时换出外存,外存中已具备运行条件的进程换入内存(中级调度)。
  • 虚拟存储技术:后文

注:磁盘空间分为文件区和对换区,文件区采用离散分配方式,对换区采用连续分配方式。


内存空间的分配与回收

两种类型分配方式:

  • 连续分配管理:用户进程分配的必须是一个连续的内存空间
  • 非连续分配管理

连续分配管理

  • 单一连续分配:
    内存分为系统区和用户区,内存中只能有一道用户程序。
  • 固定分区分配:
    用户区划分为若干个固定大小的分区(分区大小相等/不相等),每个分区可装入一道作业。

需要建立分区说明表:分区大小、起始地址、状态

  • 动态分区分配:
    在进程装入内存时,根据进程的大小动态地建立分区。

需要建立空闲分区表或空闲分区链:
2

内部碎片: 分配给某个进程的内存区域中,有些部分没用上。
外部碎片: 内存中的某些空闲分区由于太小而难以利用。我们一般通过紧凑技术来解决外部碎片。

动态分区分配算法
当多个空闲分区都满足进程大小需求时,需要选择分区,因此有以下四中分配算法:

  • 首次适应算法
    空闲分区以地址递增的次序排列,顺序查找到第一个能满足的空闲分区。
  • 最佳适应算法
    空闲分区以容量递增的次序排列,顺序查找到第一个能满足的空闲分区。
  • 最坏适应算法
    空闲分区以容量递减的次序排列,顺序查找到第一个能满足的空闲分区。
  • 邻近适应算法
    空闲分区以地址递增的次序排列,从上次查找结束的位置开始查找,找到第一个满足要求的空闲分区。

非连续分配管理*

连续分配:为用户进程分配的必须是一个连续的内存空间。
非连续分配:为用户进程分配的可以是一些分散的内存空间。

三种管理方式:

  • 基本分页存储管理
  • 基本分段存储管理
  • 段页式存储管理

基本分页存储管理

基本思想
把内存分为一个个相等的小分区,再按照分区大小把进程拆分成一个个小部分。

基本概念

  1. 内存空间中每个分区被称为页框(页帧/内存块/物理块),每个页框有一个编号(从0开始),被称为页框号(内存块号/页帧号/物理块号)。
  2. 用户进程的地址空间划分为与页框大小相等的一个个区域,被称为页(面),也有一个编号,即页号
  3. 操作系统以页框为单位为各个进程分配内存空间,即页面与页框一一对应。

那如何知道进程的每个页面在内存中存放的位置,就要为每个进程建立一张页表,如下:
在这里插入图片描述
如何得到物理地址

  1. 算出逻辑地址对应的页号
  2. 要知道该页号对应页面在内存中的起始地址
  3. 要算出路基地址在页面内的“偏移量”
  4. 物理地址 = 页面始址 + 页内偏移量

上面是我们的实现逻辑地址到物理地址转换的原理,而实际上是由基本地址变换机构(用于实现逻辑地址到物理地址转换的一组硬件机构)来实现的。
通常会在系统中设置一个页表寄存器,存放页表在内存中的起始地址 F 和页表长度 M,进程未执行时,F 和 M 放在进程控制块 PCB 中。

优化

  1. 快表
    在基本地址变换机构中,每个逻辑地址都要查询内存中的页表,而快表(联想寄存器)是一种访问速度比内存快的高速缓冲存储器,用来存放当前访问的若干页表项,以加快地址变换的过程。
  2. 二级页表
    页表一般连续存放且没必要整个页表常驻内存,因此可以使用二级页表,即在原本页表的基础上,加一个页目录表,如下:

在这里插入图片描述

基本分段存储管理

基本思想
按照程序自身的逻辑关系划分为若干段,每个段都有一个段名且从0开始编址;每段在内存中占据连续空间,各段之间可以不相邻。
在这里插入图片描述
分段系统的逻辑地址由段号(段名)和段内地址(偏移量)组成,同样需要为每个进程建立一张段映射表,即段表
在这里插入图片描述
分段与分页对比

  • 页是信息的物理单位,是系统的行为,对用户不可见
  • 段时信息的逻辑单位,是用户编程是决定,对用户是可见的
  • 分页的逻辑地址是一维的,而分段的逻辑地址是二维的
  • 分段比分页更容易实现信息的共享和包含

段页式管理方式

先来看下分页管理和分段管理的特点:

优点缺点
分页管理内存利用率高,不会产生外部碎片不易实现信息的共享和保护
分段管理方便实现信息共享和保护段太长,不易分配连续空间,且会产生外部碎片

段页式管理 = 分段 + 分页
进程先分段,再将各段分为大小相等的页面
内存空间分为与页面大小相等的一个个内存块,系统以块为单位为进程分配内存,如下:
在这里插入图片描述
同时会存在段表页表

  • 段表:每段对应一个段表项,各段表项长度相同,由段号、页表长度、页表地址组成。
  • 页表:每页对应一个页表项,各页表项长度相同,由页号、页面存放的内存块号组成。

虚拟内存

传统存储管理的缺点:

  • 一次性,即作业必须一次性全部装入内存后才能开始运行。
  • 驻留性,即一旦作业被装入内存,就会一直驻留在内存中,直到作业运行结束。

虚拟内存技术
允许一个作业分多次调入内存,虚拟内存的实现需要建立在离散分配的内存管理方式基础上,对应三种非连续分配:
在这里插入图片描述
请求调页:访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存。
页面置换:内存空间不够时,由操作系统将内存中暂时用不到的信息换出到外存。


请求分页

页表机制
请求页表项增加了四个字段:
在这里插入图片描述
缺页中断机构
每当要访问的页面不在内存时,便会产生一个缺页中断,然后由操作系统的缺页中断处理程序处理中断。

缺页的进程会阻塞,调页完成后才唤醒。

内存中有空闲块就直接给该进程分配一个空闲块,如果没有则由页面置换算法淘汰一个页面。

缺页中断是因为当前指令想要访问的目标页面未调入内存,因此属于内中断。

地址变换机构
区别与基本分页:

  • 检查页面是否在内存中
  • 若不在内存中,需要请求调页
  • 若内存空间不够,还需换出页面
  • 页面调入内存后,需要修改相应页表项

页面置换算法

页面的换入、换出需要磁盘I/O,会有较大的开销,因此算法应该追求更少的缺页率。

最佳置换算法 OPT
每次选择淘汰的页面将是以后永不使用,或者在最长时间内不再被访问的页面。

因为系统需要知道以后会出现的页面,所以是无法实现的


先进先出置换算法 FIFO
每次选择淘汰的页面是最早进入内存的页面。

只有 FIFO 算法会产生 Belady 异常。
Belady 异常:为进程分配的物理块数增大时,缺页次数不减反增的异常现象。

FIFO 算法实现简单,但是性能差


最近最久未使用置换算法 LRU
每次淘汰的页面是最近最久未使用的页面。
实现:页表增加访问字段,记录每个页面自上次被访问依赖所经历的时间 t,每次选择现有页面中 t 值最大的。
在这里插入图片描述最接近 OPT 性能的算法,但是需要专门的硬件支持,算法开销大


时钟置换算法 CLOCK
性能和开销均衡的算法,又称为最近未用算法(NRU)。

实现:

  • 每个页面设置一个访问位(1/0),再将内存中的页面通过链接指针链接成一个循环队列。
  • 当某页被访问时,访问位为 1。
  • 当淘汰某个页面时,只需检查页的访问位,如果是 0,则换出;如果是 1,置 0,暂不换出并检查下一个。
  • 若第一轮扫描所有页面是 1,则都置 0 后会进行第二轮扫描。

在这里插入图片描述


改进型的时钟置换算法
上面的时钟置换算法其实少考虑了一种情况,就是页面是否被修改过。

所以需要检查访问位和修改位,用(访问位,修改位)表示,过程如下:

  • 第一轮,淘汰 (0,0),即未被使用和修改的页面
  • 第二轮,淘汰 (0,1),即未被使用的页面,并将扫描过的页面访问位置 0
  • 第三轮,淘汰 (0,0),即未被修改的页面
  • 第四轮,淘汰 (0,1),即最早进入队列的页面

页面分配策略

驻留集:指请求分页存储管理中给进程分配的内存块的集合。
工作集:指再某段时间间隔里,进程实际访问页面的集合。
驻留集一般小于进程的总大小,驻留集大小一般不能小于工作集大小。

固定分配: 操作系统为每个进程分配一组固定的物理块,即驻留集大小不变。

可变分配: 先为每个进程分配一定数目的物理块,在进程运行期间根据情况做适当的调整,即驻留集大小可变

局部置换: 发生缺页时只能选进程自己的物理块进行置换。

全局置换: 可以将操作系统保留的空闲物理块分配给缺页进程,也可以将别的进程持有的物理块置换到外存,再分配给缺页进程。

所以根据以上四种,可以有一下组合:

  • 固定分配局部置换
    发生缺页只能从自己的进程在内存中的页面选出一页换出。
  • 可变分配全局置换
    只要缺页就给分配新物理块(空闲块/未锁定页面的内存块),缺页率会增加。
  • 可变分配局部置换
    根据发生缺页的频率来动态地增加或减少进程的物理块。

预调页策略: 在进程运行前,调入若干个可能访问到的页面,主要用于进程的首次调入。

请求调页策略: 进程在运行期间发现缺页时才将所缺页面调入内存。

抖动(颠簸)现象:
刚刚换出的页面马上又要换入内存,刚刚换入的页面又要换出外存,这种频繁的页面调度行为称为抖动或颠簸,产生颠簸的主要原因是进程频繁访问的页面数目高于可用的物理块数。

标签: OS

非特殊说明,本博所有文章均为博主原创。

评论啦~