计算机操作系统中的分页存储管理与页表的作用

前面介绍的几种存储管理方式，要求作业的逻辑地址空间连续地存放在内存的某个区域中。当内存中没有足够大的区域时，则作业无法装入，或必须移动某些作业后才能装入。是否有可能把作业的连续逻辑地址空间分散到几个不连续的内存区域，且仍能使作业正确执行？若可行的话，则既可充分利用内存空间又可减少移动所花费的开销。不仅如此，还可采用虚拟存储管理技术，实现在较小的内存空间里运行较大的作业。

5.3.1 分页存储管理基本思想

分页存储管理是把内存分成大小相等的许多区，每个区称为一块。与之对应，编制程序的逻辑地址也分成页，页的大小与块的大小相等。好比写文章时，若所用的稿纸每张可写400个字，那么这篇文章也就是400字为一页。

分页式存储器的逻辑地址由两部分组成：页号和页内地址。其格式为：

地址结构确定了内存的分块大小，也就决定了页面的大小。假定地址总长度为15位，其中页号占5位，页内地址占10位，这样逻辑地址中可有32页，编号为0～31，每一页有1 024个字节，编号为0～1 023。从地址结构来看，逻辑地址是连续的，在编程时无须考虑如何分页。当使用一组顺序的地址时，如果地址是0～1 023，则只使用了低10位地址部分，而高地址（页号）部分为“0”，显然这些地址是属第0页的。如果继续使用1 024～2 047的地址，在地址结构中页号部分为“1”，而页内地址仍为0～1 023个字节。依此类推，一组顺序的连续地址由地址结构分页了。所以，在编程时仍需用连续的逻辑地址。

存储器分配时，以物理块为单位进行分配。一个作业的信息有多少页，装入主存时就会给它分配多少物理块。但是分配给作业的物理块可以是不连续的，即作业信息是按页分散存放在内存的空闲物理块中。采用见缝插针的方法，内存中哪一块空闲，就可用其存放作业的一页信息，避免为得到连续的存储空间而进行的移动。如果作业A有4页（A0、A1、A2和A3），那么只要找出4个空闲物理块，作业A就可装入内存，如图5-9所示。

作业执行时根据逻辑地址中的页号找到所在内存的物理块号，再确定当前指令应访问的内存绝对地址。

分页存储管理必须解决两个关键的问题：第一，如何知道内存中哪些块被占用，哪些物理块空闲；第二，作业信息被分散保存后如何确保作业的正确执行。

图5-9 按页分配内存空间

在分页系统中，允许将进程的各个页离散地存储在内存不同的物理块中，但系统应能保证进程的正确运行，即能在内存中找到每个页面所对应的物理块。为此，系统又为每个进程建立了一张页面映像表，简称页表。在进程地址空间内的所有页（0～n），依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号，见图5-10的中间部分。在配置了页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。

图5-10 页表的作用

即使在简单的分页系统中，也常在页表的表项中设置一存取控制字段，用于对该存储块中的内容加以保护。当存取控制字段仅有一位时，可用来规定该存储块中的内容是允许读／写，还是只读；若存取控制字段为二位，则可规定为读／写、只读和只执行等存取方式。如果有一进程试图去写一个只允许读的存储块时，将引起操作系统的一次中断。如果要利用分页系统去实现虚拟存储器，则还须增设一数据项。

为了能将用户地址空间中的逻辑地址变换为内存空间中的物理地址，在系统中必须设置地址变换机构。该机构的基本任务是实现从逻辑地址到物理地址的转换。由于页内地址和物理地址是一一对应的（例如，对于页面大小是1 KB的页内地址是0～1 023，其相应的物理块内的地址也是0～1 023，无须再进行转换），因此，地址变换机构的任务实际上只是将逻辑地址中的页号，转换为内存中的物理块号，而页表的作用就是用于实现从页号到物理块号的变换，因此，地址变换任务是借助于页表来完成的。

