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

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

문제

페이지 교체 알고리즘으로 LRU와 LFU 알고리즘을 사용하고 페이지 참조 순서는 다음과 같다.
페이지 참조 순서 : 1, 2, 3, 1, 2, 4, 1, 2, 5, 7
이 경우 할당된 프레임의 수가 3개일 때 LRU와 LFU 알고리즘에서 발생하는 페이지 부재 횟수를 작성하시오.
단, 초기에는 기억장치가 모두 비어 있다고 가정한다.

정답

LRU : 6
LFU : 6

반응형

---

해설

📌 개념 설명

🔷 페이지 교체 알고리즘

운영체제에서 페이지 교체 알고리즘은 한정된 메모리 공간에서 필요한 데이터를 효율적으로 유지하는 방법입니다.
컴퓨터는 프로그램 실행 시 필요한 데이터를 RAM(주기억장치) 에 저장합니다. 하지만 RAM의 크기는 한정적이므로, 실행 중인 프로그램이 너무 많은 데이터를 요청하면 기존 데이터를 삭제하고 새로운 데이터를 불러와야 합니다. 이 과정에서 어떤 데이터를 삭제할 것인지 결정하는 방법이 바로 페이지 교체 알고리즘입니다.
즉, 운영체제에서 페이지 교체 알고리즘은 한정된 메모리에서 새로운 페이지를 불러오기 위해 기존 페이지 중 어떤 것을 제거할지 결정하는 방법입니다.

---

🔷 페이지 부재

페이지 부재(Page Fault) 란 CPU가 프로그램을 실행하는 도중, 필요한 페이지가 메모리(RAM)에 없는 상황을 의미합니다.
운영체제(OS)는 프로그램이 필요로 하는 데이터를 메모리(RAM)에 미리 올려놓지만, 메모리가 부족할 경우 일부만 올려놓고 나머지는 디스크(하드디스크, SSD)에 저장합니다. 그런데 프로그램 실행 중 필요한 페이지가 메모리에 없으면, CPU는 해당 페이지를 디스크에서 찾아 메모리에 적재하는 과정을 거치게 됩니다. 이때 발생하는 이벤트가 페이지 부재(Page Fault) 입니다.

---

🔷 페이지 교체 알고리즘 종류

1️⃣ FIFO (First-In, First-Out)
먼저 들어온 페이지를 먼저 내보내는 방식

• 정의
  • FIFO(선입선출) 알고리즘은 가장 먼저 메모리에 들어온 페이지를 가장 먼저 제거하는 방식입니다. 즉, 줄을 서 있는 대기열(Queue)처럼 먼저 온 순서대로 나가는 방식입니다.
• 단점
  • 오래된 페이지가 무조건 제거되므로 자주 사용되는 페이지도 삭제될 가능성이 높음
  • Belady’s Anomaly 발생 가능 (메모리 크기가 증가해도 페이지 부재 횟수가 줄어들지 않을 수 있음)

🔎 예제

• FIFO 알고리즘 적용 예제
  • 메모리 프레임(페이지 슬롯) 개수: 3개
  • 페이지 요청 순서: 1, 2, 3, 4, 1, 2, 5
  • 초기 상태: 메모리는 비어 있음
• 총 페이지 부재 횟수 7회

 

2️⃣ LRU (Least Recently Used)
가장 오랫동안 사용되지 않은 페이지를 교체

• 정의
  • LRU(최소 최근 사용) 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 제거하는 방식입니다. 즉, 최근에 사용한 페이지는 유지하고, 사용하지 않은 페이지를 내보냅니다.
• 단점
  • 최근 사용 이력을 저장해야 하므로 추가적인 저장 공간이 필요
  • 하드웨어적으로 구현하려면 복잡한 자료구조(스택, 큐 등)가 필요

🔎 예제

• LRU 알고리즘 적용 예제
  • 메모리 프레임 개수: 3개
  • 페이지 요청 순서: 1, 2, 3, 1, 2, 4, 1, 2, 5, 7
• 총 페이지 부재 횟수: 6회

 

3️⃣ LFU (Least Frequently Used)
가장 적게 사용된 페이지를 교체

• 정의
  • LFU(최소 사용 빈도) 알고리즘은 사용 횟수가 가장 적은 페이지를 제거하는 방식입니다. 즉, 자주 사용된 페이지는 유지하고, 거의 사용되지 않은 페이지를 제거합니다.
• 단점
  • 사용 빈도를 저장해야 하므로 추가적인 저장 공간이 필요
  • 특정 페이지가 계속 사용되지 않으면 오랫동안 남아있을 수 있음

🔎 예제

• LFU 알고리즘 적용 예제
  • 메모리 프레임 개수: 3개
  • 페이지 요청 순서: 1, 2, 3, 1, 2, 4, 1, 2, 5, 7
• 총 페이지 부재 횟수: 6회

 

4️⃣ NUR (Not Used Recently)
최근 사용되지 않은 페이지를 교체

• 정의
  • NUR(Not Used Recently) 알고리즘은 최근에 사용되지 않은 페이지를 우선적으로 교체하는 방식입니다.
    이 알고리즘은 하드웨어적인 지원이 필요하며, 보통 운영체제가 참조 비트(Reference Bit)와 수정 비트(Modified Bit)를 이용하여 교체할 페이지를 선택합니다.
  • 참조 비트 (R): 해당 페이지가 최근에 접근되었는지를 나타냄 (1이면 사용됨, 0이면 사용되지 않음)
  • 수정 비트 (M): 해당 페이지가 수정되었는지를 나타냄 (1이면 수정됨, 0이면 수정되지 않음)
• 페이지 교체 우선순위
  
  • 운영체제는 페이지를 다음과 같은 우선순위로 제거합니다.
    • (R=0, M=0) → 참조되지 않았고, 수정되지 않은 페이지 → 가장 먼저 제거
    • (R=0, M=1) → 참조되지 않았지만, 수정된 페이지 → 두 번째로 제거 (디스크에 저장 필요)
    • (R=1, M=0) → 참조되었지만, 수정되지 않은 페이지 → 세 번째로 제거
    • (R=1, M=1) → 참조되었고, 수정된 페이지 → 가장 마지막에 제거

728x90

---

📌 문제 해설

• LRU 알고리즘 적용
  • 메모리 프레임 개수: 3개
  • 페이지 요청 순서: 1, 2, 3, 1, 2, 4, 1, 2, 5, 7
• 총 페이지 부재 횟수: 6회

• LFU 알고리즘 적용
  • 메모리 프레임 개수: 3개
  • 페이지 요청 순서: 1, 2, 3, 1, 2, 4, 1, 2, 5, 7
• 총 페이지 부재 횟수: 6회

---

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