欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

操作系统--页面置换算法--FIFO,OPT,LRU

程序员文章站 2022-07-05 08:05:36
...

代码如下:

"""FIFO,LRU,OPT三种而页面置换算法"""
import random
import copy
from collections import deque

Max_Number = int(input("input the Max_num:"))
Physical_block = int(input("input block num:"))
Page_order = []
Simulator = []
Page_counter = []
Page_num, Lack_num = 0, 0
Lack_page_rate = 0


def initial():
    global Page_order, Simulator, Page_num, Page_counter
    Page_num = Max_Number
    for i in range(Page_num):
        Page_order.append(random.randint(0, 8))
    Page_counter = [0 for _ in range(Physical_block)]
    Simulator = [[] for _ in range(Page_num)]


def display():
    print("页面序列:", Page_order)
    print("页块:", Physical_block)
    print("页面存在序列:", Simulator)
    print("缺页次数:", Lack_num)
    print("缺页比例:", Lack_page_rate)


def lru():
    global Simulator, Lack_num, Lack_page_rate
    count = 0
    while count < len(Page_order):
        length = len(Simulator[abs(count-1)])
        if length < Physical_block:
            if count == 0:
                Simulator[count].append(Page_order[count])
                Page_counter[count] = 0
            else:
                # 要用深拷贝,不然后面的改了一个序列,前面的也会变
                temp = copy.deepcopy(Simulator[count-1])
                if Page_order[count] in temp:
                    Simulator[count] = temp
                    index = Simulator[count].index(Page_order[count])
                    Page_counter[index] = 0
                    for i in range(len(Simulator[count])):
                        if i == index:
                            Page_counter[i] = 0
                        else:
                            Page_counter[i] += 1
                else:
                    Simulator[count] = temp
                    Simulator[count].append(Page_order[count])
                    for i in range(len(Simulator[count])):
                        if i == len(Simulator[count])-1:
                            Page_counter[i] = 0
                        else:
                            Page_counter[i] += 1
        else:
            temp = copy.deepcopy(Simulator[count-1])
            Simulator[count] = temp
            if Page_order[count] in temp:
                index = Simulator[count].index(Page_order[count])
                Page_counter[index] = 0
                for i in range(Physical_block):
                    if i == index:
                        Page_counter[i] = 0
                    else:
                        Page_counter[i] += 1
            elif Page_order[count] not in temp:
                Lack_num += 1
                maxi = max(Page_counter)
                index = Page_counter.index(maxi)
                Simulator[count][index] = Page_order[count]
                Page_counter[index] = 0
                for i in range(Physical_block):
                    if i == index:
                        Page_counter[i] = 0
                    else:
                        Page_counter[i] += 1
        Lack_page_rate = round(Lack_num/len(Page_order), 2)
        count += 1
    display()
    initial()


def opt():
    """理论上是实现不了的"""
    global Simulator, Lack_num, Lack_page_rate
    count = 0
    while count < len(Page_order):
        length = len(Simulator[abs(count-1)])
        if length < Physical_block:
            if count == 0:
                Simulator[count].append(Page_order[count])
            else:
                temp = copy.deepcopy(Simulator[count-1])
                if Page_order[count] not in temp:
                    Simulator[count] = temp
                    Simulator[count].append(Page_order[count])
                else:
                    Simulator[count] = temp
        else:
            temp = copy.deepcopy(Simulator[count-1])
            Simulator[count] = temp
            if Page_order[count] not in temp:
                inde = [0 for _ in range(Physical_block)]
                indi = 0
                for item in temp:
                    if item in Page_order[count:]:
                        inde[indi] = Page_order[count:].index(item)
                    else:
                        inde[indi] = 999
                    indi += 1
                maxi = max(inde)
                index = inde.index(maxi)
                Simulator[count][index] = Page_order[count]
                Lack_num += 1
            else:
                pass
        count += 1
    Lack_page_rate = round(Lack_num/len(Page_order), 2)
    display()
    initial()


def fifo():
    global Simulator, Lack_num, Lack_page_rate
    count = 0
    Simulator = [deque() for _ in range(len(Page_order))]
    while count < len(Page_order):
        length = len(Simulator[abs(count-1)])
        if length < Physical_block:
            if count == 0:
                Simulator[count].append(Page_order[count])
            else:
                temp = copy.deepcopy(Simulator[count-1])
                Simulator[count] = temp
                if Page_order[count] not in Simulator[count-1]:
                    Simulator[count].append(Page_order[count])
        else:
            temp = copy.deepcopy(Simulator[count-1])
            Simulator[count] = temp
            if Page_order[count] not in temp:
                Lack_num += 1
                Simulator[count].popleft()
                Simulator[count].append(Page_order[count])
        count += 1
    Lack_page_rate = round(Lack_num/len(Page_order), 2)
    display()
    initial()


if __name__ == '__main__':
    initial()
    # lru()
    # fifo()
    opt()