16편에서는 연속 메모리 할당의 한계 — 외부 단편화와 “프로그램이 물리 메모리에 통째로 들어가야 한다”는 제약 — 을 확인했다. 가상메모리(virtual memory)는 이 두 문제를 동시에 해결하는 장치다. 4단계 시험에서는 개념 설명형 문항보다 페이지 테이블 주소 계산과 페이지 교체 알고리즘의 부재 횟수 계산이 압도적으로 많이 나오므로, 이 문서는 계산 과정에 가장 많은 비중을 둔다.

가상메모리가 필요한 이유

쉽게 말하면: 프로그램에게는 “메모리가 실제보다 훨씬 크고, 나만 쓰는 것”처럼 보이게 속이는 기술이다.

프로세스가 실행되려면 명령어와 데이터가 물리 메모리(주기억장치, main memory)에 있어야 한다는 것이 전통적인 전제였다. 하지만 이 전제에는 두 가지 현실적인 문제가 있다.

1. 프로그램 크기가 물리 메모리보다 클 수 있다. 16편에서 다룬 연속 할당 방식은 프로세스 전체가 메모리에 한 번에 올라가야 하므로, 물리 메모리보다 큰 프로그램은 아예 실행할 수 없다.
2. 여러 프로세스가 동시에 실행되면 물리 메모리를 나눠 써야 하므로, 각 프로세스가 쓸 수 있는 몫이 줄어든다. 멀티프로그래밍(multiprogramming, 여러 프로세스를 메모리에 동시에 올려 CPU 이용률을 높이는 방식)의 정도가 높아질수록 이 압박은 커진다.

가상메모리는 “프로세스가 실제로 참조하는 부분만 그때그때 물리 메모리에 올린다”는 아이디어로 이 문제를 해결한다. 프로세스는 자신만의 넓은 주소 공간(가상 주소 공간, virtual address space)을 가진 것처럼 동작하고, 실제로 그 주소가 물리 메모리 어디에 있는지 — 혹은 아직 메모리에 없는지 — 는 운영체제와 하드웨어가 뒤에서 처리한다.

MMU(Memory Management Unit, 메모리 관리 장치)는 CPU가 내는 가상 주소(virtual address)를 물리 주소(physical address)로 실시간 변환하는 하드웨어다. 이 변환표가 바로 다음 절의 페이지 테이블이다.

페이징 구조: 페이지·프레임·페이지 테이블

쉽게 말하면: 가상 주소 공간과 물리 메모리를 똑같은 크기의 조각으로 잘라, 조각 단위로만 대응시킨다.

가상메모리를 구현하는 대표적인 방법이 페이징(paging) 이다. 페이징은 주소 공간을 고정된 크기의 블록으로 나눠 다루는데, 이 블록의 이름이 양쪽에서 다르다.

• 페이지(page): 가상 주소 공간을 자른 고정 크기 블록.
• 프레임(frame): 물리 메모리를 자른, 페이지와 똑같은 크기의 블록.
• 페이지 테이블(page table): 어떤 페이지가 어떤 프레임에 들어가 있는지 기록한 매핑 표. 각 프로세스는 자신만의 페이지 테이블을 가진다.

페이지와 프레임의 크기가 같기 때문에(보통 4KB), 페이지를 프레임 어디에 넣어도 딱 맞아떨어진다는 것이 페이징의 핵심 성질이다. 이 성질 덕분에 외부 단편화(external fragmentation)가 원천적으로 사라진다 — 빈 프레임이 흩어져 있어도 페이지 하나씩 그 자리에 채워 넣으면 되기 때문이다. 다만 마지막 페이지가 프레임을 다 채우지 못하고 남는 공간인 내부 단편화(internal fragmentation) 는 여전히 발생할 수 있다.

가상 주소의 구조와 변환 계산

가상 주소는 두 부분으로 나뉜다.

• $p$ (페이지 번호): 이 주소가 몇 번째 페이지에 속하는지. 페이지 테이블에서 이 번호로 항목을 찾아 대응하는 프레임 번호 $f$를 얻는다.
• $d$ (오프셋, displacement): 그 페이지 안에서 몇 번째 바이트인지. 페이지 크기 안에서의 위치이므로 변환 후에도 값이 그대로 유지된다.

