BGS COLLEGE OF ENGINEERING AND TECHNOLOGY

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

Mahalakshmi Layout, Bengaluru-560086

OPERATING SYSTEM [BCS303]

MODULE-03

PROCESS SYNCHRONIZATION AND DEADLOCKS

QUESTION BANK SOLUTIONS

 MODULE-03
PROCESS SYNCHRONIZATION AND DEADLOCKS
QUESTION BANK:
[Link] is critical section? What are the requirements for the solution to critical section
problem? Explain Peterson’s solution. (Dec2023, Dec2024)

[Link] Reader’s-Writer’s problem using semaphores. (Dec2023, Dec2024)

[Link] is deadlock? What are the necessary conditions for the deadlock to occur?
(Dec2023, June2023, Mar2022, Dec2024)

[Link] different methods to recovery from deadlocks. (Jan2023)

5. What are necessary conditions for deadlock? (Jan2023)

6. What is paging hardware with TLB? (Jan2023)
[Link] structure of page table with respect to hierarchical paging. (Jan2023)

[Link] the process of segmentation. (Jan2023)

[Link] in detail how deadlock can be prevented. (June2023)

[Link] is paging? Illustrate with example internal and external fragmentation problem
encountered in contiguous memory allocation. (June2023, Mar2022)

[Link] the three methods of memory allocation. With a neat diagram explain in the
hardware support for relocation and limit register. (June2023)

[Link] is segmentation? Explain with a neat diagram. (June2023)

[Link] the resource allocation graph (Mar2022)

i) With deadlock.

ii) With a cycle but no deadlock.

[Link] are Translation Loadaside Buffer (TLB)? Explain TLB in detail with a simple paging
system with a neat diagram. (Mar2022)

[Link] the help of a neat diagram, explain the various steps of address binding. (Mar2022)
[Link] is a semaphore? Discuss the solution to the classical dinning philosopher problem.
(Dec2024)

[Link] the following snapshot of system : (Dec2023)

Answer the following using Banker’s algorithm:

i) Is the system is safe state? If so give the safe sequence.
ii) If process P2 requests (0,1,1,3) resource can it be granted immediately.

18. Consider the following snap-short of a system:

i)Find the need matrix and calculate safe sequence using banker’s algorithm mention the
above is safe or not safe.

ii)If a request from P1 arrives for (1,0,2) can the request be granted immediately?
(Jan2023, June2023, Dec2024)
 SOLUTIONS
[Link] is critical section? What are the requirements for the solution to
critical section problem? Explain Peterson’s solution. (Dec2023, Dec2024)

• Consider a system consisting of n processes {Po, P1 , ... ,Pn-1}.

• Each process has a segment of code, called a critical section in which the
process may be changing common variables, updating a table, writing a file,
and soon
• The important feature of the system is that, when one process is executing in
its critical section, no other process is to be allowed to execute in its critical
section. That is, no two processes are executing in their critical sections at the
same time.
• The critical-section problem is to design a protocol that the processes can use
to cooperate.

The general structure of a typical process Pi is shown in below figure

• Each process must request permission to enter its critical section. The section
of code implementing this request is the entry section.
• The critical section may be followed by an exit section. The remaining code is
the reminder section.

Figure: General structure of a typical process Pi

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'S SOLUTION

• This is a classic software-based solution to the critical-section problem.

There are no guarantees that Peterson's solution will work correctly on modern
computer architectures
• Peterson's solution provides a good algorithmic description of solving
the critical section problem and illustrates some of the complexities involved in
designing software that addresses the requirements of mutual exclusion,
progress, and bounded waiting.
Peterson's solution is restricted to two processes that alternate execution
between their critical sections and remainder sections. The processes are
numbered Po and P1 or Pi and Pj where j = 1-i
Peterson's solution requires the two processes to share two data items:
int turn; boolean
flag[2];
• turn: The variable turn indicates whose turn it is to enter its critical
section. Ex: if turn == i, then process Pi is allowed to execute in its critical
section.
• flag: The flag array is used to indicate if a process is ready to enter its
critical section. Ex: if flag [i] is true, this value indicates that Pi is ready to enter
its critical section.

