가상 메모리

가상메모리

프로그램이 CPU에서 실행되려면 실행에 당장 필요한 부분이 메모리에 올라와 있어야 한다. 한편 여러 프로그램이 동시에 수행되는 시분할 환경에서는 한정된 메모리 공간을 여러 프로그램이 조금씩 나누어서 사용한다. 따라서 운영체제는 어떤 프로그램에게 어느 정도의 메모리를 할당할 것인가 하는 문제에 당면하게 된다. 운영체제는 모든 프로그램들에게 같은 크기의 메모리를 할당하는 것이 아니라 몇몇 프로그램들에게 메모리를 집중적으로 할당하고 시간이 흐르면 회수하는 방식을 사용한다. 그 이유는 프로세스의 빠른 수행을 위해 프로그램마다 최소한 확보해야 하는 메모리의 크기가 존재하기 때문이다.

운영체제는 CPU에서 당장 수행해야 할 부분만을 메모리에 올려놓고 그렇지 않은 부분은 디스크의 스왑 영역에 내려놓았다가 다시 필요해지면 메모리에 올라가 있는 부분과 교체하는 방식을 사용한다. 프로그램 입장에서는 물리적 메모리 크기에 대한 제약을 생각할 필요가 없어지고, 자기 자신만이 메모리를 사용하는 것처럼 가정해 프로그램하는 것을 지원한다. 이렇게 되면 프로그램은 0번지부터 시작하는 자기 자신만의 메모리 주소 공간을 가정할 수 있는데, 이러한 메모리 공간을 가상 메모리라고 부른다.

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

---

요구 페이징

요구 페이징이란 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 당장 사용될 페이지만을 올리는 방식을 말한다. 따라서 요구 페이징 기법에서는 특정 페이지에 대해 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재한다. 이 덕에 메모리 사용량이 감소하고, 프로세스 전체를 메모리에 올리는 데 소요되는 입출력 오버헤드도 줄어든다. 요구 페이징 기법의 주된 호용은 프로그램이 물리적 메모리의 용량 제약을 벗어날 수 있도록 한다는 점이다. 프로그램을 구성하는 페이지 중 일부만을 메모리에 적재하게 되므로 물리적 메모리의 용량보다 큰 프로그램도 실행할 수 있게 되기 때문이다.

페이지 중에서 어떤 페이지가 메모리에 존재하고 어떤 페이지가 존재하지 않는지 구별하기 위해 유효-무효 비트를 두어 각 페이지가 메모리에 존재하는지 표시하게 된다. 이 비트는 프로세스를 구성하는 모든 페이지에 대해 존재해야 한다. 프로세스 실행 전에는 무효값으로 초기화되어 있지만 메모리에 적재되면 유효값으로 바뀌게 된다. 스왑아웃되면 다시 무효값이 된다. CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우를 페이지 부재가 일어났다고 말한다.

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

CPU가 무효 페이지에 접근하면 주소 변환을 담당하는 하드웨어인 MMU가 페이지 부재 트랩을 발생시키게 된다. 그러면 CPU의 제어권이 커널모드로 전환되고, 운영체제의 페이지 부재 처리루틴이 호출된다. 운영체제는 해당 페이지에 대한 접근이 적법한지를 먼저 체크하게 되는데, 사용되지 않는 주소 영역에 속한 페이지에 접근하려 했거나 해당 페이지에 대한 접근 권한 위반을 했을 경우에는 해당 프로세스를 종료시킨다. 접근 권한 위반의 예를 들자면, 읽기 전용인 페이지에 대해 쓰기 접근 시도를 하는 것을 들 수 있다.

해당 페이지에 대한 접근이 적법한 것으로 판명된 경우 물리적 메모리에서 비어 있는 프레임을 할당받아 그 공간에 페이지를 읽어 온다. 만약 프레임이 없다면 스왑 아웃 시킨다. 디스크로부터 메모리 적재할 동안 시간이 꽤 소요된다. 페이지 부재를 발생시킨 프로세스는 이때 CPU를 뺏기고 봉쇄상태가 된다. 이때 현재까지 수행되던 CPU 레지스터 상태 및 프로그램 카운터값을 PCB에 저장해서 나중에 다시 CPU할당 받았을 때를 대비한다. 디스크 입출력이 완료되어 인터럽트가 발생하면 페이지 테이블에서 해당 페이지의 유효-무효 비트를 유효로 설정하고, 봉쇄되엇던 프로세스를 준비 큐로 이동시킨다.

