17.2. 17.2 Page replacement algorithms

As already mentioned, the memory of the modern computer systems consists of several levels. These levels usually are organised into a seemingly single-level memory, called virtual memory. Users do not have to know this structure with several levels in detail: operating systems manage these levels.

The most popular methods to control this virtual memory are paging and segmentation. Paging divides both memory levels into fixed-sized units, called frames. In this case programs are also divided into parts of the same size as frams have: these parts of the programs (and data) are called pages. Segmentation uses parts of a program with changing size—these parts are called segments.

For the simplicity let us suppose that the memory consists of only two levels: the smaller one with shorter access time is called main memory (or memory for short), and the larger one with larger access time is called backing memory.

At the beginning, the main memory is empty, and there is only one program consisting of parts in the backing memory. Suppose that during the run of the program there are instructions to be executed, and the execution of each instruction there requires an access to a certain page of the program. After processing the reference string, the following problems have to be solved.

  1. Where should we place the segment of the program responsible for executing the next instruction in the main memory (if it is not there)?

  2. When should we place the segments of the program in the main memory?

  3. How should we deallocate space for the segments of the program to be placed into the main memory?

It is the placing algorithms that give the answer to the first question: as far as paging is concerned, the answer is simply anywhere—since the page frames of the main memory are of the same size and access time. During segmentation there are program segments and free memory areas, called holes alternating in the main memory–and it is the segment placing algorithms that gives the answer to the first question.

To the second question the answer is given by the transferring algorithms: in working systems the answer is on demand in most of the cases, which means that a new segment of the program starts to be loaded from the backing memory when it turns out that this certain segment is needed. Another solution would be preloading, but according to the experiences it involves a lot of unnecessary work, so it has not become wide-spread.

It is the replacement algorithms that give the answer to the third question: as far as paging is concerned, these are the page replacement algorithms, which we present in this section. Segment replacement algorithms used by segmentation apply basically the ideas of page replacement algorithms—completed them according to the different sizes of the segments.

Let us suppose that the size of the physical memory is page frames, while that of the backing memory is page frames. Naturally the inequality holds for the parameters. In practice, is usually many times bigger than . At the beginning the main memory is empty, and there is only one program in the backing memory. Suppose that during the run of the program there are instructions to be executed, and to execute the -th instruction the page is necessary, and the result of the execution of the instruction also can be stored in the same page, i. e., we are modelling the execution of the program by reference string . In the following we examine only the case of demand paging, to be more precise, only the page replacement algorithms within it.

If it is important to differentiate reading from writing, we will use writing array besides array . Entry of array is TRUE if we are writing onto page , otherwise FALSE .

Demand paging algorithms fall into two groups; there are static and dynamic algorithms. At the beginning of the running of the program both types fill the page frames of the physical memory with pages, but after that static algorithms keep exactly page frames reserved until the end of the running, while dynamic algorithms allocate at most page frames.

17.2.1. 17.2.1 Static page replacement

The input data of static page replacement algorithms are: the size of the main memory measured in number of the page frames , the size of the program measured in number of of pages , the running time of the program measured in number of instructions and the reference string ; while their output is the number of the page faults. ()

Static algorithms are based on managing the page table. The page table is a matrix with size of , the -th row of which refers to the -th page. The first entry of the row is a logical variable (present/absent bit), the value of which keeps track of whether the page is in the main memory in that certain instant of time: if the -th page is in the main memory, then TRUE and , where shows us that the page is in the j-th page frame of the main memory. If the -th page is not in the main memory, then FALSE and is non-defined. Work variable contains the number of the busy page frames of the main memory.

If the size of the pages is , then the physical address can be calculated from virtual address so that gives us the index of the virtual page frame, and gives us offset referring to virtual address . If the -th page is in the main memory in the given instant of time—which is indicated by TRUE —, then . If, however, the -th page is not in the main memory, then a page fault occurs. In this case we choose one of the page frames of the main memory using the page replacement algorithm, load the -th page into it, refresh the -th row of the page table and then calculate .

The operation of the demand paging algorithms can be described by a Mealy automaton having an initial status. This automaton can be given as , where is the set of the control states, is the initial control state, is the input alphabet, is the output alphabet, is the state transition function and is the output function.

We do not discuss the formalisation of how the automaton stop.

Sequence (or ) is called reference string. The description of the algorithms can be simplified introducing memory states : this state is the set of the pages stored in the main memory of the automat after processing the -th input sign. In the case of static demand paging algorithms . If the new memory status differs from the old one (which means that a new page had to be swapped in), then a page fault has occurred. Consequently, both a swapping of a page into an empty frame and page replacement are called page fault.