Figure: The structure of process Pi in Peterson's solution

• 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 over written immediately.
• The eventual value of turn determines which of the two processes is
allowed to enter its critical section first.
To prove that solution is correct, we need to show that
1. Mutual exclusion is preserved
2. Progress requirement is satisfied
3. Bounded-waiting requirement is met
1. To prove Mutual exclusion
• Each Pi enters its critical section only if either flag [j] == false or turn ==i.
• If both processes can be executing in their critical sections at the same time,
then flag [0] == flag [1]==true.
• These two observations imply that Pi and Pj could not have successfully
executed their while statements at about the same time, since the value of
turn can be either 0 or 1 but cannot be both. Hence, one of the processes (Pj)
must have successfully executed the while statement, whereas Pi had to
execute at least one additional statement ("turn==j").
• However, at that time, flag [j] == true and turn == j, and this condition will
persist as long as Pi is in its critical section, as a result, mutual exclusion is
preserved.
2. To prove Progress and Bounded-waiting
• A process Pi can be prevented from entering the critical section only if it is
stuck in the while loop with the condition flag [j] ==true and turn=== j; this
loop is the only one possible.
• If Pj is not ready to enter the critical section, then flag [j] ==false, and Pi can
enter its critical section.
• If Pj has set flag [j] = true and is also executing in its while statement, then
either turn === i or turn ===j.
If turn == i, then Pi will enter the critical section.
If turn== j, then Pj will enter the critical section.
• However, once Pj exits its critical section, it will reset flag [j] = false, allowing
Pi to enter its critical section.
• If Pj resets flag [j] to true, it must also set turn to i.
• Thus, since Pi does not change the value of the variable turn while executing
the while statement, Pi will enter the critical section (progress) after at most
one entry by Pj (bounded waiting).
[Link] Reader’s-Writer’s problem using semaphores. (Dec2023, Dec2024)
Readers-Writers Problem

• A data set is shared among a number of concurrent processes • Readers –

only read the data set; they do not perform any updates
• Writers – can both read and write.
• Problem – allow multiple readers to read at the same time. Only one single
writer can access the shared data at the same time.
• Shared Data
• Dataset
• Semaphore mutex initialized to 1.
• Semaphore wrt initialized to1.
• Integer readcount initialized to 0.
[Link] is deadlock? What are the necessary conditions for the deadlock to
occur? (Dec2023, June2023, Mar2022, Dec2024)

A process requests resources, if the resources are not available at that time,
the process enters a waiting state. Sometimes, a waiting process is never again
able to change state, because the resources it has requested are held by other
waiting processes. This situation is called a Deadlock.
Necessary Conditions
A deadlock situation can arise if the following four conditions hold
simultaneously in a system:
1. Mutual exclusion: At least one resource must be held in a non-sharable
mode, that is, only one process at a time can use the resource. If another
process requests that resource, the requesting process must be delayed until
the resource has been released.
2. Hold and wait: A process must be holding at least one resource and waiting
to acquire additional resources that are currently being held by other
processes.
3. No preemption: Resources cannot be preempted; that is, a resource can be
released only voluntarily by the process holding it, after that process has
completed its task.
4. Circular wait: A set {P0, P1, ... , Pn} of waiting processes must exist such that
Po is waiting for a resource held by P1, P1 is waiting for a resource held by
P2, ... , Pn-1 is waiting for a resource held by Pn and Pn is waiting for a resource
held by Po.
4. Explain different methods to recovery from deadlocks. (Jan2023)

RECOVERY FROM DEADLOCK

