Concurrency

Module – 4
Lecture 1
 Module 2

Interprocess Communication

 Processes executing concurrently in the operating system

may be either independent processes or cooperating
processes.

 Reasons for providing an environment that allows process

cooperation: Information sharing, Computation speedup and
Modularity
04-09-2024

2
 Module 2

Interprocess Communication

 Cooperating processes require an interprocess

communication (IPC) mechanism that will allow them to
exchange data.

 Two mechanisms: Shared Memory and Message passing

04-09-2024

3
 Module 2

Shared Memory and Message passing

Figure 3.11
Communications models.
(a) Shared memory.
04-09-2024

(b) Message passing

4
 Module 2

Shared Memory and Message passing

 Message passing is useful for exchanging smaller amounts of

data, because no conflicts need be avoided.

 Message passing is also easier to implement in a distributed

system than shared memory.

 Shared memory can be faster than message passing (More

System calls are used by message passing)
04-09-2024

5
 Module 2

IPC in Shared-Memory Systems

 IPC using shared memory requires communicating processes

to establish a region of shared memory.

 It resides in the address space of the processes

 Processes can exchange information by reading and writing

data in the shared areas.

 The form of the data and the location are determined by these
04-09-2024

processes and are not under the operating system’s control

6
 Module 2

IPC in Shared-Memory Systems

 Example for cooperating process: Producer – Consumer Problem

 A producer process produces information that is consumed by a
consumer process
 Example: Compiler – Assembler – Loader
 One solution to the Producer-Consumer problem uses shared
memory.
 A buffer will reside in a region of memory that is shared by the
04-09-2024

producer and consumer processes

7
 Module 2

IPC in Shared-Memory Systems

 A producer can produce one item while the consumer is

consuming another item.

 The producer and consumer must be synchronized, so that

the consumer does not try to consume an item that has not
yet been produced.

 unbounded buffer and bounded buffer

04-09-2024

8
 Module 2

Memory shared by Producer and consumer Processes

04-09-2024

9
 Module 2

The producer process using shared memory

04-09-2024

10
 Module 2

The consumer process using shared memory

04-09-2024

11
 Module 2

Producer – Consumer Problem

 Write a C program to implement the producer consumer

problem.
04-09-2024

12
 Module 2

IPC in Message-Passing Systems

 Message passing provides a mechanism to allow processes to

communicate and to synchronize their actions without
sharing the same address space.

 useful in a distributed environment

Example: an Internet chat program

04-09-2024

13
 Module 2

IPC in Message-Passing Systems

 A message-passing facility provides at least two operations:

send(message) and receive(message)

 Messages sent by a process can be either fixed or variable in

size

 If processes P and Q want to communicate, they must send

messages to and receive messages from each other: a
04-09-2024

communication link must exist between them.

14
 Module 2

IPC in Message-Passing Systems

Methods for logically implementing a link for send()/receive()

operations:

1. Direct or indirect communication

2. Synchronous or asynchronous communication

3. Automatic or explicit buffering

04-09-2024

15
 Module 2

IPC in Message-Passing Systems

Direct communication

 Here, each process that wants to communicate must

explicitly name the recipient or sender of the communication
 send(P, message)—Send a message to process P.

 receive(Q, message)—Receive a message from process Q.

 A link is established automatically between every pair of

04-09-2024

processes that want to communicate.

16
 Module 2

IPC in Message-Passing Systems

symmetry addressing and asymmetry addressing

Example for asymmetry in addressing

 send(P, message)—Send a message to process P.

 receive(id, message)—Receive a message from any process

04-09-2024

17
 Module 3

IPC in Message-Passing Systems

 With indirect communication, the messages are sent to and
received from mailboxes, or ports.

 A mailbox can be viewed abstractly as an object into which

messages can be placed by processes and from which
messages can be removed.

 Each mailbox has a unique identification.

04-09-2024

18
 Module 3

IPC in Message-Passing Systems

 A process can communicate with another process via a
number of different mailboxes, but two processes can
communicate only if they have a shared mailbox.

 Primitives for indirect communication

 send(A, message)—Send a message to mailbox A.
04-09-2024

 receive(A, message)—Receive a message from mailbox A.

19
 Module 3

IPC in Message-Passing Systems

 A process can communicate with another process via a number of
different mailboxes, but two processes can communicate only if
they have a shared mailbox.

 A mailbox may be owned either by a process or by the operating

system

 Primitives for indirect communication

 send(A, message)—Send a message to mailbox A.
04-09-2024

 receive(A, message)—Receive a message from mailbox A.

20
 Module 3

IPC in Message-Passing Systems

 Message passing may be either blocking or nonblocking— also
known as synchronous and asynchronous.
 Blocking send. The sending process is blocked until the message is
received by the receiving process or by the mailbox.
 Nonblocking send. The sending process sends the message and resumes
operation.
 Blocking receive. The receiver blocks until a message is available.
 Nonblocking receive. The receiver retrieves either a valid message or a
04-09-2024

null.

21
 Module 3

IPC in Message-Passing Systems

Buffering

 Whether communication is direct or indirect, messages

exchanged by communicating processes reside in a
temporary queue.

 Basically, such queues can be implemented in three ways:

Zero capacity, Bounded capacity and Unbounded capacity
04-09-2024

22
 Module 3

IPC in Message-Passing Systems

Buffering
 Zero capacity. The queue has a maximum length of zero
 Bounded capacity. The queue has finite length n; thus, atmost n
messages can reside in it.
 Unbounded capacity. The queue’s length is potentially infinite
