第4章存储器管理(10-5-13)

第四章存储器管理4.1存储器的层次结构

4.2程序的装入和链接

4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式

存储管理概述内存的作用内存管理概述由存储单元（字节或字）组成的一维连续地址空间，用来存放当前正在运行的程序的代码或数据，是程序中指令本身（程序计数器）所指向的存储空间。4.1存储器的层次结构

多级存储器结构对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。在较高档的计算机中，还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。如图4-1所示，在存储层次中越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。其中，寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。固定磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。

计算机的存储体系回顾内存管理概述图4-1计算机系统存储层次示意

内存管理的目的操作系统的“方便”性便于用户装入程序，无须了解底层细节可实现动态的存储空间伸缩，适应不同程序的需要操作系统的“合理”性合理分配内存空间，保证多道程序的顺利运行合理保护内存空间，防止各种可能的破坏泄漏操作系统的“有效性”有效保持内存空间的可用性，防止对资源的浪费有效实现“小空间大容量”，提高计算机的适应性有效配合CPU的调度过程，实现系统运行的稳定内存管理概述内存管理的任务内存空间的管理、分配和回收内存空间的使用情况记录——位图、分配表、分区表内存空间的分配与回收——定长与不定长、静态与动态内存空间的地址映射（转换）物理地址与逻辑地址的差别内存空间的共享和保护内存共享：进程与线程、中间件应用内存保护：如何防止地址越界或操作越权？内存空间的扩充虚拟存储：如何使用小内存空间来运行大的程序？内存管理概述4.2程序的装入和链接图4-1对用户程序的处理步骤如果程序为多个模块，则需要进行链接；单个目标模块无须进行链接。在Unix/Linux链接有多种方式。单模块的装入方式：绝对装入方式可重定位方式4.2.1程序的装入1.绝对装入方式

