페이지 교체 알고리즘 중
FIFO
와LRU
를 파이썬으로 구현해봅시다.
First In First Out
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
Least Recently Used
Doubly Linked List
와 Hash Map
자료구조를 사용하여 O(1)
의 시간복잡도를 갖는 LRU를 구현해봅시다.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