第四章 存储器管理
一、存储器的层次结构
1.1 多层结构的存储器系统
1. 存储器的多层结构
寄存器-高速缓存-主存-磁盘缓存-固定磁盘-可移动存储介质
2. 可执行存储器
寄存和主存称为可执行存储器
1.2 主存储器与寄存器
1.3 高速缓存和磁盘缓存
1. 高速缓存
2. 磁盘缓存
磁盘缓存用于缓解磁盘的 I/O 速度和主存的访问素的的不匹配，用于暂时存放频繁使用的一部分的磁盘数据和信息以减少访问磁盘的次数
磁盘缓存和高速缓存不同，本身并不是一种实际存在的存储器，而是利用主存中的部分存储空间暂时存放从磁盘中读出或写入的信息
二、程序的装入和链接
2.1 程序的装入
1. 绝对装入方式
2. 可重定位装入方式
将指令中的逻辑地址与本程序在内存中的起始地址相加得到正确的物理地址
地址变换通常在进程装入时一次完成，以后不再改变，又称为静态重定位
3. 动态运行时的装入方式
可重定位装入方式不允许程序运行时在内存中移动位置。
动态运行时装入程序在装入模块仅内存后，并不直接将逻辑地址转换为物理地址，而是推迟到程序真正要执行的时再转换。因此装入内存后的动态地址仍是逻辑地址
2.2 程序的链接
链接时装目标模块和所需的库函数装配成一个完整的装入模块
1. 静态链接
将目标模块及它们所需的库函数链接称一个完整的装配模块
- 对相对地址进行修改
- 变换外部调用符号
2. 装入时动态链接
发生一个外部模块调用事件，编译器装入程序找出相应的外部目标模块并装入内存
- 便于修改和更新
- 便于实现对目标模块的共享
3. 运行时动态链接
将对某些模块的链接推迟到程序执行时才进行
加快程序的装入过程，节省大量的内存空间
三、连续分配存储管理方式
连续分配方式是最早出现的一种存储器分配方式，该方式为一个用户程序分配一个连续的内存空间
3.1 单一连续分配
单道程序环境
3.2 固定分区分配
1. 划分分区的方法
- 分区大小相等：缺点是缺乏灵活性，但特殊场合如炉温群控系统可以使用
- 分区大小不等：通常多个小分区，适量中等分区，少量大分区
2. 内存分配
按分区大小排序，建立一张分区使用表
3.3 动态分区分配
1. 动态分区分配中的数据结构
常用的有
- 空闲分区表：每个空闲分区一个表目，包括分区号、分区大小、分区起始地址等
- 空闲分区链：在每个分区的起始部分设置踹出血控制分区分配的信息
2. 动态分区分配算法
3. 分区分配操作
分配内存
回收内存
相邻的空闲分区可以合并
3.4 基于顺序搜索的动态分区分配算法
1. 首次适应（FF）算法
地址递增找到第一个
倾向于利用内存中低址部分的空闲分区，为以后的大作业分配大的内存空间创造了条件
缺点是低址部分不断被划分，留下许多难以利用的小的空闲分区，称为碎片
2. 循环首次适应（NF）算法
不是从链首，而是从上次找的的空闲分区开始
使内存中的空闲分区分配的更均匀，减少了查找空闲分区的消耗
缺点是缺乏大的空闲分区
3. 最佳适应（BF）算法
每次找到最小的能装下的空闲分区
每次分割后所切割下来剩余部分总是最小的，碎片多
4. 最坏适应（WF）算法
每次挑选一个最大的空闲区分割一部分给作业使用
优点是剩下的空闲区不至于太小，产生碎片的可能性最小
查找效率很高
3.5 基于索引搜索的动态分区分配算法
1. 快速适应（quick fit）算法
又称分类搜索法，将空闲分区根据容量大小进行分类。每一类单独设立一个空闲分区链表
优点是查找效率高
缺点是为了合并分区，在分区归还主存时的算法复杂，系统开销大
此外该算法分配空闲分区以进程为单位，在为进程所分配的一个分区或多或少存在浪费
2. 伙伴系统（buddy system）
无论分配分区或空闲分区，大小均为
找一个最小的
对一个大小为
3. 哈希算法
利用哈希快速查找的优点，构造一张以空闲分区大小为关键字的哈希表
分配空闲分区时，根据所需大小计算哈希值，得到其位置，得到相应的空闲分区链表实现最佳分配策略
3.6 可重定位分区分配
1. 紧凑
通过移动内存中作业的位置，把原来多个分校的小分区拼接成一个打分去的方法，称为“拼接”或“紧凑“
每紧凑一次就要对移动了的程序或数据的地址进行修改，影响系统效率
2. 动态重定位
在系统中增设一个重定位寄存器，存放程序（数据）在内存中的起始位置
程序执行时真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的
3. 动态重定位分区分配算法
与动态分区分配算法基本相同，只是添加了紧凑的功能
当找不到一个足够大的空闲分区时，若所有小的空闲分区总和满足用户需求，则紧凑，否则返回分配失败
四、对换
4.1 多道程序环境下的对换技术
1. 对换的引入
对换是指内存中暂时不能运行的进程或暂时不用的程序和数据换出到外村上，以便腾出足够的内存空间，再把已具备运行条件的进程或程序数据等换入内存
可以提高处理机利用率和系统吞吐量
2. 对换的类型
- 整体对换：中级调度以整个进程为单位在，称为进程对换或整体对换
- 页面（分段）对换：如果对换的目标是进程的一个“页面”或“分段”，则称为页面分段或分段对换，统称为“部分对换”，目的是为了支持虚拟存储系统
4.2 对换空间的管理
1. 对换空间管理的主要目标
在具有对换功能的 OS 中，通常把磁盘空间分为文件区和对换区
对文件区管理的主要目标
通常的文件都是较长时间驻留在外存上，访问频率较低
主要目标是提高文件存储空间的利用率，然后才是提高文件的访问速度
因此管理采用离散分配方式
对对换空间管理的主要目标
对换空间只占用磁盘的小部分，用于存放从内存换出的进程
进程驻留的时间短暂，对换操作频率较高
主要目标是提高进程换入换出的速度，然后才是提高文件存储空间的利用率
因此采用连续分配方式，较少考虑外存中的碎片问题
2. 对换空闲盘块管理中的数据结构
形式与内存在动态分区分配方式的数据结构相似
空闲分区表或空闲分区链
每个表目记录：对换区的首址及其大小，分别用盘块号和盘块数表示
3. 对换空间的分配与回收
与动态分区方式相同
4.3 进程的换入与换出
1. 进程的换出
选择被换出的进程
先选阻塞或睡眠状态的进程，多个选优先级最低的。
又是还需考虑进程在内存的驻留时间
进程换出过程
只能换出非共享的程序和数据段。对于共享的程序和数据段，只要还有进程需要就不能被换出
2. 进程的换入
首先查看 PCB 集合中所有进程的状态，找出“就绪”但已换出的进程，选择其中已换出到磁盘上时间最久的进程
一直对换直到没有可换入进程或内存不足
五、分页存储管理方式
允许一个进程直接分散地装入许多不相邻的分区中，便可充分利用内存空间，基于这一思想产生了离散分配方式
- 分页存储管理方式：用户程序的地址空间分为若干个固定大小的区域，称为“页”或“页面”。典型的页面大小为 1KB。相应地，内存空间也分为若干个物理块或页框
- 分段存储管理方式：这是为了满足用户要求形成的一种存储管理方式。将用户程序的地址空间分为若干个大小不同的段，每段可定义一组相对完整的信息。在存储器分配时以段位单位
- 段页式存储管理方式：是两种存储管理方式结合的产物
5.1 分页存储管理的基本方法
1. 页面和物理块
页面：将进程的逻辑地址空间分为若干页，加以编号，从
开始，如第 页。内存的物理地址空间也分为若干块，同样编号，如 块。进程的最后一页常装不满一块，形成不可利用的碎片，称为“页内碎片” 页面大小：过小的页面可以减少内存碎片，有利内存利用率的提高；但会造成每个进程占用过多的页面，导致进程页表过长；还会降低页面换入换出的效率。过大的页面虽然可以减少页表长度，但会使页内碎片增大
通常的页面大小为
的幂，为
2. 地址结构
| 31~12 | 11~0 |
|---|---|
| 页号 P | 位移量 W |
包含两部分：前一部分为页号，后一部分为偏移量，即业内地址
若给定一个逻辑地址空间中的地址为
3. 页表
在分页系统中，系统为每个进程建立了一张页面映像表，简称页表，记录了相应页在内存中对应的物理块号
作用是实现从页号到物理块号的地址映射
5.2 地址变换机构
基本任务是实现从逻辑地址到物理地址的转换，借助于页表完成
1. 基本的地址变换机构
页表寄存器 PTR
2. 具有快表的地址变换机构
联想寄存器，又称 TLB，用以存放当前访问的哪些页表项
5.3 访问内存的有效时间
从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元取出数据所花费的总时间称为内存的有效访问时间（EAT）。
假设一次访问内存时间为
5.4 两级和多级页表
1. 两级页表
2. 多级页表
见下章
5.5 反置页表
1. 反置页表的引入
为减少页表占用的内存空间，引入反置页表
反置页表为每一个物理块设置一个页表项，按物理块的编号排序，内容是页号和所隶属进程的标识符
2. 地址变换
六、分段存储管理方式
6.1 分段存储管理方式的引入
通常的程序都可分为若干个短，如主程序段、子程序段、数据段以及栈段等，每个段大多是一个相对独立的逻辑单位
实现和满足信息共享、信息保护、动态链接和信息的动态增长等需要也已段位基本单位
1. 方便编程
1 | LOAD 1,[A]|<D> |
2. 信息共享
分页系统一个可被共享的过程可能需要占用数十个页面，造成共享的困难
3. 信息保护
函数只允许执行不允许读写等，只需段做标志
页面的话可能有装有不同的保护属性的程序段的数据
4. 动态增长
数据段的动态增长很难预先知道
5. 动态链接
动态链接要求的是目标程序（即段）作为链接的基本单位
6.2 分段系统的基本原理
1. 分段
分段存储管理方式中，作业的地址空间分为若干个段，如主程序段 MAIN，子程序段 X，数据段 D，栈段 S 等
每个段都从
段长并不相等
2. 段表
段表记录了段在内存中的起始地址（基址）和段长
3. 地址变换机构
先判断是否段号太大访问越界，在检查端内地址 d 和该段段长 SL，最后将段基址和段内地址相加得物理地址
同样每次访问两次内存，解决方法是也增设一个联想存储器
4. 分段和分页的主要区别
页是信息的物理单位。采用分页以实现离散分配方式，提高内存利用率。分页仅仅是系统管理上的需要，对用户不可见
分段存储管理方式中的段信息的逻辑单位，通常包含一组意义相对完整的信息，目的在于更好地满足用户需要
页的大小固定且有系统决定。短的长度不固定，决定于用户编写的程序
分页的用户程序地址空间是一维的。分段系统中用户程序的地址空间是二维的，需给出段名和段内地址
6.3 信息共享
1. 分页程序中对程序和数据的共享
可重入代码又称为纯代码，是一种允许多个进程同时访问的代码。是一种不允许任何进程对它进行修改的代码。
在每个进程中，都必须配以局部数据区，把在执行中可能改变的部分拷贝到该数据区
每个进程的页表都设置共享程序的页表项
2. 分段程序中程序和数据的共享
只需在进程的段表中为共享程序设置一个段表项即可
6.4 段页式存储管理方式
1. 基本原理
段页式系统是分段和分页原理的结合
段表内容不再是内存始址和段长，而是页表始址和页表长度
2. 地址变换过程
利用段表始址和段号，得到页表始址，在用段内页号得到页表项位置，读出物理块号，最后用块号和页内地址构成物理地址
每次需访问三次内存，为提高执行速度增设一个高速缓冲器，存[段号:段内页号]对应的块号