Paging

By: Baljit Singh Saini Memory Management

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
1. Page number (p)
2. 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
Then
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) 4
b) 10

Solution:
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

Frame Allocation

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:
- Key
- value
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

Translation look aside buffer — Use of TLB

Example

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%.
Solution:
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

Practice Problem:
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%.
Solution:
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

Previous                                         Next

Contiguous Memory Allocation Segmentation

Page size = 4bytes = 2^2 (i.e. n=2)
Address space = 32 = 2^5 (i.e. m=5)
Logical address = 10
In binary = 1010
Page number=(higher)(m-n)bits=5-2=3 bits
i.e. 010 = 2
Offset = (lower)n bits = 2 bits i.e. 10 = 2
From page table, if page number = 2
Then frame = 4
Physical address = (frame*page size)+offset = 4*4+2 = 18