第三章unix的存储.ppt

《第三章unix的存储.ppt》由会员分享，可在线阅读，更多相关《第三章unix的存储.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 UNIX的存储管的存储管理理 3.1 UNIX存储管理简介 UNIX将内存划分为固定尺寸的片或页面。页面的大小均为2的整次幂，通常为4KB。UNIX采用了虚存系统，进程空间中连续的页在物理内存中不必是连续的。内存管理子系统维护进程的逻辑（虚）页与实际的物理内存之间的映射。当请求一个连续的内存块时，内存管理子系统可以通过分配若干物理上不连续的页面来满足这个请求。虚存系统大大简化了页面分配的工作。内核为空闲页面维护一个键表结构。当进程需要页面时，内核从空闲键表中去掉足够的页面，当释放页面时，内核再将它们键入键表结构中。页的实际物理位置是无关紧要的。页面级分配器有两个主要的客户（下图）

2、。一个是虚存系统的分页系统，它为用户进程分配页面。在许多UNIX系统中，分页系统还为磁盘缓冲捉供页面。另一个客户是内核内存分配器，它为不同的内核子系统提供各种尺寸的内存诀，遁常这些内存块仅使用很短的一段时间。物理内存页面级分配器核心内存分配器分页系统网络缓冲器Proc结构节点、文件描述符 用户进程块缓冲 图3.1 内核中的内存分配 在各种UNIX系统中，大多数分配请求所要求的内存大小都远小于一个页面的大小，很明显不能用页面级分配器来实现这些功能。我们需要一套独立的机制来实现更细粒度上的内存分配。一个简单解决方案就是避免动态地进行内存分配。早期的实现的UNIX为i节点、proc结构等数据结构分配

3、固定大小的内存。当系统需要临时保存路径名或网络报文时，系统借用盘块缓冲系统中的缓冲区。此外，针对特殊情况，还设计了一些ad hoc的分配机制，如终驱动程序中的clists结构。这种策略有许多弊端。首先，它极不灵活。各种表或缓冲区的大小在系统启动或编译时就被固定下来，不能根据系统的请求而调整。系统开放人员根据典型系统的工作负荷来选择表格的缺省大小。尽管系统管理人员通常可以调节这些尺寸，但这样做缺少指导依据。如果某些表过于小，这些表就很可能溢出，并使整个系统在没有任何征兆的情况下崩渍。如果使所有的表都尽可能地大，则会造成内存的浪费。留给应用程序的内存相对减少。这也会造成系统的整体性能下降。3.2

4、资源映射图分配器 资源映射图是一系列记录空闲内存的偶对的集合（见下图）。一开始，资源映射图只有一个项，它的base就是内存池的基址，而size就是内存池的大小（见下图(b)）。随着客户不断地分配和释放内存，内存池被逐渐打碎。内核为每一段连续的空闲内存分配一项。资源映射图按基址顺序组织，这样就可以很容易地连接两个邻接的空闲内存区。1，1024(a)初识配置576，448256，128576，448128，256832，32544，128288，64128，32(b)在分配256，320，释放256，128后（c)在释放128，128之后(d)在若干操作后 利用资源映射图，内核可以用如下三种策略之

5、一来满足分配请求：最先适应分配。从第一个可以满足请求的空闲块中分配内存。这是最快的算法，但不利于减少碎片。最佳适应匹配。选择可满足请求的空闲块中最小的一个分配内存。该策略的缺点是可能会造成若干非常小的、不可用的空闲块。最差适应匹配。如果没有正合适的空闲诀，选择可瞒足请求的空闲块中最大的一个。这看上去似乎不合常理，但它是处于这样的考虑：保证分配后剩下的空间足够大，以便满足后续的请求。没有一种算法可以很好地匹配所有的使用模式。UNIX使用最先适应匹配第略。下图给出了一个管理1024字节大小内存的资源映射图。它支持两个操作：offset_t rmalloc(size);/*return offset

6、 of allocation region */void rmfree(base,size);资源映射图是一种简单的分配器，它主要有如下优点：算法易于实现。资源映射图并非仅能用于内存分配。它能管理任何有序的，需要分配和释放连续块 的对象（如页表项，以及以后将讲述的信号灯等）。它可精确地分配请求所需的内存，不浪费空间。通常是将请求取整到4或8的倍数。并不强制客户精确地释放分配的内存。分配器完成邻接空闲块的合并，有利于内存的再利用。然而，资源映射图分配器同时存在一些显著的缺点：在分配器运行一段时间后，资源映射图碎片化非常严重，生成许多很小的空闲块。这将使利用率显著下降。随着分片增加，资源图的大小也

