第5章(2)虚存管理技术+

第五（2）章虚存管理技术5.1基本概念5.2页式管理补充：多级页表

十六进制地址转换时钟(Clock)置换算法5.3段式管理5.4段页式管理5.5局部性原理和抖动问题前面所述的各种管理技术统称为实存管理技术，其特点是在作业运行时，必须将整个作业的逻辑地址空间全部装入主存(除覆盖外)，当作业尺寸大于主存可用空间时，该作业就无法运行。同实存相对的另一类存储管理技术称为虚存管理技术。同实存管理的主要区别是：不用将整个作业装入主存就可以投入运行。引入如下一些概念：

1.虚拟存储器：是指一种实际上并不存在的虚假的存储器。

2.虚拟地址：把一个运行进程访问的地址称为虚拟地址。5.1基本概念

3.实地址：把处理机可直接访问的地址称为实地址。相应的有：虚地址空间、实地址空间的概念。●问题：

把虚地址空间和实地址空间分开后，这样虚地址空间可以远远大于实地址空间，亦即作业的大小可以远远大于主存空间的大小。另一个相关问题是：作业运行时，其整个虚地址空间(逻辑地址空间)是否必须全部装入主存？如果必须的话，那么虚地址空间仍然不能大于实地址空间。一个程序的某次运行，常有些部分是不用的(如：无错误发生时就不会调用出错处理程序)。所以，只让最近要用到的那部分程序和数据装入主存，以后用到哪部分再把哪部分调入，而把不用部分调出(暂存外存)。为了完成上述功能，操作系统应负责下面三个方面的任务：（1）把哪部分调入主存；（2）放在主存什么位置；（3）主存空间不足时，把哪部分淘汰出去。本章主要介绍目前广泛使用的三种虚存管理技术：■页式管理(静态页式管理和动态页式管理)■段式管理■段页式存储管理5.2页式管理●

实现原理

1.等分主存把主存划分成大小相同的存储块，称为页面(或块)，并给各页面从零开始编上序号：0，1，2，…。

2.等分作业的逻辑地址空间将程序的逻辑地址空间也划分若干个与页面大小相同的块,称为页。也编上序号0，1，2，…。●主存分配原则系统以页面(块)为单位把主存分给作业，每页对应内存中一个页面，这些页面可以是不相临的或连续的。

●页式存储管理根据进程的页是否一次全部装入还是部分装入而分为：静态页式管理－实存管理动态页式管理－虚存管理一、静态页式管理基本原理：要求程序执行前，分配其所需的所有页面，这些页面可以是不相邻的。这意味着内存中有足够的空闲页面才能执行某个程序。需要CPU的硬件支持。

下面图显示静态页式内存使用情况：静态页式管理主存分配情况FrameNumber0123456789101112131401234567891011121314A.0A.1A.2A.3

01234567891011121314A.0A.1A.2A.3B.0B.1B.2在页式储存管理中，是以页面为单位分给用户使用，为了记录主存的使用情况，系统为每个进程建立一个页表，最简单的页表包括如下信息：（1）页号：作业的各页的页号；（2）块号：指该页装入主存的第几个页面上。1.页表与页表地址寄存器▲页的大小带来的影响页小：内碎片小，页表长，管理复杂，存储信息少，可能频繁调页；页大：页表短，管理开销小，交换时对外存I/O效率高，但内碎片大，会多浪费内存LOAD1，1120

ADD1，24100100102100068021120200040006251241030000页1页2页3页0100020003000页号块号03192-3-02页号块号14270100020003000LOAD1，1120

ADD1，241031003102400050006000700010000900080002块3块4块5块6块7块8块9块0块1块91206802操作系统作业1作业2页表2.静态页式管理的特点优点：

■没有外碎片，每个内碎片不超过页的大小■一个程序不必连续存放。■由于页的大小相等，内存的分配、回收简单，易于管理。缺点：程序要求全部装入内存才能执行。3.逻辑地址的表示用户的逻辑地址一般是从基址“0”开始连续编址。在分页系统中，每个虚地址(相对地址)用一个数对(p，d)来表示，其中p表示页号，d表示页内地址(页内偏移量)。令A是一个虚地址，页面大小为L,则：

p=INT[A/L]，d=[A]modL

例如：设页面大小L=1000字节,A=3456,则:p=INT[3456/1000]=3L=[3456]mod1000=456在内存中的表示：

若页面大小为2的幂，逻辑地址转换为页号p和位移量d就非常简单(由地址变换机构自动完成)。页号页内地址(页内偏移量)pd例如：一个页长为1K，拥有64页的虚拟空间地址结构如图下图所示。151090pd26=64(页)，页的长度=210=1024(字节)=1K举例：采用页式存储管理的系统中，若逻辑地址中的页号用8位表示，页内地址用16位表示。问：（1）用户程序的最大长度是多少兆字节？（2）主存分块为多少K字节？（KB）解：逻辑地址中的页号用8位表示，就是说逻辑地址中最大页数是28=256(页)；页内地址用16位表示，即一个(逻辑)页大小为216=65536(字节)/1024=64K。（1）用户程序的最大长度就是256页全部使用的情况了，即256*64K=16384K=16384K/1024=16MB。（2）主存分块大小应该和逻辑页大小相同，即页面=64KB4.分页管理中的地址转换

