DON BOSCO INSTITUTE OF TECHNOLOGY

DEPARTMENT OF INFORMATION SCIENCE ENGINEERING

ASSIGNMENT 2
Course name: Operating Systems Course code: 21CS44

Semester: IV Date of Given:01-08-2023 Date of Submission:09-08-2023 Max marks: 10

Module -2 CO RBTL
1. What are Monitors? Explain dining Philosopher’s solution using monitor. CO2 L1
Answer. Written below
2. Illustrate how Reader’s-Writer’s problem can be solved by using CO2 L1
semaphores.
Answer.
Written below
3. Explain Critical section problem. What are the requirements that critical CO2 L2
section problem must satisfy.
Answer
Written below
4. What is Synchronization? Explain Synchronization Hardware. CO2 L1
Answer. Synchronization is the way by which processes that share the same
memory space are managed in an operating system

-based solutions such as Peterson's are not guaranteed to work

on modern computer architectures. Instead, we can generally state that
anysolution to the critical-section problem requires a simple tool-a lock.
uiring that critical regions be
protected by locks. That is, a process must acquire a lock before entering a
critical section; it releases the lock when it exits the critical section
 -section problem could be solved simply in a uniprocessor
environment if we could prevent interrupts from occurring while a shared
variable was being modified. In this manner, we could be sure that the
current sequence of instructions would be allowed to execute in order
without preemption.

environment.
terrupts on a multiprocessor can be time consuming, as the
message is passed to all the processors. This message passing delays entry
into each critical section, and system efficiency decreases.
ware
instructions such as TestAndSet () and Swap(), that allow us either to test
and modify the content of a word or to swap the contents of two words
automatically.
instruction can be defined as
booleanTestAndSet(boolean *target) {
booleanrv = *target;
*target = TRUE;
return rv
}
ion is that it is executed
atomically. Thus, if two TestAndSet () instructions are executed
simultaneously (each on a different CPU), they will be executed
sequentially in some arbitrary order.
we can
implement mutual exclusion by declaring a Boolean variable lock,
initialized to false. The structure of process Pi is

The Swap() instruction, in contrast to the TestAndSet () instruction,

operates on the contents of two words; it is defined as,
void Swap(boolean *a, boolean *b) {
boolean temp = *a;
*a = *b;
*b = temp;
}
Figure: The definition of the Swap () instruction
 al exclusion
can be provided as follows.
to false and
each process has a local Boolean variable key. The structure of process Pi
is shown below,

 The common data structures are,

boolean waiting[n];
boolean lock;
 These data structures are initialized to false.

 To prove that the mutual exclusion requirement is met, we note that

process Pi can enter its critical section only if either waiting [i] == false or
key == false. The value of key can become false only if the TestAndSet()
is executed. The first process to execute the TestAndSet () will find key==
false; all others must wait.
 The progress requirement is met, since a process exiting the critical
section either sets lock to false or sets waiting[j] to false. Both allow a
process that is waiting to enter its critical section to proceed.
  To prove that the bounded-waiting requirement is met, we note that,
when a process leaves its critical section, it scans the array waiting in the
cyclic ordering (i + 1, i+ 2, ...,n-1, 0, ..., i -1). It designates the first
process in this ordering that is in the entry section (waiting[j]==true) as
the next one to enter the critical section. Any process waiting to enter its
critical section will thus do so within n - 1 turns.
 Unfortunately for hardware designers, implementing atomic
TestAndSet() instructions on multiprocessors is not a trivial task.
5. Define a Process Synchronization? CO2 L1
Answer Written below
6. Explain the Peterson’s Solution Problem ? CO2 L2
Answer  Peterson’s solution is a classic software-based solution to the critical-
section problem.
 Because of the way modern computer architectures perform basic
machine-language instructions, such as load and store, there are no
guarantees that Peterson's solution will work correctly on such
architectures.
 Peterson's solution is restricted to two processes that alternate execution
between their critical sections and remainder sections.
 The processes are numbered P0and P1. For convenience, when
presenting Pi, we use Pj to denote the other process; that is, j equals 1-i.
 Peterson's solution requires the two processes to share two data items:
int turn;
boolean flag[2];
 The variable turn indicates whose turn it is to enter its critical section.
That is, if turn == i, then process Pi is allowed to execute in its critical
section.
 The flag array is used to indicate if a process is ready to enter its critical
