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

1、第四章 存 储 器 管 理 第四章存储器管理 4.1 存储器的层次结构存储器的层次结构 4.2程序的装入和链接程序的装入和链接 4.3连续分配方式连续分配方式4.4基本分页存储管理方式基本分页存储管理方式4.5基本分段存储管理方式基本分段存储管理方式4.6虚拟存储器的基本概念虚拟存储器的基本概念4.7请求分页存储管理方式请求分页存储管理方式4.8页面置换算法页面置换算法4.9请求分段存储管理方式请求分段存储管理方式 第四章 存 储 器 管 理 存储管理概述内存的作用内存管理概述内存管理概述由存储单元（字节或字）组成的一维连续地址空由存储单元（字节或字）组成的一维连续地址空间，用来存放当前正在运

2、行的程序的代码或数据，间，用来存放当前正在运行的程序的代码或数据，是程序中指令本身（程序计数器）所指向的存储是程序中指令本身（程序计数器）所指向的存储空间。空间。第四章 存 储 器 管 理 4.1 存储器的层次结构存储器的层次结构 多级存储器结构多级存储器结构对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。在较高档的计算机中，还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。如图4-1所示，在存储层次中越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。其中，寄存器、高速缓存、主存储器和磁

3、盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。固定磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。 第四章 存 储 器 管 理 计算机的存储体系回顾内存管理概述内存管理概述第四章 存 储 器 管 理 图4-1 计算机系统存储层次示意 寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存第四章 存 储 器 管 理 内存管理的目的操作系统的“方便”性便于用户装入程序，无须了解底层细节可实现动态的存储空间伸缩，适应不同程序的需要操作系统的“合理”性合理分配内存空间，保证多道程序的顺利运行合理保护内存空间，防止各种可能的破坏泄漏操作系统的“有

4、效性”有效保持内存空间的可用性，防止对资源的浪费有效实现“小空间大容量”，提高计算机的适应性有效配合CPU的调度过程，实现系统运行的稳定内存管理概述内存管理概述第四章 存 储 器 管 理 内存管理的任务内存空间的管理、分配和回收内存空间的使用情况记录位图、分配表、分区表内存空间的分配与回收定长与不定长、静态与动态内存空间的地址映射（转换）物理地址与逻辑地址的差别内存空间的共享和保护内存共享：进程与线程、中间件应用内存保护：如何防止地址越界或操作越权？内存空间的扩充虚拟存储：如何使用小内存空间来运行大的程序？内存管理概述内存管理概述第四章 存 储 器 管 理 4.2 程序的装入和链接程序的装入和

5、链接 图 4-1 对用户程序的处理步骤 第四章 存 储 器 管 理 如果程序为多个模块，则需要进行链接；单个目如果程序为多个模块，则需要进行链接；单个目标模块无须进行链接。在标模块无须进行链接。在Unix/Linux链接有多种链接有多种方式。单模块的装入方式：方式。单模块的装入方式：绝对装入方式绝对装入方式可重定位方式可重定位方式4.2.1 程序的装入程序的装入第四章 存 储 器 管 理 1. 绝对装入方式绝对装入方式 按模块中的地址，将程序和数据装入到内存对应位置。程序中所使用的绝对地址，既可在编译或汇编时给出， 也可由程序员直接赋予。第四章 存 储 器 管 理 1、Absolute Loa

6、ding Mode(ALM)绝对装入方式绝对装入方式：在编译时，已经知道程序要驻留在内存的位置，如地址1024开始，则编译程序直接产生从该地址向上开展的目标代码，目标代码中全部采用绝对地址。Jump kLoad mkmJump 1424Load 2224142422241024汇编/编译Jump 1424Load 2224142422241024装入第四章 存 储 器 管 理 2.重定位重定位装入方式装入方式ALM存在问题存在问题：多道程序环境下，编译程序无法预先知道程序的装入位置。重定位装入重定位装入：目标模块的起始地址通常是从0开始，其他地址也是相对于起始地址计算的。在程序装入时，把目标程

