메모리 가상화 하는 여러 가지 방법을 배웠다.
1. Time Sharing
한 process가 memory 전체를 사용한다.
disk에 있는 process가 실행될때 마다 메모리에 전부 load를 한다. context switching이 일어나면 메모리에 있는거 전부 없애고 새로운 process에 대한 내용을 disk에서 전부 또 load한다.
말로만 들어도 오버헤드가 쩐다. disk는 참 느린 하드웨어이기 때문에 이건 진짜 성능이 구리다
2. Static Relocation
프로그램이 load될때마다 주소를 rewrite한다. 한 프로그램에 대해서 fork를 두번 하면 서로 다른 주소로 메모리에 매핑된다.
문제는 한 프로세스가 다른 프로세스의 영역을 침범할 수 있다. 그리고 한번 로드 되면 메모리에서 없애지도 못한다.
3. Dynamic Relocation : base register
process가 메모리에 load될때 가상 주소에 base register를 더한 영역에 load된다. 이때부터 MMU가 등장한다. MMU가 커널모드인지, user모드인지 보고, 커널모드면 주소를 그대로 사용한다. user모드면 가상 주소에 base register를 더해서 물리적 주소로 바꾼다.
메모리에 로드된 다음에 프로세스를 없앨 수 있다는 장점은 있지만 여전히 다른 프로세스 영역에 침범하는 문제는 해결하지 못했다.
4. Dynamic Relocation : base regeister + bound register
이제 bound register라는 것까지 둔다. 3번과 같이 kernel mode이면 가상 주소를 그대로 사용한다. 근데 user모드면 먼저 가상 주소가 bound register값보다 작은지 확인한다. 크면 exception을 raise한다. 작으면 ok다. base register값을 더해서 물리적 주소로 만든다.
이렇게 다른 프로세스의 영역에 침범하는 문제를 해결했다!
하지만 세상은 호락호락하지 않다. code, heap, stack이 메모리에 contiguous하게 할당이 되기 때문에 각 프로세스와 프로세스 사이의 빈 공간이 발생하게 된다. 빈 공간에 다른 프로세스를 넣으려니 그러기엔 또 크기가 작다. fragmentation 문제가 발생하는 것이다.
5. Segmentation
위에서 문제가 뭐였냐면 빈 공간에 뭘 넣기엔 code, heap, stack 영역을 다 합친 address space하나의 크기가 넘 크다는 것이다. 그럼 나누자!
code, heap, stack 각각을 segmentation으로 하고 segmentation 각각에 base, bound register를 둔다. 이제 각 프로세스마다 6개의 레지스터가 필요하게 되었다!
근데 os 입장에서는 이 segmentation이 code인지, stack인지, heap인지 구분할 수가 없다. 따라서 가상주소의 처음 2bit는 segmentation을 구분하는 데 쓰인다. 나머지 bit는 offset이다.
이렇게 열심히 segmentation을 했지만 fragmentation 문제를 완전히 해결하지는 못했다. 빈 공간이 존나 많은데 그 빈공간 하나는 또 존나 작아서 segmentation 하나 못 들어 가면 이건 무슨 낭비란 말인가
6. Paging
오키 좋아! 그럼 우리 segmentation도 하지 말고 address space를 4KB page로 나누자. 그럼 메모리를 4KB로 쪼개기만 하면 되니깐 fragmentation 문제도 발생 안하고, 쓰다가 메모리 모자라면 os한테 page 더 달라 하면 되고 좋다!!
그럼 address space에서의 page가 도대체 물리적 공간의 어떤 page frame에 매핑이 되는지 알아야 한다.
그래서 필요한게 page table이다. page table의 각각의 index는 VPN(Virtual Page Number)가 된다. 그리고 entry는 VPN에 해당하는 PFN(Page Frame Number)가 된다. 그리고 가상주소는 VPN|offset 이런 식으로 구성이 될 것이다.
그럼 가상 주소가 딱 들어왔다. 이 가상주소가 어떤 물리적 공간에 매핑이 되는지 알아야 한다. 그럼 먼저 page table을 가져와서 VPN에 해당하는 PFN을 찾아야한다.
즉 address translation을 할때마다 존나 메모리에 접근을 해서 page table을 가져와야 하는 것이다.
메모리에 접근하기 위해서 계속 메모리에 접근을 해야한다니요..... 역시 문제다
TLB
배경 설명이 참 길었다. paging에서 virtual address를 physical address로 바꿀때마다 계속 page table에 접근을 해서 PFN을 얻어오는 짓은 참 답이 없다.
그래서 일종의 캐시인 TLB를 사용한다.
TLB : Translation Lookaside Buffer
그니깐 address translation할 때 슥 한번 보는 버퍼라는 뜻이다.
TLB에 내가 알고싶은 VPN의 물리적 주소가 캐시가 돼 있으면 그거 슥 갖다 쓰면 된다는 것이다.
where is TLB?
그럼 TLB가 어디에 있느냐? MMU에 있습니다.
virtual address가 딱 들어오면 MMU에서 TLB에 캐시가 돼 있는지 확인을 열심히 한다.
TLB 알고리즘
- 처음에 딱 virtual address가 들어온다
- 그럼 거기서 VPN mask 씌우고 shift해서 VPN만 야무지게 구한다
- VPN에 해당하는 page table entry가 캐시돼 있는지 본다
3-1. cache 돼 있다!
1) virtual address에서 offset을 야무지게 뽑는다
2) page table entry에서 PFN을 야무지게 뽑는다
3) PFN | offset 을 한다.
4) 접근하면 끝!
3-2. cache 안 돼있다.
1) PTBR + VPN*sizeof(page table entry) 이 주소로 가서 page table entry를 찾아온다.
2) TLB에 캐시한다.
3) instruction을 다시 수행한다!
Locality
기본적으로 TLB는 캐시이다. 캐시는 locality라는 특성에 기반을 한다. locality에는 temporal locality, spatial locality가 있다.
Temporal Locality
한번 접근한 곳은 또 접근할 확률이 높다는 뜻이다.
page 하나는 4KB이다. 4KB는 사실상 큰 크기이기 때문에 거기에 code, data 등이 많이 몰려 있을 것이다. 즉 한 페이지에 계속 접근할 확률이 높다.
- ex) loop을 돌면 계속 같은 코드를 수행하므로 코드가 저장된 그 페이지에 계속 접근한다
Spatial Localtiy
어떤 주소 x에 접근했으면 x 주변 주소에 접근할 가능성이 클 때를 말한다.
- ex) 배열에 순차적으로 접근할 때
TLB는 위와 같은 temporal locality와 spatial locality를 반영하여 만들어졌다.
Who handles TLB miss?
아까 TLB 알고리즘 설명할 때 TLB가 캐시돼 있으면 그냥 바로 메모리에 접근하면 됐다. 근데 캐시가 안돼 있으면? 직접 Page table entry 열심히 찾아와서 캐시를 해야했다.
그럼 이걸 누가 해주는데?????
응 아키텍처마다 다르다.
- CISC : CISC 아키텍처에서는 hw가 직접 page table entry 찾아서 뽑아내고 캐시한다
- RISC : RISC 아키텍처에서는 TLB miss가 나면 trap을 raise해서 trap handler가 page table entry 찾아서 캐시한다
TLB implementation
기본적으로 TLB entry에는 VPN, PFN이 있을 것이다. VPN에 해당하는 PFN을 찾아야하니깐. 근데 VPN, PFN 말고 다른 bit들도 들어있다.
valid bit, protetction bits, dirty bit, ASID bit 등이 있다.
앞의 세 비트는 paging할때 봤다. 그럼 ASID bit가 뭔데?
ASID bit
기본적으로 TLB는 여러 process들이 공유를 한다. per-process가 아니라는 뜻이다.
어떤 process A가 열심히 돌아가다 B로 context-switching이 일어났다고 해보자. 이때 TLB에는 process A에서 이미 캐시한 VPN 10에 대한 entry가 있다고 하자.
process B가 열심히 돌아간다. process B가 열심히 돌아가다 VPN 10번에 접근하려 한다. 오잉? 그런데 VPN 10번이 이미 캐시가 돼 있다. 하지만 이 PFN은 B가 찾는 PFN이 아니다. process A의 10번 VPN에 대한 PFN이기 때문이다.
즉, 캐시된 VPN이 겹칠 수 있기 때문에 어떤 process의 VPN인지 나타내야한다.
따라서 VPN, PFN과 같이 Address Space의 IDentifer인 ASID bit도 같이 넣어 준다.
page sharing
disk에 잘 저장돼 있는 A.exe 파일에 대해 fork가 두 번 일어났다고 해보자. 그럼 두 개의 process가 만들어지고, process는 각자 code, stack, heap 영역을 가질 것이다.
근데 둘 다 같은 프로그램에서 만들어졌으니깐 code 영역은 같을 것이다. 따라서 두 프로세스의 코드 영역을 포함하는 페이지의 PFN을 같게 함으로써 code영역을 공유하도록 한다.
TLB Replacement Policy
TLB에 캐시돼 있는지 확인하고 안돼있길래 캐시 하려 했더니 TLB가 꽉 차 있다.
그럼 이미 있는 애 중 한 명을 버려야하는데 누구를 버릴까? 라는 issue가 생긴다.
TLB는 LRU(Least Recently Used)라는 방법을 사용한다.
TLB가 꽉 차 있으면 각 entry 중 가장 예전에 사용된 entry를 지우는 것이다.
끗!
