CSS 430
Program 3: Synchronization
Duedate: See the syllabus

1. Purpose

2. Disk.java

Upon an invocation, Disk.java checks if your current directory includes the file named DISK. If such a file exists, Disk.java reads data from this file into its private array that simulates disk blocks. Otherwise, Disk.java creates a new DISK file in your current directory. Every time it accepts a sync command, Disk.java writes all its internal disk blocks into the DISK file. When ThreadOS Kernel is shut down, it automatically issues a sync command to Disk.java, so that Disk.java will retrieve data from the DISK file upon the next invocation. If you want to start ThreadOS with a clean disk, erase the DISK file from your directory.

All disk commands such as read, write, and sync immediately returns a boolean value indicating if Disk.java has accepted a command or not. Those command takes a certain time to be completed. If a new command is issued before the disk has completed the current command, Disk.java returns false. Therefore, you have to repeat issuing the same read or write command until you receive true.

The read and the write commands do not guarantee that the buffer[] data have been read from and have been written to a specific disk block respectively until the disk command completion status becomes true. Similarly, the sync command does not guarantee that all disk blocks have been written back to the DISK file. This completion status can be checked by two commands such as testAndResetReady( ) and testReady( ) . If the previous command such as read, write, or sync has been already completed, those testing commands return true, otherwise false. The former resets the completion status to false if the status has been true, while the latter simply tests the current status but does not reset it.

The following code shows a sequence of disk read operations you have to follow:

   Disk disk = new Disk( 1000 );

   // a disk read operation:
   while ( disk.read( blockId, buffer ) == false )
      ; // busy wait
   while ( disk.testAndResetReady( ) == false )
      ; // another busy wait
   // now you can access data in buffer

import java.util.*;
import java.lang.reflect.*;
import java.io.*;

public class Kernel
{
    // Interrupt requests
    public final static int INTERRUPT_SOFTWARE = 1;  // System calls
    public final static int INTERRUPT_DISK     = 2;  // Disk interrupts
    public final static int INTERRUPT_IO       = 3;  // Other I/O interrupts

    // System calls
    public final static int BOOT    =  0; // SysLib.boot( )
    ...
    public final static int RAWREAD =  5; // SysLib.rawread(int blk, byte b[])
    public final static int RAWWRITE=  6; // SysLib.rawwrite(int blk, byte b[])
    public final static int SYNC    =  7; // SysLib.sync( )

    // Return values
    public final static int OK = 0;
    public final static int ERROR = -1;

    // System thread references
    private static Scheduler scheduler;
    private static Disk disk;

    // The heart of Kernel
    public static int interrupt( int irq, int cmd, int param, Object args ) {
	TCB myTcb;
	switch( irq ) {
	case INTERRUPT_SOFTWARE: // System calls
	    switch( cmd ) { 
	    case BOOT:
		// instantiate and start a scheduler
		scheduler = new Scheduler( ); 
		scheduler.start( );
		
		// instantiate and start a disk
		disk = new Disk( 100 );
		disk.start( );
		return OK;
            ...
            ...
	    case RAWREAD: // read a block of data from disk
		while ( disk.read( param, ( byte[] )args ) == false )
		    ;     // busy wait
		while ( disk.testAndResetReady( ) == false )
		    ;     // another busy wait
		return OK;
	    case RAWWRITE: // write a block of data to disk
		while ( disk.write( param, ( byte[] )args ) == false )
		    ;     // busy wait
		while ( disk.testAndResetReady( ) == false )
		    ;     // another busy wait
		return OK;
	    case SYNC:     // synchronize disk data to a real file
		while ( disk.sync( ) == false )
		    ;     // busy wait
		while ( disk.testAndResetReady( ) == false )
		    ;     // another busy wait
		return OK;
	    }
	    return ERROR;
	case INTERRUPT_DISK: // Disk interrupts
            ...
	case INTERRUPT_IO:   // other I/O interrupts (not implemented)
            ...
	}
	return OK;
    }
}

3. Wait and Notify

Then, how can we put the current thread into such a queue and resume a next ready thread? In Java, if an object is enclosed with the synchronized keyword, it can behave as a monitor. A thread can put itself to sleep inside such a monitor by calling the wait( ) method, and can wake up another thread sleeping in the monitor by calling notify( ) method. However, Java monitors do not distinguish different conditions. Therefore, in order to wake up a thread waiting for a specific condition, we want to implement a more generalized monitor, named SyncQueue.java:

Private/Public	Methods/Data	Descriptions
private	QueueNode[] queue	maintains an array of QueueNode objects, each representing a different condition and enqueuing all threads that wait for this condition. You have to implement your own QueueNode.java. The size of the queue array should be given through a constructor whose spec is given below.
public	SyncQueue( ), SyncQueue( int condMax )	are constructors that create a queue and allow threads to wait for a default condition number (=10) or a condMax number of condition/event types.
public	enqueueAndSleep( int condition )	allows a calling thread to sleep until a given condition is satisfied.
public	dequeueAndWakeup( int condition )	dequeues and wakes up a thread waiting for a given condition. If there are two or more threads waiting for the same condition, only one thread is dequeued and resumed. The FCFS (first-come-first-service) order does not matter.

