34.jpg

緩存算法(淘汰算法)，常見(jiàn)算法有LRU、LFU和FIFO等算法，每種算法各有各的優(yōu)勢(shì)和缺點(diǎn)及適應(yīng)環(huán)境。

PAGE REPLACEMENT POLICIES

• When page fault occurs, the referenced page must be loaded.
• If there is no available frame in memory, then one page is selected for replacement.
• If the selected page has been modified, it must be copied back to disk (swapped out).
• A page replacement algorithm is said to satisfy the inclusion property or is called a stack algorithm if the set of pages in an n-frame memory is always a subset of the pages in a(n + 1) frame memory.

FIFO (First IN, First OUT)

• FIFO implements a queue.
• A FIFO replacement algorithm links with each page the time when that page was added into the memory
• The oldest page is chosen when a page is going to be replaced. We can create a FIFO queue to hold all the pages present in the memory disk. At the head of the queue we replace the page. We insert page at the tail of the queue when a page is added into the memory disk.
• Implementation:

1.Two arrays, page[n] and frame[f_size] (queue), where n is the number of pages and f_size is the size of the frame buffer
2.When there is page fault, it replaces the page in the frame after the previously replaced frame

LRU (Least Recently Used)

• On a page fault, the frame that was least recently used is replaced.
• Implementation:

1.Two arrays, page[n] and frame[f_size] (queue), where n is the number of pages and f_size is the size of the frame buffer
2.Two additional arrays, a[f_size] & b[f_size], where a[] stores the sorted list of pages from most recently used to least recently used and b is the temporary array used to update the list
3.When page fault occurs, it finds the index of the LRU from frame[] based on the last element of a[] and replaces that page
4.Each time a page is referenced, update a[]

LFU (Least Frequently Used)

• The page which has the smallest count is going to be replaced. The reason for this selection is that a mostly used page should have a larger reference count.
• This algorithm suffers from the situation in which a page is used heavily during the staring phase of aprocess, but then is never again. Since it was used heavily, it has a large frequency count and remains in memory even if it is no longer needed.
• Implemention:

1.Two arrays, page[n] and frame[f_size], where n is the number of pages and f_size is the size of the frame buffer
2.An array cnt[f_size] is used to store and keep track of the tally or frequency of usage of the pages
3.When a page fault occurs, it replaces the page with the least frequency of usage
4.If there are more than 1 page that the least frequency of usage, use FIFO logic and replace the page that came first among those least frequently used pages.

ReplacementPolicy.java

package replacementpolicy;

import java.util.*;

class ReplacementPolicy{

