메모리 관리·가상 메모리·페이지 교체

메모리 관리는 주소 변환·보호·할당과 회수를 수행한다. 연속 할당과 단편화, 페이징·세그먼테이션의 주소 계산, 가상 메모리의 페이지 부재·교체·스래싱을 원리와 계산으로 구분한다.

그림으로 확인하기

좌우로 이동해 그림을 확인하세요.그림 크게 보기

메모리 관리의 목적과 주소 개념

메모리 관리가 수행하는 일

운영체제의 메모리 관리 기능은 다음 질문에 답한다.

1. 어느 프로세스가 어떤 주소 범위를 사용할 수 있는가?
2. 가상 주소를 어느 물리 주소에 대응시킬 것인가?
3. 새 프로세스나 새 페이지에 어느 빈 공간을 배정할 것인가?
4. 물리 메모리가 부족할 때 무엇을 내보낼 것인가?
5. 읽기·쓰기·실행 권한을 어떻게 검사할 것인가?
6. 여러 프로세스가 같은 코드나 데이터를 안전하게 공유하게 할 것인가?

메모리 관리는 단순히 빈 RAM을 찾는 기능이 아니다. 주소 변환, 할당, 보호, 공유, 회수를 함께 다룬다.

논리 주소·가상 주소·물리 주소

• 논리 주소(logical address)는 프로그램과 CPU가 명령 실행 중 사용하는 주소를 가리키는 교과서 용어다.
• 가상 주소(virtual address)는 가상 메모리 체계에서 프로세스가 보는 주소다. 현대 운영체제 설명에서는 논리 주소와 거의 같은 문맥으로 쓰이는 경우가 많다.
• 물리 주소(physical address)는 실제 물리 메모리에서의 위치다.

CPU가 가상 주소 V를 만들면 메모리 관리 장치가 현재 프로세스의 변환 구조를 이용해 물리 주소 P를 구한다. 서로 다른 프로세스가 같은 가상 주소를 사용해도 서로 다른 물리 프레임에 매핑될 수 있다. 반대로 공유 메모리나 공유 라이브러리에서는 서로 다른 가상 주소가 같은 물리 프레임을 가리킬 수도 있다.

주소 바인딩 시점

주소 바인딩(address binding)은 프로그램의 주소를 실제 적재 위치와 연결하는 시점을 말한다.

가상 메모리와 동적 재배치를 사용하려면 실행 시간 바인딩이 필요하다. 이때 MMU가 주소 변환을 지원한다.

기준 레지스터와 한계 레지스터

단순한 연속 할당에서는 다음 두 값으로 보호와 재배치를 구현할 수 있다.

• 기준 레지스터(base register): 프로세스가 배치된 물리 메모리의 시작 주소
• 한계 레지스터(limit register): 프로세스가 사용할 수 있는 논리 주소 범위의 크기

논리 주소 L이 0 <= L < limit인지 검사한 뒤 다음처럼 변환한다.

물리 주소 = base + L

예를 들어 base=12000, limit=3000, 논리 주소가 2450이면 물리 주소는 14450이다. 논리 주소 3000은 유효하지 않다. 범위의 길이가 3000이라면 유효한 변위는 0~2999이기 때문이다.

메모리 관리 전략의 세 질문

전통적인 시험 분류에서는 메모리 관리 전략을 세 종류로 나눈다.

반입·배치·교체는 서로 다른 결정이다. 예를 들어 요구 페이징을 사용하면서 프레임 교체는 LRU 근사 방식으로 수행할 수 있다.

연속 메모리 할당

단일 연속 할당

가장 단순한 방식은 운영체제가 사용하는 영역과 한 사용자 프로세스 영역으로 메모리를 나누는 것이다. 구현은 단순하지만 여러 프로세스를 동시에 메모리에 두기 어렵고 메모리 이용률이 낮다.

고정 분할 할당

물리 메모리를 미리 여러 개의 고정 크기 분할로 나누고, 각 분할에 프로세스 하나를 배치한다.

• 같은 크기 분할을 사용할 수도 있고 서로 다른 크기 분할을 사용할 수도 있다.
• 동시에 상주할 수 있는 프로세스 수는 사용 가능한 분할 수에 제한된다.
• 프로세스가 어떤 분할보다 크면 적재할 수 없다.
• 프로세스보다 큰 분할에 넣으면 분할 내부의 남는 부분이 내부 단편화가 된다.

