(4)存储器管理
一、存储器的层次结构
1.多级存储器结构
存储层次至少具有三级:最高层为CPU寄存器,中间为主存,最底层是辅存。
2.主存器与寄存器
主存器(内存)
保存运行时的程序和数据
主存的访问速度远低于CPU执行指令的速度
寄存器
访问速度最快,完全能与CPU协调工作,价格昂贵。
寄存器的长度单位以字(word)为单位。
3.高速缓存和磁盘缓存
高速缓存
访问速度介于高速缓存和寄存器之间。
磁盘缓存
远低于主存的访问速度
二、程序的装入和链接
经过以下步骤:
- 编译
- 链接
- 装入
1.程序的装入
可以有绝对装入方式、可重定位装入方式和动态运行装入方式。
绝对装入方式
绝对装入程序按照装入模块的地址,将程序和数据装入内存。
绝对装入方式只能将目标模块装入到内存事先指定的位置。
适用于单道程序环境。
可重定位装入方式
在采用可重定位装入程序将装入模块装入内存后,会使装入模块中的所有逻辑地址与实际装入内存的物理地址不同。
可重定位装入方式可将装入模块装入到内存中任何允许的位置,故可用多道程序环境。
动态运行时装入方式
可重定位装入方式不允许程序运行时在内存中移动位置。
实际情况是,在运行过程中它在内存中的位置可能经常改变,此时就应采用动态运行时装入的方式。
装入内存后的所有地址都仍然是相对地址,而将相对地址转换为绝对地址是在程序真正执行的时候。
这种方式需要一种重定位寄存器。
2.程序的链接
静态链接
装入时链接
运行时动态链接
三、连续分配方式
1.单一连续分配
应用与单用户、单任务的操作系统中
2.固定分区分配
划分分区的方法
内存分配
造成空间浪费
3.动态分区分配
分区分配中的数据结构
- 空闲分区表
- 空闲分区链
分区分配算法
-
首次适应算法:从链首开始顺序查找
缺点:低址部分不断被划分
-
循环首次适应算法:从上次找到的空闲分区的下一个空闲分区开始查找
优点:空闲分区分布的更均匀
缺点:缺乏大的空闲分区
-
最佳适应算法:为了加速寻找,该算法要求将所有的空闲分区按其容量以从小到大的顺序形成——空闲分区链。
缺点:留下难以利用的小空闲区
-
最坏适应算法:要扫描整个空闲分区表或链表,总是挑选一个最大的空闲区分割给作业使用。
优点:使剩下的空闲区不至于太小,产生的碎片率最低。
缺点:缺乏大的空闲分区。
-
快速适应算法:是将空闲分区根据其容量进行大小分类,对于每一类具有相同容量的所有空闲分区,单独设立一个空闲分区链表。
优点:查找效率高。
缺点:开销大,算法复杂。
分区分配操作
- 分配内存
- 回收内存:四种情况
4.伙伴系统
伙伴系统就是对动态分区和固定分区两种内存方式的一种折衷方案。
伙伴系统规定,无论已分配分区或空闲分区,其大小均为 2 的 k 次幂,k 为整数,l≤k≤m,其中:2^1 表示分配的最小分区的大小,2 ^m 表示分配的最大分区的大小,通常 2 ^m 是整个可分配内存的大小。
不同大小的空闲分区形成了 k(0≤k≤m)个空闲分区链表。
5.哈希算法
哈希算法就是利用哈希快速查找的优点,以及空闲分区在可利用空间表中的分布规律, 建立哈希函数,构造一张以空闲分区大小为关键字的哈希表,该表的每一个表项记录了一 个对应的空闲分区链表表头指针。
6.可重定位分区分配
动态重定位的引入
这种通过移动内存中作业的位置,以把原来多个分散的小分区拼接成一个大分区的方 法,称为“拼接”或“紧凑”。
动态重定位的实现
真正访问的内存地址 是相对地址与重定位寄存器中的地址相加而形成的。
动态重定位分区分配算法
7.对换
对换的引入
所谓“对换”,是指把内存中暂时不能 运行的进程或者暂时不用的程序和数据调出到外存上,以便腾出足够的内存空间,再把已 具备运行条件的进程或进程所需要的程序和数据调入内存。
对换方法是实现后面要讲到的请求分页和请求分段式 存储管理的基础,其目的是为了支持虚拟存储系统。
对换空间的管理
把外存分为文件区和对换区。
进程的换出和换入
(1)进程的换出。每当一进程由于创建子进程而需要更多的内存空间,但又无足够的内 存空间等情况发生时,系统应将某进程换出。其过程是:系统首先选择处于阻塞状态且优 先级最低的进程作为换出进程,然后启动磁盘,将该进程的程序和数据传送到磁盘的对换 区上。若传送过程未出现错误,便可回收该进程所占用的内存空间,并对该进程的进程控 制块做相应的修改。
(2) 进程的换入。系统应定时地查看所有进程的状态,从中找出“就绪”状态但已换出 的进程,将其中换出时间最久(换出到磁盘上)的进程作为换入进程,将之换入,直至已无可 换入的进程或无可换出的进程为止。
四、基本分页存储管理方式
如果离散分配的 基本单位是页,则称为分页存储管理方式;
如果离散分配的基本单位是段,则称为分段存 储管理方式。
1.页面和页表
页面
分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片,称为页面或页。
地址结构
它含有两部分:前一部分为页号 P,后一部分为位移量 W(或称为页内地址)。
图中的地址长 度为 32 位,其中 0~11 位为页内地址,即每页的大小为 4 KB;12~31 位为页号,地址空 间最多允许有 1 M 页。
页表
系统为每一个进程建立了一张页面映像表。
2.地址变换机构
将用户地址空间中的逻辑地址变换为内存空间中的物理地址
地址变换机构的任务实际上只是 将逻辑地址中的页号,转换为内存中的物理块号。
基本的地址变换机构
在系统中只设置一个页表寄 存器 PTR(Page-Table Register),在其中存放页表在内存的始址和页表的长度。
具有快表的地址变换机构
为了提高地址变换速度,可在地址变换机构中增设一个具有并行查寻能力的特殊高速 缓冲寄存器,又称为“联想寄存器”(Associative Memory),或称为“快表”
3.两级和多级页表
解决现代计算机系统,逻辑地址空间太大导致页表很大的问题。
解决方式:
(1) 采用离散分配方式来解决难以找到一块连续的大内存空间的问题;
(2) 只将当前需要的部分页表项调入内存,其余的页表项仍驻留在磁盘上,需要时再 调入。
两级页表
多级页表 对于 32 位的机器,采用两级页表结构是合适的;但对于 64 位的机器,两级显然不够。
五、基本分段存储管理方式
1.分段存储管理方式的引入
- 方便编程
- 信息共享
- 信息保护
- 动态增长
- 动态链接
2.分段系统的基本原理
分段
有如下结构:
段表
段表是用于实现从逻辑段到物理内存区的映射
地址变换机构
为了实现从进程的逻辑地址到物理地址的变换功能,在系统中设置了段表寄存器,用 于存放段表始址和段表长度 TL。
分页和分段的主要区别
- 页是信息的物理单位,段时信息的逻辑单位
- 页的大小且由系统决定,而段的大小不固定
- 分页的作业地址时一维的,而分段的作业地址空间时二维的。
3.信息共享
分段系统的一个突出优点,是易于实现段的共享,即允许若干个进程共享一个或多个 分段,且对段的保护也十分简单易行。
4.段页式存储管理方式
基本原理
段页式系统的基本原理,是分段和分页原理的结合,即先将用户程序分成若干个段, 再把每个段分成若干个页,并为每一个段赋予一个段名。
地址变换过程
六、虚拟存储器的基本概念
前面各种存储器有一个共同的特点,即它们都要求将一个作业全部装入内存后方能运行。于是,出现以下两种情况:
(1) 有的作业很大,其所要求的内存空间超过了内存总容量,作业不能全部被装入内存, 致使该作业无法运行。
(2) 有大量作业要求运行,但由于内存容量不足以容纳所有这些作业,只能将少数作业 装入内存让它们先运行,而将其它大量的作业留在外存上等待。
1.虚拟存储器的引入
常规存储器管理的特征
- 一次性 :一次性装入将作业装入内存
- 驻留性 :作业装入内存,便一直驻留在内存内
局部性原理
程序在执行时将呈现出局部性规律,即在一较短 的时间内,程序的执行仅局限于某个部分;相应地,它所访问的存储空间也局限于某个区 域。
局限性还体现在如下方面:
- 时间局限性:指令执行后过不久可能又会执行
- 空间局限性:访问了某个存储单元,附近的存储单元也会被访问。
虚拟存储器的定义
虚拟存储器,是指具有请求调入功能和置换功能,能从逻辑 上对内存容量加以扩充的一种存储器系统。
2.虚拟存储器的实现方法
分页请求系统
硬件支持:
- 请求分页的页表机制
- 缺页中断机构
- 地址变换机构
软件支持:
这里包括有用于实现请求调页的软件和实现页面置换的软件。
请求分段系统
这是在分段系统的基础上,增加了请求调段及分段置换功能后所形成的段式虚拟存储系 统。
它允许只装入少数段(而非所有的段)的用户程序和数据,即可启动运行。
3.虚拟存储器的特征
具有多次性、对换性和虚拟性三大主要特征。
- 多次性:多次性是指一个作业被分成多次调入内存运行
- 对换性:对换性是指允许在作业的运行过程中进行换进、换出,亦即
- 虚拟性:虚拟性是指能够从逻辑上扩充内存容量,
七、请求分页存储管理方式
1.请求分页中的硬件支持
页表机制
缺页中断机构
在请求分页系统中,每当要访问的页面不在内存时,便产生一个缺页中断,然后由操作系统的缺页中断处理程序处理中断。
此时缺页的进程阻塞,放入阻塞队列,调页完成后再将其唤醒,放回就绪队列。
缺页中断是因为当前执行的指令想要访问的目标也i按未调入内存而产生的,因此属于内中断。
地址变换
八、页面置换算法
1.最佳置换算法和先进先出置换算法
- 最佳置换算法无法实现
2.最近最久未使用置换算法 LRU
- 性能好,实现困难,开销大