第四章 存储管理

4.1

存储器工作原理

4.2连续存储空间管理4.3分页式存储管理4.4分段式存储管理4.5虚拟存储管理第四章存储管理如何对存储器加以有效的管理，不仅直接影响到存储器的利用率，而且还对系统性能有重大影响。存储器管理的主要对象是内存。存储管理的功能:分配和去配、抽象和映射、隔离与共享、存储扩充。4.1.1存储器的层次寄存器高速缓存主存储器磁盘缓存固定磁盘可移动存储介质4.1

存储器访问速度往上越高容量越往下越大如何将一个用户源程序变成一个可在内存中执行的程序，通常要经过3步骤：编译:由编译程序（Compiler）将用户源代码编译成若个目标模块（ObjectModule）。链接:由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块。装入:由装入程序（Loader）将装入模块装入内存。-程序的装入和链接4.1.2地址转换与存储保护编辑―――编译―――链接―――装入―――运行1.程序编译源程序经过编译程序或汇编程序的处理来获得多个目标模块处理时编译程序负责记录模块内引用的发生位置目标模块附有供引用使用的内部符号表和外部符号表符号表给出了各个符号名及在本目标模块中的名字地址，在模块被链接时进行转换2.程序链接1)静态链接:在程序装入之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。2)装入时动态链接:这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。a.便于修改和更新b.便于实现对目标模块的共享3)运行时动态链接:这是指对某些目标模块的链接，是在程序执行中需要该(目标)模块时，才对它进行的链接。模块Aifx>1CALLB;elseCALLC;RETURN模块BCALLC;RETURN模块CRETURN0L-10M-10N-1(a)目标模块模块Aifx>1JSRL;elseJSRL+M;RETURN模块BJSRL+M;RETURN模块CRETURN0L-1LL+M-1L+ML+M+N-1(b)装入模块三种装入方式：绝对装载方式、可重定位装载方式、动态运行时转载方式。1、绝对装载：编译后，装入前已产生了绝对地址（内存地址），装载时不再作地址重定位。绝对地址的产生：（1）由编译器完成，（2）由程序员编程完成。对（1）而言，编程用符号地址。

程序每次必须装入同一内存区；程序员必须事先了解内存的使用情况，根据内存情况确定程序的逻辑地址；程序的修改将引起整个程序中指令地址的变动；程序所有的存储引用（函数调用），在装入之前都必须转换为物理地址，这不利于存储共享。3.程序转载2、可重定位装载方式

(静态地址重定位)目标模块的起始地址通常是从0开始的，程序中的其它地址也都是相对于起始地址计算的。由装载程序将装载模块装入内存后，装载模块中程序所访问的所有逻辑地址与实际装载内存的物理地址不同，必须进行地址映射，将逻辑地址转换为物理地址。静态重定位技术：地址映射在程序装载时进行，以后不再更改程序地址。0100025005000LOAD1,2500LOAD1,1250036536510000110001250015000目标模块装入内存LOADj365符号地址相对地址绝对地址装入模块j3.动态重定位在程序运行时动态进行程序的地址转换。硬件的支持，即重定位寄存器，用于保存程序的在内存中的起始地址。能保证进程的可移动性，有效的提高内存的使用效率。运行时重定位有利于多道程序环境下，进程的换进/换出及实现紧凑技术。load1,2500365load1,25003650100250050002500500005000050100+5250055000作业J处理机一侧存储器一侧重定位寄存器(分区首地址寄存器)相对地址4.2.1固定分区存储管理4.2.2可变分区存储管理

