메모리 관리 기법 - 페이징 기법

페이징 기법

페이징 기법은 논리적 메모리를 동일 크기의 페이지로 나누고, 물리적 메모리도 페이지와 동일 크기의 페이지 프레임으로 나눈다.

• 장점
  • 프로세스의 논리적 주소 공간과 물리적 메모리 공간이 모두 같은 크기의 페이지/프레임 단위로 나누어지기 때문에 외부 조각이 발생하지 않는다. 
• 단점 
  • 프로그램의 크기가 항상 페이지 크기로 정확히 나누어 떨어지지 않을 수 있기 때문에 프로세스의 논리적 주소 공간 중 제일 마지막에 위치한 페이지에서는 물리적으로 내부조각이 발생할 수 있다.
  • 페이징 기법은 하나의 프로세스라 하더라도 페이지 단위로 물리적 메모리에 올리는 위치가 상이하다. 따라서 주소 바인딩 작업이 페이지 단위로 이루어지기 때문에 주소 바인딩 과정이 연속할당 방식에 비해 복잡하다. 

페이지 테이블

하나의 프로세스에는 여러 개의 페이지가 있고, 이들은 물리적 메모리 공간에 불연속적으로 위치한다. 따라서 가상 메모리의 특정 페이지가 물리적 메모리의 몇 번째 프레임에 들어 있다는 페이지별 물리적 주소 변환 정보를 갖고 있어야 한다. 이것이 페이지 테이블이다. 즉, 페이지 테이블은 가상 주소를 물리 주소로 매핑할 때 필요한 정보이다.

• 각 프로세스마다 페이지 테이블을 가지며, 페이지 테이블은 운영체제 커널의 주소 공간에 위치한다.
• 페이지 테이블 베이스 레지스터: CPU 내부에 존재하는 하드웨어 구성 요소 중 하나로, 현재 실행 중인 프로세스의 페이지 테이블 시작 위치 주소를 저장하고 있다. 따라서 CPU는 페이지 테이블 베이스 레지스터에 저장된 페이지 테이블 주소를 사용하여, 현재 실행 중인 프로세스의 페이지 테이블을 참조한다. 그리고 문맥 교환이 일어날 때 운영체제는 다음에 실행되는 프로세스의 페이지 테이블 주소 값으로 페이지 테이블 베이스 레지스터를 업데이트한다.
• MMU(Memory Management Unit): CPU 내부에 존재하는 하드웨어 구성 요소 중 하나로, 페이지 테이블을 사용하여 논리 주소를 물리 주소로 변환하는 역할을 한다. 

페이지 테이블은 다음과 같이 프로세스가 가질 수 있는 페이지 개수만큼 주소 변환 엔트리를 가지고 있으며, 페이지의 논리 주소가 페이지 테이블의 인덱스 번호가 된다. 따라서 페이지 테이블에서 엔트리를 찾는 시간은 O(1)이다. (배열이 아닌 트리로 구현되어 있는 경우도 있는데, 이 경우에는 O(logN)의 시간 복잡도를 갖는다.)

TLB(Translation Lookaside Buffer)

CPU가 프로세스를 실행할 때 논리 주소와 물리 주소를 매핑하기 위해 페이지 테이블을 참조하고, 이를 통해 얻은 물리 주소를 참조한다. 즉, 페이지 테이블, 물리 주소 총 2번의 메모리 접근이 일어난다. 따라서 CPU가 매번 두 번씩 메모리에 접근하는 것을 막기 위해 페이지 테이블의 일부를 캐시 메모리에 저장해둔다. 이 공간을 TLB라고 한다.

 

TLB는 CPU 내의 MMU에 포함되어 있는 하드웨어 캐시이다. 따라서 CPU가 메모리에 있는 페이지 테이블에 접근하는 것보다 더 빠르게 접근할 수 있다. CPU는 TLB를 먼저 확인하여, TLB에 캐시되어 있는 경우 페이지 테이블을 확인하지 않는다. 즉, 캐시를 통해 2번 메모리에 접근하던 것이 1번만 접근할 수 있게 된다. 

 

