Multilevel Paging and Performance

2단계뿐 아니라 3단계, 4단계 등 여러 단계의 페이지 테이블을 사용할 수 있다. 이렇게 하면 테이블을 위한 공간을 더 많이 줄일 수 있다. 그렇지만 한번의 주소변환을 위해 여러 개의 페이지 테이블을 거쳐야 하고, 페이지테이블이 물리적 메모리 상에 있기 때문에 메모리 한번 접근을 위해 주소변환을 위해 메모리를 N+1번 접근해야 한다.(N번은 주소변환, 1번은 실제 데이터 접근 / N은 N단계 페이지 테이블) 즉 시간적인 오버헤드가 커진다.

TLB는 주소변환을 해주는 일종의 캐시 메모리이다. 다단계의 페이지 테이블을 사용하면 시간이 오래 걸릴 수 있지만 사실은 주소변환이 주로 TLB를 통해 이뤄지기 때문에 다단계 테이블을 사용하더라도 시간이 지나치게 오래 걸리지는 않는다.

98퍼센트의 비율만큼은 20ns만에 주소변환이 되므로, 메모리 접근하는 시간까지 120ns 가 걸린다. TLB에 주소변환 정보가 없는 2%의 비율만큼은 20ns(TLB 찾는 시간)+400ns(주소변환)+100ns(데이터 가져오는 시간) = 520ns 걸린다. 결과적으로 28ns만 추가적으로 소요된다.

페이지 테이블에 들어가는 비트

Valid-Invalid bit

• 왼쪽이 프로그램마다 주어지는 logical memory
• 오른쪽이 physical memory
• 가운데가 page table

지금까진 logical memory의 페이지 개수만큼 page table의 엔트리가 존재했으며, 엔트리에는 논리적 메모리의 페이지가 물리적 메모리의 어디 페이지에 들어있는지 주소변환 정보를 가지고 있다고 까지만 설명하였다.

그런데 사실은 엔트리마다 부가적인 bit가 더 저장된다. 그중 하나가 valid-invalid bit이다. v로 표시된 경우, valid, i로 표시된 경우, invalid이다.

예를 들어, 위 그림에서 논리적 메모리의 경우 페이지가 5번까지 사용한다. 그런데 page table은 6,7 인덱스도 존재한다. 왜냐하면 아무리 사용되지 않더라도 page table은 프로그램 주소공간이 가질 수 있는 maximal size만큼의 엔트리를 가지기 때문이다. 그 이유는 테이블이라는 자료구조 특성 상 위에서부터 인덱스로 접근하기 위해 모든 엔트리가 다 필요하기 때문이다.

대신 사용되지 않기 때문에 valid-invalid bit을 i(invalid)로 표시한다. frame number가 진짜 0번 frame을 의미하는 건지 아닌지 구분할 수 있다.
사용되지 않는 페이지나, 당장 필요하지 않아 하드 디스크 backing store에 내려가 있는 경우에 invalid로 표시한다.

• valid는 주소변환 정보가 맞고 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 의미한다.(접근 허용)
• invalid는 해당 주소의 frame에 유효한 내용이 없음을 뜻한다. (접근 불허) → 프로세스가 그 주소 부분을 사용하지 않는 경우 or 해당 페이지가 물리적 메모리에 올라와 있지 않고 swap area(backing store)에 있는 경우

Memory Protection

또한 페이지 테이블 엔트리에 저장하는 또다른 bit가 있는데, 그것이 Memory Protection이다.

(페이지에는 항상 해당 프로세스만 접근할 수 있다)

Protection bit는 read/write/read-only 중 어떤 연산에 대한 접근 권한이 있는지를 나타낸다.

• code와 같은 경우 내용이 바뀌지 않아야 하므로 read-only로 세팅된다.
• data나 stack의 경우 데이터를 쓰고 업데이트 하는 것이 가능하기 때문에 read, write가 모두 필요하다.

Inverted Page Table

지금까지 설명한 페이지 테이블의 문제는 굉장히 많은 용량을 차지하고 있다는 것이었다. 이를 해결하기 위해 inverted page table이 나왔다.
기존의 페이지 테이블의 주소변환을 역발상으로 뒤집은 것이다. 원래의 경우 프로세스마다 페이지 테이블이 별도로 존재했다.

그러나 inverted page table의 경우 각 프로세스마다 존재하는 것이 아니라 시스템 내에 페이지 테이블이 딱 하나 존재한다. 페이지 테이블의 엔트리가 프로세스의 페이지 개수만큼 존재하는 것이 아니라 물리적 메모리의 페이지 프레임의 개수만큼 존재한다.

우리가 주소변환을 하려면 페이지 번호를 보고 위에서부터 페이지 번호만큼 떨어진 엔트리에 가서 주소변환을 하는 방법을 썼었는데 여기서는 그것이 불가능하다. 들어가는 내용이 반대로 되어있기 때문이다. 첫번째 엔트리에는 첫번째 페이지 프레임에 들어가는 논리적인 페이지 번호가 들어가있고 두번째 엔트리에는 두번째 페이지 프레임에 들어가는 논리적인 페이지 번호가 들어가 있다.

이는 physical address를 보고 logical address를 알아내는 것이다.(원래는 logical → physical 이 목적)

그래서 원래 목적인 logical → physical을 달성을 위해 페이지 테이블의 엔트리를 모두 다 탐색하여 주소변환을 한다. (시간적으로 비효율적)

또한 이 페이지테이블에 p가 어떤 프로세스의 페이지인지 프로세스의 id도 함께 존재해야 한다.(pid)

보통은 시간 오버헤드를 줄이기 위해 페이지 테이블을 그냥 메모리가 아니라 associative register에 집어넣어 병렬적 탐색이 가능하도록 한다.