操作系统：虚拟页式存储管理（缺页中断、页面置换算法）

1、基本工作原理

1、基本工作原理
在进程开始运行之前&＃xff0c;不是全部装入页面&＃xff0c;而是装入一个或者零个页面&＃xff0c;之后根据进程运行的需要&＃xff0c;动态装入其他页面&＃xff1b;当内存已满&＃xff0c;而又需要装入
新的页面时&＃xff0c;则根据某种算法淘汰某个页面&＃xff0c;以便装入新的页面。在使用虚拟页式存储管理时需要在页表中增加一些内容&＃xff1a;
页号、驻留位&＃xff08;中断位&＃xff09;、内存块号、外存地址、访问号、修改位驻留位&＃xff1a;表示该页在外存还是内存&＃xff1b;
访问位&＃xff1a;表示该页在内存期间是否被访问过&＃xff0c;又称R位&＃xff1b;
修改位&＃xff1a;表示该页在内存中是否被修改过&＃xff0c;又称M位&＃xff1b;


2、缺页中断
在地址映射过程中&＃xff0c;若在页表中发现所要访问的页面不在内存&＃xff0c;则产生中断&＃xff0c;当发生中断时&＃xff0c;系统必须在内存选择一个页面移出内存&＃xff0c;
以便为调入新的页面让出空间&＃xff0c;尽管每次可以随机选选择一个页面置换&＃xff0c;但选择不常使用的页面会是系统性能好的多&＃xff0c;减少不必要的额外
开销&＃xff0c;就产生了页面置换算法。3、页面置换算法&＃xff1a;
3.1理想页面&＃xff08;Optimal&＃xff0c; OPT)置换算法
发生缺页时&＃xff0c;有些页面在内存中&＃xff0c;其中有一页将很快被访问(包含紧接着 的下一条指令的那页)&＃xff0c;而其他页则可能到10、
100或1000条指令后才会被访问&＃xff0c;每个页都可以用在该页面首次被访问前所要执行的指令数进行标记。标记树最大的页应该被置换。举例&＃xff1a;如果某页在八百万条指令内不会被使用&＃xff0c;另外一页在六百万条指令不会被使用&＃xff0c;则置换前一个页面。这个算法无法实现&＃xff0c;因当缺页
中断时&＃xff0c;系统无法知道各个页面下一次在什么时候被访问3.2先进先出置换算法&＃xff08;First In First Out, FIFO)
置换最先调入内存的页面&＃xff0c;即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列&＃xff0c;从队尾进入&＃xff0c;从队首删除。但是
该算法会淘汰经常访问的页面&＃xff0c;不适应进程实际运行的规律&＃xff0c;目前已经很少使用。3.3最近最久未使用置换算法&＃xff08;Least Recently Used&＃xff0c; LRU&＃xff09;
刚被访问的页面&＃xff0c;可能马上又要被访问&＃xff1b;而较长时间内没有被访问的页面&＃xff0c;可能最近不会被访问。 LRU算法普偏地适用于各种类型的程
序&＃xff0c;但是系统要时时刻刻对各页的访问历史情况加以记录和更新&＃xff0c;开销太大&＃xff0c;因此LRU算法必须要有硬件的支持。3.4第二次机会页面置换算法
FIFO算法可能会把经常使用的页面置换出去&＃xff0c;为了避免这一问题&＃xff0c;对该算法进行简单的修改&＃xff1a;检查最老页面的R位&＃xff0c;如果R位是0&＃xff0c;那么
这个页面又老有没用&＃xff0c;可以立即置换出去&＃xff0c;如果是1&＃xff0c;就清零R位&＃xff0c;并将该页放到链表的尾端&＃xff0c;修改它的装入时间使它就像装入的一样&＃xff0c;
然后继续搜索。如果所有的页面都被访问过&＃xff0c;那么该算法就被降为纯粹的FIFO算法。3.5时钟页面置换算法
由于第二次机会页面置换算法要经常在链表中移动页面&＃xff0c;降低了效率。一个更好的办法&＃xff0c;将所有的页面存在一个类似钟表面的环形链
表中。3.6最近未使用(NRU&＃xff1a;Not Recently Used)
用R位和M位构造一个简单的页面置换算法&＃xff1a;当启动一个进程时&＃xff0c;它的所有页的两个位都由操作系统设置成0&＃xff0c;R位被定期的清零&＃xff0c;以
区别最近没有被访问的页和被访问了的页。
根据R位和M位&＃xff0c;分为4类页面
第0类&＃xff1a;没有被访问&＃xff0c;没有被修改
第1类&＃xff0c;没有被访问&＃xff0c;被修改
第2类&＃xff0c;被访问&＃xff0c;没有被修改
第3类&＃xff0c;被访问&＃xff0c;被修改。
NRU算法随机地从编号最小的非空类中挑选一个页淘汰之。这个算法隐含的意思是&＃xff0c;淘汰一个在最近一个时钟周期内没有被访问
的已修改页要比淘汰一个被频繁访问的干净的页好。4、Belady异常现象
从直觉上看&＃xff0c;在内存中的物理页面数越多&＃xff0c;程序的缺页次数应该越少&＃xff0c;但是实际情况并不是这样。Belady在1969年发现一个反例&＃xff0c;
使用FIFO算法时&＃xff0c;四个页框时缺页次数比三个页框时多。这种奇怪的情况称为Belady异常现象。5、影响缺页次数的因素
1&＃xff09;分配给程序的物理页面数
2&＃xff09;页面的大小
3&＃xff09;程序的编制方法
4&＃xff09;页面置换算法


2、计算缺页次数

理想页面&＃xff08;Optimal&＃xff0c; OPT)置换算法


先进先出置换算法&＃xff08;First In First Out, FIFO)


最近最久未使用置换算法&＃xff08;Least Recently Used&＃xff0c; LRU&＃xff09;


在一个请求页式存储管理中&＃xff0c;一个程序的页面走向为3&＃xff0c;4&＃xff0c;2&＃xff0c;1&＃xff0c;4&＃xff0c;5&＃xff0c;4&＃xff0c;3&＃xff0c;5&＃xff0c;1&＃xff0c;2&＃xff0c;并采用LRU算法。设分配给该程序的存储块
数 S 分别为3 和 4&＃xff0c;在该访问中发生的缺页次数 F