博客

页面置换算法模拟
算法原理：

• 1.先进先出页面置换算法
  每次置换最先调入内存的页面，即将内存中等待时间最长的页面进行置换。 此算法的适用范围是顺序结构程序。在操作系统中，若发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断 时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。 将哪些页面调入调出，就需要根据算法来确定
• 2.最近最久未使用页面置换算法
  当需要淘汰某页面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。

算法：
假设某进程运行的页面走向序列7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,7，系统分配给该进程运行的最小物理块数为3。则使用高级程序设计语言分别实现先进先出页面置换和最近最久未使用页面置换。

代码：
需注意三个函数进行不同封装

#先来先服务

class FIFO(object):
    # b_num代表进程运行的最小物理块
    # 因为采用循环队列表示内存中分配的空闲物理块,故而要牺牲一块物理块,便于循环队列的队满和队空的判断
    def __init__(self, b_num=3):
        self.b_num = b_num
        self.sq = []  # 物理块队列,默认空

    # 先来先服务算法,参数p代码需要调度的页面列表
    def Fifo(self, p):
        # 循环遍历页面列表
        for i in range(len(p)):
            print("{0}、页面{1}的处理情况: ".format(i + 1, p[i]))  # 判断页面是否己经在循环队列中
            if p[i] in self.sq:
                flag = 1  # 在队列中标记flag为1
            else:
                flag = 0  # 否则为0
            if flag == 1:
                print("页面{0}已在内存中,不发生缺页".format(p[i]))
                print("内存页面分布情况: ", end=" ")
                print(self.sq, end=' \n ')
                continue
            if flag == 0:
                # 队列是否已满,即是否还有空闲物理块
                if len(self.sq) >= self.b_num:  # 已满
                    print("无空闲的物理块发生缺页中断:页面{0}换出内存,页面{1}换入内存".format(self.sq[0], p[i]))
                    self.sq.pop(0)  # 队首出队
                    self.sq.append(p[i])  # 页面入队尾print("内存页面分布情况: " ,end=' ')print(self.sq,end= ' in ')
                else:  # 未满
                    print("尚有空闲的物理块,则页面{0}直接调入内存".format(p[i]))
                    self.sq.append(p[i])  # 页面入队尾
                    print("内存页面分布情况: ", end=" ")
                    print(self.sq,end='\n')
# 最近最久未使用算法

class LRU(object):
    def __init__(self, maxsize):
        self.maxsize = maxsize  # 物理块数目
        self.buff = {}  # buff字典表示内存分配给进程的空闲物理块
        # #key : value,key代表页号, value代表访问次数
        # 依据被访问次数来模拟页面最近最久未使用的频率,数值越大则表示最近最久未使用,页面予以淘汰

    def showInfo(self):
        print("内存页面分布情况{页号:访问次数}: ", end=' ')
        print(self.buff)

    def Lru(self, p):
        # 循环遍历页面列表
        for i in range(len(p)):
            key = p[i]  # 记录当前页面为key,便于下文按key查找字典
            print("{0}、页面{1}的处理情况:".format(i + 1, key))
            # 按key查找字典,以p[i]为key
            if key in self.buff:  # 命中,则对应的访问次数设为0,其余访问次数增1
                print("页面{0}已在内存中,不发生缺页".format(p[i]))
                for k in self.buff.keys():
                    if k == key:
                        self.buff[k] = 0
                    else:
                        self.buff[k] += 1
                # 字典按照value进行降序排序
                self.buff = dict(sorted(self.buff.items(), key=lambda item: item[1], reverse=True))
                self.showInfo()
                continue
            # 当self.buff字典的长度没超过设定的物理块数目,即物理块未满
            if len(self.buff) < self.maxsize:
                print("尚有空闲的物理块,则页面{0}直接换入内存".format(key))
                # 所有页面的访问次数增1
                for k in self.buff.keys():
                    self.buff[k] += 1
                # 添加新页面,且该页面的访问次数是0
                self.buff.update({key: 0})
                self.buff = dict(sorted(self.buff.items(), key=lambda item: item[1], reverse=True))
                self.showInfo()
                continue
            # 默认情况,缺页
            # 所有页面的访问次数增1
            for k in self.buff.keys():
                self.buff[k] += 1
            self.buff = dict(sorted(self.buff.items(), key=lambda item: item[1], reverse=True))  # 取字典第一个元素的key
            k = list(self.buff.keys())[0]
            print("无空闲的物理块发生缺页中断:页面{0}换出内存,页面{1}换入内存".format(k, key))
            # 按key删除对应的元素
            del self.buff[k]
            # 添加新页面,且该页面的访问次数是0
            self.buff.update({key: 0})
            self.showInfo()

 #入口函数
from FIFOV2 import *
from LRUV2 import *

if __name__ == '__main__':
    a = input("输入操作码:\n"
              "1:FIFO;    2:LRU;    3:退出\n")
    p = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 7]
    if a == "1":
        fifo = FIFO()
        fifo.Fifo(p)
    elif a == "2":
        lru = LRU(3)
        lru.Lru(p)
    elif a == "3":
        exit(0)
    else:
        print("操作码输入错误，退出程序")
        exit(1)

转载博客请注明出处，谢谢