18. Paging: Introduction

 

Concept of Paging

Paging ?

• address space를 page라는 fixed-sized unit으로 split up 하는 것
• paging을 이용하면 단편화 문제를 해결할 수 있다.

page frame

• physical memory에서의 page

page table

• virtual mem의 page를 physical mem의 page frame으로 mapping 한 정보를 기록해 놓은 곳
• process 마다 존재한다.

 

 

Advantages of Paging

• Flexibility : supporting the abstraction of address space effectively
• Simplicity : ease of free-space management

 

 

Example: A Simple Paging

• 64 byte address space 를 16 byte 크기의 page로 split
• 2^6 / 2^4 = 2^2 
• address space의 6bit 중 4bit는 page offset, 2bit는 page table의 index로 사용한다.
• page table 내에는, mapping 된 page frame number가 기록된다.

 

 

Address Translation

• VPN : virtual page number (page offset을 뺀 나머지 bit로 vpn)
• Offset : offset witin the page (page size에 따라)

=> virtual address 는 vpn과 offset으로 나뉜다.

• PFN : page frame number

 

 

Where Are Page Tables Stored?

• 32 bit address space를 4KB page size로 split 해보자.
• 2^32 / 2^12 = 2^20 (page table entry 개수)
• 각 page table entry 는 보통 4byte이다.
• 즉 2^20 * 4 = 4MB => page table 자체의 사이즈가 몹시 커질 수 있음.

 

 

What is in the page table?

• page table == data structure 
• OS가 VPN을 index를 사용하여 page-table entry를 look-up

 

 

Common Flags Of Page Table Entry

• Valid Bit : vpn - pfn 간에 mapping이 되어있는지
• Protection Bit : page가 read from / written to / excuted from 중 어떤 것인지 표시
• Present Bit : page frame이 현재 memory에 있는지, disk로 swapped out 되어 있는지 표시
• Dirty Bit :  해당 page가 physical로 올라온 후에, process에 의해 수정이 되었는지
• Reference Bit(Accessed Bit) : 한 번이라도 accessed 됐는지 아닌지

 

 

Paging: Too Slow

• mmu가 V.A => P.A로 변환하는 과정

1. page table의 위치

=> page table의 위치는 PCB 안에 저장 => 해당 process가 context switching 되어서 실행이 될 때, 이 위치가 mmu의 reg로 복사가 됨(CR3 => page table의 시작 주소를 알 수 있음) 

 

2. VA에서 VPN 추출 => page table의 index로 사용

=> hardware에서 해줌

 

--- 여기까지는 processor 내부에서 실행 => 크게 성능 저하 x

 

3. 그 index의 PTE를 찾아서, 그 안에 있는 PFN 정보 추출

=> processor 밖의 physical mem에 접근해야 함 ==> 성능저하 발생

 

4. VPN => PFN으로 대치 

=> processor 내부에서 실행

 

 

Accessing Memory With Paging

• VPN_MASK : VPN bit 만큼만 1로 설정, 나머지 0으로 설정해서 VPN 추출
• SHIFT(PFN_SHIFT) : offset bit만큼 늘였다 줄였다 해주는 것
• OFFSET_MASK :  offset bit 만큼만 1로 설정, 나머지 0으로 설정해서 offset 추출
• PTBR :  page table의 시작주소(physical address)

• virtual address를 받으면, vpn_mask를 이용해서 앞에 bit 추출 후 shift해서 그 bit만 남겨주기
• page table의 첫 시작 주소와, vpn (index) * size 해서 PTE 의 주소 추출
• PTE 내부 bit들이 vaild하고 accessible 하면,
• 추출한 PTE의 주소를 바탕으로 내부 PFN 값 추출 and offset 추출
• physical address 추출 방법 : PFN에서 offset bit 만큼 shift left 후 offset을 OR로 붙여주기

 

 

A Memory Trace

• 간단한 배열 c 코드를 컴파일하고 실행하면, deassembly가 돼서 assembly code로 변한다
• 배열의 주소에 값을 넣고, + 1 씩을 반복 실행

 

• 위의 첫 명령어가 0x1024에 있으니, 이 VA를 실행하려면, PA로 변환해야함 => page table 읽기
• page table을 읽었더니 , entry가 1번 => 즉 vpn = 1, 이 말은 앞에 0~1023까지가 한 page고 1024가 새로운 entry로 넘어갔으니, page size가 1KB라고 추측..(아니 근데 0~1023까지 다 vpn 0번일거라는 보장이 어디서오는거지)

1. page table 접근
2. 실제 physical mem 접근 => instructor reg로 옮기고
3. move(store)명령을 할 배열  virtual address의 page table 접근 
4. 실제 store 할 physical mem 접근
5. 이후 loop

=> 한번의 loop를 위해 총 10번의 memory reference가 이루어짐 => 성능 저하

(하나의 inst를 실행하기 위해 통상적으로 2번의 메모리 접근

=> page table 접근 + 거기서 얻은 pfn으로 실제 physical mem 접근

=> move(store)는 이 명령이 하는 일 자체가 또 physical에 접근 하는거라 추가 2번이 더 필요한 것)