Chapter 8
Lock Managers and Mutual Exclusion
The mutual exclusion, or mutex, problem involves N concurrent processes, each executing code that has
“critical sections”. The problem is to specify “entry” and “exit” procedures to surround each critical section
such that (1) at most one process is inside a critical section at any time, and (2) any process wanting to enter
the critical section eventually does so. A “classical” mutex solution has no processes other than the ones
that may access a critical section. There are also mutex solutions which make use of “arbiter” processes.
The mutual exclusion problem was formulated in 19XX by XX (Dijkstra?), assuming only read-write
atomicity and no busy waiting (hence no arbiter). Dekker presented the first correct two process solution
in 19XX and the first N process solution in 19XX (ten years later?). Since then, simpler solutions were
developed. The simplest two-process solution is probably the Peterson algorithm. The simplest N-process
solution is probably the Bakery algorithm.
Below, we describe a generic classical mutex solution and outline the obvious way to transform the
solution to a lock manager. We then do the same for a generic arbiter-based mutex solution.
To reason about these systems, we need to refer to the processes contained in them, for which we need
access to the unique abstract ids that tbe processes get when they are created. In the programs that follow,
the type Πid denotes process ids and the variables πid[0], · · · , πid[N− 1] hold the ids of the processes (πid[i]
is updated when thread i is created).
8.1 Lock managers from classical mutex solutions
A classical mutex solution has the following structure:
system-program mutex-csol(int N) {
// generic classical mutex solution
atomicity-assumptions{ mutex aa }
// atomicity assumptions of solution
init() {
mutex vars;
// mutex variables (used only in mutex entry and mutex exit)
other variables;
// non-mutex variables (used in NCS, CS)
for i := 0 to N-1 do {
Πid πid[i] := StartThread(code(i));
}
}
functi