Difference between revisions of "Computer Science/162/proj1"

From lensowiki
Jump to: navigation, search
(initial version)
 
m (Lensovet moved page CS/162/proj1 to Computer Science/162/proj1)
 
(57 intermediate revisions by 5 users not shown)
Line 1: Line 1:
−
==KThread.join()==
+
=={{c|KThread.join()}}==
 
===Implementation===
 
===Implementation===
−
KThread has a new state variable joinedOnMe, a ThreadQueue.
+
;New state variables
−
* 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 nextThread() on its joinedOnMe queue before returning.  
+
{{c|KThread}} has a new state variable {{c|joinedOnMe}}, a {{c|ThreadQueue}}, and {{c|isJoined}}, a {{c|boolean}}
−
* 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.  
+
 
 +
;Implementation details
 +
* When {{c|threadA}} calls {{c|threadB.join()}}, {{c|threadB}} adds it to its internal {{c|joinedOnMe}} queue and then puts it to sleep. In {{c|threadB}}'s {{c|finish()}} method, {{c|threadB}} calls {{c|nextThread()}} on its {{c|joinedOnMe}} queue before returning.  
 +
* {{c|join()}} also checks that this thread is not equal to the current thread and that {{c|joinedOnMe}} is not already occupied by another thread with a boolean flag, which determines whether {{c|join()}} has already been called on this thread.
  
 
===Testing===
 
===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.  
+
* {{c|threadA}} prints out a few statements, calls {{c|threadB.join()}}, then prints out a few more statements. {{c|threadB}} also prints out a series of statements. We then verify that {{c|threadB}} executes contiguously to completion before {{c|threadA}} resumes its execution, as evidenced by the sequence of printed statements.  
−
* Have a thread attempt to join itself, and call join() on the same thread multiple times (from the same and from different threads).
+
* Have a thread attempt to {{c|join()}} to itself, call {{c|join()}} on a second thread multiple times, and attempt to call {{c|join()}} on a third finished thread (all separately). These should all return immediately as this is the expected behavior.
 +
* Test 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===
 
===Pseudocode===
−
join() {
+
{{c|<pre>join() {
 
     Disable interrupts;
 
     Disable interrupts;
 
     If (CurrentThread == self or isJoined) or (status is Finished) {
 
     If (CurrentThread == self or isJoined) or (status is Finished) {
−
            Re-enable interrupts;
+
        Re-enable interrupts;
 
         Return; // conditions for join not satisfied
 
         Return; // conditions for join not satisfied
 
     } else {
 
     } else {
−
         joinedOnMe.waitingForAccess(currentThread);
+
         add CurrentThread to joinedOnMe queue;
 
         isJoined = true;
 
         isJoined = true;
 
         Sleep the currentThread;
 
         Sleep the currentThread;
 
     }
 
     }
 
     Re-enable interrupts;
 
     Re-enable interrupts;
−
}
+
}</pre>}}
−
finish(){
+
 
 +
{{c|<pre>finish() {
 
     // Interrupts have been disabled.
 
     // Interrupts have been disabled.
 
     ...(existing code)...
 
     ...(existing code)...
−
     Ready the joinedOnMe thread;
+
     Ready the thread on the joinedOnMe queue;
 
     Sleep (existing);
 
     Sleep (existing);
−
}
+
}</pre>}}
  
 +
==Condition2.java==
 +
===Implementation===
 +
;New state variables
 +
Condition2 has a new state variable {{c|waitQueue}}, a {{c|ThreadQueue}} with {{c|transferPriority}} flag set to false.
  
−
==Condition.java==
+
;Implementation details
−
===Implementation===
+
* In the {{c|sleep()}} method, we disable interrupts, the current thread is added to the {{c|waitQueue}} of threads, the corresponding lock is released, and the current thread is put to sleep. When it wakes up, the thread attempts to reacquire the corresponding lock and interrupts are re-enabled.  
−
Condition2 has a new state variable waitQueue, a ThreadQueue with transferPriority flag set to false.
+
* The {{c|wake()}} method disables interrupts and retrieves the next thread from {{c|waitQueue}}.  If the thread returned is not null, that thread is readied.  Finally, the interrupts are re-enabled.
−
* 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 {{c|wakeAll()}} method also disables the interrupts and stores the next thread from {{c|waitQueue}} as a {{c|KThread}} variable, {{c|nextThread}}. While {{c|nextThread}} is not null, the method will ready that thread and set {{c|nextThread}} to the next thread from {{c|waitQueue}}. This procedure continues until there are no more threads in {{c|waitQueue}}.
−
* 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===
 
