Paging

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

1. CPU generates logical address (e.g. 25)
2. Divide that address into two parts
   1. Page number (p)
   2. Offset (d)
3. Locate the frame (f) corresponding to the page (p) from the page table
4. 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

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

Previous                                         Next

Contiguous Memory Allocation              Segmentation