[13] 가상 메모리

KOCW - 양희재 교수님 강의를 기반으로 운영체제 정리

가상 메모리(Virtual Memory) 기술은 물리 메모리의 크기 보다 큰 프로세스를 실행할 수 있도록 하는 기술입니다. 현재 우리가 쓰는 컴퓨터들은 모두 가상 메모리 기술을 사용하고 있습니다.

요구 페이징

이전 시간에 운영체제는 메모리 낭비 방지를 위해 동적 적재 기술을 사용해 현재 실행에 필요한 루틴만 메모리에 적재합니다. 가상 메모리도 동적 적재와 같은 기술을 사용하는데 프로세스가 페이지 또는 세그멘트 단위로 잘려져 있고 필요한 부분만 메모리에 올리는 기술을 사용합니다. 보통 컴퓨터는 페이지 단위를 사용하기 때문에 이 기술을 요구 페이징(Demanding Paging)이라고 합니다.

위의 그림은 현재 프로세스에서 요구 페이징에 의해 메모리에 적재(load)된 페이지는 총 3개인 상황입니다. 컴퓨터는 특정 페이지가 메모리에 적재되어 있는지 확인하기 위해 valid bit를 사용하여 유효성을 판단합니다.

만약 CPU가 현재 실행되는 프로세스의 3번째 페이지에 접근한다면 valid bit가 0이기 때문에 인터럽트 신호를 발생시킵니다. 해당 인터럽트 신호에 대한 서비스 루틴은 디스크에 저장되어 있는 3번째 페이지를 메모리로 로드시키고 페이지 테이블에 그 정보를 추가하는 작업을 수행합니다.

기본적으로 요구 페이징을 하기 위해서 프로세스 이미지를 저장할 backing store가 필요합니다.

페이지 부재(Page Fault)

페이지 부재는 CPU가 읽으려고 하는 페이지가 메모리에 없는 경우입니다. 위에서 설명한 것 처럼 valid bit가 0인 경우이기 때문에 이 상황을 해결할 루틴을 실행해야 합니다.

• valid bit를 통해 페이지 유효성을 판단한다.

• valid bit가 0이라면 CPU에 인터럽트 신호를 보내 운영체제의 특정 ISR을 실행한다.

• 특정 ISR은 backing store에서 필요한 페이지를 탐색한다.

• 필요한 페이지를 메모리(프레임)에 적재(load) 한다.

• 페이지 테이블을 갱신한다.

• 기존 명령어를 재실행한다.

가상 메모리를 만드는 방식은 대표적으로 두 가지가 있습니다. 일반적으로 요구 페이징 방식을 사용하기 때문에 가상 메모리와 요구 페이징을 같은 용어로 사용할 수 있습니다.

pure demand paging vs. prepaging

pure demand paging은 특정 프로세스가 처음 실행할 때 어떤 페이지가 필요한지 알 수 없으므로, 아무 페이지도 올리지 않습니다. 따라서 처음부터 page fault가 일어나기 때문에 오버헤드가 클 수 있지만 메모리를 최대한 효율적으로 사용할 수 있습니다.

prepaging은 필요하다고 생각되는 페이지를 미리 메모리에 적재되는 방법입니다. 미리 들고온 페이지가 실제로 사용된다면 page fault가 발생하지 않아 속도면에서 효율성이 올라가지만 페이지가 실행되지 않는다면 메모리 낭비로 이어질 수 있습니다.

Swapping vs. Demand paging

스와핑과 요구 페이징은 둘 다 backing store사이를 오고 가는 동작을 합니다. 그러나 스와핑은 프로세스 단위로 이동하고 요구 페이징은 페이지 단위로 이동하는 차이점이 있습니다.

유효 접근 시간

CPU가 어떤 주소를 내었을 때 메모리에 있을 수도 있고 없을 수도 있습니다. 그러므로 페이지를 읽을때 걸리는 시간은 다를 수 있고 유효 접근 시간(Effective Access Time)은 평균적으로 걸리는 시간을 나타냅니다.

• p : 페이지 부재가 일어날 확률

예시를 통해 계산해 보겠습니다.

• $T_m$ : 200 nsec(DRAM)

• $T_p$ : 8 msec(seek time + rotational delay + transfer time)

• $T_{\text{eff}} = (1-p)\times200 + p\times8,000,000 = 200 + 7,999,800\times p$

• $p = \frac{1}{1,000} \rightarrow T_{\text{eff}} = 8.2 \text{usec}$ (40배 정도 느림)

