Q?

1 Process Synchroniza on (in brief)

- In a single-processor mul programming system, processes are not executed

concurrently. In order to get the appearance of concurrent execu on, a fixed me slot
is allocated to each process.
- A er u liza on of this me slot, CPU gets allocated to other process. Such switching
of CPU back and forth between processes is called as context switch.
- At a me single process gets executed so parallel processing cannot be accomplished.
- Also there is a definite amount of overhead drawn in switching back and forth
between processes.
- Apart from above limita ons, interleaved execu on offers major benefits in
processing efficiency and in program structuring.
- In a mul ple processor system, interleaving and overlapping the execu on of mul ple
processes is achievable.
- Both interleaving and overlapping correspond to basically diverse modes of execu on
and present diverse problems.
- In reality, both interleaving and overlapping can be treated as illustra on of
concurrent processing and both the techniques address the similar problems.
- The compara ve speed of execu on of processes depends on ac vi es and behavior
of other processes, how the opera ng system handles interrupts, and the scheduling
policies of the opera ng system.
Q?2 Inter-Process Communica on (IPC) in brief

- Synchroniza on and communica on are two basic requirements should be sa sfied

when processes communicate with each other.
- Synchroniza on of processes is required to achieve the mutual exclusion.
- Independent processes do not communicate with each other but coopera ng
processes may need to exchange informa on. Coopera ve processes either
communicates through shared memory or message passing.
- Coopera ng processes require an Interprocess Communica on (IPC) mechanism that
will allow them to exchange data and informa on.

There are two fundamental models of interprocess communica on:

Shared memory
Message passing

- 1. Shared Memory
- In the shared-memory model, a region of memory that is shared by coopera ng
processes is established.
- Processes can then exchange informa on by reading and wri ng data to the shared
region.
- In the message passing model, communica on takes place by means of messages
exchanged between the coopera ng processes.

- 2. Message Passing
- Message passing provides both func ons.
- Message passing has the further benefit that it lends itself to implementa on in
distributed systems as well as in shared-memory mul processor and uniprocessor
systems.
 Q?3 Cri cal Sec on (Short Answer)

- The por on of the program where shared memory is accessed is called the Cri cal
Sec on.
- To avoid race condi ons and incorrect results, only one process should execute in the
cri cal sec on at a me.
- Cri cal sec on code involves read-update-write opera ons on shared data which may
be modified by other processes.
- Hence, execu on of cri cal sec ons must be mutually exclusive.
- An algorithm is required to ensure that only one process enters the cri cal sec on at
a me without deadlock.
- The solu on must sa sfy three condi ons: Mutual Exclusion, Progress, and Bounded
Wai ng.
- A process must request permission (entry sec on), execute (cri cal sec on), and then
leave (exit sec on).
- The remaining code is called the remainder sec on.

Necessary Condi ons of Cri cal Sec on Problem

1. Mutual Exclusion
 At a me, only one process should be execu ng in the cri cal sec on (CS).
 If currently process Pi is execu ng in its CS, then other processes should not execute
in their cri cal sec ons.

2. Progress
 If no process is execu ng in its CS, then processes that wish to enter their CS can
par cipate in deciding which will enter next.
 The selec on of the next process cannot be postponed indefinitely.

3. Bounded Wai ng
 A limit must be set on the number of mes that other processes are allowed to enter
their cri cal sec ons a er a process has made a request to enter its CS and before
that request is granted.
 Q?4 Race Condi on

- A race condi on takes place when more than one process write data items so that the
final result depends on the order of execu on of instruc ons in the mul ple
processes.
- Consider two processes, P₁ and P₂, which share the global variable “x”.
At the me of execu on, process P₁ updates “x” to the value 1 and at the me of
execu on of another process, P₂ updates “x” to the value 2.
- Thus, the two tasks are in a race to write variable “x”.
In this example, the process that modifies x value lastly decides the final value of “x”.
-
Role of Opera ng System
- The opera ng system should be capable of keeping track of the different processes.
- Alloca on and reclama on of various resources should be done by opera ng system.
- Each process’s data and physical resources should be protected by opera ng system
against uninten onal interfering by other processes.
- The opera ons performed by the process and the output that it generates should not
depend on the speed of execu on compare to the speed of other concurrent
processes.
 Q?5 Peterson’s Solu on to Mutual Exclusion