section. For example, if flag [i] is true, this value indicates that Pi is ready
to enter its critical section.
 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
  We need to show that:
o Mutual exclusion is preserved.
o The progress requirement is satisfied.
o The bounded-waiting requirement is met.
 To prove property 1, we note that each P; enters its critical section only
if either flag [j] == false or turn == i. Also we note that, if both processes
can be executing in their critical sections at the same time, then flag [0]
== flag [1] ==true. Since the value of turn can be either 0 or 1
but cannot be both, p0 and p1 cannot execute there while loop
successfully. Hence one process enter the critical section other is waiting
in the while loop.
 To prove properties 2 and 3, we note that 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] to 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] to 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).
7. What are Semaphores? Explain the usage and implementation of CO2 L1
Semaphores.
 The hardware-based solutions to the critical-section problem are
Answer
complicated for application programmers to use. To overcome this
difficulty, we can use a synchronization tool called semaphore.
 A semaphore S is an integer variable that, apart from initialization, is
accessed only through two standard atomic operations: wait () or P( ) and
signal( ) or V( ).
 All modifications to the integer value of the semaphore in the wait ()
and signal() operations must be executed indivisibly. That is, when one
process modifies the semaphore value, no other process can
simultaneously modify that same semaphore value.
 In addition, in the case of wait (S), the testing of the integer value of S
(S <= 0), as well as its possible modification (S--), must be executed
without interruption.

Semaphores Usage
 Operating systems often distinguish between counting and binary
semaphores.
 The value of a counting semaphore can range over an unrestricted
domain.
 The value of a binary semaphore can range only between 0 and 1.  On
some systems, binary semaphores are known as mutex locks, as they are
locks that provide mutual exclusion.
 We can use binary semaphores to deal with the critical-section problem
£or multiple processes. Then processes share a semaphore, mutex,
initialized to 1.
 Each process Pi is organized as shown in Figure 3.14.

Semaphores Implementation
 The main disadvantage of the semaphore definition given here is that it
requires busy waiting. While a process is in its critical section, any other
process that tries to enter its critical section must loop continuously in the
entry code. This continual looping is clearly a problem in a real
multiprogramming system, where a single CPU is shared among many
processes. Busy waiting wastes CPU cycles that some other process might
be able to use productively. This type of semaphore is also called a
Spinlock.
 To overcome the need for busy waiting, we can modify the definition of
the wait() and signal() semaphore operations.
 When a process executes the wait () operation and finds that the
semaphore value is not positive, it must wait. However, rather than
engaging in busy waiting, the process can blockitself using block()
operation.
 A process that is blocked, waiting on a semaphore S, should be restarted
when some other process executes a signal() operation. The process is
restarted by a wakeup() operation, which changes the process from the
waiting state to the ready state.
 To implement semaphores under this definition, we define a semaphore
as a "C' struct:
typedef struct {
int value;
struct process *list;
} semaphore;
 Each semaphore has an integer value and a list of processes list. When a
process must wait on a semaphore, it is added to the list of processes.
 A signal() operation removes one process from the list of waiting
processes and awakens that process. The wait() semaphore operation can
now be defined as

 The block() operation suspends the process that invokes it. The
wakeup(P) operation resumes the execution of a blocked process P. These
two operations are provided by the operating system as basic system calls.
 Note that in this implementation, semaphore values may be negative,
although semaphore values are never negative under the classical
definition of semaphores with busy waiting. If a semaphore value is
negative, its magnitude is the number of processes waiting on that
semaphore. This fact results from switching the order of the decrement
and the test in the implementation of the wait () operation
8. Mention the different types of Classical Problems of Synchronization? CO2 L1
Answer The classical problems of Synchronization are:
1. Bounded Buffer (Producer Consumer) Problem
2. Readers writers problems
3. Dining Philosophers Problem
Module -3
9. What is deadlock? What are necessary conditions for deadlock? L1
Answer Definition of Deadlock: A set of processes is in a deadlocked state when
every process in the set is waiting for an event that can be caused only by
another process in the set.
Necessary Conditions for Deadlock (Deadlock Characterization)
All four conditions must hold for a deadlock to occur.

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 {P1, P2, ..., Pn} of waiting processes must exist
such that P0 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 P0.
11. Discuss the various approaches used for deadlock recovery. CO3 L1
Answer There are 2 approaches used for recovery from deadlock
1). Process Termination:-To eliminate deadlocks by aborting a process,
we 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 deadlock-detection algorithm must be invoked to determine
 whether any processes are still [Link] a process may not be