按模块中的地址，将程序和数据装入到内存对应位置。程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。1、AbsoluteLoadingMode(ALM)绝对装入方式：在编译时，已经知道程序要驻留在内存的位置，如地址1024开始，则编译程序直接产生从该地址向上开展的目标代码，目标代码中全部采用绝对地址。JumpkLoadmkmJump1424Load2224142422241024汇编/编译Jump1424Load2224142422241024装入2.重定位装入方式ALM存在问题：多道程序环境下，编译程序无法预先知道程序的装入位置。重定位装入：目标模块的起始地址通常是从0开始，其他地址也是相对于起始地址计算的。在程序装入时，把目标程序中的指令和数据的相对地址(有效地址)修改成装入位置处内存的物理地址。图4-2作业装入内存时的情况2、RelocatableLoadingMode-RLM静态重定位：地址变换只是在装入时一次性完成，以后不再改变。JumpkLoadmkmJump400Load120040012000汇编/编译Jump1400Load2200140022001000作业空间内存空间装入可重定位装入方式存在问题：虽然可以把程序装入到内存的任意位置，但不允许程序在内存中移动位置。如果程序在内存中移动，就必须对程序中的地址进行修改才能正常运行。动态运行时装入程序：把装入模块装入内存时，不把程序中的地址转换成实际的物理地址，而是在运行时才进行地址转换。2.动态运行时装入方式3、DynamicRun-TimeLoadingJumpkLoadmkmJump400Load120040012000汇编编译Jump400Load1200140022001000作业空间内存空间装入4001000++1200运行时动态重定位：在程序执行时，每当访问指令和数据时，将要访问的指令和数据的相对地址转换成绝对地址。链接的主要功能：把经汇编、编译所得到的一组目标模块和所需的库函数目标模块一起，装配成一个完整的装入模块。有三种链接方法：静态链接装入时动态链接运行时动态链接4.2.2程序的链接链接需要解决两个问题：修改相对地址：编译产生的目标模块起始地址为0，除第一块外，其余的相对地址全部要修改。变换外部调用符号：把外部调用符号变换成相对地址—形成可执行文件。模块ACallBReturn模块BCallCReturn模块CReturn0L-10M-10N-1模块AJSR“L”Return模块BJSR“L+M”Return模块CReturn0L-1LL+M-1L+ML+M+N-1可执行文件1、静态链接程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块，以后不再拆开。2、装入时动态链接优点：便于软件的版本修改和更新：只要对需要修改的模块修改后编译即可，保证所有的软件同步升级。便于实现目标模块的共享：实现多个模块共享一个模块、而不要每个程序都含有该模块的拷贝。模块ACallBReturn模块BCallCReturn模块CReturn模块AJSR“L”Return模块BJSR“L+M”Return模块CReturn0L-1LL+M-1L+ML+M+N-10L-10M-10N-1装入过程独立目标模块在内存中3、运行时动态链接装入链接的问题：程序运行期间、整个模块的结构不变—静态结构。在运行期间有些模块(如错误处理)可能不用、但一直占据内存。运行时链接：在运行期间需要一个模块才装载一个模块。模块ACallBReturn模块BCallCReturn模块CReturn模块AJSR“L”Return模块BJSR“L+M”Return模块CReturn0L-1LL+M-1L+ML+M+N-10L-10M-10N-1独立目标模块在内存中运行时装入运行时装入4.3连续分配存储管理方式连续分配存储管理有两种方式：单一连续分配方式：在内存中仅驻留一道程序，整个用户区为一个用户独占。适用于：单用户、单任务OS。分区式分配方式：可以分固定分区和动态分区。固定分区式：把内存用户区划分成若干个固定大小的区域，每个区域驻留一道程序。动态分区：根据用户程序大小、动态地对内存进行划分。特点：内存划分成多少分区是可变的。4.3.1单一连续分配方式内存划分：系统区：仅给操作系统使用(可以放在低端或高端)，由于中断向量驻留在低端、一般放在低端。用户区：提供给用户使用的区域。CPU<+OS驻留用户区界限寄存器重定位寄存器物理地址是地址错否基址越界中断信号4.3.2固定分区分配划分分区的方法：分区大小相等：把内存划分成大小相等的区域。缺点：程序小浪费空间、程序大不能运行。分区大小不等：优点：大、小程序都可运行。System256K256K256K256K256K256K256KEqual-sizePartitionSystem256K64K128K256K512K1MUnequal-sizePartition图4-4固定分区使用表内存分配：使用分区使用表（分区号，大小，始址，状态）对分区进行管理。4.3.3动态分区分配动态分区分配动态分区分配需要解决三个问题：分配管理的数据结构、分配算法、分区的分配和回收。1、分区分配中的数据结构：空闲分区表：空闲分区链：序号分区大小(K)分区始址(K)状态132256可用216512可用……………………2、动态分区分配算法动态分区分配算法：首次适应算法FF—FirstFit循环首次适应算法NF—NextFit最佳适应算法BF—BestFit最坏适应算法

WF—WorstFit8K12K22K18K8K6K36K最后分配14K8K12K22K18K8K6K36K请求分配16KFirstFitBestFitNextFit练习下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么？

5)快速适应算法(quickfit)该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分，如2KB、4KB、8KB等，对于其它大小的分区，如7KB这样的空闲区，既可以放在8KB的链表中，也可以放在一个特殊的空闲区链表中。

3、分区分配操作分区分配操作：分配与回收。分配：从头开始查找检索完否？返回m.size>u.size查找下一个m.size-u.size>size划出u.size分区整块分配修改有关数据NYNYNm.size—空闲分区大小u.size—请求分区大小size—不可再分割大小按分区分配算法内存的回收当一个进程运行结束，要释放内存，操作回收内存，并把它插入到空闲区链表中。根据回收区的位置，有四种情况需要处理：空闲区回收区回收区空闲区空闲区回收区空闲区回收区情况1情况2情况3情况44.3.4动态重定位分区分配紧凑：把空闲区合并成一个连续区域。动态重定位：程序中的相对地址变换是在程序执行期间进行的。8K12K6K18K44K紧凑0Load250010036525002500相对地址10000重定位寄存器10000Load25001010036512500+处理机存储器动态重定位分配算法原理：在动态分区分配算法中，当找不到足够大的空闲分区来满足请求的空间时进行“紧凑”。请求分配u.size分区检索空闲分区链找到m.size≥u.size按动态分区分配方式进行分配空闲分区总和≥u.size进行“紧凑”返回分区号及首址无法分配返回yNYN4.3.5伙伴系统固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，l≤k≤m，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。