静态页式管理的另一个关键问题是地址变换。即怎样由页号和页内相对地址变换到内存物理地址的问题。在页式管理中，地址变换的速度也是设计地址变换机构时必须考虑的问题之一。现以上图的指令LOAD1,1120为例说明分页管理中的地址变换过程。当CPU执行LOAD1,1120时，该指令给出的虚地址为1120，首先由地址变换机构自动将该地址分为页号p=1和位移量d=120，其转换过程如下图所示：页号块号03192-3-页表长度页表起址112091209×1000+120912068023100LOAD1,120…页式管理地址转换示意图pd控制寄存器内存地址越界比较

注：

实际的地址转换工作是计算机系统内部采用硬件机制完成的，即由地址转换机构MMU(MemoryManagementUnit)自动完成的，MMU是内存管理单元的意思，它是由中央处理器CPU用来管理虚拟存储器、物理存储器的控制线路，同时也负责虚地址映射到物理地址的映射。1.虚地址以十进制数给出页号：P＝INT(虚地址/页大小)——取整数部分位移量：W＝[虚地址]MOD页大小或

W＝虚地址%页大小——取余数根据题意产生页表；以页号查页表，得到对应页装入内存的块号计算机公式内存地址＝块号×页大小＋位移量●页式地址映射小结2.虚地址(逻辑地址、相对地址)以十六进制、八进制、二进制的形式给出将虚地址转换成二进制的数；按页的大小分离出页号和位移量(高位部分是页号，低位部分是位移量)；将低位部分——位移量直接复制到内存地址寄存器的低位部分；根据页号查页表，得到该页装入内存的物理块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。十六进制(参考)：0000=00001=10010=20011=30100=40101=50110=60111=71000=8

1001=91010=A1011=B1100=C1101=D1110=E1111=F记忆：210=1K211=2K212=4K213=8K214=16K215=32K216=64K….例1：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。解答:（1）虚地址7145P＝INT(7145/2048)＝3(对应物理块5)W＝[7145]mod2048＝1001MR=5*2048+1001=11241虚地址7145的内存地址是：11241（2）虚地址3412P＝INT(3412/2048)＝1(对应物理块9)W＝[3412]mod2048＝1364MR=9*2048+1364=19796

虚地址3412的内存地址是：19796例2：某虚拟存储器的用户空间共32个页面，每页1KB，主存16KB，假设某时刻系统为用户的0、1、2、3页分配的物理块为5、10、4、7，而该用户作业的长度为6页，试将十六进制的虚地址0A5C、103C、1A5C转换成物理地址。解答：用户空间(逻辑地址空间)为32*1KB=32KB，因215=32KB，故逻辑地址编码为15位，页面为1KB(210KB)，所以页号用5位，页内地址用10位。（1）0A5C0A5C=000101001011100P=2，W=1001011100

MR=001001001011100=125CH（2）103C103C=001000000111100P=4,W=0000111100

页号为4，合法，但该页未装入主存，故产生缺页中断；（3）1A5C1A5C=001101001011100P=6，因该用户作业的长度为6页(0~5)，故产生地址越界中断。一道考研题西北工业大学（2002）设有8页的逻辑空间，每页有1024字节(1KB)，它们被映射到32块的物理存储区中，那么逻辑地址的有效位是（）位，物理地址至少是（）位。分析：逻辑地址有两个部分组成：页号和页内偏移地址。逻辑空间有8（23）页，说明页号需要3位二进制位编码，而每页有1024（210）字节，说明页内偏移地址需要10位二进制位编码，因此逻辑地址的有效位为3+10=13位。因为物理地址与逻辑地址的页面大小相同，而物理存储块为32（25）占5位，所以物理地址至少为5+10=15位内存有32个物理块，物理块大小与逻辑块大小相同，故物理地址空间为32*1KB=32KB。因为215=32768B=32768/1024=32KB，故物理地址至少为15位。4.联想寄存器和快表联想寄存器：可按内容并行查找的快速寄存器。比内存贵、容量小。引入原因：页表驻留内存，执行访内指令要先到内存查页表，进行地址转换后才能进行访内操作，因此执行一条指令至少要访问内存两次为提高速度，将内存页表(也称慢表)中一部分经常使用页的页号和页面号等内容放在联想寄存器中(称为快表)。■具有快表的地址转换：每次访问主存时，首先查找快表，若找到所需的页，则快速形成物理地址。否则从页表(慢表)中查找后形成物理地址，同时把该页写入快表中。如果设计得当，快表的命中率可以很高。具有快表的地址变换机构页表寄存器页表始址页表长度＞页号页内地址＋逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址这就意味着，在为一个进程分配内存空间时，除了给进程本身分配内存空间外，还需要另外提供4MB的一块连续内存空间存放对应的页表。因为每个进程都要有自己的页表，这就需要更大存储空间来存放页表。5.两级和多级页表补充

