Operating System (Memory Management)

Table of Contents

1 操作系统内存管理基本知识

计算机系统的主要用途是执行程序。按照冯诺依曼计算机体系,这些程序在执行时必须存在于内存中。为改善CPU使用率和对用户的响应速度,计算机必须在内存中保留多个进程。我们需要对内存进行管理,使得各个进程能够有条理地执行。

1.1 地址绑定

在源代码里我们通常用一个变量代表地址,我们可以将变量绑定到可重定位地址,加载程序再将重定位地址绑定成绝对地址。每次绑定都是从一个地址空间到另一个地址空间的映射。
绑定可以在下面三个时期的任何一个时期中进行:
(1)、编译时进行绑定:如果在编译时就知道内存的地址,那么可以直接绑定绝对地址。MS-DOS操作系统的.COM格式程序就是在编译时绑定成绝对地址的。
(2)、加载时进行绑定:如果在编译时并不知道进程将驻留在何处,在编译时必须生成可重定位代码,这时绑定需要延迟在加载时进行。
(3)、执行时进行绑定:如果进程在执行时可以从一个内存段移到另一个内存段,那么绑定必须延迟到执行时才发生。在执行时绑定需要特定硬件支持,绝大多数计算机采用执行时绑定。

1.2 逻辑地址空间和物理地址空间

什么是逻辑地址空间?CPU生成的地址通常称为逻辑地址(logical address),所有逻辑地址的集合,就是逻辑地址空间。

什么是物理地址空间?而内存单元所看到的地址,即加载到内存地址寄存器(memory-address register)中的地址,通常称为物理地址(physical address),所有物理地址的集合,就是物理地址空间。

如果在编译时或加载时进行地址绑定,则会生成相同的逻辑地址和物理地址。如果在执行时进行地址绑定会生成不同的逻辑地址和物理地址。由于绝大多数计算机采用执行时绑定,所以逻辑地址和物理地址一般是不同的。

在运行时从逻辑地址到物理地址的映射是由称为内存管理单元(MMU)的硬件来完成的。如图 1 所示。

mem-mgmt-mmu.png

Figure 1: 内存管理单元(MMU)

2 内存管理方案

内存必须容纳操作系统和各种用户进程。应该尽可能有效地分配内存的各个部分,这是通过硬件——MMU来完成的。下面介绍四种内存管理算法:连续内存分配、分页机制、分段机制、带有分页的分段。详细内容可参见《操作系统概念》第9章,该书对分页机制和分段机制的定义和优缺点表述得很好。

2.1 连续内存分配

采用连续内存分配时,每个进程位于一个连续的内存区域。随着进程的运行和结束,连续内存分配将导致严重的内存碎片问题。

内存碎片分为外部碎片和内部碎片。
外部碎片:自由内存空间里没有分配给任何进程的小片段。
内部碎片:内存以固定大小的块为单位分配,可能进程所需要的内存大于分配的内存,二者的差就是内部碎片。

除了紧缩(移动内存内容,使空闲内存合并到一起,代价比较高)方法外,下面介绍的分页机制可以解决外部碎片问题。

2.2 分页机制

分页内存管理允许进程的物理地址空间可以是非连续的。

什么是页?物理内存分为固定大小的块,称为帧(frame)。逻辑内存也分为同样大小的块,称为页。

分页机制是通过页表将逻辑地址和物理地址对应起来。

2.2.1 页式管理的优缺点

页式管理优点:它不会产生外部碎片(只会产生内部碎片),比段式管理系统的空间浪费要小得多。

页式管理缺点:页式管理系统的缺点正好和段式管理系统相反,由于页不是逻辑上独立的实体,所以处理、保护和共享都不及段式来得方便。

2.3 分段机制

从用户的观点出发,将逻辑内存和物理内存对应。

2.3.1 段式管理的优缺点

段式管理优点:段的分界与程序的自然分界相对应;段的逻辑独立性使它易于编译、管理、修改和保护,也便于多道程序共享。(保护和共享等能在段级上进行,这非常方便!)

段式管理的缺点:容易在段间留下许多空余的零碎存储空间不好利用,造成浪费。

2.4 带有分页的分段

带有分页的分段机制可以兼取页式和段式系统的优点。

2.4.1 线性地址

下面介绍一下线性地址的概念。以IA-32架构以例,它就是00000000h~ffffffffh(即0~4G)的线性结构,是32个比特位能表示的一段连续的地址,但它是一个概念上的地址,是个抽象的地址,并不存在现实之中。线性地址主要是为分页机制而产生的,如图 2 所示。

mem-mgmt-linear-address.png

Figure 2: 带有分页的分段机制

处理器在得到逻辑地址后首先通过分段机制转换为线性地址,线性地址再通过分页机制转换为物理地址。

