Classical problems of synchronization: The producer consumer problem, Reader-writers problem, Semaphores, Dinning Philosopher problem

  • Operating systems often distinguish between counting and binary semaphores. The value of a counting semaphore can range over an unrestricted domain. The value of a binary semaphore can range only between 0 and 1.
  • On some systems, binary semaphores are known as mutex locks, as they are locks that provide mutual exclusion.
  • We can use binary semaphores to deal with the critical-section problem for multiple processes.
  • Then processes share a semaphore, mutex, initialized to 1. Each process Pi is organized as shown in Figure 2.33.
  • Counting semaphores can be used to control access to a given resource consisting of a finite number of instances.
  • The semaphore is initialized to the number of resources available. Each process that wishes to use a resource performs a wait() operation on the semaphore (thereby decrementing the count).
  • When a process releases a resource, it performs a signal() operation (incrementing the count). When the count for the semaphore goes to 0, all resources are being used.
  •  After that, processes that wish to use a resource will block until the count becomes greater than 0. We can also use semaphores to solve various synchronization problems.
  • For example, consider two concurrently running processes: P1 with a statement S1 and P2 with a statement S2.
  • Suppose we require that S2 be executed only after S1 has completed.

2.9.1 Semaphores

  • The hardware-based solutions to the critical-section problem presented in Section 2.8 are complicated for application programmers to use.
  • To overcome this difficulty, we can use a synchronization tool called semaphores.
  • A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait () and signal ().
  • The wait () operation was originally termed P (from the Dutch proberen, "to test"); signal() was originally called V (from verhogen, "to increment").
  • The definition of wait () is as follows:

wait(S)

{

While(S <= 0);

// no-opwration

s--;

}

  • The definition of signal() is as follows:

signal(S)

{

S++;

}

  • All modifications to the integer value of the semaphore in the wait () and signal() operations must be executed indivisibly.
  • That is, when one process modifies the semaphore value, no other process can simultaneously modify that same semaphore value.
  • In addition, in the case of wait (S), the testing of the integer value of S (S ≤ 0), as well as its possible modification (S--), must be executed without interruption.
  • We shall see how these operations can be implemented in Section 2.9.1.2; first, let us see how semaphores can be used.

2.9.1.1 Usage

  • Operating systems often distinguish between counting and binary semaphores. The value of a counting semaphore can range over an unrestricted domain. The value of a binary semaphore can range only between 0 and 1.
  • On some systems, binary semaphores are known as mutex locks, as they are locks that provide mutual exclusion.
  • We can use binary semaphores to deal with the critical-section problem for multiple processes.
  • Then processes share a semaphore, mutex, initialized to 1. Each process Pi is organized as shown in Figure 2.33.
  • Counting semaphores can be used to control access to a given resource consisting of a finite number of instances.
  • The semaphore is initialized to the number of resources available. Each process that wishes to use a resource performs a wait() operation on the semaphore (thereby decrementing the count).
  • When a process releases a resource, it performs a signal() operation (incrementing the count). When the count for the semaphore goes to 0, all resources are being used.
  •  After that, processes that wish to use a resource will block until the count becomes greater than 0. We can also use semaphores to solve various synchronization problems.
  • For example, consider two concurrently running processes: P1 with a statement S1 and P2 with a statement S2.
  • Suppose we require that S2 be executed only after S1 has completed.
  • We can implement this scheme readily by letting P1 and P2 share a common semaphore synch, initialized to 0, and by inserting the statements

S1;

signal(synch) ;

in process P1 and the statements

wait(synch);

S2;

in process P2.

  • Because synch is initialized to 0, P2 will execute S2 only after P1 has invoked signal (synch), which is after statement S1 has been executed.


Figure 2.33 Mutual-exclusion implementation with semaphores.

2.9.1.2 Implementation

  • The main disadvantage of the semaphore definition given here is that it requires busy waiting.
  • While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the entry code.
  • This continual looping is clearly a problem in a real multiprogramming system, where a single CPU is shared among many processes.
  • Busy waiting wastes CPU cycles that some other process might be able to use productively. This type of semaphore is also called a spinlock because the process "spins" while waiting for the lock.
    • Spinlocks do have an advantage in that no context switch is required when a process must wait on a lock, and a context switch may take considerable time.
    • Thus, when locks are expected to be held for short times, spinlocks are useful; they are often employed on multiprocessor systems where one thread can "spin" on one processor while another thread performs its critical section on another processor.
  • To overcome the need for busy waiting, we can modify the definition of the wait() and signal() semaphore operations.
  • When a process executes the wait () operation and finds that the semaphore value is not positive, it must wait.
  • However, rather than engaging in busy waiting, the process can block itself.
  • The block operation places a process into a waiting queue associated with the semaphore, and the state of the process is switched to the waiting state.
  • Then control is transferred to the CPU scheduler, which selects another process to execute. A process that is blocked, waiting on a semaphore S, should be restarted when some other process executes a signal() operation.
  • The process is restarted by a wakeup () operation, which changes the process from the waiting state to the ready state. The process is then placed in the ready queue. (The CPU may or may not be switched from the running process to the newly ready process, depending on the CPU-scheduling algorithm.)
  • To implement semaphores under this definition, we define a semaphore as a "C' struct:

typedef struct

{

int value;

struct process *list;

} semaphore;

  • Each semaphore has an integer value and a list of processes list. When a process must wait on a semaphore, it is added to the list of processes.
  • A signal() operation removes one process from the list of waiting processes and awakens that process. The wait() semaphore operation can now be defined as

wait (semaphore *S)

{

S->value--;

if (S->value < 0)

 {

add this process to S->list;

block();

}

}

  • The signal () semaphore operation can now be defined as

signal (semaphore *S)

{

S->value++;

if (S->value <= 0)

 {

remove a process P from S->list;

wakeup(P);

}

}

  • The block() operation suspends the process that invokes it. The wakeup (P) operation resumes the execution of a blocked process P. These two operations are provided by the operating system as basic system calls.
  • Note that in this implementation, semaphore values may be negative, although semaphore values are never negative under the classical definition of semaphores with busy waiting.
  • If a semaphore value is negative, its magnitude is the number of processes waiting on that semaphore. This fact results from switching the order of the decrement and the test in the implementation of the wait () operation.
  • The list of waiting processes can be easily implemented by a link field in each process control block (PCB).
  • Each semaphore contains an integer value and a pointer to a list of PCBs.
  • One way to add and remove processes from the list so as to ensure bounded waiting is to use a FIFO queue, where the semaphore contains both head and tail pointers to the queue.
  • In general, however, the list can use any queueing strategy. Correct usage of semaphores does not depend on a particular queueing strategy for the semaphore lists.
  • It is critical that semaphores be executed atomically. We must guarantee that no two processes can execute wait() and signal() operations on the same semaphore at the same time.
  • This is a critical-section problem; and in a single-processor environment (that is, where only one CPU exists), we can solve it by simply inhibiting interrupts during the time the wait() and signal() operations are executing.
  • This scheme works in a single-processor environment because, once interrupts are inhibited, instructions from different processes cannot be interleaved.
  • Only the currently running process executes until interrupts are reenabled and the scheduler can regain control.
  • In a multiprocessor environment, interrupts must be disabled on every processor; otherwise, instructions from different processes (running on different processors) may be interleaved in some arbitrary way.
  • Disabling interrupts on every processor can be a difficult task and furthermore can seriously diminish performance.
  • Therefore, SMP systems must provide alternative locking techniques-such as spinlocks-to ensure that wait() and signal() are performed atomically.
  • It is important to admit that we have not completely eliminated busy waiting with this definition of the wait () and signal () operations.
  • Rather, we have moved busy waiting from the entry section to the critical sections of application programs.
  • Furthermore, we have limited busy waiting to the critical sections of the wait () and signal () operations, and these sections are short (if properly coded, they should be no more than about ten instructions).
  • Thus, the critical section is almost never occupied, and busy waiting occurs rarely, and then for only a short time.
  • An entirely different situation exists with application programs whose critical sections may be long (minutes or even hours) or may almost always be occupied. In such cases, busy waiting is extremely inefficient.

2.9.1.3 Deadlocks and Starvation

  • The implementation of a semaphore with a waiting queue may result in a situation where two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes.
  • The event in question is the execution of a signal() operation. When such a state is reached, these processes are said to be deadlocked.
  • To illustrate this, we consider a system consisting of two processes, P0 and P1, each accessing two semaphores, S and Q, set to the value 1:


  • Suppose that P0 executes wait (S) and then P1 executes wait (Q). When P0 executes wait (Q), it must wait until P1 executes signal (Q).
  • Similarly, when P1 executes wait (S), it must wait until P0 executes signal(S). Since these signal() operations cannot be executed, P0 and P1 are deadlocked.
  • We say that a set of processes is in a deadlock state when every process in the set is waiting for an event that can be caused only by another process in the set.
  • The events with which we are mainly concerned here are resource acquisition and release. However, other types of events may result in deadlocks.
  • Another problem related to deadlocks is indefinite blocking or starvation, a situation in which processes wait indefinitely within the semaphore.
  • Indefinite blocking may occur if we remove processes from the list associated with a semaphore in LIFO (last-in, first-out) order.