CPU具有32位地址时，使用232逻辑地址空间的分页系统，规定页面4KB时，每个进程页表的表项最多有1M个，即页表最多有1M行（？），若每个页表项占用4个字节，则每个进程需要占用4MB连续内存空间存放页表(即需要1024个连续的内存物理块)。

解释：页面大小为4KB(212KB)，故页内编址12位，页号编址为:32–12=20位，220=1048576(个)=1048576/1024=1024K(个)=1M(个),所以共有1M个页表项。每个页表项占4个字节，故：1048576*4=4194304B=4096KB=4MB

可以采用两种方法来解决页表存放问题：①采用离散分配方式来解决难以找到一块连续的内存空间的问题;②只将当前需要的部分页表项调入内存，其余的页表项驻留在磁盘上，需要时再调入。采用此方法解决1）两级页表(Two-LevelPageTable)两级页表机制的做法是：■把整个页表进行分页，即将整个页表拆分成一张张小页表(称为页表页),小页表的大小与页框大小相同，然后再为这些小页表再建一张表，称为外层页表(也称页目录表)，外层页表存放每个小页表对应的内存物理块号。1011107801217421023第0页页表146…012…1023第1页页表11411501…102301234567……1141151468第1023页页表1468012…1023内存空间两级页表结构一个内存物理块为1KB。本例将页表拆分成1024个小页表。页目录表由上图可知，在页表的每个表项中存放的是进程的某页在内存的物理块号，如第0页存放在第1个物理块中，第1页存放在第4个物理块中。而在外层页表的每个表项中，所存放的是某页表分页的首址，如第0号小页表是存放在第1011物理块中，第1号小页表是存放在第1078物理块中等。在两级页表时，指令所给出的地址分为三部分：（外层页号，外层页内地址，页内地址）逻辑地址结构可描述如下(上述例子的逻辑地址结构)：1）外层页号用10位，210=1024B(将页表拆分为1024个小页)2）外层页内地址用10位，210=1024B（每个小页表为1024B）3）页内地址用12位，

212=4096B=4KB具有两级页表的地址变换机构页目录号页号页内地址p1p2d逻辑地址+外部页表寄存器页目录号+db页表物理地址……b二级页表地址变换需三次访问主存：一次访问页目录、一次访问页表页、一次访问指令或数据。虚拟地址二级页表结构及地址映射页表地址…..页目录(每进程一个)块号….页表代码或数据…..内存块++页目录地址外层页号页表位移页位移2)多级页表（略）

①对于32位的机器，采用两级页表结构是合适的；

②对于64位的机器，如果页面大小仍采用4KB(即212KB)，那么还剩下52位，假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于页号。此时在页表中可能有4096G个页表项(242=4096G)，要占用16384GB的连续内存空间。

必须采用多级页表，将页目录号表表再为页目录号表，也是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。一道考研题（东南大学2001)判断题：虚拟存储器是一个虚假的地址空间，因而这个地址空间的大小是没有限制的（）分析：在虚拟存储器中，用户的地址空间仍然受到地址字长和外存容量的限制。虚拟存储器的最大容量受地址长度（地址总线位数）决定，一个拥有32位地址长度的系统，其虚拟内存最大为232字节。当然，一个实际的虚拟存储器的大小还会受到辅助存储器大小的限制。答案错选择题一个计算机系统的虚拟存储器的最大容量是由（Ａ）确定的，其实际容量是由（B）确定的。A、Ｂ：①计算机字长；②内存容量；③硬盘容量；④内存和硬盘容量之和；⑤计算机的地址结构。答案：⑤、④2010考研题：某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为210字节（1K），页表项大小为2字节，逻辑地址结构为：,逻辑地址空间大小为216页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是

A.64

B.128

C.256D.512解：逻辑地址空间为216页，页表项为2个字节，故页表长度为

216×2=128KB，一个内存物理块存放1KB，故

128KB/1KB=128，即得页目录表(外层页表)至少包含

128个表项。

