페이지 교체 알고리즘

목차

01. 운영체제의 개요
02. 컴퓨터의 구조와 성능 향상
03. 프로세스와 스레드
04. CPU 스케줄링
05. 프로세스 동기화
06. 교착 상태
07. 물리 메모리 관리
08. 가상 메모리의 기초
09. 가상 메모리 관리
10. 입출력 시스템과 저장장치
11. 파일 시스템
12. 네트워크와 분산 시스템

---

페이지 교체 알고리즘

 

페이지 교체 알고리즘

• 스왑 영역으로 보낼 페이지를 결정하는 알고리즘
• 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상

 

종류

• 간단한 알고리즘 : 무작위, FIFO
• 이론적 알고리즘 : 최적
• 최적 근접 알고리즘 : LRU, LFU, NUR, FIFO 변형

 

성능 평가 기준

• 어떤 알고리즘이 다른 알고리즘보다 성능이 좋은지 평가하는 데에는 다양한 비교 방법이 있음.
• 여기에서는 같은 메모리 접근 패턴을 사용하여 페이지 부재횟수와 페이지 성공 횟수를 비교

 

무작위 페이지 교체 알고리즘

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

 

FIFO 페이지 교체 알고리즘

 

최적 페이지 교체 알고리즘

 

최적 근접 알고리즘의 접근방식

• 실제 구현 가능하고 성능이 최적 근접 알고리즘에 근접한 알고리즘 LRU 페이지 교체 알고리즘 : 페이지가 접근한 시간을 기준으로 대상 페이지 선정
• LFU 페이지 교체 알고리즘 : 페이지가 사용된 횟수를 기준으로 대상 페이지 선정(프리퀀시)

 

LRU 페이지 교체 알고리즘

• 최근 최소 사용 페이지 알고리즘 이라고도함
• 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑영역으로 옮김
• 최근에 사용된 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지로 선정
• 알고리즘은 시간을 기준으로 구현할 수 있으며 카운터나 참조비트를 이용하는 방법도 있음

 

카운터에 기반한 구현

• 카운터로도 LRU 페이지 교체 알고리즘을 구현할 수 있음

 

참조 비트 시프트 방식

• 각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 겻
• 참조 비트의 초기값은 0이고 접근할 때마다 1로 바뀜
• 주기적으로 오른쪽으로 이동
• 참조 비트를 갱신 하다가 페이지를 선정할 필요가 있으면 참조 비트 중 가장 작은 값을 대상 페이지로 선정
• LFU가 아니라 LRU임 → 어차피 시간을 기준으로 하기 때문에.

 

LFU 페이지 교체 알고리즘

모두가 같을 때는 임의의 프로세스를 옮기는데 여기서는 맨 위에꺼를 옮김

 

NRU 페이지 교체 알고리즘

• LRU, LFU 페이지 교체 알고리즘은 성능은 좋으나 오버헤드가 큼
• 이를 개선한 방식임
• 최근 미사용 페이지 교체 알고리즘이라고 불림
• 페이지마다 참조비트와 변경 비트를
  • 참조 비트 : 페이지에 접근하면 1이 됨
  • 변경 비트 : 페이지가 변경되면 1이 됨
• 모든 페이지의 초기상태는 (0, 0) 모든 값이 (1, 1) 이면 초기화 됨

 

2차 기회 페이지 교체 알고리즘 (FIFO 변형)

 

시계 알고리즘