4.2.3伙伴系统4.2.4主存不足的存储管理技术4.2连续存储管理4.2.1固定分区存储管理分区管理：是一种简单使用的存贮管理方案，把内存空间静态的（动态的）分割成若干大小可以不等的区域，每个作业分配一片连续的存储空间，程序一次整体装入固定式分区管理：将内存空间静态的分割成若干大小可以不等的区域，每个分区只能装入一道作业，分区的个数是内存中作业的最大道数操作系统区用户分区1用户分区2用户分区3固定分区存储管理(续)划分分区的方法：分区大小相等：将内存分割成若干个大小相等的区（太大造成内存的浪费，太小不能装入进程运行，缺乏灵活性）分区大小不等：一部分大的一部分小的，一部分适中的注意：一个分区分配了一个作业后剩余空间便不能再用，这称为内碎片；当一个区域小于一个作业时便整块被丢弃，称为外碎片为了记住哪些分区是空闲分区，哪些分区是已分配分区，系统可设置如下主存分配表：分区号大小(KB)起址(KB)状态1824已分配21632已分配33248已分配46480未分配5128144已分配操作系统作业A(7K)作业B(13K)作业C(23K)空闲分区作业D(80K)24K32K48K144K272K~~80K分区描述表内存分配情况碎片固定分区存储管理(续)缺点：固定分区存储管理限制了程序的大小,无法运行超过分区大小的程序内存空间利用率不高不便于程序动态扩充内存限制了程序道数固定分区存储管理适合于程序大小和出现频率已知的情形4.2.2可变分区存储管理按照作业的大小来划分分区，划分的时间、大小和位置都是动态的。系统启动后用户作业装入内存之前，整个用户区是一个大的空闲分区，随着作业的装入和撤离，内存空间被分成许多大小不一的分区，有的分区正被作业占用，有的分区是空闲的。当一个新的作业要求装入时，必须找到一个足够大的空闲区，如果找到的空闲分区大于作业需要量，则把该空闲分区分成两部分，一部分分配给作业，另一部分作为一个较小的空闲分区。当一个作业运行结束时，它归还的分区如果与其它空闲分区相邻，则还要进行合并，形成一个大的空闲分区。一、分区组织1．空闲分区表：在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。2．空闲分区链：为了实现对空闲分区的分配和链接，设置前向指针和后向指针，通过前、后向链接指针将所有的空闲分区链接成一个双向链。前向指针分区信息N个字节可用后向指针系统区A(8K)B(16K)C(20K)D(28K)E(56K)F(2K)G(40K)..024K32K48K68K96K152K154K194K256kA、B、C、D、E、F、G任务陆续进入内存进行执行，T0时刻，A、C、E、G已经完成，请画出当前时刻空闲分区表。如果此时有来了一个15K大小H任务，会分在哪个空闲分区里面。分区号大小(KB)起址(KB)状态1824未分配22048未分配35696未分配440154未分配562194未分配空闲分区表1．最先适应算法（首次适应算法）。每次都从头开始，寻找第一个满足需求的空闲分区。特点：找到第一个大小满足的分区，划分。有碎片（外零头），低址内存使用频繁。2．下次首次适应算法（循环首次适应算法）。与1类似，从上次找到的空闲分区的下一个开始查找。特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区3．最佳适应算法（最优适应算法）分区按大小递增排序；分区释放时需插入到适当位置。特点：产生无法利用的小碎片。4.最坏适应算法扫描整个空闲分区表或空闲分区链,总是挑选一个最大的空闲区分割给作业使用特点：分割剩余的空闲区不至于太小二、分区分配当进程运行完毕释放内存时，需合并相邻的空闲分区，形成大的分区，称为合并技术。（1）上邻空闲区：合并，改大小（2）下邻空闲区：合并，改大小，首址。（3）上、下邻空闲区：合并，改大小。（4）不邻接，则建立一新表项。三、分区回收进程1F1回收区进程2进程3进程1进程2回收区F2进程3进程1F1回收区F2进程2内存回收时的情况F1进程1回收区进程2F22.地址转换与存储保护可变分区方式采用动态重定位装入作业,作业程序和数据的地址转换由硬件完成.硬件设置两个控制寄存器:基址寄存器和限长寄存器.基址寄存器存放分配给作业使用的分区的起始地址,限长寄存器存放作业占用的连续存储空间的长度当作业占有CPU运行时,操作系统把作业所占分区的始址和长度送入基址寄存器和限长寄存器.随着逐条指令的执行和数据访问完成地址转换当逻辑地址小于限长值时，可获得绝对地址，大于时，不允许访问基址基址寄存器逻辑地址CPU绝对地址操作系统区空闲分区1用户作业1空闲分区2限长限长寄存器<限长越界中断动态分区特点系统初启时，整个内存只有一个自由块需调入一个作业时，查找所有的自由块直到找到一个满足要求的并把它分给该作业当自由块较大以至满足一个作业的需求后仍有剩余则将剩余量构成一个新的自由块交给系统当一个作业运行完毕并释放了其所得到的空间时，要考虑它上下是否邻接自由块，若有合并它们为一个较大的自由块解决了内碎片的问题，但会产生很多较小的外碎片（相对的概念）固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，l≤k≤m，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。4.2.4动态分区的实例——伙伴系统当需要为进程分配一个长度为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的空闲分区，依此类推。在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。与前面所述的多种方法相比较，由于该算法在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比前面所述的分类搜索算法差，但比顺序搜索算法好，而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。当一个新的作业要求装入,没有一个空闲分区能够满足要求,但所有空闲分区之和能够满足要求时,可以移动内存作业,合并这些小的空闲分区,使之满足新来的作业。作业移动后,要及时修改它们的基址。操作系统作业1空闲区作业2空闲区作业3空闲区操作系统作业1作业2作业3空闲区操作系统作业1作业2作业3空闲区作业44.2.3主存不足的存储管理技术-移动技术