easy. If the process was in the midst of updating a file, terminating it will
leave that file in an incorrect state. Similarly, if the process was in the
midst of printing data on a printer, the system must reset the printer to a
correct state before printing the next job.
Many factors may affect which process is chosen for termination,
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? (for
example, whether the resources are simple to preempt)
4. How many more resources the process needs in order to complete?
5. How many processes will need to be terminated?
2). 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.
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?
12. What is resource Allocation Graph? Explain how it is very useful in CO3 L1
describing deadly embrace by considering an example.
Deadlocks can be described more precisely in terms of a directed graph
Answer
called a system resource-allocation graph. This 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: 1)
Active processes {P1, P2,….Pn} represented by circles and 2) resource
types represented by rectangle with dots representing number of instances.
The set of edges E is partitioned into two different types:
1) Allocation (Assignment) edge, a directed edge from resource type Rj

allocated to Process Pi.

2) Request edge, a directed edge from process Pi to resource type Rj that
equests an instance of resource type Rj.
Example: The sets P, R and E:
P == {P1, P2, P3}
R== {R1, R2, R3, R4}
E == {Pl->Rl, P2 ->R3, Rl->P2, R2->P2,R2->Pl, R3->P3}

o One instance of resource type R1

o Two instances of resource type R2
o One instance of resource type R3
o Three instances of resource type R4.
Process states:
o Process P1 is holding an instance of resource type R2 and is waiting
foran instance of resource type R1.
o Process P2 is holding an instance of R1 and an instance of R2 and
iswaiting for an instance of R3.
o Process P3 is holding an instance of R3.

Figure: Resource allocation graph

Given the definition of a resource-allocation graph, it can be shown that, if

the graph contains no cycles, then no process in the system is deadlocked.
If the graph does contain a cycle, then a deadlock may exist. If each
resource type has exactly one instance, then a cycle implies that a
deadlock has occurred. Each process involved in the cycle is deadlocked.
If each resource type has several instances, then a cycle does not
necessarily imply that a deadlock has occurred.
For example: Suppose that in figure 4.1 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:
P1R1P2R3P3R2P1
P2R3P3R2P2
 Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the
resource R3, which is held by process P3. Process P3 is waiting for either
process P1 or process P2 to release resource R2. In addition, process P1 is
waiting for process P2 to release resource R1.
-allocation graph in Figure. In this example,
we also have a cycle:
P1R1P3R2P1

Figure: Resource allocation graph with cycle and deadlock

Figure: Resource allocation graph with a cycle but no deadlock

13. Illustrate with example the internal and external fragmentation problem. CO3 L1
Answer As processes are loaded and removed from memory, the free memory
space is broken into little pieces.

to satisfy a request but the available spaces are not contiguous; storage is
fragmented into a large number of small holes.

process size, external fragmentation may be a minor or a major problem.

some
optimization, given N allocated blocks, another 0.5 N blocks will be lost
to fragmentation. That is, one-third of memory may be unusable! This
property is known as the 50-percent rule.

Example:-
 -partition allocation scheme with a hole of 18,464
bytes. Suppose that the next process requests 18,462 bytes. If we allocate
exactly the requested block, we are left with a hole of 2 bytes.

the hole itself. The general approach to avoiding this problem is to break
the physical memory into fixed-sized blocks and allocate memory in units
based on block size.

larger than the requested memory. The difference between these two
numbers is internal fragmentation that is unused memory that is internal to
a partition.

The goal is to shuffle the memory contents so as to place all free memory
together in one large block. Compaction is not always possible.
ossible solution to the external-fragmentation problem is to
permit the logical address space of the processes to be noncontiguous,
thus allowing a process to be allocated physical memory wherever such
memory is available.

14. What are the methods available for handling deadlocks? Explain Banker’s CO3 L1
algorithm.?
We can deal with the deadlock problem in one of three ways:
Answer 1. We can use a protocol to prevent or avoid deadlocks, ensuring that the
system will never enter a deadlocked state.
2. We can allow the system to enter a deadlocked state, detect it, and
recover.
3. We can ignore the problem altogether and pretend that deadlocks never
occur in the system.

