1.内存管理概念

内存管理的基本原理和要求

主要功能

1. 内存空间的分配与回收
2. 地址转换
3. 内存空间的扩充
4. 内存共享
5. 存储保护

程序的链接与装入逻輯地址与物理地址

创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序,通常需要以下几个步骤:

1. 编译,由编译程序将用户源代码编译成若干目标模块
2. 链接，由链接程序将编译后形成的一组目标模块及它们所需的库函数链接在一起,形成一个完整的装入模块，链接方式
3. 装入，由装入程序将装入模块装入内存运行,装入方式

将用户程序变为可在内存中执行的程序的步骤

image.png

链接方式

1. 静态链接,在程序运行之前,先将各目标模块及它们所需的库函数链接成一个完整的装配模块,以后不再拆开。需要解决两个问题:
   1. 修改相对地址,编译后的所有目标模块都是从0开始的相对地址,当链接成一个装入模块时要修改相对地址
   2. 变换外部调用符号,将每个模块中所用的外部调用符号也都变换为相对地址
2. 装入时动态链接,将用户源程序编译后所得到的一组目标模块,在装入内存时,采用边装入边链接的方式
3. 运行时动态链接,对某些目标模块的链接,是在程序执行中需要该目标模块时才进行的。凡在执行过程中未被用到的目标模块,都不会被调入内存和被链接到装入模块上。

提示

• 分段存储把整个程序划分成多个模块和运行时动态连接吻合

装入方式

1. 绝对装入,只适用于单道程序环境。在编译时,若知道程序将驻留在内存的某个位置,则编译程序将产生绝对地址的目标代码。通常情况下在程序中采用的是符号地址,编译或汇编时再转换为绝对地址。
2. 可重定位装入，根据内存的当前情况,将装入模块装入内存的适当位置。在装入时对目标程序中指令和数据地址的修改过程称为重定位,又因为地址变换通常是在进程装入时一次完成的,故称为静态重定位。作业一旦进入内存,整个运行期间就不能在内存中移动,也不能再申请内存空间。
3. 动态运行时装入，也称动态重定位。装入程序把装入模块装入内存后,并不立即把装入模块中的相对地址转换为绝对地址,而是把这种地址转换推迟到程序真正要执行时才进行。这种方式需要一个重定位奇存器的支持

提示

• 固定分区采用静态重定位
• 可变分区可能会采用紧凑技术，所以进程存放位置可能会改变，因此不能采用静态重定位
• 页式管理和段式管理都是动态重定位，因为他们的逻辑地址到物理地址的转换都是在指令执行时才进行的

image.png

逻辑地址与物理地址

• 编译后,每个目标模块都从 0号单元开始编址,这称为该目标模块的相对地址(或逻辑地址)
• 进程在运行时,看到和使用的地址都是逻辑地址
• 用户程序和程序员只需知道逻辑地址,而内存管理的具体机制则是完全透明的。不同进程可以有相同的逻辑地址,因为这些相同的逻辑地址可以映射到主存的不同位置
• 物理地址空间是指内存中物理单元的集合,它是地址转换的最终地址
• 当装入程序将可执行代码装入内存时,必须通过地址转换将逻辑地址转换成物理地址,这个过程称为地址重定位

进程的内存映像

• 代码段:即程序的二进制代码,代码段是只读的,可以被多个进程共享
• 数据段:即程序运行时加工处理的对象,包括全局变量和静态变量
• 进程控制块(PCB):存放在系统区。操作系统通过 PCB 来控制和管理进程
• 堆:用来存放动态分配的变量。通过调用 malloc 函数动态地向高地址分配空间
• 栈:用来实现函数调用。从用户空间的最大地址往低地址方向增长

内存保护

1. 设置一对上、下限寄存器
2. 采用重定位寄存器(又称基地址寄存器)和界地址寄存器(又称限长寄存器)，重定位寄存器含最小的物理地址值,界地址寄存器含逻辑地址的最大值^[1]

内存共享

并不是所有的进程内存空间都适合共享,只有那些只读的区域才可以共享。可重入代码又称纯代码,是一种允许多个进程同时访问但不允许被任何进程修改的代码。但在实际执行时,也可以为每个进程配以局部数据区,把在执行中可能改变的部分复制到该数据区,这样,程序在执行时只需对该私有数据区中的内存进行修改,并不去改变共享的代码。

内存分配与回收

覆盖与交换^[2]

警告

覆盖与交换在考研大纲中已经被删除

覆盖

• 把用户空问分成一个固定区和若干覆盖区。将经常活跃的部分放在固定区, 其余部分按调用关系分段
• 首先将那些即将要访问的段放入覆盖区,其他段放在外存中,在需要调用前,系统再将其调入覆盖区,替换覆盖区中原有的段
• 覆盖技术对用户和程序员不透明

交换

把处于等待状态(或在 CPU 调度原则下被剥夺远行权利)的程序从内存移到辅存,把内存空间腾出来,这一过程又称换出;把准备好竞争 CPU 运行的程序从辅存移到内存,这一过程又称换入。第2 章介绍的中级调度采用的就是交换技术。

提示

• 交换技术主要在不同进程(或作业)之问进行,而覆盖则用于同一个程序或进程中
• 现代操作系统是通过虛拟内存技术来解决的,覆盖技术则已成为历史;而交换技术在现代操作系统中仍具有较强的生命力

连续分配管理方式

单一连续分配

内存在此方式下分为系统区和用户区,系统区仅供操作系统使用,通常在低地址部分;在用户区内存中,仅有一道用户程序,即整个内存的用户空间由该程序独占。

