CSAPP (p.869 ~ 890)
Memory Mapping
가상 메모리 area를 디스크에 저장된 object와 연결함으로써 가상 메모리 내용을 초기화하는 과정
area는 다음 두 종류의 object에 매핑 가능함
1. 리눅스 파일 시스템 내 일반 파일
area는 파일의 연속적인 section에 매핑되며, 요구 페이징에 의해 실제 페이지가 참조될 때까지 가상 페이지는 물리 메모리에 스왑 인 되지 않음
2. 익명 파일
익명 파일은 커널에 의해 생성되며, binary zero만으로 구성됨, 해당 파일에 매핑된 area에 속한 페이지가 참조되어도, 디스크와 물리 메모리 간 데이터 전송이 이루어지지 않음 (따라서, 익명 파일은 demand-zero 페이지라고도 불림)
가상 페이지가 초기화되면 물리 페이지와 커널 내 스왑 파일 간에 스왑 인/아웃 과정을 거침
실행 중인 모든 프로세스의 할당된 가상 페이지 전체 용량은 스왑 영역의 크기를 넘을 수 없음
shared/private object
여러 프로세스가 가상 메모리 area에 shared object를 매핑하면 물리 메모리에 object의 복사본은 하나만 저장됨
private object는 가상 메모리에 매핑될 때 copy-on-write technique이 사용됨
private area(private object에 매핑되는 가상 메모리 area)는 private copy-on-write로, 해당 area의 PTE는 read-only로 표시됨
여러 프로세스가 가상 메모리 area에 private object를 매핑해도, 읽기만 한다면 물리 메모리 내에는 object의 복사본이 하나만 존재함
하지만 쓰기가 발생하면 protection fault가 발생하고(RO이므로), fault handler는 프로세스가 copy-on-write area에 속한 페이지에 쓰려고 해서 fault가 발생했음을 알게 됨
핸들러는 해당 페이지를 물리 메모리에 복사하고, PTE를 업데이트하고, 해당 페이지에 쓰기 권한을 부여함
fork 함수도 copy-on-write를 사용
execve 시스템 콜
해당 함수는 현재 프로세스의 context 내에서 executable object file을 로드하고 실행시킴
실행 과정은 다음과 같음
1. 사용자 영역을 삭제
2. private area 매핑
3. shared area 매핑
4. PC를 코드 영역의 엔트리 포인트로 설정
Dynamic Memory Allocation
dynamic memory allocator는 런타임에 가상 메모리를 추가할 수 있도록 하고, heap area를 관리함
커널은 brk 변수에 힙 영역 최상단 주소를 저장함
allocator는 힙 영역을 다양한 크기의 블록 집합으로 관리하고, 각 블록은 연속된 덩어리로서 allocated 또는 free 상태임
allocator에는 두 종류가 있음
1. explicit allocator
application이 explicit하게 할당된 블록을 free해줘야 함
2. implicit allocator
할당된 블록이 더 이상 사용되지 않을 때 allocator가 이를 탐지하고 자동으로 free해주는데, 이 과정을 garbage collection이라고 부름 (implicit allocator는 garbage collector라고도 부름)
Allocator Requirements and Goals
allocator는 다음과 같은 엄격한 제약조건을 지키며 동작해야 함
1. arbitrary request sequences를 처리해야 함
2. 요청에 대해 바로 응답해야 함 (응답 순서를 바꾸거나 버퍼링할 수 없음)
3. 힙 영역만 사용
4. alignment requirement를 만족시켜야 함
5. 할당된 블록을 변경/이동할 수 없음 (free 블록만 조작 가능)
allocator는 다음과 같은 목표를 가짐
1. throughput을 최대화하기
throughput은 단위 시간에 처리할 수 있는 요청 수로 정의됨
2. 메모리 활용 최대화하기 (효율적으로 사용하기)
할당된 가상 메모리의 최대 크기는 스왑 영역 크기에 의해 제한되므로, 가상 메모리는 무한한 자원이 아님
allocator가 힙 영역을 얼마나 효율적으로 사용하는지는 peak utilization이라는 지표로 알 수 있음
두 목표는 충돌하므로 균형을 잘 맞춰야 함
Fragmentation
힙 영역의 활용도를 떨어뜨리는 주요 원인은 단편화임
단편화에는 두 종류가 있음
1. 내부 단편화
할당된 블록이 페이로드보다 큰 경우
allocator가 부여한 할당 블록의 최소 크기가 페이로드보다 크거나, alignment 제약조건을 만족시키기 위해 블록 크기를 늘린 경우 일어남
2. 외부 단편화
메모리 할당 요청을 만족시킬 수 있는 양의 free memory가 존재하지만 작게 나눠져 있어서 요청을 처리할 수 없는 경우
과거 요청 패턴, allocator의 구현뿐만 아니라 미래 요청 패턴에 의존하므로 정량화하기 어려움
Implementation Issues
allocator를 구현할 때는 다음 사항을 고려해야 함
1. Free block organization
2. Placement
3. Splitting
4. Coalescing
Implicit Free Lists
간단한 free block organization 중 하나
allocator는 블록 경계와 할당 여부를 판별하기 위해 자료구조가 필요함
implicit free list를 사용하는 경우 블록은 one word(4-byte) 헤더, 페이로드, 패딩으로 구성됨
헤더에는 블록 크기와 할당 여부를 나타내는 비트가 저장됨
이 방법은 간단하지만 free 블록 리스트를 찾는 시간이 힙 영역 내 모든 블록 수에 비례한다는 단점을 가짐
Placement Policy
메모리 할당 요청이 들어왔을 때 어떤 free block을 선택할 것인지 결정하는 정책
1. First fit
요청을 만족하는 첫 블록을 선택
2. Next fit
이전 탐색이 끝났던 지점부터 탐색 시작
3. Best fit
모든 free 블록을 탐색하고 요청을 만족하는 가장 작은 블록을 선택
Splitting Free Blocks
요청을 만족하는 free block을 찾은 후 해당 블록을 얼마나 할당할 것인지 결정해야 함
전부 할당하는 경우 간단하고 빠르지만, 내부 단편화가 발생할 수 있음
placement policy가 fit한 블록을 잘 선택해주는 경우 위 방법을 선택해도 되지만, 그렇지 않은 경우 free 블록을 쪼개서 할당 블록과 free 블록으로 나눠 사용함
Getting Additional Heap Memory
할당 요청을 만족하는 블록이 없을 때는 인접한 여러 free block을 합치고, 이 방법도 통하지 않는 경우 allocator는 sbrk 시스템 콜을 호출해서 커널로부터 추가적인 힙 메모리를 할당받음
이 메모리 영역은 하나의 큰 free block이 되어 free list에 추가되고, 요청을 처리하는 데 사용됨
Coalescing Free Blocks
인접한 free 블록들은 false fragmentation을 유발할 수 있음
따라서, coalescing 과정을 통해 병합되어야 함
언제 coalescing을 수행할 것인지에 따라 immediate coalescing과 deferred coalescing으로 나누어짐
Coalescing with Boundary Tags
블록을 free할 때 다음 블록은 현재 블록의 헤더 정보를 사용해서 찾아갈 수 있지만, 이전 블록을 찾으려면 처음부터 탐색해야 함
따라서 각 블록의 마지막에 헤더 정보를 복제한 푸터(boundary tag)를 추가함
각 블록은 헤더와 푸터를 가지게 되므로 상당한 메모리 오버헤드를 유발할 수 있는데, 할당 블록의 경우 푸터를 없애고 블록에 이전 블록의 할당 여부를 저장하게 함으로써 이를 완화할 수 있음
