UNIT – III

Process Synchronization

Process Synchronization: It is the mechanism in an Operating System that ensures that

multiple processes (or threads) can safely access shared resources (like variables, files,
printers, or databases) without conflicts or inconsistency.
When multiple processes execute concurrently, they may access shared data at the same time.
Without synchronization, this may lead to incorrect results or data corruption.
Techniques for Process Synchronization
• Software-based solutions
• Peterson’s Algorithm
• Bakery Algorithm
• Hardware-based solutions
• Test-and-Set (TSL instruction)
• Compare-and-Swap
• OS-provided Synchronization Tools
• Semaphores (counting & binary)
• Mutex locks
• Monitors & Condition Variables

Inter-process Communication:
 It is a mechanism which allows processes to communicate each other and synchronize
their actions.
 Processes executing concurrently in the operating system may be either independent
processes or cooperating processes.
 A process is independent if it does not share data with any other processes executing in
the system.
 A process is cooperating if it can affect or be affected by the other processes executing in
the system.
 Clearly, any process that shares data with other processes is a cooperating process.
There are several reasons for providing an environment that allows process cooperation:
Information sharing. Since several applications may be interested in the same piece of
information (for instance, copying and pasting), we must provide an environment to allow
concurrent access to such information.
Computation speedup. If we want a particular task to run faster, we must break it into subtasks,
each of which will be executing in parallel with the others. Notice that such a speedup can be
achieved only if the computer has multiple processing cores.
Modularity. We may want to construct the system in a modular fashion, dividing the system
functions into separate processes or threads.
Cooperating processes require an Inter-Process Communication (IPC) mechanism that will
allow them to exchange data— that is, send data to and receive data from each other.
There are two fundamental models of Inter-Process Communication
Shared Memory: In the shared-memory model, a region of memory that is shared by the
cooperating processes is established. Processes can then exchange information by reading and
writing data to the shared region.
Message Passing: In this communication takes place by means of messages exchanged between
the cooperating processes. It is useful to exchange small amount of data, because no conflicts
need to avoided. It is easier to implement in a distributed systems than share memory.

Race Condition:
A race condition occurs when two or more processes/threads access shared data at the same time,
and the final result depends on the order of execution.
Since processes run concurrently, the order is unpredictable → leading to inconsistent or wrong
results.
👉 In simple words: Two “racers” (processes) are competing to update the same data, and
whoever runs faster changes the outcome.
Expected result: counter = 2
int counter = 0; // shared variable Possible race condition outcome: counter = 1
// Thread 1 Why?
counter = counter + 1; Thread 1 reads counter (0).
// Thread 2 Thread 2 also reads counter (0).
counter = counter + 1; Both increment to 1, then store → final value is
1, not 2.

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, tables, writing a file, that is shared with at least one
other process.
 The important feature of the system is that, when one process is executing in its critical
section, no other process is allowed to execute in its critical section
 That is, no two process are allowed to shared their critical section at the same time
 The critical-section problem is to design a protocol that the processes can use to
synchronize their activity so as to cooperatively share data.

Structure of a Process

 Each process can be divided into 4 sections:

o Entry Section → Requests permission to enter the critical section.
o Critical Section → The code that accesses shared resources.
o Exit Section → Releases the lock and allows others to enter.
o Remainder Section → Code outside the critical section
General Structure of a typical process.

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.
2. 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
3. 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.
Peterson Solution:
A classic software-based solution to the critical-section problem known as
Peterson’s solution.
• Peterson’s solution addresses the requirements of critical section problem,
(Mutual Exclusion, Progress and Bound waiting)
• Peterson’s solution is restricted to two processes that alternate execution
between their critical sections and remainder sections.
• Let Pi and Pj are the two processes.
Peterson’s solution requires the two processes to share two data items:

int turn; [Indicates Whose turn it is to enter its critical section]

boolean flag[2]; [Used to indicate if a process is ready to enter its C.S]

Process i Peterson’s solution Process j Peterson’s solution

