가상 메모리는 물리 메모리 크기의 한계를 극복하기 위해 나온 기술이다. 즉, 물리 메모리보다 큰 프로세스를 수행하기 위해 가상 메모리를 사용한다. 예를 들어, 100MB 메모리 크기에서 200MB 크기의 프로세스를 수행할 수 있도록 하는 것이다.
이러한 방식이 어떻게 가능할까? 앞서 메모리 낭비 방지의 동적 할당에서도 봤듯이, 필요한 부분만 메모리에 적재하는 것이다. 프로세스를 실행할 때, 실행에 필요한 부분만 메모리에 올리는 것이다. 이러한 프로세스의 일부분은 페이지 단위일 수도 있고, 세그먼트 단위일 수도 있지만 현재 대부분은 페이지 단위를 사용한다. 이처럼 현재 필요한(요구되어지는) 페이지만 메모리에 올리는 것을 Demanding Paging(요구 페이징) 이라고 한다.
1. Demanding Paging
위 그림은 요구 페이징의 모습이다. 두 프로세스 P1, P2는 각각 필요한 페이지만 메모리에 할당하였다. 여기서 위 그림의 테이블은 P1이 수행 중일 때의 페이지 테이블이다. 기존의 페이지 테이블과 다른 점은 valid bit 가 추가되었다. 이는 현재 메모리에 페이지가 있는지 없는지를 나타내는 비트이다. 현재 페이지가 메모리에 있다면 1, 없다면 0값을 갖는다.
만약, CPU에서 P1의 3번째 페이지에 접근하는데, valid bit값이 0이다. 그러면 CPU에 인터럽트 신호를 발생하여 운영체제 내부의 ISR로 점프한다. 여기서 디스크 내부의 프로세스 P1에 있는 2번째 페이지를 메모리에 할당하는 작업을 처리한다.
위 그림은 P1의 3번째 페이지를 메모리에 올린 후 모습이다.
가상 메모리를 만드는 방법은 대표적으로 두 가지가 존재하지만, 대부분 요구 페이징을 사용하므로 가상 메모리와 요구 페이징을 같은 용어로 사용하는 경우가 많다.
1.2. Page Fault(페이지 부재)
페이지 부재는 위에서 살펴본 CPU가 접근하려는 페이지가 메모리에 없는 경우이다. 즉, 페이지 테이블의 valid bit값이 0인 경우이다.
위 그림은 page fault가 발생했을 때 처리하는 과정을 나타낸 것이다.
1. 해당 페이지가 메모리에 있는지 valid bit를 확인한다.
2. valid bit가 0이라면 CPU에 인터럽트 신호를 보내어 운영체제 내부 해당 ISR로 점프한다.
3. 해당 ISR에서 backing store(디스크)를 탐색하여 해당 프로세스의 페이지를 찾는다.
4. 해당 페이지를 비어있는 프레임에 할당한다.
5. 페이지 테이블을 갱신한다.(프레임 번호 설정, valid bit 1로 변경)
6. 다시 명령어로 돌아가서 실행한다.
1.2.1. Pure Demanding Paging
Pure Demanding Paging은 프로세스가 최초로 실행될 때는 어떤 페이지가 필요한지 알 수 없으므로, 아무 페이지도 올리지 않는다. 그러므로 프로그램을 실행하자마자 page fault가 발생한다. 즉, 순수하게 필요한 페이지만 올리는 것을 말한다. Pure Demanding Paging의 장점은 메모리를 최대한 효율적으로 사용할 수 있다. 하지만 시작부터 page fault가 발생하므로 속도면에서 느리다.
1.2.2. Prepaging
Prepaging은 pure demanding paging과 반대대는 개념이다. 프로그램을 실행할 때 필요할 것이라 판단되는 페이지를 미리 올리는 것이다. 이것의 장점은 page fault가 발생할 확률이 적으므로 속도면에서 빠르지만, 단점으로 미리 올라간 페이지를 사용하지 않는다면 메모리가 낭비된다.
1.2.3. Swapping VS Demanding Paging
Swapping와 Demanding Paging의 공통점은 둘 다 메모리와 backing store 사이를 서로 오고 가는 기능을 수행하지만, Swapping은 프로세스 단위로 이동하고 Demanding Paging은 페이지 단위로 이동하는 차이점이 있다.
1.2.4. 유효 접근 시간(Effective Access Time)
Demending Paing은 페이지 테이블에 해당 페이지가 없으면 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,800 * 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과 같은 것을 사용하는 방법이 있다.
1.2. 페이지 교체(Page Replacement)
Demanding Paging은 요구되어지는 페이지만 backing store에서 가져온다. 하지만 프로그램들이 계속 실행함에 따라 요구 페이지도 계속 늘어나고, 언젠가는 메모리가 가득 차게 될 것이다.(memory full) 여기서 다른 프로그램이 새로 실행되거나 실행중인 프로세스가 다른 페이지를 요구한다면 이미 메모리에 있는 페이지 중 하나를 다시 backing store에 보내고(page-out), 새로운 페이지를 메모리에 올려야한다.(page-in) 이를 페이지 교체라고 한다. 여기서 backing store로 page-out이 된 페이지를 victim page 라고 한다.
1.2.1. Victim Page(희생양 페이지)
희생양 페이지는 어떤 페이지로 하는 것이 좋을까? 먼저 생각할 수 있는 것은 메모리에 올라가 있는 페이지 중 CPU에 수정(modify)되지 않는 페이지를 고르는 것이 효율적으로 보인다. 수정되지 않은 페이지는 page-out이 될 때 backing store에 쓰기(write) 연산을 할 필요가 없기 때문이다. backing store는 읽는 시간도 느리지만, 거기에 더해 쓰기 작업까지 한다면 더욱 비효율적일 것이다.
그러면 해당 페이지가 수정되었는지 안되었는지를 판단할 수 있어야 하는데, 이를 위해 페이지 테이블에 modified bit(=dirty bit)를 추가하여 이를 검사한다. 해당 페이지가 수정되었다면 이 비트를 1로 두고, 수정되지 않으면 0으로 둔다. 이를 이용해서 victim page는 최대한 수정되지 않은 페이지를 선택한다.
위 그림은 modified bit를 추가한 페이지 테이블의 모습이다. 여기서 수정되지 않은 페이지는 0, 2, 3번 3개의 페이지가 존재하는데 이 중에서는 어떤 페이지를 선택해야 할까?
제일 간단한 방법은 랜덤하게 선택하는 것이지만, 이는 성능을 보장할 수 없다. 그 다음은 가장 먼저 메모리에 올라온 페이지를 희생양 페이지로 선택하는 것이다. 이는 아주 유명한 FIFO(First-In First-Out) 방식이다. 이 외에도 여러가지 방법이 존재한다.
Reference
