Synchronization Study Notes for GATE & Computer Science Engineering Exams

What is Synchronization?

Synchronization mechanisms commonly involve the use of synchronization primitives such as locks, semaphores, and condition variables. These primitives enable the serialization of access to shared resources, allowing threads or processes to coordinate their activities and avoid conflicts. Additionally, synchronization techniques encompass concepts like mutual exclusion, critical sections, and signaling, which are vital for achieving coordinated and controlled execution. It can be explained in a detailed way with the following points.

• Currency arises in three different contexts:
  • Multiple applications – Multiple programs are allowed to dynamically share processing time.
  • Structured applications – Some applications can be effectively programmed as a set of concurrent processes.
  • Operating system structure – The OS themselves are implemented as set of processes.
• Concurrent processes (or threads) often need access to shared data and shared resources.
  • Processes use and update shared data such as shared variables, files, and databases.
• Writing must be mutually exclusive to prevent a condition leading to inconsistent data views.
• Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes.

Race Condition

• The race condition is a situation where several processes access (read/write) shared data concurrently and the final value of the shared data depends upon which process finishes last
  • The actions performed by concurrent processes will then depend on the order in which their execution is interleaved.
• To prevent race conditions, concurrent processes must be coordinated or synchronized.
  • It means that neither process will proceed beyond a certain point in the computation until both have reached their respective synchronization point.

Critical Section/Region

1. Consider a system consisting of
2. n processes all competing to use some shared data.
3. Each process has a code segment, called the critical section, in which the shared data is accessed.

The Critical-Section Problem

1. The critical-section problem is to design a protocol that the processes can cooperate. The protocol must ensure that when one process is executing in its critical section, no other process is allowed to execute in its critical section.
2. The critical section problem is to design a protocol that the processes can use so that their action will not depend on the order in which their execution is interleaved (possibly on many processors).

The solution to Critical Section Problem – Requirements

• A solution to the critical-section problem must satisfy the following three requirements:
  1. Mutual Exclusion. If process Pi is executing in its critical section, then no other processes can be executing in their critical sections.
     • Implications:
       • Critical sections better be focused and short.
       • Better not get into an infinite loop in there.
       • If a process somehow halts/waits in its critical section, it must not interfere with other processes.
  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.
     • If only one process wants to enter, it should be able to.
     • If two or more want to enter, one of them should succeed.
  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.
     • Assume that each process executes at a nonzero speed
     • No assumption concerning the relative speed of the n processes.

Types of Solutions

Software solutions Algorithms whose correctness does not rely on any other assumptions.

• Hardware solutions Rely on some special machine instructions.
• Operating System solutions Provide some functions and data structures to the programmer through system/library calls.
• Programming Language solutions Linguistic constructs provided as part of a language.

Initial Attempts to Solve the Problem

• The execution of critical sections must be mutually exclusive: at any time, only one process is allowed to execute in its critical section (even with multiple processors).
• So each process must first request permission to enter its critical section.
• The section of code implementing this request is called the Entry Section (ES).
• The critical section (CS) might be followed by a Leave/Exit Section (LS).
• The remaining code is the Remainder Section (RS).

Software Solutions

• We consider first the case of 2 processes: Algorithm 1, 2 and 3
• Then we generalize to n processes: The Bakery algorithm
• Initial notation Only 2 processes, P0 and P1 When usually just presenting process Pi, always denotes other processes Pj (i != j).
• The general structure of process Pi (other processes Pj) do { entry section critical section exit section remainder section } while (1);
• Processes may share some common variables to synchronize/coordinate their actions.

Algorithm 1

Shared variables: int turn; //initially turn = 0 // turn = i, Pi can enter its critical section Process Pi do { while(turn !=i); critical section; turn=j; remainder section } while (1);

• Satisfies mutual exclusion, but not progress.

Algorithms 2

Shared variables

Boolean flag[2]; // initially flag[0]=flag[1]=false. // flag[i]=true means that P_i is ready // to enter its critical section Process Pi do { flag[i] = true; while (flag[j]); critical section flag[i] = false; remainder section } while(1);

• Satisfies mutual exclusion, but not progress requirement.

Algorithm 3

• Combined shared variables of algorithms 1 and 2.

Process Pi do {

 flag[i] = true;

 turn =j;

while (flag[j] and turn =j);

 critical section

 flag[i] = false;

 remainder section

} while(1);

• Meets all three requirements; solves the critical-section problem for two processes.

Bakery Algorithm

• The algorithm which solves the critical-section problem for n processes.
• Before entering its critical section, the process receives a number. The holder of the smallest number enters the critical section.
• If processes Pi and Pj receive the same number, if i < j, then Pi is served first; else Pj is served first.
• The numbering scheme always generates numbers in increasing order of enumeration; i.e., 1,2,3,3,3,3,4,5…
• NotationLexicographical order (ticket #, process id #)(a,b) < (c,d) if a < c or if a = c and b < dmax (a0,…, an-1) is a number, k, such that k  ai for i = 0, …, n – 1
• Shared data

Boolean choosing[n]; // Initialized to false int number[n]; //Initialized to zero do { choosing[i] = false; for(j=0; j

while( choosing[j]);

while( (number[j]!=0) && (number[j, j] < number[I,i]));

} Critical Section number[i]=0; Remainder section } while(1);

