操作系统笔记第3章虚存管理演示.docx
《操作系统笔记第3章虚存管理演示.docx》由会员分享，可在线阅读，更多相关《操作系统笔记第3章虚存管理演示.docx（31页珍藏版）》请在冰点文库上搜索。
操作系统笔记第3章虚存管理演示
3.5分页存储管理Paging（书P63）
3.5.1引言
同“实存”相对应的另外一类存储管理技术称为“虚拟存储”管理技术。
虚拟存储概念的关键在于，使运行进程的访问地址与主存的可用地址相脱离。
运行进程的访问地址叫做虚地址。
在主存中的可用地址叫做实地址。
一个运行进程可以访问的虚地址的范围叫做进程的虚地址空间。
在指定的计算机系统中，可使用的实地址范围叫做计算机的实地址空间。
用户全部程序和数据所组成的虚拟空间放在哪里呢？
通常用一个大容量的外部存储器（磁盘、磁鼓）来存放每个用户的虚拟空间的全部数据。
所以实际上用户的虚拟地址空间并不能增到无限大，它受到两个条件的制约：
⑴指令中的地址场长度的限制。
因为进程访问的虚拟地址应限制在指令中地址场长度所能表示的范围内；
⑵外部存储器大小的限制。
用户的虚拟空间不能超过外存中的作业存放空间。
综上所述，所谓虚拟存储器是一个地址空间，是进程访问的逻辑地址空间，而不是物理的主存空间。
虽然进程只访问虚地址，但是它们实际上必须在实存里运行。
因此当进程运行时虚地址必须映象成为实地址。
这种映象必须快速完成，否则计算机系统的性能就会降低到不能容忍的水平，从而抵消了采用虚拟存储器概念而带来的许多好处。
决定作业虚拟地址空间中哪部分进入主存，哪能部分放回外存的工作由操作系统负责。
具体来说它包括三方面内容：
⑴将作业的哪部分装入主存；
⑵放在主存什么位置；
⑶主存空间不足时，把哪部分置换出主存。
实现虚拟存储的两个最普通的方法是分页和分段，这要在本章详细讨论。
3．5．2分页的基本概念
一、分页概念
1．把用户的逻辑地址空间分成相同大小的块，每块顺序编号，称为“页”（Page，虚页）。
每页中指令顺序存放，页号为0，1，2，3，…
2．等分主存：
把主存也分成与页相同大小的块叫存储块（memoryBlock），也叫实页。
块一旦定下来就不能改变。
编号为0，1，2，3，…
3．主存分配原则：
分页情况下，每页装在一个存储块里，但连续的页面在内存空间中可以是不连续的，哪儿有空白区就放在哪儿，所以作业在内存中存放，页与页之间不连续，每页的信息是连续的。
二、实现原理
这就要在主存中设一个页表，或叫页面映象表（Pagemaptable）。
为作业的每页设一条表目。
这张页表是当作业装入主存时，由系统根据分配情况建立的，而且是每个作业一张页表。
系统在主存的固定区域内，拨出一些存储区来存放这些页表（系统表），系统有了这张页表后，就可对作业地址空间中的每一页进行动态重定位。
为了便于分页和简化地址变换过程，通常选择页的大小为2的幂。
例如1K=1024=210
2K=2048=211
4K=4096=212
一般为1K，页的尺寸太大，和可重定位分区分配没什么不同了，页的尺寸太小，页表就得加长，太碎，调度增加，因此一般为1-4K。
我们举一例子来说明分页技术下的动态地址变换过程：
假定机器字长为16位，其中15位为有效地址
04514
页号页内相对地址（位移量）
PW
这样一表示，实际分页系统中用户的逻辑地址是一个有序对（P,W）,P是被访问项的页号，W是被访问项在页P内的位移量。
如果一条指令在用户地址空间为100，即第P=0页，W=100；分到主存第2块（见上图），那么就是在主存中页表查出，实地址为2048+100=2148单元处。
如果指令是LOAD1，3500
这3500的用户地址空间为3072+428
查页表，3页分到块8（实页8），即8192为起始地址，页偏移428处，实地址等于8192+428=8620处，找到数据12345。
在分页技术下的动态地址变换按如下方式进行：
系统将作业的页表在主存的起始地址及页表长度放到一个控制寄存器内，当执行指令时，访问用户地址（逻辑地址）
在页面映象表中找到页3对应实页（存储块8），将实存地址与W相连接而形成。
这就是主存的物理地址8620
由上述地址变换过程可以知道，程序地址空间的分页是由系统自动完成的，用户不用管。
地址变换过程是通过页表来实现的。
因此人们称页表为地址映射表。
总之分页管理技术是
⑴作业分成页，页内连续，页号顺序；
⑵主存分成块（和页大小一样），块顺序编号；
⑶每页分配一块内存，在内存中可以是散放（可不连续放）；
物理空间和逻辑空间不一致。
⑷提供页面映射表（pagemaptable），建立页和块之间的函数关系。
⑸相对地址用（页号P，页内位移量W）表示。
页内位移量——就是页内字节相对于该页第一字节的距离，我们称页内第一字节位移量为0。
例1：
页大小=1000字节（十进制例子实际应是二进制）
105=（0，105）
4178=（4，178）
例2：
页大小=4K字节
6000=（1，1904）
⑹访内过程
LOAD1，3500
先算出页号和页内移量，查PMT表，得出该页在内存的存储块号；根据块号算出绝对地址=块号*块大小+位移量；访问绝对地址。
三、关于页表的一些考虑
1．页表大小：
这上面已讲过，是大页小表，还是小页大表。
况且要防止“越界”（页表长度——页号超过页表长度叫越界）
2．页表始址的选择：
2n幂，为了快速根据页表始址和页号找到相应表目，如作业页长为1024字节，则页长度为210，第i道作业的页表始址Pi=Ps+i*210
采用直接映象的分页地址变换：
四、采用联想存储器加快查表速度
为了提高查表速度，在地址变换机构中加入一个高速、小容量的联想存储器（associativestorage）,它的速度比主存快约一个数量级（普通主存按地址查询速度是1μs，联想存储器查询速度为0.1μs）,构成一张所谓快表。
这个联想存储器具有并行查寻能力。
运行的程序访问逻辑地址V=（P，W），为寻找页面P’联想存储器的每个表目都同时被检索。
它返回与页面P对应的块P’，并且P’与W连接，形成物理地址r。
注意进入：
进入联想映象的箭头实际上进入映象图的每个地址单元。
这表明为与P匹配，联想存储器的每个地址单元都同时被检索。
这就是造成联想存储器价格昂贵的原因。
采用联想存储器只要访问一次主存根据数据的绝对地址取数就可以取出指令或存取数据。
但实际上联想存储器价格太昂贵，不可能将页表全部放在联想存储器中实现纯粹联想映象，一般都采用折中方案。
采用联想映象与直接映象相结合的分页
保存在这张表中的页面表目仅与最近访问的页相对应，其余放在主存中（也就是执行着的作业，部分页表在联想存储器中，部分在内存中）。
查页表时，先去联想映象（快），查不到再查主存页表。
联想存储器中的表目采用这种方法置换，当要执行下一页时，硬件淘汰一页，再进一页，采用“排队先进先出”，全部由硬件线路自动完成。
只要设8个联想存储器，成功率85%，12个——93%，16个——97%，大部分都可在存储器中找到表目（这种程序特性——局部性，以后还介绍）
五、分页存储分配算法
为了实现分页存储器管理，OS必须建立和管理三种表：
⑴作业table（JT）——整个系统一张，每个作业有一对应表目
⑵MemoryBlockTable（存储分块分配表MBT）
——整个系统一张，它指出每个存储块的状态，空白块链在一起
⑶页表（Pagemaptable）——每个作业一张
六、分页存储管理的优缺点
优：
不需紧缩（拼接）就消除了碎片，提高了存储利用率与CPU利用率，提高了多道程度。
可以共享：
借助不同进程的页面映象表的表目指向同一实页的方法，则那个实页就可在这些进程中间共享。
共享有效地减少了运行一组进程所需要的主存容量，可能使一个给定的系统去支持更多的用户。
缺：
①增加动态变换机构，成本↑，速度↓。
②多占内存来放PMT表，并花费CPU时间建立和管理表格。
在分页系统中，是把主存分成固定尺寸的实页，这些实页应该是多长？
分页的页面应该是多长，各种计算机系统是不同的（教材P86）
③仍有页内碎片，平均浪费半页
静态分页管理仍需把作业全部放入内存，有些无用信息也得存入。
3．5．3请求页式存储管理
一、基本思想
在作业运行之前，不限定把作业的整个地址空间全部装入主存，而只要求把当前需要的一部分装入主存，只要能运行即可。
把一个作业的部分程序装入机器是可以运行的，产生的问题是
⑴遇到要使用的“页”不在内存怎么办？
⑵OS如何知道此“页”不在内存；
⑶此页不在内存，又马上需要，应从外存调入，如此时内存没有空白块，需从内存撤出一页，腾出空白放新调入的一页，但怎么挑，撤哪一页。
会不会发生紧接着要用撤出页的信息的可能？
产生“页面抖动”现象？
这是目前最有吸引力的办法（请求页式存储管理技术）。
称之为“虚拟存储”技术。
将“请求页式存储管理技术”称为虚拟存储技术是因为把内存和外存当作同一级存储器使用。
用户作业不需要把全部作业放入内存就可以在内存运行仅把当前需要部分放入内存，其余放在次存，当需要时调入主存，这样多大的作业也可以运行，给用户印象是内存无限大。
我们把作业地址空间称为“虚拟空间”，虚存在作业地址空间划分的页称为“虚页”；相应把主存称为“实存”，把实存中的分块称为“实页”。
二、实现原理
关于作业地址空间分页，实存分块和上一节完全一样，要有
页面映象表（PMT）——每个作业一个；
存储分块表（MBT）——整个系统一个；
作业表（JT）——整个系统一个，每个作业有一对应表目；
增加外页面表（文件映象表FileMapTable）实现请求页式存储管理，要解决两个问题：
如作业运行，访问到某页不在主存中
①如何发现；
②如何处理（调入）。
第一个问题，用扩充页表的项目解决：
页号
存储块号
中断位
辅存地址
引用位
修改位
存取控制
中断位（interruptbit）I=1表示虚页不在主存，自动触发“缺页中断”（不可屏蔽的中断），CPU必须处理中断，到外页面表中去找到此页，然后调入内存。
I=0虚页在主存。
第二个问题，解决比较复杂：
当被访问的页不在主存时，由动态地址变换机构产生一缺页中断信号，OS进行中断处理后，根据这页的辅存地址把它从辅存调入主存，然后作业继续运行。
由于作业的各页是根据请求而装入主存，所以叫请求页式存储管理。
可是新调进的页应放在什么地方？
如主存有空白块，可以把它装入任何一个空白块中。
随后把此块号填入作业页表相应表目，并改变它的中断位I=0，如果此时存储空间已满，则必须先淘汰已在主存中的页。
这有个算法问题（下面还要介绍）。
被淘汰的页是直接被新页覆盖了还是重新写回外存（磁盘），这要看这页是否被修改过。
如没修改过，主存的页内容和外存页的内容一样，新页直接覆盖它即可；如修改过，就得写回磁盘，
为了帮助ＯＳ有关软件作出页面置换决定，在页表中还增加：
⑴引用位——如果此块装入主存后被访问过，此位自动为１（程序设计认为凡是用过的页下次可能还用，没用过的可能不用，这叫程序执行的局部特性）。
虚拟存储管理策略的基础是局部性原理——进程往往会不均匀地高度局部化地访问内存。
（教材P84）
局部性表现为时间局部性与空间局部性两种：
时间局部性是对于时间的局部性——意思最近被访问的存储位置，很可能不久将来还要访问
例如a）循环
b）子程序
c）栈
d）用于计数和总计的变量
空间局部性意思是邻近的项往往是类似的——意思是存储访问有集成一组的倾向，以致一旦某个位置被访问到，很有可能它附近的位置也要被访问。
例如：
a）数组遍历
b）代码的顺序执行
c）程序员倾向于将相关的变量定义相互靠近存放。
这叫程序性能的工作集理论（由Denning于１９６８年提出，教材P83）那么设引用位，如果此页被引用过，一般淘汰不考虑它。
淘汰是要淘汰引用位为０的页。
⑵修改位——如果块中信息被修改过（往里赋过值），此位为１，若仅仅是读过，此位为０。
作用：
此位为“０”，说明与磁盘上拷贝相同，直接覆盖；此位为“１”，说明与磁盘上拷贝不同，淘汰之前要写回盘上。
这样做是为了减少输入/输出动作，减少系统开销。
三、页面置换算法（书P75）
当主存中无空闲块时，为了装入一个页面而必须按某种算法从已在主存的页中选择一而，将它暂时调出主存，让出主存空间，用来存放所需装入的页面，这个工作程序称为“页面调度”。
如何选择调出的页面是很重要的，如果采用了一个不合适的算法，就会出现这样的现象：
刚被调出的页面又立即要用，因而又要把它装入，而装入不久又被子先中调出，调出不久又被装入，如此反复，使得整个系统的页面置换非常频繁，以致大部分的cpu时间花在来回进行页的调度上，只有一小部分时间用于作业的实际运算。
这种局面称为系统“抖动”（thrashing颠簸）。
一个比较好地页面置换算法可以尽可能避免这种局面。
下面介绍几种：
⑴OPT最优算法（OptimalPapereplacemenT）
选择将来再也不被访问或最远的将来才被访问的页面置换出去。
证明这种算法最优性是可能的，实际上这种算法不能实现，因为我们不能预见未来。
⑵先进先出（FIFO）算法
在先进先出页面置换中，我们标明每页进入主存的时间。
实际上分配给一个作业的存储块数为m，建立一张m个元素的队列表Q（0），Q
（1）…Q（m-1）和一个置换指针，这个队列是按页调入主存的先后顺序排列的，指针始终指向最早调入主存的一页。
先进先出算法是当需要淘汰一页时，选择在主存中驻留时间最长的那页淘汰掉。
另外，一般认为，分配给进程的存储块（实页）越多，进程经历的页面故障（缺页中断）就越少。
但有人提出反例：
在采用FIFO置换算法的情况下，当分配给进程的实页数量增加时，某些页面访问踪迹实际上显示出缺页中断增加。
这种现象被称为FIFO异常现象（书P80）。
页面踪迹——作业访问地址空间的规律
FIFO异常现象与其说是一个重要结果，倒不如说是一种奇怪现象。
它对OS学生的实际意义是起警告作用，OS是复杂的机构，直观的感觉是靠不住的。
⑶最近最久未使用算法（LeastRecentlyUsed）
提出这种算法的基本思想，是根据一个作业在执行过程中过去的页面踪迹来推测未来的行为。
这种算法是：
当需要淘汰一页时，选择在最近一段时间内最久未用的页淘汰掉。
实现这种算法就是周期性地检查“引用位”，查到为0的引用位记录的是一个页面自上次被访问以来所经历的时间t，淘汰时选t大的就是最近一段时间最久未用的页。
这种算法的基本依据是它认为过去一段时间不曾被访问过的页，在最近的将来可能也不再会被访问。
而实际上最近最久未用页可能是一个包括有几个页面的大循环程序中的一页，下一次就要使用。
淘汰它，我们会发现自己恰恰要立即把它调回主存。
⑷最近不使用算法（Nat_Used_RecentlyPagereplacement）
这是个最流行的，低开销的近似LRU算法。
利用页表增加的引用位和修改位来实现。
规定：
引用位=0没访问过
=1此页被访问过
修改位=0没修改过
=1被修改过
算法如下：
初始，所有页的引用位全置为0，当访问某页时，此页引用位=1。
初始所有页的修改位都为0，一旦一页被修改过，它的修改位置1。
当需要淘汰一页时，首先试图找一个未引用（访问）过的页（近似LRU）。
若找不到，我们只能淘汰访问过的页。
如果一页没访问过，但要核对它是否修改过（引用位周期复位，而修改位总不变），如此页未修改过，我们就淘汰它（简单覆盖，不用访问磁盘）。
这样可以减少系统开销（overhead）。
上面提到的NUR方案，存在着
四组页面：
组1：
00，未引用过，未修改过
组2：
01，未引用过，修改过
组3：
10，引用过，未修改过
组4：
11，引用过，修改过
那么肯定组1的页首先淘汰。
四、页面共享
在分页那一节中我们就讲过，分页分配使每个作业能利用存储空间一些非连续的存储块，那么通过让不同进程的页指向同一存储块的方法实现程序库和公共数据段共享。
实现页面共享引起的主要问题是：
当共享此页的所有作业页表中的中断位和相应指针都必须更新。
六、请求页式系统的优缺点
优点：
①提供大量虚存，作业的地址空间不再受物理存储器大小的限制；
②更有效地利用主存（不用的不存）；
③方便用户大作业（不用考虑覆盖）；
缺点：
①overhead↑.“用时间换取了空间”
②容易引起系统抖动和瘫痪
3．6分段存储管理
事实上一个作业常常由大量的标准和非标准的程序模块和数据段组成。
采用请求分页存储管理，作业运行时，页是一页一页地调入，而程序常常跨页（教材P89），因此人们希望按照程序模块来划分段，并按这些段来分配主存。
所谓段，可定义为一组逻辑信息，如主程序，子程序，数组，工作区（数据区）等等都可以称之为段。
它们通常是以文件形式存于文件系统中。
3．6．1分段地址空间2
分段存储管理的基本概念可用下列几方面来表征：
1．作业的logicaladdressspace:
分段情况下要求
每个作业的地址空间按照程序自身的自然逻辑关系分成若干段。
每个段有自己的段名（段名通常由程序员给出）。
系统为了管理的方便，常常为每段规定一个内部段名。
内部段名实际上是一个编号，称为段号。
每个段的地址空间都从“0”开始，并且编成连续性的线性地址。
2．程序的地址结构：
由于虚拟地址要用（S,W）来描述，所以指令的地址的结构就如上所述，通常规定每个作业的段号为从“0”开始的连续正整数。
07823
段号段内相对地址（位移量）
SW
假定某机器指令的地址部分长为24位，如果规定左边8位表示段号，而右边16位表示段内地址，这样的地址结构就限定了一个作业最多的段数为256段，最大的段长为64K字节。
3．主存分配：
段式管理的主存分配以段为单位，每一段分配一块连续的主存分区，一个作业的各段分到的主存分区不要求是相邻连续的分区。
进程也是只有当它的现行段（作为最低限度）在主存中才可以运行。
段作为完整单位从辅存传输到主存。
一个段内部的段有单元都安排在主存中连续的单元里，但是不同的段（同一程序）可以占据实存中许多分离的存储块。
3．6．2实现原理
实现分段管理的关键在于，如何保证分段在主存空间中正确运行。
也就是说如何进行动态地址转换。
那么同分页一样：
1．段表和段表地址寄存器：
系统为每个作业建立一个段映象表（简称段表）以实现动态地址变换，指出段在主存中位置，段表中应包含以下内容：
段号；段的长度；段在主存中起始地址；段的状态位（是否在主存）；访问位（淘汰时用）；修改位（淘汰时是否要重写回磁盘）；段的外存地址等。
同样，系统还要设立一个段表地址寄存器以指出运行作业（进程）的段表在主存中的起始地址和段表的长度。
段号
段在主存起始地址
段长
中断位
辅存地址
引用位
修改位
存取控制
2．分段管理中的地址转换
段地址转换与分页情况基本相同，大致如下：
作业运行时，由系统将该作业的段表地址和段表号装入段表地址寄存器中。
当作业访问某逻辑地址（S，W）时，系统将段表地址寄存器中内容b与段号同段表表目中查得段S在主存中的起始地址S’，再将S’与段内地址W相加，而得到欲访问单元的主存绝对地址，并进行访问。
上述步骤也是由硬件自动完成的。
和分页一样，CPU执行指令的速度降低为原来的1/2（因两次访问主存）。
为了提高地址转换速度也是要采取高速缓冲器实现联想映象或直接与联想相结合的映象来完成，以提高执行指令的速度。
在这里我们特别要提一下，分页和分段在概念上是完全不同的。
①分页不是完整的逻辑信息总体的结合，而段是信息的逻辑单位，它是有意义的一组信息
②页的大小一样，段的大小不一
③段是用户可见的，（分段可以在用户编程时确定，也可以在编译程序对源程序编译时根据信息的性质来划分），而页是用户看不见的，是OS分的。
用户可感知段，分页活动用户是看不见的，而仅仅用于主存管理。
3．6．3保护措施
⑴段表中设置段长批示值以指明段长，当存储访问时，段地址中和W位移量与段长比较，如超过段长，则发生越界中段信号。
⑵建立存取控制：
段表中除指明段长外，还增加“存取方式”一项；例如人事档案只允许人事部门的进程读/写（修改），其它单位只能读（或不能读）。
R
W
E
A
读访问写访问执行访问续加访问
⑶采用存储保护Key：
OS
1
A
1
A
2
B
2
B
3
C
1
A
3
C
2
B
0
空白
4
D
CPU
存储保护键（PSW）
2
3．6．4段式虚拟存储系统
为此，系统建立下列诸表来记住状态
1段表（SMT）——每个作业一个（尺寸，存取方式，状态，位置…）
2自由存储区表——整个系统一个（FMB）
3现行分段表：
整个系统一个，记录共享段的状态
这是因为主存中可能有若干个作业，这个作业往往共享（sharing）一些段。
那么把所有共享段的信息放在现行分段表中，它记录：
共享段的状态：
当前是否在主存，该段在主存的始址，共享作业数每个作业的作业名，作业号以及在该作业中的段号，允许存取的方式等。
每个允许被共享的段，调入主存时，均在此表上登记，当共享段由主存空间紧张调出时，须查有几个用户共享它，然后给几个用户一个NO的信息。
4现行调用表每个作业一个，这是为动态链接时用，什么叫动态链接，下一小节就介绍
5作业表——整个系统一个，记录作业段表始址，段表长度。
3．6．5分段的动态链接
一个作业是许多程序模块和数据段组成的，在以前所讲的存储管理技术中，无论是分页和实存管理技术，为了程序正确的执行，必须要由链接装配程序把一个作业所调用的各个子程序和数据段连接成一个可运行的目标模块，把它们组成一个统一编址的相对地址空间。
这个过程叫运行程序的“静态链接过程”。
段的动态链接——是指在一个程序运行开始时，只将主程序装配好并调入主存。
其它各段的装配是在主程序段运行过程中逐步进行的。
每当需要调用一个新段时，再将这个新段装配好，并与主程序段链接。
1．链接间接字和链接中断
在计算机原理中介绍过机器指令中有直接寻址和间接寻址两种方式。
在间接寻址方式中，把包含直接地址的字称为间接字。
在间接字中，除了包含直接地址外，还包含附加的状态位Ｌ，
Ｌ＝１表示该段未链接要链接，发出链接中断信号
Ｌ＝０表示该段已进行了链接。
因此间接字也叫链接间接字。
在具有段的动态链接功能的机器中，处理机在执行间接指令（间接寻址）时，其硬件能自动对链接间接字中的边接标志位Ｌ进行判断。
当Ｌ＝１时，硬件自动触发中断信号，并且停止执行该间接指令，转去执行连接中断处理程序。
等到边接中断处理程序处理完后（Ｌ已置为“０”）再重新执行该间接指令；
若Ｌ＝０，就根据间接字中的直接地址去取数据执行之。
2．编译程序的链接准备工作：
假如用户用某种高级语言书写主程序ＭＡＩＮ
编译时一般遵循以下原则：
当被编译的程序段中的语句是访问本段的单元时，则该语句被编译成直接寻址指令格式；若是访问外段的单元时；则被译成间接寻址指令格式，编译程序为这在本段中设置一连接间接字，并将置字中Ｌ＝１。
链接间接字中的直接地址中本应包含直接数的地址，但由于要访问的外段与本段沿未链接，故编译程序在本段中要保留被访问段的符号名，以便访问时进行链接。
保留的方法是开辟一个存储单元来存放被访问段的符号名
升级会员 