存储管理 第三章 存储管理
§ 3.1 存储管理的概念（ *）
§ 3.2 分区存储管理（ *）
§ 3.3 页式存储管理 （ *****）
§ 3.4 段 式存储管理 （ × ）
§ 3.5 段 页式存储管理（ × ）
存储管理 一,存储器存储器主存 (内部存储器,磁芯存储器 ）
辅存 （ 外存 ） 磁盘,磁带,软盘高速缓冲存储器主存系统区 （存放 OS程序和数据）
用户区 （ 存放用户程序,数据 ）
由于系统开工期间,OS程序与其他程序一起共享主存，为安全起见，多道程序系统常由 OS把内存初始化为：
存储管理 二、常用的基本概念
1.物理地址和逻辑地址物理地址 （ 绝对地址 ）,指内存单元的地址,主存中一系列存储物理单元 。
物理地址的集合称为 物理地址空间,也叫绝对地址空间或实空间或存储空间,亦即内存空间 。 存储空间中的单元一般都是按字节从 0开始连续编址的,如一个 256MB的内存,其地址范围是 0 ～ (256M— 1)。
逻辑地址 （ 相对地址 ）,程序用来访问信息所用的一系列的地址单元 。
又 称 相对地址 或 虚地址 。
逻辑地址的集合称为 逻辑地址空间,也叫 相对地址空间 或 虚空间 或 地址空间 。
作业运行时不能按其相对地址访问内存单元,而应按相应的物理地址访问,需要进行相对地址到物理地址的转换 。
存储管理 2.重定位当一个地址装入与其地址空间不一致的存储空间中,就得要地址变换 。 也就是说将虚地址映射为内存地址,把这种作法叫做 地址重定位
＝,静态重定位,是指在程序运行之前由装入程序完成的重定位过程 。
在装入一个作业时,把作业中的指令地址全部转换为绝对地址 （ 地址转换工作是在作业执行前集中一次完成的 ） 在作业执行过程中就无须再进行地址转换工作 。
＝,动态重定位,是在程序执行过程中,在 CPU访问内存之前,将要访问的程序或数据地址转换成内存地址,
动态重定位由软件 （ 操作系统 ） 和硬件 （ 地址转换机构 ） 相互配合来实现 。 动态重定位的系统支持,程序浮动,,而静态重定位则不能 。
存储管理 3．内存扩充技术
＝,覆盖 （ overlay技术 ）
所谓覆盖,是指同一主存区可以被不同的程序段重复使用 。 通常一个作业由若干个功能上相互独立的程序段组成,作业在一次运行时,也只用到其中的几段,利用这样一个事实,我们就可以让那些不会同时执行的程序段共用同一个主存区 。 因此,我们把可以相互覆盖的程序段叫做覆盖 。 而把可共享的主存区叫做覆盖区 。
存储管理主程序 (30k)
主程序 (30k)
子程序 A(8k) 子程序 B(10k)
子程序 M(20k) 子程序 N(25k)子程序 X(15k)
主程序（ 30k)
覆盖区 1(25k)
覆盖区 0
(10k)
内存区用户的结构化程序区覆盖的基本原理可用图例说明。
存储管理 由图中的调用关系不难看出：
主程序是一个独立的段，它调用子 A和子 B，且子
A与子 B是互斥被调用的两个段，在子 A执行过程中，它调用子 X，而子 B执行过程中它又调用子 M
和子 N，显然子 M和子 N也是互斥被调用的。
覆盖技术的主要特点是打破了必须将一个作业的全部信息装入主存后才能运行的限制。在一定程度上解决了小主存运行大作业的矛盾。
存储管理
＝ > 交换 （ swapping） 技术交换技术被广泛地运用于早期的小型分时系统的存贮管理中 。
所谓交换,就是系统根据需要把主存中暂时不运行的某个 (或某些 )作业部分或全部移到外存,而把外存中的某个 (或某些 )作业移到相应的主存区,并使其投入运行 。 所以,交换技术也叫对换或滚进滚出 （ roll-in,roll-out） 。 也有的系统叫挂起调度或中级调度 。
被换出到外存的程序只是临时被剥夺了对内存的使用权,过一段时间,还必须换入内存运行 。 因此,交换是一种用时间换空间的技术 。
存储管理
交换的时机通常在以下情况发生：
① 作业的进程用完时间片或等待输入输出；
② 作业要求扩充存贮而得不到满足时 。
同覆盖技术一样，交换技术也是利用 外存 来逻辑地 扩充主存 。
它的主要特点是 打破了一个程序一旦进入主存便一直运行到结束的限制 。
存储管理 ＝,虚拟内存技术
虚拟内存技术诞生于 1961年 。
广泛使用是从上个世纪 70年代初以后,今天几乎所有的操作系统都采用虚拟内存技术来管理内存 。
这是一种利用虚拟存储器来逻辑扩充物理内存的技术 。 其基本思想是 用软硬件技术把内存与外存这两级存储器当成一级存储器来用,从而给用户提供了一个比内存也比任何应用程序大得多的虚拟存储器,使得用户编程时再也不用考虑内存大小的限制了,给用户编程带来极大的方便 。
虚拟内存技术的实现也利用了自动覆盖和交换技术 。
存储管理 三,存储管理的功能
1,内存的分配与回收
2,地址转换
3,内存共享与保护
4．内存扩充四、存储管理的分类
1,分区式存储管理
2,分页式存储管理
3,分段式存储管理
4．段页式存储管理存储管理 § 3.2 分区存储管理
分区存储管理是把主存储器中的用户区作为一个连续区或分成若干个连续区进行管理，每个连续区中可装入一个作业。
多道程序系统一般都采用多个分区的存储管理，具体可分为 固定分区 和 可变分区 两种方式。
存储管理 一、固定分区存储管理区号 分区长度 起始地址状态
1 l1K A 0
2 l2K B job2
3 l3K c 0
OS0a
b
c
d
空
job2
把主存中可分配的用户区域预先划分成若干个连续的分区，每个连续区的大小可以相同，也可以不同。但是，一旦划分好分区之后，主存中分区的个数就固定了，且每个分区的大小也固定不变。这是一种静态分区法。
存储管理 在固定分区方式管理下，每个分区用来装入一个作业。由于主存中有多个分区，
就可同时在每个分区中装入一个作业。所以，这种存储管理方式适用于多道程序系统。
等待进入主存的作业排成一个作业队列。当主存中有空闲的分区时，依次从作业队列中选择一个能装入该分区的作业。当所有的分区都已装有作业，则其他的作业暂时不能再装入，绝对不允许在同一分区中同时装入两个或两个以上的作业。已经装入主存的作业在获得处理机运行时，要限定它只能在所占的分区中执行。
存储管理 1．主存空间的分配与释放
为了管理主存空间的使用，必须设置一张,主存分配表,,以说明各分区的分配情况。主存分配表中应指出各分区的起始地址和长度，并为每个分区设一个标志位。当标志位为,0”时，
表示对应的分区是空闲分区，当标志位为非,0”时，表示对应的分区已被某作业占用。空闲分区可以用来装作业。
区号 分区大小 起始地址 标志位
0 32k 0k 1
1 8k 32k 1
2 16k 40k 0
3 32k 56k 1
4 64k 88k 0
OS
作业 A(6k)
作业 B(28k)
0
32k
40k
56k
88k
存储管理 当作业队列中有作业要装入主存时，存储管理可采用,顺序分配算法,进行主存空间的分配。
顺序查看主存分配表，找到一个标志为,0”的并且长度大于或等于欲装入作业的地址空间长度的分区，则把此分区分配给该作业，相应表目的标志位改成作业名的标识；若找不到一个这样的空闲分区，则该作业暂时不能装入主存。
主存空间的释放很简单。 某作业执行结束后必须归还所占的分区，这时存储管理根据作业名查看主存分配表，找到相应的表目后，把其中的标志位重新置成,0”即可。
存储管理 2．地址转换
固定分区管理方式下作业的地址转换常采用静态重定位技术。
3．存储保护固定分区管理方式下只考虑判断其物理地址即可 。 常采用
,界限寄存器对,法 。
If 下限地址 <=物理地址 <=上限地址
Then 继续
Else 产生,越界中断,,转越界中断的处理子程序存储管理 4．内存扩充
采用覆盖技术
5,固定分区的缺点碎片大,存在小分区占用大作业的情况 。 不利于提高资源的利用率 。 可调入的作业大小受分区大小的严格限制 。
解决办法：采用可变分区存储管理存储管理 二、可变分区存储管理
内存管理的可变分区模式，又称变长分区模式。
与固定分区的区别就是：动态的划分分区。
克服固定分区管理的,内碎片,问题。
存储管理
OS
P1
OS
P1
P2
OS
P1
P2
P3
OS
P1
P4
空闲
P3
例子：一计算机系统有 2560KB内存，采用可变分区模式管理,OS占低地址的 400KB空间，用户内存为 2160KB。
如图所示：
OS
存储管理 通过分析得到：
1.可变分区模式下，刚开始,OS就绪，但任何用户程序未进入内存前整个用户内存区是一大空间。
已占用区和空闲分区并不是绝对的。
2.必须有表来记录分区的情况。
3.程序进入内存时的例行工作就是分配空闲区和装入程序，并修改相应的空闲表和已分配区表。
4.一旦一个内存分区被分配给一个进程，该进程可能被装入该块中执行，装入时需重定位。
存储管理 ① 最先适应分配算法：
=>1.顺 序查找各个空闲区,把第一个找到能容纳申请要求的内存区分配给申请者,（ 若空闲区比作业长度大,则分割该空闲区 。 一部分分配给作业一部分空闲 。 若等大？ ）
=>2.调 整相应的空闲表和已分配表 。
评价,性能一般但实现比较简单直接,易于释放时合并相邻空间分区 。 比较容易的满足大作业的需要 。 完成一次分配平均需要的搜索次数较大,影响了工作效率 。
存储管理 ② 最佳适应算法,
搜索整个空闲区以找出满足要求的最小空闲区 。
思想,先使用小的空闲区,将大的空闲区留给大作业,所以它总是试图找出最接近实际需要的空闲区 。
评价,尽可能的保留了较大的空间 。
产生大量的不用被使用的很小的空闲区 。
该算法不一定是最佳的 。
存储管理 ③ 最坏适应算法总是搜索整个链表以找到够用的最大的空闲区,使分裂出来的小空闲区比较大,因而可以继续使用 。
评价,分割后产生的空闲区一般仍可以供以后分配使用 。
工作一段时间后,不能满足大作业对空闲区的请求 。
存储管理例题：分区存储管理算法题 (P72)
假定主存中按地址顺序依次有五个空闲区。空闲区大小依次为,15k,28k,10k,226k,110k.
现有五个作业 J1,J2,J3,J4,J5。 他们各需要主存
10k,15k,102k,26k,180k。
判断用最先适应分配算法，最坏适应分配算法，
最佳分配适应算法能否将这五个作业顺序装入？
存储管理
OS
15K
28K
10K
226K
110K
内存空闲区示意图：
OS
28K
10K
226K
110K
装入
J1
后，
内存空闲区示意图：
J1
5k
结论：只有最佳适应分配可以。
存储管理 去配算法（一般了解）：
比固定分区管理增加了合并相邻空闲区的操作。
主要是为了减少,外碎片,,利于今后大作业的到来。
回收内存空间，关键是修改两个表。
存储管理
OS
J1
J3
J2
A
B
C
D
E
F
起始地址 长度 标志位
B H1 0
D H2 0
起始地址 长度 标志位
A L1 J1
C L2 J2
E L3 J3
起始地址 长度 标志位
B H1 0
D H2 0
C L2 0
L1
H2
H1
存储管理 (a)若释放区 R既有上邻空闲区，又有下邻空闲区。 将三个空闲区合并成一个大空闲区。
空闲区 F1 释放区 R
低地址 高地址空闲区 F2
低地址 高地址空闲区 F1(a)合并后先将 R与 F2合并记为 F2,
再将 F2与 F1合并记为 F1,并将 F2从链中删除。
IF (B+H1=C) AND (C+L2=D)
THEN 修改空闲表，分配表。
存储管理
(b)若释放区 R只有上邻空闲区 F1。
则只修改空闲区 F1大小即可。
空闲区 F1 R 占用区 F2 占用区 F2空闲区 F2
低地址 高地址 低地址 高地址
(b)合并后
IF (D+H2=E)
THEN 修改空闲表，分配表。
存储管理
(c)只有下邻空闲区占用区 1 进程 P 空闲区 F2 空闲区 F2占用区 1
低地址 高地址 低地址 高地址合并后修改空闲区 F2的首地址。
F2的大小＝ F2的大小＋ R的大小
(d)既无上邻又无下邻空闲区
Else 修改释放区的首地址为空闲区的起始地址存储管理
地址转换：
动态重定位
分区的存储保护：
If 下限地址 <=物理地址 <=上限地址
Then 继续
Else 产生,越界中断,,转越界中断的处理子程序存储管理?内存扩充
消除了固定分区管理造成的,内碎片,,但是不可避免的在内存空间造成,外碎片,。
例如：如图中已有 J1,J3,J4三个作业在内存，还有两个长度分别为 300K和 260K的空闲区。但是这两个空闲区都不满足作业 J5的 500K空间的要求。
采用移动（紧缩）技术。定时的或在内存紧张时，将内存中所有作业移到内存的一端，使其相邻。
存储管理
经过紧缩后的进程在内存中的位置发生了变化，
若不对程序和数据的地址进行修改，在进程就无法运行。
要使其运行，必须进行,动态重定位,
＝,紧缩的事机：
（ 1）一旦有归还的分区便进行紧缩，系统开销大。
（ 2）当发现内存不够用时 …,
＝,移动是有条件的存储管理 3.3 页式存储管理分页存储管理是解决存储零头的一种方法 。
动态重定位是解决存储器零头问题的一种途径,
但要移动大量信息花去不少处理机时间,代价比较高,
这是因为这种分配要求把作业必须安置在一连续存储区内的缘故,而分页存储管理正是要避开这种连续性要求 。
分为,实分页存储管理 和 虚分页存储管理存储管理一、分页式存储管理－ 实存模式下的页式存储管理
1.基本原理假设一个大型饭店，所有的客房都是标准的双人间，部分客房已经住进客人，现在又有一个旅游团要求入住。接待员统计了一下，对旅游团领队说：“贵团全体成员都能住下，
两人一个房间，但是不能住在同一楼层了，因为每层空着的客房不够，更没有几个挨着的。请原谅！”。对于这样的安排，一般人不会感到奇怪。因为旅游团本来就是由一位位个人或夫妻等组成的，而饭店的客房本来也是两人一间的，两人一组正好可住在一个客房里；另外，饭店几乎每天都有入住的和退房的客人，想在同一楼层找几间挨着的客房实在不容易。
存储管理 2.基本思想
① 将整个系统的内存空间划分成一系列大小相等的块，每一块称为一个物理块、物理页或实页，页架或页帧（ frame），可简称为块（ block）。所有的块按物理地址递增顺序连续编号为 0,1,2,…… 。
这里的块相当于饭店的客房，系统对内存分块相当于饭店把大楼所有的客房都设计成标准的双人间。
存储管理
② 每个作业的地址空间也划分成一系列与内存块一样大小的块，每一块称为一个逻辑页或虚页，
也有人叫页面，可简称为页（ page）。所有的页按照逻辑地址递增顺序连续编号为 0,1、
2,…… 。
这里，对作业地址空间分页就相当于把旅游团成员分成两人一组。
存储管理
③ 一个作业，只要它的总页数不大于内存中的可用块数，系统就可以对它实施分配。系统装入作业时，
以页为单位分配内存，一页分配一个块，作业所有的页所占的块可以不连续。系统同时为这个作业建立一个页号与块号的对照表，称为 页表 。
这好象饭店有个记录客户入住情况的客户登记表一样。另外，饭店安排客户入住是要查看全部客房的使用情况一览表，相应地系统给作业分配内存时要查看主存分配表或者内存块说明表。
存储管理
④ 每个块的大小是固定的，一般是个
1/2KB～ 4KB之间的数值（请读者思考：块尺寸为什么太大或太小都不好），而且必须是个 2的幂次。
对块尺寸这样规定相当于饭店规定客房是双人间。可以设想一下，如果上例中饭店所有的客房都是十人间的话，效益肯定不如全是双人间的好存储管理概括：实模式下分页存储管理的基本原理：
系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行时，一次性把作业的全部页面装入内存，各个页所占的内存块可以不连续。
这实际是个把作业从地址空间映射到存储空间的过程存储管理 3.地址转换
页面的划分完全是一种系统硬件的行为，
一个逻辑地址放到这种地址结构重，自然就分成了页号和页内单元号两部分。
页 号 页内地址
31 12 11 0
页面大小为,4KB
存储管理 （ 1）数据结构
在分页系统中，允许将作业（进程）的任一页装入到内存中的任一可用的物理块中，但进程的地址空间本来是连续的，若把他分页后装入到不相邻的物理块中，要保证系统仍能正确运行，就要实现从进程的逻辑地址变换为内存的物理地址。
所以，系统为每个进程建立一张页面映射表，简称页表。
存储管理
0页
1页
2页
3页
4页
…
N页页号 块号
0 4
1 7
2 3
3 5
4 2
… …
页表用户程序内存通过页表实现页面映射存储管理 （ 2）地址映射
在系统中设置地址变换机构，能将用户进程地址空间中的逻辑地址变为内存空间中的物理地址。
由于页面和物理块的大小相等，页内偏移地址和块内偏移地址是相同的。无须进行从页内地址到块内地址的转换。
地址变换机构的任务，关键是将逻辑地址中的页号转换为内存中的物理块号。物理块号内的偏移地址就是页内偏移地址。
页表的作用就是从页号到物理块号的转换，所以地址变换的任务借助于页表来完成的。
存储管理块号
8
页表地址 页表长度 页号 页内地址
0
1
2
3
块号 块内地址逻辑地址页表控制寄存器页表存储管理 2,分配与回收 (P76)
3.地址变换 (映射 )
存储管理?三,快表
因为页表是存放在内存中的 CPU要存取一个数据,需访问主存两次 。
第一次：访内存中的页表,找到该页的的物理块号,将此块号与页内地址拼结形成物理地址；
第二次：真正访问该物理地址,存取其中的内容 。
这样就把程序的执行速度降低一倍 。
为了提高存取速度,在地址变换机构中增设一组寄存器,
用来存放访问的那些页表 。
把存放在高速缓冲寄存器中的页表叫快表,这个高速缓冲寄存器又叫联想存贮器 。
存储管理
联想存贮器的存取速度比主存高,
但造价也高 。 因此只能采用少量,
整个系统通常只要用 8~16个寄存器即可使程序执行速度大大提高 。 快表的格式见下图 。
页号 块号 访问位 状态位存储管理
其中,,页号,是程序访问过的地址空间的页号，
,块号,是该页所对应的主存块号；访问位指示该页最近是否被访问过。,0”表示没有被访问,,1”表示访问过 ；,状态,位指示该寄存器是否被占用。通常
,0”表示空闲,,1”表示占用。
为了保证快表中的内容为现正运行程序的页表内容，
在每个程序被选中时，由恢复现场程序把快表的所有状态位清,0”，或恢复已保存的快表内容。
存储管理
当进程访问一页时，系统将页号与快表中的所有项进行并行比较。若访问的页在快表中，即可立即进行地址转换。
当被访问的页不在快表中时，就要将由慢表找到的内存块号与虚页号填入快表中，若快表已满，则置换其中访问位为 0的一项。
另外，在设置快表的情况下，硬件地址转换机构在进行地址变换时，同时开始两个变换过程。
存储管理
一个是利用主存页表进行的正常变换过程，另一个是利用快表进行的快速变换过程。一旦快表中有与查找的页号相符合时，则立即停止正常的访主存页表过程。并将快表中的块号与
CPU给出的页内位移相拼接，得到访问主存的绝对地址。从而结束了快表的查找工作。
存储管理
1.局部性原理 (principle of locality)：
指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。还可以表现为：
–时间局部性,一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；
–空间局部性,当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。
二、虚拟存储器 (Virtual Memory)
存储管理
局部性原理的具体体现：
程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令。
过程调用的嵌套深度一般不超过 5，因此执行的范围不超过这组嵌套的过程。
程序中存在相当多的循环结构，它们由少量指令组成，
而被多次执行。
程序中存在相当多对一定数据结构的操作，如数组操作，往往局限在较小范围内。
存储管理 (1),引入虚拟存储技术的好处
大程序,可在较小的可用内存中执行较大的用户程序；
大的用户空间,提供给用户可用的虚拟内存空间通常大于物理内存 (real memory)
并发,可在内存中容纳更多程序并发执行；
易于开发,与覆盖技术比较，不必影响编程时的程序结构存储管理 (2) 虚拟存储技术的特征
不连续性,物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间）
部分交换,与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的；
大空间,通过物理内存和快速外存相结合，提供大范围的虚拟地址空间存储管理返回
总容量不超过物理内存和外存交换区容量之和。 其运行速度接近于内存，每位的成本又接近于外存，是一种性能非常优越的存储管理技术
(3) 虚拟存储技术的种类虚拟页式虚拟段式虚拟段页式存储管理返回
1,基本原理
系统自动地将作业的地址空间分页，将系统的主存空间分块，
页与块等大小，在作业运行前，只把初始需要的一部分页面装入内存块里，运行中需要访问自己地址空间中的但当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调入内存，若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的置换策略自动选择一个或一些在内存的页面，把它们换出到外存。
这里的 请求调入 和 置换功能 都是比实分页存储管理增加的内容，是实现虚拟存储的主要功能。
3,虚拟页式 (virtual paging)
存储管理 为实现虚拟页式存储管理,
页表表目需要增加 外存块号,状态位,访问位 或 访问字段,修改位,存取控制字段 等。
外存块号指出该页在外存的地址，供调入该页时用；
状态为指示该页是否在内存，供程序访问时用，也是检查是否缺页的标志位；
访问位或访问字段则是该页被访问过的标志或该页被访问过的次数；
修改位表示该页是否被修改过；存取控制字段则是用来限制页面被安全共享的。
存储管理 2.主存页面分配策略,
在虚拟页式存储管理中，在给作业分配内存时，还必须考虑解决下面两个问题：
（ 1）如何发现要访问的页不在内存？
（ 2）作业运行过程中当发现要访问页不在内存发生缺页中断时，如何为所缺的页面分配内存？
mov A,B
存储管理 3.页面调入时机
（ 1） 请求调入
当发生页面故障时进行调度,即当进程访问不在内存的页面引发缺页中断时,由系统根据这种访问请求把所缺页面装入内存 。
优点,由请求调入策略装入的页一定会被访问,再加之比较容易实现,故在目前的虚拟存储器中,大多采用此策略 。
缺点,每次仅调入一页,增加了磁盘 I/O的启动频率 。
存储管理 （ 2）预调入
=>也称先行调度,即一页面被访问前就已经预先置入内存,
以减少今后的缺页率 。
=>主要适于进程的许多页存放在外存的连续区域中的情况 。
有的系统结合请求调入使用,即每次缺页时装入多个页面 。
优点,提高调页的 I/O效率 。
缺点,基于预测,若调入的页在以后很少被访问,则效率低 。 常用于程序装入时的调页 。
存储管理
4.页面调度算法 (淘汰算法或置换算法 ):
（ 1） 最佳淘汰算法 ——OPT(Optimal)
这是 Belady于 1966年提出的一种理论上的算法。该算法每次都淘汰以后永不使用的，或者过最长的时间后才会被访问的页面。
显然，采用这种算法会保证最低的缺页率，但它是无法实现的，因为它必须知道页面“将来”的访问情况。不过，
该算法仍有一定意义，可作为衡量其他算法优劣的一个标准。
存储管理 假定系统为某个进程分配了三个物理块，进程的访问顺序为 7,0,1,2,0,3,0,4,2,3,0，
3,2,1,2
采用 OPT淘汰算法：
7 7 7 2 2 2 2 2 2 2 2 2 2 2 2
0 0 0 0 0 0 4 4 4 0 0 0 0 0
1 1 1 3 3 3 3 3 3 3 3 1 1 * * * * * *
命中
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2
存储管理
（ 2）先进先出淘汰算法 ——FIFO
这是最早出现的淘汰算法。
总是淘汰最先进入内存的页面。它实现简单，只需把进程中已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存中最老的页面。
缺点：效率不高，因为它与进程实际的运行规律不相适应，
比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。出现 bleady现象。
存储管理
Belady现象,采用 FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，
缺页率反而提高的异常现象。
Belady现象的描述,一个进程 P要访问 M个页,OS
分配 N个内存页面给进程 P；对一个访问序列 S，发生缺页次数为 PE（ S,N）。当 N增大时,PE(S,N)时而增大，时而减小。
Belady现象的原因,FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。
存储管理采用 FIFO淘汰算法：
7 7 7 2 2 2 2 4 4 4 0 0 0 0 0
0 0 0 0 3 3 3 2 2 2 2 2 1 1
1 1 1 1 0 0 0 3 3 3 3 3 2
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2
存储管理 （ 3） 最近最久未使用算法
(LRU,Least Recently Used）
根据页面调入内存后的使用情况，选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。
OPT算法使用页面将要被访问的时间,LRU算法使用页面最后一次被访问的时间。二者唯一的差别是,OPT是向前看的，而 LRU是向后看的。
存储管理 下面给出 LRU的两个实现算法：
① 计时法,对于每一页面增设一个访问时间计时器,
每当一个页面被访问时,当时的绝对时钟内容被拷贝到对应的访问时间计时器中,这样系统记录了内存中所有页面最后一次被访问的时间 。 淘汰时,选取访问时间计时器的值最小的页面 。
②堆栈法,每当进程访问某页面时，便将该页面的页号从栈中移出，将它压入栈顶。栈顶始终是最新被访问的页面的编号。栈底则是最近最久未被使用的页面的页面号。
存储管理 假定现有一进程所访问的页面的页面号序列为,4,8,0,8,1,0,2,1,2,6
随着进程的访问，栈中页面号的变化情况：
2 1 2 6
1 0 1 1 2 1 2
0 8 8 1 0 0 0 0 1
8 8 0 0 8 8 8 8 8 0
4 4 4 4 4 4 4 4 4 4 8
4,8,0,8,1,0,1,2,1,2,6
存储管理 LRU的开销是很大的，必须有硬件的支持，完全由软件实现其速度至少会减少 10倍，因此 LRU近似算法更实用些。
（ 4 ） 二 次 机 会 淘 汰 算 法 ——SC(Second
Chance)淘汰算法
这是一种 LRU的近似算法，是通过对 FIFO算法进行简单改造，结合页表中的访问位而得来一种淘汰算法。
该算法首先检查位于 FIFO链链首的页，如果它的访问位为 0，
则选择该页淘汰；如果它的访问位为 1，则清除其访问位，
将它移至 FIFO链的链尾，重复此算法的查找过程，直至遇到新链首页是一个访问位为 0的较早进入内存的页为止，把它选为被淘汰的页。
存储管理 （ 5）时钟 (Clock)淘汰算法
该算法首先检测指针所指的页面，如果它的访问位为 0，则淘汰该页，新装入的页插入到此位置，然后指针前进一个位置；如果它的访问位为 1，则清除为 0，并将指针前进一个位置，继续检查访问位。重复此过程，直到找到访问位为 0的页面为止。
缺点：就是需要把访问位为 1的处于链首的页移至链尾，这需要一定的开销。一种改进的方法就是把进程所访问的页面链成一个环形链表，再设一个指针指向最老的页面，于是形成了一种简单实用的 LRU近似算法 —— 时钟淘汰算法。
存储管理 （ 6）最近未用淘汰算法 ——NRU(Not Used Recently)淘汰算法
它把 FIFO算法的思想与页面的访问位和修改位结合起来确定一个接近 LRU算法的淘汰对象。
该算法每次都尽量选择最近最久未被写过的页面淘汰，这种干净的页面可以不被写回到磁盘。在实现时，为每一个页面设置初始值 0的访问位和修改位。当对某页面执行写操作时，其修改位和访问位均由硬件置成 1；当对某页面执行读操作时，只有其访问位被硬件置成 1。系统每隔固定时间将所有访问位都清 0。
存储管理 按照下列次序选择被淘汰的页面：
① 访问位＝０,修改位＝０；直接淘汰；
② 访问位＝０,修改位＝１； 写回外存后 淘汰；
③ 访问位＝１,修改位＝０；直接淘汰；
④访问位＝１，修改位＝１； 写回外存后淘汰；
存储管理 影响缺页中断率的因素
（ 1）页面调度算法不合理
抖动又叫颠簸，是指一段时间里，页面在内存与外存之间频繁地调度或换入换出，以至于系统用于调度页面所需要的时间比进程实际运行所占用的时间还要多。
显然，抖动是由于缺页中断率很高而引起的一种坏现象，
它将严重影响系统的效率，甚至可能使系统全面崩溃。
存储管理 （ 2）分配给作业的内存块数太少
作业的缺页中断率与作业所占内存块数成反比。分配给作业的内存块数太少是导致抖动现象发生的最主要的原因，实验分析表明：对所有的程序来说，要使其有效地工作，它在内存中的页面数不应少于它的总页面数的一半。
存储管理 （ 3）页面大小的选择不合理
虽然缺页中断率与页面尺寸成反比，但页面尺寸却不能一味地求大，它一般在 0.5KB~4KB之间，是个实验统计值。
因为页面大时，页表较小，占空间少，查表速度快，缺页中断次数少，但页面调度时间长，页内碎片较大。页面小时，恰恰相反。
（ 4）用户程序编制的方法不合适作业的缺页中断率与程序的局部化（包括时间局部化和空间局部化）程度成反比。用户程序编制的方法不合适可能导致程序运行的时空复杂度高，缺页次数多。
§ 3.1 存储管理的概念（ *）
§ 3.2 分区存储管理（ *）
§ 3.3 页式存储管理 （ *****）
§ 3.4 段 式存储管理 （ × ）
§ 3.5 段 页式存储管理（ × ）
存储管理 一,存储器存储器主存 (内部存储器,磁芯存储器 ）
辅存 （ 外存 ） 磁盘,磁带,软盘高速缓冲存储器主存系统区 （存放 OS程序和数据）
用户区 （ 存放用户程序,数据 ）
由于系统开工期间,OS程序与其他程序一起共享主存，为安全起见，多道程序系统常由 OS把内存初始化为：
存储管理 二、常用的基本概念
1.物理地址和逻辑地址物理地址 （ 绝对地址 ）,指内存单元的地址,主存中一系列存储物理单元 。
物理地址的集合称为 物理地址空间,也叫绝对地址空间或实空间或存储空间,亦即内存空间 。 存储空间中的单元一般都是按字节从 0开始连续编址的,如一个 256MB的内存,其地址范围是 0 ～ (256M— 1)。
逻辑地址 （ 相对地址 ）,程序用来访问信息所用的一系列的地址单元 。
又 称 相对地址 或 虚地址 。
逻辑地址的集合称为 逻辑地址空间,也叫 相对地址空间 或 虚空间 或 地址空间 。
作业运行时不能按其相对地址访问内存单元,而应按相应的物理地址访问,需要进行相对地址到物理地址的转换 。
存储管理 2.重定位当一个地址装入与其地址空间不一致的存储空间中,就得要地址变换 。 也就是说将虚地址映射为内存地址,把这种作法叫做 地址重定位
＝,静态重定位,是指在程序运行之前由装入程序完成的重定位过程 。
在装入一个作业时,把作业中的指令地址全部转换为绝对地址 （ 地址转换工作是在作业执行前集中一次完成的 ） 在作业执行过程中就无须再进行地址转换工作 。
＝,动态重定位,是在程序执行过程中,在 CPU访问内存之前,将要访问的程序或数据地址转换成内存地址,
动态重定位由软件 （ 操作系统 ） 和硬件 （ 地址转换机构 ） 相互配合来实现 。 动态重定位的系统支持,程序浮动,,而静态重定位则不能 。
存储管理 3．内存扩充技术
＝,覆盖 （ overlay技术 ）
所谓覆盖,是指同一主存区可以被不同的程序段重复使用 。 通常一个作业由若干个功能上相互独立的程序段组成,作业在一次运行时,也只用到其中的几段,利用这样一个事实,我们就可以让那些不会同时执行的程序段共用同一个主存区 。 因此,我们把可以相互覆盖的程序段叫做覆盖 。 而把可共享的主存区叫做覆盖区 。
存储管理主程序 (30k)
主程序 (30k)
子程序 A(8k) 子程序 B(10k)
子程序 M(20k) 子程序 N(25k)子程序 X(15k)
主程序（ 30k)
覆盖区 1(25k)
覆盖区 0
(10k)
内存区用户的结构化程序区覆盖的基本原理可用图例说明。
存储管理 由图中的调用关系不难看出：
主程序是一个独立的段，它调用子 A和子 B，且子
A与子 B是互斥被调用的两个段，在子 A执行过程中，它调用子 X，而子 B执行过程中它又调用子 M
和子 N，显然子 M和子 N也是互斥被调用的。
覆盖技术的主要特点是打破了必须将一个作业的全部信息装入主存后才能运行的限制。在一定程度上解决了小主存运行大作业的矛盾。
存储管理
＝ > 交换 （ swapping） 技术交换技术被广泛地运用于早期的小型分时系统的存贮管理中 。
所谓交换,就是系统根据需要把主存中暂时不运行的某个 (或某些 )作业部分或全部移到外存,而把外存中的某个 (或某些 )作业移到相应的主存区,并使其投入运行 。 所以,交换技术也叫对换或滚进滚出 （ roll-in,roll-out） 。 也有的系统叫挂起调度或中级调度 。
被换出到外存的程序只是临时被剥夺了对内存的使用权,过一段时间,还必须换入内存运行 。 因此,交换是一种用时间换空间的技术 。
存储管理
交换的时机通常在以下情况发生：
① 作业的进程用完时间片或等待输入输出；
② 作业要求扩充存贮而得不到满足时 。
同覆盖技术一样，交换技术也是利用 外存 来逻辑地 扩充主存 。
它的主要特点是 打破了一个程序一旦进入主存便一直运行到结束的限制 。
存储管理 ＝,虚拟内存技术
虚拟内存技术诞生于 1961年 。
广泛使用是从上个世纪 70年代初以后,今天几乎所有的操作系统都采用虚拟内存技术来管理内存 。
这是一种利用虚拟存储器来逻辑扩充物理内存的技术 。 其基本思想是 用软硬件技术把内存与外存这两级存储器当成一级存储器来用,从而给用户提供了一个比内存也比任何应用程序大得多的虚拟存储器,使得用户编程时再也不用考虑内存大小的限制了,给用户编程带来极大的方便 。
虚拟内存技术的实现也利用了自动覆盖和交换技术 。
存储管理 三,存储管理的功能
1,内存的分配与回收
2,地址转换
3,内存共享与保护
4．内存扩充四、存储管理的分类
1,分区式存储管理
2,分页式存储管理
3,分段式存储管理
4．段页式存储管理存储管理 § 3.2 分区存储管理
分区存储管理是把主存储器中的用户区作为一个连续区或分成若干个连续区进行管理，每个连续区中可装入一个作业。
多道程序系统一般都采用多个分区的存储管理，具体可分为 固定分区 和 可变分区 两种方式。
存储管理 一、固定分区存储管理区号 分区长度 起始地址状态
1 l1K A 0
2 l2K B job2
3 l3K c 0
OS0a
b
c
d
空
job2
把主存中可分配的用户区域预先划分成若干个连续的分区，每个连续区的大小可以相同，也可以不同。但是，一旦划分好分区之后，主存中分区的个数就固定了，且每个分区的大小也固定不变。这是一种静态分区法。
存储管理 在固定分区方式管理下，每个分区用来装入一个作业。由于主存中有多个分区，
就可同时在每个分区中装入一个作业。所以，这种存储管理方式适用于多道程序系统。
等待进入主存的作业排成一个作业队列。当主存中有空闲的分区时，依次从作业队列中选择一个能装入该分区的作业。当所有的分区都已装有作业，则其他的作业暂时不能再装入，绝对不允许在同一分区中同时装入两个或两个以上的作业。已经装入主存的作业在获得处理机运行时，要限定它只能在所占的分区中执行。
存储管理 1．主存空间的分配与释放
为了管理主存空间的使用，必须设置一张,主存分配表,,以说明各分区的分配情况。主存分配表中应指出各分区的起始地址和长度，并为每个分区设一个标志位。当标志位为,0”时，
表示对应的分区是空闲分区，当标志位为非,0”时，表示对应的分区已被某作业占用。空闲分区可以用来装作业。
区号 分区大小 起始地址 标志位
0 32k 0k 1
1 8k 32k 1
2 16k 40k 0
3 32k 56k 1
4 64k 88k 0
OS
作业 A(6k)
作业 B(28k)
0
32k
40k
56k
88k
存储管理 当作业队列中有作业要装入主存时，存储管理可采用,顺序分配算法,进行主存空间的分配。
顺序查看主存分配表，找到一个标志为,0”的并且长度大于或等于欲装入作业的地址空间长度的分区，则把此分区分配给该作业，相应表目的标志位改成作业名的标识；若找不到一个这样的空闲分区，则该作业暂时不能装入主存。
主存空间的释放很简单。 某作业执行结束后必须归还所占的分区，这时存储管理根据作业名查看主存分配表，找到相应的表目后，把其中的标志位重新置成,0”即可。
存储管理 2．地址转换
固定分区管理方式下作业的地址转换常采用静态重定位技术。
3．存储保护固定分区管理方式下只考虑判断其物理地址即可 。 常采用
,界限寄存器对,法 。
If 下限地址 <=物理地址 <=上限地址
Then 继续
Else 产生,越界中断,,转越界中断的处理子程序存储管理 4．内存扩充
采用覆盖技术
5,固定分区的缺点碎片大,存在小分区占用大作业的情况 。 不利于提高资源的利用率 。 可调入的作业大小受分区大小的严格限制 。
解决办法：采用可变分区存储管理存储管理 二、可变分区存储管理
内存管理的可变分区模式，又称变长分区模式。
与固定分区的区别就是：动态的划分分区。
克服固定分区管理的,内碎片,问题。
存储管理
OS
P1
OS
P1
P2
OS
P1
P2
P3
OS
P1
P4
空闲
P3
例子：一计算机系统有 2560KB内存，采用可变分区模式管理,OS占低地址的 400KB空间，用户内存为 2160KB。
如图所示：
OS
存储管理 通过分析得到：
1.可变分区模式下，刚开始,OS就绪，但任何用户程序未进入内存前整个用户内存区是一大空间。
已占用区和空闲分区并不是绝对的。
2.必须有表来记录分区的情况。
3.程序进入内存时的例行工作就是分配空闲区和装入程序，并修改相应的空闲表和已分配区表。
4.一旦一个内存分区被分配给一个进程，该进程可能被装入该块中执行，装入时需重定位。
存储管理 ① 最先适应分配算法：
=>1.顺 序查找各个空闲区,把第一个找到能容纳申请要求的内存区分配给申请者,（ 若空闲区比作业长度大,则分割该空闲区 。 一部分分配给作业一部分空闲 。 若等大？ ）
=>2.调 整相应的空闲表和已分配表 。
评价,性能一般但实现比较简单直接,易于释放时合并相邻空间分区 。 比较容易的满足大作业的需要 。 完成一次分配平均需要的搜索次数较大,影响了工作效率 。
存储管理 ② 最佳适应算法,
搜索整个空闲区以找出满足要求的最小空闲区 。
思想,先使用小的空闲区,将大的空闲区留给大作业,所以它总是试图找出最接近实际需要的空闲区 。
评价,尽可能的保留了较大的空间 。
产生大量的不用被使用的很小的空闲区 。
该算法不一定是最佳的 。
存储管理 ③ 最坏适应算法总是搜索整个链表以找到够用的最大的空闲区,使分裂出来的小空闲区比较大,因而可以继续使用 。
评价,分割后产生的空闲区一般仍可以供以后分配使用 。
工作一段时间后,不能满足大作业对空闲区的请求 。
存储管理例题：分区存储管理算法题 (P72)
假定主存中按地址顺序依次有五个空闲区。空闲区大小依次为,15k,28k,10k,226k,110k.
现有五个作业 J1,J2,J3,J4,J5。 他们各需要主存
10k,15k,102k,26k,180k。
判断用最先适应分配算法，最坏适应分配算法，
最佳分配适应算法能否将这五个作业顺序装入？
存储管理
OS
15K
28K
10K
226K
110K
内存空闲区示意图：
OS
28K
10K
226K
110K
装入
J1
后，
内存空闲区示意图：
J1
5k
结论：只有最佳适应分配可以。
存储管理 去配算法（一般了解）：
比固定分区管理增加了合并相邻空闲区的操作。
主要是为了减少,外碎片,,利于今后大作业的到来。
回收内存空间，关键是修改两个表。
存储管理
OS
J1
J3
J2
A
B
C
D
E
F
起始地址 长度 标志位
B H1 0
D H2 0
起始地址 长度 标志位
A L1 J1
C L2 J2
E L3 J3
起始地址 长度 标志位
B H1 0
D H2 0
C L2 0
L1
H2
H1
存储管理 (a)若释放区 R既有上邻空闲区，又有下邻空闲区。 将三个空闲区合并成一个大空闲区。
空闲区 F1 释放区 R
低地址 高地址空闲区 F2
低地址 高地址空闲区 F1(a)合并后先将 R与 F2合并记为 F2,
再将 F2与 F1合并记为 F1,并将 F2从链中删除。
IF (B+H1=C) AND (C+L2=D)
THEN 修改空闲表，分配表。
存储管理
(b)若释放区 R只有上邻空闲区 F1。
则只修改空闲区 F1大小即可。
空闲区 F1 R 占用区 F2 占用区 F2空闲区 F2
低地址 高地址 低地址 高地址
(b)合并后
IF (D+H2=E)
THEN 修改空闲表，分配表。
存储管理
(c)只有下邻空闲区占用区 1 进程 P 空闲区 F2 空闲区 F2占用区 1
低地址 高地址 低地址 高地址合并后修改空闲区 F2的首地址。
F2的大小＝ F2的大小＋ R的大小
(d)既无上邻又无下邻空闲区
Else 修改释放区的首地址为空闲区的起始地址存储管理
地址转换：
动态重定位
分区的存储保护：
If 下限地址 <=物理地址 <=上限地址
Then 继续
Else 产生,越界中断,,转越界中断的处理子程序存储管理?内存扩充
消除了固定分区管理造成的,内碎片,,但是不可避免的在内存空间造成,外碎片,。
例如：如图中已有 J1,J3,J4三个作业在内存，还有两个长度分别为 300K和 260K的空闲区。但是这两个空闲区都不满足作业 J5的 500K空间的要求。
采用移动（紧缩）技术。定时的或在内存紧张时，将内存中所有作业移到内存的一端，使其相邻。
存储管理
经过紧缩后的进程在内存中的位置发生了变化，
若不对程序和数据的地址进行修改，在进程就无法运行。
要使其运行，必须进行,动态重定位,
＝,紧缩的事机：
（ 1）一旦有归还的分区便进行紧缩，系统开销大。
（ 2）当发现内存不够用时 …,
＝,移动是有条件的存储管理 3.3 页式存储管理分页存储管理是解决存储零头的一种方法 。
动态重定位是解决存储器零头问题的一种途径,
但要移动大量信息花去不少处理机时间,代价比较高,
这是因为这种分配要求把作业必须安置在一连续存储区内的缘故,而分页存储管理正是要避开这种连续性要求 。
分为,实分页存储管理 和 虚分页存储管理存储管理一、分页式存储管理－ 实存模式下的页式存储管理
1.基本原理假设一个大型饭店，所有的客房都是标准的双人间，部分客房已经住进客人，现在又有一个旅游团要求入住。接待员统计了一下，对旅游团领队说：“贵团全体成员都能住下，
两人一个房间，但是不能住在同一楼层了，因为每层空着的客房不够，更没有几个挨着的。请原谅！”。对于这样的安排，一般人不会感到奇怪。因为旅游团本来就是由一位位个人或夫妻等组成的，而饭店的客房本来也是两人一间的，两人一组正好可住在一个客房里；另外，饭店几乎每天都有入住的和退房的客人，想在同一楼层找几间挨着的客房实在不容易。
存储管理 2.基本思想
① 将整个系统的内存空间划分成一系列大小相等的块，每一块称为一个物理块、物理页或实页，页架或页帧（ frame），可简称为块（ block）。所有的块按物理地址递增顺序连续编号为 0,1,2,…… 。
这里的块相当于饭店的客房，系统对内存分块相当于饭店把大楼所有的客房都设计成标准的双人间。
存储管理
② 每个作业的地址空间也划分成一系列与内存块一样大小的块，每一块称为一个逻辑页或虚页，
也有人叫页面，可简称为页（ page）。所有的页按照逻辑地址递增顺序连续编号为 0,1、
2,…… 。
这里，对作业地址空间分页就相当于把旅游团成员分成两人一组。
存储管理
③ 一个作业，只要它的总页数不大于内存中的可用块数，系统就可以对它实施分配。系统装入作业时，
以页为单位分配内存，一页分配一个块，作业所有的页所占的块可以不连续。系统同时为这个作业建立一个页号与块号的对照表，称为 页表 。
这好象饭店有个记录客户入住情况的客户登记表一样。另外，饭店安排客户入住是要查看全部客房的使用情况一览表，相应地系统给作业分配内存时要查看主存分配表或者内存块说明表。
存储管理
④ 每个块的大小是固定的，一般是个
1/2KB～ 4KB之间的数值（请读者思考：块尺寸为什么太大或太小都不好），而且必须是个 2的幂次。
对块尺寸这样规定相当于饭店规定客房是双人间。可以设想一下，如果上例中饭店所有的客房都是十人间的话，效益肯定不如全是双人间的好存储管理概括：实模式下分页存储管理的基本原理：
系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行时，一次性把作业的全部页面装入内存，各个页所占的内存块可以不连续。
这实际是个把作业从地址空间映射到存储空间的过程存储管理 3.地址转换
页面的划分完全是一种系统硬件的行为，
一个逻辑地址放到这种地址结构重，自然就分成了页号和页内单元号两部分。
页 号 页内地址
31 12 11 0
页面大小为,4KB
存储管理 （ 1）数据结构
在分页系统中，允许将作业（进程）的任一页装入到内存中的任一可用的物理块中，但进程的地址空间本来是连续的，若把他分页后装入到不相邻的物理块中，要保证系统仍能正确运行，就要实现从进程的逻辑地址变换为内存的物理地址。
所以，系统为每个进程建立一张页面映射表，简称页表。
存储管理
0页
1页
2页
3页
4页
…
N页页号 块号
0 4
1 7
2 3
3 5
4 2
… …
页表用户程序内存通过页表实现页面映射存储管理 （ 2）地址映射
在系统中设置地址变换机构，能将用户进程地址空间中的逻辑地址变为内存空间中的物理地址。
由于页面和物理块的大小相等，页内偏移地址和块内偏移地址是相同的。无须进行从页内地址到块内地址的转换。
地址变换机构的任务，关键是将逻辑地址中的页号转换为内存中的物理块号。物理块号内的偏移地址就是页内偏移地址。
页表的作用就是从页号到物理块号的转换，所以地址变换的任务借助于页表来完成的。
存储管理块号
8
页表地址 页表长度 页号 页内地址
0
1
2
3
块号 块内地址逻辑地址页表控制寄存器页表存储管理 2,分配与回收 (P76)
3.地址变换 (映射 )
存储管理?三,快表
因为页表是存放在内存中的 CPU要存取一个数据,需访问主存两次 。
第一次：访内存中的页表,找到该页的的物理块号,将此块号与页内地址拼结形成物理地址；
第二次：真正访问该物理地址,存取其中的内容 。
这样就把程序的执行速度降低一倍 。
为了提高存取速度,在地址变换机构中增设一组寄存器,
用来存放访问的那些页表 。
把存放在高速缓冲寄存器中的页表叫快表,这个高速缓冲寄存器又叫联想存贮器 。
存储管理
联想存贮器的存取速度比主存高,
但造价也高 。 因此只能采用少量,
整个系统通常只要用 8~16个寄存器即可使程序执行速度大大提高 。 快表的格式见下图 。
页号 块号 访问位 状态位存储管理
其中,,页号,是程序访问过的地址空间的页号，
,块号,是该页所对应的主存块号；访问位指示该页最近是否被访问过。,0”表示没有被访问,,1”表示访问过 ；,状态,位指示该寄存器是否被占用。通常
,0”表示空闲,,1”表示占用。
为了保证快表中的内容为现正运行程序的页表内容，
在每个程序被选中时，由恢复现场程序把快表的所有状态位清,0”，或恢复已保存的快表内容。
存储管理
当进程访问一页时，系统将页号与快表中的所有项进行并行比较。若访问的页在快表中，即可立即进行地址转换。
当被访问的页不在快表中时，就要将由慢表找到的内存块号与虚页号填入快表中，若快表已满，则置换其中访问位为 0的一项。
另外，在设置快表的情况下，硬件地址转换机构在进行地址变换时，同时开始两个变换过程。
存储管理
一个是利用主存页表进行的正常变换过程，另一个是利用快表进行的快速变换过程。一旦快表中有与查找的页号相符合时，则立即停止正常的访主存页表过程。并将快表中的块号与
CPU给出的页内位移相拼接，得到访问主存的绝对地址。从而结束了快表的查找工作。
存储管理
1.局部性原理 (principle of locality)：
指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。还可以表现为：
–时间局部性,一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；
–空间局部性,当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。
二、虚拟存储器 (Virtual Memory)
存储管理
局部性原理的具体体现：
程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令。
过程调用的嵌套深度一般不超过 5，因此执行的范围不超过这组嵌套的过程。
程序中存在相当多的循环结构，它们由少量指令组成，
而被多次执行。
程序中存在相当多对一定数据结构的操作，如数组操作，往往局限在较小范围内。
存储管理 (1),引入虚拟存储技术的好处
大程序,可在较小的可用内存中执行较大的用户程序；
大的用户空间,提供给用户可用的虚拟内存空间通常大于物理内存 (real memory)
并发,可在内存中容纳更多程序并发执行；
易于开发,与覆盖技术比较，不必影响编程时的程序结构存储管理 (2) 虚拟存储技术的特征
不连续性,物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间）
部分交换,与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的；
大空间,通过物理内存和快速外存相结合，提供大范围的虚拟地址空间存储管理返回
总容量不超过物理内存和外存交换区容量之和。 其运行速度接近于内存，每位的成本又接近于外存，是一种性能非常优越的存储管理技术
(3) 虚拟存储技术的种类虚拟页式虚拟段式虚拟段页式存储管理返回
1,基本原理
系统自动地将作业的地址空间分页，将系统的主存空间分块，
页与块等大小，在作业运行前，只把初始需要的一部分页面装入内存块里，运行中需要访问自己地址空间中的但当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调入内存，若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的置换策略自动选择一个或一些在内存的页面，把它们换出到外存。
这里的 请求调入 和 置换功能 都是比实分页存储管理增加的内容，是实现虚拟存储的主要功能。
3,虚拟页式 (virtual paging)
存储管理 为实现虚拟页式存储管理,
页表表目需要增加 外存块号,状态位,访问位 或 访问字段,修改位,存取控制字段 等。
外存块号指出该页在外存的地址，供调入该页时用；
状态为指示该页是否在内存，供程序访问时用，也是检查是否缺页的标志位；
访问位或访问字段则是该页被访问过的标志或该页被访问过的次数；
修改位表示该页是否被修改过；存取控制字段则是用来限制页面被安全共享的。
存储管理 2.主存页面分配策略,
在虚拟页式存储管理中，在给作业分配内存时，还必须考虑解决下面两个问题：
（ 1）如何发现要访问的页不在内存？
（ 2）作业运行过程中当发现要访问页不在内存发生缺页中断时，如何为所缺的页面分配内存？
mov A,B
存储管理 3.页面调入时机
（ 1） 请求调入
当发生页面故障时进行调度,即当进程访问不在内存的页面引发缺页中断时,由系统根据这种访问请求把所缺页面装入内存 。
优点,由请求调入策略装入的页一定会被访问,再加之比较容易实现,故在目前的虚拟存储器中,大多采用此策略 。
缺点,每次仅调入一页,增加了磁盘 I/O的启动频率 。
存储管理 （ 2）预调入
=>也称先行调度,即一页面被访问前就已经预先置入内存,
以减少今后的缺页率 。
=>主要适于进程的许多页存放在外存的连续区域中的情况 。
有的系统结合请求调入使用,即每次缺页时装入多个页面 。
优点,提高调页的 I/O效率 。
缺点,基于预测,若调入的页在以后很少被访问,则效率低 。 常用于程序装入时的调页 。
存储管理
4.页面调度算法 (淘汰算法或置换算法 ):
（ 1） 最佳淘汰算法 ——OPT(Optimal)
这是 Belady于 1966年提出的一种理论上的算法。该算法每次都淘汰以后永不使用的，或者过最长的时间后才会被访问的页面。
显然，采用这种算法会保证最低的缺页率，但它是无法实现的，因为它必须知道页面“将来”的访问情况。不过，
该算法仍有一定意义，可作为衡量其他算法优劣的一个标准。
存储管理 假定系统为某个进程分配了三个物理块，进程的访问顺序为 7,0,1,2,0,3,0,4,2,3,0，
3,2,1,2
采用 OPT淘汰算法：
7 7 7 2 2 2 2 2 2 2 2 2 2 2 2
0 0 0 0 0 0 4 4 4 0 0 0 0 0
1 1 1 3 3 3 3 3 3 3 3 1 1 * * * * * *
命中
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2
存储管理
（ 2）先进先出淘汰算法 ——FIFO
这是最早出现的淘汰算法。
总是淘汰最先进入内存的页面。它实现简单，只需把进程中已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存中最老的页面。
缺点：效率不高，因为它与进程实际的运行规律不相适应，
比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。出现 bleady现象。
存储管理
Belady现象,采用 FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，
缺页率反而提高的异常现象。
Belady现象的描述,一个进程 P要访问 M个页,OS
分配 N个内存页面给进程 P；对一个访问序列 S，发生缺页次数为 PE（ S,N）。当 N增大时,PE(S,N)时而增大，时而减小。
Belady现象的原因,FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。
存储管理采用 FIFO淘汰算法：
7 7 7 2 2 2 2 4 4 4 0 0 0 0 0
0 0 0 0 3 3 3 2 2 2 2 2 1 1
1 1 1 1 0 0 0 3 3 3 3 3 2
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2
存储管理 （ 3） 最近最久未使用算法
(LRU,Least Recently Used）
根据页面调入内存后的使用情况，选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。
OPT算法使用页面将要被访问的时间,LRU算法使用页面最后一次被访问的时间。二者唯一的差别是,OPT是向前看的，而 LRU是向后看的。
存储管理 下面给出 LRU的两个实现算法：
① 计时法,对于每一页面增设一个访问时间计时器,
每当一个页面被访问时,当时的绝对时钟内容被拷贝到对应的访问时间计时器中,这样系统记录了内存中所有页面最后一次被访问的时间 。 淘汰时,选取访问时间计时器的值最小的页面 。
②堆栈法,每当进程访问某页面时，便将该页面的页号从栈中移出，将它压入栈顶。栈顶始终是最新被访问的页面的编号。栈底则是最近最久未被使用的页面的页面号。
存储管理 假定现有一进程所访问的页面的页面号序列为,4,8,0,8,1,0,2,1,2,6
随着进程的访问，栈中页面号的变化情况：
2 1 2 6
1 0 1 1 2 1 2
0 8 8 1 0 0 0 0 1
8 8 0 0 8 8 8 8 8 0
4 4 4 4 4 4 4 4 4 4 8
4,8,0,8,1,0,1,2,1,2,6
存储管理 LRU的开销是很大的，必须有硬件的支持，完全由软件实现其速度至少会减少 10倍，因此 LRU近似算法更实用些。
（ 4 ） 二 次 机 会 淘 汰 算 法 ——SC(Second
Chance)淘汰算法
这是一种 LRU的近似算法，是通过对 FIFO算法进行简单改造，结合页表中的访问位而得来一种淘汰算法。
该算法首先检查位于 FIFO链链首的页，如果它的访问位为 0，
则选择该页淘汰；如果它的访问位为 1，则清除其访问位，
将它移至 FIFO链的链尾，重复此算法的查找过程，直至遇到新链首页是一个访问位为 0的较早进入内存的页为止，把它选为被淘汰的页。
存储管理 （ 5）时钟 (Clock)淘汰算法
该算法首先检测指针所指的页面，如果它的访问位为 0，则淘汰该页，新装入的页插入到此位置，然后指针前进一个位置；如果它的访问位为 1，则清除为 0，并将指针前进一个位置，继续检查访问位。重复此过程，直到找到访问位为 0的页面为止。
缺点：就是需要把访问位为 1的处于链首的页移至链尾，这需要一定的开销。一种改进的方法就是把进程所访问的页面链成一个环形链表，再设一个指针指向最老的页面，于是形成了一种简单实用的 LRU近似算法 —— 时钟淘汰算法。
存储管理 （ 6）最近未用淘汰算法 ——NRU(Not Used Recently)淘汰算法
它把 FIFO算法的思想与页面的访问位和修改位结合起来确定一个接近 LRU算法的淘汰对象。
该算法每次都尽量选择最近最久未被写过的页面淘汰，这种干净的页面可以不被写回到磁盘。在实现时，为每一个页面设置初始值 0的访问位和修改位。当对某页面执行写操作时，其修改位和访问位均由硬件置成 1；当对某页面执行读操作时，只有其访问位被硬件置成 1。系统每隔固定时间将所有访问位都清 0。
存储管理 按照下列次序选择被淘汰的页面：
① 访问位＝０,修改位＝０；直接淘汰；
② 访问位＝０,修改位＝１； 写回外存后 淘汰；
③ 访问位＝１,修改位＝０；直接淘汰；
④访问位＝１，修改位＝１； 写回外存后淘汰；
存储管理 影响缺页中断率的因素
（ 1）页面调度算法不合理
抖动又叫颠簸，是指一段时间里，页面在内存与外存之间频繁地调度或换入换出，以至于系统用于调度页面所需要的时间比进程实际运行所占用的时间还要多。
显然，抖动是由于缺页中断率很高而引起的一种坏现象，
它将严重影响系统的效率，甚至可能使系统全面崩溃。
存储管理 （ 2）分配给作业的内存块数太少
作业的缺页中断率与作业所占内存块数成反比。分配给作业的内存块数太少是导致抖动现象发生的最主要的原因，实验分析表明：对所有的程序来说，要使其有效地工作，它在内存中的页面数不应少于它的总页面数的一半。
存储管理 （ 3）页面大小的选择不合理
虽然缺页中断率与页面尺寸成反比，但页面尺寸却不能一味地求大，它一般在 0.5KB~4KB之间，是个实验统计值。
因为页面大时，页表较小，占空间少，查表速度快，缺页中断次数少，但页面调度时间长，页内碎片较大。页面小时，恰恰相反。
（ 4）用户程序编制的方法不合适作业的缺页中断率与程序的局部化（包括时间局部化和空间局部化）程度成反比。用户程序编制的方法不合适可能导致程序运行的时空复杂度高，缺页次数多。
