UNIT 3

Concurrency: Process Synchronization, The Critical-Section Problem, Classic

Problems of Synchronization, Monitors, Synchronization examples.

Deadlock: Principles of deadlock – System Model, Deadlock Characterization,

Deadlock Prevention, Detection and Avoidance, Recovery form Deadlock.

1 What is Process Synchronization

[Link]

1. Process Synchronization Overview:

Process synchronization is essential in operating systems to handle concurrent

execution of processes, especially when they share resources or memory.

2. Types of Processes:

- Independent Process: Executes without affecting others; no shared memory;

resources are exclusively bound to the process until completion.

- Cooperative Process: Executes with shared memory; execution of one

process can affect others; requires synchronization to maintain data consistency.

3. Need for Synchronization:

In cooperative processes, multiple processes share common memory which

can lead to inconsistent or incorrect data if accessed simultaneously without
control.

4. Race Condition Explanation:

Occurs when multiple processes concurrently modify shared data leading to

contradictory or inconsistent results. This is a key issue in cooperative process
management.

5. Solution via Process Synchronization:

 Employ locking mechanisms or synchronization techniques to ensure that
only one process can access the shared memory at a time, preventing data
inconsistency.

# Key Conclusions

1. Process synchronization is mandatory for cooperative processes to avoid data

inconsistency due to shared memory access.

2. Independent processes do not require synchronization because they do not

share resources or memory during execution.

3. Race conditions represent a critical problem in concurrent processing where

shared variables are updated without control, leading to unreliable results.

4. Synchronization techniques ensure consistent data state by serializing access

to shared resources, thereby preventing race conditions.

5. Understanding synchronization concepts is foundational before addressing

specific synchronization problems or examples in operating systems.

2 What is Race Condition?

[Link]

Race Condition

A race condition is a fault in a software system where the output depends on the
sequence of events. If these events don't happen in the expected order, an
incorrect outcome can occur. This problem arises in concurrent programming
when multiple processes or threads access and modify shared data at the same
time.

Example of a Race Condition

Let's imagine a variable, X, that is initially set to 10. We have two processes,
Process 1 and Process 2, that both want to increment X by 10.

 Process 1 reads X, which is 10.

  Before Process 1 can update X, Process 2 also reads X, which is still 10.

 Process 1 then completes its operation, updating X to 20 (10 + 10).

 Process 2 now completes its operation, also updating X to 20 (10 + 10).

The expected final value should be 30 (10 + 10 + 10), but because of the race
condition, the final value is 20.

Solution: Locking 🔐

A common solution to prevent race conditions is locking. Locking ensures that

only one process or thread can access the shared data at a time. This is done by
designating a critical section of code.

 When a process enters the critical section, it acquires a lock on the shared
data.

 This lock prevents any other process from accessing or modifying the
data.

 Once the process finishes its work in the critical section, it releases the
lock.

 The next process can then acquire the lock and perform its own
operations.

Example with Locking

Using the previous example, here's how locking would prevent the race
condition:

 Process 1 acquires a lock on X. It reads X (10) and updates it to 20.

 It then releases the lock on X.

 Process 2 can now acquire the lock on X. It reads X (now 20) and updates
it to 30.

 It then releases the lock on X.

With locking, the final value of X is correctly updated to 30.

3 What is critical section?

[Link]

The critical section problem is a fundamental issue in operating systems

related to process synchronization. It is a protocol designed to ensure that
multiple cooperating processes—those that share data—do not access and
modify that shared data concurrently, which can lead to data inconsistency.

Critical Section

A critical section is a segment of code within a process where it manipulates

shared resources, such as changing common variables, updating a table, or
writing to a file. The core problem is to ensure that only one process at a time
is executing its critical section.

Structure of a Process

A process's code is typically structured into four parts:

 Entry Section: The code that requests permission for the process to enter
its critical section.

 Critical Section: The code that accesses and modifies shared data.

 Exit Section: The code that follows the critical section, often releasing
locks or permissions.

 Remainder Section: The rest of the code that does not involve shared
resources.

Requirements for a Solution

A solution to the critical section problem must satisfy three essential
requirements to be effective and fair.

1. Mutual Exclusion 🔒

This is the most crucial requirement. If one process (say, Pi) is executing in its
critical section, no other process can be executing in its own critical section at
the same time. This prevents data corruption.

2. Progress ➡️

If no process is in its critical section, and some processes want to enter, the
selection of which process will enter next cannot be indefinitely postponed.
Only processes that are not in their remainder sections can participate in this
decision. This ensures that the critical section doesn't remain empty when
processes are waiting to enter.

3. Bounded Waiting

There must be a limit on the number of times other processes are allowed to
enter their critical sections after a process has made a request to enter and before
that request is granted. This prevents starvation, where a process is repeatedly
denied access to the critical section while others are granted access.

4 Explain Peterson solution for critical section problem?

[Link]

Peterson's solution is a classic, software-based algorithm for solving the critical

section problem for two processes. Although it might not work correctly on
modern computer architectures due to how they are designed, it's studied
because it offers a great conceptual example of how to meet the three main
requirements for a critical section solution: mutual exclusion, progress, and
bounded waiting.

Key Variables and Logic

Peterson's solution works by having two processes, which we'll call Pi and Pj,
share two data items:

 turn: An integer variable that indicates whose turn it is to enter the

critical section. If turn is i, it's Pi's turn. If turn is j, it's Pj's turn.

 flag: A boolean array, flag[i] and flag[j], that indicates if a process is

ready to enter its critical section. If flag[i] is true, it means Pi wants to
enter.

The logic is based on a "humble" approach. When a process wants to enter its
critical section, it first sets its own flag to true and then "humbly" gives the turn
to the other process by setting turn to the other process's ID.

For example, if process Pi wants to enter, it does the following:

1. Sets flag[i] = true

2. Sets turn = j (giving the turn to Pj)

