[운영체제] 7. 가상 메모리

1. 가상 메모리의 개념

시스템 상 메모리의 크기가 특정 프로세스를 연속 할당하기에는 부족한 경우가 있다. 이런 경우 메모리에 프로세스를 적재하기 위한 방법으로 제시된 것이 가상 메모리(virtual memory)의 개념이다.

 

가상 메모리의 핵심 개념은, 프로세스에 의해 참조되는 주소와 메모리에서 사용하는 주소를 분리하는 것이다. 그리고 프로그램 및 데이터에서 필요한 일부만 메모리에 적재함으로써 실행을 가능하도록 한다.

 

이 때, 실행 프로세스가 참조하는 주소를 가상 주소(virtual address) 라고 부르며, 실제 메모리에서 사용하는 주소를 실주소(real address) 또는 물리적 주소(physical address) 라고 한다.

 

또한 실행 프로세스가 참조하는 가상주소의 범위를 가상주소 공간(virtual address space) V 라고 하며, 특정 컴퓨터 시스템에서 사용 가능한 실주소 범위를 실주소 공간(real address space) R 이라고 한다.

 

프로세스 실행에 필요한 공간이 시스템 메모리 공간보다 큰 경우

 

프로세스는 가상주소를 참조하지만, 명령어가 실행되기 위해서는 실제로 메모리에서 실행되어야 하므로 프로세스 실행 시 가상주소를 실주소로 변환하는 과정이 필요하다. 이를 사상(mapping) 이라고 하며, 변환 함수로 표시한다.

 

 

사상에 의해 가상주소를 실주소로 변환하는 절차를 동적 주소 변환 (Dynamic Address Translation, DAT) 이라고 한다. 이를 이용하면 프로세스의 연속적인 가상주소가 실제 메모리에서도 연속적일 필요는 없다는 인위적 연속성(contiguity) 를 가지게 되므로, 사용자는 프로그램과 데이터의 위치를 염려할 필요가 없다.

 

 

2. 블록 단위 주소 변환

동적 주소 변환 방법은 주소 변환 사상표(address translation mapping table) 를 이용하는데, 주소 변환이 너무 작은 단위로 이루어 진다면 사상표 자체가 요구하는 기억장소가 커지게 되므로 정보를 블록 단위로 분류하여 관리한다.

 

블록은 블록의 번호 b 와 블록의 시작점으로부터의 변위(displacement) d로 구성된 순서쌍으로 지정된다.

 

블록의 크기가 커지면 사상기법이 요구하는 기억장치는 작아지지만, 블록이 메모리와 보조기억장치 사이를 이동하는데 필요한 전송시간이 길어지며, 메모리가 많이 소모되고, 메모리를 공유할 수 있는 프로세스 수를 제한시킨다.

 

블록의 크기가 동일하다면 그 블록을 페이지(page)라 부르고, 이런 가상메모리 구성을 페이징(paging) 기법이라고 한다. 블록의 크기가 다르다면 세그먼트(segment)라 하고, 이런 가상 메모리 구성을 세그먼테이션(segmentation) 기법이라고 한다. 두 기법을 혼용하기도 한다.

 

1. 페이징 기법

가상 메모리를 고정 크기 블록, 페이지(page) 단위로 나누어 관리하는 기법이다. 가상주소 v는 페이지 번호 p 와 변위 d 의 순서쌍 v(p, d) 로 이루어진다.

 

예를 들어 가상주소 v=(3, 8) 은 가상 메모리의 3번째 페이지에서 8바이트 떨어진 공간에 존재하는 위치를 나타낸다.

 

가상주소 v=(3, 8) 을 나타내는 예시

 

가상 주소를 실제 메모리에서도 참조하기 위해서는 메모리 영역도 가상 메모리와 동일하게 고정된 크기의 블록으로 나누어야 하며, 이 블록을 페이지 프레임(page frame) 이라고 부른다.

 

페이지를 페이지 프레임에 적재하는 것은 비어있는 임의의 프레임에 적재하며, 이를 페이지 사상표(mapping table) 을 통해 찾을 수 있도록 한다.

 

사상표를 직접 이용하여 동적 주소변환을 하는 것을 직접 사상 방식이라 한다.

 

직접 사상을 이용한 동적 주소 변환의 예시

 

또한 연관기억장치(저장된 값을 이용하여 데이터를 엑세스 하는 고속 메모리장치) 에 연관 사상표를 저장하고 동적 주소 변환을 하는 연관 사상 방식이 있다.

 

