Homework: Multiprocessor Synchronization

Read: Scalable Synchronization paper

Hand-In Procedure

You are to turn in this homework during lecture. Please write up your answers to the exercises below and hand them in to a 6.828 staff member at the beginning of lecture.

Multiprocessor Synchronization

The algorithms described in the Mellor-Crummey paper on scalable synchronization are of importance to operating systems running on multiprocessors. The kernels of such operating systems must be able to acquire locks on data structures, such as the page table, that are shared across all processors.

Don't be intimidated by the length of the paper---it is easy to read and you can focus your attention on the MCS lock of figure 5. (If you want to, you can skip Section 3 "Barriers".)

Submit: Why does the MCS lock guarantee fairness of lock acquisition?