가상메모리

베경
요구 페이징
쓰기 시 복사
페이지 교체
프레임의 할당
스레싱
메모리 사상 파일
커널 메모리의 할당

배경

가상 메모리(Virtaul Memory) 라는 것은 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 것이다. 이 기법의 가장 주요 장점중 하나는 사용자 프로그램이 물리 메모리(Pysical Memoey)보다 커져도 된다는 점이다.


물리 메모리보다 큰 가상 메모리를 보여주는 다이어그램

가상 메모리 는 실제 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한 것이다. 이렇게 함으로써 작은 메모리를 가지고도 얼마든지 큰 가상 공간을 프로그래머에게 제공할 수 있다는 점이다.

한 프로세스의 가상 주소 공간 은 그 프로세스가 메모리에 저장되는 논리적인 모습을 말한다.


가상 주소 공간

논리 메모리를 물리 메모리로부터 분리시캬주는 것 외에 가상 메모리는 페이지 공유를 통해 파일이나 메모리가 둘 또는 그 이상의 프로세스들에 의해 공유되는 것을 가능하게 한다.

시스템 라이브러리가 여러 프로세스들에게 공유될 수 있다.
프로세스들이 메모리를 공유할 수 있다.
페이지는 fork() 시스템콜을 통한 프로세스 생성 과정중에 공유될수 있기 때문에 프로세스 생성 속도를 높일수 있다.


가상 메모리를 사용한 공유 라이브러리

요구 페이징

실행 프로그램을 디스크에서 메모리로 적재 할때, 초기에 필요한 것들만을 적재 하는 전략이 있을수 있다. 이 기법을 요구 페이징(Demand Paging) 이라고 하며 가상 메모리 시스템에서 많이 사용되고 있다.

요구 페이징을 사용하는 가상메모리에서는 페이지들이 실행과정에서 실제로 필요해 질 때 적재(Dynamic Load)된다.

요구 페이징 기법은 어떤점에서 스와핑(swarpping) 기법과 유사하다.


디스크 내 인접한 공간과 페이지화 된 메모리의 이동

프로세스는 보조 메모리에 존재한다. 프로세스를 실행하고 싶으면 메모리로 읽어 들인다(Swap in). 이때 전체 프로세스를 읽어오지 않고 게으른 스왑퍼(lazy swapper) 또는 페이저(pager) 를 사용하여 그 페이지가 필요로 하는 부분만 메모리에 적재 시킨다.

기본 개념

요구 페이징을 수행하기 위해선 어느 페이지가 디스크에만 있고, 어느 페이지가 메모리에 올라와 있는지 구별할 수 있어야 한다. 따라서 하드웨어의 지원이며 페이지 테이블 에서 사용되었던 기법인 유효 무효 비트(valid/invalid bit) 기법이 사용된다. 그러나 이전의 페이지 테이블 과는 달리 이 비트가 유효(valid)하다고 설정되면 해당 페이지가 메모리에 있다는 의미이고, 무효(invalid)하다고 설정되면 해당 페이지가 유효하지 않거나(즉, 가상 주소 공간상에 정의되지 않거나) 유효하지만 디스크에 존재한다는 것을 의미한다.

어떤 페이지를 무효로 설정하는 것은 그 페이지를 접근하기 전까지는 어떠한 영향도 끼치지 않는다는 점을 주의한다. 즉, 제대로 추측하여 실제로 접근될 페이지들만을 적재한 경우 프로세스는 모든 페이지가 메모리에 존재할 때와 동일하게 수행된다.

프로세스가 메모리에 존재하는(Memory Resident) 페이지들만을 접근하는 한 실행은 정상적으로 진행된다.


일부 페이지가 주 메모리에 없을때의 페이지 테이블

프로세스가 메모리에 올라와 있지 않는 페이지를 접근하려고 하면, 이때는 페이지 테이블 항목이 무효로 되어 있으므로 페이지 부재 트랩(Page Fault Trap) 이 발생시킨다. 페이징 하드웨어는 페이지 테이블을 이용한 주소 변환 과정에서 무효 비트를 발견하고 OS에게 트랩을 건다. 이 트랩은 OS가 필요한 페이지를 적재하는데 실패했기 때문이다.