The system recovers from the deadlock automatically. There are two options
for breaking a deadlock one is simply to abort one or more processes to break
the circular wait. The other is to preempt some resources from one or more of
the deadlocked processes.
Process Termination
To eliminate deadlocks by aborting a process, use one of two methods. In both
methods, the system reclaims all resources allocated to the terminated
processes.
1. Abort all deadlocked processes: This method clearly will break the
deadlock cycle, but at great expense; the deadlocked processes may have
computed for a long time, and the results of these partial computations must
be discarded and probably will have to be recomputed later.
2. Abort one process at a time until the deadlock cycle is eliminated: This
method incurs considerable overhead, since after each process is aborted, a
deadlockdetection algorithm must be invoked to determine whether any
processes are still deadlocked.
If the partial termination method is used, then we must determine which
deadlocked process (or processes) should be terminated. Many factors may
affect which process is chosen, including:
1. What the priority of the process is
2. How long the process has computed and how much longer the process will
compute before completing its designated task
3. How many and what types of resources the process has used.
4. How many more resources the process needs in order to complete
5. How many processes will need to be terminated?
6. Whether the process is interactive or batch
Resource Preemption
To eliminate deadlocks using resource preemption, we successively preempt
some resources from processes and give these resources to other processes
until the deadlock cycle is broken. If preemption is required to deal with
deadlocks, then three issues need to be addressed:
1. Selecting a victim. Which resources and which processes are to be
preempted? As in process termination, we must determine the order of
preemption to minimize cost. Cost factors may include such parameters as the
number of resources a deadlocked process is holding and the amount of time
the process has thus far consumed during its execution.
2. Rollback. If we preempt a resource from a process, what should be done
with that process? Clearly, it cannot continue with its normal execution; it is
missing some needed resource. We must roll back the process to some safe
state and restart it from that state. Since it is difficult to determine what a safe
state is, the simplest solution is a total rollback: abort the process and then
restart it.
3. Starvation. How do we ensure that starvation will not occur? That is,
how can we guarantee that resources will not always be preempted from the
same
process?

5. What are necessary conditions for deadlock? (Jan2023)

Necessary Conditions
A deadlock situation can arise if the following four conditions hold
simultaneously in a system:
1. Mutual exclusion: At least one resource must be held in a non-sharable
mode, that is, only one process at a time can use the resource. If another
process requests that resource, the requesting process must be delayed until
the resource has been released.
2. Hold and wait: A process must be holding at least one resource and
waiting to acquire additional resources that are currently being held by other
processes.
3. No preemption: Resources cannot be preempted; that is, a resource can
be released only voluntarily by the process holding it, after that process has
completed its task.
4. Circular wait: A set {P0, Pl, ... , Pn} of waiting processes must exist such
that Po is waiting for a resource held by P1, P1 is waiting for a resource held by
P2, ... , Pn1 is waiting for a resource held by Pn and Pn is waiting for a resource
e held by Po.

6. What is paging hardware with TLB? (Jan2023)

Hardware Support
Translation Look aside Buffer
• A special, small, fast lookup hardware cache, called a translation look-aside
buffer (TLB).

• Each entry in the TLB consists of two parts: a key (or tag) and a value. •
When the associative memory is presented with an item, the item is
compared with all keys simultaneously. If the item is found, the
corresponding value field is returned. The search is fast; the hardware,
however, is expensive. Typically, the number of entries in a TLB is small, often
numbering between 64 and 1,024.
• The TLB contains only a few of the page-table entries.

Working: • When a logical-address is generated by the CPU, its page-number is

presented to the TLB.
• If the page-number is found (TLB hit), its frame-number is immediately
available and used to access memory
• If page-number is not in TLB (TLB miss), a memory-reference to page table
must be made. The obtained frame-number can be used to access memory
(Figure 1)

• In addition, we add the page-number and frame-number to the TLB, so that

they will be found quickly on the next reference.
• If the TLB is already full of entries, the OS must select one for replacement.
• Percentage of times that a particular page-number is found in the TLB is
called hit ratio. Advantage: Search operation is fast. Disadvantage: Hardware
is expensive

• Some TLBs have wired down entries that can't be removed.

• Some TLBs store ASID (address-space identifier) in each entry of the TLB that
uniquely identify each process and provide address space protection for that
process.

[Link] structure of page table with respect to hierarchical paging.

(Jan2023)
Structure of the Page Table The most common techniques for structuring the
page table:
1. Hierarchical Paging
2. Hashed Page-tables
3. Inverted Page-tables
1. Hierarchical Paging
• Problem: Most computers support a large logical-address space (232 to 264).
In these systems, the page-table itself becomes excessively large.
Solution: Divide the page-table into smaller pieces.
Two Level Paging Algorithm:
• The page-table itself is also paged.
• This is also known as a forward-mapped page-table because address
translation works from the outer page-table inwards.

