옛날에는 많은 추상화를 제공하지 않았다. 또 그럴 필요도 없었다. 메모리 내부 공간을 하나의 프로세스가 차지하는 게 편리하기도 했고, 그 당시에는 실행 파일이 그렇게 크지 않았기 때문이다. 최근들어 프로세스의 양도 많아지고, 용량도 커짐에 따라 이와 같은 방식을 활용하는 데 제약이 생겼다.
Multiprogramming, Time sharing
하나의 CPU에서 여러 프로세스를 가동함으로써 사용성을 높인다. 사용자에게는 ‘동시에‘ 여러 일을 하는 것처럼 보이게 한다. 가상화의 시작이 되는 순간이다. 이때 문제가 발생할 수 있다. 메모리에서는 다양한 프로세스가 올라가 있으므로, 보안상 다른 프로세스의 영역에는 접근하거나 쓰지 못하도록 막아야 한다.
Address space의 등장
Physical memory를 추상화한 메모리 공간이 등장한다. 프로세스의 관점에서는 모든 메모리를 사용한다고 느끼지만, 실제 물리적 메모리에서는 그렇지 않다. Program code, Heap, Stack이 한 번에 할당되는 방식. 프로세스 입장에서는 모든 메모리를 사용한다고 생각하니 다른 프로세스의 영역에 침범하는 것이 어려워진다. OS가 이를 담당하도록 한다.malloc 등의 라이브러리 콜(시스템 콜 아님, srk, sbrk 참고)을 활용해 힙 영역을 조절한다.
Address translation (Hardware-based)
물리 메모리 영역과 가상 메모리 영역이 차이가 생기므로, 이를 변환할 역할이 필요하다. 하드웨어 자체는 가상화하는 것이 불가능하므로, OS가 중간에서 돕는다. 이상적인 상황이라면 아래와 같은 경우를 생각할 수 있다
- 연속된 메모리 공간에 매핑된다.
- Address space가 크지 않고, 각각 같은 크기를 가진다.
간단한 Base and bound를 통해 변환할 수 있다
Segmentation
Heap과 Stack 사이에 큰 공간이 발생하고, 사용하지도 않을 공간을 점유하는 것은 곧 메모리 낭비다. 32-bit address space를 활용한다면, $2^{32}=2^2\times 2^{30}$, 프로세스 당 4GB의 메모리를 사용하게 된다 (Internal Fragmentation). 따라서 연속된 메모리 공간에 매핑되는 것을 내려두고, 각 Segment에 대해서 (Code, Heap, Stack) base and bound를 적용하도록 한다. 정말 사용중인 것만 물리적 메모리에 할당한다.
Address translation on segmented area
16KB Address space의 경우, 앞쪽 2개의 bit를 사용해 14-bit addressing이 가능하다. 나아가 Code의 경우 Read-only인 점을 감안해 같은 코드를 사용하는 여러 프로세스가 서로 코드를 공유할 수 있다.
코드, 스택, 힙으로 크게 나누면 관리에는 용이할 지 몰라도, 여전히 빈 공간을 효율적으로 관리하기 어렵다. 더 잘게 쪼개면 어떨까? → Segment table. Base는 register에 저장해 사용하지만, Base가 여러개가 되니 테이블을 만들어 관리해야 함.
Course-grained segmentation, Free-list management algorithms
OS가 메모리 할당 요청을 받으면, 물리적 메모리 중 빈 공간 Segment 중 용량이 있는지 확인한 뒤 할당한다. Segment는 프로세스마다 있으니 빈 공간의 크기는 서로 다르다. 물리 메모리는 빈 공간이 점점 많아지니 할당하기 더 어려워진다. 원하는 용량보다 작은 빈 공간이 발생한다. 이를 External Fragmentation이라고 한다. 해결하기 위해서는 조각모음을 하듯이 Compaction을 진행해야 하는데, 모든 시스템이 멈춰야하는 문제가 발생한다.
최대한 이런 일이 발생하는 것을 줄이고자 여러 알고리즘이 고안된다. Best/Worst/First fit, Buddy 알고리즘 등이다.
→ Buddy 알고리즘에서도 절반으로 줄여가면서 내가 원하는 용량을 찾는 거라, 필요한 것보다 더 많은 메모리가 할당되는 Internal Fragmentation이 발생할 수 있다.
Paging
Segment는 고려할 게 너무 많았다. External fragmentation으로 메모리 할당이 어려워 physical compaction이 이뤄져야 한다는 점, Heap/Stack이 자라나는 방향이 서로 달라 위치를 고려하기 힘들다는 점 등이다. 메모리를 일정 단위로 쪼갠 다음에, 필요한 만큼 사용하면 어떨까? 라는 생각으로부터 시작된 것이 Paging이다. Paging은 Segmentation과 비슷한 면이 있지만, 각각을 같은 크기의 단위로 쪼개니 매핑에서의 문제가 완화된다 (해결되는 것은 아니다).
→ 프로세스가 얼마나 많은 메모리를 썼든, 페이지 크기만큼만 신경써도 된다.
Page table
매핑에는 반드시 변환이라는 오버헤드가 따른다. 이를 얼마나 최적화하느냐가 OS의 속도를 좌우한다.
페이지 내부의 Offset은 서로 같으니, 가상 페이지 → 물리 페이지로 변환하는 작업만 진행하면 된다. 64byte address space에서는 사용하는 경우 6-bit addressing을 활용할 수 있으며, 이를 네 개로 나누어 6bit 중 앞 두개는 페이지 번호, 뒤 네 개는 오프셋으로 활용할 수 있다.
Page table gets huge
페이징 변환에 사용되는 테이블은 웬만하면 메모리에 올리는 편이 좋다. 빠른 속도를 보장해야 사용자가 불편함을 가지지 않을 테니까. 하지만 32-bit address space에서 4KB Paging을 활용한다고 해 보자.
4KB = $2^{12}$, 남은 20-bit는 Paging number로 활용. 총 $2^{20}$개의 페이지 테이블을 관리. 하나의 PTE에 4Byte(32 bit on x86-32 PTE)가 필요하므로, 총 $4 \times 2^{20}$ byte = 4MB의 메모리가 필요하다.
프로세스 하나에, 그것도 실제로 사용하는 게 아니라 페이지를 관리하는 데에만 4MB가 들어가는 건 너무 크다. 속도가 빠른 하드웨어에 관리하는 건 어려워지지 않을까? 그렇다고 IO가 큰 곳에 저장하면 프로그램이 실행될 때 실제 메모리를 찾아가는 데 오랜 시간이 걸린다.
Memory management unit, Translation lookaside buffer
IO가 커지는 것은 감수해야 하니 그와중에 최대한 줄일 수 있는 방법을 찾아보자. 매핑 정보가 많이 생성되므로 이는 작고 빠른 하드웨어가 감당할 수 없다. OS는 어떤 방식으로 이를 효율적으로 관리할까?
MMU가 메모리와 관련한 것을 관리한다. 이 안에 TLB와 Page table이 들어있다. 상대적으로 메모리보다는 빠르지만, 그만큼 모든 페이지를 관리할 만큼 큰 용량을 가지고있지 않다. 따라서 TLB Miss는 곧 IO 연산을 의미한다. 어떻게 보면 TLB는 주소 변환 캐시를 담당한다.
여기서 OS가 TLB 관리를 위해 힘쓴다. Spatial locality, Temporal locality를 생각해서 해당 페이지의 다음 것까지 prefetch해오기도 한다.
Handling TLB Miss
TLB Miss가 발생하면 어떤 식으로 대처하는지는 하드웨어에 따라 다르다. 구체적으로는 CISC, RISC에 따라서 달라진다.
RISC는 OS에서 관리하도록 하는데, TLB Miss Trap → PTE 찾고 갱신 → User mode 전환 및 Hit와 같이 동작한다.
Page table의 주소를 찾기 위해 Handler search → TLB Miss → …와 같은 문제가 발생할 수 있다. 이는 물리적 주소를 그대로 박아두거나, TLB의 일정 공간을 Evict하지 않도록 wiring해둠으로써 해결할 수 있다.
Replacement policy
TLB 뿐만 아니라, 여러 캐싱 전략에서 사용될 수 있다. 이는 미래를 모르기 때문에 여러 전략이 파생되었으므로, 그때그때 적합한 알고리즘을 택하는 것이 좋다. LRU, Random 등..
Reducing page table size
Linear page table의 경우 너무 많은 PTE를 가져야 하고, 프로세스 당 4MB 정도 되는 큰 양을 가지고있어야 한다. 이를 어떻게 하면 줄일 수 있을까? 처음으로 생각할 수 있는 건 PTE 자체의 양을 줄이는 거다. 이는 Page 크기를 키움으로써 달성할 수 있다. 하지만 메모리를 페이지 단위로 관리하는데 페이지 크기가 커지면..? Internal fragmentation이 발생한다…
Hybrid approach: Paging + Segmentation
세그먼트 안에 페이징을 넣는 시도를 한다. 우선 전체 Paging이 사용되지 않음에도 페이지 테이블이 이를 관리해야 하니, 사용하지 않는 것을 실제 테이블에서 관리하지 않으려 시도한다. Invalid bit의 활용 대신, base-bound를 확인해 Segfault를 발생할 수 있으니 사용하지 않는 페이지 개수만큼 절약할 수 있다. 하지만 arbitary size of memory를 사용하고, base-bound를 활용하는 segmentation이다보니 External fragmentation도 발생하고… PTE 자체의 양은 줄어들지만서도 관리에 꽤나 애를 먹는다.
Multi-level page tables
Page table을 트리로 관리한다. 페이지를 페이징한다(…)는 느낌이 강하다. 페이지 하나의 전체 PTE가 invalid하다면 해당 페이지를 테이블에 두지 않도록 하는 식이다. first-level page table에는 포인터와 같이 valid 여부와 해당 page를 가리키는 번호가 들어있고, second-level page table에는 실제 PTE가 들어있는 식. 메모리가 sparse할 수록 더 이점을 가져간다.
공간을 크게 절약할 수 있다는 장점이 있다. 다만 TLB Miss 시에 OS가 핸들링하는 게 복잡해진다는 문제나 두 번 메모리 참조를 해야 하니 느려진다는 단점이 있다.
x86-64에서는 PML4 – PDPT – PD – PT로 이어지는 4-Level paging을 사용한다.
운영체제 참 재미있게 들었는데, 그 이유를 생각해보면 교수님이 흐름을 정말 잘 설명해주셔서라고 생각한다. 역사를 배우는 것처럼 왜 탄생했을까? 뭐가 불편한가? 에 집중하다 보면 어느새 금방 많은 것을 학습하게 되는 듯? 🔥