Page Table Structure

1. hierarchical paging(계층적 페이징)

• 32비트 컴퓨터에선 페이지 테이블은 4MB정도로 크다.

• 페이지 테이블을 작은 조각으로 나눈다. 페이지 테이블 자체가 다시 페이지화 되는 것.

• 단점

  • 계층이 깊어질수록, 페이지 접근 시간이 늘어난다.

  • 64비트 컴퓨터의 경우 페이지 크기가 어마어마하게 크다. 너무 많은 메모리 접근을 요구하므로 구현이 불가능하다.

2. hashed page table

• 주소 공간이 32bit 보다 커지면 사용

• 해시 테이블에 각 항목은 연결리스트를 가지고 있으며, 충돌을 일으켜서 이곳으로 해시되는 원소들이 연결된다.

• 각 원소는 가상 페이지번호, 사상되는 페이지 프레임 번호, 연결 리스트 상의 다음 원소 포인터를 가진다.

• 단점
  • 물리 프레임들이 인접하게 위치되어있을수록, 충돌이 발생할 확률이 높아지고 시간이 오래걸린다.
• 알고리즘
  1. 가상 주소 공간에서 페이지 번호가 오면 그것을 해싱함수에의해 해싱한다
  2. 페이지 테이블에서 연결리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교해본다
  3. 일치하면 그에 대응하는 페이지 프레임 번호를 가져와 물리주소를 얻고
  4. 일치하지 않으면 다음 원소로 이동하여 반복.

3. Inverted Page Table

• 보통 프로세스 마다 각자 하나씩 페이지 테이블을 가짐
• 프로세스 전체가 공통으로 사용하는 페이지 테이블, 가상 주소에는 프로세스ID와 페이지 주소를 가지고 있다.
• 메모리공간을 작게 사용한다.
• 단점

  • 주소변환 시간이 더 오래 걸린다. 이는 해시 테이블로 시간을 단축할수 있지만, 매 접근 마다 해시테이블을 참조해야 하기 때문에 메모리 참조 횟수를 증가시키게 된다.

  • 메모리 공유가 어렵다. 물리페이지에 대해서 단 하나의 가상주소를 갖게 되므로 불가능하다. 왜냐하면 하나의 물리페이지는 두개이상의 가상주소를 공유할수 없기 때문이다.

참고로 Windows(32bit x86 systems)는 Inverted page table을 사용한다고 한다.

출처