Unit- II

Concurrent Process

Process Concept- A process is a sequential program in [Link] represents the basic unit
of execution in a computer system. Each process has its own memory space, program code, data,
and system resources. When a program is executed, the operating system creates a process for it
to run in.
Processes are managed by the operating system's kernel, which schedules them for execution
on the CPU, allocates resources to them, and provides mechanisms for communication and
synchronization between processes.

processes are categorized as one of the following two types:

• Independent Process: The execution of one process does not affect the execution of other
processes.
• Cooperative Process: A process that can affect or be affected by other processes executing in
the system. Process synchronization problem arises in the case of Cooperative process also
because resources are shared in Cooperative processes

Principle of concurrency-

Concurrency refers to the ability of a system to handle multiple tasks simultaneously. The
principles of concurrency aim to ensure that multiple tasks can make progress efficiently and
correctly, especially in systems where there are multiple processes or threads executing
concurrently. Concurrency can be implemented and is commonly used even on single processing
units. In a single processing unit system, concurrency can still be achieved through techniques
such as time-sharing or interleaved execution, where the CPU switches between executing
different tasks rapidly, giving the illusion of simultaneous execution.

Concurrency Control: This principle involves managing access to shared resources in a

way that prevents conflicts and ensures consistency. Techniques such as locking, transactions,
and synchronization primitives (e.g., mutexes, semaphores) are used to coordinate access to
shared data and resources among concurrent processes or threads.

Producer- Consumer Problem

Producer processes produce data items that consumer processes consume later. A buffer is used
between the producer and consumer processes. The buffer size may be fixed or variable. The
producer portion of the application generates data and stores it in the buffer, while the consumer
reads data from the buffer. The producer cannot deposit its data if the buffer is full, similarly, a
consumer cannot retrieve any data if the buffer is empty. In the producer-consumer problem, the
challenge is to ensure that producers and consumers can work concurrently without interfering
with each other, avoiding issues such as data corruption, race conditions, and deadlock.
Ex-
//producer
int count = 0;
void producer(void)

{
int itemP;
while(1)
{
Produce_item(item P)
while(count == n);
buffer[in=] item P;
in=(in + 1)mod n
count = count + 1;
}
}
//consumer
void consumer(void)
{
int itemC;
while (1)
{
while (count == 0);
itemC = buffer[out];
out = (out + 1) % n;
count = count - 1;
Consume_item(itemC);
}
}

Key aspects of the producer-consumer problem include:

Shared Buffer: There is a shared, finite-size buffer or queue where items produced by producers
are stored for consumption by consumers. The buffer allows producers to enqueue items and
consumers to dequeue items.

Producer Operations: Producers produce items and add them to the shared buffer. If the buffer
is full, producers may need to wait until space becomes available.

Consumer Operations: Consumers remove items from the shared buffer and process them. If
the buffer is empty, consumers may need to wait until items become available.

Synchronization: Producers and consumers need to synchronize their access to the shared buffer
to avoid issues such as race conditions (where the outcome depends on the timing of
uncontrollable events) and buffer overflow/underflow.

Critical Section Problem

A critical section is a code segment that can be accessed by only one process at a time. It refers
to the situation where multiple processes or threads share a common resource, such as memory,
files, or hardware devices, and they need to access this resource in a way that avoids conflicts
and maintains consistency.
The critical section problem can be summarized as follows:

1.​ Mutual Exclusion: Only one process can execute in its critical section at a [Link] any
other process requires the critical section, they must wait until it is free.
2.​ Progress: If no process is executing in its critical section,then it should not stop any other
process from accessing it. In other words,any process can enter a critical section if it's
free.
3.​ Bounded Waiting: We should be able to predict the waiting time for every process to get
into the critical section. The process must not be endlessly waiting for getting into the
critical section.

Difference between process and program

Program Process
A program is a set of instructions written in a A process is an instance of a program that is
programming language that performs a being executed by the operating system.
specific task when executed.

Programs serve as a set of instructions to be Processes are responsible for executing the
executed by a computer system. instructions provided by the program,
managing system resources, and interacting
with other processes

