CS 354 Lab 3: Thread Scheduling and Sleeping

Goal

Getting Started

This will create a subdirectory called code/ under which the threads/ subdirectory resides.

Before starting to work on this assignment, you should become familiar with the NachOS source code. You can use the Doxygen generated documentation at NachOS documentation to navigate through the code.

In addition, please read the NachOS papers linked on the class web page, especially Thomas Narten's roadmap through NachOS. In addition, make sure you are familiar with at least the C++ features outlined in Tom Anderson's overview.

A word of caution: We have changed the code to implement a preemptive scheduler and add the Sleep functionality (what used to be Sleep() is now Suspend()), so in case of conflict, information in this handout *always* overrides the documentation.

Finally, you will find Chapters 4 to 6 (especially chapter 6) of your textbook (by Silberschatz) very useful in understanding scheduling mechanisms.

Assignment

Part 1

The function timerIntH in file scheduler.ccis a good place to insert the code that checks if threads need to be awakened. When implementing the sleep list used in the Sleep(seconds) function, you must create what is called "a delta list" for efficiency. A delta list is very similar to any sorted list, except that when inserting elements, you subtract the time of the previous elements from the element being inserted (i.e., each key is relative to the previous key).

To make this clear, consider the following example. Insert into List(4 7 8 2 7). ShowList will give (2 2 3 0 1), which actually corresponds to absolute values of (2 4 7 7 8). With a delta list, only the first element needs to be decremented. When the first element reaches zero, it (and the next element(s) if they are zero) can be removed and placed on the ready queue. The header file list.h has a skeleton of the delta list class provided for you. Any other changes are up to you.

Part 2

The first scheduling policy you must implement is a "lottery scheduler." Under this policy, each thread is assigned a number of lottery tickets at creation time. The scheduler then randomly draws a "winning lottery ticket." The thread which has this ticket is scheduled to run for the time quantum.

Each time a thread receives its full quantum, its number of tickets decreases by one. For each time quantum it is in the ready queue, its number of tickets increases by one. However, the number of tickets held by any thread should never fall below 1, and should never exceed the original number of tickets allocated to it. The quantum for all the threads is one, meaning that after each timer tick, a thread gets preempted. (A quantum of x means that x ticks occur before the thread is preempted.) Unless specified by the Fork() call, a thread should have exactly one ticket.

To randomly draw a ticket from the threads in the ready queue, the scheduler can use the following approach: Let each ready thread j have Tj tickets, and the current thread C have Tc tickets. The total number of tickets allocated is Tc + T1 + T2 + ... + Tk = n, where k is number of threads in the ready list. Now generate a random number M in the range [0, n) (use random() % n). The current thread continues its execution if M < Tc, else the thread selected for execution is any Ti, for which Tc+T1+...+T(i-1) <= M < Tc+T1 + .. + Ti holds. The threads Ti can be simply selected according to order in the ready list.

The second scheduling policy requires Multiple Queues. Here, the scheduler selects the thread with the highest priority (i.e., from the first queue, then the second, .. etc) to run, and performs round-robin among threads in the same queue.

All threads are started with the highest priority level. A thread is demoted to the next highest level at the end of its quantum (if it is still running). Additionally, each thread's quantum is doubled the next time it is run, since lower priority threads get longer quanta. For instance, assume thread A starts at the highest priority, and has a quantum of 1. It is preempted after 1 timer tick, and thread B (also with the highest priority) runs. When A is preempted, thread A's priority is decreased to the next level (i.e., it is placed in the corresponding queue), and its quantum is increased to 2. You need to impose a limitation on how large the quantum can get. Do not reduce the priority or increment the quantum once a thread has quantum 8. Use 1 timer tick as the base quantum. Also note that a thread that voluntarily gives up control (e.g., by calling Yield() or Sleep() or Suspend()) before expiration of the timer MUST have its priority reset to the highest possible, and its quantum reset to 1.

If the current thread has priority x and all other threads have a lower priority than x, the current thread should continue to run as long as no other threads of equal or higher priority are in the ready lists. This should be ensured for the MLFBQ scheduler.

Implementation Details

1. For part 1, implement the void Thread::Sleep(int seconds) and void Thread::UnSleep() functions, and complete the DeltaList implementation. For the rest of the lab:
2. Provide a scheduling policy selecting function int Scheduler::SetSchedPolicy(int) that will set which scheduling policy to use. The acceptable arguments are:

      
   #define RDRBN 0x1
   #define LOTRY 0x2
   #define MLFBQ 0x3
   

   Make sure to define these values in scheduler.h. The function returns 1 if the policy has been set, or 0 otherwise. If this function is not called, the RDRBN policy must be used. (Note: This function can be called several times. However, it will not be called when there are ready threads, so you need not worry about moving threads across lists.)
3. In addition, change the Thread::Fork() function so that the 2nd argument specifies the number of tickets in case of lottery scheduling (ignored for MLFBQ), and the last argument is the data that is passed to the thread. Therefore, the definition of the function should look like:
   void Thread::Fork(VoidFunctionPtr func, int tickets, int arg)

You can use DEBUG (see utility.h and utility.cc, and use the "-d t flag") or just use #ifdef/#endif, so you can have debugging prints that can be easily turned off. Make sure your output does not include any debugging printf statements.

Notes

A call to the schedule() function will select a thread from the ready list and then will start its execution. If the timer triggers during a thread's execution, the timer handler will save the thread context, and call the schedule() function to select and switch to another thread. The newly scheduled thread will resume as if it just came out of the timer handler, Yield, Sleep, or Suspend. If no threads are available, then the system exits. (Hint: Make sure that you change the function Scheduler::IsEmpty() to account for sleeping processes.)

Do not make changes to main.cc (other than perhaps calling your own test cases), as we will replace this file when doing various tests for grading your lab. In addition, you should not have any need to change the schedule() function.

Executing

The kernel execution begins in main() where everything gets initialized. After all of the initialization has been completed, a timer is set to go off and a test function ThreadTest1() is called. The test function currently in ThreadTest1() places a few threads on the ready list and then terminates. You should see a bunch of As, Bs, Cs,... alternating with some Ping Pong messages on the screen. Try to understand what the test does (examine threadtest.cc carefully) and then make up your own tests to examine the delta list, Sleep, and scheduler functionality.

Once the scheduler determines that no threads need to run anymore, you will see a message indicating that there are no ready or pending threads, followed by a print-out of statistics.

Testing

A sample test case for Sleep() is available here . You can use this to replace threadtest.cc when you want a simple test for sleep. We recommend that you test the DeltaList first (you do not need NachOS to test it -- you can just include the code with a simple main() that calls its functions).

A sample test case for the schedulers is available here . You can use this to replace threadtest.cc when you want a simple test for your two schedulers.

Observe that since NachOS is a user process from UNIX's point of view, you can use gdb to debug your code.

Turning in the project

Part 2 (the complete lab including SetSchedPolicy, Fork, and the 2 schedulers) is now due on Sunday, October 17th, 2004 before 11:59 PM.

To submit your lab:

1. Make sure your output does not include any printf statements that you added for debugging.
2. Change directories to your threads directory.
3. Type 'make' and ensure that everything built correctly.
4. Type 'make clean' to clean up the object files, etc.
5. Use 'cd ..' to change to the parent directory of your threads subdirectory.
6. Type 'turnin -c cs354 -p lab3-1 threads' to submit your work for lab 3, part 1.
7. Type 'turnin -c cs354 -p lab3-1 -v' and verify that the files you submitted are correct.