Paging (페이징)과 TLB

물리 메모리에 할당을 불연속적으로 하는데, 프로세스를 고정 크기로 나누어 할당함

지금은 세그멘테이션보다는 페이징을 사용함

 

세그멘테이션은 가변 크기라 하드웨어랑 친하지 않아 가속받기 어렵고,

외부 단편화 문제와 프리스페이스를 다루는 문제가 있음

 

페이징은 고정 크기라 프리 스페이스 관리가 쉽고 하드웨어 가속도 받을 수 있음

 

왜 페이징인가

버추얼 메모리: 고정된 사이즈의 유닛들(called page)로 나뉨

피지컬 메모리: 고정된 사이즈의 유닛들(called page frame)로 나뉨

주소 변환: Page Table 을 사용

 

페이징 예시

버추얼 어드레스 사이즈: 64B

페이지 크기: 16B

=> 4개의 페이지

피지컬 메모리는 128B, 프레임 사이즈 16바이트 (보통 페이지 크기와 같음)

=> 8개의 프레임

 

3

7

5

2

페이지 테이블이 위와 같다고 가정,

페이지 테이블 인덱스는 Virtual Page Number

밸류는 Physical Frame Number

버추얼 메모리(4) -> 피지컬 어드레스: 3 * 16B + 4

 

버추얼 어드레스: 44

44 / 16 = 2 .. 12 => 2번 페이지 엔트리 => 5번 프레임

5 * 16B + 12B = 92B

 

버추얼 어드레스: 21

21 / 16 = 1.. 5 => 7번 프레임

7 * 16B + 5B = 117B

 

 

버추얼 어드레스 스페이스 사이즈 64B -> 6bit (2^6 = 64B)

피지컬 메모리 사이즈: 128B -> 7bit

 

Virtual address = VPN and offset

- 페이지 사이즈 16B => 4비트, 남은 2비트는 자연스럽게 VPN을 위한 비트로 할당

 

예시

버추얼 어드레스: 21 -> 01 0101

-> VPN: 01 offset: 0101

위의 페이지 테이블대로면 프레임 넘버 111

16B * 111 + 0101 => 물리 주소 117 

---

페이지 테이블은 메모리에 있고, 베이스, 바운드 레지스터는 CPU에 있음

왜 페이지 테이블을 CPU에 저장 안해두는가?

페이지 테이블은 너무 큼

 

32비트 CPU라 하고, 페이지가 4KB라 하면

2^20 개의 엔트리가 존재 .. (VPN에 20비트, 오프셋에 12비트)

PTE(Page Table Entry) 2^20 * 4MB => 4MB

100개의 프로세스: 100 * 4MB = 400 MB

CPU에 들어가기엔 너무 큼 -> 메모리에 place

 

두가지 이슈

1. 각 메모리 접근은 주소 변환이 필요함

-> 변환은 페이지 테이블이 필요함 -> 페이지 테이블이 메모리에 있음

-> 각 메모리 접근이 두번이 됨 => TLB 사용

 

2. 메모리에 있어도 여전히 큼 -> 멀티 레벨 페이지 테이블 / 인버티드 페이지 테이블

---

Page table

- 페이지 테이블 엔트리로 구성, 각각은 페이지 프레임에 매핑됨

- 정보를 나타내기 위해 사용하는 비트가 있음

P(Present): 현재 피지컬 메모리에 있는지, 아니면 스왑 아웃되어 디스크에 있는지를 나타냄

R/W(Read, Write): 쓰기가 허용되어 있는지

U/S(User, Supervisor): 유저 모드 프로세스가 해당 페이지에 접근할 수 있는지

A(Access = reference bit): 교체를 위해 존재 (스왑 아웃)

D (Dirty): 해당 페이지가 변경되었는지 (지연쓰기)

 

To access memory

// Extract the VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> SHIFT

