CSS 430 - Program 4: Paging

CSS 430
Program 4: Paging
Due date: See the syllabus

1. Purpose

This assignment is designed to help you understand the page replacement mechanism and the way it affects performance by implementing a buffer cache that stores frequently-accessed disk blocks in memory. To be more specific, you will implement a second-chance algorithm for your buffer cache, measure its performance when running various test cases, and consider the merits and demerits of your implementation.

2. Disk Caching

The idea of caching data from slower to faster storage is based on locality of reference User programs tend to access the same data or data near the data previously accessed (e.g., sequentially accessing elements in an array). This is called spatial locality and is the main reason why the operating system reads an entire block of data or a page from the disk rather than repeatedly reading the potentially smaller amounts of data the program has specifically referenced. User programs also tend to access the same data again in a very short period of time which in turn means that the less recently used blocks or pages are less likely to be used again and could be "victims" for replacement.

To accelerate ThreadOS disk accesses, we want to implement a disk cache that stores frequently-accessed disk blocks in memory, so that subsequent accesses to the same disk block can read the data already cached in memory. When the disk cache is full of cached blocks, and a new block is referenced, the OS must select a victim to be replaced with the new block. We will use second-chance algorithm (as described in our textbook)

To maintain data consistency between disk and cached blocks, a page table should be used wherein each entry has the following fields:

Field Descriptions

block frame number the disk block number of cached data. It should be set to -1 if this entry does not have valid block information.

reference bit Set to 1 (or true) whenever this block is accessed; may be reset to 0 (or false) by the second-chance algorithm when searching a next victim.

dirty bit Set to 1 (or true) whenever data is written to this block; reset 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:

Block-read algorithm
Scan all the cache entries (with the small cache we'll be using, sequential search is adequate). If the corresponding entry is found in the cache, read the block contents from the cache. If the corresponding entry is not found, find a free block entry in the cache and read the data from the disk to this cache block. If there is no free cache block, find a victim using the second-chance algorithm. If the victim's dirty bit is set, you must first write back its contents to the disk. Once you have found or created a free cache block, read new data from the disk into this cache block. Do not forget to set the reference bit.
Block-write algorithm
Scan all the cache entries. If the corresponding entry is found in the cache, write new data to this cache block. if the corresponding entry is not found, 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, but should instead mark set its dirty bit. If there is no free cache block, find a victim using the second-chance algorithm. If the victim's dirty bit is set, you must first write back its contents to the disk. read new data from the disk into this cache block. Do not forget to set the reference bit.
Block-replacement algorithm
Follow the second-chance algorithm described in your textbook on page 318.

3. Statement of Work

Part 1: Implementation

As usual, it is best to start with a fresh directory, so you should copy all the *.class files from the ThreadOS distribution directory (/usr/apps/CSS430/ThreadOS) to your directory. Copy Kernel_org.java from the ThreadOS distribution directory as Kernel.java in your directory [this file is only available during this assignment].

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 cacheBlocks number of cache blocks, each containing blockSize bytes of data, in 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 to 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 and thereafter forces Disk 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. The latter method should be called when you start running a different test case to avoid any caching effects lingering from the previous test.

Kernel_org.java is designed to use Cache.java in its interrupt() method, so you will not have to modify the Kernel for this assignment.

The following values of cmd in the Kernel interrupt()'s switch statement are relevant

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

Part 2: Performance Test

Write a user-level test program called Test4.java that conducts disk validity tests and measures the performance. Test4.java should perform the following four test cases:

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

Implement all those test items in Test4.java. This java program should receive the following two arguments and perform the test(s) associated with these arguments:

cacheEnabled determines whether the test will use the disk cache or not:
- true: Use SysLib.cread(), SysLib.cwrite() and SysLib.csync().
- false: Use SysLib.rawread, SysLib.rawwrite and SysLib.sync.
testNumber specifies one of the performance test cases (1-4) described above; an argument of 5 specifies that all 4 tests should be run with whatever value of cacheEnabled is specified in the first argument.

For each test, your Test4.java program should display the average read time and average write time. Compare the performance and consider the results when you run each of the above four test cases with and without the disk cache.

4. What to Turn In

Part 1:
- Cache.java
Part 2:
- Test4.java
- Performance results that must test all 8 combinations of parameters:
  - random accesses with cache disabled
  - random accesses with cache enabled
  - localized accesses with cache disabled
  - localized accesses with cache enabled
  - mixed accesses with cache disabled
  - mixed accesses with cache enabled
  - adversary accesses with cache disabled
  - adversary accesses with cache enabled
Report:
- Specification/design explanation on Cache.java
- Performance consideration on random accesses
- Performance consideration on localized accesses
- Performance consideration on mixed accesses
- Performance consideration on adversary accesses

gradeguide4.txt is the grade guide for the assignment 4.

5. Note

Visit CSS430 Operating Systems Assignments Home Page in order to reassure your working environment and turn-in procedure.

6. FAQ

This website could answer your questions. Please click here before emailing the professor :-).

Field	Descriptions
block frame number	the disk block number of cached data. It should be set to -1 if this entry does not have valid block information.
reference bit	Set to 1 (or true) whenever this block is accessed; may be reset to 0 (or false) by the second-chance algorithm when searching a next victim.
dirty bit	Set to 1 (or true) whenever data is written to this block; reset to 0 (or false) when this block is written back to the disk.

methods	descriptions
`Cache( int blockSize, int cacheBlocks )`	The constructor: allocates `cacheBlocks` number of cache blocks, each containing `blockSize` bytes of data, in 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 to 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` and thereafter forces `Disk` 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. The latter method should be called when you start running a different test case to avoid any caching effects lingering from the previous test.