요구 페이징의 성능

요구 페이징 기법의 성능에 가장 큰 영향을 미치는 요소는 페이지 부재의 발생 빈도이다. 디스크로부터 메모리로 읽어오는 막대한 오버헤드가 발생하기 때문이다. 요구 페이징의 성능은 요청한 페이지를 참조하는 데 걸리는 유효 접근시간으로 측정한다.

---

페이지 교체

페이지 부재로 인해 디스크를 읽어오는 작업에서 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다. 이 경우에는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하는 작업이 필요한데 이것을 페이지 교체라고 한다. 페이지 교체를 할 때에 어떤 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘을 교체 알고리즘이라고 한다. 이 알고리즘의 목표는 페이지 부채율을 최소화하는 것이다.

이 성능은 페이지 참조열에 대해 페이지 부재율을 계산함으로써 평가할 수 있다. 페이지 참조열은 참조되는 페이지들의 번호를 시간 순서에 따라 나열한 것이다. 해당 번호의 페이지가 메모리에 이미 올라와 있으면 메모리에서 적중(hit)되었다고 하고, 없는 경우에는 페이지 부재가 발생했다고 말한다.

최적 페이지 교체

부재율을 최소화하기 위해서는 교체 시 가장 먼 미래에 참조될 페이지를 쫓아내면 된다. 이러한 최적의 알고리즘을 빌레디의 최적 알고리즘 또는 MIN,OPT 등의 이름으로 부른다.

이 알고리즘은 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고 있다는 전제하에 알고리즘을 운영하므로 실제 시스템에서 올라인으로 사용할 수 있는 알고리즘은 아니다. 따라서 이러한 알고리즘을 오프라인 알고리즘이라고 부른다. 어떠한 경우보다 가장 적은 페이지 부채율을 보장하므로 다른 알고리즘의 성능에 대한 상한선을 제공한다. 따라서 어떤 시스템에서 새로운 교체 알고리즘을 설계했는데 그 성능이 빌레디의 최적 알고리즘과 유사했다고 한다면, 더 이상 교체 알고리즘의 연구가 필요하지 않다는 것을 의미한다.

선입선출 알고리즘

페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다. 가장 먼저 물리적 메모리에 들어온 페이지가 계쏙해서 많은 참조가 이루어진다고 하더라도 FIFO 알고리즘은 이 페이지를 내쫓게 되어서 비효율적인 상황이 발생할 수 있다.

물리적 메모리의 공간이 늘어나도 성능은 더 나빠질 수가 있다. 이러한 상황을 FIFO의 이상 현상 이라고 부른다.

LRU 알고리즘

시간지역성: 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질

LRU 알고리즘은 이와 같은 성질을 활용해서 페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 쫓아낸다.

LFU 알고리즘

LFU(Least Frequently Used) 알고리즘은 페이지의 참조 횟수로 교체시킬 페이지를 결정한다. 페이지 중에서 과거에 참조 횟수가 가장 적었던 페이지를 쫓아내고 그 자리에 새로 참조될 페이지를 적재한다. 그 값이 같을 경우 임의로 하나를 선정해서 쫓아낸다. 성능 향상을 위해서는 상대적으로 더 오래전에 참조된 페이지를 쫓아내도록 구현하는 것이 효율적이다.

페이지의 참조 횟수를 계산하는 방식은 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수를 카운트하는 방식인 Incache-LFU가 있다. 페이지가 메모리에서 쫓겨났다가 다시 들어온 경우 참조 횟수는 1부터 새롭게 시작된다. 그리고 메모리에 오랄와 있는지의 여부와 상관없이 그 페이지의 과거 총 참조 횟수를 카운트 하는 Perfect-LFU가 있다. 이는 메모리에서 쫓겨났다가 들어와도 이전 참조횟수가 누적이 된다. 이는 페이지의 참조횟수를 정확히 반영할 수 있다는 장점이 있지만, 메모리에서 쫓겨난 페이지의 참조 기록까지 모두 보관하고 있어야 하므로 그 오버헤드가 상대적으로 더 크다는 점이 있다.

