CSE 120: Homework #2

Fall 2015

Out: Thursday October 8

Due: Thursday October 22 at the start of class

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

Consider the following C program:
```
#include <stdlib.h>

int main (int argc, char *arg[])
{
    fork ();
    if (fork ()) {
	fork ();
    } else {
	char *argv[2] = {"/bin/ls", NULL};
	execv (argv[0], argv);
        fork ();
    }
}
```
a. How many total processes are created (including the first process running the program)? (Note that execv is just one of multiple ways of invoking exec.)
b. How many times does the /bin/ls program execute?
Hint: You can always add debugging code, compile it, and run the program to experiment with what happens.
Assume we are using multiple user-level threads in a program (multiplexed on just one kernel-level thread). If one thread in the program calls the system call fork() to create a child process, does the child process duplicate all the threads that were in the parent, or is the child process single-threaded? If instead a thread invokes exec(), will the program specified in the parameter to exec() replace the entire process, including all of the threads?
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 *) {
  ...
}
```
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. Write a monitor that implements Barrier using Mesa semantics.
```
monitor Barrier {
  ...
}
```
b. Implement Barrier using an explicit lock and condition variable. The lock and condition variable have the semantics described at the end of the "Semaphore and Monitor" lecture in the ping_pong example, and as implemented by you in Project 1.
```
class Barrier {
  ...private variables...
  void Done (int n) {
    ...
  }
  ...
}
```
Microsoft .NET provides a synchronization primitive called a CountdownEvent. Programs use CountdownEvent to synchronize on the completion of many threads (similar to CountDownLatch in Java). A CountdownEvent is initialized with a count, and a CountdownEvent can be in two states, nonsignalled and signalled. Threads use a CountdownEvent in the nonsignalled state to Wait (block) until the internal count reaches zero. When the internal count of a CountdownEvent reaches zero, the CountdownEvent transitions to the signalled state and wakes up (unblocks) all waiting threads. Once a CountdownEvent has transitioned from nonsignalled to signalled, the CountdownEvent remains in the signalled state. In the nonsignalled state, at any time a thread may call the Decrement operation to decrease the count and Increment to increase the count. In the signalled state, Wait, Decrement, and Increment have no effect and return immediately.
Use pseudo-code to implement a thread-safe CountdownEvent using locks and condition variables by implementing the following methods:
```
class CountdownEvent {
  ...private variables...
  CountdownEvent (int count) { ... }
  void Increment () { ... }
  void Decrement () { ... }
  void Wait () { ... }
}
```
Notes:
- The CountdownEvent constructor takes an integer count as input and initializes the CountdownEvent counter with count. Positive values of count cause the CountdownEvent to be constructed in the nonsignalled state. Other values of count will construct it in the signalled state.
- Increment increments the internal counter.
- Decrement decrements the internal counter. If the counter reaches zero, the CountdownEvent transitions to the signalled state and unblocks any waiting threads.
- Wait blocks the calling thread if the CountdownEvent is in the nonsignalled state, and otherwise returns.
- Each of these methods is relatively short.
[Silberschatz] Consider a system running ten I/O-bound tasks and one CPU-bound task. Assume that the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context-switching overhead is 0.1 millisecond and that all processes are long-running tasks. What is the CPU utilization for a round-robin scheduler when:
a. The time quantum is 1 millisecond
b. The time quantum is 10 milliseconds
[Silberschatz] Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes:
a. FCFS
b. RR
c. Multilevel feedback queues
Annabelle, Bertrand, Chloe and Dag 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.
- Annabelle needs to use the dictionary and a thesaurus to write her paper;
- Bertrand needs a thesaurus and a coffee cup to write his paper;
- Chloe needs a dictionary and a thesaurus to write her paper;
- Dag 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:
- Annabelle has a thesaurus and needs the dictionary.
- Bertrand has a thesaurus and a coffee cup.
- Chloe has the dictionary and needs a thesaurus.
- Dag has a coffee cup and needs another coffee cup.
a. Is the system deadlocked in this state? Explain using a resource allocation graph as a reference.

b. Is this state reachable if the four people allocated and released their resources using the Banker's algorithm? Explain.

voelker@cs.ucsd.edu