[OS] 가상메모리

가상 메모리는 물리 메모리 크기 한계를 극복하기 위해 나온 기술이다. 물리 메모리보다 큰 프로세스를 수행하기 위해 가상 메모리를 사용한다. 예를 들어 100MB의 메모리에서 200MB의 프로세스를 수행할 수 있도록 하는 것이다.

 

앞서 메모리 낭비 방지의 동적 할당에서도 봤듯이, 필요한 부분만 메모리에 적재하는 것이다. 프로세스를 실행할 때, 실행에 필요한 부분만 메모리에 올리는 것이다. 이러한 프로세스의 일부분은 페이지 단위일 수도 있고, 세그먼트 단위일 수도 있지만 현재 대부분은 페이지 단위를 사용한다. 이처럼 현재 필요한 페이지만 메모리에 올리는 것을 Demanding Paging(요구 페이징)이라고 한다.

 

Demanding Paging

위 그림은 요구 페이징의 그림이다. 두 프로세스 P1, P2는 각각 필요한 페이지만 메모리에 할당했다. 여기서 위 그림의 테이블은 P1이 수행중일 때의 페이지 테이블이다. 기존의 페이지 테이블과 다른 점은 Valid bit가 추가되었다. 이는 현재 메모리에 페이지가 있는지 없는지를 나타내는 비트이다. 현재 페이지에 메모리가 있다면 1, 없다면 0이다.

 

만약 CPU 에서 P1의 3번째 페이지에 접근하는데 Valid bit 값이 0이면 CPU에 인터럽트 신호를 발생하여 운영체제 내부의 ISR로 점프한다. 여기서 디스크 내부의 프로세스 P1에 있는 2번째 페이지를 메모리에 할당하는 작업을 처리한다.

위 그림은 P1의 3번째 페이지를 메모리에 올린 후 모습이다. 가상 메모리를 만드는 방법은 대표적으로 두 가지가 존재하나, 대부분 요구 페이징을 사용하므로 가상 메모리와 요구 페이징을 같은 용어로 사용하는 경우가 많다.

 

Page Fault(페이지 부재)

페이지 부재는 위에서 살펴본 CPU가 접근하려는 페이지가 메모리에 없는 경우이다. 즉 페이지 테이블의 Valid bit 값이 0인 경우다.

위 그림은 페이지 부재가 발생했을 때 처리 과정이다.

1. 해당 페이지가 메모리에 있는지 Valid bit를 확인한다.
2. Valid bit가 0이면 CPU에 인터럽트 신호를 보내 운영체제 내부 해당 ISR로 점프한다.
3. 해당 ISR에서 backing store(디스크)를 탐색하여 해당 프로세스의 페이지를 찾는다.
4. 해당 페이지를 비어있는 프레임에 할당한다.
5. 페이지 테이블을 갱신한다. (프레임 번호 설정, Valid bit 1로 변경)
6. 다시 명령어로 돌아가 실행한다.

Pure Demanding Paging

Pure Demanding Paging은 프로세스가 최초로 실행될 때는 어떤 페이지가 필요한지 알 수 없으므로, 아무 페이지도 올리지 않는다. 그러므로 프로그램을 실행하자마자 Page Fault(이하 페이지 부재)가 발생한다. 즉, 순수하게 필요한 페이지만 올리는 것을 말한다. Pure Demanding Paging의 장점은 메모리를 최대한 효율적으로 사용할 수 있다는 점이다. 하지만 시작부터 페이지 부재가 발생하여 속도면에서 느리다.

 

Prepaging

Prepaging은 Pure Demanding Paging과는 반대되는 개념이다. 프로그램을 실행할 때 필요할 것이라 판단되는 페이지를 미리 올리는 것이다. 이러한 방식으로 페이지 부재가 발생할 확률이 적어 속도면에서는 빠르지만 단점으로는 미리 올라간 페이지를 사용하지 않으면 메모리 낭비가 된다는 점이 있다.

 

Swapping vs Demanding Paging

Swapping과 Demanding Paging의 공통점은 둘 다 메모리와 backing store 사이를 서로 오고 가는 기능을 수행하지만 Swapping은 프로세스 단위로 이동하고 Demanding Paging은 페이지 단위로 이동하는 차이점이 있다.

 

유효 접근 시간(Effective Access Time)

Demanding Paging은 페이지 테이블에 해당 페이지가 없으면 backing store에서 메모리로 가져오는 과정이 있어 페이지 테이블에 해당 페이지가 있을 때와 없을 때가 시간 차이가 발생하게 된다. 이러한 시간 차이를 고려해 평균적으로 어느 정도 소요되는지 계산하는 것을 유효 접근 시간이라고 한다.

• p : 페이지 부재 확률(probability of a page fault = page fault rate)
• Tm : 메모리를 읽는 시간
• Tp : Page fault가 발생했을 때 소요되는 시간(대부분 backing store(하드디스크)를 읽는 시간이 차지한다.)
• T = (1 - p)Tm + pTp

예시)

