Paging

Paging is a memory management scheme that permits physical address space of a process to be non contiguous. 

In paging, physical memory is partitioned into fixed size blocks called FRAMES and logical memory is partitioned into block of same size called PAGES. The size of page is equal to frame size. Every CPU generated address is now divided into two parts 

i. Page Number (p): Used as an index into page table. 

ii. Offset

In paging, it is not necessary for a free frame to be contiguous. It can be allocated to a process that needs it. Thus there is no external fragmentation and there is no need for compaction.

Page table contain address of each page in physical memory. That is page table contain frame number in which page is available.  The base address plus page offset gives physical memory address. 

To provide memory protection, page table consists of additional bit known as valid or invalid bit. The bit is set to valid if page is in logical address space and is valid. It is set to invalid if page is not in the logical address space. Valid and Invalid bit is set by OS for each page. 

When a process arrives, its size in pages is examined. Each page of process needs one frame. Process of n pages requires that n frames are available. If frame is available, first page is loaded into one of the available frame and entry of frame number is made in the page table. The next page is now loaded and entry is made in page table. The process is repeated for all the pages of the process. 

<diagram>

In addition to page table, OS maintains a frame table. Frame table has one entry for each frame indicating whether it is free or allocated. If frame is allocated, frame table stores process name and its page number. 

Structure of Page Table

Some the methods to structuring the page table is as follows

1. Hierarchical Paging: In a 32 bit logical address space and page size of 4 KB (212), page table consist of 232/212 entries. The page table becomes very large. One solution is to divide the page table into smaller pieces. When we divide page table in two parts it is called two-level paging algorithm.  The table is also known as forward mapped page table because address obtained by moving for outer page to inner page.

In a 32 bit logical address space and page size 4KB (212), 12 bits consist off set. The remaining 20 bits page number is divided into two parts:  p1=10 bits for page number and p2=10 bits for offset. P1 is index number of outer page table and p2 is displacement of outer page table.

<diagram1>

2. Hashed Page Tables: In hashed page tables the hash value is the page number. Each entry in a hash table contains a linked list of elements that hash to same location. Each element consist of three parts

i. Logical page number

ii. Value of mapped page frame

iii. A pointer to next element of linked list

The logical page number is compared with the field 1 of first element in the linked list. If there is a match, the corresponding frame number present in field 2 is used to form the desired physical address. If no match, next entries are searched. 

Hashed Page Table

3. Inverted Page tables: An inverted page table has one entry for each frame of memory.  Each entry consist of logical address of the page and the information of a process to which the page belongs; i.e. process id. It means there is only one page table is in the system.  

Here, logical address consist of three parts

i. Process Id

ii. Page Number 

iii. Offset

The inverted page table is sorted by physical address but searching is done on logical address. When memory reference occurs, page table is searched for a match. If match is found at position x, then the physical address is (x,offset). If no match is found, an illegal address is accessed.