The zero-capacity case is sometimes referred to as a message
system with no buffering. The other cases are referred to as systems
04-09-2024

with automatic buffering

23
C o n currency
Module 4
 Module 4

Synchronization
 A cooperating process is one that can affect or be affected by
other processes executing in the system.
 Cooperating processes can either directly share a logical
address space or be allowed to share data only through shared
memory or message passing.
 Concurrent access to shared data may result in data
inconsistency
 Module 4

Synchronization - Objective
 The main objective of process synchronization is to
 E n sure that m u ltiple processes access sh ared resou rces
without interfering with each other and

 To prevent the possibility of incon sisten t data due to

concurrent access.
 Module 4

Synchronization
 It is the way by which processes that share the same memory
space are managed in an operating system.

 It helps maintain the consistency of data by using variables

or hardware so that only one process can make changes to
the shared memory at a time.

 Inconsistency of data can occur when various processes

share a common resource in a system which is why there is a
need for process synchronization in the operating system.
 Module 4

Synchronization
 Module 4

Synchronization

 If a process1 is trying to read the data present in a memory

location while another process2 is trying to change the data
present at the same location, there is a high chance that the
data read by the process1 will be incorrect.
 Module 4

Synchronization- Producer Consumer Problem

 Module 4

Synchronization - Producer Consumer Problem

Since both processes manipulate the variable count concurrently, a

situation like this occurs where several processes access and
manipulate the same data concurrently and the outcome of the
execution depends on the particular order in which the access takes
place, is called a race condition.

To guard against the race condition, we need to ensure that only one
process at a time can be manipulating the variable count.
 Module 4

The Critical Section Problem

Consider a system consisting of n processes {P0, P1, ..., Pn−1}. Each

process has a segment of code, called a critical section, in which the
process may be accessing and updating data that is shared with at least
one other process.

The important feature is when one process is executing in its critical

section, no other process is allowed to execute in its critical section.

The critical-section problem is to design a protocol that the processes

can use to synchronize their activity so as to cooperatively share data.
 Module 4

The Critical Section Problem

Each process must request permission to enter its critical section.

The section of code implementing this request is the entry section.

The critical section may be followed by an exit section.

The remaining code is the remainder section.

 Module 4

Elements/Sections of a Program/Process
 Entry Section: The entry Section decides the entry of a process.
 Critical Section: The Critical section allows and makes sure that
only one process is modifying the shared data.

 Exit Sec tion: The entry of oth er processes in the shared data
after the execution of one process is handled by the Exit section.

 Remainder Section: The remaining part of the code which is not

categorized as above is contained in the Remainder section.
 Module 4

Critical Section Problem - Primitives

 Module 4

Requirements for Synchronization

A solution to the critical-section problem must satisfy the following
three requirements:

 Mutual exclusion: If a process is running in the critical section, no

other process should be allowed to run in that section at that time.
 Progress: If no process is executing in its critical section and some processes
wish to enter their critical sections, then only those processes that are not
executing in their remainder sections can participate in deciding which will
enter its critical section next, and this selection cannot be postponed
indefinitely.
 Module 4

Requirements for Synchronization

 Bounded waiting. There exists a bound, or limit, 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.
 Module 4

Race Condition
 When more than one process is either running the same
code or modifying the same memory or any shared data,
there is a risk that the result or value of the shared data
may be incorrect because all processes try to access and
modify this shared resource. This condition is called the race
condition.
 Module 4

Race Condition
 Since many processes use the same data, the results of the
processes may depend on the order of their execution
(Sequence of their execution)

 In the critical section, a race condition occurs when the

end result of multiple thread executions varies
depending on the sequence in which the threads execute.
 Module 4

Race Condition Example

Figure: Race condition when assigning a pid

 Module 4

Critical Section Problem

 The critical-section problem could be solved simply in a

single-core environment if we could prevent interrupts from
occurring while a shared variable was being modified.

 This solution is not as feasible in a multiprocessor environment.

 Module 4

Critical Section Problem

 Two general approaches are used to handle critical sections in

operating systems: preemptive kernels and nonpreemptive kernels.
 A preemptive kernel allows a process to be preempted while it is
running in kernel mode.
 A nonpreemptive kernel does not allow a process running in kernel
mode to be preempted; a kernel-mode process will run until it exits
kernel mode, blocks, or voluntarily yields control of the CPU.
 Module 4

Critical Section Problem

 A nonpreemptive kernel is essentially free from race conditions on

kernel data structures.

 A preemptive kernel may be more responsive, since there is less risk that a
kernel-mode process will run for an arbitrarily long period before
relinquishing the processor to waiting processes.
 Module 4

Critical Section Problem – What is the Problem?

 A critical section is a code segm ent that can be accessed by

only one process at a time. (How to do it?)

 Design ing a way for cooperative processes to access sh ared

resources without creating data inconsistencies.
 Module 4

Critical Section Problem – Peterson's solution

 a classical software-based solution.
 This solution makes sure that only one process executes the
critical section at any point in time.

 It is restricted to two process that alternate execution between

the critical execution and remainder execution.
 Module 4

Critical Section Problem – Peterson's solution

Peterson's solution

Two shared variables that are used by the processes.

 A boolean flag[]: A Boolean array Flag indicates if a process
is ready to enter into its critical section

 int turn: indicates whose turn it is to enter into critical

section.
 Module 4

Critical Section Problem – Peterson's solution

