CSS 430 for 2016 Summer
Program 4: Paging
Due Date: See the syllabus
This assignment focus on page replacement mechanisms and the performance improvements achieved by implementing a buffer cache that stores frequently-accessed disk blocks in memory. In this assignment you will implement the enhanced second-chance algorithm as described in the OS textbook - Chapter 9.4. You will then measure its performance when running various test cases, and consider the merits and demerits of the implementation.
Caching data from slower external main memory to the faster internal CPU memory takes advantage of both spatial and temporal locality of data reference. User programs are likely to access the same data or the memory locations very close to the data previously accessed. This is called spatial locality and is a key reason why an operating system reads a block or page of data from the disk rather than reading just the few bytes of data the program has accessed. User programs also tend to access the same data again in a very short period of time which in turn means that the least-recently used blocks or pages are unlikely to be used and could be victims for page replacement.
To accelerate disk access in ThreadOS, you will implement a cache that stores frequently-accessed disk blocks into main memory. Therefore, subsquent acess to the same disk block can quickly read the data cached in the memory. However, when the disk cache is full and another block needs to be cached, the OS must select a victim to replace. You will employ the enhanced second-chance algorithm algorithm to choose the block to replace. If the block to be replaced has been updated while in the cache it must be written back to disk; otherwise, it can just be overwritten with the new block. To maintain htis 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 summarize how to read, write, cache and replace a block of data:
If you're using the source code in the Linux lab:
Copy kernel_org.java from the ThreadOS directory to
yours as Kernel.java. Also re-copy all class files from the
ThreadOS directory to your own directory. Note that
kernel_org.java will be available for the program 4 assignment date.
Design a disk cache based on the enhanced second-chance algorithm and implement 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 Disk.java 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.
Example:
$ java Boot
threadOS ver 1.0:
Type ? for help
threadOS: a new thread (thread=Thread[Thread-3,2,main] tid=0 pid=-1)
-->l Test4 [enabled|disabled] [1-5]
ModifyTest4.java so that it displays the average read time
and average write time (the provided Test4.java prints out only the
total time for each test, instead of the average read time and the
average write time).
Compare the performance and discuss the
results you get when you run each of the above four test cases with and
without the disk cache.