Banker's Algorithm.
-allocation-graph algorithm is not applicable to a resource
allocation system with multiple instances of each resource type.
f
processes in the system and m is the number of resource types:
o Available. A vector of length m indicates the number of available
resources of each type. If Available[j] equals k, then k instances of
resource type Rj are available.
o Max. An n x m matrix defines the maximum demand of each process.
If Max[i] [j] equals k, then process Pi may request at most k instances of
resource type Rj.
o Allocation. An n x m matrix defines the number of resources of each
type currently allocated to each process. If Allocation[i][j] equals k, then
 process Pi is currently allocated k instances of resource type Rj.
o Need. An n x m matrix indicates the remaining resource need of each
process. If Need[i][j] equals k, then process Pi may need k more instances
of resource type Rj to complete its task.
Note that Need[i][j] =Max[i][j]- Allocation [i][j].
1. Safety Algorithm
Used to find whether the system is safe state or not.
1. Let Work and Finish be vectors of length m and n, respectively.
Initialize
Work= Available and finish[i] =false for i= 0, 1, ... ,n - 1.
2. Find an index i such that both
a. finish[i] = = false
b. Needi <= Work
If no such i exists, go to step 4.
3. Work = Work + Allocation
Finish[i] = true
Go to step 2.
4. If Finish[i] ==true for all i, then the system is in a safe state.
2. Resource-Request Algorithm
Used to determine whether the requests can be safely granted.
1. If Requesti<= Needi, go to step 2. Otherwise, raise an error
condition, since the process has exceeded its maximum claim.
2. If Requesti<=Available, go to step 3. Otherwise, Pi must wait, since
the resources are not available.
3. Have the system pretend to have allocated the requested resources to
process Pi by modifying the state as follows:
Available= Available- Requesti
Allocationi =Allocationi + Requesti
Needi =Needi - Requesti
If the resulting resource-allocation state is safe, the transaction is
completed, and process Pi is allocated its resources. However, if the new
state is unsafe, then Pi must wait for Requesti, and the old resource-
allocation state is restored.
15 Describe the Segmentation technique. CO3 L1
Answer. -management scheme that supports this user
view of memory.
lection of segments.
y both the
segment name and the offset within the segment.
The user therefore specifies each address by two quantities: a segment
name and an offset.
ith the paging scheme, in which the user
specifies only a single address, which is partitioned by the hardware into a
page number and an offset, all invisible to the programmer.)

referred to by a segment number, rather than by a segment name.

< segment-number,
offset >.
-
dimensional address, the actual physical memory is still, of course, a one-
dimensional sequence of bytes.
the segment
table has a segment base and a segment limit.

segment resides in memory,

whereas the segment limit specifies the length of the segment.
ble is illustrated in Figure. A logical address
consists of two parts: a segment number, s, and an offset into that
segment, d.

nt
limit. If it is not, we trap to the operating system. When an offset is legal,
it is added to the segment base to produce the address in physical memory
of the desired byte.
he situation shown in Figure.

Figure: Segmentation Hardware

 Figure: Example of Segmentation

For example, segment 2 is 400 bytes long and begins at location 4300.
Thus, a reference to byte 53 of segment 2 is mapped onto location 4300 +
53 = 4353.

segment 3) + 852 = 4052.

A reference to byte 1222 of segment 0 would result in a trap to the
operating system, as this segment is only 1,000 bytes long.
16. What is Paging? Explain the Structure of Page Table. CO3 L1
Answer Paging is a memory-management scheme that permits the physical
address space of a process to be noncontiguous.
-forward
methods
o Consider a 32-bit logical address space as on modern computers
o Page size of 4 KB (212)
o Page table would have 1 million entries (232 / 212)
o If each entry is 4 bytes  4 MB of physical address space memory
for page table alone

thods of representing Page Table

1. Hierarchical Paging
2. Hashed Page Tables
3. Inverted Page Tables
1 Hierarchical Paging
o Break up the logical address space into multiple page tables
o A simple technique is a two-level page table
o We then page the page table

Figure:A two level page table scheme

-bit machine with 1K page size) is divided into:
o a page number consisting of 22 bits
o a page offset consisting of 10 bits

o a 12-bit page number

o a 10-bit page offset
:

where p1 is an index into the outer page table, and p2 is thedisplacement

within the page of the outer page table Known as forward-mapped page
table
 Figure: Address Translation for two-level 32bit paging architecture

-level paging scheme not sufficient

o Then page table has 252 entries

o If two level scheme, inner page tables could be 210 4-byte entries
o Address would look like

o Outer page table has 242 entries or 244 bytes