固定分区分配

• 分区大小相等
• 分区大小不等

动态分区分配

• 又称可变分区分配,它是在进程装入内存时,根据进程的实际需要,动态地为之分配内存, 并使分区的大小正好适合进程的需要。因此,系统中分区的大小和数目是可变的。
• 动态分区在开始时是很好的,但随着时间的推移,内存中会产生越来越多小的内存块,内存的利用率也随之下降
• 克服外部碎片可以通过紧凑技术来解决

分配策略

1. 首次适应(First Fit) 算法。空闲分区以地址递增的次序链接。分配内存时,从链首开始顺序查找,找到大小能满足要求的第一个空闲分区分配给作业。
2. 邻近适应(Next Fit)算法。又称循环首次适应算法,由首次适应算法演变而成。不同之处是,分配内存时从上次查找结束的位置开始继续查找。
3. 最佳适应(Best Fit)算法。空闲分区按容量递增的次序形成空闲分区链,找到第一个能满足要求且最小的空闲分区分配给作业,避免“大材小用”。
4. 最坏适应(Worst Fit) 算法。空闲分区以容量递减的次序链接,找到第一个能满足要求的, 即最大的分区,从中分割一部分存储空间给作业。

image.png

碎片

• 内部碎片，分配给某进程的内存区域中，如果有些部分没有用上。
• 外部碎片，是指内存中的某些空闲分区由于太小而难以利用。

基本分页存储管理

基本概念

将内存空间分为一个个大小相等的分区（比如：每个分区4KB），每个分区就是一个“页框”（页框=页帧=内存块=物理块=物理页面）。每个页框有一个编号，即“页框号”（页框号=页帧号=内存块号=物理块号=物理页号），页框号从0开始。

将进程的逻辑地址空间也分为与页框大小相等的一个个部分,每个部分称为一个“页”或“页面” 。每个页面也有一个编号， 即“页号”，页号也是从0开始

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。

各个页面不必连续存放，可以放到不相邻的各个页框中。

进程在执行时,以块为单位逐个申请主存中的块空间。

进程只会在为最后一个不完整的块申请一个主存块空问时,才产生主存碎片,所以尽管会产生内部碎片,但这种碎片相对于进程来说也是很小的,每个进程平均只产生半个块大小的内部碎片(也称页内碎片)。

提示

进程的最后一个页面可能没有一个页框那么大。也就是说，分页存储有可能产生内部碎片，因此页框不能太大，否则可能产生过大的内部碎片造成浪费

地址结构

页号$P$	页内偏移量$W$

地址长度为 32位, 其中0~11位为页内地址,即每页大小为 4KB;12~31位为页号,即最多允许$2^{20}$页

页表

• 为了便于在内存中找到进程的每个页面所对应的物理块,系统为每个进程建立一张页表,它记录页面在内存中对应的物理块号,页表一般存放在内存中。
• 页表的作用是实现从页号到物理块号的地址映射

页表占内存大小

页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组），所以只有块号占内存

页表的作用

基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。
通常会在系统中设置一个页表寄存器(PTR),存放页表在内存中的起始地址F和页表长度M。
进程未执行时，页表的始址和页表长度放在进程控制块(PCB)中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

分页存储管理系统中的地址变换机构

设页面大小为$L$,逻辑地址$A$ 到物理地址$E$的变换过程如下(假设逻辑地址、页号、每页的长度都是十进制数):

1. 计算页号$P(P=A/L)$和页内偏移量$W(W=A\%L)$。
2. 比较页号$P$和页表长度$M$,若$P\ge M$,则产生越界中断^[3],否则继续执行。
3. 页表中页号$P$对应的页表项地址=页表始址$F$+ 页号$P$ x 页表项长度,取出该页表项内容$b$,即为物理块号。注意区分页表长度和页表项长度。页表长度是指一共有多少页,页表项长度是指页地址占多大的存储空间。
4. 计算$E=b\times L+W$,用得到的物理地址 $E$ 去访问内存

具有快表的地址变换机构

在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器一一快表,又称相联存储器(TLB),用来存放当前访问的若干页表项,以加速地址变换的过程。与此对应,主存中的页表常称为慢表。

具有快表的地址变换机构

两级页表

为查询方便,顶级页表最多只能有 1个页面，因此顶级页表总共可以容纳$4KB/4B=1K$个页表项,它占用的地址位数为 $\log_{2}1K =10$ 位,而之前己经计算出页内偏移地址占用了 12 位,因此一个 32 位的逻辑地址空间就剩下了 10 位,正好使得二级页表的大小在一页之内,这样就得到了逻辑地址空间的格式

一级页号	二级页号	页内偏移

二级页表结构示意图

注意

• 若分为两级页表后，页表依然很长，则可以采用更多级页表，一般来说各级页表的大小不能超过一个页面
  

• 两级页表的访存次数分析（假设没有快表机构）需要3次，n级需要n+1次

基本分段存储管理

【课件】3.1.5基本分段存储管理方式

---

image.png

image.png

分段分页区别

• 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管
  理上的需要，完全是系统行为，对用户是不可见的；段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
• 页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
• 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址；分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
• 分段比分页更容易实现信息的共享和保护。

段页式管理

image.png

段号S	页号P	页内偏移量W

注意

在一个进程中,段表只有一个,而页表可能有多个

image.png

---

1. 加载重定位寄存器和界地址寄存器时必须使用特权指令,只有操作系统内核才可以加载这两个存储器。 ↩︎

2. 大纲已删除 ↩︎

3. 注意取等号的时候也会越界，因为页号从0开始 ↩︎