FIFO

FIFO(First In First Out) 알고리즘 설명

FIFO는 가장 먼저 들어온 페이지를 가장 먼저 교체하는 페이지 교체 알고리즘으로 먼저 들어온 페이지가 캐시에 오래 머물러 있는 경우 교체 대상이 된다.

 

• 간단한 구현: 페이지가 캐시에 삽입된 순서를 기준으로 가장 먼저 들어온 페이지가 교체된다.
• Belady 변이: FIFO 알고리즘에서는 페이지 프레임 수가 증가해도 페이지 미스가 증가할 수 있는 Belady 변이가 발생할 수 있다.

FIFO 알고리즘 과정:

1. 페이지 요청이 발생하면, 해당 페이지가 캐시에 있는지 확인
2. 캐시에 없으면 페이지 미스가 발생하며, 먼저 들어온 페이지(오래된 페이지)를 교체
3. 새로운 페이지는 큐의 끝에 삽입

---

 

from collections import deque

def fifo_page_replacement(page_requests, frame_count):
    frames = deque(maxlen=frame_count)  # 고정 크기의 큐 (FIFO 구조)
    page_faults = 0  # 페이지 미스(캐시 미스) 카운트

    for page in page_requests:
        if page not in frames:  # 캐시에 없으면 페이지 미스 발생
            page_faults += 1  # 페이지 미스 증가

            if len(frames) < frame_count:
                # 빈 공간이 있으면 추가
                frames.append(page)
            else:
                # 큐가 가득 차면 FIFO에 따라 첫 번째 페이지 교체
                frames.popleft()  # 먼저 들어온 페이지 제거
                frames.append(page)  # 새로운 페이지 추가

        # 캐시 상태 출력
        print(f"Page request: {page}, Frames: {list(frames)}")

    print(f"Total Page Faults: {page_faults}")


# 페이지 요청 시퀀스 및 프레임 수 설정
page_requests = [3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4]
frame_count_3 = 3  # 프레임 수 3개인 경우
frame_count_4 = 4  # 프레임 수 4개인 경우

print("FIFO with 3 frames:")
fifo_page_replacement(page_requests, frame_count_3)
print("\nFIFO with 4 frames:")
fifo_page_replacement(page_requests, frame_count_4)