7、序中的指令和数据的相对地址(有效地址)修改成装入位置处内存的物理地址。第四章 存 储 器 管 理 图 4-2 作业装入内存时的情况 LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作业地址空间内存空间第四章 存 储 器 管 理 2、Relocatable Loading Mode-RLM静态重定位静态重定位：地址变换只是在装入时一次性完成，以后不再改变。Jump kLoad mkmJump 400Load 120040012000汇编/编译Jump 1400Load 2200140022001000作业空间内存空间装入第

8、四章 存 储 器 管 理 可重定位装入方式存在问题可重定位装入方式存在问题：虽然可以把程序装入到内存的任意位置，但不允许程序在内存中移动位置。如果程序在内存中移动，就必须对程序中的地址进行修改才能正常运行。动态运行时装入程序动态运行时装入程序：把装入模块装入内存时，不把程序中的地址转换成实际的物理地址，而是在运行时才进行地址转换。2.动态运行时装入方式动态运行时装入方式第四章 存 储 器 管 理 3、Dynamic Run-Time LoadingJump kLoad mkmJump 400Load 120040012000汇编编译Jump 400Load 1200140022001000作业

9、空间内存空间装入4001000+1200运行时 动态重定位动态重定位：在程序执行时，每当访问指令和数据时，将要访问的指令和数据的相对地址转换成绝对地址。第四章 存 储 器 管 理 链接的主要功能：把经汇编、编译所得到的一组目标模块和所需的库函数目标模块一起，装配成一个完整的装入模块。有三种链接方法：静态链接装入时动态链接运行时动态链接4.2.2 程序的链接程序的链接 第四章 存 储 器 管 理 链接需要解决两个问题：链接需要解决两个问题：修改相对地址：编译产生的目标模块起始地址为0，除第一块外，其余的相对地址全部要修改。变换外部调用符号：把外部调用符号变换成相对地址形成可执行文件。第四章 存

10、储 器 管 理 模块ACall BReturn模块BCall CReturn模块CReturn0L-10M-10N-1模块AJSR “L”Return模块BJSR “L+M”Return模块CReturn0L-1LL+M-1L+ML+M+N-1可执行文件1、静态链接、静态链接程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块，以后不再拆开。第四章 存 储 器 管 理 2、装入时动态链接、装入时动态链接优点：便于软件的版本修改和更新：只要对需要修改的模块修改后编译即可，保证所有的软件同步升级。便于实现目标模块的共享：实现多个模块共享一个模块、而不要每个程序都含有该模块的拷贝

11、。模块ACall BReturn模块BCall CReturn模块CReturn模块AJSR “L”Return模块BJSR “L+M”Return模块CReturn0L-1LL+M-1L+ML+M+N-10L-10M-10N-1装入过程装入过程独立目标模块独立目标模块在内存中在内存中第四章 存 储 器 管 理 3、运行时动态链接、运行时动态链接装入链接的问题：程序运行期间、整个模块的结构不变静态结构。在运行期间有些模块(如错误处理)可能不用、但一直占据内存。运行时链接：在运行期间需要一个模块才装载一个模块。模块ACall BReturn模块BCall CReturn模块CReturn模块AJ

12、SR “L”Return模块BJSR “L+M”Return模块CReturn0L-1LL+M-1L+ML+M+N-10L-10M-10N-1独立目标模块独立目标模块在内存中在内存中运行时装入运行时装入运行时装入运行时装入第四章 存 储 器 管 理 4.3 连续分配存储管理方式连续分配存储管理方式连续分配存储管理有两种方式：连续分配存储管理有两种方式：单一连续分配方式单一连续分配方式：在内存中仅驻留一道程序，：在内存中仅驻留一道程序，整个用户区为一个用户独占。整个用户区为一个用户独占。适用于：单用户、单任务适用于：单用户、单任务OS。分区式分配方式分区式分配方式：可以分固定分区和动态分区。：可

13、以分固定分区和动态分区。固定分区式：把内存用户区划分成若干个固定大小固定分区式：把内存用户区划分成若干个固定大小的区域，每个区域驻留一道程序。的区域，每个区域驻留一道程序。动态分区：根据用户程序大小、动态地对内存进行动态分区：根据用户程序大小、动态地对内存进行划分。特点：内存划分成多少分区是可变的。划分。特点：内存划分成多少分区是可变的。第四章 存 储 器 管 理 4.3.1 单一连续分配方式单一连续分配方式内存划分：系统区：仅给操作系统使用(可以放在低端或高端)，由于中断向量驻留在低端、一般放在低端。用户区：提供给用户使用的区域。CPUu.size查找下一个m.size-u.sizesize

