Demand Paging

가상 메모리 전략

메모리의 범위를 보조기억장치까지 확대하여.

대부분의 메모리들(사용되지 않고 있는)이 보조기억장치에 존재하는 것처럼 운영하는 전략.

이 전략으로 응용 프로그램의 크기가 주 기억장치의 크기보다 크더라도 실행할 수 있다.

 

Demand Paging

프로세스의 모든 페이지를 메모리에 올려 놓지 않고, 페이지가 필요할 경우 물리 메모리로 로딩한다.

해당 기법을 위해 페이지 테이블에 추가되는 정보

Valid/Invalid bit : 해당 페이지가 물리 메모리에 존재하는지에 대한 Flag bit.

물리 메모리에 존재하면 1이고 보조기억장치(스왑 영역)에 존재하면 0이다.

Modified bit : 해당 페이지가 물리 메모리에 적재된 이후 수정되었는가에 대한 Flag bit.

수정 되었다면 1이고 수정되지 않았다면 0이다.

나중에 페이지가 물리 메모리에서 제거될 때 Modified bit가 1이라면 보조기억장치에

해당 내용이 기록되어야 한다.

 

Page Fault

가상 주소를 물리 주소로 바꿀 때, 해당 페이지가 프레임에 없는 경우 Page Fault가 발생한다.

Page Fault가 발생하면 해당 페이지를 올릴 프레임을 할당하고 스왑 영역 또는 실행 파일로부터 페이지를 로딩한다.

Swap In(Page In) : 스왑 영역에서 한 페이지를 메모리 프레임으로 읽어들이는 행위.

Swap Out(Page Out) : 메모리 프레임에 저장된 페이지를 스왑 영역에 저장하는 행위.

 

Page Fault 진행 과정

1. CPU에서 가상 주소 액세스를 시도한다.

2. 해당 주소를 페이지 테이블에서 검색한다.

3. 해당 페이지의 P bit(Valid bit)가 0인 것을 확인.(Page Fault 발생)

4. 페이지 폴트 핸들러 커널 코드가 실행된다.

5. 해당 페이지를 로드하기 위해 물리 메모리에서 희생 될 프레임을 선택한다.

6. (선택된 프레임에 해당하는) 희생될 페이지가 스왑 아웃되어 스왑 영역(보조기억장치)에 저장된다.

6-1 저장될 시 Modified bit가 1일 경우 저장되면서 값을 기록한다.

7. 현재 액세스를 시도하려는 페이지를 스왑 영역(보조기억장치)에서 찾는다.

8. 찾은 페이지를 비워두었던 프레임에 로드한다.

9. 페이지 테이블을 갱신한다(Valid bit를 1로, Modified bit를 0으로, 프레임 번호를 할당받은 곳의 번호로 갱신)

10. 해당 물리 메모리에 액세스.

 

요구 페이징을 위한 필수 알고리즘

1. 페이지 할당 알고리즘

프로세스당 할당할 프레임의 개수를 결정하는 알고리즘.

알고리즘의 목표 : 프로세스의 작업 집합(working set)에 포함된 페이지들을 수용할만한 개수의 메모리 프레임을 할당,

Page Fault 발생을 최대한 줄이는 것.

- 균등 할당 정책

모든 프로세스에게 프로세스의 크기와 관계없이 동일한 개수의 프레임을 할당.

작은 프로세스에게 많은 프레임을 주는 경우 낭비가 발생하며

큰 프로세스에게 적은 프레임을 주는 경우 페이지 폴트가 자주 발생한다.

- 비례 할당 정책

프로세스에게 할당하는 프레임의 개수를 프로세스의 크기에 비례하여 전체 프레임을 나누어 할당

프레임이 많이 필요한 프로세스에게 많은 프레임을 할당함으로써 전체적인 페이지 폴트의 수를

줄일 수 있지만 프로세스의 크기는 실행 중에 온전히 알 수 없음.

실행 중에 작업 집합에 대한 판단을 해야하는 필요성이 생김.

 

결국 프레임에게 할당할 적정 프레임의 숫자는 작업 집합을 구성할 정도, 또는

작업 집합을 약간 넘나드는 크기가 적당하다.

Windows 운영체제의 경우 프로세스마다 최소, 최대 할당 프레임 수가 존재함.

이를 working set이라고 부른다.

프로세스가 생성될 때, 최소 working set이 예약되고 프로세스가 실행되면 최소 working set만큼의

페이지가 상주할 수 있는 메모리를 할당하고자 노력한다.

 

2. 페이지 교체 알고리즘

Page Fault가 발생했을 경우 빈 프레임이 없을 때. 비울 프레임을 결정하는 알고리즘.

교체할 페이지를 선택하고 그 페이지가 들어 있는 프레임을 비우게 됨.

목표 : 작업 집합에 속하지 않은 페이지를 교체 페이지로 선택.

현재 프레임에 들어있는 페이지들은 어떤 프로세스의 작업 집합에 포함되어 있을 가능성이 높다.

현재 메모리의 상태는 실행 중인 프로세스들의 작업 집합으로 볼 수 있다.

희생할 프레임의 선택 범위

지역 교체 - 요청한 프로세스가 할당 받은 프레임 중에서 선택.

전역 교체 - 전체 프레임 중에서 선택.

알고리즘 종류

최적 교체 - 이론적인 최적 알고리즘.

가장 먼 미래에 사용될 페이지를 교체 대상으로 결정.

가장 먼 미래에 사용될 페이지를 알 수 없기 때문에 비현실적인 방안.

다른 알고리즘의 평가를 위한 기준으로 사용된다.

 

FIFO - First in, First Out

가장 먼저 들어온 페이지를 추방.

페이지가 로딩된 시간 저장 혹은 큐를 사용.

이해하기 쉽고, 구현이 쉽지만 성능이 좋지 않음.

오래 된 페이지에도 자주 사용되는 변수나 코드가 있을 수 있다.

 

LRU - 가장 최근에 사용되지 않은 페이지 선택

많은 운영체제들이 이를 변형하여 사용.

페이지가 처음 Fault되어 집합에 들어오거나 참조될 때마다 refresh 하는 방식이다.

 

Thrashing

프로세스 혹은 스레드가 실행되는 동안 빈번한 Page Fault가 발생하여 

시스템이 Page Fault를 서비스하느라 대부분의 시간을 소비하는 현상.

디스크 입출력이 심각하게 증가하며 CPU 활용률이 대폭 감소한다.

원인

메모리 양에 비해 프로세스의 개수가 너무 많은 경우

실행중인 각 프로세스의 실행에 필요한 프레임들을 모두 합친 메모리 양이 설치된 메모리에 비해 너무 클 경우

메모리에 비해 너무 많은 프로세스가 실행되어 한 프로세스에게 할당된 프레임의 개수가 너무 적을 경우

프로세스가 실행되는데 필요한 최소 페이지의 개수보다 작은 수의 프레임이 프로세스에 할당될 경우

기본적으로 메모리의 양이 너무 적은 경우 등이 원인이 된다.