操作系统实验五：存储管理设计

import numpy as np
import matplotlib.pyplot as plt
# 产生一个指令序列
def produceAddstream():
    instruct = []
    m = np.random.randint(0, 319) #在 [0，319] 的指令地址之间随机选取一起点 m
    # 每次循环生成 4 条，所以需要循环 80 次
    for i in range(80):
        instruct.append(m+1) # 顺序 执行一条指令，即执行地址为 m+1 的指令；
        n = np.random.randint(0, m+1) #在前地址 [0，m+1] 中随机选取一条指令
        instruct.append(n)   # 前地址,执行地址为 n 的指令
        instruct.append(n+1) # 顺序,n+1
        m = np.random.randint(n+2, 319) #后地址 [n+2，319] 中随机选取一条指令并执行
        instruct.append(m)   # 后地址
        # print(instruct) # [143, 40, 41, 101]
    return instruct #能看到最终的效果，但难以估计准确性，因此根据书本上的例子给出了一份测试数据
    # return [70, 0, 10, 20, 0, 30, 0, 40, 20, 30, 0, 30, 20, 10, 20, 0, 10, 70, 0, 10]
# # 置换算法的核心：遍历中，判断1.不在用户内存中，2.此时用户内存满了
# def alg(n, ins):
#     """置换算法"""
#     hit = 0       # 命中的个数
#     user_mem = [] # 用户内存
#     # 遍历所有指令
#     for (ind, i) in enumerate(ins):
#         # 如果命中 #每k存放10条指令排列虚存地址,i//10得到指令所在的页数
#         if (i//10) in user_mem:  # 命中的操作
#         else:
#             if len(user_mem) == n: # 如果用户内存已满
#                 # 内存满的操作，移出一个页面
#             user_mem.append(i//10)
#     return hit / len(ins) # 计算命中率 「命中次数」除以「指令总数」
def FIFO(n, ins):
    """先进先出置换算法"""
    user_mem = []
    hit = 0
    for i in ins:
        if i // 10 in user_mem:
            hit += 1
        else:
            if len(user_mem) == n:
                user_mem.pop(0) # 最前面的 移除内存
            user_mem.append(i // 10) # 移入内存
    return hit / len(ins)
def OPT(n, ins):
    """最佳置换算法：最近不在访问"""
    hit = 0
    user_mem = []
    dic = dict.fromkeys(range(32), []) #字典大小=页面个数
    # 使用字典来保存下一个指令的位置 键：「页号」，值：「指令位置数组」
    for (ind, i) in enumerate(ins):
        # 这里不能使用 append
        dic[i // 10] = dic[i // 10] + [ind]
    for (ind, i) in enumerate(ins):
        # 更新字典
        dic[i // 10].pop(0)
        if (i // 10) in user_mem:
            hit += 1
        else:
            if len(user_mem) == n:
                temp = [321] * n
                for (index, page) in enumerate(user_mem):
                    if len(dic[page]) > 0:
                        temp[index] = dic[page][0] #比较「指令位置数组」的第一个元素的大小
                user_mem.pop(np.argmax(temp)) #删除最大指令对应的页号
            user_mem.append(i // 10)
    return hit / len(ins)
def LRU(n, ins):
    """最近最久未使用置换算法：访问的早晚"""
    user_mem = []
    hit = 0
    for i in ins:
        if i // 10 in user_mem:
            hit += 1
            temp = user_mem.pop(user_mem.index(i//10))
            user_mem.append(temp) #删除后将该页面放在最后面
        else:
            if len(user_mem) == n:
                user_mem.pop(0) #最前面的页面删除
            user_mem.append(i//10)
    return hit / len(ins)
def LFU(n, ins):
    """最少使用置换算法：最近一段时间内，被访问的次数"""
    user_mem = []
    hit = 0
    for (ind, i) in enumerate(ins):
        if i // 10 in user_mem:
            hit += 1
        else:
            if len(user_mem) == n:
                temp = [0] * n
                # 使用前 50 条指令来测试，如果不足 50 就从开头
                for item in ins[max(0, ind - 20):ind]:
                    # 统计内存中的页在接下来20条里被访问的次数
                    for k in range(n):
                        if user_mem[k] == item // 10:
                            temp[k] += 1
                            break
                # 访问次数最少的淘汰
                user_mem.pop(np.argmin(temp))
            user_mem.append(i // 10)
    return hit / len(ins)
def main():
    """主函数"""
    ins = produceAddstream()
    result = np.zeros([4, 29])
    x = np.arange(4, 33)
    print('k     FIFO        LRU        OPT         LFU')
    for i in x:
        result[0, i-4] = OPT(i, ins)
        result[1, i-4] = FIFO(i, ins)
        result[2, i-4] = LRU(i, ins)
        result[3, i-4] = LFU(i, ins)
        print(i,'  ',result[0, i-4],'  ',result[1, i-4],'  ',result[2, i-4],'  ',result[3, i-4])
    # 画图
    plt.figure(figsize=(8, 4))
    plt.plot(x, result[0], label="OPT")
    plt.plot(x, result[1], label="FIFO")
    plt.plot(x, result[2], label="LRU")
    plt.plot(x, result[3], label="LFU")
    plt.legend()
    plt.show()
    return
main()