页目录号页号页内偏移量6.信息的共享和保护信息共享：允许进程的地址空间在内存中非连续存放，使得多个进程可共享某些页面。但共享代码页面受限制。为什么？信息保护：进行地址转换时，检查是否超页（逻辑页和页表控制寄存器中页表长度相比)；在页表中设置存取权限项。7.存储页面表存储页面表是整个系统的一张表，存储页面表指出内存各页面是否已被分配出去,以及未分配页面的总数。存储页面表也有两种构成方法。（1）位示图一种是在内存中划分一块固定区域，每个单元的每个比特代表一个页面。如果该页面已被分配，则对应比特位置1，否则置0。这种方法称为位示图法。如下图所示。位示图（2）空闲页面链存储页面表的另一种构成办法是采用空闲页面链的方法。在空闲页面链中，队首页面的第一个单元和第二个单元分别放入空闲页面总数与指向下一个空闲页面的指针。其他页面的第一个单元中则分别放入指向下一个页面的指针。空闲页面链的方法由于使用了空闲页面本身的单元存放指针，因此不占据额外的内存空间。二、动态页式管理1.引入原因

在静态页式存储管理中，要求把进程地址空间的全部页都要装入内存才能运行。而在实际中一个作业的某些部分可能在运行过程中是用不到的，比如：如果没有错误的发生，错误处理模块就不会被调用。因此，在静态页式管理中会将一些不需要的页也装入内存,而且内存资源不足时,该作业或进程将无法运行。2.动态页式管理的主要思想:

在作业或进程开始运行前，只将被认为是经常被反复执行和调用的部分装入内存，而其它部分在执行过程中动态的调入。即：通过交换的技术以小的内存运行大的作业。3.有两种动态装入方式

(1)

请求页式管理当发现欲执行的某条指令或数据不在内存时，发生缺页中断，由系统将外存的页面调入内存(软件实现)。

(2)

预调入方管理系统对那些在外存中的页进行调入顺序计算，估计出这些页中指令和数据的执行和被访问的顺序，并按此顺序事先将它们顺序调入和调出内存。4.请求页式管理需要解决的问题

(1)

如何发现页是否在内存可以用扩充页表的方法解决，即除了页号、页面号外，再增加该页是否在内存的标志位及该页在外存的起始地址。扩充后的页表如下：页号页面号标志位

外存始址

08Y

120Y

2-N

3-N

(2)如何处理缺页问题关于某页不在内存时的处理涉及两个问题：①采用何种方法把所缺的页调入内存；②如果内存没有空闲页面，把调进来的页放在什么地方(如何淘汰页的问题)。采用什么策略淘汰页(后面详细讲)如果内存中的某页被淘汰，有两种情况：其一是该页在程序运行时被修改过；其二是没被修改。如果被修改过，淘汰时应重新写到外存，若未修改，则不必重新入外存(因外存已有副本)。问题：如何知道被淘汰的页是否被修改过？

可在页表中再增加一项，以记录该页是否被修改过。增加后的页表如下：页号页面号标志位改变位

外存始址

修改位5.请求页式管理中的置换算法

置换算法在内存中没有空闲页面时被调用。它的目的是选出一个被淘汰的页面。如果内存中有足够的空闲页面存放所调入的页，则不必使用置换算法。把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中。因此，置换算法应该置换那些被访问概率最低的页，将它们移出内存。比较常用的置换算法有以下几种:

(1)

随机淘汰算法(RG)

在系统无法确定哪些页被访问的概率较低时，随机地选择某个用户的页面并将其换出。(2)轮转法(RR)

循回换出内存可用区内一个可以被换出的页面，无论该页是否刚被换进或以换进很长时间。(3)先进先出(FIFO)

总是选择在内存中驻留时间最长的一页被换出。FIFO算法认为先调入内存的页不再被访问的可能性大，因此选择最先调入的换出。事实上，那些在内存中停留时间最长的页往往也是经常被访问的页。假设某作业有5个页面，执行时引用的页序列为：0、1、2、3、0、1、4、0、1、2、3、4共访问12个页面，当系统给该进程3个内存块时，FIFO发生9次缺页中断：(4)最佳算法(OPT)

选择以后不再访问的页或经很长时间之后才可能访问的页进行淘汰。

例如：如果一个进程对页面的访问序列为：0、1、2、3、0、1、4、0、1、2、3、4，系统给该进程3个物理页块，则按照最佳置换算法，会产生7次缺页中断，缺页中断率为f=7/12。×表示缺页中断，√表示无缺页中断。×××××××√√√√√（5）最近最久未使用的页面置换算法(LRU)

该算法的基本思想是:

当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间也不会被访问。

要完全实现LRU算法是十分困难的。因为要找出最近最久未被使用的页面的话，就必须对每一个页面都设置有关的访问记录项，而且每一次访问都必须更新这些记录。这显然要花费巨大的系统开销。因此，在实际系统中往往使用LRU的近似算法。LRU页面置换算法举例：例如：进程P有5个页，进程访问页的顺序为：4，3，2，1，4，3，5，4，3，2，1，5；如果在内存中分配给该进程3个页面，则缺页情况如下：页面432143543215页面1432143543215页面243214354321页面34321435432缺页×××××××√√×××缺页中断次数：10次缺页率=(10/12)*100%=83.3%页面淘汰顺序：

