[OS] 페이징: 더 작은 테이블

장선규·2023년 8월 20일
OSOSTEP가상화운영체제페이지테이블페이징
0

[OS] OSTEP Study

목록 보기
15/28

페이징: 더 작은 테이블

페이징의 두번째 문제점은 페이지 테이블의 크기이다.

  • 예시)
    주소공간의 크기: 32비트 주소공간 (2322^{32} 바이트)
    페이지의 크기: 4KB (2122^{12} 바이트)
    가상 페이지의 개수: 232/212=2202^{32} / 2^{12} = 2^{20} 개 (약 100만)
    페이지 테이블 항목의 크기: 4바이트
    • 페이지 테이블의 크기는 약 4MB가 된다(4바이트 * 100만).
    • 그리고 각 프로세스는 자신만의 페이지 테이블을 가지므로, 100개의 프로세스가 실행중이면 총 400MB 메모리 필요

핵심 질문: 페이지 테이블을 어떻게 더 작게 만들까

1. 간단한 해법: 더 큰 페이지

페이지의 크기를 늘리면 페이지 테이블의 크기를 줄일 수 있다.

위의 예시에서 페이지의 크기를 4KB에서 16KB로 늘려보면

  • 주소공간의 크기: 32비트 주소공간 (2322^{32} 바이트)
    페이지의 크기: 16KB (2142^{14} 바이트)
    가상 페이지의 개수: 232/214=2182^{32} / 2^{14} = 2^{18} 개 (약 26만)
    페이지 테이블 항목의 크기: 4바이트
    • 페이지 테이블의 크기는 약 1MB (4바이트 * 26만)

페이지의 크기를 늘렸을 때의 부작용: 내부 단편화

  • 각 페이지의 내부가 커지므로, 내부에 단편화가 될 확률이 높아짐
  • 여러 페이지를 할당받지만, 내부 단편화로 인해 할당받은 페이지의 일부분만 사용
    -> 시스템 메모리 고갈로 이어짐
  • 따라서 많은 컴퓨터 시스템들이 비교적 작은 페이지들을 사용함 (4KB, 8KB)

2. 하이브리드 접근 방법: 페이징과 세그멘트

  • 예시) 1KB 크기의 페이지를 갖는 16KB 주소공간
    • 코드 페이지: VPN 0 -> PFN 10
      힙 페이지: VPN 4 -> PFN 23
      스택 페이지: VPN 14 -> PFN 28, VPN 15 -> PFN 4
    • 페이지 테이블 대부분이 비어있음

앞서 배운 세그멘테이션과 페이징을 같이 사용하여 효과적으로 가상 메모리 시스템을 구축할 수 있다.

  • 결합 방식: "논리 세그멘트마다 따로 페이지 테이블 두기"
    (기존에는 프로세스의 전체 주소공간을 위해 하나의 페이지 테이블을 뒀음)
  • 이 예제에서는 코드, 힙, 스택 세그멘트에 세개의 페이지 테이블이 있을 것
  • 베이스 레지스터: 세그멘트의 페이지 테이블의 시작주소를 가짐 (세그멘트의 시작주소가 아님)
  • 바운드 레지스터: 페이지 테이블의 끝을 나타냄
    • 이런 식으로 상위 두 비트는 세그먼트 구분용으로, 오프셋이 12이므로 4KB짜리 페이지, 나머지는 가상주소번호로 활용
    • TLB 미스가 발생하면
      1. 세그먼트 비트를 사용하여 어떤 베이스와 바운드 쌍을 사용할지 결정
      2. VPN 가져오기
      3. PTE의 주소를 만들기 (베이스 + VPN)
      SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT 
VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT 
AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

그러나 문제점도 있다.
1) 세그멘테이션은 유연하지 못함 (힙의 경우 드문드문 사용되어 낭비 발생)
2) 외부 단편화 유발 (페이지 테이블의 크기에 제한이 없음)

3. 멀티 레벨 페이지 테이블