페이지 부재를 처리하는 과정은 다음과 같다.

프로세스에 대한 내부 테이블(internal table : 일반적으로 PCB와 함께 유지) 을 검사하여 그 메모리 참조가 유효인지 무효인지 검사.
만약 프로세스가 무효한 페이지에 대한 참조라면 그 프로세스는 중단된다. 만약 유효한 참조인데 페이지가 아직 메모리에 올라오지 않았다면, 그것을 디스크로부터 가져와야 한다.
빈 공간, 즉 자유 프레임(Free Frame) 을 찾는다.
디스크에 새로이 할당된 프레임으로 해당 페이지를 읽어 들이도록 요청한다.
디스크 읽기가 끝나면, 이 페이지가 이제는 메모리에 있다는 것을 알리기 위해 페이지 테이블 을 갱신하며, 프로세스가 유지하고 있는 내부 테이블 을 수정한다.
트랩에 의해 중단되었던 명령어를 다시 수행한다. 이제 프로세스는 마치 그 페이지가 항상 메모리에 있었던 것 처럼 해당 페이지에 접근 할 수 있다.


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

필요한 모든 페이지가 적재되고 나면 더이상 부재 오류가 발생하지 않는다. 이것이 순수 요구 페이징(Pure Demand Paging) 이다. 즉, 어떤 페이지가 필요해지기 전까지는 결코 그 페이지를 메모리로 적재하지 않는 방법이다.

요구 페이징 을 지원하기 위해 필요한 하드웨어는 페이징 과 스와핑 을 위한 하드웨어와 동일하다.

페이지 테이블(Page Table)
- 보호 비트(Protection Bit) 를 특별한 값 또는 유효/무효 비트(valid/invalid Bit) 를 통해 특정 항목을 무효로 설정할 수 있어야 한다.
보조 기억 장치(Secondary Memory)
- 주 메모리에 없는 모든 페이지들을 가지고 있다. 이를 스왑 장치 라고 하며, 이 목적을 위해 사용되는 디스크 영역를 스왑 공간(Swap Space) 라고 한다.

요구 페이징을 위한 필수적인 요구사항은 페이지 부재 오류 처리 후에 명령어 처리를 다시 시작할 수 있어야 한다는 것이다.

쓰기 시 복사

fork()는 부모 프로세스와 똑같은 자식 프로세슷 만들어 준다. 과거에는 fork()를 하면 부모 프로세스의 페이지들을 실제로 자식 프로세스에 복사해 줌으로써 자식 프로세스의 주소 공간을 구성해 주었다. 그렇지만 대부분의 자식들은 이렇게 만들어 지자마자 exec() 시스템콜을 한다. 그러면 부모로부터 복사해온 페이지들은 모두 쓸모없게 되게 된다. 그래서 부모의 페이지들을 복사해오는 대신 쓰기 시 복사(Copy on Write) 방식을 사용 할 수 있다.

이 방식에서는 자식 프로세스가 시작할 때 부모의 페이지를 당분간 함께 사용하도록 한다. 이때 공유되는 페이지를 쓰기 시 복사 페이지 라고 표시한다.


프로세스 1이 페이지 C를 수정하기 전


프로세스 1이 페이지 C를 수정한 후

페이지 교체

논리 주소의 page의 수가 프레임의 수보다 많이 지게 되면, 프레임들중 하나을 선택하여 이를 새로운 프레임과 교체해야 한다.


페이지 교체의 필요성

기본적인 페이지 교체

만약 빈 프레임이 없다면 현재 사용되고 있지 않는 프레임을 찾아서 그것을 비워버린다. 그 프레임의 내용을 스왑 공간에 쓰고 그 페이지가 메모리에 더 이상 존재하지 않는다는 것을 나타내기 위해, 페이지 테이블을 변화 시킴으로서 프레임을 비어 있게 한다. 그리고 이제 비워진 프레임을 페이지 부재를 발생시킨 프로세스에서 사용할 수 있게 한다.


