Background

The Critical-Section Problem

Synchronization Hardware

Semaphores

Classical Problems of Synchronization

Critical Regions

Background

  1. Concurrent access to shared data may result in data inconsistency.

  2. Maintaining data consistency requires mechanisms to ensure the orderly execution of

      cooperating processes.

  3. Shared-memory solution to bounded-butter problem allows at most n – 1 items in buffer at 

      the same time. A solution, where all N buffers are used is not simple.

Suppose that we modify the producer-consumer code by adding a variable counter, initialized to 0 and incremented each time a new item is added to the buffer

Bounded Buffer

   1. If both the producer and consumer attempt to update the buffer concurrently,  the  

       assembly  language statements may get interleaved.

   2. Interleaving depends upon how the producer and consumer processes are scheduled.

Race Condition

   1. Race condition: The situation where several processes access – and  manipulate shared

       data concurrently. The final value of the shared data depends  upon which process  

        finishes  last.

  2. To prevent race conditions, concurrent processes must be synchronized.

The Critical-Section Problem

   1. n processes all competing to use some shared data

   2. Each process has a code segment, called critical section, in which the shared data is     

        accessed.

   3. Problem – ensure that when one process is executing in its critical section, no other   

       process is allowed to execute in its critical section.

Solution to Critical-Section Problem

  1. Mutual Exclusion. If process Pi is executing in its critical section, then no other processes

       can be executing in their critical sections.

  2. Progress. If no process is executing in its critical section and there exist some processes 

       that wish to enter their critical section, then the selection of the processes that will enter 

       the critical section next cannot be postponed indefinitely.

  3. Bounded Waiting. A bound must exist on the number of times that other processes are 

       allowed  to enter their critical sections after a process has made a request to enter its

       critical  section and before that request is granted.

   4. Assume that each process executes at a nonzero speed

   5. No assumption concerning relative speed of the n processes.

Semaphores

  1. Synchronization tool that does not require busy waiting.

  2. Semaphore S – integer variable can only be accessed via two indivisible (atomic) operations

            wait (S):

            Signal (S):

Two Types of Semaphores

  1. Counting semaphore – integer value can range over an unrestricted domain.

  2. Binary semaphore – integer value can range only between 0 and 1; can be simpler to 

       implement.

  3. Can implement a counting semaphore S as a binary semaphore.

Classical Problems of Synchronization

  1. Bounded-Buffer Problem

  2. Readers and Writers Problem

  3. Dining-Philosophers Problem

Critical Regions

  1. Regions referring to the same shared variable exclude each other in time.

  2. When a process tries to execute the region statement, the Boolean expression B is    

       evaluated.

if B is true, statement S is executed. If it is false, the process is delayed until B becomes true and

no other process is in the region associated with v.