• $p = \frac{1}{1,399,990} \rightarrow T{\text{eff}} = 220 \text{nsec}$ (10% 정도 느림)

페이지 부재시 대부분의 시간은 하드디스크에서 페이지를 탐색하는데 걸리는 시간입니다. 만약 페이지 부재가 1/1000의 확률로 일어난다면 약 8 usec(마이크로)가 소요됩니다. 컴퓨터 내부에서 마이크로세컨드 단위는 매우 느린속도이기 때문에 사실상 사용할 수 없는 상황이라고 할 수 있습니다.

지역성의 원리

현실적으로 메모리 접근은 시간적, 공간적 지역성을 가집니다. 일반적으로 프로그램은 대부분 반복문과 절차적인 순서로 이루어져 있기 때문에 페이지 부재 확률은 매우 낮습니다.

하드디스크 접근 시간 줄이기

HDD는 접근 시간이 매우 길기 때문에 backing store로는 부적합합니다. 따라서 SSD 또는 저렴한 DRAM을 사용하여 디스크 접근시간을 줄이는 것도 하나의 방법입니다.

페이지 교체 (Page Replacement)

요구 페이징 기술은 요구되는 페이지만 backing store에서 가지고 옵니다. 만약 여러 프로세스가 실행되는 상황에 각각의 프로세스의 요구되는 페이지만 메모리에 적재한다고 해도 언제가는 메모리가 가득차게 됩니다.

메모리가 가득 차면 추가로 페이지를 가져오기 위해 원래 메모리에 있던 페이지를 backing store로 몰아내고(page-out) 그 빈 공간에 페이지를 가져옵니다(page-in). 이처럼 다른 페이지를 메모리에 올리기 위해 backing store로 밀려나는 페이지를 victim page라고 표현합니다.

Victim page

victim page로 지정된 페이지는 backing store로 밀려날 때 현재 정보를 다시 써야할 수도 있고 아닐 수도 있습니다. 페이지는 애초에 backing store에 저장되어 있기 때문에 별다른 수정 사항이 없었다면 다시 쓸 필요는 없지만 CPU 작업을 통해 페이지 내용이 수정되었다면 바뀐 내용을 backing store에 새로 써야할 수 있습니다.

이렇게 하드디스크에 새로 쓰는 작업은 입출력 작업인데 일반적으로 입출력 작업은 속도가 느립니다. 따라서 페이지 내용이 수정되지 않은 페이지를 Victim page로 선정합니다.

페이지 내용이 수정되었는지를 확인하기 위해 페이지 테이블에 modified bit(dirty bit)를 추가하여 1이면 수정되고 0이면 수정되지 않은 것을 판단할 수 있습니다.

수정되지 않은 페이지가 여러개 존재한다면 페이지 교체 알고리즘을 통해 선택할 수 있습니다.

페이지 교체 알고리즘

Page reference string

페이지 교체 알고리즘을 알아보기 전에 Page reference string에 대해서 알아봐야 합니다. 페이지 교체 알고리즘을 적용하기 위해선 이진수의 주소가 아닌 페이지 번호가 더 중요한 정보입니다.

이해를 돕기 위해 CPU가 내는 주소가 (100, 101, 102, 432, 612, 103, 104, 611, 612)이고 페이지 크기는 100 byte라면 페이지 번호는 (1, 1, 1, 4, 6, 1, 1, 6, 6)이 됩니다. 100번지의 경우 1번 페이지에서 변위가 0인 경우이고 101번지는 1번 페이지에서 변위가 1인 경우로 생각할 수 있습니다.

이렇게 구한 페이지 번호를 기준으로 page reference string을 나타내면 (1, 4, 6, 1, 6)이 됩니다. 즉 연속된 페이지 번호는 생략하고 하나의 페이지 번호만을 나타낸 것 입니다. 그 이유는 연속된 페이지를 참조할 경우 처음으로 page fault가 발생했다면 같은 페이지에서는 page fault가 발생하지 않기 때문입니다.

First-In First-Out(FIFO)

FIFO 방식은 메모리에 먼저 올라온 페이지를 Victim page로 선정하는 방식입니다.

FIFO 알고리즘을 이해하기 위해 아래와 같은 조건을 예시로 들어보겠습니다.

프레임 개수 : 3 
page reference string : (7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1)

초기 메모리의 상태는 3개의 프레임에 아무것도 적재되어 있지 않는 상태입니다.

