Page Replacement Algorithm

• 페이지 교체 알고리즘이란,
  페이징 기법으로 메모리를 관리하는 운영체제에서
  페이지 부재(Page Fault)가 발생하여 새로운 페이지를 적재해야 되는데
  메모리에 페이지를 적재할 공간이 더이상 없어서
  이미 적재된 페이자와 새롭게 적재할 페이지를 교체해야 될 때,
  이미 적재된 페이지 중 '어떤 페이지를 교체할 것인지'를 결정하는 방법입니다.

---

페이지 교체 알고리즘 중 FIFO와 LRU를 파이썬으로 구현해봅시다.

FIFO

• First In First Out
• 물리적 메모리에 가장 먼저 올라온 페이지를 가장 먼저 교체합니다.
• 즉, 메모리에 올라온 지 가장 오래 된 페이지를 교체합니다.

FIFO in Python

from collections import deque


def FIFO():
    page_faults = 0

    page_frame = deque()
    page_frame_set = set()  # 페이지 존재 여부를 빠르게 파악하기 위한 자료구조(set)

    for i in range(len(pages)):
        page = pages[i]

        if len(page_frame) < SIZE:
            if page not in page_frame_set:
                page_faults += 1
                page_frame.append(page)
                page_frame_set.add(page)
        else:  #    page_frame is full
            if page not in page_frame_set:
                page_faults += 1
                first_page = page_frame.popleft()
                page_frame_set.remove(first_page)
                page_frame.append(page)
                page_frame_set.add(page)

    return page_faults


if __name__ == "__main__":
    pages = [3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4]
    SIZE = 4
    print("FIFO PAGE FAULT : ", FIFO())

결과

FIFO PAGE FAULT :  10

---

LRU

• Least Recently Used
• 가장 오래전에 참조한 페이지를 교체합니다.
• Doubly Linked List와 Hash Map 자료구조를 사용하여 O(1)의 시간복잡도를 갖는 LRU를 구현해봅시다.

LRU in Python

def LRU():
    class Node:
        def __init__(self, key, prev=None, next=None):
            self.key = key
            self.prev = prev
            self.next = next

    class DoublyLinkedList:
        def __init__(self):
            self.head = Node("head")
            self.tail = Node("tail")
            self.head.next = self.tail
            self.tail.prev = self.head

    class LRUCache:
        def __init__(self, csize):
            self.csize = csize
            self.hashmap = dict()
            self.frame = DoublyLinkedList()
            self.page_fault = 0

        def page_replacement(self, key):  # 페이지 교체가 발생합니다.
            temp = self.frame.tail.prev.prev
            tail = self.frame.tail
            last = self.frame.tail.prev

            temp.next, tail.prev = tail, temp
            self.hashmap.pop(last.key)

            # 새로운 페이지를 맨 앞에 추가합니다.
            self.insert_new_page_in_front(key)

        def insert_new_page_in_front(self, key):
            node = Node(key)

            self.page_fault += 1
            self.hashmap[key] = node

            # 현재 페이지를 맨 앞(가장 최근에 사용된 페이지)으로 이동합니다.
            next = self.frame.head.next
            self.frame.head.next, node.prev = node, self.frame.head
            next.prev, node.next = node, next

        def swap_existing_page(self, key):
            node = self.hashmap[key]

            # 현재 페이지를 기존 위치에서 삭제합니다.
            prev = node.prev
            next = node.next
            prev.next, next.prev = next, prev

            # 현재 페이지를 맨 앞(가장 최근에 사용된 페이지)으로 이동합니다.
            next = self.frame.head.next
            self.frame.head.next, node.prev = node, self.frame.head
            next.prev, node.next = node, next

        def put(self, key):
            # 페이지가 이미 존재합니다.
            if key in self.hashmap:
                self.swap_existing_page(key)
                return

            # 페이지가 존재하지 않지만, 아직 공간이 남아있습니다.
            if len(self.hashmap) < self.csize:
                self.insert_new_page_in_front(key)
                return

            # 페이지가 존재하지 않고 공간도 부족하므로 → 페이지 교체가 발생합니다.
            self.page_replacement(key)

        def printLRU(self):
            node = self.frame.head
            while node:
                print(node.key, end=" - ")
                node = node.next
            print()

    lru = LRUCache(SIZE)
    for i in range(len(pages)):
        page = pages[i]
        lru.printLRU()
        lru.put(page)

    return lru.page_fault


if __name__ == "__main__":
    pages = [3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4]
    SIZE = 4
    print("\nLRU PAGE FAULT : ", LRU())

결과

head - tail - 
head - 3 - tail - 
head - 2 - 3 - tail -
head - 1 - 2 - 3 - tail -
head - 0 - 1 - 2 - 3 - tail -
head - 3 - 0 - 1 - 2 - tail -
head - 2 - 3 - 0 - 1 - tail -
head - 4 - 2 - 3 - 0 - tail -
head - 3 - 4 - 2 - 0 - tail -
head - 2 - 3 - 4 - 0 - tail -
head - 1 - 2 - 3 - 4 - tail -
head - 0 - 1 - 2 - 3 - tail -

LRU PAGE FAULT :  8