7、在增加，为每一片内存区建立一个表项。如果资源 图预配置成固定数目的表项，它就有可能溢出，分配器就不能再记录某些空闲内存 区了。如果资源图动态的增长，它需要另外一个分配器来为自己分配内存。这成了递归问 题了，我们将在后面给出一个解决方案。为了合并邻接的空闲块，分配器必须按基址升序排列它们们。排序的代价很高。在 某些情况下，如资源映射图采用固定尺寸的数组实现时，情况会更糟。既便资源映 射图动态分配并组织成键表，排序仍然是十分耗时的。分配器为找到足够大的空闲诀必须对资源映射图进行线性搜素。随着碎片的增加,极端情况下搜索耗时很大,变得非常慢。尽管可以将内存池尾部的空闲页面返回给分页系统，算法并没有这样

8、设计。资源映射图算法的性能很差。这一点使它不适合成为一个通用内核内存分配器。但它还是适用于某些内核子系统的。System V的进程间通信就使用资源映射图算法管理信号量集合和消息的数据区。4.3BSD的虚存子系统也使用该算法管理映射用户空间的页表。在某些情形下，映射图的管理可以得到改进。遁常可以将映射图的每一项存放在空闲块的前几个字节中。这种方法不需要额外的内存，也不需要动态分配映射图。只需一个全局指向第一个空闲块的指针，每一个空闲块保存它自身的大小和下一个空闲块的指针。这种方法要求空闲块至少有两个字的大小（一个放尺寸，一个存指针）。一般通过强制分配和释放就可以满足这一点。3.3 对换 对换算法