It's a static entity Processes are dynamic entities.

Programs are stored on disk or in memory Processes are created and managed by the
operating system during runtime.

Difference between busy wait and blocking wait

Busy wait Blocking wait

Busy wait can lead to high CPU utilization Blocking wait is more efficient and allows the
and inefficiency CPU to be utilized by other processes.

It consumes CPU cycles continuously, even It doesn't consume CPU cycles while waiting
when there is no work to be done, hence the for the condition to become true.
term "busy" wait.

Typically used in situations where the wait Commonly used in situations where the wait
time is expected to be very short, and time is expected to be longer, such as waiting
relinquishing the CPU and context switching for I/O operations to complete.
overhead is not desirable.

Race Condition

At the time when more than one process is either executing the same code or
accessing the same memory or any shared variable; In that condition, there is a
possibility that the output or the value of the shared variable is wrong so for that
purpose all the processes are doing the race to say that my output is correct. This
condition is commonly known as a race condition. As several processes access and
process the manipulations on the same data in a concurrent manner and due to which
the outcome depends on the particular order in which the access of data takes place.

Mainly this condition is a situation that may occur inside the critical section. Race
condition in the critical section happens when the result of multiple thread execution
differs according to the order in which the threads execute. But this condition is
critical sections can be avoided if the critical section is treated as an atomic
instruction. Proper thread synchronization using locks or atomic variables can also
prevent race conditions

Mutual Exclusion- Mutual exclusion ensures that only one process or thread can access a
shared resource at a time. This principle prevents concurrent access that could lead to data
corruption or inconsistent behavior. Mutexes and locks are commonly used to implement mutual
[Link] exclusion is a fundamental concept in concurrent programming and operating
systems, ensuring that only one process or thread accesses a shared resource at any given time.
This prevents conflicts and data corruption that can occur when multiple processes attempt to
access the same resource simultaneously. Mutual exclusion is typically achieved using
synchronization mechanisms such as locks, semaphores, or mutexes.

The conditions for achieving mutual exclusion are as follows:

1.​ Mutual exclusion mechanisms should ensure that processes do not remain indefinitely
blocked from accessing the shared resource. If a process holding the resource is
interrupted or delayed, other processes should not be prevented from accessing the
resource indefinitely.
2.​ Deadlock occurs when two or more processes are waiting indefinitely for each other to
release resources, resulting in a deadlock situation where no progress can be made. To
achieve mutual exclusion effectively, mechanisms should be designed to prevent
deadlock.

Dekker’s Algorithm
It is the first known algorithm that solves the mutual exclusion problem in concurrent
programming. It is used in process queuing and allows two different threads to share the same
single-user resources without conflict by using shared memory for communication.
Dekker's algorithm will allow only a single process resource if two processes are trying to use it
at the same time. It succeeds in preventing the conflict by enforcing mutual exclusion, meaning
that one process may use the resource at a time and will wait for another process. is using it. This
is achieved with the use of two " flags" and a "token".

Working
 1.​ Turn-taking: Each process takes turns going into the critical section. They do this by
using a flag to indicate when they want to go in.
2.​ Respectful Waiting: If one process wants to go in but sees that the other has already set
its flag, it waits politely until the other process is done.
3.​ Alternating Flags: The tricky part is making sure both processes don't try to go in at the
same time. They use a clever trick with flags to handle this. Each process sets its own
flag when it wants to go in, but before doing so, it checks if the other process wants to go
in too. If it does, the process that went in first waits until the other is done before trying
again.
4.​ Clearing the Way: After finishing their work in the critical section, a process clears its
flag, indicating that it's done and the other process can go in if it wants.