while (true) { while (true) {

flag[i] = true; flag[j] = true;
turn = j; turn = i;
while (flag[j] && turn == j); while (flag[i] && turn == i);
critical section critical section
flag[i] = false; flag[j] = false;
remainder section remainder section
} }

Explanation:
To enter the critical section, process Pi first sets flag[i] to be true and then sets turn to the value j,
thereby asserting that if the other process wishes to enter the critical section, it can do so. If both
processes try to enter at the same time, turn will be set to both i and j at roughly the same time.
Only one of these assignments will last; the other will occur but will be overwritten immediately.
The eventual value of turn determines which of the two processes is allowed to enter its critical
section first.

Hardware Solution Problem for Process Synchronization: Test and Set Lock:

 There is a shared lock variable which can be take two values, either 0 or 1
0 - means the lock is open
1 - means the lock is closed
 Before entering into the critical section, a process inquire about the lock
 If it is locked it keep waiting till it becomes free
 If it not locked, it takes the lock and executes the critical section

The definition of test_and_set () instruction:

It is an atomic operation: It is single operation which cannot be interrupted by other operations

boolean test_and_set(boolean *target)

{
boolean rv = *target;
*target = true;
return rv;
}

do {
while (test_and_set(&lock));
/* do nothing */
/* critical section */ Process
1
lock = false;
/* remainder section */
} while (true);

Initial the lock value is set to 0, where (&lock) gives the address of the lock value. The
test_and_set() function will be invoked and the value of lock = 0 passed to the target value in the
function definition, hence the target value is also 0. Then the target value is stored to rv
(i.e rv = 0). The return function rv will return rv = 0. When the while condition is 0, then the
condition is false, the process go into the critical section, and its execute the critical section.
While the process is in its critical section, the target value is set to TRUE, hence the lock_value =
1. When the lock value is 1, on other process are allowed to enter into the critical section. Once
the process finished the critical section the lock value again set to FALSE, the process will
continue with the reminder section.
Advantages:
1. It is simple and easy
2. It is applicable to any number of processes
3. It can be used to support multiple critical section
Disadvantages:
1. Busy waiting is possible
2. Starvation is also possible
3. There may be deadlock

Swap
The compare_and_swap() instruction (CAS), just like the test_and_set() instruction, operates on
two words atomically, but uses a different mechanism that is based on swapping the content of
two words.

The CAS instruction operates on three operands and is defined in Figure. The operand value is
set to new value only if the expression (*value == expected) is true. Regardless, CAS always
returns the original value of the variable value. The important characteristic of this instruction is
that it is
executed atomically. Thus, if two CAS instructions are executed simultaneously (each on a
different core), they will be executed sequentially in some arbitrary order.
 Definition of swap:
int compare and swap(int *value, int expected, int new value)
{
int temp = *value;
if (*value == expected)
*value = new value;
return temp;
}

Mutual exclusion using CAS can be provided as follows: A global variable (lock) is declared and
is initialized to 0. The first process that invokes compare and swap() will set lock to 1. It will
then enter its critical section, because the original value of lock was equal to the expected value
of 0. Subsequent calls to compare and swap() will not succeed, because lock now is not equal to
the expected value of 0. When a process exits its critical section, it sets lock back to 0, which
allows another process to enter its critical section. The structure of process Pi is shown in Figure

while (true) {
while (compare and swap(&lock, 0, 1) != 0);
/* do nothing */
/* critical section */
lock = 0;
/* remainder section */
}

Producer–Consumer Problem in Operating System

Introduction
 The Producer–Consumer problem (also called Bounded Buffer Problem) is a classical
synchronization problem.
 It describes a situation where two types of processes (producers and consumers) share a
common buffer.
 The goal is to ensure correct synchronization so that producers and consumers don’t
interfere with each other while accessing the buffer.

The Problem Statement

 Producer → Generates (produces) data items and stores them in the buffer.
 Consumer → Uses (consumes) data items from the buffer.
 Shared Buffer → A fixed-size memory area (bounded buffer) used to hold the produced
