FIFO PAGE REPLACEMENT ALGORITHM

In this “FIFO PAGE REPLACEMENT ALGORITHM” covers FIFO page replacement technique with example and FIFO page replacement Program with Input-Output.

In Memory Management, Paging is a technique by which a computer can store and retrieve data from secondary storage for use in main memory. To do page replacement there are some page replacement algorithms.

Page replacement algorithms are able to decide which page needed to be replaced when new page comes in. Whenever a new page is referred and not present in memory, page fault occurs and Operating System replaces one of the existing pages with newly needed page. Different page replacement algorithms suggest different ways to decide which page to replace. The target for all algorithms is to reduce number of page faults.

First In First Out (FIFO) Page Replacement Algorithm –

In this simplest page replacement algorithm, operating system keeps track of all pages in the memory in a queue, oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.

In FCFS scheduling, Where which process comes first can execute first. Similar to this, FIFO page replacement select the first page for removal when new page is entered.

A process can be divided into several pages, when CPU requires a page that is not in the Main Memory, Some page replacement algorithms is used to load that page in Main Memory. During checking, Weather the page is found or not, it is generally described as,

Page Hit – If CPU tries to retrieve the needed page from main memory, and that page is existed in the main memory (RAM), then it is known as “PAGE HIT”. Otherwise, If not exist in main memory, then it is known as “PAGE FAULT or PAGE MISS”.

If any page fault occurs then new page must be loaded from Secondary storage to Main Memory.

FIFO PAGE REPLACEMENT EXAMPLE
FIFO PAGE REPLACEMENT EXAMPLE

ALGORITHM:

FIFO PAGE REPLACEMENT EXAMPLE
FIFO PAGE REPLACEMENT EXAMPLE

Example -1. Consider page reference string 1, 3, 0, 3, 5, 6 and 3 page slots.
Initially all slots are empty, so when 1, 3, 0 came they are allocated to the empty slots —> 3
Page Faults.
when 3 comes, it is already in memory so —> 0 Page Faults.
Then 5 comes, it is not available in memory so it replaces the oldest page slot i.e 1. —>1
Page Fault.
Finally 6 comes, it is also not available in memory so it replaces the oldest page slot
i.e 3 —>1 Page Fault.
So total page faults = 5.

Example -2. Consider the following reference string: 0, 2, 1, 6, 4, 0, 1, 0, 3, 1, 2, 1 with 4
frames.
Using FIFO page replacement algorithm –
So, total number of page faults = 9.
Given memory capacity (as number of pages it can hold)

C PROGRAM:

INPUT-OUTPUT:

Here, -1 represents empty page frames. You can see blanks here whenever there are no page fault occurs, or no new page replaced with the new. At the end, the Total page fault is 9. In order to count no of times new page enters in the queue.

YOU MIGHT LIKE :

Memory Management Note
MCQ

Leave a Reply

Your email address will not be published. Required fields are marked *

Close Bitnami banner
Bitnami