页表的功能可以由一组专门的寄存器来实现。一个页表项用一个寄存器。由于寄存器具有较高的访问速度，因而有利于提高地址变换的速度；但由于寄存器成本较高，且大多数现代计算机的页表又可能很大，使页表项的总数可达几千甚至几十万个，显然这些页表项不可能都用寄存器来实现，因而页表大多驻留在内存中。在系统中只设置一个页表寄存器PTR（Page-Table Register），在其中存放页表在内存的始址和页表的长度。进程未执行时，页表的始址和页表长度存放在本进程的PCB中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器中。所以在单处理机环境下，虽然系统中可以运行多个进程，但只需一个页表寄存器。当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址（相对地址）分为页号和页内地址两部分，再以页号为索引去检索页表。查找操作由硬件执行。在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间，系统产生地址越界中断。若未出现越界错误，则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，此时可从中得到该页的物理块号，将之装入物理地址寄存器中。与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的变换。图5-11示出了分页系统的地址变换机构。

图5-11 分页系统的地址变换机构

由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据（或向此地址中写入数据）。因此，采用这种方式会使计算机的处理速度降低近1／2，以此高昂代价来换取存储器空间利用率的提高，是得不偿失的。为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”（Associative Memory），或称为“快表”，在IBM系统中又取名为TLB（Translation Lookaside Buffer），用以存放当前访问的那些页表项。此时的地址变换过程是：在CPU给出有效地址后，由地址变换机构自动地将页号P送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中，可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如未找到对应的页表项，则还须再访问内存中的页表，把从页表项中读出的物理块号送地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，亦即重新修改快表。但如果联想寄存器已满，则OS必须找到一个老的且已被认为不再需要的页表项，将其换出。图5-12示出了具有快表的地址变换机构。由于成本的关系，快表不可能做得很大。

图5-12 具有快表的地址变换机构

5.3.2 分页存储管理的分配与回收

分页存储管理把内存的可分配区域按页面大小分成若干块，内存空间按块为单位进行分配。可用一张内存分配表来记录已分配的块和尚未分配的块以及当前剩余的空闲块数。由于块的大小是固定的，可用一张“位示图”来构成主存分配表。例如，假设内存的可分配区域被分成256块，则可用字长为32位的8个字的位示图来构成内存分配表。位示图中的每一位与一个物理块对应，用0／1分别表示对应块为空闲／已占有，另用一字节记录当前剩余的空闲块数，如图5-13所示。

图5-13 分页式存储器内存分配表

进行内存分配时，先查空闲块数能否满足作业要求。若不能满足，则作业不能装入。若能满足，则找出为“0”的一些位，置其占用标志“1”，从空闲块数中减去本次占用块数，按找到的位计算出对应的物理块号，作业可装到这些物理块中。根据为“0”的位所在的字号和位号，按如下公式可计算出对应的块号：

块号＝字号×字长＋位号(www.xing528.com)

当一个作业执行结束时，应收回作业所占的物理块。根据归还的块号计算出该块在位示图中对应的位置，将占用标志改为“0”，再把归还块数加到空闲块数中。假定归还块的块号为i，则在位示图中对应的位置为

字号＝［i／字长］ 位号＝i mod字长

其中，［ ］表示取i被字长除后的整数部分，而mod表示取其余数部分。

5.3.3 两级和多级页表

现代大多数计算机系统都支持非常大的逻辑地址空间（232～264）。在这样的环境下，页表变得非常大，要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4 KB即212 B，则在每个进程页表中的页表项可达1 M之多。又因为每个页表项占用一个字节，故每个进程仅其页表就要占用1 MB的内存空间，而且还要求是连续的。显然这是不现实的，我们可以采用下述两个方法来解决这一问题：

（1）采用离散分配方式来解决难以找到一块连续的大内存空间的问题。

（2）只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。

1.两级页表（two-level page table）

