虚拟存储管理中几种缺页中断算法计算逻辑

2023-04-25 11:49 由小顾变老顾发表于 #软件设计

题目一：在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的页面序列是1，2，3，4，1，2，5，1，2，3，4，5.假定分配给该作业的页数为3且作业初始时未装载页面，那么采用FIFO调度算法产生的缺页中断数为多少，采用LRU调度算法产生的缺页中断数为多少？

解析：

FIFO调度算法：先进先出原则，当内存中存在，则保持不变；不存在，则将右侧调出，左侧调入内存；

整体操作逻辑如下：

最核心的是绿色背景的这几个操作，由于1,2,5存在，就不会产生缺页中断。

经上图分析，FIFO算法产生的缺页中断树是9；总访问页数是12，所以缺页中断率 = 缺页中断次数 / 总访问页数＝ 9 / 12

而LRU调度算法，采用的是最近最少使用算法，当内存中存在，则把存在的调入到最前面，这样做的好处是，对于使用比较频繁的数据，无需重复加载，能够提高性能；

整体操作逻辑如下：

可以看到，绿色背景处，存在次序调换的操作，这种操作，能重新激活已存在的内存，让其延迟调出。

经上图分析，FIFO算法产生的缺页中断树是10；总访问页数是12，所以缺页中断率 = 缺页中断次数 / 总访问页数＝ 10 / 12

题目二：

某虚拟存储系统采用最近最少使用（LRU）页面淘汰算法，假定系统为每个作业分配4个页面的主存空间，其中一个页面用来存放程序。现有某作业的
程序如下：
Var A: Array[1..100，1..100] OF integer;
i，j: integer;
FOR i:=1 to 100 DO
FOR j:=1 to 100 DO
A[i，j]:=0;
设每个页面可存放200个整数变量，变量i、j存放在程序页中。初始时，程序及i、j均已在内存，其余3页为空。若矩阵A按行序存放，那么当程序执行完后共产
生（ 1）次缺页中断；若矩阵A按列序存放，那么当程序执行完后共产生（ 2）次缺页中断。
1 A.50,B.100,C.5000,D.10000
2.A.50,B.100,C.5000,D.10000

解答：

此问题的前置条件是，每页数据中行列的分布情况，按照每行100条数据，总共两行来分布，可以存在的总数刚好是200个整数变量；

此问题考察的并非是最近最少，而是最简单的缺页中断

如果按照行存储的话，那么很明显每200条中断一次，总共是10000/200=50次

如果按照列存储的话，就变成如下情况了：

再看看程序里的访问方式：

Array[0,0]、Array[0,1],Array[0,2]、Array[0,3],...Array[0,100]。每两个数，就得中断换页一次，第一行就中断50次，总共100行，供中断50*100 = 5000次

所以答案是：1：A;2:C