In case of page replacement algorithms—according to Denning's proposition—instead of and we use the state transition function . Since for the page replacement algorithms and , holds, these two items can be omitted from the definition, so page replacement algorithm can be described by the triple .

Our first example is one of the simplest page replacement algorithms, the FIFO (First In First Out), which replaces the pages in the order of their loading in. Its definition is the following: and

where and .

Running of the programs is carried out by the following - Run algorithm. In this section the in the name of the algorithms has to be replaced by the name of the page replacement algorithm to be applied (FIFO, LRU OPT, LFU or NRU). In the pseudocodes it is supposed that the called procedures know the values of the variable used in the calling procedure, and the calling procedure accesses to the new values.

-Run( )

  1     2     3  
                        FOR
                      
                      
                     
                        TO
                      
                           
                      Preparing the .   4    
                        DO
                      
                     
                     
                        FALSE
                        5  
                        *-Prepare(
                        
                        )
                        6  
                        FOR
                      
                      
                     
                        TO
                      
                           
                      Run of the program.   7    
                        DO
                      
                     
                        *-Executes(
                        
                        )
                        8  
                        RETURN
                      
                     
                  

The following implementation of the algorithm keeps track of the order of loading in the pages by queue . The preparing algorithm has to create the empty queue, i. e., to execute the instruction .

In the following pseudocode is the index of the page to be replaced, and is the index of the page of the main memory into which the new page is going to be swapped in.

FIFO-Executes( )

  1  
                        IF
                      
                     
                     
                        TRUE
                           
                      The next page is in.   2    
                        THEN
                      
                     
                        NIL
                        3  
                        IF
                      
                     
                     
                        FALSE
                           
                      The next page is out.   4    
                        THEN
                      
                        5       
                        IF
                      
                           
                      Main memory is not full.   6          
                        THEN
                      
                     
                        Inqueue(
                        
                        )
                        7                8                9       
                        IF
                      
                            
                      Main memory is full.  10          
                        THEN
                      
                     
                     
                        Enqueue(
                        
                        )
                       11             
                     
                        FALSE
                       12               13       
                        Write(
                        
                        )
                       14       
                        Read(
                        
                        )
                           
                      Reading.  15       
                     
                        TRUE
                           
                      Updating of the data.  16        
                  