2.5 IA-32架构的内存管理

本节很多内容参考《Intel® 64 and IA-32 Architectures Software Developer's Manual Volume 3A: System Programming Guide Part 1》第3章。

IA-32采用的是带有分页的分段机制(它的分段是必须的,分页是可选的)。

2.5.1 实模式(没有分页管理)

8086(它是16位的CPU,有16根数据线和20根地址线)的工作模式为实模式。

下面描述8086的逻辑地址如何转换为物理地址。

mem-mgmt-8086.png

Figure 3: 8086的逻辑地址转换为物理地址的过程

3 中逻辑地址由段值和偏移表示,形式为“段值:偏移”。
可见8086物理地址形成非常简单:物理地址 = 段值×16 + 偏移。
其中×16就是左移4位,如逻辑地址1111:2222H对应的物理地址为13332H(即11110+2222H)。

备注1:什么是64K限制和640K限制?
16位CPU下关于内存的使用,DOS有两个著名的限制,一是64K限制,一是640K限制。
所谓64K限制,就是DOS下连续使用的内存最大仅能达到64K(因为指针寄存器只有16位)。
所谓640K限制,8086能寻址1M的内存,下面的640K称为常规内存区给应用程序,上面的384K称为高端内存留给系统使用,这样在DOS下实际使用的内存就只有640K了。
盖茨最著名的言论——“无论对谁来说,640K内存已经足够。”盖茨于1981年作出了该表述。

备注2:16位CPU,由于其指针寄存器为16位,理论上的寻址为64KB(216),正是由于8086使用了段机制才使得8086能寻址1M内存。

备注3:80386处理器被复位或加电的时候以实模式启动,然后通过加载CR0使其中的保护模式使能位置位而进入保护模式。实模式下不能进行分页管理。

2.5.2 保护模式分段机制

把前面介绍的图 2 的内容具体到IA-32架构下可得到图 4 所示。

mem-mgmt-ia32.png

Figure 4: IA-32架构下的地址映射

逻辑地址到线性地址转换(分段机制)如图 5 所示。

mem-mgmt-ia32-segmented.png

Figure 5: IA-32架构下逻辑地址到线性地址的转换

逻辑地址为48位,由16位的选择符(Segment Selector)加上32位的偏移组成。其实图 5 和8086的物理地址的形成(参见图 6)非常相似。

mem-mgmt-8086-another.png

Figure 6: 8086的逻辑地址转换为物理地址的过程

5 和图 6 比较相似,只是IA-32架构中多了个描述符表(Descriptor Table),这是个什么东西呢?解释如下:
进程的逻辑地址空间分为两个部分,一部分为该进程私有(保存在本地描述符表LDT中),一部分为所有进程共享(保存在全局描述表GDT中,GDT在整个系统中只有一个)。

如果我们把逻辑地址到线性地址的转换画具体点,可得到图 7 所示。

mem-mgmt-ia32-segmented-detailed.png

Figure 7: IA-32架构下逻辑地址到线性地址的具体转换过程

在图 7 中,段选择子(Segment Selector)中有一个TI(Table Indicator)位,用来表示段是在GDT中还是在LDT中。

2.5.3 保护模式分页机制

分页机制(可选的)在分段机制之后进行,用来完成线性地址到物理地址的转换。常采用二级页表结构,如图 8 所示。

mem-mgmt-ia32-paged.png

Figure 8: 两级页表结构

两级页表结构中,第一级称为页目录,第二级称为页表。

注:
页目录和页表其实也都可以看成是“偏移量”。
页目录的基址是什么呢?是控制寄存器CR3。
页表的基址又是什么呢?它由CR3和页目录计算出。

如果我们把线性地址到物理地址的转换画具体点(图示名称和前面有细微差别,但表达意义一样),可得到图 9

mem-mgmt-ia32-paged-detailed.png

Figure 9: 80x86线性地址到物理地址的转换(分页机制)示意图

备注:控制寄存器CR0中有个PG位,它是分页机制的开关(分页机制是可选的),上图示意的是启用分页机制的情况。控制寄存器CR3中保存着页目录的基地址。

2.5.4 80386地址转换示意图

10 给出了80386保护模式下地址转换示意图(摘自《操作系统概念(第六版)》9.6节)。

mem-mgmt-80386.png

Figure 10: Intel 80386的地址转换

2.5.5 Tips:什么是段选择子(或段选择符)

段寄存器中的值,在实模式下被称为段值,在保护模式下被称为段选择子。


Author: cig01

Created: <2012-12-16 Sun 00:00>

Last updated: <2018-07-30 Mon 16:26>

Creator: Emacs 25.3.1 (Org mode 9.1.4)