Due

Objectives

• to write low level code that manages threads

Introduction

The Scheduler class defines a set of static methods that manage the threads. Scheduler maintains a queue called readyQ of pointers to Thread objects. Whenever a thread yields, it is placed on the back of the queue (in threadYielded) and another thread is chosen to run (by scheduleThread). When there are no threads left to run, the system terminates.

As given, there is no mechanism for thread synchronization or I/O.

Assignment

• add code to implement condition variables,
• add code to implement monitors,
• add code to implement a sleep method that will not block all the threads, and
• add code to implement a getchar method that threads can use to read a single character from the keyboard without blocking the other threads.

To implement condition variables, you will have to implement the blockThread(Thread*, const Condition*), wakeupOne(const Condition *) and wakeupAll(const Condition *) methods in the Scheduler class. Test your modifications with the wait_test.x program. Before making your modifications, thread 1 will finish before thread 3 even though thread 1 calls wait to block until thread 3 terminates. Once your modifications are correct, thread 1 will terminate after thread 3.

• First, add a blocked list data structure to the Scheduler class to keep track of the blocked threads. Entries on this list should record both a pointer to the blocked thread and a pointer to the condition variable it is blocked on.
• blockThread should add the given thread to the blocked list and should then call scheduleThread to schedule the next thread.
• wakeupOne should scan the blocked list for a thread that is waiting on the given condition variable (i.e. an entry on the blocked list where the second part matches the pointer passed in) and should move that thread to the ready queue.
• wakeupAll should traverse the blocked list, moving every thread waiting on the given condition variable to the ready queue.

To implement monitors, you must implement the enter, leave, suspend, and reenter methods in the Monitor class.

• Run the program monitor_test.x. This program creates two pairs of threads with one monitor per pair. Note that threads A and B are allowed to execute in their monitor simultaneously. To fix this, write code in enter and leave. enter should check the owner of lock on the monitor. If the monitor is open, then the calling thread should be allowed to enter and should become the new owner (the address of the calling thread can be obtained with the Thread::getCurrent method). Otherwise, the calling thread should be placed on the turnstile queue of threads waiting to enter and at the same time blocked by creating a new condition variable and calling wait on that condition variable. Since you will need access to that condition variable later to unblock the thread, the condition variable should be saved on the queue along with the thread. You can add fields to the TurnstileEntry structure to save this and any other additional information on the queue.

  leave should check the queue. If any threads are waiting to enter the monitor, one should be selected and unblocked by calling notify on the condition variable that was used to block it. The newly unblocked thread should be made the new owner of the lock on the monitor. If there are no threads waiting to enter, the monitor should be made open.

• Now Thread B begins execution only when Thread A has finished, but thread C never terminates. This is because it calls a monitor method from within another monitor method. Modify enter so if the calling thread is already the owner of the lock on the monitor it is allowed to enter.
• Now Thread C is allowed to proceed, but Thread D is allowed to execute in the monitor simultaneously with C. This is because when Thread C finishes baz (which is called from bar), it calls leave, which opens up the monitor to Thread D, even though C is going to return to bar which is still in the monitor. What is needed is a count of how many nested calls within the monitor the current owner has made. Each time enter detects that the current owner is entering again, that count should go up. leave should decrement the count and only reopen the monitor once the count becomes zero.
• Once monitor_test.x works correctly, run monitor_test_2.x. At this point the second test should allow its threads C and D in the monitor simultaneously. This is because thread C, two calls deep in the monitor, temporarily gives up the lock when it calls wait from baz. If, when it regains the lock, the depth is not restored to two, then when baz calls leaveMonitor and returns to bar, leaveMonitor won't know that C is still in the monitor and will let in D. suspend and reenter are the methods used to allow threads to temporarily relinquish and then reacquire the lock on a monitor. reenter and suspend work like enter and leave and must work together to ensure that when a thread calls reenter and regains access to the monitor, the depth is restored to what it was when suspend was called. To do this, suspend should return the old depth; this depth is what is passed from Object::wait as the parameter to reenter. reenter should store that depth somewhere (probably in the TurnstileEntry structures) so that the code in leave and suspend can restore it when giving access to the monitor to another thread.
• The monitors should now work correctly. Check your output for the two tests against sample output for monitor_test and sample output for monitor_test_2 (your addresses for threads A and B may be different).

The current implementation of Thread::sleep does nothing. If you change it to use the system sleep call, then the sleeping thread will block the entire thread system. Instead, you should change it so it calls the block(Blocker *) method in the Thread class. The Blocker object should be created to record information the scheduler will need to determine when to restart the thread (in this case, the time at which the thread should wake up). Thread::block(const Blocker *) has been written so it calls Scheduler::blockThread(Thread *, const Blocker *); you should change this method so it saves the information it is given and schedules another thread. You should also change scheduleThread so it will check the threads that have called sleep and move them back to the ready queue once they've slept long enough. You can use gettimeofday from sys/time.h to determine the current time (measured in microseconds since January 1, 1970):

  struct timeval tv;
  gettimeofday(&tv, NULL);
  // tv.tv_sec * 1000000LL + tv.tv_usec is now microseconds since 1/1/1970

The current implementation of Thread::getchar simply calls the getchar method from stdio.h to read a character from the keyboard. If no character is available, this will block the entire thread system. You should change Thread::getchar so it calls Thread::block(const Blocker *) before it tries to read. This time, the Blocker object should record that the blocked thread is trying to read from the keyboard. The scheduler will have to be modified so that if threads are waiting for keyboard input it will use select from sys/select.h to determine of those threads can be moved back to the ready queue:

  fd_set readfds, writefds, exceptfds;
  FD_ZERO(&readfds);
  FD_SET(0, &readfds); // stdin = descriptor 0
  FD_ZERO(&writefds);
  FD_ZERO(&exceptfds);
 
  timeval timeout;
  timeout.tv_sec = 0;
  timeout.tv_usec = 0;
 
  int result = select(fd + 1, &readfds, &writefds, &exceptfds, &timeout);

  // result is 1 if there is keyboard input available

Files

zcat p3.tar.gz | tar xvf -

and then build the program with the commands using the supplied makefile with the command make.

If you do not have NASM installed, you can try using the preassembled object files thread_asm.o and scheduler_asm.o.

Advice

The STL queue class is probably not suitable for the blocked queue since you can't iterate through an STL queue. You can use list instead.

For debugging, you may want a method that prints the the addresses of the threads on the ready queue and the blocked list.

You may want to treat threads that have blocked using wait and threads that are blocking on a timer or on I/O differently.

Grading

Submissions