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

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

A: If you're usin the copy of ThreadOS in the Linux lab, then download kernel_org.java or a new version of Kernel.java.

Q2: Is Cache.class a thread?

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

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

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

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.

Q4.1: What is the difference between SysLib.rawwrite() and the disk.write() that was mentioned in the previous question?

A:

That's a good question. Let's instead approach this the way we might if we had to do this work professionally and yet the original author was unavailable (on vacation, left the company, etc, etc).

What source code can you dig through in order to try and figure out how they differ / how they're similar?  Can you figure out what each one does in order to compare them?   Do you need to fully understand each one? (And if you don't, how can you figure out what the differences are?

As a hint - there's a copy of various .Java files for ThreadOS in the Linux Lab.  Grab that, and then start digging through there to see what you can find.

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.

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.

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.

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.

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:

Q17: Why do we need csync?

A: 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.

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.

A: You're right.

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.

    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 ( ).