182 • Chapter 6: Process Synchronization
`
`repeat
`
`produce an item in nextp
`
`wait( empty);
`wait( mutex);
`
`add nextp to buffer
`
`signal(mutex);
`signal(full);
`until false;
`
`Figure 6.10 The structure of the producer process.
`
`only reading as readers, and to the rest as writers. Obviously, if two readers
`access the shared data object simultaneously, no adverse effects will result.
`However, if a writer and some other process (either a reader or a writer)
`access the shared object simultaneously, chaos may ensue.
`To ensure that these difficulties do not arise, we require that the
`writers have exclusive access to the shared object. This synchronization
`problem is referred to as the readers-writers problem. Since it was
`originally stated, it has been used to test nearly every new synchronization
`primitive. The readers-writers problem has several variations, all
`first
`simplest one,
`referred
`to as
`the
`involving priorities. The
`readers-writers problem, requires that no reader will be kept waiting
`unless a writer has already obtained permission to use the shared object.
`In other words, no reader should wait for other readers to finish simply
`
`repeat
`wait(full);
`wait(mutex);
`
`remove an item from buffer to nextc
`
`signal(mutex);
`signal( empty);
`
`consume the item in nextc
`
`until false;
`
`Figure 6.11 The structure of the consumer process.
`
`Apple 1013 (Part 2 of 4)
`U.S. Pat. 9,189,437
`
`

`
`6.5 Classical Problems of Synchronization • 183
`
`wait(wrt);
`
`writing is performed
`
`signal(wrt);
`Figure 6.12 The structure of a writer process.
`
`because a writer is waiting. The ~econd readers-writers problem Tequires
`thati once a writer is. ready, that write;r performs its write as soon as
`possible, In other words, if a writer is waiting to access the object, no new
`readers may start reading.
`We note that .a solution to either problem may result in starvation. In
`the first case, w:dters may starve; in the second case, readers may star\re.
`For this reason, other variants of the problem have been proposed. In this
`section, we present a solution to the first readers-writers problem. Refer
`to the Bibliographic Notes for relevant references on starvation-free
`solutions to the readers-writers problem.
`In the solution to the first readers-writers problem, the reader
`processes share the following data structures:
`
`var mutex, wrt: semaphore;
`readcount : integer;
`
`The semaphores mutex and wrt are initlaliz~d to 1; readcount is initialized to
`0. The s~maphore wrt is common to both the reader and writer processes.
`The mutex . semaphore is used to ensure mutual exclusion when the
`variable readcount is updated. Readcount keeps track of how many processes
`are. currently reading the object. _The semaphore wrt functions as a mutual
`exclusion semaphore for the writers. It also is used by the first or last
`reader that enters or exits the critical section. It is not used by readers who
`enter or exit while other readers are in their critical sections.
`The code for a writer process is shown in Figure 6.12; the code for a
`reader process is shown in Figure 6.13. Note that, if a writer is in the
`critical section and ri · readers are waiting, theri one reader is queued ori
`wrt, and n - 1 readers are queued on mutex. Also observe that, wheri. a
`writer executes signal(wrt), we may resume the execution of either the
`waiting readers or a single waiting writer. The selection is made by the
`scheduler~
`
`6.5.3 The Dining-Philosophers Problem
`Consider five philosophers who spend their lives thinking and eating. The
`philosophers share a coinrnon circular table surrounded by five chairs,
`each belonging to one philosopher. In the center of the table there is a
`
`

