页面置换算法实现

python实现的页面置换算法:OPT,FIFO,LRU
最后输出三个算法分别的缺页数量随页框数n的变化曲线

import matplotlib.pyplot as plt

request:list= [0, 9, 8, 4, 4, 3, 6, 5, 1, 5, 0, 2, 1, 1, 1, 1, 8, 8, 5,
3, 9, 8, 9, 9, 6, 1, 8, 4, 6, 4, 3, 7, 1, 3, 2, 9, 8, 6, 2, 9, 2, 7, 2, 7, 8, 4, 2, 3, 0, 1, 9, 4,
7, 1, 5, 9, 1, 7, 3, 4, 3, 7, 1, 0, 3, 5, 9, 9, 4, 9, 6, 1, 7, 5, 9, 4, 9, 7, 3, 6, 7, 7, 4, 5, 3, 5, 3, 1, 5, 6, 1,
1, 9, 6, 6, 4, 0, 9, 4, 3]

def OPTInit():
    ret:dict= {0:[],1:[],2:[],3:[],4:[],5:[],6:[],7:[],8:[],9:[]}
    for i in range(len(request)):
        ret.get(request[i]).append(i)
    return ret

def FindUsedless(Schedule:dict,PTable:list,current:int):
    ret = []
    for each in PTable:
        flag = 0
        getApperance = Schedule.get(each)
        # 查询list中下一次出现的时候
        for i in getApperance :
            if current < i:
                ret.append(i-current)
                flag = 1
                break;
        if flag == 0 : # 没有查询到下一次的出现
            ret.append(114514)
    return ret

def MarkTheUnused(usedTime:list):
    maxtime = 0
    tag = 0
    for j in range(len(usedTime)):
        if usedTime[j] > maxtime:
            maxtime = usedTime[j]
            tag = j
    return tag

def OPT(n:int = 1):
    PTable:list = [];
    Schedule = OPTInit()
    ret = 0
    for i in range(len(request)):
        ## 没满就无脑装入
        if request[i] not in PTable:
            if len(PTable) >= n:
                usedTime:list = FindUsedless(Schedule,PTable,i) ## 寻找下一次的使用时间
                tag = MarkTheUnused(usedTime) ## 找到使用间隔最长的页表
                PTable.remove(PTable[tag]) ## 删除对应页表
            PTable.append(request[i])
            ret+=1 ## 缺页异常
    return ret

def FIFO(n:int = 1):
    PTable:list = [];
    ret = 0;
    for i in range(len(request)):
        ## 没满就无脑装入
        if request[i] not in PTable:
            if len(PTable) >= n:
                PTable.remove(PTable[0]) ## 把第一个进来的删掉
            PTable.append(request[i])
            ret+=1 ## 缺页异常
    return ret

def MarkTheLessUsed(usedTime:list):
    mintime = 114514
    tag = 0
    for j in range(len(usedTime)):
        if usedTime[j] < mintime:
            mintime = usedTime[j]
            tag = j
    return tag

def LRU(n:int = 1):
    PTable:list = [];
    UsedTimes:list = [];
    ret = 0;
    for i in range(len(request)):
        ## 没满就无脑装入
        if request[i] not in PTable:
            if len(PTable) >= n:
                tag = MarkTheLessUsed(UsedTimes)
                PTable.remove(PTable[tag]) ## 把使用最少的哪一个删掉
                UsedTimes.remove(UsedTimes[tag]) ## 对应记录使用次数的元素删掉
            PTable.append(request[i])
            UsedTimes.append(i)
            ret+=1 ## 缺页异常
        else:
            UsedTimes[PTable.index(request[i])] = i;
    return ret

DefaultInOPT = []
DefaultInLRU = []
DefaultInFIFO = []
for i in range(1,11):
    DefaultInOPT.append(OPT(i))
    DefaultInLRU.append(LRU(i))
    DefaultInFIFO.append(FIFO(i))
stick = [1,2,3,4,5,6,7,8,9,10]
fig = plt.figure()
axe = fig.add_axes([0.1,0.1,0.8,0.8])
axe.plot(stick,DefaultInOPT,label='OPT')
axe.plot(stick,DefaultInLRU,label='LRU')
axe.plot(stick,DefaultInFIFO,label='FIFO')
axe.legend()
plt.show()