멀티 레벨 페이지 테이블: 선형 페이지 테이블을 트리 구조로 표현

  • 페이지 테이블을 페이지 크기의 단위로 나누다.
  • 페이지 테이블의 페이지가 유효하지 않은 항목만 있으면, 해당 페이지 할당 X
  • 페이지 디렉토리(page directory)라는 자료구조를 사용하여 페이지 테이블 각 페이지의 할당 여부와 위치를 파악
    • 페이지 테이블을 구성하는 각 페이지의 존재 여부와 위치 정보를 가짐
    • 선형 페이지 테이블은 가운데 두 공간 낭비되는 중
    • 페이지 디렉토리를 사용하면, 사용하지 않는 페이지에 대해서는 할당 X
    • 페이지 디렉토리는 페이지 디렉토리 항목 (PDE)로 구성
      • 각 PDE는 페이지 테이블의 한 페이지임
      • PDE는 유효비트(할당 여부), PFN 등으로 구성
  • 장점1) 멀티 레벨 테이블은 사용된 주소공간의 크기에 비례하여 페이지 테이블 공간이 할당됨
    • 보다 작은 크기의 페이지 테이블로 주소 공간 표현도 가능
  • 장점2) 페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리가 매우 용이
    • 페이지 테이블을 할당하거나 확장할 때, 운영체제는 free 페이지 풀에 있는 빈 페이지 가져다 쓰면 됨
  • 단점1) 멀티 레벨 테이블에는 추가 비용이 발생
    • TLB 미스 시 주소 변환을 위해 두 번의 메모리 로드 발생!
      (페이지 디렉토리와 PTE 접근 각각 한 번씩)
  • 단점2) 복잡함

멀티 레벨 페이징 예제

  • 주소공간의 크기: 16KB (=2142^{14} 비트 가상 주소공간)
    (VPN: 8비트, 오프셋: 6비트)
    페이지의 크기: 64 바이트
    선형 페이지 테이블 엔트리 개수: 256개 (=282^{8})
    PTE의 크기: 4 바이트
    페이지 테이블의 크기: 1KB (= 256 * 4)
    • 페이지가 64바이트이므로, 1KB의 페이지 테이블은 16개의 64바이트 페이지로 분할됨
    • 각 페이지에는 16개의 PTE가 있음
  • PDE 주소 추출
    • 14비트 주소 공간에서 4비트는 페이지 디렉토리 색인으로 사용
    • 페이지 디렉토리는 페이지 테이블의 각 페이지마다 하나씩 있어야 하므로 총 16개의 항목이 있어야 한다.
    • 앞 4비트의 인덱스를 PD Index(페이지 테이블 인덱스) 라고 하자
    • 베이스를 더해주는 것으로 PDIndex로 PDE의 주소를 찾을 수 있음
  • PTE 주소 추출
    • 페이지 테이블 자체 인덱스로 사용됨
    • 페이지 디렉토리 옆의 4비트를 PT Index 라고 하자
    • PDE에서 얻은 PFN을 좌측 쉬프트 연산 후, 그 값을 PTIndex에 합산하여 PTE 주소 추출 가능

실제 값들을 넣어보며 하나의 가상 주소를 변환해보자

  • 페이지 디렉터리와 페이지 테이블의 일부
    • PFN 100에는 코드 세그멘트(0,1)와 힙 세그멘트(4,5)가 유효함
    • PFN 101에는 마지막 부분(15,16)가 유효함, 근데 이는 사실 VPN 254,255으로 스택 세그먼트이다.
    • 단 세 개의 페이지만 할당, 엄청난 절약!

2단계 이상 사용하기

지금까지는 멀티 레펠 페이지 테이블은 페이지 테이블 - 페이지 디렉토리의 2개 단계를 가정하였다. 경우에 따라서 트리의 단계를 더 증가시키는 것도 가능하다.