크기 16 KiB 분할에 13 KiB 프로세스를 넣으면 3 KiB가 남는다. 이 공간은 다른 프로세스가 사용할 수 없으므로 내부 단편화다.

가변 분할 할당

프로세스가 들어올 때 필요한 크기에 맞추어 연속 공간을 잘라 배정한다. 고정 분할보다 내부 낭비를 줄일 수 있지만, 프로세스의 생성과 종료가 반복되면 크기가 다른 빈 공간이 메모리 곳곳에 흩어진다.

가변 분할에서는 빈 공간 목록을 관리하고, 요청을 수용할 구멍(hole)을 선택한다.

알고리즘 이름의 best는 모든 요청 순서에서 가장 좋은 결과를 보장한다는 뜻이 아니다. 실행 시간과 단편화는 요청 크기·해제 순서·탐색 자료구조에 따라 달라진다.

배치 전략 계산 예제

초기 빈 공간 크기가 앞에서부터 100, 500, 200, 300, 600이고, 요청이 212, 417, 112, 426 순서로 들어온다고 하자. 각 요청은 선택한 구멍의 앞부분에 배치하고 남은 공간은 다시 빈 공간이 된다고 가정한다.

이 입력에서는 best-fit만 네 요청을 모두 수용하지만, 이를 일반 법칙으로 확대하면 안 된다. 다른 요청·해제 순서에서는 first-fit이나 다른 방식이 더 유리할 수 있다.

단편화·병합·압축

내부 단편화

내부 단편화(internal fragmentation)는 이미 할당된 블록 안에서 요청에 사용되지 않고 남은 공간이다. 고정 분할, 고정 크기 블록, 페이징의 마지막 페이지에서 발생할 수 있다.

예를 들어 페이지 크기가 4 KiB이고 프로세스의 실제 크기가 18 KiB라면 5페이지가 필요하다.

필요 프레임 수 = ceil(18 / 4) = 5
할당 크기 = 5 × 4 KiB = 20 KiB
마지막 페이지 내부 낭비 = 2 KiB

외부 단편화

외부 단편화(external fragmentation)는 사용 가능한 총공간은 충분하지만 여러 작은 빈 구간으로 흩어져 큰 연속 요청을 수용하지 못하는 상태다.

빈 공간이 100, 70, 90으로 나뉘어 있으면 총 260이 비어 있어도 크기 180의 연속 요청은 배치할 수 없다. 남은 공간은 할당 블록 밖에 있으므로 외부 단편화다.

병합과 압축

• 병합(coalescing)은 서로 인접한 빈 구간을 하나의 큰 빈 구간으로 합친다. 사용 중인 블록은 이동하지 않는다.
• 압축(compaction)은 사용 중인 블록을 실제로 옮겨 빈 공간을 한쪽에 모은다. 동적 재배치 지원이 필요하고, 이동 비용과 중단 시간이 발생한다.

페이징은 동일 크기 프레임 어디에나 페이지를 배치할 수 있으므로 사용자 프로세스의 일반적인 페이지 할당에서 외부 단편화를 피한다. 그러나 페이징도 마지막 페이지의 내부 단편화와 페이지 테이블 비용이 존재한다. 또한 운영체제 내부에서 큰 물리 연속 영역이 필요한 경우에는 물리 메모리 단편화 문제가 여전히 나타날 수 있다.

단편화 판별표

페이징과 주소 변환

페이지와 프레임

페이징은 다음 두 공간을 같은 크기의 블록으로 나눈다.

• 페이지(page): 가상 주소 공간의 고정 크기 블록
• 프레임(frame, page frame): 물리 메모리의 고정 크기 블록

한 프로세스의 연속된 가상 페이지들은 물리 메모리에서 서로 떨어진 프레임에 배치될 수 있다. 프로그램은 가상 주소가 연속되어 있다고 보지만, 페이지 테이블이 각 페이지를 실제 프레임에 연결한다.

주소 변환 공식

가상 주소를 A, 페이지 크기를 S라고 하면 다음과 같다.

페이지 번호 p = A // S
오프셋 d = A % S

페이지 테이블에서 페이지 p가 프레임 f에 대응한다면 물리 주소는 다음과 같다.

