Appearance
3.4 内存分配：离散分配方式
一、概述
引入原因
固定分区存在内部碎片
动态分区存在外部碎片
可重定位动态分区的系统开销大
基本思想
一个进程分配的内存由多个离散的空间组成。
分类——依据分配的基本单位
分页存储管理
- 页面：程序地址空间被划分成若干固定大小的片段
- 页框：物理内存被划分成相同大小的块
分段存储管理
- 以段为基本分配单位的存储管理方式
段页式存储管理
- 段内分页
二、分页存储管理
1. 程序空间和物理空间的组织
存储管理系统负责用户空间、物理空间的划分并编号。
2. 逻辑地址结构
页号+页内偏移量（页内地址）
32位机的分页存储系统逻辑地址结构示意图
3. 页号与页内地址的计算
对于某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式：
L一般为2的n次方，将A转化为二进制，低n位为页内地址，其余高位为页号。
示例
某系统的页面大小为1KB，设A=2170B，试计算其页号P与页内地址d。
答案
A=1000 0111 1010
P=10，即2
d=00 0111 1010，即122
4. 页表
- 作用：记录进程的每个页面对应的页框信息。
- 结构示例
5. 地址转换
系统能够得到要访问变量或程序的逻辑地址
指令或数据存放在物理地址中
地址转换的任务：将逻辑地址转换为物理地址
地址转换流程
根据逻辑地址分离出页面号和页内偏移
检查页面号是否非法，若非法则产生越界错误，否则继续
根据页面号检索页表，获得对应的页框号
检查页表的访问控制字段，确定访问是否合法
用页框号乘以页面大小获得其对应的起始地址，并将其送入物理地址的高端
将页内偏移送入物理地址的低端，即得到完整的物理地址
普通分页系统地址转换示意图
6. 页表的存储
页表存放在内存
PCB保存有页表的起始地址
页表寄存器存放当前运行进程的页表的起始地址
快表——设置高速缓存器来存储当前运行进程页表的部分表项(使用频度最高的表项)
7. 地址转换示例
示例1
一个系统，内存容量共256k，存储块的大小为1k，共256块，编号为0~255
第0~4块为操作系统所使用
现有2个用户作业，作业1和作业2，其逻辑地址空间分别占2k和2.5k
进入系统后，按块的大小划分分别占2页和3页
假设作业2正在运行，在第0页某单元处有一条指令：
MOV R1,[2500]2500→转化为十六进制为09C4H (二进制为0000 1001 1100 0100)
每页长度为1k，逻辑地址低10位构成页内地址：1C4H
高6位为2，形成页号p
查页表知第2页在内存第10块，与页内地址一起构成新的物理地址为：29C4H(二进制为0010 1001 1100 0100)
访问该单元，把其中的数据送入R1寄存器
示例2
某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：
| 页号 | 物理块号 |
|---|---|
| 0 | 5 |
| 1 | 10 |
| 2 | 4 |
| 3 | 7 |
则逻辑地址0A5C对应的物理地址为？
答案
内存16KB，所以物理地址14位
0A5CH=0000 1010 0101 1100
页号为10，页内地址10 0101 1100
由表得，页号2对应的物理块号为4
物理地址为：0001 0010 0101 1100
即125CH
示例3
在分页存储管理系统中，逻辑地址的结构长度为18位，其中11～17表示页号，0～10位表示页内偏移量。若有一个作业的各页依次放入2、3、7号物理块，试问：
主存容量最大可为多少K？分为多少块？每块多大？
逻辑地址1500应在几号页内？对应的物理地址是多少？
在页表中有三个页表项，分别为(0,2)，(1,3)，(2,7)
答案
逻辑地址18位，所以主存容量最大可为256KB
页号11～17位，所以分为128块
页内偏移量0～10位，所以每页2KB
1500二进制为10 1110 1110
页号0，页内地址10 1110 1110
页号0，物理块号为2，所以物理地址为1010 1110 1110
即0AEEH
8. 优缺点
优点
存在页内碎片，但碎片相对较小，内存利用率较高
实现了离散分配
无外部碎片
缺点
需要专门的硬件支持，尤其是快表
不支持动态链接，不易实现共享
三、分段存储器
1. 引入分段的原因
自然的组织
- 信息用户按照逻辑关系将程序分段，每段有自己的名字，可以根据段名来访问相应的程序段和数据段。
信息共享
- 程序和数据的共享是以信息的逻辑单位为基础的。“页”只是存放信息的物理单位，无完整的意义，不便于实现共享；段却是信息的逻辑单位，易于实现信息的共享。
信息保护
- 信息的保护基于信息的逻辑单位，故分段管理方式能更有效和方便地实现信息保护功能。
动态增长
- 某些段，特别是数据段，往往事先无法知道其大小，需要在运行中扩展其大小。
运行时动态链接
- 在程序执行中需要该目标模块时，由操作系统去找到该模块并将之装入内存并把它链接到调用者模块上——基于信息的逻辑划分，而非物理划分。
2. 逻辑空间的组织
程序的逻辑地址空间被划分为若干个段，每个段定义了一组逻辑信息。
每个段都有自己的名字。为了实现简单起见，通常可用一个段号来代替段名。
每个段都从0开始编址，并占用一段连续的地址空间。
段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。
整个作业的地址空间由于被分成多个段，因而是二维的，亦即，其逻辑地址由段号(段名)和段内偏移量所组成。
分段系统往往需要编译程序的支持。
3. 逻辑地址结构
段号+段内偏移量
分段系统的逻辑地址结构示意图
4. 物理空间的组织的分配
每个逻辑段装载到一段连续的内存区域
物理空间的组织类似动态分区系统
单纯分段系统的内存分配算法可采用首次匹配、循环匹配、最佳匹配、最差匹配等方式
动态分区是单纯分段系统的一个特例
5. 段表
作用：记录逻辑段和物理段的对应情况
6. 段表寄存器
存放段表起始地址和段表长度
7. 地址转换流程
从逻辑地址中分离出段号和段内偏移量
检查段号是否非法，若非法则产生越界错误，否则继续。
根据段号检索段表，获得对应的段首址和段长。
检查段内偏移量是否非法，若非法则产生越界错误，否则继续。
检查段表的访问控制字段，确定访问是否合法。
将段首址与段内地址相加，即可得到要访问的内存物理地址。
分段系统地址转换示意图
8. 优缺点
优点
便于程序模块化设计
便于动态链接
便于保护和共享
无内部碎片
缺点
地址转换需要硬件的支持——段表寄存器
分段的最大尺寸受到主存可用空间的限制
有外部碎片
四、分段与分页的比较
页是信息的物理单位，分页的目的是实现离散分配，减少内存的外部碎片，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。
分页存储管理系统既不易实现“共享”，也不易实现“运行时动态链接”，而分段系统易于实现。
五、段页式存储管理
1. 基本思想
页式存储管理的主要优点
- 内存利用率高
段式存储管理的主要优点
- 方便用户、易于共享、易于保护、可动态链接
段页式存储管理的基本思想：
采用分段方法组织用户程序，采用分页方法分配和管理内存。 即用户程序可以用模块化思想进行设计，一个用户程序由若干段构成。系统将内存划分成固定大小的页框，并将程序的每一段分割成若干页后装入内存。
2. 逻辑地址
段号+段内页号+页内偏移量
某程序的逻辑地址空间
3. 利用段表和页表实现地址映射
4. 地址转换流程
根据逻辑地址分离出段号、页号和页内偏移量
检查段号是否非法，若非法则产生越界错误，否则继续
根据段号检索段表，检查段表的访问控制字段，确定访问是否合法，若合法则继续，否则产生错误
根据段表获取页表长度和页表始址，检查页号是否非法，若非法则产生越界错误，否则继续
根据页表始址和页号检索页表，获得对应的页框号
用页框号乘以页面大小获得其对应的起始地址，并将其送入物理地址的高端
将页内偏移送入物理地址的低端，即形成完整的物理地址
段页式系统地址转换示意图
思考
在段页式系统中，为了获得一条指令或数据，须访问几次内存?
答案
第一次，访问段表，从中获得该段的页表首址
第二次，访问页表，从中取出逻辑地址指定的页面所在的页框号，并将该页框号和页内偏移量相加，形成指令或数据的物理地址
第三次访问内存，根据前面计算的物理地址，取出对应存储单元的指令或数据
5. 优缺点
优点
离散存储
内存利用率高
便于保护和共享，支持动态链接
无外部碎片
缺点
地址转换复杂
有内部碎片