假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k(0≤k≤m)个空闲分区链表。

当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i－1<n≤2i，然后在空闲分区大小为2i的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i＋1的空闲分区链表中寻找。若存在2i＋1的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。若大小为2i＋1的空闲分区也不存在，则需要查找大小为2i＋2的空闲分区，若找到则对其进行两次分割：第一次，将其分割为大小为2i＋1的两个分区，一个用于分配，一个加入到大小为2i＋1的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为2i的两个分区，一个用于分配，一个加入到大小为2i的空闲分区链表中。若仍然找不到，则继续查找大小为2i＋3的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对2k的空闲分区进行k次分割才能得到所需分区。

与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为2i的空闲分区时，若事先已存在2i的空闲分区时，则应将其与伙伴分区合并为大小为

2i＋1的空闲分区，若事先已存在2i＋1的空闲分区时，又应继续与其伙伴分区合并为大小为2i＋2的空闲分区，依此类推。在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。与前面所述的多种方法相比较，由于该算法在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比前面所述的分类搜索算法差，但比顺序搜索算法好，而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。伙伴系统例子用户区初始大小为1MB。按下列顺序分配内存：A请求100KB，B请求240KB，C请求64KB，D请求256KB，释放B，释放A，E请求75KB，释放C，释放E，释放D。给出内存分配过程。1MB4.3.5哈希算法在上述的分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区大小进行分类，对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。在为进程分配空间时，需要在一张管理索引表中查找到所需空间大小所对应的表项，从中得到对应的空闲分区链表表头指针，从而通过查找得到一个空闲分区。如果对空闲分区分类较细，则相应的空闲分区链表也较多，因此选择合适的空闲链表的开销也相应增加，且时间性能降低。

哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。

4.3.6对换(Swapping)