• page-in (7) : page fault 1번 발생, 가장 먼저 입장한 페이지 : 7
• page-in (0) : page fault 2번 발생, 가장 먼저 입장한 페이지 : 7
• page-in (1) : page fault 3번 발생, 가장 먼저 입장한 페이지 : 7
• page-in (2) : page-out(7), page fault 4번 발생, 가장 먼저 입장한 페이지 : 0
• page-in (0) : page fault 4번 발생, 가장 먼저 입장한 페이지 : 0
  ...
• page-in (1) : page fault 15번 발생, 가장 먼저 입장한 페이지: 7

최종적으로 페이지 부재는 15번 발생했습니다. FIFO 방식은 가장 입장한 페이지를 우선적으로 page-out하기 때문에 이전에 page-out한 페이지가 다음에 이용된다고 하더라도 다시 page-in을 해야 하기 때문에 비효율적입니다.

Belady's Anomaly

FIFO를 사용했을때 프레임의 수(메모리 용량)이 증가하면 page fault 수가 줄어드는 것이 일반적이지만 하지만 특정 페이지 참조열에 대해서는 프레임 수가 증가해도 page fault가 오히려 증가하는 이상 현상을 Belady's Anomaly라고 합니다.

Optimal(OPT)

OPT는 페이지 교체 알고리즘 중 가장 최적의 알고리즘 입니다. Victim page를 선정할때 가장 오랫동안 사용되지 않을 페이지를 선택하는 방식이빈다.

프레임 개수 : 3 
page reference string : (7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1)

프레임에 현재 7, 0, 1 페이지가 적재되어 있다면 이 중 앞으로 가장 오랫동안 사용되지 않을 것 같은 페이지를 선택하는 방식입니다. 0은 가장 빨리 사용되고 1, 7 순서대로 사용되기 때문에 7을 page-out 시킵니다.

매우 효율적인 알고리즘 처럼 보이지만 마치 CPU scheduling의 SJF와 마찬가지로 미래를 알 수 없어 비현실적(Unrealistic)하다는 단점이 있습니다.

Least-Recently-Used(LRU)

Optimal 방식은 최적의 page fault를 구할 수 있지만 비현실적이므로 근사값을 구해서 사용하는 알고리즘이 LRU입니다.

LRU는 최근에 사용되지 않았다면 미래에도 사용되지 않을 것이라는 가정을 따르는 알고리즘 입니다. 따라서 과거의 페이지 기록을 통해 victim page를 선택하는 방식입니다. 대부분의 컴퓨터는 LRU 방식을 사용합니다.

Global vs. Local Replacement

Global replacement

다중 프로그래밍 환경에서 메모리에 적재되어 있는 여러 페이지 중 모든 프로세스의 페이지에 대해서 Victim page를 선택하는 방식을 말합니다.

Local replacement

다중 프로그래밍 환경에서 메모리에 적재되어 있는 여러 페이지 중 자신의 프로세스의 페이지에 안에서 Victim page를 선택하는 방식을 말합니다.

성능 비교

일반적으로 Global replacement가 더 효율적입니다.

프레임 할당 (Allocation of Frames)

쓰레싱 (Thrashing)

• CPU utilization : CPU의 이용률

• Degree of multiprogramming : 메모리에 적재되어 있는 프로세스의 개수

메모리에 적재되어 있는 프로세스의 개수가 적다면 CPU는 그만큼 할 일이 적어질 것입니다. 반대로 프로세스 개수가 증가할 수록 CPU 이용률도 함께 증가할 것으로 예상할 수 있습니다.

하지만 요구 페이징을 사용하는 컴퓨터의 경우 어느 정도의 프로세스 개수가 증가한다면 CPU 이용률이 줄어드는 현상이 발생하는데 이 현상을 쓰레싱 (Thrashing)이라고 합니다.

메모리가 꽉 찰 만큼 페이지가 있지만 계속해서 프로세스가 증가한다면 많은 I/O(page-in/out) 작업으로 인해 CPU가 아무 일도 못하는 상황입니다.

쓰레싱을 극복할 수 있는 방법으로 Global 보다는 Local replacement 방식을 사용하는 것 입니다. 하지만 메모리 사용 효율이 떨어지는 단점이 있습니다. 다음으로 프로세스당 충분한/적절한 수의 프레임을 할당하는 방법이 있습니다.

정적 할당 (static allocation)

동일 할당 (Equal)