4，3，2，1，5，4，3LRU有两个近似算法最不经常使用的页面淘汰算法(LFU)1）最不经常使用页面淘汰算法LFU(leastfrequentlyused)

该算法在需要淘汰某一页时，首先淘汰到当前时间为止，被访问次数最少的那一页。这只要在页表中给每一页增设一个访问计数器即可实现。每当该页被访问时，访问计数器加1，而发生一次缺页中断时，则淘汰计数值最小的那一页，并将所有的计数器清零。最近没使用的页面淘汰算法(NUR)2）最近没有使用页面淘汰算法NUR

该算法在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。只要在页表中增设一个访问位即可实现。当某页被访问时，访问位置1。否则，访问位置0。系统周期性地对所有引用位清零。当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。（6）Clock置换算法(时钟置换算法)1）简单的Clock置换算法①为每页设置一位访问位，当淘汰一个页面时，如果指针指向页面的访问位R为0，就将其淘汰，并把新的页面插入这个位置，指针向前移动一个位置；②如果访问位R为1，就清除R位(置0)，并把指针前移一个位置，直到找到一个R位为0的页面为止。

由访问位R和修改位M可以组合成下面四种类型的页面：

1类(R=0,M=0):

表示该页最近既未被访问，又未被修改，是最佳淘汰页。