对换：把内存中暂时不能运行的进程或暂时不用的程序和数据，换到外存，以腾出足够的内存空间，把具备运行条件的进程或进程需要的程序和数据换到内存。进程对换：以整个进程为单位进行的对换—分时系统。部分对换：以“页”为单位的对换—页面对换；以“段”为单位的对换—分段对换。两者称部分对换。进程对换时系统必备的功能：对换空间管理；进程的换出；进程的换入。1、对换空间的管理具有对换功能OS外存划分：文件区和对换区。文件区：用于长期保存文件—离散分配方式。目标提高存储利用率。对换区：用于短时间存放内存换出的进程，要求较高的换进、换出速度—采用连续分配。对换区管理的记录方式：空闲分区表和空闲分区链—与内存管理类似。以磁盘块为单位。对换区的分配与回收与动态内存分配算法相同：FirstFit、NextFit、BestFit。2、进程的换出实质：把活动阻塞、就绪状态的进程转挂起状态。选择被换出的进程实施换出换出进程考虑的因素：处于阻塞或睡眠状态的、优先级最低的进程。无阻塞：选择优先级低的就绪进程。考虑优先级低产生“刚换进又换出”，兼顾在内存驻留时间。非共享的程序和数据段。如果是共享的，只能那些引用数-1后为零才能被换出。换出操作：申请对换空间，等申请成功继续。把程序、数据写入交换区，检查写入的正确性。释放进程所占的内存空间。修改被换出的进程的控制块、修改内存分配表。3、进程的换入实质：把挂起状态->活动就绪或阻塞。进程换入考虑的因素：有足够的内存空间“就绪挂起”优先于“阻塞挂起”同一队列中，优先级高、挂起时间长的优先换入。换入操作：多个进程依次换入。申请内存空间，如果申请成功继续。把挂起进程换入。修改进程PCB和内存分配链(表)。如果内存申请失败，首先实施进程换出。分页、分段存储管理方式内存分区管理存在问题：固定分区方式：将产生大量的内部“碎块”；动态分区方式：将产生大量的外部“碎块”，而进行“紧凑”则需要额外的开销。思路：把用户的程序空间划分成若干块，它们可以离散分配到内存中非连续的存储区域中。充分利用内存。分类：按程序分块的单位分为分页存储、分段存储、段页式存储。4.4分页存储管理方式基本原理：把用户程序的地址空间划分成若干固定大小的区域(fixedsizechunk)，把它们叫“页”。把内存空间划分成若干和“页”大小相同的物理块，这些物理块叫“页框”(frame)。内存分配：把用户程序的任一页分配到内存中的任一帧，从而实现非连续的、离散的内存分配。问题：如何管理、如何进行地址变换。一、分页存储管理基本方法程序A0页1页2页3页4页5页n页进程A页表00页号块号1124354859012345678…………内存9程序B0页1页2页3页4页5页m页进程B页表02页号块号132637…………页表作用：实现页号到物理块号的映射。分页存储管理方式的地址结构地址组成：页号P+(页内地址)位移量d例如：32位地址，0~11为位移量(4KB/页)，12~31为页号，最大可以有1M页。页号P和页内地址d的确定：设逻辑地址空间中的地址为A，页面大小为L:P=INT[A/L]d=[A]modL地址结构：页号P位移量d1211031页面大小的确定分页系统中，页面的大小是由硬件的地址结构所决定的。机器确定、页面大小便确定。通常是：几KB到几十KB。影响：页面↓→内部碎块↓、内存的利用率↑页面↓→页表↑、占用内存↑页面↓→页面的换出换入效率↓。二、地址变换机构分页存储系统中，地址变换机构的任务：把逻辑地址中的页号转换为内存中物理块的块号。注意：页面大小与页框大小一致，无须进行页内地址转换。实现转换：借助于页表。页表的实现：寄存器：变换速度快、成本高，适应小型系统。页表驻留在内存：速度较低、成本低，适应大系统。页表页表驻留在内存的变换机构在系统中设置一个页表寄存器(PTR—pagetableregister)：存放页表在内存的起始地址和页表的长度；非执行状态该数据保存在进程的PCB中。页表寄存器页表始址页表长度逻辑地址页号=2页内地址=12800页号块号112435…………+4内存页表>越界中断物理地址128具有快表的地址变换机构页表存放在内存时CPU存取数据，访问两次内存：第一次：访问内存页表，找到物理块号+页内地址，形成物理地址。第二次：访问内存，读/写数据。具有快表：在地址变换机构中增设一个具有并行查询能力的特殊高速缓冲存储器—联想存储器/快表。工作原理：CPU给出有效地址；如果地址在“快表”中，直接读出对应的物理块号，送往物理地址寄存器；再访问内存。如果快表中没有对应的地址，从内存“页表”读取地址送往物理地址寄存器，访问内存；把页表项存入快表或把老的页表项换出。具有快表的地址变换机构（续）页表寄存器页表始址页表长度逻辑地址页号页内地址00页号块号112435…………+4内存页表(慢表)>越界中断物理地址页号块号24输入寄存器快表三、两级、多级页表一级页表存在问题：支持的逻辑空间越大，页表就越大，页表所占用的内存空间就越大。如：设32位逻辑空间，页面大小为212B，需要220个表项，每个表项4B，则需要4M的连续内存空间。从两个方面解决：离散分配页表；部分页表驻留在外存：需要时调入内存。1、两级页表实质：把大的页表再进行分页存放，实现存放页表的页面离散存放。外部页表：存放每个页表的物理块号。逻辑地址结构：p1p2d外层页号外层页内地址页内地址31222112110逻辑地址外部页表寄存器+外部页表+页表物理地址图4-14两级页表结构2、多级页表结构32位机器用两级页表结构合适。64位用两级将产生非常大的外层页表：如：页面大小为212B,页表大小为210项，则外部页表：242项=4096G个表项。多级页表实质：对大的外部页表进行分页分成若干级外部页表，实现存放外部页表的页面离散存放。第一级第二级第三级页内偏移量外部页表寄存器PFNPFNPFNPFN—PageFrameNumber分段存储管理方式引入的目的：主要是为了满足用户和程序员的下述一系列需要：方便编程：用户把作业分成若干逻辑段，每段有自己的名字和长度，逻辑地址由段名和段内偏移量决定。分段共享：在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。分段保护：便于对信息的逻辑单位进行保护。动态链接：动态链接是以段为单位调入内存。动态增长：实际使用中，数据段的长度不能预先确定，需要动态增加。4.4基本分段存储管理方式一、分段系统的基本原理分段：把作业的地址空间划分若干段，每一段定义一组逻辑信息。为了实现简单起见，通常可用一个段号来代替段名，每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间由于是分成多个段，因而是二维的，亦即，其逻辑地址由段号(段名)和段内地址所组成。物理内存的管理采用动态分区。分段地址中的地址结构：