• Tm = 200nsec (DRAM)
• Tp = 8msec (seek time + rotational delay + transfer time)
• T = (1 - p) 200 + p 8,000,000 = 200 + 7,999,8000 * p
• p = 1/1,000 => T = 8.2usec (40배 정도 느림)
• p = 1/399,990 => T = 220nsec (10% 정도 느림)

위의 예시를 보면 page fault는 발생 확률이 낮을 수록 효율적이다. 페이지 부재는 지역성의 원리(Locality of reference)로 인해 매우 낮다. 지역성의 원리는 '메모리 접근은 시간적 지연성과 공간적 지역성을 가진다'는 의미이다.

 

• 시간적 지연성 : CPU는 어느 메모리 공간을 읽은 후에 시간이 지나도 그 공간을 다시 읽을 확률이 매우 높다는 것을 의미. 대표적인 예로 반복문이 있다. 반복문은 하나의 코드 공간을 여러번 읽는다.
• 공간적 지연성 : CPU가 메모리 공간을 읽을 때는 인접한 범위 내에서 읽는다는 의미. 프로그램은 대부분 절차적인 순서로 구현되어 순서대로 읽는 경우가 빈번하다.

이와 같이 페이지 부재가 현실적으로 발생할 확률은 매우 낮으므로 예제와 같이 40배로 느려지는 일은 거의 없다. 여기서 더 효율적으로 사용하기 위해서는 페이지 부재가 발생했을 때 소요되는 시간을 줄일 수 있는데 backing store로 HDD보다는 더욱 빠르게 동작하는 SSD나 저가형 DRAM과 같은 것을 사용하는 방법이 있다.

 

페이지 교체(Page Replacement)

Demanding paging은 요구된 페이지만 backing store에서 가져온다. 하지만 프로그램들이 계속 실행됨에 따라 요구 페이지도 계속 늘어나고, 언젠가는 메모리가 가득차게 될 것이다. 다른 프로그램이 새로 실행되거나 실행중인 프로세스가 다른 페이지를 요구한다면 이미 메모리에 있는 페이지 중 하나를 다시 backing store에 보내고(page-out), 새로운 페이지를 메모리에 올려야 한다.(page-in) 이를 페이지 교체라고 한다. 여기서 backing store로 page-out된 페이지를 victim page라고 한다.

 

Victim Page

희생양 페이지를 선정할 때, 메모리에 올라가 있는 페이지 중 CPU에 수정되지 않는 페이지를 고르는 것이 효율적으로 보인다. 수정되지 않는 페이지는 page-out이 될 때, backing store에 쓰기 연산을 할 필요가 없기 때문이다. backing store는 읽는 시간도 느리지만 거기에 쓰기 연산까지 진행된다면 더욱 비효율적일 수 밖에 없다.

 

이러한 동작을 위해 페이지 테이블에 modified bit(=dirty bit)을 추가하여 검사한다. 해당 페이지가 수정되면 이 비트를 1로 두고 아니면 0으로 둔다. 이를 사용하여 victim page는 최대한 수정되지 않은 페이지를 선택한다.

 

위 그림은 modified bit를 추가한 페이지 테이블의 모습이다. 여기서 수정되지 않은 페이지는 0, 2, 3번 3개의 페이지이다. 이 중 어떤 페이지를 선택해야 할까? 가장 간단한 것은 랜덤 선택이지만 이는 성능을 보장할 수 없다. 그 다음은 가장 메모리에 올라온 페이지를 선택하는 것이다. 이는 FIFO 방식이다. 이외에도 여러가지 방법이 존재한다.

 

페이지 교체 알고리즘

FIFO(First In First Out)

• FIFO는 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘.
• 구현이 간단하나 성능은 좋지 못하다.
• 들어온 시간을 저장하거나 올라온 순서 큐를 이용해 저장한다.
• Belady's Anomaly 현상이 발생할 수 있다.

Belady's Anomaly 현상이란 프레임 개수가 많아져도 page-fault가 줄어들지 않고 늘어나는 현상을 말한다. 직관적으로 프레임이 많아진다면 page-fault가 줄어들어야 하지만 FIFO는 그렇지 않을 수 있다.

 

OPT(Optimal)

• OPT 알고리즘은 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘.
• 모든 페이지 교체 알고리즘 중 page-fault가 발생할 확률이 가장 적다.
• Belady's Anomaly 현상이 발생하지 않는다.
• 프로세스가 앞으로 사용할 페이지를 미리 알아야한다.
• 실제로 구현하기는 거의 불가능한 알고리즘이다.
• 그래서 실사용보단 연구 목적으로 사용된다.

LRU(Least Recently Used)

 

• LRU 알고리즘은 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘.
• 최적 알고리즘과 비슷한 효과를 낼 수 있다.
• 성능이 좋은 편.
• 많은 운영체제가 채택한 알고리즘. 

LFU(Least Frequently Used)

 

• LFU는 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘
• 교체 대상이 여러개라면 가장 오랫동안 사용하지 않은 페이지를 교체

MFU(Most Frequently Used)

 

 

• MFU는 LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