第六章虚拟存储器--2528

1、第六章第六章 虚拟存储器虚拟存储器抖动l刚被换出的页很快又被访问，需重新调入，又需刚被换出的页很快又被访问，需重新调入，又需再选一页调出，如此频繁地更换页面的现象称为再选一页调出，如此频繁地更换页面的现象称为抖动抖动。l抖动导致进程在运行中，把大部分时间花费在页抖动导致进程在运行中，把大部分时间花费在页面置换上。面置换上。5.3.1页面页面置换算法置换算法l进程访问的页面不在内存而进程访问的页面不在内存而内存已无内存已无空闲空间时，空闲空间时，系统必须从内存中调出一页送磁盘的对换区中。系统必须从内存中调出一页送磁盘的对换区中。l把选择换出页面的算法称为把选择换出页面的算法称为页面置换页面置换算

2、法算法。l应将那些以后不再会访问的页面或在较长时间内应将那些以后不再会访问的页面或在较长时间内不会再访问的页面调出。不会再访问的页面调出。1、最佳、最佳置换算法置换算法选择被淘汰页是永不使用的、或者是在最长时间选择被淘汰页是永不使用的、或者是在最长时间内不再被访问的页面。内不再被访问的页面。采用最佳置换算法可保证获得采用最佳置换算法可保证获得最低的缺页率最低的缺页率。但。但由于无法预知哪一个页面是未来最长时间内不再由于无法预知哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的。被访问的，因而该算法是无法实现的。可利用该算法可利用该算法去评价其它算法去评价其它算法。 例1：假定某进程

