가상 메모리

---

프로그램에서 필요한 부분만 메모리에 로드하여 사용하면 다음과 같은 장점이 있다.

1. 프로그램을 개발할 때 실제 주소 공간에 제약에 얽매이지 않아도 된다.

2. 필요한 만큼만 메모리를 사용하기 때문에 더 많은 프로그램을 실행할 수 있다.

3. I/O 연산의 감소로 성능이 좋아진다.

 

프로세스/애플리케이션 프로그래머의 입장에서 메모리 공간은 연속된 가상의 공간이다. text, data, heap, stack의 영역으로 이루어진 sparse 주소 공간인데, 필요할 때만 메모리에 로드하기 때문에, heap과 stack사이의 hole영역은 실제 메모리에 로드되지 않는다.

 

Demand paging & Page fault

필요한 페이지만 메모리에 로드하는 것을 demand paging이라고 한다. 이를 사용하면 page fault가 발생할 수 있는데, 이는 실제 메모리에 로드 되지 않은 페이지로의 접근을 의미한다.

 

페이지 폴트 해결 과정

OS에서 해당 PCB로부터 페이지 테이블을 읽는다. invalid라면 프로세스를 멈춘다. valid한 접근이라면, free frame list를 확인하고, secondary 저장소에 읽기 요청을 한다. 데이터가 전달되면 프레임에 데이터를 저장하고 page table을 업데이트 한 뒤 인터럽트 되었던 프로세스를 재개한다.

이론 상 페이지 한 인스트럭션이 여러 페이지에 존재하는 데이터를 건드려서 여러 페이지 폴트가 발생할 수 있지만, 접근 지역성의 특징으로 인해 이러한 경우는 거의 발생하지 않는다. 따라서 Demand Paging은 현실적으로 쓸만한 방법이다.

 

페이지 교체 (Page Replacement)

free frame이 없다면 프레임 하나를 골라서 원래 있던 내용을 secondary storage에 쓰고, 원하는 내용을 storage에서 가져와서 채워야 한다. 원래 있던 내용을 쓰는 과정은 modify bit가 0이라면 생략할 수 있다.

 

1. FIFO

queue로 추가된 프레임 번호를 관리한다. 가장 오래 전에 가져온 프레임을 victim으로 선정한다.

- 항상 좋지 않다. 메모리를 늘렸는데 페이지 폴트 비율이 올라가기도 한다.

2. 최적 교체 (Optimal Replacement)

- 가장 오랫동안 사용되지 않을 페이지를 희생한다.

- 구현이 불가능하다.

3. LRU (Least Recently Used)

- 가장 오랫동안 사용되지 않은 페이지를 희생한다.

- 최적 교체를 근사한다.

- 페이지 테이블 엔트리에 마지막으로 사용된 시간을 기록하거나, doubly linked list를 통해 구현할 수 있지만 복잡하다.

4. LRU-근사

- 하드웨어에서 프레임에 대한 reference bit를 지원한다.

- shift registred에 8bit history 변수를 저장한다.

- 일정 시간마다 reference bit를 체크하고 8bit history 변수를 right shift하여 업데이트 한다.

- history값이 가장 작은 것이 LRU 프레임이 된다.

5. Second Chance

reference bit만을 가지고 진행한다. circular queue를 관리하고, reference bit가 0인 프레임을 찾는다. 검사하는 프레임마다 reference bit를 0으로 만든다. 모든 reference bit가 1인 경우 FIFO와 동일하다.

6. Enhanced Second Chance (개선된 2차 기회 알고리즘)

reference bit와 modify bit 두 가지를 동시에 본다. 4가지 종류로 프레임을 구별하고, 종류 하나씩 보면서 가장 교체하기 좋은 프레임을 선택한다. 경우에 따라 큐를 여러 번 스캔해야 한다.

7. MFU & LFU

- 프레임 별로 사용된 횟수를 기준으로 관리한다.

- 하드웨어에서 지원하는 게 아니기 때문에 성능상 좋지 않고, 최적 교체에 대한 근사도 아니다.