I am trying to teach myself LRU algorithm using this youtube video. In the below example (taken from here) why is 0 replaced by 3. Shouldn't that be 4 replaced by 3 as 4 is the least used ?
Asked
Active
Viewed 8,358 times
4 Answers
5
LRU stands for "Least Recently Used". It's based on taking advantage of "temporal locality" of reference, i.e. the thought that the same stuff will be used in a period of time.
In your case, the past three accesses before the current one were 0 - 4 - 2. This means that of the pages in physical memory, 0 was the least recently used, and so it gets paged out.
mfsiega
- 2,852
- 19
- 22
-
Thank you, I understand the concept – Roger That May 19 '12 at 20:24
0
Don't get confused between concept of LRU and Optimal Replacement Algo. In above stack 0 was used before using 4 so when replacement is to be done then 0 is most recently used as compared to 4 and 2 which too are in the stack.
0
Least Recently Used means if we have 3 frames memory and we have pages 4 9 7 5. So 4, 9 and 7 will be added into frames. Now we want to replace page 5. So we will check in memory which page is Least Recently Used in our case page no 4 is LRU so we will replace 4 with 5.
In your case 2 is Ist Recently Used, 4 is 2nd Recently Used and 0 is Least Recently Used so we will replace 0 with 3.
bummi
- 27,123
- 14
- 62
- 101
0
Page replacement algorithm LRU (LEAST RECENTLY USED) Code in C language
#include<stdio.h>
int findLRU(int time[], int n);
int main()
{
int frame_size, no_of_pages, counter = 0, flag1,f, flag2, i, j, m, pos, page_faults = 0;
int frames[10], pages[30], time[10], pri[20][20];
char x[20];
float fault_ratio,hit_ratio;
printf("Enter Total number of pages: ");
scanf("%d", &no_of_pages);
printf("Enter value of page number: ");
printf("\n");
for(i = 0; i < no_of_pages; i++)
{
scanf("%d", &pages[i]);
}
printf("\n");
printf("Enter number of frames: ");
scanf("%d", &frame_size);
for(i=0; i< no_of_pages; i++)
{
x[i]='X';
}
for(i = 0; i < frame_size; ++i)
{
frames[i] = 0;
}
for(i = 0; i < no_of_pages; ++i)
{
flag1 = flag2 = 0;
for(j = 0; j < frame_size; ++j)
{
if(frames[j] == pages[i])
{
counter++;
time[j] = counter;
flag1 = flag2 = 1;
page_faults--;
x[i]='*';
page_faults++;
break;
}
}
if(flag1 == 0)
{
for(j = 0; j < frame_size; ++j)
{
if(frames[j] == 0)
{
counter++;
page_faults++;
frames[j] = pages[i];
time[j] = counter;
flag2 = 1;
break;
}
}
}
if(flag2 == 0)
{
pos = findLRU(time, frame_size);
counter++;
page_faults++;
frames[pos] = pages[i];
time[pos] = counter;
}
for(j = 0; j < frame_size; j++)
{
pri[j][i]=frames[j];
}
}
printf("\n");
for(i = 0 ; i <no_of_pages*5+2*frame_size+1; i ++)
{
printf("-");
}
printf("\n| |");
for(i=1;i<=(no_of_pages*4)/2;i++)
{
printf(" ");
}
printf("Pages");
for(i=(no_of_pages*4)/2;i<=(no_of_pages*4)+13;i++)
{
printf(" ");
}
printf("|\n");
printf("|Frames |");
for(i = 0 ; i < no_of_pages*5+2*frame_size - 8; i ++)
{
printf("-");
}
printf("\n|\t|");
for(i=0 ; i < no_of_pages ; i++)
{
printf(" %2d |",pages[i]);
}
printf("\n");
for(i = 0 ; i < no_of_pages*5+2*frame_size+1 ; i ++)
{
printf("-");
}
printf("\n");
for(i=0;i<frame_size;i++)
{
printf("| %3d",i);
printf("\t|");
for(f=0;f<no_of_pages;f++)
{
if(pri[i][f]==0)
{
printf(" - |");
}
else
{
printf(" %2d |",pri[i][f]);
}
}
printf("\n");
}
for(i = 0 ; i < no_of_pages*5+2*frame_size+1; i ++)
{
printf("-");
}
printf("\n| |");
for(i = 0; i< no_of_pages; i++)
{
if(x[i]=='X')
{
printf("\033[0;31m");
printf(" %2c ",x[i]);
printf("\033[0m");
printf("|");
}
else
{
printf("\033[0;32m");
printf(" %2c ",x[i]);
printf("\033[0m");
printf("|");
}
}
printf("\n");
for(i = 0 ; i < no_of_pages*5+2*frame_size+1; i ++)
{
printf("-");
}
printf("\n\n Total Page Faults = Total No of pages - Total Pages hits \n");
printf(" = %d - %d \n",no_of_pages,(no_of_pages-page_faults));
printf(" = %d \n",page_faults);
printf("\n Total Page Hits = Total No of pages - Total Pages Miss \n ");
printf(" = %d - %d \n",no_of_pages,page_faults);
printf(" = %d \n",(no_of_pages-page_faults));
printf("\nTotal Page Fault ratio = Total Page faults / Total pages \n");
printf(" = %d / %d \n",page_faults,no_of_pages);
printf(" = %5.2f \n",((float)page_faults/no_of_pages));
printf("\nTotal Page Hit ratio = Total Page hits / Total pages \n");
printf(" = %d / %d \n",(no_of_pages-page_faults),no_of_pages);
printf(" = %5.2f \n",((float)no_of_pages-page_faults)/no_of_pages);
return 0;
}
int findLRU(int time[], int n)
{
int i, minimum = time[0], pos = 0;
for(i = 1; i < n; ++i)
{
if(time[i] < minimum)
{
minimum = time[i];
pos = i;
}
}
return pos;
}
Rushi PaTel
- 1
- 1