14、划出u.size分区整块分配修改有关数据NYNYNm.size空闲分区大小u.size请求分区大小size不可再分割大小按分区分配算法第四章 存 储 器 管 理 内存的回收内存的回收当一个进程运行结束，要释放内存，操作回收内存，并把它插入到空闲区链表中。根据回收区的位置，有四种情况需要处理：空闲区回收区回收区空闲区空闲区回收区空闲区回收区情况1情况2情况3情况4第四章 存 储 器 管 理 4.3.4动态重定位分区分配动态重定位分区分配紧凑：把空闲区合并成一个连续区域。动态重定位：程序中的相对地址变换是在程序执行期间进行的。8K12K6K18K44K紧凑0Load 250010036525002

15、500相对地址10000重定位寄存器10000Load 25001010036512500+处理机存储器第四章 存 储 器 管 理 动态重定位分配算法动态重定位分配算法原理：在动态分区分配算法中，当找不到足够大的空闲分区来满足请求的空间时进行“紧凑”。请求分配u.size分区检索空闲分区链找到m.sizeu.size按动态分区分配方式进行分配空闲分区总和u.size进行“紧凑”返回分区号及首址无法分配返回yNYN第四章 存 储 器 管 理 4.3.54.3.5伙伴系统伙伴系统固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很

16、低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，lkm，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。 第四章 存 储 器 管 理 假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样

17、，不同大小的空闲分区形成了k(0km)个空闲分区链表。 第四章 存 储 器 管 理 当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i1活动就绪或阻塞。进程换入考虑的因素：有足够的内存空间“就绪挂起”优先于“阻塞挂起”同一队列中，优先级高、挂起时间长的优先换入。换入操作：多个进程依次换入。申请内存空间，如果申请成功继续。把挂起进程换入。修改进程PCB和内存分配链(表)。如果内存申请失败，首先实施进程换出。第四章 存 储 器 管 理 分页、分段存储管理方式分页、分段存储管理方式内存分区管理存在问题：固定分区方式：将产生大量的内部“碎块”；动态分区方式：将产生大量的外部“碎块”，而

18、进行“紧凑”则需要额外的开销。思路：把用户的程序空间划分成若干块，它们可以离散分配到内存中非连续的存储区域中。充分利用内存。分类：按程序分块的单位分为 分页存储、分段存储、段页式存储。第四章 存 储 器 管 理 4.4 分页存储管理方式分页存储管理方式基本原理基本原理：把用户程序的地址空间划分成若干固定大小的区域(fixed size chunk)，把它们叫“页” 。把内存空间划分成若干和“页”大小相同的物理块，这些物理块叫“页框”(frame)。内存分配内存分配：把用户程序的任一页分配到内存中的任一帧，从而实现非连续的、离散的内存分配。问题问题：如何管理、如何进行地址变换。第四章 存 储 器

19、 管 理 一、分页存储管理基本方法一、分页存储管理基本方法程序A0页1页2页3页4页5页n页进程A页表00页号 块号1124354859012345678内存9程序B0页1页2页3页4页5页m页进程B页表02页号 块号132637页表作用：实现页号到物理块号的映射。第四章 存 储 器 管 理 分页存储管理方式的地址结构分页存储管理方式的地址结构地址组成：页号P+(页内地址)位移量d例如：32位地址，011为位移量(4KB/页)，1231为页号，最大可以有1M页。页号P和页内地址d的确定：设逻辑地址空间中的地址为A，页面大小为L:P= INT A / L d= A mod L地址结构地址结构：页

20、号P位移量d12 11031第四章 存 储 器 管 理 页面大小的确定页面大小的确定分页系统中，页面的大小是由硬件的地址结构所决定的。机器确定、页面大小便确定。通常是：几KB到几十KB。影响：页面内部碎块、内存的利用率页面页表、占用内存页面页面的换出换入效率。第四章 存 储 器 管 理 二、地址变换机构二、地址变换机构分页存储系统中，地址变换机构的任务：把逻辑地址中的页号转换为内存中物理块的块号。注意：页面大小与页框大小一致，无须进行页内地址转换。实现转换：借助于页表。页表的实现：寄存器：变换速度快、成本高，适应小型系统。页表驻留在内存：速度较低、成本低，适应大系统。页表第四章 存 储 器 管

