Design a cache implementation using linked list data structure. Write a Cache cl

Question

Design a cache implementation using linked list data structure. Write a Cache class having at least the following public methods – constructor, getObject, addObject, removeObject, clearCache and some others. The data to be stored in cache should be generic objects. Also, write a test program to test your cache implementation.

If it is a cache hit, then the cache returns the data item to the application and the data item will be move to the first position in the cache (Most Recently Used MRU scheme). On the other hand, if it is a cache miss, then the application needs to read the data item from disk and then the data item from disk will be added to the first position of the cache. Note that if the cache is full, the last entry (oldest one) in the cache will be removed before a new entry can be added. Similarly, whenever an application writes a data item to disk, the system will perform the same write operation to the cache copy of the data item (if any) and then move it to the first position in cache. Note that the write operation is equivalent to a remove operation followed by an add operation.

One-level Cache: A single-level cache and it works as described above.

Two-level Cache: A 2nd-level cache sits behind the 1st-level cache. Usually, the 2nd-level cache is much bigger than the 1st-level cache. Assume the 2nd-level cache contains all data in the 1st level cache, which is called (multilevel inclusion property).

Two-level cache works as follows:

1) If 1st-level cache hit: Both cache have the hit data item. Move the hit data item to the top on both cache.

2) If 1st-level cache miss and 2nd-level cache hit: The data item is not in 1st-level cache but is in 2nd-level cache. Move the data item to the top of 2nd-level cache and add the item to the top of 1st-level cache.

3) If 1st-level cache miss and 2nd-level cache miss: Retrieve the data item from disk and add the item to the top of both cache.

Hit Ratio: Some terms used to define hit ratio are:

HR: (global) cache hit ratio

HR1: 1st-level cache hit ratio

HR2: 2nd-level cache hit ratio

NH: total number of cache hits

NH1: number of 1st-level cache hits

NH2: number of 2nd-level cache hits

NR: total references to cache

NR1: number of references to 1st-level cache

NR2: number of references to 2nd-level cache (= number of 1st-level cache misses)

• One-level cache: HR = NH/NR

• Two-level cache: HR1 = NH1/NR1

HR2 = NH2/NR2

HR = (NH1+NH2)/NR1

1. Write a Cache class.

2. Write a test program. It’s usage should be

java Test 1 or

java Test 2 <1st-level cache size> <2nd-level cache size>

The cache size(s) and the text file should be input as command line arguments. Your program should create a cache (option 1) or two cache (option 2) with the specified size(s) and read in the input text file word by word. For each word, search the cache(s) to see whether there is a cache hit and update the cache accordingly.

3. Your program should output the cache hit ratio(s) after reading all words from the input text file.

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
struct node *ptr;
}*top,*top1,*temp;
int topelement();
void push(int data);
void pop();
void empty();
void display();
void destroy();
void stack_count();
void create();
int count = 0;
void main()
{
int no, ch, e;
printf(" 1 - Push");
printf(" 2 - Pop");
printf(" 3 - Top");
printf(" 4 - Empty");
printf(" 5 - Exit");
printf(" 6 - Dipslay");
printf(" 7 - Stack Count");
printf(" 8 - Destroy stack");
create();
while (1)
{
printf(" Enter choice : ");
scanf("%d", &ch);

switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
push(no);
break;
case 2:
pop();
break;
case 3:
if (top == NULL)
printf("No elements in stack");
else
{
e = topelement();
printf(" Top element : %d", e);
}
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
stack_count();
break;
case 8:
destroy();
break;
default :
printf(" Wrong choice, Please enter correct choice ");
break;
}
}
}
void create()
{
top = NULL;
}
void stack_count()
{
printf(" No. of elements in stack : %d", count);
}
void push(int data)
{
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->ptr = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp;
}
count++;
}
void display()
{
top1 = top;

if (top1 == NULL)
{
printf("Stack is empty");
return;
}

while (top1 != NULL)
{
printf("%d ", top1->info);
top1 = top1->ptr;
}
}
void pop()
{
top1 = top;

if (top1 == NULL)
{
printf(" Error : Trying to pop from empty stack");
return;
}
else
top1 = top1->ptr;
printf(" Popped value : %d", top->info);
free(top);
top = top1;
count--;
}
int topelement()
{
return(top->info);
}
void empty()
{
if (top == NULL)
printf(" Stack is empty");
else
printf(" Stack is not empty with %d elements", count);
}
void destroy()
{
top1 = top;

while (top1 != NULL)
{
top1 = top->ptr;
free(top);
top = top1;
top1 = top1->ptr;
}
free(top1);
top = NULL;

printf(" All stack elements destroyed");
count = 0;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.