For example: Consider the system with a 32-bit logical-address space and a
pagesize of 4 KB. A logical-address is divided into → 20-bit page-number and →
12-bit page-offset. Since the page-table is paged, the page-number is further
divided into → 10-bit page-number and → 10-bit page-offset. Thus, a
logicaladdress is as follows:

• where p1 is an index into the outer page table, and p2 is the displacement
within the page of the inner page table The address-translation method for
 this architecture is shown in below figure. Because address translation works
from the outer page table inward, this scheme is also known as a forward-
mapped page table.

[Link] the process of segmentation. (Jan2023)

Segmentation is the process of dividing the main memory into different

segments (parts) based on the logical division of a program such as
functions, data, stack, etc.

Each segment is of different size and represents a logical unit of the program.

Process of Segmentation:

1. Program Division:
a. A program is divided into smaller logical segments like:
i. Code segment (instructions) ii. Data segment (variables)
iii. Stack segment (function calls, return addresses) iv. Heap
segment (dynamic memory)
2. Assign Segment Numbers:
a. Each segment is given a unique segment number (ID).
3. Create Segment Table:
a. The Operating System maintains a segment table for each
process.
b. The table contains:
 i. Base address: Starting address of the segment in physical
memory
ii. Limit: Length (size) of the segment
4. Logical to Physical Address Translation:
a. The CPU generates a logical address consisting of:

<Segment Number, Offset>

b. The segment number is used to find the base address from the
segment table.
c. The offset is added to the base address to get the physical
address.
5. Access the Segment:
a. Once the physical address is obtained, the memory location is
accessed for reading or writing data.

Example:

Suppose:

• Segment table entry for Segment 2 → Base = 5000, Limit = 1000

• Logical address = (2, 200) Then:

Physical address = Base + Offset = 5000 + 200 = 5200

Advantages:

• Logical view of memory (programmer-friendly)

• Supports code sharing and protection
• Easy to grow or shrink segments dynamically

Disadvantages:

• External fragmentation
• Complex memory management compared to paging
9. Explain in detail how deadlock can be prevented. (June2023)

Deadlock can be prevented by ensuring that at least one of the four necessary
conditions cannot hold.
Mutual Exclusion :

• The mutual-exclusion condition must hold for non-sharable

resources. Sharable resources, do not require mutually exclusive
access and thus cannot be involved in a deadlock.
• Ex: Read-only files are example of a sharable resource. If several
processes attempt to open a read-only file at the same time, they can
be granted simultaneous access to the file. A process never needs to
wait for a sharable resource.
• Deadlocks cannot prevent by denying the mutual-exclusion condition,
because some resources are intrinsically non-sharable.
Hold and Wait :
To ensure that the hold-and-wait condition never occurs in the system,
then guarantee that, whenever a process requests a resource, it does not hold
any other resources.
• One protocol that can be used requires each process to request and
be allocated all its resources before it begins execution.
• Another protocol allows a process to request resources only when it
has none. A process may request some resources and use them.
Before it can request any additional resources, it must release all the
resources that it is currently allocated.
Ex:

• Consider a process that copies data from a DVD drive to a file on disk,
sorts the file, and then prints the results to a printer. If all resources
must be requested at the beginning of the process, then the process
must initially request the DVD drive, disk file, and printer. It will hold
 the printer for its entire execution, even though it needs the printer
only at the end.
• The second method allows the process to request initially only the
DVD drive and disk file. It copies from the DVD drive to the disk and
then releases both the DVD drive and the disk file. The process must
then again request the disk file and the printer. After copying the disk
file to the printer, it releases these two resources and terminates.
The two main disadvantages of these protocols:
1. Resource utilization may be low, since resources may be allocated
but unused for a long period.
2. Starvation is possible.

