Optimal Page Replacement Algorithm

intro

▶ 운영체제 메인 메모리에 존재하지 않는 새로운 page가 있을 때 page fault가 발생.

 

▶ page fault가 발생할 때, existing page와 newly needed page replacement 진행

 

▶ 이 때, page fault의 횟수를 최소화한 알고리즘이 Optimal Page Replacement Algorithm

 

▶ page hit & fault

algorithm

▶ "when page fault, pages are replaced which would not be used for the longest duration of time in the future"

 

▶

① referred page가 이미 main memory에 존재한다면, page hit count 1 증가 (page fault 발생 x; 즉 page 교체 없음)

② referred page가 main memory에 존재하지 않는다면, page fault count 1 증가(page 교체)

→ a page(in a main memory) that is never referenced in the future 존재한다면

: a page that is never referenced in the future 와 교체

→ 존재하지 않는다면

: a page that is referenced farthest in future와 교체

example

▶ 4 Page Faults(initialization) + 2 Page Faults(3이 들어올 때 main memory 7 / 0 / 1 / 2 & 4가 들어올 때 main memory 3 / 0 / 1 / 2)

 

▶ 8 Page Hits

 

▶ Page Fault Ratio = 33.33% / Page Hit Ratio = 66.66%

python code

#page number: integer
#0 in main memory: vacant
import sys
input=sys.stdin.readline

def optimal_page_replacement(N,K,pages):

    memory=[0]*N #memory initialization
    hit,fault=0,0 #number of page hits & page faults
    i=-1 #index starts from -1

    while 1:
        i+=1

        if i == K: break #no more pages left
        if 0 in memory and pages[i] not in memory: #filling main memory for the 1st time
            memory[memory.index(0)] = pages[i]
            fault+=1 #page fault
        else:#if main memory is filled with pages
            if pages[i] in memory: #already exists in main memory
                hit+=1 #page hit
                continue
            else:
                fault+=1
                flag=False
                for mem_slot in memory:
                    if mem_slot not in pages[i:]:
                        #if a page that is never referenced in the future exists
                        memory[memory.index(mem_slot)] = pages[i]
                        flag = True
                        break
                if not flag:#if not exists
                    idxs=[]
                    for mem_slot in memory: #get the indexes in the future pages
                        idxs.append((mem_slot,pages[i:].index(mem_slot)))
                    #sort
                    idxs = sorted(idxs,key=lambda x: x[1], reverse=True)
                    memory[memory.index(idxs[0][0])] = pages[i]

    print(f'page hit: {hit}')
    print(f'page fault: {fault}')
    print(f'page hit rate: {round((hit/(hit+fault))*100,2)}%')
    print(f'page fault rate: {round((fault/(hit+fault))*100,2)}%')


N=int(input()) #the number of slots in main memory
K=int(input()) #the number of pages
pages=list(map(int,input().split()))

optimal_page_replacement(N,K,pages)

 

▶ N개의 memory slot, K개 page, page list 'pages'

▶ 관련 문제 《백준 1700: 멀티탭 스케줄링》

additional info

▶ 최적 페이지 교체 알고리즘은 이론상으로 완벽. 그러나 실제 세계에서는 적용 불가능한 이상적인 알고리즘. 실제 future request의 순서를 알 수 없으므로.

 

▶ 일종의 benchmark로 활용되어 다른 알고리즘의 성능과 비교 용도로 사용

---

* youtube (by Gate Smashers)

* geeksforgeeks

* thumbnail