페이지 교체

페이지 부재 서비스 루틴이 페이지 교체를 포함하여 다음과 같이 과정이 진행 되어야 한다.

디스크에서 필요한 페이지의 위치를 알아낸다.
빈 페이지의 프레임을 찾는다. 2.1. 빈 프레임이 있다면 그것을 사용한다. 2.2. 없다면 희생될 프레임(victim frame) 을 선정하기 위해 페이지 교체 알고리즘 을 실행한다. 2.3. 희생될 페이지 를 디스크에 기록하고, 관련 테이블을 수정한다.
빼앗은 프레임에 새 페이지를 읽어오고 테이블을 수정한다.
페이지부재가 발생한 지점에서 부터 사용자 프로세스를 계속한다.

요구 페이징 시스템은 두가지 중요한 문제를 해결하야 하는데, 프레임 할당 알고리즘(Frame Allocation Algorithm) 과 페이지 교체 알고리즘(Page Replacement Algorithm) 이다. 즉 여러 프로세스가 존재하는 경우 각 프로세스에 얼마나 많은 프레임을 할당해야 하는지, 페이지 교체가 필요할 때마다 어떤 페이지를 교체해야 할지 결정해야 한다.

FIFO 페이지 교체(FIFO Page Replacement)

FIFO 페이지 교체 알고리즘은, 어떤 페이지를 교체할 때 메모리에 올라온지 가장 오래된 페이지를 교체한다.


FIFO 페이지 교체 알고리즘

FIFO 페이지 교체 알고리즘 은 이해하기도 쉽고 구현하기도 쉽지만, 성능이 항상 좋지만은 않다. 교체된 페이지가 오래 전 사용된 뒤 더이상 사용되지 않았던 초기화 모듈일수도 있고, 반대로 계속해서 자주 사용되는 변수를 포함하고 있을수도 있다.

[ 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ] 와 같은 참조열이 있을떄, 아래 그림과 같은 페이지 부재율 대 할당된 프레임 수 의 그래프를 보여진다.


FIFO 페이지 교체 알고리즘의 페이지 부재 그래프

위 그래프를 보면, 4개의 프레임을 할당했을시 페이지부재 10번이 일어났는데, 3개의 프레임을 할당하면 페이지 부재가 9번 일어남을 알 수 있다. 이러한 현상을 Belady의 모순(Belady’s Anomaly) 라고 부른다.

Belady의 모순 은 프로세스에게 프레임을 더 주었는데 오히려 페이지 부재율은 더 증가 하는 현상을 말한다.

최적 페이지 교체(Optimal Page Replacement)

최적 페이지 교체 알고리즘은, 어떤 페이지를 교체할 때 앞으로 가장 오랜 동안 사용되지 않을 페이지를 찾아 교체한다.

이 알고리즘은 할당된 프레임수가 고정된 경우 가장 낮은 페이지 부재율 을 보장한다.


최적 페이지 교체 알고리즘

이 최적 페이지 교체 알고리즘 은 프로세스가 앞으로 메모리를 어떻게 참조할 것인지 미리 알아야 하기 때문에 실제 구현이 어렵다.

LRU 페이지 교체(LRU Page Replacement)

LRU 페이지 교체 알고리즘은, 어떤 페이지를 교체할 때 가장 오랜 기간 동안 사용되지 않은 페이지를 교체한다.

LRU 페이지 교체 알고리즘 은 각 페이지 마다 마지막 사용 시간을 유지한다. 페이지 교체 시, LRU는 가장 오랫동안 사용되지 않은 페이지를 선택한다.


LRU 페이지 교체 알고리즘

LRU 페이지 교체 알고리즘 은 구현하기 위해 하드웨어의 지원이 필요하다. 프레임들을 최근 사용된 시간 순서로 파악할 수 있어야 하는 것이다. 이를 구현하기 위해 크게 두가지의 구현 방법이 존재한다.

