Issues
- 페이지 테이블 사이즈를 어떻게 줄일 것인가
- virtual <-> physical 변환 시간을 어떻게 줄일 것인가
Page Table에 관한 고찰...
32비트 주소 공간이면 프로세스마다 4MB의 페이지 테이블이 메모리에 적재되는데, 이 페이지 테이블에서 안쓰는 페이지 많은데, 굳이 모든 페이지 정보를 메모리에 올려놔야 하는가...?
그러면 현재 CPU에서 접근하고자 하는 페이지에 대한 정보만 메모리에 올려놓으려면 어떻게 하지?
-> 이제부터 알아보자.
two-level Page Tables
page number가 있던 20비트를 10비트씩 쪼개어 master page를 2^10개 만들고, 여기에서 필요할 때마다 secondary page를 만든다.
Hashed Page Tables
**hash table의 크기가 클수록 collision이 줄어든다.
- virtual page number(VPN)가 해시 테이블에 해싱된다.
- VPN, 매핑되는 프레임 넘버(PFN), 다음 엘리먼트 포인터가 연결리스트 형태로 해시테이블에 연결되어 있다. 충돌이 발생하면 들어갈 자리를 찾아야 하기 때문에 access 시간이 길어지지만 Page Table 사이즈는 줄일 수 있다.
Clustered Page Tables
hashed page table에서 변화된 방법이다
Inverted Page Tables
페이지 테이블이 프로세스마다 있는게 아니라, 페이지 테이블이 하나 있고, 거기에 PID와 페이지 넘버를 저장한다. 메모리 사용량이 줄어들지만, PID 값을 갖고 있어야 해서 오버헤드가 발생하고, page를 찾으려면 search를 해야해서 시간이 오래걸린다는 단점이 있다.
Paging Page Tables
페이지 테이블이 어디에 저장될 것인가?
-> 페이지 테이블도 메모리 내에 커널 내부에 공간이 잡혀있기 때문에 page table을 가지고 있는 page를 디스크로 page out 할 수 있다.
- Physical memory에 저장될 경우
physical memory로 page table을 관리한다면 위치를 찾아보기 쉽고 traslation도 필요없다. 어차피 OS만 page table을 관리하기 때문에 virtual page도 관리할 필요가 없다.
-> 그러나, 페이지 테이블을 계속 관리해야 한다.- Virtual memory에 저장될 경우
잘 안쓰는 page table은 page out해서 디스크로 보낸다.
-> 문제는 addressing page table은 translation을 거쳐야 한다.
-> two-level page table로 만들었을 때, secondary page table은 내려보낼 수 있지만 outer page table은 내려보냈을 때 문제가 발생한다. 따라서 outer page table을 내려보내지 않는 조치(wiring)가 필요하다. 내려보내면 문제가 발생한다.- 결국,
paging page tables 기법을 사용할 수 있게 되고, OS가 들어있는 메모리 영역도 페이징할 수 있다. 중요한 부분에 대해서는 wiring해서 디스크로 내려보내지 않도록 해야한다. 한다.(운영체제가 쓰는 코드 혹은 데이터, interrupt나 exception을 쓰는 핸들러)
TLB(Translation Lookaside Buffer)
Virtual address <-> Physical address 변환에서 페이지 페이블에서 physical address를 찾아야 하기 때문에 메모리에 access하는데 한 단계를 더 거치는 것에서 비용이 두배가 되는데, 이를 해결하기 위한 일종의 페이지 테이블의 캐시이다. TLB는 MMU에 의해 관리된다.
- TLB는 모든 PTE를 한번에 병렬적으로 찾아볼 수 있는 fully associative cache로 되어있다.
- TLB의 tag는 VPN을 갖고 values는 PTE를 갖고 있는다.
- PTE + offset으로 MMU가 physical address를 계산한다.
- page table을 액세스하는 것은 locality가 매우 높기 때문에 hit rate가 매우 높다.
-> 실제 프로세스들은 소량의 PTE(16~48개)를 가지고 있다. 2^20에 비하면 굉장히 작은 양이다.
Cache 종류
- Direct Mapped Cache : 메인메모리와 캐시 똑같은 크기로 잘라서 순서대로 매핑한다.
- Set Associative Cache : 정해진 set에서 둘 중 원하는 자리에 매핑한다.
- Fully Associative Cache : 데이터가 어디든 들어갈 수 있지만 search 해야된다.
Cache associativity가 높아질수록 hit-rate 올라가지만 비용이 증가함
TLB 동작 원리
어떤 VPN에 접근할 때, TLB를 찾아본다. 만약 TLB에 원하는 프레임을 찾으면 바로 physical memory에 엑세스한다. 만약 TLB에 없다면 페이지 테이블에서 해당 프레임이 있는 PTE를 찾아 TLB로 올린다.(페이지 테이블에는 무조건 있음. 그 프레임이 메모리에 있냐, 디스크에 있냐의 차이...당연한거임) 디스크에 있다면 page fault를 내고 디스크에서 메모리로 올린 후 hit이 난 것처럼 프레임을 읽어온다.
**당연한 동작.. 잘 생각...해..
TLB miss 처리
99%정도 hit 된다. 1%정도 miss 나는데, miss가 났을 때에는
- MMU가 page table어디에 있는지 알고 직접적으로 엑세스한다. 페이지 테이블 구조가 하드웨어 구조에 맞춰야 한다.
- Software loaded TLB(OS)가 PTE를 찾고 TLB에 load한다. 어쩔수 없이 하드웨어인 MMU를 이용하는 것보다 느리다. 또한, CPU가 TLB 조작에 대한 명령어를 지원해줘야 가능하고, 운영체제에 맞게 페이지 테이블을 자유롭게 만들 수 있다.
TLB 관리
- 운영체제는 TLB와 페이지 테이블의 PTE가 일치하는 것을 보장해야 한다.
- 프로세스가 context switch할때, TLB 엔트리 값을 모두 초기화하고 새로운 프로세스의 PTE값을 넣도록 되어있다. 여기서 오버헤드가 발생한다. 만약에 이게 싫으면 PID를 TLB 엔트리에 저장해야 하는데 어짜피 오버헤드 발생해서 이 방법은 안쓴다.
- TLB miss가 났을 때, 새로운 PTE가 로딩될 것인데, 이때, TLB에서 어떤 PTE를 뺄 것인가에 대한 TLB replacement policy를 갖고있어야 한다. 하드웨어로 보통 간단하게 구현한다.
메모리 Access
- hit : MMU에 있는 TLB에서 페이지 넘버를 찾고, TLB hit이 되면 PTE protection이 read를 허용하는지 체크한 후, page를 특정해서 MMU에 알려주면 MMU에서 physical frame 넘버와 offset을 조합하여 physical address를 알아내고 접근하여 값을 가져오고 cpu에 리턴한다.
- miss : MMU는
TLB misss - recursive fault
페이지 테이블이 OS virtual address space에 있을 경우 페이지 테이블이 page out될 수 있다. 그러면 재귀적으로 페이지 폴트가 날 수 있다. 이제, 그럼 page fault handler가 디스크에서 프레임을 찾아와 physical memory로 로드한다. 그 후, PTE를 TLB에 로드한다. 그 후, 다시 TLB 동작 수행. 근데, 여기서 또 폴트가 났다? 이거는 PTE protection bit가 성정되어있는 경우이다.
Page Fault의 두가지 경우
- Read/Write/Execute(protection fault) : operation이 허용되지 않을 때
- Invalid : 페이지가 할당된 적이 없거나 physical memory에 없어 page out된 상태
이 두가지 경우, TLB가 OS에 trap을 건다.
- Read/Write/Execute : OS가 문제 있는 것이라고 알려준다.
- Invalid(Not allocated) : OS가 프로세스에게 fault를 보낸다.
- Invalid(Not in physical memory, disk에 있는 경우) : OS가 page fault handler를 불러서 frame을 할당해주고 디스크에서 읽어서 physical memory에 업데이트하고 PTE를 수정한다.
