This can be used for testing out wiki markup. Enjoy.
Questions 1 - Thread.Join()
Implementation: KThread has a new state variable joinedOnMe, a ThreadQueue.
If (CurrentThread == self or joinedOnMe != null){
Return; // conditions for join not satisfied
} else if (status == Finished){ Return; } Else { currentThread.sleep; joinedOnMe = currentThread; }
Finished(){ … joinedOnMe.ready(); }
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 check that ThreadB executes contiguously to completion before ThreadA resumes its execution.
Question 2 - Condition2
Implementation: Condition2 has a new state variable waitQueue, a ThreadQueue of Threads transferPriority false. In the sleep() method we add the calling (current) thread to the waitQueue of threads. After the thread releases its condition lock, we disable interrupts and it is put to sleep. When it wakes up, interrupts are re-enabled and the thread attempts to reacquire the condition lock.
In the wait() method, if the waitQueue is not empty we ; Sleep(){ disableInterrupts waitQueue.waitforaccess(currentThread) // WAITFORACCESS conditionLock.release currentThread.sleep conditionLock.acquire enableInterrupts } Wake(){ Disable interrupts Nt = waitqueue .nextthread
If (nt is not null){
Ready nt } Re-enable interrupts
wakeAll while (waitqueue.nextthread != null) wake()
Testing: DO MOE
Question 3 - WaitUntil()
Implementation: Alarm has a new sorted PriorityQueue waitingThreads to keep track of when waiting threads should be woken, sorted on their wake times from lowest to highest. It also has a new inner class named waitingThread which contains a reference to the KThread and its associated wakeTime(long).
waitUntil(time){ WaitingThread wt = new WaitingThread (currentThread, currentTime + time); waitingThreads.add (wt); currentThread.sleep; }
timerInterrupt(){ while (WaitingThreads.peek().time <= currentTime){ WaitingThreads.pop().wake(); }
Class WaitingThread (){ KThread currentThread; Long time; }
Testing: For or while loop that prints out a series of statements. Check that statements for different threads are all printed contiguously according to their respective wake times.
Question 4 - Communicator
Implementation: We recognize the invariant that there will always be an unequal amount of speakers and listeners, because speakers and listeners are almost immediately paired off and return. The S/L on the larger queue will acquire lock, perform their actions, wake opposing queue and immediately return (if they slept they would be put on the end of the queue). S/L on smaller queue will acquire lock, perform their actions, sleep, and once woken up again by opposing queue, return.
Special condition for 1 on 1. Use a Boolean flag which indicates a transfer is in progress. The 2nd S/L will set the flag to true, perform its actions and wake the 1st S/L; any intruding 3rd S/L will not attempt to acquire the lock as long as this flag is true—this 3rdSL will sleep in its respective queue. The 1st S/L will be woken up by the 2nd S/L, set the Boolean to false, and return.
Testing: DO ME.
Question 5 - Priority Scheduler
PriorityQueue
NextThread get most important member off Priority and Time queue. LastThread variable is set when NextThread or acquire is called. Also triggers recalculation on popped off LastThread and popped off thread which becomes the LastThread.
PickNextThread inspect first thread without removing it and return ThreadState.
New Instance variable of effectivepriority GetEffectivePriority returns cached effective priority of a thread capped @ maxpriority
SetPriority Change actual priority of current thread Change effective priority of lastthread by difference between current threads priority and new priority.
If set priority is called on a thread with effective priority must make sure effective priority is still present, ex: 5+5, set priority to 0, thread should still have 5.
Make sure to check for transfer priority—procedure is different: ex: always return regular priority if transferpriority== false
PriorityScheduler.waitforaccess(thread)
ThreadState.WaitForAccess(priorityQueue)
Put thread onto time&priority wait queue. Sorts all by priority , time.
Recalculates effective priority.
Acquire recalculate LastThread effective priority. Set CurrentThread = LastThread and recalculate priority.
Recalculation: iterate through structure and add up all priorities.
When thread calls threadstate.acquire you get donation of all threads on waitqueue
Three things that change your priority: when another thread is added to queue waiting on you, when you acquire, when you release
Use treeset to keep track of all threads sorted on time
Every thread has a cached effective priority integer Set when acquire / next thread Wait for thread doesn’t call calculate priority on itself, calls calculate priority on current thread Waitforaccess add to something that keeps track of priority and time
TESTING: DO ME.
Question 6 - Boat
CHILD who thinks he’s the last person must sleep, but communicate to begin and say he’s done. In that case, pilot must go to sleep instead of immediately piloting back.
- of children seen == # of children gone
TESTING: set up some test cases i.e. 2 children 0 adults, 2 children 1 adult, 2 children 2 adults, 3 children 2 adults, 5 children 3 adults and work them out mathematically. then verify that threads execute the same solution.