[OS] 08. 가상메모리

 운영체제는 메모리의 연장 공간으로 디스크의 스왑 영역을 사용한다. 그렇기 때문에 운영체제는 프로그램이 물리적 메모리를 고려할 필요 없이 자기 자신만이 메모리를 사용하는 것처럼 가정해 프로그램하는 것을 지원한다. 프로그램은 0번지부터 시작하는 자기 자신만의 메모리 주소 공간을 가정할 수 있는데, 이러한 메모리 공간을 가상메모리(virtual memory)라고 부른다. 

 즉 가상 메모리는 프로세스마다 각각 0번지부터의 주소 공간을 가지게 되며, 이들 공간 중 일부는 물리적 메모리에 적재되고 일부는 디스크의 스왑 영역에 존재하게 된다.

 

 프로세스의 주소 공간을 메모리로 적재하는 단위에 따라 가상메모리 기법은 요구 페이징 방식과 요구 세그먼테이션 방식으로 구현될 수 있다. 대부분의 경우는 요구 페이징 방식을 사용한다. 

 

 

1. 요구 페이징

- 프로그램 실행 시 프로세스를 구성하는 페이지 중 당장 사용될 페이지만을 메모리에 올리는 방식
- 특정 페이지에 대해 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재한다.

 

 요구 페이징을 사용했을 때의 장점은 다음과 같다.

• 당장 필요한 페이지만 메모리에 적재하기 때문에 메모리 사용량 감소
• 프로세스 전체를 올리는 데 소요되는 입출력 오버헤드가 줄어듦
• 사용되지 않을 주소 영역에 대한 입출력을 수행하지 않기 때문에 응답시간이 단축됨
• 더 많은 프로세스 수용 가능
• 물리적 메모리의 용량 제약이 없음

 

 가상 메모리 기법에서는 특정 프로세스의 어떤 페이지가 메모리에 존재하고 어떤 페이지가 메모리에 존재하지 않는지 구별하기 위한 방안이 필요한데, 요구 페이징에서는 이를 위해 유효-무효 비트를 두어 각 페이지가 메모리에 존재하는지를 표시한다. 이 비트는 페이지 테이블의 각 항목별로 저장된다. 

 

페이지 테이블에서 유효-무효 비트의 의미

 

 처음에는 무효값으로 초기화되어 있지만, 페이지가 메모리에 적재되는 경우 유효값으로 바뀌게 되고 이후 다시 디스크로 스왑 아웃 될 경우 무효값으로 바뀌게 된다. 무효인 경우는 페이지가 현재 메모리에 없는 경우일 뿐만 아니라 그 페이지가 속한 주소 영역을 프로세스가 사용하지 않는 경우도 존재한다.

 이와 같이 유효-무효 비트가 무효값으로 세팅되어 있는 경우를 '페이지 부재(page fault)'가 일어났다고 말한다. 

 

1) 요구 페이징의 페이지 부재 처리

페이지 부재를 처리하는 과정

• CPU가 무효 페이지에 접근하면 MMU가 페이지 부재 트랩을 발생시킨다.
• CPU의 제어권이 커널모드로 전환되고, 운영체제의 페이지 부재 처리루틴이 호출된다.
• 운영체제는 먼저 페이지에 대한 접근이 적법한지를 체크한다. 사용되지 않는 주소 영역에 속한 페이지에 접근하려 했거나 접근 권한을 위반했을 경우 해당 프로세스를 종료시킨다.
• 접근이 적법할 경우 물리적 메모리에서 비어 있는 프레임을 할당받아 그 공간에 해당 페이지를 읽어온다. 비어 있는 프레임이 없다면 스왑 아웃을 한다.
• 페이지를 메모리에 적재하기까지 오랜 시간이 소요되므로 페이지 부재를 발생시킨 프로세스는 CPU를 빼앗기고 봉쇄 상태가 된다.
• 디스크 입출력이 완료됐을 경우 해당 페이지의 유효-무효 비트를 유효로 설정하고, 봉쇄되었던 프로세스를 준비 큐로 이동시킨다. 프로세스가 다시 CPU를 할당받으면 PCB에 저장해두었던 값을 복원시켜 이전에 중단되었던 명령부터 실행을 재개한다.

 

