[第五章]存储器管理

• 磁盘属于设备管理，功能属于文件管理

背景知识

对换

• 把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间；

• 再把已具备运行条件的进程或进程所需的程序或数据，调入内存。

类型

• 整体对换

• 页面（分段）对换
• 为了支持虚拟存储系统

覆盖

• 只在内存中保留那些在任何时间都需要的指令和数据

• 程序的不同部分在内存中相互替换。

• 程序员声明覆盖结构，操作系统无需特别支持

• 应用于早期的操作系统

存储器的层次结构

• 存储区

• 高速缓存

• 主存

• 磁盘缓存（硬件来说属于外存，如果作为虚拟内存，功能上属于内存）

• 磁盘

• 可移动存储介质

内存管理目的

• 方便性

• 合理性

• 有效性

程序的编译和链接

• 编译 编译程序→目标模块

• 链接 目标模块和库函数一起装入模块

• 装入 程序将模块装入内存

装入方式

• 绝对装入
• 装入模块中的绝对地址装入内存
• 仅适用单道环境

• 可重定位装入方式
• 把逻辑地址（程序地址）变换成物理地址（内存地址），让多程序得以执行
• 地址映射，将装入模块装入到内存的适当地方

• 动态运行时装入
• 基地址寄存器BR、程序地址寄存器VR、内存地址寄存器MR

程序的链接

• 静态链接
• 程序运行前
• 地址映射，修改相对地址

• 动态链接
• 边装入边链接

• 运行时链接
• 执行时需要

连续分配存储管理方式

单一连续分配

• 内存中只有一个程序

• 操作系统和用户共享RAM

• 嵌入式操作系统使用

固定分区分配

• 划分为若干个固定大小的分区，每个分区一个作业

• 分区方法：大小相等，不等

• 内存分配管理：分区使用表

• 作业大小和频率若不知道，分区和作业相差可能很大，影响系统效率

可变（动态）分区分配

数据结构

分配算法

• 首次适应法
• 划分：空闲首址递增 次序组织空闲区表（队列）
• 回收：按释放区首地址查询表，若有相邻空闲，合并空闲区
• 特点
• 找第一个满足的分区
• 地址内存使用频繁
• 缺点：有外零头
• 优点：高地址端可能保留大的分区

• 循环首次适应
• 从一个查找指针开始（上次查找的空闲区下一个）
• 效率比首次适应高

• 最佳适应
• 按照从小到大排序
• 满足要求最小的空闲区
• 缺点：产生大量碎片
• 优点：保留大空间

• 最坏适应法
• 从大到小分配
• 缺点：后面没有大的空闲区了
• 优点：碎片少

索引式搜索算法

• 快速适应
• 从小到大排序，建立索引

• 伙伴算法
1. 分区大小为2的k次幂，不同区大小形成k个链
2. 分配长度为n的空间，就找2刚好比n大
3. 如果找不到就分割比n大的2空间，然后分割成2.的大小并补充到伙伴表中
4. 回收：合并

• 哈希算法
• 空闲区大小为关键字的哈希表

回收

• 相邻空闲区合并，合并后插入相应位置，没有相邻new一个表目

• 紧凑；重定位，移动相邻不远的空闲区

非连续(离散)分配

分页存储管理

• 划分大小相等的部分，称页

• 大小为页长

• 页内地址是相对于首地址

• 访问两次内存

• 逻辑地址（页面）：（高位页号，低位页内偏移量）

• 根据页的大小划分为物理地址为大小相等的块（内存块、物理页面、页框）

• 页表存放了页和物理块之间的转化关系

内存分配

• 逻辑相邻，物理不一定相邻

• 逻辑地址长度一定，页号范围影响页内地址大小

页表

• 下标为页号

• 为每个进程建立一个页表

• 长度和首地址放在PUB中

• 运行进程的页表驻留内存，其首地址和长度由页表长度寄存器、页表始址寄存器指示

页大小

• 2

• 太大浪费

• 太小页表过长

页内地址映射

• 2K+452bit
• 放到第2K中意味着前两页已经放满
• 页号0 - 1k
• 页号1- 1k
• 页号2页内地址为452bit →块号7 →7K+452bit

• 给出的地址字为10进制，则用公式：

• 例如程序地址为8457， 页长为4KB，则8457/4096可得：商为2，余数为256。

存储器管理中的信息保护

• 越界
• 0≤页号<程序地址空间的页数

• 越权
• 存取控制字段：读/写、只读和只执行

快表

• 相联(联想)存储器

• 页号；内存块号；标识位；淘汰位

• 快表查询时间

• 命中率a

• 查询页表所需时间t

慢表

两级页表和多级页表

反置页表

小结

• 优点
• 解决外部碎片问题
• 便于管理

• 缺点
• 存在内部碎片
• 不容易实现共享

分段存储管理

• 根据逻辑管理划分为若干个程序段

• 逻辑地址：（高位段号，低位段内地址）

• 访问两次内存

• 内存分配：以段为单位分配，每个段在内存中占连续空间，但之间可以不连续存放

• 内存划分：内存空间被动态划分为若干个长度不同的区域，称为物理段

段表

• 段号是下标

• 每一进程有个段表

• 存放在进程自己的PCB

段地址映射

越界

• 段号越界

• 段内偏移量越界

快表

分段系统中对程序和数据的共享

小结

• 优点
• 段为信息逻辑单位，便于动态申请
• 管理和使用统一化
• 便于信息共享
• 便于动态链接

• 缺点
• 产生外部碎片

• 分段与分页技术的比较

段页存储管理

• 访问三次内存

• 逻辑地址

存储管理方式