CSS 430 - Program 2: Scheduler

CSS 430
Program 2: Scheduler
Duedate: See the syllabus

1. Purpose

This assignment implements and compares two CPU scheduling algorithms, the round-robin scheduling and the multilevel feedback-queue scheduling. The step-by-step procedure to complete this assignment is: (1) to observe the behavior of ThreadOS Scheduler that uses a Java-based round-robin scheduling algorithm and consider why Java thread priority is not working exactly as your expectation; (2) to redesign ThreadOS Scheduler using Thread.suspend( ) and Thread.resume( ) so that it will rigidly work in a round-robin fashion; (3) to revise your ThreadOS Scheduler as a multilevel feedback-queue scheduler; and (4) to compare those two scheduling algorithm with test thread programs.

2. Java Priority Scheduling

ThreadOS Scheduler.java implements a naive round-robin scheduler based on "Java Thread Scheduling". This scheduler program is the same as you saw in the lecture slide. However, there are no guarantees that a thread with the highest priority preempts the current thread immediately. Therefore, Scheduler.java cannot strictly enforce a round-robin scheduling. Then, how can we enforce a rigid scheduling in our ThreadOS Scheduler? One of the answers is using Thread.suspend( ) and Thread.resume( ) , both of which must be however used with the closest attention, otherwise will cause deadlocks. (This is the reason why their use is deprecated in Java 2 Platform, API documentation.)

3. Suspend and Resume

