如何用Python生成虚拟内存追踪？能否用trace模块测试OS分页策略？

Great question! Testing cache hit ratios with different memory access patterns is a perfect way to wrap your head around OS paging strategies—let's walk through how to generate both random and locality-aware traces, plus clear up the confusion around Python's trace module.

1. 生成完全随机的内存访问追踪 #

完全随机的追踪是测试缓存的基准场景（相当于最坏情况，因为没有局部性可以利用）。你可以直接用Python的random模块生成指定范围内的虚拟地址序列。

示例代码：

import random

def generate_random_trace(num_accesses, addr_min, addr_max):
    """生成完全随机的虚拟内存访问追踪"""
    trace = []
    for _ in range(num_accesses):
        # 生成一个在[addr_min, addr_max]之间的随机虚拟地址
        addr = random.randint(addr_min, addr_max)
        trace.append(addr)
    return trace

# 用法示例：生成1000次访问，地址范围0~4095（假设页大小4KB，对应1024个页）
random_trace = generate_random_trace(1000, 0, 4095)
# 可以保存到文件方便后续测试
with open("random_trace.txt", "w") as f:
    for addr in random_trace:
        f.write(f"{addr}\n")

2. 生成具有局部性的内存访问追踪 #

真实程序的内存访问几乎都有时间局部性（重复访问最近用过的地址）和空间局部性（访问相邻/连续的地址），我们可以模拟这两种特性：

2.1 时间局部性为主的追踪 #

核心思路：让大部分访问集中在一个"热点"地址池，偶尔随机访问其他地址。

import random

def generate_temporal_locality_trace(num_accesses, addr_min, addr_max, hot_ratio=0.8, hot_pool_size=20):
    """生成以时间局部性为主的追踪"""
    trace = []
    # 初始化热点地址池
    hot_addrs = random.sample(range(addr_min, addr_max+1), hot_pool_size)
    
    for _ in range(num_accesses):
        if random.random() < hot_ratio:
            # 80%概率访问热点地址池中的地址
            addr = random.choice(hot_addrs)
        else:
            # 20%概率访问随机地址
            addr = random.randint(addr_min, addr_max)
        trace.append(addr)
    return trace

# 用法示例
temporal_trace = generate_temporal_locality_trace(1000, 0, 4095)
with open("temporal_trace.txt", "w") as f:
    for addr in temporal_trace:
        f.write(f"{addr}\n")

2.2 空间局部性为主的追踪 #

核心思路：生成连续的地址块访问，偶尔跳转到其他随机块。

import random

def generate_spatial_locality_trace(num_accesses, addr_min, addr_max, block_size=16, jump_prob=0.1):
    """生成以空间局部性为主的追踪"""
    trace = []
    # 初始当前访问块的起始地址
    current_block_start = random.randint(addr_min, addr_max - block_size + 1)
    
    for _ in range(num_accesses):
        if random.random() < jump_prob:
            # 10%概率跳转到新的随机块
            current_block_start = random.randint(addr_min, addr_max - block_size + 1)
        # 在当前块内随机选一个地址（模拟空间局部性）
        offset = random.randint(0, block_size-1)
        addr = current_block_start + offset
        trace.append(addr)
    return trace

# 用法示例
spatial_trace = generate_spatial_locality_trace(1000, 0, 4095)
with open("spatial_trace.txt", "w") as f:
    for addr in spatial_trace:
        f.write(f"{addr}\n")

3. Python的trace模块能用吗？ #

简短回答：不能直接用来生成虚拟内存访问追踪。

Python的trace模块主要用于追踪Python代码的执行流程——比如记录哪些函数被调用、哪些代码行被执行、函数调用次数等，它的作用是分析代码的执行路径，而不是模拟虚拟内存的访问行为。如果你的目标是生成用于分页缓存测试的地址访问序列，trace模块帮不上忙，还是用上面的自定义生成方法更合适。

小提示：测试缓存命中率 #

生成追踪后，你可以简单模拟分页缓存来统计命中率：

def calculate_hit_ratio(trace, cache_size, page_size=4096):
    """计算分页缓存的命中率"""
    cache = set()
    hits = 0
    misses = 0
    
    for addr in trace:
        # 计算地址对应的页号
        page_num = addr // page_size
        if page_num in cache:
            hits +=1
        else:
            misses +=1
            # 如果缓存满了，随机淘汰一个页（模拟FIFO/Random替换策略）
            if len(cache) >= cache_size:
                cache.remove(random.choice(list(cache)))
            cache.add(page_num)
    
    return hits / (hits + misses)

# 测试随机追踪的命中率
random_hit_ratio = calculate_hit_ratio(random_trace, cache_size=10)
print(f"Random trace hit ratio: {random_hit_ratio:.2%}")
# 测试时间局部性追踪的命中率
temporal_hit_ratio = calculate_hit_ratio(temporal_trace, cache_size=10)
print(f"Temporal locality trace hit ratio: {temporal_hit_ratio:.2%}")

内容的提问来源于stack exchange，提问作者lincr