No Preemption :
The third necessary condition for deadlocks is that there be no
preemption of resources that have already been allocated.
To ensure that this condition does not hold, the following protocols can be
used:
• If a process is holding some resources and requests another resource
that cannot be immediately allocated to it, then all resources the
process is currently holding are preempted.
• The preempted resources are added to the list of resources for which
the process is waiting. The process will be restarted only when it can
regain its old resources, as well as the new ones that it is requesting.
If a process requests some resources, first check whether they are available. If
they are, allocate them.
If they are not available, check whether they are allocated to some other
process that is waiting for additional resources. If so, preempt the desired
resources from the waiting process and allocate them to the requesting
process.
If the resources are neither available nor held by a waiting process, the
requesting process must wait. While it is waiting, some of its resources may be
preempted, but only if another process requests them.
A process can be restarted only when it is allocated the new resources it is
requesting and recovers any resources that were preempted while it was
waiting.

Circular Wait:
One way to ensure that this condition never holds is to impose a total ordering
of all resource types and to require that each process requests resources in an
increasing order of enumeration.
To illustrate, let R = {R1, R2, ... , Rm} be the set of resource types. Assign a
unique integer number to each resource type, which allows to compare two
resources and to determine whether one precedes another in ordering.
Formally, it defined as a one-to-one function F: R ->N, where N is the set of
natural numbers.
Example: if the set of resource types R includes tape drives, disk drives, and
printers, then the function F might be defined as follows:
F (tape drive) = 1
F (disk drive) = 5
F (printer) = 12
Now consider the following protocol to prevent deadlocks. Each process can
request resources only in an increasing order of enumeration. That is, a process
can initially request any number of instances of a resource type Ri. After that,
the process can request instances of resource type Rj if and only if F(Rj) > F(Ri).

10. What is paging? Illustrate with example internal and external

fragmentation problem encountered in contiguous memory allocation.
(June2023, Mar2022)
Paging is a memory management technique used by the operating system to
divide physical memory into fixed-size blocks called frames, and divide logical
memory (process) into blocks of the same size called pages.

It helps in avoiding external fragmentation and allows processes to use

noncontiguous memory.

Two types of memory fragmentation:

1. Internal fragmentation
2. External fragmentation
1. Internal Fragmentation :

• The general approach is to break the physical-memory into fixedsized

blocks and allocate memory in units based on block size.
• The allocated-memory to a process may be slightly larger than the
requested-memory.
• The difference between requested-memory and allocated-memory is
called internal fragmentation i.e. Unused memory that is internal to a
partition.

2. External Fragmentation :

• External fragmentation occurs when there is enough total memoryspace

to satisfy a request but the available-spaces are not contiguous. (i.e.
storage is fragmented into a large number of small holes).
• Both the first-fit and best-fit strategies for memory-allocation suffer from
external fragmentation.
• Statistical analysis of first-fit reveals that given N allocated blocks,
another 0.5 N blocks will be lost to fragmentation. This property is
known as the 50-percent rule.

Two solutions to external fragmentation:

 • Compaction: The goal is to shuffle the memory-contents to place all free
memory together in one large hole. Compaction is possible only if
relocation is dynamic and done at execution-time
• Permit the logical-address space of the processes to be noncontiguous.
This allows a process to be allocated physical-memory wherever such
memory is available. Two techniques achieve this solution: 1) Paging and
2) Segmentation

11. Explain the three methods of memory allocation. With a neat diagram
explain in the hardware support for relocation and limit register. (June2023)

Two types of memory partitioning are:

1. Fixed-sized partitioning

2. Variable-sized partitioning

1. Fixed-sized Partitioning :

• The memory is divided into fixed-sized partitions.

• Each partition may contain exactly one process.
• The degree of multiprogramming is bound by the number of partitions.
• When a partition is free, a process is selected from the input queue and
loaded into the free partition.
• When the process terminates, the partition becomes available for
another process.

2. Variable-sized Partitioning :

• The OS keeps a table indicating which parts of memory are available and
which parts are occupied.
• A hole is a block of available memory. Normally, memory contains a set
of holes of various sizes.
• Initially, all memory is available for user-processes and considered one
large hole.
• When a process arrives, the process is allocated memory from a large
hole.
• If we find the hole, we allocate only as much memory as is needed and
keep the remaining memory available to satisfy future requests.

