Synchronization Hardware semaphores

  • We have just described one software-based solution to the critical-section problem. However, as mentioned, software-based solutions such as Peterson's are not guaranteed to work on modern computer architectures.
  • Instead, we can generally 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. This is illustrated in Figure 2.27.


Figure 2.27 Solution to the critical-section problem using locks.

  • In the following discussions, we explore several more solutions to the critical-section problem using techniques ranging from hardware to software based APIs available to application programmers.
  • All these solutions are based on the premise of locking; however, as we shall see, the designs of such locks can be quite sophisticated.


Figure 2.28 The definition of the TestAndSet () instruction.

Figure 2.29 Mutual-exclusion implementation with TestAndSet ().

  • We start by presenting some simple hardware instructions that are available on many systems and showing how they can be used effectively in solving the critical-section problem.
  • Hardware features can make any programming task easier and improve system efficiency. 
  • 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 often 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.

Figure 2.30 The definition of the Swap () instruction.


Figure 2.31 Mutual-exclusion implementation with the Swap() instruction.

  • 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 by describing the TestAndSet () and Swap() instructions.
  • The TestAndSet () instruction can be defined as shown in Figure 2.28. The important characteristic of this instruction is that it is executed atomically.
  • Thus, if two TestAndSet () 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 Pi is shown in Figure 2.29.
  • The Swap() instruction, in contrast to the TestAndSet () instruction, operates on the contents of two words; it is defined as shown in Figure 2.30


Figure 2.32 Bounded-waiting mutual exclusion with TestAndSet ().

  • Like the TestAndSet () instruction, it is executed atomically. If the machine supports the Swap() 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 2.31.
  • Although these algorithms satisfy the mutual-exclusion requirement, they do not satisfy the bounded-waiting requirement.
  • In Figure 2.32, we present another algorithm using the TestAndSet () 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 mutual exclusion requirement is met, we note that process Pi can enter its critical section only if either waiting [i] == false or key == false. The value of key can become false only if the TestAndSet () 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 (i + 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 TestAndSet() instructions on multiprocessors is not a trivial task.

References

  1. The Operating System Concepts by Silberschatz, Galvin, Gagne, 8th Edition
  2. MODERN OPERATING SYSTEMS by Andrew S. Tanenbaum, Second Edition

Last modified: Sunday, 19 November 2017, 12:01 PM