对换的引入将阻塞进程，暂时不用的程序、数据换出。将具备运行条件的进程换入。类型：整体对换：进程对换，解决内存紧张部分对换：页面对换/分段对换：提供虚存支持对换空间管理外存对换区比文件区侧重于对换速度。因此，对换区一般采用连续分配。采用数据结构和分配回收类似于动态分区分配。4.2.3主存不足的存储管理技术-对换技术连续分配引起:碎片离散分配方式分页存储管理将一个进程的逻辑地址空间分成若干个大小相等的页面，把内存空间分成与页面相同大小的若干个存储块，称为页框，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的页框中。分段存储管理作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。每个段都有自己的名字。每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。段页存储管理是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。4.3.1分页式存储管理的基本原理4.3.2快表4.3.3分页式存储空间的分配和去配4.3.4分页式存储空间的页面共享和保护4.3.5多级页表4.3分页存储管理4.3.1分页式存储管理的基本原理将一个进程的逻辑地址空间分成若干个大小相等的区，称为页面或页，相应地，也把内存空间分成与页面相同大小的若干个存储块，称为页框，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的页框中。对页框和页面都加以编号，从0开始，如第0号、第1号等由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”或称为“内零头”。1.页面页面和页框：逻辑空间和内存空间由机器的地址结构决定页太大，页内碎片大。页太小：页表可能很长，换入/出效率低2.地址结构