64K个段64KB长度

分段方式已得到许多编译程序的支持，编译程序能自动地根据源程序的情况而产生若干个段。例如，Pascal编译程序可以为全局变量、用于存储相应参数及返回地址的过程调用栈、每个过程或函数的代码部分、每个过程或函数的局部变量等等，分别建立各自的段。类似地，Fortran编译程序可以为公共块(Commonblock)建立单独的段，也可以为数组分配一个单独的段。装入程序将装入所有这些段，并为每个段赋予一个段号。

段表：系统为每段分配一段连续区域，而进程中的各段则离散存放在不同的分区中。段表：记录逻辑段与内存物理位置的对应映射关系。段号段长基址030K40K120K80K215K120K段表(MAIN)=0(x)=1(D)=2内存空间作业空间030K(MAIN)=0020K(X)=1015K(D)=240K80K120K地址变换机构：段表始址段表长度段表寄存器2段号段内偏移量100+段号段长基址01K6K16004K25008K32009200段表>越界中断+8292物理地址012内存空间8K为提高数据存取速度，减少内存访问次数，分段存储管理方式增设一个联想存储器。分页与分段的区别分块方式使用碎片地址长度目的分页存储管理物理分块，系统决定对程序员是不可见，使用简单每个进程只有一个内部碎片，大小不超过1页一维固定提高内存的利用率分段存储管理逻辑分块，大小与信息块有关，由编译系统划分对程序员可见，使用方便，但难度大每个进程有多个外部碎片二维不确定便于信息保护与共享，方便用户二、共享与保护可重入代码：纯代码，允许多个进程同时访问同一代码，可重入代码不允许用户对代码进行修改。分页：实现代码共享、保护比较困难。要求每个进程的每个页表项都指向共享页。分段：实现代码共享、保护简单。只要每个进程的段表项指向共享段就可以实现。信息共享图4-18分页系统中共享editor的示意图图4-19分段系统中共享editor的示意图三、段页式存储方式基本原理：先把用户的程序分为若干个段，再把每个段划分成若干页。主程序段04K8K12K16K子程序段04K8K数据段04K8K12K段号段内页号页内地址逻辑地址：图4-21利用段表和页表实现地址映射段页式存储管理的地址转换:段号=3页号=2d逻辑地址段表始址段表长度段表寄存器++越界中断段号段长页表始址页表长度状态0123页号页框号外存地址状态012+物理地址段表页表采用段页式存储管理方式,访问数据需要三次访存.4.5.1虚拟存储方法的引入原有存储管理方法中存在的问题解决问题的动机问题产生的原因解决方法的探索解决方案的可行性分析4.5虚拟存储器的基本概念

1）原有存储管理中存在的问题当作业很大，超过内存剩余时，无法装入装入的作业对内存利用率不高99%空间内的指令在短时间内都不会得到执行2）解决问题的动机解决装入作业受限提高内存利用率提高系统吞吐量短时间内执行的部分3）问题产生的原因作业装入的“一次性”作业装入后的“驻留性”4）解决方法的探索不需一次全部装入作业装入内存的程序可在不需要访问时暂时退出内存5）解决方案可行性程序执行的局部性规律（1）顺序执行规律（2）跳转的局部性程序的跳转和调用范围不大（3）数据访问的局部性局部性时间的局部性在短时间内多次被访问空间的局部性在较短程序范围内多次访问4.5.2虚拟存储器的定义虚拟存储指仅把作业的一部分装入内存便可运行的存储管理系统，通过作业各部分的动态调入和置换，用户所感觉的存储空间比实际空间大，称之为虚空间。内存程序分页磁盘对换区01230123将暂时不用的第0页置换出去部分装入后开始执行将暂时不用的第1页置换出去产生给用户感觉比实际空间大的虚拟空间01234.5.3虚拟存储的特征离散性虚拟存储建立在离散内存管理基础上多次性程序页面会多次进/出内存对换性在置换页面时需要在外存建立对换区虚拟性程序部分装入就可以执行给用户感觉比实际空间大的虚拟空间虚空间大小虚空间大小虚空间的逻辑大小＝虚空间的实际大小＝例：32位操作系统的可寻址范围是232=4GByte，Windows98系列系统。例：在window系统盘根目录下，有兑换文件－－外存对换区。如XP系统的pagefile.sys文件可寻址范围内存＋外存对换区虚拟存储例虚拟存储的外存对换区4.5.4虚拟存储器的实现方式虚拟存储器技术是在离散分配存储管理方式的基础上实现的。实现的方式：分页请求系统和分段请求系统。分页请求系统：在分页存储管理系统基础上增加请求调页、页面置换功能形成页式虚拟存储系统。需要硬件支持：请求分页的页表机制。缺页中断机构。地址变换机构。分段请求系统：在分段存储管理系统基础上增加请求调段、分段置换功能形成段式虚拟存储系统。需要硬件支持：

