1. 해시 페이지 테이블 (Hashed Page Table)의 개요
| 개념 | 페이지 테이블 크기 축소 위해 페이지 번호에 해시 함수 적용 및 연결 리스트를 참조하고 할당하는 메모리 관리 기법 | |
|---|---|---|
| 특징 | 페이지 번호에 해시 함수 적용 | – 페이지 번호에 해시 함수를 적용하여 페이지 테이블 크기 축소 가능 |
| 충돌 해결 위한 연결 리스트 | – 동일한 위치에서 충돌이 발생하며, 이를 해결하기 위해 연결 리스트 자료구조 활용 | |
- 주소 공간이 32비트보다 커지면 가상 주소를 해시값으로 사용하는 해시 페이지 테이블을 사용하여 페이지 테이블 크기 축소
2. 해시 페이지 테이블의 원리
(1) 해시 페이지 테이블의 동작 구조
| 구조 | |
|---|---|
| 설명 | – 논리 주소의 페이지 번호에 해시 함수를 적용하여 해시 테이블의 원소를 참조하고, 동일 위치의 원소 충돌을 해결하기 위해 연결 리스트를 사용하여 물리 주소 확인 및 메모리 접근 – 각 원소는 아래 세 개의 필드를 가짐. ① 가상 페이지 번호 ② 맵핑되는 페이지 프레임 번호 ③ 연결 리스트 상의 다음 원소를 가리키는 포인터 |
(2) 해시 페이지 테이블의 주소 변환 절차
| 단계 | 주소 변환 절차 |
|---|---|
| 1단계 | – 가상 주소의 가상 페이지 번호를 해싱 |
| 2단계 | – 해당 해시값의 연결 리스트의 첫 번째 원소와 가상 페이지 번호를 비교 |
| 3단계 (일치) | – 일치하면 그에 대응하는 페이지 프레임 번호를 통해 물리 주소 획득하여 주소 변환 |
| 3단계 (불일치) | – 불일치 시 연결 리스트의 다음 원소들을 탐색해가며 일치하는 가상 페이지 번호 탐색 |
- 효율적인 페이지 테이블 관리와 물리 메모리 접근을 위해 해시된 페이지 테이블과 함께 역 페이지 테이블, 다단계 페이지 테이블 등 다양한 방식 사용
3. 페이지 테이블 방식 비교
| 비교 항목 | 해시 페이지 테이블 | 역 페이지 테이블 | 다단계 페이지 테이블 |
|---|---|---|---|
| 구조 | – 해시 테이블 + 연결 리스트 체이닝 | – 물리 메모리 프레임 수 크기 하나의 테이블 | – 페이지 테이블을 계층으로 구성 |
| 메모리 사용량 | – 대형 주소 공간에 비해 효율적 | – 메모리 프레임 수 만큼 상대적 적음 | – 필요한 부분만 로드하여 메모리 절약 |
| 주소 변환 방식 | – 해시 충돌 시 연결 리스트 탐색 | – pid, 페이지 번호 검색, 최악의 경우 전체 탐색 | – 주소를 상위 비트 기준 단계별 테이블 참조 |
| 장점 | – 넓고 비연속적 주소 공간에 효율적 | – 메모리 절약 가능 | – 큰 주소 공간 효율적 관리 |
| 단점 | – 충돌 시 탐색 비용 증가, 구현 복잡 | – 탐색 속도 느림, 프로세스간 공유 불가 | – 계층이 많을 수록 참조 증가, 복잡도 증가 |
| 활용 | – 64비트 시스템 등 대형 주소 공간 | – 메모리 절약이 중요한 시스템 | – 일반적인 운영체제 표준 방식 |
- 일반적인 범용 컴퓨터는 다단계 페이지 테이블 방식을 사용하며, 시스템 특성에 따라 해시 페이지 테이블과 역 페이지 테이블 방식 선택적 사용
[참고]
- 홍릉과학출판사, Operating System Concepts 8th Edition