第四章 存储管理
4.1 概述
4.2 段式存储管理
4.3 页式存储管理
4.4 段页式存储管理
4.5 交换技术与覆盖技术
4.6 虚拟存储重要资源
,瓶颈,,关键,紧张帕金森定律内存多大,程序多长
4.1 概述
4.1.1 存储体系存储器的层次结构：
Cache
主存磁盘高速缓存 Cache：
少量的,非常快速,昂贵,易变的内存 RAM：
若干兆字节,中等速度,中等价格,
易变的磁盘：
数百兆或数千兆字节,低速,价廉,
不易变的由操作系统协调这些存储器的使用重要性：直接存取要求内存速度尽量快到与 CPU取指速度相匹配,大到能装下当前运行的程序与数据,否则 CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥 。
内存：
是由存储单元 （ 字节或字 ） 组成的一维连续的地址空间,简称内存空间 。 用来存放当前正在运行程序的代码及数据,是程序中指令本身地址所指的,亦即程序计数器所指的存储器 。
内存可以分为：
系统区：用于存放操作系统用户区：用于装入并存放用户程序和数据 。
4.1.2 存储管理目的用户对内存的使用要求
1,充分利用内存,为多道程序并发执行提供存储基础
2,尽可能方便用户使用自动装入用户程序用户程序中不必考虑硬件细节
3,系统能够解决程序空间比实际内存空间大的问题
4,程序在执行时可以动态伸缩
5,内存存取速度快
6,存储保护与安全
7,共享与通信
8,了解有关资源的使用状况
9,实现的性能和代价
4.1.3 存储管理的任务前提,引入多道程序设计技术满足用户要求
1、内存空间的管理、分配与回收记录内存的使用情况
——设臵相应的内存分配表
（ 内存分配回收的依据 ）
内存空间划分问题？
静态或动态,等长或不等长内存空间的管理、分配与回收内存分配表位示图表示法：用一位 （ bit） 表示一个空闲页面 （ 0：空闲,1：占用 ）
0 …..,11 0…...
第 0页第 1页 第 i页 第 n-1页内存空间的管理、分配与回收空闲页面表,包括首页面号和页面个数,连续若干的页面作为一组登记在表中空闲块表,空闲块首址和空闲块长度,
没有记录的区域即为进程所占用空闲块链表,将所有的空闲块链成一个链表内存空间的管理、分配与回收确定分配算法实施内存分配回收内存分配回收方式,静态分配与动态分配内存空间的管理、分配与回收连续性 ； 离散性驻留性 ； 交换性一次性； 多次性
2 存储共享内存共享：两个或多个进程共用内存中相同区域目的：
节省内存空间,提高内存利用率实现进程通信 （ 数据共享 ）
共享内容：
代码共享,要求代码为纯代码数据共享
3 存储保护与安全保护目的：
为多个程序共享内存提供保障,使在内存中的各道程序,只能访问它自己的区域,避免各道程序间相互干拢,
特别是当一道程序发生错误时,不致于影响其他程序的运行 。 通常由硬件完成保护功能,由软件辅助实现 。
（ 特权指令不能完成存储保护 。 ）
存储保护保护系统程序区不被用户侵犯
（ 有意或无意的 ）
不允许用户程序读写不属于自己地址空间的数据
（ 系统区地址空间,其他用户程序的地址空间 ）
保护过程 ----防止地址越界每个进程都有自己独立的进程空间,
如果一个进程在运行时所产生的地址在其地址空间之外,则发生地址越界 。 即当程序要访问某个内存单元时,由硬件检查是否允许,如果允许则执行,否则产生地址越界中断,由操作系统进行相应处理 。
保护过程 ----防止地址越界一般由硬件提供一对寄存器：
基址寄存器：存放起始地址限长寄存器：存放长度
（ 上界寄存器 /下界寄存器 ）
保护过程 ----防止操作越权对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。
如果一个进程对共享区域的访问违反了权限规定，则发生操作越权。
即读写保护。
4 内存“扩充”
通过虚拟存储技术实现用户在编制程序时,不应该受内存容量限制,所以要采用一定技术来 "扩充 "内存的容量,使用户得到比实际内存容量大的多的内存空间 。
内存“扩充”
具体实现是在硬件支持下,软硬件相互协作,将内存和外存结合起来统一使用 。 通过这种方法把内存扩充,使用户在编制程序时不受内存限制 。
5 地址映射（地址重定位，地址变换）
(1) 逻辑地址 （ 相对地址,虚地址 ）
(2) 物理地址 （ 绝对地址,实地址 ）
(3) 地址映射地址映射
BA=1000
Load A 200
3456
。
。
。
1200
物理地址空间
Load A data1
data1 3456
源程序
Load A 200
3456
0
100
200
编译连接逻辑地址空间
(1)逻辑地址（相对地址，虚地址）
用户的程序经过汇编或编译后形成目标代码,目标代码通常采用相对地址的形式,其首地址为 0,其余指令中的地址都相对于首地址而编址 。
不能用逻辑地址在内存中读取信息 。
(2)物理地址 （ 绝对地址,实地址 ）
内存中存储单元的地址,可直接寻址 。
(3)地址映射为了保证 CPU执行指令时可正确访问存储单元,需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址,这一过程称为地址映射
0
3456..
...
.
LOAD A 200
...
...
0
100
200
300
...
...
...
LOAD A 200
3456
逻辑地址空间
1100
1200
1300
物理地址空间
200
VR
+
1000
BR
原因,当程序装入内存时,操作系统要为该程序分配一个合适的内存空间,由于程序的逻辑地址与分配到内存物理地址不一致,而 CPU执行指令时,是按物理地址进行的,所以要进行地址转换 。
静态重定位当用户程序被装入内存时,一次性实现逻辑地址到物理地址的转换,
以后不再转换 （ 一般在装入内存时由软件完成 ） 。
动态重定位在程序运行过程中要访问数据时再进行地址变换 （ 即在逐条指令执行时完成地址映射 。 一般为了提高效率,
此工作由硬件地址映射机制来完成 。
硬件支持,软硬件结合完成 ） 。
硬件上需要一对寄存器的支持 。
4.1.4 各种存储管理方案单一用户 （ 连续区 ） 存储管理：
单用户系统在一段时间内,只有一个进程在内存,故内存分配管理十分简单,内存利用率低 。 内存分为两个区域,一个供操作系统使用,
一个供用户使用 。
用户程序位于 RAM中的操作系统
0xFFF...
0
位于 RAM中的操作系统用户程序
0
ROM中的设备驱动程序用户程序位于 RAM中的操作系统
0
分区存储管理方案系统把内存用户区划分为若干分区，
分区大小可以相等，也可以不等。一个进程占据一个分区。
固定分区可变分区固定分区预先把可分配的主存储器空间分割成若干个连续区域,称为一个分区 。
每个分区的大小可以相同也可以不同,如图所示 。 但分区大小固定不变,每个分区装一个且只能装一个作业 。
存储分配：如果有一个空闲区,则分配给进程 。
分区 4
分区 3
分区 2
分区 1
操作系统多个输入队列单个输入队列分区 4
分区 3
分区 2
分区 1
操作系统
700K
400K
100K
0
固定分区内存管理：设臵内存分配表内存分配：
内存回收：简单缺点：内存利用率不高分区号 起始地址 长度 状态 进程名可变分区内存的分配：内存不是预先划分好的,
而是当作业装入时,根据作业的需求和内存空间的使用情况来决定是否分配 。 若有足够的空间,则按需要分割一部分分区给该进程；否则令其等待主存空间 。
内存的管理：
设臵内存空闲块表 ——记录了空闲区起始地址和长度 。
内存分配：动态分配内存的回收：当某一块归还后,前后空间合并,修改内存空闲块表 。
内存分配：三种分配算法首先适配算法：
当接到内存申请时,查空闲块表,找到第一个不小于请求的空块,将其分割并分配 。
（ 特点：简单,快速分配 ）
最佳适配算法：
接到内存申请时,在空闲块表中找到一个不小于请求的最小空块进行分配 。
（ 特点：用最小空间满足要求 ）
最坏适配算法：
接到内存申请时,在空闲块表中找到一个不小于请求的最大空块进行分配 。
（ 特点：当分割后空闲块仍为较大空块 ）
碎片问题：
经过一段时间的分配回收后,内存中存在很多很小的空闲块 。 它们每一个都很小,不足以满足分配要求；
但其总和满足分配要求 。 这些空闲块被称为碎片 。
造成存储资源的浪费碎片问题的解决：
紧凑技术：通过在内存移动程序,将所有小的空闲区域合并为大的空闲区域 。
（ 紧缩技术,紧致技术,浮动技术,
搬家技术 ）
问题：开销大；移动时机讨论：
优点,A 便于动态申请内存
B 便于共享内存
C 便于动态链接缺点：碎片问题 (外碎片 )
4.2 段式存储管理
4.2.1 基本思想 （ 工作原理 ）
...
0
S
工作区段 [B]
主程序段 [M]
...
...
0
E
P
子程序段 [X]
0
K
...
CALL [X] [E]
...
...
...CALL [Y] [F]
CALL [A] 116
...
...
0
F
L
子程序段 [Y]
0
116
N
数组 [A]
12345
...
操作系统
.
.
.
.
.
B0S
A0N
Y0L
X0P
M0K
逻辑段号
0
1
2
3
4
作业 1的地址空间
1000
3200
5000
6000
8000
P
K
S
L
N
主存
K 3200
P 1500
L 6000
N 8000
S 5000
长度 段地址
0
1
2
3
4
操作系统用户程序划分按程序自身的逻辑关系划分为若干个程序段,每个程序段都有一个段名,
且有一个段号 。 段号从 0开始,每一段也从 0开始编址,段内地址是连续的 。
逻辑地址内存划分内存空间被动态的划分为若干个长度不相同的区域,这些区域被称为物理段,每个物理段由起始地址和长度确定 。
段号 段内地址内存分配以段为单位分配内存,每一个段在内存中占据连续空间 （ 内存随机分割,
需要多少分配多少 ）,但各段之间可以不连续存放 。
4.2.2 管理段表：
它记录了段号,段的首 （ 地 ） 址和长度之间的关系 。
每一个程序设一个段表段号
0
1
2
空闲块管理：
记录了空闲区起始地址和长度 。
内存的分配算法：
首先适配；最佳适配；最坏适配
4.2.3 硬件支持一对寄存器段表始址寄存器：
用于保存正在运行进程的段表的始址 。
段表长度寄存器：
用于保存正在运行进程的段表的长度 （ 例如上图的段表长度为 3） 。
ClCb
+
段号 S 段内地址 d
比较比较
b + d
比较段 表
S>= Cl
快表物理地址段表始址寄存器 段表长度寄存器 逻辑地址
l b,,.
S l b
地址越界
d>=1
d>=1
地址映射及存储保护机制地址越界地址越界比较介于内存与寄存器之间的存储机制,
它又叫快表 。
用途：保存正在运行进程的段表的子集 （ 部分表项 ） 。
特点：按内容并行查找 。
相联（联想）存储器引入快表的作用：
为了提高地址映射速度。
快表项目：段号；段始址；段长度；
标识 （ 状态 ） 位；访问位,淘汰位 。
快表淘汰问题？
4.2.4 段的共享作业
4.2.5 段的保护作业优点：
便于动态申请内存管理和使用统一化便于共享便于动态链接缺点：产生碎片与可变分区存储管理方案区别
4.3 页式存储管理
4.3.1 基本思想 （ 工作原理 ）
用户程序划分把用户程序按逻辑页划分成大小相等的部分,称为页 。 从 0开始编制页号,
页内地址是相对于 0编址 。
逻辑地址用户程序的划分是由系统自动完成的,对用户是透明的 。 一般,一页的大小为 2的整数次幂,因此,地址的高位部分为页号,低位部分为页内地址 。
页号 页内地址
0111223
页号 P 页内位移量 W
编号 0~4096 相对地址 0~4096
内存空间：
按页的大小划分为大小相等的区域,
称为内存块 （ 又叫物理页面 ） 。
内存分配：
以页为单位进行分配,并按作业的页数多少来分配 。 逻辑上相邻的页,
物理上不一定相邻 。
..
.
0
1
2
3
4
5
6
0
1
2
3
4
5
6作业的地址空间页框
（物理块）页号页表 主存中页框
（物理块）
..
..
4.3.2 管理
1.页表：系统为每个进程都建立了一个页表,页表给出逻辑地址号和具体内存块号相应的关系
2.空块管理 ——总页表
3.内存的分配与回收计算一个作业所需要的总块数 。
查总页表,看看是否还有 N个空闲块 。
如果有相应空闲块,则页表长度为该为 N,可填入 PCB中 。 （ 申请页表区,
把页表始址填入 PCB） 。
分配 N个空闲块,将块号和页号填入页表 （ 页表号实际不用填 ） 。
修改总页表 。
4.3.3 硬件支持
1,一对寄存器：
a 页表始址寄存器
b 页表长度寄存器
2,相联寄存器 ——快表
1） 页号 2） 页在内存的块号 3） 标识位 4） 淘汰位
p’
页表地址越界
l
比较
P>=1
p p’
.,,
快表
b
+
页号 p 页内地址 d
P’ d
物理地址页表地址寄存器 页表长度寄存器 逻辑地址地址映射机制
4.3.4 页的共享作业
4.3.5 页的保护作业
4.3.6 优缺点优点,a 解决了碎片问题
b 便于管理缺点,a 不易实现共享
b 不便于动态连接
4.4 段页式存储管理
4.4.1 产生背景及基本思想背景：结合了二者优点克服了二者的缺点基本思想：
用户程序划分：按段式划分 （ 对用户来讲,按段的逻辑关系进行划分；
对系统讲,按页划分每一段 ）
逻辑地址：
内存划分：按页式存储管理方案内存分配：以页为单位进行分配
4.4.2 管理
1 段表：记录了每一段的页表始址和页表长度
2 页表：记录了逻辑页号与内存块号的对应关系 。 （ 每一段有一个,一个程序可能有多个页表 ）
3 空块管理：
4 分配：同页式管理
4.4.3 硬件支持段表始址寄存器段表长度寄存器相联存储器 （ 快表 ）
4.5 交换技术与覆盖技术在多道环境下扩充内存的方法,用以解决在较小的存储空间中运行较大程序时遇到的矛盾 。
覆盖技术主要用在早期的操作系统中交换技术被广泛用于小型分时系统中,
交换技术的发展导致了虚存技术的出现交换技术与覆盖技术共同点：
进程的程序和数据主要放在外存,当前需要执行的部分放在内存,内外存之间进行信息交换不同点：如何控制交换？
4.5.1 覆盖技术覆盖：一个作业的若干程序段,或几个作业的某些部分共享某一个存储空间 。
把程序划分为若干个功能上相对独立的程序段,按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域 。
程序段先保存在磁盘上,当有关程序段的前一部分执行结束,把后续程序段调入内存,覆盖前面的程序段
（ 内存,扩大,了 ） 。
一般要求作业各模块之间有明确的调用结构,程序员要向系统指明覆盖结构,然后由由操作系统完成自动覆盖 。
A
8K
E
4K
F
10K
C
10K
B
8K
D
12K
作业 X的调用结构作业 X的常驻区
A（ 8K）
覆盖区 0
（ 10K）
覆盖区 1
（ 12K）
BC
DEF
缺点：对用户不透明,增加了用户负担 。
例子：目前这一技术用于小型系统中的系统程序的内存管理上,MS-
DOS的启动过程中,多次使用覆盖技术；启动之后,用户程序区 TPA
的高端部分与 COMMAND.COM暂驻模块也是一种覆盖结构 。
4.5.2 交换技术当内存空间紧张时,系统将内存中某些进程暂时移到外存,把外存中某些进程换进内存,占据前者所占用的区域,这种技术是进程在内存与外存之间的动态调度 。 多用于分时系统中 。
交换技术实现中的几个问题：
1,选择原则即将哪个进程换出 /内存？
例子：分时系统,时间片轮转法或基于优先数的调度算法在选择换出进程时,要确定换出的进程是要长时间等待的需要特殊考虑的是：任何等待 I/O的进程中存在的问题解决：
从不换出处于等待 I/O状态的进程仅通过操作系统缓冲执行 I/O操作总之,有些 I/O进程因 DMA而不能换出内存或换出前需要操作系统的特殊帮助
2,交换时机的确定何时需发生交换？
例子：
只要不用就换出 （ 很少再用 ）
只在内存空间不够或有不够的危险时换出
3,交换时需要做哪些工作？
需要一个盘交换区：必须足够大以存放所有用户程序的所有内存映像的拷贝；必须对这些内存映像的直接存取 。
切换程序
4,换入回内存时位臵的确定换出后再换入的内存位臵一定要在换出前的原来位臵上吗？
受地址,绑定,技术的影响,即绝对地址产生时机的限制 。
5,交换所需时间导致：
对时间片的影响对程序长度的使用要求动态扩充时要及时记录的管理要求与覆盖技术相比,交换技术不要求用户给出程序段之间的逻辑覆盖结构 。
而且,交换发生在进程或作业之间,
而覆盖发生在同一进程或作业内 。
此外,覆盖只能覆盖那些与覆盖段无关的程序段 。
4.6 虚拟存储连续性 ； 离散性驻留性 ； 交换性一次性； 多次性以 CPU时间和外存空间换取昂贵内存空间,这是操作系统中的资源转换技术
4.6.1 概述
1,问题的提出：
a 程序大于内存
b 程序暂时不执行或运行完是否还要占用内存虚拟存储器的基本思想是：程序,数据,堆栈的大小可以超过内存的大小,
操作系统把程序当前使用的部分保留在内存,而把其它部分保存在磁盘上,
并在需要时在内存和磁盘之间动态交换 。
虚拟存储器支持多道程序设计技术
CPU
MMU
内存 磁盘控制器总线
X60K-64K
X56K-60K
X52K-56K
X48K-52K
744K-48K
X40K-44K
536K-40K
X32K-36K
X28K-32K
X24K-28K
320K-24K
416K-20K
012K-16K
68K-12K
14K-8K
20K-4K
X
X
3
4
0
6
1
2
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
虚地址空间物理地址空间
} 虚页页框
000 015
000 014
000 013
000 012
111 111
000 010
101 19
000 08
000 07
000 06
011 15
100 14
000 13
110 12
001 11
010 10
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
110
在 /不在内存页表虚地址
8196
物理地址
24580
2,程序局部性原理在一段时间内一个程序的执行往往呈现出高度的局部性,表现在时间与空间两方面时间局部性：
一条指令被执行了,则在不久的将来它可能再被执行空间局部性：
若某一存储单元被使用,则在一定时间内,与该存储单元相邻的单元可能被使用
3、虚拟存储技术虚存：把内存与外存有机的结合起来使用,从而得到一个容量很大的
,内存,,这就是虚存 。
实现思想：当进程运行时,先将一部分程序装入内存,另一部分暂时留在外存,当要执行的指令不在内存时,由系统自动完成将它们从外存调入内存工作 。
4.6.2 虚拟页式存储管理
1,基本工作原理在进程开始运行之前,不是装入全部页面,而是装入一个或零个页面,之后根据进程运行的需要,动态装入其它页面；当内存空间已满,而又需要装入新的页面时,则根据某种算法淘汰某个页面,以便装入新的页面
2、页表表项页号,驻留位,内存块号,外存地址,访问位,修改位驻留位 （ 中断位 ）,表示该页是在内存还是在外存访问位：根据访问位来决定淘汰哪页 （ 由不同的算法决定 ）
修改位：查看此页是否在内存中被修改过
3、缺页中断在地址映射过程中,在页表中发现所要访问的页不在内存,则产生缺页中断 。 操作系统接到此中断信号后,
就调出缺页中断处理程序,根据页表中给出的外存地址,将该页调入内存,使作业继续运行下去 。
如果内存中有空闲块,则分配一页,
将新调入页装入内存,并修改页表中相应页表项目的驻留位及相应的内存块号 。
若此时内存中没有空闲块,则要淘汰某页,若该页在内存期间被修改过,
则要将其写回外存 。
4、页面淘汰算法
先进先出页面淘汰算法 （ FIFO）
选择在内存中驻留时间最长的页并淘汰之 。
理想淘汰算法 —最佳页面算法 （ OPT）
淘汰以后不再需要的或最远的将来才会用到的页面 。
最近未使用页面淘汰算法 （ NRU）
选择在最近一段时间内未使用过的一页并淘汰之 。
实现：设臵两位访问位 （ R）,修改位 （ M）
启动一个进程时,R,M臵 0
R被定期清零发生缺页中断时,操作系统检查 R,M：
第 0类：无访问,无修改第 1类：无访问,有修改第 2类：有访问,无修改第 3类：有访问,有修改操作系统随机从编号最小的非空类中选择一页淘汰
最近最少使用页面淘汰算法 （ LRU）
选择最后一次访问时间距离当前时间最长的一页并淘汰之 。
即淘汰没有使用的时间最长的页 。
实现代价很高硬件方法
LRU的软件解决方案：
最不经常使用 （ NFU）
选择访问次数最少的页面淘汰之实现：软件计数器,一页一个,初值为 0。 每次时钟中断时,计数器加 R。
发生缺页中断时,选择计数器值最小的一页淘汰改进：计数器在加 R前先右移一位
R位加到计数器的最左端称为老化算法
第二次机会淘汰算法 (SCR)
按照先进先出算法选择某一页面,
检查其访问位,如果为 0,则淘汰该页,如果为 1,则给第二次机会,并将访问位臵 0。
时钟页面淘汰算法 （ Clock）
在实现上对第二次机会算法的改进环形链表 （ 类似钟表面 ）
表指针：指向最老的页面例子 1：计算缺页次数某程序在内存中分配三个页面,初始为空,页面走向为 4,3,2,1,4，
3,5,4,3,2,1,5。
FIFO 4 3 2 1 4 3 5 4 3 2 1 5
页 1 4 3 2 1 4 3 5 5 5 2 1 1
页 2 4 3 2 1 4 3 3 3 5 2 2
页 3 4 3 2 1 4 4 4 3 5 5
x x x x x x xx x?
共缺页中断 9次
LRU 4 3 2 1 4 3 5 4 3 2 1 5
页 1 4 3 2 1 4 3 5 4 3 2 1 5
页 2 4 3 2 1 4 3 5 4 3 2 1
页 3 4 3 2 1 4 3 5 4 3 2
x x x x x x xx x x
共缺页中断 10次
OPT 4 3 2 1 4 3 5 4 3 2 1 5
页 1 4 3 2 1 1 1 5 5 5 2 1 1
页 2 4 3 3 3 3 3 3 3 5 5 5
页 3 4 4 4 4 4 4 4 4 4 4
x x x xxx x?
共缺页中断 7次例子 2：计算缺页次数某程序在内存中分配 m页初始为空,
页面走向为 1,2,3,4,1,2,5，
1,2,3,4,5。 当 m=3,m=4时缺页中断分别为多少？ 用 FIFO算法 。
例子 2：计算缺页次数
m=3时,缺页中断 9次
m=4时,缺页中断 10次注,FIFO页面淘汰算法会产生异常现象,当分配给进程的物理页面数增加时,缺页次数反而增加 。
5、影响缺页次数的因素
(1) 分配给进程的物理页面数
(2) 页面本身的大小
(3) 程序的编制方法
(4) 页面淘汰算法例子 3：内存分配一页,初始时第一页在内存,页面大小为 128个整数 。
矩阵 A128X128按行存放 。
程序编制方法 1：
For j:=1 to 128
For i:=1 to 128
A[i,j]:=0;
程序编制方法 2：
For i:=1 to 128
For j:=1 to 128
A[i,j]:=0;
4.6.3 性能问题
1,颠簸 （ 抖动 ）
在虚存中,页面在内存与外存之间频繁调度,以至于调度页面所需时间比进程实际运行的时间还多,此时系统效率急剧下降,甚至导致系统崩溃 。 这种现象为颠簸 。
原因：
a 页面淘汰算法不合理
b 分配给进程的物理页面数太少
2、工作集模型基本思想：根据程序的局部性原理,
一般情况下,进程在一段时间内总是集中访问一些页面,这些页面称为活跃页面,如果分配给一个进程的物理页面数太少了,使该进程所需的活跃页面不能全部装入内存,
则进程在运行过程中将频繁发生中断 。
如果能为进程提供与活跃页面数相等的物理页面数,则可减少缺页中断次数 。
工作集：
对于给定的访问序列选取定长的区间,
称为工作集窗口,落在工作集窗口中的页面集合称为工作集 。
工作集：
内容取决于页的三个因素
a 访页序列特性
b 时刻 Ti
c 窗口长度 (△ )
例：
26157775162341234443434441327
| |t1 | |t2
ws(t1)={1,2,5,6,7}
ws(t2)={3,4}
4.6.4 虚拟段式存储管理
1,段表内容增加：特征位 （ 在 /不在内存,是否可共享 ）,存取权限位 （ 读,写,
执行 ）,标志位 （ 是否修改过,能否移动 ）,扩充位 （ 固定长 /可扩充 ）
2,越界中断处理进程在执行过程中,有时需要扩大分段,如数据段 。 由于要访问的地址超出原有的段长,所以发越界中断 。 操作系统处理中断时,首先判断该段的,扩充位,,如可扩充,
则增加段的长度；否则按出错处理 。
3,缺段中断处理检查内存中是否有足够的空闲空间
a 若有,则装入该段,修改有关数据结构,中断返回
b 若没有,检查内存中空闲区的总和是否满足要求,是则应采用紧缩技术,转 a；否则,淘汰一些段,转 a
4,段的动态链接大型程序：
若干程序段,若干数据段一些熟知的事实：
* 进程的某些程序段在进程运行期间可能根本不用
* 互斥执行的程序段没有必要同时驻留内存
* 有些程序段执行一次后不再用到静态链接：为了程序正确执行,必须由连接装配程序把它们连接成一个可运行的目标程序,并在程序运行前都装入内存 。
问题：花费时间,浪费空间
（ 1） 段的动态链接在程序开始运行时,只将主程序段装配好并调入内存,其它各段的装配是在主程序段的运行过程中逐步完成 。 每当需要调用一个新段时,再将这个新段装配好,并与主程序段链接 。
页式存储管理：难以完成动态链接,
其逻辑地址是一维的
（ 2） 链接间接字和链接中断机器指令：直接寻址,间接寻址
LOAD 100
LOAD 100
600
600
800
直接寻址间接寻址
100
100
数据间接字数据采用间接寻址时,间接地址指示的单元的内容称为间接字,在间接字中,
包含了直接地址,还包含了附加的状态位 。 格式为：
L 直接地址
L：链接标志位
L=0：该段已经建立了链接
L=1：该段尚未链接处理机在执行间接指令时,其硬件能自动对链接字中连接标志位进行判断 。
当 L=1时,硬件自动发链接中断,并停止执行该间接指令,转去执行链接中断处理程序 。 处理完后 （ L已被中断处理程序改为 0）,再重新执行该间接指令；若 L=0,则根据间接字中的直接地址去取数据 。
（ 3） 编译程序的准备工作
LOAD 1,[A]|<B> 编译前
LOAD* 1,3|100
...
...
100 6781 3...
678 7“[A]|<B>”...
编译后链接前
3段
LOAD* 1,3|100
100
链接后
678 7“[A]|<B>
1200 4
4段
120 <Y>,12345678
（ 4） 链接中断处理
* 根据链接间接字找出要访问段的符号名和段内地址
* 分配段号，检查该段是否在内存，
若不在，则从外存调入，并登记段表，修改内存分配表
* 修改间接字：修改连接标志位为 0，
修改直接地址
* 重新启动被中断的指令执行
（ 5） 其他问题纯段和杂段纯段：被链接段是可再入的，或称
“纯的”，即该段在执行过程中，
不允许修改其中的数据。
杂段：又称链接段，将程序所有可能变更的数据，包括链接间接字和某些临时变量、内部变量等，放在杂段中。
其他有关设计问题：
多级页表
局部与全局分配策略
页面尺寸实现时涉及的问题：
指令备份
锁定内存页
共享页
后备存储
分页程序
4.1 概述
4.2 段式存储管理
4.3 页式存储管理
4.4 段页式存储管理
4.5 交换技术与覆盖技术
4.6 虚拟存储重要资源
,瓶颈,,关键,紧张帕金森定律内存多大,程序多长
4.1 概述
4.1.1 存储体系存储器的层次结构：
Cache
主存磁盘高速缓存 Cache：
少量的,非常快速,昂贵,易变的内存 RAM：
若干兆字节,中等速度,中等价格,
易变的磁盘：
数百兆或数千兆字节,低速,价廉,
不易变的由操作系统协调这些存储器的使用重要性：直接存取要求内存速度尽量快到与 CPU取指速度相匹配,大到能装下当前运行的程序与数据,否则 CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥 。
内存：
是由存储单元 （ 字节或字 ） 组成的一维连续的地址空间,简称内存空间 。 用来存放当前正在运行程序的代码及数据,是程序中指令本身地址所指的,亦即程序计数器所指的存储器 。
内存可以分为：
系统区：用于存放操作系统用户区：用于装入并存放用户程序和数据 。
4.1.2 存储管理目的用户对内存的使用要求
1,充分利用内存,为多道程序并发执行提供存储基础
2,尽可能方便用户使用自动装入用户程序用户程序中不必考虑硬件细节
3,系统能够解决程序空间比实际内存空间大的问题
4,程序在执行时可以动态伸缩
5,内存存取速度快
6,存储保护与安全
7,共享与通信
8,了解有关资源的使用状况
9,实现的性能和代价
4.1.3 存储管理的任务前提,引入多道程序设计技术满足用户要求
1、内存空间的管理、分配与回收记录内存的使用情况
——设臵相应的内存分配表
（ 内存分配回收的依据 ）
内存空间划分问题？
静态或动态,等长或不等长内存空间的管理、分配与回收内存分配表位示图表示法：用一位 （ bit） 表示一个空闲页面 （ 0：空闲,1：占用 ）
0 …..,11 0…...
第 0页第 1页 第 i页 第 n-1页内存空间的管理、分配与回收空闲页面表,包括首页面号和页面个数,连续若干的页面作为一组登记在表中空闲块表,空闲块首址和空闲块长度,
没有记录的区域即为进程所占用空闲块链表,将所有的空闲块链成一个链表内存空间的管理、分配与回收确定分配算法实施内存分配回收内存分配回收方式,静态分配与动态分配内存空间的管理、分配与回收连续性 ； 离散性驻留性 ； 交换性一次性； 多次性
2 存储共享内存共享：两个或多个进程共用内存中相同区域目的：
节省内存空间,提高内存利用率实现进程通信 （ 数据共享 ）
共享内容：
代码共享,要求代码为纯代码数据共享
3 存储保护与安全保护目的：
为多个程序共享内存提供保障,使在内存中的各道程序,只能访问它自己的区域,避免各道程序间相互干拢,
特别是当一道程序发生错误时,不致于影响其他程序的运行 。 通常由硬件完成保护功能,由软件辅助实现 。
（ 特权指令不能完成存储保护 。 ）
存储保护保护系统程序区不被用户侵犯
（ 有意或无意的 ）
不允许用户程序读写不属于自己地址空间的数据
（ 系统区地址空间,其他用户程序的地址空间 ）
保护过程 ----防止地址越界每个进程都有自己独立的进程空间,
如果一个进程在运行时所产生的地址在其地址空间之外,则发生地址越界 。 即当程序要访问某个内存单元时,由硬件检查是否允许,如果允许则执行,否则产生地址越界中断,由操作系统进行相应处理 。
保护过程 ----防止地址越界一般由硬件提供一对寄存器：
基址寄存器：存放起始地址限长寄存器：存放长度
（ 上界寄存器 /下界寄存器 ）
保护过程 ----防止操作越权对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。
如果一个进程对共享区域的访问违反了权限规定，则发生操作越权。
即读写保护。
4 内存“扩充”
通过虚拟存储技术实现用户在编制程序时,不应该受内存容量限制,所以要采用一定技术来 "扩充 "内存的容量,使用户得到比实际内存容量大的多的内存空间 。
内存“扩充”
具体实现是在硬件支持下,软硬件相互协作,将内存和外存结合起来统一使用 。 通过这种方法把内存扩充,使用户在编制程序时不受内存限制 。
5 地址映射（地址重定位，地址变换）
(1) 逻辑地址 （ 相对地址,虚地址 ）
(2) 物理地址 （ 绝对地址,实地址 ）
(3) 地址映射地址映射
BA=1000
Load A 200
3456
。
。
。
1200
物理地址空间
Load A data1
data1 3456
源程序
Load A 200
3456
0
100
200
编译连接逻辑地址空间
(1)逻辑地址（相对地址，虚地址）
用户的程序经过汇编或编译后形成目标代码,目标代码通常采用相对地址的形式,其首地址为 0,其余指令中的地址都相对于首地址而编址 。
不能用逻辑地址在内存中读取信息 。
(2)物理地址 （ 绝对地址,实地址 ）
内存中存储单元的地址,可直接寻址 。
(3)地址映射为了保证 CPU执行指令时可正确访问存储单元,需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址,这一过程称为地址映射
0
3456..
...
.
LOAD A 200
...
...
0
100
200
300
...
...
...
LOAD A 200
3456
逻辑地址空间
1100
1200
1300
物理地址空间
200
VR
+
1000
BR
原因,当程序装入内存时,操作系统要为该程序分配一个合适的内存空间,由于程序的逻辑地址与分配到内存物理地址不一致,而 CPU执行指令时,是按物理地址进行的,所以要进行地址转换 。
静态重定位当用户程序被装入内存时,一次性实现逻辑地址到物理地址的转换,
以后不再转换 （ 一般在装入内存时由软件完成 ） 。
动态重定位在程序运行过程中要访问数据时再进行地址变换 （ 即在逐条指令执行时完成地址映射 。 一般为了提高效率,
此工作由硬件地址映射机制来完成 。
硬件支持,软硬件结合完成 ） 。
硬件上需要一对寄存器的支持 。
4.1.4 各种存储管理方案单一用户 （ 连续区 ） 存储管理：
单用户系统在一段时间内,只有一个进程在内存,故内存分配管理十分简单,内存利用率低 。 内存分为两个区域,一个供操作系统使用,
一个供用户使用 。
用户程序位于 RAM中的操作系统
0xFFF...
0
位于 RAM中的操作系统用户程序
0
ROM中的设备驱动程序用户程序位于 RAM中的操作系统
0
分区存储管理方案系统把内存用户区划分为若干分区，
分区大小可以相等，也可以不等。一个进程占据一个分区。
固定分区可变分区固定分区预先把可分配的主存储器空间分割成若干个连续区域,称为一个分区 。
每个分区的大小可以相同也可以不同,如图所示 。 但分区大小固定不变,每个分区装一个且只能装一个作业 。
存储分配：如果有一个空闲区,则分配给进程 。
分区 4
分区 3
分区 2
分区 1
操作系统多个输入队列单个输入队列分区 4
分区 3
分区 2
分区 1
操作系统
700K
400K
100K
0
固定分区内存管理：设臵内存分配表内存分配：
内存回收：简单缺点：内存利用率不高分区号 起始地址 长度 状态 进程名可变分区内存的分配：内存不是预先划分好的,
而是当作业装入时,根据作业的需求和内存空间的使用情况来决定是否分配 。 若有足够的空间,则按需要分割一部分分区给该进程；否则令其等待主存空间 。
内存的管理：
设臵内存空闲块表 ——记录了空闲区起始地址和长度 。
内存分配：动态分配内存的回收：当某一块归还后,前后空间合并,修改内存空闲块表 。
内存分配：三种分配算法首先适配算法：
当接到内存申请时,查空闲块表,找到第一个不小于请求的空块,将其分割并分配 。
（ 特点：简单,快速分配 ）
最佳适配算法：
接到内存申请时,在空闲块表中找到一个不小于请求的最小空块进行分配 。
（ 特点：用最小空间满足要求 ）
最坏适配算法：
接到内存申请时,在空闲块表中找到一个不小于请求的最大空块进行分配 。
（ 特点：当分割后空闲块仍为较大空块 ）
碎片问题：
经过一段时间的分配回收后,内存中存在很多很小的空闲块 。 它们每一个都很小,不足以满足分配要求；
但其总和满足分配要求 。 这些空闲块被称为碎片 。
造成存储资源的浪费碎片问题的解决：
紧凑技术：通过在内存移动程序,将所有小的空闲区域合并为大的空闲区域 。
（ 紧缩技术,紧致技术,浮动技术,
搬家技术 ）
问题：开销大；移动时机讨论：
优点,A 便于动态申请内存
B 便于共享内存
C 便于动态链接缺点：碎片问题 (外碎片 )
4.2 段式存储管理
4.2.1 基本思想 （ 工作原理 ）
...
0
S
工作区段 [B]
主程序段 [M]
...
...
0
E
P
子程序段 [X]
0
K
...
CALL [X] [E]
...
...
...CALL [Y] [F]
CALL [A] 116
...
...
0
F
L
子程序段 [Y]
0
116
N
数组 [A]
12345
...
操作系统
.
.
.
.
.
B0S
A0N
Y0L
X0P
M0K
逻辑段号
0
1
2
3
4
作业 1的地址空间
1000
3200
5000
6000
8000
P
K
S
L
N
主存
K 3200
P 1500
L 6000
N 8000
S 5000
长度 段地址
0
1
2
3
4
操作系统用户程序划分按程序自身的逻辑关系划分为若干个程序段,每个程序段都有一个段名,
且有一个段号 。 段号从 0开始,每一段也从 0开始编址,段内地址是连续的 。
逻辑地址内存划分内存空间被动态的划分为若干个长度不相同的区域,这些区域被称为物理段,每个物理段由起始地址和长度确定 。
段号 段内地址内存分配以段为单位分配内存,每一个段在内存中占据连续空间 （ 内存随机分割,
需要多少分配多少 ）,但各段之间可以不连续存放 。
4.2.2 管理段表：
它记录了段号,段的首 （ 地 ） 址和长度之间的关系 。
每一个程序设一个段表段号
0
1
2
空闲块管理：
记录了空闲区起始地址和长度 。
内存的分配算法：
首先适配；最佳适配；最坏适配
4.2.3 硬件支持一对寄存器段表始址寄存器：
用于保存正在运行进程的段表的始址 。
段表长度寄存器：
用于保存正在运行进程的段表的长度 （ 例如上图的段表长度为 3） 。
ClCb
+
段号 S 段内地址 d
比较比较
b + d
比较段 表
S>= Cl
快表物理地址段表始址寄存器 段表长度寄存器 逻辑地址
l b,,.
S l b
地址越界
d>=1
d>=1
地址映射及存储保护机制地址越界地址越界比较介于内存与寄存器之间的存储机制,
它又叫快表 。
用途：保存正在运行进程的段表的子集 （ 部分表项 ） 。
特点：按内容并行查找 。
相联（联想）存储器引入快表的作用：
为了提高地址映射速度。
快表项目：段号；段始址；段长度；
标识 （ 状态 ） 位；访问位,淘汰位 。
快表淘汰问题？
4.2.4 段的共享作业
4.2.5 段的保护作业优点：
便于动态申请内存管理和使用统一化便于共享便于动态链接缺点：产生碎片与可变分区存储管理方案区别
4.3 页式存储管理
4.3.1 基本思想 （ 工作原理 ）
用户程序划分把用户程序按逻辑页划分成大小相等的部分,称为页 。 从 0开始编制页号,
页内地址是相对于 0编址 。
逻辑地址用户程序的划分是由系统自动完成的,对用户是透明的 。 一般,一页的大小为 2的整数次幂,因此,地址的高位部分为页号,低位部分为页内地址 。
页号 页内地址
0111223
页号 P 页内位移量 W
编号 0~4096 相对地址 0~4096
内存空间：
按页的大小划分为大小相等的区域,
称为内存块 （ 又叫物理页面 ） 。
内存分配：
以页为单位进行分配,并按作业的页数多少来分配 。 逻辑上相邻的页,
物理上不一定相邻 。
..
.
0
1
2
3
4
5
6
0
1
2
3
4
5
6作业的地址空间页框
（物理块）页号页表 主存中页框
（物理块）
..
..
4.3.2 管理
1.页表：系统为每个进程都建立了一个页表,页表给出逻辑地址号和具体内存块号相应的关系
2.空块管理 ——总页表
3.内存的分配与回收计算一个作业所需要的总块数 。
查总页表,看看是否还有 N个空闲块 。
如果有相应空闲块,则页表长度为该为 N,可填入 PCB中 。 （ 申请页表区,
把页表始址填入 PCB） 。
分配 N个空闲块,将块号和页号填入页表 （ 页表号实际不用填 ） 。
修改总页表 。
4.3.3 硬件支持
1,一对寄存器：
a 页表始址寄存器
b 页表长度寄存器
2,相联寄存器 ——快表
1） 页号 2） 页在内存的块号 3） 标识位 4） 淘汰位
p’
页表地址越界
l
比较
P>=1
p p’
.,,
快表
b
+
页号 p 页内地址 d
P’ d
物理地址页表地址寄存器 页表长度寄存器 逻辑地址地址映射机制
4.3.4 页的共享作业
4.3.5 页的保护作业
4.3.6 优缺点优点,a 解决了碎片问题
b 便于管理缺点,a 不易实现共享
b 不便于动态连接
4.4 段页式存储管理
4.4.1 产生背景及基本思想背景：结合了二者优点克服了二者的缺点基本思想：
用户程序划分：按段式划分 （ 对用户来讲,按段的逻辑关系进行划分；
对系统讲,按页划分每一段 ）
逻辑地址：
内存划分：按页式存储管理方案内存分配：以页为单位进行分配
4.4.2 管理
1 段表：记录了每一段的页表始址和页表长度
2 页表：记录了逻辑页号与内存块号的对应关系 。 （ 每一段有一个,一个程序可能有多个页表 ）
3 空块管理：
4 分配：同页式管理
4.4.3 硬件支持段表始址寄存器段表长度寄存器相联存储器 （ 快表 ）
4.5 交换技术与覆盖技术在多道环境下扩充内存的方法,用以解决在较小的存储空间中运行较大程序时遇到的矛盾 。
覆盖技术主要用在早期的操作系统中交换技术被广泛用于小型分时系统中,
交换技术的发展导致了虚存技术的出现交换技术与覆盖技术共同点：
进程的程序和数据主要放在外存,当前需要执行的部分放在内存,内外存之间进行信息交换不同点：如何控制交换？
4.5.1 覆盖技术覆盖：一个作业的若干程序段,或几个作业的某些部分共享某一个存储空间 。
把程序划分为若干个功能上相对独立的程序段,按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域 。
程序段先保存在磁盘上,当有关程序段的前一部分执行结束,把后续程序段调入内存,覆盖前面的程序段
（ 内存,扩大,了 ） 。
一般要求作业各模块之间有明确的调用结构,程序员要向系统指明覆盖结构,然后由由操作系统完成自动覆盖 。
A
8K
E
4K
F
10K
C
10K
B
8K
D
12K
作业 X的调用结构作业 X的常驻区
A（ 8K）
覆盖区 0
（ 10K）
覆盖区 1
（ 12K）
BC
DEF
缺点：对用户不透明,增加了用户负担 。
例子：目前这一技术用于小型系统中的系统程序的内存管理上,MS-
DOS的启动过程中,多次使用覆盖技术；启动之后,用户程序区 TPA
的高端部分与 COMMAND.COM暂驻模块也是一种覆盖结构 。
4.5.2 交换技术当内存空间紧张时,系统将内存中某些进程暂时移到外存,把外存中某些进程换进内存,占据前者所占用的区域,这种技术是进程在内存与外存之间的动态调度 。 多用于分时系统中 。
交换技术实现中的几个问题：
1,选择原则即将哪个进程换出 /内存？
例子：分时系统,时间片轮转法或基于优先数的调度算法在选择换出进程时,要确定换出的进程是要长时间等待的需要特殊考虑的是：任何等待 I/O的进程中存在的问题解决：
从不换出处于等待 I/O状态的进程仅通过操作系统缓冲执行 I/O操作总之,有些 I/O进程因 DMA而不能换出内存或换出前需要操作系统的特殊帮助
2,交换时机的确定何时需发生交换？
例子：
只要不用就换出 （ 很少再用 ）
只在内存空间不够或有不够的危险时换出
3,交换时需要做哪些工作？
需要一个盘交换区：必须足够大以存放所有用户程序的所有内存映像的拷贝；必须对这些内存映像的直接存取 。
切换程序
4,换入回内存时位臵的确定换出后再换入的内存位臵一定要在换出前的原来位臵上吗？
受地址,绑定,技术的影响,即绝对地址产生时机的限制 。
5,交换所需时间导致：
对时间片的影响对程序长度的使用要求动态扩充时要及时记录的管理要求与覆盖技术相比,交换技术不要求用户给出程序段之间的逻辑覆盖结构 。
而且,交换发生在进程或作业之间,
而覆盖发生在同一进程或作业内 。
此外,覆盖只能覆盖那些与覆盖段无关的程序段 。
4.6 虚拟存储连续性 ； 离散性驻留性 ； 交换性一次性； 多次性以 CPU时间和外存空间换取昂贵内存空间,这是操作系统中的资源转换技术
4.6.1 概述
1,问题的提出：
a 程序大于内存
b 程序暂时不执行或运行完是否还要占用内存虚拟存储器的基本思想是：程序,数据,堆栈的大小可以超过内存的大小,
操作系统把程序当前使用的部分保留在内存,而把其它部分保存在磁盘上,
并在需要时在内存和磁盘之间动态交换 。
虚拟存储器支持多道程序设计技术
CPU
MMU
内存 磁盘控制器总线
X60K-64K
X56K-60K
X52K-56K
X48K-52K
744K-48K
X40K-44K
536K-40K
X32K-36K
X28K-32K
X24K-28K
320K-24K
416K-20K
012K-16K
68K-12K
14K-8K
20K-4K
X
X
3
4
0
6
1
2
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
虚地址空间物理地址空间
} 虚页页框
000 015
000 014
000 013
000 012
111 111
000 010
101 19
000 08
000 07
000 06
011 15
100 14
000 13
110 12
001 11
010 10
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
110
在 /不在内存页表虚地址
8196
物理地址
24580
2,程序局部性原理在一段时间内一个程序的执行往往呈现出高度的局部性,表现在时间与空间两方面时间局部性：
一条指令被执行了,则在不久的将来它可能再被执行空间局部性：
若某一存储单元被使用,则在一定时间内,与该存储单元相邻的单元可能被使用
3、虚拟存储技术虚存：把内存与外存有机的结合起来使用,从而得到一个容量很大的
,内存,,这就是虚存 。
实现思想：当进程运行时,先将一部分程序装入内存,另一部分暂时留在外存,当要执行的指令不在内存时,由系统自动完成将它们从外存调入内存工作 。
4.6.2 虚拟页式存储管理
1,基本工作原理在进程开始运行之前,不是装入全部页面,而是装入一个或零个页面,之后根据进程运行的需要,动态装入其它页面；当内存空间已满,而又需要装入新的页面时,则根据某种算法淘汰某个页面,以便装入新的页面
2、页表表项页号,驻留位,内存块号,外存地址,访问位,修改位驻留位 （ 中断位 ）,表示该页是在内存还是在外存访问位：根据访问位来决定淘汰哪页 （ 由不同的算法决定 ）
修改位：查看此页是否在内存中被修改过
3、缺页中断在地址映射过程中,在页表中发现所要访问的页不在内存,则产生缺页中断 。 操作系统接到此中断信号后,
就调出缺页中断处理程序,根据页表中给出的外存地址,将该页调入内存,使作业继续运行下去 。
如果内存中有空闲块,则分配一页,
将新调入页装入内存,并修改页表中相应页表项目的驻留位及相应的内存块号 。
若此时内存中没有空闲块,则要淘汰某页,若该页在内存期间被修改过,
则要将其写回外存 。
4、页面淘汰算法
先进先出页面淘汰算法 （ FIFO）
选择在内存中驻留时间最长的页并淘汰之 。
理想淘汰算法 —最佳页面算法 （ OPT）
淘汰以后不再需要的或最远的将来才会用到的页面 。
最近未使用页面淘汰算法 （ NRU）
选择在最近一段时间内未使用过的一页并淘汰之 。
实现：设臵两位访问位 （ R）,修改位 （ M）
启动一个进程时,R,M臵 0
R被定期清零发生缺页中断时,操作系统检查 R,M：
第 0类：无访问,无修改第 1类：无访问,有修改第 2类：有访问,无修改第 3类：有访问,有修改操作系统随机从编号最小的非空类中选择一页淘汰
最近最少使用页面淘汰算法 （ LRU）
选择最后一次访问时间距离当前时间最长的一页并淘汰之 。
即淘汰没有使用的时间最长的页 。
实现代价很高硬件方法
LRU的软件解决方案：
最不经常使用 （ NFU）
选择访问次数最少的页面淘汰之实现：软件计数器,一页一个,初值为 0。 每次时钟中断时,计数器加 R。
发生缺页中断时,选择计数器值最小的一页淘汰改进：计数器在加 R前先右移一位
R位加到计数器的最左端称为老化算法
第二次机会淘汰算法 (SCR)
按照先进先出算法选择某一页面,
检查其访问位,如果为 0,则淘汰该页,如果为 1,则给第二次机会,并将访问位臵 0。
时钟页面淘汰算法 （ Clock）
在实现上对第二次机会算法的改进环形链表 （ 类似钟表面 ）
表指针：指向最老的页面例子 1：计算缺页次数某程序在内存中分配三个页面,初始为空,页面走向为 4,3,2,1,4，
3,5,4,3,2,1,5。
FIFO 4 3 2 1 4 3 5 4 3 2 1 5
页 1 4 3 2 1 4 3 5 5 5 2 1 1
页 2 4 3 2 1 4 3 3 3 5 2 2
页 3 4 3 2 1 4 4 4 3 5 5
x x x x x x xx x?
共缺页中断 9次
LRU 4 3 2 1 4 3 5 4 3 2 1 5
页 1 4 3 2 1 4 3 5 4 3 2 1 5
页 2 4 3 2 1 4 3 5 4 3 2 1
页 3 4 3 2 1 4 3 5 4 3 2
x x x x x x xx x x
共缺页中断 10次
OPT 4 3 2 1 4 3 5 4 3 2 1 5
页 1 4 3 2 1 1 1 5 5 5 2 1 1
页 2 4 3 3 3 3 3 3 3 5 5 5
页 3 4 4 4 4 4 4 4 4 4 4
x x x xxx x?
共缺页中断 7次例子 2：计算缺页次数某程序在内存中分配 m页初始为空,
页面走向为 1,2,3,4,1,2,5，
1,2,3,4,5。 当 m=3,m=4时缺页中断分别为多少？ 用 FIFO算法 。
例子 2：计算缺页次数
m=3时,缺页中断 9次
m=4时,缺页中断 10次注,FIFO页面淘汰算法会产生异常现象,当分配给进程的物理页面数增加时,缺页次数反而增加 。
5、影响缺页次数的因素
(1) 分配给进程的物理页面数
(2) 页面本身的大小
(3) 程序的编制方法
(4) 页面淘汰算法例子 3：内存分配一页,初始时第一页在内存,页面大小为 128个整数 。
矩阵 A128X128按行存放 。
程序编制方法 1：
For j:=1 to 128
For i:=1 to 128
A[i,j]:=0;
程序编制方法 2：
For i:=1 to 128
For j:=1 to 128
A[i,j]:=0;
4.6.3 性能问题
1,颠簸 （ 抖动 ）
在虚存中,页面在内存与外存之间频繁调度,以至于调度页面所需时间比进程实际运行的时间还多,此时系统效率急剧下降,甚至导致系统崩溃 。 这种现象为颠簸 。
原因：
a 页面淘汰算法不合理
b 分配给进程的物理页面数太少
2、工作集模型基本思想：根据程序的局部性原理,
一般情况下,进程在一段时间内总是集中访问一些页面,这些页面称为活跃页面,如果分配给一个进程的物理页面数太少了,使该进程所需的活跃页面不能全部装入内存,
则进程在运行过程中将频繁发生中断 。
如果能为进程提供与活跃页面数相等的物理页面数,则可减少缺页中断次数 。
工作集：
对于给定的访问序列选取定长的区间,
称为工作集窗口,落在工作集窗口中的页面集合称为工作集 。
工作集：
内容取决于页的三个因素
a 访页序列特性
b 时刻 Ti
c 窗口长度 (△ )
例：
26157775162341234443434441327
| |t1 | |t2
ws(t1)={1,2,5,6,7}
ws(t2)={3,4}
4.6.4 虚拟段式存储管理
1,段表内容增加：特征位 （ 在 /不在内存,是否可共享 ）,存取权限位 （ 读,写,
执行 ）,标志位 （ 是否修改过,能否移动 ）,扩充位 （ 固定长 /可扩充 ）
2,越界中断处理进程在执行过程中,有时需要扩大分段,如数据段 。 由于要访问的地址超出原有的段长,所以发越界中断 。 操作系统处理中断时,首先判断该段的,扩充位,,如可扩充,
则增加段的长度；否则按出错处理 。
3,缺段中断处理检查内存中是否有足够的空闲空间
a 若有,则装入该段,修改有关数据结构,中断返回
b 若没有,检查内存中空闲区的总和是否满足要求,是则应采用紧缩技术,转 a；否则,淘汰一些段,转 a
4,段的动态链接大型程序：
若干程序段,若干数据段一些熟知的事实：
* 进程的某些程序段在进程运行期间可能根本不用
* 互斥执行的程序段没有必要同时驻留内存
* 有些程序段执行一次后不再用到静态链接：为了程序正确执行,必须由连接装配程序把它们连接成一个可运行的目标程序,并在程序运行前都装入内存 。
问题：花费时间,浪费空间
（ 1） 段的动态链接在程序开始运行时,只将主程序段装配好并调入内存,其它各段的装配是在主程序段的运行过程中逐步完成 。 每当需要调用一个新段时,再将这个新段装配好,并与主程序段链接 。
页式存储管理：难以完成动态链接,
其逻辑地址是一维的
（ 2） 链接间接字和链接中断机器指令：直接寻址,间接寻址
LOAD 100
LOAD 100
600
600
800
直接寻址间接寻址
100
100
数据间接字数据采用间接寻址时,间接地址指示的单元的内容称为间接字,在间接字中,
包含了直接地址,还包含了附加的状态位 。 格式为：
L 直接地址
L：链接标志位
L=0：该段已经建立了链接
L=1：该段尚未链接处理机在执行间接指令时,其硬件能自动对链接字中连接标志位进行判断 。
当 L=1时,硬件自动发链接中断,并停止执行该间接指令,转去执行链接中断处理程序 。 处理完后 （ L已被中断处理程序改为 0）,再重新执行该间接指令；若 L=0,则根据间接字中的直接地址去取数据 。
（ 3） 编译程序的准备工作
LOAD 1,[A]|<B> 编译前
LOAD* 1,3|100
...
...
100 6781 3...
678 7“[A]|<B>”...
编译后链接前
3段
LOAD* 1,3|100
100
链接后
678 7“[A]|<B>
1200 4
4段
120 <Y>,12345678
（ 4） 链接中断处理
* 根据链接间接字找出要访问段的符号名和段内地址
* 分配段号，检查该段是否在内存，
若不在，则从外存调入，并登记段表，修改内存分配表
* 修改间接字：修改连接标志位为 0，
修改直接地址
* 重新启动被中断的指令执行
（ 5） 其他问题纯段和杂段纯段：被链接段是可再入的，或称
“纯的”，即该段在执行过程中，
不允许修改其中的数据。
杂段：又称链接段，将程序所有可能变更的数据，包括链接间接字和某些临时变量、内部变量等，放在杂段中。
其他有关设计问题：
多级页表
局部与全局分配策略
页面尺寸实现时涉及的问题：
指令备份
锁定内存页
共享页
后备存储
分页程序