LFU 알고리즘은 LRU보다 더 장기적인 시간 규모에서의 참조 성향을 고러할 수 있다는 장점이 있다. 하지만 LFU는 시간에 따른 페이지 참조의 변화를 반영하지 못하고, LRU보다 구현이 복잡하다는 단점이 있다.

클럭 알고리즘

클럭 알고리즘은 LRU를 근사시킨 알고리즘으로 NUR(Not Used Recently) 또는 NRU(Not Recently Used)알고리즘으로도 불린다.

LRU 알고리즘이 가장 오래전에 참조된 페이지를 교체하는 것에 비해 클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체한다. 최근에 참조되지 않은 페이지를 교체 대상으로 선정한다는 측면에서 LRU와 비슷하지만 가장 오래되었다는 것을 보장하지는 못한다는 점에서 LRU를 근사시킨 알고리즘으로 볼 수 있다. 하지만 이 알고리즘은 하드웨어적인 자원으로 동작하기 때문에 훨씬 빠르고 효율적이다. 2차 기회 알고리즘이라고도 부른다.

---

페이지 프레임의 할당

여러 프로세스가 수행되는 상황에서 각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인지를 결정해야 하고 이런 기본적인 할당 알고리즘은 세 가지로 나누어볼 수 있다.

첫 번째 방법은 모든 프로세스에게 페이지 프레임을 균일하게 할당하는 균등할당 방식

두 번째 방법은 프로세스의 크기에 비례해 페이지 프레임을 할당하는 비례할당 방식

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

그러나 할당 알고리즘만으로는 프로세스의 페이지 참조 특성을 제대로 반영하지 못할 우려가 있다. 현재 수행 중인 프로세스의 수가 지나치게 많을 경우 프로세스당 할당되는 메모리 양이 과도하게 적어질 수 있기 때문이다. 그렇기 때문에 종합적인 상황을 고려해서 각 프로세스에 할당되는 페이지 프레임의 수를 결정할 필요가 있으며, 경우에 따라서는 일부 프로세스에게 메모리를 할당하지 않는 방식으로 나머지 프로세스들에게 최소한의 메모리 요구량을 충족시킬 수 있어야 한다.

---

전역교체와 지역교체

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

전역교체 방법은 모든 페이지 프레임이 교체 대상이 될 수 있는 방법이다.

지역교체 방법은 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법이다. 지역교체 방법은 프로세스마다 페이지 프레임을 미리 할당하는 것을 전제로 한다. 반면 전역교체 방법은 프로세스마다 메모리를 할당하는 것이 아니라 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법이다.

LRU, LFU, 클럭 등의 알고리즘은 물리적 메모리 내에 존재하는 전체 페이지 프레임들을 대상으로 적용하기에 전역교체 방법이다.

그러나, 만약 프로세스별로 페이지 프레임을 할당하고, 교체할 페이지도 그 프로세스에게 할당된 프레임 내에서 선정하게 되는 것이고, LRU, LFU 등의 알고리즘이 프로세스별로 독자적으로 운영할 때에는 지역교체 방법이 된다.

---

스레싱

프로세스가 원활하게 수행되기 위해서는 일정 수준 이상의 페이지 프레임을 할당받아야 하는데, 그렇지 못하게 되면 페이지 부재율이 크게 상승해 CPU 이용률이 급격히 떨어질 수 있다. 이런 현상을 스레싱이라고 부른다.

