内存页面置换常见的三种算法

本文最后更新于:2022年5月3日 晚上

介绍

在地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

算法

  • LRU算法

    该算法维护一个字典,存留所有已遍历过的页面以及上次遍历到当前的距离。每轮遍历都使字典里的value + 1
    遇到需要替换时,遍历该字典找到最大value(既最久没有使用的页面)对应的index并进行替换

    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
    34
    35
    # LRU algorithm
    def lru(data):
    memory = []
    fault = 0
    last_reference = {}
    for page in data:
    for node in last_reference:
    last_reference[node] += 1
    last_reference[page] = 0



    if memory.count(page) == 0: # This page is not exists in the list
    if len(memory) < numOfFrames:
    memory.append(page)
    else:
    fault += 1

    recently = None
    for node in last_reference:

    if recently == None:
    recently = node
    continue
    elif last_reference[node] > last_reference[recently]:
    recently = node

    memory[memory.index(recently)] = page
    last_reference.pop(recently)
    else:
    last_reference[page] = 0
    # print(memory, page)
    # print(last_reference)

    print(memory, "numbers of fault:", fault)
  • FIFO算法

    该算法维护一个变量,指向当前内存中最早插入的页面。
    遇到需要替换时,pop这个变量指向的内容并且在该位置插入页面。再把该变量+1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    # FIFO algorithm
    def fifo(data):
    memory = []
    fault = 0
    oldestAddr = 0
    for page in data:
    if oldestAddr >= numOfFrames:
    oldestAddr -= numOfFrames

    if page not in memory:
    if len(memory) < numOfFrames:
    memory.append(page)
    else:
    memory.pop(oldestAddr)
    memory.insert(oldestAddr, page)
    fault += 1
    oldestAddr += 1
    print(memory, "numbers of fault:", fault)
  • Optimal算法

    该算法在遇到需要替换时,会搜索当前内存中的页面是否在后续出现。如果后续不再出现,则替换该页面。如果内存中的所有页面都在后续出现,则选取到当前距离最大的页面进行替换。

    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
    34
    # OPTIMAL algorithm
    def optimal(data):
    memory = []
    fault = 0
    for index, page in enumerate(data):
    if len(memory) < numOfFrames:
    if memory.count(page) == 0: # current page is not existing
    memory.append(page)

    elif memory.count(page) == 0:
    fault += 1
    # pick one to replace
    next_use = {}
    pick = None
    # check if use furture
    for temp in memory:
    if temp not in data[index:]: # doesnt use furture
    pick = temp
    break
    else: # use in furture
    distance = data[index:].index(temp)
    next_use[temp] = distance
    else: # every node is use in furture
    # calculate farest node
    for node in next_use:
    if pick == None:
    pick = node
    else:
    if next_use[node] > next_use[pick]:
    pick = node

    memory[memory.index(pick)] = page
    print(memory, page)
    print(memory, "numbers of fault:", fault)