    public static void main(String args[]){

        Scanner scan = new Scanner(System.in);
        int frameSize, page=0, choice, n;                   //Declare variables for: frame size, page, choice, and size n
        String inputString;                                 //String variable for the input string and array of Strings for the pages 
        String pages[];                     
        String frame[];                                     //The array for the frames

        do{
            /* MAIN MENU */
            System.out.println( "====================" );
            System.out.println( "\tMenu" );
            System.out.println(  "====================") ;
            System.out.println("\t1.FIFO" );
            System.out.println( "\t2.LRU" );
            System.out.println( "\t3.LFU" );
            System.out.println( "\t4.EXIT" );

            /* Input Choice */
            do {
                System.out.println( "Enter your choice: " );
                while ( !scan.hasNextInt() ) {
                    System.out.println( "Your input is invalid. The choices are 1, 2, 3 and 4 only." );
                    System.out.println("Enter your choice: ");
                    scan.next();
                }
                choice = scan.nextInt();
                if( choice!=1 && choice!=2 && choice!=3 && choice!=4 )
                {
                    System.out.println("Your input is invalid. The choices are 1, 2, 3 and 4 only. Enter Again.");
                }
            }while (choice!=1 && choice!=2 && choice!=3 && choice!=4);

            /* EXIT if input choice is 4*/
            if( choice == 4 ){
                System.out.println( "*****************************" );
                System.out.println( "  You chose to EXIT. Bye! :)" );
                System.out.println( "*****************************" );
                break;
            }
            /* Input Number of Pages */
            do {                                                                        //while input is not a positive integer, asks for input
                System.out.println( "Enter the number of pages: " );
                while ( !scan.hasNextInt() ) {                                          //checks if input is not an integer
                    System.out.println( "Please enter an integer." );                       //displays error message
                    scan.next();
                }
                n = scan.nextInt();                                                     //gets number of pages input
                if( n <= 0 ){
                    System.out.println( "Please enter a positive integer." );   //checks if input is not positive
                }                                                               //displays error message
                                                                                
            } while ( n <= 0 );
            
            pages = new String[n];                                                      //allocates memory for n number of Strings

            /* Input the Reference String separated by  "\\s+" or space */
            System.out.println( "Enter Reference String (must be separated by space): " );
            scan.nextLine();
            do{                                                                         //while length of pages[] array is not equal to n, asks for input
                inputString = scan.nextLine();                                          //gets the input string
                pages = inputString.split( "\\s+" );                                        //splits the string into substrings separated by space and store in the pages[] array
                if( pages.length != n ){                                                    //checks if the number of pages entered is equal to n
                    System.out.println( "The number of pages in your input string is not " + n + ". It is " + pages.length + ". Please enter string again." ); //displays error message
                }
            }while( pages.length != n );

            /* Input the Number of Frames */
            do {                                                                        //while input is not a positive integer, asks for input
                System.out.println( "Enter Number of Frames: " );
                while ( !scan.hasNextInt() ) {                                          //checks if input is not an integer
                    System.out.println( "Please enter an integer." );   //displays error message
                    scan.next();
                }
                frameSize = scan.nextInt();                                             //gets frame buffer size input
                if( frameSize <= 0) {
                    System.out.println( "Please enter a positive integer." );   //checks if input is not positive
                                                                            //displays error message
                }                                               
                            
            }while ( frameSize <= 0 );

            frame = new String[ frameSize ];                                                    //string array frame[] of frameSize
            for( int i = 0; i < frameSize; i++ ){                                                   //initializes frame array with " " which indicates an empty frame array
                frame[i]=" ";
            }

            /* Display the data inputed */
            System.out.println( "The size of input string: " + n );
            System.out.println( "The input string: " + inputString );
            System.out.println( "The Number of Frames: " + frameSize + "\n" );
            System.out.println( "pages array: " );

            for (int i = 0; i < pages.length ; i++) {
                System.out.println("index " + "[" + i + "]: " + pages[i]);  
            }
            System.out.println("\n");

            /* Perform FIFO page replacement */
            if( choice == 1 ){
                System.out.println( "************************" );
                System.out.println( "\tFIFO" );
                System.out.println( "************************" );
                FIFO(n, pages, frame);
            }

            /* Perform LRU page replacement */
            if( choice == 2 ){
                System.out.println( "************************" );
                System.out.println( "\tLRU" );
                System.out.println( "************************" );
                LRU( n, pages, frame, frameSize );
            }

            /* Perform LFU page replacement */
            if( choice == 3 ){
                System.out.println( "************************" );
                System.out.println( "\tLFU" );
                System.out.println( "************************" );
                LFU( n, pages, frame, frameSize );
            }
        }while( choice != 4 );
    }

