운영체제

20) 페이징: 더 작은 테이블

페이징엔 문제가 있었다...
1. 페이지 테이블에 접근할때 성능저하 -> TLB로 어느정도 해결
2. 페이지 테이블의 크기

페이지 테이블이 크면 많은 메모리 공간을 차지...
EX) 페이지 크기가 4KB(2^12바이트), PTE는 각 4바이트인 32비트 주소공간(2^32바이트)

그렇다면 가상 페이지는 2^20개 존재, 이는 2^20*4바이트의 PTE를 의미...

일반 배열 페이지 테이블은 메모리를 과다하게 차지..

Linear tables

• 하나의 프로세스당 하나의 테이블을 가진다
  • 4KB 페이지, 32비트 주소 공간, 4바이트 PTE?
    • 페이지 테이블 사이즈 = 2^32/2^12*4바이트 = 4MB(하나의 프로세스 당)

페이지 테이블이 너무 크고 메모리를 너무 많이 잡아 먹는다

더 큰 페이지, 작은 테이블

페이지 테이블이 너무 크고 메모리를 잡아먹어!!

그럼.. 16KB 크기인 페이지,32비트 주소공간, 4바이트 PTE를 가정해보자

> 페이지 테이블 사이즈 = 2^32/2^14*4바이트 = 1MB(프로세스 당)

페이지 크기가 4배 증가했으니 PTE 크기가 1/4인건 당연..
그리고 페이지 크기 증가는 부작용이 있다...

문제점: 내부 단편화

• 할당된 페이지 내부의 낭비공간이 증가함
  • 프로세스가 여러 페이지를 할당받지만 페이지의 일부분만 사용함

그래서 많은 시스템들이 작은 페이지를 사용함

공통 페이지 사이즈

• ISA는 4KB, 8KB 페이지 사이즈를 지원한다.
• 다양한 페이지 사이즈
  • 256kb,1mb,4mb,16mb....
    • 유동적으로 조절해.. 데이터가 큰 경우
  • TLB에 오는 압박을 줄이기 위해 사용한다
    • 음.. 페이지 개수를 줄이니 TLB에 저장하는 양이 준다 그말?
  • 데이터베이스 관리에 사용된다

문제점. 페이지테이블의 대부분 공간이 사용되지 않는다.. 그냥 빈 공간 메모리 낭비!!

하이브리드 접근 법: Paging and segments

프로세스 전체 주소공간을 위해 하나의 페이지 테이블을 두는 대신,
세그멘트마다 따로 페이지 테이블을 두자!
베이스와 바운드를 사용하자!

• 페이징과 세그멘테이션의 좋은 부분을 합쳐!
• 페이지 테이블의 오버헤드를 줄이기 위해
  • 베이스 레지스터는 세그먼트의 시작주소를 가리키는 것이 아닌, 세그멘트의 페이지테이블의 시작주소를 가진다.
  • 바운드 레지스터는 페이지 테이블의 끝을 가리킨다.
    • 세그멘트의 최대 유효 페이지의 개수를 가리킴

그래서 프로세스 마다 3개의 페이지 테이블이 존재(코드 스택 힙)

• 프로세스가 실행할때, 각 세그멘트의 베이스 레지스터는 각 세그멘트 페이지 테이블의 시작 물리 주소를 가진다.

• seg주소, VPN, Offset으로 가상 주소가 구성된다.

• context switch시 각 레지스터(베이스,,바운드.. 각 영역마다 )들은 새로운 프로세스의 페이지테이블의 위치 값으로 변경됨

TLB 미스일때

하드웨어가 페이지테이블에서 주소를 가져온다

1. 하드웨어는 세그멘트 비트(SN)을 이용하여, 어떤 베이스와 바운드를 사용할지 결정
2. 하드웨어는 레지스터에 있는 물리 주소(sn이용)를 VPN을 이용해 PTE의 주소를 얻음
   • sn을 가상주소에서 마스킹을 통해 얻음
   • vpn을 가상주소에서 마스킹을 통해 얻음
   • pte주소 = base[sn]+vpn(*sizeof(pte))

