优秀课件笔记之存储管理(上)

1、本文所以内容来自 著名高校课件和学生笔记（校园里面经常见到有人高价买笔记）
2、任课教师不会提供参考文献，所以只能对作者表示感谢，如果引用了您的作品，可以用回复方式补充参考文献。
3、我不对文章无关问题进行解答，文章内容也比较难，我也很难解答您遇到的问题，如果发现BUG可以用回复方式帮我修正。
4、本课 计算机操作系统
，适用于计算机操作系统课、考研

本课其他部分的导航条见页面底部

§
5.1
存储管理的功能
§
5.2
分区存储管理
§
5.3
覆盖与交换技术
§
5.4
页式管理
§

§5.1
存储管理的功能
• 存储器是计算机系统的重要资源之一。因为任何程序和数
据以及各种控制用的数据结构都必须占用一定的存储空
间，因此，存储管理直接影响系统性能。
• 存储器由内存（primary
srotage
）和外存（secondary
storage
）组成。内存由顺序编址的块组成，每块包含相应
的物理单元。CPU
要通过启动相应的输入输出设备后才能
使外存与内存交换信息。本章主要讨论内存管理问题。主
要包括：几种常用的内存管理方法、内存的分配和释放算
法、虚拟存储器的概念、控制主存和外存之间的数据流动
方法、地址变换技术和内存数据保护与共享技术等。下面
先介绍存储管理的功能。
3
5.1.1
虚拟存储器
• 虚拟存储器是存储管理的核心概念。现代计算机
系统的物理存储器都分为内存和外存，内存价格
昂贵，不可能用大容量的内存存储所有被访问的
或不被访问的程序与数据段。而外存尽管访问速
度较慢，但价格便宜，适合于存放大量信息。这
样，存储管理系统把进程中那些不经常被访问的
程序段和数据放入外存中，待需要访问它们时再
将它们调入内存。那么，对于那些一部分数据和
程序段在内存而另一部分则在外存的进程，怎样
安排它们的地址呢？通常由用户编写的源程序，
首先要由编译程序编译成CPU
可执行的目标代码。
然后，链接程序把一个进程的不同程序段链接起
来以完成所要求的功能。
4
• 显然，对于不同的程序段，应具有不同的地址。有
两种方法安排这些编译后的目标代码的地址。一种
方法是按照物理存储器中的位置赋予实际物理地址。
这种方法的好处是CPU
执行目标代码时的执行速
度高。但是，由于物理存储器的容量限制，能装入
内存并发执行的进程数将会大大减少，对于某些较
大的进程来说，当其所要求的总内存容量超过内存
容量时将会无法执行。另外，由于编译程序必须知
道内存的当前空闲部分及其地址，并且把一个进程
的不同程序段连续地存放起来，因此编译程序将非
常复杂。
5
• 另一种方法是编译链接程序把用户源程序编译后链
接到一个以0
地址为始地址的线性或多维虚拟地址
空间。这里，链接既可以是在程序执行以前由链接
程序完成的静态链接，也可以是在程序执行过程中
由于需要而进行的动态链接。而且，每一个进程都
拥有这样一个空间（这个空间是一维的还是多维的
由存储管理方式决定）。每个指令或数据单元都在
这个虚拟空间中拥有确定的地址，把这个地址称为
虚拟地址（virtual address
tservuaiadldr
）。显然，进程在该空
间的地址排列可以是非连续的，其实际物理地址由
虚拟地址到实际物理地址的地址变换机构变换得到。
由源程序到实际存放该程序指令或数据的内存物理
位置的变换如图5.1
所示。
6
图5.1
地址变换与物理存储器
• 将进程中的目标代码、数据等的虚拟地址组成的虚
拟空间称为虚拟存储器。虚拟存储器不考虑物理存
储器的大小和信息存放的实际位置，只规定每个进
程中互相关连的信息的相对位置。与实际物理存储
器只有一个（单机系统中），且被所有进程共享不
一样，每个进程都拥有自己的虚拟存储器，且虚拟
存储器的容量是由计算机的地址结构和寻址方式确
定的。例如，直接寻址时，如果CPU
的有效地址
长度为16
位，则其寻址范围为
0
到64K
。
7
• 图5.1
中的编译和链接主要是语言系统的设计问题。
不过，由虚拟存储器到物理存储器的变换是操作系
统所必须解决的问题。要实现这个变换，必须要有
相应的硬件支持，并使这些硬件能够完成统一管理
内存和外存之间数据和程序段自动交换的虚拟存储
器功能。即，由于每个进程都拥有自己的虚存，且
每个虚存的大小不受实际物理存储器的限制，因
此，系统不可能提供足够大的内存来存放所有进程
的内容。内存中只能存放那些经常被访问的程序和
数据段等。这就需要有相当大的外部存储器，以存
储那些不经常被访问或在某一段时间内不会被访问
的信息。待到进程执行过程中需要这些信息时，再
从外存中自动调入主存。
8
5.1.2
地址变换
• 内存地址的集合称为内存空间或物理地址空间。内
存中，每一个存储单元都与相应的称为内存地址的
编号相对应。显然，内存空间是一维线性空间。
• 怎样把几个虚存的一维线性空间或多维线性空间变
换到内存的唯一的一维物理线性空间呢？这涉及到
两个问题。一个是虚拟空间的划分问题。例如进程
的正文段和数据段应该放置在虚拟空间的什么地方。
虚拟空间的划分使得编译链接程序可以把不同的程
序模块（它们可能是用不同的高级语言编写的），
链接到一个统一的虚拟空间中去。虚拟空间的划分
与计算机系统结构有关。VAX-11
机的虚拟空间结
构如图5.2
。
9
图5.2
虚拟空间的划分
• 第二个问题是把虚拟空间中已链接和划分好的内容
装入内存，并将虚拟地址映射为内存地址的问题。
称之为地址重定位或地址映射。地址映射就是要建
立虚拟地址与内存地址的关系。实现地址重定位或
地址映射的方法有两种：静态地址重定位和动态地
址重定位。
10
1.
静态地址重定位
• 静态地址重定位（static address relocation
）是在
虚拟空间程序执行之前由装配程序完成地址映射工
作。假定分配程序已分配了一块首地址为BA
的内
存区给虚拟空间内的程序段，且每条指令或数据的
虚拟地址为VA
，那么，该指令或数据对应的内存
地址为MA
，从而完成程序中所有地址部分的修
改，以保证CPU
的正确执行。显然，对于虚拟空间
内的指令或数据来说，静态地址重定位只完成一个
首地址不同的连续地址变换。它要求所有待执行的
程序必须在执行之前完成它们之间的链接，否则将
无法得到正确的内存地址和内存空间。
11
• 静态重定位的优点是不需要硬件支持。但是，使用
静态重定位方法进行地址变换无法实现虚拟存储器。
这是因为，虚拟存储器呈现在用户面前的是一个在
物理上只受内存和外存总容量限制的存储系统，这
要求存储管理系统只把进程执行时频繁使用和立即
需要的指令与数据等存放在内存中，而把那些暂时
不需要的部分存放在外存中，待需要时自动调入，
以提高内存的利用率和并行执行的作业道数。显
然，这是与静态重定位方法矛盾的，静态重定位方
法将程序一旦装入内存之后就不能再移动，并且必
须在程序执行之前将有关部分全部装入。
• 静态重定位的另一个缺点是必须占用连续的内存空
间，这就难以做到程序和数据的共享。
12
2.
动态地址重定位
• 动态地址重定位（dynamic address relocation
）
是在程序执行过程中，在CPU
访问内存之前，将
要访问的程序或数据地址转换成内存地址。动态
重定位依靠硬件地址变换机构完成。
• 地址重定位机构需要一个(
或多个)
基地址寄存器
BR
和一个(
或多个)
程序虚拟地址寄存器VR
。指令
或数据的内存地址MA
与虚拟地址的关系为:
MA=(BR)+ (VR)
()+=这里，(BR)
与(VR)
分别表示寄存器BR
与VR
中的内容。
• 动态重定位过程可参看图5.3
。
13
图5.3
动态地址重定位
14
其具体过程是:
(1)
设置基地址寄存器BR
，虚拟地址寄存器VR
。
(2)
将程序段装入内存，且将其占用的内存区首地
址送BR
中。例如，在图5.3
中，(BR)=1000
。
(3)
在程序执行过程中，将所要访问的虚拟地址送
入VR
中，例如在图5.3
中执行LOAD A 500
语句
时
，将所要访问的虚拟地址500
放入VR
中。
(4)
地址变换机构把VR
和BR
的内容相加，得到实
际访问的物理地址。
15
动态重定位的主要优点有:
(1)
可以对内存进行非连续分配。显然，对于同一
进程的各分散程序段，只要把各程序段在内存中
的首地址统一存放在不同的BR
中，则可以由地址
变换机构变换得到正确的内存地址。
(2)
动态重定位提供了实现虚拟存储器的基础。因
为动态重定位不要求在作业执行前为所有程序分
配内存，也就是说，可以部分地、动态地分配内
存。从而，可以在动态重定位的基础上，在执行
期间采用请求方式为那些不在内存中的程序段分
配内存，以达到内存扩充的目的。
(3)
有利于程序段的共享。
16
5.1.3
内外存数据传输的控制
• 要实现内存扩充，在程序执行过程中，内存和外存
之间必须经常地交换数据。也就是说，把那些即将
执行的程序和数据段调入内存，而把那些处于等待
状态的程序和数据段调出内存。最基本的控制办法
有两种。一种是用户程序自己控制，另一种是操作
系统控制。
• 用户程序自己控制内外存之间的数据交换的例子是
覆盖。覆盖技术要求用户清楚地了解程序的结构，
并指定各程序段调入内存的先后次序。覆盖是一种
早期的主存扩充技术。使用覆盖技术，用户负担很
大，且程序段的最大长度仍受内存容量限制。因
此，覆盖技术不能实现虚拟存储器。
17
• 操作系统控制方式又可进一步分为两种。一种是交
换(swapping)
方式，另一种是请求调入(on demand)
方式和预调入(on
prefetch
ftcehpr
)
方式。
• 交换方式由操作系统把那些在内存中处于等待状态
的进程换出内存，而把那些等待事件已经发生、处
于就绪态的进程换入内存。
• 请求调入方式是在程序执行时，如果所要访问的程
序段或数据段不在内存中，则操作系统自动地从外
存将有关的程序段和数据段调入内存的一种操作系
统控制方式。而预调入则是由操作系统预测在不远
的将来会访问到的那些程序段和数据段部分，并在
它们被访问之前系统选择适当的时机将它们调入内
存的一种数据流控制方式。
18
• 由于交换方式一般不进行部分交换，即每次交
换都交换那些除去常驻内存部分后的整个进
程，而且，即使能完成部分交换，也不是按照
执行的需要而交换程序段，只是把受资源限制、
暂时不能执行的程序段换出内存。因此，虽然
交换方式也能完成内存扩充任务，但它仍未实
现那种所谓自动覆盖、内存和外存统一管理、
进程大小不受内存容量限制的虚拟存储器。只
有请求调入方式和预调入方式可以实现进程大
小不受内存容量限制的虚拟存储器。
19
5.1.4
内存的分配与回收
• 内存的分配与回收是内存管理的主要功能之一。无
论采用哪一种管理和控制方式，能否把外存中的数
据和程序调入内存，取决于能否在内存中为它们安
排合适的位置。因此，存储管理模块要为每一个并
发执行的进程分配内存空间。另外，当进程执行结
束之后，存储管理模块又要及时回收该进程所占用
的内存资源，以便给其他进程分配空间。
• 为了有效合理地利用内存，设计内存的分配和回收
方法时，必须考虑和确定以下几种策略和数据结构:
(1)
分配结构：登记内存使用情况，供分配程序使用
的表格与链表。例如内存空闲区表、空闲区队列等。
20
(2)
放置策略：确定调入内存的程序和数据在内存中
的位置。这是一种选择内存空闲区的策略。
(3)
交换策略：在需要将某个程序段和数据调入内存
时，如果内存中没有足够的空闲区，由交换策略来
确定把内存中的哪些程序段和数据段调出内存，以
便腾出足够的空间。
(4)
调入策略：外存中的程序段和数据段什么时间按
什么样的控制方式进入内存。调入策略与5.1.3
节中
所述内外存数据流动控制方式有关。
(5)
回收策略：回收策略包括二点，一是回收的时
机，二是对所回收的内存空闲区和已存在的内存空
闲区的调整。
21
5.1.5
内存信息的共享与保护
• 内存信息的共享与保护也是内存管理的重要功能之
一。
在多道程序设计环境下，内存中的许多用户
或系统的程序和数据段可供不同的用户进程共享。
这种资源共享将会提高内存的利用率。但是，反过
来说，除了被允许共享的部分之外，又要限制各进
程只在自己的存储区活动，各进程不能对别的进程
的程序和数据段产生干扰和破坏，因此须对内存中
的程序和数据段采取保护措施。
• 常用的内存信息保护方法有硬件法、软件法和软硬
件结合三种。
22
• 上下界保护法是一种常用的硬件保护法。上下界存
储保护技术要求为每个进程设置一对上下界寄存器。
上下界寄存器中装有被保护程序和数据段的起始地
址和终止地址。在程序执行过程中,
在对内存进行
访问操作时首先进行访址合法性检查,
即检查经过
重定位后的内存地址是否在上、下界寄存器所规定
的范围之内。若在规定的范围之内，则访问是合法
的；否则是非法的，并产生访址越界中断。上下界
保护法的保护原理如图5.4
。
23
图5.4
上、下界寄存器保护法
24
• 另外，保护键法也是一种常用的存储保护法。保护
键法为每一个被保护存储块分配一个单独的保护键。
在程序状态字中则设置相应的保护键开关字段，对
不同的进程赋予不同的开关代码和与被保护的存储
块中的保护键匹配。保护键可设置成对读写同时保
护的或只对读，写进行单项保护的。例如，图5.5
中的保护键0
，就是对2K
到4K
的存储区进行读写同
时保护的，而保护键2
则只对4K
到6K
的存储区进行
写保护。如果开关字与保护键匹配或存储块未受到
保护，则访问该存储块是允许的，否则将产生访问
出错中断。
25
图5.5
保护键保护法
26
• 另外一种常用的内存保护方式是：界限寄
存器与CPU
的用户态或核心态工作方式相
结合的保护方式。在这种保护模式下，用
户态进程只能访问那些在界限寄存器所规
定范围内的内存部分，而核心态进程则可
以访问整个内存地址空间。UNIX
系统就
是采用的这种内存保护方式。
27
§5.2
分区存储管理
• 分区管理是把内存划分成若干个大小不等的区域，
除操作系统占用一个区域之外，其余由多道环境下
的各并发进程共享。分区管理是满足多道程序设计
的一种最简单的存储管理方法。
• 下面结合分区原理来讨论分区存储管理时的虚存实
现、地址变换、内存的分配与释放以及内存信息的
共享与保护等问题。
5.2.1
分区管理基本原理
• 分区管理的基本原理是给每一个内存中的进程划分
一块适当大小的存储区,
以连续存储各进程的程序
和数据，使各进程得以并发执行。按分区的时机，
分区管理可以分为固定分区和动态分区两种方法。
28
1.
固定分区法
• 把内存区固定地划分为若干个大小不等的区域。划
分的原则由系统操作员或操作系统决定。分区一旦
划分结束，在整个执行过程中每个分区的长度和内
存的总分区个数将保持不变。
• 系统对内存的管理和控制通过数据结构——
分区说
明表进行，分区说明表说明各分区号、分区大小、
起始地址和是否是空闲区(
分区状态)
。内存的分配
释放、存储保护以及地址变换等都通过分区说明表
进行。图5.6
给出了固定分区时分区说明表和对应
内存状态的例子。
• 图中，操作系统占用低地址部分的20K
，其余空间
被划分为4
个分区，其中1,2,3
号分区已分配，4
号分
区未分配。
29
图5.6
固定分区法
30
2.
动态分区法
• 动态分区法在作业执行前并不建立分区，分区的
建立是在作业的处理过程中进行的，且其大小可
随作业或进程对内存的要求而改变。这就改变了
固定分区法中那种即使是小作业也要占据大分区
的浪费现象，从而提高了内存的利用率。
• 采用动态分区法，在系统初启时，除了操作系统
中常驻内存部分之外，只有一个空闲分区。随
后，分配程序将该区依次划分给调度选中的作业
或进程。图5.7
给出了FIFO
调度方式时的内存初
始分配情况。
31
图5.7
内存初始分配情况
32
• 随着进程的执行，会出现一系列的分配和释放。如
在某一时刻，进程C
执行结束并释放内存之后，管
理程序又要为另两个进程E
（设需内存50K
）和F
（设需内存16K
）分配内存。如果分配的空闲区比
所要求的大，则管理程序将该空闲区分成两个部
分，其中一部分成为已分配区而另一部分成为一个
新的小空闲区。图5.8
给出了采用最先适应算法
(first fit)
分配内存时进程E
和进程F
得到内存以及进
程B
和进程D
释放内存的内存分配变化过程。如图
5.8
所示，在管理程序回收内存时，如果被回收分
区有和它邻接的空闲分区存在，则要进行合并。
33
图5.8
内存分配变化过程
34
• 与固定分区法时相同，动态分区法也要使用分区说
明表等数据结构对内存进行管理。除了分区说明表
之外，动态分区法还把内存中的可用分区单独构成
可用分区表或可用分区自由链，以描述系统内的内
存资源。与此相对应,
请求内存资源的作业或进程
也构成一个内存资源请求表。图5.9
给出了可用表,
自由链和请求表的例子。
• 可用表的每个表目记录一个空闲区，主要参数包括
区号、长度和起始地址。采用表格结构，管理过程
比较简单，但表的大小难以确定，可用表要占用一
部分内存。
35
图5.9
可用表、自由链及请求表
36
• 自由链则是利用每个内存空闲区的头几个单元存放本空
闲区的大小及下个空闲区的起始地址，从而把所有的空
闲区链接起来。然后，系统再设置一自由链首指针让其
指向第一个空闲区，这样，管理程序可通过链首指针查
到所有的空闲区。采用自由链法管理空闲区，查找时要
比可用表困难，但由于自由链指针是利用的空闲区自身
的单元，所以不必占用额外的内存区。
• 请求表的每个表目描述请求内存资源的作业或进程号以
及所请求的内存大小。
• 无论是采用可用表方式还是自由链方式，可用表或自由
链中的各个项都要按照一定的规则排列以利查找和回收。
下面讨论分区法的分区分配与回收问题。
37
5.2.2
分区的分配与回收
1.
固定分区时的分配与回收
• 固定分区法时的内存分配与回收较为简单，当用
户程序要装入执行时，通过请求表提出内存分配
要求和所要求的内存空间大小。存储管理程序根
据请求表查询分区说明表，从中找出一个满足要
求的空闲分区，并将其分配给申请者。固定分区
时的分配算法如图5.10
。
• 固定分区的回收更加简单。当进程执行完毕，不
再需要内存资源时，管理程序将对应的分区状态
置为未使用即可。
图5.10 38
固定分区分配算法
39
2.
动态分区时的分配与回收
• 动态分区时的分配与回收主要解决三个问题:
(1)
对于请求表中的要求内存长度，从可用表或自由链中
寻找出合适的空闲区分配程序。
(2)
分配空闲区之后，更新可用表或自由链。
(3)
进程或作业释放内存资源时，和相邻的空闲区进行链接
合并，更新可用表或自由链。
• 动态分区时的分配方法
从可用表或自由链中寻找空闲区的常用方法有三种。
它们是最先适应法(first fit algorithm)
,
最佳适应法(best fit
algorithm)
和最坏适应法(worst fit
algoriathm
)
。这三种
方法要求可用表或自由链按不同的方式排列。
40
(1)
最先适应法
最先适应法要求可用表或自由链按起始
地址递增的次序排列。该算法的最大特点是
一旦找到大于或等于所要求内存长度的分
区，则结束探索。然后，该算法从所找到的
分区中划出所要求的内存长度分配给用户，
并把余下的部分进行合并(
如果有相邻空闲
区存在)
后留在可用表中，但要修改其相应
的表项。
最先适应算法如图5.11
所示。
图5.11 41
最先适应算法
42
(2)
最佳适应算法
最佳适应算法要求从小到大的次序组成空
闲区可用表或自由链。当用户作业或进程申请
一个空闲区时，存储管理程序从表头开始查
找，当找到第一个满足要求的空闲区时，停止
查找。如果该空闲区大于请求表中的请求长
度，则与最先适应法时相同，将减去请求长度
后的剩余空闲区部分留在可用表中。
43
(3)
最坏适应算法
最坏适应算法要求空闲区按其大小递减的顺
序组成空闲区可用表或自由链。当用户作业或进
程申请一个空闲区时，先检查空闲区可用表或自
由链的第一个空闲可用区的大小是否大于或等于
所要求的内存长度，若可用表或自由链的第一个
项长度小于所要求的，则分配失败，否则从空闲
区可用表或自由链中分配相应的存储空间给用
户，然后修改和调整空闲区可用表或自由链。
44
3.
动态分区时的回收与拼接
• 当用户作业或进程执行结束时，存储管理程序要收
回已使用完毕的空闲区，并将其插入空闲区可用表
或自由链。这里，在将回收的空闲区插入可用表或
自由链时,
和分配空闲区时一样，也要碰到剩余空
闲区拼接问题。
解决这个问题的办法之一就是在
空闲区回收时或在内存分配时进行空闲区拼接，以
把不连续的零散空闲区集中起来。
• 在将一个新可用区插入可用表或队列时,
该空闲区
和上下相邻区的关系是下述4
种关系之一: a)
该空闲
区的上下两相邻分区都是空闲区；b)
该空闲区的上
相邻区是空闲区；c)
该空闲区的下相邻区是空闲
区；d)
两相邻区都不是空闲区。如图5.12
所示。
45
图5.12
空闲区的合并
46
• 对上述
4
种情况，如果释放区与上下两空闲区相邻，则将三
个空闲区
合并为一个空闲区
。
新空闲区的起始地址为上空
闲区的起始地址，大小为三个空闲区之和
。
空闲区合并
后，取消可用表或自由链中下空闲区的表目项或链指针，
修改上空闲区的对应项。
• 如果释放区只与上空闲区相邻，则将释放区与上空闲区
合
并为一个空闲区
，其起始地址为上空闲区的起始地址，大
小为上空闲区与释放区之和。合并后，修改上空闲区对应
的可用表的表目项或自由链指针。
• 如果释放区与下空闲区相邻，则
将释放区与下空闲区合
并，并将释放区的起始地址作为合并区的起始地址
。合并
区的长度为释放区与下空闲区之和。合并后修改可用表或
自由链中相应的表目项或链指针。
• 如果释放区不与任何空闲区相邻，则释放区作为一个新可
用区插入可用表或自由链。
47
4.
几种分配算法的比较
• 由于回收后的空闲区要插入可用表或自由链中，而
且可用表或自由链是按照一定顺序排列的，所以，
除了搜索查找速度与所找到的空闲区是否最佳，释
放空闲区的速度也对系统开销产生影响。下面从查
找速度、释放速度及空闲区的利用等三个方面对上
述三种算法进行比较。
• 首先，从搜索速度上看，最先适应算法具有最佳性
能。尽管最佳适应算法或最坏适应算法看上去能很
快地找到一个最适合的或最大的空闲区。再者，从
回收过程来看，最先适应算法也是最佳的。因为使
用最先适应算法回收某一空闲区时，无论被释放区
是否与空闲区相邻，都不用改变该区在可用表或自
由链中的位置，只需修改其大小或起始地址。
48
• 最先适应算法的另一个优点就是尽可能地利用了低
地址空间，从而保证高地址有较大的空闲区来放置
要求内存较多的进程或作业。
• 最佳适应法找到的空闲区是最佳的。不过,
在某些
情况下并不一定提高内存的利用率。
• 最坏适应算法正是基于不留下碎片空闲区这一出发
点的。它选择最大的空闲区来满足用户要求，以期
分配后的剩余部分仍能进行再分配。
• 总之，上述三种算法各有特长，针对不同的请求队
列，效率和功能是不一样的。
49
5.2.3
有关分区管理其他问题的讨论
1.
关于虚存的实现
利用分区式管理，也同样存在有每个用户可以
自由编程的虚拟空间。
但是,
分区式管理方式无法实
现那种用户进程所需内存容量只受内存和外存容量之
和限制的虚拟存储器。如果不采用内存扩充技术，每
个用户进程所需内存容量是受到分区大小限制的。
2.
关于内存扩充
由于分区式管理时各用户进程或作业所要求的内
存容量受到分区大小的限制,
如果不采用内存扩充技
术，将会极大地限制分区式管理技术的使用。在分区
式管理中，可以使用覆盖或交换技术来扩充内存。
50
3.
关于地址变换和内存保护
• 静态地址重定位和动态地址重定位技术，都可用来完成分区式内
存管理的地址变换。
显然，
动态分区时分区大小不固定，而空闲
区的拼接会移动内存中的程序和数据，因此，使用静态地址重定
位的方法来完成动态分区时的地址变换是不妥当的。
• 在进行动态地址重定位时，
每个分区需要一对硬件寄存器
的支
持，即
基址寄存器
和
限长寄存器
，分别用来存放作业或进程在内
存分区的起始地址和长度。这一对硬件寄存器除了完成动态地址
重定位的功能之外，还具有保护内存中数据和程序的功能
。这由
硬件检查
CPU
执行指令所要访问的虚拟地址
完成。即设
CPU
指令
所要访问的虚拟地址为
D
，若
D>VR (VR
是限长寄存器中的限长
值
)
，则说明地址越界
,
所要访问的内存地址超出了该作业或进程
所占用的内存空间。这时将产生
保护中断
。系统转去
进行出错处
理
。若
D<=VR
，则该地址是合法的，由硬件完成对该虚拟地址的
动态重定位。
• 保护键法
也可用来对内存各分区提供保护。
51
4.
分区存储管理的主要优缺点
u 分区存储管理的主要优点如下:
(1)
实现了多个作业或进程对内存的共享，有助于多道程序设
计，从而提高了系统的资源利用率。
该方法要求的硬件支持少，管理算法简单，因而实现容易。
u 主要缺点有:
(1)
内存利用率仍然不高。和单一连续分配算法一
样，存储器
中可能含有从未用过的信息。而且，还存在着严重的碎小空
闲区(
碎片)
不能利用的问题。
(2)
作业或进程的大小受分区大小控制，除非配合采用覆盖和交
换技术。
(3)
难以实现各分区间的信息共享。
52
§5.3
覆盖与交换技术
覆盖与交换技术是在多道环境下用来
扩充内存的两种方法。覆盖技术主要用在
早期的操作系统中，而交换技术则在现代
操作系统中仍具有较强的生命力。
53
5.3.1
覆盖技术
• 覆盖技术是基于这样一种思想提出来的，即一个程
序并不需要一开始就把它的全部指令和数据都装入
内存后再执行。在单CPU
系统中，每一时刻事实上
只能执行一条指令。因此，不妨把程序划分为若干
个功能上相对独立的程序段，按照程序的逻辑结构
让那些不会同时执行的程序段共享同一块内存区。
通常，这些程序段都被保存在外存中，当有关程序
段的先头程序段已经执行结束后，再把后续程序段
调入内存覆盖前面的程序段。这使得用户看来，好
像内存扩大了，从而达到了内存扩充的目的。
54
• 但是，覆盖技术要求程序员提供一个清楚的覆盖结
构。即程序员必须完成把一个程序划分成不同的程
序段，并规定好它们的执行和覆盖顺序的工作。 操
作系统根据程序员提供的覆盖结构来完成程序段之
间的覆盖。一般来说，一个程序究竟可以划分为多
少段，以及让其中的哪些程序共享哪一内存区只有
程序员清楚。这要求程序员既要清楚地了解程序所
属进程的虚拟空间及各程序段所在虚拟空间的位
置，又要求程序员懂得系统和内存的内部结构与地
址划分，因此，程序员负担较重。所以,
覆盖技术
大多用在对操作系统的虚空间和内部结构很熟悉的
程序员才会使用。
55
• 例如，设某进程的程序正文段由A
，B
，C
，D
，E
和F
等6
个程序段组成。它们之间的调用关系如图
5.13(a)
所示，程序段A
调用程序段B
和C
，程序段B
又调用程序段F,
程序段C
调用程序段D
和E
。
• 由图5.13(a)
可以看出，程序段B
不会调用C
，程序
段C
也不会调用B
。因此，程序段B
和C
无需同时驻
留在内存，它们可以共享同一内存区。同理，程序
段D
、E
、F
也可共享同一内存区。其覆盖结构如图
5.13(b)
所示。
56
图5.13
覆盖示例
57
• 在图5.13(b)
中,
整个程序正文段被分为两个部分.
一
个是常驻内存部分，该部分与所有的被调用程序段
有关，因而不能被覆盖。这一部分称为根程序。图
5.13(b)
中，程序段A
是根程序。另一部分是覆盖部
分，图中被分为两个覆盖区。其中，一个覆盖区由
程序段B
，C
共享。其大小为B
，C
中所要求容量大
者。另一个覆盖区为程序段F
，D
，E
共享。两个覆
盖区的大小分别为50 K
与40 K
。这样，虽然该进程
正文段所要求的内存空间是
A(20K)+B(50K)+F(30K)+C(30K)+D(20K)+E(40K)=190K
但由于采用了覆盖技术，只需110 K
的内存空
间即可开始执行。
58
5.3.2
交换技术
• 多道程序环境或分时系统中，同时执行好几个作业或
进程。如果让这些等待中的进程继续驻留内存，将会
造成存储空间的浪费。因此，应该把处于等待状态的
进程换出内存。
• 实现上述目标比较常用的方法之一就是交换。交换是
指先将内存某部分的程序或数据写入外存交换区，再
从外存交换区中调入指定的程序或数据到内存中来，
并让其执行的一种内存扩充技术。与覆盖技术相比，
交换不要求程序员给出程序段之间的覆盖结构。而
且，交换主要是在进程或作业之间进行，而覆盖则主
要在同一个作业或进程内进行。另外，覆盖只能覆盖
那些与覆盖程序段无关的程序段。
59
• 交换进程由换出和换入两个过程组成。其中换出
(swap out)
过程把内存中的数据和程序换到外存交
换区，而换入(swap in)
过程把外存交换区中的数据
和程序换到内存分区中。
• 换出过程和换入过程都要完成与外存设备管理进程
通信的任务。由交换进程发送给设备进程的消息m
中应包含分区的分区号i
、该分区的基址basei
iebas
、长
度sizei
和方向及外存交换区中分区起始地址。交换
进程和设备管理进程通过设备缓冲队列进行通信。
换出过程SWAPOUT
可描述如下:
60
SWAPOUT(i):
begin local m
m.base
embas
←
basei
iebas
;
m.ceiling
←basei
iebas
+
sizei
;
m.direction
← "out";
m.destination
← base of free area on swap area;
backupstorebasei
iteobkrauscps
← m.destination;
send( (m
senm(，i)
，device queue);
end
• 在SWAPOUT(i)
中，除了前5
行描述所需要的控制信
息之外，backupstorbasei
iteobkrauscps
是用来记录被换出数据和
程序的起始地址以便换入时使用的。而send
指令则
驱动设备做相应的数据读写操作。
61
• 与SWAPOUT
过程相同，可以写出SWAPIN
ISPNWA
过程。
SWAPIN(i):
begin local m
m.base
←
basei
iebas
;
m.ceiling
←
basei
iebas
+
sizei
;
m.direction
← "in";
m.source
←
backupstorebasei
iteobkrauscps
;
send( (m,i)
，device queue);
end
• 交换技术大多用在小型机或微机系统中。这样的系
统大部分采用固定的或动态分区方式管理内存。
62
§5.4
页
式
管
理
5.4.1
页式管理的基本原理
• 分区式管理方式尽管实现方式较为简单，但存在着
严重的碎片问题使得内存的利用率不高。再者，分
区式管理时，由于各作业或进程对应于不同的分区
以及在分区内各作业或进程连续存放，进程的大小
仍受分区大小或内存可用空间的限制。而且，分区
式管理也不利于程序段和数据的共享。页式管理正
是为了减少碎片以及为了只在内存存放那些反复执
行或即将执行的程序段与数据部分，而把那些不经
常执行的程序段和数据存放于外存待执行时调入，
以提高内存利用率而提出来的。
• 页式管理的基本原理如下：
63
• 首先，各进程的虚拟空间被划分成若干个长度相等
的页(page)
。页长的划分和内存外存之间数据传输
速度以及内存大小等有关。一般每个页长大约为1-
4K
,
经过页划分之后，进程的虚地址变为页号p
与页
内地址w
所组成。例如，一个页长为1K,
,1K
拥有1024
页的虚拟空间地址结构如图5.14
。
19
10 9
0
图5.14
页的划分
页内地址W
页号P
64
• 除了把进程的虚拟空间划分为大小相等的页之外，
页式管理还把内存空间也按页的大小划分为片或页
面(page frame)
。这些页面为系统中的任一进程所
共享(
除去操作系统区外)
。从而，分页管理时，用
户进程在内存空间内除了在每个页面内地址连续之
外，每个页面之间不再连续。第一是实现了内存中
碎片的减少，因为任一碎片都会小于一个页面。第
二是实现了由连续存储到非连续存储这个飞跃，为
在内存中局部地、动态地存储那些反复执行或即将
执行的程序和数据段打下了基础。
• 页式管理把页式虚地址与内存页面物理地址建立一
一对应页表，并用相应的硬件地址变换机构，来解
决离散地址变换问题。页表方式实质上是动态重定
位技术的一种延伸。
65
• 再者,
页式管理采用请求调页或预调页技术实现了
内外存存储器的统一管理。即内存内只存放那些经
常被执行或即将被执行的页，而那些不常被执行以
及在近期内不可能被执行的页，则存放于外存中待
需要时再调入。请求调页或预调页技术是基于工作
区的局部性原理的，有关局部性原理将在本节的后
面部分介绍。
• 由于使用了请求调页或预调页技术，页式管理时内
存页面的分配与回收已和页面淘汰技术及缺页处理
技术结合起来。不过，页面的换入换出仍是必要
的，这只要把上节所述的交换进程稍加修改就能用
于页面的交换。
• 分页管理的重点在于页划分之后的地址变换以及页
面的调入调出技术。
66
5.4.2
静态页面管理
静态页面管理方法在作业或进程开始执行之前，把该
作业或进程的程序段和数据全部装入内存的各个页面中，
并通过页表(page mapping table)
和硬件地址变换机构实现
虚拟地址到内存物理地址的地址映射。
1.
内存页面分配与回收
静态分页管理的第一步是为要求内存的作业或
进程分配足够的页面。系统依靠存储页面表、请求
表以及页表来完成内存的分配工作。首先来介绍这
三个表。
67
(1)
页表
• 最简单的页表由页号与页面号组成。如图5.15
所示。
• 页表在内存中占有一块固定的存储区。
页表的大
小由进程或作业的长度决定。例如，对于一个每页
长1 K
，大小为20 K
的进程来说，如果一个内存单
元存放一个页表项，则只要分配给该页表20
个存储
单元即可。显然，页式管理时每个进程至少拥有一
个页表。
图5.15
基本页表示例
页号页面号
68
(2)
请求表
• 请求表用来确定作业或进程的虚拟空间的各页在内
存中的实际对应位置。为了完成这个任务，系统必
须知道每个作业或进程的页表起始地址和长度，以
进行内存分配和地址变换。另外，请求表中还应包
括每个作业或进程所要求的页面数。
• 请求表整个系统一张，如图5.16
所示。
图5.16
请求表示例
69
存储页面表
存储页面表也是整个系统一张，存储页面表
指出内存各页面是否已被分配出去,
以及未分配页
面的总数。存储页面表也有两种构成方法，一种
是在内存中划分
一块固定区域，每个单元的每个
比特代表一个页面。如果该页面已被分配，则对
应比特位置1
，否则置0
。这种方法称为位示图法。
如图5.17
所示。
70
图5.17
位示图
71
• 位示图要占据一部分内存容量，例如，一个划分为
1 024
个页面的内存，如果内存单元长20
比特，则
位示图要占据1 024/20=52
个内存单元。
• 存储页面表的另一种构成办法是采用空闲页面链的
方法。在空闲页面链中，队首页面的第一个单元和
第二个单元分别放入空闲页面总数与指向下一个空
闲页面的指针。其他页面的第一个单元中则分别放
入指向下一个页面的指针。空闲页面链的方法由于
使用了空闲页面本身的单元存放指针，因此不占据
额外的内存空间。
72
2.
分配算法
• 利用上述
三个表格和数据结构
，给出一个页面分配算法。
• 首先，请求表给出进程或作业要求的页面数。然
后，由存储页面表检查是否有足够的空闲页面，如
果没有，则本次无法分配。如果有则首先分配设置
页表，并填写请求表中的相应表项后，按一定的查
找算法、搜索出所要求的空闲页面，并将对应的页
面号填入页表中。图5.18
给出了上述页面分配算法
的流程图。
• 静态页式管理的页面回收方法较为简单，当进程执
行完毕时，拆除对应的页表，并把页表中的各页面
插入存储页面表即可。
图5.18 73
页面分配算法流图
74
3.
地址变换
• 静态页式管理的另一个关键问题是地址变换。即怎
样由页号和页内相对地址变换到内存物理地址的问
题。另外，由于静态重定位可以使CPU
直接访问物
理地址，而分区式管理中的动态重定位也只需把基
址寄存器中的分区起始地址与待访问指令的虚地址
相加即可得到所要访问的物理地址。这两种重定位
法都不需要访问内存就可得到待执行指令所要访问
的物理地址。页式管理时，地址变换的速度也是设
计地址变换机构时必须考虑的问题之一。
• 由地址分配方式知道，在一个作业或进程的页表
中，连续的页号对应于不连续的页面号。例如，设
一个3
页长的进程具有页号0
，1
，2
，但其对应的页
面号则为2
，3
，8
。如图5.19
所示。
75
图5.19
页号与页面号
• 设每个页面长度为1K
，指令LOAD 1
，2500
的虚地
址为100
，怎样通过图5.19
所示页表来找到该指令
所对应的物理地址呢?
下面使用该例子说明地址变
换过程。
• 首先，需要有一个装置页表始址和页表长度用的控
制寄存器。系统把所调度执行的进程页表始址和长
度从请求表中取出置入控制寄存器中。
8
2
3
1
2
0
页号页面号
76
• 然后，由控制寄存器的页表始址，可以找到页表所
在位置。并由虚地址100
可知，指令LOAD 1
，2500
在第0
页的第100
单元之中。由于第0
页与第2
个页面
相对应，因此，该指令在内存中的地址为
2048+100=2148
。
• 当CPU
执行到第2148
单元的指令时，CPU
要从有效
地址2500
中取数据放入1
号寄存器中。为了找出2500
对应的实际物理地址，地址变换机构首先将2500
转
换为页号与页内相对地址组成的地址形式。即p=2
2p=
，
w=452
。
• 由页表，可知第2
页所对应的页面号等于8
。最后，
将页面号8
与页内相对地址w=452
相连，得到待访问
的物理内存地址8644
。其变换过程由图5.20
所示。
77
图5.20
地址变换
78
• 上述地址变换过程全部由硬件地址变换机构自动完成。
• 另外，由于页表是驻留在内存的某个固定区域中，
而取数据或指令又必须经过页表变换才能得到实际
物理地址。因此，取一个数据或指令至少要访问内
存两次以上。一次访问页表以确定所取数据或指令
的物理地址，另一次是根据地址取数据或指令。这
比通常执行指令的速度慢了一倍。提高查找速度一
个最直观的办法就是把页表放在寄存器中而不是内
存中，但由于寄存器价格太贵，这样做是不可取的。
另一种办法是在地址变换机构中加入一个高速联想
存储器，构成一张快表。在快表中，存入那些当前
执行进程中最常用的页号与所对应的页面号，从而
以提高查找速度。
79
• 静态页式管理解决了分区管理时的碎片问题。但
是，由于静态页式管理要求进程或作业在执行前
全部装入内存，如果可用页面数小于用户要求
时，该作业或进程只好等待。而且，作业或进程
的大小仍受内存可用页面数的限制。这些问题将
在动态(
请求)
页式管理中解决。
80
5.4.3
动态页式管理
• 动态页式管理是在静态页式管理的基础上发展起来
的。它分为请求页式管理和预调入页式管理。
• 请求页式管理和预调入页式管理在作业或进程开始
执行之前，都不把作业或进程的程序段和数据段一
次性地全部装入内存，而只装入被认为是经常反复
执行和调用的工作区部分。其他部分则在执行过程
中动态装入。请求页式管理与预调入页式管理的主
要区别在它们的调入方式上。请求页式管理的调入
方式是，当需要执行某条指令而又发现它不在内存
时或当执行某条指令需要访问其他的数据或指令
时，这些指令和数据不在内存中，从而发生缺页中
断，系统将外存中相应的页面调入内存。
81
• 预调入方式是，系统对那些在外存中的页进行调入
顺序计算，估计出这些页中指令和数据的执行和被
访问的顺序，并按此顺序将它们顺次调入和调出内
存。除了在调入方式上请求页式管理和预调入管理
有些区别之外，其他方面这两种方式基本相同。因
此，下面主要介绍请求页式管理。
• 请求页式管理的地址变换过程与静态页式管理时的
相同，也是通过页表查出相应的页面号之后，由页
面号与页内相对地址相加而得到实际物理地址。
• 但是，由于请求页式管理只让进程或作业的部分程
序和数据驻留在内存中，因此，在执行过程中，不
可避免地会出现某些虚页不在内存中的问题。怎样
发现这些不在内存中虚页以及怎样处理这种情况，
是请求页式管理必须解决的两个基本问题。
82
• 第一个问题可以用扩充页表的方法解决。即与每个
虚页号相对应，除了页面号之外，再增设该页是否
在内存的中断位以及该页在外存中的副本起始地址。
扩充后的页表如图5.21
。
图5.21
加入中断处理后的页表
3
2
1
0
页号页面号中断位外存始址
83
• 关于虚页不在内存时的处理，涉及到两个问题。第
一，采用何种方式把所缺的页调入内存。第二，如
果内存中没有空闲页面时，把调进来的页放在什么
地方。也就是说，采用什么样的策略来淘汰已占据
内存的页。还有，如果在内存中的某一页被淘汰，
且该页曾因程序的执行而被修改，则显然该页是应
该重新写到外存上加以保存的。而那些未被访问修
改的页，因为外存已保留有相同的副本，写回外存
是没有必要的。因此，在页表中还应增加一项以记
录该页是否曾被改变。增加改变位后的页表项如图
5.22
所示。
84
图5.22
加入改变位后的页表
改变位
3
2
1
0
页号页面号中断位外存始址
85
• 有关缺页的调入和存放，在内存中没有空闲页面
时，实际上是一个内存页面置换算法的问题。选择
什么样的置换算法，将直接影响到内存利用率和系
统效率。事实上，如果置换算法选择不当，有可能
产生刚被调出内存的页又要马上被调回内存，调回
内存不久又马上被调出内存，如此反复的局面。这
使得整个系统的页面调度非常频繁，以致大部分时
间都花费在主存和辅存之间的来回调入调出上。这
种现象被称为抖动(thrashing)
现象。
• 有关抖动现象的讨论，将在下节中介绍。
• 动态页式管理的流程图如图5.23
所示。
86
图5.23
动态页式管理流图
87
• 在图5.23
中，有关地址变换部分是由硬件自动完成
的。当硬件变换机构发现所要求的页不在内存时，
产生缺页中断信号，由中断处理程序做出相应的处
理。中断处理程序是由软件实现的。除了在没有空
闲页面时要按照置换算法选择出被淘汰页面之外，
还要从外存读入所需要的虚页。这个过程要启动相
应的外存和涉及到文件系统。因此，请求页式管理
是一个十分复杂的处理过程，内存利用率的提高是
以牺牲系统开销的代价换来的。
• 下面介绍几种常用的置换算法。
88
5.4.4
请求页式管理中的置换算法
置换算法在内存中没有空闲页面时被调用。它
的目的是选出一个被淘汰的页面。如果内存中有足
够的空闲页面存放所调入的页，则不必使用置换算
法。把内存和外存统一管理的真正目的是把那些被
访问概率非常高的页存放在内存中。因此，置换算
法应该置换那些被访问概率最低的页，将它们移出
内存。比较常用的置换算法有以下几种:
(1)
随机淘汰算法。在系统设计人员认为无法确定哪
些页被访问的概率较低时，随机地选择某个用户的
页面并将其换出将是一种明智的作法。
(2)
轮转法和先进先出算法。轮转法循回换出内存可
用区内一个可以被换出的页，无论该页是刚被换进
或已换进内存很长时间
89
• FIFO
算法认为先调入内存的页不再被访问的可能性要比其
他页大，因而选择最先调入内存的页换出。
实现
FIFO
算法
需要把各个已分配页面按分配时间顺序链接起来，组成
FIFO
队列
，并设置一
置换指针
指向
FIFO
队列的队首页面。
这样，当要进行置换时，只需把置换指针所指的
FIFO
队列
前头的页顺次换出，而把换入的页链接在
FIFO
队尾即可。
• 由实验和测试发现
FIFO
算法和
RR
算法的内存利用
率不高。这是因为，这两种算法都是基于
CPU
按线
性顺序访问地址空间
的这个假设上。事实上，
许多
时候，
CPU
不是按线性顺序访问地址空间的
，例如
执行循环语句时。因此，那些在内存中停留时间最
长的页往往也是经常被访问的页。尽管这些页变
“
老
”
了。但它们被访问的概率仍然很高。
90
• 先进先出算法的另一个缺点是它有一种陷阱现象。
一般来说，对于任一作业或进程，如果给它分配的
内存页面数越接近于它所要求的页面数，则发生缺
页的次数会越少。在极限情况下，这个推论是成立
的。因为如果给一个进程分配了它所要求的全部页
面，则不会发生缺页现象。但是，使用FIFO
算法
时，在未给进程或作业分配足它所要求的页面数
时，有时会出现分配的页面数增多，缺页次数反而
增加的奇怪现象。这种现象称为Belady
现象。如图
5.24
所示。
91
图5.24
FIFO
算法的Belady
现象
92
• 下面的例子可以用来说明FIFO
算法的正常换页情
况和Belady
现象。例:
设进程P
共有8
页，且已在内
存中分配有3
个页面，程序访问内存的顺序(
访问串)
为7
，0
，1
，2
，0
，3
，0
，4
，2
，3
，0
，3
，2
，1
，
2
，0
，1
。这里，这些自然数代表进程P
所建的程序
和数据的页号。内存中有关进程P
所建的程序和数
据的各页面变化情况如图5.25
所示。
图5.25
Belady
现象示例(1)
2
2
2
3
3
3
3
3
0
0
0
1
1
1
1
i
i
i
i
2
2
2
2
2
3
3
3
0
0
0
0
√ √ √ √ √ √ √ √ √ √ √ √
0
0
0
0
0
0
0
4
4
4
2
2
2
2
7
7
7
1
0
2
1
2
3
0
3
2
4
0
3
0
2
1
0
7
93
• 由图5.25
可以看出，进程在一个执行过程中，实际
上发生了12
次缺页。如果设缺页率为缺页次数与访
问串的访问次数之比，则该例中的缺页率为
12/17=70.5%
。
• 如果给进程P
分配4
个页面，则在其执行过程中内存
页面的变化情况如图5.26
所示。
• 进程P
在拥有4
个内存页面时，共发生9
次缺页，其
缺页率为9/17=52.9%
。
• 以上是使用FIFO
算法正常换页时的例子。下面我
们来看看另外一种访问串时的情况。设进程P
可分
为5
页，访问串为1
，2
，3
，4
，1
，2
，5
，1
，2
，
3
，4
，5
。当进程P
分得3
个页面时，执行过程中内
存页面变化如图5.27
所示。
94
图5.26 Belady
现象示例(2)
图5.27
Belady
现象示例(3)
1
1
1
1
2
2
2
2
2
2
2
2
2
2
√ √ √ √ √ √ √ √ √
4
4
4
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
2
2
2
3
3
3
3
3
3
3
3
3
7
7
7
7
7
1
0
2
1
2
3
0
3
2
4
0
3
0
2
1
0
7
4
4
2
2
2
2
2
3
3
3
3
3
3
1
1
1
1
1
2
2
2
√ √ √ √ √ √ √ √ √
5
5
5
5
5
5
4
4
4
1
1
1
5
4
3
2
1
5
2
1
4
3
2
1
95
• 由图5.27
可知，进程P
在执行过程中共缺页9
次，其
缺页率为9/12=75%
。
• 但是，如果为进程P
分配4
个内存页面，是否缺页率
会变小呢?
进程P
分得4
个页面时，执行过程中内存
页面的变化情况如图5.28
。
图5.28 Belady
现象示例(4)
3
3
3
4
4
4
4
4
4
√ √ √ √ √ √ √ √ √ √
5
1
1
1
1
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
4
4
5
5
5
5
1
1
1
1
1
1
5
4
3
2
1
5
2
1
4
3
2
1
96
• 由图5.28
可知，当进程P
分得4
个页面时，在执行过
程中的缺页次数为10
次。即缺页率=10/12=
83.3
%
。
• 先进先出算法产生Belady
现象的原因在于它根本没
有考虑程序执行的动态特征。
(3)
最近最久未使用页面置换算法(least recently used)
该算法的基本思想是:
当需要淘汰某一页时，
选择离当前时间最近的一段时间内最久没有使用过
的页先淘汰。该算法的主要出发点是，如果某页被
访问了，则它可能马上还要被访问。或者反过来
说，如果某页很长时间未被访问，则它在最近一段
时间也不会被访问。
97
• 要完全实现
LRU
算法是十分困难的
。因为要找出最近最久
未被使用的页面的话，就必须对每一个页面都设置有关的
访问记录项，而且每一次访问都必须更新这些记录。这显
然要花费巨大的系统开销。因此，在实际系统中往往使用
LRU
的近似算法。
• 比较常用的
近似算法
有
:
a)
最不经常使用页面淘汰算法
LFU(least frequently used)
该算法在需要淘汰某一页时，首先淘汰到当前时间为
止，被访问次数最少的那一页。这只要在页表中给每一页
增设一个
访问计数器
即可实现。每当该页被访问时，访问
计数器加
1
，而发生一次缺页中断时，则淘汰计数值最小的
那一页，并将所有的计数器清零。
98
b)
最近没有使用页面淘汰算法
NUR
该算法在需要淘汰某一页时，
从那些最近一个时期内未被
访问的页中任选一页淘汰
。只要在页表中增设一个
访问位
即
可实现。当某页被访问时，访问位置
1
。否则，访问位置
0
。
系统周期性地对所有引用位清零。当需淘汰一页时，从那些
访问位为零的页中选一页进行淘汰。
(4)
理想型淘汰算法
OPT(optimal replacement algorithm)
该算法淘汰在访问串中将来再也不出现的或是在离当前最
远的位置上出现的页。
这样，淘汰掉该页将不会造成因需要
访问该页又立即把它调入的现象。遗憾的是，这种算法无法
实现，因为它要求必须预先知道每一个进程的访问串。
99
5.4.5
存储保护
u页式管理可以为内存提供两种方式的保护。
一种是
地址越界保护
，另一种是
通过页表控
制对内存信息的存取操作方式以提供保护
。
u地址越界保护可由地址变换机构中的控制寄
存器的值
——
页表长度和所要访问的虚地址
相比较来完成。
u存取控制保护的实现则是在页表中增加相应
的
保护位
即可。
100
5.4.6
页式管理的优缺点
综上所述，
页式管理具有如下优点
:
(1)
由于它不要求作业或进程的程序段和数据在内存中连续存放，从
而
有效地解决了碎片问题
。
(2)
动态页式管理提供了内存和外存统一管理的
虚存实现
方式，使用
户可以利用的存储空间大大增加。这既提高了主存的利用率，又
有利于组织多道程序执行。
其主要缺点是
:
(1)
要求有相应的硬件支持
。例如地址变换机构，缺页中断的产生和选择淘汰页面
等都要求有相应的硬件支持。这增加了机器成本。
(2)
增加了系统开销
，例如缺页中断处理等。
(3)
请求调页的算法如选择不当，
有可能产生抖动现象
。
(4)
虽然消除了碎片，但
每个作业或进程的最后一页内总有一部分空间得不到利用
。
如果页面较大
，则这一部分的损失仍然较大。