Homework 3

This assignment is intended to help you study for the second exam. It will not be graded (i.e., you need not turn anything in).

1. Use a serializer to implement the following critical section: there are two kinds of threads, red and green. Up to three threads can be in the critical section at any time, but not all can be the same color. (Assume that the semantics of the serializer are that only the first thread in a queue is awaken/checked every time a thread leaves the serializer.)
2. Consider a critical section with two locks (lock1 and lock2) that can be acquired in any order and do not have to be both acquired. Design a spin-lock (i.e., show the locking code using a test_and_set instruction) that satisfies the following requirements:
• Deadlock is prevented (i.e., it is never the case that a holder of lock1 is waiting for lock2 while a holder of lock2 is waiting for lock1).
• No thread ever spins while holding a lock, as this will prevent another thread that needs only that lock from doing useful work.
• The lock has good performance in terms of latency, delay, and bandwidth consumption on an SMP machine with snooping caches.

You can assume that the contention for locks is low (a well designed concurrent program typically will not have high contention)—that is, there are very rarely more than 2 threads spinning. Justify with a couple of sentences why your lock works well. Note: donπt use spin-locks in your projects. Spin-locks are architecture-specific.