    /* 1. First In First Out (FIFO) */
    public static void FIFO( int n, String pages[], String frame[] ){                       //arguments accept a size n, an array of the pages and the frame array
        String page;
        boolean flag;                                                                   //flag for page fault
        int pageFaultCounter = 0, page_fault = 0;                                           //frame pageFaultCounter; page fault counter
        /* while there are pages */
        for( int pg=0 ; pg < n ; pg++ ){                                                
            page = pages[ pg ];
            flag = true;                                                                //initially, flag is true because it has not yet found a page hit
            for( int j=0 ; j < frame.length ; j++ ){                                        //checks if page hit
                if( frame[j].equals( page ) ){                                              
                    flag = false;                                                       //if page hit, no fault occurs
                    break;
                }
            }
            if( flag ){                                                                 //If there is page fault,
                frame[ pageFaultCounter ] = page;                                       //replace the page in frame[pageFaultCounter].
                pageFaultCounter++;
                if( pageFaultCounter == frame.length ) 
                {
                    pageFaultCounter=0;                    //set pageFaultCounter back to 0 if pageFaultCounter is equal to length of frame
                }                               
                System.out.print( "frame: " );
                /* display the frame buffer array */
                for( int j=0 ; j < frame.length ; j++ )
                {
                    System.out.print( frame[j]+"   " );
                }
                System.out.print( " --> page fault!" );
                System.out.println();
                page_fault++;                                                               //add 1 to the page faults
            }
            else{
                System.out.print( "frame: " );                                          //If page hit, no replacement
                /* diaplay the frame buffer array */                                            
                for( int j=0 ; j < frame.length ; j++ ){
                    System.out.print(frame[j]+"   " );
                }
                System.out.print( " --> page hit!" );
                System.out.println();
            }
        }
        System.out.println( "\nTotal Page Fault/s:" + page_fault + "\n" );                          //Display Total Page Fault
    }

    /* Least Recently Used (LRU) */
    public static void LRU( int n, String pages[], String frame[], int frameSize ){         //arguments accept a size n, an array of the pages, the frame array and frame size
        String page = " ";                                                              //temp page
        boolean flag;                                                                   //flag for page fault
        int k = 0, page_fault = 0;                                                      //index k (if page fault occurs); page fault counter
        String a[] = new String[ frameSize ];                                               /* 2 temporary arrays to keep track of LRU page, sorted from most recent to least recent */
        String b[] = new String[ frameSize ];                                               /* first element of a[] is most recent and the last element is the LRU */
        for(int i = 0 ; i < frameSize ; i++ ){                                                  //initialize array elements to " "
            a[ i ] = " ";
            b[ i ] = " ";
        }

        for( int pg = 0 ; pg < n ; pg++ ){
            page = pages[ pg ];
            flag = true;                                                                //initially, flag is true because it has not yet found a page hit
            for( int j=0 ; j < frameSize ; j++ ){                                           //checks if page hit
                if( frame[ j ].equals( page ) ){                                                
                    flag = false;                                                       //If page hit, no page fault occurs
                    break;
                }
            }
    
            for( int j=0 ; j < frameSize && flag ; j++ ){                                   //While page fault occurs and find the least recently used page,
                if( frame[ j ].equals(a[ frameSize-1 ] ) ){                                     //If least recently used
                    k = j;                                                              //set index to be replaced
                    break;
                }
            }
    
            if( flag ){                                                                 //If page fault,
                frame[ k ] = page;                                                          //replace frame[k] with the page.   
                System.out.print( "frame: " );
                /* display frame buffer array */
                for(int j = 0 ; j < frameSize ; j++)
                    System.out.print( frame[j] + "  " );
                System.out.println( " --> page fault!" );
                page_fault++;                                                               //add 1 to page fault counter
            }
            else{                                                                       //If page hit, no replacement
                /* display frame buffer array */
                System.out.print( "frame: " );
                for( int j=0 ; j < frameSize ; j++ )
                    System.out.print( frame[ j ]+"  " );
                System.out.println( " --> page hit!" );
            }

            int p = 1;                                                                  //counter
            b[ 0 ] = page;                                                                  //first element of b[] is the page (b is most recent)
            /* update MRU-LRU array */
            for( int j=0 ; j < a.length ; j++ ){                                            //while j < size of frames
                if( !page.equals( a[ j ] ) && p < frameSize ) {                                 //the elements in a[] that are not equal to referenced page or is not the most recently used are copied to b[j] from left
                    b[ p ] = a[ j ];                                                            
                    p++;
                }
            }
            for( int j = 0 ; j < frameSize ; j++ ){                                         //set LRU a[] to the updated LRU b[]
                a[ j ] = b[ j ];
            }
        }
        System.out.println( "\nTotal Page Fault/s: "+ page_fault + "\n" );                          //display total page faults
    }

