Chapter 10 · Virtual Memory I

① CPU가 가상 주소를 생성한다. 가상 주소는 상위 비트의 VPN(virtual page number)과 하위 비트의 offset으로 나뉜다. (예: 32비트 가상 주소, 4KB page → VPN 20비트 + offset 12비트)

② VPN을 현재 프로세스의 page table에 대한 인덱스로 사용하여 해당 PTE를 읽는다.

③ PTE의 valid bit가 valid이면 PTE에서 PFN(page frame number)을 추출한다. invalid이면 page fault가 발생한다.

④ 물리 주소 = <PFN :: offset>. PFN을 물리 주소의 상위 비트에, 원래 offset을 하위 비트에 그대로 붙여 최종 물리 주소를 완성한다.

PTE는 일반적으로 다음 필드로 구성된다.

• valid bit (V): PTE가 유효한지 나타낸다. 매 가상 주소 참조 시 검사된다. invalid이면 page fault.
• reference bit (R): 해당 page에 읽기 또는 쓰기가 발생하면 설정된다. page replacement 알고리즘에서 활용된다.
• modify bit (M, dirty bit): 해당 page에 쓰기가 발생하면 설정된다. swap out 시 dirty이면 디스크에 기록해야 하고, clean이면 그냥 버린다.
• protection bits (Prot): 해당 page에 허용된 연산(read-only, read-write, execute-only 등)을 제어한다.
• PFN: 매핑된 물리 frame 번호.

① CPU가 가상 주소를 참조할 때 해당 PTE의 valid bit가 invalid이면 trap이 발생하여 OS의 page fault handler로 제어가 넘어간다.

② OS는 해당 주소가 프로세스의 유효한 가상 주소 공간 내에 있는지 검사한다. 범위를 벗어나면 프로세스를 종료(illegal access)한다.

③ invalid PTE에 저장된 swap file 위치 정보를 통해 디스크에서 해당 page의 위치를 파악한다.

④ 빈 frame을 확보한다. 빈 frame이 없으면 page replacement 알고리즘으로 희생(victim) page를 선택하고 evict한다 (dirty이면 swap file에 write back).

⑤ 디스크 swap file에서 해당 page를 확보한 frame으로 읽어온다(디스크 I/O).

⑥ page table의 PTE를 갱신하여 새 PFN을 기록하고 valid bit를 valid로 설정한다.

⑦ page fault를 일으킨 명령을 처음부터 재시작(restart)한다.

장점

• 물리 메모리 할당이 쉽다: 빈 frame 목록에서 꺼내기만 하면 된다.
• external fragmentation이 없다: 모든 단위가 고정 크기이기 때문이다.
• page 단위 swap out이 쉽다: 모든 chunk가 같은 크기이며 valid bit로 swap out 여부를 감지한다.
• page 보호·공유가 쉽다.

단점 및 해결책

• internal fragmentation: 프로세스가 정확한 page 배수만큼 메모리를 사용하지 않아 마지막 page 내 낭비 발생. 해결책: page 크기 최적화.
• 메모리 참조 오버헤드(성능): 주소 조회마다 page table 참조 + 실제 메모리 = 2회 참조. 해결책: TLB(하드웨어 캐시).
• page table 공간 오버헤드: 32비트 주소 + 4KB page → 2²⁰개 PTE × 4B = 4MB/프로세스. 프로세스 25개면 100MB. 해결책: multi-level page table, inverted page table 등.

Segmentation은 메모리를 코드·스택·힙 같은 논리적 단위(segment)로 나누는 기법이다. 가상 주소는 <segment# :: offset> 형태이며, 각 segment는 독립적으로 크기를 조절할 수 있다.

하드웨어는 segment table로 지원한다. 각 항목에는 base(물리 시작 주소)와 limit(크기)이 있다. 주소 변환 시 offset이 limit보다 작은지 확인한 후 base + offset으로 물리 주소를 계산한다. limit 초과 접근 시 protection fault.

단편화 비교

• Paging: 고정 크기 frame을 사용하므로 external fragmentation이 없다. 대신 프로세스가 page 배수만큼 사용하지 않으면 마지막 page 내에 낭비가 생기는 internal fragmentation이 발생한다.
• Segmentation: 가변 크기 segment를 할당·해제하면 물리 메모리 사이사이에 사용할 수 없는 작은 빈 공간들이 생기는 external fragmentation이 발생한다. segment 내부에서는 필요한 만큼만 사용하므로 internal fragmentation은 없다.

Demand paging이 실용적인 근본 이유는 locality이다.

• temporal locality: 최근에 참조한 위치는 가까운 미래에 다시 참조될 가능성이 높다.
• spatial locality: 최근에 참조한 위치 근처도 곧 참조될 가능성이 높다.

locality 덕분에 한 번 메모리에 적재된 page는 이후 여러 번 재사용된다. 따라서 page fault는 비교적 드물게 발생하고, 전체 평균 메모리 접근 시간이 허용 가능한 수준으로 유지된다.

"demand" paging이라는 이름은 프로세스가 실제로 page를 요구(demand)할 때, 즉 처음 접근할 때만 메모리에 올린다는 의미이다. 프로세스 시작 시 모든 PTE의 valid bit가 false이므로 첫 명령 실행부터 cold fault가 발생하며, 실제로 필요한(demanded) page만 순차적으로 적재된다.

Segmentation with paging은 segmentation과 paging을 결합한 하이브리드 기법이다. IA-32(x86) 아키텍처가 대표적으로 지원한다.

동작 원리

• segmentation으로 코드·데이터·힙·스택 등을 논리 단위로 관리한다. segment는 보통 크기가 크며 논리적 보호·공유 이점을 제공한다.
• 각 segment는 고정 크기 page로 다시 분할된다. segment가 "pageable"해진다.
• segment 전체를 메모리에 올리는 대신 필요한 page 부분만 이동시킨다.

external fragmentation 제거 이유

순수 segmentation에서는 가변 크기 segment를 물리 메모리에 배치할 때 크기가 들쭉날쭉해 external fragmentation이 생긴다. 하지만 segmentation with paging에서는 segment를 고정 크기 page로 분할하고, 물리 메모리는 항상 고정 크기 frame 단위로 할당한다. 따라서 빈 frame이 있는 한 항상 할당할 수 있고 외부 단편화가 발생하지 않는다.

프로그래머 투명성

• Paging: 투명(yes). 가상 주소 공간은 프로그래머에게 0부터 N까지의 연속 공간처럼 보이고 page 경계는 의식할 필요 없다.
• Segmentation: 투명하지 않음(no). 프로그래머(또는 컴파일러)가 segment 경계를 인식해야 하며 가상 주소가 <segment#::offset> 형태이다.

코드·데이터 별도 보호

• Paging: page 단위 protection bit가 있지만 논리적 코드/데이터 경계와 page 경계가 일치하지 않을 수 있어 제한적.
• Segmentation: code segment는 read-only/execute, data segment는 read-write 등으로 segment 수준에서 명확하게 보호 가능.

단편화 유형

• Paging: internal fragmentation (마지막 page의 미사용 공간).
• Segmentation: external fragmentation (가변 크기 할당·해제로 인한 조각난 빈 공간).

발명 목적

• Paging: 큰 선형 가상 주소 공간을 효율적으로 제공하기 위해.
• Segmentation: 논리적으로 독립된 주소 공간 — 공유와 보호를 용이하게 하기 위해.