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

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

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

§5.5 段式与段页式管理
§5.6 局部性原理和抖动问题
本章小结

§
5.5
段式与段页式管理
5.5.1
段式管理的基本思想
• 分区式管理和页式管理时的进程地址空间结构都是
线性
的，这要求对源程序进行编译、链接时，把源程序中的主
程序、子程序、数据区等按线性空间的一维地址顺序排列
起来。这使得
不同作业或进程之间共享公用子程序和数据
变得非常困难。
如果系统不能把用户给定的程序名和数据
块名与这些被共享程序和数据在某个进程中的虚页对应起
来，则不可能共享这些存放在内存页面中的程序和数据。
另外，
由于在页式管理时，一个页面中可能装有两个不同
子程序段的指令代码，因此，通过页面共享来达到共享一
个逻辑上完整的子程序或数据块是不可能的。
• 再者，
分区管理和页式管理只能采用静态链接
。从减少
CPU
开销和存储空间浪费的角度来看，静态链接是不合适
的。
102
• 综上所述，段式存储管理是基于为用户提供一个方
便灵活的程序设计环境而提出来的。
段式管理的基
本思想是
:
把程序按内容或过程
(
函数
)
关系分成段，
每段有自己的名字。一个用户作业或进程所包含的
段对应于一个
二维线性虚拟空间
，也就是一个二维
虚拟存储器。段式管理程序以
段
为单位分配内存，
然后通过地址映射机构把段式虚拟地址转换成实际
的内存物理地址。
和页式管理时一样，段式管理也
采用只把那些经常访问的段驻留内存，而把那些在
将来一段时间内不被访问的段放入外存，待需要时
自动调入的方法实现二维虚拟存储器。
103
5.5.2
段式管理的实现原理
1.
段式虚存空间
• 段式管理把一个进程的虚地址空间设计成二维结
构，即段号
s
与段内相对地址
w
。
页式管理中，被划
分的页号按顺序编号递增排列，属
一维空间
，而段
式管理中的段号与段号之间无顺序关系。
另外，段
的划分也不像页的划分那样具有相同的页长，
段的
长度是不固定的
。
每个段定义一组逻辑上完整的程
序或数据。
例如，一个进程中的程序和数据可被划
分为主程序段、子程序段、数据段与工作区段。
• 每个段是一个首地址为零的、连续的一维线性空间。
根据需要，
段长可动态增长
。
对段式虚地址空间
的访问包括两个部分
:
段名
和
段内地址
。
104
例如，
CALL [X]|<Y>
转向段名为
X
的子程序的入口点
Y
。
LOAD 1,[A]|6
将段名为
A
的数组中第
6
个元素的值读到寄存器
1
中。
STORE 1,[B]|<C>
将寄存器
1
的内容存入段名为
B
，
段中地址为
C
的单元中。
其中的段名
X
，
A
，
B
及入口名
Y
等经编译程序和链接程序
编译链接后转换成机器内部可以识别的段号和段内单元号。
例如，
CALL
［
X
］
|<Y>
可被编译成
CALL 3|120,
如果［
X
］
对应的段号为
3
，
<Y>
对应的段内单元号为
120
的话。
105
2.
段式管理的内存分配与释放
• 段式管理中以段为单位分配内存，每段分配一个连续的内
存区。由于各段长度不等，所以这些存储区的大小不一。
而且，同一进程所包含的各段之间不要求连续。
• 段式管理的内存分配与释放在作业或进程的执行过程中
动
态进行
。
首先，
段式管理程序为一个进入内存准备执行的
进程或作业分配部分内存，以作为该进程的工作区和放置
即将执行的程序段。随着进程的执行，进程根据需要随时
申请调入新段和释放老段。
进程对内存区的申请和释放可
分为两种情况。
一种是当进程要求调入某一段时，内存中
有足够的空闲区满足该段的内存要求。另一种是内存中没
有足够的空闲区满足该段的内存要求。
106
• 对于第一种情况，系统要用相应的
表格
或
数据结构
来管理
内存空闲区，以便对用户进程或作业的有关程序段进行内
存分配和回收。事实上，可以采用和动态分区式管理相同
的空闲区管理方法。即把内存各空闲区按物理地址从低到
高排列或按空闲区大小从小到大或从大到小排列。与这几
种空闲区自由链相对应，分区式管理时所用的几种分配算
法
:
最先适应法
、
最佳适应法
、
最坏适应法
都可用来进行空
闲区分配。当然，
分区式管理时用到的内存回收方法也可
以在段式管理中使用
。
• 另一种内存空闲区的分配与回收方法是在内存中没有足够
的空闲区满足调入段的内存要求时使用的。这时，段式管
理程序根据给定的
置换算法
淘汰内存中在今后一段时间内
不再被
CPU
访问的段，也就是淘汰那些访问概率最低的段。
107
• 动态页式管理中的几种常用的淘汰算法都可以用来作为段
式管理时的淘汰算法
。例如
FIFO
置换算法、
LRU
算法及其
近似算法等。但是，
与页式管理时每页具有相同的长度时
不一样，需要调入的某段长度可能大于被淘汰的一段程序
或数据的长度。这样，仅仅淘汰一段可能仍然满足不了需
要调入段的内存要求。此时，就应再淘汰另外的段直到满
足需调入段的内存要求时为止。
• 事实上，
一次调入时所需淘汰的段数与段的大小有关
。如
果一个作业或进程的段数较多，且段长之间的差别较大，
则有可能出现调入某个大段时，需淘汰好几个小段的情况。
不过，
在段式管理时，任何一个段的段长都不允许超过内
存可用区长度，否则将会造成内存分配出错。
108
• 除了初始分配之外，
段的动态分配是在
CPU
所要访
问的指令和数据不在内存时产生缺段中断的情况下
发生的。
因此，
段的淘汰或置换算法实际上是缺段
中断处理过程的一部分
。
• 缺段中断处理过程的全过程如图
5.29
所示。图
5.29
中，
X
代表所缺段段号。该处理程序是在
CPU
访问
执行时，地址变换机构发现该段不在内存，而由硬
件发出缺段中断信号后被调用的。
109
图
5.29
缺段中断处理过程
110
3.
段式管理的地址变换
由于段式管理只存放部分用户信息副本在内存，而大部分
信息在外存中，这必然引起
CPU
访内时发生所要访问的段不
在内存的现象。那么，
CPU
如何感知到所要访问的段不在内
存而启动中断处理程序呢
?
还有，
段式虚拟地址属于一个二维的虚拟空间
。
一个二维
空间的虚拟地址怎样变换为一个一维的线性物理地址呢
?
这些
都由段式地址变换机构解决。
(1)
段表
(segment mapping table)
和页式管理方案类似，段式管理程序在进行初始内存分配
之前，
首先根据用户要求的内存大小为一个作业或进程建立
一个段表
，
以实现动态地址变换和缺段中断处理及存储保护
等。
与页式管理时一样，段式管理也是通过
段表
来进行内存
管理。考虑了缺段处理和段式访问控制保护后的段表如图
5.30
所示。
111
图
5.30
段表
图中
段号
与用户指定的段名一一对应，
始址
和
长度
分别
表示该段在内存或外存的物理地址与实际长度。
存取方式
是
用来对该段进行存取保护的。只有处理机状态字中的存取控
制位与段表中存取方式一致时才能访问该段。
内外
栏是指出
该段现在存储于外存还是内存中。如果该栏目指出所访问段
在外存的话，则发生中断。而
访问位
则是根据淘汰算法的需
要而设的，这里假定淘汰算法淘汰那些访问位未被改变过的
段
(NUR
算法
)
。
访问位
内外
存取方式
长度
始址
段号
112
(2)
动态地址变换
• 一般在内存中给出一块固定的区域放置段表
。当某
进程开始执行时，管理程序首先把该进程的段表始
址放入段表地址寄存器。通过访问段表寄存器，管
理程序得到该进程的段表始址从而可开始访问段表。
然后，由虚地址中的段号
s
为索引，查段表。若该
段在内存，则判断其存取控制方式是否有错。如果
存取控制方式正确，则从段表相应表目中查出该段
在内存的起始地址，并将其和段内相对地址
w
相
加，从而得到实际内存地址。
113
• 如果该段不在内存，则产生
缺段中断
将
CPU
控制权交给内
存分配程序。内存分配程序首先检查空闲区链，以找到足
够长度的空闲区来装入所需要的段。如果内存中的可用空
闲区总数小于所要求的段长时，则检查段表中
访问位
，以
淘汰那些访问概率低的段并将需要段调入。段式地址变换
过程如图
5.31
所示。
• 与页式管理时相同，
段式管理时的地址变换过程也必须经
过二次以上的内存访问
。
即首先访问段表以计算得到待访
问指令或数据的物理地址，然后才是对物理地址进行取数
据或存数据操作。
为了提高访问速度，页式地址变换时使
用的
高速联想寄存器
的方法也可以用在段式地址变换中。
如果在联想寄存器中找到了所需要的段，则可以大大加快
地址变换速度。
114
图
5.31
段式地址变换过程
115
4.
段的共享与保护
段式存储管理可以方便地实现内存信息共享和进行有效地
内存保护。这是因为段是按
逻辑意义
来划分的，可以
按段名
访问
的缘故。
(1)
段的共享
在多道环境下，常常有许多子程序和应用程序是被多个用
户所使用的。特别是在多窗口系统、支持工具等广泛流行的
今天，被共享的程序和数据的个数和体积都在急剧增加，有
时往往超过用户程序长度的许多倍。这种情况下，如果每个
用户进程或作业都在内存保留它们共享程序和数据的副本，
那就会极大地浪费内存空间。最好的办法是
内存中只保留一
个副本，供多个用户使用，称为
共享
。
图
5.32
给出了一个段
式系统中共享的例子。
图116
5.32
段式系统中共享内存副本
117
如图
5.32
所示那样，如果用户进程或作业需要共享内
存中的某段程序或数据，
只要用户使用相同的段名，就
可在新的段表中填入已存在于内存之中的段的起始地
址，并置以适当的读写控制权，就可做到共享一个逻辑
上完整的内存段信息。
另外，在多道环境下，由于进程的并发执行
,
一段程
序为多个进程共享时，有可能出现多次同时重复执行该
段程序的情况
(
即某个进程在未执行完该段程序之前，
其他并发进程又已开始执行该段程序
)
。这就要求它
在
执行过程中，该段程序的指令和数据不能被修改。
还
有，与一个进程中的其他程序段一样，
共享段有时也要
被换出内存
。这时，就要在段表中设立相应的
共享位
来
判别该段是否正被某个进程调用。显然
一个正在被某
个进程使用或即将被某个进程使用的共享段是不应该调
出内存的。
118
(2)
段的保护
与页式管理时相同，段式管理的保护主要有两种。
一种是
地址越界保护法
，另一种是
存取方式控制保护
法
。关于存取方式控制保护已在前面介绍，这里不再
重复。而
地址越界保护则是利用段表中的段长项与虚
拟地址中的段内相对地址比较进行的
。若段内相对地
址大于段长，系统就会产生保护中断。不过，在允许
段动态增长的系统中，段内相对地址大于段长是允许
的。为此，
段表中设置相应的
增补位
以指示该段是否
允许该段动态增长。
119
5.5.3
段式管理的优缺点
与页式管理和分区式管理比较，段式管理的长处与短处可分别
小结如下
:
(1)
和动态页式管理一样，段式管理也提供了内外存统一管理的虚
存实现
。与页式管理不同的是，段式虚存每次交换的是一段有
意义的信息，而不是像页式虚存那样只交换固定大小的页从而
需要多次缺页中断才能把所需信息完整地调入内存。
(2)
在段式管理中，
段长可根据需要动态增长
。这对那些需要不断
增加或吸收新数据的段来说，将是非常有好处的。
(3)
便于对具有完整逻辑功能的信息段进行共享
。
(4)
便于实现动态链接
。由于段式管理是按信息的逻辑意义来划分
段，每段对应一个相应的程序模块。因此，可用段名加上段入
口地址等方法在执行过程中调入相应的段进行动态链接。当
然，
段的动态链接需要一定的硬件支持
。例如需要链接寄存器
存放被链接段的出口等。
120
• 段式管理比其他几种方式要求有更多的硬件支持
。
这就提高了机器成本。另外，由于在内存空闲区管
理方式上与分区式管理相同，在碎片问题以及为了
消除碎片所进行的合并等问题上较分页式管理要差。
再者，允许段的动态增长也会给系统管理带来一定
的难度和开销。
• 段式管理的另一个缺点就是每个段的长度受内存可
用区大小的限制
。
• 和页式管理一样，段式管理系统在选择淘汰算法时
也必须十分慎重，否则也有可能产生
抖动现象
。
121
5.5.4
段页式管理的基本思想
• 以上几种存储管理方式各有特长。
段式管理为用户提供了
一个二维的虚地址空间，反映了程序的逻辑结构，有利于
段的动态增长以及共享和内存保护等，这大大地方便了用
户。而分页系统则有效地克服了碎片，提高了存储器的利
用率。从存储管理的目的来讲，主要是方便用户的程序设
计和提高内存的利用率。
那么，
把段式管理和页式管理结
合起来让其互相取长补短不是更好吗
?
于是，段页式管理方
式便被提了出来。
• 不过，
段页式管理的开销会更大
。因此，段页式管理方式
一般只用在
大型机系统
中。近年来由于硬件发展很快，段
页式管理的开销在工作站等机型上已变得可以容忍了。
122
5.5.5
段页式管理的实现原理
1.
虚地址的构成
段页式管理时，一个进程仍然拥有一个自己的
二
维地址空间
，这与段式管理时相同。首先，
一个进程
中所包含的具有独立逻辑功能的程序或数据仍被划分
为段，并有各自的段号
s
。
这反映和继承了段式管理
的特征。其次，
对于段
s
中的程序或数据，则按照一
定的大小将其划分为不同的页。
和页式系统一样，最
后
不足一页的部分仍占一页
。这反映了段页式管理中
的
页式特征
。从而，
段页式管理时的进程的虚拟地址
空间中的虚拟地址由三部分组成
:
即
段号
s
，
页号
p
和
页内相对地址
d
。
如下所示
:
123
• 对于这个由三部分组成的虚拟地址来说，
程序员可
见的仍是
段号
s
和
段内相对地址
w
。
p
和
d
是由地址
变换机构把
w
的高几位解释成页号
p
，
以及把剩下
的低位解释为页内地址
d
而得到的。
• 由于
虚拟空间的最小单位是页而不是段
，从而内存
可用区也就被划分成为若干个大小相等的页面，且
每段所拥有的程序和数据在内存中可以分开存放。
分段的大小也不再受内存可用区的限制。
124
2.
段表和页表
• 为了实现段页式管理，
系统必须为
每个作业或进程
建立一张段表，
管理内存分配与释放、缺段处理、
存储保护和地址变换等。
另外，
由于一个段又被划
分成了若干页，
每个段又必须建立一张页表
，把段
中的虚页变换成内存中的实际页面。
显然，
与页式
管理时相同，页表中也要有实现缺页中断处理和页
面保护等功能的表项。
另外，
由于在段页式管理
中，页表不再是属于进程而是属于某个段，因此，
段表中应有专项指出该段所对应页表的
页表始址
和
页表长度
。
段页式管理中段表、页表以及内存的关
系如图
5.33
所示。图中各表中
其他栏可参考段式或
页式管理中的相应栏目
。
125
图
5.33
段页式管理中段表、页表与内存的关系
126
3.
动态地址变换过程
• 在一般使用段页式存储管理的计算机系统中，都在
内存中辟出一块固定的区域存放进程的段表和页表。
因此，
在段页式管理系统中，要对内存中指令或数
据进行一次存取的话，至少需要访问三次以上的内
存。
第一次
是由段表地址寄存器得到段表始址去访
问段表，由此取出对应段的页表地址。
第二次
则是
访问页表得到所要访问的物理地址。只有在访问了
段表和页表之后，
第三次
才能访问真正需要访问的
物理单元。
显然，这将使
CPU
的执行指令速度大大
降低。
127
• 为了提高地址转换速度，设置
快速联想寄存器
就显得比段
式管理或页式管理时更加需要。
在快速联想寄存器中，存
放当前最常用的段号
s
、
页号
p
和对应的内存页面与其他控
制用栏目。
当要访问内存空间某一单元时，可在通过段表、
页表进行内存地址查找的同时，根据快速联想寄存器查找
其段号和页号。
如果所要访问的段或页在快速联想寄存器
中，则系统不再访问内存中的段表、页表而直接把快速联
想寄存器中的值与页内相对地址
d
拼接起来得到物理地址。
经验表明，一个在快速联想寄存器中装有
1/10
左右的段号、
页号及页面的段页式管理系统，可以通过快速联想寄存器
找到
90%
以上的所要访问的内存地址。
• 段页式管理的地址变换机构如图
5.34
所示。
128
图
5.34
段页式地址变换
129
• 以上简单地介绍了段页式管理中地址变换的基本原理。有
关段页式管理中的
存储保护
和
共享
以及
缺段或缺页中断处
理
等，可参照段式管理或页式管理中的方法解决。
• 总之，因为
段页式管理是段式管理的页式管理方案结合而
成的，所以具有它们二者的优点
。但反过来说，
由于管理
软件的增加，复杂性和开销也就随之增加了。
另外，
需要
的硬件以及占用的内存也有所增加。
更重要的是，
如果不
采用联想寄存器的方式提高
CPU
的访内速度，将会使得执
行速度大大下降。
130
§
5.6
局部性原理和抖动问题
• 动态页式管理，段式管理以及段页式管理都提供了一种将
内存和外存统一管理的实现方法
。
然而，由于上述实现方
法实质上要在
内存和外存之间交换信息
，因此，就要不断
地启动外部设备以及相应的处理过程。一般来说，计算机
系统的外部存储器具有较大的容量而访问速度并不高。为
了进行数据的读写而涉及到的一系列处理程序也要耗去大
量的时间。
如果内存和外存之间数据交换频繁，势必会造
成对输入
/
输出设备的巨大压力和使得机器的主要开销大多
用在反复调入调出数据和程序段上，从而无法完成用户所
要求的工作。
因此，
要求在内存中存放一个不小于最低限
度的程序段或数据，而且它们必须是那些正在被调用，或
那些即将被调用的部分。
131
• 由
模拟实验
知道，
在几乎所有的程序的执行中，在一段时间
内，
CPU
总是集中地访问程序中的某一个部分而不是随机地对
程序所有部分具有平均访问概率。把这种现象称为
局部性原理
。
与
CPU
访问该局部内的程序和数据的次数相比，该局部段的移
动速率相当慢。这就使得前面所讨论的页式管理、段式管理以
及段页式管理所实现的虚存系统成为可能。
• 但是，如果不能正确地将那些系统所需要的局部段放入内存的
话，则显然系统的效率会大大降低，甚至无法有效地工作。
• 试验表明，任何程序在局部性放入时，都有一个临界值要求。
当内存分配小于这个临界值时，内存和外存之间的交换频率将
会急剧增加，
而内存分配大于这个临界值时，再增加内存分配
也不能显著减少交换次数。
• 这个
内存要求的临界值被称为
工作集
。图
5.35
说明这种情况。
132
图
5.35
内存与交换次数的关系
133
• 一个进程执行过程中
缺页
(missing page)
的发生有
两种可能。
一种是并发进程所要求的工作集总和大
于内存可提供的可用区。
这时，
系统将无法正常工
作，因为缺乏足够的空间装入所需要的程序和数据。
另一种可能性是，虽然存储管理程序为每个并发进
程分配了足够的工作集，但系统无法在开始执行前
选择适当的程序段和数据进入内存。
这种情况下，
只能依靠执行过程中，当
CPU
发现所要访问的指令
或数据不在内存时，由硬件中断后转入中断处理程
序，将所需要的程序段和数据调入。
这是一种很自
然的处理方法。
134
• 当给进程分配的内存小于所要求的工作集时，由于内存外存之
间交换频繁，访问外存时间和输入
/
输出处理时间大大增加，反
而造成
CPU
因等待数据空转，使得整个系统性能大大下降，这
就造成了系统抖动。
• 可以利用
统计模型
进一步分析工作集与抖动之间的关系。
• 设
r
为
CPU
在内存中存取一个内存单元的时间，
t
为从外存中读
出一页数据所需时间，
p(s)
为
CPU
访问内存时，所访问的页正
好不在内存的概率，这里
s
是当前进程在内存中的工作集。
• 显然，在虚存情况下存取一个内存单元的平均时间可描述为
T=
r+p(s
)
*
t
由程序模拟可知，
p(s
)=
ae
-bs
这里，
0<a<1<b
，
ae
-bs
<<r
135
• 另外，假定内存中各并发进程具有相同的统计特性，而且
对于一个并发进程来说，只有发生缺页时才变成等待状态。
这是为了简化讨论而忽略了外部设备和进程通信功能的存
在。
• 由于访问外存一个页面的速度为
t
，
且缺页发生的概率为
p(s)
，
则在处理机访问一个内存单元的
r
时间内，平均每秒
引起的内外存之间页传送率为
p(s)/r
。
也就是每
r/p(s)
秒需要
从外存向内存传送一页。从而
，对于一个在虚存范围内执
行的进程，它可以处于三种可能的状态之中，即
:
(1)t
＜
r/p(s
)
(2)t
＞
r/p(s
)
(3)t=
r/p(s
)
136
• 对于第一种情况，由于页传送速度大于访问外存页面的速
度，因此，进程在执行过程中发生缺页的次数较少，并不
经常从外存调页。
• 但是，在第二种情况时，由于内外存之间的页面传送速度
已经小于访问外存页面速度，因此，进程在执行过程中发
生缺页的次数已经多到外存供不应求的地步。事实上，这
时的系统已处于抖动状态。
• 第三种情况是一种较理想的情况，即进程在执行过程中所
需要的页数正好等于从外存可以调入的页数。此时该进程
在内存中占有最佳工作集。
• 根据以上讨论可知，一个进程在内存中占有最佳工作集的
条件是
: p(w)=r/t
• 这里，
r
是
CPU
访问内存单元所需平均时间，
t
是访问外存一
个页面所需平均时间。
137
• 因为
p(w)
可表示为
p(w)=
ae
-bw
• 从而有，
w=
ln(at/r)/b
rabnt(
• 即，
与内存存取速度
r
相比，若外存传送速度越
慢，所需工作集就越大。
• 当然，上面讨论是在作了许多近似的情况下得出的
结论。事实上，由于各进程所包含的程序段多少，
选用的淘汰算法等不一样，工作集的选择也不一样。
一般来说，选择工作集有静态和动态两种选择方
法，这里不再进一步介绍
。
• 另外，由以上讨论，我们可以找出解决抖动问题的
几种关键办法。
138
• 抖动只有在
t>r/p(s)
时才会发生。而
p(s)
等于
ae
-bs
是一个与工
作集
s
、
参数
a
和
b
有关的概率值。
p(s)
是可以改变的。对于给定
的系统来说，
t
和
r
则是一个很难改变的数字。显然，解决抖动问
题的最关键办法是将
p(s)
减少到使
t=r/p(s)
。
这只需要
:
(1)
增加
s
，
也就是
扩大工作集
，或是
(2)
改变参数
a
和
b
，
也就是
选择不同的淘汰算法以解决抖动问题
。
• 在物理系统中，为了防止抖动的产生，在进行淘汰或置换时，
一般总是把缺页进程锁住，不让其换出，而调入的页或段总是
占据那些暂时得不到执行的进程所占有的内存区域，从而扩大
缺页进程的工作集。
UNIX System
Ⅴ中就是采用的这种方法。
139
本
章
小
结
• 本章介绍了各种常用的内存管理方法，它们是
分区式管理、
页式管理、段式管理和段页式管理。
内存管理的核心问题
是如何
解决内存和外存的统一，以及它们之间的数据交换
问题。
内存和外存的统一管理使得内存的利用率得到提
高，用户程序不再受内存可用区大小的限制。与此相关
联，内存管理要解决内存扩充、内存的分配与释放、虚拟
地址到内存物理地址的变换、内存保护与共享、内外存之
间数据交换的控制等问题。
• 图
5.36
系统地对几种存储管理方法所提供的功能和所需硬件
支持作了一个比较。