===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.
+
* {{c|Condition2.java}} was tested using a class called {{c|CondThread}}, which implements {{c|Runnable}}. The class is instantiated with an integer {{c|iterations}}, a lock, a {{c|Condition2}} variable to call {{c|sleep()}} on, and a {{c|Condition2}} variable to call {{c|wake()}} on. When a {{c|CondThread}} runs, it acquires the lock, then enters a for-loop of 6 iterations. On each iteration, the thread will print out a debug statement noting that the current thread is on the ith iteration. When the loop iteration number is equal to {{c|iterations}}, threads can take one of three actions:
−
 
+
*#If the thread's ID is '0', then that thread is the waking thread and calls {{c|wake()}} on its second condition variable.
 +
*#If the thread's ID is '0-all', it calls {{c|wakeAll()}} on its second condition variable
 +
*#Otherwise, it goes to sleep on its first condition variable. Using the output, we verify that the threads all run in the correct order and all execute to completion.
 +
* Sleep several threads on the condition variable. Upon waking, these threads should print a unique statement and perform a {{c|wake()}} on the condition variable. Have one thread perform an initial {{c|wake()}} on the condition variable and verify that all threads are executed.
 +
* Sleep several threads on several various condition variables.  Verify via console print statements that the proper threads wake up at the correct times according to which condition variable they were sleeping on.
 +
* Sleep several threads on the condition variable, then have one final thread wake them all with {{c|wakeAll()}}. Verify that all threads have woken up via console print statements.
 +
* Sleep several threads on several various condition variables, then have one thread call {{c|wakeAll()}} on one of the condition variables.  Verify via console print statements that all the threads put to sleep on that condition variable wake up and that only those threads wake up.
  
 
===Pseudocode===
 
===Pseudocode===
−
Sleep(){  
+
{{c|<pre>sleep() {  
−
Disable Interrupts;
+
    Disable Interrupts;
−
Add current thread to wait queue;
+
    Add current thread to wait queue;
−
Release the lock;
+
    Release the lock;
−
Put the current thread to sleep;
+
    Put the current thread to sleep;
−
Acquire the lock;
+
    Acquire the lock;
−
Re-enable Interrupts;
+
    Re-enable Interrupts;
−
}
+
}</pre>}}
  
 +
{{c|<pre>wake() {
 +
    AssertTrue (lock held by current thread);
 +
    Disable interrupts;
 +
    If there is a thread on the wait queue:
 +
        Remove the first thread and wake it;
 +
    Re-enable interrupts;
 +
}</pre>}}
  
−
Wake(){
+
{{c|<pre>wakeAll() {
−
AssertTrue (lock held by current thread);
+
    Disable interrupts;
−
Disable interrupts;
+
    While there are threads on the wait queue:
−
If there is a thread on the wait queue, remove and wake it;
+
        Remove the first thread and wake it;
−
Re-enable interrupts;  
+
    Re-enable interrupts;  
−
}
+
}</pre>}}
  
−
WakeAll(){
+
=={{c|waitUntil()}}==
−
Disable interrupts;
+
===Implementation===
−
While there are threads on the wait queue, call wake().;
+
;New state variables
−
Re-enable interrupts;
+
Alarm has a new instance variable, {{c|waitingThreads}}, which is a Java {{c|PriorityQueue}} of waiting threads with the target wake time as their priority. It also contains a new inner class named {{c|WaitingThread}}, which contains a reference to a {{c|KThread}} and its associated {{c|wakeTime}}. The {{c|PriorityQueue waitingThreads}} will be populated with instances of this inner class.
−
}
 
  
−
 
+
;Implementation details
−
==WaitUntil()==
+
* {{c|waitUntil()}} creates a new instance of {{c|waitingThread}}, which will associate the current thread with the given time argument. It will then add this {{c|waitingThread}} instance to the {{c|PriorityQueue}} and put the current thread to sleep.  This method is atomic.  
−
===Implementation===
+
* {{c|timerInterrupt()}} peeks at the first {{c|WaitingThread}} in the {{c|waitQueue}} and checks if its associated wake time is less than or equal to the current time.  If it is, this method will pop the {{c|WaitingThread}} off the {{c|waitQueue}} and wake the associated thread.  This process is repeated until the wake time of the first {{c|WaitingThread}} is greater than the current time.
−
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===
 
===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 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 wake time.
−
* 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.
+
* 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===
 