연관 사상을 이용한 동적 주소 변환의 예시

 

일반적으로 최근에 참조 된 페이지는 연관 사상표에 기록해두고 사용하며, 참조된 지 오래 된 페이지를 사용할 때는 직접 사상을 이용하여 연관 사상표에 기록 후 참조하는 방식으로 혼용하여 사용한다.

 

페이징 기법에서 프로세스 사이의 메모리 보호는 페이지 단위로 이루어진다. 또한 메모리가 동일 크기의 프레임으로 나누어져서 사용되므로 외부단편화는 발생하지 않지만, 내부 단편화가 발생할 수 있다.

 

2.세그먼테이션 기법

페이징 기법과 크게 다르지 않으나 페이징 기법에서 블록의 단위 역할을 하는 페이지 대신 세그먼트를 사용한다. 각 세그먼트의 크기는 다를 수 있으며 세그먼트를 메모리에 적재할때에는 충분한 크기의 메모리 영역에 놓으면 된다.

 

3. 페이징/세그먼테이션 혼용 기법

세그먼테이션 기법의 논리적 장점과 페이징 기법의 물리적 메모리 관리 측면의 장점을 모두 활용하기 위한 기법이다.

 

각 세그먼트를 다시 페이지 단위로 분할하고, 메모리도 페이지 프레임으로 분할하여 하나의 페이지만 페이지 프레임에 적재하는 방식이다.

 

3. 페이지 호출기법

1. 요구 페이지 호출기법

요구 페이지 호출기법(demand page fetch strategy)는, 한 프로세스의 페이지 요구가 있을 때 요구 페이지를 메모리에 적재하는 방식이다.

 

요구 페이지 호출기법은 어느 페이지를 메모리에 옮길지 결정하는데 오버헤드가 적고, 메모리에 옮겨진 페이지는 모두 프로세스에서 실제로 참조되고 있는 페이지임을 알 수 있다.

 

다만 실제로 사용이 되어야 하는 시점에 호출이 발생하기 때문에 프로세스의 실행 시간 도중 페이지의 부재가 발생한다.

 

2. 예상 페이지 호출 기법

예상 페이지 호출기법(prepaging) 이란, 현 시점에서 엑세스 되고 있지는 않지만 곧 사용될 것으로 예상되는 페이지를 미리 메모리에 옮기는 방법이다.

 

예상이 올바르게 이루어졌다면 프로세스 실행이 단절되지 않아 실행시간을 감소시킬 수 있다.

 

4. 페이지 교체기법

페이징 기법에서는 모든 페이지 프레임이 사용되고 있는 것이 일반적이다. 따라서 효율적인 프로세스 실행을 위해서는 사용 빈도가 적은 페이지를 적절한 타이밍에 교체해주어야 한다.

 

하지만 어떠한 페이지들은 효율적인 동작을 위해 교체가 일어나지 않아야 한다. 이러한 페이지로는 페이징을 위한 슈퍼바이저 코드 영역이나, 커널에 속하지 못한 보조기억장치 드라이버 영역, 시간을 맞춰 동작해야 하는 코드 영역, 데이터 버퍼 영역 등이 있다.

 

1. FIFO 페이지 교체

FIFO(First In First Out) 페이지 교체 기법은, 메모리에서 가장 오래 있었던 페이지를 교체하는 기법이다. 간단한 FIFO 큐를 통해 구현된다.

 

단순하게 들어온 시간에 의해 교체가 이루어지기 때문에 앞으로도 사용 빈도가 높은 페이지를 교체할 가능성이 있다.

 

해당 기법의 가장 큰 단점은 Belady의 이상현상(anomaly)이 일어난다는 것이다. 이는 프로세스에 더 많은 수의 페이지 프레임을 할당할 경우 오히려 페이지 부재가 더 많이 발생할 수 있는 문제이다.

 

2. LRU 페이지 교체

LRU(Least Recently Used) 페이지 교체기법은 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체하는 전략이다.

 

LRU 페이지 교체기법은 두가지 방법으로 구현될 수 있는데, 첫 번째는 각 페이지가 참조될 때 마다 시간을 기록하는 방법과, 리스트를 이용하는 방법이다. 리스트를 이용하는 경우 가장 최근에 참조되는 페이지를 선두의 인덱스로 옮기고, 교체가 필요한 경우 가장 후미의 인덱스 페이지가 교체 대상이 된다.

 

