void XCHG (bool *X, bool *Y) {
bool tmp = *X;
*X = *Y;
*Y = tmp;
}
Show how XCHG can be used instead of test-and-set to implement the
acquire() and release() functions of the spinlock data structure described
in the "Synchronization" lecture.
struct lock {
bool isAvailable = TRUE;
}
void acquire (struct lock* p_lock) {
bool isAvailable = FALSE;
while (!isAvailable) {
XCHG (&(p_lock->isAvailable), &isAvailable);
}
}
void release (struct lock* p_lock) {
p_lock->isAvailable = TRUE;
}
Consider the following test program for an implementation of KThread.join in Nachos. It begins when the main Nachos thread calls KThread.selfTest. You do not need to know the details of how join is implemented. All you need to know is that when a parent thread calls join on a child thread, the parent does one of two things: (1) if the child is still running, the parent blocks until the child finishes (at which point the parent is placed on the ready queue); (2) if the child has finished, the parent continues to execute without blocking. Assume join uses a wait queue of some kind in its implementation.
private static class A implements Runnable {
A () {}
public void run () {
KThread t2 = new KThread (new B()).setName ("B");
System.out.println ("foo");
t2.fork ();
System.out.println ("far");
t2.join ();
System.out.println ("fum");
}
}
private static class B implements Runnable {
B () {}
public void run () {
System.out.println ("fie");
}
}
public static void selfTest() {
KThread t1 = new KThread (new A()).setName ("A");
System.out.println ("fee");
t1.fork ();
System.out.println ("foe");
t1.join ();
System.out.println ("fun");
}
i. Assume that the scheduler runs threads in FIFO order with non-preemptive scheduling (no preemptive time-slicing), and threads are placed on wait queues in FIFO order. Trace the execution of this program until it returns from selfTest and (a) write the sequence of context switches that occurred up this point, (b) write the output of the program, and (c) list the queues that the threads are on, and their relative order if more than one thread is on a queue.
Below is the sequence of lines of code executed by the threads.
The letter on the left identifies which thread is executing the
line of code. The code lines below are not part of the answer, we
are just including them to help illustrate how the program
executes:
m KThread t1 = new KThread (new A()).setName ("A");
m System.out.println ("fee");
m t1.fork (); // adds A to the ready queue
m System.out.println ("foe");
m t1.join (); // sleeps main on A's join queue
A KThread t2 = new KThread (new B()).setName ("B");
A System.out.println ("foo");
A t2.fork (); // adds B to the ready queue
A System.out.println ("far");
A t2.join (); // sleeps A on B's join queue
B System.out.println ("fie");
B (returns and finishes, wakes up A which joined on B)
A System.out.println ("fum");
A (returns and finishes, wakes up main which joined on A)
m System.out.println ("fun");
m (returns)
a. Context switches: main → A → B → A → main
b. Output: fee foe foo far fie fum fun // fine if you don't have the newlines for convenience
c. Thread queues when selfTest returns:
currentThread: main
readyQueue: (nothing, A & B have finished)
join wait queue: (nothing, A & B have finished)
ii. Next consider what happens if we add a call to yield in between lines (1) and (2) in selfTest:
[...]
System.out.println ("foe"); // line 1 for part (b)
currentThread.yield ();
t1.join (); // line 2 for part (b)
[...]
Adding the yield will change the sequence of context switches (e.g., increasing the number of context switches). For this particular example, though, the output does not change. While in general changing the sequence and number of context switches could easily change the output, in this case why is the output still the same?
Below is the modified sequence of lines of code executed by the
threads when we add the call to yield.
m KThread t1 = new KThread (new A()).setName ("A");
m System.out.println ("fee");
m t1.fork (); // adds A to the ready queue
m System.out.println ("foe");
m currentThread.yield (); // switches to head of ready queue (A), adding main back to the ready queue
A KThread t2 = new KThread (new B()).setName ("B");
A System.out.println ("foo");
A t2.fork (); // adds B to the ready queue
A System.out.println ("far");
A t2.join (); // sleeps A on B's join queue,
m t1.join (); // sleeps main on A's join queue
B System.out.println ("fie");
B (returns and finishes, wakes up A which joined on B)
A System.out.println ("fum");
A (returns and finishes, wakes up main which joined on A)
m System.out.println ("fun");
m (returns)
The sequence of context switches becomes:
main → A → main → B → A → main
There is one more context switch to main after A calls join, but when main continues it immediately calls join on A and context switches to B. In other words, the yield delays main's call to join on A, but in doing so it does not change the ordering of the statements that print. In particular, note that when A calls join on B, the ready queue consists of main (first) and then B. As a result, when A calls join the next thread that runs is main, not B.
You need only use pseudocode in your answers. It does not have to compile, and you can use any syntax or method names you are comfortable with (but it does have to look like code). Do not manipulate interrupts or invoke thread methods, or add methods to locks, threads, and condition variables. Also do not use data structures other than locks and condition variables to store references to threads.
a. Use pseudocode to implement a classic monitor that implements Barrier and coordinates threads using a condition variable. In a classic monitor, the locks are implicit: the compiler generates calls to acquire and release on the lock, so the programmer does not need to (the lock does not appear in the code).
monitor Barrier {
int called;
Condition barrier;
Barrier () {
called = 0;
barrier = new Condition();
}
void done (int needed) {
called++;
if (called == needed) {
barrier.wakeAll()
} else {
while (called < needed) {
barrier.sleep()
}
}
}
}
b. Use pseudocode to implement Barrier and again coordinate threads using a condition variable as above, but now add the code for using an explicit lock. See the slides towards the end of the "Semaphore and Monitor" lecture about using an explicit lock with condition variables. This style is also what you have been using in Project 1.
class Barrier {
int called;
Lock lock;
Condition barrier;
Barrier () {
called = 0;
lock = new Lock();
barrier = new Condition(lock);
}
void done (int needed) {
lock.acquire();
called++;
if (called == needed) {
barrier.wakeAll()
} else {
while (called < needed) {
barrier.sleep()
}
}
lock.release();
}
}
class PriorityLock {
boolean held;
int numhigh;
Lock lock;
Condition cv;
PriorityLock () {
lock = new Lock();
cv = new Condition(lock);
held = false;
numhigh = 0;
}
void acquire (int priority) {
lock.acquire();
if (priority == high) {
numhigh++;
while (held) {
cv.sleep();
}
// could decrement high here and remove arg to release but,
// want to allow for solutions that use two cvs as well
} else {
while (held || (numhigh > 0)) {
cv.sleep();
}
}
held = true;
lock.release();
}
void release (int priority) {
lock.acquire();
held = false;
if (priority == high) numhigh--;
cv.wakeAll();
lock.release();
}
}
Consider the following state:
Is the system deadlocked in this state? Explain using a resouce allocation graph.
The resource allocation graph, shown below, can be fully
reduced. Chidi is not blocked. Erasing the edges incident on
Chidi unblocks Tahani and Jason. Erasing their edges unblocks
Eleanor.