3. Enters a while loop that checks two conditions: while (flag[j] && turn ==
j)

o This loop will only run if Pj also wants to enter (flag[j] is true) and
Pi has given the turn to Pj (turn == j).

o If both conditions are true, Pi will wait in this loop, effectively

letting Pj go first.

4. If the loop condition becomes false, Pi can enter its critical section.

5. After leaving the critical section, Pi sets flag[i] = false to indicate it is no

longer interested in entering.

How Peterson's Solution Meets the Requirements

Peterson's solution successfully fulfills the three key requirements for a critical
section solution:

 Mutual Exclusion: This is ensured by the while loop. If both processes

try to enter at the same time, the turn variable will be set by both, but the
last one to write will win. The other process will be forced to wait in its
 while loop. For example, if Pi sets turn=j and then Pj sets turn=i, the final
value of turn is i. This means Pj will wait, and Pi can enter its critical
section, ensuring that only one process is inside at a time.

 Progress: When no process is in its critical section, a process that wishes

to enter will not be indefinitely delayed. If a process Pi wants to enter, it
sets flag[i] = true. If the other process Pj is not interested, its flag[j] will
be false, and Pi will not be stuck in the while loop and can enter
immediately.

 Bounded Waiting: There is a strict limit on how long a process has to

wait. A process only has to wait for one round of execution by the other
process. Once the other process exits its critical section, it sets its flag to
false, which allows the waiting process to proceed. This prevents
starvation.

5 Explain Hardware solution for critical section problem in process

synchronization?

[Link]

The Test and Set Lock, a hardware-based solution for process

synchronization. It uses a shared lock variable to ensure that only one
process can enter a critical section at a time. The Test and Set operation
is a single, atomic instruction, meaning it cannot be interrupted.

How It Works ⚙️

The core of the Test and Set lock is a shared variable, lock, which can
have two values:

 0: Unlocked (the critical section is available).

 1: Locked (the critical section is in use).

The process for a program trying to enter its critical section is as follows:

1. Test: A process checks the value of the lock variable.

2. Set: If the lock is 0, the process immediately sets the lock to 1 and enters
its critical section.

3. Wait: If the lock is already 1, the process must wait in a loop,

continuously "testing" the lock until it becomes 0.

The TestAndSet() instruction is designed as an atomic operation. This

means that the act of both testing the lock and setting its value to 1
happens in one indivisible step. No other process can interrupt this
operation. This is crucial for preventing a race condition between two
processes trying to acquire the lock at the same time.

Implementation 💻

The Test and Set instruction is a function, TestAndSet(Boolean *target),

that returns a boolean value.

 It takes a pointer to the lock variable as an argument.

 It creates a temporary boolean variable, rv, and stores the current value of
the target (the lock) in it.

 It then immediately sets the target to true (or 1).

 Finally, it returns the original value of rv.

A process uses this function in a loop to enter its critical section. When a
process first runs, the lock is 0.

1. The TestAndSet(lock) function is called.

2. The rv variable gets the value of the lock (0).

3. The lock is immediately set to 1.

4. The function returns the original value of rv (0).

5. The process sees 0 as the return value, the loop condition becomes false,
and it can enter the critical section.

If another process tries to enter while the first process is inside the critical
section, it calls TestAndSet(lock):
 1. The lock is currently 1.

2. The rv variable gets the value of the lock (1).

3. The lock is immediately set to 1 (no change, but the operation still
happens).

4. The function returns the original value of rv (1).

5. The process sees 1 as the return value, the loop condition stays true, and
the process is forced to wait in the loop.

Once the first process finishes, it sets the lock back to 0 and the waiting
process can then proceed.

Advantages and Disadvantages ✔️❌

 Mutual Exclusion (Satisfied): The atomic nature of the Test and Set
instruction guarantees that only one process can successfully set the lock
and enter the critical section at a time.

 Bounded Waiting (Not Satisfied): A major drawback is the potential for

starvation. If multiple processes are waiting for the lock, and the
scheduler keeps favoring a specific process, it's possible that an
"unlucky" process never gets a chance to acquire the lock. This is because
there's no defined order of waiting, and the lock is given to the first
process that successfully executes TestAndSet() after the lock is released

6 What is semaphore?

[Link]

Introduction to Semaphores 🚦

Semaphores, proposed by computer scientist Edsger Dijkstra, are a software-

based solution to the synchronization problem. They are a valuable tool for
application programmers because they abstract away the complexities of
hardware-level synchronization. A semaphore is simply a non-negative integer
variable shared between processes. It is used to control access to shared
resources and solve the critical section problem.

The wait() and signal() Operations

A semaphore, which we'll call S, can only be accessed through two

fundamental, atomic operations:

 wait() (historically denoted as P for "proberen," Dutch for "to test"): This