// Form the address of the page-table entry (PTE)
PTEAddr = PTBR + (VPN * sizeof(PTE))

// Fetch the PTE
PTE = AccessMemory(PTEAddr)

// check if process can access the page
if ( PTE.Valid == False )
    RaiseException(SEGMENTATION_FAULT)
else if ( CanAccess(PTE.ProtectBits) == False )
    Raise( PROTECTION_FAULT )
else
    // Access is OK: form physical address and fetch it
    offset = VirtualAddress & OFFSET_MASK
    PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
    Register = AccessMemory(PhysAddr)

버추얼 어드레스 사이즈: 64B, 페이지 크기: 16B

피지컬 메모리는 128B, 프레임 사이즈 16바이트 가정

64바이트 => 6비트 필요

 

VPN_MASK: 0x30 (110000)

SHIFT: 4

OFFSET_MASK: 0xFF

PFN_SHIFT: 4

 

다른 방법 없이 메모리에 접근을 하면 위와 같은 의사 코드대로 작동

 

 

메모리 트레이스

int array[1000];
...
for(i = 0; i < 1000; i++)
    array[i] = 0;

1024 movl $0x0, (%edi, %eax, 4)
1028 incl %eax
1032 cmpl $0x0328, %eax
1036 jne  0x1024

가정

페이지/프레임 사이즈: 1KB

Code- VPN:1, PFN:4  (PA = 4*1024)

Array- VPN:39, PFN:7  (PA = 7*1024)

PT: PA 1024에 위치 

** 페이지 테이블은 커널이 관리함

 

인스트럭션에 4번, 데이터에 1번 -> 5번의 메모리 접근

각각에 메모리 변환 -> 5번의 메모리 접근 추가

=> 각각의 For 루프마다 10번의 메모리 접근

 

굉장히 많은 메모리 접근이 일어나는데 이걸 어떻게 해결하느냐

=> 캐싱

 

TLB (Translation Lockaside Buffer)

CPU 내부에 있는 버퍼, MMU(Memory Management Unit)의 일부

최근에 사용한 엔트리들을 TLB에 올려둠

= Address-translation cache

1) HW first check TLB

2) if (hit), translation performs quickly without having to consult PT

3) otherwise, access PT

4) update TLB to cache the recently used PTE

 

의사 코드

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)

if( Success == True )
    if( CanAccess( TlbEntry.ProtectBits ) == True )
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = ( TlbEntry.PFN << SHIFT ) | offset
        Regiser = AccessMemory(PhysAddr)
    else
        RaiseException( PROTECTION_FAULT )