계수기(Counters)
- 가장 간단한 방법으로, 각 페이지 항목마다 사용 시간 필드를 넣고 CPU에 논리적인 시계나 계수기를 추가한다. 그리고 매번 메모리 접근마다 시간은 증가한다.
- 시간값이 가장 작은 페이지가 교체된다.
- LRU 페이지를 찾기 위해 페이지 테이블 을 탐색해야 한다.
스택(Stack)
- 페이지 번호의 스택을 유지하는 방법이다. 페이지가 참조될 때마다 페이지 번호는 스택중간에서 제거 되어 스택의 top에 놓이게 된다. 이런 방법으로 진행하다 보면 스택의 top은 항상 가장 최근에 사용된 페이지이고, bottom은 가장 오랫동안 이용되지 않은 페이지 이다.
- 매 갱신시에 약간 더 오버헤드가 크지만 교체가 일어날 경우 페이지 테이블 을 탐색할 필요가 없다.


가장 최근의 페이지 참조를 기록하기 위한 스택의 사용

최적 페이지 교체 알고리즘 과 마찬가지로 LRU 페이지 교체 알고리즘 은 Belady의 모순 을 일으키지 않는다. 이렇게 페이지 교체 알고리즘들 중에서 Belady의 모순 을 일으키지 않는 알고리즘들을 스택 알고리즘(Stack Alorithm) 이라고 부른다.

LRU근사 페이지 교체(LRU Approximation Page Replacement)

LRU 페이지 교체 알고리즘을 충분히 지원하는 하드웨어는 거의 없다. 그러나 많은 시스템은 참조비트(Reference Bit)의 형태로 어느정도 지원은 하괴있다.

처음에 모든 참조비트는 OS에 의해 0으로 채워진다. 프로세스가 실행되면서 참조되는 페이지의 비트는 하드웨어가 1로 설정한다.


2차 기회(clock) 페이지 교체 알고리즘

계수 기반 페이지 교체(Counting Based Page Replacement)

각 페이지를 참조할 때 마다 계수를 하여 페이지 교체에 사용하되는 두 알고리즘이 있다.

LFU 알고리즘(Least Frequently Used Algorithm)
- LFU 알고리즘 은 참조 횟수가 가장 작은 페이지를 교체하는 방법이다.
MFU 알고리즘(Most Freeuently Used Algorithm)
- MFU 알고리즘 은 가장 작은 참조 횟수를 가진 페이지가 가장 최근 참조됫 것이고 앞으로 사용될 것이라는 판단에 근거한 방법이다.

프레임의 할당

여러개의 프로세스들에게 제한된 가용 메모리를 어떻게 할당할 것인가?

최소로 할당해야할 프레임의 수(Minimum Number of Frames)

최소한의 프레임을 할당해야만 하는 한가지 이유는 성능과 관계된다.

각 프로세스에 할당되는 프레임 수가 줄어들면 페이지 부재율은 증가하고 프로세스의 실행은 늦어지게 된다. 또한 명령어 수행을 완료되기 전에 페이지 부재가 발생하면 그 명령어가 재실행되어야 한다. 즉, 하나의 명령어가 참조하는 모든 페이지는 동시에 메모리에 올라와 있어야 그 명령어의 수행이 끝날수가 있게 된다.

프로세스의 최소 프레임 수는 아키텍처에 의해 결정되고 최대 할당 수는 가용 물리 메모리에 의해 결정된다.

할당 알고리즘(Allocation Algorithm)

균등 할당 방식(Equal Allocation)
- 모든 프로세스에게 똑같이 할당한다.
비례 할당 방식(Proportional Allocation)
- 가용 메모리를 각 프로세스의 크기 비율에 맞추어 할당한다.
우선순위 할당 방식(Priority Allocation)
- 비례 할당 방식기반이지만, 프레임 비율을 프로세스의 크기가 아닌 우선순위를 사용하여 할당한다.

전역 대 지역 할당(Global / Local Allocation)

전역 교체(Global Replacement)
- 전역 교체 는 프로세스가 교체할 프레임을 다른 프로세스에 속한 프레임을 포함한 모든 프레임을 대상으로 찾는 경우이다.
지역 교체(Local Replacement)
- 각 프로세스가 자기에게 할당된 프레임등 중에서만 교체될 희생자를 선택할 수 있는 경우이다.

