Distribution

Average	36.83
Stdev	7.47
Min	15
Q1	32
Q2	38
Q3	43
Max	50

1. Lifetime problems in naming systems

Graded by Mendel

(8 points) Naming systems can run into problems when a name's lifetime differs from the object referenced by the name. A name might live longer than the object it refers to, or the object might live longer than the name.
(a) Describe a technique used for dealing with this lifetime problem.
(b) Which of these two problems (a name living longer than its object or the object living longer than its name) would likely be less harmful in a system?

(a) In class we presented a technique called reference counts that keeps a count of the number of names referring to an object. When the count is non-zero the object is kept around and when it reaches zero the object is freed. This insures that the lifetimes of the name and the object match. Several students mentioned garbage collection as is done in Java. Although not discussed in class, it does deal with the lifetime problem by tracking references to an object and only freeing something when no references exist.

(b) The problem of an object dying before a name is referred to as the dangling reference problem whereas the name dying before object is refer to as a memory leak. In programming languages (like the C we are using) where is it difficult to detect dangling references and using them can corrupt memory, memory leaks are frequently less harmful. In environments where it is easy to detect and handle dangling references they are the less harmful. So the answer to this question can go either way but the example naming system should match what you claim is less harmful.

2. Another thread holds my lock

Graded by Justin

(7 points) When running on a uniprocessor (a machine with a single CPU) a thread in a deadlock-free program tries to acquire a lock and finds some other thread holds it. Is this likely an error? If so, describe why. If not, describe what it means and what should happen when the situation is encountered.

Most people understood that this isn't an error, and that the entire purpose of locks is to handle this situation.

When a thread tries to acquire a lock held by some other thread, it should go to sleep and wait (block) until the thread holding the lock releases it. At that point, the blocked thread can wake up and start running again.

About half of the solutions suggested that the waiting thread may want to spin in a loop waiting for the lock to become available. On a multicore machine, this might be a good idea, but on a single-core machine, you can be assured that the lock you want won't become available while you're spinning, since no other thread can run while you have the CPU! So it's better to go to sleep immediately.

Another common misconception was that deadlock and race conditions in general are impossible on a single-core machine. In fact, the operating system gives each thread the illusion that it has a CPU to itself by switching between threads once every few milliseconds. Because of this preemptive context switching, you're exposed to all the same race conditions on a uniprocessor machine as on a multiprocessor machine.

3. Modifying condition variable wait()

Graded by Aditya

(9 points) Assume you went in and changed the condition variable wait() method so that it no longer accessed (i.e. released and acquired) the monitor lock. Which of the conditions would occur if existing code tries to use this new condition variable wait() implementation:
(a) Race condition
(b) Deadlock
(c) Livelock
For each condition explain your answer.

This question was asking what would result if you were to modify an existing system with a monitor lock and a condition variable and eliminated the fact that the condition variable wait() originally released and acquired the monitor lock, and then one of the threads called this modified wait() during the course of its execution. It was not asking what would occur in a hypothetical multithreaded program where the only means of synchronization was the condition variable. This is an important distinction. Parts a, b, and c were worth 2, 5, and 2 points respectively.

(a) Race conditions would not occur because access to data is still granted only when the monitor lock is held. When a thread holds a lock and calls the new wait(), it will retain the lock and so no other thread will be able to get that lock and access the data. Therefore there can be no race conditions.

(b) Deadlock would occur. Consider a system with two threads, t1 and t2. First, t1 acquires the monitor lock. Suppose t1 calls wait() on some condition that t2 is supposed to signal. Because wait() no longer releases and acquires the monitor lock, t1 enters the wait state without relinquishing the monitor lock. Consequently, t2 cannot acquire the monitor lock and start executing. Because t2 cannot start its execution, it can never signal t1. Therefore we have reached deadlock.

(c) Livelock would not occur. Remember that livelock is when threads are executing, but performing no useful work. As soon as a thread calls the new wait(), it deadlocks itself and all the other threads that need to access the monitor lock. There is no execution whatsoever, which is not livelock.

