《请求分页性能分析》由会员分享，可在线阅读，更多相关《请求分页性能分析（23页珍藏版）》请在金锄头文库上搜索。
1、4.8.4 4.8.4 请求分页系统的性能分析（补充）请求分页系统的性能分析（补充）练习：练习：现有一请求调页系统，页表保存在寄存器中。若有一个被替换的页现有一请求调页系统，页表保存在寄存器中。若有一个被替换的页未被修改过，则处理一个缺页中断需要未被修改过，则处理一个缺页中断需要8ms；若被替换的页被修改；若被替换的页被修改过，则处理一个缺页中断需要过，则处理一个缺页中断需要20ms。内存存取时间为。内存存取时间为1 s ,访问页访问页表的时间可以忽略不计。假设表的时间可以忽略不计。假设70%被替换的页被修改过，为保证有被替换的页被修改过，为保证有效存取时间不超过效存取时间不超过2 s ，则可
2、接受的最大缺页率是多少？，则可接受的最大缺页率是多少？p*(0.7*20+0.3*8+0.001)+(1-p)*0.001=0.00216.4p+0.001=0.00216.4p=0.001P=1/16400 0.00006驻留集指虚拟页式管理中给进程分配的物理页面数目。驻留集指虚拟页式管理中给进程分配的物理页面数目。驻留集与缺页率的关系：驻留集与缺页率的关系：v每个进程的每个进程的驻留集驻留集越小，则同时越小，则同时驻留内存的进程驻留内存的进程就就越多，可以提高越多，可以提高并行度和处理器利用率并行度和处理器利用率；另一方面，；另一方面，进程的进程的缺页率缺页率上升，使上升，使调页的开销调页
3、的开销增大。增大。v进程的进程的驻留集达到某个数目之后驻留集达到某个数目之后，再给它分配更多，再给它分配更多页面，页面，缺页率不再明显下降缺页率不再明显下降。该数目是。该数目是“缺页率驻缺页率驻留集大小留集大小 曲线上的曲线上的拐点拐点。2. 2. 驻留集驻留集( (resident set)resident set)物理块数物理块数(驻留集驻留集)缺缺页页率率拐点拐点3. 3. 工作集模型工作集模型（Working set Working set 1968年由年由Denning提出）提出） 基本思想：根据程序的局部性原理，一般情况下进程在基本思想：根据程序的局部性原理，一般情况下进程在一段时
4、间内总是集中访问一些页面，这些页面称为活跃一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理块数太少了，使该进页面，如果分配给一个进程的物理块数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程所需的活跃页面不能全部装入内存，则进程在运行过程中则不断发生中断。程中则不断发生中断。 如果能为进程提供与活跃页面数相等的物理块数如果能为进程提供与活跃页面数相等的物理块数(驻留驻留集集)，则可减少缺页中断次数。，则可减少缺页中断次数。工作集工作集是在某段时间间隔是在某段时间间隔 里，里，进程实际要访问页面的集进程实际要访问页面的集合合，可用一个二元函数，可用一
5、个二元函数W(t, W(t, ) )表示。表示。可见可见,工作集的内容取决于页的三个因素：工作集的内容取决于页的三个因素： 访页序列特性访页序列特性 时刻时刻t 窗口长度窗口长度()其中,t指某一特定的时刻, 是是对于给定访问序列所选取的定长区间，也称为工作集窗口.进程开始执行后，随着访问新页面逐步建立进程开始执行后，随着访问新页面逐步建立较稳定的工作较稳定的工作集集。当内存访问的。当内存访问的局部性区域局部性区域的位置大致稳定时，工作集的位置大致稳定时，工作集大小也大致稳定；局部性区域的位置改变时，工作集大小也大致稳定；局部性区域的位置改变时，工作集快速快速扩张和收缩过渡扩张和收缩过渡到下一
6、个稳定值。到下一个稳定值。工作集大小的变化工作集大小的变化引入工作集的目的是依据进程在过去的一段时间内访问的页引入工作集的目的是依据进程在过去的一段时间内访问的页面来面来调整驻留集大小调整驻留集大小。即：驻留集大小的。即：驻留集大小的动态调整策略动态调整策略：记录一个进程的工作集变化；记录一个进程的工作集变化；定期从驻留集中删除不在工作集中的页面；定期从驻留集中删除不在工作集中的页面；总是让驻留集包含工作集；总是让驻留集包含工作集；4.4.抖动问题抖动问题( (颠簸颠簸 ThrashingThrashing ) ) If a process does not have “enough” pag
7、es, the Page fault rate is very high. This leads to: low CPU utilization operating system thinks that it needs to increase the degree of multiprogramming another process added to the system Thrashing a process is busy swapping pages in and outThrashingThrashing 可见，不适当地提高多道程序度可见，不适当地提高多道程序度,不仅不会提高系不仅
8、不会提高系统吞吐量，反而会使之下降。统吞吐量，反而会使之下降。 OS要选择一个适当的进要选择一个适当的进程数目，以程数目，以在并发水平和缺页率之间达到一个平衡在并发水平和缺页率之间达到一个平衡。5、影响缺页次数的因素、影响缺页次数的因素(1)分配给进程的物理块数分配给进程的物理块数一个程序运行时遇到缺页中断的次数，是和分配给该道程一个程序运行时遇到缺页中断的次数，是和分配给该道程序的物理块数成反比的，但当主存容量达到某个值时，缺序的物理块数成反比的，但当主存容量达到某个值时，缺页次数减少不再明显。多数程序都有一个确定值页次数减少不再明显。多数程序都有一个确定值拐点拐点(2) 页面本身的大小页面
9、本身的大小页面大，页表小，省空间且查找快；缺页次数相对也少；页面大，页表小，省空间且查找快；缺页次数相对也少；一次换页的时间长，页内碎片空间浪费的可能性较大。页一次换页的时间长，页内碎片空间浪费的可能性较大。页面小则相反面小则相反.(3) 页面置换算法页面置换算法(页面淘汰算法页面淘汰算法)选择最合适的置换算法。选择最合适的置换算法。(4) 程序的编制方法程序的编制方法尽可能使编出的程序具有高度的局部性，则执行时可经常尽可能使编出的程序具有高度的局部性，则执行时可经常集中在几个页面上进行访问，减少缺页率集中在几个页面上进行访问，减少缺页率.程序的编制方法程序的编制方法程序的编制方法程序的编制方
10、法选择适当的数据结构选择适当的数据结构选择适当的数据结构选择适当的数据结构, ,增强程序访问的局部性增强程序访问的局部性例：二维数组例：二维数组(512*512)(512*512)清零问题：假设内存分配清零问题：假设内存分配2 2个物理块，一个个物理块，一个块用来装入程序和变量块用来装入程序和变量i i、j; j;另一块用来存放数组数据。初始时调另一块用来存放数组数据。初始时调第一页进入内存第一页进入内存, ,页面大小为页面大小为512512个整数。个整数。 ex: 数组在主存中存放顺序与使用顺序的一致性数组在主存中存放顺序与使用顺序的一致性：行优先存放：行优先存放：法法1发生发生512*51
11、2=262144次缺页，法次缺页，法2只发生只发生512次缺页。次缺页。 法法1：int A512512;法法2： int A512512 for (j=0;j512;j+) for (i=0;i512;i+) for (i=0;i512;i+)for (j=0;j512;j+) Aij=0;Aij=0; 程序的编制方法程序的编制方法程序的编制方法程序的编制方法加强编译程序和装入程序的效能：加强编译程序和装入程序的效能：加强编译程序和装入程序的效能：加强编译程序和装入程序的效能：编译程序：能把程序代码和程序的数据分离开来，减少常用编译程序：能把程序代码和程序的数据分离开来，减少常用的程序纯代码
12、被换出的机会；的程序纯代码被换出的机会；装入程序：应将纯代码部分装入同一页或几页中，切不要把装入程序：应将纯代码部分装入同一页或几页中，切不要把纯代码部分与非纯代码或数据部分放入同一页中，以减少那纯代码部分与非纯代码或数据部分放入同一页中，以减少那些常用子程序所在的页被换出的机会些常用子程序所在的页被换出的机会。 4.8.5 4.8.5 请求分段存储管理方式请求分段存储管理方式虚拟分段虚拟分段( (virtual segmentation)virtual segmentation)1) 需要在进程段表中添加若干项：需要在进程段表中添加若干项：存取方式存取方式：如读如读R，写写W，执行执行X访问
13、字段访问字段A：被访问的频繁程度被访问的频繁程度存在位存在位P(present bit)，即状态位：是否已经调入内存即状态位：是否已经调入内存修改位修改位(modified bit/dirty bit)：进入内存后，是否被修改过进入内存后，是否被修改过增补位（该段是否增长过，在虚拟页式中没有该位）增补位（该段是否增长过，在虚拟页式中没有该位）外存始址外存始址(本段在外存中的起始地址本段在外存中的起始地址,起始盘块号起始盘块号)硬件支持硬件支持在简单段式存储管理的基础上，增加请求调段和段置换功能。在简单段式存储管理的基础上，增加请求调段和段置换功能。2)缺段中断缺段中断：指令和操作数必定不会跨越
14、在段边界上，所以，频繁：指令和操作数必定不会跨越在段边界上，所以，频繁缺段现象较少。但由于段长不定，所以处理较缺页复杂。缺段现象较少。但由于段长不定，所以处理较缺页复杂。拼接后形成合适拼接后形成合适大小的空闲区大小的空闲区淘汰一个或几个段淘汰一个或几个段以形成合适大小的以形成合适大小的空闲区空闲区虚段不在内存中虚段不在内存中阻塞请求的进程阻塞请求的进程内存中有合适的空闲区？内存中有合适的空闲区？从外存读入段从外存读入段修改段表和内存空闲链修改段表和内存空闲链唤醒请求进程唤醒请求进程返回返回空闲区大小总和能否满足？空闲区大小总和能否满足？N NN N3)地址变换机构地址变换机构: P156在地址
15、变换机制中又增加了在地址变换机制中又增加了缺段中断缺段中断的请求及其处理等。的请求及其处理等。启动要处理指令启动要处理指令 计算有效地址计算有效地址 访问地址访问地址v= (s,p,d)v= (s,p,d)SS段表长吗？段表长吗？段链接了吗？段链接了吗？段在主存吗？段在主存吗？PP页表长吗？页表长吗？访问类型合访问类型合 法吗？法吗？页在主存吗？页在主存吗？ 缺页中断处理缺页中断处理执行下一条指令执行下一条指令 访问该地址访问该地址 完成指令完成指令形成主存地址形成主存地址出错处理出错处理 越界中断处理越界中断处理 链接中断处理链接中断处理缺段中断处理缺段中断处理允允 许许 动动 态态增增 长
16、吗？长吗？ 出错处理出错处理N NN NN NN NN NN NN N4)请求请求段页式段页式地址变换机构地址变换机构引入引入共享段表共享段表实现对实现对共享段共享段的共享：的共享：段名段名段长段长内存始址内存始址状态状态外存始址外存始址共享进程计数共享进程计数count状态状态进程名进程名进程号进程号段号段号存取控制存取控制共享段的分配与回收：共享段的分配与回收：分段共享与保护分段共享与保护分段共享分段共享存储保护的目的：存储保护的目的：1) 1)保护保护系统程序区系统程序区不被用户侵犯（有意或无意的）不被用户侵犯（有意或无意的）2) 2)不允许用户程序读写不允许用户程序读写不属于自己地址空
17、间的数据不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间）（系统区地址空间，其他用户程序的地址空间）在多道程序设计的环境下，系统中有系统程序和多个用户在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，如何保证用户程序不破坏系统程序，用户程序同时存在，如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？这就是程序之间不相互干扰？这就是存储保护所要解决的问题存储保护所要解决的问题。分段保护分段保护v 越界保护：越界保护：逻辑地址段号与段表长度比较逻辑地址段号与段表长度比较 段内地址与段长比较段内地址与段长比较 上下界保护上下界保护v 存取控制检查存取控制检查：使用
18、：使用“存取控制存取控制”字段规定对段的访问方式字段规定对段的访问方式只读、只执行、读只读、只执行、读/写。写。v 环保护环保护：处理器状态分为多个环处理器状态分为多个环(ring)，分别具有不同的分别具有不同的存储访问特存储访问特权级别权级别(privilege)，通常是级别高的在内环，编号小（如通常是级别高的在内环，编号小（如0环级别最高）环级别最高） ；在环系统中在环系统中,程序的访问和调用遵循如下规则程序的访问和调用遵循如下规则:可访问同环或更低级别环的可访问同环或更低级别环的数据数据；可调用同环或更高级别环的可调用同环或更高级别环的服务服务。分段保护的几种措施分段保护的几种措施存储保
19、护通常通过存储保护通常通过存储保护检查来实现，存储保护检查来实现，是针对每个存储访是针对每个存储访问操作进行的，必须由相应的处理器硬件机构支持。问操作进行的，必须由相应的处理器硬件机构支持。上下界保护上下界保护下界寄存器下界寄存器 存放程序段装入内存后的开始地址（首址）存放程序段装入内存后的开始地址（首址）上界寄存器上界寄存器 存放程序段装入内存后的末地址存放程序段装入内存后的末地址判别式：判别式：下界寄存器下界寄存器 物理地址物理地址 上界寄存器上界寄存器例例：有有一一程程序序装装入入内内存存的的首首地地址址是是500500，末末地地址址是是15001500，访访问问内存的逻辑地址是内存的逻
20、辑地址是500500、345345、10001000。 下界寄存器：下界寄存器：500 500 上界寄存器：上界寄存器：15001500 逻辑地址装入内存的首地逻辑地址装入内存的首地 物理地址物理地址 1 1、500500500 500 1000 500 1000 1000 500 1000 15001500 2 2、345345500 500 845 500 845 845 500 845 15001500 3 3、10001000500 500 1500 500 1500 1500 500 1500 15001500对同环或更低级环数据的访问对同环或更低级环数据的访问对同环或更高级别环服务
21、的调用对同环或更高级别环服务的调用Ring 0Ring 1Ring 2Call ReturnCallReturnreturncall练习：练习：一一个个程程序序的的段段表表如如下下表表，其其中中存存在在位位为为1 1表表示示段段在在内内存存，存存取取控控制制字字段段中中WW表表示示可可写写，R R表表示示可可读读，E E表表示示可可执执行行。对对下下面面的的5 5条条指指令令，在在执执行行时时会产生什么样的结果？会产生什么样的结果？(1)(1)STORE R1,0,70STORE R1,0,70(2)(2)STORE R1,1,20STORE R1,1,20(3)(3)LOAD R1,3,20
22、LOAD R1,3,20(4)(4)LOAD R1,3,100LOAD R1,3,100(5)(5)JMP 2,100JMP 2,100段号段号存在存在位位内存内存始址始址段长段长存取存取控制控制00500100W11100030R213000200E31800080R40500040R缺段中断缺段中断只读，保护性中断只读，保护性中断合法，形成物理地址合法，形成物理地址80208020，将该单元内容读入寄存器，将该单元内容读入寄存器R1R1中中越界中断越界中断合法，跳到合法，跳到31003100处继续执行处继续执行(1)(1)STORE R1,0,70STORE R1,0,70(2)(2)ST
23、ORE R1,1,20STORE R1,1,20(3)(3)LOAD R1,3,20LOAD R1,3,20(4)(4)LOAD R1,3,100LOAD R1,3,100(5)(5)JMP 2,100JMP 2,100答：答：第三章第三章 存储管理存储管理存储分配存储分配存储扩充存储扩充存储保护存储保护连续分配存储管理方式：连续分配存储管理方式：单一连续、固定分区，动态分区、伙伴系统、可重定位分区单一连续、固定分区，动态分区、伙伴系统、可重定位分区“紧凑紧凑”离散分配存储管理方式：离散分配存储管理方式：地址变换、逻辑地址、物理地址、地址变换、逻辑地址、物理地址、地址变换机构地址变换机构分页分页:页表、快表、多级页表、反置页表页表、快表、多级页表、反置页表分段分段:段表段表段页段页:虚拟存储虚拟存储:“对换对换”技术和覆盖技术、局部性原理、虚拟存储器概念、技术和覆盖技术、局部性原理、虚拟存储器概念、 实现方式：实现方式： 请求分页：硬件支持、请求分页：硬件支持、 软策略：软策略： 内存分配内存分配调页策略调页策略 页面置换策略页面置换策略 性能分析性能分析:缺页率对访问时间的影响缺页率对访问时间的影响,驻留集驻留集,工作集工作集,抖动现象抖动现象,影响缺页率的因素影响缺页率的因素 请求分段：请求分段： 存储保护存储保护：共享和保护的含义和基本方法：共享和保护的含义和基本方法
