가상 메모리 part 1

등장 배경

가상 메모리는 1960년대 영국 맨체스터 대학교에서 제작된 아틀라스 컴퓨터 시스템에서 처음 등장했다. 메인 메모리보다 용량이 큰 기억 공간에 주소를 지정할 수 있게 해주는 메모리 관리 기법으로, 메인 메모리에서 사용자와 논리 메모리를 물리적으로 분리해 프로그래머에게 가상의 메모리 공간을 제공한다.

계층 구조

가상 메모리 시스템은 주로 페이징으로 구현된다. 메인 메모리를 더 효율적으로 사용할 수 있게 해 더 많은 작업을 메모리에 적재할 수 있고, 프로그래머가 메인 메모리의 제한된 용량과 중첩 사용 문제를 신경 쓰지 않아도 되게 해준다.

동시성

가상 메모리는 실제 프로세스 실행에 꼭 필요한 부분만 메인 메모리에 두고, 나머지는 2차 기억장치(디스크)에 저장한다. 가상 메모리 공간에 흩어져 있던 프로세스의 항목들이 2차 기억장치에 분산 적재되었다가, 프로세스가 실행되면서 필요한 만큼만 메인 메모리로 옮겨지는 방식이 가상 메모리 관리 기법을 가능하게 하는 이유다. 실제로 모든 프로그램이 항상 동시에 쓰이지는 않는다. 행렬, 리스트, 테이블 같은 자료구조는 실제로 쓰이는 크기보다 정의된 크기가 더 큰 경우가 많고, 문서 편집기에서 자주 쓰지 않는 복사·붙여넣기·잘라내기·삽입 같은 메뉴는 실제로 사용되는 하나만 메모리에 적재하고 나머지는 내보내도 무방하다.

가상 메모리의 장점과 단점

장점은 프로그래밍이 쉬워진다는 것이다. 공간 제약이 없어 중첩(오버레이)을 따로 작성할 필요가 없고, 공간이 부족해도 부분 적재가 가능해 더 많은 작업을 동시에 실행할 수 있어 프로세서 이용률과 처리율이 향상된다.

단점도 있다. 메모리와 디스크 공간 사이를 오가는 이동량이 늘어나 교체 공간을 확보해야 하고, 어느 시점에 어느 페이지를 적재하고 다시 내보낼지 정하는 페이징 알고리즘도 결정해야 하며, 페이지 부재를 처리할 방안도 함께 마련해야 한다.

주소 분리

가상 주소를 실제 물리적 주소로 변환하는 과정을 **사상(Mapping)**이라 하며, 이 변환 함수의 속도가 느리면 시스템 성능이 떨어진다. 프로그램 주소 공간(가상 주소)을 V, 메인 메모리 공간(실제 주소)을 R이라 하면, 사상 F에 의해 가상 메모리는 F: V → R로 정의된다.

동적 주소 변환(DAT, Dynamic Address Translation)

가상 메모리는 인위적 연속성이라는 성질을 가져서, 프로세스의 가상 주소 공간에서는 연속적인 주소라도 물리 주소 공간에서까지 연속적으로 저장할 필요가 없다. 덕분에 사용자는 프로그램과 데이터가 실제로 어디에 적재되는지 신경 쓸 필요가 없다.

메모리 관리 기법

여러 사용자가 메인 메모리를 공유하려면, 메인 메모리보다 큰 보조기억장치에 데이터나 프로그램을 저장하고 유지할 방법이 필요하다. 이를 위해 2단계 메모리 관리 기법을 쓴다. 1단계는 프로세스가 실행되며 참조하는 데이터를 저장하는 1차 기억장소, 즉 메인 메모리이고, 2단계는 제한된 메인 메모리에 다 들어가지 못하는 데이터를 저장하는 디스크 같은 대용량 2차 기억장치다.

블록 사상

사상을 바이트나 워드 단위로 하면 주소 사상 테이블(Address Mapping Table)을 유지하는 데 필요한 정보량이 지나치게 커진다. 이를 줄이기 위해 주소를 블록 단위로 처리하는 것을 블록 사상이라 한다.

2차원 주소 체계

블록 단위 가상 시스템은 2차원적인 주소 체계를 갖는다. 시스템은 각 프로세스의 블록 사상 테이블을 메모리에 유지하며, 시작점 레지스터(Block Table Origin Register)에 메모리 주소 a가 담겨 있다. 여기에 변위 값을 더해 실제 메모리 주소 r = b’ + d를 계산하는데, b’는 실제 메모리 주소 a + b 위치에 있는 블록 사상 테이블의 셀에 저장된 값이다.

