페이지 교체 알고리즘

페이지 교체 알고리즘

• 스왑 영역으로 보낼 페이지를 결정하는 알고리즘

 

무작위 페이지 교체 알고리즘 (random page replacement algorithm)

• 스왑 영역에서 쫓아낼 대상 페이지를 특별한 로직 없이 무작위로 선정
• 지역성을 전혀 고려하지 않음 (성능이 좋지 않음)

지역성

 

기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질

페이지 교체 알고리즘이 쫓아낼 페이지를 찾을 때 지역성을 바탕으로 함

지역성에는 공간의 지역성, 시간의 지역성, 순차적 지역성이 있음

 

 

FIFO 페이지 교체 알고리즘

• 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑영역 이동
• 무조건 오래된 페이지를 대상 페이지로 선정하기에 성능이 떨어짐

 

 

최적 페이지 교체 알고리즘

• 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮김
• 메모리가 앞으로 사용할 페이지를 미리 살펴보고 대상 페이지를 정함
• 이상적인 방법이지만 실제로 구현할 수 없음

 

 

최적 근접 알고리즘

• LRU 페이지 교체 알고리즘 : 페이지에 접근한 시간을 기준으로 대상 페이지를 선정
• LFU 페이지 교체 알고리즘 : 페이지가 사용된 횟수를 기준으로 대상 페이지를 선정

 

 

LRU 페이지 교체 알고리즘

• 최근 최소 사용 페이지 교체 알고리즘
• 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮김

카운터에 기반한 구현

• LRU 페이지 교체 알고리즘을 카운터를 사용해 구현

참조 비트 시프트 방식

• 각 페이지에 일정 크기의 참조 비트를 만들어 사용
• 참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1로 바뀜
• 참조 비트 중 가장 작은 값을 대상 페이지로 선정

 

 

 

LFU 페이지 교체 알고리즘 

• 페이지가 몇 번 사용 되었는지는 기준으로 대상 페이지를 선정
• 사용된 횟수가 가장 적은 페이지를 스왑 영역으로 옮김

 

 

NUR 페이지 교체 알고리즘

• LRU, LFU 페이지 교체 알고리즘은 성능은 좋으나 추가적인 오버헤드가 큼
• NRU는 두 개의 비트만으로 구현 가능
• 최근 미사용 페이지 교체 알고리즘
• 페이지 마다 참조 비트와 변경 비트를 가짐
  • 참조 비트 : 페이지에 접근하면 1이 됨
  • 변경 비트 : 페이지가 변경되면 1이 됨

 

• 대상 페이지를 찾을 때 참조 비트가 0인 페이지를 먼저 찾고, 없으면 변경 비트가 0인 페이지를 찾음
• 같은 비트의 페이지가 여러 개라면 무작위로 대상 페이지를 선정

 

 

2차 기회 페이지 교체 알고리즘

• FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용
• 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동
• 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더줌