设计程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。

三、程序要求：

1）利用先进先出FIFO、最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。

2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。

3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,Pn，算法选择1-FIFO，2-OPI，3-LRU。

4）输出：每种算法的缺页次数和缺页率。

四、实现提示：

用C++语言实现提示：

1）程序中进程调度时间变量描述如下：


MaxNumber = 100
PageOrder = np.zeros(MaxNumber, dtype=int)  # 页面序列 创建了一个长度为MaxNumber的整数型数组，并将所有元素初始化为零。
PageNum = 0  # 页面个数
LackNum = 0  # 缺页次数
MinBlockNum = 0  # 最小物理块数
PageDisCount = np.zeros(MaxNumber, dtype=int)  # 当前内存距离下一次出现的距离
LRUtime = np.zeros(MaxNumber, dtype=int)  # 存储队列中各个页面最近使用情况
 
LackPageRate = 0.0  # 缺页率
LackPageNum = 0  # 缺页数
VirtualQueue = np.zeros(MaxNumber, dtype=int)  # 虚拟队列

2）进程调度的实现过程如下：

变量初始化；
接收用户输入最小物理块数m，页面个数n，页面序列P1, … ,Pn，选择算法1-FIFO，2-OPI，3-LRU；
根据用户选择的算法进行页面的分配和置换，输出页面置换算法的模拟过程；
计算选择算法的缺页次数和缺页率；
输出选择算法的缺页次数和缺页率。

五、代码设计与实现

（一）程序设计

（1）最佳置换算法：

设计思想:

按照页面号引用串的顺序，依次将物理块装入页面中，当装入下一个物理块，发现当页面已满时，将在最长时间内不再被访问的页面换出。

初始化一个大小为物理块数的帧数组，用于存储当前在内存中的页面。
遍历给定的引用串中的每个页面。
对于每个页面，检查它是否已经在帧数组中。如果是，则跳过该页面并继续遍历下一个页面。
如果该页面不在帧数组中，则需要进行页面置换。找到帧数组中以后不再使用或者在最长时间内不再被访问的页面，并用当前页面替换它。
重复步骤3和4，直到遍历完引用串中的所有页面。
计算缺页次数和缺页率。

部分源代码：


def OPI():
    #缺页数、缺页率、虚拟列表、当前内存距离下一次出现的距离
    global LackPageNum, LackPageRate, VirtualQueue, PageDisCount
    print("********* 你选择了OPI算法：********* ")
    print("页面置换情况如下:")
    initial()
 
    isInQueue = False
    point = 0#指向最长时间未被访问的下标
    for i in range(MinBlockNum, PageNum):
        isInQueue = PageOrder[i] in VirtualQueue
 
        if not isInQueue:
            LackPageNum += 1
            for s in range(MinBlockNum):
                dis = 1#表示队列每个值距离下一次访问的距离
                # 从页面序列的第i个位置开始找起
                for t in range(i, PageNum):
                    if VirtualQueue[s] != PageOrder[t]:
                        dis += 1
                    else:
                        break
                PageDisCount[s] = dis
            #指向当前虚拟列表中数据在后面最晚出现的
            point = np.argmax(PageDisCount)
 
            VirtualQueue[point] = PageOrder[i]
            display()
 
    LackPageRate = LackPageNum / PageNum
    print(f"缺页数LackPageNum = {LackPageNum}")
    print(f"缺页率LackPageRate = {LackPageRate}")

（2）先进先出(FIFO)页面置换算法

设计思想：

把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，使它总是指向最老的页面；每次淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

初始化一个大小为物理块数的帧数组，用于存储当前在内存中的页面。
遍历给定的引用串中的每个页面。
对于每个页面，检查它是否已经在帧数组中。如果是，则跳过该页面并继续遍历下一个页面。
如果该页面不在帧数组中，则需要进行页面置换。选择最早进入内存的页面进行置换，并用当前页面替换它。
重复步骤3和4，直到遍历完引用串中的所有页面。
计算缺页次数和缺页率。

部分源代码：


def FIFO():
    # 总缺页数、缺页率、虚拟队列
    global LackPageNum, LackPageRate, VirtualQueue
    print("********* 你选择了FIFO算法：********* ")
    print("页面置换情况如下:")
    initial()
 
    isInQueue = False
    point = 0#指向最老的页面
    for i in range(MinBlockNum, PageNum):
        isInQueue = PageOrder[i] in VirtualQueue
        # 如果当前页面不在队列中
        if not isInQueue:
            LackPageNum += 1#缺页数加1
            VirtualQueue[point] = PageOrder[i]
            display()
            point = (point + 1) % MinBlockNum
            #当point指向队尾后一位的时候，将point重新指向队首
 
    LackPageRate = LackPageNum / PageNum
    print(f"缺页数LackPageNum = {LackPageNum}")
    print(f"缺页率LackPageRate = {LackPageRate}")

（3）LRU（Least Recently Used）置换算法

设计思想：

赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当需淘汰一个页面时，选择现有页面中其t值最大的，即最久未使用的页面予以淘汰。

初始化一个大小为物理块数的帧数组，用于存储当前在内存中的页面。
初始化一个大小为物理块数的时间数组，用于记录每个页面最近被访问的时间。
遍历给定的引用串中的每个页面。
对于每个页面，检查它是否已经在帧数组中。如果是，则更新该页面在时间数组中对应的值，并跳过该页面继续遍历下一个页面。
如果该页面不在帧数组中，则需要进行页面置换。选择时间数组中值最小的页面进行置换，并用当前页面替换它，同时更新该页面在时间数组中对应的值。
重复步骤4和5，直到遍历完引用串中的所有页面。
计算缺页次数和缺页率。

部分源代码：


def LRU():
    #缺页数、缺页率、虚拟列表、存储队列中各个页面最近使用情况
    global LackPageNum, LackPageRate, VirtualQueue, LRUtime
    print("********* 你选择了LRU算法：********* ")
    print("页面置换情况如下:")
 
    initial()
    isInQueue = False
    point = 0#指向最长时间未被访问的下标
   
 
    for i in range(MinBlockNum, PageNum):
        isInQueue = PageOrder[i] in VirtualQueue#序列第i个页是否在队列里
        #如果不在队列里
        if not isInQueue:
            LackPageNum += 1#缺页数+
            point = np.argmax(LRUtime)#指针指向最久未使用的
            for j in range(MinBlockNum):
                if VirtualQueue[j] != VirtualQueue[point]:
                    LRUtime[j] += 1
 
            VirtualQueue[point] = PageOrder[i]#将PageOrder[i]放入VirtualQueue中最久未使用的位置
            LRUtime[point] = 0
 
            display()
        # 如果PageOrder[i]在VirtualQueue中
        else:
            for s in range(MinBlockNum):
                if VirtualQueue[s] != PageOrder[i]:
                    LRUtime[s] += 1
                else:
                    LRUtime[s] = 0
 
    LackPageRate = LackPageNum / PageNum
    print(f"缺页数LackPageNum = {LackPageNum}")
print(f"缺页率LackPageRate = {LackPageRate}")

总代码：


import numpy as np
 
MaxNumber = 100
PageOrder = np.zeros(MaxNumber, dtype=int)  # 页面序列 创建了一个长度为MaxNumber的整数型数组，并将所有元素初始化为零。
PageNum = 0  # 页面个数
LackNum = 0  # 缺页次数
MinBlockNum = 0  # 最小物理块数
PageDisCount = np.zeros(MaxNumber, dtype=int)  # 当前内存距离下一次出现的距离
LRUtime = np.zeros(MaxNumber, dtype=int)  # 存储队列中各个页面最近使用情况
 
LackPageRate = 0.0  # 缺页率
LackPageNum = 0  # 缺页数
VirtualQueue = np.zeros(MaxNumber, dtype=int)  # 虚拟队列
 
 
def input_data():
    global MinBlockNum, PageNum, PageOrder
    MinBlockNum = int(input("请输入最小物理块数: "))
    PageNum = int(input("请输入页面个数: "))
    PageOrder = list(map(int, input("请输入页面序列（以空格分隔）: ").split()))
 
    print("读取数据结果如下：")
    print(f"最小物理块数 = {MinBlockNum}")
    print(f"页面个数 = {PageNum}")
    print("页面序列如下:")
    print(" ".join(map(str, PageOrder)))
 
 
def initial():
    # 总缺页数、缺页率、当前内存距离下一次出现的距离、虚拟队列、存储队列中各个页面最近使用情况
    global LackPageNum, LackPageRate, PageDisCount, VirtualQueue, LRUtime
    LackPageNum = MinBlockNum
    LackPageRate = 0.0
 
    PageDisCount = np.zeros(MaxNumber, dtype=int)
    VirtualQueue = np.full(MaxNumber, -1, dtype=int)
    LRUtime = np.zeros(MinBlockNum, dtype=int)
 
    for i in range(MinBlockNum):
        isInQueue2 = VirtualQueue[:i].__contains__(PageOrder[i]) #用于判断PageOrder[i]是否在子列表中
        if not isInQueue2:
            VirtualQueue[i] = PageOrder[i]
            for k in range(i):
                LRUtime[k] += 1#之前的页面对应的时间+1
            display()
        else:
            LRUtime[i] = 0#重新更新为0，表示最近刚刚使用
 
 
def FIFO():
    # 总缺页数、缺页率、虚拟队列
    global LackPageNum, LackPageRate, VirtualQueue
    print("********* 你选择了FIFO算法：********* ")
    print("页面置换情况如下:")
    initial()
 
    isInQueue = False
    point = 0#指向最老的页面
    for i in range(MinBlockNum, PageNum):
        isInQueue = PageOrder[i] in VirtualQueue
        # 如果当前页面不在队列中
        if not isInQueue:
            LackPageNum += 1#缺页数加1
            VirtualQueue[point] = PageOrder[i]
            display()
            point = (point + 1) % MinBlockNum
            #当point指向队尾后一位的时候，将point重新指向队首
 
    LackPageRate = LackPageNum / PageNum
    print(f"缺页数LackPageNum = {LackPageNum}")
    print(f"缺页率LackPageRate = {LackPageRate}")
 
 