31 1211 0逻辑地址A；页大小L(设为4096)；页内偏移d P=(int)A/Ld=AmodL如：A＝8210B.则P=2,d=18分页存储管理页号P页内位移d3、页表0页1页2页3页4页5页n页02132638495n0123456789用户程序页表页面号页框号内存地址转换由页表完成逻辑页号—物理页框号的映射。一、基本地址变换机构： 越界保护每个进程对应一页表，其信息（如长度、始址）放在PCB中，执行时将其首地址装入页表寄存器。二、地址转换的过程进程运行前系统把页表基址存入页表基址寄存器运行时硬件自动将逻辑地址分成两部分，页号P和页内位移d找到页表基址后，按页号P作为索引查页表，得到页框号，根据公式完成地址转换物理地址=页框号×块长+页内位移分页系统地址转换页表始址页表长度＋页号(3)页内地址(342)页表寄存器逻辑地址(12630)＜越界中断5页框号页表页号0123物理地址68155页号012368154.3.2快表由于页表放在内存中，这样，CPU每存取一个数据时，需要两次访问内存一次访问页表取得物理块号以形成物理地址第二次根据物理地址存取数据,速度降低了一倍为了提高速度,在存储管理部件中增设一个专用的高速缓冲存储器,用来存放最近访问过的部分页表,这种相联存储器称为快表；快表昂贵，不易过多。如Intel80486的快表为32个单元具有快表的分页系统地址转换页表始址页表长度＋页号(2)页内地址(342)页表寄存器逻辑地址＜越界中断5页框号页表页号0123物理地址6815相联存储器快表501268页框号页号有了快表,根据页号查找对应的物理块号时：首先查找快表，若找到则将物理块号和页内地址（也是块内地址）拼接形成物理地址若在快表中未找到物理块号，则再查找内存页表，获取物理块号，一方面形成物理地址，另一方面将该表项抄到快表中，以备下次再次访问该页面有的系统查快表和查内存页表是同时进行的，一旦从快表中找到了对应项，则立即停止对内存页表的查找当快表已满且要登记新页时，需要淘汰旧快表项，最简单的策略是“先进先出”

例：有一分页式系统，其页表存放在主存中：①如果对主存的一次存取需要10ns,试问实现一次页面访问的存取时间是多少?②如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间为2ns,试问此时的存取时间是多少?答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。■页表在主存的存取访问时间

=10*2=20(ns)■增加快表后的存取访问时间

=0.85*12+(1-0.85)*（2+10*2）=13.4(ns)4.3.3分页式存储空间的分配和去配位示图由一些二进制位组成,每一位对应一个内存物理块,位值表示所对应的物理块是否已分配出去.分配和回收物理块时只需修改位值即可链表方法1111100011111111110011111100011100000001111111111100000011111111111000000114.3.4分页式存储空间的共享与保护分页存储管理在实现共享时,必须区分数据共享和程序共享,实现数据共享时,允许不同的作业对共享的数据页使用不同的页号,只要让各自页表中的有关表目指向共享的数据信息块就行了实现程序共享时,由于页式存储结构要求逻辑地址空间是连续的,所以程序运行前它们的页号就确定了.对共享的程序必须规定一个统一的页号.当共享程序的作业数增多时,要规定一个统一的页号是困难的实现信息保护的办法是在页表中增加一些标志位,用来指出该页的信息可读/写\只读\只可执行\不可访问等4.3.5

多级页表现代的大多数计算机系统，都支持非常大的逻辑地址空间(232~264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4KB，则在每个进程页表中的页表项可达1兆个之多，又因为每个页表项占用4个字节，故每个进程仅仅其页表就要占用4MB的内存空间，而且还要求是连续的。多级页表（续）多级页表实现方法

（1）把整个页表进行分页，分成一张张小页表(称为页表页或页目录表)，小页表的大小与页框相同，为进行索引查找，为这些小页表建一张页目录表，其表项指出小页表所在页框号及相关信息（2）系统为每个进程建一张页目录表，它的每个表项对应一个页表页，而页表页的每个表项给出了页面和页框的对应关系,页目录表是一级页表，页表页是二级页表（3）逻辑地址结构有三部分组成：页目录、页表页和位移

B

offset目录位移页表页位移

页内位移BF进程一级页表进程二级页表物理地址逻辑地址页目录表控制寄存器4.4.1程序分段结构4.4.2分段式存储管理的基本原理4.4.3段的共享和保护4.4.4分段和分页的比较4.4分段式存储管理基于模块化的程序设计，通常将一个大任务分成若干个相对独立的子任务，对应于子任务编写子程序，称为段。各个子程序可以独立的编辑、编译、链接和执行各个子程序由实现的功能决定，长度各不相同。执行时，根据实际需要将各个子程序链接成一个大程序。4.4.1

程序分段结构-分段存储管理的引入4.4.2分段式存储管理的基本原理

段号

段内偏移量在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。每个段都有自己的名字。每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间，由于是分成多个段，因而是二维的，亦即，其逻辑地址由段号（段名）和段内地址所组成。分段地址中的地址具有如下结构：作业空间（MAIN)=0030k（X)=1020k（D)=2015k（S)=3010k内存空间30k40k20k80k15k120k10k150k段长段首址段号0123段表段表：为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。段表始址段表长度＋段号（2)100段表寄存器逻辑地址＜越界中断122980物理地址分段系统地址变换机构＋30k40k20k80k15k120k10k150k段长段首址段号0123段表例题对以下段表,请将逻辑地址(0,137),(1,4000),(2,3600),(5,230)转换成物理地址.段号起始地址段长050K10KB160K3KB2120K5KB370K8KB4150K4KB4.4.3