모든 프로세스에게 같은 수의 프레임을 할당하는 방식입니다. 이 방식은 프로세스의 크기가 전부 다르기 때문에 효율적이지 않습니다.

비례 할당 (Proportional)

프로세스 각각의 크기에 따라 비례하여 프레임을 할당하는 방식입니다. 하지만 프로세스 크기가 크더라도 실제로 사용하지 않는 기능이 많을 수 있기 때문에 효율적이지 않습니다.

동적 할당 (dynamic allocation)

Working set model

시간별로 CPU가 내는 주소에 관한 실험을 통해 어떠한 Locality 현상을 발견했습니다. 위의 그래프 처럼 하나의 프로세스를 특정 시간 별로 사용하고 있는 주소는 집단성을 띄고 있는 것을 확인할 수 있습니다. 그러므로 시간 별로 프로세스에게 할당 되어야 할 프레임 수를 할당할 수 있습니다.

하지만 시간별 Locality는 실제로 돌려보지 않는 이상 알 수 없기 때문에 이 문제를 극복하기 위해 나온 방법이 working set model 입니다.

working set model은 현재 시점에서 일정 과거 시간($\Delta$)안의 사용되었던 페이지의 집합을 사용하는 방법입니다. 여기서 일정한 과거 시간은 working window라고도 하며 프로그래머가 설정할 수 있는 변수이고 과거 페이지의 집합은 working set이라고 합니다.

현재 시점에서의 working set의 크기가 4개 이므로 현재 프로세스에 4개의 프레임을 할당해주는 방식으로 시간이 지나면 working set안의 페이지 개수를 달라질 수 있습니다.

PFF(Page-Fault Frequency)

어떤 프로세스에 대해서 프레임을 많이 할당하면 Page-Fault는 그만큼 줄어들게 됩니다. 운영체제는 프로스스의 page-fault를 기억해두고 상한선(upper bound)보다 page-fault가 더 발생하면 프레임을 더 할당하고, 하한선(lower bound)보다 더 적게 page-fault가 일어나면 프레임을 회수하는 방법입니다.

페이지 크기 (Page size)

페이지를 어떤 크기로 자를지도 중요한 문제입니다. 일반적으로 4KB기준으로 자르고 최대 4MB의 크기로 페이지를 자릅니다. 하드웨어가 발전함에 따라 페이지의 크기도 점차적으로 증가되어 왔습니다.

페이지 크기의 영향

내부 단편화

페이징 기법은 프로세스를 특정 크기로 자르기 때문에 프로세스의 총 크기가 페이지 크기의 배수가 아니라면 마지막 페이지는 메모리 낭비로 이어질 수 있습니다. 따라서 내부 단편화를 줄이기 위해서는 페이지 크기가 작은 것이 좋습니다.

Page-in/out의 시간

Page-in/out 소요시간에 가장 큰 비중을 차지하는 작업은 하드디스크에서 특정 페이지를 찾는(seek time)입니다. seek time을 줄이기 위해서는 페이지 크기가 큰 것이 좋습니다. 페이지 크기가 충분히 크다면 한번 탐색을 할 때 많은 양의 페이지를 읽고 쓸 수 있기 때문입니다.

페이지 테이블 크기

페이지 테이블은 프로세스가 몇 개의 페이지로 이루어져 있는지에 따라 결정됩니다. 따라서 페이지 크기가 클수록 더 작은 페이지 테이블을 사용하기 때문에 페이즈 크기가 클수록 좋습니다.

Memory resolution

Memory resolution(해상도)은 프로세스가 필요한 정보만 메모리에 있는 정도를 나타냅니다. 따라서 이 값이 크다면 메모리 낭비가 줄어든 상황이고 작다면 메모리 낭비가 일어나는 상황입니다. 이러한 측면에서 페이지 크기 크다면 불필요한 정보가 메모리에 적재되어 있을 수 있으므로 페이지 크기가 작을수록 좋습니다.

Page fault 발생 확률

Page fault가 적게 일어나려면 페이지 크기가 큰 것이 좋습니다.

기술 동향

페이지 테이블

페이징 시간에도 설명한것 처럼 페이지 테이블을 CPU, 메모리에 직접 저장하는 방식이 아닌 별도의 칩(Translation Lookaside Buffer 캐시)를 이용하는 방법을 사용합니다.

반도체 기술이 발전함에 따라 캐시메모리도 CPU의 내장형(on-chip)형태로 발전되어 왔고 마찬가지로 TLB도 on-chip 형태로 만들어지고 있습니다.