3.5 分页存储管理Paging(书P63)3.5.1 引言同“实存”相对应的另外一类存储管理技术称为“虚拟存储”管理技术。虚拟存储概念的关键在于，使运行进程的访问地址与主存的可用地址相脱离。运行进程的访问地址叫做虚地址。在主存中的可用地址叫做实地址。一个运行进程可以访问的虚地址的范围叫做进程的虚地址空间。在指定的计算机系统中，可使用的实地址范围叫做计算机的实地址空间。用户全部程序和数据所组成的虚拟空间放在哪里呢？通常用一个大容量的外部存储器（磁盘、磁鼓）来存放每个用户的虚拟空间的全部数据。所以实际上用户的虚拟地址空间并不能增到无限大，它受到两个条件的制约： 指令中的地址场长度的限制。因为进程访问的虚拟地址应限制在指令中地址场长度所能表示的范围内； 外部存储器大小的限制。用户的虚拟空间不能超过外存中的作业存放空间。综上所述，所谓虚拟存储器是一个地址空间，是进程访问的逻辑地址空间，而不是物理的主存空间。虽然进程只访问虚地址，但是它们实际上必须在实存里运行。因此当进程运行时虚地址必须映象成为实地址。这种映象必须快速完成，否则计算机系统的性能就会降低到不能容忍的水平，从而抵消了采用虚拟存储器概念而带来的许多好处。决定作业虚拟地址空间中哪部分进入主存，哪能部分放回外存的工作由操作系统负责。具体来说它包括三方面内容： 将作业的哪部分装入主存； 放在主存什么位置； 主存空间不足时，把哪部分置换出主存。实现虚拟存储的两个最普通的方法是分页和分段，这要在本章详细讨论。352 分页的基本概念一、分页概念1把用户的逻辑地址空间分成相同大小的块，每块顺序编号，称为“页”（Page，虚页）。每页中指令顺序存放，页号为0，1，2，3，2等分主存：把主存也分成与页相同大小的块叫存储块（memory Block），也叫实页。块一旦定下来就不能改变。编号为0，1，2，3，3主存分配原则：分页情况下，每页装在一个存储块里，但连续的页面在内存空间中可以是不连续的，哪儿有空白区就放在哪儿，所以作业在内存中存放，页与页之间不连续，每页的信息是连续的。二、实现原理这就要在主存中设一个页表，或叫页面映象表（Page map table）。为作业的每页设一条表目。这张页表是当作业装入主存时，由系统根据分配情况建立的，而且是每个作业一张页表。系统在主存的固定区域内，拨出一些存储区来存放这些页表（系统表），系统有了这张页表后，就可对作业地址空间中的每一页进行动态重定位。为了便于分页和简化地址变换过程，通常选择页的大小为2的幂。例如1K=1024=2102K=2048=2114K=4096=212一般为1K，页的尺寸太大，和可重定位分区分配没什么不同了，页的尺寸太小，页表就得加长，太碎，调度增加，因此一般为1-4K。我们举一例子来说明分页技术下的动态地址变换过程：假定机器字长为16位，其中15位为有效地址04514页号页内相对地址（位移量）PW这样一表示，实际分页系统中用户的逻辑地址是一个有序对（P,W）,P是被访问项的页号，W是被访问项在页P内的位移量。如果一条指令在用户地址空间为100，即第P=0页，W=100；分到主存第2块（见上图），那么就是在主存中页表查出，实地址为2048+100=2148单元处。如果指令是LOAD 1，3500这3500的用户地址空间为3072+428查页表，3页分到块8（实页8），即8192为起始地址，页偏移428处，实地址等于8192+428=8620处，找到数据12345。在分页技术下的动态地址变换按如下方式进行：系统将作业的页表在主存的起始地址及页表长度放到一个控制寄存器内，当执行指令时，访问用户地址（逻辑地址）在页面映象表中找到页3对应实页（存储块8），将实存地址与W相连接而形成。这就是主存的物理地址8620由上述地址变换过程可以知道，程序地址空间的分页是由系统自动完成的，用户不用管。地址变换过程是通过页表来实现的。因此人们称页表为地址映射表。总之分页管理技术是 作业分成页，页内连续，页号顺序； 主存分成块（和页大小一样），块顺序编号； 每页分配一块内存，在内存中可以是散放（可不连续放）；物理空间和逻辑空间不一致。 提供页面映射表（page map table），建立页和块之间的函数关系。 相对地址用（页号P，页内位移量W）表示。页内位移量就是页内字节相对于该页第一字节的距离，我们称页内第一字节位移量为0。例1：页大小=1000字节 （十进制例子实际应是二进制）105=（0，105） 4178=（4，178）例2：页大小=4K字节6000=（1，1904） 访内过程LOAD 1，3500先算出页号和页内移量，查PMT表，得出该页在内存的存储块号；根据块号算出绝对地址=块号*块大小+位移量；访问绝对地址。三、 关于页表的一些考虑1页表大小：这上面已讲过，是大页小表，还是小页大表。况且要防止“越界”（页表长度页号超过页表长度叫越界）2页表始址的选择：2n幂，为了快速根据页表始址和页号找到相应表目，如作业页长为1024字节，则页长度为210，第i道作业的页表始址Pi=Ps+i*210采用直接映象的分页地址变换：四、采用联想存储器加快查表速度为了提高查表速度，在地址变换机构中加入一个高速、小容量的联想存储器（associative storage）,它的速度比主存快约一个数量级（普通主存按地址查询速度是1s，联想存储器查询速度为0.1s）,构成一张所谓快表。这个联想存储器具有并行查寻能力。运行的程序访问逻辑地址V=（P，W），为寻找页面P联想存储器的每个表目都同时被检索。它返回与页面P对应的块P，并且P与W连接，形成物理地址r。注意进入：进入联想映象的箭头实际上进入映象图的每个地址单元。这表明为与P匹配，联想存储器的每个地址单元都同时被检索。这就是造成联想存储器价格昂贵的原因。采用联想存储器只要访问一次主存根据数据的绝对地址取数就可以取出指令或存取数据。但实际上联想存储器价格太昂贵，不可能将页表全部放在联想存储器中实现纯粹联想映象，一般都采用折中方案。采用联想映象与直接映象相结合的分页保存在这张表中的页面表目仅与最近访问的页相对应，其余放在主存中（也就是执行着的作业，部分页表在联想存储器中，部分在内存中）。查页表时，先去联想映象（快），查不到再查主存页表。联想存储器中的表目采用这种方法置换，当要执行下一页时，硬件淘汰一页，再进一页，采用“排队先进先出”，全部由硬件线路自动完成。只要设8个联想存储器，成功率85%，12个93%，16个97%，大部分都可在存储器中找到表目（这种程序特性局部性，以后还介绍）五、分页存储分配算法为了实现分页存储器管理，OS必须建立和管理三种表： 作业 table(JT)整个系统一张，每个作业有一对应表目 Memory Block Table（存储分块分配表MBT）整个系统一张，它指出每个存储块的状态，空白块链在一起 页表（Page map table）每个作业一张六 、分页存储管理的优缺点优：不需紧缩（拼接）就消除了碎片，提高了存储利用率与CPU利用率，提高了多道程度。可以共享：借助不同进程的页面映象表的表目指向同一实页的方法，则那个实页就可在这些进程中间共享。共享有效地减少了运行一组进程所需要的主存容量，可能使一个给定的系统去支持更多的用户。缺： 增加动态变换机构，成本，速度。 多占内存来放PMT表，并花费CPU时间建立和管理表格。在分页系统中，是把主存分成固定尺寸的实页，这些实页应该是多长？分页的页面应该是多长，各种计算机系统是不同的（教材P86） 仍有页内碎片，平均浪费半页静态分页管理仍需把作业全部放入内存，有些无用信息也得存入。353 请求页式存储管理一、基本思想在作业运行之前，不限定把作业的整个地址空间全部装入主存，而只要求把当前需要的一部分装入主存，只要能运行即可。把一个作业的部分程序装入机器是可以运行的，产生的问题是 遇到要使用的“页”不在内存怎么办？ OS如何知道此“页”不在内存； 此页不在内存，又马上需要，应从外存调入，如此时内存没有空白块，需从内存撤出一页，腾出空白放新调入的一页，但怎么挑，撤哪一页。会不会发生紧接着要用撤出页的信息的可能？产生“页面抖动”现象？这是目前最有吸引力的办法（请求页式存储管理技术）。称之为“虚拟存储”技术。将“请求页式存储管理技术”称为虚拟存储技术是因为把内存和外存当作同一级存储器使用。用户作业不需要把全部作业放入内存就可以在内存运行仅把当前需要部分放入内存，其余放在次存，当需要时调入主存，这样多大的作业也可以运行，给用户印象是内存无限大。我们把作业地址空间称为“虚拟空间”，虚存在作业地址空间划分的页称为“虚页”；相应把主存称为“实存”，把实存中的分块称为“实页”。二、实现原理关于作业地址空间分页，实存分块和上一节完全一样，要有页面映象表（PMT）每个作业一个；存储分块表（MBT）整个系统一个；作业表（JT）整个系统一个，每个作业有一对应表目；增加外页面表（文件映象表File Map Table）实现请求页式存储管理，要解决两个问题：如作业运行，访问到某页不在主存中 如何发现； 如何处理（调入）。第一个问题，用扩充页表的项目解决：页号存储块号中断位辅存地址引用位修改位存取控制中断位（interrupt bit）I=1 表示虚页不在主存，自动触发“缺页中断”（不可屏蔽的中断），CPU必须处理中断，到外页面表中去找到此页，然后调入内存。I=0 虚页在主存。第二个问题，解决比较复杂：当被访问的页不在主存时，由动态地址变换机构产生一缺页中断信号，OS进行中断处理后，根据这页的辅存地址把它从辅存调入主存，然后作业继续运行。由于作业的各页是根据请求而装入主存，所以叫请求页式存储管理。可是新调进的页应放在什么地方？如主存有空白块，可以把它装入任何一个空白块中。随后把此块号填入作业页表相应表目，并改变它的中断位I=0，如果此时存储空间已满，则必须先淘汰已在主存中的页。这有个算法问题（下面还要介绍）。被淘汰的页是直接被新页覆盖了还是重新写回外存（磁盘），这要看这页是否被修改过。如没修改过，主存的页内容和外存页的内容一样，新页直接覆盖它即可；如修改过，就得写回磁盘，为了帮助有关软件作出页面置换决定，在页表中还增加： 引用位如果此块装入主存后被访问过，此位自动为（程序设计认为凡是用过的页下次可能还用，没用过的可能不用，这叫程序执行的局部特性）。虚拟存储管理策略的基础是局部性原理进程往往会不均匀地高度局部化地访问内存。（教材P84）局部性表现为时间局部性与空间局部性两种：时间局部性是对于时间的局部性意思最近被访问的存储位置，很可能不久将来还要访问例如 a)循环b)子程序c)栈d)用于计数和总计的变量空间局部性意思是邻近的项往往是类似的意思是存储访问有集成一组的倾向，以致一旦某个位置被访问到，很有可能它附近的位置也要被访问。例如： a)数组遍历 b)代码的顺序执行 c)程序员倾向于将相关的变量定义相互靠近存放。这叫程序性能的工作集理论（由Denni