페이지 교체 알고리즘(FIFO) 와 스래싱(THRASHING)

⭐ 페이지 교체 알고리즘 - FIFO

🔸 동작 방식

1. 페이지 요청: CPU가 특정 페이지를 요청.
2. 페이지 폴트 확인: 해당 페이지가 메모리에 없으면 페이지 폴트 발생.
3. 프레임 공간 확인:
   • 프레임에 빈 자리가 있으면 그냥 페이지 삽입.
   • 없으면 가장 먼저 들어온(오래된) 페이지를 제거.
4. 새 페이지 적재: 빈 자리 또는 제거된 자리에 새 페이지 삽입.

🔸 용어 설명

📘 1. 페이지(Page)

• 프로세스의 가상 메모리를 일정한 크기로 나눈 단위
• 예: 프로세스가 100KB를 요구하면 4KB 단위로 나누어 25개 페이지로 관리
• CPU는 가상 주소 = 페이지 번호 + 오프셋 형태로 접근함

---

📗 2. 프레임(Frame)

• 실제 메모리(RAM)를 페이지와 같은 크기로 나눈 단위
• 페이지는 프레임에 적재됨 (1:1 매핑)
• 물리 주소는 프레임 번호 + 오프셋

---

📙 3. 페이지 폴트(Page Fault)

• CPU가 요청한 페이지가 메모리(RAM)에 없을 때 발생하는 예외
• 이 경우 운영체제가 디스크에서 해당 페이지를 읽어와 프레임에 적재
• 폴트가 많으면 시스템 성능 저하 (디스크 접근 → 느림)

---

📚 비유: 책가방(프레임) vs 교과서(페이지)

페이지	교과서 한 권 (수학, 과학 등)
프레임	책가방 안 칸 (교과서를 담는 공간)
페이지 폴트	필요한 교과서가 가방에 없을 때
페이지 교체	가방이 꽉 찼을 때 오래 안 쓴 교과서를 꺼내고 새 교과서 넣기

 

예시 상황

• 수업 중 "과학책"이 필요함 (→ 과학 페이지 접근)
• 근데 가방(메모리)에 없음 (→ 페이지 폴트 발생)
• 가방이 꽉 참 (→ 페이지 교체 필요)
• 가장 먼저 넣었던 수학책 뺌 (FIFO 알고리즘)
• 과학책 가방에 넣음 (페이지 로딩)

---

🔸 예시

프레임 수: 3
참조 스트링: 7, 0, 1, 2, 0, 3, 0, 4

순서	입력 페이지	메모리 상태	페이지 폴트	교체된 페이지
1	7	7	✅	-
2	0	7, 0	✅	-
3	1	7, 0, 1	✅	-
4	2	0, 1, 2	✅	7
5	0	0, 1, 2	❌	-
6	3	1, 2, 3	✅	0
7	0	2, 3, 0	✅	1
8	4	3, 0, 4	✅	2

• ✅ 총 페이지 폴트 횟수: 7회

 

✅ 구조

• 일반적으로 Queue로 구현
• 새 페이지는 enqueue, 오래된 페이지는 dequeue

from collections import deque

def fifo(pages, frame_size):
    memory = deque()
    faults = 0
    for page in pages:
        if page not in memory:
            if len(memory) >= frame_size:
                memory.popleft()  # 가장 오래된 페이지 제거
            memory.append(page)
            faults += 1
    return faults

 

✅ 장점

• 구현이 단순 (큐 구조만 있으면 됨)
• 이해하기 쉬움

---

✅ 단점

• 가장 오래된 페이지가 아직 자주 쓰이는 페이지일 수도 있음
• 따라서 성능이 좋지 않음 (예: Belady's Anomaly 발생 가능)

---

✅ Belady's Anomaly (벨라디의 역설)

• 일반적으로 프레임 수가 증가하면 페이지 폴트가 줄어야 함
• 하지만 FIFO에서는 프레임 수가 늘어나도 페이지 폴트가 늘어나는 경우가 있음
• 다른 알고리즘은 재사용성을 고려하므로 이런 이상현상 없음 (오직 FIFO만)

예시:

• 3프레임일 때: 폴트 9번
• 4프레임일 때: 폴트 10번

프레임이 더 많으면 페이지가 더 오래 살아남을 것 같지만,
FIFO는 들어온 순서만 보므로 오히려 자주 쓰는 페이지가 먼저 쫓겨남.

⭐ 스레싱

✅ 발생 조건

1. 작은 물리 메모리(RAM)
2. 여러 프로세스가 동시에 실행 중
3. 각 프로세스가 필요한 페이지 수 > 프레임 수
4. 페이지 폴트가 매우 자주 발생
5. CPU 시간 대부분이 페이지 교체 작업에 소모됨

---

📚 비유로 설명

학생이 책가방(프레임)에 2권만 넣을 수 있는데,
선생님이 수학, 과학, 영어, 사회책을 번갈아 계속 요구함.
→ 계속 꺼내고 다시 넣고 반복 (공부 못 함)
→ 이게 스래싱

---

📌 요약

• 페이지 폴트 빈도가 과도하게 높음
• 시스템 성능 급락
• 해결 방법: 프로세스 수 줄이거나, 메모리 늘리거나, 워킹셋 알고리즘 적용