운영체제는 CPU의 이용률이 낮을 경우 메모리에 올라와 있는 프로세스의 수가 적기 때문이라고 판단하는데, 준비 큐에 프로세스가 단 하나라도 있으면 CPU는 그 프로세스를 실행하므로 일한다. 즉 CPU의 이용률이 낮다는 것은 준비 큐가 빈다는 뜻이다. 프로세스 수가 너무 적어 이들이 I/O 작업을 하느라 준비 큐가 비는 경우가 발생했다는 것이다. 이렇게 CPU의 이용률이 낮으면 운영체제는 메모리에 올라가는 프로세스의 수를 늘리게 된다. 메모리에 동시에 올라가 있는 프로세스의 수를 다중 프로그래밍 정도(Multi-Programming Degree:MPD) 라고 부른다. MPD가 과도하게 높아지면 각 프로세스에게 할당되는 메모리의 양이 지나치게 감소하게 된다. 이렇게 되면 원활한 수행을 위한 최소한의 페이지 프레임도 할당받지 못하는 상태가 되어 페이지 부재가 빈번히 발생하게 된다. 페이지 부재가 발생하면 디스크 I/O작업을 수반하므로 문맥교환이 일어나게 된다. 근데 다른 프로세스 또한 메모리 양이 적으면 또 부재가 발생하게 된다. 이렇게 반복되다보면 시스템은 페이지 부재를 처리하느라 매우 분주해지고 CPU의 이용률은 급격히 떨어지게 된다. 그럼 운영체제는 메모리에 올라와 있는 프로세스의 수가 적어서라는 판단을 하고 MPD를 높이기 위해 프로세스를 메모리에 또 추가하게 되고 그럼 더욱 할당된 프레임 수가 감소되고 악순환이 반복된다. 이때 프로세스들은 서로의 페이지를 교체하며 스왑 인/아웃을 계속 발생시키고 CPU는 일을 안하게 된다. 이러한 상황을 스레싱이라고 부르게 되는 것이다. MPD를 적절히 조절해 CPU 이용률을 높이는 동시에 스레싱 발생을 방지하는 방법에는 워킹셋 알고리즘과 페이지 부재 빈도 알고리즘이 있다.

워킹셋 알고리즘

프로세스는 일정 시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있다. 이렇게 집중적으로 참조되는 페이지들의 집합을 지역성 집합이라고 한다. 워킹셋 알고리즘은 이러한 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘을 뜻한다.

워킹셋 알고리즘에서는 프로세스가 일정 시간 동안 원활히 수행하기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합을 워킹셋이라고 정의하고, 프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당한다. 그렇지 못한다면 해당 프로세스에게 할당된 페이지 프레임을 모두 반납시킨 후 그 프로세스의 주소 공간 전체를 디스크로 스왑 아웃 시킨다. 워킹셋 알고리즘은 워킹셋 윈도우를 이용해서 해당 시간 사이에서 참조된 서로 다른 페이지들의 집합을 구한다. 워킹셋 알고리즘은 메모리에 올라와 있는 프로세스들의 워킹셋 크기의 합이 프레임의 수보다 클 경우 일부 프로세스를 스왑 아웃시켜서 남은 프로세스의 워킹셋이 메모리에 모두 올라가는 것을 보장한다. 이는 MPD를 줄인다. 반면 프로세스들의 워킹셋을 모두 할당한 후에도 프레임이 남을 경우, 스왑 아웃되었던 프로세스를 다시 메모리에 올려서 워킹셋을 할당함으로써 MPD를 증가시킨다.

윈도우의 크기가 너무 작으면 지역성 집합을 모두 수용하지 못할 우려가 있고, 반대로 윈도우의 크기가 너무 크면 여러 규모의 지역성 집합을 수용할 수 있는 반면 MPD가 감소해 CPU 이용률이 낮아질 우려가 있다. 시간의 흐름에 따라 워킹셋의 크기가 변하는데 이는 일종의 동적인 프레임 할당 기능까지 수행한다고 할 수 있다.

페이지 부재 빈도 알고리즘

페이지 부재 빈도(Page Fault Frequency : PFF) 알고리즘은 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절한다. 어떤 프로세스의 페이지 부재율이 시스템에서 미리 정해놓은 상한값을 넘게 되면 이 프로세스에 할당된 프레임의 수가 부족하다고 판단하여 이 프로세스에게 프레임을 추가로 더 할당한다. 이때 추가로 할당할 빈 프레임이 없다면 일부 프로세스를 스왑아웃시켜 메모리에 올라가 있는 프로세스의 수를 조절한다. 반면 프로세스의 페이지 부재율이 하한값 이하로 떨어지면 이 프로세스에게 필요 이상으로 많은 프레임이 할당한 것으로 간주해 할당된 프레임의 수를 줄인다.

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

---