CSS 430
Program 2: Scheduler
Due date: See the Dropbox

1. Purpose

This assignment will give you an opportunity to develop an intimate understanding of CPU scheduling, by implementing and comparing the performance of two CPU scheduling algorithms: round-robin and a multilevel feedback queue. More specifically, the assignment is to:

  1. Observe the default behavior of ThreadOS Scheduler, which uses a Java-based round-robin scheduling algorithm, and consider why the Java thread priority scheme does not produce results one might expect from a round-robin scheduler
  2. Modify ThreadOS Scheduler using the suspend() and resume() methods defined in the Java Thread class, so that its behavior will more closely correspond to the behavior one would expect to see in a round-robin scheduler
  3. Design and implement a new Scheduler that implements a multilevel feedback queue
  4. Compare those two scheduling algorithm with test thread programs provided with the ThreadOS distribution (/usr/apps/CSS430/ThreadOS):

2. Java Priority Scheduling

The ThreadOS program Scheduler.java implements a naive round-robin scheduler based on standard Java Thread Scheduling. The Scheduler uses three priority levels: New user threads are added to the Scheduler's queue with a priority level of 2. At any given time, there will be at most one user thread with a priority level of 4.

The Scheduler infinitely loops, performing the following steps:

  1. Select the next user thread from the queue to run
  2. Set that user thread's priority to 4
  3. Sleep for a timeslice
  4. Set the selected user thread priority to 2

However, the Java Thread Scheduling specification offers no guarantee that a thread with higher priority will immediately preempt a currently running thread with a lower priority. Therefore, the default Scheduler does not rigorously enforce a round-robin scheduling algorithm. One might consider a variety of ways to better approximate a round-robin scheduler; the approach recommended for this assignment is to use suspend() and resume() methods defined in the Java Thread class.

*** Note that great care must be taken when using these methods, as they can easily lead to deadlock conditions, which is why suspend(), resume() and stop() have all been deprecated ... and why you should generally avoid using these methods outside the current context. We use Thread.suspend() and Thread.resume() only for this assignment and only inside Scheduler.java (and its derivatives).

3. Suspend and Resume

As you might suspect, 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 or resumed immediately. In order to implement a more rigorous round-robin CPU scheduling algorithm, we could modify ThreadOS Scheduler to remove the first user thread from its ready queue, dispatch it (give it some CPU time) via the resume() method, and then interrupt it via the suspend() method after an execution quantum has been expired. However, suspend() and resume() may cause a deadlock if a suspended thread holds a lock (Chapter 6) and a runnable thread tries to acquire this lock.

To avoid any deadlocks, we must use synchronized methods and statements, and/or guarded blocks with wait() and notify() methods. These will be covered in more detail later (Chapter 6), and you will be offered an opportunity to become more intimately familiar with them when you explore inter-thread synchronization in Programming Assignment 3. For now, when you see the use of synchronized methods or statements in Scheduler.java, don't remove them or add additional synchronized methods or statements, lest your Scheduler.java become vulnerable to creating deadlocks. You may, however, modify statements within existing syncrhonized methods or statements.

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

   uw1-320-20% 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-20%

4. Structure of ThreadOS Scheduler

The algorithm of ThreadOS Scheduler is implemented in Scheduler.java. It manages each thread via a thread control block (TCB).

Thread Control Block (TCB.java)

The current implementation of the TCB class includes four private data members:

The TCB constructor simply initializes these private data members with arguments passed to it. The TCB class provides four associated public methods to retrieve its private data members: getThread(), getTid(), getPid(), and getTerminated(). In addition, it also has a setTerminated() method that sets terminated true.

Private data members of Scheduler.java

