23 Page Replacement Algorithms I

Mary Anitha Rajam

 

26.1  Introduction

 

In this module, we learn what is meant by page replacement and an algorithm used for page replacement. In the previous module we learnt what demand paging is. In demand paging, pages are brought into memory only when the pages are needed. All the pages of a process need not be kept in the main memory at the same time. Only the pages that are in use need to be kept in the main memory. That is, if a process has ‘n’ pages, it is not necessary to allocate ‘n’ page frames for the process in the physical memory.

 

Suppose a process with 10 pages uses only half of the 10 pages, the unused 5 pages need not be brought into the memory. The advantage of this scheme saves I/O. The time required to move the unused pages into the memory is saved. This reduces the space occupied by the process in the physical memory. This means that there is more free space in the physical memory that can be used to accommodate other processes. This increases the degree of multiprogramming (Degree of multiprogramming is the number of processes that can be kept in the physical memory at the same time).

 

26.2  Page Replacement 

 

Suppose there are 50 frames in the physical memory. There are 10 processes and each process has 10 pages. If the entire process is put into the physical memory, only 5 processes (5 x 10 = 50 pages) can be accommodated. If, all the processes have to be brought into the physical memory 100 physical frames are needed. If only 5 frames are allocated for each process, then all the 10 processes can be accommodated in the physical memory. But all the space in the physical memory is occupied now and hence, results in over-allocation.

 

Suppose, suddenly, one process tries to use all its 10 pages. There are only 50 physical pages in the physical memory and all the 50 pages are occupied. The process that wants to use all the pages tries to bring all the pages into the physical memory. Now, page fault occurs for the 5 pages which are to be brought in (The other 5 pages of the process are already in physical memory). While bringing in the pages from the secondary storage device, it is found that there are no free frames in the physical memory.

 

How can this problem be solved? One way is to decrease the degree of multiprogramming. That is, if you try to reduce the number of processes kept in the physical memory, then there will be more free space for the other processes. Suppose two processes are removed, 10 physical frames will be freed and these page frames can be used by the remaining processes.

 

The other way to overcome this problem is page replacement. That is, when a page is brought into the main memory and if there is no free frame, a victim page is chosen from the main memory, moved out to the backing store and the required page is brought into the main memory.

 

26.3  Need For Page Replacement 

 

Figure 26.1 shows an example of over allocation. The logical memory of user 1 and user 2 are shown. User 1 has four pages and user 2 also has four pages. The page tables of user1 and user2 are also shown. Three pages of user1 (pages H, load M and J) and three pages of user2 (A, D and E) are filled in the physical memory. It is seen that all the physical frames are filled. There is no free frame.

 

One page of user 1 (M) and one page of user 2 (B) are not present in the physical memory. M and B are present in the disk. Since the main memory is full, there is no place to bring in pages B and M.

Fig. 26.1 Need for page replacement (Source: [1])

 

Suppose there is a reference for page ‘M’ by user1. The page table is checked. It is found that the page is marked invalid. The OS checks if it is a legal page of the process and if it is present in the disk. Since the page is present in the disk, the OS tries to bring the page into the physical memory but finds that there is no free frame in the physical memory. Therefore, page replacement is needed. That is, some space has to be freed. Some page currently present in the physical memory should be moved out into the disk and the required page has to be brought into that place.

 

26.4 Basic Page Replacement 

 

This section explains what happens when a page replacement is done. The page fault service routine that we learnt in an earlier module is modified to include page replacement. The steps that are involved in the page replacement are given below:

 

1. Find the location of the desired page on disk. (In the example given above, the operating system finds where page M is present in the disk)

2. Find a free frame:

–  If there is a free frame, use it

–  If there is no free frame, use a page replacement  algorithm  to  select  a  victim frame

3. Write the victim page to the disk; change the page and frame tables accordingly (The page table entry corresponding to the victim page should be marked as invalid. The frame table entry corresponding to the frame should be marked as free).