2) 요구 페이징의 성능

 요구 페이징 기법의 성능에 가장 큰 영향을 미치는 요소는 페이지 부재의 발생 빈도이다. 페이지 부재가 적게 발생할수록 요구 페이징의 성능은 향상될 수 있다. 페이지 부재가 일어나지 않는 경우는 페이지가 이미 메모리에 적재되어 있는 것이므로 메모리에 접근하는 시간만이 소요된다.

 

 페이지 부재가 일어나면 많은 오버헤드가 필요하다. 

• 메모리에 빈 프레임이 없을 경우 올라와 있는 페이지 중 하나의 페이지를 선택해 스왑 아웃해야 한다.
• 페이지를 다 읽어왔을 경우 인터럽트를 통해 프로세스를 준비 상태로 변경하고 자신의 차례가 되면 문맥교환이 필요
• 이러한 과정에서 디스크 입출력과 각종 오버헤드가 포함되어 시간이 오래 걸린다.

 

2. 페이지 교체

메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하는 작업

 

 

페이지 교체의 예

 페이지 교체를 할 때 어떠한 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘을 교체 알고리즘이라고 하는데, 이 알고리즘의 목표는 페이지 부재율을 최소화하는 것이다. 그러므로 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택해서 내쫓는 것이 성능을 향상시킬 수 있는 방안이다.

 

 

1) 최적 페이지 교체

 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내는 방법

 

• 빌레디의 최적 알고리즘(Belady's optimal algorithm)이라고 부른다.
• 페이지를 교체할 때 가장 먼 미래에 참조될 페이지를 선정하여 스왑 아웃한다.
• 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고있다는 전제하에 알고리즘을 운영하므로 실제 사용할 수 있는 알고리즘은 아니다.
• 다른 알고리즘의 성능에 대한 상한선을 제공한다.

 

 아래 그림은 페이지 참조열이 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 일 때 알고리즘이 동작하는 방식을 나타낸다.

최적 페이지 교체 알고리즘을 사용한 페이지 교체

 

2) 선입선출 알고리즘 (FIFO, First In First Out)

페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는 방법

 

• 페이지의 향후 참조 가능성을 고려하지 않기 때문에 비효율적인 상황이 발생할 수 있다. 
• 페이지 프레임을 늘리더라도 페이지 부재가 더 많이 발생할 수 있다. 이러한 상황을 FIFO의 이상 현상(FIFO anomaly)이라고 부른다. 
• 다음에 나올 LRU 알고리즘에서는 이상 현상이 발생하지 않는다.

 

 아래 그림은 페이지 참조열이 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5이며 메모리 프레임이 3개일 때와 4개일 때 FIFO 알고리즘이 운영되는 예를 나타낸다.

FIFO 알고리즘에 의한 페이지 교체

 

3) LRU 알고리즘 (Least Recently Used)

- 페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 쫓아내는 방법
- 즉, 마지막 참조 시점이 가장 오래된 페이지를 교체하는 방법을 말한다.

 

• 페이지 교체 알고리즘의 성능 향상을 위해서는 향후 사용될 가능성이 낮은 페이지를 우선적으로 메모리에서 쫓아내는 것이 바람직하다.
• 페이지의 참조 성향 중 중요한 한 가지 성질로 시간지역성(temporal locality)이 있다. 이는 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질을 의미한다.
• LRU 알고리즘은 이와 같은 성질을 활용하는 방법이다.

 

 아래 그림은 물리적 메모리의 페이지 프레임이 4개일 때 페이지 참조열이 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5에 대해 LRU 알고리즘을 적용하는 경우를 나타낸다.

LRU 알고리즘을 적용한 경우의 페이지 교체

 

4) LFU 알고리즘 (Least Frequently Used)

과거에 참조 횟수가 가장 적었던 페이지를 쫓아내고 그 자리에 새로 참조될 페이지를 적재하는 방법

 

