자바 구현 페이지 교체 알고리즘 (LRU, LFU, FIFO)
캐 시 알고리즘 (도태 알고리즘) 은 흔히 볼 수 있 는 알고리즘 으로 LRU, LFU, FIFO 등 알고리즘 이 있 고 각 알고리즘 은 각각 장점 과 단점 과 적응 환경 이 있 습 니 다.
PAGE REPLACEMENT POLICIES
FIFO (First IN, First OUT)
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)
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)
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 + "
" );
System.out.println( "pages array: " );
for (int i = 0; i < pages.length ; i++) {
System.out.println("index " + "[" + i + "]: " + pages[i]);
}
System.out.println("
");
/* 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( "
Total Page Fault/s:" + page_fault + "
" ); //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( "
Total Page Fault/s: "+ page_fault + "
" ); //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( "
Total Page Fault/s: " + page_fault + "
" );
}
}
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
캐 시 알고리즘 의 좋 고 나 쁨 을 평가 하 는 기준 은 주로 두 가지 가 있 는데 하 나 는 명중률 이 높 아야 하고, 다른 하 나 는 알고리즘 이 쉽게 이 루어 져 야 한다.핫 이 슈 데이터 가 존재 할 때 LRU 의 효율 성 은 좋 지만 우발 적 이 고 주기 적 인 대량 작업 은 LRU 명중률 을 급 격 히 떨 어 뜨리 고 캐 시 오염 상황 이 심각 하 다.LFU 는 LRU 보다 효율 적 이 고 주기 적 이거 나 우발 적 인 조작 으로 캐 시 명중률 이 떨 어 지 는 문 제 를 피 할 수 있다.그러나 LFU 는 데이터 의 과거 기록 을 기록 해 야 한다. 데이터 액세스 모드 가 바 뀌 면 LFU 는 미래 데이터 에 영향 을 미 칠 과거 기록 데이터 의 '캐 시 오염' 효용 을 적용 하 는 데 더 많은 시간 이 필요 하 다.FIFO 는 실현 은 간단 하지만 명중률 이 낮 아 실제로 도 이런 알고리즘 을 거의 사용 하지 않 는 다. \ #개인 홈 페이지: www. iooy. com
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
