[정보처리기사] LRU 페이지 교체 알고리즘 | 2024년 3회 정보처리기사 실기 기출문제

2024년 3회 정보처리기사 실기 기출문제

문제

3개의 페이지를 수용할 수 있는 주기억장치가 있으며, 초기에는 모두 비어 있다고 가정한다. 다음의 순서로 페이지 참조가 발생할 때, LRU(Least Recently Used) 페이지 교체 알고리즘을 사용할 경우, 총 몇 번의 페이지 부재(Page Fault)가 발생하는지 구하시오.

정답

12

반응형

---

해설

📌 개념 설명

🔷 페이지 교체 알고리즘

운영체제에서 프로세스는 논리적 주소 공간을 사용하지만, 실제로는 제한된 물리적 메모리(RAM) 를 사용합니다.
그래서 운영체제는 필요한 페이지들만 메모리에 적재하고, 나머지는 보조기억장치(디스크) 에 보관합니다.

하지만 메모리에 올릴 수 있는 페이지 수에는 한계가 있기 때문에,
새로운 페이지를 메모리에 적재해야 할 때 공간이 부족하면 기존의 페이지 중 일부를 제거해야 합니다.

이때 어떤 페이지를 제거할지 결정하는 방식이 바로 페이지 교체 알고리즘입니다.

---

🔷 페이지 부재

페이지 부재(Page Fault) 는
프로세스가 참조한 페이지가 현재 메모리에 없는 경우를 말합니다.

이럴 경우 운영체제는:

1. 보조기억장치에서 해당 페이지를 메모리로 가져오고,
2. 필요시 기존 페이지를 하나 교체(제거)하며,
3. 다시 명령을 수행합니다.

즉, 페이지 부재는 메모리에 해당 페이지가 없어 생기는 예외 상황입니다.
따라서 페이지 부재가 많을수록 성능은 저하됩니다.

---

🔷  LRU (Least Recently Used) 알고리즘

LRU는 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식의 알고리즘입니다.
즉, 페이지를 교체해야 할 상황이 오면, 지금까지 사용된 이력을 기반으로,가장 오래 전에 사용된 페이지를 선택하여 제거합니다.

728x90

---

📌 문제 해설

LRU 알고리즘 표

LRU 알고리즘 표

 

1. 처음 3개의 페이지(7, 0, 1) 는 메모리가 비어 있으므로 모두 적재 → 3번의 페이지 부재

2. 이후에도 새로운 페이지(2, 3, 4 등)가 등장하면,
LRU 알고리즘에 따라 가장 오래 전에 사용된 페이지를 찾아 교체합니다.
예를 들어, 7 0 1 상태에서 2가 들어오면 가장 오래전에 사용된 7을 제거합니다.

3. 이미 메모리에 있는 페이지가 참조되면 페이지 부재가 발생하지 않습니다.

총 정리

 

• 7 → 없음 → ✅(부재o) 메모리: [7]
• 0 → 없음 → ✅ 메모리: [7, 0]
• 1 → 없음 → ✅ 메모리: [7, 0, 1]
• 2 → 없음 → ✅ 7 제거(가장 오래전에 사용됨) → [0, 1, 2]
• 0 → 있음 → ❌(부재x)
• 3 → 없음 → ✅ 1 제거 → [0, 2, 3]
• 0 → 있음 → ❌
• 4 → 없음 → ✅ 2 제거 → [0, 3, 4]
• 2 → 없음 → ✅ 3 제거 → [0, 4, 2]
• 3 → 없음 → ✅ 4 제거 → [0, 2, 3]
• 0 → 있음 → ❌
• 3 → 있음 → ❌
• 2 → 있음 → ❌
• 1 → 없음 → ✅ 2 제거 → [0, 3, 1]
• 2 → 없음 → ✅ 0 제거 → [3, 1, 2]
• 0 → 없음 → ✅ 3 제거 → [1, 2, 0]
• 1 → 있음 → ❌
• 7 → 없음 → ✅ 2 제거 → [1, 0, 7]
• 0 → 있음 → ❌
• 1 → 있음 → ❌

 

 

---

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."