21、 理 页表驻留在内存的变换机构页表驻留在内存的变换机构在系统中设置一个页表寄存器(PTRpage table register)：存放页表在 内存的起始地址和页表的长度；非执行状态该数据保存在进程的PCB中。页表寄存器页表始址 页表长度逻辑地址页号=2 页内地址=12800页号 块号112435+4内存页表越界中断物理地址128第四章 存 储 器 管 理 具有快表的地址变换机构具有快表的地址变换机构页表存放在内存时CPU存取数据，访问两次内存：第一次：访问内存页表，找到物理块号+页内地址，形成物理地址。第二次：访问内存，读/写数据。具有快表：在地址变换机构中增设一个具有并行查询能力的特殊高速缓

22、冲存储器联想存储器/快表。工作原理：CPU给出有效地址；如果地址在“快表”中，直接读出对应的物理块号，送往物理地址寄存器；再访问内存。如果快表中没有对应的地址，从内存“页表”读取地址送往物理地址寄存器，访问内存；把页表项存入快表或把老的页表项换出。第四章 存 储 器 管 理 具有快表的地址变换机构（续）具有快表的地址变换机构（续）页表寄存器页表始址 页表长度逻辑地址页号页内地址00页号 块号112435+4内存页表(慢表)越界中断物理地址页号 块号24输入寄存器快表第四章 存 储 器 管 理 三、两级、多级页表一级页表存在问题：支持的逻辑空间越大，页表就越大，页表所占用的内存空间就越大。如：设

23、32位逻辑空间，页面大小为212B，需要220个表项，每个表项4B，则需要4M的连续内存空间。从两个方面解决：离散分配页表；部分页表驻留在外存：需要时调入内存。第四章 存 储 器 管 理 1、两级页表、两级页表实质：把大的页表再进行分页存放，实现存放页表的页面离散存放。外部页表：存放每个页表的物理块号。逻辑地址结构：p1p2d外层页号外层页内地址页内地址3122 2112 110逻辑地址外部页表寄存器+外部页表+页表物理地址第四章 存 储 器 管 理 图 4-14 两级页表结构 101110780121742n第0页页表1460121023第1页页表114115011023外部页表012345

24、671141151468第n页页存空间第四章 存 储 器 管 理 2、多级页表结构、多级页表结构32位机器用两级页表结构合适。64位用两级将产生非常大的外层页表：如：页面大小为212B,页表大小为210项，则外部页表：242项=4096G个表项。多级页表实质：对大的外部页表进行分页分成若干级外部页表，实现存放外部页表的页面离散存放。第一级第二级第三级页内偏移量外部页表寄存器PFNPFNPFNPFNPage Frame Number第四章 存 储 器 管 理 分段存储管理方式引入的目的：主要是为了满足用户和程序员的下述一系列需要：方便编程：用户把作业分成若干逻辑段，每段

25、有自己的名字和长度，逻辑地址由段名和段内偏移量决定。分段共享：在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。分段保护：便于对信息的逻辑单位进行保护。动态链接：动态链接是以段为单位调入内存。动态增长：实际使用中，数据段的长度不能预先确定，需要动态增加。4.4 基本分段存储管理方式基本分段存储管理方式 第四章 存 储 器 管 理 一、分段系统的基本原理一、分段系统的基本原理分段：把作业的地址空间划分若干段，每一段定义一组逻辑信息。为了实现简单起见，通常可用一个段号来代替段名，每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的

26、地址空间由于是分成多个段，因而是二维的，亦即，其逻辑地址由段号(段名)和段内地址所组成。 物理内存的管理采用动态分区。第四章 存 储 器 管 理 分段地址中的地址结构： 64K个段64KB长度第四章 存 储 器 管 理 分段方式已得到许多编译程序的支持，编译程序能自动地根据源程序的情况而产生若干个段。例如，Pascal编译程序可以为全局变量、用于存储相应参数及返回地址的过程调用栈、每个过程或函数的代码部分、每个过程或函数的局部变量等等，分别建立各自的段。类似地，Fortran编译程序可以为公共块(Common block)建立单独的段，也可以为数组分配一个单独的段。装入程序将装入所有这些段，并