2.9.1.4 Priority Inversion

  • A scheduling challenge arises when a higher-priority process needs to read or modify kernel data that are currently being accessed by a lower-priority process-or a chain of lower-priority processes.
  • Since kernel data are typically protected with a lock, the higher-priority process will have to wait for a lower-priority one to finish with the resource.
  • The situation becomes more complicated if the lower-priority process is preempted in favor of another process with a higher priority.
  • As an example, assume we have three processes, L, M, and H, whose priorities follow the order L < M < H.
  • Assume that process H requires resource R, which is currently being accessed by process L.
  • Ordinarily, process H would wait for L to finish using resource R. However, now suppose that process M becomes runnable, thereby preempting process L.
  • Indirectly, a process with a lower priority-process M-has affected how long process H must wait for L to relinquish resource R.

PRIORITY INVERSION AND THE MARS PATHFINDER

    • Priority inversion can be more than a scheduling inconvenience. On systems with tight time constraints, priority inversion can cause a process to take longer than it should to accomplish a task.
    • When that happens, other failures can cascade, resulting in system failure. Consider the Mars Pathfinder a NASA space probe that landed a robot, the Sojourner rover, on Mars in 1997 to conduct experiments.
    • Shortly after the Sojourner began operating, it started to experience frequent computer resets. Each reset reinitialized all hardware and software, including communications.
    • If the problem had not been solved, the Sojourner would have failed in its mission.
    • The problem was caused by the fact that one high-priority task, "bc_dist," was taking longer than expected to complete its work.
    • This task was being forced to wait for a shared resource that was held by the lower-priority "ASI/MET" task, which in turn was preempted by multiple medium-priority tasks.
    • The "bc_dist" task would stall waiting for the shared resource, and ultimately the "bc_sched" task would discover the problem and perform the reset.
    • The Sojourner was suffering from a typical case of priority inversion.
    • The operating system on the Sojourner was VxWorks, which had a global variable to enable priority inheritance on all semaphores.
    • After testing, the variable was set on the Sojourner (on Mars!), and the problem was solved. A full description of the problem, its detection, and its solution was written by the software team lead and is available at research.microsoft.com/ mbj /MarsYathfinder Authoritative_Account.html.

  • This problem is known as priority inversion. It occurs only in systems with more than two priorities, so one solution is to have only two priorities.
  • That is insufficient for most general-purpose operating systems, however. Typically these systems solve the problem by implementing a priority-inheritance protocol.
  • According to this protocol, all processes that are accessing resources needed by a higher-priority process inherit the higher priority until they are finished with the resources in question.
  • When they are finished, their priorities revert to their original values. In the example above, a priority-inheritance protocol would allow process L to temporarily inherit the priority of process H, thereby preventing process M from preempting its execution.
  • When process L had finished using resource R, it would relinquish its inherited priority from Hand assume its original priority.
  • Because resource R would now be available, process H-not M-would run next.

2.9.2 Classic problems of Synchronization


Figure 2.34 The structure of the producer process.

  • In this section, we present a number of synchronization problems as examples of a large class of concurrency-control problems. These problems are used for testing nearly every newly proposed synchronization scheme.
  • In our solutions to the problems, we use semaphores for synchronization.

2.9.2.1  Bounded-Buffer Problem (Producer-Consumer Problem)

  • It is commonly used to illustrate the power of synchronization primitives. Here, we present a general structure of this scheme without committing ourselves to any particular implementation.
  • We assume that the pool consists of n buffers, each capable of holding one item.
  • The mutex semaphore provides mutual exclusion for accesses to the buffer pool and is initialized to the value 1.  The empty and full semaphores count the number of empty and full buffers.
  • The semaphore empty is initialized to the value n; the semaphore full is initialized to the value 0.
  • The code for the producer process is shown in Figure 2.34; the code for the consumer process is shown in Figure 2.35. Note the symmetry between the producer and the consumer.
  • We can interpret this code as the producer producing full buffers for the consumer or as the consumer producing empty buffers for the producer.

Figure 2.35 The structure of the consumer process.

