查找和分配算法比较(1)
• 从搜索空闲区速度及主存利用率来看, 最先适用分配、下次适应分配和最佳 适应算法比最坏适应算法性能好。
• 如果空闲区按从小到大排列,则最先适 用分配算法等于最优适应分配算法。
• 如果空闲区按从大到小排列,则最先适 用分配算法等于最坏适应分配算法。
查找和分配算法比较(2)
逻辑地址空间
0 ...
100 LOAD A 200
...
200 3456
...
300
BR 1000
VR 200 +
物理地址空间
... 0
LOAD A 200 1100
...
34......56内存时，一次性实现逻辑 地址到物理地址的转换，以后不再转换
200
Load A 200 3456
1100 Load A 200
地址映射
1200
3456 。 。
• 逻辑地址（相对地址，虚地址）
用户的程序经过汇编或编译后形成目标代码， 目标代码通常采用相对地址的形式，其首地址为0， 其余指令中的地址都相对于首地址而编址 不能用逻辑地址在内存中读取信息
• 物理地址（绝对地址，实地址）
速度更快
主要问题：
CPU 寄存器
Cache 主存/内存 磁盘/外存
CPU自身的运算速度很快，内 存、外存的访问速度受到限 制
操作系统协调各存储器的使用
使 CPU的运算速度 得到发挥
成本更低 容量更大
2.内存/主存
由存储单元（字节或字）组成的一维连续的地址空间
•用来存放当前正在运行程序的代码及数据 •是程序中指令本身地址所指的、亦即程序计数器所
标志 未分配 未分配 未分配
空 空
标志 P1 P2 P3 P4 P5 P6
内存分配策略
（1）首先适应算法 将最先找到的第一个满足长度的空闲区分配给
进程 （2）最佳适应算法
将满足长度的、最小空闲区分配给进程 （3）最坏适应算法
将满足长度的、最大空闲区分配给进程
可变分区管理的分配算法
1）最先适应分配算法 2）下次适应分配算法 3) 最优适应分配算法 4）最坏适应分配算法 5) 快速适应分配算法
• 空闲区按从小到大排列时, 最先适 用分配算法能尽可能使用低地址区, 从而高地址空间有较大的空闲区容 纳大的作业。
• 下次适应分配算法会使存储器空间 得到均衡使用。
• 最优适应分配算法的主存利用率最 好,但可能会导致空闲区分割下来 的部分很小。
查找和分配算法比较(3)
• 处理某种作业序列时, 最坏适应分 配算法可能性能最佳,它选择最大空 闲区,使得分配后剩余下来的空闲区 不会太小,仍能用于再分配。
指的存储器（可以由处理器直接访问！）
分为系统区与用户区 • 系统区：用于存放操作系统 • 用户区：用于装入并存放用户程序和数据
3. 存储管理的目的
• 充分利用内存，为多道程序并发执行提供存储基础 • 尽可能方便用户使用
自动装入用户程序 用户程序中不必考虑硬件细节 • 系统能够解决程序空间比实际内存空间大的问题 • 程序在执行时可以动态伸缩 • 内存存取速度快 • 存储保护与安全 • 共享与通信 • 了解有关资源的使用状况 • 实现的性能和代价
内存中存储单元的地址，可直接寻址
• 地址转换
为了保证CPU执行指令时可正确访问存储 单元，需将用户程序中的逻辑地址转换为运行时由 机器直接寻址的物理地址，这一过程称为地址映射
原因: 当程序装入内存时, 操作系统要为该程序 分配一个合适的内存空间，由于程序的逻辑地址与 分配到内存物理地址不一致, 而CPU执行指令时， 是按物理地址进行的，所以要进行地址转换
限长寄存器：存放长度
（或 上界寄存器/下界寄存器）
• 防止操作越权
对于允许多个进程共享的存储区域，每个进程 都有自己的访问权限。如果一个进程对共享区域的 访问违反了权限规定，则发生操作越权，即读写保 护
（4）内存扩充 通过虚拟存储技术实现
用户在编制程序时，不应该受内存容量限制， 所以要采用一定技术来“扩充”内存的容量，使用户 得到比实际内存容量大的多的内存空间
一般在装入内存时由软件完成
• 动态地址转换
变换
在程序运行过程中要访问数据时再进行地址
即在逐条指令执行时完成地址映射
一般为了提高效率，此工作由硬件地址映射机制 来完成。
硬件上需要一对寄存器的支持
5. 单一用户（连续区）存储管理方案
单用户系统在一段时间内，只有一个进 程在内存，故内存分配管理十分简单，内存 利用率低。内存分为两个区域，一个供操作 系统使用，一个供用户使用
0xFFF...
用户程序
位于RAM中的 操作系统
位于RAM中的 操作系统
0
用户程序 0
ROM中的 设备驱动程序
用户程序
位于RAM中的 操作系统
0
二、分区存储管理
满足多道程序运行的、最简单的存储管理方案
系统把内存用户区划分为若干分区 分区大小可以相等，也可以不等
一个进程占据一个分区 •固定分区 •可变分区
标志 未分配 未分配 未分配
空 空
标志 P1 P2 P3 P4 空 空
0K 15K
38K 48K
68K 80K 85K 98K 110K 120K
空闲区表
始址 15K 48K 98K
长度 23K 20K 12K
已分配区表
始址 0K 38K 68K 110K 80K 85K
长度 15K 10K 12K 10K 5K 13K
操作系统 作业1 作业2 作业3 空闲区
操作系统 作业1 作业2 作业3 作业4
空闲区
• 分区的保护 设置界地址寄存器 保护键
• 优点 便于动态申请内存 便于共享内存
• 缺点 碎片问题(外碎片)，内存利用率不高 受实际内存容量限制
4. 存储管理的任务
（1）内存空间的管理、分配与回收 （2）存储共享 （3）存储保护 （4）内存扩充 （5）地址转换
（1）内存空间的管理、分配与回收
– 记录内存的使用情况 ——设置相应的内存分配表 （内存分配、回收的依据）
– 内存空间划分问题？ 静态或动态，等长或不等长
• 记录分配状态（内存分配表）的方法 – 位示图：用一位代表一个页面（0：空闲，1：占用）
• 内存分配
静态方式：程序要求的内存空间在运行前确定 动态方式：程序要求的内存空间在运行前及运行
过程中确定
• 内存回收
（2）存储共享 两个或多个进程共用内存中相同区域
目的： 节省内存空间，提高内存利用率 实现进程通信（数据共享）
共享内容： 代码共享，要求代码为纯代码 数据共享
（3）存储保护
为多个程序共享内存提供保障，使在内存中 的各道程序，只能访问它自己的区域，避免各道程 序间相互干扰，特别是当一道程序发生错误时，不 致于影响其他程序的运行
根据分配表查找合适的分区 执行完毕时释放内存
多个等待队列 分区4
分区3
单个等待队列
分区2
分区1 操作系统
分区4
分区3 分区2
分区1 操作系统
2. 可变分区
• 基本思想 ➢内存不是预先划分好的 ➢作业装入时，根据作业的需求和内存 空间的使用情况来决定是否分配 ➢若有足够的空间，则按需要分割一部 分分区给该进程；否则令其等待内存 空间
通常由硬件完成保护功能，由软件辅助实现
• 防止地址越界
每个进程都有自己独立的进程空间，如 果一个进程在运行时所产生的地址在其地址空间之 外，则发生地址越界
当程序要访问某个内存单元时，由硬件 检查是否允许，如果允许则执行，否则产生地址越 界中断，由操作系统进行相应处理
一般由硬件提供一对寄存器：
基址寄存器：存放起始地址
1 0 …... 1 …... 0
第0页第1页
第i页
第n-1页
– 空闲页面表：包括首页面号和页面个数，连续若干 的页面作为一组登记在表中
– 空闲块表：空闲块首址和空闲块长度，没有记录的 区域即为进程所占用
• 程序与内存的对应关系
连续性
离散性（存放方式）
一次性
多次性（装入方式）
驻留性
交换性（退出方式）
第九讲 存储(内存)管理基础
处理器： 摩尔定律：每18个月翻一番 （集成
度->速度） ?
内存： 帕金森定律:
内存有多大，程序就有多长
内容
一、概述 二、分区存储管理
一、概述
1. 存储体系 2.内存/主存 3. 存储管理的目的 4. 存储管理的任务 5. 单一用户（连续区）存储管理
方案
1. 存储体系
• 最先适应算法简单、快速，在实际 的操作系统中用得较多；其次是最 佳适应算法和下次适应算法。
可变分区地址转换与存储保护
限长寄存器 基址寄存器
限长
基址
操作系统区
空闲分区1
CPU
逻辑地址
<限长
用户作业1 绝对地址 空闲分区2
越界中断
• 内存回收 当某一块归还后，前后空间合并，修改内存空 闲块表
考虑：上邻、下邻、上下相邻、上下不相邻
1. 固定分区
预先把可分配的内存空间分割成若干个连续 区域 每一区域称为分区
每个分区的大小可以相同也可以不同 分区大小固定不变 每个分区装一个且只能装一个作业
内存管理：设置内存分配表
分区号 起始地址 长度 状态 进程
1
0
8k
占用 P1
2
8k
16k
空闲
3
24k
32k
占用 P2
4
56k
64k
空闲
5
120k 128k 占用 P3
• 内存管理 ➢未分配（空闲）区表 记录了空闲区的起始地址和长度 ➢已分配区表 记录了已分配区的起始地址、长度和 程序