Procedure writing writes the page chosen to be swapped out into the backing memory: its first parameter answers the question where from (from which page frame of the memory) and its second parameter answers where to (to which page frame of the backing memory). Procedure Reading reads the page needed to execute the next instruction from the backing memory into the appropriate page frame of the physical memory: its first parameter is where from (from which page frame of the backing memory) and its second parameter is where to (to which page frame of the memory). When giving the parameters of both the procedures we use the fact that the page frames are of the same size, therefore, the initial address of the -th page frame is -times the page size in both memories. Most of the page replacement algorithms do not need to know the other entries of reference string to process reference , so when calculating space requirement we do not have to take the space requirement of the series into consideration. An exception for this is algorithm OPT for example. The space requirement of the FIFO-RUN algorithm is determined by the size of the page frame - this space requirement is . The running time of the FIFO-RUN algorithm is de-termined by the loop. Since the procedure called in rows 6 and 7 performs only a constant number of steps (provided that queue-handling operations can be performed in , the run-ning time of the FIFO-RUN algorithm is . Note that some of the pages do not change while being in the memory, so if we assign a modified bit to the pages in the memory, then we can spare the writing in row 12 in some of the cases.

Our next example is one of the most popular page replacement algorithms, the LRU (Least Recently Used), which replaces the page used least recently. Its definition is the following: and

where , and if , then .

The next implementation of LRU does not need any preparations. We keep a record of the time of the last usage of the certain pages in array , and when there is a replacement needed, the least recently used page can be found with linear search.

LRU-Executes( )

  1  
                        IF
                      
                     
                     
                        TRUE
                           
                      The next page is in.   2    
                        THEN
                      
                        3  
                        IF
                      
                     
                     
                        FALSE
                           
                      The next page is not in.   4    
                        THEN
                      
                        5       
                        IF
                      
                           
                      The physical memory is not full.   6          
                        THEN
                      
                        7                8       
                        IF
                      
                           
                      The physical memory is full.   9          
                        THEN
                      
                       10             
                        FOR
                      
                      
                     
                        TO
                      
                       11                
                        DO
                      
                     
                        IF
                      
                     
                     
                        TRUE
                      and                           12                   
                        THEN
                      
                       13             
                     
                        FALSE
                       14               15             
                        Write(
                        
                        )
                       16       
                        Read(
                        
                        )
                           
                      Reading.  17       
                     
                        TRUE
                           
                      Updating.  18         19        
                  

If we consider the values of both n and p as variables, then due to the linear search in rows 10–11, the running time of the LRU-RUN algorithm is .

The following algorithm is optimal in the sense that with the given conditions (fixed and ) it causes a minimal number of page faults. This algorithm chooses the page from the ones in the memory, which is going to be used at the latest (if there are several page that are not needed any more, then we choose the one at the lowest memory address from them) to be replaced. This algorithm does not need any preparations either.

OPT-Executes( )

  1  
                        IF
                      
                     
                     
                        TRUE
                           
                      The next page is in.   2    
                        THEN
                      
                     
                        NIL
                        3  
                        IF
                      
                     
                     
                        FALSE
                           
                      The next page is not in.   4    
                        THEN
                      
                        5       
                        IF
                      
                            
                      The main memory is not full.   6          
                        THEN
                      
                        7                8       
                        IF
                      
                           
                      The main memory is full.   9          
                        THEN
                      
                     
                        OPT-Swap-Out(
                        
                        )
                       10             
                     
                        FALSE
                       11               12             
                        Write(
                        
                        )
                       13       
                        Read(
                        
                        )
                           
                      Reading.  14       
                     
                        TRUE
                           
                      Updating.  15        
                  

Procedure OPT-Swap-Out determines the index of the page to be replaced.

OPT-Swap-Out( )

  1        
                      Preparation.   2  
                        FOR
                      
                      
                     
                        TO
                      
                        3    
                        DO
                      
                     
                     
                        FALSE
                        4        
                      Determining the protection of the page frames.   5  
                        WHILE
                      
                      and 
                     
                        TRUE
                      and 
                     
                        FALSE
                      and             6    
                        DO
                      
                        7       
                     
                        TRUE
                        8          9        
                      Finding the frame containing the page to be replaced.  10    11  
                        WHILE
                      
                     
                     
                        TRUE
                       12    
                        DO
                      
                       13    14  
                        RETURN
                      
                      
                  

Information about pages in the main memory is stored in : TRUE means that the page stored in the -th frame is protected from being replaced due to its going to be used soon. Variable protected keeps track of how many protected pages we know about. If we either find protected pages or reach the end of , then we will choose the unprotected page at the lowest memory address for the page to be replaced.

Since the OPT algorithm needs to know the entire array , its space requirement is . Since in rows 5–8 of the OPT-Swap-Out algorithm at most the remaining part of has to be looked through, the running time of the OPT-Swap-Out algorithm is . The following LFU (Least Frequently Used) algorithm chooses the least frequently used page to be replaced. So that the page replacement would be obvious we suppose that in the case of equal frequencies we replace the page at the lowest address of the physical memory. We keep a record of how many times each page has been referenced since it was loaded into the physical memory with the help of array frequency[1..n - 1]. This algorithm does not need any preparations either.

LFU-Executes( )

  1  
                        IF
                      
                     
                     
                        TRUE
                           
                      The next page is in.   2    
                        THEN
                      
                        3  
                        IF
                      
                     
                     
                        FALSE
                           
                      The next page is not in.   4    
                        THEN
                      
                        5       
                        IF
                      
                           
                      The main memory is not full.   6          
                        THEN
                      
                        7                8       
                        IF
                      
                           
                      The physical memory is full.   9          
                        THEN
                      
                       10             
                        FOR
                      
                      
                     
                        DOWNTO
                      
                       11                
                        DO
                      
                     
                        IF
                      
                     
                     
                        TRUE
                      and                           12                   
                        THEN
                      
                       13             
                     
                        FALSE
                       14               15             
                        Kiír(
                        
                        )
                       16       
                        Read(
                        
                        )
                           
                      Reading.  17       
                     
                        TRUE
                           
                      Updating.  18         19        
                  

Since the loop body in rows 11–13 of the LFU-Executes algorithm has to be executed at most -times, the running time of the algorithm is . There are certain operating systems in which there are two status bits belonging to the pages in the physical memory. The referenced bit is set to TRUE whenever a page is refer-enced (either for reading or writing), while the dirty bit is set to TRUE whenever modifying (i.e. writing) a page. When starting the program both of the status bits of each page is set to FALSE . At stated intervals (e. g. after every -th instruction) the operating system sets the referenced bit of the pages which has not been referenced since the last setting to FALSE . Pages fall into four classes according to the values of their two status bits: class 0 contains the pages not referenced and not modified, class 1 the not referenced but modified, class 2 the referenced, but not modified, and finally, class 3 the referenced and modified ones.

The NRU (Not Recently Used) algorithm chooses a page to be replaced from the nonempty class with the smallest index. So that the algorithm would be deterministic, we suppose that the NRU algorithm stores the elements of each class in a row.

The preparation of this algorithm means to fill arrays referenced and dirty containing the indicator bits with FALSE values, to zero the value of variable performed showing the number of the operations performed since the last zeroing and to create four empty queues.

NRU-Prepares( )

  1  
                        FOR
                      
                      
                     
                        TO
                      
                        2    
                        DO
                      
                     
                     
                        FALSE
                        3       
                     
                        FALSE
                        4     5     6     7   
                  

NRU-Executes( )

  1  
                        IF
                      
                     
                     
                        TRUE
                           
                      The next page is in.   2    
                        THEN
                      
                     
                        IF
                      
                     
                     
                        TRUE
                        3       
                        THEN
                      
                     
                     
                        TRUE
                        4  
                        IF
                      
                     
                     
                        FALSE
                           
                      The next page is not in.   5    
                        THEN
                      
                        6       
                        IF
                      
                           
                      The main memory is not full.   7          
                        THEN
                      
                        8                9             
                     
                        TRUE
                       10             
                        IF
                      
                     
                     
                        TRUE
                       11                
                        THEN
                      
                     
                     
                        TRUE
                       12       
                        IF
                      
                           
                      The main memory is full.  13          
                        THEN
                      
                     
                        NRU-Swap-Out(
                        
                        )
                       14             
                     
                        FALSE
                       15               16             
                        IF
                      
                     
                     
                        TRUE
                       17                
                        THEN
                      
                     
                        Write(
                        
                        )
                       18       
                        Read(
                        
                        )
                           
                      Reading.  19       
                     
                        TRUE
                           
                      Updating.  20         21  
                        IF
                      
                       22    
                        THEN
                      
                     
                        FOR
                      
                      
                     
                        TO
                      
                       23       
                        DO
                      
                     
                        IF
                      
                     
                     
                        FALSE
                       24          
                        THEN
                      
                     
                     
                        FALSE
                      
                  

Choosing the page to be replaced is based on dividing the pages in the physical memory into four queues .

NRU-Swap-Out( )

  1  
                        FOR
                      
                      
                     
                        TO
                      
                           
                      Classifying the pages.   2    
                        DO
                      
                     
                        IF
                      
                     
                     
                        FALSE
                        3       
                        THEN
                      
                     
                        IF
                      
                     
                     
                        FALSE
                        4          
                        THEN
                      
                     
                        Enqueue(
                        
                        )
                        5          
                        ELSE
                      
                     
                        Enqueue(
                        
                        )
                        6       
                        ELSE
                      
                     
                        IF
                      
                     
                     
                        FALSE
                        7          
                        THEN
                      
                     
                        Enqueue(
                        
                        )
                        8                
                        ELSE
                      
                     
                        Enqueue(
                        
                        )
                        9  
                        IF
                      
                           
                      Choosing the page to be replaced.  10    
                        THEN
                      
                     
                     
                        Dequeue(
                        
                        )
                       11    
                        ELSE
                      
                     
                        IF
                      
                       12       
                        THEN
                      
                     
                     
                        Dequeue(
                        
                        )
                       13       
                        ELSE
                      
                     
                        IF
                      
                       14          
                        THEN
                      
                     
                     
                        Dequeue(
                        
                        )
                       15          
                        ELSE
                      
                     
                     
                        Dequeue(
                        
                        )
                       16  
                        RETURN
                      
                      
                  

The space requirement of the RUN-NRU algorithm is and its running time is . The Second-Chance algorithm is a modification of FIFO. Its main point is that if the referenced bit of the page to be replaced is FALSE according to FIFO, then we swap it out. If, however, its referenced bit is TRUE , then we set it to FALSE and put the page from the beginning of the queue to the end of the queue. This is repeated until a page is found at the be-ginning of the queue, the referenced bit of which is FALSE . A more efficient implementation of this idea is the Clock algorithm which stores the in-dices of the pages in a circular list, and uses a hand to point to the next page to be replaced.

The essence of the LIFO (Last In First Out) algorithm is that after filling in the physical memory according to the requirements we always replace the last arrived page, i. e., after the initial period there are pages constantly in the memory—and all the replacements are performed in the page frame with the highest address.

17.2.2. 17.2.2 Dynamic paging

It is typical of most of the computers that there are multiple programs running simultane-ously on them. If there is paged virtual memory on these computers, it can be managed both locally and globally. In the former case each program's demand is dealt with one by one, while in the latter case a program's demand can be satisfied even at other programs' expenses. Static page replacement algorithms using local management have been discussed in the last section. Now we present two dynamic algorithms. The WS ( Working-Set ) algorithm is based on the experience that when a program is run-ning, in relatively short time there are only few of its pages needed. These pages form the working set belonging to the given time interval. This working set can be defined for example as the set of the pages needed for the last instructions. The operation of the algorithm can be illustrated as pushing a “window” with length of along reference array , and keeping the pages seen through this window in the memory.

WS( )

  1  
                        IF
                      
                     
                     
                        FALSE
                           
                      The next page is not in.   2    
                        THEN
                      
                     
                        WS-swap-out(
                        
                        )
                        3       
                        Write(
                        
                        )
                        4       
                     
                        TRUE
                        5          6  
                        IF
                      
                           
                      Does  in the memory?   7    
                        THEN
                      
                        8       
                        WHILE
                      
                      and    9          
                        DO
                      
                       10       
                        IF
                      
                       11          
                        THEN
                      
                     
                     
                        FALSE
                      
                  

When discussing the WS algorithm, to make it as simple as possible, we suppose that , therefore, storing the pages seen through the window in the memory is possible even if all the references are different (in practice, is usually significantly bigger than due to the many repetitions in the reference string).

The WS-Swap-Oout algorithm can be a static page replacement algorithm, for instance, which chooses the page to be replaced from all the pages in the memory—i. e., globally. If, for example, the FIFO algorithm with running time is used for this purpose, then the running time of the WS algorithm will be , since in the worst case it has to examine the pages in the window belonging to every single instruction.

The PFF (Page Frequency Fault) algorithm uses a parameter as well. This algorithm keeps record of the number of the instructions executed since the last page fault. If this number is smaller when the next page fault occurs than a previously determined value of parameter , then the program will get a new page frame to be able to load the page causing page fault. If, however, the number of instructions executed without any page faults reaches value , then first all the page frames containing pages that have not been used since the last page fault will be taken away from the program, and after that it will be given a page frame for storing the page causing page fault.

PFF( )

  1        
                      Preparation.   2  
                        FOR
                      
                      
                     
                        TO
                      
                        3    
                        DO
                      
                     
                     
                        FALSE
                        4       
                     
                        FALSE
                        5  
                        FOR
                      
                      
                     
                        TO
                      
                           
                      Running.   6    
                        DO
                      
                     
                        IF
                      
                     
                     
                        TRUE
                        7       
                        THEN
                      
                        8       
                        ELSE
                         
                     
                        PFF-Swap-In(
                        
                        )
                        9          
                        Write(
                        
                        )
                       10          
                     
                        TRUE
                       11       
                        FOR
                      
                     
                     
                        TO
                      
                       12          
                        DO
                      
                     
                        IF
                      
                     
                     
                        FALSE
                       13             
                        THEN
                      
                     
                     
                        FALSE
                       14                
                     
                        FALSE
                      
                  

Exercises

17.2-1 Consider the following reference string: . How many page faults will occur when using FIFO, LRU or OPT algorithm on a computer with main memory containing page frames?

17.2-2 Implement the FIFO algorithm using a pointer—instead of queue —pointing to the page frame of the main memory, which is the next one to load a page.

17.2-3 What would be the advantages and disadvantages of the page replacement algorithms' using an page map—besides the page table—the -th row of which indicating whether the -th row of the physical memory is reserved, and also reflecting its content? 17.2-4 Write and analyse the pseudo code pseudocode of Second-Chance, Clock and LIFO algorithms.

17.2-5 Is it possible to decrease the running time of the NFU algorithm (as far as its order of magnitude is concerned) if the pages are not classed only after each page faults, but the queues are maintained continuously?

17.2-6 Another version, NFU', of the NRU algorithm is also known, which uses four sets for classing the pages, and it chooses the page to be replaced from the nonempty set with the smallest index by chance. Write the pseudo code of operations In-Set and From-Set needed for this algorithm, and calculate the space requirement and running time of the NFU' algorithm.

17.2-7 Extend the definition of the page replacement automat so that it would stop after processing the last entry of the finite reference sequence.

Hint. Complete the set of incoming signs with an 'end of the sequence' sign.