[OS] 9. Virtual Memory Management(가상 메모리 관리)

Part 1.

적재(fetch) 전략

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

요구 페이징(demand paging)

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

지역성(locality, 구역성, 국부성)

• Peter J. Denning 증명(1968)
• 프로세스는 현재 실행되는 주소 부근에서 국부적인 부분만을 집중적으로 참조한다는 성질
  • 페이징 시스템: 가상 주소 공간에서 인접한 몇 개의 페이지만을 특정 시점에서 사용
• 가상 메모리 관리의 이론적 근거
• 시간 지역성(temporal locality)
  • 최근 참조된 메모리 공간이 가까운 미래에도 계속 참조될 가능성 높음
  • 반복(loop) 구조, 프로시저, 스택(stack) 등
• 공간 지역성(spatial locality)
  • 일단 어떤 메모리 위치가 참조되면 근처 메모리 공간도 계속 참조되는 경향
  • 배열 검색, 순차적 코드의 실행, 관련변수의 인접 선언 등

페이지 교체(replacement)

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

 

 

Part 2.

페이지 교체 전략: 어떤 페이지를 메모리에서 내보낼지 결정

-이상적인 교체 전략: 가장 오랫동안 참조되지 않을 페이지 선택. 구현 어려움.

-휴리스틱(heuristic) 이용

• 무작위 페이지 교체(random page replacement)
  • 무작위로 교체할 페이지 선택
  • 구현 용이
  • 바로 다음 참조될 페이지도 교체 가능
• 선입선출(FIFO) 페이지 교체
  • 가장 오랫동안 메모리에 머문 페이지 교체
  • 비교적 낮은 비용으로 구현 가능
  • 가장 빈번하게 사용되는 페이지가 교체될 가능성
  • 실제 적용에는 부적합
• Belady의 모순(Delady's Anomaly)
  • FIFO 페이지 교체 전략 사용 중
  • 페이지 프레임 수를 늘리면 페이지 부재의 발생이 감소해야하나 오히려 늘어나는 경우가 발생하는  상황
• 최소 최근 사용(Least-Recently-Used, LRU) 페이지 교체
  • 가장 오랫동안 참조되지 않은 채 메모리를 차지한 페이지 교체
  • FIFO 교체 전략보다 효과적
  • FIFO 교체 전략보다 구현 부담 증가(참조된 페이지를 대기열의 맨 뒤로)
  • 바로 다음에 참조될 페이지 교체 가능(loop 구조에서 발생 가능)
• 최소 사용빈도(Least0Frequently-Used, LFU) 페이지 교체
  • 가장 적게 사용되는 페이지 교체
  • 자주 참조되지 않는 페이지는 앞으로도 사용될 가능성이 낮을 것 가정
  • 잘못된 페이지 교체 가능성
    • 과거에 자주 사용된 페이지는 앞으로 사용되지않을 가능성 있음.
    • 새로운 페이지일수록 참조 빈도가 낮지만, 앞으로 자주 참조될 가능성 있음
• 최근 미사용(Not-Used-Recently, NUR) 페이지 교체
  • 최소 최근 사용(LRU) 방법을 낮은 비용으로 근사
  • 참조 비트(reference bit)와 변경 비트(modified bit) 사용
    • 참조비트
      • 최근 사용되지 않은 페이지 확인
      • 주기적 reset
      • 사용시 setting
    • 변경 비트
      • 해당 페이지에 수정이 있을 시 셋팅
  • 하드웨어적인 참조/변경 비트가 없는 시스템에서도 구현 가능
  • 참조/변경 비트값에 따른 페이지 교체 우선순위
    • (참조,변경)일때 : (0,0)-(0,1)-(1,0)-(1,1)
• 이차기회(Second Chance) 페이지 교체
  • FIFO 교체 전략의 변형
  • 페이지별로 참조 비트(referenced bit)가 있는 FIFO 전략
    • 페이지가 참조될 때마다, 참조 비트를 on(1)로 설정
    • 가장 오래된 페이지의 참조 비트 확인
      • FIFO 대기열(queue)로 페이지 참조비트 관리
      • 대기열의 front에서 교체 대상 선택
        • >>on상태: off시킨 후, FIFO 대기열의 맨 뒤로 배치
        • >>off상태: 해당 페이지 교체
    • 모든 참조비트가 1이면 전체적으로 참조비트를 0으로 설정
  • 사용중인 페이지가 교체될 확률 최소화
• 클록(clock) 페이지 교체
  • 이차기회 페이지 교체와 유사
  • FIFO 대기열 대신에 환형 리스트(circular list) 사용
• 원거리 페이지(far page) 교체
  • 프로세스의 참조 패턴을 나타내는 접근 그래프 생성(컴파일된 프로그램에서 생성)
  • 접근 그래프에서 참조된 페이지로부터 가장멀리 떨어진 참조되지 않은 페이지 교체
  • 모든 페이지가 참조되면(marked) 전체 페이지 reset
  • 실제 구현 곤란(생성비용)

 

Part 3.

스레싱(thrashing)

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

작업집합(working set)

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

 

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

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

페이지 부재 빈도(Page-Fault-Frequency, ,PFF) 페이지 교체

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

전역 페이지 교체(global replacement): 프로세스를 구별하지 않고, 전체 페이지 프레임 중에 선택하여 교체. 프로세스별 할당되는 페이지 프레임 수 조절 곤란

지역 페이지 교체(local replacement): 각 프로세스가 자신에게 할당된 페이지 프레임 중에서 하나를 선택하여 교체

 

페이지 크기에 따른 특성

• 페이지가 작을 수록 테이블 단편화 발생
• 페이지가 작을수록 다른 프로세스에 대한 메모리 사용기회 확대
• 마지막 페이지의 절반(안쓰는 양의 평균)은 낭비=> 페이지가 클수록 불리
• 페이지가 클 수록 디스크로부터 전송시간 감소. 작으면 여러번 입출력 필요. 회전/탐색지연은 전송시간보다 큰 부담
• 페이지가 작으면 총 입출력 감소.
• 페이지가 크면 페이지 부재 감소

페이지 부재 시간간격(interfault time): 프로세스에 할당된 페이지 프레임의 수에 따라 페이지 부재 시간 간격은 증가하다가 수렴

시간경과에 따른 참조되는 페이지 비율: 실행시간 후 짧은 시간 내에 상당수 페이지 참조

 

Linux의 페이지 교체 전략

• 변형된 clock 페이지 교체 전략
  • 두개 연결리스트 사용
  • 활성리스트: 활성페이지 포함. 리스트 앞에 가장 최근 사용한 페이지 위치
  • 비활성리스트: 비활성 페이지 포함. 가장 오래전에 사용된 페이지 리스트 끝에 배치