그리고 TLB에서 데이터를 찾을 때는 병렬적으로 수행되어 O(1)의 시간 복잡도를 갖는다. 이것이 가능한 이유는 TLB가 연관 메모리로 구현되어 있기 때문이다. 다음과 같이 논리 주소인 p를 기준으로, 페이지 번호 p를 갖는 엔트리가 있는지 병렬적으로 찾는다.

즉, CPU의 프로세스 실행 과정은 다음과 같다.

1. CPU는 프로세스를 실행시키기 위해 논리 주소에 따른 물리 주소를 알아내야 한다. 
2. MMU는 TLB에 찾고자 하는 논리 주소가 있는지 확인한다.
3. 있으면 해당 물리 주소에 접근하고, 없으면 페이지 테이블 베이스 레지스터를 참조하여 페이지 테이블을 참조한다.
4. 페이지 테이블에 찾고자 하는 논리 주소가 있는지 확인한다.

요구 페이징

페이징 기법은 요구 페이징 기법을 사용한다. 요구 페이징은 당장 수행해야 할 부분만 메모리에 올려놓고 그렇지 않은 부분은 디스크의 스왑 영역에 내려놓았다가 필요해지면 메모리에 올라가 있는 부분과 교체하는 방식이다. 이러한 요구 페이징은 가상메모리 시스템에서 사용된다. 

 

프로그램이 실행되기 위해 그 프로세스의 주소 공간 전체가 메모리에 올라와 있어야 할 필요는 없다. 예를 들어 사용자가 여러 옵션 중 선택하는 로직의 경우, 선택 여부에 따라 실행되지 않는 코드가 있을 수 있으며, 예외 처리 코드도 마찬가지이다.

 

이를 통한 이점은 다음과 같다.

• 메모리 사용량 감소: 당장 필요한 페이지만 메모리에 올리기 때문에 메모리 사용량이 감소한다.
• 더 많은 프로세스 수용: 한 프로세스의 메모리 사용량이 감소하므로 시스템이 더 많은 프로세스를 수용할 수 있다. 
• 메모리 용량보다 큰 프로그램도 실행 가능: 프로그램을 구성하는 페이지 중 일부만 메모리에 적재하므로 물리적 메모리의 용량보다 큰 프로그램도 실행이 가능하다.
• I/O 감소: 빈번하게 사용되는 코드가 메모리에 올라가기 때문에 디스크 I/O의 수가 줄어든다.

유효-무효 비트 값

요구 페이징 기법을 사용하면 프로세스의 모든 페이지가 물리적 메모리에 올라가 있지 않다. 따라서 프로세스를 구성하는 페이지 중에서 어떤 페이지가 메모리에 존재하고 어떤 페이지가 스왑 영역에 존재하는지 구분하기 위해 페이지 테이블에는 각 페이지 별로 유효-무효 비트 값이 존재한다.

• invalid: 페이지가 물리적 메모리에 올라가 있지 않은 경우, 사용되지 않은 주소 영역인 경우
• valide: 페이지가 물리적 메모리에 올라가 있는 경우

프로세스가 실행되기 전에는 모두 invalid로 초기화되어 있다. 그러나 특정 페이지가 메모리에 적재되면 해당 페이지의 유효-무효 비트 값은 valid로 변경되고, 메모리에 적재되어 있던 페이지가 스왑 아웃될 때는 다시 invalid로 변경된다. 

페이지 부재(page fault)

페이지 부재는 CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않은 경우, 즉 참조하려는 페이지에 해당하는 페이지 테이블의 유효-무효 비트 값이 invalid인 경우를 의미한다.

 

페이지 부재가 일어나면 해당 페이지를 디스크로부터 읽어와서 메모리에 올려야 한다. 즉, I/O 작업이 필요하다. 따라서 이는 사용자 프로그램이 직접 할 수 없으므로, 주소 변환을 담당하는 하드웨어인 MMU가 페이지 부재 트랩을 발생시킨다. 그러면 CPU의 제어권이 운영체제로 넘어가서 커널 모드로 전환되고, 운영체제의 페이지 부재 처리루틴이 호출되어 다음 순서로 페이지 부재를 처리한다.