물리 주소 = f × S + d

페이지와 프레임의 크기가 같으므로 페이지 내부의 위치인 오프셋은 바뀌지 않는다.

주소 변환 예제

• 페이지 크기: 1024바이트
• 가상 주소: 2500
• 페이지 2의 프레임 번호: 7

페이지 번호 = 2500 // 1024 = 2
오프셋 = 2500 % 1024 = 452
물리 주소 = 7 × 1024 + 452 = 7620

2500 ÷ 1024의 몫은 페이지 번호이고 나머지는 오프셋이다. 프레임 번호 7을 가상 주소에 그대로 더하는 방식이 아니다.

비트 수 계산

페이지 크기가 2^d바이트이면 오프셋은 d비트다. 가상 주소가 m비트라면 페이지 번호는 m-d비트다.

예를 들어 32비트 가상 주소와 4 KiB 페이지를 사용하면 다음과 같다.

4 KiB = 4096 = 2^12바이트
오프셋 = 12비트
가상 페이지 번호 = 32 - 12 = 20비트
가상 페이지 수 = 2^20개

물리 메모리가 1 GiB이고 페이지 크기가 4 KiB라면 프레임 수는 다음과 같다.

1 GiB / 4 KiB = 2^30 / 2^12 = 2^18개 프레임

물리 주소가 30비트라면 프레임 번호 부분은 30-12=18비트다.

페이지 테이블 크기 계산

단일 단계 페이지 테이블에서 각 가상 페이지마다 페이지 테이블 항목(PTE) 하나가 필요하다고 가정한다.

• 가상 주소: 32비트
• 페이지 크기: 4 KiB
• PTE 크기: 4바이트

가상 페이지 수 = 2^(32-12) = 2^20
페이지 테이블 크기 = 2^20 × 4바이트 = 2^22바이트 = 4 MiB

이 값은 단일 단계 테이블이 전체 가상 주소 범위의 항목을 모두 가진다는 단순 가정의 결과다. 다단계 페이지 테이블은 사용하지 않는 큰 주소 범위의 하위 테이블을 만들지 않아 공간을 줄일 수 있다.

페이지 테이블과 TLB

페이지 테이블 항목

페이지 테이블 항목에는 구현에 따라 다음 정보가 들어갈 수 있다.

교재에 따라 valid/invalid 비트를 “프로세스 주소 공간에 속하는가”와 “현재 메모리에 있는가”의 의미로 혼용하기도 한다. 문제에서 비트의 정의를 먼저 확인해야 한다. 이 이론에서는 접근 자체의 유효성과 현재 물리 메모리 상주 여부를 구분한다.

TLB의 역할

변환 색인 버퍼(Translation Lookaside Buffer, TLB)는 최근 사용한 가상 페이지 번호와 프레임 번호의 대응을 보관하는 고속 캐시다.

주소 접근의 단순 흐름은 다음과 같다.

1. CPU가 가상 주소를 생성한다.
2. MMU가 TLB에서 가상 페이지 번호를 찾는다.
3. TLB 적중이면 저장된 프레임 번호를 사용한다.
4. TLB 미스이면 페이지 테이블을 탐색한다.
5. 페이지 테이블에서 상주한 유효 매핑을 찾으면 TLB를 갱신하고 접근을 계속한다.
6. 접근을 완료할 수 없는 상태이면 페이지 부재 예외를 발생시켜 운영체제가 처리한다.

TLB 미스는 페이지 부재와 같지 않다. TLB에만 없고 페이지 테이블에는 정상 매핑이 있을 수 있다. 반대로 페이지 테이블에서 상주하지 않은 페이지나 권한 위반을 발견하면 운영체제 처리가 필요하다.

유효 접근 시간 계산

다음 단순 모델을 가정한다.

• TLB 조회 시간: ε
• 메모리 접근 시간: t
• TLB 적중률: α
• 단일 단계 페이지 테이블
• TLB 조회와 메모리 접근이 순차적으로 일어남
• 페이지 부재는 제외

TLB 적중 시에는 TLB 조회 1회와 실제 데이터 접근 1회가 필요하다.

적중 시간 = ε + t

TLB 미스지만 페이지가 상주한 경우에는 TLB 조회, 페이지 테이블 접근, 실제 데이터 접근이 필요하다.

