가상 메모리 관리

가상 메모리 적재 전략

적재(fetch) 전략

• 페이지나 세그먼트를 보조기억장치에서 메모리로 이동시키는 시점 결정
• 예측 적재 전략
  • 프로세스가 조만간 참조할 것 같은 페이지를 예측하여 적재
  • 휴리스틱 사용
• 요구 적재 전략
  • 프로세스에서 명시적으로 참조하는 페이지를 적재
  • 해당 페이지가 적재될 때까지 대기

요구 페이징

• 페이징 시스템에서 요구할 때 페이지를 적재하는 것
• 페이지 적재를 위한 대기 시간 증가

지역성

• 프로세스는 현재 실행되는 주소 부근에서 국부적인 부분만을 집중적으로 참조한다는 성질
  • 페이징 시스템
    • 가상 주소 공간에서 인접한 몇 개의 페이지만을 특정 시점에서 사용
• 가상 메모리 관리의 이론적 근거
• 시간 지역성
• 공간 지역성

시간 지역성

• 최근 참조된 메모리 공간이 가까운 미래에도 계속 참조될 가능성 높음
• 반복 구조, 프로시저, 스택 등

공간 지역성

• 일단 어떤 메모리 위치가 참조되면, 근처 메모리 공간도 계속 참조되는 경향
• 배열 검색, 순차적 코드의 실행, 관련변수의 인접 선언 등

페이지 교체

• 페이지 부재(page fault)
  • 참조하려는 페이지가 메모리에 없는 상황
• 페이지 부재가 발생하면
  • 해당 페이지를 보조기억장치에서 메모리로 적재
  • 페이지 사상표의 해당 항목 갱신
• 빈 페이지 프레임이 없으면, 메모리 상의 페이지를 보조기억장치로 내보내어, 공간 확보
  • 교체 대상 페이지가 수정되지 않은 경우
    • 보조기억장치로 저장 불필요
  • 변경 비트(modified bit, dirty bit) 사용
    • 페이지 사상표의 항목에 포함
    • 해당 페이지의 변경여부 표시

페이지 교체 전략

• 어떤 페이지를 메모리에서 내보낼지 결정

최적의 페이지 교체 전략(optimal page replacement strategy)

• 가장 오랫동안 참조되지 않을 페이지 선택
• 구현 곤란
• 휴리스틱을 이용하여 교체할 페이지 결정

무작위 페이지 교체(random page replacement)

• 무작위로 교체할 페이지 선택
• 구현 용이
• 바로 다음 참조될 페이지도 교체 가능

선입선출(FIFO) 페이지 교체

• 가장 오랫동안 메모리에 머문 페이지 교체
• 비교적 낮은 비용으로 구현 가능
• 가장 빈번하게 사용되는 페이지가 교체될 가능성
• 실제 적용에는 부적합

Belady의 모순

• FIFO 페이지 교체전략 사용 중
• 페이지 프레임의 개수를 늘리면 페이지 부재의 발생이 감소해야 하나, 오히려 늘어나는 경우가 발생하는 상황

최소 최근 사용(LRU) 페이지 교체

• 가장 오랫동안 참조되지 않은 채 메모리를 차지한 페이지 교체
• FIFO 교체 전략보다 효과적
• FIFO 교체 전략보다 구현 부담 증가
  • 참조된 페이지는 대기열의 맨 뒤로 이동
• 바로 다음에 참조될 페이지 교체 가능
  • 반복 구조에서 발생 가능

최소 사용빈도(LFU) 페이지 교체

• 가장 적게 사용되는 페이지 교체
• 자주 참조되지 않는 페이지는 앞으로도 사용될 가능성이 낮을 것 가정
• 잘못된 페이지 교체 가능성
  • 과거에 자주 사용된 페이지는 앞으로 사용되지 않을 가능성 있음
  • 새로운 페이지일수록 참조 빈도가 낮지만, 앞으로 자주 참조될 가능성이 있음

최근 미사용(NUR) 페이지 교체

• 최소 최근 사용(LRU) 방법을 낮은 비용으로 근사
• 참조 비트와 변경 비트 사용
  • 참조 비트
    • 최근 사용되지 않은 페이지 확인
    • 주기적으로 리셋
    • 사용시 셋팅
  • 변경 비트
    • 해당 페이지에 수정이 있을 시 셋팅
• 하드웨어적인 참조/변경 비트가 없는 시스템에서도 구현 가능
• 우선 순위
  • 1: 참조: 0 변경: 0
  • 2: 참조: 0 변경: 1
  • 3: 참조: 1 변경: 0
  • 4: 참조: 1 변경: 1

이차기회 페이지 교체

• FIFO 교체 전략의 변형
• 페이지별로 참조 비트가 있는 FIFO 전략
  • 페이지가 참조될 때 마다, 참조 비트를 on(1) 으로 설정
  • 가장 오래된 페이지의 참조 비트 확인
    • FIFO 대기열(queue)로 페이지 참조비트 관리
    • 대기열의 front에서 교체 대상을 선택
      • on 상태: off 시킨 후, FIFO 대기열의 맨 뒤로 배치
      • off 상태: 해당 페이지 교체
  • 모든 참조 비트가 1이면, 전체적으로 참조비트를 0으로 설정