    /* Least Frequently Used (LFU) */
    public static void LFU( int n, String pages[], String frame[], int frameSize ){         //arguments accept a size n, an array of the pages, the frame array and frame size
        int k = 0, page_fault = 0;                                                          //index k for frequency array; page fault countersummarize
        int leastFrequency;                                                                     //for the least frequency
        String page;                                                                    //tempp page
        int Frequency[] = new int[ frameSize ];                                                 //array to store and keep track of frequencies
        boolean flag = true;                                                                //flag for a page fault
        
        /* Initializes the frequency to 0 */
        for(int i = 0 ; i < frameSize ; i++ ){
            Frequency[ i ] = 0;
        }
        /* while there is page */
        for( int pg = 0 ; pg < n ; pg++ ){
            page = pages[ pg ];                                                         //assign temp page = pages[page]
            flag = true;                                                                    //initially, flag is true because it has not yet found a page hit

            for( int j=0 ; j < frameSize ; j++ ){                                           //checks if page hit
                if( page.equals( frame[ j ] ) ){                                                //If page hit, no page fault occurs
                    flag = false;
                    Frequency[ j ]++;                                                           //add 1 to its frequency
                    break;                                                              //break
                }
            }

            if( flag ){                                                                 //If a page hit occurs,
                leastFrequency = Frequency[ 0 ];
                for( int j = 0 ; j < frameSize ; j++ ){                                     //Look for least number of frequency
                    if( Frequency[ j ] < leastFrequency ){
                        leastFrequency = Frequency[ j ];
                        break;
                    }
                }
                for( int j = 0 ; j < frameSize ; j++ ){                                     //Find the page with the least frequency from the left
                    if( leastFrequency == Frequency[ j ] ){                                                 //The left-most page will be the one to be replaced
                        frame[ j ] = page;
                        k = j;
                        break;
                    }
                }
                Frequency[ k ] = 1;                                                             //set the frequency of new page to 1
                System.out.print( "frame: " );
                /* display frame buffer array */
                for( int j = 0 ; j < frameSize ; j++ ){
                    System.out.print( frame[ j ]+"   " );
                    page_fault++;                                                           //add 1 to page fault counter
                }
                System.out.println( " --> Page fault!" );
            }
            else{                                                                       //If page hit, no replacement
                System.out.print( "frame: " );
                /* display frame buffer array */
                for( int j = 0 ; j < frameSize ; j++ )
                    System.out.print( frame[ j ]+"   " ); 
                System.out.print( " --> Page hit!" );
                System.out.println();
            }
        }       
        System.out.println( "\nTotal Page Fault/s: " + page_fault + "\n" );
    }
}

Running Effect

屏幕快照 2017-12-01 10.37.38.png

屏幕快照 2017-12-01 10.37.50.png

Source Download

Please click the address:Page Replacement Policy (LRU、LFU、FIFO)

Summarize

評(píng)價(jià)一個(gè)緩存算法好壞的標(biāo)準(zhǔn)主要有兩個(gè)，一是命中率要高，二是算法要容易實(shí)現(xiàn)。當(dāng)存在熱點(diǎn)數(shù)據(jù)時(shí)，LRU的效率很好，但偶發(fā)性的、周期性的批量操作會(huì)導(dǎo)致LRU命中率急劇下降，緩存污染情況比較嚴(yán)重。LFU效率要優(yōu)于LRU，且能夠避免周期性或者偶發(fā)性的操作導(dǎo)致緩存命中率下降的問(wèn)題。但LFU需要記錄數(shù)據(jù)的歷史訪問(wèn)記錄，一旦數(shù)據(jù)訪問(wèn)模式改變，LFU需要更長(zhǎng)時(shí)間來(lái)適用新的訪問(wèn)模式，即：LFU存在歷史數(shù)據(jù)影響將來(lái)數(shù)據(jù)的“緩存污染”效用。FIFO雖然實(shí)現(xiàn)很簡(jiǎn)單，但是命中率很低，實(shí)際上也很少使用這種算法。
#個(gè)人主頁(yè)：www.iooy.com