opt, lru, fifo, lfu等頁面置換算法的python實作

頁面置換算法（opt, lru, fifo, lfu) python

（1） 通過計算不同算法的命中率比較算法的優劣。同時也考慮了使用者記憶體容量對命中率的影響。

頁面失效次數為每次通路相應指令時，該指令所對應的頁不在記憶體中的次數。

在本實驗中，假定頁面大小為1k，使用者虛存容量為32k，使用者記憶體容量為4頁到32頁。

（2） produce_addstream通過随機數産生一個指令序列，共320條指令。

A、 指令的位址按下述原則生成：

1） 50%的指令是順序執行的

2） 25%的指令是均勻分布在前位址部分

3） 25%的指令是均勻分布在後位址部分

B、 具體的實施方法是：

1） 在[0，319]的指令位址之間随機選取一起點m；

2） 順序執行一條指令，即執行位址為m+1的指令；

3） 在前位址[0，m+1]中随機選取一條指令并執行，該指令的位址為m’；

4） 順序執行一條指令，位址為m’+1的指令

5） 在後位址[m’+2，319]中随機選取一條指令并執行；

6） 重複上述步驟1）~5），直到執行320次指令

C、 将指令序列變換稱為頁位址流

在使用者虛存中，按每k存放10條指令排列虛存位址，即320條指令在虛存中的存放方式為：

第0條~第9條指令為第0頁（對應虛存位址為[0，9]）；

第10條~第19條指令為第1頁（對應虛存位址為[10，19]）；

。。。。。。

第310條~第319條指令為第31頁（對應虛存位址為[310，319]）；

按以上方式，使用者指令可組成32頁。

（3） 計算并輸出下述算法在不同記憶體容量下的命中率。

1） 最佳置換算法（OPT）；

2） 先進先出算法（FIFO）；

3） 最近最久未使用頁面置換（LRU）；

4） 最少使用頁面淘汰算法(LFU）

代碼如下

"""
 存儲管理
"""
import random

random.seed(2019)
stream = []  # 頁面走向
Len = 320  #


def produce_addstream():
    """
    1）	50%的指令是順序執行的
    2）	25%的指令是均勻分布在前位址部分
    3）	25%的指令是均勻分布在後位址部分
    :return:
    """
    ret = []
    count = 320
    while count > 0:
        count -= 4
        m = random.randint(0, 319)
        pre = random.randint(0, m + 1)
        next = random.randint(pre + 2, 319)
        ret.extend([m + 1, pre, pre + 1, next])
        print(m + 1, pre, pre + 1, next)
    print("位址流", ret)
    return [(i - 1) // 10 for i in ret]


def fifo(seq):
    ps = []
    miss = 0
    for size in range(4, 33):
        for page in seq:
            if page not in ps:
                if len(ps) < size:
                    ps.append(page)
                else:
                    ps.pop(0)
                    ps.append(page)
                miss += 1
        print("記憶體為{}k時的命中率為{:.2%}".format(size, 1 - miss / Len))
        miss = 0


def lru(seq):
    ps = []
    miss = 0
    for size in range(4, 33):
        for page in seq:
            if page not in ps:
                if len(ps) < size:
                    ps.append(page)
                else:
                    ps.pop(0)
                    ps.append(page)
                miss += 1
            else:
                ps.append(ps.pop(ps.index(page)))  # 彈出後插入到最近剛剛通路的一端
        print("記憶體為{}k時的命中率為{:.2%}".format(size, 1 - miss / Len))
        miss = 0


def opt(seq):
    """"
    最佳置換算法，其所選擇的被淘汰的頁面将是以後永不使用的，或是在最長（未來）時間内不再被通路的頁面。
    """

    def find_eliminated(start):
        temp = {}
        for _, i in enumerate(seq[start:]):
            if i in ps and i not in temp:
                temp[ps.index(i)] = _
            if len(temp) == len(ps):
                break
        if len(temp) < len(ps):
            for i in range(len(ps)):
                if i not in temp:
                    return i
        # all in ps, find max one
        mx, j = 0, 0
        for i, v in temp.items():
            if v > mx:
                mx = v
                j = i
        return j

    ps, miss, eliminated = [], 0, -1
    for size in range(4, 33):
        for index, page in enumerate(seq):
            if page not in ps:
                if len(ps) < size:
                    ps.append(page)
                else:
                    ps.pop(find_eliminated(index + 1))
                    ps.append(page)
                miss += 1
        print("記憶體為{}k時的命中率為{:.2%}".format(size, 1 - miss / Len))
        miss = 0


def lfu(seq):
    """
    LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一個資料在最近一段時間内使用次數很少，
    那麼在将來一段時間内被使用的可能性也很小”的思路。
    """

    ps, miss, bad, bad_i = {}, 0, 1 << 31 - 1, 0
    for size in range(4, 33):
        for i, page in enumerate(seq):
            if page not in ps:
                if len(ps) < size:  # 記憶體還未滿
                    ps[page] = 1
                else:
                    for j, v in ps.items():
                        if v < bad:
                            bad, bad_i = v, j
                    ps.pop(bad_i)
                    ps[page] = 1
                    bad, bad_i = 2 ** 32 - 1, 0
                miss += 1
            else:
                ps[page] += 1
        print("記憶體為{}k時的命中率為{:.2%}".format(size, 1 - miss / Len))
        miss = 0


pair = {1: opt, 2: fifo, 3: lru, 4: lfu}
if __name__ == "__main__":
    prompt = """"There are algorithms in the program
            1、	Optimization algorithm
            2、	First in first out algorithm
            3、	Least recently used algorithm
            4、	Least frequently used algorithm
            """
    print("Start memory management")
    print("Producing address flow, wait for a while, please...")
    stream = produce_addstream()
    print("位址頁号流", stream)
    while True:
        print(prompt)
        opt = int(input("Select an algorithm number, please."))
        while opt not in pair:
            print("There is not the algorithm in the program!")
            print(prompt)
            opt = int(input("Select an algorithm number, please."))
        pair[opt](stream)  # 執行對應的算法
        if input("Do you want try again with another algorithm(y/n)") == "n":
            break