미스 시간 = ε + 2t

따라서 유효 접근 시간(EAT)은 다음과 같다.

EAT = α(ε + t) + (1-α)(ε + 2t)

ε=10ns, t=100ns, α=0.95라면 다음과 같다.

EAT = 0.95×110 + 0.05×210
    = 104.5 + 10.5
    = 115ns

실제 하드웨어에서는 TLB와 캐시의 병렬 조회, 다단계 페이지 워크 캐시, 큰 페이지 등이 영향을 준다. 계산 문제에서는 반드시 제시된 모델을 따른다.

페이지 크기의 상충 관계

페이지 크기가 클수록 무조건 빠르거나 작을수록 무조건 효율적인 것이 아니다. 작업의 접근 패턴과 하드웨어 특성에 따라 상충 관계가 있다.

세그먼테이션

세그먼트의 의미

세그먼테이션은 프로그램을 코드, 전역 데이터, 힙, 스택, 모듈처럼 논리적 의미가 있는 가변 길이 단위로 나눈다. 논리 주소는 일반적으로 다음 두 부분으로 표현한다.

(세그먼트 번호, 변위)

세그먼트 테이블 항목에는 기준 주소(base), 한계값(limit), 보호 정보 등이 들어간다.

세그먼트 주소 변환

세그먼트 번호 s로 항목을 찾고 변위 d가 범위 안인지 검사한다.

0 <= d < limit[s]
물리 주소 = base[s] + d

예를 들어 세그먼트 2의 base=4000, limit=1000일 때 (2,620)은 유효하며 물리 주소는 4620이다. (2,1000)은 유효하지 않다. 길이가 1000인 세그먼트의 마지막 유효 변위는 999다.

페이징과 세그먼테이션 비교

가상 메모리와 반입 전략

가상 메모리의 기능

가상 메모리는 프로세스가 물리 메모리의 실제 배치와 크기를 직접 관리하지 않도록 추상화한다.

• 각 프로세스에 독립적인 주소 공간을 제공한다.
• 필요한 페이지를 서로 떨어진 물리 프레임에 배치할 수 있다.
• 사용하지 않는 주소 범위에는 실제 프레임을 배정하지 않을 수 있다.
• 읽기·쓰기·실행 권한을 페이지 단위로 검사할 수 있다.
• 동일한 물리 페이지를 여러 프로세스가 통제된 방식으로 공유할 수 있다.
• 현재 필요한 부분만 상주시켜 물리 메모리보다 큰 주소 공간을 다룰 수 있다.

가상 메모리가 물리 RAM 자체를 늘리는 것은 아니다. 상주하지 않은 데이터는 파일, 스왑 영역, 실행 파일 같은 보조 저장장치에서 다시 가져오거나 필요 시 새로 초기화한다. 물리 메모리보다 지나치게 큰 활성 작업 집합을 사용하면 성능이 급격히 떨어질 수 있다.

요구 반입과 예상 반입

• 요구 반입(demand fetch, demand paging)은 실제 참조가 발생했을 때 페이지를 메모리로 가져온다. 불필요한 페이지를 미리 읽지 않지만 첫 접근에서 페이지 부재 지연이 발생한다.
• 예상 반입(prepaging, anticipatory fetch)은 곧 사용할 것으로 예상되는 페이지를 미리 가져온다. 예측이 맞으면 부재를 줄일 수 있지만 사용하지 않을 페이지를 읽어 I/O와 프레임을 낭비할 수 있다.

요구 페이징은 “페이지를 전혀 미리 적재하지 않는다”는 절대 규칙이 아니라, 기본적으로 참조를 계기로 상주시키는 정책을 말한다. 실제 시스템은 순차 읽기 예측 등 여러 최적화를 함께 사용할 수 있다.

스와핑과 페이징

“스왑을 사용한다”와 “모든 가상 메모리 페이지가 항상 디스크에 복사되어 있다”는 같은 말이 아니다. 파일에서 다시 읽을 수 있는 깨끗한 페이지는 별도의 스왑 복사본 없이 버릴 수 있고, 새 익명 페이지는 처음 접근할 때 0으로 초기화될 수 있다.

페이지 부재 처리

페이지 적중·부재·교체

