Question: Difference between paging & segmentation? Explain various page replacement algorithm.

Mumbai University > Information Technology > Sem5 > Operating System

Marks: 10M

Year: May 15

modified 5 months ago by gravatar for Abhishek Tiwari Abhishek Tiwari50 written 3.0 years ago by gravatar for Ramnath Ramnath3.7k
Sr No Paging Segmentation
1 A page is a contiguous range of memory addresses which is mapped to physical memory. A segment is an independent address space. Each segment has addresses in a range from 0 to maximum value.
2 It has only one linear address space. It has many address spaces.
3 Invisible to,programmer Visible to programmer
4 Procedures and data cannot be separated Procedures and data can be separated
5 Procedures cannot be shared between users Procedures can be shared between users
6 Procedures and data cannot be protected separately Procedures and data can be protected separately
7 Eliminates external,fragmentation. Eliminates internal,fragmentation.
8 A page is of fixed size A segment is of arbitrary size.
9 Paging consist of Static linking & dynamic loading Segment consist of Dynamic Linking & Dynamic Loading
10 A,page is of physical unit A page is of logical unit

Page Replacement Algorithm:

  • Page replacement algorithms decide which memory pages to swap out, write to disk when a page of memory needs to be allocated. When a fault occurs, the OS loads the faulted page from disk into a page of memory. The goal of the replacement algorithm is to reduce the fault rate by selecting the best victim page to remove.

  • A page replacement algorithm is said to satisfy the inclusion property or is called a stack algorithm if the set of pages in a k-frame memory is always a subset of the pages in a (k+1) frame memory.

  • Following are the page replacement algorithm:

    1) First in First out (FIFO)

    2) Optimal

    3) Least Recently used(LRU)

    1) First in First out(FIFO):

    • The simplest page-replacement algorithm is a first-in, first-out (FIFO) algorithm.

    • A FIFO replacement algorithm associates with each page the time when that page was brought into memory.

    • When a page must be replaced, the oldest page is chosen.

    • On the one hand, the page replaced may be an initialization module that was used a long time ago and is no longer needed.

    • On the other hand, it could contain a heavily used variable that was initialized early and is in constant use. 0, 4, 3, 2, 1, 4, 6, 3, 0, 8, 9, 3, 8, 5.

enter image description here


Hit = 1

Fault = 13


  • Simple to understand & easy to operate.

  • Better for long process

  • No starvation

  • Maintain a Linked list of all pages in memory.


  • This scheduling method is Non-Pre-emptive

  • Throughput is not emphasized.

2) Optimal:

Optimal page replacement algorithm is considered the best possible page replacement policy in a virtual memory theoretically but is difficult to implement. According to the optimal page replacement algorithm, the page in the main memory, which will not be referred to for the longest time is swapped out from the main memory to create room for the requested page. For eg: 0, 4, 3, 2, 1, 4, 6, 3, 0, 8, 9, 3, 8, 5.

enter image description here


  • Has the lowest page fault rate

  • It reduces the total page replacement timings

  • Never suffers from Belady’s anomaly.

  • It improves the system performance by reducing overhead for number of page faults and swapping pages in and out, when a page fault occurs.


  • Difficult to implement

  • It needs forecast i.e. Future knowledge.

  • It becomes very difficult for an operating system to calculate after what interval a page is to be referred to.

3) Least Recently used (LRU) :

  • In this algorithm, the page that has not been used for the longest period of time has to be replaced.

  • LRU is implementable because it works on past knowledge of pages

  • If there is page A in memory that has been referenced 20 million instructions in past and page B has been referenced 10 million instructions in past, then choose page A for replacement.

  • There are two ways of finding LRU page frame:

1) Maintain a List: Every time a page is referenced, it is moved to the head of the list. When a page fault occurs the LRU frame is at the tail of the list.

2) Maintain a Counter or Timer: On every reference store the counter on a table entry associated with the referenced frame. On a page fault, Search through the table for the smallest entry.

enter image description here


  • It is amenable to full statistical analysis.

  • Never suffers from Belady’s anomaly


  • Implementation is difficult

  • Require substantial hardware assistance

written 3.0 years ago by gravatar for Ramnath Ramnath3.7k
Please log in to add an answer.