2类(R=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。

3类(R=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问。

4类(R=1,M=1):

最近已被访问且被修改，该页可能再被访问。2.改进型Clock置换算法

其执行过程可分成以下三步：

(1)从指针所指示的当前位置开始，扫描循环队列，寻找R=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。

(2)如果第一步失败，则开始第二轮扫描，寻找R=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位R都置为0。

(3)如果第二步也失败，则将指针返回到开始的位置，并将所有的访问位R置为0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。6.Belady现象(异常现象)Belady现象：先进先出算法的一个缺点是它有一种陷阱现象。一般来说，对于任何一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。在极限情况下，这个推论是成立的。因为如果给一个进程分配了它所要求的全部页面，则不会发生缺页现象。但是，使用FIFO算法时，在未给进程或作业分配足够的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象。如下图所示。Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。FIFO算法的Belady现象7.Belady现象举例

例1：进程P有5页程序访问页的顺序为：1,2,3,4,1,2,5,1,2,3,4,5；如果在内存中分配3个页面，则缺页情况如下:×表示缺页中断，√表示无缺页中断。FIFO

1

2

3

4

1

2

5

1

2

3

4

5

页0

1

2

3

4

1

2

5

5

5

3

4

4

页1

1

2

3

4

1

2

2

2

5

3

3

页2

1

2

3

4

1

1

1

2

5

5

缺页

×

×

×

×

×

×

×

√

√

×

×

√

(12次访问中产生9次缺页中断)例2：进程P有5页程序访问页的顺序为：1,2,3,4,1,2,5,1,2,3,4,5；如果在内存中分配4个页面，则缺页情况如下:×表示缺页中断，√表示无缺页中断。(12次访问中产生10次缺页中断)8.抖动(Thrashing)现象在请求式页式管理中，在作业或进程运行过程中，当发现欲访问的页不在内存时，将产生缺页中断，分两种情况：

（1）如果主存中有空闲页面，则将所缺的页调入主存即可

(换入)。（2）如果主存中没有空闲的页面，则将调用置换算法将主存的某一个页面淘汰出去(换出)。如果置换算法选择不当，有可能会产生刚被换出内存的页又要马上被换入内存，而换入内存不久又马上被换出，如此反复将使整个系统的页面调度非常频繁，以致大部分时间都花费在主存和辅存之间来回换入和换出上，这种现象称为抖动现象。

综上所述，页式管理具有如下优点:

(1)由于它不要求作业或进程的程序段和数据在内存中连续存放，从而有效地解决了碎片问题。

(2)动态页式管理提供了内存和外存统一管理的虚存实现方式，使用户可以利用的存储空间大大增加。这既提高了主存的利用率，又有利于组织多道程序执行。

9.页式管理的优缺点其主要缺点是:(1)要求有相应的硬件支持。例如地址变换机构，缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。这增加了机器成本。(2)增加了系统开销，例如缺页中断处理等。(3)在请求页式管理中，如果置换算法选择不当，有可能产生抖动现象。(4)虽然消除了碎片，但每个作业或进程的最后一页内总有一部分空间得不到利用。如果页面较大，则这一部分的损失仍然较大。详解抖动：这个内存要求的临界值被称为工作集。图5.35说明这种情况。图5.35内存与交换次数的关系可以利用统计模型进一步分析工作集与抖动之间的关系。设r为CPU在内存中存取一个内存单元的时间t为从外存中读出一页数据所需时间p(s)为CPU访问内存时（即r时间内），所访问的页正好不在内存的概率，这里s是当前进程在内存中的工作集。在虚存情况下存取一个内存单元的平均时间可描述为T=r+p(s)*t由程序模拟可知，p(s)=ae-bs这里，0<a<1<b，ae-bs<<r假定内存中各并发进程具有相同的统计特性，而且对于一个并发进程来说，只有发生缺页时才变成等待状态。

由于访问外存一个页面的时间为t，且缺页发生的概率为p(s)，则在处理机访问一个内存单元的r时间内，平均每秒引起的内外存之间页传送率为p(s)/r。也就是每r/p(s)秒需要从外存向内存传送一页。(根据内存的读取时间和缺页概率来研究外存)对于一个在虚存范围内执行的进程，它可以处于三种可能的状态之中，即:t＜r/p(s) (2)t＞r/p(s) (3)t=r/p(s)对于第一种情况，由于页传送速度大于访问外存页面的速度（读取外存的时间小于平均缺页时间），因此，进程在执行过程中发生缺页的次数较少，并不经常从外存调页。在第二种情况时，由于内外存之间的页面传送速度已经小于访问外存页面速度（读取外存的时间大于平均缺页时间），因此，进程在执行过程中发生缺页的次数已经多到外存供不应求的地步。事实上，这时的系统已处于抖动状态。第三种情况是一种较理想的情况，即进程在执行过程中所需要的页数正好等于从外存可以调入的页数。此时该进程在内存中占有最佳工作集。根据以上讨论可知，一个进程在内存中占有最佳工作集的条件是:p(s)=r/tr是CPU访问内存单元所需平均时间，t是访问外存一个页面所需平均时间。因为p(s)可表示为p(w)=ae-bs从而有，s=ln(at/r)/b即，与内存存取速度r相比，若外存传送速度越慢(t大)，所需工作集就越大。实际中，由于各进程所包含的程序段多少，选用的淘汰算法等不一样，工作集的选择也不一样。由以上讨论，我们可以找出解决抖动问题的几种关键办法。抖动只有在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，也就是选择不同的淘汰算法以解决抖动问题。

在前面介绍的各种管理技术中，用户的逻辑地址空间都是一维的线性地址空间，这要求对源程序进行编译、链接时，把源程序中的主程序、子程序、数据区等按线性空间的一维地址顺序排列起来。这使得不同作业或进程之间共享公用子程序和数据变得非常困难，同时程序也不能动态地增长(程序的每部分的修改都要影响到其它部分。因此，程序的任何改动都要重新编译、链接和装配)。

另外，在页式管理中，一个页面中可能装有两个不同子程序段的指令代码，因此，通过页面来共享一个逻辑上完整的子程序或数据块是不可能的。

5.3段式管理一、基本概念1.段的定义

所谓段是一组相关的逻辑信息的集合。如主程序、子程序、数组和数据区等.2.作业的逻辑地址空间在分段情况下，每个作业的地址空间按照自身的逻辑关系分成若干个段，每个段有自己的段名(由程序员自己给出)和段号(系统自动生成)。每个段的逻辑地址空间均从基地址“0”开始编成连续的线性地址(故在分段情况下，作业的逻辑地址空间是二维的)。3.作业虚地址的表示

每个作业或进程的虚地址分为两部分：

即：虚地址（S，W）举例：

段号－S段内地址－WCALL[x]|<Y>LOAD1,[A]|6STORE1,[B]|<C>………01k分段MAIN＝0(主程序)0600Y:……分段X＝1(子程序)05000800C:……分段A＝2(数组)分段B＝3(数据区)10012061200CALL[x]|<Y>表示转移到子程序x中的入口点Y；LOAD1,[A]|6将数组A的第六个单元的值读入寄存器1中；STORE1,[B]|<C>将寄存器1中的内容存入分段B中的地址为C的单元中。段式管理的基本思想：把程序按内容或过程(函数)关系分成段，每段有自己的段名。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间。段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换成物理地址。和页式管理一样，段式管理也采用只把那些经常访问的段驻留内存，而把那些在将来一段时间内不被访问的段放入外存，待需要时自动调入的方法实现二维虚拟存储器。二、段式管理的内存分配与释放段式管理中以段为单位分配内存，即：每段分配一个连续的内存区。由于各段长度不等，所以这些存储区的大小不一。而且，同一个作业或进程所包含的每个段分配的空间可以是不相邻的。段式管理的内存分配与释放在作业或进程的执行过程中动态进行。首先，段式管理程序为一个进入内存准备执行的进程或作业分配部分内存，随着进程或作业的执行，根据需要随时申请调入段(换入)或淘汰段(换出)

。当进程要求调入某一段时，进程申请内存区可分为两种情况：（1）一种是当进程要求调入某一段时，内存中有足够的空闲区满足该段的内存要求。（2）另一种是内存中没有足够的空闲区满足该段的内存要求。第一种情况（内存有足够的内存区）当发生缺段时，内存有足够的连续的内存分区。系统要用相应的表格或数据结构来管理内存空闲区，以便对用户进程或作业的有关程序段进行内存分配和回收。事实上，可以采用和动态分区式管理相同的空闲区管理方法。即把内存各空闲区按物理地址从低到高排列或按空闲区大小从小到大或从大到小排列（空闲区自由链）。分区式管理时所用的几种分配算法:最先适应法、最佳适应法、最坏适应法都可用来进行空闲区分配。当然，分区式管理时用到的内存回收方法也可以在段式管理中使用。第二种情况（内存没有足够的内存区）在内存中没有足够的空闲区满足调入段的内存要求时。段式管理程序根据给定的置换算法淘汰内存中在今后一段时间内不再被CPU访问的段，也就是淘汰那些访问概率最低的段。动态页式管理中的几种常用的淘汰算法都可以用来作为段式管理时的淘汰算法。但是，与页式管理时每页具有相同的长度时不一样，需要调入的某段长度可能大于被淘汰的一段程序或数据的长度。这样，仅仅淘汰一段可能仍然满足不了需要调入段的内存要求。此时，就应再淘汰另外的段直到满足需调入段的内存要求时为止。事实上，一次调入时所需淘汰的段数与段的大小有关。如果一个作业或进程的段数较多，且段长之间的差别较大，则有可能出现调入某个大段时，需淘汰好几个小段的情况。不过，在段式管理时，任何一个段的段长都不允许超过内存可用区长度，否则将会造成内存分配出错。除了初始分配之外，段的动态分配是在CPU所要访问的指令和数据不在内存时产生缺段中断的情况下发生的。因此，段的淘汰或置换算法实际上是缺段中断处理过程的一部分。缺段中断处理过程的全过程如下图所示。其中：X代表所缺段的段号。该处理程序是在CPU访问执行时，地址变换机构发现该段不在内存，而由硬件发出缺段中断信号后被调用的。缺段中断处理过程FIFO:先来先服务LRU:最近最久未使用的页面置换算法三、段表和段表地址寄存器同分页一样，系统为每个作业建立一个段映射表－简称段表，以实现动态地址转换(该表由系统自动建立)。段表内容：段号、段的长度、段在主存的始址、段的状态位、访问位、修改位、段在外存的地址等(如下表所示)。段表地址寄存器：用以指出运行作业的段表在主存的起始地址和段表的长度。段表段号段长主存始址状态位访问位修改位在外存的地址四、段式管理中的地址变换在段式管理中，把一个虚地址分成段号和段内地址(段内偏移量)——（s,w）其中：s:段号w:段内地址(段内偏移量)151090sw26=64(段)，每段的最大长度=210=1024(字节)=1K举例：若段式存储管理中，供用户使用的逻辑地址为24位，其中段内地址占用16位。请分步骤计算并加以说明原因：（1）用户程序最多可分为多少段？（2）当把程序装人主存时，每段占用主存的最大连续区为多少K字节？解:(1)逻辑地址24位，段内16位，则用来表示段号用了24-16=8位。即用户程序最多可分为28=256个段；(2)每段的最大地址范围是216=65536B=65536/1024=64K，即每段占用主存的最大连续区为64K字节。四、段式管理中的地址变换在内存中给出一块固定的区域放置段表。当某进程开始执行时，管理程序首先把该进程的段表始址放入段表地址寄存器。通过访问段表地址寄存器可找到该进程的段表始地址址。然后由虚地址中的段号S查找段表。若该段在内存，则从段表相应表目中查出该段在内存的起始地址，并将其和段内相对地址w相加，从而得到实际的内存地址。如果该段不在内存，则产生缺段中断将CPU控制权交给内存分配程序。内存分配程序首先检查空闲区，以找到足够长度的空闲区来装入所需要的段。如果内存中的可用空闲区总数小于所要求的段长时，则检查段表中访问位，以淘汰那些访问概率低的段并将需要段调入。下面以LOAD1,1|100例，说明在段式管理中的地址转换过程MAIN=0[x]=1[A]=2LOAD1,1|100………12345…01K50001002000…段号段长主存始址

01K6K15008K23004KOS02k4k6k8k8×1024+100=8292LOAD1,1|100～～～～123458292[A]=2MAIN=0[x]=1段表长段表地址寄存器●

以LOAD1,1|100为例说明地址转换过程段表地址寄存器

段表长·1100段号s段内地址w段号段长主存始址

01K6K15008K23004K8×102410012345物理地址：段式地址映射示意图8×1024＋100＝8292与页式管理时相同，段式管理时也必须经过二次以上的内存访问。即首先访问段表以计算得到待访问指令或数据的物理地址，然后才是对物理地址进行读/写操作。为了提高访问速度，页式地址变换时使用的高速联想寄存器的方法也可以用在段式地址变换中。如果在联想寄存器中找到了所需要的段，则可以大大加快地址变换速度。五、段的共享与保护段式存储管理可以方便地实现内存信息共享和进行有效地内存保护。1.

段的共享在多道环境下，常常有许多子程序和应用程序是被多个用户所使用。如果每个用户进程或作业都在内存保留它们共享程序和数据的副本，那就会极大地浪费内存空间。最好的办法是内存中只保留一个副本，供多个用户使用，称为共享。下图给出了一个段式系统中共享的例子。如上图所示，如果用户进程或作业需要共享内存中的某段程序或数据，只要用户使用相同的段名，就可在新的段表中填入已存在于内存之中的段的起始地址，并以适当的读写控制权，就可做到共享一个逻辑上完整的内存段信息。在多道环境下，由于进程的并发执行,一段程序为多个进程共享时，有可能出现多次同时重复执行该段程序的情况(即某个进程在未执行完该段程序之前，其它并发进程又已开始执行该段程序)。这就要求它在执行过程中，该段程序的指令和数据不能被修改。另外，与一个进程中的其它程序段一样，共享段有时也要被换出内存。这时，就要在段表中设立相应的共享位来判别该段是否正被某个进程调用。显然一个正在被某个进程使用或即将被某个进程使用的共享段是不应该调出内存的。2.段的保护

与页式管理时相同，段式管理的保护主要有两种:一种是地址越界保护法，另一种是存取方式控制保护法。而地址越界保护则是利用段表中的段长项与虚拟地址中的段内相对地址比较进行的。若段内相对地址大于段长，系统就会产生保护中断。不过，在允许段动态增长的系统中，段内相对地址大于段长是允许的。为此，段表中设置相应的增补位以指示该段是否允许该段动态增长。六、段的动态链接静态链接装配，必须在运行前一次就把所有的子程序链接在一起并装入内存。这样，不仅占用大量的主存空间，而且也要耗费大量的CPU时间。所以最好采用什么时候用到哪一段再把该段调入内存，然后重新链接装配，这种方法称为段的动态链接。所谓段的动态链接是指：在一个程序开始运行时，只将主程序段调入内存，其它各段的装配是在主程序段运行过程中逐步进行的，每当调入一个新段时，再将这个段装配好，并与主程序段链接。

在段式存储管理环境下，因为分段是按信息的逻辑单位划分的，各段有自己的段名，并在作业运行期间仍能保持原有的逻辑信息结构，这不仅存取方便，而且增加一个段或增大一个段，不会影响其它段，段式管理的这一特点，十分有利段的动态链接。七、段式虚拟系统在段式虚拟系统中，通常只要把一个作业时当前需要的一个或几个段装入内存就可以投入运行，而其它分段都保存在外存(如磁盘)上。在运行过程中一旦发现要访问的段不在内存时，就产生缺段中断，由缺段中断处理程序来处理。（1）缺段中断处理程序通过查找主存自由分区表，若找到一块足够大的内存区，就将所缺的段调入主存；（2）若找不到，就检查未分配的内存空间的总和，确定是否对内存进行“紧缩”，或者根据一定的原则调出(淘汰)一些段，然后再将所缺的段调入内存，同时改变各种表格的相关项目；（3）中断处理完后，新调入的段与主存中原有的段进行段的动态链接，才能正常运行。八、段式管理的优缺点1.优点（1）提供了虚拟存储器。与页式管理不同的是，段式虚存每次交换的是一段有意义的信息，而不是像页式虚存那样只交换固定大小的页从而需要多次缺页中断才能把所需信息完整地调入内存。（2）允许动态增长一个段。段长可根据需要动态增长，这对那些需要不断增加或吸收新数据的段来说，将是非常有好处的。（3）允许程序的动态链接和装配。（4）便于实现共享。如果几个作业都需要某子程序或数据区时，只在内存保留一个副本即可。2.缺点（1）和页式管理一样，段式管理系统在选择淘汰算法时也必须十分慎重，否则也有可能产生抖动现象。（2）段式管理比其他几种方式要求有更多的硬件支持。这就提高了机器成本。另外，由于在内存空闲区管理方式上与分区式管理相同，在碎片问题以及为了消除碎片所进行的合并等问题上较分页式管理要差。再者，允许段的动态增长也会给系统管理带来一定的难度和开销（3）段式管理的另一个缺点就是每个段的长度受内存可用区大小的限制。段页式储存管理是把分段和分页两种管理技术相结合，综合了二者的优点(分段在逻辑上的优点和分页在管理存储空间方面的优点)。即：用分段的方法来了分配和管理虚存，用分页的方法来分配和管理内存。一、基本思想(或实现原理)

（1）等分主存：把整个主存空间分成大小相等的存储块－页面，并从0依次编上序号。（2）作业的地址空间采用分段方式，即按程序的自然逻辑关系把作业的地址空间分成若干段，而每一段均有自己的段名和段号。5.4段页式管理04k-1分段MAIN＝0(主程序)03k-1分段X＝1(子程序)02k-1分段A＝2(数组)内存（3）作业的每一段又采用分页方法，即按页面大小