Paging

* To permit the physical address space of process to be noncontinuous

* How?

- Divide physical memory into fixed-sized blocks called frames

- Divide logical memory into blocks of the same size called pages

- To run a program of size n pages, it is needed to find n free frames and load the program

- Set up a page table to translate logical to physical addresses

- Internal fragmentation 

위 그림을 보면 logical memory에 있는 내용들이 page table에 저장된 physical memory의 위치에 잘 들어가있음을 알 수 있다

Address Translation Scheme

* Address generated by CPU is divided into

+ Page number(p) : Used as an index into a page table which contains base address of each page in physical memory

+ Page offset(d) : Combined with base address to define the physical memory address that is sent to the memory 

p

d

m-n                                                                                n

given logical address space 2^m and page size 2^n

예)

옆 그림은 32바이트 메모리와 4바이트 페이지를 나타낸다

4바이트 페이지란 page entry size를 의미한다

또한 page size=frame size이다

Free frames

그림을 보면 0 1 2 3이라는 frame#에 14 13,18,20이라는 page를 할당한 모습

Implementation of page table

* Page table is kept in the main memory

* Page table base register(PTBR)은 page table을 가리킨다 (page table이 main memory의 어디에 있는지)

* Page table length register(PTLR)은 page table의 크기를 나타낸다 (=process 크기)

* 이 scheme에서 모든 데이터와 명령어 액세스는 두 개의 메모리 액세스를 요구한다! -> 하나는 page table에 대한 것, 다른 하나는 data와 instruction에 대한 것!

* 두 메모리 액세스는 Translation Look-aside Buffers(TLB)라는 special fast lookup h/w cache를 이용해 해결할 수 있다 (왜 해결해야 하는가? 메모리 액세스가 여러번 일어나면 시스템 성능이 낮아지므로)

TLB

* Some TLBs store address-space identifiers(ASIDs) in each TLB entry (identify+protection의 기능)

* Effective access time

+ TLB lookup - ε time unit

+ Memory access time - 1 time unit

+ Hit ratio (α) - % of times that a page number is found int the TLB

+ Effective Access Time(EAT) : Paging의 성능 측정

= (1+ε)α+ (2+ε)(1-α) = 2+ε-α

= (memory access + TLB lookup)TLB hit + (memory access+PageTable access+TLB lookup)(TLB miss)

Memory protection

* Implemented by protection bites associated with each frame

* valid-invalid bit

+ Attached to each entry in the page table

+ valid - indicates associated pate is in the process' logical address space

+ invalid - indicates the pate is not in the process' logical address space

Shared code

* One copy of read-only code shared among processes

Structure of the page table

1 Hierarchical  Paging

* break up the logical address into multiple page tables

* a simple technique is two level page table

outer page table은 각 page의 시작주소를 가리킨다

예)+ two level page table scheme example

- 32-bit machine with 4K(2^12) page size

= m=32, n=12 bit

- Each page entry size = 4 bytes

= PT 전체크기는 4M (2^(m-n) = 2^20 = 1MB * 4byte)

- A logical address is divided into 

page number consisting 20 bits

page offset consisting 12 bits

- since the page table itself is paged, the page number is further divided into 

10 bit page number

10 bit page offset  (4MB/4KB = 2^10 blocks = 1KB)

장점 : 모든 Page table을 저장할 필요가 없다

block들을 secondary store에 놔두고 필요할  때 찾아쓰면 된다

* Three-level page size

+ A logical address (on 64 bit machine with 4K page size)

+ 42bit outer page -> 32bit 2nd outer page & 10bit outer tage

2 Hashed Page tables

* Common in address spaces > 32bits

* virtual page number is hashed into page table; this page table contains a chain of elements hashing into the same location

* virtual page numbers are compared in this chain searching for a match; if a match is found, the corresponding physical frame is extracted

3 Inverted Page tables

* One entry for each real page of memory

* Entry consists of the virtual address of the page stored in the real memory location, with information about the process that owns that page

* Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs

그림에서 i는 물리적 메모리 공간과 mapping

문제는 크기가 너무 커질 수 있다는 것