段的共享和保护段的共享是通过不同作业段表中的项指向同一个段基址来实现的于是，几道作业共享的程序就可放在一个段中，只要让各道作业的共享部分有相同的基址/限长值就可以了必须对共享段的信息进行存取控制和保护ed1ed2…ed40data1_1…data1_10021122……40604161……5070…ed1ed2…ed40data1_1…data1_10data2_1…data2_10进程1进程2页表页表ed1ed2…ed40data2_1…data2_10主存分页系统中共享editor021122……40604161……分段系统中共享editoreditordata1editordata2段长基址1608040240段长基址1608040380editordata1…data2在分段系统中，实现共享则容易得多，只需在每个进程的段表中为文本编辑程序设置一个段表项。进程1进程2段表4.4.4分段和分页的比较分段是信息的逻辑单位，由源程序的逻辑结构所决定,用户可见；分页是信息的物理单位，与源程序的逻辑结构无关，用户不可见。段长可根据用户需要来规定，段起始地址可从任何主存地址开始；页长由系统确定，页面只能以页大小的整倍数地址开始。分段方式中,源程序(段号,段内位移)经连结装配后地址仍保持二维结构;分页方式中,源程序(页号,页内位移)经连结装配后地址变成了一维结构思考在分页存储管理中,其逻辑地址空间是__维的.在分段存储管理中,其逻辑地址空间是__维的.在没有快表的情况下,分页系统每访问一次数据,要访问__次内存;分段系统每访问一次数据,要访问__次内存.在分页系统中为实现地址变换而设置了页表寄存器,其中存放了__和__.程序未运行时,这些信息保存在__中.页表中的基本数据项是__,段表中的基本数据项是__和__.把逻辑地址分成页号和页内地址是由__进行的,所以分页系统的作业地址空间是__维的.把逻辑地址分成段号和段内地址是由__进行的,所以分段系统的作业地址空间是__维的.思考页表寄存器的值为下面哪些页表有错（）5页框号页号01236815501236815页表始址页表长度464K5页框号页号01276815503468155页框号页号01268501268ABC4.5.1虚拟存储器概念4.5.2请求分页虚拟存储管理4.5.4请求段页式虚拟存储管理4.5虚拟存储管理4.5.1虚拟存储器概念前面介绍的连续的（分区）、离散的（分页和分段）管理均是将程序一次性全部装入内存后才能运行，在下面情况下：（1）一个特别大的作业，不能够一次装入内存（2）有大量作业在外存上等待运行，而又没有足够大的内存容纳这些作业，只能将少量作业装入内存运行，大量的作业在外存上等待解决办法：（1）可以从物理上扩大内存（2）逻辑上扩充内存，即虚拟内存技术局部性原理C++程序示例局部性原理程序执行的局部性是指在一段时间内，程序访问的存储空间仅限于某个区域（这称为空间局部性），或者最近访问过的程序代码和数据很快会再被访问（这称为时间局部性）。第一，程序中只有少量分支和过程调用，大都是顺序执行的指令。第二，程序包含若干循环，是由相对较少的指令组成，在循环过程中，计算被限制在程序中很小的相邻部分中。第三，很少出现连续的过程调用，相反，程序中过程调用的深度限制在小范围内，一段时间内，指令引用被局限在很少几个过程中。第四，对于连续访问数组之类的数据结构，往往是对存储区域中相邻位置的数据的操作。第五，程序中有些部分是彼此互斥的，不是每次运行时都用到的，如出错处理程序。虚拟存储系统思想基于局部性原理，程序在运行之前，没有必要全部装入内存，将将要运行的少数先装内存便可开始运行,其余部分留在磁盘上。运行时，要访问的如果已调入内存，继续运行；如果未调入，通过操作系统“部分装入”，再运行。如果内存已满，用“部分替换”功能，将内存中暂时不用的部分调到磁盘上，把要访问的调入。大的用户程序在较小的内存空间运行。更多的作业并发执行。用户角度看,系统所具有的内存容量,将比实际内存容量大得多。虚拟存储器的定义在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分对换功能，为用户提供一个比物理内存容量大得多的，可寻址的“内存储器”。虚拟存储器的容量取决于计算机的地址结构和可用的物理内存和外存的容量之和。逻辑地址空间处理器虚拟地址存储管理部件物理地址主存辅存物理地址空间虚拟存储管理的概念（续）实现虚拟存储器必须解决好以下有关问题：主存辅存统一管理问题逻辑地址到物理地址的转换问题部分装入和部分对换问题虚拟存储器的实现方法主要有：请求分页式虚拟存储管理请求段页式虚拟存储管理4.5.2请求分页虚拟存储管理1.请求分页式虚拟存储的硬件支撑2.请求分页虚拟存储的基本原理3.交换区4.页面装入策略和清除策略5.页面分配策略6.缺页中断率7.页面替换策略8.请求分页虚拟存储管理的几个设计问题1.请求分页式虚拟存储管理的硬件支撑