3、有8个页面，系统为分配了三个物理块并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1使用最佳置换算法发生几次页面置换？图 5-3利用最佳页面置换算法时的置换图 引用率70770170122010320304243230321201201770101页框(物理块）243701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1210701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2

4、1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1最佳置换算法发生最佳置换算法发生6 6次页面置换次页面置

5、换701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 12、先进先出、先进先出页面置换算法页面置换算法淘汰最先进入内存的页面，即选择在内存中驻留淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。时间最久的页面予以淘汰。该算法实现简单该算法实现简单 假定某进程有假定某进程有8 8个页面，系统为个页面，系统为分配了三个物理块并考虑有以分配了三个物理块并考虑有以下的页面号引用串：下的页面号引用串：7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1使用使用先进

6、先进先出页面置换先出页面置换算法发生几次页面置算法发生几次页面置换？换？图 5-4利用FIFO置换算法时的置换图 引用率70770170122010323104430230321013201770201页框230420423023012712701210701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1

7、 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1发生发生1212次次页面置换页面置换701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 13、最近、最近最久未使用置换算法最久未使用置换算法根据页面调入内存后的使用情况进根据页面调入内存后的使用情况进行决策。行决策。由于无法预测各页面将来的使用情由于无法预测各页面将来的使用情况，只能利用况，只能利用“最近的过去最近的过去”作为作为“最近的将来最近的将来”的近似，选择的近似，选择最近最近最久未使用最久未使用

8、的页面予以淘汰。的页面予以淘汰。 该算法赋予每个页面一个访问字段，用来该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时记录一个页面自上次被访问以来所经历的时间间T T，当须淘汰一个页面时，选择现有页面，当须淘汰一个页面时，选择现有页面中其中其T T值最值最大大的，即最近最久未使用的页面的，即最近最久未使用的页面予以淘汰。予以淘汰。 假定某进程有假定某进程有8 8个页面，系统为个页面，系统为分配了三个物理块并考虑有以分配了三个物理块并考虑有以下的页面号引用串：下的页面号引用串：7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3

9、，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1使用最近使用最近最久未使用算法发生几次页面置最久未使用算法发生几次页面置换？换？图5-5LRU页面置换算法 引用率70770170122010320304403230321132201770101页框402432032102210701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2

10、 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1发生发生9 9次次页面置换页面置换701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 13、最少使用置换算法为每个页面设置一个移位寄存器，为每个页面设置一个移位寄存器，用来记录该页面被访问的频率。用来记录该页面被访问的频率。选择在选择在最近时期使用最少的页面作最近时期使用最少的页面作为淘汰页为淘汰页。701 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1发生发生9 9次页面置换次页面置换每页设置一位访问位。再将内存中的

11、所有页面都通过每页设置一位访问位。再将内存中的所有页面都通过链接指针链成一个循环队列。链接指针链成一个循环队列。当某页被访问时，其访问位置当某页被访问时，其访问位置1 1。淘汰时检查其访问。淘汰时检查其访问位，如果是位，如果是0 0就换出；若为就换出；若为1 1则重新将它复则重新将它复0 0。再按再按FIFOFIFO算法检查下个页面。到队列中的最后算法检查下个页面。到队列中的最后个页个页面时，若其访问位仍为面时，若其访问位仍为1 1，则再返回到队首再去检查，则再返回到队首再去检查第一个页面。第一个页面。又称为最近未用算法。又称为最近未用算法。5.3.3简单简单CLOCK算法算法5.3.4页面页

12、面缓冲算法缓冲算法 采用可变分配和局部置换方式采用可变分配和局部置换方式如果页面末被修改，就将它直接放入如果页面末被修改，就将它直接放入空闲空闲链链表；否则，放入表；否则，放入已修改页面已修改页面的链表中。的链表中。页面在内存并不做物理移动而只是将页表中页面在内存并不做物理移动而只是将页表中的表项移到链表之中。的表项移到链表之中。5.5请求分段存储管理请求分段存储管理 5.5.1请求分段中的硬件支持请求分段中的硬件支持5.5.2分段的共享与保护分段的共享与保护 请求分段中的硬件支持请求分段中的硬件支持l段表机制段表机制 l缺段中断机制缺段中断机制l地址变换机制地址变换机制 段段 表表段段名名段

13、段长长段的段的基址基址存取存取方式方式访问字访问字段段修改修改位位存在存在位位增补增补位位外存外存始址始址存取存取方式方式 ：表示：表示本段本段属性属性，只读、只只读、只执行、允许读执行、允许读/ /写写访问字段访问字段A A。访问频率。访问频率修改位修改位MM。用于表示该页在进入内存后，。用于表示该页在进入内存后， 是否被修改过，供置换页面时参考。是否被修改过，供置换页面时参考。存在位存在位P P。指示本段是否已调入内存，供。指示本段是否已调入内存，供 程序访问时参考。程序访问时参考。增补位。特有的字段，用于本段在增补位。特有的字段，用于本段在运行过程运行过程中，是否做过动态增长。中，是否做

14、过动态增长。外存始值。本段在外存中的起始地址，即外存始值。本段在外存中的起始地址，即 起始盘块号。起始盘块号。请求分段系统中的中断处理过程 虚段S不在内存阻塞请求进程内存中有合适的空闲区吗？从外存读入段S修改段表及内存空区链唤醒请求进程返回空区容量总和能否满足？空区拼接，以形成一个合适的空区淘汰一个或几个实段，以形成一个合适空区否否是是 请求分段系统的地址变换过程 访问sww段长?符合存取方式?段S在主存?修改访问字段,如写访问,置修改位1形成访问主存地址(A) (主存始址) (位移量w)返回分段越界中断处理分段保护中断处理缺段中断处理是是是否否否动态链接动态链接L 间接地址间接地址静态链接静

15、态链接动态链接动态链接装入时动态链接：在装入内存时，边装入边链接。装入时动态链接：在装入内存时，边装入边链接。运行时动态链接：运行时，用到哪个模块，再链接哪个模块，用不到运行时动态链接：运行时，用到哪个模块，再链接哪个模块，用不到的模块可不装入内存。的模块可不装入内存。间接字间接字 L=1：表示要动态链接，发出链接中断信号，转系统处理。表示要动态链接，发出链接中断信号，转系统处理。 L=0：直接地址。直接地址。动态链接的实现动态链接的实现实现动态链接对编译器的要求实现动态链接对编译器的要求LOAD 1,X|MAINLOAD 1,0|1000X|MAIN=01 0 100401001000100

16、4当某段的指令是访问本段内的地址时，将其译成直接寻址指令。当某段的指令是访问本段外的地址时，将其译成间接寻址指令，并将链接中断位L置1，设置链接中断处理程序。间接地址间接地址：存放直接地址的地址。动态链接过程动态链接过程0 1 120当程序执行到LOAD 1，0|1000时，由于L=1发出链接中断信号，OS得到控制。系统找到0段的1004号单元处的符号串”X|“，将X段调入内存，分配一个段号X=1，同时找到=120后修改间接字，并置L=0。中段返回后，执行指令，此时L=0为直接寻址指令。LOAD 1,0|1000X|1 0 1004010010001004LOAD 1,0|1000X|MAIN=01 0 100401