페이징만 이용했을 때와 차이

• 페이징은 하나의 PTBR을 이용해 값 계산 but 이건 세개중 하나의 레지스터 사용

하이브리드의 핵심: 세그멘트마다 레지스타 쌍이 따로 존재!

• 각 바운드 레지스터 값은 세그멘트의 최대 유효 페이지 개수를 나타낸다
  • 코드 세그멘트가 0 1 2 페이지를 사용한다면, 바운드는 3으로 설정
    • 바운드를 넘어가는 메모리 접근은 예외를 발생

하이브리드도 문제가

• 빈 공간이 많은 힙, 여전히 페이지 테이블의 낭비를..
• 외부 단편화
  • 페이지 테이블 크기에 제한이 없고, 다양한 크기를 가진다

=> 페이지 테이블 크기를 줄여야해

멀티 레벨 페이지 테이블

페이지 디렉토리 -> 페이지 테이블 엔트리 -> 페이지

linear 페이지 테이블을 트리와 같이 생각해보자

• 페이지 테이블을 페이지 크기의 단위로 나눈다
• 유효하지 않은 항목이 있다면 해당 페이지를 할당하지 않는다.
• 페이지 디렉터리라는 자료구조를 사용해 페이지 테이블 각 페이지의 할당 여부와 위치를 파악한다
  • 페이지 디렉터리는 페이지 테이블을 구성하는 각 페이지의 존재 여부와 위치정보를 가짐

ex 책 그림

• linear 페이지 테이블은 중간부분의 공간은 사용하지 않는다

  • 그치만 공간은 할당되어 있다

• 페이지 디렉터리에는 두개의 유효한 페이지가 있다

  • 유효 페이지 두개는 메모리에 존재한다

페이지 디렉터리를 이용해 어떤 페이지들이 할당되었는지를 관리한다

리니어에선 4*4 바이트
멀티레벨에선 페이지 디렉터리(4)+PDE(4*2) = 12바이트

준다!

page directory entries

• 페이지 디렉터리의 각 항목은 페이지 테이블의 한 페이지를 나타낸다
  • 페이지 디렉터리는 페이지 디렉터리 엔트리(PDE)로 구성된다
• PDE는 valid bit, PFN을 가진다
  • Valid: 항목이 가리키고 있는 페이지들 중 최소한 하나가 유효
    • PDE가 가리키는 페이지내의 최소한 하나의 PTE의 valid가 1이다
  • Invalid: 실제 페이지가 할당되지 않음

과정

64바이트 페이지를 갖는 16KB크기의 주소 공간(2^14비트), 4바이트 PTE
페이지가 2^6 바이트의 크기니 offset 6bit가 필요, 그럼 14비트 체계니 vpn은 8 bit를 차지

linear 페이지 일때는 2^8개의 PTE로 구성된다. 변함 없다.
6개의 페이지를 사용중이라 가정
페이지 테이블의 크기는 1KB(256*4바이트)

페이지가 64바이트의 크기를 지니니 페이지테이블(2^10)은 16개의 64바이트 페이지들로 분할된다
(2^4*2^6=2^10)
=> 각 페이지엔 16개의 PTE가 있다

(이해완료.. 페이지 테이블도 메모리에 들어가기때문에 페이지로 쪼개져야함
페이지 테이블의 크기는 (256*4바이트) 그런데 이게 메모리에 들어가야함
페이지 크기가 64바이트네? 그럼 페이지 테이블도 16개의 페이지로 쪼개짐)

2단계 멀티레벨 페이지 테이블로 구성해보자~

일단 페이지 디렉터리의 인덱스를 구성해야함.
페이지테이블은 256개인데 16개의 페이지로 나뉘어져있다.
디렉터리는 페이지 테이블의 각 페이지마다 필요!
=> 16개의 디렉터리 인덱스가 필요하다 VPN에서 4비트를 사용

페이지 디렉토리 인덱스

• 페이지 디렉토리는 페이지 테이블의 각 페이지마다 하나씩 있어야 한다.

