2024. 5. 31. 20:40ㆍCS/Operating System
어떻게 운영체제가 메모리를 조금이라도 적게 쓰고 virtual 한 어드레스를 잘 번역할 수 있을까? 좀 더 빨리 번역할 수 있을까?
먼저 space overhead를 생각해보자.
- 32bit 머신에서 페이지 테이블이 4KB, 페이지 테이블 한 row가 4byte라고 한다면 엔트리가 2^20개이므로 총 2^24, 즉 프로세스당 페이지 테이블을 4MB 사용한다.
어떻게 좀 더 줄일 수 있을까?
- 프로세스가 실행되면서 어드레스 스페이스를 전체 다 사용하지는 않는다. 페이지 테이블 엔트리가 2^20개라는 건 4GB를 다 사용한다고 생각하고 페이지 테이블을 만드는 것이다. 그런데 실제로 그런 프로세스는 잘 없고 대부분이 메모리의 일부분만 사용한다.
- 오버헤드를 잘 줄이려면 실제로 사용되는 주소 공간의 일부만 매핑하면 된다.
어떻게 실제로 사용되는 부분만 매핑할까?
- 페이지 테이블을 해시 테이블 linked list로 만든다. 이 방식의 문제는 페이지를 찾을 때 index를 사용할 수 없어서 search 해야 하므로 오래 걸린다는 문제가 있다.
- 페이지 테이블 구조를 동적으로 확장 가능하게 만들 수 있다. linked list나 B트리 같은 자료 구조를 사용하여 필요한 페이지 테이블 엔트리만 생성하고 연결할 수 있지만 이 방식은 시간적 오버헤드가 심하다.
- 여러 레벨을 사용할 수 있다. Two-level, hierarchical, hashed, ... 하나씩 알아보자.
Two-level Page Tables
Two-level page table은 다음과 같은 주소와 테이블을 가진다.
- Master page #, Secondary Pagge #, Offset
- Master page table : master page number → secondary page table
- Secondary page table : secondary page number → page frame number
Example
32 bit address space, 4KB pages, 4bytes/PTE의 예시를 생각해 보자.
offset bit는 어쩔 수 없이 12bit를 사용해야 하고 master page, secondary page는 20bit 중 아무렇게나 자를 수 있다.
잘라낸 비트의 앞쪽은 master page로 사용하고 index를 이용해서 master page table에 접근하면 secondary page table을 찾을 수 있다. secondary page table에서 frame number를 찾을 수 있다.
생각해 보면 master page가 10bit라는 건 master page table은 2^10개의 엔트리가 필요하다는 것이다. secondary page table의 엔트리 또한 1024개이고 secondary page table의 수도 1024개이다.
two-level을 사용하려는 목적이 페이지 테이블이 차지하는 메모리를 아끼자는 건데, 페이지 테이블이 2^10개 필요하고 테이블 당 2^10개의 엔트리가 필요하므로 총 2^20만큼 사용해야 한다. 게다가 outer page table 사이즈만큼 더 필요하므로 그렇게 이득은 아니다.
진짜 그럴까?
사실은 이득이다.
outer page table은 반드시 초기에 만들어져야 한다. 그런데 만약 한 세컨더리 페이지 테이블 안에서 프로그램이 다 돌아간다면 나머지 세컨더리 페이지 테이블들은 미리 만들 필요가 없다.
따라서 세컨더리 페이지 테이블을 이용한 Two level Page table을 사용하면 메모리를 많이 아낄 수 있다.
그런데 이 기법의 문제는 페이지 테이블에서 무조건 두 번의 액세스 발생한다. 이 기법은 master page table을 엑세스 하고, secondary page table을 엑세스 해야 피지컬한 메모리에 엑세스 할 수 있다. 따라서 성능적으로 오버헤드가 더 증가한다.
Multi-level Page Tables
멀티 레벨 페이지 테이블도 있다. 레벨 1이 master page table과 유사한 테이블이고 master page table을 이용해서 레벨 2, 레벨 3에 접근할 수 있고 레벨 3에서 피지컬 한 어드레스에 접근할 수 있다. 이 방식은 메모리는 굉장히 많이 아낄 수 있지만 오버헤드는 4배이다.
심지어 Multi-level page table 앞에 segment도 있어서 segment table 한 번 더 뒤져봐야 한다.
Hashed Page Tables
- virtual address의 virtual page number를 hash function(모듈러 등)을 돌리는 방법이다.
- 해시 테이블 엔트리는 충돌 문제 때문에 linked list로 연결된다. vpn과 일치하는지 linked list를 따라가면서 체크하게 된다.
- 해시 테이블을 사용하면 페이지 테이블의 사이즈가 줄어든다. 페이지 테이블의 엔트리 수가 해시 펑션에 따라 정할 수 있는 것이다.
- 1024로 모듈러 연산을 쓴다면 1024개의 엔트리를 가진다.
- 이 방식은 linked list를 따라서 search 해야 한다는 문제를 가지고 있다.
해시 테이블 엔트리의 크기는 어떻게 될까?
- 가상 페이지 넘버, 매핑된 프레임 값, linked list를 위한 포인터도 가지고 있어야 하므로 노드 하나가 대략 12byte를 가지고 있어야 한다.
Clustered page tables
<<여기부터
해시 테이블을 개선하기 위해 Clustered page tables를 고안되었다.
- 해시 결과가 같은
- 노드 여러 개를 묶어서 한 클러스터화 시키고 이들을 linked list로 만들었다.
- 그리고 VPN의 일부를 Block offset으로 정한다.
- 노드 안에서 Block offset을 이용해서 검색하면 linked list를 이전 방식보다 조금만 검색해도 된다. 예를 들어 block offset이 3이면 VPBN 2를 바로 보고 VPBN이 일치하지 않으면 다음 linked list를 뒤져본다.
사실 노드를 채우는 방식이 순차적으로 채우는 게 아니라 VPBN에 따라 Block offset에 따라서 값을 또 정하는 것이므로 메모리 낭비가 좀 더 있을 수 있다.
Clustered page tables가 더 좋은 이유는 search 횟수가 적어진다는 것이다.
질문할 내용 : VPN을 VPBN과 Block offset으로 나누고 VPBN을 해시함수를 돌려서 해시 테이블에 접근.
-> 해시 테이블에 VPBN으로 여러 노드들이 linked list로 달려있는데 해시 결과가 같은 것들의 모임인가요?
-> VPBN이 같다면 Block offset으로 해당 노드의 PPN을 찾는 걸로 알고 있는데 PPN이 PFN과 같은 건가요?
여기까지 다시 정리하기>>
Inverted Page Table
원래는 가상 주소로 페이지 테이블을 만들었다. Inverted Page Table은 반대로 피지컬 한 메모리를 기준으로 페이지 테이블을 만드는 방식이다. 페이지 테이블 엔트리 하나하나가 프레임 하나하나에 매핑된다.
- 하나의 엔트리가 메모리의 real page에 매핑된다.
- 엔트리는 real memory에 저장된 페이지의 가상 주소와 해당 페이지를 소유하는 프로세스의 정보로 이루어져 있다.
- PID를 관리해야만 한다.
주소를 번역하는 과정은 다음과 같다.
- CPU는 32bit의 page number, offset, pid 주소를 받아서 페이지 테이블을 search 하기 시작한다.
- 페이지 테이블의 위에서부터 search를 진행하다가 pid, p가 일치하는 i+1번째 페이지를 찾았다면
- i번째 프레임과 매핑된 것이다. i, d가 물리 주소가 된다. i가 offset처럼 작동하지만 실제 offset은 아니라는 것을 주의하자!
장점
- 페이지 테이블의 사이즈가 피지컬 한 메모리의 사이즈에 의해 결정된다.
- 만약 피지컬한 메모리가 4GB라면 페이지 테이블은 2^20이 될 것이다. 엔트리 하나의 사이즈가 pid 4byte, page number 4byte라면 8*2^20이다. 프로세스 하나라면 비효율적이다.
- 기존의 방식에서는 프로세스의 개수만큼 페이지 테이블이 필요하다. 그러나 이 방식에서는 페이지 테이블이 global 하게 딱 하나만 있으면 된다. 프로세스가 여러 개라면 pid를 가지고 찾는 것이므로 페이지 테이블 하나의 크기는 좀 크더라도 전체적으로 따지면 아낄 수 있다.
- pid와 p만 알면 프레임에 따라 페이지 테이블을 정한 것이므로 프레임 넘버 i를 바로 알 수 있다.
단점
- 최악에는 엔트리 수만큼 search 해야 한다.
- 앞에 해시를 쓰거나 서치 트리를 만들거나 하면 search 수를 줄일 수 있지만 어쨌든 간에 search 자체가 오버헤드가 된다.
- 또 하나의 오버헤드는 PID를 유지 관리해야 한다는 것이다.
- 만약 3번 프로세스가 100개 정도의 페이지를 사용했다면 페이지 테이블 엔트리 100개 정도를 3번이 쓰고 있었을 테고, 3번이 죽는다면 그만큼 페이지 테이블에서 찾아서 지워야 한다.
- 즉, 페이지 테이블 전체를 search 하는 일이 꽤 빈번하게 일어난다.
이런 오버헤드를 제외하면 페이지 테이블 사이즈는 확실히 줄일 수 있다. Inverted가 아마도 페이지 테이블 메모리를 많이 아낄 수 있겠지만 serach 오버헤드는 가장 클 것이다.
실제로는 Multi level Page Tables를 많이 사용한다. 임베디드에서 딱 하나의 프로세스만 가능하다면 Inverted도 나쁘지 않을 수 있다. 임베디드에서는 피지컬 한 메모리가 매우 작을 것이기 때문이다.
페이지 테이블을 어디다 두고 관리할까?
- 피지컬한 메모리에 두기
- translation이 요구되지 않으므로 address 하기 쉽다.
- VAS의 lifetime 동안 메모리를 계속 소모하고 있다는 문제가 있다.
- 운영체제가 사용하는 가상 메모리에 두기
- 페이지 테이블이 한동안 안 쓰이면(Cold page table) 페이지 테이블 자체도 디스크로 내려 보낼 수 있다.(swapping)
- 페이지 테이블을 위한 페이지 테이블도 또 있어야 한다. 프로세스의 어드레스 스페이스 상위 1기가 정도는 커널 코드로 사용하는데 여기의 일부가 페이지 테이블이 되는 것이다.
- 또, 멀티 레벨을 쓴다면 outer page table은 디스크로 내려보내면 안 된다. 그 기법을 wiring이라 한다.
운영체제 또한 가상 메모리에 두므로 스와핑 일어날 수 있다. 따라서 디스크로 절대 내려보내면 안 되는 데이터나 코드가 존재한다. 인터럽트 익셉션 핸들러가 디스크로 내려가면 큰일이다.