Memory Mapping and Protection

• Memory-protection means protecting OS from user-process and

protecting user- processes from one another.
• Memory-protection is done using o Relocation-register: contains the
value of the smallest physicaladdress. o Limit-register: contains the
range of logical-addresses.
• Each logical-address must be less than the limit-register.
• The MMU maps the logical-address dynamically by adding the value in
the relocation- register. This mapped-address is sent to memory
• When the CPU scheduler selects a process for execution, the dispatcher
loads the relocation and limit-registers with the correct values.
• Because every address generated by the CPU is checked against these
registers, we can protect the OS from the running-process.
• The relocation-register scheme provides an effective way to allow the
OS size to change dynamically.
• Transient OS code: Code that comes & goes as needed to save
memoryspace and overhead for unnecessary swapping.
12. What is segmentation? Explain with a neat diagram. (June2023)

Segmentation is an OS memory management technique that divides a program

into logical, variable-sized partitions called segments, such as code, data, and
stack, to organize memory more efficiently and reflect the program's structure.
Each segment is handled separately and can be given different access rights, while
the OS uses a segment table to map the logical address (segment number and
offset) to the physical address

Basic Method of Segmentation

This is a memory-management scheme that supports user-view of memory

(Figure 1).

• A logical-address space is a collection of segments.

• Each segment has a name and a length.

• The addresses specify both segment-name and offset within the segment.

• Normally, the user-program is compiled, and the compiler automatically

constructs

• segments reflecting the input program. For ex: The code, Global variables, The
heap, from which memory is allocated

•The stacks used by each thread, The standard C library

Hardware support for Segmentation

•Segment-table maps 2 dimensional user-defined addresses into

onedimensional physical addresses.

• In the segment-table, each entry has following 2 fields:

1. Segment-base contains starting physical-address where the segment resides
in memory.

2. Segment-limit specifies the length of the segment (Figure 2).

•A logical-address consists of 2 parts:

1. Segment-number(s) is used as an index to the segment-table

2. Offset(d) must be between 0 and the segment-limit.

•If offset is not between 0 & segment-limit, then we trap to the OS

(logicaladdressing attempt beyond end of segment).

•If offset is legal, then it is added to the segment-base to produce the

physical-memory address.
13. Describe the resource allocation graph (Mar2022)

i) With deadlock.

ii) With a cycle but no deadlock.

Deadlocks can be described in terms of a directed graph called System Resource

Allocation Graph

The graph consists of a set of vertices V and a set of edges E. The set of vertices V
is partitioned into two different types of nodes:

•P = {P1, P2, ...,Pn}, the set consisting of all the active processes in the system.

• R = {R1, R2, ..., Rm} the set consisting of all resource types in the system.
A directed edge from process Pi to resource type Rj is denoted by Pi → Rj it
signifies that process Pi has requested an instance of resource type Rj and is
currently waiting for that resource.
A directed edge from resource type Rj to process Pi is denoted by Rj → Pi it
signifies that an instance of resource type Rj has been allocated to process Pi.

• A directed edge Pi → Rj is called a Request Edge.

• A directed edge Rj → Pi is called an Assignment Edge.
Pictorially each process Pi as a circle and each resource type Rj as a rectangle.
Since resource type Rj may have more than one instance, each instance is
represented as a dot within the rectangle.

A request edge points to only the rectangle Rj, whereas an assignment edge must
also designate one of the dots in the rectangle.

When process Pi requests an instance of resource type Rj, a request edge is

inserted in the resource-allocation graph. When this request can be fulfilled, the
request edge is instantaneously transformed to an assignment edge. When the
process no longer needs access to the resource, it releases the resource; as a
result, the assignment edge is deleted.

The resource-allocation graph shown in Figure depicts the following situation.

The sets
P, K and E:

• P = {P1, P2, P3}

• R= {R1, R2, R3, R4}

• E = {Pl →Rl, P2 → R3, Rl → P2, R2 → P2, R2 → P1, R3 → P3 }
Resource instances:

• One instance of resource type R1

• Two instances of resource type R2

• One instance of resource type R3 • Three instances of resource type R4

Process states:

• Process P1 is holding an instance of resource type R2 and is waiting for an

instance of resource type R1.

• Process P2 is holding an instance of R1 and an instance of R2 and is waiting for

an instance of R3.

• Process P3 is holding an instance of R3•

i)If the graph does contain a cycle, then a deadlock may exist.

Suppose that process P3 requests an instance of resource type R2. Since no

resource instance is currently available, a request edge P3 → R2 is added to the
graph. At this point, two minimal cycles exist in the system:

1. P1 →R1 → P2 → R3 → P3 → R2→P
2. P2 →R3 → P3 → R2 → P2

Suppose that process P3 requests an instance of resource type R2. Since no

resource instance is currently available, a request edge P3 → R2 is added to
the graph. At this point, two minimal cycles exist in the system: 1. P1 →R1 →
P2 → R3 → P3 → R2→P1 2. P2 →R3 → P3 → R2 → P2

ii)Consider the resource-allocation graph in below Figure. In this example

also have a cycle: P1→R1→P3→R2→P1

However, there is no deadlock. Observe that process P4 may release its

instance of resource type R2. That resource can then be allocated to P3,
breaking the cycle.
14. What are Translation Loadaside Buffer (TLB)? Explain TLB in detail with a
simple paging system with a neat diagram.

Translation Look aside Buffer

• A special, small, fast lookup hardware cache, called a translation look-aside
buffer (TLB).
• Each entry in the TLB consists of two parts: a key (or tag) and a value.
• When the associative memory is presented with an item, the item is
compared with all keys simultaneously. If the item is found, the
corresponding value field is returned. The search is fast; the hardware,
however, is expensive. Typically, the number of entries in a TLB is small, often
numbering between 64 and 1,024.
• The TLB contains only a few of the page-table entries.
Working:
• When a logical-address is generated by the CPU, its page-number is
presented to the TLB.
• If the page-number is found (TLB hit), its frame-number is immediately
available and used to access memory
• If page-number is not in TLB (TLB miss), a memory-reference to page table
must be made. The obtained frame-number can be used to access memory
(Figure 1)
• In addition, we add the page-number and frame-number to the TLB, so that
they will be found quickly on the next reference.
• If the TLB is already full of entries, the OS must select one for replacement.
• Percentage of times that a particular page-number is found in the TLB is
called hit ratio.
Advantage: Search operation is fast.
Disadvantage: Hardware is expensive.
• Some TLBs have wired down entries that can't be removed.
• Some TLBs store ASID (address-space identifier) in each entry of the TLB that
uniquely identify each process and provide address space protection for that
process.

15. With the help of a neat diagram, explain the various steps of address
binding

• User programs typically refer to memory addresses with symbolic

names. These symbolic names must be mapped or bound to physical memory
addresses.
• Address binding of instructions to memory-addresses can happen at 3
different stages.
1. Compile Time - If it is known at compile time where a program will
reside in physical memory, then absolute code can be generated by the
compiler, containing actual physical addresses. However, if the load address
changes at some later time, then the program will have to be recompiled.

2. Load Time - If the location at which a program will be loaded is not

known at compile time, then the compiler must generate relocatable code,
which references addresses relative to the start of the program. If that starting
address changes, then the program must be reloaded but not recompiled.
3. Execution Time - If a program can be moved around in memory during
the course of its execution, then binding must be delayed until execution time

16. What is a semaphore? Discuss the solution to the classical dinning

philosopher Problem

• A semaphore is a synchronization tool is used solve various synchronization

problem and can be implemented efficiently

Dining-Philosophers Problem
Consider five philosophers who spend their lives thinking and eating. The
philosophers share a circular table surrounded by five chairs, each belonging to

one philosopher. In the center of the table is a bowl of rice, and the table is laid
with five single chopsticks.

