페이지 교체 알고리즘
페이지와 프레임
페이지: 가상 메모리를 일정한 크기로 나눈 블럭프레임: 물리 메모리를 일정한 크기로 나눈 블럭
페이지 교체
프로그램 부분적재
가상 메모리를 사용하면서 실제 물리적 메모리의 크기보다 논리적 메모리 크기가 커지면서 물리 메모리에 프로그램의 일부 페이지만 부분적재
요구 페이징
CPU가 해당 페이지를 요구할 때까지 적재하지 않는 요구 페이징 방식을 사용
페이지 대치
페이지 부재가 발생하면 트랩을 걸어 해당 페이지를 적재해야 하는데 물리 메모리에 페이지를 적재할 여유가 없으면 물리 메모리에서 희생될 페이지를 찾아 교체
이때 어떤 메모리를 희생시킬 것인지 결정하는 알고리즘 필요
페이지 교체 알고리즘 종류
최적 대치 알고리즘(Belady, B0)
앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아서 교체, 실현 어려움, 페이지 교체 알고리즘의 상한선
최악 대치 알고리즘
랜덤하게 아무 페이지 선택, 페이지 교체 알고리즘의 하한선
FIFO
메모리에 적재된지 가장 오래된 페이지 교체
Belady's Anomaly : 프레임 수가 커져도 페이지 교체율이 증가 가능
LRU
가장 오래 사용하지 않은 페이지 대치
locality of reference에 근거하여 오래 사용하지 않은 페이지는 앞으로도 사용되지 않을 것이라고 가정
B0와의 대칭성에 따른 성능의 유사성
사용한 시간 정보를 저장하는 법
계수기 or 클럭의 시간값 사용 : 페이지 테이블에 클럭 레지스터 값을 복사해둠
스택 사용 : 페이지를 스택에 담고 사용할 때마다 top으로 이동시키며 스택 유지
LFU
가장 적은 참조횟수를 가지는 페이지 교체
가장 적은 참조횟수를 가지는 페이지가 여러 개면 LRU 적용
오버헤드를 줄이면서 지역성 활용, 횟수를 기준으로 하므로 최근에 사용된 프로그램이 교체되는 오버헤드
LRU 근사 알고리즘
계수기 or 클럭 시간, 스택 대신 하드웨어의 지원으로 LRU 구현
참조비트
각 페이지마다 참조비트를 추가해 초기엔 0으로 설정하고 사용되면 하드웨어가 1로 설정
참조비트를 보고 사용순서는 몰라도 사용여부 판별
참조바이트
각 페이지마다 참조바이트도 추가하고 일정 시간마다 참조바이트를 시프트하고 참조비트를 추가
최근 8회의 시간동안 해당 페이지의 참조기록을 저장하여 참조바이트 값이 가장 작은 페이지를 대치
한계 : 바이트라 8번까지 기억 가능
2차 기회 알고리즘
참조비트가 0이면 교체하고, 1이면 0으로 설정해 다시 기회를 부여
개선된 2차 기회 알고리즘
참조비트 뿐만 아니라 오염비트까지 사용해 성능 개선
참조X변경X -> 참조X변경O -> 참조O변경X -> 참조O변경O 순으로 교체
페이지 교체 범위
Local : 같은 프로세스의 페이지만 교체 가능 (scalability)
Global : 아무 페이지나 교체 가능 (efficient)
사전 대치
페이지 부재 발생 시, 트랩에 의해 처리되고 프로세스가 다시 스케줄링되어야 함
항상 빈 프레임을 가지고 있으므로 오버헤드를 줄임
사전 적재
페이지 참조에 대한 예측을 통해 미리 여러 페이지를 한 번에 적재해 놓는 방법
함수와 행렬과 같은 경우 연관 페이지를 모두 적재
프레임
페이지 부재율과 프레임 수는 반비례
프로세스에 프레임 할당하는 방법
균등 할당 : 모든 프로세스에 똑같은 수의 프레임
비례 할당 : 프로그램의 크기에 비례하여 프레임 할당
우선순위 할당 : 우선순위에 따라 프레임 할당
페이지 크기
작아지면 locality에 의해 페이지 부재율 낮아짐, 커지면 locality 효과가 약화되어 페이지 부재율 커짐
쓰레싱
프로세스가 많아지면 페이지 부재율이 증가하고, 프로세스는 페이징을 기다리는 동안 CPU 이용률이 떨어져서 CPU 스케줄러는 프로세스 수를 증가시키는 악순환
프로세스가 실행되는 시간보다 페이지 교체하는 데 더 많은 시간 소요
작업 세트 모델로 프로세스마다 최소한의 프레임 수 보장
리눅스에서의 페이지 교체
LRU 근사 페이지 교체 사용
Page aging(LFU), Exponential decline(LFU + LRU), 다중 레벨 LRU 참고
Last updated
