Explain the First In First Out (FIFO) algorithm with an example in OS.

Question

Aryan Kumar · Answer

The First In First Out (FIFO) algorithm is also used in page replacement in operating systems where the page that was brought into memory first should be the one that is replaced first.

Let's take an example to understand the FIFO page replacement algorithm. Let's consider a page reference string consisting of 10 pages:

3, 1, 4, 2, 5, 3, 2, 4, 6, 7

The size of the page frame is 3, which means that only 3 pages can be kept in memory at a time. Initially, the page frames are empty.

When the first page, 3, is referenced, it is not in memory, so a page fault (miss) occurs, and the page is brought into the first frame. When the second page, 1, is referenced, it is also not in memory, so it is brought into the second frame. Similarly, when the next few pages are referenced, they are brought into the next available frames until all the frames are filled. The page frame at this point looks like this:

| 3 | 1 | 4 |	//miss

Now, when the 2 page is referenced, it is not in memory, so the first page that was brought in, which is 3, is replaced by 2. The page frame now looks like this:

| 2 | 1 | 4 |	// miss - not already present in frame buffer

Similarly, when the next few pages are referenced, they are brought into the next available frames until all the frames are filled.

| 2 | 5 | 4 |	// miss 
| 2 | 5 | 3 |	// miss
| 2 | 5 | 3 |	// hit - already exist in frame buffer.
| 4 | 5 | 3 |	// miss
| 4 | 6 | 3 |	// miss

When the last page, 7, is referenced, it is not in memory, so the last page that was brought in, which is 3, is replaced by 7. The final page frame looks like this:

| 4 | 6 | 7 |	// miss

The advantage of the FIFO page replacement algorithm is it's simple and easy to implement.

Krishnapriya Rajeev · Answer

The First In First Out (FIFO) algorithm is also used in page replacement in operating systems where the page that was brought into memory first should be the one that is replaced first.

Let's take an example to understand the FIFO page replacement algorithm. Let's consider a page reference string consisting of 10 pages:

3, 1, 4, 2, 5, 3, 2, 4, 6, 7

The size of the page frame is 3, which means that only 3 pages can be kept in memory at a time. Initially, the page frames are empty.

When the first page, 3, is referenced, it is not in memory, so a page fault (miss) occurs, and the page is brought into the first frame. When the second page, 1, is referenced, it is also not in memory, so it is brought into the second frame. Similarly, when the next few pages are referenced, they are brought into the next available frames until all the frames are filled. The page frame at this point looks like this:

| 3 | 1 | 4 |	//miss

Now, when the 2 page is referenced, it is not in memory, so the first page that was brought in, which is 3, is replaced by 2. The page frame now looks like this:

| 2 | 1 | 4 |	// miss - not already present in frame buffer

Similarly, when the next few pages are referenced, they are brought into the next available frames until all the frames are filled.

| 2 | 5 | 4 |	// miss 
| 2 | 5 | 3 |	// miss
| 2 | 5 | 3 |	// hit - already exist in frame buffer.
| 4 | 5 | 3 |	// miss
| 4 | 6 | 3 |	// miss

When the last page, 7, is referenced, it is not in memory, so the last page that was brought in, which is 3, is replaced by 7. The final page frame looks like this:

| 4 | 6 | 7 |	// miss

The advantage of the FIFO page replacement algorithm is it's simple and easy to implement.

Process	Arrival Time
P1	0
P2	1
P3	2
P4	3

Process	Execution Time
P1	5
P2	3
P3	2
P4	4

Process	Execution Order
P1	1
P2	2
P3	3
P4	4

forum

Explain the First In First Out (FIFO) algorithm with an example in OS.

Can you answer this question?

2 Answers