• 페이지의 참조 횟수로 교체시킬 페이지를 결정하는 방법이다.
• 최저 참조 횟수를 가진 페이지가 여러 개일 경우 임의로 하나를 선정하는데, 이때 상대적으로 더 오래전에 참조된 페이지를 쫓아내는 것이 더 효율적이다.
• LFU 알고리즘은 LRU 알고리즘보다 오랜 시간 동안의 참조 기록을 반영할 수 있다는 장점이 있다. 
• 하지만 시간에 따른 페이지 참조의 변화를 반영하지 못하고, LRU보다 구현이 복잡하다는 단점이 있다. 

 

5) 클럭 알고리즘

하드웨어적인 지원을 통해 오랫동안 참조되지 않은 페이지 중 하나를 교체하는 알고리즘.

 

• 하드웨어적인 지원을 통해 LRU, LFU등과 같은 소프트웨어적 알고리즘의 운영 오버헤드를 줄인 방식
• LRU를 근사(approximation)시킨 알고리즘으로 NUR(Not Used Recently) 또는 NRU(Not Recently Used) 알고리즘이라고도 부른다.
• LRU와 유사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못한다.
• 하지만 하드웨어적 지원으로 인해 LRU에 비해 페이지의 관리가 훨씬 빠르고 효율적으로 이루어진다. 
• 교체할 페이지를 선정하기 위해 페이지 프레임들의 참조비트(reference bit)를 순차적으로 조사한다. 
• 참조비트는 각 프레임마다 하나씩 존재하며 그 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅된다.
• 참조비트가 1인 페이지는 0으로 바꾼 후 지나가고 참조비트가 0인 페이지는 교체한다. 
• 시곗바늘이 한 바퀴 도는 동안 다시 참조되지 않은 페이지를 교체한다. 

클럭 알고리즘

 

3. 페이지 프레임의 할당 

 프로세스 여러 개가 동시에 수행되는 상황에서는 각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인지 결정해야 한다. 이를 위해서 메모리를 할당 하는 알고리즘들이 존재한다.

 

① 균등할당(equal allocation) 방식

• 모든 프로세스에게 페이지 프레임을 균일하게 할당하는 방식

 

② 비례할당(proportional allocation) 방식 

• 프로세스의 크기에 비례해 페이지 프레임을 할당하는 방식
• 프로세스의 크기가 모두 균일하지 않다는 점에 착안한 방식으로 프로세스의 크기를 고려한 균등할당 방식으로 볼 수 있다.

 

③ 우선순위 할당(priority allocation) 방식 

• 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당하는 방식 
• 당장 CPU에서 실행될 프로세스와 그렇지 않은 프로세스를 구분하여 전자 쪽에 더 많은 페이지 프레임을 할당하는 방식 

 

 하지만 위와 같은 할당 알고리즘만으로는 프로세스의 페이지 참조 특성을 제대로 반영하지 못할 우려가 있다. 명령을 실행할 때 프로세스의 주소 공간 중 스택, 데이터 등 각기 다른 영역을 참조하기 때문에 일반적으로 여러 페이지를 동시에 참조하게 된다. 따라서 프로세스를 정상적으로 수행하기 위해서는 적어도 일정 수준 이상의 페이지 프레임을 각 프로세스에 할당해야 한다. 

 

 

4. 전역교체와 지역교체 

 교체할 페이지를 선정할 때, 교체 대상이 될 프레임의 범위를 어떻게 정할지에 따라 교체 방법을 전역교체와 지역교체로 구분할 수 있다.

 

전역교체(global replacement)

• 모든 페이지 프레임이 교체 대상이 될 수 있는 방법
• 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법이다. 
• 페이지 교체 시 다른 프로세스에 할당된 프레임을 빼앗아올 수 있는 방식이다.

 

지역교체(local replacement)

• 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법 
• 프로세스마다 페이지 프레임을 미리 할당하는 것을 전제로 한다. 
• 해당 프로세스에게 할당된 프레임 내에서만 페이지를 교체할 수 있다. 

 