else
    PTEAddr = PTBR + (VPN + 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()

 

 

Example Code

int sum = 0;
for( i = 0; i < 10; i++ ) {
    sum += a[i];
}

 

페이지 사이즈: 16B

TLB

Offset->	00	04	08	12~16
VPN: 06		a[0]	a[1]	a[2]
VPN: 07	a[3]	a[4]	a[5]	a[6]
VPN: 08	a[7]	a[8]	a[9]

총 10번의 접근 중 3번 미스 => TLB 히트율 70%

 

페이지 사이즈가 32B이면?

0, 1, 2, 3, 4, 5, 6

7, 8, 9

같은 형태로 페이지 테이블이 만들어지고, 10번 중 2번 미스 -> 히트율 80%

 

밖에 포루프 한 번 더 있어서 전부 다시 접근하면?

20번 중 3번 미스 (페이지 16바이트 기준) => 히트율 85%

20번 중 2번 미스 (페이지 32바이트 기준) => 히트율 90%

 

*

캐싱이 효과적인 이유

Temporal locality : 어떤 부분이 접근되면 가까운 미래에 다시 접근할 가능성이 높음

Spatial locality : 어떤 부분이 접근되면 그 주변 메모리가 접근됨

*

 

캐시 사이즈를 엄청 크게 늘리면 어떤가

캐시 자체가 크기를 작게하고 빠른 메모리라 정의에 맞지 않는 것

 

 

TLB 미스는 어디서 다루나

- 하드웨어, 소프트웨어 두 가지 방법 존재

 

HW-managed TLB

- 하드웨어 로직으로 처리

- 인텔 CPU 같은 CISC 프로세서에서 처리

 

SW-managed TLB

- 하드웨어는 단순히 예외 레이즈만 함

- OS(TLB 트랩 핸들러)가 명시적으로 TLB를 다룸 -> 더 복잡함

- MIPS, Sun SPARC v9 같은 RISC 프로세서에서 처리

 

TLB 구성

VPN + PFN + other bits

페이지 테이블에는 VPN이 인덱스라 따로 필요 없는데 TLB에는 필요함

 

Bits

- Valid bit: 엔트리가 valid한 상태인지 아닌지

- Protection bitsL R/W/E

- 나머지: ASID (Address-Space IDentifier), Dirty bit..

Fully-associative - 아무 위치에 할당 가능함

패럴렐하게 서치

* Direct Mapping: 자기 번호에 따라 들어갈 곳이 딱 정해짐

* Set-associative Mapping: 전체 캐시를 몇 개의 셋으로 나누고 셋마다 들어갈 수 있는 자리가 있음

* Fully-associative Mapping: 아무대나 들어갈 수 있음

TLB는 Fully-associative하게 만들고 서치를 패럴렐하게 만들었음

 

 

ASID

Address-Space IDentifier

프로세스는 자신만의 버추얼 메모리를 가지는데,

페이지 넘버가 같아도 프레임 넘버는 다를 수 있음

 

솔루션1: 문맥교환 전 플러시

모든 valid bit를 0으로 세팅 .. 부하가 심함

 

솔루션2: AISD 사용

어드레스 스페이스마다 ID를 줘서 구분

---

TLB로 속도는 향상시켰는데 페이지 테이블의 크기는 어떻게 할 것이냐

1. 페이지 사이즈를 크게 한다

2. 세그멘테이션 + 페이징 하이브리드

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

4. 인버티드 페이지 테이블

 

1. Bigger pages

페이지 사이즈 4KB -> 페이지 테이블 사이즈 4MB

페이지 사이즈 8KB -> 페이지 테이블 사이즈 2MB

페이지 사이즈 4MB -> 페이지 테이블 사이즈 4KB

 

장점: 단순하고 TLB 히트에 효과적

단점: 내부 단편화, 헤비 로딩

 

멀티플 사이즈는 어떤가

장점: 유연하고, 내부 단편화

단점: OS 입장에서 복잡함

 

2. Hybrid approach

일단 세그멘테이션을 하면 중간에 안쓰는 페이지들은 접근하려고 해도 세그멘테이션 폴트

=> 유효한 페이지만 페이지 테이블에서 보관해도 됨

Virtual address -> segmentation -> Linear address -> paging -> Physical address

 

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

페이지 테이블에는 비어있는 엔트리가 굉장히 많음 -> 낭비

페이지 디렉토리: 각 엔트리는 관련된 페이지 테이블을 대표

페이지 디렉토리에 밸리드 비트를 사용 -> 아직 할당되지 않은 많은 페이지 테이블을 저장하지 않아도 됨

 

버추얼 어드레스는 3가지 파트로 나뉘어짐: 디렉토리 인덱스, 페이지 테이블 인덱스, 오프셋

버추얼 메모리 사이즈 16KB -> 어드레스 14비트

페이지 사이즈 64B -> 오프셋 비트 : 6비트

2^14 / 2^6 -> 2^8 (버추얼 메모리 사이즈 / 페이지 사이즈 => 페이지 수 == 페이지 테이블 엔트리 수)

리니어 어프로치로는 총 256개가 사용됨

 

멀티 레벨 어프로치

프레임 안에 다시 페이지 테이블 엔트리가 들어가야 함

64B / 4B => 16  (보통 엔트리 하나에 4바이트 사용)

프레임 당 16개 엔트리까지 사용 가능 (4비트)

16*16이면 256이니 2레벨이면 됨

 

주소 변환

Page Directory		Page of PT (@PFN:100)			Page of PT(@PFN:101)
PFN	valid	PFN	vaild	prot	PFN	valid	prot
100	1	10	1	r-x	-	0
-	0	23	1	r-x	-	0
-	0	-	0	-	-	0
-	0	-	0	-	-	0
-	0	80	1	rw-	-	0
-	0	59	1	rw-	-	0
-	0	-	0	-	-	0
-	0	-	0	-	-	0
-	0	-	0	-	-	0
-	0	-	0	-	-	0
-	0	-	0	-	-	0
-	0	-	0	-	-	0
-	0	-	0	-	-	0
-	0	-	0	-	-	0
-	0	-	0	-	55	1	rw-
101	1	-	0	-	45	1	rw-

VA = 100

=> 00 0000 0110 0100

디렉토리: 0000, PT index: 0001, Offset: 100100

디렉토리 0000 => PT 100

PT index 0001 => PFN 23

PA = 23 * 64B + 36

 

VA = 300

=> 00 0001 0010 1100

디렉토리: 0000, PT index: 0100, Offset: 101100

디렉토리 0000 => PT 100

PT index 0100 => PFN 23

PA = 80 * 64B + 44

 

VA = 16257

=> 11 1111 1000 0001

디렉토리: 1111, PT index: 1110, Offset: 000001

디렉토리 1111 => PT 101

PT index 1110 => PFN 55

PA = 55 * 64B + 1

 

VA = 200

=> 00 0000 1100 1000

디렉토리: 0000, PT index: 0011, Offset: 001000

디렉토리 0000 => PT 100

PT index 0011 => X

invaild in PT

 

VA 1030

=> 00 0100 0000 0110

디렉토리: 0001, PT index: 0000, Offset: 000110

디렉토리 0001 => X

invalid in directory

 

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)

