=={{c|KThread.join()}}==

;New state variables{{c|KThread}} has a new state variable {{c|joinedOnMe}}, a {{c|ThreadQueue}}. , and {{c|isJoined}}, a {{c|boolean}} ;Implementation details

* ThreadA {{c|threadA}} prints out a few statements, calls ThreadB{{c|threadB.join()}}, then prints out a few more statements. ThreadB {{c|threadB}} also prints out a series of statements. We want to then verify that ThreadB {{c|threadB}} executes contiguously to completion before ThreadA {{c|threadA}} resumes its execution, as evidenced by the sequence of printed statements. * Have a thread attempt to {{c|join ()}} to itself, and call {{c|join() }} on the same a second thread multiple times, and also attempt to call {{c|join ()}} on a third finished thread(all separately). These should all return immediately because as this is the join condition was not satisfiedexpected behavior.* Have 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.

{{c|<pre>join() {

Re-enable interrupts;

}</pre>}}  {{c|<pre>finish(){

Ready the thread in on the joinedOnMe queue;

}</pre>}}

==ConditionCondition2.java==

;New state variablesCondition2 has a new state variable {{c|waitQueue}}, a {{c|ThreadQueue }} with {{c|transferPriority }} flag set to false.  ;Implementation details* In the {{c|sleep() }} method, we disable interrupts, the calling (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, interrupts are re-enabled and the thread attempts to reacquire the condition corresponding lockand interrupts are re-enabled. * The {{c|wake() }} method disables interrupts and checks if retrieves the next thread from {{c|waitQueue is empty}}. If it the thread returned is notnull, the method readies the first that thread in the waitQueueis readied. Finally, wake() the interrupts are re-enables interruptsenabled. * 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 call wake() as long as ready that thread and set {{c|nextThread}} to the next thread from {{c|waitQueue}}. This procedure continues until there are no more threads still in the {{c|waitQueue}}.

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

Sleep{{c|<pre>sleep(){ Disable Interrupts; Add current thread to wait queue; Release the lock; Put the current thread to sleep; Acquire the lock; Re-enable Interrupts;}</pre>}}

Wake(){AssertTrue (lock held by current thread);Disable interrupts;If there is a thread on the wait queue, remove and wake it;Re-enable interrupts; } WakeAll{c|<pre>wakeAll(){ Disable interrupts; While there are threads on the wait queue, call : Remove the first thread and wake().it; Re-enable interrupts; }</pre>}}

==WaitUntil()=====;Implementation===Alarm has a new instance variable, waitingThreads, which is a Java PriorityQueue of waiting threads with the target wake time as their priority. It also contains a new inner class named waitingThread, which contains a reference to the KThread and its associated wakeTime.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.

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