A philosopher gets hungry and tries to pick up the two chopsticks that are
closest to her (the chopsticks that are between her and her left and right
neighbors). A philosopher may pick up only one chopstick at a time. When a
hungry philosopher has both her chopsticks at the same time, she eats
without releasing the chopsticks. When she is finished eating, she puts down
both chopsticks and starts thinking again. It is a simple representation of the
need to allocate several resources among several processes in a deadlock-
free and starvation-freemanner.

Solution: One simple solution is to represent each chopstick with a semaphore.

A philosopher tries to grab a chopstick by executing a wait() operation on that
semaphore. She releases her chopsticks by executing the signal() operation on
the appropriate semaphores. Thus, the shared data are semaphore
chopstick[5]; where all the elements of chopstick are initialized to 1. The
structure of philosopher is shown

Several possible remedies to the deadlock problem are replaced by:

• Allow at most four philosophers to be sitting simultaneously at the table.
• Allow a philosopher to pick up her chopstick only if both chop sticks are
available.
 • Use an asymmetric solution—that is, an odd-numbered philosopher picks up
first her left chopstick and then her right chopstick, whereas an even
numbered philosopher picks up her right chopstick and then her left
chopstick.

17. Consider the following snap-short of a system: (Dec2023)

Answer the following using Banker’s algorithm:

i) Is the system is safe state? If so give the safe sequence.

ii) If process P2 requests (0,1,1,3) resource can it be granted
immediately.
PROCESS ALLOCATION MAX AVAILABLE NEED TOTAL

A B C D A B C D A B C D A B C D A B C D

P0 2 0 0 1 4 2 1 2 3 3 2 1 2 2 1 1 12 12 8 10

P1 3 1 2 1 5 2 5 2 5 3 2 2 2 1 3 1

P2 2 1 0 3 2 3 1 6 6 6 3 4 0 2 1 3

P3 1 3 1 2 1 4 2 4 7 10 6 6 0 1 1 2

P4 1 4 3 2 3 6 6 5 9 11 6 9 2 2 3 3

12 12 8 10
 i)Yes , the system is safe
Safe sequence state < P0 , P3 , P4 , P2 , P1 >
ii) Applying resource request algorithm:
(i)Requesti <= Needi → <0 1 1 3> <= <0 2 1 3>
(ii) Requesti <= availablei → <0 1 1 3> <= <3 3 2 1> →False
Hence <0 1 1 3> cannot be granted immediately because request is not less
than available.
[Link] the following snapshot of system

iii) Find the need matrix and calculate safe sequence using banker’s
algorithm mention the above is safe or not safe. ii) If a request from
P1 arrives for (1,0,2) can the request be granted immediately?
(Jan2023, June2023, Dec2024)
Ans.
PROCESS ALLOCATION MAX AVAILABLE NEED TOTAL
A B C A B C A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2 7 4 3 10 5 7
P1 2 0 0 3 2 2 5 3 2 1 2 2
P2 3 0 2 9 0 2 7 4 3 6 0 0
P3 2 1 1 2 2 2 7 4 5 0 1 1
P4 0 0 2 4 3 3 7 5 5 4 3 1
10 5 7

1. Yes the system is safe

Safe sequence state < P1,P3,P4,P0,P2>
2. Applying resource request algorithm
i)Request <= need :
<1,0,2> <=<1,2,2>
ii)Request <= available
<1,0,2> <= <3,2,2>
iii)Available=Available– Request
<3,2,2> - <1,0,2> = <2,2,0>

Allocation = Allocation + Request

<2,0,0> + <1,0,2> = <3,0,2>

Need = Need – Request

<1,2,2> - <1,0,2> = <0,2,0>

PROCESS ALLOCATION MAX AVAILABLE NEED TOTAL

A B C A B C A B C A B C A B C
P0 0 1 0 7 5 3 2 2 0 7 4 3 10 4 7
P1 3 0 2 3 2 2 5 2 2 0 2 0
P2 3 0 2 9 0 2 7 3 3 6 0 0
P3 2 1 1 2 2 2 7 3 5 0 1 1
P4 0 0 2 4 3 3 10 3 7 4 3 1
10 4 7

Safe sequence state : <P1,P3,P4,P2,P0>

Therefore, if P1 requests <1,0,2> it can be granted immediately.