《计算机操作系统 》课件-4.6虚拟存储系统

4.6虚拟存储系统虚拟存储器的基本概念指具有请求调入功能和置换功能，能够利用外存储器的空余空间从逻辑上对内存容量进行扩充的一种存储器系统。进程的局部性特征时间局部性。若某个指令或者数据被访问了，那么在不久的将来将会再次访问该指令或者数据。这是由于程序中的循环结构导致的。空间局部性。若某个指令或者数据被访问了，那么它附近的指令或者数据可能马上会被访问。这是程序顺序执行的方式和线性数据结构（如数组）所导致的。虚拟存储器的引入在以下两方面进行了改变：将进程调入的一次性或者整体性改为多次性将进程的驻留性改为置换性图4-20虚拟存储系统示意图请求分页存储管理方式基于页面系统的扩充方式是虚拟存储器系统的一种实现方式。虚拟存储器只是把一部分程序内容装入内存，而把其他的部分放置在辅存（硬盘）中。当要执行的部分页面不在内存中时，需要及时把这部分页面调入内存。页面调入的时候可能还需要考虑置换的问题。两种页式系统①

简单页式系统：装入一个程序的全部页面才能投入运行。

②

请求页式系统：装入一个程序的部分页面即可投入运行。扩充页表功能

状态位：标识该页是否在主存访问字段：记录页面被访问的情况，修改位：页面装入内存后是否被修改过，供页面置换时参考。外存地址：该页面在外存的位置缺页处理

页面置换策略可变分配全局置换固定分配局部置换可变分配局部置换页面置换算法选择淘汰页面的规则叫做置换算法（淘汰算法）置换算法直接影响到请求分页系统的性能最佳置换算法OPT先进先出法FIFO最近最久未使用法LRU最近最少使用法LFU时钟算法CLOCK

页面置换的相关问题颠簸（thrashing）——抖动在主存和辅存之间的频繁页面置换的现像称为页面“颠簸”或者“抖动”，这种情况会导致系统效率急剧下降。缺页中断率假定程序p共有n页，系统分配m块，有；

若程序p在运行中：成功的访问次数为s，不成功的访问次数为f；缺页中断率：

r：置换算法；m：系统分配的块数；p：程序特征置换算法最佳算法（OPT算法）当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页应是以后不再要用，或者是在最长的时间以后才会用到的那页。页走向41327354132361012302144444

4

4

2

2

2

2

2

1127

5

1

1

1

1

3

3

333

3

3

3

6

0

0

缺页+++++

+++

+

+

+

+

基于OPT置换算法的情况基于OPT算法时，发生缺页中断的次数为12，页面置换的次数为9，缺页率为12/20。最佳算法（OPT算法）是一个理论算法。为什么该方法无法实现？进程真正的页面走向是未知的，无法全部预知页面之后进行全局最优化。常用的置换算法①

先进先出淘汰算法(FIFO——FirstInFirstOut)

思路：总是选择在主存中最早进入主存（即居留时间最长）的一页淘汰。页走向41327354132361012302144422

24442

220

00

2

1117

77111

666

22

3

333

55533

311

13

缺页+++++

+++++

+++

++

基于FIFO算法时，缺页15次，置换12次，缺页率15/20。问题：如何实现找到先进入的页面？Belady现象在FIFO淘汰算法中的一种特殊现象思考：增加进程的主存块数量对缺页率会有怎样的影响？例：在一个请求分页系统中，假如一个作业的页面走向为1，2，3，4，1，2，5，1，2，3，4，5,当分给该作业的物理块数M分别为3和4时，请用FIFO计算缺页次数和缺页率，并比较所得的结果。使用FIFO算法——物理块数为3:页走向123412512345111144

4555

2

2221

1133

3

333

2224

缺页+++++++++

缺页次数：9，缺页率：9/12。使用FIFO算法——物理块数为4:缺页次数：10，缺页率：10/12，这种异常现象称为Belady现象。页走向12341251234511111

5555442

222

2111153

33

33222244444333缺页++++++++++先进先出淘汰算法(FIFO算法)

容易实现适合按线性顺序访问地址空间的程序有的页面经常被访问，但是可能因为存留时间久而换出缺页中断率大概是OPT法的三倍存在Belady现象最近最久未使用淘汰算法（LRU算法）总是选择最长时间未被使用的那一页淘汰。页走向41327354132361012302144422

55533

330

033

2

1117

74442

211

110

3

333

33111

666

222

缺页+++++

+++++

+++

+++

缺页次数：16，缺页率：16/20。Clock置换算法

(1)

简单的clock置换算法：每页设置一位访问位。当某页被访问了，则访问位置“1”。内存中的所有页链接成一个循环队列；置换算法：循环检查各页面的使用情况。若访问位为“0”，选择该页淘汰；若访问位为“1”，复位访问位为“0”，查询指针前进一步。又称为“最近未使用”置换算法（NRU）(2)改进型Clock置换算法：访问位A、修改位M，共同表示一个页面的状态页面的四种状态：

00：(A=0;M=0)最近未被访问也未被修改

01：(A=0;M=1)最近未被访问但已被修改

10：(A=1;M=0)最近已被访问但未被修改

11：(A=1;M=1)最近已被访问且被修改(2)改进型Clock置换算法：三轮扫描：第一轮：查找A=0,M=0页面，未找到，下一步；第二轮：查找A=0,M=1页面，A位复位为“0”，未找到，下一步；第三轮：把所有A置为“0”，重复第一轮，必要时再重复第二轮。补充：页面缓冲置换算法算法：可变分配局部置换策略，FIFO页面置换算法空闲页面链表：已修改页面链表：空闲内存块空白内存块或未修改淘汰页所在内存块已修改淘汰页

所在内存块淘汰页未被修改已被修改Windows2000空闲块链表：（1）零初始化链表；（2）空闲链表；（3）后备链表：未修改淘汰页；（4）修改链表：已修改淘汰页修改页面写回器零页线程页面缓冲算法举例：（1）系统初始化完成后假设系统内存有10个空闲块，则相应空闲内存块链表为：空闲页面链表：已修改页面链表：Null（2）创建P1进程，分配4个块，则分配到0,1,2,3四块，此时空闲页面链表变为：0198765432987654页面缓冲算法举例：（3）P1装入0,1,2,3四个页面：（4）P1访问0页、1页、2页，其中0页修改，1页、2页不修改：0132013201320132M的值：100页面缓冲算法举例：（5）P1写第5页，缺页，按照FIFO，淘汰0页，则系统处理方式为：已修改页面链表：空闲页面链表：进程P1占据内存情况：009876551324132M的值：1000页面缓冲算法举例：（6）P1读第6页，缺页，按照