멀티 레벨 페이지 테이블의 목적은 페이지 테이블의 모든 분할된 부분들이 단일 페이지 크기에 맞도록 하는 것이다. 만약 페이지 디렉토리가 너무 커지면 단일 페이지의 크기도 커지게 된다. 따라서 여러개의 페이지의 디렉토리로 분할할 필요가 있다.

  • 예시) 512바이트 페이지와 30비트 가상 주소 공간
    • VPN: 21개의 비트
      오프셋: 9개의 비트
      페이지의 크기: 512 바이트
      PTE의 크기: 4바이트
    • 한 페이지에 128개의 PTE를 넣을 수 있다. (512/4 = 128)
    • 따라서 페이지 테이블의 페이지의 인덱스는 7비트가 필요하다.
      (VPN의 페이지 테이블 색인 21비트 중 하위 7비트 사용)
    • 그러면 VPN에서 14개의 비트가 남고, 페이지 디렉토리에 2142^{14}개의 항목이 있게 된다.

      이러면 128 페이지 분량의 연속된 메모리가 필요한데, 페이지 테이블을 페이지 단위로 나누어 배치할 수 있는 멀티 레벨 페이지 테이블의 근본 취지가 훼손된 셈이다.

  • 이 문제를 해결하기 위해 페이지 디렉토리 자체를 멀티 페이지들로 나누어 트리의 단계를 늘리도록 한다.
    • 이런 식으로 페이지 디렉토리가 트리 형태로 구성된다.
    • PD 인덱스 0에서 먼저 상위 단계 페이지 디렉토리에서 PDE를 가져온다.
    • 유효하다면 방금 얻은 물리 주소와 PD 인덱스 1을 결합하여 페이지 테이블 인덱스가 존재한 물리페이지를 구한다.
    • 해당 페이지가 유효할 경우, 최종적으로 PTE 주소는 2번째 단계의 PDE에서 얻은 물리 주소와 결합하여 실제 주소를 구한다.

변환 과정: TLB를 기억하자

VPN = (VirtualAddress & VPN_MASK) >> SHIFT 
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True) // TLB 히트
	if (CanAccess(TlbEntry.ProtectBits) == True) 
    	Offset = VirtualAddress & OFFSET_MASK 
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
	else
		RaiseException(PROTECTION_FAULT)    
else // TLB 미스
    // 먼저, 페이지 디렉터리 항목을 얻어야 함
    PDIndex = (VPN & PD_MASK) >> PD_SHIFT
    PDEAddr = PDBR + (PDIndex * sizeof(PDE)) 
    PDE = AccessMemory(PDEAddr)
    if (PDE.Valid == False)
		RaiseException(SEGMENTATION_FAULT) 
    else
        // PDE 가 유효함: 이제 페이지 테이블에서 PTE를 가져오자
        PTIndex = (VPN & PT_MASK) >> PT_SHIFT
        PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE)) 
        PTE = AccessMemory(PTEAddr)
        if (PTE. Valid == False)
        	RaiseException(SEGMENTATION_FAULT)
        else if (CanAccess(PTE. ProtectBits) == False) 
        	RaiseException(PROTECTION_FAULT)
        else	
        	TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits) 
            RetryInstruction()
  1. TLB 검사 후 TLB Entry 추출
  2. 히트 시, 테이블 참조 없이 물리주소 직접 구성
  3. 미스 시, 멀티 레벨 페이지 테이블 참조
    1) PDE를 메모리에서 가져옴
    2) PDE가 유효하면 페이지 테이블에서 PTE를 가져옴
    3) 이후 TLB에 VPN, PFN, Protection 비트를 넣어줘 캐싱

4. 역 페이지 테이블

역 페이지 테이블: 물리 페이지를 가상 주소 상의 페이지로 변환하는 테이블

  • 여러 페이지 테이블 대신 하나의 페이지 테이블만 두어 공간을 절약한다.
  • 역 페이지 테이블의 각 항목은 해당 물리 페이지를 사용 중인 프로세스 번호, 해당 가상 페이지 번호를 갖고 있다.
  • 탐색 속도 향상을 위해 해시 테이블을 사용한다.

5. 페이지 테이블을 디스크로 스와핑하기

여전히 모든 페이지 테이블을 물리 메모리에 놓기에는 양이 너무 클 수도 있다.

  • 따라서 페이지 테이블을 커널 가상 메모리에 존재시킬 수 있다.
  • 시스템 메모리가 부족할 경우, 페이지 테이블들을 디스크로 스왑(swap)하기도 한다.

참고

https://velog.io/@junttang/OS-2.6-MV-6-Multi-Level-Page-Tables

profile
장선규
코딩연습
이전 포스트

[OS] 페이징: 더 빠른 변환 (TLB)

0개의 댓글