가상 기억 장치
- 가상기억장치 : 현재 사용중인 프로그램의 일부를 주기억장치에 유지하고 나머지는 보조기억장치에 유지
- 사용자가 보조기억장치의 용량만큼 기억장소를 갖고 있는 것처럼 프로그램 작성 가능
- 사용자 프로그램이 물리 메모리보다 커져도 됨
메모리 계층 구조
레지스터 | <워드> 로드/저장 에 의한 엄격한 이동 | 캐시 | <라인> 캐시 실패에 따른 자동 전송 | 주기억장치 | <페이지> 페이지 부재에 따른 자동 이동 | 가상 기억 장치 |
---|
- 페이징 시스템으로 가상 메모리 구현
- 주기억장치의 제한된 용량과 중첩 사용 문제 해결
사상(Mapping)
- 사상 : 가상 주소를 실제 물리 주소로 변환하는 과정
가상 주소 만들기
- 프로그램을 여러 개의 블록으로 나누고, 각 명령어는 블록 번호(b)와 블록의 시작점부터 해당 명령어까지의 변위(d)를 쌍으로 만듬
- 주기억장치도 블록 프레임으로 나눔
- OS는 프로그램의 블록이 실제로 어디에 있는지 페이지 테이블에 저장, 유지/관리
가상 기억 장치 관리 정책
- 반입(fetch) 정책
- 어떤 페이지/세그먼트를 메모리로 반입할 것인가?
- 요구 페이징
- 해당 페이지가 요구될 때만 보조기억장치에서 주기억장치로 반입
- 프로그램의 일부를 처리할 때 다른 부분은 실행되지 않는다는 사실을 이용하여 프로그램의 일부만을 주기억장치에 적재
- 가상메모리는 보통 페이징으로 구현되며, 세그먼트 시스템들은 대부분 하나의 세그먼트가 다시 여러 페이지로 나뉘는 기법 사용
- 예상 페이징 : 요청될 페이지를 미리 예측하여 반입
- 프로그램이 메모리에 있지 않은 페이지 사용시 페이지 부재(page fault) 발생
- 배치(placement) 정책
- 반입한 페이지/세그먼트 를 어디에 둘 것인가?
- 페이지 : 블록과 메모리의 블록 프레임 크기가 같고, 어떤 프레임에 적재하던지 PMT에 존재하므로 문제 없음
- 세그먼트 : 가변 분할 기법처럼 최초/최적/최악 적합 등과 같은 배치 기법 필요
- 교체(replacement) 정책
- 페이지 부재가 발생하고, 메모리가 꽉 차 있을 경우, 어떤 페이지를 하드디스크로 보낼 것인가?
페이지 교체 순서
- 디스크에서 필요한 페이지의 위치 파악
-
빈 페이지 프레임 탐색
- 빈 프레임이 있으면 사용
- 없다면 희생될 프레임 선정 위해 페이지 교체 알고리즘 실행
- 희생될 페이지를 디스크에 기록 후, 관련 테이블 수정
- 빼앗을 프레임에 새 페이지를 읽어오고 테이블 수정
- 페이지 부재가 발생한 지점에서부터 사용자 프로세스 계속함
페이지 교체 알고리즘
- 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 - 다시 사용될 확률 높은, 교체시 디스크에 내용 기록
- std::pair<참조 비트, 변경 비트>