Data members Descriptions
private Vector queue a list of TCBs for all active threads; this is the ready queue
private int timeSlice a time slice allocated to each user thread execution
private static final int DEFAULT_TIME_SLICE = 1000 the unit is milliseconds (i.e., 1000 = 1 second)
private boolean[] tids Each array entry indicates whether the corresponding thread ID has been used (if so, 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 tids[] array with a maxThreads number of elements
private int getNewTid() finds a tids[] array element whose value is false, and returns its index as a new thread ID
private boolean returnTid( int tid ) sets the corresponding tids[] element, (i.e., tids[tid]) false. The return value is false if tids[tid] is already false, (i.e., if this tid has not been used), otherwise true
public int getMaxThreads() returns the length of the tids[] array, (i.e., the available number of threads)
public TCB getMyTcb() finds the currently running thread's TCB in the active thread queue and returns it
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 as terminated (sets its terminated field to true). 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 user thread to sleep for a specified time period
private void schedulerSleep() puts the Scheduler thread to sleep for a time quantum
public Scheduler( int quantum, int maxThreads ) receives two arguments: quantum is the time slice allocated to each thread execution and maxThreads is the maximum number of threads to be spawned, (namely the length of tids[]). The Scheduler creates an active thread queue and initializes the tids[] array
public void run() This is the heart of Scheduler, which has an infinite loop that
  1. Selects the first available TCB from its queue
  2. Raises that TCB's thread priority to 4
  3. Yields the CPU to that TCB's user thread (by sleeping for a time quantum)
  4. If the user thread finishes (i.e., its TCB's terminated flag is set):
      remove its TCB from the queue and return its TCB's tid
    else (the time quantum has expired):
      lower the thread's priority to 2 and move its TCB to the end of the queue

The ThreadOS Scheduler itself is started by the ThreadOS Kernel. It creates a queue of TCBs for managing all user threads invoked by the SysLib.exec( String args[] ) system call. Upon receiving an exec() system call, ThreadOS Kernel instantiates a new user thread (t) and calls the scheduler's addThread( Thread t ) method. A new TCB is allocated for this thread and enqueued in the Scheduler's queue. The Scheduler executes an infinite while loop as described above.

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 and sees that it has been marked as terminated, it deletes the TCB from its queue.

5. Statement of Work

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

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

To begin with, run the Test2d thread on our ThreadOS: 

[joemcc@uw1-320-18 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 Test2d
l Test2d
threadOS: a new thread (thread=Thread[Thread-5,2,main] tid=1 pid=0)
06383: Thread[a] submitted
threadOS: a new thread (thread=Thread[Thread-7,2,main] tid=2 pid=1)
06388: Thread[b] submitted
threadOS: a new thread (thread=Thread[Thread-9,2,main] tid=3 pid=1)
06388: Thread[c] submitted
threadOS: a new thread (thread=Thread[Thread-11,2,main] tid=4 pid=1)
06389: Thread[d] submitted
threadOS: a new thread (thread=Thread[Thread-13,2,main] tid=5 pid=1)
06389: Thread[e] submitted
threadOS: a new thread (thread=Thread[Thread-15,2,main] tid=6 pid=1)
08378: Thread[a] is running (  100,     0)
08481: Thread[a] is running (  200,     3)
08583: Thread[a] is running (  300,     5)
08685: Thread[a] is running (  400,     7)
08787: Thread[a] is running (  500,     9)
08889: Thread[a] is running (  600,    11)
08991: Thread[a] is running (  700,    13)
09093: Thread[a] is running (  800,    15)
09195: Thread[a] is running (  900,    17)
09297: Thread[a] is running ( 1000,    19)
09380: Thread[b] is running (  100,     0)
09399: Thread[a] is running ( 1100,    21)
09482: Thread[b] is running (  200,     2)
09501: Thread[a] is running ( 1200,    23)
09584: Thread[b] is running (  300,     4)
09603: Thread[a] is running ( 1300,    25)
09686: Thread[b] is running (  400,     6)
09705: Thread[a] is running ( 1400,    27)
09788: Thread[b] is running (  500,     8)
09807: Thread[a] is running ( 1500,    29)
...

Test2d spawns five child threads from TestThread2d, named a, b, c, d and e. A message will be printed when each thread is submitted, showing [the least significant 5 digits of] the timestamp and the thread name. Then for each simulated CPU burst, a message will be printed showing the timestamp, thread name and the CPU execution time and wait time for the thread thus far. When a thread terminates, a message showing the timestamp, the thread name, its response time, total wait time, total execution time and turnaround time will be shown. 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 a "running" message for the thread 10 times consecutively. However, messages from different threads will be mixed up on your display.

Make a backup copy of the distribution scheduler (e.g., cp Scheduler.java Scheduler_0.java).

Now, modify the ThreadOS' Scheduler.java code using suspend() and resume(). There are 5 modifications, all affecting statements calling setpriority(): 3 statements will be removed, 2 will be replaced.

  1. remove setPriority(2) from the addThread() method (line 96)
  2. remove setPriority(6) from the run() method (line 127)
  3. replace current.setPriority(4) with current.resume() in the run() method (line 143)
  4. remove current.setPriority(4) from the run() method (line 148)
  5. replace current.setPriority(2) with current.suspend() in the run method (line 157)

Compile your modified Scheduler.java with javac, and test it with Test2d to confirm that your Scheduler has implemented a more rigorously enforced round-robin scheduling policy. If your Scheduler is working correctly, each TestThread2d thread should print out a message 10 times consecutively.

You can also run Test2c, which also spawns five child threads, named a, b, c, d and e, though it runs TestThread2c rather than TestThread2d for those threads. Unlike Test2d, no submission message will be printed, nor will any intermediate results be shown. When a thread terminates, a message showing the timestamp, the thread name, its response time, total wait time, total execution time and turnaround time will be shown. 

-->l Test2c
l Test2c
threadOS: a new thread (thread=Thread[Thread-17,2,main] tid=7 pid=0)
threadOS: a new thread (thread=Thread[Thread-19,2,main] tid=8 pid=7)
threadOS: a new thread (thread=Thread[Thread-21,2,main] tid=9 pid=7)
threadOS: a new thread (thread=Thread[Thread-23,2,main] tid=10 pid=7)
threadOS: a new thread (thread=Thread[Thread-25,2,main] tid=11 pid=7)
threadOS: a new thread (thread=Thread[Thread-27,2,main] tid=12 pid=7)
84749: Thread[b]: response:  2999; wait:  4018; execution:  1000; turnaround:  4018
87248: Thread[e]: response:  6006; wait:  6517; execution:   500; turnaround:  6517
87797: Thread[c]: response:  4001; wait:  7066; execution:  3000; turnaround:  7066
87834: Thread[a]: response:  1998; wait:  7104; execution:  5000; turnaround:  7104
91948: Thread[d]: response:  5004; wait: 11217; execution:  6000; turnaround: 11217
Test2c finished; total time = 11225
-->

Part 2: implementing a Multilevel Feedback Queue scheduler

Save a copy of the modified scheduler you created for Part 1 (e.g., cp Scheduler.java Scheduler_1.java). Modify your scheduler and implement a multilevel feedback queue scheduler. The generic algorithm is described in the textbook. Your multilevel feedback queue scheduler must meet the following specifications:
  1. It has three queues, numbered from 0 (highest priority) to 2 (lowest priority): Q0, Q1, Q2.
  2. A new thread's TCB is always enqueued into the tail of Q0.
  3. Your scheduler first executes all threads in Q0. Q0's time quantum is half the one in Part 1's round-robin scheduler, (i.e., timeSlice / 2).
  4. If a thread in Q0 does not complete its execution within Q0's time slice, the scheduler moves the thread's corresponding TCB to the tail of Q1.
  5. If Q0 is empty, the scheduler will execute threads in Q1. Q1's time quantum is the same as the one in Part 1's round-robin scheduler, (i.e., timeSlice). However, in order to respond to new threads in the higher priority queue (Q0), your scheduler should execute a thread in Q1 for only timeSlice / 2 and then check if Q0 has any TCBs. If so, it will execute all threads in Q0 first, and thereafter resume the execution of the same thread in Q1 for another timeSlice / 2.
  6. If a thread in Q1 does not complete its execution within Q1's time quantum, (i.e., timeSlice), the scheduler moves the thread's TCB to the tail of queue 2.
  7. If both Q0 and Q1 are empty, the scheduler will execute threads in Q2. Q2's time quantum is twice the one in Part 1's round-robin scheduler, (i.e., timeSlice * 2). However, in order to respond to new threads in the higher priority queues (Q0 and Q1), your scheduler should execute a thread in Q2 for only timeSlice / 2 and then check if Q0 or Q1 has any TCBs. If so, it will execute all threads in Q0 and Q1 (using the priority schemes for each queue outlined above), and thereafter resume the execution of the same thread in Q2 for another timeSlice / 2.
  8. If a thread in Q2 does not complete its execution for Q2's time slice, (i.e., timeSlice * 2), the scheduler will move it to the tail of Q2.it [Note: the use of RR in Q2 is different from the textbook example that schedules threads in Q2 with FCFS.]
Compile your new Scheduler.java and test with Test2d to assure that your Scheduler has implemented a multilevel feedback queue scheduling algorithm. When it is working correctly, make a backup copy (e.g., cp Scheduler.java Scheduler_2.java).

Part 3: Conducting performance evaluations

Assuming you've named your schedulers Scheduler_1.java and Scheduler_2.java, you can activate either scheduler by re-copying it to Scheduler.java and recompiling it. For example:

Run Test2c on both your round-robin and the multilevel feedback queue schedulers.

The following table shows the threads' CPU burst times:
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. Determine whether / how / why your multilevel feedback queue scheduler has performed better/worse than your round-robin scheduler.

6. What to Turn In

  • No hardcopy
  • Submit the following files:
    1. Part 1:
      • Scheduler_1.java (RR using suspend and resume)
      • Scheduler_1.output (output from loading Test2c - not Test2d - with RR)
    2. Part 2:
      • Scheduler_2.java (MFQ using suspend and resume)
      • Scheduler_2.output (output from loading Test2c - not Test2d - with MLFQ)
    3. Part 3: Report (Word or PDF file)
      • What changes did you observe between Test2d on the distribution scheduler and using Scheduler_1.java (RR with suspend and resume)?
      • Describe the changes you made to the modified scheduler (Scheduler_1.java) in order to implement the multi-level feedback queue (Scheduler_2.java).
      • Compare test results between Part 1 and Part 2. Discuss whether / how / why your multi-level feedback queue scheduler has performed better/worse than your round- robin scheduler. THIS IS IMPORTANT. (Because CSS430 is not merely a programming course.)
      • Desribe what would happen if you were to implement Q2 based on FCFS rather than Round Robin. (Your discussion may focus on what would happen if you were to run Test2c in a FCFS-based Q2.)
    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 :-).