벨라디의 이상현상 (Belady's Anomaly)

벨라디의 이상현상 (Belady's Anomaly)

벨라디의 이상현상(Belady's Anomaly)은 페이지 교체 알고리즘에서 발생하는 비정상적인 현상으로, 페이지 프레임 수를 늘렸음에도 불구하고 페이지 부재(page fault)가 오히려 증가하는 현상을 의미합니다. 이는 운영체제 메모리 관리에서 대표적인 비정상적인 현상으로 알려져 있습니다.

---

1. 벨라디의 이상현상 개념

보통 페이지 교체 알고리즘에서는 페이지 프레임 수가 많아지면 페이지 부재가 줄어들 것으로 기대합니다. 하지만 특정 조건에서 FIFO(First In First Out)와 같은 몇몇 알고리즘에서는 페이지 프레임 수가 증가해도 페이지 부재가 줄어들지 않고 오히려 늘어나는 현상이 발생할 수 있습니다. 이를 Belady's Anomaly라고 합니다.

---

2. 벨라디의 이상현상 발생 조건

벨라디의 이상현상은 다음과 같은 조건에서 발생할 수 있습니다:

1. FIFO 페이지 교체 알고리즘 사용
   • FIFO는 오래된 페이지를 무조건 제거하기 때문에 발생합니다.
2. 특정한 페이지 요청 패턴 존재
   • 페이지 요청 시퀀스가 특정 패턴을 따를 때 발생합니다.

---

3. 벨라디의 이상현상 예시 (FIFO 알고리즘)

다음은 페이지 프레임이 3개일 때와 4개일 때 페이지 부재 수를 비교하는 예입니다.

페이지 요청 시퀀스:

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

---

(1) 페이지 프레임 3개 (FIFO 사용)

요청 페이지	메모리 상태 (3 프레임)	페이지 부재(PF)
1	1 - -	✅
2	1 2 -	✅
3	1 2 3	✅
4	2 3 4	✅
1	3 4 1	✅
2	4 1 2	✅
5	1 2 5	✅
1	2 5 1	✅
2	5 1 2	✅
3	1 2 3	✅
4	2 3 4	✅
5	3 4 5	✅

페이지 부재 수: 12

---

(2) 페이지 프레임 4개 (FIFO 사용)

요청 페이지	메모리 상태 (4 프레임)	페이지 부재(PF)
1	1 - - -	✅
2	1 2 - -	✅
3	1 2 3 -	✅
4	1 2 3 4	✅
1	1 2 3 4	❌
2	1 2 3 4	❌
5	2 3 4 5	✅
1	3 4 5 1	✅
2	4 5 1 2	✅
3	5 1 2 3	✅
4	1 2 3 4	✅
5	2 3 4 5	✅

페이지 부재 수: 10

---

결과 해석:

• 페이지 프레임 3개일 때: 페이지 부재 = 12회
• 페이지 프레임 4개일 때: 페이지 부재 = 10회

이 예시에서는 페이지 프레임이 증가했음에도 불구하고 페이지 부재 수가 줄어들었기 때문에 이상현상이 발생하지 않았습니다. 하지만 특정 페이지 시퀀스에서는 페이지 프레임 수가 늘어도 부재 수가 증가할 수 있으며, 이를 벨라디의 이상현상(Belady's Anomaly)라고 합니다.

---

4. 벨라디의 이상현상이 발생하지 않는 알고리즘

다음 알고리즘들은 벨라디의 이상현상이 발생하지 않음이 수학적으로 증명되었습니다:

• Optimal (OPT): 이론적으로 가장 적은 페이지 부재 발생
• LRU (Least Recently Used): 가장 오랫동안 사용되지 않은 페이지 제거

이 두 알고리즘은 스택 알고리즘(Stack Algorithm)을 사용하며, 메모리 크기 증가 시 페이지 부재 수가 절대 증가하지 않음을 보장합니다.

---

5. 결론

벨라디의 이상현상은 운영체제와 메모리 관리에서 FIFO 알고리즘의 비효율성을 드러내는 대표적인 사례입니다. 페이지 프레임 수 증가가 항상 성능 개선으로 이어지지는 않는다는 점을 잘 설명해 줍니다. 이를 이해하면 더 효율적인 페이지 교체 알고리즘(LRU, Optimal 등)을 선택하는 데 도움이 됩니다.