The idea here is * {{c|ThreadState.myResources}} - collection of PriorityQueues that signify the Locks or other resources that Threads keep track this thread currently holds.* {{c|ThreadState.waitingOn}} - collection of the PriorityQueues corresponding to both the resources that they are currently holding and those that they want this thread has attempted to holdacquire but could not.* {{c|ThreadState.effective}} - the cached effective priority of this thread. this value is invalidated when dirty is true* {{c|ThreadState. We can do dirty}} - set to true when this via hooking PriorityQueuethread's waitForAccesspriority is changed, acquire, and nextThreador when one of the queues in myResources flags itself as dirty.

Once we have this, every time a thread tries ;Implementation overviewThe idea here is that {{c|Thread}}s keep track of the {{c|PriorityQueue}}s corresponding to wait on a queue, or takes control of a queue, we can tell that queue that its overall effective priority may have changed, and it can in, turn tell both the thread resources that they are currently holds the resource holding and those that one of the PriorityQueues it holds may have had its priority changedthey want to hold. That holder We can do this via hooks in turn tell the same to the PriorityQueues that it is waiting on{{c|PriorityQueue}}'s {{c|waitForAccess()}}, {{c|acquire}}, and so on. Eventually a thread holding a resource that everyone needs, but with a low priority will be marked for priority recalculation{{c|nextThread}} methods.

At Once we have this point recalculation is simple. The effective priority , every time a thread tries to wait on a queue, or takes control of a thread is queue, we can tell the maximum of queue that its own actual overall effective priority may have changed, and it can, in turn, tell the priorities of all the PriorityQueues thread that it currently holds. The effective priority of a PriorityQueue is the maximum effective priority resource that one of all the threads waiting on it (if the queue is supposed to donate priority), and so on and so forth in this mutually recursive manner. ;New state variables*'''PriorityQueue''' – {{c|ThreadState holder, ArrayList<ThreadState> waitQueue, int effective, boolean dirtyPriorityQueue}}<br />*'''ThreadState''' – s it holds may have had its priority changed. That holder can in turn tell the same to the {{c|int effective, boolean dirty, HashSet<PriorityQueue> myResources, WaitingOn}}<br /> PriorityQueue.holder - this ThreadState corresponds to the holder of the resource signified by the PriorityQueue.waitQueue - an ArrayList of ThreadStates s that it is waiting on this resource. Unsorted.PriorityQueue, and so forth.dirty - set to true when Eventually 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 which is invalidated while dirty is true. ThreadState.myResources - collection of PriorityQueues holding a resource that signify the Locks or other resources that this thread currently holds.ThreadState.waitingOn - collection of PriorityQueues corresponding to resources that this thread everyone needs, but has attempted to acquire but could not.ThreadState.effective - the cached effective a low priority, will be marked for priority of this thread. this value is invalidated when dirty is trueThreadState.dirty - set to true when this thread's recalculation and thus priority is changed, or when one of the queues in myResources flags itself as dirtyescalation.

* {{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 ThreadStates{{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 myResrouces{{c|myResources}}.* {{c|ThreadState.setPriority() }}* :This method will change the actual priority of the thread associated with the {{c|ThreadState}}. It then does 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 PriorityQueues {{c|PriorityQueue}}s that the thread is waiting for, does setDirty on them. 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, otherwise recalculates by returning the max of the effective priorities of the PriorityQueues {{c|PriorityQueue}}s in {{c|myResources}}.

;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 int getPriorityvoid setDirty() if already dirty return non-donated priority. public int getEffectivePriority() if ( dirty) { effective = non-donated prioritytrue; for each PriorityQueue of the PriorityQueues pq that I am currently holdingwaiting on, effective = MAX(effective, pq.getEffectivePriority) } return effective;setDirty

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(); }