===Pseudocode===
−
waitUntil(time){
+
{{c|<pre>waitUntil(time){
 
     Disable interrupts;
 
     Disable interrupts;
 
     Create a new waitingThread;
 
     Create a new waitingThread;
Line 83: Line 99:
 
     Sleep the current thread;
 
     Sleep the current thread;
 
     Re-enable interrupts;
 
     Re-enable interrupts;
−
}  
+
}</pre>}}
  
−
 
+
{{c|<pre>timerInterrupt(){
−
timerInterrupt(){
 
 
     AssertTrue (interrupts have already been disabled);
 
     AssertTrue (interrupts have already been disabled);
 
     For all waitingThreads that have exceeded their associated wait time;
 
     For all waitingThreads that have exceeded their associated wait time;
 
     Wake their associated threads and remove from queue;
 
     Wake their associated threads and remove from queue;
−
}
+
}</pre>}}
−
 
 
  
 
==Communicator==
 
==Communicator==
 
===Implementation===
 
===Implementation===
−
We add new state variables (a lock, a bool, two counters, and two condition variables):
+
;New state variables
−
Lock lock
+
{{c|<pre>Lock lock = new Lock()
−
int speakerCount
+
int activeSpeakers = 0
−
int listenerCount
+
int waitingSpeakers = 0
−
bool exInProgress
+
int activeListeners = 0
 +
int waitingListeners = 0
 
Condition speakers
 
Condition speakers
−
Condition listeners.
+
Condition listeners
−
* We use a Boolean flag which indicates if a transfer is in progress.
+
Condition return</pre>}}
−
* 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.
+
;Implementation details
−
* 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.  
+
* 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 {{c|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 {{c|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, the counterpart action will also attempt to wake ''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===
 
===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.
 
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
+
First, we set up a manual sequence of {{c|speak()}} and {{c|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.
 
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.
+
 
 +
Finally, we repeated the same procedure, but intermingled the creation of speakers and listeners via {{c|.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.
 
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===
+
To be able to perform these tests, we created a number of helper classes which implement Runnable. {{c|MassSpeaker}} and {{c|MassListener}} are designed to be run by a single thread each. These will 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.
−
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() {
+
A second set of runnables, {{c|MassTSpeaker}} and {{c|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.
−
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;
 
−
}
 
  
 +
===Pseudocode===
 +
{|
 +
| style="vertical-align: top;"|
 +
  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 waiting to return;
 +
            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 waiting to return;
 +
            AL--;
 +
            AS--;
 +
            if (There are waiting listeners) {
 +
                Wake a waiting listener;
 +
            }
 +
            Store the word;
 +
            Release the lock;
 +
            Return the word;
 +
        }
 +
    }
 +
|}
  
 
==Priority Scheduler==
 
==Priority Scheduler==
 
===Implementation===
 
===Implementation===
−
New state variables are shown by the class they appear in:
+
;New state variables
−
PriorityQueue: KThread lastThread
+
* {{c|PriorityQueue.holder}} - this ThreadState corresponds to the holder of the resource signified by the  
−
ThreadState: int donatedPriority
+
* {{c|PriorityQueue.waitQueue}} - an ArrayList of ThreadStates waiting on this resource. Unsorted.
−
PriorityScheduler: TreeSet¬Ђlong (time), KThread¬ї waitQueue
+
* {{c|PriorityQueue.dirty}} - set to true when a new thread is added to the queue, or any of the queues in the waitQueue flag themselves as dirty.
−
* nextThread()
+
* {{c|PriorityQueue.effective}} - the cached highest of the effective priorities in the waitQueue. This value is invalidated while dirty is true.
−
* 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.
 
  
 +
* {{c|ThreadState.myResources}} - collection of PriorityQueues that signify the Locks or other resources that this thread currently holds.
 +
* {{c|ThreadState.waitingOn}} - collection of PriorityQueues corresponding to resources that this thread has attempted to acquire but could not.
 +
* {{c|ThreadState.effective}} - the cached effective priority of this thread. this value is invalidated when dirty is true
 +
* {{c|ThreadState.dirty}} - set to true when this thread's priority is changed, or when one of the queues in myResources flags itself as dirty.
  
 +
;Implementation overview
 +
The idea here is that {{c|Thread}}s keep track of the {{c|PriorityQueue}}s corresponding to both the resources that they are currently holding and those that they want to hold. We can do this via hooks in {{c|PriorityQueue}}'s {{c|waitForAccess()}}, {{c|acquire}}, and {{c|nextThread}} methods.
 +
 +
Once we have this, every time a thread tries to wait on a queue, or takes control of a queue, we can tell the queue that its overall effective priority may have changed, and it can, in turn, tell the thread that currently holds the resource that one of the {{c|PriorityQueue}}s it holds may have had its priority changed. That holder can in turn tell the same to the {{c|PriorityQueue}}s that it is waiting on, and so forth. Eventually a thread, which is holding a resource that everyone needs, but has a low priority, will be marked for priority recalculation and thus priority escalation.
 +
 +
At this point, recalculation is simple. The effective priority of a thread is the maximum of its own actual priority and the priorities of all the {{c|PriorityQueue}}s that it currently holds. The effective priority of a {{c|PriorityQueue}} is the maximum effective priority of all the threads waiting on it (if the queue is supposed to donate priority), and so on and so forth in a mutually recursive manner.
 +
 +
;Implementation details
 +
* {{c|PriorityQueue.nextThread()}}
 +
:This method retrieves and removes the highest priority thread off the Priority-Time {{c|ArrayList}}. It then flags the previous holder of this resource as {{c|dirty}}, and removes the queue from that holder's resource list. It then sets the retrieved thread to this queue's new {{c|holder}}, and flags that thread as {{c|dirty}} as well.
 +
* {{c|PriorityQueue.acquire(KThread thread)}}
 +
:Sets the {{c|holder}} of this queue to the specified thread, bypassing the queue. Resets previous {{c|holder}} and sets {{c|dirty}} flags as in {{c|nextThread()}}.
 +
* {{c|PriorityQueue.pickNextThread()}}
 +
:Simply retrieves the highest priority thread off this queue.
 +
* {{c|PriorityQueue.setDirty()}}
 +
:Set this queue's {{c|dirty}} flag, and calls {{c|setDirty}} on the current holder of this thread.
 +
* {{c|PriorityQueue.getEffectivePriority()}}
 +
:If this queue is {{c|dirty}}, returns the maximum of each of the {{c|ThreadState}}s{{c|.getEffectivePriority()}} in this queue. Those calls in turn become mutually recursive when they call {{c|getEffectivePriority()}} on the {{c|PriorityQueues}} in their {{c|myResources}}.
 +
* {{c|ThreadState.setPriority()}}
 +
:This method will change the actual priority of the thread associated with the {{c|ThreadState}}. It then calls {{c|setDirty()}} on this thread.
 +
* {{c|ThreadState.setDirty()}}
 +
:Sets the {{c|dirty}} flag on this thread, then calls {{c|setDirty()}} on each of the {{c|PriorityQueue}}s that the thread is waiting for. Mutually recursive.
 +
* {{c|ThreadState.getEffectivePriority}}
 +
:Like the analogue of this function in {{c|PriorityQueue}}, returns the (cached) priority if this thread is not {{c|dirty}}; otherwise, recalculates by returning the max of the effective priorities of the {{c|PriorityQueue}}s in {{c|myResources}}.
  
 
===Testing===
 
===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.
 
* 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.
 
* Verify donation works by creating a high priority thread and joining it to a low priority thread with a high priority thread already queued.
 +
* Create complex set of interdependent threads and multiple locks, verify that execution order is correct.
  
 
===Pseudocode===
 
===Pseudocode===
 +
;PriorityQueue
 +
{{c|<pre>
 +
public void waitForAccess(KThread thread)
 +
    add this thread to my waitQueue
 +
      thread.waitForAccess(this)
 +
 
 +
public void acquire(KThread thread)
 +
    if I have a holder and I transfer priority, remove myself from the holder's resource list
 +
    thread.acquire(this)
 +
 
 +
public KThread nextThread()
 +
    if I have a holder and I transfer priority, remove myself from the holder's resource list
 +
    if waitQueue is empty, return null
 +
      ThreadState firstThread = pickNextThread();
 +
      remove firstThread from waitQueue
 +
      firstThread.acquire(this);
 +
    return firstThread
 +
 +
public int getEffectivePriority()
 +
    if I do not transfer priority, return minimum priority
 +
    if (dirty)
 +
        effective = minimum priority;
 +
        for each ThreadState t in waitQueue
 +
            effective = MAX(effective, t.getEffectivePriority())
 +
        dirty = false;
 +
    return effective;
 +
 +
  public void setDirty()
 +
      if I do not transfer priority, there is no need to recurse, return
 +
      dirty = true;
 +
      if I have a holder, holder.setDirty()
 +
 
 +
protected ThreadState pickNextThread()
 +
      ThreadState ret = null
 +
      for each ThreadState ts in waitQueue
 +
        if ret is null OR ts has higher priority/time ranking than ret
 +
            set ret to ts
 +
    return ret;</pre>}}
 +
 +
;ThreadState
 +
{{c|<pre>
 +
public int getPriority()
 +
    return non-donated priority.
 +
 +
public int getEffectivePriority()
 +
    if (dirty) {
 +
          effective = non-donated priority
 +
        for each PriorityQueue pq that I am currently holding
 +
          effective = MAX(effective, pq.getEffectivePriority)
 +
    }
 +
    return effective;
 +
 +
public void setPriority(int priority)
 +
    set non-donated priority to the argument
 +
    setDirty();
  
 +
  public void setDirty()
 +
      if already dirty return
 +
      dirty = true;
 +
      for each of the PriorityQueues pq I am waiting on,
 +
        pq.setDirty
 +
 +
public void waitForAccess(PriorityQueue waitQueue)
 +
    add the waitQueue to my waitingOn list
 +
    if the waitQueue was previously in myResources, remove it and set its holder to null.
 +
      if waitQueue has a holder, set the queue to dirty to signify possible change in the queue's effective priority
 +
 +
public void acquire(PriorityQueue waitQueue)
 +
    add waitQueue to myResources list
 +
    if waitQueue was in my waitingOn list, remove it
 +
    setWaitQueue's holder to me
 +
    setDirty();</pre>}}
  
 
==Boat.java==
 
==Boat.java==
 
===Implementation===
 
===Implementation===
−
Algorithm for solving boat problem (high level):
+
;New state variables (all shared)
−
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.
+
{{c|<pre>lock = new Lock()
−
 
+
boatIsland = Island.A
−
There are the following state variables:
 
−
lock L = new lock
 
−
boatIsland = A
 
 
boatPilot = null
 
boatPilot = null
 
boatDeparting = false
 
boatDeparting = false
 
boatLookingForChild = false
 
boatLookingForChild = false
−
numChildrenOnB = 0
+
childCounter = 0
−
numAdultsOnA = 0
+
adultCounterA = 0
−
condition childrenWaitingOnA, adultsWaitingOnA, childrenWaitingOnB, adultsWaitingOnB, waitingToRide, waitingToPilot //separate condition variables all on lock L
+
adultCounterB = 0
 +
sleepingChildren = 0
 +
waiters = 0
  
−
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.
+
pipe = new Communicator()</pre>}}
  
−
Child Algorithm (with Pseudocode):
+
Condition variables, all on lock: {{c|childrenWaitingOnA}}, {{c|adultsWaitingOnA}}, {{c|childrenWaitingOnB}}, {{c|adultsWaitingOnB}}, {{c|waitingToRide}}, {{c|waitingToPilot}}
−
Each child will begin running on island A and try to acquire the lock.
 
  
−
childItinerary () {
+
In addition, each thread has a local variable to keep track of which island the person is currently on.
−
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.
+
;Implementation overview
 +
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. 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.
  
−
if the child is on island A and the boat is not departing {
+
;Implementation details
−
if the boat does not have a pilot and the boat is not looking for a passenger { //first move of pattern
+
Each child will begin running on Oahu and try to acquire the lock.
−
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.
+
If the child is on Oahu and the boat is available for use (i.e. {{c|<nowiki>boatLookingForChild == false</nowiki>}} and {{c|<nowiki>boatPilot == null</nowiki>}} and {{c|<nowiki>boatDeparting == false</nowiki>}}), it will assume the role of pilot and set the {{c|boatLookingForChild}} variable to true, then going to sleep on {{c|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 {{c|waitingToRide}}. He then increments the {{c|childCounter}}, wakes up the passenger child so that he can ride to Molokai, and goes back to sleep.
  
−
else if (boatPilot == CHILD and boatLookingForChild) {
+
The passenger, upon arrival at Molokai, increments the {{c|childCounter}} and speaks to {{c|begin()}} the number of children on Molokai. The child passenger then wakes up the pilot and goes to sleep on {{c|childrenWaitingOnB}}. Once the pilot child reawakens, he returns to Oahu, decrementing {{c|childCounter}} before departure.
−
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.
+
Upon return to Oahu, if the number of adults on Oahu (according to {{c|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 {{c|childCounter}}), the pilot wakes up the adults waiting on A, puts himself to sleep on {{c|childrenWaitingOnA}}, releases the lock after wake, and restarts the looop. Otherwise, he simply releases the lock and restarts the loop.
  
−
} else if (myIsland == boatIsland == B and !boatDeparting) {
+
The adults all begin on Oahu, try to acquire the lock, and each initially increment {{c|adultCounterA}}.
−
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.
+
If the adult is on Oahu, the boat is available for use, and there is at least one child on Molokai according to {{c|childCounter}}, the adult pilots to Molokai. Otherwise, he wakes a child on {{c|childrenWaitingOnA}} and goes to sleep on {{c|adultsWaitingOnA}}.
  
−
else {
+
If the adult does pilot across, he increments {{c|adultCounterB}} upon arrival to Molokai, speaks to {{c|begin()}} the value of {{c|childCounter}}, wakes up a child from {{c|childrenWaitingOnB}} so that he can pilot the boat back to Oahu, and then puts himself to sleep on {{c|adultsWaitingOnB}}.  The adult is now done and will never be woken again.
−
if (myIsland == A)
 
−
sleep and wait to ride
 
−
else
 
−
sleep on island B;
 
−
}
 
  
−
Adult Algorithm (with Pseudocode):
+
If a child is sleeping on Molokai on {{c|childrenWaitingOnB}} and gets woken by an adult, he will decrement {{c|childCounter}} and pilot himself back to Oahu. Upon arrival, he releases the lock and restarts the loop.
−
The adults all begin on island A and acquire the lock.  The adults also increment a global counter numAdultsOnA.
 
  
−
adultItinerary() {
+
For both adults and children, if the boat is busy or inaccessible as determined by the state of the {{c|boatPilot}}, {{c|boatDeparting}}, {{c|boatLookingForChild}}, and {{c|boatIsland}} variables given the person's current location, each will go back to sleep on the appropriate condition variable (i.e. {{c|childrenWaitingOnA}} for child threads on Oahu).
−
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.
+
;{{c|begin()}} behavior
−
 
+
{{c|begin()}} creates the required number of child and adult threads and then forks them. Then, it begins to {{c|listen()}} on the one shared Communicator ({{c|pipe}}). When {{c|begin()}} receives a message, it checks the "spoken" number as well as {{c|adultCounterB}} against the number of spawned threads to see if everyone is across yet.
−
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.  
 
  
 +
The reason that it does not check the value of {{c|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 {{c|begin()}} from knowing the true number of children on Molokai.
  
 
===Testing===
 
===Testing===
Line 306: Line 373:
  
 
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.
 
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.
 +
 +
==Design questions==
 +
;Why is it fortunate that we did not ask you to implement priority donation for semaphores?
 +
:Currently, each time a thread acquires a lock or calls {{c|join()}}, we know who is currently holding the resource. This allows us to donate priority to this single resource if a higher-priority thread begins waiting on it. With semaphores, this is not possible for initial values greater than 1, because the last thread to successfully "acquire" the semaphore will not necessarily be the one with the lowest priority. The implementation would need to change to keep track of all threads that are actually using the semaphore currently and thus be able to determine which of those has the lowest priority and needs to "receive" a donation.
 +
;A student proposes to solve the boats problem by use of a counter, AdultsOnOahu. Since this number isn't known initially, it will be started at zero, and incremented by each adult thread before they do anything else. Is this solution likely to work? Why or why not?
 +
:No, because there is no way of enforcing the fact that everyone will increment it before they do anything else.

Latest revision as of 03:51, 20 February 2023

KThread.join()

Implementation

New state variables

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

Implementation details
  • 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 then verify that threadB executes contiguously to completion before threadA resumes its execution, as evidenced by the sequence of printed statements.
  • Have a thread attempt to join() to itself, call join() on a second thread multiple times, and attempt to call join() on a third finished thread (all separately). These should all return immediately as this is the expected behavior.
  • Test 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 on the joinedOnMe queue;
    Sleep (existing);
}

Condition2.java

Implementation

New state variables

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

Implementation details
  • In the sleep() method, we disable interrupts, the 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, the thread attempts to reacquire the corresponding lock and interrupts are re-enabled.
  • The wake() method disables interrupts and retrieves the next thread from waitQueue. If the thread returned is not null, that thread is readied. Finally, the interrupts are re-enabled.
  • The wakeAll() method also disables the interrupts and stores the next thread from waitQueue as a KThread variable, nextThread. While nextThread is not null, the method will ready that thread and set nextThread to the next thread from waitQueue. This procedure continues until there are no more threads in waitQueue.

Testing

  • Condition2.java was tested using a class called CondThread, which implements Runnable. The class is instantiated with an integer iterations, a lock, a Condition2 variable to call sleep() on, and a Condition2 variable to call wake() on. When a CondThread runs, it acquires the lock, then enters a for-loop of 6 iterations. On each iteration, the thread will print out a debug statement noting that the current thread is on the ith iteration. When the loop iteration number is equal to iterations, threads can take one of three actions:
    1. If the thread's ID is '0', then that thread is the waking thread and calls wake() on its second condition variable.
    2. If the thread's ID is '0-all', it calls wakeAll() on its second condition variable
    3. Otherwise, it goes to sleep on its first condition variable. Using the output, we verify that the threads all run in the correct order and all execute to completion.
  • 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.
  • Sleep several threads on several various condition variables. Verify via console print statements that the proper threads wake up at the correct times according to which condition variable they were sleeping on.
  • Sleep several threads on the condition variable, then have one final thread wake them all with wakeAll(). Verify that all threads have woken up via console print statements.
  • Sleep several threads on several various condition variables, then have one thread call wakeAll() on one of the condition variables. Verify via console print statements that all the threads put to sleep on that condition variable wake up and that only those threads wake up.

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 the first thread and wake it;
    Re-enable interrupts; 
}
 
wakeAll() {
    Disable interrupts;
    While there are threads on the wait queue:
        Remove the first thread and wake it;
    Re-enable interrupts; 
}

waitUntil()

Implementation

New state variables

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 a KThread and its associated wakeTime. The PriorityQueue waitingThreads will be populated with instances of this inner class.

Implementation details
  • waitUntil() creates a new instance of waitingThread, which will associate the current thread with the given time argument. It will then add this waitingThread instance to the PriorityQueue and put the current thread to sleep. This method is atomic.
  • timerInterrupt() peeks at the first WaitingThread in the waitQueue and checks 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 wake 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

New state variables
Lock lock = new Lock()
int activeSpeakers = 0
int waitingSpeakers = 0
int activeListeners = 0
int waitingListeners = 0
Condition speakers
Condition listeners
Condition return
Implementation details
  • 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, the counterpart action will also attempt to wake 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.

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.

To be able to perform these tests, we created a number of helper classes which implement Runnable. MassSpeaker and MassListener are designed to be run by a single thread each. These will 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.

Pseudocode

  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 waiting to return;
           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 waiting to return;
           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
  • PriorityQueue.holder - this ThreadState corresponds to the holder of the resource signified by the
  • PriorityQueue.waitQueue - an ArrayList of ThreadStates waiting on this resource. Unsorted.
  • PriorityQueue.dirty - set to true when a new thread is added to the queue, or any of the queues in the waitQueue flag themselves as dirty.
  • PriorityQueue.effective - the cached highest of the effective priorities in the waitQueue. This value is invalidated while dirty is true.
  • ThreadState.myResources - collection of PriorityQueues that signify the Locks or other resources that this thread currently holds.
  • ThreadState.waitingOn - collection of PriorityQueues corresponding to resources that this thread has attempted to acquire but could not.
  • ThreadState.effective - the cached effective priority of this thread. this value is invalidated when dirty is true
  • ThreadState.dirty - set to true when this thread's priority is changed, or when one of the queues in myResources flags itself as dirty.
Implementation overview

The idea here is that Threads keep track of the PriorityQueues corresponding to both the resources that they are currently holding and those that they want to hold. We can do this via hooks in PriorityQueue's waitForAccess(), acquire, and nextThread methods.

Once we have this, every time a thread tries to wait on a queue, or takes control of a queue, we can tell the queue that its overall effective priority may have changed, and it can, in turn, tell the thread that currently holds the resource that one of the PriorityQueues it holds may have had its priority changed. That holder can in turn tell the same to the PriorityQueues that it is waiting on, and so forth. Eventually a thread, which is holding a resource that everyone needs, but has a low priority, will be marked for priority recalculation and thus priority escalation.

At this point, recalculation is simple. The effective priority of a thread is the maximum of its own actual priority and the priorities of all the PriorityQueues that it currently holds. The effective priority of a PriorityQueue is the maximum effective priority of all the threads waiting on it (if the queue is supposed to donate priority), and so on and so forth in a mutually recursive manner.

Implementation details
  • PriorityQueue.nextThread()
This method retrieves and removes the highest priority thread off the Priority-Time ArrayList. It then flags the previous holder of this resource as dirty, and removes the queue from that holder's resource list. It then sets the retrieved thread to this queue's new holder, and flags that thread as dirty as well.
  • PriorityQueue.acquire(KThread thread)
Sets the holder of this queue to the specified thread, bypassing the queue. Resets previous holder and sets dirty flags as in nextThread().
  • PriorityQueue.pickNextThread()
Simply retrieves the highest priority thread off this queue.
  • PriorityQueue.setDirty()
Set this queue's dirty flag, and calls setDirty on the current holder of this thread.
  • PriorityQueue.getEffectivePriority()
If this queue is dirty, returns the maximum of each of the ThreadStates.getEffectivePriority() in this queue. Those calls in turn become mutually recursive when they call getEffectivePriority() on the PriorityQueues in their myResources.
  • ThreadState.setPriority()
This method will change the actual priority of the thread associated with the ThreadState. It then calls setDirty() on this thread.
  • ThreadState.setDirty()
Sets the dirty flag on this thread, then calls setDirty() on each of the PriorityQueues that the thread is waiting for. Mutually recursive.
  • ThreadState.getEffectivePriority
Like the analogue of this function in PriorityQueue, returns the (cached) priority if this thread is not dirty; otherwise, recalculates by returning the max of the effective priorities of the PriorityQueues in myResources.

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.
  • Create complex set of interdependent threads and multiple locks, verify that execution order is correct.

Pseudocode

PriorityQueue
public void waitForAccess(KThread thread)
    add this thread to my waitQueue
      thread.waitForAccess(this)
  
public void acquire(KThread thread) 
    if I have a holder and I transfer priority, remove myself from the holder's resource list
    thread.acquire(this)
  
public KThread nextThread() 
    if I have a holder and I transfer priority, remove myself from the holder's resource list
    if waitQueue is empty, return null
      ThreadState firstThread = pickNextThread();
      remove firstThread from waitQueue
      firstThread.acquire(this);
    return firstThread

public int getEffectivePriority()
    if I do not transfer priority, return minimum priority
    if (dirty)
        effective = minimum priority;
        for each ThreadState t in waitQueue
            effective = MAX(effective, t.getEffectivePriority())
        dirty = false;
    return effective;

  public void setDirty()
      if I do not transfer priority, there is no need to recurse, return
      dirty = true;
      if I have a holder, holder.setDirty()
  
protected ThreadState pickNextThread() 
      ThreadState ret = null
      for each ThreadState ts in waitQueue
         if ret is null OR ts has higher priority/time ranking than ret
            set ret to ts
    return ret;
ThreadState
public int getPriority()
    return non-donated priority.

public int getEffectivePriority()
    if (dirty) {
          effective = non-donated priority
        for each PriorityQueue pq that I am currently holding
          effective = MAX(effective, pq.getEffectivePriority)
    }
    return effective;

public void setPriority(int priority)
    set non-donated priority to the argument
    setDirty();

  public void setDirty()
      if already dirty return
      dirty = true;
      for each of the PriorityQueues pq I am waiting on,
        pq.setDirty

public void waitForAccess(PriorityQueue waitQueue)
    add the waitQueue to my waitingOn list
    if the waitQueue was previously in myResources, remove it and set its holder to null.
      if waitQueue has a holder, set the queue to dirty to signify possible change in the queue's effective priority

public void acquire(PriorityQueue waitQueue)
    add waitQueue to myResources list
    if waitQueue was in my waitingOn list, remove it
    setWaitQueue's holder to me
    setDirty();

Boat.java

Implementation

New state variables (all shared)
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.

Implementation overview

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. 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.

Implementation 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.

Design questions

Why is it fortunate that we did not ask you to implement priority donation for semaphores?
Currently, each time a thread acquires a lock or calls join(), we know who is currently holding the resource. This allows us to donate priority to this single resource if a higher-priority thread begins waiting on it. With semaphores, this is not possible for initial values greater than 1, because the last thread to successfully "acquire" the semaphore will not necessarily be the one with the lowest priority. The implementation would need to change to keep track of all threads that are actually using the semaphore currently and thus be able to determine which of those has the lowest priority and needs to "receive" a donation.
A student proposes to solve the boats problem by use of a counter, AdultsOnOahu. Since this number isn't known initially, it will be started at zero, and incremented by each adult thread before they do anything else. Is this solution likely to work? Why or why not?
No, because there is no way of enforcing the fact that everyone will increment it before they do anything else.
Retrieved from "http://www.lensovet.net/~sysadmin/w/index.php?title=Computer_Science/162/proj1&oldid=24275"