VPN에서 페이지 디렉터리 인덱스를 추출하면
PDE주소 = 페이지디렉터리베이스 + (PDIDEX*sizeof(PDE))
를 통해 PDE의 주소를 찾을 수 있다.

PDE의 valid가 invalid이면 주소 접근은 유효하지 않다.
valid라면 PDE가 가리키는 페이지 테이블의 페이지에서 PTE를 읽어야 한다.
=> VPN의 나머지 비트를 활용

페이지 테이블 인덱스(PTI)를 활용한다
PTE주소 = PFN + (PTI * sizeof(PTI))

계산

• 32 비트 아키텍쳐, 4KB 페이지 사이즈

  • 페이지 number는 20bit로
  • offset은 12비트

• VPN은 나뉘어짐

  • 10비트는 PDI
    • (2^20(VPN) X 2^2(PTE크기))[페이지 테이블의 전체 크기] / 2^12(페이지의 크기) = 10비트
      • 페이지 테이블가 페이지로 나뉘어지는 과정
  • 10비트는 PTI
    • 2^12(페이지 크기) / 2^2(PTE의 크기) = 10 bit
      • 한 페이지에 몇개의 PTE를 넣을 수 있나?

멀티레벨 페이지 테이블 장단점

장점

• 사용된 주소 공간의 크기에 비례하여 페이지 테이블 공간이 할당
  • 작은 크기의 페이지 테이블로 주소공간을 표현할 수 있다
• 페이지 테이블을 페이지 크기로 분할해 메모리관리가 쉽다
  • 페이지 테이블을 할당, 확장 시 OS는 다음 빈 페이지를 쓰면 된다
    • 페이지 디렉터리가 있으니 위치 파악이 쉬움
  • linear일땐.. 배열에서 빈공간을 탐색해야함

단점

• 멀티 레벨 테이블에는 추가 비용이 발생한다 Time-space trade off
  • TLB 미스시 주소 변환을 위해 두번의 메모리 접근을 해야함
    • 페이지 디렉터리, PTE
• 복잡도가 커짐
  • 단순 linear보다 복잡하다

멀티레벨 페이지 테이블: level of indirection

• 멀티레벨 구조는 페이지 디렉토리의 사용을 통해 수준을 조정할 수 있다.
  • 물리메모리에서 원하는 위치에 페이지 테이블 페이지를 위치한다

2단계 이상 사용

멀티레벨 페이지 테이블의 목적은 페이지 테이블의 모든 분할된 부분들이 단일 페이지 크기에 맞도록

• 페이지 디렉터리가 너무 커지면??

--

• 만약 페이지 디렉터리가 2^14 엔트리를 가진다면, 이건 한페이지가 아니라 128개이다.
  • 디렉터리가 2^14개, 디렉터리가 가리키는 각 페이지는 128개의 PTE를 가짐

하나의 페이지에 128개의 PTE를 넣을 수 있음(7비트)
근데 페이지 디렉터리에 2^14개가 들어가게됨(14비트)
페이지 디렉터리를 위해 연속적인(페이지 크기가아닌) 공간이 필요,..

멀티레벨 페이지 테이블의 근본 취지가 훼손

• 페이지 테이블을 페이지 단위로 나누어 배치하도록

• 더 많은 트리 레벨을 설정 가능

  • 페이지 디렉토리를 더 많은 페이지 레벨로 쪼개

--

TLB를 사용

• TLB 히트가 있따면 페이지 테이블 참조 없이 물리 주소를 알 수 있다.
• 미스라면 멀티 레벨 페이지 테이블의 모든 단계를 거쳐 물리 주소를 구한다
  • 비용이 막대

    TLB는 좋다

역 페이지 테이블

여러개의 페이지 테이블(프로세스 당 하나) 대신 시스템에 단 하나의 페이지 테이블만!

• 테이블은 물리 페이지를 가상 주소 상의 페이지로 변환

• 테이블의 각 항목은 해당 물리페이지를 사용 중인 프로세스 번호, 해당 가상 페이지 번호를 가짐

• tradeoff

  • 작은 페이지 테이블 크기
  • 검색 속도 증가
    • 이를 줄이기 위해 해시를 사용