CSS 430
Program 3: Synchronization

Duedate: See the syllabus


1. Purpose

This assignment exercises an implementation of Java monitors. While the original Java monitors have only an ability of randomly waking up one or all sleeping threads, our Java monitor allows threads to sleep on and wake up from a specific condition. Using this special monitor in SynchQueue.java, we prevent threads from busy waiting on disk read and write operations. To be specific, we will preempt the current thread if it executes a disk read or write operation, put it into the SynchQueue's list, and chose another thread for execution. Thus, we can prevent I/O-bound threads from wasting CPU power. Furthermore, using this SynchQueue.java monitor, we will also implement SysLib.wait( ) and SysLib.exit( ) system calls, with which threads can wait until one of their child threads will be terminated.

2. Disk.java

In our ThreadOS, Disk.java simulates a slow disk device composed of 1000 blocks, each containing 512 bytes. Those blocks are divided into 10 tracks, each of which thus includes 100 blocks. This disk provides the following commands (all of which return a boolean value):
Operations Behaviors
read( int blockId, byte buffer[] ) reads data into buffer[] from the disk block specified by blockId
write( int blockId, byte buffer[] ) writes the buffer[] data to the disk block specified by blockId
sync( ) writes back all logical disk data to the file DISK
testAndResetReady( ) tests the disk status to see if the current disk command such as read, write, or sync has been completed or not, and resets it if the command has been completed.
testReady( ) tests the disk status to see if the current disk command such as read, write, or sync has been completed or not. (The disk status will however not be reset.)

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
All disk operations must be requested as a system call from user threads to ThreadOS Kernel, (i.e., Kernel.java). Those disk operations are thereafter forwarded to the disk device, (i.e., Disk.java). Because of this reason, Kernel.java includes the above code. The following code is a portion of Kernel.java related to disk operations.
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

The above code example has two severe performance problems. First of all, a user thread must repeat requesting a disk service until the disk accepts its request. Second, a user thread needs to repeatedly check if its request has been served. Such spin loops simply cause the user thread to waste the CPU resource until either relinquishing CPU upon a context switch or receiving a response from the disk. That is the main reason why all threads waiting for a disk service should be enqueued into an I/O queue.

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
In the above example, the condition 1 stands for that a thread is waiting for the disk to accept a request, whereas the condition 2 stands for that a thread is waiting for the disk to complete a service, (i.e., waiting for the buffer[] array to be read or written). The remaining problem is who will wake up a thread sleeping on this ioQueue under the condition 1 or 2. It is ThreadOS Kernel that has received an interrupt from the disk device. The following code shows a portion of Kernel.java to wake up a sleeping thread:
    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( )

In Java, you can use the join( Thread t ) method to have the calling thread wait for the termination of the thread pointed to by the argument t. However, if an application program forks two or more threads and it simply wants to wait for all of them to complete, waiting for a particular thread is not a good solution. In Unix/Linux, the wait( ) system call is based on this idea. It does not receive any arguments, (thus no PID to wait on), but simply waits for one of the child processes and returns a PID that has woken up the calling process.

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( ) );
When SysLib.join( ) is invoked, it interrupts Kernel.java with an interrupt request type = Kernel.WAIT. Then, Kernel.java puts the current thread to sleep in waitQueue under the condition = this thread's ID. When SysLib.exit( ) is invoked, it interrupts Kernel.java with an interrupt request type = Kernel.EXIT. Then, Kernel.java searches waitQueue for and wakes up the thread waiting under the condition = the current thread's parent ID.
   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;
One more feature of SysLib.join( ) is to return to the calling thread the ID of the child thread that has woken it up. For this purpose, we need to redefine SyncQueue's enqueueAndSleep( ) and dequeueAndWakeup( ) as follows:
Private/Public Methods/Data Descriptions
public enqueueAndSleep( int condition ) enqueues the calling thread into the queue and sleeps it until a given condition is satisfied. It returns the ID of a child thread that has woken the calling thread.
public dequeueAndWakeup( int condition ), dequeueAndWakeup( int condition, int tid ) 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. This function can receive the calling thread's ID, (tid) as the 2nd argument. This tid will be passed to the thread that has been woken up from enqueueAndSleep. If no 2nd argument is given, you may regard tid as 0.

5. Statement of Work

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

Design and code SyncQueue.java as the above specification. Modify the code of the WAIT and the EXIT case in Kernel.java using SyncQueue.java, so that threads can wait for one of their child threads to be terminated. Note that SyncQueue.java should be instantiated as waitQueue upon a boot, (i.e., in the BOOT case).
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( ) );
               ...
}
Compile your SyncQueue.java and Kernel.java, and thereafter run Test2.java from the Shell.class to confirm:
  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.
Use the ThreadOS-original Shell.class, in particular if you didn't get a perfect grade in hw1.

Part 2: Implementing Asynchronous Disk I/Os

Before going onto Part 2, save your Kernel.java as Kernel.old. Thereafter, modify Kernel.java to use SyncQueue.java in the three case statements: RAWREAD, RAWWRITE, and SYNC, so that disk accesses will no longer cause spin loops. Note that SyncQueue.java should be instantiated as ioQueue upon a boot, (i.e., in the BOOT case).
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 X pairs of threads (where X = 1 ~ 4), one conducting only numerical computation and the other reading/writing many blocks randomly across the disk. Those two types of 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

  • Hardcopy:
    1. Part 1:
      • Kernel.old (which you have modified for Part 1)
      • SyncQueue.java
      • Any other java programs you coded necessary to implement SyncQueue.java (QueueNode.java or whatever you named)
      • Result when running Test2.class from Shell.clas
      • Specifications and descriptions about your java programs
    2. Part 2:
      • Kernel.java (which you have modified for Part 2)
      • Test3.java
      • TestThread3a.java and TestThread3b.java if you have implemented disk reading and writing threads separately rather than all in Test3.java.
      • Performance result when running Test3.java on your Kernel.old (implemented in Part 1)
      • Performance result when running Test3.java on your Kernel.java (implemented in Part 2)
      • Specifications and descriptions about your java program
    3. Report:
      • Discussions about performance results you got for part 2
  • Softcopy:
    1. Part 1:
      • Kernel.old (which you have modified for Part 1)
      • SyncQueue.java
      • Any other java programs you coded necessary to implement SyncQueue.java (QueueNode.java or whatever you named)
    2. Part 2:
      • Kernel.java (which you have modified for Part 2)
      • Test3.java
      • TestThread3a.java and TestThread3b.java if you have implemented disk reading and writing threads separately rather than all in Test3.java.
    gradeguide3.txt is the grade guide for the assignment 3.

    6. Note

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

    7. FAQ

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