Computer Science/162/proj1

KThread.join()

Implementation

KThread has a new state variable joinedOnMe, a ThreadQueue, and isJoined, a boolean.

• When threadA calls threadB.join(), thread B adds it to its internal joinedOnMe queue and then puts it to sleep. In the finish() method, calls ready on the 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 several threads execute for loops that print out a series of statements. Check that statements for different threads are all printed contiguously and in ordering consistent with their respective wake times.
• Have a main thread print out system times with a set frequency, and have timed threads print when they have exceeded their wait times. Verify that they execute relatively close to their expected exit time.

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, a bool, two counters, and two condition variables): Lock lock int speakerCount int listenerCount bool exInProgress Condition speakers Condition listeners.

• We use a Boolean flag which indicates if a transfer is in progress.
• A lone first speaker or listener will sleep on its respective condition variable until its counterpart wakes it up so that they can both return.
• A second thread performing a counterpart action to the first thread will set the exInProgress flag to true, perform its actions and wake the 1st thread; any intruding 3rd thread will not attempt to proceed as long as the exInProgress flag is trueвАФthis 3rd thread will sleep on its respective condition variable, so that we can maintain synchronicity.
• The 1st thread will be woken up by the 2nd thread before the 2nd thread returns, at which point the first thread will set the Boolean to false, attempt to wake waiting threads of its type (this is due to the possibility of additional sleeping threads being added in the moment between one thread returning and another about to return), and finally return.

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.

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.

Pseudocode

speak(word) {

   Acquire the lock;
   While there are speakers, or an exchange is in progress:
       Increment the number of speakers and sleep;
       After waking, decrement the number of speakers;
   Set the word to speak;
   Increment number of speakers;
   If there are no listeners and there's no exchange in progress:

Go to sleep;

   If there are listeners and there's no exchange in progress:
       Wake a listener;
   else:
       Wake a speaker;
   Properly set if there is an exchange in progress or not;
   Release the lock and return;

}

listen() { Acquire the lock; While there are other listeners or an exchange is in progress: Increment the number of listeners and sleep; After waking, decrement the number of speakers; Increment the number of listeners; If there are no speakers and there's no exhange in progress: Go to sleep; If there's no exchange in progress: Wake a speaker; Flip the boolean that indicates if there's an exchange in progress; Set the return value to the speaker's word; Decrement the number of listeners; Release the lock and 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.

Boat.java

Implementation

Algorithm for solving boat problem (high level): If there are no children on island B or if there are no adults left on island A, two children from island A will pilot over and one will return to A. If there is a child on island B, an adult will pilot over to island B and the child will bring the boat back to island A. Once the adults are all on island A, the children can begin to transfer themselves over to island B.

There are the following state variables: lock L = new lock boatIsland = A boatPilot = null boatDeparting = false boatLookingForChild = false numChildrenOnB = 0 numAdultsOnA = 0 condition childrenWaitingOnA, adultsWaitingOnA, childrenWaitingOnB, adultsWaitingOnB, waitingToRide, waitingToPilot //separate condition variables all on lock L

Each thread will attempt to acquire the lock (which represents the boat). If the thread can performs one of its assigned tasks, then it executes it. Otherwise it will go to sleep.

Child Algorithm (with Pseudocode): Each child will begin running on island A and try to acquire the lock.

childItinerary () {

myIsland = A
while (true) {
acquire L

If the child is on island A and the boat is available for use, then it will ask for a passenger child and go to sleep. Once a passenger child is found, the pilot will be awoken by the passenger child and pilot them to island B. He now increments the global counter numChildrenOnB. He wakes up the passenger child so that he can be moved to island B as a passenger and goes to sleep. The passenger, increments the numChildrenOnB counter and wakes up the pilot. Once the pilot child reawakens, he will speak to begin(), telling the begin thread the number of children currently on island B. He then returns to island A and decrements numChildrenOnB. If the number of adults on island A (according to numAdultsOnA) is not 0, he wakes up the adults waiting on A, puts himself to sleep on the children waiting on A condition variable, and releases the lock (after wake). Otherwise, he simply releases the lock.

if the child is on island A and the boat is not departing {

if the boat does not have a pilot and the boat is not looking for a passenger { //first move of pattern
boatLookingForChild = true;
boatPilot = CHILD;
sleep and wait to pilot;
pilot to B;
wake up passenger; 

increment number of children on B; boatIsland = B; boatLookingForChild = false; sleep and wait to pilot; speakToBegin() decrement num of children on B child pilots to A

boatIsland = A 

if number of adults on A != 0 { wake adults waiting on A;

sleep and wait on island A; 

} release L;

continue;

}

If the child is on island A and the boat is asking for a passenger, the child will set the boat as departing, wake up the pilot child, and go to sleep. After the pilot child is awoken by the pilot, he will transfer himself to island B as a passenger and increment numChildrenOnB. He awakens the pilot child (so that he can pilot back to A with the boat), puts the children waiting on B to sleep, and releases the lock.

else if (boatPilot == CHILD and boatLookingForChild) {

boatDeparting = true;
wake a pilot;
sleep and wait to ride;
child ride to B; 

increment number of children on B;

myIsland = B;
boatDeparting = false;
wake a pilot;
sleep on island B;
release L;
continue;

}

If the child is on island B with the boat and the boat is not in use, he will pilot himself back to A and decrement the counter numChildrenOnB.

} else if (myIsland == boatIsland == B and !boatDeparting) { decrement num of children on B

child pilots to A;
myIsland = boatIsland = A;
boatPilot = null;
release L;
continue;

}

If none of these conditions are met, the child is put to sleep as waiting on his respective island.

else {

if (myIsland == A)

sleep and wait to ride

else

sleep on island B; }

Adult Algorithm (with Pseudocode): The adults all begin on island A and acquire the lock. The adults also increment a global counter numAdultsOnA.

adultItinerary() {

myIsland = A
increment numAdultsOnA
while(true) {
acquire L;

If the adult is on island A, the boat is available for use and the last boat pilot was a child, the adult pilots to island B. He then wakes up one child waiting on island B so that he can pilot the boat back to A. The adult is now done with its task and goes to sleep, thus releasing the lock for other threads to use.

if (myIsland == boatIsland == A and !boatDeparting and boatPilot == CHILD and !boatLookingForChild) {

boatPilot = ADULT;
adult pilots to B;
boatIsland = myIsland = B;
wake a child sleeping on B;
sleep on B;
continue;

}

Otherwise the adult puts the adults on his respective island to sleep.

else {

if (myIsland == A)

sleep on A;

else

sleep on B; }

In begin(), each time the child threads speaks to it, begin() will check if number of children on B is equal to the number of child threads that it forked. Since all adults must be on B before number of children increases, this tells us that we are done.

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.