CSS 430 - FAQ on Program 4: Paging

CSS 430
FAQ on Program 4: Paging
Instructor: Munehiro Fukuda

Q1: Which version of Kernel.java should I use?

A: Download kernel_org.java or a new version of Kernel.java.

Download Kernel_org.java or a new version of Kernel.java, both of which include a correct implementation of EXEC, EXIT, and WAIT. You can download them from uw1-320 machines.

Q2: Is Cache.class a thread?

A: No, it is an ordinary Java class. Kernel instantiates one Cache.class.

Kernel.java creates an instance of your Cache.java as an ordinary Java object but not a thread.

     cache = new Cache( disk.blockSize, 10 );

It gets to know that the disk block size is 512 bytes and the number of cached blocks is 10. As you see Kernel.java, Kernel calls read, write, sync, and flush methods of cache according to each request.

 
case CREAD: // to be implemented in assignment 4 return
    cache.read( param, ( byte[] )args ) ? OK : ERROR;

Where param is a block number. What your Cache.java has to do is if such a block is cached in Cache.java, it will copy the contents to args upon a read( ) call, and will copy the contents of args to this cached block upon a write( ) call.

Q3: How can I find which blocks are cached in Cache.java?

A: You should maintain an array or a Vector of 10 elements, each including:

   frame field:   a cached block number
                  initialized to -1 (this means this frame is invalid.)
   reference bit: set whenever this block is accessed and reset by
                  a second-chance algorithm
   dirty bit:     set whenever a write request occurs and reset when
                  this block is written back to the disk

Q4: What is the sequence of a cache read?

A: Here is a big hint:

    - When a read( ) is called, first go through the array or the
      Vector of 10 elements, each including a different cache block and
      its block information, (i.e., frame#, reference and dirty bits.)
    - If you find the corresponding block, (i.e., if the read( )'s first
      argument matches the frame # of one of those elements,) simply
      copies this element's data to the 2nd argument. The reference bit
      is set, too. That's it.
    - If you don't find the corresponding block, now you have to find
      out an invalid element whose frame# is -1.
    - If you don't find any invalid elements, then, you have to chose
      a victim according to the 2nd-chance algorithm.
    - If it is a victim and its dirty bit is 1, then, write back this
      contents to the disk using disk.write( ). The dirty bit is reset.
    - Now, you have to read the corresponding disk block from disk into
      this freed element. Then, update this element's frame# with this
      disk block#. The reference bit is set.
    - Finally, copies this contents to the 2nd argument. That's it.

Q5: What is the sequence of the write?

A: Think about it by yourself!

Q6: What is the sequence of sync?

A: Write back all cached block to the disk. Clear a dirty bit. But do not invalidate them.

Q7: What is the sequence of flush?

A: Write back all cached block to the disk. Clear both dirty and reference bit. Invalidate all the cached blocks.

Q8: How should I check if my Cache is working

A; For all of the test, write meaningless data to the disk or the cache and then compare what is on the disk or the cache to what I just wrote.

Q9: How can I generate random accesses?

A: Use the Random class.

It generates a new random number by nextInt( ), which however can be a negative integer. Use Math.abs( ) to get a positive integer and then round it up using "% 512".

Q10: How can I round up using "% 512" or "% 10"?

A: See below:

    import java.util.*;

    Random r = new Random( );
    Math.abs( r.nextInt( ) ) % 512;

Q11: How can I generate localized accesses?

A: You may just access only 10 blocks repeatedly.

Perform the following steps:

1.  Create a byte array of 512 elements and fill it with meaningless data.
    This array acts as a block of data.
2.  Write the block of data created in step 1 to several blockIds that
    are close together.
3.  Read the same blocks that were just written to to see if their
    contents are the same as the byte array created in step1.

Q12: How can I generate mixed accesses?

A: Use the Random class. Round it up using "% 10". If it is 0 to 8, you should go to localized accesses. If it is 9, you should go to random accesses.

Q13: How can I generate adversary accesses?

A: Generate access patterns, each causes a cache miss.

This means that you have to choose a block number which has not been chosen in the last 10 accesses. Also try to think about a very pathetic situation where each access moves a disk head a lot for example from track 0 to track 9. Note that blocks 0 to 99 belong to track 0, blocks 100 to 199 belong to track 1, and so on.

Q14: My adversary accesses ran a bit faster than the random accesses. What's wrong?

A: Your adversary accesses didn't move a disk head frequently.

See the answer to Q13.

Q15: How many time should I call cread( ) and cwrite( ) in total.

A: 200 creads and 200 cwrites for each test may be enough to see differences between cache enabled and disabled.

Q16: Should we track the amount of time each write takes and sum them together? Then do this again for the reads? Or can we just give the total amount of time it took to complete both the reads/writes?

A: What you can do is:

measure the total amount of time elapsed for for 200 writes and for 200 reads, and calculate the average time for a write and for a write by dividing the measured time by 200.

Q17: Why do we need csync?

A: Test4.java should call csync at its very end.

Your disk operation may remain in your Cache.java but not be yet reflected to Disk.java even after you get finished with Test4.java. Test4.java should call csync at its very end.

Q18: Why do we need cflush?

A: Every time you start a new test, you have to flush out cached block.

If you conduct another test before stopping ThreadOS, your Cache may still cache some Disk blocks. This is unfair for the following tests. Thus, every time you start a new test, you have to flush out cached block.

Q19: Should write( ) and read( ) in Cache.java be synchronized?

A: Yes.

Q20: If each method in Cache.java use "synchronized", there appear some drawback.

Using a "synchronized" method, only one thread could be active in the Cache at a time. This would be bad when the Cache has to read from the disk itself, which could take a long time, the running thread would be put to sleep, letting other threads execute, but they wouldn't be able to read or write because the lock would still be held.

A: You're right.

Although this synchronization deteriorate the performance, the effect of cache hits will beat such synchronization drawback. Thus, in total, performance will be improved.

Q21: Should I run Test4.java from the shell?

A: You don't have to. You may run your Test4.java from the loader.

% java Boot
-->l Test4 arg0 arg1

Q22: I'm running into a methodNotFound exception when I run Test4, any ideas?

public class TestThread4 extends Thread
{
    ...
    private byte[]  buffer = new byte[512];

    public void TestThread4(String args[])
    {
       ...

A: The constructor should not return any value.

Your TestThread4 construct should be:

    public TestThread4( ) or
    public TestThread4( String args[] )

Q23: Why cannot my buffer be passed to SysLib.cwrite( )

     byte [] buffer = new byte[512];
     String str;
     str = "Block Number " + block+"\n";
     buffer = str.getBytes();
     SysLib.rawwrite(block,buffer);

A: Your buffer[] has been corrupted before passed to SysLib.write ( ).

Be reminded that a Java assignment only substitutes the left-hand-side variable with a pointer to the right-hand-side variable. In the above example, buffer was originally assigned a 512-byte data but was substituted with a pointer to the str variable whose size is much less than 512 bytes.