가상 주소와 테이블 항목

가상 주소는 순서쌍 V = (p, d)로 표시하며, p는 페이지 번호, d는 페이지 변위다. 예를 들어 16비트 가상 주소가 1킬로바이트(1024바이트) 크기의 페이지를 쓸 경우, 가상 주소 1502(0000 0101 1101 1110)에서 최하위 10비트(0111011110)는 페이지 변위, 최상위 6비트(000001)는 페이지 번호를 나타낸다. 32비트 논리 주소가 4킬로바이트 페이지를 쓰는 경우에는 페이지 테이블 항목 하나당 4바이트(32비트)를 유지한다. 페이지는 블록 단위로 디스크에서 메인 메모리로 옮겨져 메인 메모리의 한 블록(페이지 프레임)에 자리 잡는데, 메인 메모리는 가상 페이지와 같은 크기의 페이지 프레임들로 나뉘어 있어 페이지가 사용 가능한 어떤 프레임에도 들어갈 수 있다.

페이지 테이블 항목 구성(PTE, Page Table Entry)

페이지 테이블 항목은 여러 플래그로 구성된다. P 플래그는 참조 페이지가 메인 메모리에 저장되어 있는지 나타내고, P/W 플래그는 쓰기·읽기 액세스 권한을 담는다. PWT, PCD 플래그는 하드웨어 캐시로 페이지(테이블)를 처리하는 방식을 나타내고, A 플래그는 페이지 프레임에 따른 페이징 단위 주소 적용을 나타낸다. D(W) 플래그는 페이지 수정 여부를, PAT 플래그는 페이지 테이블 속성을, G 플래그는 페이지 테이블 항목 확인을 나타내며, 나머지 비트는 시스템 프로그래머가 자유롭게 쓸 수 있다.

가상(논리) 주소에서 물리 주소로의 변환 과정

먼저 가상 주소의 페이지 번호(예: 0x2)로 페이지 테이블을 색인해 프레임 번호(예: 0x8)를 얻는다. 참조하는 페이지가 메인 메모리에 없다면 프로세스 수행이 불가능하다. 이어서 프레임 번호(0x8)와 페이지 변위를 결합해 메인 메모리의 실제 주소(물리 주소)를 구한다. 페이지 프레임 번호가 {1, 2, 3, … n}이라면, 실제 메모리 주소 r은 프레임 번호와 페이지 크기를 곱한 값에 변위 d를 더해 계산한다(r = 프레임 번호 × 페이지 크기 + d).

비 타당 비트

프로그램이 비 타당 비트로 표시된 페이지에 접근하지 않는 한 실행에는 영향이 없다. 하지만 그 페이지에 접근하면 페이지 부재가 발생해 운영체제로 트랩이 걸린다.

페이지 부재

프로세서가 만들어낸 가상(논리) 주소 V = (p, d)에서 페이지 번호 p는 주소 번역(페이지 테이블 레지스터) 과정을 거쳐 페이지 테이블의 해당 항목에 접근한다. 이때 그 페이지가 담긴 프레임이 메모리에 있는지 확인하고, 저장되어 있지 않다면 페이지 부재가 발생한다. 저장되어 있다면 프레임 번호와 변위를 결합해 물리 주소를 만들지만, 페이지 부재가 나면 해당 페이지가 디스크에 있다는 뜻이므로 그 페이지를 메모리로 가져온 뒤 명령을 다시 시작해야 한다.

순수 요구 페이징

순수 요구 페이징은 실제로 요구가 있을 때까지 페이지를 메모리에 들여놓지 않는 방법이다. 메모리에 실행할 프로세스의 페이지가 하나도 없어도 프로세스는 수행을 시작할 수 있다. 처음에는 최소한의 명령만으로도 페이지 부재를 계속 일으키다가, 페이지가 하나씩 메모리로 들어오면서 필요한 페이지가 모두 적재될 때까지 필요할 때마다 부재를 일으킨다. 수행에 필요한 모든 페이지가 메모리에 올라오면, 프로세스는 더 이상 페이지 부재 없이 수행을 이어간다.

