Computer Science/162/proj1

Contents

KThread.join()

Implementation

KThread has a new state variable joinedOnMe, a ThreadQueue.

• When threadA calls threadB.join(), threadB adds it to its internal joinedOnMe queue and then puts it to sleep. In threadB's finish() method, threadB calls nextThread() on its joinedOnMe queue before returning.
• join() also checks that this thread is not equal to the current thread and that joinedOnMe is not already occupied by another thread with a boolean flag, which determines whether join() has already been called on this thread.

Testing

• ThreadA prints out a few statements, calls ThreadB.join(), then prints out a few more statements. ThreadB also prints out a series of statements. We want to verify that ThreadB executes contiguously to completion before ThreadA resumes its execution.
• Have a thread attempt to join itself, and call join() on the same thread multiple times, and also attempt to call join on a finished thread. These should all return immediately because the join condition was not satisfied.
• Have a chain of threads. Thread C will attempt to join Thread B. Thread B will attempt to join Thread A. Thread A forks last. Verify that A executes before B, and B executes before C.

Pseudocode

join() {

   Disable interrupts;
   If (CurrentThread == self or isJoined) or (status is Finished) {
            Re-enable interrupts;
       Return; // conditions for join not satisfied
   } else {
       add CurrentThread to joinedOnMe queue;
       isJoined = true;
       Sleep the currentThread;
   }
   Re-enable interrupts;

} finish(){

   // Interrupts have been disabled.
   ...(existing code)...
   Ready the thread in the joinedOnMe queue;
   Sleep (existing);

}

Condition.java

Implementation

Condition2 has a new state variable waitQueue, a ThreadQueue with transferPriority flag set to false.

• In the sleep() method, we disable interrupts, the calling (current) thread is added to the waitQueue of threads, the corresponding lock is released, and the current thread is put to sleep. When it wakes up, interrupts are re-enabled and the thread attempts to reacquire the condition lock.
• The wake() method disables interrupts and checks if the waitQueue is empty. If it is not, the method readies the first thread in the waitQueue. Finally, wake() re-enables interrupts.
• wakeAll() will call wake() as long as there are threads still in the waitQueue.

Testing

• Sleep several threads on the condition variable. Upon waking, these threads should print a unique statement and perform a wake() on the condition variable. Have one thread perform an initial wake() on the condition variable and verify that all threads are executed.

Pseudocode

Sleep(){ Disable Interrupts; Add current thread to wait queue; Release the lock; Put the current thread to sleep; Acquire the lock; Re-enable Interrupts; }

Wake(){ AssertTrue (lock held by current thread); Disable interrupts; If there is a thread on the wait queue, remove and wake it; Re-enable interrupts; }

WakeAll(){ Disable interrupts; While there are threads on the wait queue, call wake().; Re-enable interrupts; }

WaitUntil()

Implementation

Alarm has a new instance variable, waitingThreads, which is a Java PriorityQueue of waiting threads with the target wake time as their priority. It also contains a new inner class named waitingThread, which contains a reference to the KThread and its associated wakeTime.

• waitUntil() creates a new instance of waitingThread, which will associate the currentThread with the give time argument. It will then add this waitingThread instance to the PriorityQueue and put the current thread to sleep. This method is atomic.
• timerInterrupt() peek at the first WaitingThread in the waitQueue and check if its associated wake time is less than or equal to the current time. If it is, this method will pop the WaitingThread off the waitQueue and wake the associated thread. This process is repeated until the wake time of the first WaitingThread is greater than the current time.

Testing

• Have the timer interrupt print a debug statement, and have timed threads print the times they go to sleep and when they have woken up. Verify that they wake up relatively close to their expected exit time.
• Make sure threads called with illegal times return immediately. Test threads that go to sleep chronologically in order (1, 500, 1050) as well as threads that go to sleep with the same times ( 50, 50) and threads that go to sleep in reverse order (500, 250). Verify they all wake up when they are supposed to.

Pseudocode

waitUntil(time){

   Disable interrupts;
   Create a new waitingThread;
   Add the waiting thread to the priority queue;
   Sleep the current thread;
   Re-enable interrupts;

}

timerInterrupt(){

   AssertTrue (interrupts have already been disabled);
   For all waitingThreads that have exceeded their associated wait time;
   Wake their associated threads and remove from queue;

}

Communicator

Implementation

We add new state variables (a lock, four counters, and two condition variables): Lock lock int activeSpeakers int waitingSpeakers int activeListeners int waitingListeners Condition speakers Condition listeners Condition return