Peterson's solution
/ / Shared variables
bool flag[2] = {false, false}; / / Initially both flags are false
int turn = 0; / / Initially turn is 0 (P1's turn)
 Module 4

Critical Section Problem – Peterson's solution

 Module 4

Critical Section Problem – Peterson's solution

while (true) { while (true) {
flag[i] = true;
flag[j] = true;
tu rn = j; //giving priority to Pj (the jth
process) in case Pj is also trying to enter the turn = i;
critical section.
while (flag[i] & & turn == i) {
while (flag[j] & & turn == j) {
/ / Busy wait until process i's flag
/ / Busy wait until process j's flag is false
is false or turn is j
or turn is i

} }

/ / Critical Section (Pi) / / Critical Section (Pj)

flag[i] = false; / / Process i has exited C S
flag[j] = false; / / Process j has exited C S
 Module 4

Critical Section Problem – Peterson's solution

 E a c h process has a flag variable (e.g., flag[0] for P0 and flag[1] for P1).
 The flag[i] is set to tru e when process Pi wants to enter the critical
section, signaling its intent.

 A turn variable is used to decide which process should proceed if both

processes are trying to enter the critical section simultaneously.

 This ens u res that the oth er process gets a fair chan ce to access the
critical section.
 Module 4

Critical Section Problem – Peterson's solution

 Before Entering the Critical Section:

 A process Pi sets flag[i] = tru e, indicating it wants to enter the
critical section.
 It then sets turn = j, where j is the index of the other process (e.g., if
i = 0, then j = 1).
 The process then enters a busy-wait loop: while (flag[j] & & turn ==
j).
 Module 4

Critical Section Problem

 Before Entering the Critical Section:
 This loop will only exit if the other process Pj is not interested in
entering the critical section (flag[j] = false) or if the current process
Pi is allowed to enter because the turn is in its favor (turn != j).

 Critical Section:
 Once the loop exits, process Pi enters the critical section. At this
point, Pi can safely access shared resources without interference
from Pj.
 Module 4

Critical Section Problem

 Exiting Critical Section:

 After finishing the work in the critical section, process Pi sets flag[i]
= false, indicating it no longer needs access to the critical section .
This action allows the other process Pj to proceed if it is waiting.
 Module 4

Critical Section Problem

 Boolean flag and turn are both shared variable

 Initially, the flags are false.

 When a process wants to execute its critical section, it sets its

 flag to true and

 turn into the index of the other process

 This means that the process wants to execute but it will allow the other process
to run first.
 Module 4

Critical Section Problem

 Set flag[i] to true to indicate its intention to enter the critical section.

 Set turn to j to yield the right to enter the critical section to process j.
 Enter a busy waiting loop, checking if flag[j] is true and if turn is j. If both
conditions are met, the process continues waiting.

 Once the conditions are no longer met, the process enters its critical section.
 After exiting the critical section, set flag[i] to false to indicate that it has
finished.
 Module 4

Critical Section Problem

Peterson's solution
 The process perform s busy waiting u n til the other process
has finished its own critical section.

 After this, the current process enters its critical section

 After completin g the critical section, it sets it’s own flag to
false, indicating it does not wish to execute anymore
 Module 4

Critical Section Problem

Peterson's solution
Busy Waiting:
 Busy waiting is a technique in which a process repeatedly checks a
condition to enter its critical section instead of being blocked.

 Busy waiting occurs in the while loops where each process checks the
flag and turn variables to determine if it’s safe to enter its critical
section.
 During busy waiting, the process consumes C P U cycles while it waits
for the condition to become true.
 Module 4

Critical Section Problem

Peterson's solution – Points
 The turn variable acts as a tie-breaker when both processes
want to enter the critical section at the same time.

 If both processes set their respective flag to true (indicating

their intent to enter the critical section), the turn variable
helps to decide which process gets to enter first.
 Module 4

Critical Section Problem – Bakery Algorithm

 Module 4

Critical Section Problem – Bakery Algorithm

Bakery Algorithm
 Design ed to ensu re that only one process can access a
critical section at a time.

 It is suitable when we have many number of process i.e. n>2

 It's particu larly u sefu l in distrib u ted systems where

processes might be running on different machines.
 Module 4

Critical Section Problem

Bakery Algorithm

 E a ch process is assign ed a u n ique ticket n u m ber. These

numbers are ordered lexicographically, meaning they are
compared based on their individual digits from left to right.

 Before entering the critical section, a process acquires a ticket

number. This number is determined by finding the maximum
ticket number among all other processes and then incrementing
it.
 Module 4

Critical Section Problem

Bakery Algorithm
 A process waits until its ticket number is the smallest among all
processes that are currently trying to enter the critical section or have
already entered.
 Once a process has the smallest ticket number, it can enter the critical
section.
 After exiting the critical section, the process releases its ticket,
allowing other processes to acquire tickets and enter the critical
section.
 Module 4

Critical Section Problem

Bakery Algorithm - Example

Consider three processes, P1, P2, and P3.

 Initial State: All processes have their tickets set to 0.

 P1 Acquires Ticket: P1 acquires ticket number 1.

 P2 Acquires Ticket: P2 acquires ticket number 2.

 P3 Acquires Ticket: P3 acquires ticket number 3.

 Module 4

Critical Section Problem

Bakery Algorithm - Example
 Now, P1 has the sm allest ticket n u m ber and can enter the
critical section.

 After P1 finishes and releases its ticket,

 P2 has the smallest ticket number and can enter.

 Finally, P3 will enter.

Bakery Algorithm
Bakery Algorithm
 Module 4

Critical Section Problem – Bakery Algorithm

repeat
choosing[i] := true;
number[i] := max(number[0], number[1], . . . , number[n-1]) + 1;
choosing[i] := false;
for j := 0 to n - 1 do
begin
while choosing[j] do no-op; / / Wait until process j finishes choosing
its number
while n u m ber[j] != 0 and (nu m ber[j], j) < (nu m ber[i], i) do no-op; / /
Wait until it's i's turn
end;
/ / Critical section
number[i] := 0; / / Exit the critical section
/ / Remainder section
until false;
 Module 4

Critical Section Problem

Bakery Algorithm - Points
 Fairness: It ens u res that all processes eventu ally get to enter the
critical section, preventing starvation.
 Freedom from S tarvation: No process is indefinitely preven ted from
entering the critical section.
 Freedom from Deadloc k: The algorith m preven ts deadlocks by
ensuring that processes always make progress.
 Distributed: It can be u sed in distributed systems where processes
may be running on different machines.
 Module 4

Critical Section Problem

Bakery Algorithm - Points

 Choosing Array (choosing[i]):

 This is a boolean array where choosing[i] is set to true when process
i is selecting a number (a "ticket") for itself before entering the critical
section. It is set to false once the process has chosen its number
 Module 4

Critical Section Problem

Bakery Algorithm - Points

 Number Array (number[i]):

 This array holds the number (or "ticket") for each process. The
number represents the process's place in line to enter the critical
section.

 A higher number means the process will wait longer, and a lower
number means it gets to enter sooner.
 Module 4

Critical Section Problem

Bakery Algorithm - Points

 Choosing the number or Ticket

 choosing[i] := true;: Process i sets its choosing flag to tru e

indicating that it's in the process of choosing a number.
 Number[i] := max(number[0], number[1], . . . , number[n-1]) + 1;:
Process i picks a number that is one greater than the maximum
number in the number array. This step ensures that each
process gets a unique and sequential number.
 Module 4

Critical Section Problem

Bakery Algorithm - Points
 ch oosin g[i] := false;: Process i sets its ch oosin g flag to false
after it has chosen its number.
 Module 4

Critical Section Problem

Bakery Algorithm - Points

 Waiting to Enter the Critical Section:

 for j := 0 to n - 1: Process i checks all other processes j.

 while choosing[j] do no-op;: Process i waits until process j
finishes choosing its number. This ensures that if j is in the
middle of choosing its number, i does not make a decision
based on incomplete information.
 Module 4

Critical Section Problem

Bakery Algorithm - Points

 Waiting to Enter the Critical Section:

 while number[j] != 0 and (number[j], j) < (number[i], i) do no-op;:

 If process j has a lower n u m ber (indicating it has higher priority) and j
has not yet entered the critical section (number[j] != 0), process i will wait.

 If n u m ber[j] == n u m ber[i], the process with the sm aller index j gets

priority. This ensures fairness and prevents deadlock.
 Module 4

Critical Section Problem

Bakery Algorithm - Points
 Entering the Critical Section:
 Once process i has confirmed that it has the smallest number (or highest
priority) among all competing processes, it proceeds to enter the critical
section.

 Exiting the Critical Section:

 number[i] := 0;: After finishing in the critical section, process i resets its
number to 0, indicating that it no longer wishes to enter the critical
section.
 Module 4

Critical Section Problem

Bakery Algorithm - Points

 Remainder Section:
 The process can then perform oth er non -critical operations before
repeating the process if it needs to enter the critical section again.
 Module 4

Critical Section Problem

Bakery Algorithm - Points
 S im plest kn own solu tions to the m utu al exclu sion problem for n
processes.
 E n su res that shared resou rces are u sed efficiently in a
multithreaded environment.

 It is free from starvation.

 It uses FIFO
 It works with atomic registers.
 Module 4

Critical Section Problem

Bakery Algorithm - Points
 It is unreliable because any one of the processes can fail and
halt progress.
C o n currency
Module 4
 Module 4

Critical Section Problem

Hardware Support for Synchronization
 Module 4

Critical Section Problem

Hardware Support for Synchronization

Hardware-based solutions for critical sections leverage

specialized instructions provided by the processor to ensure
mutual exclusion.
These instructions are atomic, meaning they execute as a
single, indivisible operation, preventing other processes from
interfering.
Critical Section Problem
Critical Section Problem
 Module 4

Critical Section Problem

Synchronization Hardware 1 – Test and S et
 It's a locking mechanism that prevents multiple processes from
accessing the same resource

 A shared Boolean variable, commonly known as a 'lock', is used.

 When a process wants to access a resource, it 'tests' the lock. If
the lock is false (unlocked), the process sets it to true (locked)
and proceeds with its task. If the lock is true, the process waits
until it's released.
An Example
 Module 4

Critical Section Problem

Synchronization Hardware 1 – Test and S e t

boolean lock = false;

boolean TestAndSet(boolean &target){
boolean returnValue = target;
target = true;
return returnValue;
}
while(1){
while(TestAndSet(lock));
CRITICAL S E C T I O N C O D E ;
lock = false;
REMAINDER SECTION CO D E ;
}
 Module 4

Critical Section Problem

Synchronization Hardware 1 – Test and Synchronization Hardware 1 – Test and
Set Set
Thread 1:
Thread 2:
 Enters the outer while(1) loop.
 Enters the inner while(TestAndSet(lock))  Enters the outer while(1) loop.
loop.  Enters the inner while(TestAndSet(lock))
 TestAndSet sets lock to true and returns loop.
false, exiting the inner loop.  TestAndSet sees that lock is already true
 Executes the CRITICAL S E C T I O N C O D E .
and retu rns true, con tinu ing the inn er
 Sets lock to false.
 E x ecutes the RE M AIND E R S E C TION loop.
CODE.  Thread 2 will keep spinning in this loop
 Goes back to the beginning of the outer until Thread 1 releases the lock.
loop.
 Module 4

Critical Section Problem

Synchronization Hardware 1 – Test and S et

 The target parameter in the function is passed by reference,

meaning that any changes made to target within the
function will also affect the original variable that was passed
to the function. In this case, the original variable is lock.
 Module 4

Critical Section Problem

Synchronization Hardware 2 – Compare and Swap
It involves two operations: 'swap' and 'unlock’.
A boolean lock variable is used here as well.

The 'swap' operation exchanges the valu e of the lock with a local
variable.

If the lock was false, it becomes true, and the process proceeds.
The 'unlock' operation sets the lock back to false when the process
is done.
Synchronization Hardware 2 – Compare and Swap

// Mutual exclusion with the

compare and swap() instruction.

Figure Mutual exclusion with the compare and swap() instruction

 Module 4

Critical Section Problem – Compare and Swap

Synchronization Hardware 2 – Swap
boolean lock = false;
individual key = false;

void swap(boolean &a, boolean &b){

boolean temp = a;
a = b;
b = temp;
}

while(1){
key=true;
while(key==true)
{
swap(lock,key);
}

CRITICAL SECTION C O D E
lock = false;
REMAINDER SECTION C O D E
 Module 4

Critical Section Problem

Synchronization Hardware – Compare and Swap
 E a c h process executes the following loop:
 Sets its key to true, indicating its intention to enter the critical section.
 While key is still true, repeatedly swaps the values of lock and key.
 If the swap operation is successful (i.e., lock was false and key was true), the
process has acquired the lock and can enter the critical section.
 After executing the critical section, the process sets lock to false to release the
lock for other processes.
 The loop continues, allowing the process to try entering the critical section again
if necessary.
 Module 4

Critical Section Problem

Synchronization Hardware – Compare and Swap
 The com pare_ a n d_s wap instru ction attem pts to atom ically
update the lock variable.

 If the lock is cu rrently 0, it is set to 1, indicating that the

process has entered the critical section.

 If the lock is already 1, the process retries the loop u n til it

successfully acquires the lock.
 Module 4

Critical Section Problem

Synchronization Hardware – Compare and Swap

 Variables:
 key: A boolean variable for each process, indicating wheth er
the process is trying to enter the critical section.

 lock: A shared boolean variable representing the lock for the

critical section.
Process Synchronization – Mutex

 The hardware-based solutions to the critical-section problem are

complicated as well as inaccessible to application programmers.
 Operating-system designers build higher-level software tools to
solve the critical-section problem, one such tool is MUTEX.
 The mutex lock is used to protect critical sections and thus prevent
race conditions.
 A process must acquire the lock before entering a critical section; it
releases the lock when it exits the critical section. The
acquire()function acquires the lock, and the release() function
releases the lock
Process Synchronization – Mutex

 A mutex lock has a boolean variable available whose value indicates

if the lock is available or not.
 A process that attempts to acquire an unavailable lock is blocked
until the lock is released.
 Calls to either acquire() or release() must be performed atomically.
 The main disadvantage of the implementation is that it requires
busy waiting.
 Busy waiting wastes CPU cycles that some other process might be
able to use productively
Process Synchronization – Mutex

The type of mutex lock is also called a spinlock because the

process “spins” while waiting for the lock to become
available.
Solution to the critical-section problem using mutex locks
Process Synchronization – Semaphores
Process Synchronization – Semaphores
Semaphores
 A semaphore S is an integer variable that is accessed only
through two standard atomic operations: wait() and signal().

 Introduced by the Dutch scientist Edsger Dijkstra

 the wait() operation was originally termed P (to test) and signal() was
originally called V (to increment)
Process Synchronization – Semaphores
Semaphores
 U sed to enforce m u tu al exclu sion, avoid race conditions , and
implement synchronization between processes.

 Binary Semaphore and Counting Semaphore

Process Synchronization – Semaphores
Semaphores – Primitives - wait (P) and signal (V).
Process Synchronization – Semaphores
Semaphores – Primitives - wait (P) and signal (V).
 The wait operation decrements the value of the semaphore,
and the signal operation increments the value of the
semaphore.

 When the value of the semaphore is zero, any process that

performs a wait operation will be blocked until another
process performs a signal operation.
Process Synchronization
Semaphores – Primitives - wait (P) and signal (V).
 When a process perform s a wait operation on a sem aph ore,
the operation ch ecks wheth er the valu e of the sem aph ore is

>0.
 If so, it decrem ents the valu e of the sem aph ore and lets the
process continue its execution;

 otherwise, it blocks the process on the semaphore

Process Synchronization
Semaphores – Primitives - wait (P) and signal (V).
 A signal operation on a semaphore activates a process
blocked on the semaphore if any or increments the value of
the semaphore by 1.

 Due to these semantics, semaphores are also called counting

semaphores.
Process Synchronization
Semaphores – Primitives - wait (P) and signal (V).
 Wait()/Down()/P()- Helps in controlling the entry of processes
in C S . The operation decrements the value of its argument as
soon as a process enters the critical section.

 Signal()/UP()/V()- Helps control the process's exit after

execution from C S . Increment the value of its argument as
soon as the execution is finished.
Process Synchronization

Semaphore
Types

Binary Counting
Semaphore Semaphore
Process Synchronization
Binary Semaphores

 This is also known as a mutex lock.

 It can have only two values 0 and 1.

 Its value is initialized to 1.

 It is u sed to implem en t the solu tion of critical section
problems with multiple processes.
Process Synchronization
Binary Semaphores
Process Synchronization
Binary Semaphores
 If the value of the semaphore was initially
1, then on the entering of the process into
the critical section, the wait function
would have decremented the value to 0
meaning that no more processes can
access the critical section (making sure of
mutual exclusion -- only in binary
semaphores).
Process Synchronization
Binary Semaphores
 Once the process exits the critical
section, the signal operation is
executed an d the valu e of the
semaphore is incremented by 1,
mean in g that the critical section can
now be accessed by another process.
Process Synchronization
Binary Semaphores
int semaphore = 1;
void P() {
while (semaphore == 0) {
/ / Busy waiting until the semaphore is unlocked
}
semaphore = 0;
void V() {
semaphore = 1; / / Unlock the semaphore (exit critical section)
}
Process Synchronization
Counting Semaphores
 Counting semaphores can be used to control access to a given
resource consisting of a finite number of instances.
 Coordinate access to resources
 Here, the Semaphore count is the number of resources available
 If the value of the Semaphore is anywhere above 0, processes can
access the critical section or the shared resources.
 The n u m ber of processes that can access the resou rces/ code is
the value of the semaphore
Process Synchronization
Counting Semaphores
 if the value is 0, it means that there aren't any resources that
are available, or the critical section is already being accessed
by several processes and cannot be accessed by more
processes.
 Counting semaphores are generally used when the number of
instances of a resource is more than 1, and multiple
processes can access the resource.
Process Synchronization
Counting Semaphores
Process Synchronization
Counting Semaphores
 P() (Wait): This decreases the value of the semaphore. If the
value is greater than 0, the process can proceed. If it is 0, the
process must wait until the value becomes greater than 0.

 V() (Signal): This increases the value of the semaphore,

signaling that a resource has been released and is available
for other processes
Process Synchronization
Counting Semaphores
int semaphore = 3;
void P() {
while (semaphore == 0) {
/ / Busy waiting until a resource becomes available
}
semaphore--; / / Decrease the semaphore value (acquire a resource)
}
void V() {
semaphore++; / / Increase the semaphore value (release a resource)
}
/ / Example usage with multiple processes using a shared resource
Process Synchronization
Semaphores Disadvantage

Busy Waiting
- it wastes CPU cycles

- It is also called as Spinlock

Process Synchronization – Monitors
Process Synchronization – Monitors

 Monitors are a programming language component that aids

in the regulation of shared data access.

 The Monitor is a package that contains shared data

structures, operations, and synchronization between
concurrent procedure calls.
Process Synchronization – Monitors

 An abstract data type—or ADT—encapsulates data with a set of

functions to operate on that data that are independent of any
specific implementation of the ADT.

 A monitor type is an ADT that includes a set of programmer-

defined operations that are provided with mutual exclusion
within the monitor.
Process Synchronization
Why Monitor?
 Various types of errors can be generated easily when
programmers use semaphores or mutex locks incorrectly

 S o we n e e d a h i gh - l eve l synchronization tool

Process Synchronization
Monitor
 Processes operating outside
the monitor can't access
the monitor's internal
variables, but they can
call the monitor's
procedures.
Fig: Pseudocode syntax of a monitor
Process Synchronization
Monitor

 monitor_name is the name of the monitor

 p1, p2, pn are the procedures that provide access to sh ared
data and variables enclosed in monitors

 It ensu re that only one thread is accessed at a time for u sing

the shared resource.
Process Synchronization
Monitor - Components
 Initialization: Initialization code is executed when a monitor is
initialized. It is needed once when the monitors are created and
initialized.

 It helps initialize any shared data structures that the monitor will
use to perform specific tasks.

 Initialization code is used to initialize a variable when we want to

use it.
Process Synchronization
Monitor - Components
 Private D ata: It is an essential featu re of mon itors that helps
make the data private.

 It is involved in holding mon itors’ confidential data , which

includes private functions.

 Private fields and fun ction s are not visible ou tside of the
monitor.
Process Synchronization
Monitor - Components
 Monitor Procedure: Procedures operate on shared variables
defined inside the monitor.
 Monitor procedures or fun ction s can be invoked outside the
monitor.
 These are fun ction s or meth ods which are executed within the
monitors’ context.

 They are usually used for shared resource manipulation.

Process Synchronization
Monitor - Components
 Queue: Queue data structure maintains a list of threads waiting
for a shared resource.

 Whenever we request a thread to use shared resources, but

another thread is currently using the shared resource, then we
cannot use the shared resource at that time.

 But whenever the resource is in its available state, the thread at

the front is granted access to the resource.
Process Synchronization – About Monitor

A function defined within a monitor can access only those variables

declared locally within the monitor and its formal parameters.

The monitor construct ensures that only one process at a time is active
within the monitor.

In monitor, to provide synchronization additional mechanisms are

provided by the condition construct.
Process Synchronization - Monitor

 Condition Variables: A programmer who needs to write a tailor-

made synchronization scheme can define one or more variables of
type condition: condition x, y;
 The only operations that can be invoked on a condition variable are
wait() and signal(). The operation [Link](); means that the process
invoking this operation is suspended until another process invokes
[Link]();
Process Synchronization
 Wait() Function: This function is used for releasing a mutex associated with the monitor.
 It waits for a particular condition to be valid.
 A mutex is a program object that enables sharing of the same resources by multiple
programs by taking turns.
 When a thread calls the wait() function, it adds a thread to the list and puts it to sleep.
 It releases the mutex and enters a blocked state until another thread signals the
condition.
 Therefore, variables are suspended and placed in the condition variables' block queue
whenever we perform a wait operation.

 Signal() Function: This function is used to wake up a waiting thread.

 When a thread calls the function, it allies the thread to proceed by waking it up.
 This function gives a chance to one of the blocked variables.
Process Synchronization
Monitor – Overall Working
 When a thread wants to access the shared data, it enters the monitor. If no
other thread is using the monitor, the thread proceeds.

 If another thread is already inside the monitor, the new thread is blocked until
the monitor becomes available (the current thread exits the monitor).

 Inside the monitor, condition variables can be used to let a thread wait until a
specific condition is met (e.g., waiting for input or for a buffer to be filled).
When this condition occurs, another thread signals it, allowing the waiting
thread to proceed
Process Synchronization
Schematic view of a monitor.
Process Synchronization
Monitor with condition variables
Implementing a Monitor Using Semaphores
Implementation of the monitor mechanism using semaphores.
 For each monitor, a binary semaphore mutex (initialized to 1) is
provided to ensure mutual exclusion.
 A process must execute wait(mutex) before entering the monitor and
must execute signal(mutex) after leaving the monitor.
 Signaling processes can use an additional binary semaphore, next
(initialized to 0). to suspend themselves.
 An integer variable next count is also provided to count the number
of processes suspended on next.
Resuming Processes within a Monitor
How do we determine which of the suspended processes should be
resumed next? FCFS (or)
 the conditional wait construct can be used- [Link](c);
 where c is an integer expression that is evaluated when the wait()
operation is executed. The value of c, which is called a priority
number, is then stored with the name of the process that is
suspended.
 When [Link]() is executed, the process with the smallest priority
number is resumed next.
Implementing a Monitor Using Semaphores

A monitor to allocate a single resource

Resuming Processes within a Monitor
How do we determine which of the suspended processes should be
resumed next?

Resource allocate monitor

 Each process, when requesting an allocation of this resource,
specifies the maximum time it plans to use the resource.
 The monitor allocates the resource to the process that has the
shortest time-allocation request.
Resuming Processes within a Monitor
How do we determine which of the suspended processes should be
resumed next?
A process that needs to access the resource in question must observe
the following sequence:
[Link](t);
…. access the resource;
[Link]();
where R is an instance of type ResourceAllocator.
Resuming Processes within a Monitor

Problems that are faced by the monitor

• A process might access a resource without first gaining access
permission to the resource.
• A process might never release a resource once it has been granted
access to the resource.
• A process might attempt to release a resource that it never requested.
• A process might request the same resource twice
Resuming Processes within a Monitor
Solutions
Include the resource access operations within the ResourceAllocator
monitor.
Check for two conditions to establish the correctness of this system
- user processes must always make their calls on the monitor in a
correct sequence
- Ensure that an uncooperative process does not simply ignore the
mutual-exclusion gateway provided by the monitor and try to access
the shared resource directly, without using the access protocols
C o n currency
Module 4
 Module 4

Classic Problems of Synchronization

 Module 4

The Bounded-Buffer Problem

• Producer-consumer problem
• The pool consists of n buffers, each capable of holding one item.
• The producer must not insert data when the buffer is full and the
consumer must not consume data when the buffer is empty
• The producer and consumer should not operate simultaneously
 Module 4

The Bounded-Buffer Problem

Solution using Semaphore – Data structures used

m (mutex) – binary semaphore to acquire and release the lock
empty – a counting semaphore whose initial value is the number of
buffers in the pool (i.e. initially the pool is empty)
Full – a counting semaphore whose initial value is 0
 Module 4

The Bounded-Buffer Problem

Solution using Semaphore

 Module 4

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, read and write)
the database.
 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.
 Module 4

The Readers Writers Problem

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
 Module 4

The Readers Writers Problem

Several ways to implement

1. No reader be kept waiting unless a writer has already

obtained permission to use the shared object
2. Once a writer is ready, that writer perform its write as
soon as possible

But these solutions may lead to starvation

 Module 4

The Readers Writers Problem

Implementation using Semaphore

1. mutex, a semaphore (initialized to 1) which is used to

ensure mutual exclusion when readcount is updated.
2. wrt, a semaphore (initialized to 1) common to both reader
and writer processes
3. Readcount – an integer variable (intialized to 0) that
keeps track of how many processes are currently reading the
object.
 Module 4

The Bounded-Buffer Problem

Solution using Semaphore

 Module 4

The Dining-Philosophers Problem

- problem definition
- classic synchronization problem

Figure: The situation of the dining philosophers.

 Module 4

Critical Section Problem

Data structures used

Philosopher executes a wait() on semaphore to grab a chopstick

Use signal() to release a chopstick

Five chopsticks- five semaphore i.e. semaphore chopstick[5];

Synchronization Hardware 2 – Compare and Swap

No t wo Phi l o so pher wi l l st art eat at a t i me

Th en t he so l ut i o n i s fi n e.
 Module 4

Critical Section Problem

Several possible remedies to the deadlock problem are the

following:
• 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
• Use an asymmetric solution—that is, an odd-numbered philosopher
picks up first her left chopstick and then her right chopstick, whereas
an even numbered philosopher picks up her right chopstick and then
her left chopstick.
Multiprocessors and Locking
Multiprocessors and Locking
In multiprocessor systems, where multiple processors share resources and
execute processes concurrently, locking mechanisms are critical for ensuring
data consistency, preventing race conditions, and coordinating access to shared
resources.

Without proper synchronization, concurrent access can lead to inconsistent

states.

Locks are synchronization primitives used to control access to shared

resources.
Multiprocessors - Shared Memory Architecture - UMA
Multiprocessors - Shared Memory Architecture - NUMA
Uniform Memory Access (UMA)

Fig. Cache coherence problem

Uniform Memory Access (UMA)

Cache coherence – data inconsistency problem at caches in multiprocessor system

• Cache Write policies: Write through and write back

• Cache Coherence Schemes:

• Write through + write back
• Write invalidate + write update + Write back - policies

• Snooping" protocols are typically used to maintain cache coherence on centralized Multiprocessors.

• Processor Synchronization – Mutual exclusion / barrier synchronization

Locks
• A simple example of a serializing mechanism is the use of exclusive locks.
• Server can lock any object that is about to be used by a client.
• If another client wants to access the same object, it has to wait until the object is
unlocked in the end.
Figure: Transactions T and U with exclusive locks
Transaction T: Transaction U:
balance = [Link]() balance = [Link]()
[Link](bal*1.1) [Link](bal*1.1)
[Link](bal/10) [Link](bal/10)
Operations Locks Operations Locks
openTransaction
bal = [Link]() lock B
[Link](bal*1.1) openTransaction
[Link](bal/10) Lock A bal = [Link]() waits for T ’s
lock on B
closeTransaction unlock A , B
lock B
[Link](bal*1.1)
[Link](bal/10) lock C
closeTransaction unlock B , C
Figure: Lock compatibility

For one object Lock requested

read write
Lock already set none OK OK
read OK wait
write wait wait

An object can be read and write. From the compatibility table, we know pairs of read operations
from different transactions do not conflict. So a simple exclusive lock used for both read and write
reduces concurrency more than necessary. (Many readers/Single writer)
Rules;
1. If T has already performed a read operation, then a concurrent transaction U must not write until
T commits or aborts.
2. If T already performed a write operation, then concurrent U must not read or write until T
commits or aborts.
Shared Lock and Exclusive lock
• Locks must be obtained before read/write can begin
• If a transaction want to read and write the same object, it can either
• Obtain an X-lock before reading and unlock it immediately
afterwards
• Obtain an S-lock before reading, then obtain an X-lock before
writing. And unlock it immediately afterwards.
Scalable Locks
In operating systems, scalable locks are designed to efficiently handle
synchronization in environments with many threads or processors, ensuring
performance does not degrade as the system scales.

Traditional locking mechanisms like basic spinlocks or mutexes can become

bottlenecks when contention increases, especially in multiprocessor systems.
Key Characteristics of Scalable Locks
1. Low Contention: Minimize the number of threads contending for the
same lock.
2. Reduced Overhead: Avoid excessive CPU usage due to spinning or
frequent context switches.
3. Fairness: Ensure threads are served in a fair order, avoiding starvation.
4. Scalability: Perform well as the number of processors or threads increases.
Scalable Locks - Types
1. Ticket Locks
How It Works:
Each thread receives a unique ticket when requesting a lock.
The lock is granted to the thread with the next ticket number.
Advantages:
Ensures fairness by serving threads in order.
Avoids contention hot-spots since threads spin only when their turn approaches.

2. MCS Locks (Mellor-Crummey and Scott)

How It Works:
Maintains a queue of waiting threads, with each thread spinning on its own memory location
rather than a shared one.
Threads pass the lock to the next in the queue.
Advantages:
Reduces contention on shared memory, making it scalable in NUMA (Non-Uniform Memory
Access) architectures.
Scalable Locks - Types
3. Read-Write Locks
How It Works:
Allows multiple threads to hold the lock in read mode, but only one thread in write
mode.
Advantages:
Improves concurrency for workloads with frequent reads and infrequent writes.

4. Adaptive Locks
How It Works:
Switches between spinning (busy-waiting) and blocking (context switch) based on the
lock's contention level.
Advantages:
Balances the trade-off between spinning and blocking to reduce overhead.
Lock-Free Coordination
Lock-free coordination is a technique in concurrent programming where
multiple threads or processes interact and manipulate shared data without
using locks.

Instead of relying on traditional locking mechanisms like mutexes or

semaphores, it uses atomic operations and non-blocking algorithms to ensure
safe, consistent access to shared resources.

Lock-free algorithms are essential in applications requiring extreme

parallelism, such as simulations or machine learning.

In real-time systems, locking mechanisms introduce unpredictable delays.

Lock-free coordination ensures consistent, low-latency behavior.
Characteristics of Lock-Free Coordination
Non-blocking: Threads are never forced to wait for a lock to be
released.
Progress Guarantee: At least one thread makes progress at any
time (preventing deadlock).
Minimized Overhead: No context switching due to blocking,
reducing latency and improving performance.
Scalability: Performs well under high contention, especially in
multiprocessor systems.
Lock-Free Coordination - Techniques
1. Atomic Operations
Definition: Operations performed as a single, indivisible step.
Examples:
Compare-And-Swap (CAS): Compares a value at a memory location with an expected
value and updates it if they match.

2. Lock-Free Data Structures

Specially designed data structures that use atomic operations for thread-safe operations.
Examples:
Lock-Free Queues: Threads enqueue and dequeue elements atomically.
Lock-Free Stacks: Allow concurrent push and pop operations.
Lock-Free Hash Tables: Support concurrent inserts, deletes, and lookups.