1. 교체정책 (Replacement Strategy)
- 주기억장치에 참조하려고 하는 페이지가 없을 경우 페이지 부재가 발생 이때, 주기억장치 내에 어떤 페이지와 교체할 것인가를 결정하는 방법
- 페이지 부재가 발생하면 운영체제가 메모리에 들어올 페이지에 대한 공간을 만들어 주기위해 주기억장치에서 제거할 페이지를 선택하게 된다.
1) 최적 교체
- 현재 주기억장치에 있는 페이지들 중 현재 시점 이후로 가장 오랫동안 참조되지않을 페이지 교체
- 페이지 호출순서를 사전에 미리 파악해야하기때문에 비현실적
2) 선입선출
- 각 페이지가 주기억장치로 들어올 때마다 그 시간을 기억하고 있다가 페이지가 교체될 필요가 있을때 가장 먼저 주기억장치에 들어있는 페이지와 교체시키는 방법
- 원래는 페이지 프레임 (가용한 페이지 개수) 개수를 늘리면 부재율이 줄어드는데 fifo는 그러지 않음
3) 2차 기회 교체 (SCR, Second Chance Replacement)
- FIFO 방식의 단점인 가장 오랫동안 주기억장치에 있었던 자주쓰이던 페이지가 대체될 수도 있다는 것을 막기위한 방법 → 참조 비트를 두어 관리
- 페이지 사상표에 한개의 참조비트를 만들어, 처음에는 모든 참조비트를 0으로 그 후 프로세스가 수행되면서 참조한 각 페이지와 관계된 참조비트는 그값이 1로 변경
4) LRU (Least Recently Used)
- 최근에 가장 적게 쓰인 페이지 대체
- 최근의 상황이 가까운 미래에 대한 좋은 척도라는 locality에 의존
5) LFU (Least Frequently Used)
- 사용빈도가 가장 적은 페이지가 교체
- 가장 드물게 사용된 페이지가 가장 최근에 주기억장치에 옮겨진 페이지일 가능성이 있어, locality 위배
6) NUR (Not Used Recently)
- 근래에 쓰이지 않은 페이지는 가까운 미래에도 쓰이지 않을 가능성 많음
- 새로 호출하는 페이지와 대체
- 각 페이지당 필요한 두개의 하드웨어 비트를 둔다.
- 참조비트 (0) : 페이지가 호출된 적이 없을때
- 참조비트 (1) : 페이지가 호출된 적이 있을때
- 변형비트(0) : 페이지 내용이 변형되지 않을때
- 변형비트(1) : 페이지 내용이 변형되었을때
- 참조비트보단 변형비트가 우선순위
7) Working Set
- 프로세스에게 필요한 만큼의 프레임을 재할당하는 방법
- 일정한 시간간격 사이에 하나의 프로세스가 참조하는 페이지들의 집합
- 최근에 참조하는 페이지들의 집합에 속하지 않는 페이지를 교체시키는 기법
- 스레싱을 일어나지 않게 하여 cpu 이용률을 최대화 시킴
8) 페이지 부재 빈도 (PFF, Page Fault Frequency)
- workingset은 일정주기로 기억장치를 참조하고 나서 세트를 고치는 반면, PFF 방식은 페이지 부재율에 따라 주기억장치의 페이지 프레임 수를 조절
- 페이지 부재율을 적정수준으로 유지
2. 스래싱 (Thrashing)
너무 자주 페이지 교환이 일어나는 경우 프로그램 수행시간보다 페이지 교체에 많은 시간을 할애
- 다중프로그래밍 정도가 더 커지면 스래싱 현상이 자주 일어남 (cpu 이용률 감소)
해결책
- 다중프로그래밍 정도를 낮춘다.
- 프로세스들에게 충분히 큰 페이지 프레임을 할당
- 프로세스들이 가질 수 있는 페이지 프레임 수를 늘림
- 지역성이나 우선순위 교환 알고리즘 하용
- 지역 교환 알고리즘
- 한프로세스가 스래싱을 유발하더라도 다른 프로세스로부터 프레임을 뺏어올수없고 자기가 할당된 프레임 내부에서 교환
3. 교체 지역성 (locality)
프로세스들은 기억장치 내의 정보를 균일하게 액세스하는 것이 아니라, 어느 한 순간에는 특정 부분을 집중적으로 참조
- 캐시메모리, 연관기억장치, LRU, WorkingSet, PFF 등의 근거 이론
종류
- 시간지역성
- 최근에 접근한 데이터나 명령을 곧 다시 사용할 가능성이 높다는 것
- Looping, Subroutine, Stack, Counting, 집계에 활용되는 변수
- 공간지역성
- 어떤 주소를 접근하면 그 주변 주소들도 함께 접근될 가능성이 높다는 것
- 배열 순회, 순차적 코드실행, 프로그래머들이 관련된 변수를 근처에 선언