- Peterson’s solution is applicable for only two processes. It provides a simple way to
understand the critical section problem and satisfies mutual exclusion, progress and
bounded waiting.
- The two processes Pi and Pj execute alternately between their critical section and
remainder section.

int x;
boolean y[2];

- The variable x decides who will enter in its cri cal sec on. If x = i, then process Pi is
permissible to execute in its cri cal sec on.
- The y array is used to specify whether process is ready to enter its cri cal sec on.
- For example, if y[i] is true, this value indicates that Pi is ready to enter its cri cal
sec on.
- In order to enter the cri cal sec on, process Pi first sets y[i] = true and then sets
variable x to the value j. Pi sets x = j because, if the other (Pj) process desires to enter
the cri cal sec on, it can do so.
- If both processes a empt to enter simultaneously, x will be set to both i and j at
approximately the same me.
- Only one of these assignments will last; the other will occur but will be overwri en
straight away.
-
Algorithm
do {
y[i] = TRUE;
x = j;
while (y[j] && x == j);
y[i] = FALSE;
} while (TRUE);
 Q?6 Producer–Consumer Problem (Algorithm)

- In producer-consumer problem assumes that buffer is bounded buffer. This means

that there is a finite numbers of slots are available in a buffer. While producing the
items, if the buffer is full the producer process should be suspended.
- In the same way, while consuming the items from buffer, if it becomes empty,
consumer should be suspended. It is also necessary to ensure that only one process
at a time manipulates a buffer to avoid race conditions or lost updates.
- Sleep-wake up system calls is used in this situation to avoid race condition. Producer
process should go to sleep when buffer is full and consumer process should wake up
when producer will put data in buffer.
- In the same way, consumer goes to sleep until the producer puts some data in buffer
and wakes up to consume this data.
- Here two processes, producer and consumer share a common, fixed-size (bounded)
buffer. The producer puts data into the buffer and the consumer takes data out.
- Difficulty arises when the producer wants to put a new data in the buffer, but there is
no space in buffer. That is, it is already full.
- Way out to this problem is that, producer goes to sleep and to be awakened when
the consumer has removed data.
- It may also happen that, consumer wants to take out data from the buffer but buffer
is already empty.
- Way out to this problem is that, consumer goes to sleep un l the producer puts some
data in buffer and wakes consumer up.
 Q?7 Deadlock

 We know that processes needs different resources in order to complete the

execu on.
 So in a mul programming environment, many processes may compete for a mul ple
number of resources.
 In a system, resources are finite. So with finite number of resources, it is not possible
to fulfill the resource request of all processes.
 When a process requests a resource and if the resource is not available at that me,
the process enters a wait state. In a mul programming environment it may happen
with many processes.
 There is chance that wai ng processes will remain in same state and will never again
change state.
 It is because the resources they have requested are held by other wai ng processes.
When such type of situa on occurs then it is called as deadlock.
 If there are 5 same type of resources are available in system then we say that there
are 5 instances of this resource type.
 Suppose the process request the instance of resource. If any instance of the resource
type is allocated to it, then request will be fulfilled.
 If it is not possible to fulfill the request, then the instances are not iden cal, and the
resource type classes have not been defined appropriately.
 As a rule, first process must request a resource and then use it. A er the use of this
resource, it should release it. A process may request any number of resources which
are necessary to complete its execu on.
Following are the sequence when a process may u lize a resource :
1. Request : If it is not possible to fulfill the request instantly, then the reques ng
process must wait un l it can get the resource.
2. Use : The process use the resource to accomplish the task.
3 Release : The process free the resource a er use
 Q?8 Necessary condi ons for deadlock

If the following four condi ons hold simultaneously in a system then a deadlock situa on can
occur in the system.
Four condi ons of deadlock
1. Mutual exclusion
2. Hold and wait
3. No preemp on
4. Circular wait

