The least recently used (LRU) cache algorithm exists the element from the cache(when it’s full) that was least recently used. After an element is requested from the cache, it should be added to the cache (if not already there) and considered the most recently used element in the cache.
Initially, the cache is empty. The input to the function lruCountMiss shall consist of an integer max_cache_size, an array pages and its length Len
The function should return an integer for the number of cache misses using the LRU cache algorithm.
Solution
#include<stdio.h>
int lruMissCount(int, int*, int);
int lruMissCount(int np, int *arr, int n){
int pages[10][2],i,j,k,min,flag,pf=0,lru=1;
for(i=0;i<np;i++){
pages[i][0]=arr[i];
pages[i][1]=lru++;
pf++;
}
for(;i<n;i++){
flag=0;
for(j=0;j<np;j++){
if(pages[j][0]==arr[i]){
flag=1;
break;
}
}
if(flag==1){
pages[j][1]=lru++;
}
else{
min=pages[0][1];
k=0;
for(j=0;j<np;j++){
if(min>pages[j][1]){
min=pages[j][1];
k=j;
}
}
pages[k][0]=arr[i];
pages[k][1]=lru++;
pf++;
}
}
return pf;
}
int main() {
int np,arr[50],n,i,pf;
scanf("%d %d",&np,&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
pf = lruMissCount(np,arr,n);
printf("%d",pf);
}
Sample Input1
3 16
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0
Sample Output1
11
Sample Input2
2 9
2 3 1 3 2 1 4 3 2
Sample Output2
8
Test Code
Initially, the cache is empty. The input to the function lruCountMiss shall consist of an integer max_cache_size, an array pages and its length Len
The function should return an integer for the number of cache misses using the LRU cache algorithm.
Solution
#include<stdio.h>
int lruMissCount(int, int*, int);
int lruMissCount(int np, int *arr, int n){
int pages[10][2],i,j,k,min,flag,pf=0,lru=1;
for(i=0;i<np;i++){
pages[i][0]=arr[i];
pages[i][1]=lru++;
pf++;
}
for(;i<n;i++){
flag=0;
for(j=0;j<np;j++){
if(pages[j][0]==arr[i]){
flag=1;
break;
}
}
if(flag==1){
pages[j][1]=lru++;
}
else{
min=pages[0][1];
k=0;
for(j=0;j<np;j++){
if(min>pages[j][1]){
min=pages[j][1];
k=j;
}
}
pages[k][0]=arr[i];
pages[k][1]=lru++;
pf++;
}
}
return pf;
}
int main() {
int np,arr[50],n,i,pf;
scanf("%d %d",&np,&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
pf = lruMissCount(np,arr,n);
printf("%d",pf);
}
Sample Input1
3 16
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0
Sample Output1
11
Sample Input2
2 9
2 3 1 3 2 1 4 3 2
Sample Output2
8
Test Code