[python]实现操作系统虚拟内存中的页替换算法FIFO,OPT,LRU

OPT：最佳替换算法（optional replacement）。替换下次访问距当前时间最长的页。

LRU:最近最少使用(Least Recently Used).替换上次使用距离当前最远的页。

FIFO:先进先出(First In First Out),将页面看做一个循环缓冲区，按循环方式替换。这是实现最为简单的算法，隐含的逻辑是替换驻留在内存时间最长的页。

FIFO:

BLOCKNUMBER = 3


#加载数据
def loadData():
    F = open('data')
    data = F.read().split(' ')
    F.close()
    return data

usedBlock = []
n = 0

# 将下一页加入到内存中
def loadNextPage(memory,page):
    global n

    if page not in memory:
        n += 1
        if len(memory)<BLOCKNUMBER:
            memory.append(page)
        else:
            memory.pop(0)
            memory.append(page)

    return memory

data = loadData()
for i in data:
    usedBlock = loadNextPage(usedBlock,i)
    # print(usedBlock)

print('发生缺页的次数为%s'  %n)

OPT:

BLOCKNUMBER = 3

#加载数据
def loadData():
    F = open('data')
    data = F.read().split(' ')
    F.close()
    return data

usedBlock = []
n = 0

def loadNextPage(memory,page,data):
    global n
    l = []
    if page not in memory:
        n += 1
        if len(memory) < BLOCKNUMBER:
            memory.append(page)

        else:
            for m in memory:
                for i in range(len(data)):
                    if m == data[i]:
                        l.append(i)
                        break
                    elif i == len(data)-1 and m != data[i]:
                        l.append(2147483647)
            index = l.index(max(l))

            memory.remove(memory[index])
            memory.append(page)
    return memory

data = loadData()
data2 = data.copy()
for i in data:
    data2.remove(i)
    usedBlock = loadNextPage(usedBlock,i,data2)


print('发生缺页的次数为%s'  %n)

LRU:

BLOCKNUMBER = 3


#加载数据
def loadData():
    F = open('data')
    data = F.read().split(' ')
    F.close()
    return data

usedBlock = []
n = 0

def loadNextPage(memory,page):
    global n

    if page in memory:
        memory.remove(page)
        memory.append(page)
    else:
        n += 1
        if len(memory)<BLOCKNUMBER:
            memory.append(page)
        else:
            memory.pop(0)
            memory.append(page)
    return memory


data = loadData()
for i in data:
    usedBlock = loadNextPage(usedBlock,i)

print('发生缺页的次数为%s'  %n)