4. Read the desired page (M) into the (newly) free frame

5. Update the page and frame tables (The page table entry corresponding to M is marked as valid and the frame number is added in the page table entry. The frame table is marked as being used and the incoming page is noted).

6. Restart the process.

7. If no frame is free, two page transfers are required (one out and one in). This doubles the page fault service time and increases the effective access time.

 

To reduce moving out and moving in, a modify (dirty) bit is used. After bringing a page into the physical memory, if the page was not modified, the page need not be written back into the physical memory. The modify bit is set only when the page is modified. When a victim page is chosen for moving out, if the modify bit is not set for that page, that page is not written to the disk. The page to be brought inside is brought into the frame where the victim page is present. This reduces the overhead of page transfers since only modified pages are written to disk.

Fig. 26.2 Page replacement (Source: [1])

 

Figure 26.2 shows an example of the page replacement procedure. Page ‘o’ which was present in the main memory is swapped out and the corresponding entry is marked invalid in the page table. Page ‘f’ is brought into the frame of ‘o’ from the disk. Page table entry for ‘f’ is set as valid.

 

To implement demand paging, two problems should be solved:

 

(i)   Frame-allocation algorithm

(ii)  Page replacement algorithm

 

When multiple processes are in main memory, the operating system should decide how many frames should be allocated to each process. Suppose there are 10 processes and there are 50 frames, a decision has to be made as to how many frames should be given to each process. This is called frame allocation.

 

Whenever page replacement is needed, the operating system should decide which page should be selected for replacement. This is done by a page replacement algorithm.

 

There are many page replacement algorithms. In this module we learn one page replacement algorithm called the First In First Out (FIFO) page replacement algorithm. The performance of any page replacement algorithm should be such that the page-fault rate is the lowest. The algorithm is evaluated by running it on a particular string of memory references (reference string) and computing the number of page faults on that string. Suppose the following address sequence is 0122, 0435, 0123, 0511 and the page size is 100 bytes. Then the addresses 0 to 99 are in the first page, 100 to 199 are in the second page and so on. The reference string shows the page numbers corresponding to the addresses. For example, the page number corresponding to the 0122 is 1. Thus the reference string for the address sequence given above is 1,4,1,5.

Fig. 26.3 Number of page faults vs. number of frames (Source: [1])

 

Figure 26.3 shows how the number of page faults generally varies with the number of frames. When the number of frames is increased, it is expected that the number of page faults should decrease.

 

We now look at the working of the FIFO page replacement algorithm.

 

26.5 First-In-First-Out (FIFO) Algorithm 

 

The First-In-First-Out algorithm is the simplest page-replacement algorithm. In this method, the process that was brought into the memory first is chosen for replacement first. With each page the time when it was brought into memory is attached, When a page must be replaced, the oldest page must be selected. This algorithm can be implemented using a FIFO queue to hold all pages in memory. When a page is brought into memory, the page is inserted into the tail of the queue.

Fig. 26.4 Example of FIFO page replacement (Source: [1])

 

Figure 26.4 shows an example of how page replacement is done using the FIFO page replacement algorithm. The reference string 7, 0, 1, …, 1 is shown. There are three free frames in the physical memory. The first reference is to page 7 and 7 is brought into one free frame. The second reference is to page 0. Since there is a free frame, that page is also brought into the physical memory. The next reference is to page 1. Page 1 is also brought into the physical memory. The next reference is to page 2. Page 2 is not present in the physical memory and there is no free frame in the physical memory. Therefore a page that is already present in the main memory is to be chosen for replacement. Of the three pages (7, 0, 1) present in the main memory, page 7 is the one that was brought into the memory first. Therefore, page 7 is moved out to the disk and page 2 is brought into that place.

 