27、为每个段赋予一个段号。 第四章 存 储 器 管 理 段表：系统为每段分配一段连续区域，而进程中的各段则离散存放在不同的分区中。段表：记录逻辑段与内存物理位置的对应映射关系。段号段长基址030K40K120K80K215K120K段表(MAIN)=0(x)=1(D)=2内存空间作业空间030K(MAIN)=0020K(X)=1015K(D)=240K80K120K第四章 存 储 器 管 理 地址变换机构：段表始址 段表长度段表寄存器2段号段内偏移量100+段号段长基址01K6K16004K25008K32009200段表越界中断+8292物理地址012内存空间8K为提高数据存取速度，减少内存访问

28、次数，分段存储管理方式增设一个联想存储器。第四章 存 储 器 管 理 分页与分段的区别分块方式使用碎片地址长度目的分页存储管理物理分块，系统决定对程序员是不可见，使用简单每个进程只有一个内部碎片，大小不超过1页一维固定提高内存的利用率分段存储管理逻辑分块，大小与信息块有关，由编译系统划分对程序员可见，使用方便，但难度大每个进程有多个外部碎片二维不确定便于信息保护与共享，方便用户第四章 存 储 器 管 理 二、共享与保护二、共享与保护可重入代码：纯代码，允许多个进程同时访问同一代码，可重入代码不允许用户对代码进行修改。分页：实现代码共享、保护比较困难。要求每个进程的每个页表项都指向共享页。分段：

29、实现代码共享、保护简单。只要每个进程的段表项指向共享段就可以实现。第四章 存 储 器 管 理 信息共享信息共享 ed 1ed 2ed 40data 1data 10进程12122606170页表ed 1ed 2ed 40data 1data 10进程22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180页表图 4-18 分页系统中共享editor的示意图第四章 存 储 器 管 理 图 4-19 分段系统中共享editor的示意图 editor进程1data 1进程2editordata 2段表段长基址1608040

30、2401608040380editordata 1data 280240280380420第四章 存 储 器 管 理 三、段页式存储方式三、段页式存储方式基本原理：先把用户的程序分为若干个段，再把每个段划分成若干页。主程序段04K8K12K16K子程序段04K8K数据段04K8K12K段号段内页号页内地址逻辑地址：第四章 存 储 器 管 理 图 4-21 利用段表和页表实现地址映射 段号状态页表大小页表始址0111213041页号状态存储块#0111213041操作系统主存页表段表段表大小段表始址段表寄存器第四章 存 储 器 管 理 段页式存储管理的地址转换段页式存储管理的地址转换:段号=3页

31、号=2d逻辑地址段表始址 段表长度段表寄存器+越界中断段号段长页表始址页表长度状态0123页号页框号外存地址状态012+物理地址段表页表采用段页式存采用段页式存储管理方式储管理方式,访访问数据需要三问数据需要三次访存次访存.第四章 存 储 器 管 理 4.5.1虚拟存储方法的引入原有存储管理方法中存在的问题解决问题的动机问题产生的原因解决方法的探索解决方案的可行性分析4.5 虚拟存储器的基本概念虚拟存储器的基本概念 第四章 存 储 器 管 理 1）原有存储管理中存在的问题原有存储管理中存在的问题当作业很大，超过内存剩余时，无法装入装入的作业对内存利用率不高99%空间内的指令在短时间内都不会得到

32、执行2）解决问题的动机解决问题的动机解决装入作业受限提高内存利用率提高系统吞吐量第四章 存 储 器 管 理 3）问题产生的原因）问题产生的原因作业装入的“一次性”作业装入后的“驻留性”4）解决方法的探索）解决方法的探索不需一次全部装入作业装入内存的程序可在不需要访问时暂时退出内存第四章 存 储 器 管 理 5）解决方案可行性）解决方案可行性程序执行的局部性规律（1）顺序执行规律（2）跳转的局部性程序的跳转和调用范围不大（3）数据访问的局部性局部性时间的局部性 在短时间内多次被访问空间的局部性 在较短程序范围内多次访问第四章 存 储 器 管 理 4.5.2虚拟存储器的定义虚拟存储指仅把作业的一部

