First In First Out

FIFO

Belady Anomaly In FIFO

Least Recently Used

LRU

Most Recently Used

MRU

Random Page Replacement

Optimal Page Replacement




I N T R O D U C T I O N



Introduction To Paging

Non-contiguous memory allocation is a memory allocation technique that allows storing parts of a single process in a non-contiguous manner. Different parts of the same process can be stored at different places in the main memory.

Non-contiguous memory allocation is of two types:
1) Paging
2) Segmentation

Learn More

Paging

Paging is a storage mechanism that allows OS to retrieve processes from the secondary storage into the main memory in the form of pages.Paging is used for faster access to data, and it is a logical concept. Paging is basically an equal fixed size partitioning scheme wherein the main memory and the secondary memory are divided into fixed-size partitions. The partitions in the secondary memory are called pages and the partitions of the main memory are called the frames. Pages of the process are brought into the main memory only when they are required otherwise they reside in the secondary storage. Different operating systems have different frame sizes.


Example: Let us assume that the main memory is of the size 32KB and the frame size is 2KB each. The main memory will be divided into 16 frames each of 2KB. Say there are 4 separate processes in the system namely, P1, P2, P3, P4. Each of the processes is of 8KB and all the processes are divided into a page of 2KB. The operating system can store 1 page in one frame. At the beginning of the process, all the frames remain empty so that all the pages of the processes will get stored in a contiguous way.


Now say for example that P2 and P4 are moved to the waiting state after some time and so we can say that 8 frames have become empty. Other pages can be loaded into these empty boxes. Meanwhile, there is another P5 of 16KB waiting in the ready queue. So now the process P5 is divided into 2 parts (internally contiguous ) each of 8KB. So now there are 8 non-contiguous frames present in the main memory. The CPU always generates the logical address and from that, the physical address of the main memory is generating with the help of page offset value and frame number.

  • Advantages


    • ->Easy to use memory management algorithm
    ->No need for external Fragmentation
    ->Swapping is easy between equal-sized pages and page frames.


  • Disadvantages

    • ->May cause Internal fragmentation.
    ->Complex memory management algorithm.
    ->Page tables consume additional memory.
    ->Multi-level paging may lead to memory reference overhead.

Page Replacement Algorithms

First In First Out

This is the simplest page replacement algorithm. In this algorithm, the operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue.


Learn More

Belady's Anamoly

Belady’s anomaly is the name given to the phenomenon where increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern.


Learn More

Most Recenetly Used

MRU Page Replacement Algorithm works on a prediction that the pages that have been used more times in the last few instructions will probably be used again and again.


Learn More



Least Recently Used

LRU Page Replacement Algorithm works on a prediction that the pages that have been used more times in the last few instructions will probably be used again and again.


Learn More

Optimal Page Replacement

In optimal page replacement algorithm, the page that is not used for a long time in the future is replaced.


Learn More

Random Page Replacement

Random replacement algorithm replaces a random page in memory. This eliminates the overhead cost of tracking page references.


Learn More


Click Below for Live Simulation

Live Simulation