if(Success == True)
    if( CanAccess(TlbEntry.ProtectBits) == True )
        Offset = VirtualAddress & OFFSETMASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)
else
    PDIndex = (VPN & PD_MASK) >> PD_SHIFT
    PDEAddr = PDBR + (PDIndex * sizeof(PDE))
    PDE = AccessMemory(PDEAddr)
    if(PDE.Valid == False)
        RaiseException(SEGMENTATION_FAULT)
    else
        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)
            ReteyInstruction

 

2레벨 이상의 경우

버츄얼 어드레스: 30비트

페이지 사이즈: 512B

512 = 2^9 => 오프셋 9비트, VPN: 21비트

페이지 당 엔트리 수: 128개 (512/4)

 

2레벨로 구성할 경우

Page Table Index 7bit (128개)

Page Directory Index는 남은 14비트 커버 필요

=> 페이지 디렉토리가 128개 됨 (2^14 = 2^7 * 2^7 이고, 페이지 하나에 2^7 감당 가능)

 

3레벨로 구성할 경우

Page Table Index 7bit (128개)

Page Directory Index0 7bit

Page Directory Index1 7bit

=> save memory

 

인텔 32비트: 2레벨

인텔 64비트: 4레벨

 

 

4. Inverted Page Table

기존 페이지 테이블은 VPN을 인덱스로 사용하고, 프로세스 당 하나 존재함

인버티드 페이지 테이블은 반대로 PFN이 인덱스고 VPN이 엔트리의 내용, 시스템에 하나 존재

페이지 넘버가 있으면 위에서부터 리니어하게 검사하거나 해싱

 

플래시 메모리 관리 시(FTL) 프레임 넘버가 어디 페이지 넘버에 해당하는 지 알 필요가 있을 수 있는데,

그럴 때 사용하는 기술임