33、分装入内存便可运行的存储管理系统，通过作业各部分的动态调入和置换，用户所感觉的存储空间比实际空间大，称之为虚空间。第四章 存 储 器 管 理 4.5.3虚拟存储的特征离散性虚拟存储建立在离散内存管理基础上多次性程序页面会多次进/出内存对换性在置换页面时需要在外存建立对换区虚拟性程序部分装入就可以执行给用户感觉比实际空间大的虚拟空间第四章 存 储 器 管 理 虚空间大小虚空间大小虚空间的逻辑大小 虚空间的实际大小 例：32位操作系统的可寻址范围是232=4GByte，Windows98系列系统。例：在window系统盘根目录下，有兑换文件外存对换区。如XP系统的pagefile.sys文件第四章

34、 存 储 器 管 理 虚拟存储例第四章 存 储 器 管 理 4.5.4虚拟存储器的实现方式虚拟存储器技术是在离散分配存储管理方式的基础上实现的。实现的方式：分页请求系统和分段请求系统。分页请求系统：在分页存储管理系统基础上增加请求调页、页面置换功能形成页式虚拟存储系统。需要硬件支持：请求分页的页表机制。缺页中断机构。地址变换机构。第四章 存 储 器 管 理 分段请求系统：在分段存储管理系统基础上增加请求调段、分段置换功能形成段式虚拟存储系统。需要硬件支持： 请求分段的页表机制。 缺段中断机构。 地址变换机构。第四章 存 储 器 管 理 4.6 请求分页存储管理方式请求分页存储管理方式 4.6.

35、1 请求分页中的硬件支持请求分页中的硬件支持 页号 物理块号 状态位P 访问字段A 修改位M外存地址 在简单页式存储管理的基础上，增加请求调页和页面在简单页式存储管理的基础上，增加请求调页和页面置换功能。置换功能。页表机制：主要用于把逻辑地址变换为物理地址。保存程序换进、换出的信息。第四章 存 储 器 管 理 缺页中断机构缺页中断机构：在请求分页系统中，每当要访问的页面不在内存，便产生一缺页中断。缺页中断的特点：在指令执行期间产生和处理中断信号。一条指令可能产生多次缺页中断。ABCopy Ato B123456第四章 存 储 器 管 理 地址变换机构地址变换机构：程序请求访问一页开始页号页表长

36、度越界中断YesCPU检索快表页表项在快表中?访问表页页在内存中?缺页中断修改快表修改访问位和修改位形成物理地址结束YesYes中断返回第四章 存 储 器 管 理 缺页中断处理保护CPU现场从外存中找到缺页内存满否？选择一页换出该页是否修改过？将该页写回外存OS命令CPU从外存读取缺页启动I/O硬件将一页从外存换入内存修改页表中断结束返回恢复CPU现场YesYes第四章 存 储 器 管 理 4.6.2 页面分配进程物理块分配：保证进程能正常运行最小物理块数确定。为每个进程分配物理块：固定或可变。对进程分配物理块数的算法。最小物理块：保证进程能正常运行的最少 块数，与硬件的结构有关：对于单地址指

37、令、直接寻址方式：最少物理块数为2。指令页和数据页；允许间接寻址至少3块。第四章 存 储 器 管 理 页面分配和置换策略：固定分配 局部置换可变分配 全局置换 固定分配局部置换：分配给进程的物理块数固定、置换也是从进程的物理块(局部)中选择换出。可变分配全局置换：分配给进程的物理块根据进程的缺页情况变化、换出块从系统所有进程(全局)选择。可变分配局部置换：分配给进程的物理块根据今年成的缺页情况变化、置换从进程的物理块中选择(局部)第四章 存 储 器 管 理 分配算法分配算法分配算法有：平均分配、按比例分配、考虑优先权分配。平均分配：根据系统总块数和当前的进程数平均分配。按比例分配：按每个进程的