With the SyncQueue.java, we can now code more efficient disk operations.

   Disk disk = new Disk( 1000 );
   SyncQueue ioQueue = new SyncQueue( );
   ...
   ...
   // a disk read operation:
   while ( disk.read( blockId, buffer ) == false )
      ioQueue.enqueueAndSleep( 1 ); // relinquish CPU to another ready thread
   while ( disk.testAndResetReady( ) == false )
      ioQueue.enqueueAndSleep( 2 ); // relinquish CPU to another ready thread
   // now you can access data in buffer

    public static int interrupt( int irq, int cmd, int param, Object args ) {
	TCB myTcb;
	switch( irq ) {
	case INTERRUPT_SOFTWARE: // System calls
            ...
            ...
	case INTERRUPT_DISK: // Disk interrupts
	    // wake up the thread waiting for a service completion
	    ioQueue.dequeueAndWakeup( 1 );

	    // wake up the thread waiting for a request acceptance
	    ioQueue.dequeueAndWakeup( 2 );

	    return OK;
        ...
        }
        return OK;
    }    

4. SysLib.join( ) and SysLib.exit( )

Now, consider thread synchronizations in our ThreadOS. We should not allow a user thread to directly access another thread's reference. Otherwise, a user thread can take over thread management such as suspending, resuming and killing other threads. This is ThreadOS' task. Therefore, ThreadOS should not allow a user thread to call the Java join( Thread t ) method. It should follow the same synchronization semantics as Unix/Linux. For such synchronization, ThreadOS provides two system calls such as SysLib.join( ) and SysLib.exit( ) . SysLib.join( ) permits the calling thread to sleep until one of its child threads calls SysLib.exit( ) upon its termination. It returns the ID of the child thread that woke up the calling thread.

We can apply SyncQueue.java for implementing those two system calls. First of all, Kernel.java should instantiate a new SyncQueue object, say waitQueue. This waitQueue will use each thread ID as an independent waiting condition.

   SyncQueue waitQueue = new SyncQueue( scheduler.getMaxThreads( ) );

   case WAIT:
        // get the current thread id (use Scheduler.getMyTcb( ) )
	// let the current thread sleep in waitQueue under the condition
        // = this thread id (= tcb.getTid( ) )
	return OK; // return a child thread id who woke me up
   case EXIT:
        // get the current thread's parent id (= tcb.getPid( ) )
        // search waitQueue for and wakes up the thread under the condition
        // = the current thread's parent id
	return OK;

5. Statement of Work

Part 1: Implementing SysLib.wait( ) and SysLib.exit( )

public class Kernel
{
    private static SyncQueue waitQueue;
    ...

    public static int interrupt( int irq, int cmd, int param, Object args ) {
        TCB myTcb;
        switch( irq ) {
        case INTERRUPT_SOFTWARE: // System calls
            switch( cmd ) {
            case BOOT:
               ...
               waitQueue = new SyncQueue( scheduler.getMaxThreads( ) );
               ...
}

1. Test2.java waits for the termination of all its five child threads, (i.e., the TestThread2.java threads).
2. Shell.java waits for the termination of Test2.java. Shell.java should not display its prompt until Test2.java has completed its execution.
3. Loader.java waits for the termination of Shell.java. Loader.java should not display its prompt ( --> ) until you type exit from the Shell prompt.

Part 2: Implementing Asynchronous Disk I/Os

public class Kernel
{
    private static SyncQueue ioQueue;
    ...

    public static int interrupt( int irq, int cmd, int param, Object args ) {
        TCB myTcb;
        switch( irq ) {
        case INTERRUPT_SOFTWARE: // System calls
            switch( cmd ) {
            case BOOT:
               ...
               ioQueue = new SyncQueue( );
               ...
}

Write a user-level test thread called Test3.java which spawns and waits for the completion of two threads, one conducting only numerical computation and the other reading/writing many blocks randomly across the disk. Those two threads may be written in TestThread3a.java and TestThread3b.java separately or written in TestThread3.java that receives an argument and conducts computation or disk accesses according to the argument. Test3.java should measure the time elapsed from the spawn to the termination of its child threads.

Measure the running time of Test3.java when running it on your ThreadOS. Then, replace Kernel.java with the older version, Kernel.old that does not permit threads to sleep on disk operations. Compile and run this older version to see the running time of Test3.java. Did you see the performance improved by your newer version? Discuss the results in your report.

To verify your own test program, you may run the professor's Test3.class that receives one integer, (i.e., X) and spawns X pairs of computation and disk intensive threads. Since UW1-320 machines include multi-cores, you need to increase X up to 3 or 4 for observing the clear difference between interruptible and busy-wait I/Os.

[css430@uw1-320-20 ThreadOS]$ java Boot
threadOS ver 1.0:
Type ? for help
threadOS: a new thread (thread=Thread[Thread-3,2,main] tid=0 pid=-1)
-->l Test3 3
l Test3 3
...
elapsed time = 85162 msec.
-->q

5. What to Turn In