operation decrements the semaphore's value. 4 If the value becomes
negative, the process is blocked and must wait. 5 It is used to acquire a
resource or enter a critical section.

 signal() (historically denoted as V for "verhogen," Dutch for "to

increment"): This operation increments the semaphore's value. 6 If there
are processes waiting on the semaphore, one of them will be woken up. It
is used to release a resource or exit a critical section.

The key to these operations is their atomicity—they cannot be interrupted.

When a process modifies a semaphore's value, no other process can do so
[Link] prevents race conditions on the semaphore itself.

Types of Semaphores

There are two main types of semaphores, each with a different use case:

1. Binary Semaphore 🔒

A binary semaphore can only have a value of 0 or 1. It is often referred to as a

mutex (mutual exclusion) lock because its primary use is to enforce mutual
exclusion.9

 Initial value: Typically set to 1.

 Logic:

o wait(): If S is 1, a process can enter its critical section, and S is

decremented to 0.10 If S is already 0, the process must wait.
 o signal(): When a process leaves its critical section, S is
incremented back to 1, signaling that the critical section is now
free.11

 Example: Imagine a single-stall restroom. The semaphore is the

"occupied" sign. When it's free, S is 1. When a person goes in, they wait()
(check the sign, see it's free, go in) and the sign flips to "occupied" (S
becomes 0). Anyone else who comes by must wait() until the first person
comes out and signal()s (flips the sign back to "vacant," S becomes 1).

2. Counting Semaphore ➕

A counting semaphore can have an unrestricted integer value. It is used to

control access to a resource that has multiple identical instances.

 Initial value: Set to the number of available resource instances.

 Logic:

o wait(): A process decrements the semaphore to acquire an instance

of the resource. If the semaphore's value becomes 0 (or negative),
all instances are in use, and any subsequent process must wait.

o signal(): A process increments the semaphore when it releases an

instance of the resource, making it available for another process.14

7 Explain produces consumer problem with example?

[Link]

classic process synchronization problem in operating systems called the

Producer-Consumer Problem, and how it can be solved using semaphores.

The Producer-Consumer Problem

The Producer-Consumer problem involves two main processes:

 The Producer: This process generates data items and places them into a
shared buffer.
  The Consumer: This process removes data items from the buffer and uses
them.

The problem arises from the need for synchronization between these two
processes. If the producer is faster than the consumer, it may try to add an item
to a buffer that is already full. Conversely, if the consumer is faster than the
producer, it may try to remove an item from a buffer that is empty.

To prevent these issues, the producer must stop producing when the buffer is
full, and the consumer must stop consuming when the buffer is empty.

Solving the Problem with Semaphores

To solve the Producer-Consumer problem, three semaphores are used:

1. mutex (Binary Semaphore): This is a binary semaphore (value 0 or 1)

used to ensure mutual exclusion. It acts as a lock on the shared buffer.
Only one process (either the producer or the consumer) can access the
buffer at any given time.

2. empty (Counting Semaphore): This is a counting semaphore that tracks

the number of empty slots in the buffer. Its initial value is equal to the
size of the buffer. The producer uses this semaphore to ensure it does not
insert items into a full buffer.

3. full (Counting Semaphore): This is a counting semaphore that tracks the

number of full slots in the buffer. Its initial value is 0. The consumer uses
this semaphore to ensure it does not try to remove items from an empty
buffer.

The Producer and Consumer Routines

Here's a breakdown of the logic for each process using these semaphores:

Producer's Routine

The producer performs the following steps to add an item to the buffer:
 1. wait(empty): The producer waits on the empty semaphore. This
decrements the empty count. If the buffer is full (empty is 0), the
producer will be blocked until a consumer removes an item.

2. wait(mutex): The producer waits on the mutex semaphore. This acquires

the lock, ensuring no other process can access the buffer.

3. Insert item: The producer adds the new item to the buffer.

4. signal(mutex): The producer signals the mutex semaphore, releasing the

lock on the buffer.

5. signal(full): The producer signals the full semaphore, incrementing the

count of full slots.

Consumer's Routine

The consumer performs the following steps to remove an item from the buffer:

1. wait(full): The consumer waits on the full semaphore. This decrements

the full count. If the buffer is empty (full is 0), the consumer will be
blocked until a producer adds an item.

2. wait(mutex): The consumer waits on the mutex semaphore to acquire the

lock on the buffer.

3. Remove item: The consumer removes an item from the buffer.

4. signal(mutex): The consumer signals the mutex semaphore, releasing the

lock.

5. signal(empty): The consumer signals the empty semaphore, incrementing

the count of empty slots.

Using these semaphores and their atomic wait() and signal() operations, the
Producer-Consumer problem is effectively solved, preventing the data
inconsistency and starvation issues that would otherwise occur.

8 Describe Readers-Writers problem? write algorithm using

semaphores?
[Link]

The readers-writers problem is a classic synchronization problem in operating

systems that involves coordinating access to a shared resource, like a database,
among multiple processes. The goal is to allow multiple readers to access the
resource concurrently but to ensure exclusive access for writers.

The Problem

There are two types of processes:

 Readers: Processes that only read data from the shared resource. They
don't modify the data.

 Writers: Processes that both read and write (update) the data.

The core issue is that while multiple readers can access the data at the same
time without any problems, chaos can ensue if a writer tries to access the data
concurrently with either a reader or another writer.

 Writer-Reader Conflict: If a writer is updating the data while a reader is

trying to read it, the reader may get inconsistent or corrupt information.

 Writer-Writer Conflict: If two writers try to modify the same data at the
same time, the changes may be lost or mixed up, leading to data
corruption.

To prevent these issues, writers must have exclusive access to the shared
resource.

Solution Using Semaphores

The readers-writers problem can be solved using two semaphores and one
integer variable.

 mutex (Semaphore): A binary semaphore initialized to 1. It's used to

provide mutual exclusion for a shared variable, readcount.

 wrt (Semaphore): A binary semaphore initialized to 1. This semaphore

is shared by both readers and writers. It ensures that only one writer can
 access the database at a time and that no reader can access the database
while a writer is writing.

 readcount (Integer Variable): An integer variable initialized to 0. It

keeps track of the number of active reader processes.

Writer Process Code

The writer's code is simpler because it needs exclusive access.

1. wait(wrt): The writer waits on the wrt semaphore. If the semaphore is

available (its value is 1), it acquires the lock by decrementing its value to
0. If it's not available, the writer is blocked.

2. Performs Writing: Once the lock is acquired, the writer performs its
write operation on the database.

3. signal(wrt): After writing, the writer signals the wrt semaphore, releasing
the lock for others to use.

Reader Process Code

The reader's code is more complex because it allows for concurrent access with
other readers but not with writers.

1. wait(mutex): The reader waits on the mutex semaphore to protect the

readcount variable.

2. readcount++: The reader increments readcount to indicate that a new

reader is active.

3. if (readcount == 1) wait(wrt): If this is the first reader, it waits on the

wrt semaphore. This prevents any writer from entering the database while
at least one reader is present.

4. signal(mutex): The reader releases the mutex semaphore, allowing other

readers to modify readcount and enter.

5. Performs Reading: The reader performs its read operation on the

database.

6. wait(mutex): The reader again waits on the mutex to protect readcount

before exiting.
 7. readcount--: The reader decrements readcount to indicate that it is no
longer active.

8. if (readcount == 0) signal(wrt): If this is the last reader to leave, it

signals the wrt semaphore. This releases the lock, allowing a waiting
writer to proceed.

9. signal(mutex): The reader releases the mutex semaphore.

This solution gives priority to readers. Once a single reader is active, any new
readers can enter without waiting for a writer to finish, but a waiting writer will
not get the chance to write until the last reader has left.

9 Explanation of Dinning philosopher Problem in process synchronization?

[Link]

The Dining Philosophers Problem is a classic synchronization problem in

operating systems that illustrates the challenges of resource allocation and
deadlock. It's a conceptual problem used to model how competing processes can
share a limited number of resources in a deadlock-free and starvation-free
manner.

The Problem

Imagine a round table with five philosophers and five forks, one placed between
each pair of philosophers.

The philosophers can be in two states:

 Thinking: They do not need any resources.

 Eating: When a philosopher gets hungry, they must pick up both the fork
to their left and the fork to their right. They can only pick up one fork at a
time. After eating, they must put both forks down.

The core of the problem lies in the limited number of forks. A philosopher can't
eat without both forks, and each fork is a shared resource used by two different
philosophers. If a philosopher picks up one fork and the other is not available,
they will wait indefinitely, holding onto the fork they have.
This scenario, where a group of processes is permanently blocked because each
process is holding a resource and waiting for another resource acquired by a
different process in the same group, is a classic example of deadlock.

A Simple Solution with Semaphores (and its Flaw)

One straightforward approach to solving this problem is to represent each fork

as a binary semaphore. A binary semaphore is like a lock that can be either 0
(locked) or 1 (unlocked), ensuring that only one philosopher can hold a
particular fork at any given time.

Let's use an array of five semaphores called chopstick[5], one for each fork, all
initialized to 1.

The code for each philosopher (P_i) would be:

1. wait(chopstick[i]): The philosopher tries to pick up the left fork.

2. wait(chopstick[(i+1)%5]): The philosopher tries to pick up the right

fork.

3. Eat: If both forks are successfully acquired, the philosopher eats.

4. signal(chopstick[i]): The philosopher puts down the left fork.

5. signal(chopstick[(i+1)%5]): The philosopher puts down the right fork.

6. Think: The philosopher returns to the thinking state.

This solution successfully prevents two adjacent philosophers from eating at the
same time. However, it is vulnerable to deadlock. If all five philosophers
become hungry at the same time, they will all pick up their left fork. The
chopstick semaphores will all be set to 0. Then, each philosopher will try to
acquire their right fork, but all right forks are now the left forks of their
neighbors and are locked. This creates a circular dependency where everyone is
waiting for the person next to them, leading to a permanent deadlock.

Remedies to Avoid Deadlock

To prevent this deadlock situation, a few remedies can be applied:

 1. Limit the Number of Philosophers: Allow only four philosophers at the
table at a time. This ensures that at least one fork is always available,
preventing the circular waiting condition.

2. Atomic Pick-up: Allow a philosopher to pick up their chopsticks only if

both are available. The check and the pick-up operation must be a single,
atomic transaction (a critical section) to prevent a deadlock.

3. Asymmetric Solution: Implement a rule where odd-numbered

philosophers pick up their left fork first, while even-numbered
philosophers pick up their right fork first. This breaks the symmetry of
the problem and prevents the simultaneous, circular acquisition of
resources.

10 What is Monitor? Explain about different components of Monitors.

[Link]

Monitors are a high-level synchronization construct that provide a more

convenient and less error-prone way to manage concurrent processes
compared to semaphores. Unlike semaphores, where synchronization
logic is embedded within a program's code, a monitor encapsulates the
shared data and the procedures that operate on that data into a single,
cohesive structure.

Key Concepts

 High-Level Abstraction: Monitors are a data type that provides a clear

and effective mechanism for process synchronization. They are a "black
box" for synchronization, meaning the programmer doesn't need to worry
about the underlying synchronization details.

 Encapsulation: A monitor combines shared variables and the procedures

that operate on them into a single, protected unit. The shared variables
within a monitor can only be accessed by the procedures defined within
that same monitor.

 Mutual Exclusion: A core feature of a monitor is that it ensures that only

one process at a time can be "active" within the monitor's procedures.
 This guarantees mutual exclusion and prevents race conditions on the
shared data.

Monitor Structure and Syntax

A monitor can be thought of as a special kind of class or module. Its basic

syntax includes:

 Shared Variables: Declarations of variables that will be shared among

different processes.

 Procedures/Functions: The bodies of the procedures that can operate on

the shared variables.

 Initialization Code: Code to initialize the shared variables.

The structure protects the shared data, as procedures can only access the
variables declared within the monitor's local scope.

Condition Variables

To handle more complex synchronization needs, monitors also use a

special type of variable called a condition variable. These are used for
process coordination and signaling.

 wait() operation: A process that needs to wait for a specific condition

(e.g., a buffer to be empty) can execute [Link](), where x is a condition
variable. This suspends the process and places it in a queue for that
condition.

 signal() operation: A process that changes the state of a resource can

execute [Link](). This resumes exactly one of the suspended processes
(if any) that are waiting on that condition variable.

This provides a more structured and safer way to handle process

suspension and resumption than raw semaphores. A process waiting on a
condition variable doesn't hold the monitor's lock, allowing other
processes to enter the monitor.

Monitor vs. Semaphores

 The main advantage of monitors over semaphores is their ability to
prevent common programming errors that can lead to deadlocks or other
timing issues. With semaphores, a programmer could mistakenly forget to
call a signal() operation or call wait() in the wrong order, causing the
entire system to deadlock.

With a monitor, mutual exclusion is handled automatically by the

construct itself. A programmer only needs to use the provided procedures
and the wait() and signal() operations on condition variables, which are
clearly defined and less prone to user error. This makes monitors a more
reliable and convenient solution for process synchronization.

11 Explain Dinning philosopher problem using monitors?

[Link]

The Problem Revisited

The Dining Philosophers Problem illustrates a classic deadlock scenario in

which five philosophers are seated at a round table with a single fork between
each pair.1 To eat, a philosopher needs to acquire both the left and right forks. A
deadlock can occur if all five philosophers simultaneously pick up their left
fork, leading to a state where everyone is holding one fork and waiting for the
other, which is held by a neighbor.

Monitors provide a more robust, deadlock-free solution by ensuring a

philosopher can pick up their chopsticks only if both are available.

The Monitor-Based Solution

The solution uses a single monitor named dp (for Dining Philosophers) that
encapsulates all shared data and synchronization logic. This monitor includes:

 enum state[5]: An array to keep track of the state of each of the five
philosophers. The possible states are thinking, hungry, and eating.
Initially, all philosophers are in the thinking state.
  condition self[5]: An array of condition variables, one for each
philosopher. A philosopher uses this to wait if they are hungry but can't
acquire the forks.

The monitor contains three key procedures:

1. pickup(int i) (When a philosopher gets hungry)

1. A philosopher i who wants to eat calls this function.

2. The philosopher's state is set to hungry.

3. The test(i) function is called to check if the philosopher can eat.

2. test(int i) (Checks if a philosopher can eat)

This function checks three conditions before allowing a philosopher i to eat:

1. The philosopher i is currently hungry.

2. The philosopher to the left ((i+4)%5) is not eating.

3. The philosopher to the right ((i+1)%5) is not eating.

If all three conditions are true, the philosopher's state is set to eating, and a
signal(self[i]) is invoked. This allows any waiting philosopher i to proceed with
eating. If any of the conditions are false, the philosopher's state remains
hungry, and they are forced to wait.

3. putdown(int i) (When a philosopher finishes eating)

1. A philosopher i who has finished eating calls this function.

2. Their state is set to thinking.

3. The test() function is called for both the left ((i+4)%5) and right
((i+1)%5) neighbors. This checks if either of them, now that a fork is
free, can start eating.

How this Solution Prevents Deadlock

The key to this solution is the test() function. Unlike the semaphore-based
solution where philosophers could acquire a single fork and wait indefinitely for
the second, this monitor-based approach ensures that a philosopher only
transitions to the eating state (acquires both forks) after both neighbors are
confirmed to be not eating.

If all five philosophers become hungry at the same time, they will all set their
state to hungry and call test(). The test() function for each philosopher will find
that their neighbors are also hungry, and thus not eating. However, no
philosopher can transition to the eating state because they are all waiting for the
signal() that can only be invoked after the test() conditions are fulfilled. Since
the monitor guarantees only one process can be active at a time, the first
philosopher to enter the monitor will check their neighbors. As their neighbors
are also hungry, they won't be in the eating state, so the test will pass for the
first philosopher, and they will start eating. This breaks the symmetric waiting
pattern and prevents deadlock. The signal(self[i]) operation on the condition
variable ensures that a waiting philosopher is woken up and gets a chance to eat
once the forks become available.

12 What is deadlock?

[Link]

A deadlock occurs in a multi-programming environment when a set of

processes are all waiting for resources that are held by other processes within
the same set. This creates a circular waiting condition where no process can
proceed because they are all dependent on each other to release a resource. It's a
state of permanent blocking.

For example, if Process A is holding Resource 1 and needs Resource 2, while

Process B is holding Resource 2 and needs Resource 1, a deadlock occurs. Both
processes are stuck, waiting for the other to release the needed resource.

Resources Involved in Deadlocks

Resources can be classified into two types, which is important for understanding
deadlocks:

 Preemptable Resources: These resources can be taken away from a

process without causing the computation to fail. A prime example is
 memory. The operating system can swap out a process from RAM to
make space for another.

 Non-preemptable Resources: These resources cannot be taken away

from a process without causing the computation to fail. Deadlocks
generally involve these types of resources. Examples include printers,
CD/DVD writers, and files that a process has locked for exclusive use.

The video emphasizes that deadlocks primarily involve non-preemptable

resources, as preemptable resources can often be reallocated to resolve a
potential deadlock.

13 What are the necessary conditions for the occurrence of

deadlock?

[Link]

Deadlock Characterization

Deadlock can be characterized in two ways: by the necessary conditions that

cause it and by using a resource allocation graph.

The Four Necessary Conditions

For a deadlock to occur, all four of the following conditions must be met
simultaneously:

1. Mutual Exclusion: At least one resource in the system must be a non-

shareable resource. This means that only one process at a time can use
the resource. If another process requests it, it must wait until the resource
is released.

2. Hold and Wait: A process must be holding at least one resource while
waiting to acquire additional resources that are currently held by other
processes.

3. No Preemption: Resources cannot be forcibly taken away from a

process. A resource can only be released voluntarily by the process that is
holding it after it has completed its task.
 4. Circular Wait: A set of processes must be waiting in a circular chain.
For example, Process P0 is waiting for a resource held by P1, P1 is
waiting for a resource held by P2, and so on, until the last process Pn is
waiting for a resource held by P0.

If any one of these four conditions is not met, a deadlock cannot occur.

Resource Allocation Graph

A resource allocation graph is a directed graph used to model and visualize a

system's state regarding processes and resource allocation. It can help detect a
deadlock.

 Vertices: The graph has two types of vertices:

o Circles (P): Represent processes.

o Squares (R): Represent resource types.

 Edges: There are two types of directed edges:

o Request Edge: An edge from a process to a resource (e.g., P1

→R1) indicates that the process is requesting an instance of that
resource.

o Assignment Edge: An edge from a resource to a process (e.g., R1

→P1) indicates that an instance of that resource has been allocated
to the process.

 Resource Instances: Dots within the square vertices represent the

number of instances available for that resource type.

Deadlock Detection using the Graph

A cycle in a resource allocation graph is a strong indicator of a potential

deadlock.

 Single-Instance Resources: If a cycle exists in the graph and every

resource type in the cycle has only one instance, then a deadlock has
definitely occurred.
  Multiple-Instance Resources: If a cycle exists in the graph but the
resources in the cycle have multiple instances, a deadlock may or may
not have occurred. The presence of a cycle in this case is a necessary but
not sufficient condition for a deadlock. It's possible that a waiting process
could eventually get the resource it needs from an instance that is released
by a non-involved process.

14 Explain the method to handle the deadlock?

[Link]

The methods used to handle deadlocks in operating systems.

There are four primary methods to handle a deadlock situation:

1. Deadlock Prevention

2. Deadlock Avoidance

3. Deadlock Detection and Recovery

4. Deadlock Ignorance

The first two methods are applied before a deadlock occurs, while the latter two
are used after a deadlock has already happened.

1. Deadlock Prevention 🚫

Deadlock prevention aims to ensure that a deadlock never occurs by

constraining how requests for resources are made. This is done by making sure
that at least one of the four necessary conditions for deadlock never holds true.
The four conditions are:

 Mutual Exclusion: A resource can be used by only one process at a time.

 Hold and Wait: A process holds one resource while waiting for another.
  No Preemption: A resource cannot be forcibly taken from a process.

 Circular Wait: A circular chain of processes exists where each process is

waiting for a resource held by the next process in the chain.

By designing the system in a way that breaks at least one of these conditions,
you can prevent deadlocks from ever happening. For example, if you can
eliminate the "Hold and Wait" condition by forcing processes to request all their
necessary resources at once, you can prevent a deadlock.

2. Deadlock Avoidance 🧠

Deadlock avoidance is a less strict approach than prevention. Instead of

preventing any of the four conditions from ever happening, it allows the
conditions to exist but ensures that the system always remains in a "safe state."
A safe state is one where the system can allocate resources to each process in
some order without causing a deadlock.

This method requires that the operating system has prior knowledge of the
resources that each process will need during its lifetime. The system then
dynamically examines the resource allocation state to ensure that there is a safe
sequence of processes that can be executed. The Banker's Algorithm is a
classic example of a deadlock avoidance algorithm.

3. Deadlock Detection and Recovery 🚨

This approach is applied after a deadlock has occurred. The system allows
deadlocks to happen but then detects them and recovers from them.

 Detection: The system periodically runs a detection algorithm (often

using a resource allocation graph) to check for the presence of a
deadlock. If a cycle is found in the graph, it signifies that a deadlock has
occurred.

 Recovery: Once a deadlock is detected, the system must recover to break

the deadlock. A simple recovery strategy is to terminate one or more
processes involved in the deadlock. By killing a process, its held
resources are released, potentially allowing the other processes to
continue execution.

4. Deadlock Ignorance 🤷
This is the most common approach used in many modern operating systems,
such as Windows and Linux. The operating system simply ignores the
possibility of a deadlock and assumes that deadlocks will never occur. The
rationale behind this approach is that deadlocks are extremely rare events, and
the overhead required for prevention, avoidance, or detection and recovery
would be too high and would degrade system performance. If a deadlock does
occur, it is often handled by a simple system reboot.

15 Write deadlock prevention techniques?

[Link]

What is Deadlock Prevention?

Deadlock prevention is an approach to handling deadlocks

by ensuring that one of the four necessary conditions for a
deadlock can never occur. The four conditions are mutual
exclusion, hold and wait, no preemption, and circular
wait. By eliminating just one of these, you can guarantee that
a deadlock will not happen.

Eliminating the Four Conditions

The video analyzes each of the four conditions to see if they

can be eliminated.

1. Mutual Exclusion ❌

 Definition: Resources are non-shareable, meaning only

one process can use a resource at a time.

 Can it be eliminated? No. For many resources like

printers or tape drives, simultaneous access by multiple
processes would lead to corrupted or meaningless results.
It's not logically possible to eliminate this condition for all
resource types.

2. Hold and Wait ✅

  Definition: A process holds at least one resource while
waiting to acquire another resource held by a different
process.

 Can it be eliminated? Yes. Two main approaches can be

used:

1. Request all resources at once: A process must

request all the resources it needs before it starts
execution. It only proceeds if all resources are
granted. This eliminates the "hold" part of the
condition.

2. Release held resources: If a process holding

resources requests a new one that isn't available, it
must release all the resources it currently holds and
then re-request them.

 Disadvantages: These approaches have major

drawbacks, including poor resource utilization
(resources are held even when not in use) and starvation
(a process might repeatedly fail to acquire all its resources
and never run).

3. No Preemption ✅

 Definition: A resource cannot be forcibly taken away

from a process; it can only be released voluntarily by the
process itself.

 Can it be eliminated? Yes. The operating system can be

designed to preempt resources in certain situations. For
example:

1. If a process requests a resource that is not available,

the OS can check if the requesting process is
currently holding any other resources. If so, the OS
can preemptively take those resources away and
reallocate them to other waiting processes.
 2. If a process holding a resource is waiting for another
resource, the OS can preempt the resources from the
waiting process and reallocate them to a different
process that needs them.

4. Circular Wait ✅

 Definition: A circular chain of processes exists, where

each process is waiting for a resource held by the next
process in the chain.

 Can it be eliminated? Yes. You can impose an ordering

on all resource types.

 Approach: The operating system assigns a unique integer

to each resource type (e.g., printer=1, scanner=2).
Processes must request resources in a strictly
incremental order. If a process is holding a resource type
with an integer value of i, it can only request a new
resource with a value greater than i. This prevents the
formation of a circular wait chain.

16 Explain deadlock avoidance using Banker's Algorithm?

[Link]

Banker's Algorithm is a deadlock avoidance algorithm used in operating

systems. It helps ensure that a system remains in a safe state by carefully
allocating resources to processes, preventing a deadlock from ever occurring.
The algorithm checks if a requested resource allocation will leave the system in
a safe state, where it can eventually complete all processes, even if they make
maximum resource requests. It is also known as the safety algorithm.

The Core Idea

The algorithm's main goal is to allocate resources to processes in a way that

avoids deadlock. It does this by checking a single condition: if a process's
needed resources are less than or equal to the available resources, it can be
executed.
If this condition is met:

1. The resources are allocated to the process.

2. The process executes and completes.

3. The process releases all its allocated resources.

4. The system's available resources are updated to include the newly

released ones.

This process is repeated for all processes that haven't completed their execution.
If all processes can eventually finish, the state is considered safe.

Key Concepts and Data Structures

To implement the Banker's Algorithm, the following key data structures are
used:

 Processes (Pᵢ): A set of processes (e.g., P₀, P₁, P₂, etc.) that request and
use resources.

 Resources (Rⱼ): A set of resource types (e.g., R₀, R₁, R₂, etc.). Each
resource type has a certain number of instances.

The algorithm relies on four main matrices and vectors:

 Available: A vector representing the number of currently available

resources of each type. This is the pool of resources that can be allocated.

 Maximum: An n×m matrix (where n is the number of processes and m is

the number of resource types) that defines the maximum number of
resources of each type that a process might need to complete its task.

 Allocation: An n×m matrix showing the number of resources of each type

currently allocated to each process.

 Need: An n×m matrix that indicates the number of resources each process
needs to complete its execution. It is calculated as:

Need=Maximum−Allocation
Example Walkthrough

Let's illustrate the algorithm with a concrete example.

Given:

 Processes: P₀, P₁, P₂, P₃, P₄

 Resource Types: R₀, R₁, R₂

 Total Resources: R₀ = 10, R₁ = 5, R₂ = 7

State Table:

Process Maximum Allocation

R₀ R₁ R₂ R₀ R₁ R₂

P₀ 753 010

P₁ 322 302

P₂ 902 302

P₃ 222 211

P₄ 433 002

Step 1: Calculate Need and Available Resources

First, we calculate the Need matrix and the initial Available resources.

 Need: We use the formula Need=Maximum−Allocation.

Process Need

R₀ R₁
R₂
 Process Need

P₀ 743

P₁ 020

P₂ 600

P₃ 011

P₄ 431

 Available: We sum up the allocated resources and subtract them from the
total.

o Allocated R₀: 0+3+3+2+0=8. Available R₀: 10−8=2.

o Allocated R₁: 1+0+0+1+0=2. Available R₁: 5−2=3.

o Allocated R₂: 0+2+2+1+2=7. Available R₂: 7−7=0.

So, the initial Available vector is: (2, 3, 0).

Step 2: Find a Safe Sequence

Now, we check which processes can complete their execution with the available
resources. We find a safe sequence of process execution.

 P₀: The need is (7, 4, 3), and available is (2, 3, 0).

o Need R₀ (7) is not ≤ Available R₀ (2). Cannot execute.

 P₁: The need is (0, 2, 0), and available is (2, 3, 0).

o Need (0, 2, 0) ≤ Available (2, 3, 0). Condition met.

Action: P₁ can be completed. We add P₁ to our safe sequence.

o New Available: Current Available + P₁'s Allocated Resources

o New Available = (2, 3, 0) + (3, 0, 2) = (5, 3, 2).

 P₂: The need is (6, 0, 0), and available is now (5, 3, 2).
 o Need R₀ (6) is not ≤ Available R₀ (5). Cannot execute.

 P₃: The need is (0, 1, 1), and available is now (5, 3, 2).

o Need (0, 1, 1) ≤ Available (5, 3, 2). Condition met.

Action: P₃ can be completed. We add P₃ to our safe sequence.

o New Available: Current Available + P₃'s Allocated Resources

o New Available = (5, 3, 2) + (2, 1, 1) = (7, 4, 3).

 P₄: The need is (4, 3, 1), and available is now (7, 4, 3).

o Need (4, 3, 1) ≤ Available (7, 4, 3). Condition met.

Action: P₄ can be completed. We add P₄ to our safe sequence.

o New Available: Current Available + P₄'s Allocated Resources

o New Available = (7, 4, 3) + (0, 0, 2) = (7, 4, 5).

 P₀: We go back to the beginning to check the uncompleted processes.

The need is (7, 4, 3), and available is now (7, 4, 5).

o Need (7, 4, 3) ≤ Available (7, 4, 5). Condition met.

Action: P₀ can be completed. We add P₀ to our safe sequence.

o New Available: Current Available + P₀'s Allocated Resources

o New Available = (7, 4, 5) + (0, 1, 0) = (7, 5, 5).

 P₂: The need is (6, 0, 0), and available is now (7, 5, 5).

o Need (6, 0, 0) ≤ Available (7, 5, 5). Condition met.

Action: P₂ can be completed. We add P₂ to our safe sequence.

o New Available: Current Available + P₂'s Allocated Resources

o New Available = (7, 5, 5) + (3, 0, 2) = (10, 5, 7).

Step 3: Conclude
All processes have been completed. The final available resources vector, (10, 5,
7), matches the total number of resources in the system, which confirms all
resources were released.

Since we found a sequence where all processes can complete their execution,
the system is in a safe state. Therefore, a deadlock will not occur.

The safe sequence is: <P₁, P₃, P₄, P₀, P₂>.

17 ExplainDeadlock Detection using a Resource Allocation Graph

[Link]

Deadlock Detection using a Resource Allocation Graph 🔎

Deadlock detection is a method for identifying if a system has entered a

deadlock state. One of the primary tools for this is a Resource Allocation Graph.
This graph visually represents the state of a system's resources and the processes
that hold or request them.

The graph consists of two types of vertices:

 Processes (P): Represented by a circle.

 Resources (R): Represented by a rectangle.

Within the resource rectangle, dots are used to represent the number of
instances of that resource. For example, a rectangle with one dot represents a
resource with a single instance, while a rectangle with two dots represents a
resource with two instances.

Edges in the Graph

There are two types of edges (directed arrows) in a resource allocation graph:

 Request Edge: This is an arrow from a process to a resource. It signifies

that the process is requesting an instance of that resource.

 Assignment Edge: This is an arrow from a resource to a process. It

signifies that the resource instance has been assigned (or allocated) to the
process.

Deadlock Detection Rules

The key to using the resource allocation graph for deadlock detection is to look
for cycles. A cycle occurs when there is a circular dependency in the graph,
such as Process P₁ requesting a resource held by P₂, which in turn is requesting
a resource held by P₃, and so on, until Pₙ is requesting a resource held by P₁.

The interpretation of a cycle depends on the type of resources involved:

Resource
Cycle Detection Rule Outcome
Type

Single If a cycle is formed, it definitely Deadlock

Instance indicates a deadlock. Detected

Multiple If a cycle is formed, it may indicate a Possible

Instances deadlock, but it's not guaranteed. Deadlock

Example Walkthroughs

Case 1: Single-Instance Resources 📌

Consider the following scenario:

 P₁ holds R₁ and requests R₂.

 P₂ holds R₂ and requests R₁.

The resource allocation graph for this would show a cycle: P₁ → R₂ → P₂ →
R₁ → P₁.

Since R₁ and R₂ are single-instance resources, this cycle confirms a deadlock.

P₁ cannot proceed because P₂ holds R₂, and P₂ cannot proceed because P₁
holds R₁. This is a classic "circular wait" condition.

Case 2: Multiple-Instance Resources 🔁

Consider a different scenario with a multi-instance resource, R₂:

 P₁ holds R₁ and requests an instance of R₂.

 P₂ holds an instance of R₂ and requests R₁.

 There is a second, available instance of R₂.

The graph would still show a cycle: P₁ → R₂ → P₂ → R₁ → P₁.

However, because R₂ has a second instance available, P₁ can still be allocated a

new instance of R₂, complete its task, and release R₁. Once R₁ is released, P₂
can then acquire it and finish. Therefore, despite the cycle, there is no deadlock.
The cycle only indicates a possibility of a deadlock, which must be verified by a
more complex algorithm.

Summary of Deadlock Detection

Single-Instance Multiple-Instance
Graph Condition
Resources Resources

May or may not be

Cycle Forms Deadlock
deadlock

No Cycle No Deadlock No Deadlock

In conclusion, while a resource allocation graph is a powerful visual tool, it only

provides a definitive answer for deadlock detection when dealing with single-
instance resources. For multi-instance resources, more complex algorithms are
needed to verify if the system is truly in a deadlock state.
18 Explain deadlock recovery?

[Link]

Deadlock recovery in operating systems. Deadlock recovery

refers to the process of restoring the system to a safe state
once a deadlock has been detected. This can be achieved
through two primary strategies: process termination and
resource preemption.

1. Process Termination

This method involves ending one or more processes to break

the circular dependency that caused the deadlock. There are
two main approaches:

A. Abort All Processes 💀

This is the simplest but most drastic approach. All processes

involved in the deadlock are terminated. This immediately
resolves the deadlock, but it has a major drawback: any work
completed by those processes is lost and must be restarted
from the beginning. This is an expensive solution, especially for
long-running jobs that were near completion.

B. Abort One Process at a Time ✂️

A more controlled approach is to terminate only one process at

a time. After each termination, the system's state is re-
evaluated using a deadlock detection algorithm (like the
Banker's Algorithm) to see if the deadlock has been resolved.
This is repeated until the system returns to a safe state.

This method is less disruptive than aborting all processes, but it

introduces its own set of problems:

 Overhead: Repeatedly running the deadlock detection

algorithm after each termination is computationally
intensive and creates significant overhead.
  Process Selection: Deciding which process to terminate is
a critical and complex decision. The criteria for selecting a
"victim" process can include:

o Priority: Terminating a low-priority process.

o Resources Held: Terminating a process holding many

resources that are needed by other processes.

o Completion Progress: Terminating a process that has

not yet completed much of its work.

2. Resource Preemption

This method involves taking a resource away from a process

that currently holds it and giving it to another process. This is
done "preemptively" or by force, rather than waiting for the
holding process to release it voluntarily. Resource preemption
requires a rollback mechanism.

The process of resource preemption involves three key steps:

A. Victim Selection 🎯

First, a "victim" process must be chosen from which to preempt

a resource. The criteria for this selection are similar to those for
process termination, aiming to minimize the cost of the
preemption. Factors considered include the process's priority,
the number of resources it holds, and its progress.

B. Rollback ⏪

After a resource is taken from a process, that process is often

forced to rollback to a safe state, effectively restarting from a
checkpoint or from the beginning. This is necessary because
the process's state may have become inconsistent without the
preempted resource. The process will then have to wait for the
resource to be allocated to it again.

C. Starvation ⏳
A significant problem with resource preemption is starvation. If
the same process is repeatedly chosen as the victim for
resource preemption, it may never be able to complete its
execution. This happens when the process keeps restarting
only to have its resources taken away again. A fair preemption
strategy is needed to prevent this.

Summary

In summary, recovering from a deadlock involves a choice

between two main strategies, each with its own trade-offs:

1. Process Termination: Simple but potentially wasteful if all

processes are aborted. A more iterative approach can be
used, but it introduces overhead and requires careful
victim selection.

2. Resource Preemption: A more granular approach that

targets specific resources. It requires a robust rollback
mechanism and carries the risk of starvation if not
managed properly.