38、页面数分配物理块。 bk=(Sk/Si)*Mbk -第k个进程分配的块数。Sk -第k个进程分配的页面数。Si -目前所有进程的页面数之和。M-内存的总物理块数。考虑优先权分配策略：给予重要、紧急的任务更高的优先权、更大的内存空间。第四章 存 储 器 管 理 页面调入策略页面调入策略需要考虑：何时调入页面、从何处调入页面、如何操作。何时调入页面：请求调页(demand paging)：只调入发生缺页时所需的页面。优点：容易实现。缺点：对外存I/O次数多，开销较大预调页(prepaging)：在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。优点：提高调页的I/O效率。缺点：基于预测，若调

39、入的页在以后很少被访问，则效率低。常用于程序装入时的调页。第四章 存 储 器 管 理 从何处调页从何处调页请求分页系统中外存分：文件区和对换区。因此缺页调入内存有三种情况：当对换区空间足够时：运行前把进程有关的文件拷贝到对换区，运行过程直接从对换区调入所需的页面。当对换区空间不足时，凡是不会被修改的文件，直接从文件区调入。UNIX方式：与进程有关的文件放在文件区；因此未运行过的页面，都从文件区调入；而运行过程中换出的页面，放入对换区，以后从对换区调入。第四章 存 储 器 管 理 页面调入过程页面调入过程进程所需的页面不在内存向CPU发出缺页中断转中断处理程序中断处理程序中断处理程序保留CPU环

40、境分析中断原因转缺页中断恢复CPU环境中断处理结束继续执行缺页中断处理程序缺页中断处理程序查找页表获得该页的外存物理块号内存满否？从外存把缺页调入内存修改页表按照页面置换算法，找到换出的页面该页被修改过？写入快表缺页中断处理结束修改页表YesYes先把换出页面写入磁盘第四章 存 储 器 管 理 4.7 页面置换算法页面置换算法页面置换算法：选择换出页面的算法。重要性：页面置换算法选择不当，将导致进程发生“抖动”；即刚换出的页面很快又被重新调入，产生某进程频繁地换进、换出。常见的置换算法：最佳置换算法先进先出置换算法最近最久使用置换算法最少使用置换算法页面缓冲算法等等第四章 存 储 器 管 理

41、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 引用率707701701

42、22010320304243230321201201770101页框(物理块）203图 4-25 利用最佳页面置换算法时的置换图 第四章 存 储 器 管 理 2. 先进先出先进先出(FIFO)页面置换算法页面置换算法 引用率70770170122010323104430230321013201770201页框2304204230230127127011总是把最先进入内存的页面淘汰出去可以通过链表来表示各页的建立时间先后。性能较差。较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出。并且有Belady现象。第四章 存 储 器 管 理 Belady现象：采用FIFO算法时，如

43、果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。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次

44、；FIFO123412512345页 0123412555344页 112341222533页 21234111255缺 页xxxxxxxxX第四章 存 储 器 管 理 如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；FIFO123412512345页 0123444512345页 112333451234页 21222345123页 3111234512缺 页xxxxxxxxxx第四章 存 储 器 管 理 4.7.2 最近最久未使用最近最久未使用(LRU)置换算法置换算法 1. LRU(Least Recently Used)置换算法的描述置换算法的描述 图 4-27 L

45、RU页面置换算法 引用率70770170122010320304403230321132201710701页框402432032102选择内存中最久未使用的页面被置换。第四章 存 储 器 管 理 2. LRU置换算法的硬件支持置换算法的硬件支持 1) 寄存器寄存器每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。R=Rn-1Rn-2Rn-3 R2R1R0 这是局部性原理的合理近似，性能接近最佳算法。但由这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。于需要记录页面使用时间的先后关系，硬件

46、开销太大。第四章 存 储 器 管 理 图 4-28 某进程具有8个页面时的LRU访问情况 第四章 存 储 器 管 理 2) 栈栈 图 4-29 用栈保存当前使用页面时栈的变化情况 4474707407047170410174010741210742120741210742621076把被访问的页面移到栈顶，于是栈底的是最久未使用页面。第四章 存 储 器 管 理 4.7.3 轮转算法(clock)每页有一个使用标志位(use bit)，若该页被访问则置user bit=1。置换时采用一个指针，从当前指针位置开始按地址先后检查各页，寻找use bit=0的页面作为被置换页。指针经过的user bi