➔ 1. Mutual exclusion
This condi on ensure that, resource should be used by single process at a me and it
remains with using process in non-sharable mode. If same resource is needed by another
process then the reques ng process must be postponed to use this resource. Reques ng
process will get the resource a er released by holding process.
➔ 2. Hold and wait
The process holds minimum one resource and waits to obtain remaining needed resources
that are at present being held by other processes.
➔ 3. No preemp on
Preemp on of the resource will not be done; Process holding the resource, releases it on its
own a er the comple on of the its chosen task.
➔ 4. Circular wait
In this condi on, a collec on of wai ng processes say {P0, P1, ...., Pn } exist such that P0 is
wai ng for a resource that is held by P1, P1 is wai ng for a resource that is held by P2, .....,
Pn-1 is wai ng for a resource that is held by Pn, and Pn is wai ng for a resource that is held
by P0.
 Q?9 Deadlock Preven on

Deadlock Preven on (Simple and Easy Explana on)

 Deadlock occurs when all four condi ons happen together:
Mutual exclusion, Hold and wait, No preemp on, Circular wait
 To prevent deadlock, we make sure that at least one of these condi ons does not
occur.
 So, deadlock preven on is done by denying one or more of these condi ons.

1. Mutual Exclusion
 Some resources are non-shareable (e.g., printer).
 Only one process can use such resources at a me.
 If another process requests it, it must wait.
 This condi on cannot be completely eliminated because some resources are
inherently non-shareable.

2. Hold and Wait

 A process holds one resource and waits for addi onal resources.
 To prevent this:
o A process should request all resources at once before execu on, OR
o It should request resources only when it is not holding any resource
 Disadvantages:
o Resources may remain unused for a long me
o Can cause starva on (some processes may wait indefinitely)
3. No Preemp on
 Normally, resources cannot be taken back forcefully from a process.
 To prevent deadlock:
o If a process requests a new resource and it is not available,
it must release all currently held resources
o These resources are then allocated to other processes
 The process will request all resources again later.

4. Circular Wait
 Deadlock occurs when processes form a circular chain of wai ng
(e.g., P1 → P2 → P3 → P1)
 To prevent this:
o Assign a number/order to each resource type
o Processes must request resources in increasing order only
 This removes the possibility of circular wai ng.
 Q?10 Deadlock Avoidance

 Deadlock avoidance requires that the system has some informa on in advance.
Ini ally every process declares the maximum number of resources it may need.
 Another way to avoid deadlock is to have extra informa on about how resources will
be requested.
 If we know the order in which a process will request and release resources, then we
can decide for each request whether the process should wait or proceed.
 To avoid circular wait completely, deadlock avoidance algorithm checks the resource
alloca on state dynamically.
Resource Alloca on State includes:
 Number of available resources in the system
 Number of allocated resources
 Maximum requirement of processes

 Dijkstra’s Banker’s algorithm is used for deadlock avoidance.

 It requires prior knowledge of the maximum resources needed by each process.
 The OS behaves like a banker:
o It gives resources only if enough resources are available
o Otherwise, it makes the process wait
 This situa on is called a safe state.

➔ Safe State
 A system is in a safe state if it can allocate resources to all processes in some order
and s ll avoid deadlock.
 If there exists a sequence like < P1, P2, …, Pn >, then it is called a safe sequence.
 In this sequence, each process Px can get its required resources from:
i. Available resources in the system
ii. Resources released by previous processes (Py where y < x)
 If a process (Pi) cannot get required resources, it must wait un l another process (Pj)
finishes and releases resources.
 Q?11 Deadlock Avoidance

 Banker’s algorithm is used in a system where there are mul ple instances of each
resource type.
 It is less efficient compared to resource-alloca on graph algorithm.
 Every new process must tell in advance the maximum number of resources it may
need.
 A process should not request more resources than available in the system.
 When a process makes a request, the system checks whether giving resources will
keep the system in a safe state.
o If yes → resources are allocated
o If no → process must wait

Data Structures Used in Banker’s Algorithm

1. Available (A[m])
 Array of size m
 Shows number of available resources of each type

2. Max (M[n][m])
 2D array
 Shows maximum resources needed by each process
 M[i][j] = k → Process Pi may need at most k instances of resource Rj

3. Alloca on (C[n][m])
 2D array
 Shows currently allocated resources to each process
 C[i][j] = k → Process Pi has been given k instances of resource Rj
4. Need (N[n][m])
 2D array
 Shows remaining resources needed by each process
 Formula:
N[i][j] = M[i][j] - C[i][j]
 N[i][j] = k → Process Pi s ll needs k more instances of resource Rj