물리 주소는 페이지 테이블에서 찾은 프레임 번호 $f$와 오프셋 $d$를 그대로 이어 붙여 만든다.

비트 수로 직접 계산해 보자. 32비트 주소 체계를 쓰고 페이지 크기가 4KB($2^{12}$ 바이트)라고 하면,

페이지 크기가 $2^{12}$바이트라는 것은 한 페이지 안의 위치를 표현하는 데 12비트가 필요하다는 뜻이다($2^{12} = 4096$가지 위치).

전체 32비트 중 오프셋이 12비트를 쓰므로, 나머지 20비트가 페이지 번호에 배정된다. 즉 이 프로세스는 최대 $2^{20}$개(약 100만 개)의 페이지를 가질 수 있다.

결과 해석: 페이지 크기를 키우면(예: 4KB에서 16KB로) 오프셋 비트가 늘고 페이지 번호 비트가 줄어 페이지 테이블 항목 수는 줄어들지만, 대신 내부 단편화가 커질 여지가 생긴다. 시험에서는 “페이지 크기가 커지면 어떤 값이 커지고 어떤 값이 작아지는가”를 묻는 문항이 자주 나오므로, 이 상충 관계(trade-off)를 기억해 두어야 한다.

페이지 부재와 스래싱

쉽게 말하면: 필요한 페이지가 메모리에 없으면 디스크에서 가져와야 하고, 이 일이 너무 자주 일어나면 시스템이 일은 안 하고 페이지만 나르다 끝난다.

가상메모리는 “당장 필요한 페이지만 메모리에 올린다”는 요구 페이징(demand paging) 방식을 쓴다. 프로세스가 아직 메모리에 없는 페이지를 참조하면 페이지 부재(page fault) 가 발생하고, 운영체제는 다음 순서로 처리한다.

페이지 부재 처리는 메모리 접근(수십∼수백 나노초)에 비해 디스크 접근(수 밀리초, 약 10만 배 느림)이 압도적으로 오래 걸리기 때문에, 부재가 자주 발생하면 시스템 성능이 급격히 나빠진다.

스래싱(thrashing) 은 이 현상이 극단으로 치달은 상태를 가리킨다. 멀티프로그래밍 정도를 높이려고 너무 많은 프로세스를 동시에 메모리에 올리면, 각 프로세스가 실제로 쓸 수 있는 프레임 수가 줄어든다. 그러면 프로세스가 자기 작업에 꼭 필요한 페이지 집합(워킹셋, working set — 특정 시간 구간 동안 실제로 참조하는 페이지들의 집합)조차 메모리에 다 올리지 못해 페이지 부재가 끊임없이 일어나고, CPU는 실제 연산 대신 페이지를 나르는 데만 시간을 쓴다. 그 결과 CPU 이용률이 오히려 떨어지는 역설적인 상황이 벌어진다.

비유로 이해하기: 책상이 좁은데 책을 열 권씩 꺼내 놓고 작업하면, 책 한 권을 볼 때마다 다른 책을 책장에 도로 넣고 새 책을 꺼내 오는 데만 시간을 다 쓰게 된다. 정작 읽고 쓰는 일은 못 한다 — 이것이 스래싱이다.

운영체제는 워킹셋 모델이나 페이지 부재 빈도(page-fault frequency)를 관찰해, 스래싱 조짐이 보이면 일부 프로세스를 메모리에서 완전히 내보내(스와핑, swapping) 남은 프로세스에게 프레임을 더 배정하는 방식으로 대응한다.

페이지 교체 알고리즘

쉽게 말하면: 빈 프레임이 없을 때 “누구를 내보낼지” 정하는 규칙이며, 이 규칙에 따라 페이지 부재 횟수가 크게 달라진다.

같은 참조열(reference string, 프로세스가 순서대로 참조하는 페이지 번호의 나열)이라도 어떤 교체 알고리즘을 쓰느냐에 따라 부재 횟수가 다르다. 페이지 4개(A, B, C, D)를 참조하는 아래 참조열을 프레임 3개인 시스템에서 FIFO, OPT, LRU 세 가지로 직접 추적해 비교한다.