• 페이지 적중(page hit): 필요한 페이지가 이미 물리 메모리에 상주하여 정상 접근한다.
• 페이지 부재(page fault): 현재 변환·상태로는 접근을 완료할 수 없어 운영체제의 예외 처리가 필요하다.
• 페이지 교체(page replacement): 유효한 페이지 부재를 처리해야 하지만 빈 프레임이 없을 때 기존 상주 페이지를 희생자로 선택한다.

따라서 페이지 부재가 발생했다고 항상 페이지 교체를 하는 것은 아니다. 빈 프레임이 있으면 새 페이지를 그 프레임에 적재하면 된다.

요구 페이징의 처리 흐름

상주하지 않은 유효 페이지를 참조했다고 가정하면 일반적인 흐름은 다음과 같다.

1. CPU가 가상 주소를 참조한다.
2. MMU가 TLB와 페이지 테이블을 확인한다.
3. 현재 접근을 완료할 수 없어 페이지 부재 예외가 발생한다.
4. 운영체제가 주소가 프로세스의 합법적인 범위이고 요청 권한이 맞는지 검사한다.
5. 잘못된 주소나 권한 위반이면 오류로 처리하고, 정상적인 비상주 페이지면 계속한다.
6. 빈 프레임을 찾는다.
7. 빈 프레임이 없으면 교체 알고리즘으로 희생 페이지를 선택한다.
8. 희생 페이지가 변경되었다면 보조 저장장치에 기록한다.
9. 희생 페이지의 기존 매핑과 관련 TLB 정보를 무효화한다.
10. 필요한 페이지를 저장장치에서 읽거나 새 페이지를 초기화한다.
11. 페이지 테이블을 새 프레임과 상태 정보로 갱신한다.
12. 중단된 명령을 다시 시작한다.

저장장치 I/O를 기다리는 동안 해당 프로세스는 대기하고 다른 프로세스가 CPU를 사용할 수 있다. “페이지 부재마다 반드시 현재 프로세스에서 다른 프로세스로 문맥 교환한다”는 식으로 단정해서는 안 되지만, I/O 대기 때문에 스케줄링 전환이 일어날 가능성이 크다.

참조 비트와 변경 비트

• 참조 비트(reference/accessed bit, R)는 페이지가 최근 접근되었음을 나타내는 데 사용한다. 읽기나 쓰기 접근에서 설정될 수 있다.
• 변경 비트(modified/dirty bit, M)는 페이지가 메모리에 들어온 뒤 쓰기로 수정되었음을 나타낸다.

깨끗한 희생 페이지는 원본 파일이나 저장장치에서 다시 읽을 수 있으면 단순히 버릴 수 있다. 변경된 페이지는 재사용 전에 내용을 저장해야 하므로 추가 쓰기 I/O가 필요하다. 그러나 “변경되지 않은 페이지는 페이지 부재 처리 비용이 0”이라는 뜻은 아니다. 새 페이지를 읽는 비용은 여전히 있을 수 있다.

페이지 부재를 포함한 접근 시간

정상 메모리 접근 시간이 100ns이고, 페이지 부재 처리 시간이 8ms라고 하자. 여기서는 8ms가 예외 처리와 I/O를 포함한 전체 부재 서비스 시간이라고 가정한다.

페이지 부재 확률을 p라고 하면 단순 평균은 다음과 같다.

EAT = (1-p) × 100ns + p × 8,000,000ns

p=0.000001, 즉 백만 번 접근당 한 번이라면 다음과 같다.

EAT ≈ 0.999999×100 + 0.000001×8,000,000
    ≈ 108ns

페이지 부재가 매우 드물어 보여도 저장장치 접근 시간이 메모리보다 훨씬 크기 때문에 평균 접근 시간에 큰 영향을 줄 수 있다. 문제에서 부재 서비스 시간이 정상 접근을 포함하는지 별도인지 확인해야 한다.

지역성·프레임 할당·교체 범위

지역성

프로그램은 모든 주소를 무작위로 똑같이 사용하지 않고 일정 기간 일부 주소에 접근을 집중하는 경향이 있다.

LRU는 시간 지역성을 이용한다. 큰 페이지나 미리 읽기는 공간 지역성이 높을 때 유리할 수 있다. 지역성이 약한 접근에서는 기대 효과가 줄어든다.

