FIFO页面替换算法如何工作？

1. Overview

In an operating system, memory management is a crucial topic. It provides ways to dynamically control and coordinate computer memory. Memory management allows allocating a portion of memory when requested by a program. It also automatically deallocates memory from a program when it is no longer used by a program.

There are various techniques used in memory management. One such method is paging. In paging, page replacement algorithms play an important role and decide which page to keep in the main memory when a new page comes in.

First-in, first-out (FIFO) is the simplest among page replacement algorithms. In this tutorial, we’ll cover FIFO thoroughly.

2. General Idea

Let’s first discuss some background of page replacement algorithms.

Page replacement algorithms come under the paging technique. Paging in the operating system is mainly used for virtual memory management. Paging is a method that allows a computer to retrieve and store data from the secondary memory (e.g. HDD or drum memory) into the main memory (RAM). The data which is extracted from the secondary memory is termed as a page in memory management.

Page replacement algorithms like FIFO are used when there is a new page request, and there is not enough space in the main memory to allocate the new page.

Hence, a page replacement algorithm decides which page it should replace so that it can allocate the memory for the new page. The steps of a page replacement can be summarized in a flowchart:

First-in, first-out (FIFO) algorithm has a simple approach to this problem. We keep track of all the pages by using a queue in the main memory. As soon as a page comes in, we’ll put it in the queue and continue. In this way, the oldest page would always be in the first place of the queue.

Now when a new page comes in and there is no space in the memory, we remove the first page in the queue, which is also the oldest one. It repeats this process until the operating system has page flow in the system.

3. Page Fault

A Page fault is another important concept in page replacement algorithms. A page fault occurs when a page requested by a program is not present in the main memory.

A page fault generates an alert for the operating system. The operating system then retrieves the page from the secondary or virtual memory to the main memory. All the processes run in the background.

Generally, this takes a few milliseconds; still, it has a significant impact on the performance of the operating system. A high number of page faults can slow down the whole system. Although page faults are common in modern days operating systems, a large number of page faults may cause the program to crash or terminate unexpectedly.

The effectiveness of a page replacement algorithm is measured with the number of page fault it generates. The more effective the page replacement algorithm is, the less the number of page faults generated by the algorithm.

4. FIFO Pseudocode

Now that we know the theory behind the FIFO page replacement algorithm, let’s see the pseudocode:

algorithm FindPageFault(P, N, C)
    // INPUT
    //    P = an array of page references (0-based indexing)
    //    N = the number of pages
    //    C = the memory capacity
    // OUTPUT
    //    PF = the total number of page faults
    
    S <- empty set
    QPage <- empty queue
    PF <- 0
    
    for k <- 0 to N - 1:
        if size(S) < C:
            if P[k] not in S:
                S.add(P[k])
                PF <- PF + 1
                QPage.enqueue(P[k])
        else if P[k] not in S:
            val <- QPage.front()
            QPage.dequeue()
            S.remove(val)
            S.add(P[k])
            QPage.enqueue(P[k])
            PF <- PF + 1
    
    return PF

Here denotes the set of current pages in the system. We created a queue and named it as to store the incoming pages in a FIFO manner. Initially, we set the number of page fault to zero.

Now when a new page comes in, we check the capacity of set . Here, we have three cases. The first one is when the set can store the new incoming page, and the page isn’t already present in the set. In this case, we normally store the new page in the set .

The second scenario is when the set can store the new incoming page, but the page is already present in the set. In this case, we’ll mark it as a page hit and won’t increase the count of the variable .

The third case occurs when the set is full. Here we need to perform FIFO to remove pages from the queue.

Finally, when all the pages are either stored or removed from the set , the algorithm returns the total number of page fault and terminates.

5. An Example

In this section, we’ll take an example and run the FIFO page replacement algorithm on it.

We’re taking page reference strings: in our example. Also, we’re considering the capacity of the queue is . Initially, our queue is empty. Now let’s fill the queue with pages and apply a FIFO algorithm:

Here the number on top of each table represents the reference number of new incoming pages. While doing this process, we’re also calculating the number of page faults.

In our example, the total number of page faults that occurred using the FIFO page replacement algorithm is .

6. Advantages and Disadvantages

The main advantage of the FIFO page replacement algorithm is its simplicity. It is easy to understand and implement. It also uses a queue data structure. The number of operations is limited in a queue makes the implementation simple.

Let’s talk about some disadvantages now. When the number of incoming pages is large, it might not provide excellent performance.

When we increase the number of frames or capacity to store pages in the queue, it should give us less number of page faults. Sometimes FIFO may behave abnormally, and it may increase the number of page faults. This behavior of FIFO is called Belady’s anomaly.

In FIFO, the system should keep track of all the frames. Sometimes it results in slow process execution.

7. Conclusion

In this tutorial, we’ve discussed FIFO page replacement in detail.

We’ve discussed the general idea and demonstrated the algorithm with an example.

FIFO page replacement algorithm is definitely not the best page replacement algorithm to use practically. When the number of incoming pages is less, and a user is looking for a simple approach, FIFO might be a reasonable choice.