1. CPU가 페이지 테이블을 참조한다.
2. 찾고자 하는 페이지의 유효-무효 비트 값이 invalid이다. 따라서 주소 변환을 담당하는 하드웨어인 MMU가 페이지 부재 트랩을 발생시키고, CPU의 제어권이 운영체제로 넘어가서 운영체제의 페이지 부재 처리루틴이 호출된다.
3. 우선 해당 페이지에 대한 접근이 허용 가능한지 체크한다(사용되지 않는 주소 영역에 속한 페이지에 접근하려 했거나 해당 페이지에 대한 접근 권한이 없을 경우에는 해당 프로세스를 종료시킨다).
4. 해당 페이지에 접근이 허용 가능하면, 물리적 메모리에서 비어 있는 프레임을 할당받아 그 공간에 해당 페이지를 적재시킨다. 만약 비어 있는 프레임이 없다면 메모리에 올라와 있는 페이지 중 하나를 디스크로 스왑 아웃시킨다. 한편 요청된 페이지를 메모리로 적재하기까지 오랜 시간이 소요된다(I/O 작업). 따라서 I/O 작업이 일어나는 동안 페이지 부재를 발생시킨 프로세스는 CPU를 빼앗겨 봉쇄 상태가 되고, CPU는 다른 프로세스에게 할당된다. (이때 현재까지 수행되던 CPU 레지스터 상태 및 프로그램 카운터 값을 PCB에 저장해두어 나중에 이 프로세스가 다시 CPU를 할당받았을 때 일을 재개할 수 있도록 한다.)
5. I/O 작업이 끝나면 페이지 테이블에 기록한다(이때 유효-무효 비트 값은 valid). 그리고 해당 프로세스는 CPU를 기다리는 준비 큐에 줄을 서게 된다.
6. 이후에 해당 프로세스가 CPU를 획득하게 되면 이번에는 페이지 부재가 일어나지 않고 MMU에 의해 정상적으로 주소 변환이 일어난다.

페이지 교체

페이지 부재가 발생하면 요청된 페이지를 메모리로 적재해야 한다. 그런데 이때 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다. 따라서 이 경우에는 메모리에 올라와 있는 페이지 중 하나를 디스크의 스왑 영역으로 스왑 아웃시켜야 한다. 이것을 페이지 교체라고 한다. 

페이지 교체 알고리즘

페이지 교체를 할 때에는 어떤 프레임에 있는 페이지를 스왑 아웃시킬지 결정하는 알고리즘이 필요한데, 이를 교체 알고리즘이라고 한다. 이 알고리즘의 목표는 페이지 부재율을 최소화하는 것이다.

최적(Optimal) 알고리즘(=빌레디의 최적 알고리즘, MIN, OPT)

최적 알고리즘은 가장 먼 미래에 참조될 페이지를 내쫓는다. 이 알고리즘은 어떠한 알고리즘을 사용하는 경우보다도 가장 적은 페이지 부재율을 보장한다.

 

그러나 이는 미래에 어떤 페이지가 어떤 순서로 참조될지 미리 알고있다는 전제하에 작용하므로, 실제 시스템에서 사용할 수 있는 알고리즘은 아니다. 따라서 이를 오프라인 알고리즘이라고도 부른다.

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

선입선출 알고리즘은 메모리에 가장 먼저 올라온 페이지를 내쫓는다.

 

이 알고리즘은 페이지의 향후 참조 가능성을 고려하지 않기 때문에 비효율적인 상황이 발생할 수도 있다. (ex, 가장 먼저 적재된 페이지가 이후 빈번하게 참조되는 경우)

LRU(Least Recently Used) 알고리즘

LRU 알고리즘은 가장 오래 전에 사용된 페이지를 내쫓는다.

 