• The first lone speaker or listener will be counted as active, or in the process of exchanging a message and returning, and will sleep on the return condition variable until its counterpart wakes it up so that they can both return.
• A second thread performing the same action as a currently active thread will be counted as waiting, and be put to sleep on its respective condition variable. Otherwise, it will check if there is an active thread of its counterpart action waiting on the return condition variable. If there isn’t, it will attempt to wake waiting threads of its counterpart action prior to going to sleep on the return condition variable. If there is a counterpart active thread, it will wake it up and they both will return. Prior to returning, a counterpart action will also attempt to wake sleeping waiting threads of its type.
• Any interjecting threads that execute in between an exchange of message will be stopped by the active counters, which do not decrement until BOTH counterparts in the exchange have returned.

Testing

Our original solution exhibited non-deterministic behavior, so after rewriting it, we decided to stress it exceptionally to make sure that it was working correctly. We tested our communicator in three main ways.

First, we set up a manual sequence of speak() and listen() actions on different threads and executed them in a particular order, verifying that the resulting sequence of messages was correct, monitored via print statements to the console

Second, we set off a random number of speakers, followed by a random number of listeners, and verified that the limiting resource was completely used up, i.e. that a matching number of speakers and listeners returned and that this was equal to the smaller of numbers of created speakers/listeners. Finally, we repeated the same procedure, but intermingled the creation of speakers and listeners via .fork(), such that listeners would start listening before all the speakers were queued up.

Third, we used testing functions: MassSpeaker and MassListener are designed to be run by a single thread each. These runnables iterate until a given limit, and on each iteration, there is a 50% chance that a speak (or listen) is called. After each iteration, the thread yields to the opposite thread to do the same. Debug statements will display what threads are doing at each iteration and how messages are being exchanged. With this we can generate large amounts of calls with randomized orders between two threads, and will be able to verify all speaks are correctly received by a listen. A second set of runnables, MassTSpeaker and MassTListener, are designed to fork off several threads themselves, with each of these forked threads performing a single speak or listen. These forked threads are also executed with 50% chance on each iteration to provide random ordering. We can also verify if all threads are correctly paired off via print statements to console.

The latter two tests were run with up to 500 threads of speakers and listeners each (with a temporary override on the number of max threads in Nachos) and the number of listen and speak operations was analyzed via script. The speakers and listeners would print statements while executing code, which allowed us to perform this analysis.

  speak(int word) {
       Acquire the lock;
       while (There is an active speaker) {
           WS++;
           Sleep as a waiting speaker;
           WS--;
       }
       AS++;
       Set the word;
       if (There is an active listener) {
           Wake the active listener;
           Release the lock;
           Return;
       } else {
           if (There are waiting listeners) {
               Wake a waiting listener;
           }
           Sleep as an active speaker;
           AS--;
           AL--;
           if (There are waiting speakers) {
               Wake a waiting speaker;
           }
           Release the lock;
           Return;
       }
   }
   
   listen() {
       Acquire the lock;
       while (There is an active listener) {
           WL++;
           Sleep as a waiting listener;
           WL--;
       }
       AL++;
       if (There is an active speaker) {
           Wake an active speaker;
           Store the word;
           Release the lock;
           Return the word;
       } else {
           
           if (There are waiting speakers) {
               Wake a waiting speaker;
           }
           Sleep as an active listener;
           AL--;
           AS--;
           if (There are waiting listeners) {
               Wake a waiting listener;
           }
           Store the word;
           Release the lock;
           Return the word;
       }
   }

Priority Scheduler

Implementation

New state variables are shown by the class they appear in: PriorityQueue: KThread lastThread ThreadState: int donatedPriority PriorityScheduler: TreeSet¬Ђlong (time), KThread¬ї waitQueue

• nextThread()
• This method retrieves and removes the highest priority thread off the Priority-Time set. It calculates this thread's priority based on priorities of the threads waiting in the queue. It resets the priority of thread previously in the lastThread position to its original priority. The thread to be returned is also set as the new lastThread.
• pickNextThread()
• This method retrieves the first thread from the Priority-Time set without removing it from the set. It creates a new ThreadState from this thread and returns the ThreadState.
• getEffectivePriority()
• This method sums the associated thread's priority and its donatedPriority. If this sum is less than 7, the method returns the sum. Otherwise, the max priority 7 is returned.
• setPriority()

This method will change the actual priority of the thread associated with the ThreadState. The effective priority of lastThread must also be by difference between current threads priority and new priority.

• waitForAccess(priorityQueue)

This method puts thread associated with the threadState onto the Priority-Time set. The set sorts all threads by priority, then time. The associated thread will then be put to sleep. This method will also recalculate effective priority: it will add up all priorities of the threads in the set and donate it to the lastThread.

• acquire()
• This method calculates the priority of the associated thread based on priorities of the threads waiting in the queue. It resets the priority of the thread previously in the lastThread position to its original priority. The associated thread is set as the new lastThread.

Testing

