物理内存管理


概述

操作系统内存管理的作用

  • 抽象:将物理地址抽象为逻辑地址,这样使用者在编写代码时不需要关心程序实际要占用的内存的地址,不同的程序都从逻辑地址0开始就可以。
  • 保护:每个进程都有自己独立的地址空间,每个进程只能访问自己的地址空间,尽管不同进程的地址空间可能在内存中是连续存放的
  • 共享:不同进程可以访问相同的内存,不同的进程之间有一些代码是相同的,比如说系统的内核代码,如果每个进程的空间是保护的,系统内核代码就要存多份,会造成内存的浪费,因此需要将保护和共享统一起来,尽管这两项要求是矛盾的
  • 虚拟化:得到更大的地址空间,不同进程的地址空间存放在内存中不用的位置,但在每个进程自己的角度看,因为是从逻辑地址0开始的,相当于自己独占了整个内存空间,甚至还可以加上外存,使进程的逻辑地址空间要大于内存的空间

操作系统的内存管理方式

重定位

早期的计算机,编写程序直接使用内存的物理地址,程序中数据存放在什么位置,在内存中就存放在什么位置,这种方法导致程序只能在特定的计算机上运行。为了使得程序更加具有通用性,可以程序编写过程中使用一个地址,实际在内存中使用另一个地址,在程序执行时,通过重定位,将程序使用的地址映射到内存中的地址,这样一来,只要改变映射关系,程序在内存中的位置也随之改变。

分段

程序内部可以分成三个相对独立的部分:数据、代码和堆栈,不会从堆栈直接访问代码段的内容,也很少由从代码段直接访问数据段的内容,因此,可以将存储程序的整个连续的内存块分为3段,段与段之间不要求连续,这样需要的连续内存空间就变小了。

分页

分段得到的段与段之间不需要连续,但每个段仍需要连续的内存空间进行存放,这要求仍然很高。此时可以将整个内存分成固定大小的块,称之为,内存与页的关系相当于存储体与存储单元之间的关系。页的大小一般为4K。

虚拟存储

程序在没有运行时实际上是存放在硬盘(也就是外存)上的,内存和硬盘之间的数据交换是由操作系统完成的,作为使用者,并不关心系统内部是如何交换数据的,我们只需要看到一个可以存放程序数据的空间(不关心具体存在内存还是硬盘),这个逻辑上的空间是可以大于真实的物理内存的空间的,这就是虚拟存储,虚拟存储的地址就是逻辑地址。

