Solved-A cache is a storage in memory — Programming #1 -Solution

Description

Introduction:

This programming assignment asks you to design a cache implementation using linked list data structure. That is, 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.

Description:

A cache is a storage in memory. If a data item has a copy in cache, application can read this data item from cache directly. The usage of cache is as follows. Whenever an application requires a data item, it searches the cache rst. 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 rst position in the cache (we call it the 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 rst 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 rst 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 de ne hit ratio are:

HR: (global) cache hit ratio

HR₁: 1st-level cache hit ratio

HR₂: 2nd-level cache hit ratio

NH: total number of cache hits

NH₁: number of 1st-level cache hits

NH₂: number of 2nd-level cache hits

NR: total references to cache

NR₁: number of references to 1st-level cache

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

One-level cache: HR = ^NH_NR

Two-level cache: HR1 =	NH1	HR2 =	NH2		HR =	NH1+NH2
	NR1			NR2			NR1

What you need to do:

1. Create a directory /cs321/lab1 for this assignment.

2. Write a Cache class.

3. Execute the following command (assuming you are in the directory /cs321/lab1) to make a link to the text le. Don’t copy this le as it is quite large!

ln -s /home/JHyeh/cs321/labs/lab1/files/Encyclopedia.txt

4. Write a test program Test.java. It’s usage should be

java Test 1 <cache size> <input textfile name> or

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

The cache size(s) and the text le should be input as command line arguments. Your program should create a cache (option 1) or two cache (option 2) with the speci ed size(s) and read in the input text le word by word. For each word, search the cache(s) to see whether there is a cache hit and update the cache accordingly. I will use the le Encyclopedia.txt and a small text le small.txt (in the same directory as the Encyclopedia.txt does) to test your program.

5. Your program should output the cache hit ratio(s) after reading all words from the input text le. You can nd the sample outputs, result1k2k, result1k5k and result.small, in the directory

/home/JHyeh/cs321/labs/lab1/files/

Submission:

Submit your program(s) from onyx by copying all of your les to an empty directory (with no subdirectories) and typing the following FROM WITHIN this directory:

submit jhyeh cs321 p1