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

本文最后更新于：2022年5月4日 凌晨

介绍

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

算法

  • 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)