Peterson’s Solution - Peterson's solution is a classic algorithm used for achieving mutual
exclusion in concurrent programming. It's named after Gary L. Peterson, who introduced it in
1981. The algorithm is primarily designed for two processes (or threads) sharing a critical
section, ensuring that they do not execute that section simultaneously, thus avoiding conflicts and
maintaining data integrity.
Peterson's solution typically works:
1.​ Shared Variables: There are typically two shared variables:
●​ Flags: Each process has a flag associated with it. The flag indicates whether the
process is interested in entering the critical section.
●​ Turn: This variable indicates whose turn it is to enter the critical section.
2.​ Initialization: Initially, both flags are set to indicate that neither process is interested in
entering the critical section. The initial value of the turn variable can be arbitrary or
predefined.
3.​ Entering the Critical Section:
●​ A process indicates its interest in entering the critical section by setting its flag to
true.
●​ The process then sets the turn variable to indicate that it's the other process's turn.
●​ The process checks if the other process is also interested in entering the critical
section and if it's their turn. If it is, the process yields, waiting for its turn.
4.​ Leaving the Critical Section:
●​ After completing its work in the critical section, the process resets its flag,
indicating that it's no longer interested in entering the critical section.
●​ This action allows the other process to enter the critical section.
5.​ Turn Switching:
●​ If both processes are interested in entering the critical section, but it's not their
turn, they yield control to each other, ensuring that one of them eventually gets
the chance to enter.

Semaphores -It's a variable used to solve the critical section problem and to solve the critical
section problem and to achieve process synchronization in the multiprocessing environment.
The two most common kinds of semaphores are counting semaphores and binary
[Link] semaphores can take non-negative integer values and binary semaphores
can take 0 or 1.
Semaphores are synchronization primitives used in concurrent programming to control access to
shared resources by multiple processes or threads. They are integer variables that are accessed
via two standard atomic operations: wait (P) and signal (V).
Advantages of Semaphores:

1.​ Resource Synchronization: Semaphores allow for the orderly access of shared resources,
preventing race conditions and ensuring data integrity.
2.​ Flexibility: They can be used to solve a variety of synchronization problems, such as
producer-consumer, readers-writers, and dining philosophers.
3.​ Efficiency: Semaphores are typically efficient and lightweight, as they rely on
hardware-supported atomic operations.
4.​ Scalability: They can scale to handle large numbers of concurrent processes or threads
without significantly impacting performance.

Disadvantages of Semaphores:

1.​ Complexity: Improper use of semaphores can lead to subtle bugs, such as deadlocks and
livelocks, which can be challenging to debug.
2.​ Overhead: In certain situations, the use of semaphores can introduce overhead due to
context switching and synchronization costs.
3.​ Potential for Priority Inversion: In preemptive scheduling environments, semaphores can
lead to priority inversion, where a low-priority task holds a semaphore required by a
high-priority task, delaying its execution.
4.​ Lack of Enforcement: Semaphores provide mechanisms for synchronization but do not
enforce proper usage. It's up to the programmer to ensure correct implementation and
usage.

Reader Writer Problem

The reader writer problem relates to an object such as a file that is shared between multiple
processes. Some of these processes are readers, they only want to read data from objects and
some of the processes are writers, they want to write into the object.
The reader-writer problem is used to manage synchronization so that there are no problems with
the object data. If two readers access the object at the same time there is no problem. However if
the writers or a reader and writer may access the can access at same time, may be a problem.

To solve this problem, a writer should get exclusive access to an object, when a writer is
accessing the object, no reader or writer may access it. However multiple readers can access the
object at the same time.

1.​ Readers: Multiple readers can access the shared resource simultaneously without any
problem. They don't modify the resource, so allowing concurrent access by multiple
readers is generally safe.
2.​ Writers: Writers, on the other hand, must have exclusive access to the shared resource.
When a writer wants to modify the resource, no other readers or writers should be
allowed to access it.

Dining Philosophers problem-

The Dining Philosophers problem is another classic synchronization [Link] problem is

framed around a group of philosophers sitting around a dining table with a bowl of noodles in
front of each of them. There are also forks placed between each pair of adjacent philosophers.
Philosophers spend their time thinking and eating noodles. However, to eat, they need two forks
- the one to their left and the one to their right.
Here are the main constraints of the problem:

1.​ Each philosopher must alternately think and eat.

