Programming Assignment #1 Solution

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:




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



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.



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

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 = NHNR




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


NR2


NR1



What you need to do:




Create a directory /cs321/lab1 for this assignment.



Write a Cache class.



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.




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