页面置换算法python

以下是Python实现LRU和FIFO页面置换算法的示例代码，并使用缺页率进行算法的评价：

LRU页面置换算法示例代码：

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

# 测试
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # 输出：1
cache.put(3, 3)
print(cache.get(2)) # 输出：-1
cache.put(4, 4)
print(cache.get(1)) # 输出：-1
print(cache.get(3)) # 输出：3
print(cache.get(4)) # 输出：4

FIFO页面置换算法示例代码：

class FIFOCache:
    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        self.queue = []

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
        else:
            if len(self.cache) >= self.capacity:
                del self.cache[self.queue.pop(0)]
            self.queue.append(key)
            self.cache[key] = value

# 测试
cache = FIFOCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # 输出：1
cache.put(3, 3)
print(cache.get(2)) # 输出：-1
cache.put(4, 4)
print(cache.get(1)) # 输出：-1
print(cache.get(3)) # 输出：3
print(cache.get(4)) # 输出：4

评价算法的缺页率示例代码：

def page_faults(pages, capacity, algorithm):
    if algorithm == 'LRU':
        cache = LRUCache(capacity)
    elif algorithm == 'FIFO':
        cache = FIFOCache(capacity)
    else:
        return -1
    faults = 0
    for page in pages:
        if cache.get(page) == -1:
            cache.put(page, 1)
            faults += 1
    return faults / len(pages)

# 测试
pages = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
capacity = 3
print(page_faults(pages, capacity, 'LRU')) # 输出：0.5454545454545454
print(page_faults(pages, capacity, 'FIFO')) # 输出：0.5454545454545454