A lot of students thought that since wait() no longer accessed or released locks, there would now be race conditions, that there could not be deadlocks, and that livelock might occur. This misses the point of the question, but I gave some partial credit to the justifications of these answers based on the knowledge of concurrency they displayed.

4. Idempotence in DNS

Graded by Aditya

(7 points) Is the resolve function of the Domain Name System (DNS) an example of an idempotent service? Justify your answer.

Depending on how you define idempotent, the answer to this question can be either yes or no. Here are the three classes of acceptable responses:

If you define idempotence as having no side effects, you can argue that calling the resolve function of DNS is idempotent since it does not change any mappings between domains and IP addresses. It is also possible to state that a call to resolve results in the caching of that lookup at the closest name server, which is a side effect, and thus the resolve function is not idempotent. Either of these received full credit.

If you define idempotence as having the same result every time, you can say that the resolve function is not idempotent, since you might get a different result due to DNS-based load-balancing (recall the Facebook example from lecture). Students who ignored this nuance and said that a given domain always maps to the same IP address, thus making this function idempotent, received most of the points. Partial credit was also given to responses which conflated idempotence and naming contexts and claimed that DNS was not idempotent because different locations can get different IP addresses for the same domain.

If you define idempotence as obeying the property that f(f(x)) = f(x), then you can say that the resolve function is not idempotent, since resolving a domain name yields an IP address, but then calling resolve with that IP address as an argument does not yield the same IP address as the result.

5. Shared locks in Client/Service architectures

Graded by Andrew

(7 points) Would it make sense for a client and service of a client/service architecture to share a lock? Explain your answer.

We intended this question to refer to shared memory locks. Such locks would normally not make sense given a client/service architecture, as client/service implies restricting communication to message passing and enforced modularity. Answers discussing that shared locks did not make sense because of enforced modularity received full credit.

Answers claiming shared locks make sense because communication can be done with bounded buffers received partial credit. The example in the book in 5.1-2 would not be called a client/service architecture because it does not enforce modularity. Moreover, 5.3 describes an implementation where the buffer is managed by the operating system, providing the typical communication abstraction for client/service architectures. While the operating system may use locks to coordinate the bounded buffer, these would not be considered shared locks as neither the client nor the service has access to them.

Some client/service architectures do use distributed locks. Although we did not cover these in class, a yes answer along with a description showing a good understanding of distributed locking schemes received full credit.

6. Soft modularity versus enforced modularity

Graded by Alex

(6 points) Explain why it is more difficult for a programmer to intentionally violate modularity in a system that uses enforced modularity than in a system that uses soft modularity.

What we were looking for in this question is an understanding of how enforced modularity is actually "enforced", and how this enforcement is lacking in soft modularity schemes, making it easier for a programmer to violate module boundaries.

In a system with soft modularity, modules share a common address space. This makes it possible, for example, for a routine in one module to affect the behavior of code considered to be in other modules, by intentionally smashing the stack or maliciously overwriting parts of shared memory. Although modifying the "private" memory of other modules in a soft modularity scheme can be prevented by the programming language and the compiler (e.g., a field declared private in Java), the programmer can easily go ahead and change that to public.

In a system with enforced modularity, modules do not share memory address space and communicate solely via messages. So as long as modules implement correct parameter verification and input sanitization, it is a lot more difficult to violate module boundaries. Although, it does happen sometimes.

7. Talking to the GPU

Graded by the collective

(6 points) Graphic Processing Units (GPUs) are I/O devices commonly found in modern computers. Unlike most other I/O devices that communicate directly only with the operating system, application programs communicate directly with GPUs. Describe the concept from class that best describes this exceptional behavior.

This is a classic example of layer bypass.

Solutions didn't need to use the exact phrase "layer bypass" in order to receive most of the credit on this question, so long as they demonstrated an understanding of the concept.

A few solutions correctly identified layer bypass and then went on to invoke other buzzwords ("virtualization" was common). We deducted a few points in these cases.