장점으로는 다중 프로그래밍의 정도를 높이면서도 실제로 접근하지 않은 페이지는 적재하지 않아 메모리를 절약할 수 있고, 프로그램을 시작할 때 로딩 지연이 적으며, 적은 페이지만 읽으므로 초기 디스크 오버헤드도 적다. 보호 오류를 페이지 오류로 활용할 수 있어 별도의 하드웨어 지원이 필요 없고, 여러 프로그램이 수정되기 전까지 페이지를 공유할 수 있어(공유 페이지, 코드 공유) 자원을 더 절약할 수 있다. 메모리가 충분하지 않은 시스템에서도 대용량 프로그램을 실행할 수 있고, 예전의 중첩(오버레이) 기법보다 구현하기도 쉽다.

단점은 개별 프로그램이 페이지에 처음 접근할 때 약간의 지연이 생긴다는 점이다. 프리 페이징으로 마지막에 실행했던 몇 개의 페이지를 미리 불러와 성능을 개선할 수 있지만, 저비용·저성능 시스템에서는 페이지 대체를 지원하는 메모리 관리 장치가 아예 없는 경우도 있고, 전반적으로 메모리 관리(페이지 교체)가 복잡해진다.

페이징 성능

요구 페이징 환경에서 유효 액세스 시간을 따져보면, 메모리 액세스 시간(Ma)은 대개 1~200나노초(ns) 수준이다. 페이지 부재가 없으면 유효 액세스 시간은 메모리 액세스 시간과 같지만, 페이지 부재가 나면 보조기억장치에서 해당 페이지를 읽은 뒤 요구된 워드에 접근해야 하므로 시간이 훨씬 더 걸린다. 페이지 부재가 일어날 확률을 p(0 ≤ p ≤ 1)라 하자.

페이지 부재 시간 계산

유효 액세스 시간을 계산하려면 페이지 부재 시간을 먼저 알아야 한다. 페이지 부재가 나면 인터럽트 처리, 페이지 교체, 프로세스 재시작 과정을 거쳐야 한다. 인터럽트 처리와 프로세스 재시작은 수백 개의 명령어로 이루어져 있어 비교적 짧은 시간(약 1~1,000마이크로초)에 끝난다. 반면 페이지 교체 시간은 디스크 헤드의 탐색 시간(약 5ms), 지연 시간(약 3ms), 전송 시간(약 0.05ms)을 더해 대략 8ms 정도로 추산된다. 소프트웨어·하드웨어 처리 시간을 모두 합친 총 페이지 부재 처리 시간은 약 8ms다. 메모리 액세스 시간이 200ns, 평균 페이지 부재 처리 시간이 8ms이라면, 유효 액세스 시간은 (1-p) × 200 + p × 8,000,000으로 계산된다.

유효 액세스 시간의 감속

유효 액세스 시간은 페이지 부재율에 비례해 늘어난다. 1,000번 접근 중 한 번 페이지 부재가 나면 유효 액세스 시간은 약 8.2마이크로초(8,199.8ns)가 되어, 순수 메모리 액세스 시간(200ns)보다 40배나 느려진다. 만약 감속을 10% 미만으로 유지하고 싶다면, 약 399,990번(= 1/0.0000025) 접근 중 한 번 이하로 페이지 부재가 일어나야 한다. 페이지 부재율이 높을수록 유효 액세스 시간은 늘어나고 프로세스 수행 속도는 느려진다. 다행히 대부분의 페이지는 처음 참조될 때만 부재가 발생하고, 이후에는 메모리에 남아 있어 부재가 반복되지 않는다.

페이지 대치

페이지 부재 횟수와 프레임 개수의 관계는 참조 문자열(메모리를 참조하는 페이지들의 나열)을 이용해 분석할 수 있다.

선입선출(FIFO)

FIFO는 페이지가 메모리에 들어간 시간을 기준으로, 가장 오래된 페이지부터 우선 교체한다. 페이지 부재가 발생하면 제거할 페이지를 골라 보조기억장치로 옮기고 페이지 테이블의 타당/비타당 비트를 바꾼 뒤, 새로 들어온 페이지의 테이블 항목을 갱신해 FIFO 큐의 맨 끝에 삽입한다. 다만 FIFO에는 **벨레디의 변칙(Belady’s Anomaly)**이라는 문제가 있다. 할당되는 프레임 수를 늘려도 오히려 페이지 부재율이 높아지는 역설적인 현상이다.