对于要求连续的内存空间来存放页表的问题，可利用将页表进行分页并离散地将各个页面分别存放在不同的物理块中的办法来加以解决，同样也要为离散分配的页表再建立一张页表，称为外层页表（outer page table），在每个页表项中记录页表页面的物理块号。下面仍以前面的32位逻辑地址空间为例来说明。当页面大小为4 KB时（12位），若采用一级页表结构，应具有20位的页号，即页表项应有1 M个；在采用两级页表结构时，再对页表进行分页，使每页中包含210（即1 024）个页表项，最多允许有210个页表分页；或者说，外层页表中的外层页内地址P2为10位，外层页号P1也为10位，如图5-14所示。

图5-14 两级页表结构

图5-15所示为两级页表结构图，可以看出，在页表的每个表项中存放的是进程的某页在内存中的物理块号，如第0页存放在1号物理块中，第1页存放在4号物理块中。而在外层页表的每个页表项中，所存放的是某页表分页的首址，如第0页页表是存放在第1 011号物理块中。可以利用外层页表和页表这两级页表，来实现从进程的逻辑地址到内存中物理地址间的变换。

为方便实现地址变换，在地址变换机构中同样需要增设一个外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号，作为外层页表的索引，从中找到指定页表分页的始址，再利用P2作为指定页表分页的索引，找到指定的页表项，其中即含有该页在内存的物理块号，用该块号和页内地址d即可构成访问的内存物理地址。图5-16表示了两级页表时的地址变换机构。

图5-15 两级页表结构

图5-16 具有两级页表的地址变换机构

对页表离散分配，虽然解决了对大页表不需大片存储空间的问题，但并未解决用较少的内存空间去存放大页表的问题。换言之，只用离散分配空间的办法并未减少页表所占用的内存空间。解决方法只是把当前需要的一批页表项调入内存，以后再根据需要陆续调入。在采用两级页表结构的情况下，对于正在运行的进程，必须将其外层页表调入内存，而对页表则只需调入一页或几页。为了表征某页的页表是否已经调入内存，还应在外层页表项中增设一个状态位S，其值若为0，表示该页表分页尚未调入内存；否则说明其分页已在内存中。进程运行时，地址变换机构根据逻辑地址中的P1，查找外层页表；若所找到的页表项中的状态位为0，则产生一中断信号，请求OS将该页表分页调入内存。关于请求调页的详细情况，将在后文虚拟存储器中介绍。

2.多级页表

对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，采用两级页表是否仍可适用？假设页面大小仍采用4 KB即212 B，那么还剩下52位，假定仍按物理块的大小（212位）来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4 096 G个页表项，要占用16 384 GB的连续内存空间。这样的结果显然是不能令人接受的，因此必须采用多级页表，将外层页表再进行分页，也就是将各分页离散地装入到不相邻的物理块中，再利用第2级的外层页表来映射它们之间的关系。

对于64位的计算机，如果要求它能支持264 B（＝1 844 744 TB）规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。故在近两年推出的64位OS中，把可直接寻址的存储器空间减少为45位长度（即245）左右，这样便可利用三级页表结构来实现分页存储管理。

5.3.4 分页存储管理的页面共享和保护

分页存储管理有利于实现多个作业共享程序和数据。在多道程序设计系统中，编译程序、编辑程序、解释程序、公共子程序、公共数据等都是可共享的。这些共享的信息在内存中只要保留一个副本。各作业共享这些信息时可使它们各自的页表中有关表目指向共享信息所在的主存块。图5-17是页面共享的示意图。具体实现时涉及与用户程序衔接的一些细节问题，有一定难度，本课程不做阐述。

页面的共享可节省内存空间，但实现信息共享必须解决共享信息的保护问题。通常的办法是在页表中增加一些标志，指出该页的信息可读／写或只读或可执行等。如图5-17中规定了共享程序只可执行，共享数据只可读。处理器在执行指令时要进行核对，欲想向只读块写入信息就停止执行指令并产生中断。

图5-17 页的共享示意图