操作系统-内存管理-局部/全局页置换策略的比较

问题描述

????????编写一个程序，该程序能说明当有两个进程的简单情况下，使用局部页置换策略和全局页置换策略的差异。读者将会用到能生成一个基于统计模型的页面访问串的例程。这个模型有N个状态，从0到N-1，代表每个可能的页面访问，每个状态i相关的概率pi代表下一次访问仍指向同一页面的几率。否则，下一次页面访问将以等概率指向其他任何一个页面。

代码实现思路

import random


def generate_page_sequence(N, pi):
    sequence = []
    while True:
        next_state = random.choices([i for i in range(N)], pi)[0]
        if next_state == 0:  # 0代表退出状态
            break
        sequence.append(next_state)
    return sequence


def simulate_local_page_replacement(pi, N, M):
    sequence = generate_page_sequence(N, pi)
    local_history = [0] * N  # 局部历史记录
    page_faults = 0  # 页面错误数
    for page in sequence:
        if page not in local_history:  # 页面错误
            local_history.append(page)  # 更新局部历史记录
            page_faults += 1  # 增加页面错误数
        else:  # 页面命中
            if len(local_history) > M:  # 如果局部历史记录超出阈值，进行页面替换
                local_history.pop(0)  # 移除最早的页面访问记录
                local_history.append(page)  # 更新局部历史记录
    return page_faults  # 返回页面错误数


def simulate_global_page_replacement(pi, N, M):
    sequence = generate_page_sequence(N, pi)
    global_history = set()  # 全局历史记录（使用集合来存储页面访问）
    page_faults = 0  # 页面错误数
    for page in sequence:
        if page not in global_history:  # 页面错误
            global_history.add(page)  # 更新全局历史记录
            page_faults += 1  # 增加页面错误数
        else:  # 页面命中
            if len(global_history) > M:  # 如果全局历史记录超出阈值，进行页面替换
                global_history.remove(random.choice(list(global_history)))  # 从全局历史记录中随机移除一个页面访问记录
    return page_faults  # 返回页面错误数


if __name__ == "__main__":
    pi = [0.01, 0.02, 0.03, 0.05, 0.07, 0.08, 0.1, 0.12, 0.12, 0.4]  # 假设每个页面的访问概率
    N = 10 # 总共的页面数量
    M = 3  # 每个进程的局部历史记录长度（也是全局历史记录的阈值）
    local_faults = simulate_local_page_replacement(pi, N, M)
    global_faults = simulate_global_page_replacement(pi, N, M)
    print(f"局部置换的缺页次数: {local_faults}")
    print(f"全局置换的缺页次数: {global_faults}")

结果呈现