지역 교체 방법에서는 프로세스에 할당된 프레임의 수는 변하지 않는다. 전역 교체 하에서는 한 프로세스에 할당된 프레임의 수는 바뀔수 있다.

일반적으로 전역교체가 지역교체 알고리즘보다 더 좋은 성능을 보이며, 더 많이 사용된다.

비균등 메모리 접근(Non Uniform Memory Access)

특정 보드 상의 CPU는 같은 보드의 메모리를 다른 보드의 메모리보다 더 빠르게 접근할 수 있다. 메모리 접근 시간이 현저하게 차이가 나는 시스템을 모두 비균등 메모리 접근(NUMA) 시스템 이라고 한다.

어느 페이지를 어느 프레임에 할당하느냐 하는 정책이 NUMA의 성능에 커다란 영향을 미친다.

스레싱

어떤 프로세스가 충분한 프레임을 할당받지 못했다고 가정한다. 활발하게 사용되는 페이지 집합을 지원해 줄 만큼 프레임을 충분히 할당받지 못한 프로세스는 페이지 부재가 바로 발생할 것이다. 이떄 페이지 교체가 필요하지만 이미 활발하게 사용되는 페이지들 만으로 이루어져 있으므로 어떤 페이지가 교체되는 바로 다시 필요해 질 것이다. 결과적으로 바로 바로 반복해서 페이지 부재가 발생하며 교체된 페이지는 얼마 지나지 않아 다시 읽어올 필요가 생긴다. 이러한 과도한 페이징 작업을 스레싱(Thrashing) 이라고 부르며, 이는 어떤 프로세스가 실제 실행보다 더 많은 시간을 페이징에 사용되고 있을 경우를 뜻한다.

스레싱의 원인

일반적으로 스레싱은 전역 교환 알고리즘(Global Replacement) 상에서 발생한다. 즉, 전역 교환 알고리즘 상에서 어떤 프로세스의 페이지인지에 대한 고려 없이 페이지 교체를 수행하려 하다보니, 페이지가 교체된 프로세스에게 필요한 페이지를 교체했을시 교체된 프로세스는 페이지 부재를 발생 시키고, 다시 다른 프로세스의 프레임을 가져올 것이다.

스레일은 심각한 성능 저하를 초래한다.

처음에는 다중 프로그래밍 정도가 높아지에 따라 CPU의 이용율도 높아진다. 증가속도가 감소하기는 하지만 최대값에 도달하기 까지 증가한다. 그러나 다중 프로그래밍 정도가 그 이상으로 더 커지면 스레싱이 일어나게 되고 CPU의 이용율은 급격히 떨어진다. 따라서 이 지점에서는 CPU의 이용룰을 높이고 스레싱을 중지시키기 위해 다중 프로그래밍 정도를 낮춰야 한다.


스레싱

스레싱은 지역 교환 알고리즘(Local Replacement) 이나 우선순위 교환 알고리즘(Priority Replacement) 을 사용하면 제한할 수 있다.

작업 집합 모델(Working Set Model)

스레싱 현상을 방지하기 위해서는 각 프로세스가 필요로 하는 최소한의 프레임 개수를 보장해야 한다.

각 프로세스가 필요로하는 최소한의 프레임 수를 알기 위해 사용되는 한가지 방법은 작업 집합 방법(Working Set Method) 이다.

작업 집합 방법 은 먼저 프로세스가 실제로 사용하고 있는 프레임의 수가 몇개인지를 알아보는 것에서 시작한다. 이 방법은 프로세스 실행의 지역성 모델(Locality Model) 을 기반으로 한다.

지역성 모델 이란 프로세스가 실행될 때에는 항상 어떤 특정한 지역에서만 메모리를 집중적으로 참조함을 의미한다. 여기서 지역(Locality) 란, 집중적으로 함꼐 참조되는 페이지들의 집합을 뜻한다.