存储管理部件--MMU①管理硬件页表寄存器：负责装入将要占用处理器的进程的页表②分解逻辑地址为页号和页内地址③管理快表：查找快表、装入表目和清除表目④访问页表⑤当要访问的页面不在内存时发出缺页中断，页面访问越界时发出越界中断⑥管理特征位：设置和检查页表中的状态位、访问字段、修改位、保护权限等2.请求分页系统的基本原理在进程开始运行之前，不是装入全部页面，而是装入一个或几个页面，进程运行过程中，访问的页面不在内存时，再装入所需页面；若内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面怎样才能发现页面不在内存中呢?怎样处理这种情况呢?采用的办法是：扩充页表的内容，增加驻留标志位和页面辅存的地址等信息页号页框号驻留位P引用位U修改位M外存地址是否已调入内存被访问次数或多长时间未被访问，供选择换出页面时参考是否被修改过,页面置换时参考外存上的地址,调入时参考页表机制逻辑地址空间主存(用户区)CPU逻辑地址快表主存(系统区)运行进程页表辅存缺页中断处理①分解地址③⑤访问MMU②查快表③命中④不命中⑤页表命中⑦发缺页中断⑧调页⑨装入、改表④查页表运行进程页表基址⑥装入快表运行进程映象进程切换时装入物理地址页框页内地址页号页内地址请求分页的地址变换过程查快表有登记无登记查页表登记入快表发缺页中断在主存在辅存形成绝对地址继续执行指令重新执行被中断指令恢复现场调整页表和主存分配表装入所需页面主存有空闲块保护现场有选择调出页面该页是否修改未修改已修改把该页写回辅存相应位置操作系统-缺页中断处理程序硬件MMU逻辑地址无①②③④3.交换区

操作系统在磁盘上定义一个交换区用来保存临时换出的页面，交换区是物理内存的扩展，它和内存一起组成虚拟存储空间，文件系统不能占用交换区空间。