상주 집합과 프레임 할당

상주 집합(resident set)은 한 프로세스의 페이지 중 현재 물리 메모리에 있는 집합이다. 운영체제는 각 프로세스에 몇 개의 프레임을 줄지 결정해야 한다.

프로세스가 명령 하나를 완료하는 데 동시에 필요한 최소 페이지 수보다 적은 프레임을 받으면 반복 부재로 실행을 진행하기 어렵다. 최소 프레임 수는 명령어 구조와 주소 참조 수에 영향을 받을 수 있다.

지역 교체와 전역 교체

• 지역 교체(local replacement)는 페이지 부재를 낸 프로세스가 이미 받은 프레임 안에서 희생자를 고른다.
• 전역 교체(global replacement)는 다른 프로세스의 프레임도 희생 후보로 삼을 수 있다.

프레임 할당 방식과 교체 알고리즘을 혼동하지 않는다. “LRU를 사용한다”는 희생자를 고르는 기준이고, “지역 교체를 사용한다”는 후보 집합의 범위다.

스래싱·워킹 셋·페이지 부재 빈도

스래싱의 원인과 증상

스래싱은 프로세스들이 실제 계산보다 페이지를 내보내고 다시 읽는 데 대부분의 시간을 쓰는 상태다.

일반적인 악화 흐름은 다음과 같다.

1. 동시에 상주한 프로세스 수가 증가한다.
2. 각 프로세스가 받을 수 있는 프레임이 줄어든다.
3. 활성 지역을 유지하지 못해 페이지 부재가 급증한다.
4. 프로세스들은 I/O를 기다리고 CPU 이용률이 낮아진다.
5. 운영체제가 CPU 이용률 저하를 작업 부족으로 잘못 해석해 프로세스를 더 넣으면 상태가 악화된다.
6. 처리량과 응답성이 크게 떨어진다.

페이지 부재가 몇 번 발생했다는 사실만으로 스래싱이라고 하지 않는다. 부재가 지속적으로 매우 높고 시스템이 유용한 실행보다 페이지 이동에 매달리는 상태여야 한다.

워킹 셋

시점 t에서 최근 Δ개의 메모리 참조 또는 최근 Δ시간 동안 참조된 페이지 집합을 워킹 셋이라 한다.

W(t, Δ) = 최근 창 Δ 안에서 참조된 서로 다른 페이지의 집합

워킹 셋 크기는 프로그램의 현재 지역을 근사한다. 모든 프로세스의 워킹 셋 요구량 합을 D, 사용 가능한 총 프레임 수를 m이라고 하면 다음 관점으로 판단할 수 있다.

D = Σ |W_i(t, Δ)|
D > m 이면 전체 활성 집합을 동시에 수용할 수 없어 스래싱 위험이 큼

이때 한 프로세스를 중단하거나 일부를 스왑 아웃하여 다중 프로그래밍 정도를 낮추고, 남은 프로세스의 워킹 셋을 보호할 수 있다.

Δ가 너무 작으면 실제 지역에 필요한 페이지를 놓치고, 너무 크면 과거 지역까지 포함하여 프레임을 과다 요구할 수 있다.

페이지 부재 빈도 기법

페이지 부재 빈도(Page-Fault Frequency, PFF)는 프로세스의 부재율을 상한과 하한 사이에 유지하려는 방식이다.

• 부재율이 상한보다 높으면 프레임을 더 주거나 프로세스를 중단한다.
• 부재율이 하한보다 낮으면 일부 프레임을 회수할 수 있다.
• 모든 프로세스의 부재율이 높은데 남는 프레임이 없다면 다중 프로그래밍 정도를 낮춰야 한다.

워킹 셋은 최근 참조 페이지 집합 자체를 추적하고, PFF는 관찰된 페이지 부재율을 기준으로 조절한다.

스래싱 완화 방법

• 각 프로세스의 워킹 셋에 가까운 상주 집합을 보장한다.
• PFF를 관찰해 프레임을 동적으로 배분한다.
• 동시에 메모리에 둔 프로세스 수를 줄인다.
• 지역 교체로 한 프로세스의 과도한 부재가 다른 프로세스의 프레임을 침범하지 않게 할 수 있다.
• 접근 지역성을 높이도록 데이터 배치와 순회 순서를 개선한다.
• 단순히 FIFO를 LRU로 바꾸는 것만으로 프레임 절대 부족 문제를 항상 해결할 수는 없다.

