1학년 1학기 기말고사 컴퓨터 시스템 일반 - 가상 기억 장치

작성일 | In
가상 기억 장치
  • 가상기억장치 : 현재 사용중인 프로그램의 일부를 주기억장치에 유지하고 나머지는 보조기억장치에 유지
  • 사용자가 보조기억장치의 용량만큼 기억장소를 갖고 있는 것처럼 프로그램 작성 가능
  • 사용자 프로그램이 물리 메모리보다 커져도 됨
메모리 계층 구조
레지스터 <워드>
로드/저장
에 의한
엄격한 이동		 캐시 <라인>
캐시 실패에
따른 자동 전송		 주기억장치 <페이지>
페이지 부재에
따른 자동 이동		 가상 기억 장치
  • 페이징 시스템으로 가상 메모리 구현
  • 주기억장치의 제한된 용량과 중첩 사용 문제 해결
사상(Mapping)
  • 사상 : 가상 주소를 실제 물리 주소로 변환하는 과정
가상 주소 만들기
  • 프로그램을 여러 개의 블록으로 나누고, 각 명령어는 블록 번호(b)와 블록의 시작점부터 해당 명령어까지의 변위(d)를 쌍으로 만듬
  • 주기억장치도 블록 프레임으로 나눔
  • OS는 프로그램의 블록이 실제로 어디에 있는지 페이지 테이블에 저장, 유지/관리
가상 기억 장치 관리 정책
  • 반입(fetch) 정책
    • 어떤 페이지/세그먼트를 메모리로 반입할 것인가?
    • 요구 페이징
      • 해당 페이지가 요구될 때만 보조기억장치에서 주기억장치로 반입
      • 프로그램의 일부를 처리할 때 다른 부분은 실행되지 않는다는 사실을 이용하여 프로그램의 일부만을 주기억장치에 적재
      • 가상메모리는 보통 페이징으로 구현되며, 세그먼트 시스템들은 대부분 하나의 세그먼트가 다시 여러 페이지로 나뉘는 기법 사용
    • 예상 페이징 : 요청될 페이지를 미리 예측하여 반입
    • 프로그램이 메모리에 있지 않은 페이지 사용시 페이지 부재(page fault) 발생

  • 배치(placement) 정책
    • 반입한 페이지/세그먼트 를 어디에 둘 것인가?
    • 페이지 : 블록과 메모리의 블록 프레임 크기가 같고, 어떤 프레임에 적재하던지 PMT에 존재하므로 문제 없음
    • 세그먼트 : 가변 분할 기법처럼 최초/최적/최악 적합 등과 같은 배치 기법 필요

  • 교체(replacement) 정책
    • 페이지 부재가 발생하고, 메모리가 꽉 차 있을 경우, 어떤 페이지를 하드디스크로 보낼 것인가?
페이지 교체 순서
  1. 디스크에서 필요한 페이지의 위치 파악
  2. 빈 페이지 프레임 탐색
    1. 빈 프레임이 있으면 사용
    2. 없다면 희생될 프레임 선정 위해 페이지 교체 알고리즘 실행
    3. 희생될 페이지를 디스크에 기록 후, 관련 테이블 수정
  3. 빼앗을 프레임에 새 페이지를 읽어오고 테이블 수정
  4. 페이지 부재가 발생한 지점에서부터 사용자 프로세스 계속함
페이지 교체 알고리즘
  • FIFO 페이지 교체
    • 가장 먼저 들어온 페이지를 교체
    • 이해 쉽고 설계 간단 but 오래 있던 페이지는 앞으로 계속 사용될 가능성이 높다.
    • Belady의 모순
      • 프로세스에게 프레임을 더 주었는데 페이지 부재율은 더 증가

  • 최적 페이지 교체(OPT, Optimal Page replacement)
    • 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체
    • 어떤 페이지가 필요할 것인지 알 수 없으므로 현실적이지 않다.

  • LRU(Least Recently Used)
    • 가장 오랫동안 사용하지 않은 페이지를 교체
    • 불러왔던 시간을 기록해야 하므로 시간 오버헤드 발생, 구현 어려움

  • LFU(Least Frequently Used)
    • 참조 횟수가 가장 적은 페이지를 교체
    • 바로 불러온 페이지가 교체될 수 있다.
      • 가장 최근에 주기억장치로 옮겨온 페이지가 가장 참조 횟수가 적을 수 있다.

  • 2차 기회 페이지 교체 알고리즘(Second Change Algorithm)
    • 기본은 FIFO
    • 페이지가 선택될 때 참조 비트 조사
      • 0이면 페이지 교체
      • 1이면 그 페이지에 2차적 기회 부여
    • 모든 참조 비트는 0으로 초기화
    • 그 후 참조된 페이지는 1로 변경
    • 1인 페이지가 참조되면 0으로 변경하고 다음에 페이지 교체

  • 2차 기회 개선 알고리즘(Enhanced Second Change Algorithm) = NUR(Not Used Recently)
    • std::pair<참조 비트, 변경 비트>
      • <0, 0> : 최근 사용x, 수정x - 교체하기 가장 좋은 페이지
      • <0, 1> : 최근 사용x, 수정o - 페이지를 교체하려면 디스크에 내용 기록
      • <1, 0> : 최근 사용o, 수정x - 다시 사용될 확률 높음
      • <1, 1> : 최근 사용o, 수정o - 다시 사용될 확률 높은, 교체시 디스크에 내용 기록