页面置换仿真实验

内容

  • FIFO
  • LRU

1. 实验目的

  • 加深对虚拟内存管理理论的理解
  • 学习页面置换的实现机制及页面置换算法的实现

2. 实验原理与设计思想

  • FIFO(First In, First Out)

    淘汰在内存最久的页面

    • 与实际运行规律不符
    • 页面调入的先后不能反映页面的使用情况，性能较差

  • LRU(Least Recently Used, LRU)

    最近最久未使用及最少使用

    • 记录每个页面距离上次被访问的时间$t$,淘汰$t$最大的页面

3. 实验内容

4. 通用部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import random
import heapq
from collections import namedtuple, deque
from beeprint import pp

visit = namedtuple('visit', ['idx', 'prior'])
global SIZE
SIZE = 3
global LOOP
LOOP = 20
random.seed()
testp = deque([7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 5, 4, 3, 6, 5, 3, 2])


class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

    def getlength(self):
        return len(self._queue)


def getRandom(pri):
    # return visit(random.randint(0, 10), pri)
    return visit(testp.popleft(), pri)

简要说明

  • PriorityQueue类：实现一个优先队列
  • getRandom函数：取得一个随机数
  • SIZE：页框树
  • LOOP：循环次数
  • testp：用于测试的页面访问的序列

5. 核心算法实现

FIFO

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def FIFO():
        global SIZE, LOOP
        cnt = 0
        q = PriorityQueue()
        for i in range(LOOP):
            v = getRandom(i)
            if v.idx not in [x[-1] for x in q._queue]:
                if q.getlength() < SIZE:
                    q.push(*v)
                    cnt+=1
                else:
                    q.pop()
                    q.push(*v)
                    cnt+= 1
        return cnt/LOOP

  • 结果

    • 在页框SIZE=3，随机访问次数LOOP=1000的情况下模拟

    • 以预设访问序列plist模拟

    • 页表元组的首元素代表优先级，越小代表越早进入

      • 页表元组的次元素代表驻留的页面

LRU

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def LRU():
        global SIZE, LOOP
        cnt = 0
        q = PriorityQueue()
        for i in range(LOOP):
            v = getRandom(i)
            if v.idx not in [x[-1] for x in q._queue]:
                if q.getlength() < SIZE:
                    q.push(*v)
                else:
                    q.pop()
                    q.push(*v)
                cnt += 1
            else:
                for k,x in enumerate(q._queue):
                    if x[-1] == v.idx:
                       q._queue.pop(k)
                       q.push(*v)           
        return cnt/LOOP

  • 结果

    • 在页框SIZE=3，随机访问次数LOOP=1000的情况下模拟

    • 以预设访问序列plist模拟

    • 页表元组的首元素代表优先级，越小代表越早进入

      • 页表元组的次元素代表驻留的页面
      • 若访问的页面在页表中，则更新页表优先级

6. 参考资料

Wikipedia contributors. (2019, December 18). FIFO (computing and electronics). In Wikipedia, The Free Encyclopedia. Retrieved 16:36, December 30, 2019, from https://en.wikipedia.org/w/index.php?title=FIFO_(computing_and_electronics)&oldid=931313064

Wikipedia contributors. (2019, December 14). Cache replacement policies. In Wikipedia, The Free Encyclopedia. Retrieved 16:36, December 30, 2019, from https://en.wikipedia.org/w/index.php?title=Cache_replacement_policies&oldid=930744547