페이지 교체의 공통 원칙

교체가 필요한 조건

페이지 교체는 다음 조건이 모두 성립할 때 필요하다.

1. 참조한 페이지가 현재 상주하지 않는다.
2. 접근 자체는 유효하며 페이지를 가져와야 한다.
3. 사용할 수 있는 빈 프레임이 없다.

빈 프레임이 있다면 희생 페이지를 고르지 않고 그 프레임에 적재한다.

계산 문제의 공통 규칙

페이지 교체 문제를 풀기 전에 다음 조건을 적는다.

• 참조 문자열
• 프레임 수
• 초기 프레임 상태
• 알고리즘
• 적중 시 순서·비트·빈도 갱신 규칙
• 동률 처리 규칙
• 쓰기 참조 여부와 변경 비트
• local/global 후보 범위

초기 프레임이 비어 있으면 처음 등장한 서로 다른 페이지는 상주할 때까지 모두 페이지 부재다. 같은 페이지가 이미 프레임에 있으면 적중이며 중복 적재하지 않는다.

깨끗한 페이지와 변경된 페이지

희생 페이지가 변경 비트 0이면 재사용 가능한 원본이 있을 때 쓰기 없이 프레임을 비울 수 있다. 변경 비트 1이면 변경 내용을 보조 저장장치에 기록해야 할 수 있다. 페이지 교체 알고리즘이 단순히 부재 수만 최소화하는 것과 I/O 비용까지 최소화하는 것은 완전히 같은 목표가 아니다.

OPT·FIFO·LRU

OPT 또는 MIN

최적 교체(OPT, MIN)는 현재부터 미래를 보아 다음 참조가 가장 늦거나 다시 참조되지 않을 페이지를 희생한다.

• 주어진 참조 문자열에서 최소 페이지 부재 수를 제공하는 비교 기준이다.
• 실제 실행 중에는 미래 참조를 정확히 알 수 없어 일반적인 온라인 구현 정책으로 사용할 수 없다.
• 시뮬레이션 결과가 OPT보다 적은 부재를 냈다면 계산이 잘못되었을 가능성이 높다.

FIFO

FIFO는 메모리에 가장 먼저 적재된 페이지를 희생한다.

• 큐로 구현하기 쉽다.
• 페이지가 적중해도 적재 순서는 갱신하지 않는다.
• 자주 사용하는 페이지라도 오래 전에 들어왔다면 교체될 수 있다.
• 프레임 수를 늘렸는데 오히려 부재 수가 증가하는 Belady 현상이 나타날 수 있다.

LRU

LRU는 현재 시점에서 가장 오랫동안 참조되지 않은 페이지를 희생한다.

• 과거의 최근 사용 이력을 이용해 시간 지역성을 근사한다.
• 페이지가 적중하면 최근 사용 순서를 갱신한다.
• 정확한 구현에는 참조 시각, 순서 스택 등 추가 비용이 필요하다.
• 실제 운영체제는 참조 비트와 목록 등을 이용해 LRU에 가까운 근사 정책을 사용할 수 있다.
• LRU는 스택 성질을 가지므로 프레임 수 증가로 페이지 부재가 증가하는 Belady 현상이 발생하지 않는다.

FIFO와 LRU를 가르는 짧은 예제

프레임 3개가 비어 있고 참조가 1, 2, 3, 1, 4라고 하자.

• 1,2,3을 적재한 뒤 1은 적중이다.
• 다음 4에서 FIFO는 가장 먼저 적재된 1을 내보낸다. 중간의 1 적중은 FIFO 순서를 바꾸지 않았다.
• LRU는 1이 방금 사용되었으므로 가장 오래 참조되지 않은 2를 내보낸다.

FIFO는 적재 시점, LRU는 마지막 참조 시점을 본다.

알고리즘 비교

LFU·NRU·Second Chance·Clock

LFU

LFU(Least Frequently Used)는 참조 횟수가 가장 적은 페이지를 희생한다.