이는 참조된 시간을 기준으로 링크드리스트 형태로 구현한다. 따라서 페이지 참조가 일어날 때 링크드리스트 재조정의 시간은 O(1)이다. 페이지가 참조되면, 해당 페이지의 노드를 가장 아래로 옮기면 되기 때문이다.

LFU(Least Frequently Used) 알고리즘

LFU 알고리즘은 과거에 참조 횟수가 가장 적었던 페이지를 쫓아낸다. 만약 최저 참조 횟수를 가진 페이지가 여러 개이면 임의로 하나를 선정해 그 페이지를 쫓아낸다. 성능 향상을 위해서는 최저 참조 횟수를 가진 페이지들 중에서 상대적으로 더 오래전에 참조된 페이지를 쫓아내도록 구현하는 것이 효율적이다.

 

이는 참조 횟수를 기준으로 힙 형태로 구현한다.

 

만약 LRU처럼 링크드리스트 형태로 관리한다면, 페이지가 참조될 때 링크드리스트 재조정의 시간은 최악의 경우 O(N)이 걸린다. 만약 참조 횟수가 1 늘어나서 3이 되었다고 가정하면, 바로 아래의 노드와 비교하며 3보다 큰 노드가 나올 때까지 노드의 순서를 바꾸기 때문이다.

 

따라서 LFU는 힙으로 구현되어 있으며, 참조 횟수가 가장 적은 페이지를 가장 위 노드로 둔다. 따라서 페이지 참조가 일어날 때 재조정 시간은 O(logN)의 시간이 걸린다.

클럭 알고리즘

페이징 시스템에서 LRU와 LFU 알고리즘은 실제로 사용될 수 없는데, 그 이유는 다음과 같다. 

• 운영체제는 페이지 참조 시점과 횟수를 제대로 알 수 없다. CPU가 이미 메모리에 올라와 있는 페이지(valid)에 접근할 경우, 운영체제의 개입이 불필요하다. 페이지 테이블을 참조하고, valid인 페이지의 물리 주소를 알아내는 것은 MMU라는 하드웨어를 통해 이루어지기 때문이다. 따라서 이 경우, 운영체제는 해당 페이지를 새로 참조했다는 사실을 알 수 없다. 즉, 운영체제는 페이지 참조 시점과 횟수를 제대로 알 수가 없다. 운영체제는 페이지 부재가 일어나서 CPU 제어권이 운영체제로 넘어왔을 때에만 해당 페이지가 참조되려고 한다는 것을 알 수 있다. 
• 페이지의 참조 시점과 횟수 정보 저장하고 비교해야 하므로 오버헤드가 발생한다.

클럭 알고리즘은 LRU 근사 알고리즘으로, 페이징 시스템에서 LRU를 사용할 수 없는 것을 근사 개념을 활용해 보완한 알고리즘이다. 

 

클럭 알고리즘은 페이지 테이블의 각 엔트리에 reference bit와 modified bit를 두어 구현한다. MMU는 페이지 읽기가 발생하면 reference bit만 1로 만들고, 페이지 쓰기가 발생하면 reference bit와 modified bit 둘 다 1로 만든다. 

• reference bit (1: 최근에 참조된 페이지)
  • MMU는 주소 변환을 할 때 해당 페이지가 CPU에 의해 참조되었다는 의미로, 해당 페이지의 reference bit를 1로 바꾼다.
  • CPU는 원형 리스트를 돌면서 reference bit가 0인 것을 찾을 때까지 탐색한다.
    • reference bit가 1이면, 최근에 참조된 페이지이므로 0으로 바꾸고 다음 노드를 탐색한다.
    • reference bit가 0이면, 최근에 참조되지 않은 페이지이므로 해당 페이지를 쫓아낸다. 
  • 즉, 비트를 1로 바꾸는 것은 MMU라는 하드웨어가 하는 일이고, 비트를 0으로 바꾸는 것은 운영체제가 하는 일이다.
  • 한 바퀴를 탐색한 후에 특정 페이지의 reference bit가 1이라는 것은, 이전에 탐색할 때 0으로 변경했는데 그 사이에 페이지 참조가 일어나서 1로 바뀐 것이다. 즉, 한 바퀴를 탐색한 후에도 reference bit가 1이라는 것은, 최근에 참조된 페이지라는 것이다.