The next reference is to page 0. Page 0 is already present in the main memory. Therefore it is a hit and page 0 is used from the main memory. The next reference is to page 3. Page 3 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 2, 0 and 1, 0 is the page that was brought into the main memory first. Page 0 is moved out and page 3 is moved in.

 

The next reference is to page 0. Page 0 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 2, 3 and 1, 1 is the page that was brought into the main memory first. Page 1 is moved out and page 0 is moved in.

 

The next reference is to page 4. Page 4 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 2, 3 and 0, 2 is the page that was brought into the main memory first. Page 2 is moved out and page 4 is moved in. The next reference is to page 2. Page 2 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 4, 3 and 0, 3 is the page that was brought into the main memory first. Page 3 is moved out and page 2 is moved in.

 

The next reference is to page 3. Page 3 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 4, 2 and 0, 0 is the page that was brought into the main memory first. Page 0 is moved out and page 3 is moved in. The next reference is to page 0. Page 0 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 4, 2 and 3, 4 is the page that was brought into the main memory first. Page 4 is moved out and page 0 is moved in.

 

The next reference is to page 3. Page 3 is present in the main memory and hence, it is a hit. The next reference is to page 2. Page 2 is present in the main memory and hence, it is a hit. In the above two references, since the pages are already present in the main memory, there is no need for page replacement.

 

The next reference is to page 1. Page 1 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 0, 2 and 3, 2 is the page that was brought into the main memory first. Page 2 is moved out and page 1 is moved in. The next reference is to page 2. Page 2 is not present in the main memory and hence, a page in the main memory has to be chosen for replacement. Of 0, 1 and 3, 3 is the page that was brought into the main memory first. Page 3 is moved out and page 2 is moved in. The next reference is to page 0. Page 0 is present in the main memory and hence, it is a hit. The next reference is to page 1. Page 1 is present in the main memory and hence, it is a hit.

 

In this example, there are 15 page faults when the FIFO algorithm is used.

 

The performance of the FIFO algorithm is not good. If a page is a part of an initialization module that was used long ago, but need not be used now, then choosing that page for replacement increases the performance. But if a variable was initialized long ago but is constantly in use, then choosing the page with that variable for replacement does not increase the performance. Even if a constantly used page is moved out, it will only slow down the performance, but does not cause incorrect execution.

 

FIFO replacement algorithm suffers from Belady’s anomaly. This is explained using the example given below. Consider the reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Suppose that there are 3 frames in the physical memory (3 pages can be in memory at a time per process). Figure 26.5 shows the way in which page replacement is done. It is seen that there are 9 page faults.

Fig. 26.5 Example for FIFO page replacement (Reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4,5 and 3 frames)

 

For the same reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, suppose the number of frames is increased to 4 frames (4 pages can be in memory at a time per process). Figure 26.6 shows that there are 10 page faults.

Fig. 26.6 Example for FIFO page replacement (Reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4,5 and 4 frames)

 

Thus, it is seen that the number of page faults increases when the number of frames is increased. Generally, when the number of frames is increased, the number of page faults is expected to decrease. But in FIFO page replacement algorithm, it is possible that the number of page faults will increase with the increase in the number of frames. This is called Belady’s anomaly. Figure 26.7 show how the number of page faults varies with the variation in the number of frames when FIFO replacement is used.

Fig. 26.7 FIFO Illustrating Belady’s Anomaly (Source: [1])

 

26.6 Summary

 

This module explained the need for page replacement. There are a number of page replacement algorithms. In this module, we learnt the First-in-first-out page replacement algorithm. We also saw  that the FIFO page replacement algorithm  suffers from Belady’s anomaly.

 

 

 

References

  1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Sixth Edition, John Wiley & Sons Inc., 2003.
  2. Andrew S. Tanenbaum, Herbert Bos, “Modern Operating Systems”, Fourth Edition, Pearson Education, 2014.
  3. Gary Nutt, “Operating Systems”, Third Edition, Pearson Education, 2009.