페이지 교체 알고리즘

 

프로세스가 요구한 페이지가 현재 메모리에 없는 경우, 페이지 부재(page fault)가 발생

-> 스왑 영역에서 페이지를 메모리로 가져온다. 이 때, 메모리가 꽉 찼다면 메모리에 있는 페이지를 스왑 영역으로 보내야 한다.

 

페이지 교체 알고리즘은 메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 알고리즘이다.

메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지(victim page)로 선정 -> 페이지 부재를 줄이고, 시스템의 성능을 향상

 

성능 평가 기준

페이지 부재 횟수, 페이지 성공 횟수를 기준으로 비교하려고 한다.

페이지 교체 알고리즘은 유지 비용 역시 고려해야 한다.

페이지 부재의 횟수를 알 수 있는 방법: 페이지 참조열(page reference string)
cpu가 참조하는 페이지들 중 '연속된 페이지를 생략한' 페이지열을 사용할 수 있다.
예를 들어, 어떤 CPU가 [2 2 2 3 5 5 3 3 7] 순으로 페이지를 참조했을 때, 연속된 페이지를 생략한 [2 3 5 7]을 페이지 참조열이라고 한다.

연속된 페이지를 생략할 수 있는 이유?
만약 처음 등장한 5에서 페이지 폴트가 발생하면, 이미 5를 가져왔기 때문에 그 바로 뒤에 등장한 5에 대해서는 일어나지 않는다

 

* 프레임: 물리 메모리를 일정한 크기로 나눈 블록
* 페이지: 가상 메모리를 일정한 크기로 나눈 블록

 

아래의 페이지 교체 알고리즘은 다음과 같은 메모리 접근 순서를 사용하고, 물리 메모리는 3개의 프레임을 가졌다고 가정한다.

상단의 숫자는 메모리의 접근 순서이며, 페이지의 번호 대신 알파벳을 사용한다.

 

 

페이지 교체 알고리즘 overall

1. OPT - Optimal : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
2. FIFO - First In First Out
3. LRU - Least Recently Used : 가장 오랫동안 사용되지 않은 페이지 교체
4. LFU - Least Frequently Used : 참조 횟수가 가장 작은 페이지 교체
5. NUR - Not Used Recently : 최근에 사용하지 않은 페이지 교체

 

OPT (optimal algorithm)

가장 성능이 좋은 페이지 교체 알고리즘이다.

• 가장 먼 미래에 참조될 페이지를 대상 페이지로 설정한다. (LFD, Longest Forward Distance)
• 오프라인 알고리즘의 한 형태이다.
• 미래의 페이지 참조 패턴을 내부적으로 알 수 없음 -> 실사용이 어렵다.
• 이론적으로 최적의 성능을 제공하므로, 타 페이지 교체 알고리즘과 성능 비교에서 상한선을 제공한다.

 

FIFO

시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 내보낸다.

페이지 부재가 일어난 경우(원하는 페이지가 메모리에 없는 경우) -> 실패

큐로 구현한다.

메모리에 올라온 시간만 고려하기 때문에, 자주 사용되는 페이지가 스왑 영역으로 옮겨지기도 한다.

 

페이지 교체 알고리즘에서는 앞으로 사용하지 않을 페이지를 스왑 아웃 시키는 것이 중요한데, FIFO 알고리즘은 무조건 오래된 페이지를 대상 페이지(victim page)로 선정하기 때문에 성능이 떨어진다.

 

LRU (Least Recently Used)

가장 최근에 사용되지 않은(참조가 오랫동안 되지 않은) 페이지를 스왑 영역으로 옮긴다.

• 최적 페이지 교체 알고리즘 중 하나.
• temporal locality을 고려한다: 가장 최근에 참조된 페이지가 가장 가까운 미래에 다시 참조될 가능성이 높다.
• 페이지 교체를 위해 페이지마다 시간 or 접근 순서를 기록하는 카운터를 사용한다.
• 프로세스가 주기억장치에 접근할 때마다 참조된 페이지 시간을 기록해야 함 -> 막대한 오버헤드 발생

LFU (Least Frequently Used)

최소 빈도 알고리즘이라고도 한다.

페이지의 참조 횟수로 대상 페이지를 결정한다.

(현재 프레임에 있는 페이지마다 사용된 횟수를 세어, 가장 적은 페이지를 스왑 영역으로 옮김)

• 최적 페이지 교체 알고리즘 중 하나.
• 참조횟수를 통해 장기적 시간규모에서의 참조 성향을 고려할 수 있다.
• 가장 최근에 불러온 페이지가 교체될 수 있다.
• 구현이 더 복잡하며, 막대한 오버헤드가 발생.

NUR (Not Used Recently, Clock algorithm)

최근 미사용 페이지 교체 알고리즘이라고도 한다.

참조비트와 변경비트를 이용해 대상 페이지를 결정한다. (오버헤드를 줄이고, 메모리 낭비 최소화)

참조비트: 페이지에 접근(read/execute)하면 1
변경비트: 페이지가 변경(write/append)하면 1

모든 페이지의 초기 상태는 (0, 0)
접근 발생 시 (1, 0)
변경 발생 시 (0, 1)
접근과 변경이 모두 발생한 경우 (1, 1)

 

• 비트가 (0, 0) -> (0, 1) -> (1, 0) -> (1, 1)인 페이지 순서로 스왑 영역으로 옮긴다.
• 우선 고려 대상은 참조비트
  • 참조비트가 0인 페이지를 먼저 찾고, 변경 비트가 0인 페이지를 찾는다.
• 같은 비트의 페이지가 여러개라면 OS 설계자, 관리자에 따라 대상 페이지 설정이 달라진다.
  • 랜덤으로 페이지 선정
  • oldest 프레임에 들어있는 페이지 선정
  • ...
• 모든 페이지의 비트가 (1,1)인 경우 (0,0)으로 초기화한다.
• LRU, LFU과 거의 비슷한 성능이면서도 불필요한 공간 낭비를 해결한 알고리즘이다.

 

 

 

 

ref.

https://velog.io/@chappi/OS는-할껀데-핵심만-합니다.-17편-페이지-교체-알고리즘FIFO-LRU-LFU-NUR-2차-기회-알고리즘-시계-알고리즘

OS는 할껀데 핵심만 합니다. 17편 페이지 교체 알고리즘(FIFO, LRU, LFU , NUR, 2차 기회 알고리즘, 시계

https://rob-coding.tistory.com/37

[운영체제] 페이지 교체 알고리즘

https://velog.io/@mm723/운영체제-페이지-교체와-프레임-할당

운영체제 : 페이지 교체와 프레임 할당