한 프로그램은 여러개의 지역으로 구성되어 있고, 이 지역들은 서로 겹쳐질 수고 있다.


메모리 참조 패턴의 지역성(Locality)


작업 집합 모델

모든 프로세스 전체의 프레임 요구량이 시스템이 보유한 총 메모리의 크기보다 커지면 어떤 프로세스는 지역을 위한 충분한 프레임을 메모리에 가질 수 없기 때문에 스레싱을 유발한다.

페이지 부재 빈도(PFF, Page Fault Frequency)

페이지 부재 빈도 는 페이지 부재율의 상한과 하한을 정해놓고, 만약 페이지 부재율이 상한을 넘으면 그 프로세스에게 프레임을 더 할당해주고, 하한 보다 낮으면 그 프로세스의 프레임 수를 줄인다. 이렇게 함으로써 작업 집합 모델 보다 더 직접적으로 부재율을 관찰하고 조절함으로써 스레싱을 방지 할 수 있다.


페이지 부재 빈도


작업 집합과 페이지 부재율

메모리 사상 파일

open(), read(), write() 시스템 호출을 사용하여 디스크에 있는 파일을 순차적으로 읽을떄, 이러한 방식을 사용하면 파일이 매번 액세스될 떄마다 시스템 호출을 해야하고 디스크에 접근해야 한다. 아와 같이 하는 대신 디스크 입출력을 가상 메모리 기법을 적용하여 메모리 참조 방식 으로 대신 할 수 있다. 이러한 접근 방식을 메모리 사상 방식(Memory Mapping Method) 라고 하며, 프로세스의 가상 주소 공간중 일부를 관련된 파일인 메모리 사상 파일(Memory Mapped File) 에 할애하는 것을 말한다.


메모리 사상 파일


메모리 사상 입출력을 사용한 공유 메모리

커널 메모리의 할당

사용자 모드에서 수행중인 프로세스가 추가적인 메모리를 요구하면 커넣이 관리하는 가용 페이지 프레임에서 페이지들이 할당된다. 가용 리스트는 페이지 교체 정책들에 의해 물리 공간상에 여기 저기 흩어져 있는 페이지들로 채워진다.

사용자 프로세스가 단 한 바이트만 필요로하는 경우라면 프로세스가 한 페이지 프레임을 할당 받았으므로 내부 단편회가 발생한다. 그러나 커널 메모리는 보통 사용자 모드 프로세스에게 할당해 주기 위한 페이지 리스트와는 별도의 메모리 풀에서 할당 받는다. 이렇게 하는 이유는 다음과 같다.

커널은 다양한 크기의 자료구조를 위해 메모리를 할당받는다.
가상 메모리 인터페이스를 통하지 않고 물리 메모리에 직접 접근하는 특정 하드웨어 장치는 물리적으로 연속적인 메모리를 필요로 하는 경우가 있다.

커널 프로세스에 할당되는 메모리 관리 기법

버디 시스템(Buddy System)
- 물리적으로 연속된 페이지들로 이루어진 고정된 크기의 세그먼트로 부터 메모리를 할당한다.
- 메모리는 이 세그먼트로부터 2의 거듭제곱 할당기에 의해 2의 거듭제곱 단위로 할당 된다.
- 버디 시스템 의 장점중 하나는 합병(Coalescing) 이라고 부르는 과정을 통해 서로 인접한 버디들이 손쉽게 하나의 큰 세그먼트로 합쳐질 수 있다는 점이다.


버디 시스템에서의 할당

슬랩 할당(Slab Allocation)
- 슬랩(slab) 이라 불리는 하나 또는 그 이상의 연속된 페이지들로 구성된다.
- 캐시(cache) 는 하나 혹은 그 이상의 슬랩 들로 구성되어 있다.
- 각 커널 자료구조마다 하나의 캐시가 존재한다.
- 단편화에 의해 낭비되는 메모리가 없다.
- 메모리 요청이 빠르게 처리된다.


슬랩 할당

참고. operating system concepts(9E) - Abraham Silberschatz

OS - 가상메모리