We have just described one software-based solution to the critical-section problem. In general, we can state that any solution to the critical-section problem requires a simple tool—a lock. Race conditions are prevented by requiring that critical regions be protected by locks. That is, a process must acquire a lock before entering a critical section; it releases the lock when it exits the critical section.
In the following discussions, we explore several more solutions to the critical-section problem using techniques ranging from hardware to softwarebased APIs available to application programmers. All these solutions are based on the premise of locking; however, as we shall see, the design of such locks can be quite sophisticated.
Hardware features can make any programming task easier and improve system efficiency. In this section, we present some simple hardware instructions that are available on many systems and show how they can be used effectively in solving the critical-section problem. The critical-section problem could be solved simply in a uniprocessor environment if we could prevent interrupts from occurring while a shared variable was being modified.
In this manner, we could be sure that the current sequence of instructions would be allowed to execute in order without preemption. No other instructions would be run, so no unexpected modifications could be made to the shared variable. This is the approach taken by nonpreemptive kernels. Unfortunately, this solution is not as feasible in a multiprocessor environment. Disabling interrupts on a multiprocessor can be time consuming, as the message is passed to all the processors.
This message passing delays entry into each critical section, and system efficiency decreases. Also, consider the effect on a system's clock, if the clock is kept updated by interrupts. Many modern computer systems therefore provide special hardware instructions that allow us either to test and modify the content of a word or to swap the contents of two words atomically—that is, as one uninterruptible unit. We can use these special instructions to solve the critical-section problem in a relatively simple manner. Rather than discussing one specific instruction for one specific machine, we abstract the main concepts behind these types of instructions. The TestAndSet() instruction can be defined as shown in Figure 6.4.
The important characteristic is that this instruction is executed atomically. Thus, if two TestAndSet C) instructions are executed simultaneously (each on a different CPU), they will be executed sequentially in some arbitrary order. If the machine supports the TestAndSet () instruction, then we can implement mutual exclusion by declaring a Boolean variable lock, initialized to false. The structure of process P, is shown in Figure 6.5.
The SwapO instruction, in contrast to the TestAndSet0 instruction, operates on the contents of two words; it is defined as shown in Figure 6.6. Like the TestAndSet 0 instruction, it is executed atomically. If the machine supports the SwapO instruction, then mutual exclusion can be provided as follows. A global Boolean variable lock is declared and is initialized to false. In addition, each process has a local Boolean variable key. The structure of process P, is shown in Figure 6.7.
Although these algorithms satisfy the mutual-exclusion requirement, they do not satisfy the bounded-waiting requirement. In Figure 6.8, we present another algorithm using the TestAndSetO instruction that satisfies all the critical-section requirements.
The common data structures are boolean waiting[n]; boolean lock; These data structures are initialized to false. To prove that the mutualexclusion requirement is met, we note that process P; can enter its critical section only if either waiting[i] == false or key -- false. The value of key can become false only if the TestAndSetO is executed. The first process to execute the TestAndSet () will find key == false; all others must wait. The variable waiting[i] can become false only if another process leaves its critical section; only one waiting [i] is set to false, maintaining the mutual-exclusion requirement.
To prove that the progress requirement is met, we note that the arguments presented for mutual exclusion also apply here, since a process exiting the critical section either sets lock to false or sets waiting[j] to false. Both allow a process that is waiting to enter its critical section to proceed. To prove that the bounded-waiting requirement is met, we note that, when a process leaves its critical section, it scans the array waiting in the cyclic ordering (z' + 1, i + 2,..., n — 1, 0, ..., i — 1). It designates the first process in this ordering that is in the entry section (waiting [j] =- true) as the next one to enter the critical section.
Any process waiting to enter its critical section will thus do so within n — 1 turns. Unfortunately for hardware designers, implementing atomic TestAndSetQ instructions on multiprocessors is not a trivial task. Such implementations are discussed in books on computer architecture.