o One solution is to add a 2nd outer page table
o But in the following example the 2nd outer page table is still 234 bytes
in size And possibly 4 memory access to get to one physical memory
location
17. What is Swapping? Does this increase OS overhead? Justify your answer. CO3 L1
Answer Swapping is a memory management method that temporarily swaps out
idle or blocked processes from main memory to secondary memory which
ensures proper memory utilisation

Figure: Swapping of two processes using a disk as a backing store.

store, and then brought back into memory for continued execution
o Total physical memory space of processes can exceed physical
memory
– fast disk large enough to accommodate copies of all
memory images for all users; must provide direct access to these memory
images
– swapping variant used for priority-based scheduling
 algorithms; lower-priority process is swapped out so higher-priority
process can be loaded and executed
e is directly
proportional to the amount of memory swapped
-to-run processes which have
memory images on disk
systems (i.e., UNIX,
Linux, and Windows)
18. What are Translation Load side Buffer(TLB)?Explain TLB in detail with CO3
a simple paging system with a neat diagram.
A Translation lookside Buffer (TLB) is a memory cache that stores recent
Answer
translations of virtual memory to physical address for faster retrieval.

les.
Most allocate a page table for each process.

the instruction counter) in the process control block.

table is
reasonably small (for example, 256 entries). Most contemporary
computers, however, allow the page table to be very large (for example, 1
million entries).
table
is not feasible. Rather, the page table is kept in main memory.

memory location. If we want to access location i, we must first index into

the page table.
frame
number, which is combined with the page offset to produce the actual
physical address.
eme, two memory accesses are needed to access a byte
(one for the page-table entry, one for the byte).
ll, fast
lookup hardware cache, called a translation look-aside buffer (TLB).
s used with page tables in the following way.
-table entries. When a logical
address is generated by the CPU, page number is first searched in TLB.
lable
and is used to access memory.
ss than 10 percent longer than it would if an
unmapped memory reference were used.
a memory
reference to the page table must be made.
 Figure: Paging hardware with TLB

nd in the
TLB is called the hit ratio.
-percent hit ratio means that we find the desired page number in
the TLB 80 percent of the time.
econds to
access memory, then a mapped-memory access takes 120 nanoseconds
when the page number is in the TLB.
nds), then
we must first access memory for the page table and frame number (100
nanoseconds) and then access the desired byte in memory (100
nanoseconds), for a total of 220 nanoseconds.
-access time, we weight each case by its
probability:
Effective access time = 0.80 * 120 + 0.20 * 220 = 140 nanoseconds.
-percent slowdown in memory-access
time (from 100 to 140 nanoseconds).
-percent hit ratio,
we have effective access time = 0.98 * 120 + 0.02 * 220 = 122
nanoseconds
19. Write a note on Contiguous memory allocation. CO3
Answer Contiguous Memory allocation
.1. Memory Mapping and Protection

o Resident operating system, usually held in low memory with

interrupt vector
o User processes then held in high memory
o Each process contained in single contiguous section of memory
m each other,
and from changing operating-system code and data
s value of smallest physical address
– each logical
address must be less than the limit register

relocation register.
ss is sent to memory

Figure: Hardware support for relocation and limit registers

. Memory Allocation

memory into several fixedsized partitions (MFT-Multiprogramming with

fixed number of partitions).
ontain exactly one process. Thus, the degree of
multiprogramming is bound by the number of partitions.

selected from the input queue and is loaded into the free partition.
e process terminates, the partition becomes available for
another process.
-partition scheme called MVT
(Multiprogramming with variable number of partitions).
le
indicating which parts of memory are available and which are occupied.

one large block of available memory a hole.

each process and the
amount of available memory space in determining which processes are
allocated memory.

then compete for CPU

time.
ng
system may then fill
with another process from the input queue.
orst fit
strategies are used to select the free hole for the new process.
o First fit. Allocate the first hole that is big enough. Searching can start
either at the beginning of the set of holes or at the location where the
previous first-fit search ended. We can stop searching as soon as we find a
free hole that is large enough.
o Best fit. Allocate the smallest hole that is big enough. We must search
the entire list, unless the list is ordered by size. This strategy produces the
smallest leftover hole.
o Worst fit. Allocate the largest hole. Again, we must search the entire
list, unless it is sorted by size. This strategy produces the largest leftover
hole, which may be more useful than the smaller leftover hole from a best-
fit approach.