`
`Chapter 6; Process Synchronization
`
`wait(mutex);
`readcount:
`if readcount
`signal(mutex);
`
`readcount + 1;
`1 then wait(wrt);
`
`reading is performed
`
`wait(mutex);
`readcount:
`if readcount
`signal(mutex);
`
`readcount
`1;
`0 then signal(wrt);
`
`Figure 6.13 The structure of a reader process.
`
`bowl of rice, and the table is laid with five single chopsticks
`When a philosopher thinks, she does not interact with
`From time to time, a philosopher gets hungry and tries to
`chopsticks that are closest to her (the chopsticks that are
`her left and right neighbors). A philosopher may pick
`chopstick at a time. Obviously, she cannot pick up a
`already in the hand of a neighbor. When a hungry L/.LLLH.JC'\J
`her chopsticks at the same time, she eats without releasing
`When she is finished eating, she puts down both of her
`thinking again.
`considered
`problem
`dining-philosophers
`synchronization problem, neither because of its practical
`because computer scientists dislike philosophers, but
`example for a large class of concurrency-control problems.
`
`Figure 6.14 The situation of the dining philosophers.
`
`

`
`6.5 Classical Problems of Synchronization • 185
`
`representation of the need to allocate several resources among several
`processes in a deadlock and starvation-free manner.
`One simple solution is to represent each chopstick by a semaphore. A
`philosopher tries to grab the chopstick by executing a wait operation on
`that semaphore; she releases her chopsticks by executing the signal
`operation on the appropriate semaphores. Thus, the shared data are
`
`var chopstick: array [0 . .4] of semaphore;
`
`where all the elements of chopstick are initialized to 1. The structure of
`philosopher i is shown in Figure 6.15.
`Although this solution guarantees that no two neighbors are eating
`simultaneously,
`it nevertheless must be rejected because it has the
`possibility of creating a deadlock. Suppose that all five philosophers
`become hungry simultaneously, and each grabs her left chopstick. All the
`elements of chopstick will now be equal to 0. When each philosopher tries
`to grab her right chopstick, she will be delayed forever.
`Several possible remedies to the deadlock problem are listed next .. In
`Section 6.7, we present a solution to the dining-philosophers problem that
`ensures freedom from deadlocks.
`
`• Allow at most four philosophers to be sitting simultaneously at the
`tabJe.
`• Allow a philosopher to pick up her chopsticks only if both chopsticks
`are available (note that she must pick them up in a critical section) ..
`
`• Use an asymmetric solution; that is, an odd philosopher picks up first
`her left chopstick and then her right chopstick, whereas an even
`philosopher picks up her right chopstick and then her left chopstick.
`
`repeat
`wait(chopstick[i]);
`wait(chopstick[i+ 1 mod 5]);
`
`eat
`
`signal( chopstick[ i]);
`signal(chopstick[i+ 1 mod 5]);
`
`think
`
`until false;
`
`Figure 6.15 The structure of philosopher i.
`
`

`
`186 • Chapter 6: Process Synchronization
`
`Finally, any satisfactory solution to the dining-philosophers probl~m
`must guard against the possibility that one of the philos'?phers will starve
`to death. A deadlock-free solution does not necessarily eliminate the
`possibility of starvation.
`
`6.6 • Critical Regions
`
`Although semaphores provide a convenient and effective mechanism for
`process synchronization, their incorrect use can still result in timing errors
`that are difficult to detect, since these errors happen only if some particular
`execution sequences take place, and these sequences 9-o not always occur.
`We have seen an example of such types of errors in the use of co~nters
`in our solution to the producer-consumer problem (Section 6.1). I~ that
`example, the timing problem happ~ned only rarely, and even then the
`counter value appeared to be a reasonable valt1~ -
`off by only 1.
`Nevertheless, this solution is obviously not an acceptable one. It is ·for th~s
`reason t1:1-at semaphores were intr()duced in the first place.
`Unfortunately, such timing errors can still occur with the use of
`semaphores. To illustrate how, let us review the solution to the critical(cid:173)
`section problem using semaphores. All processes share a semaphore
`variable mutex, which is initialized to 1. Each process must execute
`wait(mutex) before entering the critical section, and signal(mutex) afterward.
`If this sequence is not observed, ·two processes may be in th~ir critical
`sections simultaneously.
`·
`·
`Let us examine the various diffict1lties that may result. Note that these
`difficulties will arise even if a single process is not well behaved. This
`situation may be the result of ap. honest programming· error or ot" an
`uncooperative programmer.
`
`• Suppose that a process interchanges the order in which the wait and
`signal operations on the semaphore mutex are exeq.Ited, resulting in the
`following execution:
`·
`
`signal(mutex);
`
`critical section
`
`wait(mutex);
`
`In this situation, several processes may be executing in their ~ritical
`section simultaneously, viol~tipg the mutual-exclusion requirement.
`if several processes . are
`This error may be discovered only
`simultaneously active in their c:P.tical sections. Note that this situation
`may not always be reproducible;
`
`

`
`6.6 Critical Regions • 187
`
`• Suppose that a process replaces signal(mutex) with wait(mutex). That is,
`it executes
`
`wait( mutex);
`
`critical section
`
`wait(mutex);
`
`In this case, a deadlock will occur.
`
`• Suppose that a process omits the wait(mutex), or the signal(mutex), or
`both. In this case, either mutual exclusion is violated or a deadlock will
`occur.
`
`These examples illustrate that various types of errors can be generated
`easily when semaphores are used incorrectly to solve the critical-section
`problem. Similar problems may arise in the other synchronization models
`we discussed in Section 6.5.
`To deal with the type of errors we have outlined, a number of high(cid:173)
`level language constructs have been introduced.
`In this section, we
`describe one fundamental high-level synchronization construct -
`the
`critical region (sometimes referred to as conditional critical region). In Section
`the
`6.7, we present another fundamental synchronization construct -
`monitor.
`In our presentation of these two constructs, we assume that a
`process consists of some local data, and a sequential program that can
`operate on the data. The local data can be accessed by only the sequential
`program that is encapsulated within the same process. That is, one process
`cannot directly a~cess the local data of another process. Processes can,
`however, share global data.
`The critical-region high-level synchronization construct requires that a
`variable v of type T, which is to be shared among many processes, be
`declared as
`
`var v: shared T;
`
`The variable v can be accessed only inside a region statement of the
`following form:
`
`region v when B do S;
`
`This construct means that, while statement S is being executed, no other
`process can access the variable v. The expression B is a Boolean expression
`that governs the access to the critical region. When a process tries to enter
`the critical-section region, the Boolean expression B is evaluated. If the
`
`

`
`188 • Chapter 6: Process Synchronization
`
`expression is true, statement 5 is executed. If it is false, the process
`relinquishes the mutual exclusion and is delayed until B becomes true and
`no other process is in the region associated with v. Thus, if the two
`statements,
`
`region v when true do 51;
`region v when true do 52;
`
`are executed concurrently in distinct sequential processes, the result will be
`equivalent to the sequential execution "51 followed by 52," or "52 followed
`by 51."
`The critical-region construct guards against certain simple errors
`associated with the semaphore solution to the critical-section problem that
`may be made by a programmer. Note that it does not necessarily eliminate
`all synchronization errors; rather, it reduces their number. If errors occur
`in the logic of the program, reproducing a particular sequence of events
`may not be simple.
`The critical-region construct can be effectively used to solve certain
`general synchronization problems. To illustrate, let us code the bounded(cid:173)
`buffer scheme. The buffer space and its pointers are encapsulated in
`
`var buffer: shared record
`pool: anay [O .. n-1] of item;
`count,in,out: integer;
`
`end;
`
`The producer process inserts a new item nextp into the shared buffer by
`executing
`
`region buffer when count < n
`do begin
`pool[in] := nextp;
`in:= in+1 mod n;
`count : = count + 1;
`end;
`
`The consumer process removes an item from the shared buffer and puts it
`in nextc by executing
`
`region buffer when count > 0
`do begin
`nextc := pool[out];
`out:= out+1 mod n;
`count : = count - 1;
`end;
`
`

`
`6.6 Critical Regions • 189
`
`region could be
`the conditional critical
`illustrate how
`Let us
`implemented by a compiler. With each shared variable, the following
`variables are associated:
`
`var mutex, first-delay, second-delay: semaphore;
`first-count, second-count: integer;
`
`The semaphore mutex is initialized to 1; the semaphores first-delay and
`second-delay are initialized to 0. The integers first-count and second-count are
`initialized to 0.
`Mutually exclusive access to the critical section is provided by mutex. If
`a process cannot enter the critical section because the Boolean condition B
`is ·false, it initially waits on the first-delay semaphore. A process waiting on
`the first-delay semaphore is eventually moved to the second-delay semaphore
`before it is allowed to reevaluate its Boolean condition B. We keep track of
`the number of processes waiting on first-delay and second-delay, with first(cid:173)
`count and second-count respectively.
`When a process leaves the critical section, it may have changed the
`value of some Boolean condition B that prevented another process from
`
`wait(mutex);
`while not B
`do begin
`first-count : = first-count + 1;
`if second-count > 0
`then signal(second-delay)
`else signal(mutex);
`wait(first-delay);
`first-count : = first-count - 1;
`second-count : = second-count + 1;
`if first-count> 0
`then signal(first-delay)
`else signal(second-delay);
`wait(second-delay);
`second-count := second-count - 1;
`end;
`
`S· I
`if first-count > 0
`then signal(first-delay);
`else if second-count > 0
`then signal(second-delay);
`else signal(mutex);
`
`Figure 6.16
`
`Implementation of the conditional-region construct.
`
`

`
`190 • Chapter 6: Process Synchronization
`
`entering the critical section. Accordingly, we must trace through the queue
`of processes waiting on first-delay and second-delay (in that order) allowing
`each process to test its Boolean condition. When a process tests its Boolean
`condition (during this trace), it may discover that the latter now evaluates
`to the value true.
`In this case, the process enters its critical section.
`·Otherwise, the process must wait again on the first-delay and second-delay
`semaphores, as described previously. Accordingly, for a shared variable x,
`the statement
`
`region x when B do S;
`
`this
`that
`in Figure 6.16. Note
`implemented as shown
`can be
`implementation requires the reevaluation of the expression B for any
`waiting processes every time a process leaves the critical region. If several
`processes are delayed, waiting for their respective Boolean expressions to
`become true, this reevaluation overhead may result in inefficient code.
`There are various optimization methods that we can use to reduce this
`overhead. Refer to the Bibliographic Notes for relevant references.
`
`6.7 • Monitors
`
`Another high-level synchronization construct is the monitor type. A
`monitor is characterized by a set of programmer-defined operators. The
`representation of a monitor type consists of declarations of variables whose
`values define the state of an instance of the type, as well as the bodies of
`procedures or functions that implement operations on the type. The
`syntax of a monitor is
`
`type monitor-name = monitor
`variable declarations
`
`procedure entry Pl ( ... );
`begin ... end;
`
`procedure entry P2 ( ... );
`begin ... end;
`
`procedure entry Pn ( ... );
`begin ... end;
`
`begin
`initialization code
`end.
`
`

`
`6.7
`
`The representation of a monitor type cannot be used
`various processes. Thus, a procedure defined within a monitor can access
`only those variables declared locally within the monitor
`parameters. Similarly, the local variables of a monitor can be
`only the local procedures.
`a
`The monitor construct ensures that only one process
`active within the monitor. Consequently, the programmer does
`code this synchronization constraint explicitly (Figure 6.17).
`monitor construct, as defined so far/ is not sufficiently powerful
`some synchronization schemes. For this purpose, we need to .,.."" ...... ,,..._
`tional synchronization mechanisms. These mechanisms are
`condition construct. A programmer who needs to wrjte her own
`synchronization scheme can define one or more variables of
`
`var X1 y: condition;
`
`The only operations that can be invoked on a condition
`and signal. The operation
`
`x.wait;
`
`operations
`
`Figure 6.17 Schematic view of a monitor.
`
`

`
`192
`
`Chapter 6: Process Synchronization
`
`means that the process invoking this operation is suspended
`process invokes
`
`x.signal;
`
`The x.signal operation resumes exactly one suspended
`is suspended, then the signal operation has no effect;
`state of x is as though the operation was never executed
`the signal operation
`Contrast
`this operation with
`semaphores, which always affects the state of the semaphore.
`Now suppose that, when the x.signal operation is invoked by a n.-.nr<t:>CC
`P, there is a suspended process Q associated with condition x.
`the suspended process Q is allowed to resume its execution, the
`process P must wait. Otherwise, both P and Q will
`simultaneously within the monitor. Note, however, that both pr•OCt~ss>e
`conceptually continue with their execution. Two possibilities
`
`1. P either waits until Q leaves the monitor, or waits
`condition.
`Q either waits until P leaves the monitor, or waits for
`condition.
`
`queues associated with
`x, y conditions
`
`...
`
`operations
`
`Figure 6.18 Monitor with condition variables.
`
`

`
`6 .. 7 Monitors • 193
`
`There are reasonable arguments in favor of adopting either option 1 or
`option 2. Since P was already executing in the monitor, choice 2 seems
`more reasonable. However, if we allow process P to <:ontinue, the "logical"
`condition for which Q was "Yaiting may no longer hold by the time Q is
`resumed.
`··"
`Choice 1 was advocated by Hoare, mainly because the preceding
`argument in favor of it translates directly to simpler and more elegant
`proof rules. A compromise between these two choices was adopted in the
`language Concurrent Pascal. When process P executes the signal operation,
`it immediately leaves the monitor. Hence, Q is immediately resumed. This
`model is less powerful than Hoare's, because a process cannot signal more
`than once during a single procedure call.
`Let us illustrate these concepts by presenting a deadlock-free solution
`to the dining-philosophers probl~m. Recall that a philosopher is allowed to
`pick up her chopsticks only if both of them are available. To code this
`solution, we need to distinguish between three states in which a
`philosopher may be. For this purpose, we introduce the following data
`structure:
`
`var state: array [0 .. 4] of (thinking, hungry, eating);
`
`Philosopher i can set the variable state[i] = eating only if her two neighbors
`are not eating (state[i+4 mod 5] =I= eating and state[i+ 1 mod 5] =I= eating).
`We also need to declare
`
`var self: array [0 .. 4] of condition;
`
`where philosopher i can delay herself when she is hungry, but is unable to
`obtain the chopsticks she needs.
`We are now in a position to describe our solution. The distribution of
`the chopsticks is controlled by the monitor shown in Figure 6.19.
`Philosopher i must invoke the operations pickup and putdown on an
`instance dp of the dining-philosophers monitor in the following sequence:
`
`dp.pickup(i);
`
`eat
`
`dp.putdown(i);
`
`It is easy to show that this solution ensures that no two neighbors are
`eating simultaneously~ and that no deadlocks will occur. We note,
`however, that it is possible for a philosopher to starve to death. We shall
`not present a solution to this problem, but rather shall leave it as an
`exercise for you.
`
`

`
`194 • Chapter 6: Process Synchronization
`
`type dining-philosophers = monitor
`var state : array [0 . .4] of (thinking, hungry, eating);
`var self: array [0 . .4] of condition;
`
`procedure entry pickup (i: 0 . .4);
`begin
`state[i] : = hungry;
`test (i);
`if state[i] =F eating then self[i].wait;
`end;
`
`procedure entry putdown (i: 0 .. 4);
`begin
`state[i] : = thinking;
`test (i+4 mod 5);
`test (i+ 1 mod 5);
`end;
`
`procedure test (k: 0 . .4);
`begin
`if state[k+4 mod 5] =I= eating
`and state[k] = hungry
`and state[k+ 1 mod 5] =I= eating
`then begin
`state[k] := eating;
`self[k].signal;
`end;
`
`end;
`
`begin
`fori:= 0 to 4
`do state[i] : = thinking;
`
`end.
`
`Figu~e 6.19 A monitor solution to the dining-philosopher problem.
`
`We shall now consider a possible implementation of the monitor
`mechanism using semaphores. For each monitor, a semaphore mutex
`(initialized to 1) is provided. A process must execute wait(mutex) before
`entering the monitor, and must execute signal(mutex) after leaving the
`monitor.
`/
`Since a signaling process must wait until the resumed process either
`leaves or waits, an additional semaphore, next, is introduced, initialized to
`
`

`
`6.7 Monitors • 195
`
`0,. on which the signaling processes may suspend themselves. An integer
`variable next-count will also be provided to count the number of processes
`suspended on next. Thus, each external procedure F will be replaced by
`
`wait(mJtex);
`
`body ofF;
`
`if next-count > 0
`then signal(next)
`else signal(mutex);
`
`Mutual exclusion within a monitor is ensured.
`We can now describe how condition variables are implemented. For
`each condition x, we introduce a semaphore x-sem and an integer variable
`x-count, both initialized to 0. The operation x.wait can now be implemented
`as
`
`x-count : = x-count + 1;
`if next-count > 0
`then signal(next)
`else signal(mutex);
`wait(x-sem);
`x-count : = x-count - 1;
`
`The operation x.signal can be implemented as
`
`if x-count > 0
`then begin
`next-count : = next-count + 1;
`signal(x-sem);
`wait( next);
`next-count : = next-count - 1;
`end;
`
`This implementation is applicable to the definitions of monitors given by
`both Hoare and Brinch Hansen. In some cases, however, the generality of
`the implementation is unnecessary, and a significant improvement in
`efficiency is possible. We leave this problem to you in Exercise 6.12.
`We turn now to the subject of process-resumption order within a
`If several processes are suspended on condition x, and an
`monitor.
`x.signal operation is executed by some process, then how do we determine
`which of the suspended processes should be resumed next? One simple
`solution is to use an FCFS ordering, so that the process waiting the longest
`
`

`
`196 • Chapter 6: Process Synchronization
`
`is resumed first. There are, however, many circumstances in which such a
`simple scheduling scheme
`is not adequate. For
`this purpose,
`the
`conditional-wait construct can be used; it has the form
`
`x.wait(c);
`
`where cis an integer expression that is evaluated when the wait operation
`is executed. The value of c, which is called a priority number, is then stored
`with the name of the process that is suspended. When x.signal is executed,
`the process with the smallest associated priority number is resumed next.
`To illustrate this new mechanism, we consider the monitor shown in
`Figure 6.20, which controls the allocation of a single resource among
`competing processes. Each process, when requesting an allocation of its
`resources, specifies the maximum time it plans to use the resource. The
`monitor allocates the resource to that process that has the shortest time(cid:173)
`allocation request.
`A process that needs to access the resource in question must observe
`the following sequence:
`
`R.acquire(t);
`
`access the resource;
`
`R.release;
`
`where R is an instance of type resource-allocation.
`Unfortunately,
`the monitor concept cannot guarantee
`preceding access sequences will be observed. In particular,
`
`that
`
`the
`
`• A process might access the resource without first gaining access
`permission to that resource.
`
`• A process might never release the resource once it has been granted
`access to that resource.
`
`• A p~ocess might attempt to release a resource that it never requested.
`
`• A process might request the same resource twice (without first
`releasing that resource).
`
`Note that the same difficulties are encountered with the critical section
`construct, and these difficulties are similar in nature to those that
`encouraged us to develop the critical-region and monitor constructs in the
`first place. Previously, we had to worry about the correct use of
`semaphores. Now, we have to .Worry about the correct use of higher-level
`
`I
`
`