We add new ;New state variables (a lock, four counters, and two condition variables): {{c|<pre>Lock lock = new Lock()int activeSpeakers= 0int waitingSpeakers= 0int activeListeners= 0int waitingListeners= 0Condition speakers

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’tisn'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, a the counterpart action will also attempt to wake sleeping ''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 '''both''' counterparts in the exchange have returned.

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

 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.

Sleep as an active speakerwaiting to return;

Sleep as an active listenerwaiting to return;

;New state variables are shown by the class they appear in: * {{c|PriorityQueue: KThread lastThread.holder}} - this ThreadState: int donatedPriorityPriorityScheduler: TreeSet¬Ђlong (time), KThread¬ї waitQueue* nextThread()* This method retrieves and removes corresponds to the highest priority thread off the Priority-Time set. It calculates this thread's priority based on priorities holder of the threads waiting in resource signified by the queue* {{c|PriorityQueue. It resets the priority waitQueue}} - an ArrayList of thread previously in the lastThread position to its original priorityThreadStates waiting on this resource. The thread to be returned is also set as the new lastThreadUnsorted. * pickNextThread()* This method retrieves the first thread from the Priority{{c|PriorityQueue.dirty}} -Time set without removing it from the set. It creates to true when 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, added to the method returns the sum. Otherwisequeue, the max priority 7 is returned.* setPriority() This method will change the actual priority or any of the thread associated with queues in the ThreadState. The effective priority of lastThread must also be by difference between current threads priority and new prioritywaitQueue flag themselves as dirty. * waitForAccess(priorityQueue) This method puts thread associated with the threadState onto the Priority-Time set{{c|PriorityQueue. 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 cached highest of the associated thread based on effective priorities of the threads waiting in the queuewaitQueue. It resets the priority of the thread previously in the lastThread position to its original priority. The associated thread This value is invalidated while dirty is set as the new lastThreadtrue.

Algorithm for solving boat problem ;New state variables (high levelall 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. There are the following state variables:{{c|<pre>lock L = new lockLock()boatIsland = Island.A

numChildrenOnB childCounter = 0numAdultsOnA adultCounterA = 0condition childrenWaitingOnA, adultsWaitingOnA, childrenWaitingOnB, adultsWaitingOnB, waitingToRide, waitingToPilot //separate condition variables all on lock LadultCounterB = 0sleepingChildren = 0Each thread will attempt to acquire the lock (which represents the boat). If the thread can performs one of its assigned tasks, then it executes it. Otherwise it will go to sleep. Child Algorithm (with Pseudocode):Each child will begin running on island A and try to acquire the lock. childItinerary () { myIsland waiters = A while (true) { acquire L If the child is on island A and the boat is available for use, then it will ask for a passenger child and go to sleep. Once a passenger child is found, the pilot will be awoken by the passenger child and pilot them to island B. He now increments the global counter numChildrenOnB. He wakes up the passenger child so that he can be moved to island B as a passenger and goes to sleep. The passenger, increments the numChildrenOnB counter and wakes up the pilot. Once the pilot child reawakens, he will speak to begin(), telling the begin thread the number of children currently on island B. He then returns to island A and decrements numChildrenOnB. If the number of adults on island A (according to numAdultsOnA) is not 0, he wakes up the adults waiting on A, puts himself to sleep on the children waiting on A condition variable, and releases the lock (after wake). Otherwise, he simply releases the lock.

if the child is on island A and the boat is not departing { if the boat does not have a pilot and the boat is not looking for a passenger { //first move of pattern boatLookingForChild = true; boatPilot = CHILD; sleep and wait to pilot; pilot to B; wake up passenger; increment number of children on B; boatIsland = B; boatLookingForChild pipe = false; sleep and wait to pilot;speakToBeginnew Communicator()decrement num of children on Bchild pilots to A boatIsland = A if number of adults on A != 0 {wake adults waiting on A; sleep and wait on island A; </pre>}release L; continue;}

If the child is Condition variables, all on island A and the boat is asking for a passengerlock: {{c|childrenWaitingOnA}}, the child will set the boat as departing{{c|adultsWaitingOnA}}, wake up the pilot child{{c|childrenWaitingOnB}}, and go to sleep. After the pilot child is awoken by the pilot{{c|adultsWaitingOnB}}, 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){{c|waitingToRide}}, puts the children waiting on B to sleep, and releases the lock.{{c|waitingToPilot}}

else if (boatPilot == CHILD and boatLookingForChild) { boatDeparting = true; wake In addition, each thread has a pilot; sleep and wait local variable to ride; child ride to B; increment number keep track of children which island the person is currently on B; myIsland = B; boatDeparting = false; wake a pilot; sleep on island B; release L; continue;}.

;Implementation 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 is on island B with 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 is not in use). If the thread can perform one of the tasks fitting for the current state of the world, it executes it. Otherwise, he it will pilot himself back go to sleep on the condition variable corresponding to A its current role and decrement the counter numChildrenOnBlocation.

} else if (myIsland == boatIsland == B and !boatDeparting) {;Implementation detailsdecrement num of children Each child will begin running on B child pilots Oahu and try to A; myIsland = boatIsland = A; boatPilot = null; release L; continue;}acquire the lock.

If none 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 these conditions are metpilot 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 is put and pilot them both to Molokai, while the passenger goes to sleep as waiting on his respective island{{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 The passenger, upon arrival at Molokai, increments the { if {c|childCounter}} and speaks to {{c|begin(myIsland == A)sleep }} the number of children on Molokai. The child passenger then wakes up the pilot and wait goes to ride elsesleep on island B;{{c|childrenWaitingOnB}}. Once the pilot child reawakens, he returns to Oahu, decrementing {{c|childCounter}}before departure.

Adult Algorithm Upon return to Oahu, if the number of adults on Oahu (with Pseudocodeaccording to {{c|adultsWaitingOnA}}):The 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 all begin waiting on island A , puts himself to sleep on {{c|childrenWaitingOnA}}, releases the lock after wake, and acquire restarts the looop. Otherwise, he simply releases the lock. The adults also increment a global counter numAdultsOnAand restarts the loop.

adultItinerary() The adults all begin on Oahu, try to acquire the lock, and each initially increment { myIsland = A increment numAdultsOnA while(true) { acquire L;c|adultCounterA}}.

If the adult is on island AOahu, the boat is available for use , and the last boat pilot was a there is at least one childon Molokai according to {{c|childCounter}}, the adult pilots to island BMolokai. He then Otherwise, he wakes up one a child waiting on island B so that he can pilot the boat back to A. The adult is now done with its task {{c|childrenWaitingOnA}} and goes to sleep, thus releasing the lock for other threads to useon {{c|adultsWaitingOnA}}.

if If the adult does pilot across, he increments {{c|adultCounterB}} upon arrival to Molokai, speaks to {{c|begin(myIsland == boatIsland == A and !boatDeparting and boatPilot == CHILD and !boatLookingForChild) }} the value of {{ boatPilot = ADULT; adult pilots to B; boatIsland = myIsland = B; wake c|childCounter}}, wakes up a child sleeping on B; from {{c|childrenWaitingOnB}} so that he can pilot the boat back to Oahu, and then puts himself to sleep on B;{{c|adultsWaitingOnB}}. continue;}The adult is now done and will never be woken again.

Otherwise 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 adult puts lock and restarts the adults on his respective island to sleeploop.

else For both adults and children, if the boat is busy or inaccessible as determined by the state of the {{c|boatPilot}}, {{c|boatDeparting}}, {{ if (myIsland == A)c|boatLookingForChild}}, and {{c|boatIsland}} variables given the person's current location, each will go back to sleep on A; elsesleep the appropriate condition variable (i.e. {{c|childrenWaitingOnA}} for child threads on B;}Oahu).

In ;{{c|begin(), each time }} behavior{{c|begin()}} creates the required number of child and adult threads speaks and then forks them. Then, it begins to it, {{c|listen()}} on the one shared Communicator ({{c|pipe}}). When {{c|begin() will check if }} receives a message, it checks the "spoken" number of children on B is equal to as well as {{c|adultCounterB}} against the number of child spawned threads that it forked. Since all adults must be on B before number of children increases, this tells us that we are doneto see if everyone is across yet.