OPT,LRU,FIFO页面置换算法python实现

实验三 请求页式存储管理中常用页面置换算法模拟
【开发语言及实现平台或实验环境】
C++/C#
Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET 2003

【实验目的】
（1）了解内存分页管理策略
（2）掌握调页策略
（3）掌握一般常用的调度算法
（4）学会各种存储分配算法的实现方法。
（5）了解页面大小和内存实际容量对命中率的影响。

【实验要求】
（1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响；
（2）实现OPT 算法 (最优置换算法) 、LRU 算法 (Least Recently) 、 FIFO 算法 (First IN First Out)的模拟；
（3）会使用某种编程语言。

【实验原理】
分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。
在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。
一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。
一、最佳置换算法OPT(Optimal)
它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。
二、先进先出(FIFO)页面置换算法
这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
三、最近最久未使用置换算法
1、LRU(Least Recently Used)置换算法的描述
FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

# Init
M = 4
N = 17

class page:
    def __init__(self,num,time):      
        # 记录页面号
        self.num = num  
        # 记录调入内存时间
        self.time = time

class main:
    # 初始化内存单元，缓冲区
    def __init__(self):
        # 初始化内存单元
        self.b = [page(-1,M-i-1) for i in range(0,M)]
        # 初始化内存当前状态，缓冲区
        self.c = [[-1 for i in range(0,N)] for j in range(0,M)]
        # 记录调入队列
        self.queue = []
        self.k = -1
        self.flag =-1
        self.process()

    def print_string(self):
        print("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|")

    # 取得在内存中停留最久的页面，默认状态下为最早点入的页面
    def get_max(self,b):
        max = -1
        flag = 0
        for i in range(0,M):
            if b[i].time >max:
                max = b[i].time
                flag = i
        return flag 

    # 判断页面是否已在内存中
    def equation(self,fold,b):
        for i in range(0,M):
            if fold == b[i].num:
                return i
        return -1
    # OPT 算法
    def opt(self,fold,b,index,a):
        max = -1
        val = self.equation(fold,b)
        if val >= 0:
            pass
        else:
            self.queue.append(fold)
            self.k += 1

            for j in range(0,M):
                for k in range(index+1,N):
                    if b[j].num==a[k]:
                        b[j].time = k-j
                    else:
                        b[j].time = 20

            for i in range(0, M):
                if b[i].num ==-1:
                    val = i
                    break;
                else:
                    if b[i].time > max:
                        max = b[i].time
                        val = i
            b[val].num = fold
    # LRU 算法
    def lru(self, fold, b):
        val = self.equation(fold, b)
        if val >= 0:
            b[val].time = 0
            for i in range(0, M):
                if i != val:
                    b[i].time += 1
        else:
            self.queue.append(fold)
            self.k += 1
            val = self.get_max(b)
            b[val].num = fold
            b[val].time = 0
            for i in range(0, M):
                if (i != val):
                    b[i].time += 1

    # FIFO 算法
    def fifo(self, fold, b):
        val = self.equation(fold, b)
        if val >= 0:
            pass
        else:
            self.queue.append(fold)
            self.k += 1
            self.flag += 1
            self.flag %= 4
            self.b[self.flag].num = fold


    # 打印内存状态
    def Myprint(self,a):
        self.print_string()
        for j in range(0, N):
            print("|%2d" % (a[j]), end=" ")
        print("|")
        self.print_string()
        for i in range(0, M):
            for j in range(0, N):
                if self.c[i][j] == -1:
                    print("|%2c" % (32), end=" ")
                else:
                    print("|%2d" % (self.c[i][j]), end=" ")
            print("|")
        self.print_string()
        print("调入队列为")
        for i in range(0, self.k + 1):
            print("%2d" % (self.queue[i]), end=" ")
        print("\n缺页次数为：%6d\n缺页率：%16.6f" % (self.k + 1, (float)(self.k + 1) / N))
    # 主程序
    def process(self):
        a = [1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4]

        for i in range(0, N):
            self.fifo(a[i], self.b)
            self.c[0][i] = a[i]

            # 记录当前的内存单元中的页面
            for j in range(0, M):
                self.c[j][i] = self.b[j].num
        # 结果输出
        print("fifo算法内存状态为：")
        self.Myprint(a)

        # 初始化内存单元
        self.b = [page(-1, M - i - 1) for i in range(0, M)]
        # 初始化内存当前状态，缓冲区
        self.c = [[-1 for i in range(0, N)] for j in range(0, M)]
        # 记录调入队列
        self.queue = []
        self.k = -1
        for i in range(0, N):
            self.lru(a[i], self.b)
            self.c[0][i] = a[i]

            # 记录当前的内存单元中的页面
            for j in range(0, M):
                self.c[j][i] = self.b[j].num
        # 结果输出
        print("lru算法内存状态为：")
        self.Myprint(a)

        # opt 算法
        # 初始化内存单元
        self.b = [page(-1, M - i - 1) for i in range(0, M)]
        # 初始化内存当前状态，缓冲区
        self.c = [[-1 for i in range(0, N)] for j in range(0, M)]
        # 记录调入队列
        self.queue = []
        self.k = -1
        for i in range(0, N):
            self.opt(a[i], self.b, i,a)
            self.c[0][i] = a[i]

            # 记录当前的内存单元中的页面
            for j in range(0, M):
                self.c[j][i] = self.b[j].num

        # opt 算法输出
        print("opt算法内存状态为：")
        self.Myprint(a)
if __name__ == "__main__":
    main()