2.​ A philosopher can only eat if they have both forks.
3.​ Forks can be shared between adjacent philosophers.
4.​ The system should avoid deadlock (where all philosophers are holding one fork and
waiting for the other).
5.​ The system should avoid starvation (where a philosopher may never get the chance to
eat).

To Solve the Dining Philosophers problem involves designing a strategy for the philosophers to
pick up and release forks in a way that prevents deadlock and starvation while allowing them all
to eat as much as possible.

Some common solutions to the Dining Philosophers problem include:

 1.​ Chopstick as a shared resource: Each fork is considered a shared resource, and
philosophers must request and release them in a way that prevents deadlock. Techniques
like using mutex locks or semaphores to coordinate access to the forks can be employed.
2.​ Resource hierarchy: Assign a unique index to each fork and allow philosophers to pick up
forks only in a specific order (e.g., always pick up the lower-indexed fork first). This
prevents circular wait conditions and guarantees progress.
3.​ Asymmetric solution: For example, having one philosopher pick up the left fork first and
another philosopher pick up the right fork first can break symmetry and prevent deadlock.
4.​ Timeouts and resource preemption: Allow philosophers to hold onto forks for a limited
time. If a philosopher cannot obtain both forks within a certain time frame, they release
any forks they currently hold and retry later.
5.​ Philosopher prioritization: Allow certain philosophers to have priority access to forks or
enforce a rule where a philosopher must wait until both neighboring philosophers have
finished eating before attempting to eat themselves.

Sleeping Barber Problem -

This problem is analogy based upon the hypothetical barber shop with one barber and a waiting
room with a limited number of chairs. The barber alternates between cutting hair and taking
breaks. When a customer arrives:

1.​ If there are empty chairs in the waiting room, the customer sits and waits for the barber.
2.​ If all chairs are occupied, the customer leaves the shop.

The problem arises when multiple customers arrive simultaneously and try to access the barber
and the waiting room concurrently. To prevent conflicts and ensure proper behavior,
synchronization mechanisms must be implemented.

Key elements of the problem:

1.​ Barber: Can cut hair or take breaks.

 2.​ Waiting Room: Has a limited number of chairs where customers can wait.
3.​ Customers: Arrive, wait if there are available chairs, or leave if the waiting room is full.

To solve the Sleeping Barber Problem, synchronization techniques like semaphores, mutexes, or
monitors can be employed to coordinate access to the barber and waiting room, ensuring mutual
exclusion and preventing race conditions.

A common solution involves using semaphores to control access to shared resources:

●​ A semaphore for the barber chair to ensure exclusive access by either the barber or a
customer.
●​ Another semaphore for the waiting room to limit the number of customers allowed inside.

The logic typically involves:

1.​ Customer arrives:

●​ If the waiting room is not full, enter and wait.
●​ If the waiting room is full, leave.
2.​ Barber:
●​ If a customer is waiting, cut hair.
●​ If no customer is waiting, sleep.
3.​ When the barber finishes cutting hair, the customer leaves the chair, and another customer
may take their place if one is waiting.

Hardware Based Solution to Synchronization: There is no guarantee that the Software-based

solution like Peterson’s will work on modern architecture. Hence, certain hardware-based
solution to synchronization are proposed. Two such solutions are:
1. TestAndSet() instruction
2. Swap() instruction
3. Unlock and Lock
Both these instructions are atomic instructions which means that when a process is executing any
of these instructions it can not be preempted until the instruction is complete.

1. TestAndSet() Instructions
TestAndSet() instruction uses a boolean variable lock. The initial value of the lock is false. The
variable lock ensures mutual exclusion. If the value of lock is false, this means that no process is
in its critical section. Hence, the value true means that some process is running in its critical
section.
Lock and unlock:
Unlock and Lock In addition to Test and Set, this algorithm uses waiting[i] to check if there are
any processes in the wait. The processes are set in the ready queue with respect to the critical
section.
Inter-Process Communication-
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.
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 executed in parallel with the others. Notice that such a speedup
can be achieved only if the computer has multiple processing cores.