페이징 기법
- 모든 페이지 프레임이 사용되고 있을떄 새로 적재된어야할 페이지를 위해 적절한 교체 대상을 결정
교체 대상 선택
- 최적화의 원칙
- 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 선택
- 이론적으로 최적이나 미래를 예측할 수 없어 실현 불가능
- 선택을 위한 기본 정책
- 대체로 좋은 결론은 내리면서 선택을 위한 시간 및 공간 오버헤드가 적은 방법
- 교체 제외 페이지
- 페이징을 위한 커널코드 영역
- 보조기억장치 드라이버 영역
- 시간을 맞춰 동작해야하는 코드 영역
- 입출력장치를 위한 데이터 버퍼 영역 등
페이지 교체 알고리즘
FIFO
- 메모리내에 가장 오래 있었던 페이지를 선택하여 교체
- 구현 FIFO 큐 이용
- 단점
- 가장 많이 쓰이는 페이지를 교체시킬 가능성 있음
- Belady의 이상현상 : 프로세스에 더 많은 수의 페이지 프레임을 한당하면 오히려 페이지 부제가 더 많이 발생할 수 있는 현상
LRU
- Least Recently Used
- 메모리내애서 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체
- 국부성 휴리스틱에 기반
- 최근의 상황이 가까운 미래에 대한 좋은 척도
- 시간 국부성, 공간 국부성
- 구햔 : 참조시각 또는 리스트 사용
- 참조시각을 이용한 구현
- 각 페이지가 참조될때마다 그떄의 시각을 테이블에 기록
- 교체가 필요한 경우 참조시각이 가장 오래된 페이지를 선택하여 교체
- 리스트를 이용한 구현
- 각페이지가 참조될때마다 리스트의 선두로 옮김
- 교체가 필요한 경우 리스트의 끝에 있는 페이지를 선택하여 교체
- 장점
- Belady의 이상현상 발생하지 않음
- 많은 경우 최적화 원칙에 근사한 선택 가능
- 단점
- 국부성이 맞는 않은 상황도 존재
- 막대한 오버헤드
LFU
-
Least Frequentlt Used
-
메모리내에서 참조된 횟수가 가장 적은 페이지를 선택하여 교체
-
구현: 참조횟수 이용
-
단점
- 최근에 들어와서 참조횟수가 적은것이 빠질 가능성 큼
- 초기에 매우 많이 사옹된 후 더이상 사용되지 않는 페이지는 교체 가능성 많음
- 막대한 오버헤드
2차 기회 페이지 교체
- 참조비트가 0이면서 메모리내에 가장 오래있었던 페이지를 선택하여 교체
- 구현: FIFO 큐와 참조비트 이용
- 각페이지가 메모리에 적재될떄는 참조비트 0
- 적재된 상태에서 추가로 참조되면 참조비트 1
- 참조할 페이지가 메모리에 없는 경우
- 빈페이지 프레임이 있으면 -> 페이지적대, 큐에 추가, 참조비트는 0
- 빈페이지 프레임이 없으면 -> 큐의 선두항목을꺼내 참조비트조서, 1이면 0으로 바꿔 큐의 뒤에 추가 후 앞단계로 이동, 0이면 교체대상으로 선택하여 교체
- 참조할 페이지가 메모리에 있는경우
- 큐 위치 변화없이 참조비트만 1로 설정
- 변현된 원형 큐를 이용한 구현(클럭 페이지 교체 알고리즘)
- 포인터는 마지막에 추가된 페이지의 다음 위치를 가리킴
-> 빈페이지 프레임이 있는 경우 : 빈칸
-> 페이지 프레임이 꽉 찬경우 : 큐의 선두
프로세스별 페이지 집합관리
- 프로세스마다 사용할 수 있는 페이지 프레임의 개수만큼 메모리에 유지되는 페이지 집합
- 집합의 크기가 작을 수록 시스템 처리량 증대
- 각 프로세스별 페이지 부재는 자주발생하여 성능저하
- 집합의 크기가 클수록 프로세스별 페이지 부재는 감소
- 메모리에 적재되 수 있는 프로세스는 줄어듦
- 각 프로세스가 사용할 수 있는 페이지 프레임 개수 관리
- 워킹세트 알고리즘, PFF 알고리즘
워킹세트알고리즘
- 워킹세트 모델
- 페이지 부재비율을 감소시키이위해 Denning이 제안
- 프로세스가 수행됨에 따라 그 프로세스의 워킹세트는 변할 수 있으며 워킹세트의 크기도 달라질 수 있음
- 워킹세트 알고리즘의 원칭
- 프로세스의 워킹 세트를 메모리에 유지시키는 것
- 워킹세트를 메모리에 유지하지 않으면 쓰래싱 유발가능
- 쓰레싱: 페이지 부재가 비정상적으로 많이 발생하여 프로세스 처리보다 페이지 교체처리에 너무 많은 시간을 소비하여 시스템의 처리랑이 급감하는 현상
- 프로세스마다 워킹세트 크기에 맞게 페이지 프레임 개수 조절
- 충분한 여분의 페이지 프레임이 존재
- 실행 프로세스 수 늘림
- 실행중인 프로세스들의 워킹세트 크기의 합이 총 페이지 프레임 수를 넘어섬
- 우선순위가 낮은 프로세스를 일시중지
- 문제점
- 관를 통해 미래를 예측하는 것이 정확하지 않음
- 워킹셑느를 정확이 알아내고 계속 업데이트 하는 것이 현싫적으로 어려움
- 워킹세트 윈도 크기 델다의 최적값을 알기 어려우며 이 역시 변화할 수 있음
PFF 알고리즘
- 페이지 부재빈도(PFF)를 이용하여 프로세스블 페이지 집합의 크리를 변화시키는 기법
- PFF(Page Fault Frequency)
- 얼마자 자주 페이지 교체가 발생하는지를 나타내는 척도
- 페이지 부재가 발생하면 직전 페이지 부재이후로 경과된 시간의 역수
- PFF의 상한과 하한을 정해둠
- PFF가 상한보다 높으면 -> 페이지 프레임 개수를 1증가
- PFF가 하한보다 낮으면 -> 그사이에 참조되지 않았던 페이지를 모두 제거
기억이 안되면, 기록을 -