交换区管理重点是维护交换区映射表，该表用来记录所有被换出内存的页面在交换区中的位置，以便在需要时再次换入内存。当页面第二次被换出内存时，仅当页面修改过（脏页）才写入交换区，否则因已有副本就直接将它丢弃。4.页面装入策略和清除策略页装入策略：请页式调入：在需要访问程序和数据时,才把所在页面装入主存优点是确保只有被访问的页才调入内存，节省了主存空间缺点是处理缺页中断和调页的系统开销较大，每次仅调一页,增加了磁盘I/O次数预调式调入：由系统预测进程将要使用的页面,使用前预先调入主存,每次调入若干页面,而不是仅调一页优点是减少磁盘I/O启动次数，节省寻道和收索时间缺点是可能所调入页面大多未使用，效率低。页面清除策略请页式清除仅当一页选中被替换,且之前它又被修改过,才把这个页面写回辅存预约式清除对所有更改过的页面,在需要之前就把它们都写回外存4.页面装入策略和清除策略(续)5.页面分配策略系统为进程分配主存,需考虑因素:①分给进程的空间越小,同一时间处于内存的进程就越多，至少有一个进程处于就绪态的可能性就越大②如果进程只有小部分在主存里,即使局部性很好,缺页中断率还会增加③分给进程的内存超过一定限度后，再增加内存空间,不会明显降低进程的缺页中断率假设固定分配，运行FORTRAN程序，共有0.25×106次页面引用，页面大小为256个字。分给进程的页框数分别为6、8、10、12和14FIFO所产生的缺页中断基本上是Opt的2倍，Clock则比较接近于LRU0510152025354030068101214分配的页数每千次访问的缺页中断数

FIFO

CLOCK

LRU

OPT页面分配策略固定分配：固定分配使进程在生命周期中保持固定数目的物理块，每个进程物理块的分配方式主要有：平均分配按比例分配考虑优先权的分配可变分配不时重新评价进程的缺页率，增加或减少进程的页框数，以改善系统的总性能。页面替换策略局部替换：局部替换在进程发生缺页时仅从该进程的物理块中淘汰页面,以调入所缺页面全局替换：全局替换则在进程发生缺页时可从系统中任一进程的物理块中淘汰页面页面分配和替换常用的组合策略有三种:固定分配局部置换、可变分配全局置换和可变分配局部置换6.缺页中断率页面替换主存空间已经用完，而又要装入新页时，必须把主存的一些页面调出去，叫页面替换页面淘汰算法确定被淘汰页的算法“抖动”(Thrashing)(“颠簸”)现象是淘汰算法不好而产生的一种现象。刚淘汰的页面又立即要用，又将其调入，然后再淘汰、再调入。浪费大量CPU的时间假定作业p共计n页，系统分配给它的主存块只有m块（１≤m≤n）。如果作业p在运行中成功的访问次数为S，不成功的访问次数（缺页次数）为F，则总的访问次数Ａ为：A=S+F，又定义：f=F/A称f为缺页中断率6.缺页中断率影响缺页中断率f的因素有：(1)主存页框数(2)页面大小(3)页面替换算法(4)程序特性程序要将128×128的数组置“0”。分给的主存只一块，页面尺寸为每页128个字，数组中的元素每行存放在一页中。intA[128][128];for(intj=0;j<128;j++)for(inti=0;i<128;i++)A[i][j]:=0总共产生（128*128－1）次缺页中断intA[128][128];for(inti=0;i<128;i++)for(intj=0;j<128;j++)A[i][j]:=0总共产生（128－1）次缺页中断请求分页虚拟存储管理（续）几种页面替换策略:最佳页面算法(OPT、Belady算法)先进先出页面淘汰算法(FIFO)最近最久未使用页面淘汰算法(LRU)Clock置换算法最佳页面替换算法(OPT)其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳页面置换算法，通常可保证获得最低的缺页率。假定系统为某进程分配了三个页框（物理块），并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1；70770170122010320304243230321201201770101203共缺页中断9次，缺页中断率为9/20=45%;页面替换6次总是淘汰最先进入内存的页面.页面按先后次序链接成一个队列设置一个替换指针,指向最老的页面先进先出（FIFO）页面替换算法70770170122010323104230230321013201771201023430420423012702701共缺页中断15次，缺页中断率为15/20=75%;页面替换12次最近最少使用LRU替换算法访问字段，上次被访问以来所经历的时间t选择t值最大的页面淘汰用“最近的过去”作为“最近的将来”的近似70770170122010320304230321132201710201032403402432107共缺页中断12次，缺页中断率为12/20=60%;页面替换9次1）引用位法方法：每页设置一个引用标志位R，访问某页时，由硬件将页标志位R置1，隔一定时间t将所有页的标志R均清0发生缺页中断处理：从标志位R为0的页中挑选一页淘汰。并将所有页的标志位R清0主要问题：时间间隔t的选择，t太大则标志位R均为1，t太小则标志位R均为0LRU算法的硬件支持2）计数器法方法：每个页面设置一个多位计数器，每当访问一页时，就使它对应的计数器加1。又叫最不常用页面替换算法LFU。发生缺页中断处理：选择计数值最小的对应页面淘汰，并将所有计数器全部清0。LRU算法的硬件支持3）计时法方法：为每个页面设置一个多位计时器，每当页面被访问时，系统的绝对时间记入计时器缺页中断处理：比较各页面的计时器的值，选最小值的未使用的页面淘汰，因为，它是最“老”的未使用的页面。时钟页面替换算法一个页面首次装入主存，其“引用位”置1。主存中的任何页面被访问时,“引用位”置1。淘汰页面时,从指针当前指向的页面开始扫描循环队列，把遇到的“引用位”是1的页面的“引用位”清0,跳过这个页面;把所遇到的“引用位”是0的页面淘汰掉,指针推进一步。扫描循环队列时，如果遇到的所有页面的“引用位”为1，指针就会绕整个循环队列一圈，把碰到的所有页面的“引用位”清0;指针停在起始位置，并淘汰掉这一页,然后，指针推进一步。P9U1P19U1P1U0P45U1P191U1P556U0P13U0P67U1P33U1P222U0

