Page Replacement Algorithm

When a process executes and the desired page is not in memory, page fault occurs. After locating desired page in memory, OS finds free frame. BUT OS finds that there are no free frames. The OS at this point have multiple options

1.       Terminate the user process

2.       Swap out the process and freeing all its frames

3.       Page Replacement

When no frame is free, process of finding a page that is not currently being used and free it is known as page replacement. The page replacement causes the following sequences of steps to occur

1.       Find the location of the desired page on the disk

2.       Find a free frame

a.       If frame is free, use it

b.      If there is no free frame, use page replacement algorithm to find a page that is not currently being used to select victim frame

c.       Write victim frame back to disk

d.      Update page and frame table

3.       Issue a disk read operation to a free frame

4.       After completing disk read, update page table to show desired page is in the memory now.

5.       Restart the user process

FIFO Page Replacement Algorithm

The simplest page replacement algorithm is First In First Out (FIFO) algorithm. The algorithm associates with each page the time it was brought into the memory.  It replaces that has been in memory for the longest period of time( brought in memory first).  A queue is used to implement FIFO algorithm. A new page is inserted at the rear end whereas page is replaced from the front end of the queue.

The algorithm is easy to understand and program. But performance is not good.

Optimal Page Replacement Algorithm

Optimal Page Replacement algorithm replaces the page that will not be used for the longest period of time.

This algorithm gives lowest possible page fault rate for a fixed number of frames. This algorithm on the other hand is difficult to implement because it requires future knowledge of reference string.

LRU Page Replacement Algorithm

LRU Page replacement algorithm replaces the page that has not been used for the longest period of time. The algorithm associates with each page the time of the page last use.

LRU can be viewed as Optimal Page replacement algorithm in backward  direction and therefore doesnot require future knowledge of reference string.

The algorithm can be implemented in two ways

Keep stack of page numbers. When page is referred, it is popped 

Demand Paging

Consider a menu driven program that has 50 options. Depending upon user choice one option will execute. But to execute a program it must be loaded into the memory.

One way is to load the complete program in physical memory at program execution time. This makes inefficient use of memory because out of 50 options available, code under one option will be executed.

Alternatively, we can load pages only when they are needed. This is known as demand paging and used in virtual memory management.

Demand Paging is an efficient memory management technique in which page is loaded only when demanded during program execution. Pages that are never accessed, never loaded into the memory. 

This technique has following advantages

i.                     No limitation on size of physical memory available.

ii.                   Each program takes less memory as a result more programs run at same time which in turn increases CPU utilization and throughput.

iii.                  Less number of swapping occurs therefore program runs faster

In demand paging, each process resides in secondary memory(disk). When a process execute instead of loading entire process in physical memory, the page that is needed will only be swapped. As compared to swappere who swaps all the pages of process in memory, we use a lazy swapper that swap only those pages that are need. In addition, since each process is a collection of pages therefore we call it a pager not swapper. Pager guess which page will be used and therefore instead of swapping whole process, pager brings only those pages in memory that is needed.

To distinguish between the pages that are in memory or on the disk, page table uses valid invalid bit scheme is used. If the page is legal and in memory, then the bit is set to valid. The bit is set to invalid, if the page is in the disk or page doesn’t belong to logical address space of the process.

When a process executes and access only pages that are in memory (known as memory resident pages), execution occurs normally. BUT when a process requires a page that was not in memory (bit is invalid), page fault occurs. The following steps is required to handle page fault

1.       Trap sent to the operating system

2.       If page reference was legal and determine the location of the page on the disk to brought the page into the memory.

3.       Find a free frame.

4.       Issue a disk read operation to a free frame

5.       After completing disk read, update page table to show desired page is in the memory now.

6.       Restart the instructions that were interrupted by the trap.

Virtual memory

Virtual memory is a storage allocation scheme in which secondary memory can be treated as a part of main memory.

Virtual memory gives an illusion of having large memory when in reality only smaller system’s RAM (physical memory) is available.

Virtual Memory is implemented using Demand Paging.

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. 

Fragmentation

Fragmentation is a phenomenon in which storage space is used inefficiently. Fragmentation occurs when main memory is available but space is not sufficient to load any other process.  Due to swapping and dynamic memory allocation, user process swap in and swap out of the main memory. As a result there are free space but we cannot load new process because available size is smaller than size of the process.

Types of Fragmentation:

Internal Fragmentation occurs when memory allocated to a process is slightly larger than the actual memory requirement of the process. The difference is known as internal fragmentation. Internal fragmentation is actually unused memory internal to a process partition.

Example: Suppose, four process arrives and P1 requires 35 KB, P2 requires 70 KB, nd P4 requires 28 KB. The new process P5 requires 54KB. Memory requirement of process P5 is not fulfilled because internal fragmentation occurs in this case.

REASON: Total Free Memory = 50 + 2 + 5= 57 KB. But we cannot allocate to process P5 because free memory is within allocated process memory area.

2   External Fragmentation occurs when there is a sufficient area within main memory to satisfy current process memory requirement. BUT memory cannot be allocated because available memory is not contiguous.

Example: Suppose a new process arrives and needs 100 KB. In this case, external fragmentation occurs and memory is not allocated to new process.

REASON: The total free memory available is 30+20+60+10=120KB. But we cannot allocate memory to new process because available free memory is not contiguous.

 

The solution for external fragmentation is compaction and non contiguous memory allocation

Compaction is a process to shuffle memory content so that all free memory forms one large block. Practically this is not possible every time.

Another way to solve external fragmentation is allowing logical address space to be non contiguous. The two methods used are Paging and Segmentation.