5. 스레싱

 프로세스가 원활하게 수행되기 위해서는 일정 수준 이상의 페이지 프레임을 할당받아야 한다. 그렇지 못할 경우 성능상의 심각한 문제가 발생할 수 있다. 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못하면 페이지 부재율(page fault rate)이 크게 상승해 CPU 이용률(CPU utilization)이 급격히 떨어질 수 있기 때문이다. 이와 같은 현상을 스레싱(thrashing)이라고 한다.

 

 CPU 이용률이 낮다는 것은 준비 큐가 비는 경우가 발생한다는 뜻이다. CPU 이용률이 낮으면 운영체제는 메모리에 올라가는 프로세스의 수를 늘리게 된다. 메모리에 동시에 올라가 있는 프로세스의 수를 다중 프로그래밍의 정도(Multi-Programming Degree: MPD)라고 부르는데 MPD가 과도하게 높아지면 각 프로세스에게 할당되는 메모리의 양이 지나치게 감소하게 된다. 이럴 경우 페이지 부재가 빈번히 발생하게 된다. 

 빈번히 발생하는 페이지 부재로 인해 운영체제는 또 다시 메모리에 올라와 있는 프로세스의 수가 적어 이러한 현상이 발생했다고 판단하고, 다시 MPD를 높이기 위해 또 다른 프로세스를 메모리에 추가하게 된다. 그러나 이로 인해 프로세스상 할당된 프레임의 수가 더욱 감소하고 페이지 부재가 더욱 빈번히 발생하게 된다. 

 이렇게 프로세스들은 서로의 페이지를 교체하며 스왑 인과 스왑 아웃을 지속적으로 발생시키고, CPU는 대부분의 시간에 일을 하지 않게 된다. 이러한 상황을 스레싱이라고 부르게 되는 것이다. 

 

 

스레싱이 발생하는 경우

 

 일반적으로 MPD를 높이면 CPU 이용률은 증가하게 된다.하지만 어느 한계를 넘어서면 위의 그림과 같이 CPU 이용률은 급격히 떨어지게 된다. MPD를 적절히 조절해 CPU 이용률을 높이는 동시에 스레싱 발생을 방지하는 방법으로 워킹셋 알고리즘과 페이지 부재 빈도 알고리즘이 있다.

 

1) 워킹셋 알고리즘 (working-set algorithm)

- 워킹셋 : 프로세스가 일정 시간 동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합
- 워킹셋이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘이다.

 

• 프로세스는 일정 시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있는데, 이렇게 집중적으로 참조되는 페이지들의 집합을 지역성 집합(locality set)이라고 한다.
• 워킹셋 알고리즘은 이러한 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘이다.
• 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당한다. 
• 그렇지 않으면 프로세스에게 할당된 페이지 프레임들을 모두 반납시킨 후 그 프로세스의 주소 공간 전체를 디스크로 스왑 아웃 시킨다.
• 이와 같은 방법으로 MPD를 조절하고 스레싱을 방지한다.

 

2) 페이지 부재 빈도 알고리즘 (page-fault frequency scheme)

프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절하는 방식

 

• 시스템에서 미리 정해놓은 상한값과 하한값이 존재한다.
• 어떤 프로세스의 페이지 부재율이 상한값을 넘게 되면 이 프로세스에 할당된 프레임의 수가 부족하다고 판단하여 이 프로세스에게 프레임을 추가로 더 할당한다. 빈 프레임이 없다면 일부 프로세스를 스왑 아웃시켜 메모리에 올라가 있는 프로세스의 수를 조절한다.
• 페이지 부재율이 하한값 이하로 떨어지면 이 프로세스에게 필요 이상으로 많은 프레임이 할당된 것으로 간주해 할당된 프레임의 수를 줄인다. 
• 모든 프로세스에 필요한 프레임을 다 할당한 후에도 프레임이 남는 경우 스왑 아웃되었던 프로세스에게 프레임을 할당함으로써 MPD를 높인다. 

페이지 부재 빈도 알고리즘 

 

Reference 

운영체제와 정보기술의 원리 - 교보문고