COS 318: Operating Systems, Fall 2013

Quiz 2: Synchronizations

Due: 11:55pm, Wednesday, October 9

This quiz checks your understanding of the lectures and its reading assignments during the past week. You may reference the textbook, lecture slides, and your notes. Online sites (e.g., Wikipedia) may also be consulted but you must cite them in your writeup.

Each question is worth three points. Please strive for clarity and brevity in your answers. Essay questions should require no more than one or two short paragraphs.

Submit your answers by clicking the "submit" link on the lecture schedule page. Only online submissions will be accepted. Please submit plain ASCII text files.

Questions:

Consider a machine with an atomic instruction called compare-and-swap (CAS), provided by the hardware, with the following pseudo-code:

int CAS(int *a, int old, int new) {
    if (*a != old) return 0;
    *a = new;
     return 1;
}

In the lecture, we talked about test-and-set (TAS) instruction, which has the following pseudo-code:

int TAS(int *a) {
    if (*a != 0) return 0;
    *a = 1;
    return 1;
}

Implement an atomic TAS function using the CAS function.

Suggested solution:

int TAS(int *a) {
    return CAS(a, 0, 1);
}

In class, we discussed how to use semaphores to solve the consumer-producer problem (lecture note page number 8). Suppose that we modify the code as follows:



Please tell whether this modification is correct or incorrect. If you think it is correct, tell us the advantages and disadvantages, comparing with the solution in the lecture. If you think it is incorrect, tell us what can go wrong by showing an example.

Suggested solution: The modification is incorrect. Consider the case where the buffer is full. Suppose a Producer runs. It holds mutex and wait on the emptyCount semaphore. A Consumer now runs. It will wait on P(mutex).

Use no more than six sentences to explain the differences among Hoare’s monitor, Hansen’s monitor, and Mesa monitor, in terms of the implementation of Signal.

Suggested solution: Hoare proposed to run the signaled thread immediately, suspending the current thread. Hansen proposed that Signal must be the last statement of a monitor procedure. Mesa monitor allows the current thread to continue its execution after executing Signal. Mesa monitor allows Signal to wakeup more than one thread. Programming with Mesa monitor requires checking the condition again after returning from Wait, because the condition may no longer be true.