FIFO(First-In First-Out): 가장 먼저 들어온 페이지를 내보낸다

큐(queue) 구조로 프레임에 들어온 순서를 기억해 두었다가, 자리가 필요하면 가장 오래 있었던 페이지부터 내보낸다.

FIFO는 총 10번의 참조 중 8번 부재, 2번 적중(4번째, 5번째 참조)이다. FIFO는 구현이 단순하지만 “오래 있었다”는 사실이 “앞으로도 안 쓰인다”는 것을 보장하지 않는다는 약점이 있다 — 실제로 A는 6번째 참조 직후인 7번째에 다시 쓰이는데도 가장 먼저 내보내졌다.

OPT(Optimal, 최적 교체): 가장 먼 미래에 쓰일 페이지를 내보낸다

앞으로의 참조를 전부 미리 안다고 가정하고, 프레임 안에서 다음에 가장 늦게 다시 쓰이거나 아예 다시 쓰이지 않을 페이지를 내보낸다.

OPT는 총 5번 부재로 세 알고리즘 중 가장 적다. OPT는 이론적으로 증명 가능한 최소 부재 횟수를 내지만, 미래의 참조 순서를 미리 알아야 하므로 실제 운영체제에는 구현할 수 없다. 시험에서는 다른 알고리즘의 성능을 비교하는 기준선(baseline) 으로만 등장한다.

LRU(Least Recently Used): 가장 오랫동안 안 쓰인 페이지를 내보낸다

“최근에 쓰인 페이지는 곧 또 쓰일 가능성이 높다”는 지역성(locality, 최근 참조한 데이터나 그 근처를 다시 참조하는 경향)에 기반해, 가장 오래전에 참조된 페이지를 내보낸다. OPT처럼 미래를 볼 필요 없이 과거 기록만으로 판단할 수 있어 실제 시스템에 구현된다.

LRU는 총 6번 부재다. 같은 참조열에서 FIFO(8번)보다 적고 OPT(5번)에는 못 미치는, 실제 구현 가능한 알고리즘 중에서는 합리적인 성능을 보인다.

결과 해석: 같은 참조열, 같은 프레임 개수(3개)에서 OPT 5번 < LRU 6번 < FIFO 8번 순으로 부재가 많았다. 이 순서는 일반적인 경향이며 항상 성립하는 것은 아니지만, “미래를 안다(OPT)“가 가장 유리하고 “과거 사용 이력을 본다(LRU)“가 “그냥 들어온 순서만 본다(FIFO)“보다 대체로 낫다는 직관을 확인할 수 있다.

Clock(Second-Chance) 알고리즘

LRU를 정확히 구현하려면 참조마다 시각을 기록해야 해 오버헤드가 크다. Clock 알고리즘은 각 프레임에 참조 비트(reference bit) 1개만 두고 이를 근사한다.

• 페이지가 참조될 때마다 참조 비트를 1로 켠다.
• 교체가 필요하면 시계 바늘처럼 프레임을 순서대로 돌면서, 참조 비트가 0인 페이지를 만나면 즉시 내보낸다.
• 참조 비트가 1인 페이지를 만나면 비트를 0으로 끄고 “한 번의 기회”를 준 뒤 다음 프레임으로 넘어간다.

이 방식은 완전한 LRU만큼 정확하지는 않지만 하드웨어 부담이 훨씬 적어 실제 운영체제에서 널리 쓰인다.

Belady의 이상현상(Belady’s Anomaly)

일반적으로는 프레임 수를 늘리면 페이지 부재가 줄거나 최소한 그대로 유지될 것이라고 기대한다. 그런데 FIFO 알고리즘에서는 프레임 수를 늘렸는데도 오히려 페이지 부재가 늘어나는 경우가 있으며, 이를 Belady의 이상현상이라 부른다. LRU와 OPT는 이런 이상현상이 생기지 않는 것으로 증명된 스택 알고리즘(stack algorithm)에 속하지만, FIFO는 그렇지 않다. 시험에서는 “프레임을 늘렸는데 부재가 늘어날 수 있는 알고리즘은?”이라는 형태로 자주 출제된다.