• 적중할 때 해당 페이지의 빈도를 증가시킨다.
• 오랫동안 메모리에 있어 과거에 많이 사용된 페이지가 현재는 쓰이지 않아도 높은 빈도로 남을 수 있다.
• 이를 줄이기 위해 일정 주기마다 빈도를 감소시키는 에이징을 적용할 수 있다.
• 빈도가 같은 페이지가 여러 개면 FIFO, LRU, 작은 프레임 번호 등 동률 규칙을 문제에서 정해야 한다.

동률 규칙이 제시되지 않았는데 단일한 프레임 상태를 단정하면 안 된다. 다만 어떤 동률 선택을 해도 부재 수가 같은 입력도 있다.

NRU 또는 NUR

NRU(Not Recently Used)는 국내 일부 교재에서 NUR(Not Used Recently)로도 표기되며, 참조 비트 R과 변경 비트 M으로 페이지를 네 등급으로 나누고, 번호가 가장 낮은 비어 있지 않은 등급에서 희생자를 고른다.

참조 비트는 주기적으로 0으로 초기화하여 “최근”의 의미를 만든다. NRU는 정확한 참조 순서를 저장하지 않으므로 LRU의 근사 방식이지 LRU 자체가 아니다. 같은 등급 안의 선택 방법은 별도 규칙이 필요하다.

Second Chance

Second Chance는 FIFO 큐에 참조 비트를 결합한다.

1. FIFO 순서의 가장 오래된 후보를 본다.
2. 후보의 R=0이면 희생한다.
3. R=1이면 R을 0으로 만들고 즉시 희생하지 않은 채 다음 후보로 넘어간다.
4. R=0인 페이지를 찾을 때까지 반복한다.

최근 참조된 오래된 페이지에 한 번 더 기회를 주므로 순수 FIFO보다 지역성을 반영하지만 정확한 LRU는 아니다.

Clock

Clock 알고리즘은 프레임을 원형 목록으로 놓고 시계 바늘처럼 포인터를 이동시키며 Second Chance를 구현한다.

• 새 참조가 발생하면 해당 페이지의 참조 비트를 1로 설정한다.
• 교체가 필요할 때 포인터가 가리키는 페이지의 비트를 검사한다.
• R=1이면 0으로 지우고 포인터를 다음으로 이동한다.
• R=0이면 그 페이지를 교체하고 포인터를 다음 위치로 옮긴다.

Enhanced Second Chance는 (R,M) 조합을 이용해 최근 미참조이면서 깨끗한 페이지를 우선 찾는다. 구현에 따라 여러 번 순회하며 참조 비트를 지울 수 있다.

페이지 교체 계산과 Belady 현상

계산 조건

다음 참조 문자열과 빈 초기 프레임을 사용한다.

참조 문자열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

동일한 참조 문자열에서 계산한 부재 수는 다음과 같다.

이 입력에서는 프레임을 3개에서 4개로 늘렸을 때 FIFO 부재 수가 9에서 10으로 증가한다. 이것이 Belady 현상이다. LRU와 OPT는 프레임 수가 늘수록 기존 프레임 집합을 포함하는 스택 성질을 가지므로 이 현상이 발생하지 않는다.

한 입력에서 FIFO가 LRU보다 부재가 적게 나올 수도 있다. LRU가 모든 개별 참조 문자열에서 FIFO보다 항상 적은 부재를 보장하는 것은 아니다. 중요한 차이는 LRU가 지역성을 이용하고 Belady 현상이 없다는 성질이다.

FIFO 3프레임 추적

아래 프레임 상태는 가장 오래된 페이지 → 가장 최근에 적재된 페이지 순서의 FIFO 큐다.

페이지 부재는 총 9회다. 적중한 1, 2, 5는 FIFO 큐의 순서를 바꾸지 않는다.

FIFO 4프레임 추적

페이지 부재는 총 10회다. 프레임을 늘렸는데도 FIFO의 적재 순서가 참조 지역성과 맞지 않아 부재가 증가했다.

스택 알고리즘의 의미

프레임 수가 n일 때 상주하는 페이지 집합이 프레임 수 n+1일 때의 상주 집합에 항상 포함되는 알고리즘을 스택 알고리즘이라 한다. LRU와 OPT는 이 포함 관계를 만족하므로 프레임 수를 늘렸을 때 페이지 부재 수가 증가하지 않는다. FIFO는 이 포함 관계를 보장하지 않는다.