def OPI():
    #缺页数、缺页率、虚拟列表、当前内存距离下一次出现的距离
    global LackPageNum, LackPageRate, VirtualQueue, PageDisCount
    print("********* 你选择了OPI算法：********* ")
    print("页面置换情况如下:")
    initial()
 
    isInQueue = False
    point = 0#指向最长时间未被访问的下标
    for i in range(MinBlockNum, PageNum):
        isInQueue = PageOrder[i] in VirtualQueue
 
        if not isInQueue:
            LackPageNum += 1
            for s in range(MinBlockNum):
                dis = 1#表示队列每个值距离下一次访问的距离
                # 从页面序列的第i个位置开始找起
                for t in range(i, PageNum):
                    if VirtualQueue[s] != PageOrder[t]:
                        dis += 1
                    else:
                        break
                PageDisCount[s] = dis
            #指向当前虚拟列表中数据在后面最晚出现的
            point = np.argmax(PageDisCount)
 
            VirtualQueue[point] = PageOrder[i]
            display()
 
    LackPageRate = LackPageNum / PageNum
    print(f"缺页数LackPageNum = {LackPageNum}")
    print(f"缺页率LackPageRate = {LackPageRate}")
 
 
def LRU():
    #缺页数、缺页率、虚拟列表、存储队列中各个页面最近使用情况
    global LackPageNum, LackPageRate, VirtualQueue, LRUtime
    print("********* 你选择了LRU算法：********* ")
    print("页面置换情况如下:")
 
    initial()
    isInQueue = False
    point = 0#指向最长时间未被访问的下标
 
 
    for i in range(MinBlockNum, PageNum):
        isInQueue = PageOrder[i] in VirtualQueue#序列第i个页是否在队列里
        #如果不在队列里
        if not isInQueue:
            LackPageNum += 1#缺页数+
            point = np.argmax(LRUtime)#指针指向最久未使用的
            for j in range(MinBlockNum):
                if VirtualQueue[j] != VirtualQueue[point]:
                    LRUtime[j] += 1
 
            VirtualQueue[point] = PageOrder[i]#将PageOrder[i]放入VirtualQueue中最久未使用的位置
            LRUtime[point] = 0
 
            display()
        # 如果PageOrder[i]在VirtualQueue中
        else:
            for s in range(MinBlockNum):
                if VirtualQueue[s] != PageOrder[i]:
                    LRUtime[s] += 1
                else:
                    LRUtime[s] = 0
 
    LackPageRate = LackPageNum / PageNum
    print(f"缺页数LackPageNum = {LackPageNum}")
    print(f"缺页率LackPageRate = {LackPageRate}")
 
 
def display():
    for i in range(MinBlockNum):
        if VirtualQueue[i] >= 0:
            print(VirtualQueue[i], end=" ")
    print()
 
 
def main():
    input_data()
 
    isContinue = 1
    while isContinue:
        print("******************************************************")
        print("********* 请选择算法    **********")
        print("********* 1代表FIFO算法 **********")
        print("********* 2代表OPI算法  **********")
        print("********* 3代表LRU算法  **********")
        chooseAlgorithm = int(input())
        if chooseAlgorithm == 1:
            FIFO()
        elif chooseAlgorithm == 2:
            OPI()
        elif chooseAlgorithm == 3:
            LRU()
        else:
            print("请输入正确的序号进行选择：")
 
        print("********** 是否继续选择算法?              **********")
        print("********** 输入1代表继续，输入0代表退出！ **********")
        isContinue = int(input())
 
    print("***************************结束***************************")
 
 
if __name__ == "__main__":
    main()

（二）运行结果

实例1：

输入：

输出：

（1）FIFO算法运行结果

（2）OPI算法运行结果

（3）LRU算法运行结果

实例2

输入：

输出：

（1）FIFO算法运行结果

（2）OPI算法运行结果

（3）LRU算法运行结果

六、总结

页面置换算法是在内存已满且需要访问的页面不在内存中时，选择一个内存中的页面换出的方法。不同的算法有不同的选择标准和效率。
最佳置换算法是选择在未来最长时间内不再被访问的页面换出，它可以保证最低的缺页率和置换率，但是它是无法实现的，因为我们无法预知未来的页面访问情况。
先进先出置换算法是选择最先进入内存的页面换出，它实现简单，但是效率不高，可能会导致经常被访问的页面被频繁地换出。
最近最久未使用置换算法是选择最久没有被访问的页面换出，它是根据过去的页面访问情况来预测未来的访问情况，但是这种预测并不一定准确，因此它的效率也不是很高。
先进先出置换算法的性能之所以差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。LRU置换算法是根据页面调入内存后的使用情况做出决策的。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/687597