• Instantiate new threads and set their priorities in decreasing order. Have the threads state their priorities as they execute and verify that they were run in decreasing order according to their priorities.
• Verify donation works by creating a high priority thread and joining it to a low priority thread with a high priority thread already queued.

Pseudocode

Boat.java

Implementation

Algorithm for solving boat problem (high level): If there are no children on Molokai or if there are no adults left on Oahu, two children from Oahu will pilot over and one will return to Molokai. If there is a child on Molokai, an adult will pilot over to Molokai and the child will bring the boat back to Oahu. This process, carried to completion eventually results in all of the adults and children on Molokai.

Shared state variables

lock = new Lock()
boatIsland = Island.A
boatPilot = null
boatDeparting = false
boatLookingForChild = false
childCounter = 0
adultCounterA = 0
adultCounterB = 0
sleepingChildren = 0
waiters = 0

pipe = new Communicator()

Condition variables, all on lock: childrenWaitingOnA, adultsWaitingOnA, childrenWaitingOnB, adultsWaitingOnB, waitingToRide, waitingToPilot

In addition, each thread has a local variable to keep track of which island the person is currently on.

Basic idea

Each thread will attempt to acquire the lock (which essentially represents control over the boat). If the thread can perform one of the tasks fitting for the current state of the world, it executes it. Otherwise, it will go to sleep on the condition variable corresponding to its current role and location.

Algorithm details

Each child will begin running on Oahu and try to acquire the lock.

If the child is on Oahu and the boat is available for use (i.e. boatLookingForChild == false and boatPilot == null and boatDeparting == false), it will assume the role of pilot and set the boatLookingForChild variable to true, then going to sleep on waitingToPilot. Once a passenger child is found, the pilot will be awoken by the passenger child and pilot them both to Molokai, while the passenger goes to sleep on waitingToRide. He then increments the childCounter, wakes up the passenger child so that he can ride to Molokai, and goes back to sleep.

The passenger, upon arrival at Molokai, increments the childCounter and speaks to begin() the number of children on Molokai. The child passenger then wakes up the pilot and goes to sleep on childrenWaitingOnB. Once the pilot child reawakens, he returns to Oahu, decrementing childCounter before departure.

Upon return to Oahu, if the number of adults on Oahu (according to adultsWaitingOnA) is not 0 and there is still a child left on Molokai to row the boat back after the adult goes across (according to childCounter), the pilot wakes up the adults waiting on A, puts himself to sleep on childrenWaitingOnA, releases the lock after wake, and restarts the looop. Otherwise, he simply releases the lock and restarts the loop.

The adults all begin on Oahu, try to acquire the lock, and each initially increment adultCounterA.

If the adult is on Oahu, the boat is available for use, and there is at least one child on Molokai according to childCounter, the adult pilots to Molokai. Otherwise, he wakes a child on childrenWaitingOnA and goes to sleep on adultsWaitingOnA.

If the adult does pilot across, he increments adultCounterB upon arrival to Molokai, speaks to begin() the value of childCounter, wakes up a child from childrenWaitingOnB so that he can pilot the boat back to Oahu, and then puts himself to sleep on adultsWaitingOnB. The adult is now done and will never be woken again.

If a child is sleeping on Molokai on childrenWaitingOnB and gets woken by an adult, he will decrement childCounter and pilot himself back to Oahu. Upon arrival, he releases the lock and restarts the loop.

For both adults and children, if the boat is busy or inaccessible as determined by the state of the boatPilot, boatDeparting, boatLookingForChild, and boatIsland variables given the person's current location, each will go back to sleep on the appropriate condition variable (i.e. childrenWaitingOnA for child threads on Oahu).

begin() behavior

begin() creates the required number of child and adult threads and then forks them. Then, it begins to listen() on the one shared Communicator (pipe). When begin() receives a message, it checks the "spoken" number as well as adultCounterB against the number of spawned threads to see if everyone is across yet.

The reason that it does not check the value of childCounter directly is because by the time it receives the message, it is possible that a child has already piloted back to Oahu, thus decrementing the counter and preventing begin() from knowing the true number of children on Molokai.

Testing

We tested different numbers of both children and adults and verified by hand that the sequence of events, in terms of rowing from one island to the other, was correct.

First, we tried various numbers of children with no adults at all: the base case of two children, then a small but odd number of children, and then large numbers of both odd and even amounts of children.

Then, we tested having small numbers of children and adults together, with a greater number of children than adults, both odd and even-number combinations. Again, we monitored that the rowing pattern was correct by hand. We also watched the number of people who have arrived at Molokai and made sure that these numbers made sense.

Finally, we tested larger numbers of both adults and children and verified that the rowing patterns were correct. We tested both combinations with more adults than children and vice versa. The rowing pattern, as well as number of people on Molokai, was monitored to make sure no rules were being violated.