请求分段的页表机制。

缺段中断机构。

地址变换机构。

4.6请求分页存储管理方式4.6.1请求分页中的硬件支持页号物理块号状态位P访问字段A修改位M外存地址在简单页式存储管理的基础上，增加请求调页和页面置换功能。页表机制：主要用于把逻辑地址变换为物理地址。保存程序换进、换出的信息。缺页中断机构：在请求分页系统中，每当要访问的页面不在内存，便产生一缺页中断。缺页中断的特点：在指令执行期间产生和处理中断信号。一条指令可能产生多次缺页中断。ABCopyAtoB123456地址变换机构：程序请求访问一页开始页号>页表长度越界中断YesCPU检索快表页表项在快表中?访问表页页在内存中?缺页中断修改快表修改访问位和修改位形成物理地址结束YesYes中断返回缺页中断处理保护CPU现场从外存中找到缺页内存满否？选择一页换出该页是否修改过？将该页写回外存OS命令CPU从外存读取缺页启动I/O硬件将一页从外存换入内存修改页表中断结束返回恢复CPU现场YesYes4.6.2页面分配进程物理块分配：保证进程能正常运行最小物理块数确定。为每个进程分配物理块：固定或可变。对进程分配物理块数的算法。最小物理块：保证进程能正常运行的最少块数，与硬件的结构有关：对于单地址指令、直接寻址方式：最少物理块数为2。指令页和数据页；允许间接寻址至少3块。页面分配和置换策略：固定分配局部置换可变分配全局置换固定分配局部置换：分配给进程的物理块数固定、置换也是从进程的物理块(局部)中选择换出。可变分配全局置换：分配给进程的物理块根据进程的缺页情况变化、换出块从系统所有进程(全局)选择。可变分配局部置换：分配给进程的物理块根据今年成的缺页情况变化、置换从进程的物理块中选择(局部)分配算法分配算法有：平均分配、按比例分配、考虑优先权分配。平均分配：根据系统总块数和当前的进程数平均分配。按比例分配：按每个进程的页面数分配物理块。

bk=(Sk/∑Si)*Mbk--第k个进程分配的块数。Sk--第k个进程分配的页面数。∑Si--目前所有进程的页面数之和。M--内存的总物理块数。考虑优先权分配策略：给予重要、紧急的任务更高的优先权、更大的内存空间。页面调入策略页面调入策略需要考虑：何时调入页面、从何处调入页面、如何操作。何时调入页面：请求调页(demandpaging)：只调入发生缺页时所需的页面。优点：容易实现。缺点：对外存I/O次数多，开销较大预调页(prepaging)：在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。优点：提高调页的I/O效率。缺点：基于预测，若调入的页在以后很少被访问，则效率低。常用于程序装入时的调页。从何处调页请求分页系统中外存分：文件区和对换区。因此缺页调入内存有三种情况：当对换区空间足够时：运行前把进程有关的文件拷贝到对换区，运行过程直接从对换区调入所需的页面。当对换区空间不足时，凡是不会被修改的文件，直接从文件区调入。UNIX方式：与进程有关的文件放在文件区；因此未运行过的页面，都从文件区调入；而运行过程中换出的页面，放入对换区，以后从对换区调入。页面调入过程进程所需的页面不在内存向CPU发出缺页中断转中断处理程序中断处理程序保留CPU环境分析中断原因转缺页中断恢复CPU环境中断处理结束继续执行缺页中断处理程序查找页表获得该页的外存物理块号内存满否？从外存把缺页调入内存修改页表按照页面置换算法，找到换出的页面该页被修改过？写入快表缺页中断处理结束修改页表YesYes先把换出页面写入磁盘4.7页面置换算法页面置换算法：选择换出页面的算法。重要性：页面置换算法选择不当，将导致进程发生“抖动”；即刚换出的页面很快又被重新调入，产生某进程频繁地换进、换出。常见的置换算法：最佳置换算法先进先出置换算法最近最久使用置换算法最少使用置换算法页面缓冲算法等等4.7.1最佳置换算法和先进先出置换算法

