CSS 430
Program 4: Paging
Duedate: See the syllabus

1. Purpose

2. Disk Caching

To accelerate the ThreadOS' disk accesses, we want to implement a disk cache that stores frequently-accessed disk blocks onto the memory, so that the second or the later access to the same disk block simply reads the data cached on the memory. When the disk cache is full of cached blocks, it must find out a victim to be replaced with a newly cached block. We will use second-chance algorithm (as described in our textbook.) To maintain data consistency between disk and cached blocks, each cached block must have the following entry information:

Entry items	descriptions
block frame number	contains the disk block number of cached data. It should be set to -1 if this entry does not have valid block information.
reference bit	is set to 1 or true whenever this block is accessed. Reset it to 0 or false by the second-chance algorithm when searching a next victim.
dirty bit	is set to 1 or true whenever this block is written. Reset it to 0 or false when this block is written back to the disk.

The following instructions summarizes how to read, write, cache and replace a block of data:

1. Block-read algorithm
   Scan all the cache entries. (Of course, sequential search is enough.) If the corresponding entry has been found in the cache, read the contents from the cache. Otherwise, find a free block entry in the cache and read the data from the disk to this cache block. If you cannot find out any free cache block, find a victim using the second-chance algroithm. If this victim is dirty, you must first write back its contents to the disk and thereafter read new data from the disk into this cache block. Do not forget to set the reference bit.
2. Block-write algorithm
   Scan all the cache entries. (Again, sequential search is enough.) If the corresponding entry has been found in the cache, write new data to this cache block. Otherwise, find a free block entry in the cache and write the data to this cache block. You do not have to write this data through to the disk device. Mark its cache entry as dirty. If you cannot find out any free cache block, find a victim using the second-chance algorithm. If this victim is dirty, you must first write back its contents to the disk and thereafter write new data into this cache block. Do not forget to set the reference bit.
3. Block-replacement algorithm
   Follow the second-chance algorithm described on your texbook page 318.

3. Statement of Work

Part 1: Implementation

Design a disk cache based on second-chance algorithm and code it in Cache.java. Its specification is:

methods	descriptions
Cache( int blockSize, int cacheBlocks )	The constructor: allocates a cacheBlocks number of cache blocks, each containing blockSize-byte data, on memory
boolean read( int blockId, byte buffer[ ] )	reads into the buffer[ ] array the cache block specified by blockId from the disk cache if it is in cache, otherwise reads the corresponding disk block from the disk device. Upon an error, it should return false, otherwise return true.
boolean write( int blockId, byte buffer[ ] )	writes the buffer[ ]array contents to the cache block specified by blockId from the disk cache if it is in cache, otherwise finds a free cache block and writes the buffer [ ] contents on it. No write through. Upon an error, it should return false, otherwise return true.
void sync( ) and void flush( )	writes back all dirty blocks to Disk.java and therefater forces Diskjava to write back all contents to the DISK file. The sync( ) method still maintains clean block copies in Cache.java, while the flush( ) method invalidates all cached blocks. The former method must be called when shutting down ThreadOS. On the other hand, the later method should be called when you keep running a different test case without receiving any caching effects incurred by the previous test.

Kernel_org.java uses your Cache.java in its interrupt( ) method, so that you don't have to modify the kernel.

1. BOOT: instantiates a Cache.java object, (say cache) with 10 cache blocks.
2. CREAD: is called from the SysLib.cread( ) library call. It invokes cache.read( ).
3. CWRITE: is called from the SysLib.cwrite( ) library call. It invokes cache.write( ).
4. CSYNC: is called from the SysLib.csync( ) library call. It invokes cache.sync( ).
5. CFLUSH: is called from the SysLib.flush( ) library call. It invokes cache.flush( ).

Part 2: Performance Test

1. Random accesses:
   read and write many blocks randomly across the disk. Verify the correctness of your disk cache.
2. Localized accesses:
   read and write a small selection of blocks many times to get a high ratio of cache hits.
3. Mixed accesses:
   90% of the total disk operations should be localized accesses and 10% should be random accesses.
4. Adversary accesses:
   generate disk accesses that do not make good use of the disk cache at all.

1. The 1st argument: directs that a test will use the disk cache or not. Test4.java uses SysLib.rawread, SysLib.rawwrite, and SysLib.sync system calls if the argument specifies "no use of disk cache", otherwise SysLib.cread, SysLib.cwrite, and SysLib.csync system calls.
2. The 2nd argument: directs one of the above four performance tests.

4. What to Turn In