items.
Constraints:
1. Buffer Full → Producer must wait (cannot insert more).
2. Buffer Empty → Consumer must wait (cannot remove).
3. Mutual Exclusion → Only one process can access the buffer at a time.
Why Synchronization is Needed?
 If two producers write simultaneously → Data corruption.
 If two consumers remove simultaneously → Inconsistent results.
 If a consumer tries to remove from an empty buffer → Underflow.
 If a producer tries to insert into a full buffer → Overflow.

Lets look more closely at how the bounded buffer illustrated inter-process communication using
shared memory. The following variables reside in a region of memory shared by the producer
and consumer processes.

#define BUFFER SIZE 10

typedef struct{
…….

}item;
item buffer[BUFFER SIZE];

int in = 0;
int out = 0;

 The shared buffer is implemented as a circular array with two logical pointers: in and out
 in → Points to the next empty slot where the producer will insert an item.
 out → Points to the next full slot from where the consumer will remove an item.
 Both are initialized to 0.
 if in == out → Buffer is empty.
 If (in + 1) % BUFFER_SIZE == out → Buffer is full.
 The producer process has a local variable next produces in which the new item to be
produces is stored
 The consumer process has a local variable next consumed in which the item to be consumed
is stored.

Producer process Consumer process

Item next produced; Item next consumed;
While true){ While true){
/* Produce an item in next production*/ While(in = = out);
While (((in + 1) % BUFFER_SIZE) == out); /*do nothing*/
/*do nothing*/ Next consumed = buffer[out];
buffer[in] = next producer out = (out + 1) % BUFFER_SIZE;
In = (in + 1) % BUFFER_SIZE; /* consume an item in next consumption*/
} }
Example for the Producer process:

Let’s say BUFFER_SIZE = 5.

 Initially: in = 0, out = 0 → Buffer empty.
 Producer generates first item:
o Checks condition → (1 % 5 != 0) → not full.
o Places item at buffer[0].
o in = (0+1)%5 = 1.
 Producer generates second item:
o Places at buffer[1], then in = 2.
 This continues until:
o in = 4, out = 0.
o Next position = (4+1)%5 = 0.
o Since out = 0, condition becomes true → buffer full → producer waits.

Semaphores:

 Semaphores is a technique to mange concurrent processes by using a simple integer value,

which is known as semaphore.
 A semaphore S is an integer variable that is accessed only through two standard atomic
operations: wait() and signal().
1. wait() operation was originally termed P (from the Dutch proberen, “to test”);
2. signal() was originally called V (from verhogen, “to increment”)

Definition of wait () Definition of signal ()

P (Semaphore S) { V (Semaphore S) {
While (S <= 0) ; While (S <= 0);
// busy wait // busy wait
S -- ; S -- ;
} }

Wait () operation: Each process that wishes to use a resource performs a wait() operation on
the semaphore (thereby decrementing the count)
Explanation: That means if a process (say P1) want to use the resource, it will perform the wait
operation on S and it will decrement the S. During that time no other process (say P2) is allowed
enter into the critical section. Suppose if S > 0, the process(P2) come out the while
loop[while(S<=0); ] and the S value is decremented (S --) and the process(P2) use the resource

Signal() operation: When a process releases a resource, it performs a signal() operation

(incrementing the count)
Explanation: When a process already using the resource with some value of S, once completed
its execution it will release the resources and increment the S value, so that other process can use
the resource.
[All the modifications to the integer value of the semaphore(S) in the wait() and signal() must be
executed indivisibly. That is, when one process modifies the semaphore value then no other
process can simultaneously modify the same semaphore value.]

There are two types Semaphores.

1. Binary Semaphore: The value of S has only two values either 0 or 1. These are known as
mutex locks, as they are locks that provide the mutual exclusion.
2. Counting Semaphore: Its value can range over an unrestricted domain. It is used to
control access to a resource that has multiple instances

Semaphores can also use 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. In process P1, we insert the
statements

In process P2, we insert the statements