CSE 120: Homework #2

Fall 2025

Due: Thursday October 23 at 11:59pm

For the homework questions below, if you believe that you cannot answer a question without making some assumptions, state those assumptions in your answer.

The Intel x86 instruction set architecture provides an atomic instruction called XCHG for implementing synchronization primitives. (If you are curious, this reference page shows the full syntax and semantics of the instruction.) Semantically, XCHG works as follows (although keep in mind it is executed atomically):
```
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 {
  ...
}

void acquire (struct lock *) {
  ...
}

void release (struct lock *) {
  ...
}
```
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), 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.]
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.
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 {
  ...private variables...
  void done (int n) {
    ...
  }
  ...
}
```
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 {
  ...private variables...
  void done (int n) {
    ...
  }
  ...
}
```
A PriorityLock lets threads acquire a lock with two levels of priority, low and high. Threads that call acquire with high priority will acquire the lock before threads that call acquire with low priority. There is no lock preemption, though; if a thread with low priority holds the lock, it keeps the lock until it calls release, even if a thread with high priority calls acquire. low and high are predefined integer constants. Assume that the priority argument always has one of these two values and that a thread will call both acquire and release with the same value. Using pseudocode, implement the class PriorityLock using locks and condition variables to synchronize. Do not manipulate interrupts or invoke thread methods, or add methods to locks and condition variables. You need only use pseudocode in your answer. 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).
```
class PriorityLock {
  ...private variables...
  PriorityLock () {
    ...
  }
  void acquire (int priority) {
    ...
  }
  void release (int priority) {
    ...
  }
}
```
Eleanor, Chidi, Tahani, and Jason are working on their term papers in CSE 120, which is a 10,000 word essay on My All-Time Favorite Race Conditions. To help them work on their papers, they have one dictionary, two copies of Roget's Thesaurus, and two coffee cups.
- 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 resource allocation graph as a reference.