One of the goals of this question is to give you practice with context switching and thread queue manipulation in Nachos, and the hope is that you will find it useful for working on project 1 (so there is value in doing this problem well before the due date).
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");
}
Assume that the scheduler runs threads in FIFO order with non-preemptive scheduling (no preemptive time-slicing) on a single CPU core, 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.
a. Context switches: main →
b. Output:
c. Thread queues when selfTest returns:
currentThread:
readyQueue:
join wait queue:
[Hint: First try the problem by following the code manually, keeping track of which queues threads are on using paper. Then, once you have implemented join, try adding the code as a test in KThread.java and running it to check your answer.]
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
c. Thread queues when selfTest returns:
currentThread: main
readyQueue: (nothing, A & B have finished)
join wait queue: (nothing, A & B have finished)
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;
}
A common pattern in parallel scientific programs is to have a set of threads do a computation in a sequence of phases. In each phase i, all threads must finish phase i before any thread starts computing phase i+1. One way to accomplish this is with barrier synchronization. At the end of each phase, each thread executes Barrier::Done(n), where n is the number of threads in the computation. A call to Barrier::Done blocks until all of the n threads have called Barrier::Done. Then, all threads proceed. You may assume that the process allocates a new Barrier for each iteration, and that all threads of the program will call Done with the same value.
a. Use pseudocode to write a monitor that implements Barrier.
monitor Barrier {
int waiters = 0;
Condition barrier;
Barrier () {
barrier = new Condition();
}
void Done (int n) {
waiters++;
if (waiters == n) {
barrier.wakeAll();
} else {
barrier.sleep();
}
}
}
b. Use pseudocode to implement Barrier using an explicit lock and condition variable. The lock and condition variable have the Mesa semantics described in the "Condition Variables" lecture, and as implemented by you in Project 1.
class Barrier {
int waiters = 0;
Lock lock;
Condition barrier;
Barrier () {
lock = new Lock();
barrier = new Condition(lock);
}
void Done (int n) {
lock.acquire();
waiters++;
if (waiters == n) {
barrier.wakeAll();
} else {
barrier.sleep();
}
lock.release();
}
}
c. Use pseudocode to implement Barrier using an explicit lock and one semaphore. [Hint: think about how can you make sure that all n-1 waiting threads are woken up. There are multiple possible approaches to implementing this.]
In this solution, the nth thread to arrive signals the semaphore once, allowing
one thread to exit from wait. After exiting wait, that
thread will call signal, allowing one more thread to exit wait.
This will continue, with each thread waking up one more thread, until all threads
have exited Done. (This pattern of calling wait and then
signal is called a turnstile because it forces threads to pass
through it one after another.) Alternatively, you can solve this problem using a
for loop in which the nth thread wakes all waiting threads.
class Barrier {
int waiters = 0;
Lock lock;
Semaphore sem;
Barrier () {
lock = new Lock();
sem = new Semaphore(0);
}
void Done (int n) {
lock.acquire();
waiters++;
if (waiters == n) {
sem.signal();
}
lock.release();
sem.wait();
sem.signal();
}
}
Torrey Pines would like your help synchronizing surfers and the ocean. Using pseudocode, implement the class Surfing using locks and condition variables to synchronize multiple surfer threads with one ocean thread (do not manipulate interrupts). Your solution also cannot change the lock, condition variable, or thread classes, and do not use data structures other than locks and condition variables to store references to threads.
You need only use pseudocode in your answers. Your pseudocode does not have to compile, and you can use whatever syntax you are most comfortable with (the solutions use the Nachos syntax). But it does have to look like code.
The Surfing class can be in one of two states, either breaking or calm. Surfer threads invoke the paddle method to indicate the direction, left or right, they would like to surf the break. When calm, surfer threads block until the next wave arrives. When breaking, surfer threads block if the wave is not breaking in their direction, and otherwise return immediately.
The ocean thread invokes the wave method indicating the direction the next wake is breaking (left, right, or both ways). It changes the state to breaking and wakes up all surfer threads waiting to catch waves in that direction, or wakes up all threads if the wave is breaking in both directions. It invokes the done method to indicate that the wave is finished breaking, changing the state back to calm. The ocean thread alternates invoking wave and done, and the state is initially calm.
class Surfing {
enum State { CALM, BREAKING; }
enum Direction { LEFT, RIGHT, BOTH; }
State state;
Direction breakdir;
Lock lock;
Condition left, right;
Surfing () {
state = CALM;
lock = new Lock();
left = new Condition(lock);
right = new Condition(lock);
}
void paddle (Direction dir) {
lock.acquire();
if (state == BREAKING && (breakdir == dir || breakdir == BOTH)) {
lock.release();
return;
}
if (dir == LEFT) {
left.sleep();
} else {
right.sleep();
}
lock.release();
}
void wave (Direction dir) {
lock.acquire();
state = BREAKING;
breakdir = dir;
if (dir == LEFT) {
left.wakeAll();
} else if (dir == RIGHT) {
right.wakeAll();
} else {
left.wakeAll();
right.wakeAll();
}
lock.release();
}
void done () {
lock.acquire();
state = CALM;
lock.release();
}
}
- Eleanor needs to use the dictionary and a thesaurus to write her paper;
- Chidi needs a thesaurus and a coffee cup to write his paper;
- Tahani needs a dictionary and a thesaurus to write her paper;
- Jason needs two coffee cups to write his paper (he likes to have a cup of regular and a cup of decaf at the same time to keep himself in balance).
Consider the following state:
- Eleanor has a thesaurus and needs the dictionary.
- Chidi has a thesaurus and a coffee cup.
- Tahani has the dictionary and needs a thesaurus.
- Jason has a coffee cup and needs another coffee cup.
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.
