• 비어 있는 메모리가 많으면 페이지 폴트 발생 시 빈 페이지 리스트에서 빈 페이지를 찾아 폴트 발생한 페이지에 할당하면 됨
• 빈 메모리 공간이 거의 없으면 OS는 메모리 압박 해소를 위해 다른 페이지를 강제로 페이징 아웃 해 공간 확보
• 내보낼 페이지 선택은 OS의 교체 정책 안에 집약 됨

22.1 캐시 관리

• 메인 메모리는 시스템의 가상 메모리 페이지를 가져다 놓기 위한 캐시로 생각할 수 있음
• 캐시를 위한 교체 정책 목표: 캐시 미스 최소화(디스크로 부터 페이지 가져오는 횟수 최소)
• 키시 히트 횟수를 최대로 하는것도 목표(접근된 페이지가 메모리에 이미 존재하는 횟수를 최대로)
• 평균 메모리 접근 시간(average memory access time. AMAT):

  • 컴퓨터 아키텍트가 하드웨어 캐시 성능을 측정 시 사용하는 미터법

  • $AMAT = (P_{Hit} ⋅ T_M) + (P_{Miss} ⋅ T_D)$

    

⚙

$T_M$: 메모리 비 접근 비용

$T_D$: 디스크 접근 비용

$P_{Hit}$: 캐시에서 데이터 항목을 찾을 확률

$P_{Miss}$: 캐시에서 데이터를 못찾을 확율

• 히트와 미스는 각각 0.0에서 1.0 가이의 값을 가지고 두 합은 1.0을 만족

22.2 최적 교체 정책

• 미스를 최소화 하는 정첵
• 가장 먼 시점에 접근할 페이지를 버림
• 구현 HARD

ex)

• 프로그램이 0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1의 순서대로 가상 페이지들을 접근
• 캐시에 세 개 페이지 저장 가능

• 캐시는 빈상태로 시작하기 떄문에 첫 세번은 미스(최초 시작 미스 or 강제 미스)
• 3을 만나면 3은 캐시에 없음으로 미스
• 2을 가장 나중에 접근함으로 2를 버림

히트 6번, 미스 5번 이니 히트율: 54.5%

강제 미스 제외 히트율: 85.7%

22.3 간단한 정책 : FIFO

• 선입선출(먼저 들어온 것이 먼저 나감)

• 시스템에 페이지 들어오면 큐에 삽입

• 교체해야 할 경우 큐의 테일의 페이지가 내보내짐

• 구현 EASY

히트율: 36.4%

강제 미스 제외 히트율: 57.1%

22.4 또 다른 간단한 정책 : 무작위 선택

랜덤 게임

• 메모리 압박 발생 시 무작위로 페이지 선택해 교체
• 구현EASY
• 내보낼 블럭 제대로 선택하려는 노오력을 하지 않음
• 운빨게임이지만 FIFO보다 약간 더 좋은 성능
• 최적의 방법보단 약간 나쁜 성능

동작 방식은 그때 그때 달라짐

22.5 과거 정보의 사용 : LRU

FIFO, 무작위는 중요한 페이지 또는 바로 다시 참조할 페이지를 내보낼 수 있는 문제가 있음

• 페이지 교체 정책이 활용할 수 있는 과거 정보
  • 빈도수: 한 페이지가 여러차레 접근되었으면 어떤 가치가 있기 때문
  • 최근성: 최근에 접근 된 페이지일수록 가까운 미래에 접근 될 확률 높음
• 이런 정책은 지역성의 원칙을 기반에 둔다
• 지역성의 원칙
  • 프로그램은 특정 코드와 자료 구조를 빈번하게 접근하는 경향 있음
  • 과거의 현상을 보고 중요한 페이지 판단후 내보낼 페이지 선택 시 중요 페이지는 메모리에 보존

교체 알고리즘

• LeastFrequently-Used(LFU): 가장 적은 빈도로 사용된 페이지를 교체
• LeastRecently-Used(LRU): 가장 오래 전에 사용하였던 페이지를 교체

• 반대 경우인 Most-Frequently-Used(MFU)와 Most-Recently-Used(MRU)
  와 같은 알고리즘도 존재. 하지만 잘 동작하지 않음

22.6 워크로드에 따른 성능 비교

공간 지역성: 어떤 페이지 P 가 접근되었으면 그 페이지 주변의 페이지들이 참조되는 경향

시간 지역성: 가까운 과거에 참조되었던 페이지는 가까운 미래에 다시 접든되는 경향

• 지역성이 없다면 어느 정책을 사용하든 상관X

• 20% 페이지들에서 80%의 참조가 발생
• 나머지 80% 페이지 들에서는 20% 참조 발생
• 파레토 법칙이랑 비슷한 경우같음
• LRU의 과거 정보가 완벽하지 않다는 것을 의미
• 상황따라 좋은 방법이 다르다

• 50개 페이지를 순차적 참조하는 경우

22.7 과거 이력 기반 알고리즘의 구현

• 이처럼 LRU는 좋은 결과를 보이지만 과거 정보에 기반 둔 정책은 문제 있음
• 어떤 페이지 교체할지 알아내는 비용을 최소화 해야함
• 이를 위해 페이지 접근시 해당 페이지를 목록의 맨 앞으로 이동
• 최근 접근 을 관리하기 위함

22.8 LRU 정책 근사하기

LRU 정책에 가까운 구현은 가능하다

• use bit(reference bit)라는 하트웨어 지원이 필요
• 페이지 참조될 때 마다 HW에 의해 use bit가 1로 설정됨
• HW는 이 비트를 절대 지우지 않음(0으로 설정 X)
• 운영체제가 0으로 바꿈

use bit를 활용하는 방법은 시계 알고리즘이 있다

가정

• 시스템의 모든 페이지들이 환형 리스트 구성

• 시계바늘이 특정 페이지 가리킴

• 페이지 교체 시 OS는 현재 바늘이 가르키고 있는 페이지 use bit가 1이면 (최근에 사용) 교체 대상 X

• 후 use bit 0으로 설정, 다음 페이지 넘어가 use bit가 0인 페이지 찾음

22.9 갱신된 페이지 (Dirty Page)의 고려

페이지가 변경 되어 더티 상태 되었을 때 그 페이지를 내보내기 위해서는 디스크에 변경내용을 기록해야 하기 때문에 비용이 높다

변경되지 않았으면 추가비용 X

이 동작을 지원하기 위해 HW는 modified bit(더티 비트) 포함해야 함

22.11 쓰래싱

쓰래싱(thrashing): 메모리 사용 요구가 감당X, 실행중 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우 시스템이 무한 페이징을 하는 상황

해결 방안

• 진입 제어
  • 다수 프로세스 존재 시 일부 프로세스 실행 중지
  • 워킹 셋: 프로세스가 실행중 일정 시간동안 사용하는 페이지 집합
• 메모리 부족 킬러(일부 버전 Linux)
  • 메머리 요구 초과 시 실행
  • 메모리 요구량 높은 프로세스 골라죽임
  • 문제가 많다