{{c|KThread}} has a new state variable {{c|joinedOnMe}}, a {{c|ThreadQueue}}., and {{c|isJoined}}, a {{c|boolean}}

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

Re-enable interrupts;

{{c|<pre>Sleepsleep() {

{{c|<pre>Wakewake() {

If there is a thread on the wait queue, remove : Remove the first thread and wake it;

{{c|<pre>WakeAllwakeAll() {

While there are threads on the wait queue, call : Remove the first thread and wake().it;

==WaitUntil{{c|waitUntil()}}==

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

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

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

{{c|<pre>waitUntil(time){

}</pre>}}

 {{c|<pre>timerInterrupt(){

}</pre>}}

Sleep as an active speakerwaiting to return;

Sleep as an active listenerwaiting to return;

'''* {{c|PriorityQueue.holder}} - this ThreadState corresponds to the holder of the resource signified by the * {{c|PriorityQueue.waitQueue}} - an ArrayList of ThreadStates waiting on this resource. Unsorted.* {{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.* {{c|PriorityQueue''' – .effective}} - the cached highest of the effective priorities in the waitQueue. This value is invalidated while dirty is true. * {{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|KThread lastThreadThreadState.effective}}<br />- 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 overviewThe 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|int donatedPriorityPriorityQueue}}<br />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. '''PriorityScheduler''' – 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|ArrayList<KThread> waitQueuePriorityQueue}}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.

* {{c|PriorityQueue.nextThread()}}* :This method retrieves and removes the highest priority thread off the Priority-Time set{{c|ArrayList}}. It calculates then flags the previous holder of this threadresource as {{c|dirty}}, and removes the queue from that holder's priority based on priorities of the threads waiting in 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. It resets acquire(KThread thread)}}:Sets the priority {{c|holder}} of this queue to the specified thread previously in , bypassing the lastThread position to its original priorityqueue. The thread to be returned is also set Resets previous {{c|holder}} and sets {{c|dirty}} flags as the new lastThreadin {{c|nextThread()}}. * {{c|PriorityQueue.pickNextThread()}}* This method :Simply retrieves the first highest priority thread from the Priority-Time set without removing it from the setoff this queue.* {{c|PriorityQueue. It creates a new ThreadState from setDirty()}}:Set this thread queue's {{c|dirty}} flag, and returns calls {{c|setDirty}} on the ThreadStatecurrent holder of this thread. * {{c|PriorityQueue.getEffectivePriority()}}* This method sums the associated thread's priority and its donatedPriority. :If this sum queue is less than 7{{c|dirty}}, returns the method returns maximum of each of the sum{{c|ThreadState}}s{{c|.getEffectivePriority()}} in this queue. Otherwise, Those calls in turn become mutually recursive when they call {{c|getEffectivePriority()}} on the max priority 7 is returned{{c|PriorityQueues}} in their {{c|myResources}}.* {{c|ThreadState.setPriority() }}:This method will change the actual priority of the thread associated with the {{c|ThreadState}}. The effective priority of lastThread must also be by difference between current threads priority and new priorityIt then calls {{c|setDirty()}} on this thread. * waitForAccess{{c|ThreadState.setDirty(priorityQueue) }}This method puts :Sets the {{c|dirty}} flag on this thread associated with , then calls {{c|setDirty()}} on each of the threadState onto {{c|PriorityQueue}}s that the Priority-Time setthread is waiting for. The set sorts all threads by priority, then timeMutually recursive. The associated thread will then be put to sleep* {{c|ThreadState. This method will also recalculate effective prioritygetEffectivePriority}}: it will add up all priorities Like the analogue of the threads this function in {{c|PriorityQueue}}, returns the set and donate it to the lastThread.* acquire(cached)* This method calculates priority if this thread is not {{c|dirty}}; otherwise, recalculates by returning the priority max of the associated thread based on effective priorities of the threads waiting in the queue. It resets the priority of the thread previously {{c|PriorityQueue}}s in the lastThread position to its original priority. The associated thread is set as the new lastThread{{c|myResources}}.

FIXME;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>}}

;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