LRU 기법은 국부적 경험에 의존하기 때문에 최적화 원칙에 근사한 선택을 할 수 있지만, 판단이 맞지 않는 상황도 존재할 수 있다. (예: 3개의 페이지 프레임이 존재하고, 4개의 페이지가 루프되는 경우)

 

또한 LRU 기법은 시간을 기록하거나 리스트를 유지하는 등 오버헤드가 크므로 자주 사용되지 않는 기법이다.

 

3. LFU 페이지 교체

LFU(Least Frequently Used) 페이지 교체기법은, 참조된 횟수가 가장 적은 페이지를 교체하는 방법이다.

이 페이지 또한 국부적 경험에 의존하여, 좋지 않은 결과를 유발할 수 있다. 예를 들면 많이 사용되었지만 더 이상 사용되지 않는 페이지는 교체 대상에서 제외되고, 자주 사용될 예정이지만 가장 최근에 호출되어 참조 횟수가 적은 페이지는 즉시 교체대상이 될 수 있다.

또한 LRU 기법과 마찬가지로 페이지 호출 횟수를 관리하여야 하므로 오버헤드가 크다.

 

4. NUR 페이지 교체

NUR(Not Used Recently) 페이지 교체기법은 참조와 수정 여부로 페이지를 구분하여 관리하는 기법이다. LRU와 유사하지만 적은 오버헤드로 적절한 성능을 낼 수 있어 실제로 자주 쓰이는 기법이다.

 

각 페이지당 2개의 하드웨어 비트인 참조 비트(referenced bit) r과 수정 비트(modified bit) m을 두고 각각 참조, 수정이 일어나는 경우 해당 비트를 변경한다.

 

페이지 교체가 필요한 경우에는 참조와 수정이 일어나지 않은 순서대로 호출하여 교체한다.

 

5. 2차 기회 페이지 교체

2차 기회 페이지 교체기법은 FIFO 페이지 교체기법을 보완하여 참조 비트를 활용한다. 이는 가장 자주 사용하던 페이지라도 교체 대상으로 결정할 수 없더록 보완하는 기법이다.

해당 교체기법은 다음과 같은 알고리즘을 따른다.

1. FIFO 큐의 선두 항목을 꺼내 참조 비트를 조사
2. 참조 비트가 0 이면 그 프레임을 교체 대상으로 선택
3. 참조 비트가 1 이면 0 으로 수정 후 FIFO 큐의 맨 뒤로 보냄

 

6. 클럭 페이지 교체

클럭 페이지 교체기법(clock page replacement) 는 2차 기회 알고리즘의 변형으로 2차 기회 알고리즘의 FIFO 큐를 원형 큐로 수정 한 기법이다.

 

2차 기회 알고리즘에서 페이지가 두 번째 기회를 얻거나 새로운 페이지가 들어올 때 마다 데이터의 이동이 일어나는 오버헤드를 최소화 하기 위해 원형 큐를 이용한다.

 

7. 프로세스별 페이지 집합 관리

프로세스마다 메모리에 유지해야 하는 페이지의 집합이 적을 경우, 적재할 수 있는 프로세스는 많아져서 시스템 처리량이 증대될 수 있다.

 

하지만 각 프로세스 별로 페이지 부재가 자주 발생하여 프로세스 별 성능은 저하될 수 있다.

이러한 성질에 기반하여 각 프로세스별 페이지 집합을 관리하기 위한 두가지 알고리즘이 있다.

 

 

1) 워킹세트 알고리즘

워킹세트(working set) 는 가상 메모리 관리기법에서 하나의 프로세스가 자주 참조하는 페이지 집합을 나타낸다.

 

하나의 프로세스가 효율적으로 실행되기 위해 시스템은 워킹세트를 모니터링 하여 워킹세트 크기에 충분한 프레임을 할당하여야 한다.

 

 

2) PFF 알고리즘

페이지 부재율(page fault rate)은 페이징 기법 환경에서 프로세스가 얼마나 잘 실행되는가의 한 척도를 나타낸다.

 

따라서 부재가 너무 자주 일어나는 프로세스는 너무 적은 페이지 프레임을 가지고 있다고 가정하며, 너무 적은 부재가 나타나는 프로세스는 너무 과한 페이지 프레임을 가지고 있다고 가정한다.

 

PFF 알고리즘은 페이지 부재 빈도에 대한 상한과 하한을 두고, 프로세스 별 페이지 부재 빈도를 측정하여 상한보다 높아지면 상주 페이지 세트를 늘리고, 하한보다 낮아지면 호출되지 않았던 페이지를 모두 제거한다.