操作系统17--请求分页性能分析

17.1/232020年1月操作系统4.8.4请求分页系统的性能分析（补充）1.缺页率对有效访问时间的影响在请求分页系统中，假设存储器的访问时间ma为100ns（一般为10ns～几百ns），缺页率为p，缺页中断时间为25ms，则：ma=100ns=0.1s,缺页中断时间＝25000s有效访问时间=(1-p)×0.1+p×（25000+0.1)=0.1+25000×p可见,有效访问时间与缺页率成正比。如果缺页率为0.1%，则有效访问时间约为25μs，与直接访问存储器的有效访问时间(0.1μs)相比，程序的性能大大降低。如果希望在缺页时，仅使有效访问时间延长不超过10%，即:25000*P+0.10.1(1+0.1)因此,P4*10-7即:要求在2.5*106次的访问中至多发生一次缺页，即请求分页方式应保持非常低的缺页率,才不至于影响程序执行速度。此外，提高磁盘I/O的速度，对改善请求分页系统的性能至关重要(为此，应选用高速磁盘和高速磁盘接口)17.2/232020年1月操作系统练习：现有一请求调页系统，也表保存在寄存器中。若有一个被替换的页未被修改过，则处理一个缺页中断需要8ms；若被替换的页被修改过，则处理一个缺页中断需要20ms。内存存取时间为1s,访问页表的时间可以忽略不计。假设70%被替换的页被修改过，为保证有效存取时间不超过2s，则可接受的最大缺页率是多少？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.0000617.3/232020年1月操作系统驻留集指虚拟页式管理中给进程分配的物理页面数目。驻留集与缺页率的关系：每个进程的驻留集越小，则同时驻留内存的进程就越多，可以提高并行度和处理器利用率；另一方面，进程的缺页率上升，使调页的开销增大。进程的驻留集达到某个数目之后，再给它分配更多页面，缺页率不再明显下降。该数目是“缺页率－驻留集大小曲线上的拐点。2.驻留集(residentset)物理块数(驻留集)缺页率拐点17.4/232020年1月操作系统3.工作集模型（Workingset1968年由Denning提出）基本思想：根据程序的局部性原理，一般情况下进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理块数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中则不断发生中断。如果能为进程提供与活跃页面数相等的物理块数(驻留集)，则可减少缺页中断次数。17.5/232020年1月操作系统工作集是在某段时间间隔里，进程实际要访问页面的集合，可用一个二元函数W(t,)表示。可见,工作集的内容取决于页的三个因素：􀂾访页序列特性􀂾时刻t􀂾窗口长度(△)其中,t指某一特定的时刻,是对于给定访问序列所选取的定长区间，也称为工作集窗口.进程开始执行后，随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。工作集大小过渡阶段时间稳定阶段工作集大小的变化17.7/232020年1月操作系统引入工作集的目的是依据进程在过去的一段时间内访问的页面来调整驻留集大小。即：驻留集大小的动态调整策略：•记录一个进程的工作集变化；•定期从驻留集中删除不在工作集中的页面；•总是让驻留集包含工作集；17.8/232020年1月操作系统4.抖动问题(颠簸Thrashing)•Ifaprocessdoesnothave“enough”pages,thePagefaultrateisveryhigh.Thisleadsto:–lowCPUutilization–operatingsystemthinksthatitneedstoincreasethedegreeofmultiprogramming–anotherprocessaddedtothesystem•Thrashing=aprocessisbusyswappingpagesinandout17.9/232020年1月操作系统Thrashing可见，不适当地提高多道程序度,不仅不会提高系统吞吐量，反而会使之下降。OS要选择一个适当的进程数目，以在并发水平和缺页率之间达到一个平衡。•Whydoesdemand-pagingwork?Localitymodel–Processmigratesfromonelocalitytoanother–Localitiesmayoverlap•Whydoesthrashingoccur?Ssizeoflocalitytotalmemorysize17.10/232020年1月操作系统5、影响缺页次数的因素(1)分配给进程的物理块数一个程序运行时遇到缺页中断的次数，是和分配给该道程序的物理块数成反比的，但当主存容量达到某个值时，缺页次数减少不再明显。多数程序都有一个确定值——拐点(2)页面本身的大小页面大，页表小，省空间且查找快；缺页次数相对也少；一次换页的时间长，页内碎片空间浪费的可能性较大。页面小则相反.(3)页面置换算法(页面淘汰算法)选择最合适的置换算法。(4)程序的编制方法尽可能使编出的程序具有高度的局部性，则执行时可经常集中在几个页面上进行访问，减少缺页率.17.11/232020年1月操作系统程序的编制方法——选择适当的数据结构,增强程序访问的局部性例：二维数组(512*512)清零问题：假设内存分配2个物理块，一个块用来装入程序和变量i、j;另一块用来存放数组数据。初始时调第一页进入内存,页面大小为512个整数。ex:数组在主存中存放顺序与使用顺序的一致性：行优先存放：法1发生512*512=262144次缺页，法2只发生512次缺页。法1：intA[512][512];法2：intA[512][512]for(j=0;j512;j++)for(i=0;i512;i++)for(i=0;i512;i++)for(j=0;j512;j++)A[i][j]=0;A[i][j]=0;17.12/232020年1月操作系统程序的编制方法——加强编译程序和装入程序的效能：–编译程序：能把程序代码和程序的数据分离开来，减少常用的程序纯代码被换出的机会；–装入程序：应将纯代码部分装入同一页或几页中，切不要把纯代码部分与非纯代码或数据部分放入同一页中，以减少那些常用子程序所在的页被换出的机会。17.13/232020年1月操作系统4.8.5请求分段存储管理方式虚拟分段(virtualsegmentation)1)需要在进程段表中添加若干项：–存取方式：如读R，写W，执行X–访问字段A：被访问的频繁程度–存在位P(presentbit)，即状态位：是否已经调入内存–修改位(modifiedbit/dirtybit)：进入内存后，是否被修改过–增补位（该段是否增长过，在虚拟页式中没有该位）–外存始址(本段在外存中的起始地址,起始盘块号)硬件支持在简单段式存储管理的基础上，增加请求调段和段置换功能。17.14/232020年1月操作系统2)缺段中断：指令和操作数必定不会跨越在段边界上，所以，频繁缺段现象较少。但由于段长不定，所以处理较缺页复杂。拼接后形成合适大小的空闲区淘汰一个或几个段以形成合适大小的空闲区虚段不在内存中阻塞请求的进程内存中有合适的空闲区？从外存读入段修改段表和内存空闲链唤醒请求进程返回空闲区大小总和能否满足？NN3)地址变换机构:P156在地址变换机制中又增加了缺段中断的请求及其处理等。17.15/232020年1月操作系统启动要处理指令计算有效地址访问地址v=(s,p,d)S≤段表长吗？段链接了吗？段在主存吗？P≤页表长吗？访问类型合法吗？页在主存吗？缺页中断处理执行下一条指令访问该地址完成指令形成主存地址出错处理越界中断处理链接中断处理缺段中断处理允许动态增长吗？出错处理NNNNNNN4)请求段页式地址变换机构17.16/232020年1月操作系统引入共享段表实现对共享段的共享：段名段长内存始址状态外存始址共享进程计数count状态进程名进程号段号存取控制……共享段的分配与回收：分段共享与保护分段共享17.17/232020年1月操作系统存储保护的目的：–1)保护系统程序区不被用户侵犯（有意或无意的）–2)不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间）在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？这就是存储保护所要解决的问题。分段保护17.18/232020年1月操作系统越界保护：逻辑地址段号与段表长度比较段内地址与段长比较上下界保护存取控制检查：使用“存取控制”字段规定对段的访问方式只读、只执行、读/写。环保护：处理器状态分为多个环(ring)，分别具有不同的存储访问特权级别(privilege)，通常是级别高的在内环，编号小（如0环级别最高）；在环系统中,程序的访问和调用遵循如下规则:可访问同环或更低级别环的数据；可调用同环或更高级别环的服务。分段保护的几种措施存储保护通常通过存储保护检查来实现，是针对每个存储访问操作进行的，必须由相应的处理器硬件机构支持。17.19/232020年1月操作系统上下界保护下界寄存器存放程序段装入内存后的开始地址（首址）上界寄存器存放程序段装入内存后的末地址判别式：下界寄存器≤物理地址＜上界寄存器例：有一程序装入内存的首地址是500，末地址是1500，访问内存的逻辑地址是500、345、1000。下界寄存器：500上界寄存器：1500逻辑地址＋装入内存的首地＝物理地址1、500＋500＝1000500≤1000＜1500√2、345＋500＝845500≤845＜1500√3、1000＋500＝1500500≤1500＜1500×Ring0Ring1Ring2DataaccessDataaccess对同环或更低级环数据的访问对同环或更高级别环服务的调用•Ring0•Ring1•Ring2•CallReturn•Call•Returnreturncall17.22/232020年1月操作系统练习：一个程序的段表如下表，其中存在位为1表示段在内存，存取控制字段中W表示可写，R表示可读，E表示可执行。对下面的5条指令，在执行时会产生什么样的结果？(1)STORER1,[0,70](2)STORER1,[1,20](3)LOADR1,[3,20](4)LOADR1,[3,100](5)JMP[2,100]段号存在位内存始址段长存取控制00500100W11100030R213000200E31800080R40500040R•缺段中断•只读，保护性中断•合法，形成物理地址8020，将该单元内容读入寄存器R1中•越界中断•合法，跳到3100处继续执行(1)STORER1,[0,70](2)STORER1,[1,20](3)LOADR1,[3,20](4)LOADR1,[3,100](5)JMP[2,100]答：17.23/232020年1月操作系统第三章存储管理存储分配存储扩充存储保护连续分配存储管理方式：单一连续、固定分区，动态分区、伙伴系统、可重定位分区“紧凑”离散分配存储管理方式：地址变换、逻辑地址、物理地址、地址变换机构分页:页表、快表、多级页表、反置页表分段:段表段页:虚拟存储:“对换”技术和覆盖技术、局部性原理、虚拟存储器概念、实现方式：请求分页：硬件支持、软策略：内存分配调页策略页面置换策略性能分析:缺页率对访问时间的影响,驻留集,工作集,抖动现象,影响缺页率的因素请求分段：存储保护：共享和保护的含义和基本方法