湘潭大学操作系统第5章.ppt

* 5.7.2 请求分页存储管理 2. 缺页中断机构 每当所要访问的页面不在内存时，便要产生一次缺页中断，请求OS将所缺之页调入内存。缺页中断虽要经历与一般中断相同的几个步骤，但它是一种特殊的中断，与一般中断的区别主要是： (1) 在指令执行期间产生和处理中断信号。通常CPU都是在一条指令执行完后去检查是否有中断请求到达。有则响应，无则继续执行下一条指令。而缺页中断是在指令执行期间，发现所要访问的指令和数据不在内存时产生和处理的。 (2) 一条指令在执行期间，可能产生多次缺页中断。这时硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处，继续执行。 * B: A: Copy A To B 例如：执行 COPY A TO B 指令时，可能要产 生6次缺页中断 6 5 4 3 2 1 页面 * 5.7.2 请求分页存储管理 地址变换过程 　　请求分页系统中的地址变换机构是在分页系统地址变换机构的基础上，为实现虚拟存储器，再增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。图5.16示出了请求分页系统中的地址变换过程。 * 图 5.16 请求分页中的地址变换过程 * 5.7.3 页面置换算法 缺页率　　假设一个进程的逻辑空间为n页，系统为其分配的内存物理块数为m(m≤n)。如果在进程的运行过程中，访问页面成功(即所访问页面在内存中)的次数为S，访问页面失败(即所访问页面不在内存中，需要从外存调入)的次数为F，则该进程总的页面访问次数为A?=?S?+?F，那么该进程在其运行过程中的缺页率即为 缺页率的影响因素: 1) 页面大小；2) 进程分配物理块的数目；3) 页面置换算法；4) 程序固有特性。 * 5.7.3 页面置换算法 在请求分页存储管理中，进程或作业执行中产生缺页中断，需要从外存中调入对应的程序或数据到内存当中，此时，如果内存已经满了，那么应该调出哪一页以腾出内存空间就需要遵循一定的算法。通常把这类算法称为页面置换算法。 一个好的算法，应具有较低的页面更换频率。理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长时间内不会再访问的页面调出。 * 1. 最佳置换算法(Optimal replacement, OPT) 　　最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。但由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 — — 7 — 0 — 7 — 0 — 1 2 — 0 — 1 2 — 0 — 3 2 — 4 — 3 2 — 0 — 3 2 — 0 — 1 7 — 0 — 1 页面的编号 系统为某进程分配的三个物理块（页框） 进程运行时先后将7，0，1三个页面装入内存，此时内存已满，若进程要访问新的页面，则需淘汰三者之一 进程访问页面2，此时产生缺页中断，将页面2调入内存，但调入之前须将内存中的某页换出。 OS根据最佳置换算法，将页面7淘汰，因页面0将在第5次被访问，页面1在第14次被访问，而页面7要在第18次时被访问才需调入。 进程访问访问页面3，引起页面1被淘汰，因在内存中的1，2，0三个页面中，页面1将是以后最晚才被访问的，要在第14次才被访问。 采用最佳置换算法，只发生6次页面置换 进程在运行过程中共发生9次缺页中断 缺页中断和页面置换次数分别是多少？ 编号页面的引用顺序（页面走向）： 1 2 3 4 5 6 7 8 9 1015161718 1920 * 2. 先进先出置换算法(First in first out, FIFO) FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。 7 0 1