페이징 (Paging) - (2)

1. 페이지 테이블의 구조 (Structure of the Page Table)

• 많은 현대 컴퓨터는 매우 큰 주소 공간 (32 bits, or 64 bits)를 가진다.
• 이러한 환경에서 페이지 테이블도 상당히 커진다.
• Example
  • 32bit 논리 주소 공간, page size : 4KB
  • 페이지 테이블은 (2^32/2^12) 개의 entry를 가질 것이다.
  • 각 entry는 4Byte로 구성되기 때문에 2^22 = 4MB의 공간이 필요하다.
• 페이지 테이블의 크기가 커짐에 따라 메인 메모리에서 연속적으로 할당하기를 어렵다.

(1) 계층적 페이징 (Hierarchical Paging)

2단계 페이징 기법(two-level paging scheme)

페이지 테이블을 다시 페이징한다.

• 이 방식은 주소 변환이 바깥 페이지 테이블에서 시작하여 안쪽으로 들어오므로 forward-mapped page table이라고도 부른다.

• 논리 주소 (가정 : 32bit machine, page size : 1KB = 2^10 byte)
  • page number : 22 bits
  • page offset : 10 bits
• page table을 페이징 한다.
  • page number : 12 bits
  • page offset : 10 bits

• p1 : outer page table의 인덱스
• P2 : inner page table의 페이지 내의 오프셋
• d : page offset

 

(2) 해시 페이지 테이블 (Hashed Paged Tables)

논리 페이지 번호가 페이지 테이블에 해싱되어 있다.

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

• 해시 페이지 테이블 알고리즘
  • 논리 주소 공간으로부터 페이지 번호가 오면 해싱한다.
  • 결과를 가지고 해시 페이지 테이블에서 연결 리스트를 따라가며 첫 번째 원소와 논리 페이지 번호를 비교한다.
  • 일치되면 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻는다.
• 64bit 시스템에서는 클러스터 페이지 테이블 (clustered page tables)을 사용한다.
  • 해시 페이지 테이블의 각 항목이 한 개의 페이지만 가리키는 것에 반해 클러스터 페이 테이블의 각 항목은 여러 개의 페이지를 가리킨다.

(3) 역 페이지 테이블 (Inverted Page Table)

메모리 프레임마다 한 항목씩(entry)을 할당한다.

• 각 항목은 그 프레임에 올라와 있는 페이지 주소
• 그 페이지를 소유하고 있는 프로세스의 ID

• 물리 프레임에 대응되는 항목만 테이블에 저장한다.
  • 훨씬 작은 공간을 점유한다. (장점)
• 페이지 테이블 주소변환 시간이 더 오래 걸린다. (단점)
  • 역 페이지 테이블은 물리 주소에 따라 정렬되어 있고 탐색은 가상 주소를 기준으로 하므로 테이블 전체를 탐색해야 한다.
• 공유 가상 주소를 가질 수 없다. (단점)
  • 물리 페이지마다 하나의 가상 페이지 항목만 있으므로 하나의 물리 페이지는 두 개 이상의 공유 가상 주소를 가잘 수 없다.

 

2. 스와핑 (Swapping)

프로세스 실행 중에 임시로 백업 저장장치(backing store)에 내보내어졌다가 실행을 계속하기 위해 다시 메모리로 되돌아오는 것.

(1) 기본 스와핑 (Standard Swapping)

메인 메모리와 백업 저장장치 간에 전체 프로세스가 이동한다.

• 백업 저장장치
  • 저장 및 다시 접근해야 하는 프로세스를 수용할 수 있을 만큼 커야 하며, 이러한 메모리 이미지에 직접 액세스 할 수 있어야 한다.
• 실제 물리 메모리보다 더 많은 프로세스를 수용할 수 있다. (장점)
• 메모리와 백업 저장장치 간에 프로세스 전체를 이동하는 데 걸리는 시간이 매우 크다 (단점)
  • 최신 운영체제에서는 사용되지 않는다.

(2) 페이징에서의 스와핑 (Swapping with Paging)

메모리와 백업 저장장치 간에 프로세스 페이지가 이동한다.

• 프로세스 전체를 스왑 하는 비용보다는 훨씬 적은 비용이 발생한다.
• 페이지-아웃 : 페이지를 메모리에서 백업 저장장치로 이동
• 페이지-인 : 백업 저장장치에서 메모리로 페이지 이동

(3) 모바일 시스템에서의 스와핑 (Swapping on Mobile Systems)

• 모바일 시스템은 스와핑을 지원하지 않는다.
• 일반적으로 모바일 장치들은 비휘발성 저장장치로 플래시 메모리를 사용한다.
  • 저장공간이 작다.
  • 플래시 메모리는 허용되는 쓰기 횟수가 정해져 있다.
  • 플래시 메모리와 CPU 사이의 처리량이 저조하다.
• 스와핑을 사용하는 대신 가용 메모리가 정해진 임계값보다 떨어지면 응용에 할당된 메모리를 자발적으로 반환하도록 요청한다.