|
|
|
|
|
分区存储管理的一个特点是连续性，每个程序都分得一片连续的内存区域。这种连续性将导致碎片问题，包括固定分区中的内碎片和可变分区中的外碎片。为了解决这些问题，人们又提出了页式存储管理方案。它的基本出发点是打破存储分配的连续性，使一个程序的逻辑地址空间可以分布在若干个离散的内存块上，从而达到充分利用内存，提高内存利用率的目的。
|
|
|
|
页式存储管理的基本思路是：一方面，把物理内存划分为许多个固定大小的内存块，称为物理页面（physical page），或页框（page frame）。另一方面，把逻辑地址空间也划分为大小相同的块，称为逻辑页面（logical page），或简称为页面（page）。页面的大小要求是2n，一般在512B到8KB之间。当一个用户程序被装入内存时，不是以整个程序为单位，把它存放在一整块连续的区域，而是以页面为单位来进行分配。对于一个大小为N个页面的程序，需要有N个空闲的物理页面把它装进来，当然，这些物理页面不一定是连续的。
|
|
|
|
下图是一个具体的例子。各个任务的逻辑地址空间和内存的物理地址空间被划分为1KB大小的页面。任务1有两个页面，任务2有三个页面，任务3有一个页面。当这三个任务被装入内存后，它们在内存空间的分布可能是：任务1的两个页面分别存放在第5和第6个物理页面中，它们碰巧被放在了一起。任务2的三个页面分别存放在第2、第4和第7个物理页面中。也就是说，虽然它们在逻辑地址空间是三个连续的页面，但在物理地址空间却被分散在内存的不同位置。最后，任务3的这个页面被存放在第8个物理页面中。
|
|
|
|
|
|
|
|
在实现页式存储管理的时候，需要解决以下的几个问题：
|
|
|
|
|
|
.内存的分配与回收：当一个任务到来时，如何给它分配内存空间？当一个任务运行结束后，如何回收它所占用的内存空间？
|
|
|
|
.地址映射：当一个任务被加载到内存后，可能被分散地存放在若干个不连续的物理页面当中。在这种情形下，如何把程序中使用的逻辑地址转换为内存访问时的物理地址，以确保它能正确地运行。
|
|
|
|
|
|
|
|
.页表：页表给出了任务的逻辑页面号与内存中的物理页面号之间的对应关系。
|
|
|
|
.物理页面表：用来描述内存空间中各个物理页面的使用分配状况。在具体实现上，可以采用位示图或空闲页面链表等方法。
|
|
|
|
下图是页表的一个例子。在任务的逻辑地址空间当中，总共有4个页面，即页面0、页面1、页面2和页面3。页表描述的是逻辑页面号与物理页面号之间的对应关系，即每一个逻辑页面存放在哪一个物理页面中。页表的下标是逻辑页面号，从0到3。相应的页表项存放的就是该逻辑页面所对应的物理页面号。在本例中，任务的4个逻辑页面分别存放在第1、第4、第3和第7个物理页面中。
|
|
|
|
|
|
|
|
|
|
当一个任务到来时，需要给它分配相应的内存空间，即将其每一个逻辑页面都装入到内存当中。显然，内存的分配与回收算法与物理页面表的实现方法是密切相关的。以位示图为例，内存的分配过程是这样的：
|
|
|
|
（1）对于一个新来的任务，计算它所需要的页面数N。然后查看位示图，看是否还有N个空闲的物理页面。
|
|
|
|
（2）如果有足够的空闲物理页面，就去申请一个页表，其长度为N，并把页表的起始地址填入到该任务的任务控制块TCB当中。
|
|
|
|
（3）分配N个空闲的物理页面，把它们的编号填入到页表中。这样，就建立了逻辑页面与物理页面之间的对应关系。
|
|
|
|
（4）修改位示图，对刚刚被占用的那些物理页面进行标记。
|
|
|
|
当一个任务运行结束，释放了它所占用的内存空间后，需要对这些物理页面进行回收，并对位示图的内容进行相应的修改。
|
|
|
|
|
|
如前所述，当一个任务被加载到内存后，它的各个连续的逻辑页面，被分散地存放在若干个不连续的物理页面当中。在这种情形下，为了保证程序能够正确地运行，需要把程序中使用的逻辑地址转换为内存访问时的物理地址，也就是地址映射。
|
|
|
|
那么如何将一个逻辑地址映射为相应的物理地址呢？在页式存储管理当中，连续的逻辑地址空间被划分为一个个的逻辑页面，这些逻辑页面被装入到不同的物理页面当中。也就是说，系统是以页面为单位来进行处理的，而不是以一个个的字节为单位。因此，地址映射的基本思路是：
|
|
|
|
.逻辑地址分析：对于给定的一个逻辑地址，找到它所在的逻辑页面，以及它在页面内的偏移地址；
|
|
|
|
.页表查找：根据逻辑页面号，从页表中找到它所对应的物理页面号；
|
|
|
|
.物理地址合成：根据物理页面号及页内偏移地址，确定最终的物理地址。
|
|
|
|
|
|
由于页面的大小一般都是2的整数次幂，因此，人们可以很方便地进行逻辑地址的分析。具体来说，对于给定的一个逻辑地址，可以直接把它的高位部分作为逻辑页面号，把它的低位部分作为页内偏移地址。例如，假设页面的大小是4KB，即212，逻辑地址为32位。那么在一个逻辑地址当中，最低的12位就是页内偏移地址，而剩下的20位就是逻辑页面号。
|
|
|
|
下图是逻辑地址分析的一个例子，在这个例子中，逻辑地址用十六进制形式表示。假设页面的大小为1KB，逻辑地址为0x3BAD。在这种情形下，首先把这个十六进制的地址展开为二进制的形式。然后，由于页面的大小为1KB，即2的10次方，所以这个逻辑地址的最低10位，就表示页内偏移地址，而剩下的最高6位，就表示逻辑页面号。因此，该地址的逻辑页面号是0x0E，页内偏移地址是0x03AD。
|
|
|
|
|
|
|
|
如果逻辑地址不是用十六进制，而是用十进制的形式来表示，那么有两种做法：一是先把它转换为十六进制的形式，然后重复刚才的步骤。二是采用如下的计算方法：
|
|
|
|
|
|
|
|
用页面大小去除逻辑地址，得到的商就是逻辑页面号；得到的余数就是页内偏移地址。例如，假设页面的大小为2KB，现在要计算逻辑地址7145的逻辑页面号和页内偏移地址。用2048去除7145，得到的商是3，余数是1001。所以这个逻辑地址的逻辑页面号是3，页内偏移地址是1001。实际上，这个算法和刚才的十六进制的方法是完全等价的。从二进制运算的角度来看，一个是右移操作，一个是除法操作。把一个整数右移N位等价于把它除以2N。
|
|
|
|
|
|
对于给定的一个逻辑地址，如果知道其逻辑页面号，就可以去查找页表，从中找到相应的物理页面号。
|
|
|
|
在具体实现上，页表通常是保存在内核的地址空间中，因为它是操作系统的一个数据结构。另外，为了能够访问页表的内容，在硬件上要增加一对寄存器。一个是页表基地址寄存器，用来指向页表的起始地址；另一个是页表长度寄存器，用来指示页表的大小，即对于当前任务，它总共包含有多少个页面。操作系统在进行任务切换的时候，会去更新这两个寄存器当中的内容。
|
|
|
|
|
|
对于给定的一个逻辑地址，如果已经知道了它所对应的物理页面号和页内偏移地址，可以采用简单的叠加算法，计算出最终的物理地址。假设物理页面号为f，页内偏移地址为offset，每个页面的大小为2n，那么相应的物理地址为：f×2n+offset。
|
|
|
|
下图是页式存储管理当中的地址映射机制，也是以上各个步骤的一个综合。假设在程序的运行过程中，需要去访问某个内存单元，因此就给出了这个内存单元的逻辑地址。如前所述，这个逻辑地址由两部分组成，一是逻辑页面号，二是页内偏移地址。这个分析工作是由硬件自动来完成的，对用户是透明的。在页表基地址寄存器当中，存放的是当前任务的页表首地址。将这个首地址与逻辑页面号相加，就找到相应的页表项。里面存放的是这个逻辑页面所对应的物理页面号。将这个物理页面号取出来，与页内偏移地址进行组合，从而得到最终的物理地址。然后就可以用这个物理地址去访问内存。
|
|
|
|
|
|
|
|
现有的这种地址映射方案，虽然能够实现从逻辑地址到物理地址的转换，但它有一个很大的问题。当程序运行时需要去访问某个内存单元，例如，去读写内存当中的一个数据，或是去内存取一条指令，需要访问2次内存。第一次是去访问页表，取出物理页面号；第二次才是真正去访问数据或指令。也就是说，内存的访问效率只有50%。这样，就会降低获取数据的存取速度，进而影响到整个系统的使用效率。为了解决这个问题，人们又引入了快表的概念。它的基本思路来源于对程序运行过程的一个观察结果。对于绝大多数的程序，它们在运行时倾向于集中地访问一小部分的页面。因此，对于它们的页表来说，在一定时间内，只有一小部分的页表项会被经常地访问，而其他的页表项则很少使用。根据这个观察结果，人们在MMU中增加了一种特殊的快速查找硬件：TLB（Translation Lookaside Buffer），或者叫关联存储器，用来存放那些最常用的页表项。这种硬件设备能够把逻辑页面号直接映射为相应的物理页面号，不需要再去访问内存当中的页表，这样就缩短了页表的查找时间。
|
|
|
|
在TLB方式下，地址映射的过程略有不同。当一个逻辑地址到来时，它首先会到TLB当中去查找，看这个逻辑页面号所在的页表项是否包含在TLB当中，这个查找的速度是非常快的，因为它是以并行的方式进行。如果能够找到的话，就直接从TLB中把相应的物理页面号取出来，与页内偏移地址拼接成最终的物理地址。如果在TLB中没有找到该逻辑页面，那只能采用通常的地址映射方法，去访问内存当中的页表。接下来，硬件还会在TLB当中寻找一个空闲单元，如果没有空闲单元，就把某一个页表项驱逐出来，然后把刚刚访问过的这个页表项添加到TLB当中。这样，如果下次再来访问这个页面，就可以在TLB中找到它。
|
|
|
|
|
|
（1）没有外碎片，而且内碎片的大小不会超过页面的大小。这是因为系统是以页面来作为内存分配的基本单位，每一个页面都能够用上，不会浪费。只是在任务的某一些页面当中，可能没有装满，里面有一些内碎片。
|
|
|
|
（2）程序不必连续存放，它可以分散地存放在内存的不同位置，从而提高了内存利用率。
|
|
|
|
|
|
|
|
（1）程序必须全部装入内存，才能够运行。如果一个程序的规模大于当前的空闲空间的总和，那么它就无法运行。
|
|
|
|
（2）操作系统必须为每一个任务都维护一张页表，开销比较大。简单的页表结构已经不能满足要求，必须设计出更为复杂的结构，如多级页表结构、哈希页表结构、反置页表等。
|
|
|
