Chapter#15 Paging

Chapter#15 Paging

- Address Translation Techniques

 - Dynamic Relocation

 - Segmentation

 - Paging

- Translation Lookaside Buffer

 

---

Paging

concept of paging

page(or virtual page)라 불리는 fixed-size unit으로 주소 공간을 분할한다 ( <-> segmentation은 variable size 할당)

 

page frame이라는 페이지들로 physical memory를 분할한다

page table은 각 프로세스에 존재하며 virtual address에서 physical address로 translate한다

 

Advantages of Paging

Flexibility : 주소 공간 효율의 abstraction 지원

- heap과 stack이 어떻게 커지는지 굳이 관리할 필요 없음

Simplicity : free-space management 효율성

- no external fragmentation

 

Virtual Address

VPN : Virtual Page Number

Offset : page의 offset ( or VPO : Virtual Page Offset )

ex) 64Byte address space with 16Byte page

- 64Byte address space : 6bits

- 4 virtual pages ( 64/16 ) : VPN = 2bits

- 16Byte page : VPO = 4bits

 

 

address translation

Page Table

virtual address를 physical address로 mapping하는 자료구조

OS에서  VPN에 맞는 PFN의 PTE(page table entry)를 참조하여 physical address 확인

 

Page Table은 어디에 저장될까?

- awfully large (e.g. 32bit address space, 4KB page, 20bit VPN => 4MB = 2^20 entries * 4B per PTE)

- 모든 PTE의 register 유지 불가능 > page table은 main memory에 저장됨

 

Flags on PTE

Valid bit : 유효한가?

Protection bit : read from, written to, executed from가능한가?

Present bit : physical memory에 있는가 disk에 있는가

Dirty bit : memory에 들어온 후로 페이지가 수정되었는가?

Reference bit (Accessed bit) : page가 accessed 되었는가?

 

Page Sharing : Copy on Write

fork() 등을 통해 두 프로세스가 코드 영역 등을 공유할 수 있다

ex) fork를 통해 두 프로세스 A, B가 같은 메모리 공간을 가르킨다고 하자

프로세스 B의 값이 수정되는 경우 해당 페이지의 값이 copy 된 후 새 페이지에 write된다

코드 영역의 경우 Protection bit이 RE(Read)이므로, MMU에 의해 수정이 금지된다

 

Problems with Paging

Internal Fragmentation : data size가 page size보다 작은 경우 발생

- Solution : using small page size

Performance degradation : 한 번의 memory access를 위해 두 번 memory access가 필요

- Solution : TLB

Huge page tables : code, heap, stack(in segmentation < many PTEs(in paging)

- Table size : 4MB = 2^20 entries * 4B per PTE (32bit address space, 4KB page, 20bit VPN => 4MB)

- 100개 이상 process : 4MB * 100 = 400MB (very large!)

 

- page size를 늘린다면? (e.g. 16KB)

 - Table size : 1MB = 2^18 entries * 4B per PTE

 - Internal fragmentation 발생! (Trade-Off)

 

- Solution : hybrid or multi-level paging

---

Translation Lookaside Buffers (TLB)

chip의 MMU(memory-mangement unit)의 일부분

잘 사용되는 V2P address translation의 H/W cache (keep popular PTEs in SRAM)

 

Address Translation

a) 기존 방법 (VA : Virtual Address, PA : Physical Address, PTE : Page Table Entry,  PTEA : PTE Address)

1) 프로세스가 VA를 MMU로 보냄

2-3) MMU가 PTE를 메모리의 page table에서 가져옴

4) MMU가 메모리에 PA 보냄

5) 메모리가 data word를 프로세스한테 보냄

 

b) TLB 사용

TLB Hit	TLB Miss

 

TLB Entry

일반적으로 32, 64 or 128 entries를 가진다

H/W는 parallel하게 TLB 전체를 뒤진다.

Other bits : Valid bits, Protection bits, ASID(Address-Space Identifier)

 

TLB Issue : Handling TLB Miss

H/W(CPU)가 할까 S/W(OS)가 할까?

Hardware-managed TLBs	Software-managed TLBs
PTBR(page-table base register)이 page table을 가리킴 e.g. CR3 register in X86 1. 현재 page table로 이동 2. 알맞은 PTE 찾기 3. Desired Translation 추출 4. TLB를 Translation으로 Update 5. Instruction 재시도	1. H/W raise exception : - 1. 현재 instruction 정지 - 2. kernel mode로 변경 - 3. trap handler로 이동 2. OS의 traphandler 작동 3. OS가 page table의 translation 확인 4. OS가 special privilaged instructions로 TLB Update 5. OS가 trap에서 돌아옴 6. H/W가 Instruction 재시도
+ Efficient : CPU Cycle이 얼마 필요 없다 - Complex CPU design- Lack of flexibility - (probably) Hight TLB miss ratio - H/W가 victim 선택함	+ Simple CPU Design + Flexibility : H/W변경없이 page table 구현 + Lower TLB miss ratio - Relatively Slower : trap handler는 CPU Cycle 많이 소모

 

 

TLB Issue : Context Switching

Can't Distinguish which entry meant for which process	ASID express that

같은 TLB Entry를 가진 두 프로세스의 page가 Context Switching을 통해 동시에 TLB에 올라간 경우 구분에 문제가 있다

ASID를 통해 어떤 프로세스의 Entry인지 확인

---

 

학교 강의를 토대로 개인 공부 목적으로 작성되어 오타가 및 오류가 있을 수 있으며, 문제가 될 시 삭제될 수 있습니다.