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

介绍

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

算法

  • LRU算法

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

# 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

# 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算法

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

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

项目地址

Github[PageReplacementAlgorithm]

评论