1.最佳(Optimal)置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。因无法预先知道哪个页面将是未来最长时间内不被引用，本算法无法实现；但可利用他评价其他算法。假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

图4-25利用最佳页面置换算法时的置换图2.先进先出(FIFO)页面置换算法总是把最先进入内存的页面淘汰出去可以通过链表来表示各页的建立时间先后。性能较差。较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出。并且有Belady现象。Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。Belady现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S,N)时而增大，时而减小。Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。Belady现象的例子进程P有5页程序访问页的顺序为：1,2,3,4,1,2,5,1,2,3,4,5；如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次；如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；4.7.2最近最久未使用(LRU)置换算法1.LRU(LeastRecentlyUsed)置换算法的描述图4-27LRU页面置换算法选择内存中最久未使用的页面被置换。2.LRU置换算法的硬件支持

1)寄存器每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。R=Rn-1Rn-2Rn-3…R2R1R0

这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。图4-28某进程具有8个页面时的LRU访问情况2)栈图4-29用栈保存当前使用页面时栈的变化情况把被访问的页面移到栈顶，于是栈底的是最久未使用页面。4.7.3轮转算法(clock)每页有一个使用标志位(usebit)，若该页被访问则置userbit=1。置换时采用一个指针，从当前指针位置开始按地址先后检查各页，寻找usebit=0的页面作为被置换页。指针经过的userbit=1的页都修改userbit=0，最后指针停留在被置换页的下一个页。也称最近未使用算法(NRU,NotRecentlyUsed)，它是LRU(最近最久未使用算法)和FIFO的折衷。1.简单的Clock置换算法图4-30简单Clock置换算法的流程和示例2.改进型Clock置换算法由访问位A和修改位M可以组合成下面四种类型的页面：

1类(A=0,M=0):表示该页最近既未被访问，又未被修改，是最佳淘汰页。

2类(A=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。

3类(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问。

4类(A=1,M=1):最近已被访问且被修改，该页可能再被访问。其执行过程可分成以下三步：

(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。

(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。

(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。1.最少使用置换算法(LFU,LeastFrequentlyUsed)选择到当前时间为止被访问次数最少的页面被置换；每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；4.7.4其它置换算法2.页面缓冲算法(pagebuffering)被置换页面的选择和处理：用FIFO算法选择被置换页，把被置换的页面放入两个链表之一。如果页面未被修改，就将其归入到空闲页面链表的末尾否则将其归入到已修改页面链表。它是对FIFO算法的发展，通过被置换页面的缓冲，有机会找回刚被置换的页面；需要调入新的物理页面时，将新页面内容读入到空闲页面链表的第一项所指的页面，然后将第一项删除。空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，只需较小开销，而被访问的页面可以返还作为进程的内存页。当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表，这样能大大减少I/O操作的次数。4.7.5请求分页系统的性能分析一、缺页率对有效访问时间的影响：一般内存的访问时间ma在10ns到数百ns之间。而访问外存要寻道时间、旋转时间、数据转送时间，一般在24ms。考虑缺页概率为p，则：有效访问时间=(1-p)×ma+p×缺页中断时间ma按100ns计算;缺页中断时间：(1)缺页中断服务时间；(2)将缺页读入的时