• modified bit (1: 최근에 변경된 페이지)
  
  • 특정 페이지를 쫓아낼 때 modified bit가 0이면, 해당 페이지가 메모리에 올라온 이후에 수정되지 않았다는 의미이다. 따라서 메모리에서 해당 페이지를 지우기만 한다.
  • 특정 페이지를 쫓아낼 때 modified bit가 1이면, 해당 페이지가 메모리에 올라온 이후에 수정되었다는 의미이다. 따라서 디스크의 스왑 영역에 수정 사항을 반영한 후에 메모리에서 페이지를 지운다.

클럭 알고리즘은 가장 오래 전에 참조된 페이지를 내쫓는다고 보장할 순 없지만, 최근에 참조된 페이지를 내쫓지 않는다는 것은 보장한다. 따라서 NUR(Not Used Recently) 또는 NRU(Not Recently Used) 알고리즘이라고도 한다.

Global vs Local Replacement

앞서 설명한 알고리즘들은 물리적 메모리에서 페이지를 쫓아낼 때 어떤 프로세스의 페이지인지 고려하지 않는다. 즉, 물리적 메모리가 꽉 차서 자리가 없을 때 각 알고리즘에 따라 쫓아낼 페이지를 고르는데, 이때 쫓아낼 페이지가 어떤 프로세스의 페이지인지 구분하지 않는다. 이를 Global Replacement라고 한다.

• Global Replacement: replace(스왑 아웃 + 스왑 입) 시 다른 프로세스의 페이지 프레임을 내쫓을 수 있다.
• Local Replacement: replace 시 다른 프로세스의 페이지 프레임을 내쫓을 수 없다. 즉, 미리 각 프로세스마다 일정량의 물리적 메모리 공간을 할당하는 방식이다. 이러한 방식을 적용하는 이유는 프로세스 실행 시 페이지 부재가 빈번히 발생하지 않기 위함이다. 즉, 각 프로세스에게 할당되어야 하는 최소한의 물리적 메모리 양이 있다고 보는 방식이다.
  • equal allocation: 모든 프로세스에게 똑같은 양을 할당한다.
  • proportionial allocation: 프로세스 크기에 비례하여 할당한다.
  • priority allocation: 프로세스가 CPU를 언제 사용하는지에 따라 할당한다.

스레싱(Thrashing)

사용하는 프로세스가 많아질수록(MPD: Multi-Programming Degree) CPU 이용률이 증가한다. 그러나 어느 순간 CPU 이용률이 급격히 떨어지는데 그 이유 중 하나가 스레싱이다. 스레싱은 페이지 부재가 빈번히 발생하여 CPU의 프로세스 처리 시간보다 스와핑 I/O 시간이 더 많이 발생하는 현상이다.

 

스레싱이 발생하는 과정을 알아보자.

1. MPD가 과도하게 많아지면 각 프로세스에게 할당되는 메모리의 양이 지나치게 감소하게 된다.
2. 따라서 각 프로세스들은 원활한 수행을 위한 최소한의 페이지 프레임도 할당받지 못하여 페이지 부재가 빈번하게 발생하게 된다.
3. 페이지 부재가 발생하면 이를 처리하기 위해 디스크  I/O 작업이 수행되고, 이 작업이 수행되는 동안 CPU 제어권은 다른 프로세스에게 넘어간다. 그런데 이때 CPU를 할당받은 다른 프로세스도 할당받은 메모리 양이 지나치게 적어 페이지 부재가 발생하면 또 다른 프로세스에게 CPU가 할당된다. 이러한 과정이 반복되면 결국 준비 큐에 있는 모든 프로세스에게 CPU가 한 번씩 할당되었지만 모두 페이지 부재가 발생하여 이를 처리하기 위해 CPU의 이용률은 급격히 떨어지게 된다.
4. 이 상황에서 운영체제는 메모리에 올라와 있는 프로세스의 수가 적어 CPU 이용률이 낮은 것이라 판단하여 다른 프로세스를 메모리에 추가하게 된다.
5. 이로 인해 프로세스당 할당된 프레임의 수는 더욱 감소하고 페이지 부재는 더욱 빈번하게 발생하는 악순환이 발생한다.이 경우 프로세스들은 서로의 페이지를 교체하며 스왑 아웃과 스왑 인을 지속적으로 발생시키고, 그동안 CPU는 일을 하지 않게 된다. 이러한 상황을 스레싱이라고 부른다. 

