운영체제 메모리 단원 통합 확장 설명 - 책처럼 읽는 버전
운영체제 메모리 단원 통합 확장 설명 - 책처럼 읽는 버전
이 문서는 기존 Obsidian에 정리된 OS 메모리 수업 노트 10개를 바탕으로, 하나의 긴 흐름으로 다시 풀어 쓴 통합 설명본이다. 목표는 책을 읽듯이 메모리 단원의 큰 구조를 이해하는 것이다.
이 문서를 읽는 방법
메모리 단원은 처음 보면 용어가 너무 많다.
- logical address
- physical address
- MMU
- relocation register
- limit register
- contiguous allocation
- segmentation
- paging
- page table
- TLB
- hierarchical page table
- virtual memory
- demand paging
- page fault
- page replacement
- thrashing
- copy-on-write
- mmap
- buddy system
- slab allocator
이 용어들을 따로따로 외우면 굉장히 흩어진 지식처럼 느껴진다.
그런데 사실 메모리 단원 전체는 하나의 질문으로 이어진다.
여러 프로그램이 동시에 실행될 때, OS는 한정된 물리 메모리를 어떻게 안전하고 효율적으로 나누어 줄 것인가?
이 질문을 조금 더 쪼개면 다음 흐름이 된다.
1. 프로세스가 보는 주소와 실제 RAM 주소는 왜 다른가?
2. 주소를 어떻게 변환할 것인가?
3. 여러 프로세스를 물리 메모리에 어떻게 배치할 것인가?
4. 배치 방식이 느리면 어떻게 빠르게 만들 것인가?
5. page table이 너무 커지면 어떻게 줄일 것인가?
6. 물리 메모리가 부족하면 어떻게 할 것인가?
7. 필요한 page만 올리는 virtual memory는 어떻게 가능한가?
8. page fault가 너무 많아지면 어떤 일이 생기는가?
9. OS는 이 구조를 이용해 어떤 최적화를 하는가?
10. 커널 자신이 쓰는 메모리는 어떻게 관리하는가?
Part 1. 메모리 문제는 어디서 시작되는가
1. 메모리는 단순하지만, 메모리 관리는 단순하지 않다
RAM 자체만 보면 메모리는 꽤 단순한 장치다.
주소를 주면 그 위치의 값을 읽거나 쓴다.
address 1000 -> value 읽기
address 1000 <- value 쓰기
메모리 장치 자체는 “이 주소가 누구 것인지”, “이 프로세스가 여기 접근해도 되는지”, “이 값이 코드인지 데이터인지”를 모른다.
메모리는 그냥 주소와 값을 다룬다.
그런데 운영체제 입장에서 메모리는 훨씬 복잡한 자원이다. 왜냐하면 한 컴퓨터 안에서 여러 프로세스가 동시에 실행되기 때문이다.
예를 들어 브라우저, 카카오톡, IDE, 음악 플레이어, 터미널이 동시에 떠 있다고 하자.
각 프로그램은 자기만의 메모리 공간이 있는 것처럼 실행된다. 브라우저는 자기 코드와 데이터가 있고, IDE도 자기 코드와 데이터가 있다. 그런데 실제 RAM은 하나다.
즉, 현실은 이렇다.
실제 물리 메모리 RAM 하나
[ OS ][ browser ][ IDE ][ messenger ][ music ][ free ... ]
하지만 각 프로세스는 이렇게 생각하고 싶어 한다.
나는 나만의 메모리 공간을 가진다.
주소는 0번부터 시작한다.
내 코드, 내 데이터, 내 heap, 내 stack이 있다.
여기서 운영체제 메모리 관리의 핵심 문제가 시작된다.
프로세스에게는 자기만의 깨끗한 주소 공간을 주는 것처럼 보이게 하면서, 실제로는 하나의 물리 메모리를 여러 프로세스가 안전하게 나눠 써야 한다.
2. logical address와 physical address
이 문제를 이해하려면 먼저 주소가 두 종류로 나뉜다는 것을 받아들여야 한다.
Logical address
Logical address는 CPU가 프로그램을 실행하면서 만들어 내는 주소다.
프로그램 입장에서는 이 주소가 자기 메모리 주소다.
예를 들어 어떤 프로그램이 변수 x를 읽는다고 하자.
프로그램은 대략 이런 식으로 동작한다.
내 주소 공간의 120번 위치에 있는 값을 읽어라.
여기서 120은 logical address다.
이 주소는 “실제 RAM의 120번 칸”이라는 뜻이 아니다. “이 프로세스의 주소 공간 안에서 120번 위치”라는 뜻이다.
Physical address
Physical address는 실제 RAM에서의 주소다.
RAM의 어느 칸에 접근할 것인지를 나타낸다.
실제 RAM의 84320번 위치
실제 RAM의 90112번 위치
프로세스가 보는 logical address와 실제 RAM의 physical address는 다를 수 있다.
오히려 실행 시간에는 다른 것이 정상이다.
CPU가 만든 logical address
↓
주소 변환
↓
physical address
↓
RAM 접근
3. 왜 둘을 분리해야 하는가
처음에는 이렇게 생각할 수 있다.
그냥 프로그램이 실제 RAM 주소를 직접 쓰면 안 되나?
안 된다.
이유는 크게 세 가지다.
1. 프로그램이 어디에 올라갈지 미리 알 수 없다
프로그램을 컴파일할 때는 그 프로그램이 실제 RAM의 어디에 올라갈지 모른다.
오늘은 RAM의 10000번부터 올라갈 수도 있고, 내일은 30000번부터 올라갈 수도 있다. 다른 프로그램이 먼저 메모리를 쓰고 있으면 위치가 바뀐다.
따라서 프로그램 코드 안에 physical address를 박아 넣으면 유연성이 사라진다.
2. 프로세스마다 자기 주소 공간을 독립적으로 가져야 한다
프로세스 A도 주소 1000을 쓸 수 있고, 프로세스 B도 주소 1000을 쓸 수 있다.
하지만 둘의 주소 1000은 같은 physical address를 의미하면 안 된다.
Process A logical 1000 -> physical 50000
Process B logical 1000 -> physical 82000
이렇게 해야 각 프로세스가 서로를 침범하지 않는다.
3. 보호가 필요하다
프로세스가 OS 영역이나 다른 프로세스 영역을 마음대로 읽고 쓸 수 있으면 시스템은 무너진다.
따라서 OS는 “이 프로세스가 접근해도 되는 주소 범위인가?”를 검사해야 한다.
주소 변환은 단순히 주소를 바꾸는 작업이 아니라 보호 기능과도 연결된다.
4. MMU는 왜 필요한가
MMU는 Memory Management Unit이다.
CPU가 만든 logical address를 physical address로 바꾸는 하드웨어 장치라고 이해하면 된다.
CPU
logical address 생성
↓
MMU
logical -> physical 변환
↓
Memory
physical address 접근
중요한 점은 이 변환이 실행 중에 매우 자주 일어난다는 것이다.
프로그램은 명령어를 가져올 때도 메모리를 접근하고, 변수를 읽을 때도 메모리를 접근하고, stack을 사용할 때도 메모리를 접근한다.
그러면 매번 주소 변환이 필요하다.
따라서 주소 변환은 느리면 안 된다. 그래서 OS만으로 처리하지 않고 하드웨어인 MMU가 참여한다.
5. relocation register와 limit register로 보는 가장 단순한 변환
가장 단순한 메모리 배치 방식은 프로세스를 물리 메모리의 연속된 공간에 통째로 올리는 것이다.
예를 들어 프로세스 P가 물리 주소 50000부터 올라갔다고 하자.
프로세스는 자기 logical address가 0부터 시작한다고 생각한다.
Process P logical address space
0 100 200 300
|-------|--------|--------|
Physical memory
50000 50100 50200 50300
|-------|--------|--------|
이때 logical address 120은 physical address 50120이 된다.
physical address = relocation register + logical address
= 50000 + 120
= 50120
여기서 relocation register는 이 프로세스가 물리 메모리에서 시작하는 위치를 담는다.
그런데 이것만으로는 부족하다.
프로세스가 자기 범위를 넘어서는 logical address를 만들면 어떻게 될까?
예를 들어 이 프로세스의 크기가 300인데 logical address 500에 접근하려고 하면, 이것은 자기 공간을 벗어난 접근이다.
그래서 limit register가 필요하다.
if logical address >= limit:
trap 발생
else:
physical address = relocation + logical address
limit register는 프로세스가 접근할 수 있는 범위의 크기를 나타낸다.
이 구조가 protection의 가장 기본적인 모습이다.
6. segmentation fault를 여기서 이해하기
segmentation fault는 단순히 “프로그램이 이상하게 죽었다”가 아니다.
핵심은 프로세스가 허용되지 않은 메모리 영역에 접근했다는 뜻이다.
예를 들어 다음과 같은 일이 있을 수 있다.
- 할당받지 않은 주소를 읽었다.
- 이미 해제한 메모리를 접근했다.
- NULL pointer를 따라갔다.
- 읽기 전용 영역에 쓰려고 했다.
- 자기 주소 공간 밖으로 나갔다.
운영체제와 하드웨어는 이런 접근을 감지하고 trap을 발생시킨다.
그러면 OS는 해당 프로세스에게 오류를 알리고 보통 프로세스를 종료시킨다.
메모리 보호는 운영체제의 안정성을 지키는 핵심이다. 프로세스 하나가 잘못된 주소를 건드렸다고 해서 전체 컴퓨터가 망가지면 안 된다.
Part 2. 프로세스를 물리 메모리에 어떻게 배치할 것인가
7. Contiguous allocation: 통째로 연속 배치하기
가장 직관적인 방법은 프로세스 전체를 물리 메모리의 연속된 공간에 넣는 것이다.
Physical memory
[ OS ][ Process A ][ Process B ][ free ][ Process C ][ free ]
이 방식은 이해하기 쉽다.
프로세스가 하나의 덩어리로 올라가고, relocation register와 limit register로 주소 변환과 보호를 처리할 수 있다.
장점은 단순함이다.
- 주소 변환이 쉽다.
- 하드웨어 지원도 단순하다.
- 프로세스의 시작 주소와 크기만 알면 된다.
하지만 문제가 있다.
바로 fragmentation이다.
8. fragmentation: 공간은 있는데 못 쓰는 문제
fragmentation은 메모리가 조각나는 문제다.
특히 contiguous allocation에서는 external fragmentation이 중요하다.
External fragmentation
외부 단편화는 빈 공간의 총량은 충분하지만, 연속된 큰 공간이 없어서 할당하지 못하는 상황이다.
예를 들어 100MB짜리 프로세스를 올려야 한다고 하자.
물리 메모리에는 free 공간이 총 120MB 있다.
그런데 이렇게 흩어져 있다.
[ 30MB free ][ used ][ 40MB free ][ used ][ 50MB free ]
총합은 120MB지만, 연속된 100MB 공간은 없다.
그래서 100MB 프로세스를 올릴 수 없다.
이것이 external fragmentation이다.
Internal fragmentation
내부 단편화는 할당받은 공간 안에서 낭비가 생기는 것이다.
예를 들어 4KB 단위로만 할당할 수 있는데 실제로는 3.2KB만 필요하다면 0.8KB가 낭비된다.
할당 단위: 4KB
실제 사용: 3.2KB
낭비: 0.8KB
contiguous allocation에서는 external fragmentation이 특히 치명적이다.
9. First fit, best fit, compaction
연속 공간을 할당할 때 OS는 어떤 빈 공간을 선택할지 정해야 한다.
First fit
처음으로 발견한 충분히 큰 공간에 넣는다.
앞에서부터 free block을 찾다가 들어갈 수 있으면 바로 할당
장점은 빠르다는 것이다.
단점은 시간이 지나면 앞쪽에 작은 조각들이 생기기 쉽다.
Best fit
들어갈 수 있는 공간 중 가장 딱 맞는 공간을 선택한다.
요청 크기보다 큰 free block 중 가장 작은 block 선택
장점은 큰 공간을 아끼는 것처럼 보인다는 점이다.
하지만 작은 leftover가 많이 생겨 오히려 fragmentation이 심해질 수 있다.
Compaction
조각난 프로세스들을 한쪽으로 몰아서 큰 free block을 만드는 방법이다.
before
[ A ][ free ][ B ][ free ][ C ][ free ]
after compaction
[ A ][ B ][ C ][ big free ]
좋아 보이지만 비용이 크다.
프로세스를 메모리 안에서 옮겨야 하고, 그에 따라 주소 변환 정보도 수정해야 한다. 실행 중인 프로세스의 메모리를 옮기는 것은 쉬운 일이 아니다.
그래서 contiguous allocation은 단순하지만 한계가 있다.
10. Segmentation: 의미 있는 조각으로 나누기
Contiguous allocation은 프로세스를 하나의 큰 덩어리로 본다.
하지만 실제 프로그램의 주소 공간은 의미 있는 부분들로 나뉜다.
- code segment
- data segment
- heap segment
- stack segment
Segmentation은 이 의미 단위로 주소 공간을 나누는 방식이다.
logical address space
[ code ][ data ][ heap ][ stack ]
각 segment는 물리 메모리의 서로 다른 위치에 올라갈 수 있다.
code -> physical 10000
heap -> physical 80000
stack -> physical 50000
주소는 보통 다음처럼 해석된다.
logical address = segment number + offset
예를 들어 (segment 2, offset 120)은 2번 segment의 시작 주소에 120을 더한 위치다.
physical address = segment_table[2].base + offset
단, offset이 해당 segment의 limit을 넘으면 protection fault가 난다.
11. Segmentation의 장점과 한계
Segmentation은 프로그램 구조와 잘 맞는다.
code는 읽기 전용으로 만들 수 있고, stack은 stack답게 보호할 수 있고, segment 단위 공유도 가능하다.
예를 들어 여러 프로세스가 같은 code segment를 공유할 수도 있다.
하지만 segmentation도 본질적으로 각 segment를 연속된 공간에 배치한다.
따라서 external fragmentation이 남는다.
segment 하나는 연속된 physical memory 공간이 필요함
↓
시간이 지나면 free hole이 조각남
↓
external fragmentation 발생
그래서 segmentation은 의미적으로는 좋지만, 메모리 활용 측면에서는 paging만큼 깔끔하지 않다.
12. Paging: 의미를 버리고 고정 크기로 자르기
Paging은 segmentation과 정반대 방향의 사고다.
Segmentation은 의미 있는 단위로 나눈다.
Paging은 의미를 보지 않는다. 그냥 고정 크기로 자른다.
프로세스의 logical address space를 page라는 고정 크기 조각으로 나누고, physical memory도 같은 크기의 frame으로 나눈다.
logical address space
[ page 0 ][ page 1 ][ page 2 ][ page 3 ]
physical memory
[ frame 0 ][ frame 1 ][ frame 2 ][ frame 3 ][ frame 4 ]
page와 frame의 크기는 같다.
그래서 어떤 page든 어떤 frame에 들어갈 수 있다.
page 0 -> frame 3
page 1 -> frame 7
page 2 -> frame 1
page 3 -> frame 9
중요한 점은 프로세스의 logical address space에서는 page들이 연속되어 있지만, physical memory에서는 frame들이 흩어져 있어도 된다는 것이다.
13. Paging이 external fragmentation을 해결하는 방식
Paging에서는 프로세스 전체를 연속된 공간에 넣지 않아도 된다.
필요한 frame 개수만큼 빈 frame을 아무 곳에서나 가져오면 된다.
예를 들어 프로세스가 4개의 page를 가진다면, free frame 4개만 있으면 된다.
free frame: 2, 8, 13, 20
process page 0 -> frame 8
process page 1 -> frame 2
process page 2 -> frame 20
process page 3 -> frame 13
연속될 필요가 없다.
그래서 external fragmentation이 크게 줄어든다.
하지만 paging에도 낭비가 전혀 없는 것은 아니다.
마지막 page가 꽉 차지 않을 수 있다.
page size: 4KB
프로세스 마지막 부분: 1KB만 사용
낭비: 3KB
이것은 internal fragmentation이다.
즉, paging은 external fragmentation을 해결하는 대신, page 단위 때문에 약간의 internal fragmentation을 감수한다.
14. Page table: page와 frame의 연결표
Paging을 하려면 각 page가 어떤 frame에 들어갔는지 알아야 한다.
이 정보를 담는 것이 page table이다.
page table
page 0 -> frame 8
page 1 -> frame 2
page 2 -> frame 20
page 3 -> frame 13
CPU가 logical address를 만들면, MMU는 그 주소를 page number와 offset으로 나눈다.
logical address
+-------------+--------+
| page number | offset |
+-------------+--------+
page number로 page table을 찾고, offset은 그대로 유지한다.
frame number = page_table[page number]
physical address = frame number + offset
예를 들어 page size가 4KB라면 offset은 page 안에서의 위치다.
logical address가 page 3의 offset 100이라면 다음처럼 변환된다.
page table[3] = frame 13
physical address = frame 13의 시작 위치 + 100
15. Paging의 진짜 비용: 메모리 접근이 늘어난다
Paging은 아름답지만 문제가 있다.
메모리를 한 번 접근하려고 해도 page table을 먼저 봐야 한다.
단순하게 생각하면 다음과 같다.
1. page table에서 frame number 읽기
2. 실제 physical memory 접근
즉, 원래 메모리 한 번이면 될 일이 두 번이 된다.
without paging:
memory access 1번
with paging:
page table access 1번 + actual memory access 1번
이것은 성능에 매우 큰 부담이다.
그래서 TLB가 필요해진다.
Part 3. 주소 변환을 빠르게 만들기
16. TLB: 주소 변환 결과를 저장하는 작은 정답지
TLB는 Translation Lookaside Buffer다.
자주 쓰는 page number와 frame number의 매핑을 저장하는 작은 하드웨어 캐시다.
TLB
page 3 -> frame 13
page 7 -> frame 2
page 9 -> frame 20
CPU가 logical address를 만들면 MMU는 먼저 TLB를 확인한다.
logical address의 page number 확인
↓
TLB에 있나?
↓
있으면 바로 frame number 획득
↓
actual memory 접근
TLB에 있으면 page table을 메모리에서 읽지 않아도 된다.
이를 TLB hit라고 한다.
TLB에 없으면 page table을 봐야 한다.
이를 TLB miss라고 한다.
17. TLB가 효과적인 이유는 locality다
TLB는 작다.
그런데도 효과적이다.
이유는 프로그램이 보통 locality를 가지기 때문이다.
Temporal locality
최근 접근한 것을 곧 다시 접근할 가능성이 높다.
예를 들어 반복문 안에서 같은 변수나 같은 배열 일부를 계속 쓴다.
Spatial locality
어떤 주소를 접근하면 그 주변 주소도 곧 접근할 가능성이 높다.
예를 들어 배열을 앞에서부터 순서대로 읽는다.
for (int i = 0; i < n; i++) {
sum += arr[i];
}
이런 패턴에서는 같은 page 안의 여러 주소를 계속 접근한다.
한 번 TLB에 page mapping이 올라오면 여러 번 재사용된다.
그래서 작은 TLB도 큰 효과를 낸다.
18. Effective Access Time, EAT
TLB가 있을 때 평균 메모리 접근 시간을 계산할 수 있다.
개념적으로는 다음과 같다.
EAT = hit_ratio * hit_time + miss_ratio * miss_time
예를 들어 단순화해서 생각해 보자.
- TLB lookup 시간은 매우 작다고 하자.
- 메모리 접근 시간은 100ns라고 하자.
- TLB hit이면 실제 메모리 접근 1번이면 된다.
- TLB miss이면 page table 접근 1번 + 실제 메모리 접근 1번이 필요하다.
TLB hit: 약 100ns
TLB miss: 약 200ns
만약 hit ratio가 99퍼센트라면 평균은 거의 100ns에 가깝다.
하지만 hit ratio가 낮아지면 평균 접근 시간이 빠르게 나빠진다.
핵심은 이것이다.
Paging은 주소 변환 때문에 느려질 수 있지만, TLB hit ratio가 충분히 높으면 실제 성능 부담을 크게 줄일 수 있다.
19. PTE에는 무엇이 들어가는가
Page table entry, PTE는 단순히 frame number만 담지 않는다.
운영체제는 각 page에 대한 여러 상태 정보를 PTE에 넣는다.
대표적으로 다음과 같은 정보가 있다.
| 정보 | 의미 |
|---|---|
| frame number | 이 page가 어느 physical frame에 있는가 |
| valid bit | 이 entry가 유효한가, 또는 현재 memory에 있는가 |
| protection bit | 읽기, 쓰기, 실행 권한 |
| dirty bit | 메모리에 올라온 뒤 수정되었는가 |
| reference bit | 최근 접근되었는가 |
| COW 관련 bit | copy-on-write 상태인가 |
이 정보를 보면 page table은 단순한 주소 변환표가 아니다.
Page table은 OS의 메모리 정책이 실제로 구현되는 장소다.
- 보호를 위해 permission을 둔다.
- demand paging을 위해 valid bit를 둔다.
- page replacement를 위해 reference bit를 둔다.
- write-back 최적화를 위해 dirty bit를 둔다.
- COW를 위해 write permission을 조정하고 COW 상태를 표시한다.
즉, page table은 가상 메모리 시스템의 중심 자료구조다.
Part 4. Page table이 너무 커지는 문제
20. Single-level page table의 문제
주소 공간이 커질수록 page table도 커진다.
예를 들어 32-bit 주소 공간에서 page size가 4KB라고 하자.
주소 공간 크기: 2^32 bytes = 4GB
page size: 2^12 bytes = 4KB
page 개수: 2^32 / 2^12 = 2^20 pages
즉, 프로세스 하나당 page table entry가 약 100만 개 필요하다.
각 PTE가 4바이트라면 page table만 약 4MB다.
프로세스 하나당 4MB면 꽤 크다.
64-bit 주소 공간으로 가면 문제는 훨씬 커진다.
그런데 실제 프로세스는 자기 주소 공간 전체를 다 쓰지 않는다.
주소 공간은 크게 열려 있지만, 실제로 쓰는 부분은 일부다.
virtual address space
[ code ][ data ][ heap ... 빈 공간 ... stack ]
Single-level page table은 쓰지 않는 주소 공간에 대해서도 entry를 준비해야 할 수 있다.
이것이 낭비다.
21. Hierarchical page table: page table도 page처럼 나누기
Hierarchical page table의 아이디어는 단순하다.
page table 전체를 한 덩어리로 만들지 말고, page table 자체도 여러 조각으로 나누자.
2-level page table을 예로 들면 주소를 이렇게 나눈다.
logical address
+----------------+--------------+--------+
| page directory | page table | offset |
+----------------+--------------+--------+
첫 번째 부분은 page directory를 찾는 데 쓴다.
두 번째 부분은 실제 page table 안의 entry를 찾는 데 쓴다.
세 번째 부분은 page 안의 offset이다.
page directory
↓
필요한 page table page
↓
PTE
↓
physical frame + offset
핵심은 사용하지 않는 주소 영역에 대해서는 두 번째 단계의 page table을 만들지 않아도 된다는 점이다.
22. Hierarchical page table의 메모리 절약 원리
프로세스가 주소 공간 전체 중 일부만 사용한다고 하자.
사용 중인 virtual page 영역
[ code ] [ heap ] [ stack ]
사용하지 않는 영역
[ huge unused virtual address range ]
Single-level page table은 이 전체 영역에 대한 entry를 준비해야 할 수 있다.
하지만 hierarchical page table은 실제로 쓰는 영역에 해당하는 하위 page table만 만든다.
page directory
entry 0 -> code 영역 page table 존재
entry 1 -> 없음
entry 2 -> 없음
entry 3 -> heap 영역 page table 존재
...
entry N -> stack 영역 page table 존재
비어 있는 영역은 page directory entry만 invalid로 두면 된다.
그래서 page table memory를 줄일 수 있다.
23. Hierarchical page table의 trade-off
하지만 공짜는 없다.
단계가 늘어나면 주소 변환 때 읽어야 할 테이블도 늘어난다.
2-level page table에서는 최악의 경우 다음 접근이 필요하다.
1. page directory 접근
2. page table 접근
3. 실제 memory 접근
3-level이면 더 늘어난다.
그래서 TLB가 더 중요해진다.
TLB hit이면 이 여러 단계를 건너뛰고 바로 frame number를 얻을 수 있다.
TLB hit:
logical page -> physical frame 바로 획득
TLB miss:
page directory, page table을 따라가며 변환
즉, hierarchical page table은 메모리를 아끼지만, 주소 변환 경로는 길어질 수 있다. 이 비용을 TLB가 줄여 준다.
24. Hashed page table과 inverted page table
큰 주소 공간에서는 page table 구조를 다르게 잡기도 한다.
Hashed page table
Hashed page table은 virtual page number를 hash해서 entry를 찾는다.
주소 공간이 매우 클 때 전체 page table을 배열처럼 만드는 대신, 실제로 존재하는 mapping을 hash table로 관리한다.
virtual page number
↓ hash
bucket
↓
matching entry 탐색
장점은 sparse한 주소 공간에서 효율적일 수 있다는 점이다.
단점은 hash collision 처리가 필요하고, 탐색이 완전히 단순한 배열 접근은 아니라는 점이다.
Inverted page table
일반 page table은 프로세스의 virtual page를 기준으로 frame을 찾는다.
virtual page -> physical frame
Inverted page table은 관점을 뒤집는다.
physical frame마다 “이 frame을 어떤 프로세스의 어떤 virtual page가 쓰는가”를 기록한다.
physical frame -> (process id, virtual page)
물리 frame 개수는 virtual page 개수보다 훨씬 작을 수 있다.
그래서 table 크기를 줄일 수 있다.
하지만 주소 변환 때 원하는 virtual page가 어느 frame에 있는지 찾아야 하므로 탐색 구조가 필요하다.
25. Huge page: page를 크게 쓰는 이유
일반적인 page size는 4KB인 경우가 많다.
하지만 큰 메모리 영역을 다루는 프로그램에서는 huge page를 쓰기도 한다.
예를 들어 2MB, 1GB 같은 큰 page를 사용할 수 있다.
Huge page의 장점은 TLB 효율이다.
TLB entry 하나가 커버하는 메모리 범위가 커진다.
4KB page:
TLB entry 1개 -> 4KB 커버
2MB huge page:
TLB entry 1개 -> 2MB 커버
큰 배열이나 데이터베이스 buffer처럼 넓은 메모리 영역을 순회하는 경우, TLB miss를 줄일 수 있다.
하지만 huge page도 항상 좋은 것은 아니다.
- 내부 단편화가 커질 수 있다.
- 작은 객체에는 부적합하다.
- OS의 page allocation이 더 까다로울 수 있다.
따라서 huge page는 성능을 위해 선택적으로 쓰는 도구다.
Part 5. Virtual Memory의 등장
26. Main memory에서 Virtual memory로 넘어가는 생각의 변화
지금까지는 기본적으로 이렇게 생각했다.
프로세스의 logical address space를 physical memory 어딘가에 배치한다.
그런데 virtual memory에서는 생각이 바뀐다.
프로세스의 주소 공간 전체를 처음부터 물리 메모리에 올릴 필요가 있을까?
프로그램은 자기 주소 공간 전체가 존재한다고 생각한다.
하지만 실제로 실행 중에 모든 code와 data를 한 번에 다 쓰지는 않는다.
예를 들어 프로그램 안에 오류 처리 코드가 있다고 하자. 오류가 발생하지 않으면 그 코드는 실행되지 않는다.
큰 배열을 할당했지만 일부만 접근할 수도 있다.
프로그램 시작 시점에는 stack의 일부만 쓰고, heap도 필요한 만큼만 커진다.
그래서 OS는 이렇게 생각한다.
프로세스에게는 큰 주소 공간이 있는 것처럼 보여 주자.
하지만 실제 RAM에는 지금 필요한 page만 올리자.
이것이 virtual memory의 핵심이다.
27. Demand paging
Demand paging은 말 그대로 필요할 때 page를 가져오는 방식이다.
처음부터 모든 page를 memory에 올리지 않음
↓
프로세스가 어떤 page에 접근함
↓
그 page가 memory에 없으면 page fault
↓
OS가 storage에서 page를 가져와 memory에 올림
↓
명령 재시작
이 방식의 장점은 분명하다.
- 프로그램 시작이 빨라질 수 있다.
- 실제로 안 쓰는 page를 RAM에 올리지 않아도 된다.
- 더 많은 프로세스를 동시에 실행할 수 있다.
- 물리 메모리보다 큰 주소 공간을 제공할 수 있다.
하지만 page fault가 발생하면 비용이 크다.
그래서 demand paging은 locality가 있을 때 효과적이다.
28. Valid bit와 invalid bit
Virtual memory에서는 page table entry가 단순히 frame number만 담으면 안 된다.
어떤 page는 현재 physical memory에 있고, 어떤 page는 아직 없다.
이를 표시하기 위해 valid bit 또는 present bit가 필요하다.
PTE
valid = 1 -> 현재 memory에 있음
valid = 0 -> 현재 memory에 없음, 접근하면 page fault
예를 들어 다음과 같은 page table이 있다고 하자.
page 0 -> frame 5, valid
page 1 -> invalid
page 2 -> frame 9, valid
page 3 -> invalid
프로세스가 page 0에 접근하면 정상적으로 frame 5를 사용한다.
프로세스가 page 1에 접근하면 page fault가 발생한다.
여기서 중요한 점은 invalid가 항상 “잘못된 주소”라는 뜻은 아니라는 것이다.
두 경우가 있다.
- 정말 프로세스 주소 공간에 없는 page다.
- 주소 공간에는 있지만 현재 RAM에 올라와 있지 않은 page다.
OS는 page fault handler에서 이 둘을 구분해야 한다.
29. Page fault 처리 흐름
Page fault가 발생하면 단순한 함수 호출보다 훨씬 복잡한 일이 일어난다.
흐름을 자세히 보면 다음과 같다.
1. CPU가 어떤 virtual address에 접근한다.
2. MMU가 page table을 확인한다.
3. valid bit가 0이거나 permission 문제가 있으면 fault를 발생시킨다.
4. CPU는 trap을 통해 OS kernel로 진입한다.
5. OS는 fault가 난 주소가 유효한 주소인지 확인한다.
6. 유효하지 않으면 프로세스를 종료하거나 signal을 보낸다.
7. 유효하지만 memory에 없는 page라면 free frame을 찾는다.
8. free frame이 없으면 page replacement를 수행한다.
9. 필요한 page를 storage에서 읽어온다.
10. page table을 갱신한다.
11. fault를 낸 명령어를 다시 실행한다.
이 마지막 단계가 중요하다.
Page fault는 프로그램 입장에서 투명해야 한다.
프로그램은 “내가 방금 메모리를 읽었더니 OS가 디스크에서 page를 가져왔구나”라고 직접 알 필요가 없다.
명령어가 다시 실행되면 이번에는 page가 memory에 있으므로 정상적으로 진행된다.
30. Restart instruction이 중요한 이유
Page fault가 발생하면 fault를 낸 명령어가 완전히 끝난 것이 아니다.
예를 들어 다음 명령어가 있다고 하자.
load R1, [virtual address X]
이 명령어가 실행되다가 X가 있는 page가 memory에 없어서 page fault가 났다.
OS가 page를 가져온 뒤에는 이 명령어를 다시 실행해야 한다.
그래야 프로그램은 마치 처음부터 page가 있었던 것처럼 동작한다.
어떤 명령어는 중간에 여러 memory access를 할 수도 있다. 그래서 CPU와 OS는 page fault 후 명령어를 안전하게 재시작할 수 있어야 한다.
이것이 virtual memory가 하드웨어 지원 없이는 구현하기 어려운 이유 중 하나다.
31. Swap과 storage의 역할
Virtual memory에서 physical memory는 cache처럼 동작한다.
전체 주소 공간의 모든 page를 RAM에 둘 수 없으므로, 일부 page는 storage에 있다.
virtual address space 전체
↓
일부 page는 RAM
일부 page는 disk/swap area/file
메모리에 없는 page가 필요하면 storage에서 가져온다.
메모리가 부족하면 어떤 page를 storage로 내보낼 수도 있다.
이때 수정된 page라면 disk에 write-back해야 한다.
수정되지 않은 page라면 원본 파일에서 다시 읽을 수 있으므로 그냥 버릴 수도 있다.
여기서 dirty bit가 중요해진다.
dirty = 0 -> 수정 안 됨, 버려도 됨
dirty = 1 -> 수정됨, 내보내기 전에 storage에 기록 필요
Part 6. Page replacement와 thrashing
32. Page fault rate가 성능을 결정한다
Demand paging은 좋은 아이디어지만 page fault가 너무 자주 나면 성능이 무너진다.
Page fault는 일반 memory access보다 훨씬 비싸다.
특히 disk I/O가 들어가면 차이가 엄청나다.
단순히 감각적으로 보면 다음과 같다.
memory access: 매우 빠름
page fault with disk I/O: 매우 느림
그래서 평균 접근 시간은 page fault rate에 민감하다.
EAT = (1 - p) * memory_access_time + p * page_fault_service_time
여기서 p가 page fault rate다.
page fault service time이 매우 크기 때문에 p가 아주 작아도 평균 시간이 크게 늘어날 수 있다.
33. Page replacement: 누구를 내보낼 것인가
Page fault가 났는데 free frame이 있으면 간단하다.
그 frame에 필요한 page를 가져오면 된다.
문제는 free frame이 없을 때다.
이때 OS는 현재 memory에 있는 page 중 하나를 골라 내보내야 한다.
이것이 page replacement다.
memory full
↓
새 page가 필요함
↓
어떤 page를 victim으로 선택할 것인가?
좋은 replacement 알고리즘은 앞으로 당분간 쓰지 않을 page를 내보내야 한다.
하지만 OS는 미래를 정확히 모른다.
그래서 여러 알고리즘이 나온다.
34. FIFO, Optimal, LRU
FIFO
FIFO는 가장 먼저 들어온 page를 먼저 내보낸다.
가장 오래 전에 memory에 올라온 page 제거
간단하지만, 오래 있었다고 해서 앞으로 안 쓰인다는 보장은 없다.
자주 쓰는 page가 오래 있었다는 이유로 쫓겨날 수 있다.
Optimal
Optimal은 앞으로 가장 오랫동안 쓰이지 않을 page를 내보낸다.
이론적으로 가장 좋다.
하지만 미래 접근 패턴을 알아야 한다.
현실 OS는 미래를 알 수 없으므로 실제 구현용이라기보다 비교 기준으로 사용한다.
LRU
LRU는 Least Recently Used다.
가장 오랫동안 사용되지 않은 page를 내보낸다.
미래를 모르니 과거를 보고 추정하는 방식이다.
최근에 쓰인 page는 곧 다시 쓰일 가능성이 높다.
오래 안 쓰인 page는 앞으로도 안 쓰일 가능성이 높다.
locality가 있는 프로그램에서는 합리적인 전략이다.
하지만 정확한 LRU를 구현하려면 모든 접근 순서를 추적해야 하므로 비용이 크다.
35. Second chance와 Clock algorithm
정확한 LRU는 비싸다.
그래서 현실에서는 reference bit를 이용한 근사 알고리즘을 쓴다.
Second chance는 FIFO를 기반으로 하되, 최근에 참조된 page에게 한 번 기회를 더 준다.
victim 후보 page 확인
reference bit = 0 -> 내보냄
reference bit = 1 -> reference bit를 0으로 바꾸고 뒤로 보냄
Clock algorithm은 이를 원형 큐처럼 구현한 것이다.
clock hand가 page들을 돌며 확인
ref = 1이면 0으로 바꾸고 넘어감
ref = 0이면 victim으로 선택
핵심은 “최근에 한 번이라도 쓰였으면 바로 내보내지 말자”는 것이다.
36. Thrashing: page fault만 하느라 일을 못 하는 상태
Thrashing은 시스템이 실제 계산보다 page 교체에 대부분의 시간을 쓰는 상태다.
프로세스들이 필요로 하는 working set이 물리 메모리에 들어가지 못하면 page fault가 계속 발생한다.
page fault 발생
↓
page를 가져오려고 다른 page를 내보냄
↓
조금 뒤 내보낸 page가 다시 필요함
↓
또 page fault
↓
반복
이 상태에서는 CPU utilization이 오히려 떨어진다.
겉으로는 프로세스가 많아 보이지만, 실제로는 CPU가 일을 하는 것이 아니라 I/O와 page fault 처리에 시간을 빼앗긴다.
37. Degree of multiprogramming과 CPU utilization
Multiprogramming 정도가 높아지면 처음에는 CPU utilization이 올라간다.
프로세스 하나가 I/O를 기다리는 동안 다른 프로세스를 실행할 수 있기 때문이다.
하지만 너무 많은 프로세스를 동시에 올리면 각 프로세스에게 돌아가는 frame 수가 부족해진다.
그러면 page fault가 늘고 thrashing이 발생한다.
프로세스 수 증가
↓
처음에는 CPU utilization 증가
↓
메모리 부족
↓
page fault 증가
↓
thrashing
↓
CPU utilization 감소
따라서 OS는 무조건 많은 프로세스를 올리는 것이 아니라, 메모리 상황을 보며 조절해야 한다.
38. Working set model
Working set은 어떤 시간 구간 동안 프로세스가 실제로 활발히 사용하는 page들의 집합이다.
최근 Δ 시간 동안 참조된 pages = working set
프로세스의 working set을 memory에 유지할 수 있으면 page fault가 적다.
반대로 working set을 담을 frame이 부족하면 page fault가 많아진다.
예를 들어 어떤 프로세스가 반복문 안에서 page 1, 2, 3, 4를 계속 쓴다면 working set은 대략 이 4개다.
이 4개를 memory에 둘 수 있으면 안정적으로 실행된다.
하지만 frame이 3개밖에 없으면 계속 하나가 빠지고 다시 필요해지는 일이 생길 수 있다.
39. Page Fault Frequency, PFF
Working set을 정확히 추적하는 것은 어렵다.
그래서 page fault frequency를 기준으로 조절할 수도 있다.
아이디어는 간단하다.
page fault rate가 너무 높다 -> frame을 더 줘야 함
page fault rate가 너무 낮다 -> frame을 조금 회수해도 됨
이 방식은 프로세스별 page fault 빈도를 보고 메모리 할당량을 조절한다.
궁극적인 목표는 thrashing을 피하고, memory를 효율적으로 나누는 것이다.
Part 7. Copy-on-Write와 memory-mapped file
40. Copy-on-Write는 “쓸 때 복사하기”다
Copy-on-Write, COW는 이름 그대로 write가 발생할 때 복사하는 기법이다.
대표 상황은 fork()다.
fork()를 하면 부모 프로세스의 주소 공간을 자식 프로세스가 복제한다.
단순하게 구현하면 부모의 모든 page를 자식용으로 복사해야 한다.
하지만 이것은 너무 비싸다.
그래서 OS는 처음에는 부모와 자식이 같은 physical frame을 바라보게 한다.
fork 직후
parent page table ─┐
├─ same physical frame
child page table ─┘
둘 다 읽기만 하면 문제가 없다.
하지만 한쪽이 쓰려고 하면 독립성이 깨진다.
그래서 쓰기 시점에 page fault를 발생시키고, OS가 새 frame을 만들어 복사한다.
child가 write 시도
↓
COW page fault
↓
새 frame 할당
↓
기존 page 내용 복사
↓
child page table을 새 frame으로 변경
↓
write 수행
41. COW와 shared memory는 다르다
COW와 shared memory는 둘 다 여러 프로세스가 같은 frame을 볼 수 있다는 점에서 비슷하다.
하지만 목적이 다르다.
| 구분 | shared memory | Copy-on-Write |
|---|---|---|
| 목적 | 데이터를 진짜로 공유 | 복사 비용을 줄이는 최적화 |
| write 의미 | 한쪽이 쓰면 다른 쪽도 보는 것이 목적 | 한쪽이 쓰면 분리해야 함 |
| 대표 상황 | IPC, 공유 버퍼 | fork 이후 부모와 자식 |
| 핵심 | 함께 보기 | 필요할 때만 복사하기 |
COW에서 공유는 영구적인 공유가 아니다.
처음에는 같은 내용을 가지고 있으니 잠깐 같이 보게 두는 것이다.
누군가 내용을 바꾸려는 순간, OS는 둘을 분리한다.
42. COW는 demand paging과 닮았다
Demand paging은 page를 실제로 접근할 때까지 memory에 올리지 않는다.
COW는 page를 실제로 쓸 때까지 복사하지 않는다.
둘 다 핵심은 지연이다.
Demand paging:
필요할 때까지 page loading을 미룸
Copy-on-Write:
write가 필요할 때까지 page copy를 미룸
운영체제는 이런 지연 전략을 많이 쓴다.
왜냐하면 실제로 필요하지 않은 일에 미리 비용을 쓰는 것은 낭비이기 때문이다.
43. Memory-mapped file은 파일을 메모리처럼 다룬다
보통 파일을 다룰 때는 open, read, write, close를 쓴다.
fd = open("data.txt", ...);
read(fd, buffer, size);
write(fd, buffer, size);
close(fd);
이 방식은 파일 시스템 API를 통해 데이터를 주고받는다.
Memory-mapped file은 다르게 접근한다.
파일의 일부 또는 전체를 프로세스의 virtual address space에 붙인다.
file on disk
[ page 0 ][ page 1 ][ page 2 ]
↓ mmap
process address space
[ virtual page 10 ][ virtual page 11 ][ virtual page 12 ]
이제 프로세스는 파일을 메모리처럼 읽고 쓴다.
p[0] = 'A';
x = p[1024];
겉으로는 메모리 접근이지만, OS 내부에서는 page fault와 page cache, dirty page 관리가 연결된다.
44. mmap은 왜 유용한가
Memory-mapped file은 특히 다음 상황에서 유용하다.
1. 랜덤 접근이 자연스럽다
파일의 여기저기를 자주 접근해야 한다면 seek, read, write를 반복하는 것보다 주소 계산으로 접근하는 것이 편할 수 있다.
일반 파일 I/O:
seek -> read -> seek -> write
mmap:
memory[index] 접근
2. 여러 프로세스가 같은 파일을 공유하기 쉽다
여러 프로세스가 같은 파일을 매핑하면 같은 file-backed page를 볼 수 있다.
Process A address space ─┐
├─ file-backed physical page
Process B address space ─┘
물론 동기화는 여전히 필요하다.
하지만 모델 자체는 “같은 메모리 영역을 같이 본다”에 가깝다.
3. OS의 page cache와 자연스럽게 연결된다
파일 내용을 page 단위로 memory에 올리고, 수정된 page는 dirty page로 관리한 뒤 나중에 storage에 반영할 수 있다.
45. mmap은 항상 빠른가
아니다.
예전에는 “파일 성능이 안 나오면 mmap을 써라”는 조언이 많았다.
하지만 지금은 상황에 따라 다르다.
- 파일 시스템도 많이 최적화되었다.
- SSD는 랜덤 접근 성능이 과거 HDD보다 훨씬 좋다.
- mmap도 page fault, TLB, flush, 동기화 비용이 있다.
- 작은 파일이나 단순 sequential I/O에서는 일반 read/write가 더 단순하고 충분히 빠를 수 있다.
그래서 mmap은 “무조건 빠른 마법”이 아니다.
정확한 이해는 이것이다.
mmap은 파일을 메모리 주소 공간에 매핑하는 접근 모델이다.
랜덤 접근, 공유, 큰 파일 일부 접근 같은 상황에서 코드 구조나 성능상 이점이 있을 수 있다.
Part 8. 커널 메모리 관리
46. 사용자 프로세스 메모리와 커널 메모리는 요구사항이 다르다
사용자 프로세스에게 page를 할당할 때는 보통 free frame 하나를 찾아 page table에 연결하면 된다.
물리적으로 연속될 필요가 없는 경우가 많다.
하지만 커널은 다르다.
커널은 하드웨어 장치와 직접 상호작용하고, 내부 자료구조를 매우 자주 만들고 없앤다.
그래서 커널 메모리에는 두 가지 특별한 요구가 생긴다.
- 물리적으로 연속된 메모리가 필요할 수 있다.
- 작은 커널 객체를 빠르게 할당하고 해제해야 한다.
47. DMA와 물리적으로 연속된 메모리
DMA는 Direct Memory Access다.
CPU가 데이터를 하나하나 복사하지 않고, 장치가 직접 메모리와 데이터를 주고받게 하는 방식이다.
CPU가 직접 복사:
device -> CPU -> memory
DMA:
device -> memory
CPU는 명령만 내림
문제는 DMA 장치가 보통 physical address를 기준으로 동작한다는 점이다.
사용자 프로세스 입장에서는 버퍼가 연속된 virtual address처럼 보일 수 있다.
하지만 실제 physical frame은 흩어져 있을 수 있다.
virtual buffer
[ page 0 ][ page 1 ][ page 2 ]
physical frames
page 0 -> frame 100
page 1 -> frame 7
page 2 -> frame 81
DMA 장치에게는 이 흩어진 구조가 까다롭다.
그래서 OS가 물리적으로 연속된 bounce buffer를 만들고 데이터를 한 번 복사해야 할 수도 있다.
이것은 성능 비용이다.
따라서 커널은 때때로 physical contiguous memory를 확보해야 한다.
48. Buddy system
Buddy system은 물리적으로 연속된 page block을 관리하기 위한 기법이다.
메모리를 2의 거듭제곱 크기 block으로 나누어 관리한다.
예를 들어 256KB block이 있으면 반으로 나누어 128KB 두 개를 만들고, 다시 64KB, 32KB 식으로 나눌 수 있다.
256KB
├─ 128KB
│ ├─ 64KB
│ └─ 64KB
└─ 128KB
├─ 64KB
└─ 64KB
20KB 요청이 들어오면 20KB를 담을 수 있는 가장 작은 2의 거듭제곱 block인 32KB를 할당한다.
해제할 때는 buddy가 함께 free 상태라면 다시 합친다.
32KB + 32KB -> 64KB
64KB + 64KB -> 128KB
Buddy system의 목표는 큰 연속 free block을 가능한 한 잘 보존하는 것이다.
단점은 요청 크기가 2의 거듭제곱에 딱 맞지 않으면 내부 단편화가 생길 수 있다는 점이다.
49. Slab allocator
Buddy system은 page block 단위 관리에 좋다.
하지만 커널에는 작은 객체가 매우 자주 생성되고 삭제된다.
예를 들어 process descriptor, file object, inode, socket 구조체 같은 것들이다.
이런 객체를 매번 일반 동적 할당으로 만들면 비용이 크다.
Slab allocator는 자주 쓰는 객체를 위한 cache를 만든다.
PCB cache
[ free object ][ free object ][ free object ]
프로세스가 생성되면 cache에서 객체 하나를 꺼낸다.
프로세스가 종료되면 객체를 완전히 버리지 않고 초기화한 뒤 cache에 돌려놓는다.
이 방식은 object pooling과 비슷하다.
50. Slab, cache, object
Slab allocator를 이해할 때 세 용어를 구분하면 좋다.
| 용어 | 의미 |
|---|---|
| object | 실제 커널 구조체 하나 |
| cache | 같은 종류 object들의 풀 |
| slab | 여러 object를 담는 연속된 메모리 묶음 |
예를 들어 3KB짜리 객체가 많다면 page 3개, 즉 12KB slab 안에 3KB 객체 4개를 넣을 수 있다.
slab 12KB
[ 3KB obj ][ 3KB obj ][ 3KB obj ][ 3KB obj ]
이렇게 하면 특정 객체 크기에 맞춘 효율적인 할당이 가능하다.
Buddy system과 slab allocator는 함께 쓰일 수 있다.
buddy system이 연속 page block 제공
↓
slab allocator가 그 위에 object cache 구성
↓
커널 객체를 빠르게 할당/해제
Part 9. 메모리 접근 패턴과 실제 성능 감각
51. 같은 알고리즘도 접근 순서에 따라 성능이 달라진다
메모리 단원은 OS 내부 이야기로만 끝나지 않는다.
프로그래머가 메모리를 어떤 순서로 접근하느냐도 성능에 큰 영향을 준다.
예를 들어 C에서 2차원 배열을 생각해 보자.
int a[128][128];
C는 보통 row-major order로 배열을 배치한다.
즉, 같은 행의 원소들이 연속해서 놓인다.
a[0][0], a[0][1], a[0][2], ...
a[1][0], a[1][1], a[1][2], ...
따라서 행을 먼저 고정하고 열을 움직이는 순회가 locality에 좋다.
for (int i = 0; i < 128; i++) {
for (int j = 0; j < 128; j++) {
sum += a[i][j];
}
}
이렇게 하면 한 page를 가져왔을 때 그 page 안의 데이터를 여러 번 활용할 수 있다.
52. 나쁜 순회는 page fault를 폭증시킬 수 있다
반대로 열 방향으로 순회하면 메모리 배치와 어긋날 수 있다.
for (int j = 0; j < 128; j++) {
for (int i = 0; i < 128; i++) {
sum += a[i][j];
}
}
이 경우 접근이 메모리에서 멀리뛰기처럼 일어날 수 있다.
a[0][0] -> page A
a[1][0] -> page B
a[2][0] -> page C
...
프레임이 충분하면 괜찮을 수도 있다.
하지만 working set보다 frame이 조금 부족하면, 방금 쫓겨난 page가 곧 다시 필요해지는 일이 반복될 수 있다.
그 결과 page fault가 크게 늘어난다.
이 예시는 운영체제의 page replacement와 프로그래머의 접근 패턴이 실제로 연결된다는 것을 보여 준다.
53. 성능을 망치는 대표 비용들
강의 후반부에서 중요한 실전 감각이 나온다.
소프트웨어에서 비싼 작업은 대표적으로 다음과 같다.
- I/O
- memory copy
- dynamic memory allocation
- page fault
I/O는 장치나 storage를 기다려야 해서 비싸다.
Memory copy는 데이터가 클수록 memory bandwidth와 cache를 많이 쓴다.
Dynamic allocation은 내부적으로 free block 탐색, 분할, 병합, metadata 관리가 필요할 수 있다.
Page fault는 OS trap, frame 확보, disk I/O, page table 갱신, 명령 재시작까지 포함할 수 있어 매우 비싸다.
이 감각을 가지면 운영체제 개념이 단순 이론이 아니라 실제 프로그램 성능과 연결된다.
Part 10. 전체 구조를 다시 하나로 묶기
54. 메모리 단원의 큰 이야기
이제 전체를 하나의 이야기로 다시 묶어 보자.
처음 문제는 단순했다.
여러 프로세스가 하나의 RAM을 어떻게 나눠 쓸 것인가?
먼저 프로세스에게 독립된 주소 공간을 주기 위해 logical address와 physical address를 분리했다.
이 주소를 변환하기 위해 MMU가 필요해졌다.
처음에는 relocation register와 limit register로 단순하게 처리할 수 있었다.
하지만 프로세스를 통째로 연속 배치하면 fragmentation 문제가 생겼다.
Segmentation은 프로그램의 의미 구조를 반영했지만, 여전히 external fragmentation을 완전히 해결하지 못했다.
Paging은 주소 공간을 고정 크기 page로 잘라서 어떤 frame에나 넣을 수 있게 만들었다.
이로써 external fragmentation 문제는 크게 줄었다.
하지만 paging은 page table 접근 때문에 주소 변환 비용이 커졌다.
그래서 TLB가 등장했다.
또 page table 자체가 커지는 문제가 생겨 hierarchical page table, hashed page table, inverted page table 같은 구조가 나왔다.
그 다음에는 생각이 한 단계 더 확장된다.
프로세스의 모든 page를 처음부터 RAM에 올릴 필요가 있을까?
이 질문에서 virtual memory와 demand paging이 나온다.
필요한 page만 memory에 올리고, 없으면 page fault를 통해 가져온다.
하지만 page fault가 너무 많으면 성능이 무너진다.
그래서 page replacement, working set, PFF, thrashing 제어가 필요하다.
마지막으로 OS는 이 구조를 이용해 더 똑똑한 최적화를 한다.
- fork 비용을 줄이기 위해 Copy-on-Write를 쓴다.
- 파일을 주소 공간에 붙이기 위해 memory-mapped file을 쓴다.
- 커널 내부에서는 buddy system과 slab allocator로 메모리를 관리한다.
결국 메모리 단원은 하나의 원리로 이어진다.
주소를 추상화하고, 실제 물리 자원은 필요할 때 효율적으로 연결한다.
55. 가장 중요한 mental model
메모리 단원을 공부할 때 다음 그림을 머릿속에 두면 좋다.
Program
나는 내 주소 공간 전체가 있는 것처럼 생각함
↓
CPU
logical address 생성
↓
MMU + TLB
빠르게 주소 변환 시도
↓
Page Table
mapping, permission, valid bit 확인
↓
Physical Memory
실제 frame 접근
↓
없거나 권한 문제가 있으면
↓
Page Fault
↓
OS Kernel
유효성 확인, frame 확보, disk I/O, page table 갱신
↓
Instruction restart
이 그림 하나에 대부분의 개념이 들어 있다.
- logical address
- physical address
- MMU
- TLB
- page table
- valid bit
- page fault
- demand paging
- page replacement
- protection
- OS kernel
56. 자주 헷갈리는 질문들
Q1. logical address는 가짜 주소인가?
가짜라기보다 프로세스 관점의 주소다.
프로세스에게는 진짜 주소처럼 보인다. 하지만 RAM에 접근하려면 physical address로 변환되어야 한다.
Q2. virtual address와 logical address는 같은 말인가?
문맥에 따라 거의 비슷하게 쓰이는 경우가 많다.
특히 virtual memory를 다룰 때 프로세스가 보는 주소를 virtual address라고 부른다.
Q3. paging을 쓰면 fragmentation이 완전히 사라지는가?
external fragmentation은 크게 줄어든다.
하지만 page 단위 때문에 internal fragmentation은 남을 수 있다.
Q4. page fault는 항상 나쁜가?
Page fault는 정상적인 demand paging 동작의 일부일 수 있다.
하지만 너무 자주 발생하면 성능이 크게 나빠진다.
Q5. TLB miss와 page fault는 같은가?
다르다.
TLB miss는 주소 변환 정보가 TLB에 없어서 page table을 봐야 하는 상황이다.
Page fault는 page table을 봤는데 page가 memory에 없거나 권한 문제가 있어서 OS가 개입해야 하는 상황이다.
Q6. valid bit가 0이면 무조건 잘못된 접근인가?
아니다.
그 주소가 정말 잘못된 주소일 수도 있고, 유효한 주소지만 현재 memory에 없는 page일 수도 있다.
OS가 page fault handler에서 판단한다.
Q7. COW page fault는 page가 disk에 없어서 발생하는가?
꼭 그렇지 않다.
COW page fault는 page가 memory에 있어도 발생할 수 있다. 공유 중인 page에 write하려고 했기 때문에 OS가 복사하려고 개입하는 것이다.
Q8. mmap은 read/write보다 항상 빠른가?
아니다.
mmap은 파일을 주소 공간에 매핑하는 다른 접근 방식이다. 상황에 따라 유용하지만 항상 빠른 것은 아니다.
57. 시험 직전 핵심 문장 모음
- 프로세스는 logical address를 만들고, 실제 RAM은 physical address로 접근한다.
- MMU는 logical address를 physical address로 변환한다.
- Limit register는 프로세스가 자기 범위를 벗어나지 못하게 보호한다.
- Contiguous allocation은 단순하지만 external fragmentation 문제가 있다.
- Segmentation은 의미 단위로 나누지만 여전히 external fragmentation이 남는다.
- Paging은 고정 크기 page와 frame을 사용해 external fragmentation을 줄인다.
- Page table은 page number를 frame number로 바꿔 주는 표다.
- Paging은 주소 변환 비용이 커서 TLB가 필요하다.
- TLB는 자주 쓰는 address translation 결과를 저장하는 하드웨어 캐시다.
- Hierarchical page table은 사용하지 않는 주소 공간의 page table을 만들지 않아 메모리를 아낀다.
- Virtual memory는 프로세스에게 큰 주소 공간을 보여 주고, 실제로 필요한 page만 RAM에 올린다.
- Demand paging은 page가 필요할 때 가져오는 방식이다.
- Page fault는 필요한 page가 memory에 없거나 권한 문제가 있을 때 OS가 개입하는 사건이다.
- Page replacement는 free frame이 없을 때 어떤 page를 내보낼지 정하는 정책이다.
- Thrashing은 page fault 처리만 하느라 실제 일을 못 하는 상태다.
- Working set은 최근에 실제로 쓰는 page들의 집합이다.
- Copy-on-Write는 write가 발생할 때까지 page 복사를 미루는 최적화다.
- Memory-mapped file은 파일을 프로세스 주소 공간에 붙여 메모리처럼 접근하는 방식이다.
- Buddy system은 커널이 연속된 물리 page block을 관리하는 기법이다.
- Slab allocator는 자주 쓰는 커널 객체를 cache로 재사용하는 기법이다.
- Locality가 좋으면 TLB와 paging이 잘 작동하고, locality가 나쁘면 page fault가 늘 수 있다.
58. 마지막으로, 이 단원을 어떻게 이해하면 좋은가
메모리 단원은 처음에는 복잡해 보이지만, 사실 같은 질문을 계속 다른 수준에서 푸는 과정이다.
첫 번째 수준에서는 “주소가 다르다”를 이해한다.
logical address != physical address
두 번째 수준에서는 “주소를 변환해야 한다”를 이해한다.
MMU, relocation, limit, page table
세 번째 수준에서는 “어떻게 배치할 것인가”를 이해한다.
contiguous allocation, segmentation, paging
네 번째 수준에서는 “빠르게 하려면 어떻게 할 것인가”를 이해한다.
TLB, EAT, hierarchical page table
다섯 번째 수준에서는 “RAM이 부족하면 어떻게 할 것인가”를 이해한다.
virtual memory, demand paging, page fault, page replacement
여섯 번째 수준에서는 “OS가 이 구조를 어떻게 활용하는가”를 이해한다.
Copy-on-Write, mmap, kernel allocator
이렇게 보면 용어들이 흩어진 것이 아니라, 하나의 계단처럼 이어진다.
운영체제의 메모리 관리는 결국 다음 균형을 잡는 일이다.
보호해야 한다.
빠르게 접근해야 한다.
메모리를 아껴야 한다.
프로그램에게는 단순한 주소 공간처럼 보여야 한다.
실제로는 복잡한 물리 자원을 효율적으로 나눠야 한다.
이 균형을 잡기 위해 운영체제는 주소 변환, page table, TLB, demand paging, replacement, COW, mmap, kernel allocator 같은 장치를 쓴다.
이제 메모리 단원을 볼 때 각 용어를 따로 외우기보다 이렇게 물어보면 된다.
이 개념은 보호, 성능, 메모리 절약, 추상화 중 어떤 문제를 해결하려고 나온 것인가?
그 질문에 답할 수 있으면 메모리 단원의 큰 줄기는 잡힌 것이다.
Part 11. 숫자로 따라가는 주소 변환
59. 주소 변환은 결국 “몫과 나머지” 문제다
Paging에서 주소 변환이 어렵게 느껴지는 이유는 page number, frame number, offset 같은 용어가 한꺼번에 나오기 때문이다.
하지만 수학적으로 보면 굉장히 단순하다.
어떤 주소가 있을 때, page size로 나누면 된다.
virtual address ÷ page size
↓
몫 = page number
나머지 = offset
예를 들어 page size가 100이라고 하자.
virtual address 237은 다음처럼 나뉜다.
237 ÷ 100 = 2 ... 37
page number = 2
offset = 37
즉, virtual address 237은 “2번 page 안의 37번째 위치”라는 뜻이다.
page table에서 page 2가 frame 8에 들어 있다고 하면 physical address는 이렇게 된다.
frame 8의 시작 위치 + offset 37
frame size도 page size와 같으므로, frame 8의 시작 위치는 다음과 같다.
8 * 100 = 800
따라서 physical address는 다음과 같다.
800 + 37 = 837
전체 과정을 한 번에 쓰면 이렇다.
virtual address 237
page size 100
237 = page 2 + offset 37
page table[2] = frame 8
physical address = 8 * 100 + 37 = 837
이것이 paging address translation의 핵심이다.
60. 2진수 주소로 이해하기
실제 컴퓨터에서는 page size가 보통 2의 거듭제곱이다.
예를 들어 page size가 4KB라고 하자.
4KB = 4096 bytes = 2^12 bytes
그러면 offset은 12bit가 된다.
왜냐하면 page 안에서 0부터 4095까지 위치를 표현해야 하기 때문이다.
offset 범위: 0 ~ 4095
필요한 bit 수: 12bit
32-bit virtual address라면 전체 주소는 32bit다.
그중 아래 12bit는 offset으로 쓰고, 나머지 위 20bit는 page number로 쓴다.
32-bit virtual address, page size 4KB
+----------------------+------------+
| page number: 20 bits | offset: 12 |
+----------------------+------------+
따라서 virtual page 개수는 다음과 같다.
2^20 pages
이런 식으로 주소를 bit 단위로 나누는 것이 paging 주소 변환의 기본이다.
61. 실제 예제 1: page size가 4KB일 때
조건을 잡아 보자.
virtual address = 0x12345
page size = 4KB = 0x1000
page table[0x12] = frame 0xABC
4KB는 16진수로 0x1000이다.
즉, offset은 아래 12bit, 16진수로는 마지막 3자리다.
virtual address 0x12345
page number = 0x12
offset = 0x345
page table을 보니 page 0x12는 frame 0xABC에 있다.
그러면 physical address는 frame number 뒤에 offset을 붙이면 된다.
frame number = 0xABC
offset = 0x345
physical address = 0xABC345
왜 그냥 붙여도 되냐면 page size가 4KB라 offset이 정확히 12bit, 즉 16진수 3자리이기 때문이다.
frame 0xABC의 시작 주소 = 0xABC000
physical address = 0xABC000 + 0x345 = 0xABC345
이 예제에서 핵심은 두 단계다.
1. virtual address를 page number와 offset으로 나눈다.
2. page number를 frame number로 바꾸고 offset은 그대로 둔다.
62. 실제 예제 2: logical address가 잘못된 경우
이번에는 단순한 relocation/limit 방식으로 보자.
조건은 다음과 같다.
relocation register = 10000
limit register = 3000
이 프로세스는 logical address 0부터 2999까지 접근할 수 있다.
접근 1: logical address 1200
1200 < 3000
범위 안이다.
따라서 physical address는 다음과 같다.
10000 + 1200 = 11200
정상 접근이다.
접근 2: logical address 3500
3500 >= 3000
범위를 넘었다.
이때는 physical address를 계산하면 안 된다.
바로 trap이 발생해야 한다.
logical address 3500
↓
limit 위반
↓
protection fault
이 예제에서 중요한 점은 limit check가 address translation보다 먼저 와야 한다는 것이다.
허용되지 않은 주소를 physical address로 바꾸는 순간 이미 보호가 깨진다.
63. 주소 변환 문제를 푸는 고정 순서
시험이나 과제에서 주소 변환 문제가 나오면 다음 순서로 풀면 된다.
1. page size를 확인한다.
2. offset bit 수를 구한다.
3. virtual address를 page number와 offset으로 나눈다.
4. page table에서 page number에 해당하는 entry를 찾는다.
5. valid bit와 protection bit를 확인한다.
6. 유효하면 frame number를 얻는다.
7. physical address = frame number + offset으로 만든다.
8. 유효하지 않으면 page fault 또는 protection fault로 판단한다.
여기서 학생들이 자주 틀리는 부분은 offset이다.
offset은 변하지 않는다.
Page number만 frame number로 바뀐다.
virtual address: [ page number ][ offset ]
↓
physical address: [ frame number ][ offset ]
offset이 그대로인 이유는 page 안에서의 위치와 frame 안에서의 위치가 같기 때문이다.
Part 12. Page table 크기와 TLB 계산을 손으로 해보기
64. Page table 크기 계산의 기본 공식
Page table 크기 문제도 결국 공식은 단순하다.
page 개수 = virtual address space size / page size
page table size = page 개수 * PTE size
예를 들어 다음 조건을 보자.
virtual address space = 4GB
page size = 4KB
PTE size = 4 bytes
먼저 page 개수를 구한다.
4GB = 2^32 bytes
4KB = 2^12 bytes
page 개수 = 2^32 / 2^12 = 2^20
PTE 하나가 4바이트라면 page table 크기는 다음과 같다.
2^20 * 4 bytes = 2^20 * 2^2 = 2^22 bytes = 4MB
즉, 프로세스 하나의 page table만 4MB가 될 수 있다.
처음에는 4MB가 작아 보일 수 있다.
하지만 프로세스가 100개라면 단순 계산으로 400MB다.
그리고 64-bit 주소 공간으로 가면 훨씬 커진다.
그래서 page table 크기 문제는 실제 OS에서 매우 중요하다.
65. 왜 page size를 키우면 page table이 작아지는가
Page size가 커지면 page 개수는 줄어든다.
예를 들어 같은 4GB 주소 공간에서 page size를 4KB에서 8KB로 늘려 보자.
4KB page: 2^32 / 2^12 = 2^20 pages
8KB page: 2^32 / 2^13 = 2^19 pages
page 개수가 절반으로 줄었다.
따라서 page table entry 수도 줄고, page table 크기도 줄어든다.
하지만 page size를 무작정 키울 수는 없다.
왜냐하면 internal fragmentation이 커질 수 있기 때문이다.
예를 들어 어떤 프로세스가 마지막 page에서 100바이트만 사용한다고 하자.
page size 4KB -> 약 3996 bytes 낭비
page size 2MB -> 약 2MB 가까이 낭비 가능
또 page가 커지면 불필요한 데이터까지 같이 memory에 올라올 수 있다.
그래서 page size는 trade-off다.
| page size | 장점 | 단점 |
|---|---|---|
| 작음 | 내부 단편화 적음, 필요한 데이터만 세밀하게 관리 | page table 커짐, TLB coverage 작음 |
| 큼 | page table 작아짐, TLB coverage 커짐 | 내부 단편화 증가, 불필요한 데이터 적재 가능 |
66. TLB coverage라는 감각
TLB entry 하나는 page 하나의 mapping을 담는다.
따라서 TLB가 커버할 수 있는 전체 메모리 범위는 다음과 같다.
TLB coverage = TLB entry 수 * page size
예를 들어 TLB entry가 64개이고 page size가 4KB라면 다음과 같다.
64 * 4KB = 256KB
즉, TLB가 동시에 빠르게 변환해 줄 수 있는 주소 범위는 대략 256KB다.
만약 page size가 2MB인 huge page라면 다음과 같다.
64 * 2MB = 128MB
TLB entry 수는 같아도 page size가 커지면 coverage가 커진다.
그래서 huge page는 큰 메모리 영역을 반복적으로 접근하는 프로그램에서 TLB miss를 줄이는 데 도움이 될 수 있다.
하지만 앞에서 말했듯 internal fragmentation과 allocation 부담이 생긴다.
67. EAT 계산 예제
조건을 잡아 보자.
memory access time = 100ns
TLB lookup time = 10ns
TLB hit ratio = 90%
TLB hit이면 다음 시간이 걸린다.
TLB lookup 10ns + memory access 100ns = 110ns
TLB miss이면 page table을 memory에서 읽고, 실제 memory도 읽어야 한다.
TLB lookup 10ns + page table memory access 100ns + actual memory access 100ns = 210ns
따라서 EAT는 다음과 같다.
EAT = 0.9 * 110ns + 0.1 * 210ns
= 99ns + 21ns
= 120ns
TLB가 없으면 paging 때문에 memory access가 200ns 정도 걸릴 수 있다.
TLB가 있어서 평균이 120ns로 줄었다.
여기서 hit ratio가 얼마나 중요한지 보인다.
68. Page fault까지 포함한 EAT 감각
이번에는 page fault까지 생각해 보자.
조건은 다음과 같다.
memory access time = 100ns
page fault service time = 10ms
page fault rate = 0.001
단위를 맞춰야 한다.
10ms = 10,000,000ns
EAT는 대략 다음과 같다.
EAT = (1 - p) * 100ns + p * 10,000,000ns
p = 0.001
EAT = 0.999 * 100 + 0.001 * 10,000,000
≈ 99.9 + 10,000
≈ 10,099.9ns
Page fault rate가 0.1퍼센트밖에 안 되는데 평균 접근 시간이 100ns에서 약 10,000ns로 늘었다.
이 예제의 메시지는 강하다.
Page fault는 너무 비싸서, 아주 작은 확률로만 발생해도 평균 성능을 크게 망칠 수 있다.
그래서 virtual memory 시스템은 page fault rate를 낮게 유지하는 것이 매우 중요하다.
Part 13. Page replacement를 직접 손으로 돌려보기
69. Replacement 문제의 기본 형태
Page replacement 문제는 보통 이렇게 나온다.
frame 수 = 3
reference string = 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
각 숫자는 접근한 page number다.
frame이 3개뿐이므로 동시에 page 3개만 memory에 둘 수 있다.
새 page를 접근했는데 memory에 없으면 page fault가 난다.
frame이 비어 있으면 그냥 넣으면 된다.
frame이 꽉 차 있으면 replacement algorithm에 따라 victim을 고른다.
70. FIFO로 돌려보기
FIFO는 먼저 들어온 page를 먼저 내보낸다.
frame 수가 3이고 reference string이 다음과 같다고 하자.
7, 0, 1, 2, 0, 3, 0, 4
처음에는 frame이 비어 있다.
접근 7: fault, [7]
접근 0: fault, [7, 0]
접근 1: fault, [7, 0, 1]
이제 frame이 꽉 찼다.
다음 page 2는 없다. FIFO에서는 가장 먼저 들어온 7을 내보낸다.
접근 2: fault, 7 제거 -> [0, 1, 2]
다음 page 0은 이미 있다.
접근 0: hit, [0, 1, 2]
다음 page 3은 없다. FIFO 기준 가장 오래된 page는 0이다.
접근 3: fault, 0 제거 -> [1, 2, 3]
바로 다음에 0을 다시 접근한다.
접근 0: fault, 1 제거 -> [2, 3, 0]
이 장면에서 FIFO의 약점이 보인다.
0은 방금 hit가 났던 page다. 최근에 쓰였는데도 “오래 전에 들어왔다”는 이유로 쫓겨났다.
FIFO는 단순하지만 locality를 잘 반영하지 못한다.
71. LRU로 돌려보기
LRU는 가장 오래 사용되지 않은 page를 내보낸다.
같은 예제를 보자.
reference string = 7, 0, 1, 2, 0, 3, 0, 4
frame 수 = 3
처음 세 개는 fault다.
7 -> fault, [7]
0 -> fault, [7, 0]
1 -> fault, [7, 0, 1]
2를 접근한다.
현재 7, 0, 1 중 가장 오래 사용되지 않은 것은 7이다.
2 -> fault, 7 제거, [0, 1, 2]
0을 접근한다.
0 -> hit, [0, 1, 2]
이제 최근 사용 순서는 대략 다음과 같다.
가장 최근: 0
그 전: 2
가장 오래됨: 1
3을 접근한다.
LRU는 1을 제거한다.
3 -> fault, 1 제거, [0, 2, 3]
다시 0을 접근한다.
0 -> hit, [0, 2, 3]
4를 접근한다.
현재 0, 2, 3 중 가장 오래 사용되지 않은 것은 2다.
4 -> fault, 2 제거, [0, 3, 4]
LRU는 FIFO보다 locality를 더 잘 반영한다.
하지만 실제 OS에서 정확한 LRU를 구현하려면 모든 memory reference의 시간을 추적해야 해서 비용이 크다.
72. Optimal은 왜 이론용인가
Optimal은 앞으로 가장 늦게 다시 쓰일 page를 제거한다.
예를 들어 현재 frame이 다음과 같다고 하자.
frames = [0, 1, 2]
앞으로의 reference = 0, 3, 0, 4, 2, 3
새 page 3을 넣어야 한다면 0, 1, 2 중 하나를 빼야 한다.
미래를 보면 다음과 같다.
0은 곧 다시 쓰임
2는 나중에 쓰임
1은 앞으로 안 쓰임
따라서 optimal은 1을 제거한다.
이것이 가장 좋다.
하지만 OS는 실제 실행 중에 미래 reference string을 모른다.
그래서 optimal은 현실 구현용이라기보다 다른 알고리즘을 평가할 때 기준으로 쓴다.
73. Clock algorithm을 감각적으로 이해하기
Clock algorithm은 LRU를 정확히 구현하지 않고 비슷하게 흉내 내는 방법이다.
각 page에는 reference bit가 있다.
reference bit = 1 -> 최근 접근됨
reference bit = 0 -> 최근 접근 증거 없음
clock hand가 원형으로 page들을 돈다.
[ page A, ref=1 ] <- hand
[ page B, ref=0 ]
[ page C, ref=1 ]
victim을 찾아야 할 때 hand가 page를 본다.
- ref가 1이면 0으로 바꾸고 넘어간다.
- ref가 0이면 victim으로 선택한다.
이것이 second chance다.
최근에 접근된 page에게 한 번 더 기회를 주는 것이다.
정확한 LRU는 아니지만, hardware bit 하나로 어느 정도 locality를 반영할 수 있다.
Part 14. Page fault, COW, mmap을 사건 흐름으로 보기
74. Demand paging page fault 사건 기록
프로그램이 어떤 주소 X를 읽으려고 했다고 하자.
load R1, [X]
이때 X가 속한 page가 memory에 없다.
사건은 이렇게 진행된다.
1. CPU가 load 명령을 실행한다.
2. MMU가 X의 page table entry를 확인한다.
3. valid bit가 0이다.
4. MMU가 page fault trap을 발생시킨다.
5. CPU는 kernel mode로 전환한다.
6. OS page fault handler가 실행된다.
7. OS는 X가 프로세스의 유효한 주소인지 확인한다.
8. 유효하지 않으면 segmentation fault 처리한다.
9. 유효한 주소라면 backing store에서 page 위치를 찾는다.
10. free frame을 찾는다.
11. free frame이 없으면 replacement로 victim을 고른다.
12. victim이 dirty면 disk에 write-back한다.
13. 필요한 page를 disk에서 frame으로 읽어온다.
14. page table entry를 valid로 바꾸고 frame number를 기록한다.
15. fault를 낸 load 명령을 다시 실행한다.
16. 이번에는 page가 memory에 있으므로 성공한다.
프로그램 입장에서는 그냥 load가 조금 오래 걸린 것처럼 보인다.
하지만 OS 내부에서는 많은 일이 일어난다.
75. COW page fault 사건 기록
이번에는 fork() 이후 부모와 자식이 같은 frame을 공유하고 있다고 하자.
parent page table -> frame A
child page table -> frame A
둘의 PTE는 read-only처럼 표시되어 있고, COW 상태가 기록되어 있다.
자식이 해당 page에 write하려고 한다.
child: k = 1
사건은 이렇게 진행된다.
1. child가 COW page에 write를 시도한다.
2. PTE가 writable이 아니므로 protection fault가 발생한다.
3. OS page fault handler가 실행된다.
4. OS는 이것이 진짜 illegal write인지 COW write인지 확인한다.
5. COW write라면 새 frame B를 할당한다.
6. frame A의 내용을 frame B로 복사한다.
7. child의 PTE가 frame B를 가리키도록 바꾼다.
8. child의 PTE에 write permission을 준다.
9. child의 명령을 다시 실행한다.
10. child는 frame B에 값을 쓴다.
결과는 다음과 같다.
parent -> frame A, old value
child -> frame B, new value
중요한 점은 COW fault가 “page가 RAM에 없어서” 발생한 것이 아니라는 점이다.
Page는 이미 RAM에 있었다.
다만 공유 중인 page에 쓰려고 해서 OS가 복사하려고 개입한 것이다.
76. mmap page fault 사건 기록
이번에는 파일을 mmap했다고 하자.
file data.bin
page 0
page 1
page 2
process address space
virtual page 100 -> file page 0
virtual page 101 -> file page 1
virtual page 102 -> file page 2
처음에는 실제 파일 page가 memory에 없을 수 있다.
프로세스가 virtual page 101에 접근한다.
value = mapped_region[4096]
사건은 이렇게 진행된다.
1. CPU가 mapped address에 접근한다.
2. MMU가 PTE를 확인한다.
3. 해당 file-backed page가 아직 memory에 없어서 page fault가 난다.
4. OS는 이 주소가 mmap된 파일 영역임을 확인한다.
5. 파일의 해당 offset을 계산한다.
6. page cache 또는 storage에서 file page를 가져온다.
7. physical frame에 file page 내용을 올린다.
8. PTE를 frame에 연결한다.
9. 명령을 다시 실행한다.
쓰기 접근이면 해당 page가 dirty가 될 수 있다.
나중에 OS는 dirty page를 파일로 flush한다.
memory write
↓
dirty file-backed page
↓
msync / munmap / OS write-back policy
↓
file updated
Part 15. 이해를 확인하는 긴 연습 문제
77. 연습 1: 주소 변환하기
조건은 다음과 같다.
page size = 1KB
virtual address = 2500
page table:
page 0 -> frame 4
page 1 -> frame 9
page 2 -> frame 1
page 3 -> frame 7
1KB는 1024 bytes다.
먼저 virtual address 2500을 page number와 offset으로 나눈다.
2500 ÷ 1024 = 2 ... 452
page number = 2
offset = 452
page table을 보면 page 2는 frame 1에 있다.
frame size도 1024 bytes다.
frame 1 시작 주소 = 1 * 1024 = 1024
physical address = 1024 + 452 = 1476
정답은 1476이다.
여기서 page number 2가 frame number 1로 바뀌었고, offset 452는 그대로 유지되었다.
78. 연습 2: page table 크기 계산하기
조건은 다음과 같다.
virtual address = 32bit
page size = 8KB
PTE size = 4 bytes
8KB는 2^13 bytes다.
32bit 주소 공간은 2^32 bytes다.
따라서 page 개수는 다음과 같다.
2^32 / 2^13 = 2^19 pages
PTE 하나가 4 bytes, 즉 2^2 bytes다.
page table size = 2^19 * 2^2 = 2^21 bytes
2^20 bytes가 1MB이므로, 2^21 bytes는 2MB다.
정답은 2MB다.
79. 연습 3: TLB hit ratio가 바뀌면 어떻게 되는가
조건은 다음과 같다.
TLB lookup = 5ns
memory access = 100ns
TLB hit time = 5 + 100 = 105ns
TLB miss time = 5 + 100 + 100 = 205ns
hit ratio 99퍼센트
EAT = 0.99 * 105 + 0.01 * 205
= 103.95 + 2.05
= 106ns
거의 memory access 1번과 비슷하다.
hit ratio 80퍼센트
EAT = 0.8 * 105 + 0.2 * 205
= 84 + 41
= 125ns
아직 나쁘지 않지만 차이가 난다.
hit ratio 50퍼센트
EAT = 0.5 * 105 + 0.5 * 205
= 52.5 + 102.5
= 155ns
TLB hit ratio가 낮아질수록 paging의 주소 변환 비용이 점점 드러난다.
80. 연습 4: Thrashing 상황 판단하기
어떤 시스템에 프로세스 4개가 있고, 각 프로세스의 working set 크기가 다음과 같다고 하자.
P1 working set = 10 frames
P2 working set = 15 frames
P3 working set = 20 frames
P4 working set = 25 frames
전체 physical frame은 60개다.
전체 working set 합은 다음과 같다.
10 + 15 + 20 + 25 = 70 frames
필요한 working set은 70인데 실제 frame은 60이다.
모든 프로세스의 working set을 동시에 memory에 유지할 수 없다.
이 상황에서는 page fault가 많아지고 thrashing 위험이 있다.
OS가 할 수 있는 일은 다음과 같다.
- 어떤 프로세스를 swap out해서 degree of multiprogramming을 낮춘다.
- page fault frequency가 높은 프로세스에 frame을 더 준다.
- 전체적으로 memory pressure를 낮춘다.
핵심은 무조건 프로세스를 많이 올리는 것이 좋은 게 아니라는 점이다.
81. 연습 5: COW와 일반 page fault 구분하기
다음 두 상황을 비교하자.
상황 A
프로세스가 valid bit가 0인 page에 접근했다.
그 page는 프로세스의 주소 공간에는 있지만 아직 memory에 없다.
이 경우는 demand paging page fault다.
OS는 backing store에서 page를 가져와 frame에 올린다.
상황 B
fork() 이후 parent와 child가 같은 frame을 공유하고 있다.
Child가 그 page에 write하려고 했다.
이 경우는 COW page fault다.
OS는 새 frame을 할당하고 기존 내용을 복사한 뒤 child의 PTE를 새 frame으로 바꾼다.
둘 다 page fault handler가 처리하지만 원인은 다르다.
Demand paging fault:
page가 memory에 없음
COW fault:
page는 memory에 있지만 공유 상태라 write 전에 복사해야 함
Part 16. 마지막 복습: 이 단원을 내 말로 설명하기
82. 1분 설명 버전
운영체제의 메모리 관리는 프로세스에게 자기만의 주소 공간이 있는 것처럼 보이게 하면서, 실제로는 한정된 물리 메모리를 안전하고 효율적으로 나누는 일이다.
CPU는 logical address를 만들고, MMU는 page table과 TLB를 이용해 physical address로 변환한다.
Paging은 주소 공간을 page로 나누고 물리 메모리를 frame으로 나누어, 프로세스의 page를 아무 free frame에나 배치할 수 있게 한다. 그래서 external fragmentation을 줄일 수 있다.
하지만 paging은 주소 변환 비용과 page table 크기 문제가 생기므로 TLB와 hierarchical page table 같은 구조가 필요하다.
Virtual memory는 프로세스의 모든 page를 처음부터 memory에 올리지 않고, 실제로 접근할 때 page fault를 통해 가져오는 방식이다.
Page fault가 너무 많으면 thrashing이 생기므로 replacement algorithm, working set, PFF 같은 정책이 필요하다.
OS는 이 구조를 활용해 Copy-on-Write, memory-mapped file, kernel memory allocator 같은 기법도 구현한다.
83. 10초 설명 버전
운영체제 메모리 관리는 “프로세스에게는 큰 자기 주소 공간처럼 보여 주고, 실제 RAM은 page 단위로 필요한 만큼만 안전하게 연결해 주는 기술”이다.
84. 개념별로 딱 한 문장씩
- Logical address: 프로세스가 자기 주소 공간 안에서 만든 주소다.
- Physical address: 실제 RAM에서 접근하는 주소다.
- MMU: logical address를 physical address로 바꾸는 하드웨어다.
- Relocation register: 프로세스가 물리 메모리에서 시작하는 위치를 더해 주는 값이다.
- Limit register: 프로세스가 자기 범위를 넘지 못하게 막는 값이다.
- Contiguous allocation: 프로세스를 물리 메모리의 연속된 공간에 통째로 배치한다.
- Segmentation: 주소 공간을 code, data, stack 같은 의미 단위로 나눈다.
- Paging: 주소 공간을 고정 크기 page로 나누고, 물리 메모리를 frame으로 나눈다.
- Page table: page number를 frame number로 바꾸는 표다.
- TLB: 자주 쓰는 주소 변환 결과를 저장하는 작은 하드웨어 캐시다.
- Hierarchical page table: page table 자체를 여러 단계로 나누어 메모리 낭비를 줄인다.
- Virtual memory: 전체 주소 공간이 있는 것처럼 보이게 하되, 실제 memory에는 필요한 page만 올린다.
- Demand paging: page가 실제로 필요할 때 가져온다.
- Page fault: 필요한 page가 memory에 없거나 권한 문제가 있어 OS가 개입하는 사건이다.
- Page replacement: free frame이 없을 때 어떤 page를 내보낼지 정하는 정책이다.
- Working set: 최근에 실제로 사용 중인 page들의 집합이다.
- Thrashing: page fault 처리만 하느라 실제 일을 못 하는 상태다.
- Copy-on-Write: write가 발생할 때까지 page 복사를 미루는 기법이다.
- mmap: 파일을 프로세스 주소 공간에 매핑해 메모리처럼 접근하는 방식이다.
- Buddy system: 커널이 연속된 physical page block을 관리하는 기법이다.
- Slab allocator: 자주 쓰는 커널 객체를 cache로 만들어 빠르게 재사용하는 기법이다.
85. 진짜 마지막 체크리스트
이 단원을 이해했는지 확인하려면 아래 질문에 답해 보면 된다.
[ ] logical address와 physical address의 차이를 설명할 수 있다.
[ ] MMU가 왜 필요한지 설명할 수 있다.
[ ] relocation/limit 방식의 주소 변환을 계산할 수 있다.
[ ] contiguous allocation의 external fragmentation을 설명할 수 있다.
[ ] segmentation과 paging의 차이를 설명할 수 있다.
[ ] page number와 offset을 나눌 수 있다.
[ ] page table을 이용해 physical address를 계산할 수 있다.
[ ] TLB hit/miss가 EAT에 미치는 영향을 계산할 수 있다.
[ ] page table 크기를 계산할 수 있다.
[ ] hierarchical page table이 왜 메모리를 아끼는지 설명할 수 있다.
[ ] demand paging과 page fault 흐름을 순서대로 말할 수 있다.
[ ] page replacement 알고리즘의 차이를 설명할 수 있다.
[ ] thrashing과 working set의 관계를 설명할 수 있다.
[ ] COW fault와 demand paging fault를 구분할 수 있다.
[ ] mmap이 일반 read/write와 어떻게 다른지 설명할 수 있다.
[ ] buddy system과 slab allocator의 목적 차이를 설명할 수 있다.
이 체크리스트를 대부분 설명할 수 있으면, 메모리 단원의 뼈대는 잡힌 것이다.
참고한 기존 Obsidian 노트와 원본 영상
이 통합본은 아래 10개 Obsidian 정리본을 흐름에 맞춰 다시 풀어쓴 것이다.