유효접근시간(EAT) 계산

쉽게 말하면: 페이지 부재가 어쩌다 한 번씩만 나도, 그 한 번이 워낙 느리기 때문에 평균 접근시간을 크게 끌어올린다.

페이지 부재율 $p$가 주어졌을 때 평균적으로 메모리 접근 한 번에 걸리는 시간을 유효접근시간(EAT, Effective Access Time) 이라 하고 다음과 같이 계산한다.

• $p$: 페이지 부재율(page fault rate). 전체 메모리 참조 중 부재가 발생하는 비율.
• $m_a$: 정상적인 메모리 접근시간(memory access time).
• $t_{fault}$: 페이지 부재 한 번을 처리하는 데 걸리는 시간(디스크 입출력 포함).

메모리 접근시간이 100나노초(ns), 페이지 부재 처리 시간이 10밀리초(ms, 1ms = 1,000,000ns이므로 10ms = 10,000,000ns), 페이지 부재율이 0.1퍼센트($p = 0.001$)인 시스템의 EAT를 계산해 보자.

결과 해석: 부재율이 겨우 0.1퍼센트인데도 EAT는 정상 접근시간(100ns)의 약 101배인 약 10.1마이크로초(µs)로 뛰었다. 이는 페이지 부재 처리 시간이 정상 접근시간보다 약 10만 배 느리기 때문이다. 이 계산은 “부재율이 이 값 이하로 유지되어야 EAT가 목표치를 넘지 않는다”는 역산 문제로도 자주 출제되므로, 식을 $p$에 대해 정리하는 연습도 해 두어야 한다.

자주 틀리는 점

• 페이지와 프레임을 반대로 착각한다. 페이지는 가상 주소 공간의 조각, 프레임은 물리 메모리의 조각이다. “페이지 번호”는 페이지 테이블의 입력, “프레임 번호”는 그 출력이다.
• OPT를 실제 구현 가능한 알고리즘으로 착각한다. OPT는 이론적 하한선을 보여 주는 기준일 뿐, 미래를 알아야 하므로 실제 시스템에는 쓸 수 없다.
• 부재율만 보고 EAT를 과소평가한다. 부재율이 아무리 작아도 부재 처리 시간이 정상 접근시간보다 수만~수십만 배 크므로, 작은 부재율 차이도 EAT에 큰 영향을 준다.
• FIFO는 항상 LRU보다 나쁘다고 단정한다. 일반적인 경향일 뿐, 특정 참조열에서는 FIFO와 LRU의 부재 횟수가 같거나 드물게 역전될 수도 있다는 점에 유의해야 한다.

핵심 정리

• 가상메모리는 프로세스에게 실제보다 큰 주소 공간을 제공하고, 페이지 단위로 필요한 부분만 물리 메모리에 올린다(요구 페이징).
• 가상 주소는 페이지 번호 $p$와 오프셋 $d$로 나뉘며, 페이지 테이블이 $p$를 프레임 번호 $f$로 변환한다. 페이지 크기가 커지면 오프셋 비트는 늘고 페이지 번호 비트는 준다.
• 페이지 부재가 지나치게 잦으면 스래싱이 발생해 CPU 이용률이 오히려 떨어진다.
• 페이지 교체 알고리즘은 FIFO(구현 단순, 부재 많음), OPT(이론적 최소, 구현 불가), LRU(과거 이력 기반, 실제 구현), Clock(참조 비트로 LRU를 근사)로 나뉘며, 같은 참조열이라도 알고리즘에 따라 부재 횟수가 달라진다.
• FIFO에서는 프레임을 늘려도 부재가 늘어나는 Belady의 이상현상이 나타날 수 있다.
• 유효접근시간(EAT)은 부재율이 아주 작아도 부재 처리 시간이 워낙 크기 때문에 크게 늘어날 수 있다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제: https://bdes.nile.or.kr 
• 관련 심화 내용: /독학사/2단계/운영체제/14_virtual-memory-and-demand-paging, /독학사/2단계/운영체제/15_page-replacement-algorithms
• 관련 심화 내용: /독학사/2단계/컴퓨터구조/17_virtual-memory-and-page-faults