• To prove that the Bakery algorithm works, we have to show that if P_i is in its critical section and P_k (k≠i) has already chosen its number[k]≠0 then

(number[i],i)<(number[k],k)

• Consider that P_i is already in its critical section and P_k trying to enter the P_k’s critical section. When process P_k executes the second while loop for j=i, it finds that:

number[i] ≠ 0

(number[i],i)<(number[k],k) Thus it continues looping in the while loop until pi leaves the critical section.

• Note that processes enter in their critical section on a first-come, first-serve basis.

What about Process Failure

• If all 3 criteria (ME, progress, bounded waiting) are satisfied, then a valid solution will provide robustness against the failure of a process in its remainder section (RS). Since failure in RS is just like having an infinitely long RS.
• However, no valid solution can provide robustness against a process failing in its critical section (CS). A process Pi that fails in its CS does not signal that fact to other processes: for them, Pi is still in its CS.

The drawback of Software Solutions

• Processes that are requesting to enter their critical section are busy waiting (consuming processor time needlessly).
• If critical sections are long, it would be more efficient to block processes that are waiting.

Mutual Exclusion – Hardware Support

• Interrupt disabling
  • A process runs until it invokes an operating-system service or until it is interrupted
  • Disabling interrupts guarantees mutual exclusion
  • The processor is limited in its ability to interleave programs
  • Multiprocessing
    • disabling interrupts on one processor will not guarantee mutual exclusion
• Special machine instructions
  • Normally, access to a memory location excludes other access to that same location.
  • Extension: designers have proposed machine instructions that perform 2 actions atomically (indivisible) on the same memory location (e.g., reading and writing).
  • The execution of such an instruction is also mutually exclusive (even on Multiprocessors).
  • They can be used to provide mutual exclusion but need to be complemented by other mechanisms to satisfy the other 2 requirements of the CS problem.

Test And Set Synchronization Hardware

• Test and modify the content of a word atomically.

Mutual Exclusion with Test-and-Set

Shared data: boolean lock = false; Process Pi

 

Swap Synchronization Hardware

• Atomically swap two variables.

Mutual Exclusion with Swap Shared data: boolean lock = false; Process Pi

Semaphores

• A synchronization tool (provided by the OS) that does not require busy waiting.
• Logically, a semaphore S is an integer variable that, apart from initialization, can only be accessed through 2 atomic and mutually exclusive operations:
  • wait(S)
  • signal(S)

Wait and Signal Operations

• Modification to the value of semaphore (S) in the wait and signal is executed individually.
• In wait, the testing and possible modification of S must also be executed without interruption.

Usage of Semaphore

The fundamental principle of semaphore is this: Two or more processes can cooperate by means of simple signals such that a process can be forced to stop at a specified place until it has received a specified signal. Usage 1: Critical Section of n Processes Problem Shared data: semaphore mutex; //initially mutex=1 Process Pi:

Usage 2: synchronization of 2 processes

• Suppose that we have two processes, P₁ with statement s₁ and P₂ with statement s₂. We require that s₂ be executed only after s₁ has been completed. This can be done with a shared semaphore variable, mutex initialized to 0, and by inserting the following statements in P₁

s₁; signal(mutex); And the following statements in P₂ wait(mutex) s₂;

Semaphore Implementation

• A process that is blocked waiting on a semaphore should be restarted when some other process executes a signal operation. The blocked process should be restarted by a wakeup operation which put that process into the ready queue.
• The semaphore discussed so far requires a busy waiting. That is if a process is in the critical section, the other process that tries to enter its critical section must loop continuously in the entry code.
  • To overcome the busy waiting problem, the definition of the semaphore operations wait and the signal should be modified.
  • When a process executes the wait operation and finds that the semaphore value is not positive, the process can block itself. The block operation places the process into a waiting queue associated with the semaphore.
• To implement the semaphore, we define a semaphore as a record as:

• Assume two simple operations:
  • block suspends the process that invokes it.
  • wakeup(P) resumes the execution of a blocked process P.

Semaphore operations are now defined as

Types of Semaphores

• Counting semaphore – integer value can range over an unrestricted domain.
• Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement.
• Can implement a counting semaphore S as a binary semaphore.

Implementing S as a Binary Semaphore

Data structures: binary-semaphore S1, S2; int C: Initialization: S1 = 1 S2 = 0 C = initial value of semaphore S Implementing S wait operation wait(S1); C–; if (C < 0) { signal(S1); wait(S2); } signal(S1); signal operation wait(S1); C ++; if (C <= 0) signal(S2); else signal(S1);

Usage of Semaphores

• We can use binary semaphores to deal with the critical section problem for multiple processes. The n processes share a semaphore, mutex, initialized to 1.
• The value of binary semaphore can range only between 0 and 1.
• Binary semaphores are known as mutex locks as they are locks that provide mutual exclusion.
• Counting semaphores can be used to control access to a given resource consisting of a finite number of instances
• The value of a counting semaphore can range over an unrestricted domain.

Classical Problem of Process Synchronization

1. Producer-consumer problem
2. Readers-writer problem
3. Dining-philosopher problem

Bounded-Buffer Problem

Shared data semaphore full, empty, mutex; // initially full = 0, empty = n, mutex = 1

Producer Process

 

Download Byjus Exam Prep App for the best Preparation

Online Classroom Program

BYJU’S Exam Prep Test Series