9、的三个部分：对换设备上的空间管理，将进程换出内存，将进程换入内存 3.3.1 对换空间的分配 对换设备是在一个磁盘的可配置段中的一个块设备。内核在对换设备上是以一组连续的磁盘块为单位来分配空间的。算法：malloc 输入：（1）映射地址；（2）所请求的资源的数目 输出：如果成功返回则为地址，否则返回结果0 for(每个映像图表项）if(当前映射图的表项能满足请求的单位数)if(请求数量=该表项中的单位数)从映射图中删除该表项；else 修改该表项的起始地址及单位数目；return(该表项原来的地址）return(0)释放资源时，注意处理以下三种情况：(1)被释放的资源完全填满了映射图中的一个空

10、洞；它们的地址在映射图中刚刚能连接紧接其后和其前的那些表项；(2)被释放的资源部分填满了映射图中的一个空洞；它们的地址在映射图中刚刚能连接紧接其后或其前的那些表项；(3)被释放的资源部分地填充了映射图中的一个空洞；但其地址不连接映射图的任何表项；传统的UNIX系统只是用一个对换设备，但System V的最新版允许使用多个对换设备。内核采用循环算法来选用对换设备，以保证对换设备上有足够大的连续存储空间。管理人员可以动态地创建和取消对换设备。3.3.2 进程的换出 如果内核需要内存空间，它就换出进程。以下事件可引起进程的换出：（1）系统调用fork必须为子进程分配空间；（2）系统调用 brk扩大一

11、个进程的大小；（3）一个进程由于其栈的自然增长而变大；（4）为了运行以前被换出、而现在又应被换人的进程。其中，由fork引起的情况最为突出，它是唯一不能放弃被进程先前占据的内存映象空间的情况。当内核决定了某一进程应从主存中换出时，它使该进程中的每个区的引用数减回，并把那些引用数减为0的区换出。内核分配对换设备空间，并将该进程锁在内存中（对应于上述事件1、2和3），以防止在当前的对换操作过程中，对换进程将它对换出来。内核将区的对换地址保存在区表表项中。内核绕过高速缓冲，直接在对换设备和用户地址空间之间对换数据，并在一次IO操作中对换尽可能多的数据。如果硬件不能一次传送多个页面的话，内核的软件必须

12、循环地一次传送一页内存。因此，数据传送的精确速率及传送机制，除其他因素外，主要依赖于磁盘控制器的能力和存储管理的实现。例如，如果按页面来组织内存，那么，要被换出的数据在物理存储器上就可能是不连续的。内核必须收集被换出的数据的页面地址，磁盘驱动程序也可能要使用这些页面地址来启动IO。对换进程在换出剩下的数据之前要等待每一个IO操作的完成。内核没有将一进程的整个虚地址空间全部写到对换设备上去。仅将已分配给进程的物理存储拷贝到所分配的对换设备空间上去，而忽略那些尚未分配的虚地址。当内核将该进程换回到内存时，它知道该进程的虚地址映射，从而能将该进程重新分配到正确的虚地址上。内核通过把数据读到先前建立的

13、与虚地址位置一致的物理存储器的位置去，消除了一次额外的从数据缓冲到物理存储器的拷贝。下图给出了一个将一个进程的内存映象映射到对换设备上的例子 0 278K1K 432K空64K 573K65K 647K66K 595K空128K 401K空 虚地址的布局 虚地址 物理地址 正文 数据 栈进程空间到对换设备的映射684690下图给出了一个进程换入内存的例子 0 401K1K 370K空64K 788K65K 492K66K 647K空128K 955K空 虚地址的布局 虚地址 物理地址 正文 数据 栈进程空间到对换设备的映射690684 从理论上说，进程的所有存储空间，包括它的U区和核心栈，都可

14、以被换出，尽管在进行敏感操作时，内核可能暂时地将一个区锁在内存。然而，在实际上，如果U区含有进程地址转换表，则内核在实现上就不能换出U区。实现上还要决定是否一个进程能将其自身换出，还是必须由另一个进程来将其换出。1系统调用 fork的对换 在系统调用fork的描述中，假定了父进程找到了足够的内存空间以创建子进程的上下文。否则，内核将换出该进程但并不释放被（父）进程的内存映象所占据的内存。当换出完成后，子进程在对换设备上，父进程将子进程置为就绪状态，然后返回用户态。由于子进程处于就绪状态，所以对换进程总会将其换入内存。内核在内存中总会调度到它，这时子进程完成它的fork系统调用部分然后返回用户态

15、。2扩展对换 如果进程需要的内存比当前已分配给它的内存还多，不管这是由栈增长引起的还是由于调用系统调用 brk所引起的，内核都要进行一次进程的扩展对换 （expansion swap）。内核在对换设备上预定足够的空间以容纳进程的存储空间，其中包括新申请的空间。然后内核修改进程地址转换映射以适应新的虚存空间，但此时并不分配物理存储地址（由于没有可用的物理空间）。最后内核通过一次通常的对换操作将该进程换出，同时将对换设备上新分配的空间清零（见下图）。当以后内核将该进程换入时，将按新的（增加了尺寸的）地址转换映射图来分配物理地址。这样，当该进程恢复执行时就有了足够的空间。0 278K1K 432K空

16、64K 573K65K 647K66K 595K空128K 401K129K -空 虚地址的布局 虚地址 物理地址 正文 数据 栈为扩展对换修改内存映像图684690 3.3.3 进程的换入 进程0，即对换进程，是唯一的将进程从对换设备上换人内存的进程。在系统初始化结束时，对换进程进入一个无限循环，它的任务就是将进程换人或换出。它总是试图将进程从对换设备上换人内存；如果需要主存空间，就将进程换出内。如果对换进程没有事做（例如没有进程要换入）或不能做任何事情（例如没有进程可以被换出），它就睡眠。内核定期地唤醒对换进程。尽管对换进程具有高优先权，内核同调度其他进程一样调度对换进程运行，但对换进程仅

17、在核心态下运行。对换进程不调用系统调用，但使用内核内部函数来执行对换，这是所有核心进程的主要工作方式。当对换进程被唤醒后，它进行换入进程的工作，此时，它查找所有处在“就绪且换出”状态的进程，从中选取换出时间最长者，如果有足够的内存，就将进程换入。将进程换入的操作是换出操作的逆过程：分配物理存储，将进程从对换设备读入，然后释放对换空间。算法swapper*换人曾被换出的进程，腾出空间。输人：输出：loop：for（所有已被换出的就绪进程）选取被换出时间最长的进程；if（没有这样的进程）sleep（事件：必须换入进程）；goto loop；if（主存中有足够的空间存放该进程）换入该进程；goto

18、loop；for（所有已装入内存、非僵死而且没被锁在内存的进程）if（有一个睡眠进程）选取优先权值与驻留时间之和在数值上最高的进程；else *没有睡眠的进程。*选取驻留时间与nice值之和在数值上最高的进程；if（所选择的进程不在睡眠或不满足驻留时间的要求）sleep（事件：必须换入进程）；else 换出进程；goto loop;1 如果对换进程成功地换入了一个进程，它仍继续查找状态为“就绪且换出”的进程来换人并重复上述过程。最终会发生下列情形之一：对换设备上没有“就绪”的进程：这时，对换进程进入睡眠，直到一个对换设备上的进程被唤醒或内核换出一个“就绪”状态的进程。对换进程找到了应被换入的进

19、程，但系统没有足够的内存空间：此时，对换进程试图换出另一进程，如果成功则重新启动对换算法，查找需要换入2进程。如果对换进程必须换出一个进程，那么对换进程检查在内存的每一进程：僵死进程不用换出，因为僵死进程不占据任何物理存储；锁在内存中的进程（例如正在进行区操作）也不能换出。内核换出正在睡眠的进程而不是换出“就绪”进程。因为“就绪”进程很可能很快就被调度上。选取哪一个睡眠进程来换出取决于进程的优先权和它在内存驻留的时间。如果内存中没有正在睡眠的进程，那么选择哪个“就绪”进程来换出就取决于进程的nice值和它在内存中驻留的时间。一个就绪进程在被换出前必须至少在内存驻留了2秒，一个要被换入的进程必须

20、至少已被换出了2秒户如对换进程找不到可换出的进程，或者，要换人或要换出的进程在它们的环境里的驻留时间都不超过2秒，对换进程就睡眠于一个事件上。这一事件指出，对换进程要换入一个进程，但是找不到足够的内存来存放它。在这一状态下，时钟每秒唤醒一次对换进程。如果有任何进程要进人睡眠状态，内核也要唤醒对换进程，因为进入睡眠的进程可能比对换进程以前所查找的进程更应被换出。如果对换出了一个进程，或因不能换出一个进程而进人睡眠，它将从头执行对换算法，以换入可被换入进程。对换进程基于进程被换出的时间来选择要换入的进程。另一个换入标准是具有最高优先权的就绪进程，因为这样的进程应该得到较多的运行机会。在系统重负载的

21、情况下，这种策略可获得“略微”好一点的系统吞吐量。但是，选择换出进程以得到内存空间的算法有更为严重的缺陷。第一，对换进程根据进程的优先权、内存驻留时间及它的nice值换出一个进程。尽管对换进程换出一个进程仅仅是为了腾出空间以换入另一个进程，但换出一个进程可能并不能为要换入的进程提供足够的内存空间。举例来说，如果对换进程想要换入一个占1兆字节内存的进程而系统又没有空闲内存，这时换出一个仅占2K字节内存的进程是不解决问题的。一个替代的策略是，仅当一组进程能为换入进程提供足够的内存空间时，才换出这组进程。第二，如果对换进程因为不能为换入进程找到足够的内存空间而睡眠，它醒来时将重新寻找一个要换入的进程

22、，尽管先前它已经有了一个要换入的进程。因为与此同时可能有其他的进程被唤醒，而它们又比先前选中的进程更应被换入。对先前已选中的进程的一点安慰是，对换进程仍然试图将其换入。在一些实现的版本中，对换进程在选择下一个换入进程之前总是试图换出多个较小的进程来为一个要换入的大进程提供空间。第三，假若对换进程选中了一个“就绪”进程换出，但可能该进程自从被换入之后一直没有运行。这一抖动显然不是我们所希望的。最后，值得一提的是另一个危险。如果对换进程要换出一个进程，但在对换设备上又找不到空区，这时若下列四个条件满足时，系统就会产生死锁；在主存中的所有进程都进入睡眠；所有“就绪”进程都已被换出；在对换设备上没有空

23、间以容纳新的进程以及在内存中已无空间来存放要换入的进程。解决对换进程这一问题的希望在于请求调页算法。最近几年，请求调页算法已在UNIX系统上实现。3.3 请求分页 UNIX内核中的内存管理子系统负责完成内存和二级存储器之间的数据分布。它直接操作称为存储管理单元（MMU）的部件，该部件完成CPU与主存间的数据传输。一 UNIX系统内存管理的早期时代 早期的UNIX实现（版本7或更早）运行在PDP-11上，它有一个只有64KB地址空间的16位体系结构。这种限制造成各种用于用户程序和内核的软件覆盖技术的产生。这种方法通过覆盖那些程序暂时不再使用的地址空间来复用内存。例如，一旦系统被加载并运行后，系统

24、初始化代码就不再使用了，就可以把它释放掉，供程序的其他部分使用。这种覆盖技术需要应用程序开发人员的显式参与，他们必须清楚程序及运行它的机器的许多细节。早期UNIX的内存管理机制只有交换机制。进程被整个加载到一片连续物理内存中。物理内存只能同时容纳很少几个进程。它们分时运行，如果又有一个进程要运行，就必须对换出去一个现有的进程。该进程被复制到磁盘上预定义好的交换区中，每个进程在其创建时都在该区上分配一片交换空间，保证进程有足够交换空间可用。1978年，分页系统出现在UNIX系统中(VAX-1/780)。VAX-11/780有一个32位体系结构，4GB地址空间，提供分页硬件支持。3BSD是第一个支

25、持分页系统的UNIX版本。在20世纪80年代中期，所有的UNIX系统都使用分页作为主要的内存管理机制，而交换只起辅助作用。在分页系统中，内存和进程的地址空间都被分成固定大小的页。这些页面在需要时被换进或换出内存，内存的页通常称为页面。在任何时刻可以有若干个活动进程，而每个进程在物理内存中只有一部分页，每个进程都认为自已是系统中的唯一一个程序。程序的地址是虚拟的，由硬件划分为页号和页内偏移。硬件和操作系统一起将程序地址空间的虚页号转换为物理页面号，并访问相应的内存单元。如果所需的页面不在内存中，就必须将其换入内存。对于纯分页系统来说，直到页面需要（被访问时），才将其换人内存。大部分现代UNIX系

26、统都进行一定程度的预分页，即换入那些马上可能使用的页面。二 分 页 分页系统负责分配和管理全体进程的地址空间。它对物理资源的使用进行优化，这当然包括主存和二级存储设备，以最小的代价实现需要的功能。下面首先来看看所有的分页系统中共同关注的基本问题。1 功能要求 既然需要分页结构，我们就先来考虑一下它要有哪些功能。从管理的角度出发，我们发展出一组详细的功能需求：地址空间管理。在fork时内核为进程分配地址空间，在进程exit时释放它们。如果进程调用了exec系统调用，内核释放原来的地址空间，为新程序分配一个新的地址空间。地址空间上的其他主要操作包括：改变数据区、堆栈区的大小，增加新的可访问内存区（

27、如共享内存）。地址转换。对访问内存的每一条指令，MMU都要将进程产生的虚地址转换为主存的物理地址。页面是分页系统中内存分配，保护和地址转换的基本单位。一个虚地址首先转换为虚页号和页内偏移。然后虚页号再通过某种地址转换映射图转换为物理页号。如果访问的页面不在物理内存中（没有驻留），就会引起一个页面失效异常。内核的异常处理函数处理这个异常，将页面加载到内存中。内存保护。进程不应该以非授权方式访问或修改页面。内核保护它的数据和代码，以防用户进程修改它们，否则，用户程序就会偶然地（或恶意的）破坏了内核。出于安全性的考虑，内核也必须防止进程读取它的代码或数据。进程访问其他进程的页也是不允许的。进程的某些

28、地址空间对进程本身也应该是受保护的。例如，进程的正文区通常是写保护的，防止进程偶然破坏其正文区。内核通过低层的硬件机制实现系统的内存保护机制。当内核发现存在对非法地址访问时，就向那个进程发送一个段违例信号（SIGSEGV）。内存共享。UNIX进程的特点及其交互方式很自然地要求共享它们地址空间中的某一部分。例如，运行同一程序的所有进程共享程序的同一份正文区。进程也可显式地要求与协同进程共享一段内存。标准库的正文区也可以用同样的方式共享。这些都是高层次共享的例子，还有一些低级共享的例子。低级共享可以共享个别的页面。比如，fork后，父进程与子进程只要不修改数据区或堆浅区，它们就共享那些页面。监视系

29、统负荷。通常情况下，分页系统可以应付活动进程的请求。然而，有时系统会进入超负荷状态。当这种情况发生时，进程得不到足够的内存来容纳它的活动页面，不能继续运行。分页系统的负荷依赖于活动进程的数目及其尺寸，以及内存访问模式。操作系统监视分页系统，发现上述情况后，采取相应措施。其地服务。内存管理系统还支持其他一些功能，如文件映射，动态链接库，以及执行存储在远程节点上的程序。内存管理结构对整个系统性能有很大的影响，设计时尤为注重性能和可扩缩性。如果要求系统可以运行于不同类型的机器上，可移植性也是很重要的。最后，内存子系统应该对用户是透明的，用户在写代码时无需考虑低层的内存结构。三三 虚拟地址空间虚拟地址

30、空间 进程的地址空间包括程序访同或引用的全部（虚）内存单元。任何时刻，地址空间连同进程的寄存器上下文就是进程的当前状态。进程调用exec启动新程序后，内核依据新程序的映像建立地址空间。分页结构中将地址空间分成许多固定尺寸的页面，程序的这些页面包含如下几种类塑的信息：正文 初始化数据 未初始化数据 修改的数据 栈 堆 共享内存 共享库 这些页面类型有不同的保护权限，初始化方法，以及进程间的共享方式。正文页通常是只读的，而数据，堆和残页面是可读可写的。共享内存页面上的保护权限通常在其被创建时设置。四四 页面初始访问页面初始访问 即使没有程序页面在内存中，进程照样可以开始运行一个程序。随着它不断访问

31、那些不在内存中的页面，系统产生页面失效，内核为其分配空闲页面，用含适的数据进行初始化。首次对页面访问的初始化方法不同于之后对页面访问的初始化方法。这里我们介绍首次访问。正文和初始化数据页面直接从执行文件中读取。未初始化数据页面置为0，这样那些全局未初始化变量的初值自动置为0。共享库页面从库文件中读取，u区和内核栈在进程创建时通过复制父进程页面建立。如果某个进程执行的程序已由另一个已存在的进程执行或刚刚执行完。此时，内存或交换区等高速设备中尚有该程序的全部或部分页面。在这种情况下，系统可以避免从执行文件中再次访问页面。五五 交换区交换区 所有活动进程的全部尺寸一般远大于物理内存，因此内存只能为每

32、一个进程保存某些页面。如果进程需要的页面不在内存内核就必顷挪用另外一个页面，丢弃原来的内容。理想情况下，我们应只替换那些不再需要的页面，比如属于终止进程的页面。通常这是不可能的，内核只能借用一个未来可能使用的页面。因此，内核必须将该页面的内容保存在二级存储设备上。UNIX使用交换区保存临时页面，它一般由一个或多个磁盘分区组成。当系统初始配置时，保留一定量的未格式化磁盘用于交换区。这些空间不能由文件系统使用。下图说明了一个页面是如何在物理内存和不同的二级存储设备间移动的。如果某个保存在交换区的页面再次被访同，内核的页面失效处理函数就从交换区中读出它们。为了这样做，必须维护某种形式的交换区映射图，

33、记录所有被换出的页面在交换区上的位置。如果页面又需要被换出内存，仅当其内容与己保存的副本不同时才迎行复制。仅当页面为已修改的时才保存它，也即页面自上次从交换区读出后是否被修改过。如果系统的硬件支持页表项上的己修改位，实现这一功能是根容易的。但如果没有硬件支持，内核就必须通过其他方式获取信息。1正文页不必保存到交换区中，它们可以从执行文件中获得。某些实现出于性能考虑也同样换出正文页。交换区映射图一般都设计非常高效的数据结构，内核只需简单地索引一张驻留在内存中的表就可以查到页面在交换区上的位置。如果是定位执行文件的页面，内核就必页通过文件系统，文件系统访问i节点可能还要检查某些间接块。这是比较慢的

34、操作，特别是当读取间接块时还需要额外的磁盘访问。然而，将正文页换出也需要额外的磁盘I/O，这可能抵消了快速的换入操作带来的好处。大多数现代UNIX不换出正文页，直接从文件读回页面。未初始化数据页 首次访问时分配 已修改页面在 释放前保存 正文和初和始化数据 磁盘上的可执行文件 主存 交换区 堆栈页面 发生在已换出 页面的后继失 首次访问时分配 效 3.4 分页管理的硬件要求分页管理的硬件要求 内存管理子系统依赖低层的硬件完成若干任务。这些任务是由一个位于CPU和主存之间的硬件部件完成的，该部件称为内存管理单元（MMU）。MMU的结构对内核中的内存管理子系统的设计有着重大的影响。一一 MMU M

35、MU的工作原理的工作原理 MMU的主要任务是完成虚地址转换。大多数系统使用页表，快表或两者兼备实现地址转换映射图。一般系统的MMU工作原理大致如下：(1)内核地址空间对应一个页表，每个进程的用户地址空间对应一个或多个页表。页表是一个数组，每一项对应进程中的一个虚页，页表项（PTE）的素引对应其描述的虚页。例如，正文区页表中的PTE 3，对应正文区中的虚页3。(2)页表项大小通常为32位，分为若干域。这些域包括物理页面号，保护权限，有效位，修改位，以及可选的引用位。页表项的格式由硬件预先定义。除此之外，页表是位于内存中的非常简单的数据结构。MMU仅使用那些加载到硬件页表寄存器中的活动表。通常，在

36、单处理机中，有两个活动页表：个是内核的，另一个是当前运行的进程的。（3）MMU将虚地址分为虚页号和页内偏移，然后在页表中定位该虚页项，抽取出物理页面号，再加上页内偏移计算出物理地址。地址转换可能因以下三个原因失败：边界错误。地址不在进程有效地址范围内，没有虚页对应的页表项。有效性错误。页表项被标记为无效。这通常是说页面不在内存中，有几种情况，即使页面是有效的且在内存中，有效位同样会被置无效。保护错误。页面不允许某些极限的访问（如对只读页面写，用户过程访问内核页等）。在以上情况下，MMU发出一个异常，并将控制权较交给内核的处理函数，这个异常称为页面失效。失效地址以及失效类型（有效性失效或保护失效

37、）一同传递给失效处理函数。处理函数完成页面的加载或利用信号（SIGSEGV）通知进程。如果成功地处理了失效，进程（当它再次运行时）必须重新启动引起失效的指令。这需要硬件在失效前保存足以启动失效指令的正确信息。（4）每次页面被写入硬件设置其PTE上的修改位，如果操作系统发现该位被置，在其重新利用页面时要将该页面保存在存储设备上。如果硬件支持PTE上的引用位，可以在每次访问页面时设置该位。这就可以使操作系统监视驻留页面的使用情况，重新利用那些看起来不再使用的页面。(5)如果进程有一个非常大的地址空间，它的页表也会非常大。比如，如果一个进程的地址空间是2GB，页面尺寸是lKB，则页表有200万项，总

38、共需要8Mb的内存保存页表。在内存 中保存这么大的页表是不可能的。而且，大部分地址空间可能根本不使用（般的进程地址空间只包括正文、数据、栈等几个区，分别在地址空间不同的地方。该问题的解决可以页表本身被分页的方法。即用一个高级页表来映射低级页表。使用这样一种多级页表层 次，只需为那些映射有效地址的低级页表分配页面。(6)页表将MMU与内核联系在一起，两者都可以访问使用和修改PTE。此外，硬件还有一 组指向页表基址的寄存器。MMU负责使用PTE转换虚地址，检查进程中的有效位和保护权限，设置引用位和修改位等等，而内核则要建立页表，在PTE中填写正确的数据，设置指向页表的MMU寄存器等。这些寄存器通常

39、在上下文切换时需要重新设置。二二 MMU MMU缓存缓存 仅用页面还不能提供有效的地址转换。每条指令都需要访问若干次内存：一个用于转换程序计数器指定的虚地址，一个是读取指令。与此相似，还有每个内存操作数的两次访同。如果页表本身是分页的或是多级的，访问内存的次数会更多。由于每次内存访问至少需一个CPU周期，如此多的内存访问将使内存带宽趋于饱和，指令的执行时间增加到不可接受的地步。这个问题有两个解决方案，第一个是增加高速缓存。许多机器都有分离的数据缓存和指令缓存，或者仅使用一个统一的缓存。从缓存中读取数据比从内存要快。许多机器是通过物理地址访问缓存。它完全由硬件管理，对软件是透明的。缓存访问发生在

40、地址转换之后，所以这种方法的收效甚微。第二种方法是使用快表（TLB）。TLB是一个关联缓存，保存最近使用的地址转换数据。快表项与页表项很相似，也包含地址转换信息和保护 权限等，可能还有一些行记用来标识该地址属于哪个进程。缓存是关联的，也就是说查找不是基于素引的，而是基于内容的：在快表项中同时查找虚页号。三三 lntel 80 x86 lntel 80 x86的的MMUMMU Intel 80 x86是基于System V的UNIX的主要平台之一，它有4GB的地址空间（32位地址），页面大小为4096字节，同时支持分段和分页机制。分页启动 是 每一个虚地址包括一个16位的段选择符和一个32位偏移

41、。分段层将虚地址转换为32位的线性地址，然后再由分页层转换为物理地址。可以通过清除CRO寄存器的最高 位关闭分页机制制，此时线性地址就是物理地址。段偏移段转换页转换物理地址页表否 进程地址空间可使用8192个段。每个段由一个段描述符定义，其中包括基址，尺寸，保护权限。每个进程有一个自己的局部描述符表（LDT），每一项对应一个段。还有一个全局范围的全局描述符表（GDT），其中包含内核正文区、数据区、堆栈区，外加一些特殊的段，如每个进程的LDT等。当转换一个虚地址时，MMU通过段段选择符从GDT或LDT中选择正确的段描述符，检查偏移是否在段的范围内，如上段基址得到线性地址。在x80上实现的UNIX

42、仅在内存保护，内核陷人，上下文切换等情况中使用段，它对用户进程隐藏段的存在，进程看到一个平坦的地址空间。为达到这个目的，每个内核建立的段都使用基址0，并且有足够大的尺寸，当然不包含高端的虚存，选部分（指虚存）用于内核正文和数据。正文区是只读的，而数据区则是可读写的，但两者都指向同一位置。每一个LDT还包括一些特殊的段一用于系疣调用项的调用门段，以及在上下文交换时保存寄存器上下文的任务状态段（TSS）。x80用二级页表。4KB的大小，意味着进程最多可以使用多达100多万个页面。3.5 3.5 请求分页的软件实现请求分页的软件实现 一一 请求调页管理的数据结构请求调页管理的数据结构 在UNIX系统

43、中，为实现请求调页，核心配置了四种数据结构：页表、磁盘块描述表、页面数据表和对换使用表。1页表 为了实现请求调页策略，UNIX System V将进程的每个区分为若干页，以将它们分配到不相邻的物理块中，为此每个区设置了一张页表。为了支持请求调页，每个页表项中需包含以下字段：物理块号：即页在内存中的物理块号。年龄：记录该页作为一个进程工作集中的一页有多长时间。访问位：指示该页最近是否被访问过。修改位：指示该页内容是否被修改过。有效位：指示该页内容是否有效。写时拷贝位：指示进程修改该页时，是否要为该页建立拷贝。保护位：指示此页允许的访问方式。2磁盘块描述表 在UNIX系统中，每个页表项对应一个磁盘

44、块描述项，其中记录了各页面的磁盘拷贝所在的磁盘块号。一个页面的内容或在一个对换设备的特定块中，或在一个可执行文件中。如果该页在一个可执行文件中，此时磁盘块描述项中的存储器类型为File，设备块号是该页在文件中的逻辑块号。如果该页面在对换设备上，则此时的存储器类型为Disk，对换设备号和块号则用于指示该页面的拷贝所驻留的逻辑对换设备和相应的盘块号。年 写时 修 访 有 保 页面（物理）地址 龄 拷贝 改 问 效 护 页表表项 类 型 对换设备 块 号 （对换、文件、清零、填入）磁盘块描述项 3页面数据表 每个页面数据表项描述内存中的一个物理页，每个表项包含：(1)页状态。指示该页的拷贝是在对换设

45、备上还是在可执行文件中。(2)内存引用计数。指出引用该页的进程数目。(3)逻辑设备。指出含有该页拷贝的逻辑设备和块号，它可以是对换设备，也可以是文件系统。(4)指向空闲页链表中下一个页面数据表项的指针和指向散列队列中下一个页面数据表项的指针。在系统初启时，核心将所有的页面数据表项链接为一个空闲页链表，形成空闲页缓冲池。为给一个区分配一个物理页，核心从空闲链表之首摘下一个空闲页表项，修改其对换设备号和块号后，将它放到相应的散列队列中。4对换使用表 对换设备上的每一页都占有对换使用表的一个表项，表项中含有一个引用计数，其数值表示有多少页表项指向该页。1页表项 磁盘块描述项 页 号794 对换设备1

46、 块号2743 引用数1 对换设备1块号2743页面数据表象794物理页794引用数1对换使用表项对换设备块2743请求分页的各数据结构之间的关系是意图 说明，一个进程的虚地址为1493K，由页表项可得知其物理页为794，其拷贝在对换设备1的第2743号盘块中。物理页794有一页面数据表项，该表项中同样指出，该页在对换设备1上的第2743号盘块中有一拷贝，其引用数为1。1区T引用数：2页表项虚地址 页 24K 967区P1引用数：2页表项虚地址 页 97K 613页面数：967引用数：1区C1引用数：2页表项虚地址 页 97K 613对换使用表项页面：613引用数：2调页系统中的fork 进程

47、P区表进程C区表调页系统中的系统调用exec索引节点磁盘块描述符逻辑块 841452790384索引节点块链表区四四 偷页进程偷页进程 在 UNIX系统的核心中，专门设置了一个偷页进程（核心进程），其主要任务有二：每隔一定时间增加内存中所有有效页的年龄；当有效页的年龄达到规定值后便将它换出。1增加有效页年龄增加有效页年龄 一个页可计数的最大年龄取决于它的硬件设施。若只设置了两位作为年龄域，其有效页的年龄只能取值0、l、2和3。当该页的年龄为0、1、2时，该页处于不可换出状态。而当其年龄达到3时，便可将它换出内存。每当内存中的空闲页面数低于某规定的低限时，核心便唤醒偷页进程，由偷页进程去检查内存

48、中的每一个活动的非上锁区，对所有有效页的年龄字段加1。对于那些年龄字段已增至3的页便不再加1，而是将它们换出。每当有进程访问了某个页面时，便将该页的年龄置0。下图显示了一个有效页的年龄变化情况。图中的数字说明，该页刚被进程访问过，因而它的年龄值为0。此后，该页又被偷页进程检查了两次，致使其年龄增至2。由于该页又被进程访问，于是其年龄又降为0。后来，它又被偷页进程检查了三次，其年龄又增至3，这样，当偷页进程再次检查时便将其换出。页在内存123n页不在内存可以换出换出换入页面计龄的状态图 页被引用在内存 0 1 2 0 1 0 1 2 3不在内存 页被访问页被访问页被换出页状态 时间某个页面计龄的

49、例子 2 2对换出页的几种处理方法对换出页的几种处理方法 当偷页进程从内存中的有效页中找到可被换出的页后，可采取下面三种方法对它们进行处理：(1)若在对换设备上己有被换出页的拷贝，且被换出页的内容未被修改，则此时核心不必将该页重写回对换设备上，而只需将该页的页表项的有效位清零，并将页面数据表项中的引用数减1，最后将该页表项放入空闲页链表中。(2)若在对换设备上没有被换出页的拷贝，则应将该页写到对换设备上。但为了提高对换效率，偷页进程并不是有一个页面换出一个页面，而是先将所有要换出的页链接到一个换出页链表上，然后再查看是否还有其他有效页要换出。当换出页面链上的页数达到某一规定值时，比如 64页，

50、核心才真正将这些页面写入对换区。(3)在对换设备上已有换出页的副本，但该页内容已被修改过。此时核心将释放该页在对换设备上占有的空间，再重新将该页拷贝到对换设备上。在第一、三种情况下偷页进程要将该页拷贝到对换设备上。3 3将换出页面写到对换设备上将换出页面写到对换设备上 (1)当换出页面链上的页数达到规定值时，核心应将它们换出。为此，应首先为这些页面分配一连续的对换空间，以便将它们一起换出；(2)如果对换设备上没有足够大的连续空间，而其空闲存储空间的总和又大于64K时，核心可采取每次换出一页的方式将它们换出。每当核心向对换设备上写一个页面时，须首先清除该页表项的有效位，并将页面数据表项中的引用数