워킹셋 알고리즘

워킹셋은 프로세스가 특정 시점에 원활히 수행되기 위해 메모리에 올라와 있어야 하는 페이지들의 집합이다. 이들은 프로세스가 최근에 참조한 페이지들로 구성되며, 프로세스가 일시적으로 필요로하는 페이지의 집합이다. 워킹셋 알고리즘은 프로세스가 실행될 때 해당 프로세스가 사용하는 페이지의 집합인 워킹셋을 추적하고 관리하는 알고리즘이다. 즉, 워킹셋은 워킹셋 알고리즘에 의해 프로세스가 실행될 때 동적으로 변경된다. 

 

워킹셋의 모든 페이지를 메모리에 올릴 수 있으면 올리고, 그렇지 않으면 일부 프레임을 스왑 아웃시킨다. 이때 어떤 페이지를 스왑 아웃시킬지 결정할 때 워킹셋을 고려한다. 즉, 워킹셋에 포함되지 않는 페이지 또는 최근에 참조되지 않은 페이지를 스왑 아웃시킨다.

페이지 부재 빈도 알고리즘

페이지 부재 빈도 알고리즘은 프로세스의 페이지 부재율을 주기적으로 조사하고 이에 근거하여 각 프로세스에 할당할 메모리 양을 동적으로 조절한다. 

• 어떤 프로세스의 페이지 부재율이 시스템에서 미리 정해놓은 상한값을 넘게 되면, 이 프로세스에게 할당된 프레임 수가 부족하다고 판단하여 이 프로세스에게 프레임을 추가로 할당한다. 이때 추가로 할당할 프레임이 없으면 일부 프로세스를 스왑 아웃시킨다.
• 반면 프로세스의 페이지 부재율이 하한값 이하로 떨어지면, 이 프로세스에게 필요 이상으로 많은 프레임이 할당된 것으로 간주해 할당된 프레임의 수를 줄인다.

이런 방식으로 모든 프로세스에게 필요한 프레임을 다 할당한 후에도 프레임이 남는 경우, 스왑 아웃되었던 프로세스에게 프레임을 할당함으로써 MPD를 높인다. 페이지 부재 빈도 알고리즘에서는 이런 원리로 MPD를 조절하면서 CPU 이용률을 높이는 동시에 스레싱을 방지한다. 

페이지 사이즈

가장 많이 쓰이는 페이지 사이즈는 4KB이지만, 점점 메모리 크기와 프로그램 크기가 커지며 페이지 사이즈가 커지는 것이 추세이다.

 

만약 페이지 사이즈를 감소시키면 어떻게 될까?

• 장점
  • 내부 조각 감소
  • 필요한 정보만 작은 크기로 메모리에 올라가 한정된 양의 메모리를 효율적으로 이용할 수 있다. 
• 단점
  • 페이지 수 증가, 페이지 테이블 크기 증가
  • 대부분의 경우 연속된 코드를 읽을 때 연속된 페이지를 메모리에 적재한다. 즉, 하나의 페이지에 대한 페이지 부재가 발생하여 해당 페이지를 메모리로 적재하면, 이어서 다음 페이지도 같은 과정으로 메모리에 적재한다는 의미이다. 따라서 페이지 사이즈가 작아지면 페이지 부재가 빈번히 발생하고, 그만큼 디스크에서 메모리로 페이지를 올리는 I/O 작업도 빈번히 발생할 것이다. 

---

Reference

• 이화여자대학교출판문화원, 운영체제와 정보기술의 원리, 반효경