所有的这些实现都高度依赖于计算机的硬件,比如MMU(存储管理单元

空间地址和地址生成

物理地址空间

物理地址空间就是硬件支持的地址空间,就是系统总线中地址总线表示的物理地址空间。

物理地址的起始是地址0,最大编号为2n-1,n为地址总线的根数。每个内存单元都有唯一的编号,但这个编号对于使用者来说无法利用,因为你无法得知你的程序会放在内存中的哪个位置。

逻辑地址空间

逻辑地址是在CPU运行的进程看到的地址,即CPU自己生成的地址。逻辑地址空间就是所有程序生成的逻辑地址的集合。

逻辑地址的起始地址是0,最大地址就是程序信息存储所需要的最大地址,称为MAXprog

当程序加载到内存进行执行,程序变成进程,此时在程序的可执行文件里面,地址0到MAXprog就是此程序的逻辑地址空间,再通过重定位等方式将逻辑地址映射到物理地址。

逻辑地址空间是绑定到单独的一套物理地址空间的

逻辑地址的生成

  • 程序源代码:源代码中一个程序P,P中有一个调用函数foo,实际上程序名或者函数名指的就是地址
  • 经过编译,得到汇编码:程序源码中的操作部分(比如加减乘除)变成了机器能够识别的指令,但地址部分仍然是字符,机器无法识别
  • 经过汇编,得到机器码:汇编码的地址部分由字符变成了逻辑地址,P程序开始地址为0,调用foo就是跳转到foo的地址75
  • 进行链接:程序运行过程中还可能会利用到其他模块的函数,比如输入输出函数,但其他的模块的位置并不清楚,此时要将需要的库函数与程序的机器码连接到一起,组成一个线性序列,此时的地址仍然是逻辑地址
  • 程序加载到内存(重定位):经过编译汇编连接过程后会得到程序的可执行文件,运行时需要加载到内存中,可执行文件内的地址是从0开始的,但加载到内存中可以放在任意位置,这就需要进行重定位,将逻辑地址转换为实际存放的内存中的地址

地址生成的时机

在上面的图示中,从源代码到生成存放在内存中的地址要经过四个过程,在最后的加载时生成了内存地址,其实除了加载过程,其他的过程也可以作为生成内存地址的时机。

  • 编译时:如果已知程序在内存中存放的起始位置,可以在编译时直接将内存地址写入,但如果程序的其实地址改变,需要重新编译。这种情况用在手机中的功能机,不允许自己往手机里添加额外的软件
  • 加载时:如果编译时不知道程序的起始位置,编译器需要生成可重定位的代码,在加载时,根据可执行文件内的重定位表生成绝对地址。如果起始地址发生变化,只需要重新加载程序就行。现代的智能手机就是这种情况
  • 执行时:前面两种方式要求程序在内存中要用一块连续的内存块存放,而且在程序的执行过程中不能移动位置,因为绝对地址已经生成了,如果移动位置就会出错。在执行时才生成绝对地址就使得程序在执行时也可以移动位置。这种情况需要地址转换(映射)硬件的支持

整个地址生成的流程:

1.CPU:

  • ALU:需要逻辑地址的内存内容
  • MMU:进行逻辑地址和物理地址的转换
  • CPU控制逻辑:给总线发送物理地址请求

2.内存:

  • 发送物理地址的内容给CPU
  • 接受CPU的数据到物理地址

3.操作系统:

  • 建立逻辑地址LA和物理地址PA的映射

地址检查

连续内存分配

连续内存分配和内存碎片

  • 连续内存分配是指给进程分配一块不小于指定大小的连续的物理内存区域
  • 内存碎片:在分配给不同进程的内存块之间的空闲内存,这些空闲部分如果无法被利用,就称为内存碎片

内存碎片可以分成两个部分:

  • 外部碎片:分配单元之间的未被使用内存
  • 内部碎片:分配单元内部的未被使用内存,这取决于分配单元大小是否要取整(2的整数次幂,便于管理),比如进程要请求510字节的内存,但内存会分配给进程512字节的空间,这样其中的2字节就会空闲下来,这就是内碎片

动态分区分配

当程序被加载执行时,会分配一个进程指定大小可变的分区(块、内存块),分区的地址是连续的。当进程结束时,进程会把分配到的内存块归还给操作系统,以便再分配给新的进程。

为了实现这种功能,操作系统要维护一个数据结构,包含当前所有进程的已分配分区,以及所有的空闲分区。

动态分区分配的方法有很多,常用的策略有最先匹配(First-fit),最佳匹配(Best-fit),最差匹配(Worst-fit)。

最先匹配

思路:分配第一个足够大的块,分配n个字节,使用第一个可用的空间比n大的空闲块

原理&实现
  • 空闲分区列表按地址顺序排序
  • 分配过程中,搜索一个合适的分区
  • 释放分区时,检查是否可与临近的空闲分区合并
优缺点
  • 优点:实现简单;在高地址空间有大块的空闲分区

  • 缺点:会产生外部碎片,分配大块时较慢,因为大的空闲块都在分区列表的后面,要一直搜索

最佳匹配

思路:分配足够小的足够大的分区,分配n字节分区时,查找并使用不小于n的最小空闲分区

原理&实现
  • 空闲分区列表按照大小排序
  • 分配时,查找一个合适的分区
  • 释放时,查找并且合并临近的空闲分区(如果找到)
优缺点

优点:

  • 当大部分分配的尺寸较小时,效果很好
  • 可避免大的空间分区被拆分
  • 可减小外部碎片的大小,每次分配都是比所需空间大最小的空闲块
  • 相对简单

缺点:

  • 产生外部碎片
  • 释放分区时较慢
  • 容易产生很多无用的小碎片

最差匹配

思路:分配最大的分区,分配n个字节,使用尺寸不小于n的最大空闲分区

原理&实现
  • 空闲分区列表由大到小排序
  • 分配时,选最大的分区
  • 释放时,检查是否可以与邻近的空闲分区合并,进行可能的合并,并调整空闲分区列表顺序
优缺点

优点:

  • 中等大小的分配较多时,效果最好
  • 避免出现太多的小碎片

缺点:

  • 释放分区较慢
  • 产生外部碎片
  • 容易破坏大的分区,因此后续难以分配大的分区

碎片整理

碎片整理:通过调整进程占用的分区位置来减小或避免分区碎片

碎片整理的方法

紧凑

通过移动分配给进程的内存分区,以合并外部碎片

条件:所有的应用程序可动态重定位

如果采用紧凑的办法,要考虑两个问题:

  • 移动的时间:进程处于运行状态时不能搬动,一般处于等待状态搬动
  • 开销:最简单的合并方法是将所有进程移到内存的一端,所有的空闲区域移动到内存的另一端,形成一个大的空闲块,但这种方法开销较大
分区对换

通过抢占并回收处于等待状态进程的分区,以增大可用的内存空间。

具体操作是如果有新的进程进入,但内存空间不够的情况下,可以将处于等待状态的进程暂时从内存中交换到外部存储上,以空出内存空间供新的进程使用,等到换出的进程运行时,再从外存换回内存。

Linux系统的交换(swap)区的目的就是进行分区对换

伙伴系统

伙伴系统(Buddy System)是连续内存分配的一种方法,它比较好的折中了分配和回收过程中带来的合并和分配块的位置以及碎片问题。

具体过程

  • 设整个可分配的分区大小为2u

  • 当需要的分区大小为2u - 1 < s < 2u 时,把整个块分配给该进程。

    如果s < 2i - 1时,无法将整个大小为2i大小的块分给进程,此时要将这个空闲块划分成两个大小为2i - 1 - 1的空闲分区,再次比较大小,重复划分过程,直到2i - 1 < s <= 2i,将一个空闲块分给进程

数据结构

  • 空闲块按大小和起始地址组织成二维数组
  • 初始状态:只有一个大小为2u的空闲块

分配过程

  • 由小到大在空闲块数组中找到最小的可用空闲块
  • 如果空闲块过大,对可用空闲块进行二等分,直到得到合适的可用空闲块

释放过程

  • 把释放的块放入空闲块数组
  • 合并满足合并条件的空闲块

合并条件

  • 大小相同 2i
  • 地址相邻
  • 起始地址较小的块的起始地址必须为2i + 1的倍数

整个分配及合并过程如图所示:

其实从上图所示的过程中可以发现,整个空闲块的划分相当于一个树状结构,二等分之后的空闲块分别为原始空闲块的左右子块(左右节点),合并时只有是兄弟子块(兄弟节点)的两个空闲块才能合并,比如图中B和D的内存块就不能合并。

Buddy System主要用来做内核里的存储分配


文章作者: likai
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 likai !
评论
 上一篇
物理内存管理(二) 物理内存管理(二)
上一篇文章详细讲了物理内存的连续分配,这篇文章讲一下物理内存的非连续分配 非连续内存分配的需求背景连续分配的缺点: 分配给程序的物理内存必须连续 存在外碎片和内碎片 内存分配的动态修改困难 内存利用率较低 非连续分配的设计目标:提高
2020-07-30
下一篇 
数据结构之链表 数据结构之链表
概念python内置的数据结构列表是一种顺序表,列表在内存中占用一段连续的内存空间,列表的第一项数据的地址就是列表的地址,数据项的下标其实可以看做是相对于列表起始地址的偏移量,这也就是为什么列表的查询的时间复杂度是O(1)的,而插入inse
2020-07-28
  目录