• 사용중인 페이지가 교체될 확률을 최소화

클록 페이지 교체

• 이차기회 페이지 교체와 유사
• FIFO 대기열 대신에 환형 리스트 사용

원거리 페이지 교체

• 프로세스의 참조 패턴을 나타내는 접근 그래프 생성
  • 컴파일된 프로그램에서 접근 그래프 생성
• 접근 그래프에서 참조된 페이지로 부터 가장 멀리 떨어진 참조되지 않은 페이지 교체
• 모든 페이지가 참조되면 전체 페이지 리셋
• 실제 구현 곤란
  • 접근 그래프 생성 비용

쓰레싱(thrashing)

• 너무 자주 페이지 교체가 일어나는 현상
• 페이지 부재가 계속적으로 발생하여, 프로세스의 처리시간보다 페이지 교체시간이 더 많아지는 현상
  • 낮은 CPU 사용율 초래
  • OS는 다중 프로그래밍 정도 증가 필요 판단
  • 추가적인 프로세스 실행
  • 페이지 부재 증가 악순환

작업 집합 모델

작업 집합(working set)

• 실행 중인 프로세스가 일정 시간 동안에 참조하는 페이지들의 집합
• 페이지 작업집합 W(t,w)
  • 시간 윈도우 [t-w,t] 동안 프로세스가 참조한 페이지들의 집합
  • 프로세스의 효율적인 실행을 위해 메모리에 있어야하는 페이지들의 집합
    • 작업 집합이 메모리에 유지되지 않으면 쓰레싱 발생 가능
  • 지역성 특성 때문에 작업집합 유지 가능

윈도우 크기와 작업 집합의 크기의 관계

• 윈도우 크기 w가 커짐에 따라 메모리에 유지하는 작업 집합도 커지지만, w가 일정수준 이상 커지면 작업집합이 증가하지 않음

작업 집합 기반 페이지 교체 전략

• 작업 집합 내의 페이지만 메모리에 유지
• 프로세스가 작업 집합 간에 전이를 하는 경우
  • 새로운 작업 집합에 속하지 않을 페이지들이 메모리에 존재
  • 이들 페이지를 줄이는 것이 메모리 관리 목표

페이지 부재 빈도(PFF) 페이지 교체

• 프로세스의 페이지 부재 빈도에 따라 메모리에 유지할 페이지 개수 조절
• 페이지 부재 간격(interfault time)에 따라 메모리에 유지할 페이지 개수 조절
• 작업 집합 페이지 교체 전략 대비 장점
  • PFF: 페이지 부재가 발생할 때만 메모리에 유지할 페이지 조정
    • 페이지 부재 발생시점과 바로 이전 페이지 부재 발생시점의 간격이 임계값 이상이면, 그 사이에 참조되지 않은 모든 페이지를 방출
  • 작업 집합 전략: 메모리를 참조할 때마다 작업 집합 관리

전역/지역 페이지 교체

• 전역 페이지 교체
  • 프로세스를 구별하지 않고, 전체 페이지 프레임 중에 선택하여 교체
  • 프로세스 별로 할당되는 페이지 프레임 수의 조절 곤란
• 지역 페이지 교체
  • 각 프로세스가 자신에게 할당된 페이지 프레임 중에서 하나를 선택하여 교체

페이지 크기

페이지 크기에 따른 특성

• 페이지가 작을수록 테이블 단편화(table fragmentation) 발생
  • 페이지 사상표 크기 증가에 따른 기억장소 낭비
• 페이지가 작을수록 다른 프로세스에 대한 메모리 사용기회 확대
• 마지막 페이지의 절반은 낭비
  • 페이지 크기가 클수록 불리
• 페이지가 클수록 디스크로 부터 전송 시간 감소(필요한 부분이 클 때)
  • 페이지가 작으면 여러번 입출력 필요
  • 회전/탐색 시간 지연이 전송시간보다 큰 부담
• 페이지 크기가 작아지면 총 입출력 양은 감소
  • 실제로 필요한 부분만 적재 경향
• 페이지가 클수록 페이지 부재 감소(메모리가 충분히 클 때)

페이징에서 프로그램 동작

페이지 부재 시간간격

• 프로세스에 할당된 페이지 프레임의 수에 따라 페이지 부재 시간은 증가하다가 수렴

시간 경과에 따른 참조되는 페이지의 비율

• 실행 시작 후 짧은 시간 내에 상당수의 페이지가 참조

LINUX의 페이지 교체 전략

변형된 클록 페이지 교체 전략 사용

• 두 개의 연결리스트 사용
• 활성 리스트
  • 활성 페이지 포함
  • 리스트의 앞에 가장 최근 사용 페이지 위치
• 비활성 리스트
  • 비활성 페이지 포함
  • 가장 오래전에 사용된 페이지 리스트 끝에 배치
• 비활성 리스트의 페이지만 교체