`
`6. 7 Monitors • 197
`
`type resource-allocation = monitor
`var busy: boolean;
`x: condition;
`
`procedure entry acquire (time: integer);
`begin
`if busy then x.wait(time);
`busy : = true;
`end;
`
`procedure entry release;
`begin
`busy : = false;
`x.signal;
`end;
`
`begin
`busy : = false;
`end.
`
`Figure 6.20 A monitor to allocate a single resource.
`
`programmer-defined operations, with which the compiler can no longer
`assist us.
`One possible solution to the above problem is to include the resource(cid:173)
`access operations within resource-allocation monitor. However, this solution
`will result in scheduling being done according to the built-in monitor(cid:173)
`scheduling algorithm, rather than by the one we have coded.
`To ensure that the processes observe the appropriate sequences, we
`must inspect all the programs that make use of the resource-allocation
`monitor and its managed resource. There are two conditions that we. must
`check to establish the correctness of this system. First, user processes
`must always make their calls on the monitor in a correct sequence. Second,
`we must be sure that an uncooperative process does not simply ignore the
`mutual-exclusion gateway provided by the monitor, and try to access the
`shared resource directly, without using the access protocols. Only if these
`two conditions can be ensured can we guarantee that no time-dependent
`errors will occur, and that the scheduling algorithm will not be defeated.
`Although this inspection may be possible for a small, static system, it is
`not reasonable for a large system or for a dynamic system. This access(cid:173)
`control problem can be solved only by additional mechanisms that will be
`elaborated in Chapter 13.
`
`

`
`198 • Chapter 6: Process Synchronization
`
`6.8 • Synchronization in Solaris 2
`
`To solidify this discussion, we now return to Solaris 2. Before the advent
`of Solaris 2, Sunos used critical sections
`to guard important data
`structures. The system implemented the critical sections by setting the
`interrupt level to as high as or higher than any interrupt that could modify
`the same data. Thus, no interrupt would occur that would allow a change
`to the same data.
`In Section 5.5, we described the changes needed to support real-time
`computing on a time-sharing system. Solaris 2 was designed to provide
`real-time capabilities, be multithreaded, and support multiprocessors.
`Continuing to use critical sections would have caused a large performance
`degradation, as the kernel bottlenecked waiting for entry into critical
`sections. Further, critical sections could not have been implemented via
`interrupt elevation because interrupts could occur on other processors on a
`multiprocessor system. To avoid these problems, Solaris 2 uses adaptive
`mutexes to protect access to every critical data item.
`On a multiprocessor system, an adaptive mutex starts as a standard
`If the data are locked, and
`semaphore implemented as a spinlock.
`therefore already in use, the adaptive mutex does one of two things. If the
`lock is held by a thread that is currently running, the thread waits for the
`lock to become available because the thread holding the lock is likely to be
`done soon. If the thread holding the lock is not currently in run state, the
`thread blocks, going to sleep until it is awakened by the lock being
`released. It is put to sleep so that it will avoid spinning when the lock will
`not be freed reasonably quickly. A lock held by a sleeping thread is likely
`to be in this category. On a uniprocessor system, the thread holding the
`lock is never running if the lock is being tested by another thread, because
`only one thread can run at a time. Therefore, on a uniprocessor system,
`threads always sleep rather than spin if they encounter a lock.
`For more complex synchronization situations, Solaris 2 uses condition
`variables and readers-writers locks. The adaptive mutex method described
`above- is used to protect only those data that are accessed by short code
`segments. That is, a mutex is used if a lock will be held for less than a
`few hundred instructions. If the code segment is longer than that, spin
`waiting will be exceedingly inefficient. For longer code segments,
`condition variables are used. If the desired lock is already held, the thread
`issues a wait and sleeps. When a thread frees the lock, it issues a signal to
`the next sleeping thread in the queue. The extra cost of putting a thread
`to sleep and waking it, and of the associated context switches, is less than
`the cost of wasting several hundred instructions waiting in a spinlock.
`The readers-writers locks are used to protect data that are accessed
`frequently, but usually only
`in a
`read-only manner.
`In
`these
`circumstances,
`readers-writers
`locks are more efficient
`than are
`
`

`
`(;.9 Atomjc Transactions • 199
`
`semaphores, beca~se multiple thr~ads may be reading data concurrently,
`whereqs semapho~es would always §er+alize access · to th~ data.
`Readers-writers locl<s are expensive to implement, so qgain they 'lre used
`on only long sections of code. ·
`
`6.9 • Atomic Transactions
`
`The mu4:tal exclusion of critical ~ections ensures that the critical sections
`are exeq.1ted ~tomically. That i~, if two critical sections are executed
`concu~e!ltly, the result is equivalent to t~eir sequential execution in some
`unlqtown order. Although this prpperty · i~ useful in many application
`doma~ns, there are many ci;lses where we wpuld like to make sure that a
`critical section form,s a singJe logical unit. of work that either is performed
`i:n its entirety o:r is not performed at ~11. An ex~mple is funds transfer, in
`which one account is debited an4 another is credited .. C:leady, it is
`essential for data consistency that e1ther both the credit anci debit occur, or
`that neither occur.
`·
`· ·
`·
`The remainder qf this ~ection is related to the field of database
`systems. Databases are concerned with the storage and retrieval of data,
`and with.· the consistency of the qata. Recently, there has ·been an upsurge
`of interest in using database-systems techrt~ques in operating systems.
`Operating syste~s can be viewed as mcmipulators of di;1ta; as s~ch, they
`can benefit · from. the advaqced t~chniques a11d models available from
`datapase research. For in~tance; many ·of the ad ho~ techniques used in
`operating systems to manflge files could ·b~ ~ore fle~ble and powerful if
`more formal database methods were used in their place. In Sections 6.9.2
`to. 6.9.4, we destribe what the~e d:atabase techniques are, and how they
`can l:>e used by operating systems.
`·
`·
`·
`·
`
`6. 9.1 Systelll Model
`A collection of. instructions (operations) t~at performs a single logical
`function is called atransaction. A major issue in. processing transactions is
`the preservation of. atoinicity despite ·the. possibility of failures within the
`computer system.
`In Section 6. 9, we describe · various mechanisms for
`ensuring
`transaction atomicity. We do so by first considering an
`environment where only one transaction qm be executing at a time. Then,
`we · cons1d~r ·the
`case where · multiple · transactions
`a~e active
`simultaneously.
`A . transaction is a program unit that accesses and possibly updates
`various data items that inay reside on the disk within some files. From our
`point of view, a tran~action is simply a sequence of read and writ~
`operations~ ter~nated by eit}l:er a COJ11111~t operaqort Or an abort opera~on.
`
`

`
`200 • Chapter 6: Process Synchronization
`
`A commit operation signifies that the transaction has terminated its
`execution successfully, whereas an abort operation signifies that the
`transaction had to cease its normal execution due