2.9.2.2 The Readers-Writers Problem

  • Suppose that a database is to be shared among several concurrent processes. Some of these processes may want only to read the database, whereas others may want to update (that is, to read and write) the database.
  • We distinguish between these two types of processes by referring to the former as readers and to the latter as writers.
  • Obviously, if two readers access the shared data simultaneously, no adverse effects will result. However, if a writer and some other process (either a reader or a writer) access the database simultaneously, chaos may ensue.
  • To ensure that these difficulties do not arise, we require that the writers have exclusive access to the shared database while writing to the database.
  • 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 involving priorities. The simplest one, referred to as the first readers-writers problem, requires that no reader be kept waiting unless a writer has already obtained permission to use the shared object.


Figure 2.36 The structure of a writer process.

  • In other words, no reader should wait for other readers to finish simply because a writer is waiting.
  • The second readers – writers problem requires that, once a writer is ready, that writer 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.
  • A solution to either problem may result in starvation. In the first case, writers may starve; in the second case, readers may starve.
  • For this reason, other variants of the problem have been proposed. Next, we present a solution to the first readers-writers problem.
  • In the solution to the first readers-writers problem, the reader processes share the following data structures:

semaphore mutex, wrt;

int readcount;

  • The semaphores mutex and wrt are initialized to 1; readcount is initialized to 0. The semaphore wrt is common to both reader and writer processes.
  • The mutex semaphore is used to ensure mutual exclusion when the variable readcount is updated. The readcount variable keeps track of how many processes are currently reading the object.
  • The semaphore wrt functions as a mutual-exclusion semaphore for the writers. It is also 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 2.36; the code for a reader process is shown in Figure 2.37.
  • Note that, if a writer is in the critical section and n readers are waiting, then one reader is queued on wrt, and n- 1 readers are queued on mutex.
  • Also observe that, when 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.
  • The readers-writers problem and its solutions have been generalized to provide reader-writer locks on same systems.
  • Acquiring a reader-writer lock requires specifying the mode of the lock either read or write access


Figure 2.37 The structure of a reader process

  • When a process wishes only to read shared data, it requests the reader-writer lock in read mode; a process wishing to modify the shared data must request the lock in write mode.
  • Multiple processes are permitted to concurrently acquire a reader-writer lock in read mode, but only one process may acquire the lock for writing, as exclusive access is required for writers.
  • Reader-writer locks are most useful in the following situations:
    • In applications where it is easy to identify which processes only read shared data and which processes only write shared data.
    • In applications that have more readers than writers. This is because reader - writer locks generally require more overhead to establish than semaphores or mutual-exclusion locks. The increased concurrency of allowing multiple readers compensates for the overhead involved in setting up the reader - writer lock.

2.9.2.3 The Dining-Philosophers Problem

  • Consider five philosophers who spend their lives thinking and eating. The philosophers share a circular table surrounded by five chairs, each belonging to one philosopher. In the center of the table is a bowl of rice, and the table is laid with five single chopsticks (Figure 2.38).


Figure 2.38 The situation of the dining philosophers.

  • When a philosopher thinks, she does not interact with her colleagues. From time to time, a philosopher gets hungry and tries to pick up the two chopsticks that are closest to her (the chopsticks that are between her and her left and right neighbors).
  • A philosopher may pick up only one chopstick at a time. Obviously, she cam1ot pick up a chopstick that is already in the hand of a neighbor.
  • When a hungry philosopher has both her chopsticks at the same time, she eats without releasing her chopsticks.
  • When she is finished eating, she puts down both of her chopsticks and starts thinking again.
  • The dining-philosophers problem is considered a classic synchronization problem neither because of its practical importance nor because computer scientists dislike philosophers but because it is an example of a large class of concurrency-control problems.
  • It is a simple representation of the need to allocate several resources among several processes in a deadlock-free and starvation-free manner.
  • One simple solution is to represent each chopstick with a semaphore.
  • A philosopher tries to grab a chopstick by executing await () operation on that semaphore; she releases her chopsticks by executing the signal() operation on the appropriate semaphores.
  • Thus, the shared data are

semaphore chopstick[5];

  • where all the elements of chopstick are initialized to 1.


Figure 2.39 The structure of philosopher i.

  • The structure of philosopher i is shown in Figure 2.39. Although this solution guarantees that no two neighbors are eating simultaneously, it nevertheless must be rejected because it could create 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.
    • Allow at most four philosophers to be sitting simultaneously at the table.
    • Allow a philosopher to pick up her chopsticks only if both chopsticks are available (to do this, 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
  • Note, however, that any satisfactory solution to the dining-philosophers problem must guard against the possibility that one of the philosophers will starve to death. A deadlock-free solution does not necessarily eliminate the possibility of starvation.

References

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

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