페이지 교체 알고리즘

💡 페이지 교체 알고리즘이란?

• 운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램 일부만 주기억 장치에 적재해 사용한다. 이를 가상 메모리 기법이라고 한다.
• 페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 때, 어떤 페이지 프레임을 선택헤 교체할 것인지 결정하는 방법.

# 가상 메모리(Virtual Memory)

• 물리 메모리 크기의 한계 극복을 위해.
• 메인 메모리의 크기가 한정되어 있어 물리적인 메모리 크기보다 크기가 큰 프로세스는 실행시키기 어렵다.
• 이를 실행시키기 위해 나온 방법이 바로 가상 메모리
• 핵심은 프로세스 실행시, 필요한 부분만 메모리에 적제하는 것. 이것을 요구 페이징이라고 한다.
• 프로그램에 실제 메모리 주소(물리주소)가 아닌 가상의 메모리 주소(가상/논리주소)를 주는 방식
• 논리주소는 MMU를 통해 물리주소로 변환

장점

• 물리 메모리 크기의 제약에 자유로워진다.
• 더 적은 메모리를 차지해 많은 프로그램을 동시에 수행할 수 있다.

참고: 가상메모리란?

 

# 페이징(Paging)

사용하는 이유

• 프로세스 실행 시, 모든 부분이 필요한 것은 아니다.
• 필요한 부분만 메모리에 올려 메인 메모리에 올라가는 프로세스의 크기를 줄일 수 있다.
• 프로세스를 페이지 단위로 나누어 실행에 필요한 부분과 필요 없는 부분으로 나눈다.
  • 당장 실행에 필요한 메모리만 메모리해 적재하는 기법이 요구 페이징이다.
• 논리 주소의 메모리를 고정된 크기의 Page로 나누어 관리한다.

특징

• 물리주소 공간은 연속적이지 않을 수 있다.
• 페이지는 모두 같은 크기를 가진다.
• 물리주소 공간을 페이지와 같은 크기로 나눈 것을 프레임이리거 한다.
• Page Size는 하드웨어에 의해 정해진다.
• Page Table을 사용해 논리주소에서 프레임을 가리키는 물리주소로 매핑한다.
• 외부 단편화 X, 내부 단편화 발생

참고: 페이징이란?

 

상황

• 요구 페이징에 의해 메모리가 꽉 차있다.
• 필요한 페이지가 메모리에 없다.
• 빈 프레임이 없을 경우, 희생당할 프레임을 골라야 한다. ⇒ 페이지 교체 알고리즘

 

1. FIFO(First In, First Out) 알고리즘

• 가장 먼저 메모리에 올라온 페이지 교체
• 특징
  • 구현은 간단하지만 성능은 좋지 않다.
  • 들어온 시간을 저장하거나 Queue를 사용해 구현 가능

2. OPT(Optional) 알고리즘

• 앞으로 가장 오랫동안 사용하지 않을 페이지 교체
• 특징
  • 모든 알고리즘 중 page-fault 발생이 적다.
  • 앞으로 사용할 페이지를 미리 알고 있어야 한다.
  • 실제로는 구현 불가능

3. LRU(Least Recently Used) 알고리즘

• 가장 오랫동안 사용하지 않는 페이지 교체
• 특징
  • 오랫동안 사용하지 않았다면 앞으로도 사용하지 않을 것
  • Optional과 비슷한 효과
  • 많은 운영체제가 선택

4. LFU(Least Frequency Used) 알고리즘

• 참조 횟수가 가장 적은 페이지 교체
• 교체 대상이 여러개라면 가장 오랫동안 사용하지 않은 페이지를 교체한다.
• 특징
  • 많이 사용하지 않는다면 앞으로도 많이 사용되지 않을 것
  • 최근에 적재된 페이지가 교체될 수 있다.
  • 참조횟수 카운팅이 필요하다.
  • 초반에 많이 사용되고 나중에 사용되지 않을 경우 👎

5. MFU(Most Frequently Used) 알고리즘

• 참조 횟수가 가장 많은 페이지를 교체
• 특징
  • 참조 횟수가 많은 페이지는 이제 사용되지 않을 것이고, 적은 페이지는 최근에 사용된 것이라고 생각

•