Write short note on Beladys anomaly

7views

written 4.0 years ago by

teamques10 ★ 70k

• modified 4.0 years ago

Belady’s Anomaly

Operating System uses a non-contagious memory allocation scheme called a Paging System.
In this paging system each process is divided into multiple pages.
These pages are then further placed or loaded into the several fixed-size frames in the main memory.
Page faults happen when a page referenced by the CPU is not found in the main memory.
After the occurrence of a page fault, the needed page has to be accessed from the secondary memory into the main memory.
If all the frames in the main memory are already filled, then a page has to be replaced.
To do this page replacement algorithms are used, that decide which page should be replaced.

Effect of addition of frames:

Adding the number of frames into the main memory, then the count of page faults should either decrease or remain constant.
But sometimes the abnormal scenario happens. Such as, on increasing the number of frames into the main memory, the count of page faults also increases.
This phenomenon of increasing the count of page faults on increasing the number of frames into the main memory is called Belady’s Anomaly.
This weird behavior is observed only sometimes not for all times in all scenarios.

Factors that cause Belady’s Anomaly

Page Replacement Algorithms that do not follow stack properties are suffered from this.
Stack-based page replacement algorithms do not suffer from Belady’s Anomaly. Because these algorithms assign priority to a page for a replacement that is independent of the number of frames in the main memory.

Algorithms Suffered from Belady’s Anomaly

FIFO Page Replacement Algorithm
Random Page Replacement Algorithm
Second Chance Algorithm

Algorithms Not suffered from Belady’s Anomaly

LRU Page Replacement Algorithm
Optimal Page Replacement Algorithm

Because these algorithms follow stack properties and are also called stack-based page replacement algorithms. Hence, they do not suffer from Belady’s Anomaly.

Example of FIFO Page Replacemnt Algorithm:

Consider String = 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4

For Frame size = 3

String	0	1	2	3	0	1	4	0	1	2	3	4
Frame 3			2	2	2	1	1	1	1	1	3	3
Frame 2		1	1	1	0	0	0	0	0	2	2	2
Frame 1	0	0	0	3	3	3	4	4	4	4	4	4
Hit/Miss	M	M	M	M	M	M	M	H	H	M	M	H

Number of Page Faults = 9

For Frame Size = 4

String	0	1	2	3	0	1	4	0	1	2	3	4
Frame 4				3	3	3	3	3	3	2	2	2
Frame 3			2	2	2	2	2	2	1	1	1	1
Frame 2		1	1	1	1	1	1	0	0	0	0	4
Frame 1	0	0	0	0	0	0	4	4	4	4	3	3
Hit/Miss	M	M	M	M	H	H	M	M	M	M	M	M

Number of Page Faults = 10

Above Example of FIFO shows that count of page faults increase when the number of frames is increased from 3 to 4.

ADD COMMENT EDIT