1、2011秋季秋季第四章第四章 存储管理之段页式管理存储管理之段页式管理4.2 4.2 分区存储管理分区存储管理4.3 4.3 页式存储管理页式存储管理4.4 4.4 段式存储管理段式存储管理4.5 4.5 段页式存储管理段页式存储管理4.6 4.6 交换技术与覆盖技术交换技术与覆盖技术4.7 4.7 虚拟存储虚拟存储 4.3 页式存储管理 为什么要引进分页技术为什么要引进分页技术?n分区式存储管理：程序要求连续存放，分区式存储管理：程序要求连续存放，会产生会产生碎片碎片问题。大程序进入时需要问题。大程序进入时需要移动移动已在主存中的信息。已在主存中的信息。n分页式存储管理允许把一个作业存放分页
2、式存储管理允许把一个作业存放到若干不相邻接的分区中到若干不相邻接的分区中n免去移动信息免去移动信息n充分利用主存空间充分利用主存空间2011秋季秋季1.用户程序划分用户程序划分 把用户程序按逻辑页划分成大小相把用户程序按逻辑页划分成大小相等的部分，称为页。从等的部分，称为页。从0开始编制页开始编制页号，页内地址是相对于号，页内地址是相对于0编址编址2011秋季秋季逻辑地址逻辑地址 用户程序的划分是由系统自动完成用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的，对用户是透明的。一般，一页的大小为的大小为2的整数次幂，因此，地址的整数次幂，因此，地址的高位部分为页号，低位部分为页的高
3、位部分为页号，低位部分为页内地址内地址页号页号 页内地址页内地址2011秋季秋季0111231页号页号P页内位移量页内位移量W编号编号01048575相对地址相对地址04095逻辑地址：一维2011秋季秋季内存空间：内存空间：按页的大小划分为大小相等的区域，按页的大小划分为大小相等的区域，称为内存块（物理页面，称为内存块（物理页面，页框页框）内存分配：内存分配：以页为单位进行分配，并按作业的以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，页数多少来分配。逻辑上相邻的页，物理上不一定相邻物理上不一定相邻2011秋季秋季.01234560123456作业的作业的地址空间地址空间页框页
4、框（物理块）（物理块）页页号号页页表表主存中页框主存中页框（物理块）（物理块）.2011秋季秋季4.3.3管理管理1.页表：页表：系统为每个进程建立一个页表，页系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的表给出逻辑页号和具体内存块号相应的关系关系 页表放在内存，属于进程的现场信息页表放在内存，属于进程的现场信息2.空块管理空块管理位示图位示图3.内存的分配与回收内存的分配与回收2011秋季秋季0310/10/10/10/10/1017空闲块数空闲块数空块管理空块管理位示图位示图2011秋季秋季计算一个作业所需要的总块数计算一个作业所需要的总块数N查位示图，看看是否还有查位示
5、图，看看是否还有N个空闲块个空闲块如果有足够的空闲块，则页表长度如果有足够的空闲块，则页表长度设为设为N，可填入，可填入PCB中；申请页表区，中；申请页表区，把页表始址填入把页表始址填入PCB依次分配依次分配N个空闲块，将块号和页号个空闲块，将块号和页号填入页表填入页表修改位示图修改位示图2011秋季秋季4.3.4 硬件支持硬件支持1系统设置一对寄存器：系统设置一对寄存器：页表始址寄存器页表始址寄存器 页表长度寄存器页表长度寄存器2相联存储器相联存储器快表快表 快表表项：快表表项：页号；内存块号；标识位；淘汰位页号；内存块号；标识位；淘汰位2011秋季秋季1.基本的地址变换机构基本的地址变换机
6、构 图图 4-12 分页系统的地址变换机构分页系统的地址变换机构 页表寄存器页表始址页表长度页号(3)页内地址逻辑地址L越界中断1块号b页表页号012物理地址32011秋季秋季p页表页表地址越界地址越界L比较比较P=Lpp.快表快表 b+页号页号p p 页内地址页内地址dPd物理地址物理地址页表地址寄存器页表地址寄存器页表长度寄存器页表长度寄存器逻辑地址逻辑地址快表地址映射机制快表地址映射机制存在的问题n当读当读/写数据时，必须访问两次主存。写数据时，必须访问两次主存。n第一次按页号读出页表中相应栏内容的块号第一次按页号读出页表中相应栏内容的块号n第二次根据计算出来的绝对地址进行读第二次根据计
7、算出来的绝对地址进行读/写写n解决方法：利用高速缓存解决方法：利用高速缓存 假定访问主存时间为100毫微秒，访问相联存储器时间为20毫微秒，相联存储器为32个单元时快表命中率可达90%，按逻辑地址存取的平均时间为：（10020）90%(100+100+20)(1-90%)130毫微秒 比两次访问主存的时间100毫微秒2+20220毫微秒下降了四成多。2011秋季秋季4.3.5 页式管理的优缺点页式管理的优缺点优点：解决了碎片问题优点：解决了碎片问题 便于管理便于管理缺点：不易实现共享缺点：不易实现共享 不便于动态连接不便于动态连接思考：页的共享？页的保护？思考：页的共享？页的保护？2011秋季
8、秋季4.3.3 两级和多级页表两级和多级页表 逻辑地址空间逻辑地址空间(232264)。页表就变得非常大，要。页表就变得非常大，要占用相当大的连续的内存空间。占用相当大的连续的内存空间。eg:32位逻辑地址空间的分页系统，规定页面大位逻辑地址空间的分页系统，规定页面大小为小为4 KB即即212 B，则在每个进程页表中的页表项可，则在每个进程页表中的页表项可达达1兆个之多。解决办法：兆个之多。解决办法：1、采用离散分配方式。解决难以找到一块连续的采用离散分配方式。解决难以找到一块连续的大内存空间的问题；大内存空间的问题；2、只将当前需要的部分页表、只将当前需要的部分页表项调入内存，项调入内存，其
9、余的页表项仍驻留在磁盘上，需要其余的页表项仍驻留在磁盘上，需要时再调入。时再调入。2011秋季秋季1.两级页表两级页表(Two-Level Page Table)逻辑地址结构可描述如下：逻辑地址结构可描述如下：为了解决页表需要连续存储空间的问题，将页表离散的放入内存，然后建立一个页表的页表（连续存储在外存中），用以标识页表放在内存中的位置。同时逻辑地址也变成了如上的表示（一维）2011秋季秋季图图 4-14 两级页表结构两级页表结构 101110780121742n第0页页表1460121023第1页页表114115011023外部页表012345671141151468第n页页表146801
10、21023内存空间2011秋季秋季图图 4-15 具有两级页表的地址变换机构具有两级页表的地址变换机构 外部页号P1P2外部页内地址页内地址d逻辑地址外部页表寄存器外部页表db页表页表物理地址2011秋季秋季页目录地址页目录地址目录位移目录位移页表位移页表位移页位移页位移虚拟地址虚拟地址页表地址页表地址.页目录（每进程一个）页目录（每进程一个）块号块号.页表页表代码或数据代码或数据.内存块内存块二级页表结构及地址映射二级页表结构及地址映射+2011秋季秋季段号段号单元号单元号4.4.1基本思想基本思想l 一个程序的各个段离散存放l 段式存储管理 单个段的存储基于可变分区存储管理 实现，占据连续
11、的内存存储空间l 段页式存储管理 单个段的存储基于页式存储管理实现4.4分段式存储管理2011秋季秋季.0S工作区段工作区段B主程序段主程序段M.0EP子程序段子程序段X0K.CALL X E.CALL Y FCALL A 116.0FL子程序段子程序段Y0116N数组数组A12345.2011秋季秋季操作系统操作系统.B0SA0NY0LX0PM0K逻辑段号逻辑段号01234作业作业1的地址空间的地址空间10003200500060008000PKSLN主存主存K 3200P 1500L 6000N 8000S 5000长度长度 段地址段地址01234操作系统操作系统2011秋季秋季用户程序划
12、分用户程序划分 按程序自身的逻辑关系划分为若干个按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，程序段，每个程序段都有一个段名，且有一个段号。段号从且有一个段号。段号从0开始，每一开始，每一段也从段也从0开始编址，段内地址是连续开始编址，段内地址是连续的的2011秋季秋季逻辑地址逻辑地址内存划分内存划分 内存空间被动态的划分为若干个长度内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物不相同的区域，这些区域被称为物理段，每个物理段由起始地址和长理段，每个物理段由起始地址和长度确定度确定段号 段内地址2011秋季秋季内存分配内存分配 以段为单位分配内存，每一个段在内以
13、段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间需要多少分配多少），但各段之间可以不连续存放可以不连续存放2011秋季秋季4.4.2 管理管理段表：段表：它记录了段号，段的首（地）址和长度之它记录了段号，段的首（地）址和长度之间的关系间的关系 每一个程序设置一个段表，放在内存每一个程序设置一个段表，放在内存 属于进程的现场信息属于进程的现场信息段号段号012段首址段首址段长度段长度58K20K100K110K260K140K2011秋季秋季空闲块管理：空闲块管理：记录了空闲区起始地址和长度记录了空闲区起始地址和长度内存
14、的分配算法：内存的分配算法：首先适配；最佳适配；最坏适配首先适配；最佳适配；最坏适配2011秋季秋季4.4.3 硬件支持硬件支持系统设置一对寄存器系统设置一对寄存器段表始址寄存器：段表始址寄存器：用于保存正在运行进程的段表的始址用于保存正在运行进程的段表的始址段表长度寄存器：段表长度寄存器：用于保存正在运行进程的段表的用于保存正在运行进程的段表的长度（例如上图的段表长度为长度（例如上图的段表长度为3）2011秋季秋季 Cl Cb+段号段号S S 段内地址段内地址d比较比较比较比较b +d段段表表S=Cl快表快表物理地址物理地址段表始址寄存器段表始址寄存器段表长度寄存器段表长度寄存器逻辑地址逻辑
15、地址lb.Slb地址越界地址越界d=1d=1地址映射及存储保护机制地址映射及存储保护机制地址越界地址越界地址越界地址越界比较比较L:为段长，注意与分页的区别2011秋季秋季 介于内存与寄存器之间的存储机制，介于内存与寄存器之间的存储机制，它又叫快表它又叫快表用途：保存正在运行进程的段表的子用途：保存正在运行进程的段表的子集（部分表项）集（部分表项）特点：按内容并行查找特点：按内容并行查找相联（联想）存储器（相联（联想）存储器（associative memory）TLB（Translation lookaside buffers）2011秋季秋季引入快表的作用：引入快表的作用：为了提高地址映射
16、速度为了提高地址映射速度 快表项目：段号；段始址；段长度；快表项目：段号；段始址；段长度；标识（状态）位；访问位（淘汰位）标识（状态）位；访问位（淘汰位）快表淘汰问题？快表淘汰问题？（淘汰机制）（淘汰机制）2011秋季秋季4.4.3 信息共享信息共享 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的示意图的示意图
17、2011秋季秋季图图 4-19 分段系统中共享分段系统中共享editor的示意图的示意图 editor进程1data 1进程2editordata 2段表段长基址16080402401608040380editordata 1data 2802402803804202011秋季秋季优点：优点：便于动态申请内存便于动态申请内存 管理和使用统一化管理和使用统一化 便于共享便于共享 便于动态链接便于动态链接缺点：产生碎片缺点：产生碎片思考：与可变分区存储管理方案的相同点思考：与可变分区存储管理方案的相同点与不同点？与不同点？2011秋季秋季4.4.4段页式存储管理段页式存储管理1。产生背景及基本思想
18、。产生背景及基本思想 背景：结合了二者优点背景：结合了二者优点 克服了二者的缺点克服了二者的缺点2011秋季秋季基本思想：基本思想：用户程序划分：按段式划分（对用用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）对系统讲，按页划分每一段）逻辑地址：逻辑地址：内存划分：按页式存储管理方案内存划分：按页式存储管理方案内存分配：以页为单位进行分配内存分配：以页为单位进行分配段号段号段内地址段内地址页号页号页内地址页内地址2011秋季秋季段页式存储方式的段页式存储方式的 管理管理1.段表：记录了每一段的页表始址和段表：记录了每一段的
19、页表始址和页表长度页表长度2.页表：记录了逻辑页号与内存块号页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个的对应关系（每一段有一个，一个程序可能有多个页表）程序可能有多个页表）3.空块管理：同页式管理空块管理：同页式管理4.分配：同页式管理分配：同页式管理2011秋季秋季图图 4-21 利用段表和页表实现地址映射利用段表和页表实现地址映射 段号状态页表大小页表始址0111213041页号状态存储块#0111213041操作系统主存页表段表段表大小段表始址段表寄存器2011秋季秋季2.地址变换过程地址变换过程 图图 4-22 段页式系统中的地址变换机构段页式系统中的地址变换机构 段
20、表寄存器段表始址段表长度段号S页号P段超长段表0123页内地址页表0123b块号 b块内地址页表始址页表长度2011秋季秋季4.5 虚拟存储技术虚拟存储技术 计算机系统资源管理策略：计算机系统资源管理策略：内存比较昂贵，同时资源有限；内存比较昂贵，同时资源有限；外存较大，价格便宜；外存较大，价格便宜；以以CPU时间和外存空间换取昂贵时间和外存空间换取昂贵内存空间，这是操作系统中的内存空间，这是操作系统中的资源转资源转换技术换技术2011秋季秋季1.常规存储器管理方式的特征常规存储器管理方式的特征(1)一次性。作业在运行时全部一次装一次性。作业在运行时全部一次装入。入。(2)驻留性。作业装入内存
21、后，直至作驻留性。作业装入内存后，直至作业结束才完全撤出。业结束才完全撤出。2011秋季秋季4.5.1 概述概述 1、问题的提出、问题的提出 程序大于内存程序大于内存 程序暂时不执行或运行完是否还要占程序暂时不执行或运行完是否还要占用内存用内存 虚拟存储器的基本思想是：程序、数虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。在内存和磁盘之间动态交换。虚拟存储器支持多道
22、程序设计技术虚拟存储器支持多道程序设计技术2011秋季秋季2、程序局部性原理、程序局部性原理 在一段时间内一个程序的执行往往呈现出在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面高度的局部性，表现在时间与空间两方面时间局部性：时间局部性：一条指令被执行了，则在不久的将来它可能一条指令被执行了，则在不久的将来它可能再被执行再被执行空间局部性：空间局部性：若某一存储单元被使用，则在一定时间内，若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用与该存储单元相邻的单元可能被使用2011秋季秋季3、虚拟存储技术、虚拟存储技术 虚存：把内存与外存有机的结合起来虚
23、存：把内存与外存有机的结合起来使用，从而得到一个容量很大的使用，从而得到一个容量很大的“内存内存”，这就是虚存这就是虚存 实现思想：当进程运行时，先将一部分实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作完成将它们从外存调入内存工作 目的：目的：提高内存利用率。提高内存利用率。2011秋季秋季4.5.3 虚拟存储器的特征虚拟存储器的特征 1.多次性多次性一个作业分多次调入内存执行一个作业分多次调入内存执行 2.对换性对换性进程运行期间允许
24、程序和数据换进、换出。进程运行期间允许程序和数据换进、换出。3.虚拟性虚拟性 从逻辑上对内存进行扩充，允许运行比内从逻辑上对内存进行扩充，允许运行比内存大的程序存大的程序2011秋季秋季4.6虚拟页式存储管理虚拟页式存储管理(请求分页式请求分页式)1、基本工作原理、基本工作原理 在进程开始运行之前，不是装入全在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法要装入新的页面时，则根据某种算法淘汰
25、某个页面，以便装入新的页面淘汰某个页面，以便装入新的页面2011秋季秋季2、页表表项（有可能在外存上，故如下）、页表表项（有可能在外存上，故如下）页号、驻留位、内存块号、外存地址、访问页号、驻留位、内存块号、外存地址、访问位、修改位位、修改位驻留位（中断位）：驻留位（中断位）：表示该页是在内存还是表示该页是在内存还是在外存在外存访问位：访问位：根据访问位来决定淘汰哪页（由不根据访问位来决定淘汰哪页（由不同的算法决定）同的算法决定）修改位：修改位：查看此页是否在内存中被修改过查看此页是否在内存中被修改过页号页号中断位中断位 内存块号内存块号外存地址外存地址访问位访问位 修改位修改位2011秋季秋
26、季3、缺页中断（、缺页中断（Page Fault）在地址映射过程中，在页表中发现所要访问的在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，据页表中给出的外存地址，将该页调入内存，使作业继续运行下去使作业继续运行下去如果内存中有空闲块，则分配一页，将新调入如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号留位及相应的内
27、存块号若此时内存中没有空闲块，则要淘汰某页，若若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存该页在内存期间被修改过，则要将其写回外存2011秋季秋季与一般中断机制的区别;(1)指令执行期间产生和处理中断信号。因为在执行期间发现缺少某页。（2）一条指令期间可能需要多次中断才能完成任务。因为一条指令需要的数据或指令可能跨越多个页面。页面B：A：654321指令copy ATO B2011秋季秋季3.地址变换机构地址变换机构 缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外
28、存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是图图 4-24 请求分页中的地址变换过程请求分页中的地址变换过程 2011秋季秋季4.6.2 内存分配策略和分配算法内存分配策略和分配算法 1.最小物理块数的确定最小物理块数的确定 保证进程正常运行所需的最小物理块数。当系统为进程分保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。配的物理块数少于此值时，进程将无法运行。（1）若是单地址指令且采用直接寻址方式，则
29、所需的最少物）若是单地址指令且采用直接寻址方式，则所需的最少物理块数为理块数为2。一块是用于存放指令的页面，另一块则是用于存放。一块是用于存放指令的页面，另一块则是用于存放数据的页面。数据的页面。（2）如果该机器允许间接寻址时，则至少要求有三个物理块。）如果该机器允许间接寻址时，则至少要求有三个物理块。（3）对于某些功能较强的机器，对于某些功能较强的机器，其指令长度可能是两个或多其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。目标地址所涉及的区域也都可能跨两个页面。201
30、1秋季秋季2.物理块的分配策略物理块的分配策略 1)固定分配局部置换固定分配局部置换(Fixed Allocation,Local Replacement)为某个进程分配固定页面数，其间不能改变。需要置换为某个进程分配固定页面数，其间不能改变。需要置换时候只能置换自己的。时候只能置换自己的。2)可变分配全局置换可变分配全局置换(Variable Allocation,lobalReplacement)先为进程一定的内存页面，如果在需要责从空闲块中选先为进程一定的内存页面，如果在需要责从空闲块中选择相应的页面分配给它。择相应的页面分配给它。3)可变分配局部置换可变分配局部置换(Variable
31、Allocation,Local Replacemen 初始分配同上，但是如果发生缺页，必须置换自己的页面。初始分配同上，但是如果发生缺页，必须置换自己的页面。如果缺页率过高，如果缺页率过高，os再为其分配一定的页面数目。再为其分配一定的页面数目。2011秋季秋季3.物理块分配算法物理块分配算法 1)平均分配算法平均分配算法 这是将系统中所有可供分配的物理块，平均分配给各个这是将系统中所有可供分配的物理块，平均分配给各个进程。进程。例如，当系统中有例如，当系统中有100个物理块，有个物理块，有5个进程在运行时，个进程在运行时，每个进程可分得每个进程可分得20个物理块。这种方式貌似公平，但实际上
32、个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为进程其大小为200页，只分配给它页，只分配给它20个块，这样，它必然会个块，这样，它必然会有很高的缺页率；而另一个进程只有有很高的缺页率；而另一个进程只有10页，却有页，却有10个物理块个物理块闲置未用。闲置未用。2011秋季秋季 2)按比例分配算法按比例分配算法 这是根据进程的大小按比例分配物理块的算法。如果这是根据进程的大小按比例分配物理块的算法。如果系统中共有系统中共有n个进程，每个进程的页面数为个进程，每个进程的页面数为Si，则系统中各
33、，则系统中各进程页面数的总和为：进程页面数的总和为：又假定系统中可用的物理块总数为又假定系统中可用的物理块总数为m，则每个进程所能分，则每个进程所能分到的物理块数为到的物理块数为bi，将有：，将有：b应该取整，它必须大于最小物理块数。应该取整，它必须大于最小物理块数。niiSS1mSSbii2011秋季秋季 3)考虑优先权的分配算法考虑优先权的分配算法 在实际应用中，为了照顾到重要的、紧迫的作业能尽在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，快地完成，应为它分配较多的内存空间。通常采取的方法应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按是
34、把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。程分配其物理块的。2011秋季秋季4.6.3 调页策略调页策略 1.何时调入页面何时调入页面 1)预调页策略预调页策略 一次调入进程的多个相邻的多个页面，这样可以降一次调入进程的多个相邻的多个页面，这样可以降低每次缺页都要进行调入
35、的开销。可以采用预测机低每次缺页都要进行调入的开销。可以采用预测机制进行处理。制进行处理。2)请求调页策略请求调页策略 发生缺页时才将缺页调入内存中。在目前的虚拟存发生缺页时才将缺页调入内存中。在目前的虚拟存储中基本采用此种方法进行。储中基本采用此种方法进行。2011秋季秋季2.从何处调入页面从何处调入页面 外存分为两部分：用于存放文件的文件区和用于外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。对换区是采用连续分配方存放对换页面的对换区。对换区是采用连续分配方式，故对换区的磁盘式，故对换区的磁盘I/O速度比文件区的高。这样，速度比文件区的高。这样，每当发生缺页请求时，系统应从
36、何处将缺页调入内每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：存，可分成如下三种情况：(1)系统拥有足够的对换区空间，这时可以全部系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，从对换区调入所需页面，以提高调页速度。为此，在进程运行前，在进程运行前，便须将与该进程有关的文件，从文便须将与该进程有关的文件，从文件区拷贝到对换区。件区拷贝到对换区。2011秋季秋季 (2)系统缺少足够的对换区空间，这时凡是不会被修改系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于的文件，都直接从文件区调入；而当换
37、出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。出时，便须调到对换区，以后需要时，再从对换区调入。(3)UNIX方式。由于与进程有关的文件都放在文件区，方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次行过但又被换出的页面，由
38、于是被放在对换区，因此在下次调入时，应从对换区调入。由于调入时，应从对换区调入。由于UNIX系统允许页面共享，系统允许页面共享，因此，因此，某进程所请求的页面有可能已被其它进程调入内存，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。此时也就无须再从对换区调入。2011秋季秋季 3.页面调入过程页面调入过程 (1)向向CPU发出缺页中断，保留发出缺页中断，保留CPU环境，环境，分析中断原因后，分析中断原因后，转入缺页中断处理程序。转入缺页中断处理程序。(2)查找页表，得到该页在外存的物理块后，查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘如果此
39、时内存能容纳新页，则启动磁盘I/O将将所缺之页调入内存，然后修改页表。所缺之页调入内存，然后修改页表。（3）如果内存已满，则须先按照某种置换）如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；算法从内存中选出一页准备换出；2011秋季秋季 （4）检查该页是否被修改。a.如果该页未被修改过，可不必将该页写回磁盘；b.如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存。(5)修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。(6)在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。2011秋季秋季 4.7页面淘汰算法页面淘汰算
40、法 1、最佳页面淘汰算法（、最佳页面淘汰算法（OPT）淘汰以后不再需要的或最远的将来才会用到淘汰以后不再需要的或最远的将来才会用到的页面（理论上可行，实际上不可行）的页面（理论上可行，实际上不可行）2、最近最久未使用（最近最久未使用（LRU）在最近的一段时间之内一直没有被访问的在最近的一段时间之内一直没有被访问的页面，我们可以认为该页面在将来可能页不会页面，我们可以认为该页面在将来可能页不会被访问，所以淘汰掉。被访问，所以淘汰掉。即淘汰没有使用即淘汰没有使用的时间最长的页。的时间最长的页。2011秋季秋季 3、先进先出页面淘汰算法（、先进先出页面淘汰算法（FIFO）选择在内存中驻留时间最长的页
41、并淘汰之选择在内存中驻留时间最长的页并淘汰之 4、第二次机会淘汰算法、第二次机会淘汰算法(NUR)按照先进先出算法选择某一页面，检查按照先进先出算法选择某一页面，检查其访问位，如果为其访问位，如果为0，则淘汰该页，如果为，则淘汰该页，如果为1，则给第二次机会，并将访问位置，则给第二次机会，并将访问位置0。该算法要求在访问某页面时将其访问位置该算法要求在访问某页面时将其访问位置12011秋季秋季 1、OPT页面置换算法 假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 进程运行时，先将7，0，1三个页面装
42、入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。时刻PMF1 23 45 67 8 9 101112 13 141516 1718 1907 0 12 03 04 2 3 03 212 01 7 017 07107210ffffv210230230v2342342fV Vf34230f230v230v210f210v210V210v710f710v710v缺页率=9/20=45%2011秋季秋季2.先进先出先进先出(FIFO)页面置换算法页面置换算法 引用率70770170122010323104430230321013201770201页
43、框2304204230230127127011图图 4-26 利用利用FIFO置换算法时的置换图置换算法时的置换图 时刻PMF1 23 45 67 8 9 101112 13 141516 1718 1907 0 12 03 04 2 3 03 212 01 7 017 07107210ffffv210321032f4032403ffff24032f032v032v103f210f210v210v721f072f107f缺页率=15/20=75%2.先进先出先进先出(FIFO)页面置换算页面置换算法法时刻PMF1 23 45 67 8 9 101112 13 141516 1718 1907
44、0 12 03 04 2 3 03 212 01 7 017 07107210ffffv210230230v4304204ffff23023f023v023v123f123v120f120v170f170v170v缺页率=12/20=60%3.LRU(Least Recently Used)置换算法置换算法的描述的描述 2011秋季秋季例：计算缺页次数例：计算缺页次数 某程序在内存中分配三个页面，初某程序在内存中分配三个页面，初始为空，页面走向为始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，52011秋季秋季FIFO 4 3 2 1 4 3 5 4 3 2 1 5页页1 4 3
45、 2 1 4 3 5 5 5 2 1 1页页2 4 3 2 1 4 3 3 3 5 2 2页页3 4 3 2 1 4 4 4 3 5 5 x x x x x x x x x 共缺页中断共缺页中断9次次2011秋季秋季 LRU 4 3 2 1 4 3 5 4 3 2 1 5页页1 4 3 2 1 4 3 5 4 3 2 1 5页页2 4 3 2 1 4 3 5 4 3 2 1页页3 4 3 2 1 4 3 5 4 3 2 x x x x x x x x x x共缺页中断共缺页中断10次次2011秋季秋季 OPT 4 3 2 1 4 3 5 4 3 2 1 5页页1 4 3 2 1 1 1 5 5
46、 5 2 1 1页页2 4 3 3 3 3 3 3 3 5 5 5页页3 4 4 4 4 4 4 4 4 4 4 x x x x x x x 共缺页中断共缺页中断7次次最佳页面算法（最佳页面算法（OPT）2011秋季秋季 LRU置换算法的硬件支持置换算法的硬件支持 1)寄存器寄存器 为了记录某进程在内存中各页的使用情况，须为每个为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3 R2R1R0 进程访问某物理块时，要将相应的寄存器r位置为1。定时信号将每隔一段时间将寄存器右移1位，将n位
47、寄存器看作一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用页面。如下图所示：2011秋季秋季图图 4-28 某进程具有某进程具有8个页面时的个页面时的LRU访问情况访问情况 2011秋季秋季2)栈栈 图图 4-29 用栈保存当前使用页面时栈的变化情况用栈保存当前使用页面时栈的变化情况 4474707407047170410174010741210742120741210742621076 保存当前使用的各个页面的页面号，当进程访问某个保存当前使用的各个页面的页面号，当进程访问某个页面时，便将该页面的页面号从栈中取出，将其压入栈顶。页面时，便将该页面的页面号从栈中取出，将其压
48、入栈顶。因此栈顶永远是最近使用的页面，而栈底则是最近最久没有因此栈顶永远是最近使用的页面，而栈底则是最近最久没有被访问的页面。被访问的页面。2011秋季秋季4、Clock置换算法置换算法（NUR）1.简单的简单的Clock置换算法置换算法 图图 4-30 简单简单Clock置换算法的流程和示例置换算法的流程和示例 入口查寻指针前进一步，指向下一个表目页面访问位0?选择该页面淘汰是返回置页面访问位“0”否块号页号访问位指针0124034215650711替换指针注：页面被访问时，其访问位被置为12011秋季秋季2.改进型改进型Clock置换算法置换算法 由访问位由访问位A和修改位和修改位M可以组
49、合成下面四种类型的页面：可以组合成下面四种类型的页面：1类类(A=0,M=0):表示该页最近既未被访问，表示该页最近既未被访问，又未被修改，又未被修改，是最佳淘汰页。是最佳淘汰页。2类类(A=0,M=1)：表示该页最近未被访问，表示该页最近未被访问，但已被修改，但已被修改，并不是很好的淘汰页。并不是很好的淘汰页。3类类(A=1,M=0)：最近已被访问，最近已被访问，但未被修改，但未被修改，该页有该页有可能再被访问。可能再被访问。4类类(A=1,M=1):最近已被访问且被修改，最近已被访问且被修改，该页可能再被该页可能再被访问。访问。2011秋季秋季 (1)从指针所指示的当前位置开始，从指针所指
50、示的当前位置开始，扫描扫描循环队列，循环队列，寻找寻找A=0且且M=0的第一类页面，的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位在第一次扫描期间不改变访问位A。(2)如果第一步失败，即查找一周后未遇如果第一步失败，即查找一周后未遇到第一类页面，到第一类页面，则开始第二轮扫描，寻找则开始第二轮扫描，寻找A=0且且M=1的第二类页面，将所遇到的第一的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置将所有扫描过的页面的访问位都置0。20
