1,277
edits
Changes
m
Re-enable interrupts;
We add a lock, four counters, and two condition variables.
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 New state variables(all shared)
Lensovet moved page CS/162/proj1 to Computer Science/162/proj1
=={{c|KThread.join()}}==
===Implementation===
;New state variables{{c|KThread}} has a new state variable {{c|joinedOnMe}}, a {{c|ThreadQueue}}. , and {{c|isJoined}}, a {{c|boolean}} ;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===
* {{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 {{c|join()}} to itself, call {{c|join()}} on the same (but different) 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.
Disable interrupts;
If (CurrentThread == self or isJoined) or (status is Finished) {
Return; // conditions for join not satisfied
} else {
}</pre>}}
==ConditionCondition2.java==
===Implementation===
;New state variables
===Testing===
* {{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===
{{c|<pre>Sleepsleep() {
Disable Interrupts;
Add current thread to wait queue;
}</pre>}}
{{c|<pre>Wakewake() {
AssertTrue (lock held by current thread);
Disable interrupts;
If there is a thread on the wait queue, remove : Remove the first thread and wake it;
Re-enable interrupts;
}</pre>}}
{{c|<pre>WakeAllwakeAll() {
Disable interrupts;
While there are threads on the wait queue, call : Remove the first thread and wake().it;
Re-enable interrupts;
}</pre>}}
==WaitUntil{{c|waitUntil()}}==
===Implementation===
;New state variablesAlarm 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 waitingThread{{c|WaitingThread}}, which contains a reference to the a {{c|KThread }} and its associated {{c|wakeTime}}. The {{c|PriorityQueue waitingThreads}} will be populated with instances of this inner class. ;Implementation details* {{c|waitUntil() }} creates a new instance of {{c|waitingThread}}, which will associate the currentThread current thread with the give 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. * {{c|timerInterrupt() peek }} peeks at the first {{c|WaitingThread }} in the {{c|waitQueue }} and check 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.
===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 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===
{{c|<pre>waitUntil(time){
Disable interrupts;
Create a new waitingThread;
Sleep the current thread;
Re-enable interrupts;
} </pre>}}
{{c|<pre>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;
}</pre>}}
==Communicator==
===Implementation===
;New state variables
{{c|<pre>Lock lock = new Lock()
int activeSpeakers = 0
Condition return</pre>}}
;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 {{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.
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 classeswhich implement Runnable. {{c|MassSpeaker}} and {{c|MassListener}} are designed to be run by a single thread each. These runnables 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, {{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.
Wake a waiting listener;
}
Sleep as an active speakerwaiting to return;
AS--;
AL--;
Wake a waiting speaker;
}
Sleep as an active listenerwaiting to return;
AL--;
AS--;
==Priority Scheduler==
===Implementation===
;New state variables are shown * {{c|PriorityQueue.holder}} - this ThreadState corresponds to the holder of the resource signified by the class they appear in: * {{c|PriorityQueue: KThread lastThreadThreadState: int donatedPriorityPriorityScheduler: TreeSet¬Ђlong (time), KThread¬ї .waitQueue}} - an ArrayList of ThreadStates waiting on this resource. Unsorted.* nextThread()* This method retrieves and removes the highest priority thread off the Priority{{c|PriorityQueue.dirty}} -Time set. It calculates this to true when a new thread's priority based on priorities is added to the queue, or any of the threads waiting queues in the queuewaitQueue flag themselves as dirty.* {{c|PriorityQueue. It resets effective}} - the priority cached highest of thread previously the effective priorities in the lastThread position to its original prioritywaitQueue. The thread to be returned This value is invalidated while dirty is also set as the new lastThreadtrue. * pickNextThread()* This method retrieves the first thread from the Priority{{c|ThreadState.myResources}} -Time set without removing it from collection of PriorityQueues that signify the set. It creates a new ThreadState from Locks or other resources that this thread and returns the ThreadStatecurrently holds. * getEffectivePriority()* This method sums the associated thread's priority and its donatedPriority{{c|ThreadState. If waitingOn}} - collection of PriorityQueues corresponding to resources that this sum is less than 7, the method returns the sum. Otherwise, the max priority 7 is returnedthread has attempted to acquire but could not.* setPriority() This method will change the actual priority of the thread associated with the {{c|ThreadState. The effective}} - the cached effective priority of lastThread must also be by difference between current threads priority and new prioritythis thread. this value is invalidated when dirty is true* waitForAccess(priorityQueue) This method puts thread associated with the threadState onto the Priority{{c|ThreadState.dirty}} -Time set. The set sorts all threads by to true when this thread's priorityis changed, then timeor when one of the queues in myResources flags itself as dirty. ;Implementation overviewThe associated thread will then be put to sleep. This method will also recalculate effective priority: it will add up all priorities idea here is that {{c|Thread}}s keep track of the threads in {{c|PriorityQueue}}s corresponding to both the set resources that they are currently holding and donate it those that they want to the lastThreadhold.* acquireWe can do this via hooks in {{c|PriorityQueue}}'s {{c|waitForAccess()}}, {{c|acquire}}, and {{c|nextThread}} methods.* This method calculates the priority of the associated Once we have this, every time a thread based tries to wait on priorities a queue, or takes control of a queue, we can tell the threads waiting queue that its overall effective priority may have changed, and it can, in turn, tell the queue. It resets thread that currently holds the priority resource that one of the thread previously {{c|PriorityQueue}}s it holds may have had its priority changed. That holder can in turn tell the lastThread position same to its original prioritythe {{c|PriorityQueue}}s that it is waiting on, and so forth. The associated Eventually a thread , which is set as the new lastThreadholding 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===
* 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
{{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==
===Implementation===
{{c|<pre>lock = new Lock()
boatIsland = Island.A
In addition, each thread has a local variable to keep track of which island the person is currently on.
;Basic ideaImplementation overviewIf 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.
;Algorithm Implementation details
Each child will begin running on Oahu and try to acquire the lock.
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.