In paging the physical address space of a process is non-contiguous. Paging is implemented using frames and pages.
- Frames – fixed size blocks of physical memory
- Pages – fixed size slots of logical memory
To execute a process, its pages are loaded into any available memory frames from the backing store. A Page Table is used to translate logical address to physical address
Address Translation in Paging
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 unit
- CPU generates logical address (e.g. 25)
- Divide that address into two parts
- Page number (p)
- Offset (d)
- Locate the frame (f) corresponding to the page (p) from the page table
- Generate physical address by combining “f” and “d” (e.g. 100101)
How to break logical address into page number and page offset?
If address space size = 2m
Page size = 2n
Page number = higher order (m-n) bits
Page offset = n low-order bits
Example of Paging
Q. Using a page size of 4bytes and physical memory of 32 bytes, find the physical address if the logical address is
a) Page size = 4bytes = 22 (i.e. n=2)
Address space = 32 = 25 (i.e. m=5)
Logical address = 4
In binary = 00100
Page number=(higher)(m-n)bits=5-2=3 bits
i.e. 001 = 1
Offset = (lower)n bits = 2 bits i.e. 00 = 0
From page table, if page number = 1
Then frame = 6
Physical address = frame * page size+offset = 6*4+0 = 24
b) Discuss your answer in the comments section
- Process requests frames corresponding to its two pages 0 and 1
- OS consults free frame list
- Allocates two frames and makes entry in page table
- Update the free frame list
Hardware Support using TLB
- Translation Look aside buffer (TLB) is a high-speed, associative memory.
- Need – to reduce memory access time
- Entry in TLB consists of:
- Adv: access is fast
- Dis: high cost
Address Mapping Using TLB
- CPU generates logical address that comprise of page number (p) and offset (o).
- Next, look for frame number (f) corresponding to p in TLB.
- If the entry is present in TLB then it is a TLB Hit
- In contrast if entry is missing in TLB, then it is searched in page table which is in main memory.
- This is referred as TLB miss
Q. If it takes 20 nanoseconds to search the TLB and 100 nanoseconds to access memory, then find the effective access time if the hit-ratio is 80%.
Time taken to access data if page entry is in TLB = 20+100=120
Time taken to access data if page entry is not in TLB = 20+100+100 = 220
Hence, Effective access time = .80120 + .20220
= 140 nanoseconds
Q. If it takes 20 nanoseconds to search the TLB and 100 nanoseconds to access memory, then find the effective access time if the miss-ratio is 2%.
Effective access time = .98120 + .02220
= 122 nanoseconds
PPT on Paging
Note: Clicking on the “next” slide button will not display any animation. Hence, Click within the slide area for animations.
Video on Paging