：：下帧指针n012345678一个页替换前的缓冲区状态P9U1P19U1P1U0P45U0P191U0P727U1P13U0P67U1P33U1P222U0n012345678替换一页后的缓冲区状态页框号

：：时钟页面替换算法的改进算法把”引用位”和”修改位”结合起来使用，共组合成四种情况：(1)最近没有被引用,没有被修改(r=0,m=0)(2)最近被引用,没有被修改(r=1,m=0)(3)最近没有被引用,但被修改(r=0,m=1)(4)最近被引用过,也被修改过(r=1,m=1)步1：选择最佳淘汰页面，从指针当前位置开始,扫描循环队列。扫描过程中不改变“引用位”，把找到的第一个r=0,m=0的页面作为淘汰页面。步2：如果步1失败，再次从原位置开始，查找r=0且m=1的页面，把找到的第一个这样的页面作为淘汰页面，而在扫描过程中把指针所扫过的页面的“引用位”r置0。步3：如果步2失败，指针再次回到了起始位置，由于此时所有页面的“引用位”r均己为0，再转向步1操作，必要时再做步2操作，这次一定可以挑出一个可淘汰的页面。时钟页面替换算法的改进算法工作集模型用于模拟实现局部最佳页面替换算法使用滑动窗口，但不向前查看引用串，而是向后看通过考察最近主存需求来估计进程将需要的页框数

进程工作集

在某一段时间间隔内进程运行所需访问的页面集合W(t,△)表示在时刻t-△到时刻t自己所访问的页面集合，它就是进程在时刻t的工作集。变量△称为“工作集窗口尺寸”，工作集所包含的页面数称为“工作集尺寸”工作集替换示例页面引用串与上例相同，△=3。当系统有空闲页框供分配，并在时刻t=0时，初始工作集为（p1，p4，p5），其中，p1在时刻t=0被引用，p4在时刻t=-1被引用，而p5在时刻t=-2时刻被引用。第一次缺页中断发生在时刻t=1，页面p3被装入一个空闲页框，另外3个