최적 페이지 대치 알고리즘

이 알고리즘은 '앞으로 가장 오랫동안 사용하지 않을 페이지를 대치하라’는 원칙을 따르며, 모든 알고리즘 중 페이지 부재율이 가장 낮다. 고정된 프레임 수에서 이론적으로 가능한 가장 낮은 페이지 부재율을 보장하지만, 미래를 미리 알아야 하므로 실제로 구현할 수는 없고 다른 알고리즘의 성능을 비교하는 기준으로 쓰인다.

최근 최소 사용(LRU, Least Recently Used)

LRU는 과거의 데이터로 미래를 예측한다는 통계적 개념에 기반한다. 메모리의 지역성을 활용해 각 페이지에 마지막으로 사용된 시간을 연관시키고, 페이지를 교체할 때 가장 오래 사용되지 않은 페이지를 선택한다. 시간을 거슬러 올라가 찾는 최적 페이지 대치 알고리즘이라고도 볼 수 있다.

계수기를 이용한 순서 결정 방법

각 페이지 테이블 항목에 사용 시간 레지스터를 연관시키고, 프로세스에 논리 클록이나 계수기를 붙여 프레임의 순서를 결정하는 방법이다. 클록 레지스터의 값은 페이지 테이블의 사용 시간 레지스터로 복사되어, 각 페이지가 마지막으로 참조된 시간을 기록한다. 다만 페이지를 탐색하고 테이블 변화를 추적하는 부담이 크다는 점을 고려해야 한다. 이를 보완한 부가 참조 비트 알고리즘은 각 페이지에 8비트 정보를 두고 일정한 간격으로 참조 비트를 기록한다. 8비트 시프트 레지스터는 최근 8번의 기간 동안 페이지가 사용된 기록을 담는데, 값이 00000000이면 8번 동안 한 번도 사용되지 않았다는 뜻이고, 11000100은 01110111보다 더 최근에 사용되었다는 뜻이다.

시계(2차적 기회) 대치 알고리즘

시계 알고리즘은 FIFO를 기반으로 하며, LRU와 성능은 비슷하면서도 오버헤드는 더 적다. 각 프레임에 사용 여부를 나타내는 참조(사용) 비트를 두고, 페이지가 처음 프레임에 적재되거나 다시 참조될 때마다 이 비트를 1로 설정한다. 프레임들은 원형 버퍼(큐)로 구성되어 각자 포인터를 가지며, 페이지를 교체할 때 포인터는 교체된 프레임의 다음 프레임을 가리키도록 이동한다.

최소 사용 빈도수(LFU, Least Frequently Used)

LFU는 페이지마다 참조 횟수를 세는 계수기를 두고, 가장 적게 참조된 페이지를 교체한다. 다만 프로세스 초기에 한 페이지가 많이 쓰이다가 이후 전혀 쓰이지 않는 경우에는 효과가 떨어진다. 방금 들어온 페이지는 계수가 작다는 이유로 앞으로 쓰일 확률이 높다고 보고 교체 후보에서 제외하며, 오히려 가장 많이 쓰인(계수가 높은) 페이지를 교체하는 MFU 방식도 있다. 다만 LFU와 MFU 모두 구현 비용이 높고 최적 알고리즘에 비해 성능이 떨어져 실제로는 잘 쓰이지 않는다.

페이지 버퍼링(Page Buffering)

페이지 버퍼링은 FIFO의 성능 저하를 막기 위해, 교체 대상으로 선택된 페이지를 곧바로 내보내지 않고 잠시 메인 메모리에 유지하는 방법이다. 포인터 리스트로 페이지를 관리하며 대치 알고리즘 자체는 FIFO를 그대로 쓴다. 프로세스가 그 페이지를 다시 참조하면 오버헤드 없이 해당 프로세스의 작업에 곧바로 되돌릴 수 있어 페이지 부재가 해결되고, 변경된 페이지들을 리스트에 모아 일괄 처리하면 입출력 연산 횟수가 줄어 디스크 접근 시간도 아낄 수 있다.

알고리즘 비교 분석

베르(Baer, 1980)는 페이지 크기 256워드, 프레임 수를 6, 8, 10, 12, 14개로 바꿔가며 여러 대치 알고리즘의 성능을 비교했다. 프레임 수가 적을수록 알고리즘 간의 성능 차이가 두드러지게 나타났다.