We use Thread.suspend( ) and Thread.resume( ) only for this assignment, in particular only inside Scheduler.java of our ThreadOS.
Note that, in general, you should avoid using Thread.suspend( ) and Thread.resume( ) in your future thread programs (of course including the assignment 3, 4, and 5.

The suspend( ) method suspends a target thread, whereas the resume( ) method resumes a suspended thread. These methods are not system-dependent. No matter what operating systems you use, a target thread is suspended and resumed immediately. In order to implement a rigid round-robin CPU scheduling, we could modify ThreadOS Scheduler to dequeue a front user thread from its circular list, to resume it with the resume method, and to suspend it with the suspend method after a execution quantum has been expired. However, suspend and resume may cause a deadlock if a suspended thread holds a lock and a runnable thread tries to acquire this lock. To avoid any deadlocks, we must pay our closest attention when using them with synchronized, wait( ) and notify( ) keywords. (They will be taught in the assignment 3 to realize inter-threads synchronization.) When you peek Scheduler.java, you see some synchronized keywords in it. Don't remove them or put additional synchronized keywords, otherwise your Scheduler.java will easily fall into a deadlock.

When you compile Java programs that use deprecated methods such as suspend( ) and resume, you must compile them with a -deprecation option. Although the javac compiler will print out some warning messages, just ignore them in the assignment 2.

   uw1-320-00% javac -deprecation Scheduler.java
   ./Scheduler.java:128: warning: resume() in java.lang.Thread has been deprecated
                       currentThread.resume( );
                                    ^
   ./Scheduler.java:136: warning: suspend() in java.lang.Thread has been deprecated
                       currentThread.suspend( );
                                    ^
   2 warnings
   uw1-320-00%

4. Structure of TheadOS Scheduler

The algorithm of ThreadOS Scheduler, (i.e., Scheduler.java) is based on our lecture slide, while its data structure is extended to manage each user thread using a thread control block (TCB).

Thread Control Block (TCB.java)

See the source code of TCB.java. The current implementation of TCB includes four private data members: (1) a reference to the corresponding thread object (thread), (2) a thread identifier (tid), (3) a parent thread identifier (pid), and (4) the terminated variable to indicate the corresponding thread has been terminated. The TCB constructor simply initializes those private data members with arguments passed to it. The TCB class provides four public methods to retrieve its private data members: getThread( ), getTid( ), getPid( ), and getTerminated( ). In addition, it also has setTerminated( ) that sets terminated true.

Private data members of Scheduler.java

In addition to three private data members from the lecture slide example, we have two more data such as a boolean array - tids[] and a constant - DEFAULT_MAX_THREADS, both related to TCB.

Data members	Descriptions
private Vector queue;	a list of all active threads, (to be specific, TCBs).
private int timeSlice;	a time slice allocated to each user thread execution
private static final int DEFAULT_TIME_SLICE = 1000;	the unit is millisecond. Thus 1000 means 1 second.
private boolean[] tids;	Each array entry indicates that the corresponding thread ID has been used if the entry value is true.
private static final int DEFAULT_MAX_THREADS = 10000;	tids[] has 10000 elements

Methods of Scheduler.java

The following shows all the methods of Scheduler.java.

Methods	Descriptions
private void initTid( int maxThreads )	allocates the tid[] array with a maxThreads number of elements
private int getNewTid( )	finds an tid[] array element whose value is false, and returns its index as a new thread ID.
private boolean returnTid( int tid )	sets the corresponding tid[] element, (i.e., tid[tid]) false. The return value is false if tid[tid] is already false, (i.e., if this tid has not been used), otherwise true.
public int getMaxThreads( )	returns the length of the tid[] array, (i.e., the available number of threads).
public TCB getMyTcb( )	finds the current thread's TCB from the active thread queue and returns it
public Scheduler(int quantum, int maxThreads)	receives two arguments: (1) the time slice allocated to each thread execution and (2) the maximal number of threads to be spawned, (namely the length of tid[]). It creates an active thread queue and initializes the tid[] array
private void schedulerSleep( )	puts the Scheduler to sleep for a given time quantum
public TCB addThread( Thread t )	allocates a new TCB to this thread t and adds the TCB to the active thread queue. This new TCB receives the calling thread's id as its parent id.
public boolean deleteThread( )	finds the current thread's TCB from the active thread queue and marks its TCB as terminated. The actual deletion of a terminated TCB is performed inside the run( ) method, (in order to prevent race conditions).
public void sleepThread( int milliseconds )	puts the calling thread to sleep for a given time quantum.
public void run( )	This is the heart of Scheduler. The difference from the lecture slide includes: (1) retrieving a next available TCB rather than a thread from the active thread list, (2) deleting it if it has been marked as "terminated", and (3) starting the thread if it has not yet been started. Other than this difference, the Scheduler repeats retrieving a next available TCB from the list, raising up the corresponding thread's priority, yielding CPU to this thread with sleep( ), and lowering the thread's priority.

The scheduler itself is started by ThreadOS Kernel. It creates a thread queue that maintains all user threads invoked by the SysLib.exec( String args[] ) system call. Upon receiving this system call, ThreadOS Kernel instantiates a user thread and calls the scheduler's addThread( Thread t ) method. A new TCB is allocated to this thread and enqueued in the scheduler's thread list. The scheduler repeats an infinite while loop in its run method. It picks up a next available TCB from the list. If the thread in this TCB has not yet been activated (but instantiated), the scheduler starts it first. It thereafter raises up the thread's priority to execute for a given time slice.

When a user thread calls SysLib.exit( ) to terminate itself, the Kernel calls the scheduler's deleteThread( ) in order to mark this thread's TCB as terminated. When the scheduler dequeues this TCB from the circular queue and finds out that it has been marked as terminated, it deletes this TCB.

5. Statement of Work

You should use UW1-320's Linux machines for performance evaluations

Part 1: Modifying Scheduler.java with suspend( ) and resume( )

To begin with, run the Test2b thread on our 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 Test2b
    l Test2b
    threadOS: a new thread (thread=Thread[Thread-6,2,main] tid=1 pid=0)
    threadOS: a new thread (thread=Thread[Thread-8,2,main] tid=2 pid=1)
    threadOS: a new thread (thread=Thread[Thread-10,2,main] tid=3 pid=1)
    threadOS: a new thread (thread=Thread[Thread-12,2,main] tid=4 pid=1)
    threadOS: a new thread (thread=Thread[Thread-14,2,main] tid=5 pid=1)
    threadOS: a new thread (thread=Thread[Thread-16,2,main] tid=6 pid=1)
    Thread[a] is running
    ....

Test2b spawns five child threads from TestThread2b, each named Thread[a], Thread[b], Thread[c], Thread[d], and Thread[e]. They prints out "Thread[name] is running" every 0.1 second. If the round-robin schedule is rigidly enforced to give a 1-second time quantum to each thread, you should see each thread printing out the same message about 10 times consecutively:

    Thread[a] is running    
    Thread[a] is running   
    Thread[a] is running
    Thread[a] is running
    Thread[a] is running
    Thread[a] is running
    Thread[a] is running
    Thread[a] is running
    Thread[a] is running
    Thread[a] is running
    Thread[b] is running
    Thread[b] is running
    ....
    ....

However, messages will be mixed up on your display. Now, modify this ThreadOS' Scheduler.java code using suspend( ) and resume( ). The modification will be:

to remove setPriority(2) (line 96) from the addThread( ) method,
to remove setPriority(6) (line 127) from the run( ) method,
to replace current.setPriority(4) (line 143) with current.resume( ),
to remove current.setPriority(4) (line 148) from the run( ) method, and finally
to repalce current.setPriority(2) (line 157) with current.suspend( ).

Compile your Scheduler.java with javac, and thereafter test with Test2b.java if your Scheduler has implemented a rigid round-robin scheduling algorithm. If your Scheduler is working correctly, each TestThread2b thread should print out the same message 10 times consecutively.

Part 2: implementing a multilevel feed back-queue scheduler

Modify your scheduler and implement a multilevel feed back-queue scheduler. The generic algorithm is described in the textbook. Your multilevel feed back-queue scheduler must have the following specification:

It has three queues, numbered from 0 to 2.
A new thread's TCB is always enqueued into queue 0.
Your scheduler first executes all threads in queue 0. The queue 0's time quantum is a half of the one in Part 1's round-robin scheduler, (i.e., timeSlice / 2).
If a thread in the queue 0 does not complete its execution for queue 0's time slice, (i.e., timeSlice / 2 ), the scheduler moves the corresponding TCB to queue 1.
If queue 0 is empty, it will execute threads in queue 1. The queue 1's time quantum is the same as the one in Part 1's round-robin scheduler, (i.e., timeSlice). However, in order to react new threads in queue 0, your scheduler should execute a thread in queue 1 for timeSlice / 2 and then check if queue 0 has new TCBs. If so, it will execute all threads in queue 0 first, and thereafter resume the execution of the same thread in queue 1 for another timeSlice / 2.
If a thread in queue 1 does not complete its execution for queue 1's time quantum, (i.e., timeSlice ), the scheduler then moves the TCB to queue 2.
If both queue 0 and queue 1 is empty, it can execute threads in queue 2. The queue 2's time quantum is a double of the one in Part 1's round-robin scheduler, (i.e., timeSlice * 2). However, in order to react threads with higher priority in queue 0 and 1, your scheduler should execute a thread in queue 2 for timeSlice / 2 and then check if queue 0 and 1 have new TCBs. The rest of the behavior is the same as that for queue 1.
If a thread in queue 2 does not complete its execution for queue 2's time slice, (i.e., timeSlice * 2 ), the scheduler puts it back to the tail of queue 2. (This is different from the textbook example that executes threads in queue 2 with FCFS.)

Again, compile your Scheduler.java and test with Test2b.java to assure that your Scheduler has implemented a multilevel feed back-queue scheduling algorithm.

Part 3: Conducting performance evaluations

Run Test2.java on both your round-robin and the multilevel feed back-queue scheduler.

    $ java boot
    threadOS ver 1.0:
    Type ? for help
    threadOS: a new thread (thread=Thread[Thread-3,2,main] tid=0 pid=-1)
    -->l Test2

Similar to Test2b, Test2 spawns five child threads from TestThread2b, each named Thread[a], Thread[b], Thread[c], Thread[d], and Thread[e]. They prints out nothing but their performance data upon their termination:

thread[b]: response time = 2012 turnaround time = 3111 execution time = 1099
thread[e]: response time = 5035 turnaround time = 5585 execution time = 550
....

The following table shows their CPU burst time:

Thread name	CPU burst (in milliseconds)
Thread[a]	5000
Thread[b]	1000
Thread[c]	3000
Thread[d]	6000
Thread[e]	500

Compare test performance results between Part 1 and Part 2. Discuss how and why your multilevel feed back-queue scheduler has performed better/worse than your round-robin scheduler.

6. What to Turn In

Hardcopy:

Part 1:
- Your Scheduler.java
- Execution Output (Test2.java is enough)
Part 2:
- Your Scheduler.java
- Execution Output (Test2.java is enough)
Report:
- Explain the algorithm of your Part 2's Scheduler.java in some statements, using some flowcharts, or whatever.
- Compare test results between Part 1 and Part 2. Discuss how and why your multilevel feed back-queue scheduler has performed better/worse than your round- robin scheduler. THIS IS IMPORTANT. (Because CSS430 is not a programming course. :-))
- Consider what would happen if you were to implement the queue 2 based on FCFS rather than Round Robin. (Your discussion may focus on what if you run Test2.java in this FCFS-baed queue 2.)

Softcopy:

Part 1:
- Your Scheduler.java
- Please rename its filename Scheduler1.java.
Part 2:
- Your Scheduler.java
- The name is Scheduler.java as it is.

gradeguide2.txt is the grade guide for the assignment 2.

7. Note

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

8. FAQ

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