47、t=1的页都修改user bit=0，最后指针停留在被置换页的下一个页。也称最近未使用算法(NRU, Not Recently Used)，它是LRU(最近最久未使用算法)和FIFO的折衷。1. 简单的简单的Clock置换算法置换算法 第四章 存 储 器 管 理 图 4-30 简单Clock置换算法的流程和示例 入口查寻指针前进一步，指向下一个表目页面访问位0?选择该页面淘汰是返回置页面访问位“0”否块号页号访问位指针0124034215650711替换指针第四章 存 储 器 管 理 State of buffer just prior to a page replacement0123456

48、78n.Page 9use = 1Page 19use = 1Page 1use = 0Page 45use = 1Page 191use = 1Page 556use = 0Page 13use = 0Page 67use = 1Page 33use = 1Page 222use = 0next frame pointer第四章 存 储 器 管 理 State of buffer just afterthe next page replacement012345678n.Page 9use = 1Page 19use = 1Page 1use = 0Page 45use = 0Page 19

49、1use = 0Page 727use = 1Page 13use = 0Page 67use = 1Page 33use = 1Page 222use = 0第四章 存 储 器 管 理 2. 改进型改进型Clock置换算法置换算法 由访问位A和修改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。 2类(A=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。 3类(A=1, M=0)： 最近已被访问， 但未被修改， 该页有可能再被访问。 4类(A=1, M=1): 最近已被访问且被修改， 该页可能再

50、被访问。 第四章 存 储 器 管 理 其执行过程可分成以下三步： (1) 从指针所指示的当前位置开始， 扫描循环队列， 寻找A=0且M=0的第一类页面， 将所遇到的第一个页面作为所选中的淘汰页。 在第一次扫描期间不改变访问位A。 (2) 如果第一步失败，即查找一周后未遇到第一类页面， 则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。 (3) 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。 然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。

51、 第四章 存 储 器 管 理 1.最少使用置换算法(LFU, Least Frequently Used)选择到当前时间为止被访问次数最少的页面被置换；每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；4.7.4 其它置换算法其它置换算法 第四章 存 储 器 管 理 2. 页面缓冲算法(page buffering)被置换页面的选择和处理：用FIFO算法选择被置换页，把被置换的页面放入两个链表之一。如果页面未被修改，就将其归入到空闲页面链表的末尾否则将其归入到已修改页面链表。它是对FIFO算法的发展，通过被置换页面的缓冲，有机

52、会找回刚被置换的页面；第四章 存 储 器 管 理 需要调入新的物理页面时，将新页面内容读入到空闲页面链表的第一项所指的页面，然后将第一项删除。空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，只需较小开销，而被访问的页面可以返还作为进程的内存页。当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表，这样能大大减少I/O操作的次数。第四章 存 储 器 管 理 4.7.5 请求分页系统的性能分析请求分页系统的性能分析一、缺页率对有效访问时间的影响： 一般内存的访问时间ma在10ns到数百ns之间。而访问外存要寻道时间、旋转时间、数据转送时间，一般在24

53、ms。考虑缺页概率为p，则：有效访问时间=(1-p) ma + p 缺页中断时间ma按100ns计算; 缺页中断时间： (1)缺页中断服务时间；(2)将缺页读入的时间；(3)进程重新执行的时间。总计约25ms，因此有效访问时间=(1-p) 0.1+p25000=0.1+24999.9p可见：p 有效访问时间 ，磁盘速度 有效访问时间 。第四章 存 储 器 管 理 例题现有一请求页式系统，页表保存在寄存器中。若有一个可用的空页或被置换的页未被修改，则它处理一个缺页中断需要8ms；若被置换的页已被修改，则处理一缺页中断因增加写回外存时间而需要20ms，内存的存取时间为1s。假定70%被置换的页被修改过，为保证有效存取时间不超过2s，可接受的最大缺页中断率是多少？第四章 存 储 器 管 理 二、工作集二、工作集工作集：指在某段时间间隔内，进程要访问的页面的集合。要使程序有效的运行且产生缺页较少，就必须使程序的工作集全部在内存。由于无法预知程序在不同时刻将访问哪些页面，因此只能根据程序过去某段时间内的行为来表示