BCS303 OS - Module III Notes

OperatingSystems BCS303
HKBK College of Engineering

Department of Computer Science and Engineering
SEMESTER–3
OperatingSystems–BCS303
Module III
Deadlocks:
 Deadlocks;Systemmodel;
 Deadlockcharacterization;
 Methodsforhandlingdeadlocks;
 Deadlockprevention;
 Deadlockavoidance;Deadlockdetectionandrecoveryfromdeadlock.
MemoryManagement:
 Memorymanagementstrategies:
 Background;
 Swapping;
 Contiguousmemoryallocation;
 Paging;
 Structureofpagetable;
 Segmentation.
1 CSE/HKBKCE
MODULE3
DEADLOCKS
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.
SYSTEMMODEL
 A system consists of a finite number of resources to be distributed among a number of

competing processes. The resources are partitioned into several types, each consisting of
some number of identical instances. Memory space, CPU cycles, files, and I/0 devices
are examples of resource types.
 A process must request a resource before using it and must release the resource after
using it. A process may request as many resources as it requires carrying out its
designated task. The number of resources requested may not exceed the total number of
resources available in the system.
Underthenormalmodeofoperation,aprocessmayutilizearesourceinonlythefollowing sequence:
1. Request:Theprocessrequeststheresource.Iftherequestcannotbegranted
immediately,thentherequestingprocessmustwaituntilitcanacquiretheresource.
2. Use:Theprocesscanoperateontheresource.
3. Release:Theprocessreleasestheresource.
A set of processes is in a deadlocked state when everyprocess in the set is waiting for an event
that can be caused only by another process in the set. The events with which we are mainly
concerned here are resource acquisition and release. The resources may be either physical
resources or logical resources
Toillustrateadeadlockedstate,considerasystemwiththreeCDRWdrives.
SupposeeachofthreeprocessesholdsoneoftheseCDRWdrives.Ifeachprocess nowrequests another
drive, the three processes will be in a deadlocked state.
Eachiswaitingfortheevent"CDRWisreleased,"whichcanbecausedonlyby oneofthe other waiting
processes. This example illustrates a deadlock involving the same resource type.
2 CSE/HKBKCE
Deadlocks may also involve different resource types. For example, consider a system with one
printer and one DVD drive. Suppose that process Pi is holding the DVD and process P jis
holdingtheprinter. If Pirequests the printer andPj requests the DVD drive, adeadlock occurs.
DEADLOCK CHARACTERIZATION
NecessaryConditions
Adeadlocksituationcanariseifthefollowingfourconditionsholdsimultaneouslyinasystem:
1. Mutual exclusion: At least one resource must be held in a non-sharable mode, that is,
onlyone processata time canuse theresource. If another process requeststhatresource, 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. Nopreemption: Resourcescannotbepreempted;thatis,aresource canbereleasedonly

voluntarily bythe 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 Pois
waiting for a resource held by P1, P1is waiting for a resource held by P2, ... , Pn-1is
waitingforaresourceheldbyPnandPniswaitingforaresourceheldbyPo.
Resource-AllocationGraph
Deadlocks can be described in terms of a directed graph called System Resource-Allocation

Graph
ThegraphconsistsofasetofverticesVandasetofedgesE.ThesetofverticesVis partitioned into two

different types of nodes:
 P={P1,P2,...,Pn},the setconsistingofalltheactiveprocessesinthesystem.
 R={R1,R2,...,Rm}thesetconsistingofallresourcetypesinthesystem.
A directed edge from process P ito resource type Rjis denoted by Pi→ Rjit signifies that process
Pihas requested an instance of resource type Rjand is currently waiting for that resource.
A directed edge from resource type Rjto process Piis denoted by Rj→ Piit signifies that an
instance of resource type Rjhas been allocated to process Pi.
 AdirectededgePi→RjiscalledaRequestEdge.
 AdirectededgeRj→Pi is calledan AssignmentEdge.
3 CSE/HKBKCE
Pictorially each process Pias a circle and each resource type Rjas a rectangle. Since resource
type Rjmay have more than one instance, each instance is represented as a dot within the
rectangle.
A request edge points to onlythe rectangle Rj, whereas an assignment edge must also designate
one of the dots in the rectangle.
When process Pirequests an instance of resource type Rj,a request edge is inserted in the
resource-allocation graph. When this request can be fulfilled, the request edgeis instantaneously
transformed to an assignmentedge. When the process no longer needs access to the resource, it
releases the resource; as a result, the assignment edge is deleted.
Theresource-allocationgraphshowninFiguredepictsthefollowingsituation.
ThesetsP,KandE:
 P={P1,P2,P3}
 R={R1,R2,R3,R4}
 E={Pl→Rl,P2→R3,Rl→P2,R2→P2,R2→P1,R3→P3}
Resourceinstances:
 OneinstanceofresourcetypeR1
 Twoinstancesofresourcetype R2
 OneinstanceofresourcetypeR3
 ThreeinstancesofresourcetypeR4
Processstates:
 ProcessP1isholdinganinstanceof resourcetype R2andiswaitingforaninstanceof
resource type R1.
 ProcessP2isholdinganinstanceof R1andan instanceof R2andiswaitingforan instance
of R3.
 ProcessP3isholdinganinstanceofR3.
4 CSE/HKBKCE
Ifthegraphdoescontainacycle,thenadeadlockmayexist.
 If eachresourcetype hasexactlyoneinstance,thenacycleimpliesthatadeadlockhas
occurred. If the cycle involves only a set of resource types, each of which has only a
single instance, then a deadlock has occurred. Each process involved in the cycle is
deadlocked.
 If eachresourcetype has severalinstances,thenacycledoesnotnecessarilyimplythat a
deadlock has occurred. In this case, a cycle in the graph is a necessary but not a
sufficient condition for the existence of deadlock.
Toillustratethisconcept,theresource-allocationgraphdepictedinbelowfigure:
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
Figure:Resource-allocationgraphwithadeadlock.
Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is
heldbyprocessP3.ProcessP3 is waiting foreitherprocess P1or processP2 torelease resource R2.
In addition, process P1 is waiting for process P2 to release resource R1.
Considertheresource-allocationgraphinbelowFigure.Inthisexamplealsohaveacycle:
P1→R1→P3→R2→P1
Figure:Resource-allocationgraphwithacyclebutnodeadlock
5 CSE/HKBKCE
However,thereisnodeadlock.ObservethatprocessP4mayreleaseitsinstanceofresource type R2.

That resource can then be allocated to P3, breaking the cycle.
METHODSFORHANDLINGDEADLOCKS
Thedeadlockproblemcanbehandledinoneofthreeways:
1. Use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a
deadlocked state.
2. Allowthesystemtoenteradeadlockedstate, detectit,andrecover.
3. Ignoretheproblemaltogetherandpretendthatdeadlocksneveroccurinthesystem.
To ensure that deadlocks never occur, the system can use either deadlock prevention or a
deadlock-avoidance scheme.
Deadlock prevention provides a set of methods for ensuring that at least one of the necessary
conditions cannot hold. These methods prevent deadlocks by constraining how requests for
resources can be made.
Deadlock-avoidance requires that the operating system be given in advance additional

information concerning which resources a process will request and use during its lifetime. With
this additional knowledge, it can decide for each request whether or not the process shouldwait.
To decide whether the current requestcan be satisfied or must be delayed, the system must
consider the resources currently available, the resources currently allocated to each process, and
the future requests and releases of each process
If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm,

then a deadlock situation may arise. In this environment, the system can provide an algorithm
that examines the state of the system to determine whether a deadlock has occurred and an
algorithm to recover from the deadlock.
In the absence of algorithms to detect and recover from deadlocks, then the system is in a
deadlock state yet has no way of recognizing what has happened. In this case, the undetected
deadlock will result in deterioration of the system's performance, because resources are being
held byprocesses that cannot run and because more and more processes, as they make requests
for resources, will enter a deadlocked state. Eventually, the system will stop functioning and
will need to be restarted manually.
6 CSE/HKBKCE
DEADLOACKPREVENTION
Deadlockcanbepreventedbyensuringthatatleastoneofthefournecessaryconditionscannot hold.
MutualExclusion
 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.
HoldandWait
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 onlywhen it has none. A process
may request some resources and use them. Before it can request anyadditional resources,
it must release all the resources that it is currently allocated.
Ex:
 Consider a process that copies data froma 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 printerfor 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.
Thetwomaindisadvantagesoftheseprotocols:
1. Resourceutilization maybelow, sinceresources maybeallocated butunusedforalong
period.
2. Starvationispossible.
7 CSE/HKBKCE
NoPreemption
The third necessary condition for deadlocks is that there be no preemption of resources that
have already been allocated.
Toensurethatthisconditiondoesnothold,thefollowingprotocolscanbeused:
 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 wellas
the new ones that it is requesting.
If a process requests some resources, first check whether they are available. If theyare, 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 bya 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.
CircularWait
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 todetermine whether
one precedes another in ordering. Formally, it defined as a one-to-one function
F:R->N,whereNisthesetofnaturalnumbers.
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(tapedrive)=1
F(diskdrive)=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 instancesof aresourcetype -Ri. Afterthat, theprocess canrequest instances of resourcetype Rjif
and only if F(Rj) > F(Ri).
8 CSE/HKBKCE
DEADLOCKAVOIDANCE
 To avoid deadlocks an additional information is required about how resources are to be

requested. With the knowledge of the complete sequence of requests and releases for
each process, the system can decide for each request whether or not the process should
wait in order to avoid a possible future deadlock
 Each request requires that in making this decision the system consider the resources
currently available, the resources currently allocated to each process, and the future
requests and releases of each process.
 The various algorithms that use this approach differ in the amount and type of
information required. The simplest model requires that each process declare the
maximum number of resources of each type that it may need. Given this a priori
information, it is possible to construct an algorithm that ensures that the system will
never enter a deadlocked state. Such an algorithm defines the deadlock-avoidance
approach.
Safe State
 Safe state: A state is safe if the system can allocate resources to each process (up to its
maximum) in some order and still avoid a deadlock. A system is in a safe state only if
there exists a safe sequence.
 Safe sequence: A sequence of processes <P1, P2, ... , Pn> is a safe sequence for the
current allocation state if, for each Pi, the resource requests that Pi can still make can be
satisfied bythe currently available resources plus the resources held by all Pj, with j <i.
In this situation, if the resources that Pi needs are not immediately available, then Pi can wait
until all Pj have finished. When they have finished, Pi can obtain all of its needed resources,
complete its designated task, return its allocated resources, and terminate. When Pi terminates,
Pi+1 can obtain its needed resources, and so on. Ifno such sequence exists, then the system state
is said to be unsafe.
A safe state is not a deadlocked state. Conversely, a deadlocked state is an unsafe state. Not all
unsafestatesaredeadlocksasshowninfigure.Anunsafestate mayleadtoadeadlock.Aslong as the
state is safe, the operating system can avoid unsafe states
9 CSE/HKBKCE
Figure:Safe,unsafe,anddeadlockedstatespaces.
Resource-Allocation-GraphAlgorithm
 Ifaresource-allocationsystemhasonlyoneinstanceofeachresource type,thena variant

of the resource-allocation graph is used for deadlock avoidance.
 Inadditiontotherequestandassignmentedges,anewtypeofedgeisintroduced,called a claim
edge.
 AclaimedgePi->RjindicatesthatprocessPi mayrequestresource Rjatsome timein the
future. This edge resembles a request edge in direction but is represented in the graph
by a dashed line.
 When process Pi requests resource Rj, the claim edge Pi ->Rj is converted to a request
edge. When aresource RjisreleasedbyPitheassignmentedgeRj->Piisreconvertedto a
claim edge Pi->Rj.
Figure:Resource-allocationgraphfordeadlockavoidance.
Notethattheresourcesmustbeclaimedaprioriinthesystem.Thatis,beforeprocessPistarts executing, all

its claim edges must already appear in the resource-allocation graph.
We canrelax thisconditionbyallowinga claimedgePi ->Rjto beaddedtothe graphonlyif all the
edges associated with process Pi are claim edges.
Now suppose that process Pi requests resource Rj. The request can be granted only if
convertingtherequestedgePi->RjtoanassignmentedgeRj->Pidoesnotresultinthe formation of a
cycle in the resource-allocation graph.
10 CSE/HKBKCE
There is need to check for safety by using a cycle-detection algorithm. An algorithm for
detecting a cycle in this graph requires an order of n2 operations, where n is the number of
processes in the system.
 Ifnocycleexists,thentheallocationoftheresourcewillleavethesysteminasafestate.
 If a cycleis found,thenthe allocationwillputthe systemin an unsafe state. In thatcase,
process Pi will have to wait for its requests to be satisfied.
To illustrate this algorithm, consider the resource-allocation graph as shown above. Suppose
that P2 requests R2. Although R2 is currently free, we cannot allocate it to P2, since this action
will create a cycle in the graph.
A cycle, indicates that the system is in an unsafe state. If P1 requests R2, and P2 requests R1,
then a deadlock will occur.
Figure:Anunsafestateinaresource-allocationgraph
Banker'sAlgorithm
The Banker’s algorithm is applicable to a resource allocation system with multiple instances of
each resource type.
 When a new process enters the system, it must declare the maximum numberof instances
of each resource type that it may need. This number may not exceed the total number of
resources in the system.
 When a user requests a set of resources, the system must determine whether the
allocation of these resources will leave the system in a safe state. If it will, the resources
are allocated; otherwise, the process must wait until some other process releases enough
resources.
11 CSE/HKBKCE
Toimplementthebanker'salgorithmthefollowingdatastructuresareused. Let n =
number of processes, and m = number of resources types
Available:Avectoroflengthmindicatesthenumberofavailableresourcesofeachtype.If available [j] =

k, there are k instances of resource type Rj available.
Max:Annx mmatrix definesthe maximumdemandof eachprocess. If Max[i,j]=k, thenprocess Pi

mayrequest at most k instances of resource type Rj
Allocation:Annxmmatrixdefinesthenumberof resourcesof eachtypecurrentlyallocated toeach

process. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj
Need:Annxmmatrixindicatestheremainingresourceneedofeachprocess.IfNeed[i,j]=k, then Pi may

need k more instances of Rj to complete its task.
Need[i,j]=Max[i,j]–Allocation[i,j]
SafetyAlgorithm
Thealgorithmforfindingoutwhetherornota systemis inasafestate.Thisalgorithmcanbe described as

follows:
1. LetWorkandFinishbevectorsoflengthmandn,respectively. Initialize: Work

= Available
Finish[i]=falsefori=0,1,…,n-1
2. Findanindexisuchthatboth:
(a) Finish[i]=false
(b) NeediWork
Ifnosuchiexists,gotostep4
3. Work=Work+Allocationi
Finish[i]=true go
to step 2
4. IfFinish[i]==trueforalli,thenthesystemisinasafestate
Thisalgorithmmayrequireanorderofmxn2operationstodeterminewhetherastateissafe.
12 CSE/HKBKCE
Resource-RequestAlgorithm
Thealgorithmfordeterminingwhetherrequestscanbesafelygranted.
Let Requestibe the request vector for process Pi. If Requesti[j] == k, then process Piwants k
instancesof resource typeRj.Whenarequestforresources ismade byprocessPi,thefollowing actions
are taken:
1. IfRequestiNeedigotostep2.Otherwise,raiseerrorcondition,sinceprocesshasexceeded its
maximum claim
2. IfRequestiAvailable,gotostep3.OtherwisePimustwait,sinceresourcesarenotavailable
3. HavethesystempretendtoallocaterequestedresourcestoPibymodifyingthestateas follows:
Available = Available – Request;
Allocationi= Allocationi+
Requesti;Needi=Needi–Requesti;
Ifsafetheresourcesareallocatedto Pi
IfunsafePimustwait,andtheoldresource-allocationstateisrestored
Example
ConsiderasystemwithfiveprocessesPothroughP4andthreeresourcetypesA,B,andC.
ResourcetypeAhasteninstances, resource typeBhasfiveinstances, andresourcetypeC
hasseveninstances.Suppose that,attime T0thefollowingsnapshot of the systemhasbeen taken:
13 CSE/HKBKCE
ThecontentofthematrixNeedisdefinedtobeMax-Allocation
Thesystemiscurrentlyinasafestate.Indeed, thesequence <P1,P3,P4,P2,P0>satisfiesthe safety

criteria.
Supposenowthat processP1requestsoneadditionalinstanceofresourcetypeAandtwo instances of

resource type C, so Request1= (1,0,2). Decide whether this request can be immediately granted.
CheckthatRequestAvailable
(1,0,2)(3,3,2)true
Thenpretendthatthisrequesthasbeenfulfilled,andthefollowingnewstateisarrived.
Executingsafetyalgorithmshowsthatsequence<P1,P3,P4,P0,P2>satisfiessafety requirement.
14 CSE/HKBKCE
DEADLOCKDETECTION
If a system does not employ either a deadlock-prevention or a deadlock avoidance
algorithm,then a deadlock situation may occur. In this environment, the system may provide:
 An algorithm that examines the state of the system to determine whether a deadlock has
occurred
 Analgorithmtorecoverfromthedeadlock
SingleInstanceofEachResourceType
 If all resources have only a single instance, then define a deadlock detection algorithm
that uses a variant of the resource-allocation graph, called a wait-for graph.
 This graph is obtained from the resource-allocation graph by removing the resource
nodes and collapsing the appropriate edges.
 An edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj
toreleasearesourcethatPineeds.AnedgePi→Pjexistsinawait-forgraphifandonly ifthe
corresponding resource allocation graph containstwo edges Pi→Rqand Rq→Pifor some
resource Rq.
Example: In below Figure, a resource-allocation graph and the corresponding wait-for graph is
presented.
Figure:(a)Resource-allocationgraph.(b)Correspondingwait-forgraph.
 Adeadlockexistsinthesystemifandonlyifthewait-forgraphcontainsacycle. To detect
deadlocks, the system needs to maintain the wait-for graph and periodically invoke
an algorithm that searches for a cycle in the graph.
 Analgorithmtodetectacycleinagraphrequiresanorderof n2operations,wherenis the
number of vertices in the graph.
15 CSE/HKBKCE
SeveralInstancesofaResourceType
Adeadlockdetectionalgorithmthatis applicabletoseveralinstances of aresourcetype.The algorithm

employs several time-varying data structures that are similar to those used in the banker's
algorithm.
 Available:Avectoroflengthmindicatesthenumberofavailableresourcesof
eachtype.
 Allocation:Annx mmatrixdefinesthenumberofresourcesofeachtype
currentlyallocated to each process.
 Request:Annxmmatrixindicatesthecurrentrequestofeachprocess.If Request[i][j] equals
k, then process P; is requesting k more instances of resource type Rj.
Algorithm:
1. LetWorkandFinishbevectorsoflengthmandn,respectivelyInitialize:
(a) Work=Available
(b) Fori=1,2, …,n,ifAllocationi0,thenFinish[i]=false;
otherwise, Finish[i] = true
2. Findanindexisuchthatboth:
(a) Finish[i]==false
(b)RequestiWork
Ifnosuchiexists,gotostep4
3. Work=Work+Allocationi
Finish[i]=true go
to step 2
4. If Finish[i]==false,forsomei,1in,thenthesystemisindeadlockstate.Moreover,if Finish[i]
== false, then Piis deadlocked
AlgorithmrequiresanorderofO(mxn2)operationstodetect whetherthesystemisin deadlocked

state
ExampleofDetectionAlgorithm
Considera systemwithfiveprocessesPothroughP4andthreeresourcetypesA, B,andC.

ResourcetypeA hasseveninstances,resource typeBhas twoinstances,andresourcetype Chas
six instances. Suppose that, at time T0, the following resource-allocation state:
16 CSE/HKBKCE
Afterexecutingthealgorithm,Sequence<P0,P2,P3,P1,P4>willresultinFinish[i]=truefor all i
SupposenowthatprocessP2makesoneadditionalrequestforaninstanceof type C.The Request
matrix is modified as follows:
Thesystemisnowdeadlocked.Althoughwe canreclaimtheresourcesheldbyprocess Po,the number of

available resources is not sufficient to fulfill the requests of the other processes.
Thus,adeadlockexists,consistingofprocessesP1,P2,P3,andP4.
Detection-AlgorithmUsage
Thedetectionalgorithmcanbeinvokedontwofactors:
1. Howoftenisadeadlocklikelytooccur?
2. Howmanyprocesseswillbeaffectedbydeadlockwhenit happens?
Ifdeadlocksoccurfrequently,thenthedetectionalgorithmshouldbeinvokedfrequently.Resources
allocated to deadlocked processes will be idle until the deadlock can be broken.
If detection algorithm is invoked arbitrarily, there may bemany cycles in the resource graph and
so we would not be able to tell which of the many deadlocked processes “caused” the deadlock.
17 CSE/HKBKCE
RECOVERYFROMDEADLOCK
The system recovers from the deadlock automatically. There are two options for breaking a
deadlockoneissimplytoabortone or moreprocessesto breakthe circularwait.Theother isto preempt
some resources from one or more of the deadlocked processes.
ProcessTermination
Toeliminatedeadlocksbyabortingaprocess, useoneoftwomethods.Inbothmethods,the system
reclaims all resources allocated to the terminated processes.
1. Abortalldeadlockedprocesses: Thismethodclearlywillbreakthedeadlockcycle,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
incursconsiderableoverhead,sinceaftereachprocessisaborted,adeadlock-detection
algorithm must be invoked to determine whether any processes are still deadlocked.
Ifthepartialterminationmethodisused,thenwemustdeterminewhichdeadlockedprocess(or processes)
should be terminated. Manyfactors may affect which process is chosen, including:
1. Whatthepriorityoftheprocess is
2. Howlongtheprocesshascomputedandhowmuchlongertheprocess willcompute before
completing its designated task
3. Howmanyandwhattypesof resourcestheprocesshasused.
4. Howmanymoreresourcestheprocessneedsinordertocomplete
5. Howmanyprocesses willneedtobeterminated?
6. Whethertheprocessisinteractiveorbatch
ResourcePreemption
To eliminatedeadlocksusingresourcepreemption,wesuccessively preemptsome resources from

processes and give these resources to other processes until the deadlock cycle is broken.
Ifpreemptionisrequiredtodealwithdeadlocks,thenthreeissuesneedtobeaddressed:
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,itcannotcontinue withits normalexecution;itis missingsomeneeded
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.
18 CSE/HKBKCE
3. Starvation.Howdoweensurethatstarvationwillnotoccur?Thatis,howcanwe guarantee that

resources will not always be preempted from the same process?
19 CSE/HKBKCE
MEMORYMANAGEMENT
MainMemoryManagementStrategies
 Every program to be executed has to be executed must be in memory. The instruction

must be fetched from memory before it is executed.
 Inmulti-taskingOS memorymanagementiscomplex,becauseas processesare swapped in
and out of the CPU, their code and data must be swapped in and out of memory.
BasicHardware
 Main memory, cache and CPU registers in the processors are the only storagespacesthat
CPU can access directly.
 The program and data must be bought into the memory from the disk, for the process to
run. Each process has a separate memory space and must access only this range of legal
addresses. Protection of memory is required to ensure correct operation. This prevention
is provided by hardware implementation.
 Two registers are used - a base register and a limit register. The base register holds the
smallest legal physical memoryaddress; the limit register specifies the size of the range.
 For example, The base register holds the smallest legal physical memory address; the
limit register specifies the size of the range. For example, if the base register holds
300040 and limit register is 120900, then the program can legally access all addresses
from 300040 through 420940 (inclusive).
Figure:Abaseandalimit-registerdefinealogical-addressspace
 The base and limit registers can be loaded only by the operating system, which uses a
special privileged instruction. Since privileged instructions can be executed only in
kernel mode only the operating system can load the base and limit registers.
20 CSE/HKBKCE
Figure:Hardwareaddressprotectionwithbaseandlimit-registers
AddressBinding
 Userprogramstypicallyrefertomemoryaddresseswith symbolicnames.Thesesymbolic
namesmustbemappedorboundtophysicalmemoryaddresses.
 Addressbindingofinstructionstomemory-addressescanhappenat3differentstages.
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, containingactualphysical
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. ExecutionTime - If a programcanbe moved around in memoryduringthecourse of its
execution, then binding must be delayed until execution time.
21 CSE/HKBKCE
Figure:Multistepprocessingofauserprogram
LogicalVersusPhysicalAddressSpace
 TheaddressgeneratedbytheCPUisalogicaladdress,whereasthememoryaddress where
programs are actually stored is a physical address.
 The set of all logical addresses used by a program composes the logical address
space,and the set of all corresponding physical addresses composes the physical address
space.
 Theruntimemappingoflogicaltophysicaladdressesishandledbythememory-management
unit (MMU).
 Oneofthesimplestisamodificationofthebase-registerscheme.
 Thebaseregisteristermedarelocationregister
 Thevalueintherelocation-registerisaddedtoevery addressgeneratedby a user-
process at the time it is sent to memory.
 The user-program deals with logical-addresses; it never sees the real physical-
addresses.
Figure:Dynamicrelocationusingarelocation-register
22 CSE/HKBKCE
DynamicLoading
 Thiscanbeusedtoobtainbettermemory-spaceutilization.
 Aroutineisnotloadeduntilitiscalled.
Thisworksasfollows:
1. Initially,allroutinesarekeptondiskinarelocatable-loadformat.
2. Firstly,the main-programisloadedintomemoryandisexecuted.
3. Whena main-programcallstheroutine,the main-programfirstcheckstoseewhetherthe
routine has been loaded.
4. Ifroutinehasbeennotyetloaded,theloaderiscalledtoloaddesiredroutineinto memory.
5. Finally,controlispassedtothenewlyloaded-routine.
Advantages:
1. Anunusedroutineisneverloaded.
2. Usefulwhenlargeamountsofcodeareneededtohandleinfrequentlyoccurringcases.
3. Althoughthetotalprogram-sizemaybelarge,theportionthatisused(andhenceloaded) may be
much smaller.
4. Doesnotrequirespecialsupportfromthe OS.
DynamicLinkingandSharedLibraries
 With static linking library modules get fully included in executable modules, wasting
both disk space and main memory usage, because every program that included a certain
routine from the library would have to have their own copy of that routine linked into
their executable code.
 With dynamic linking, however, only a stub is linked into the executable module,
containing references to the actual library module linked in at run time.
 Thestubisasmallpieceofcodeusedtolocatetheappropriatememory-resident library-
routine.
 Thismethodsaves diskspace,becausethelibraryroutinesdonotneedtobefully
included in the executable modules, only the stubs.
 An added benefit of dynamically linked libraries (DLLs, also known as shared
librariesorsharedobjectsonUNIXsystems)involveseasyupgradesandupdates.
Sharedlibraries
 A library may be replaced by a new version, and all programs that reference the library
will automatically use the new one.
 Version info. is included in both program & library so that programs won't accidentally
execute incompatible versions.
23 CSE/HKBKCE
Swapping
 Aprocessmustbeloadedintomemoryinordertoexecute.
 If there is not enough memory available to keep all running processes in memory at the
same time, then some processes that are not currently using the CPU may have their
memory swapped out to a fast local disk called the backing store.
 Swapping is the process of moving a process from memory to backing store and moving
another process from backing store to memory. Swapping is a very slow process
compared to other operations.
 A variant of swapping policy is used for priority-based scheduling algorithms. If a
higher-priorityprocess arrives and wants service, the memory manager can swap out the
lower-priority process and then load and execute the higher-priority process. When the
higher-priority process finishes, the lower-priority process can be swapped back in and
continued. This variant of swapping is called roll out, roll in.
Swappingdependsuponaddress-binding:
 Ifbindingisdoneatload-time,thenprocesscannotbeeasilymovedtoadifferent location.
 Ifbindingisdoneatexecution-time,thenaprocesscanbeswappedintoadifferent memory-
space, because the physical-addresses are computed during execution-time.
Major part of swap-time is transfer-time; i.e. total transfer-time is directly proportional to

theamount of memory swapped.
Disadvantages:
1. Context-switchtimeisfairlyhigh.
2. If wewanttoswap aprocess,we mustbesure thatitiscompletelyidle. Two
solutions:
i) NeverswapaprocesswithpendingI/O.
ii) ExecuteI/OoperationsonlyintoOSbuffers.
Figure:Swappingoftwoprocessesusingadiskasabackingstore
24 CSE/HKBKCE
Example:
Assumethattheuserprocess is10MBinsize andthebacking store isastandardhard diskwith a
transfer rate of 40 MB per second.
Theactualtransferofthe10-MBprocesstoorfrommainmemorytakes 10000
KB/40000 KB per second = 1/4 second
=250 milliseconds.
Assuming that no head seeks are necessary, and assuming an average latencyof 8 milliseconds,
the swap time is 258 milliseconds. Since we must both swap out and swap in, the total swap
time is about 516 milliseconds.
ContiguousMemoryAllocation
 The main memory must accommodate both the operating system and the various user
processes. Therefore we need to allocate the parts of the main memory in the most
efficient way possible.
 Memory is usually divided into 2 partitions: One for the resident OS. One for the user
processes.
 Eachprocessiscontainedinasinglecontiguoussectionofmemory.
1. MemoryMappingandProtection
 Memory-protectionmeansprotectingOSfromuser-processandprotectinguser-
processes from one another.
 Memory-protectionisdoneusing
o Relocation-register:containsthevalueofthesmallestphysical-address.
o Limit-register:containstherangeoflogical-addresses.
 Eachlogical-addressmustbelessthanthelimit-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 wayto allow the OS size to change
dynamically.
 TransientOScode:Codethatcomes&goesasneededtosavememory-spaceand overhead for
unnecessary swapping.
25 CSE/HKBKCE
Figure:Hardwaresupportforrelocationandlimit-registers
2. MemoryAllocation
Twotypesofmemorypartitioningare:
1. Fixed-sizedpartitioning
2. Variable-sizedpartitioning
1. Fixed-sizedPartitioning
 Thememoryisdividedintofixed-sizedpartitions.
 Eachpartitionmaycontainexactlyoneprocess.
 Thedegreeof multiprogrammingisboundbythenumberofpartitions.
 When a partition is free, a process is selected from the input queueand loaded into
thefree partition.
 Whentheprocessterminates,thepartitionbecomesavailableforanotherprocess.
2. Variable-sizedPartitioning
 TheOSkeeps atableindicatingwhich parts of memoryareavailable andwhichpartsare

occupied.
 Aholeisablockofavailablememory.Normally,memorycontainsasetofholesof various sizes.
 Initially,allmemoryisavailableforuser-processesandconsideredonelargehole.
 Whenaprocessarrives,theprocessisallocatedmemoryfromalargehole.
 Ifwefindthehole,weallocateonlyasmuchmemoryasisneededandkeepthe remaining
memory available to satisfy future requests.
26 CSE/HKBKCE
Threestrategiesusedtoselectafreeholefromthesetofavailableholes:
1. FirstFit:Allocatethefirstholethatisbigenough.Searchingcanstarteitheratthe beginning of
the set of holes or at the location where the previous first-fit search ended.
2. BestFit:Allocatethesmallestholethatisbigenough.Wemustsearchtheentirelist, unless the

list is ordered bysize. This strategy produces the smallest leftover hole.
3. WorstFit:Allocatethelargesthole.Again,wemustsearchtheentirelist,unlessitis sorted by
size. This strategy produces the largest leftover hole.
First-fitandbestfitarebetterthanworstfitintermsofdecreasingtimeandstorageutilization.
3. Fragmentation
Twotypesofmemoryfragmentation:
1. Internalfragmentation
2. Externalfragmentation
1. InternalFragmentation
 Thegeneralapproach isto breakthe physical-memoryintofixed-sizedblocks and
allocate memory in units based on block size.
 Theallocated-memorytoaprocessmaybeslightlylargerthantherequested-memory.
 The difference between requested-memory and allocated-memory is called internal
fragmentation i.e. Unused memory that is internal to a partition.
2. ExternalFragmentation
 External fragmentation occurs when there is enough total memory-space 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.
Twosolutionstoexternalfragmentation:
 Compaction: The goal is to shuffle the memory-contents to place all free memory
togetherinonelargehole.Compactionispossibleonlyif relocationisdynamicanddone at
execution-time
 Permit the logical-address space of the processes to be non-contiguous. This allows a
process to be allocated physical-memory wherever such memory is available. Two
techniques achieve this solution: 1) Paging and 2) Segmentation.
27 CSE/HKBKCE
Paging
 Pagingisamemory-managementscheme.
 Thispermitsthephysical-addressspaceofaprocesstobenon-contiguous.
 Thisalsosolvestheconsiderableproblemoffittingmemory-chunksofvaryingsizes onto the
backing-store.
 Traditionally:Supportforpaginghasbeenhandledbyhardware.
 Recentdesigns:Thehardware&OSarecloselyintegrated.
BasicMethodofPaging
 The basic method for implementing paging involves breaking physical memory into
fixed-sized blocks called frames and breaking logical memory into blocks of the same
size called pages.
 When a process is to be executed, its pages are loaded into anyavailable memoryframes
from the backing store.
 The backing store is divided into fixed-sized blocks that are of the same size as the
memory frames.
ThehardwaresupportforpagingisillustratedinFigure1.
Figure1:Paginghardware
 AddressgeneratedbyCPUisdividedinto2parts(Figure 2):
1. Page-number(p)isusedasanindextothepage-table.Thepage-tablecontainsthe base-
address of each page in physical-memory.
2. Offset (d) is combined with the base-address to define the physical-address. This
physical-address is sent to the memory-unit.
 Thepagetablemapsthepagenumbertoaframenumber,toyieldaphysicaladdress
 Thepagetablemapsthepagenumbertoaframenumber,toyieldaphysicaladdress which also
has two parts: The frame number and the offset within that frame.
 Thenumberofbitsintheframenumberdetermineshowmany framesthesystem can address,
and the number of bits in the offset determines the size of each frame.
28 CSE/HKBKCE
ThepagingmodelofmemoryisshowninFigure2.
Figure2:Pagingmodeloflogicalandphysicalmemory.
 Thepagesize(liketheframesize)isdefinedbythehardware.
 The size of a page is typically a power of 2, varying between 512 bytes and 16 MB per
page, depending on the computer architecture.
 The selection of a power of 2 as a page size makes the translation of a logical address
into a page number and page offset.
 If the size of logical address space is 2m and a page size is 2n addressing units (bytes or
words), then the high-order m – n bits of a logical address designate the page number,
and the n low-order bits designate the page offset.
Thus,thelogicaladdressisasfollows:
pagenumber pageoffset
p d
m-n n
 When a process requests memory(e.g. when its code is loaded in fromdisk), freeframes
are allocated from a free-frame list, and inserted into that process's page table.
 Processes are blocked from accessing anyone else's memorybecause all of their memory
requests are mapped through their page table. There is no way for them to generate an
address that maps into any other process's memory space.
 Theoperatingsystemmustkeep trackof eachindividualprocess's pagetable, updating it
whenever the process's pages get moved in and out of memory, and applying the correct
page table when processing system calls for a particular process. This all increases the
overhead involved when swapping processes in and out of the CPU.
29 CSE/HKBKCE
Figure:Freeframes(a)beforeallocationand(b)afterallocation.
HardwareSupport
TranslationLookasideBuffer
 A special, small, fast lookup hardware cache, called a translation look-aside buffer
(TLB).
 EachentryintheTLBconsistsoftwoparts:akey(ortag)andavalue.
 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.
 TheTLBcontainsonlyafewofthepage-tableentries.
Working:
 Whenalogical-addressisgeneratedbytheCPU,itspage-numberispresentedtothe 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)
30 CSE/HKBKCE
Figure1:PaginghardwarewithTLB
 In addition, we add the page-number and frame-number to the TLB, so that theywill be
found quickly on the next reference.
 IftheTLBisalreadyfullofentries,theOSmustselectoneforreplacement.
 Percentageoftimesthataparticularpage-numberisfoundintheTLBiscalledhitratio.
Advantage: Search operation is fast.

Disadvantage:Hardwareisexpensive.
 SomeTLBshavewireddownentriesthatcan'tberemoved.
 Some TLBs store ASID(address-space identifier) ineach entryof the TLB that uniquely
identify each process and provide address space protection for that process.
Protection
 Memory-protectionisachievedbyprotection-bitsforeachframe.
 Theprotection-bitsarekeptinthepage-table.
 Oneprotection-bitcandefineapagetoberead-writeorread-only.
 Everyreference to memorygoes through the page-table to find the correct frame-
number.
 Firstly,the physical-addressis computed. Atthesame time, the protection-bit ischecked to
verify that no writes are being made to a read-only page.
 Anattempttowritetoaread-only pagecausesahardware-traptotheOS(ormemory protection
violation).
31 CSE/HKBKCE
ValidInvalidBit
 Thisbitisattachedtoeachentryinthepage-table.
 Validbit:“valid”indicatesthattheassociatedpageisintheprocess’logicaladdress space, and
is thus a legal page
 Invalidbit:“invalid”indicatesthatthepageisnotintheprocess’logicaladdressspace
Illegaladdressesaretrappedbyuseofvalid-invalidbit.
TheOSsetsthisbitforeachpagetoallowordisallowaccesstothepage.
Figure:Valid(v)orinvalid(i)bitinapage-table
SharedPages
 Anadvantageofpagingisthepossibilityofsharingcommoncode.
 Re-entrant code (Pure Code) is non-self-modifying code, it never changes during
execution.
 Twoormoreprocessescanexecutethesamecodeatthesametime.
 Eachprocesshasitsowncopyofregistersanddata-storagetoholdthedataforthe process's
execution.
 Thedatafor2differentprocesseswillbedifferent.
 Onlyonecopyoftheeditorneedbekeptinphysical-memory(Figure5.12).
 Eachuser'spage-table mapsontothesamephysicalcopyof theeditor,butdatapagesare
mapped onto different frames.
Disadvantage:
Systemsthatuseinvertedpage-tableshavedifficultyimplementingshared-memory.
32 CSE/HKBKCE
Figure:Sharingofcodeinapagingenvironment
StructureofthePageTable
Themostcommontechniquesforstructuringthepagetable:
1. HierarchicalPaging
2. HashedPage-tables
3. InvertedPage-tables
1. HierarchicalPaging
 Problem:Mostcomputerssupportalargelogical-addressspace(232to264).Inthese systems,
the page-table itself becomes excessively large.
 Solution:Dividethepage-tableintosmallerpieces.
TwoLevelPagingAlgorithm:
 Thepage-tableitselfisalsopaged.
 This is also known asa forward-mapped page-table because address translation
worksfrom the outer page-table inwards.
33 CSE/HKBKCE
Figure:Atwo-levelpage-tablescheme
Forexample:
Considerthesystemwitha32-bitlogical-addressspaceandapage-sizeof 4KB. A
logical-address is divided into
→20-bitpage-numberand
→12-bitpage-offset.
Sincethepage-tableispaged,thepage-numberisfurtherdivided into
→10-bitpage-numberand
→10-bitpage-offset.
Thus,alogical-addressisasfollows:
 where p1is an index into the outer page table, and p2is 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.
Figure:Addresstranslationforatwo-level32-bitpagingarchitecture
34 CSE/HKBKCE
2. HashedPageTables
 Thisapproachisusedforhandlingaddressspaceslargerthan32bits.
 Thehash-valueisthevirtualpage-number.
 Eachentryinthehash-tablecontainsalinked-listofelementsthathashtothesame location (to
handle collisions).
 Eachelementconsistsof3fields:
1. Virtualpage-number
2. Valueofthemappedpage-frameand
3. Pointertothenextelementinthelinked-list.
Thealgorithmworksasfollows:
 Thevirtualpage-numberishashedintothehash-table.
 Thevirtualpage-numberiscomparedwiththefirstelementinthelinked-list.
 Ifthereisamatch,thecorrespondingpage-frame(field2)isusedtoformthedesired physical-
address.
 Ifthereisnomatch,subsequententriesinthelinked-listaresearchedforamatching virtual page-
number.
Figure:Hashedpage-table
3. InvertedPageTables
 Hasoneentryforeachrealpageofmemory.
 Eachentry consistsofvirtual-addressofthepagestoredinthatrealmemory-location and
information about the process that owns the page.
 Eachvirtual-addressconsistsofatriplet<process-id,page-number,offset>.
 Eachinvertedpage-tableentryisapair<process-id,page-number>
35 CSE/HKBKCE
Figure:Invertedpage-table
Thealgorithmworksasfollows:
1. When a memory-reference occurs, part of the virtual-address, consisting of <process-id,
page-number>, is presented to the memory subsystem.
2. Theinvertedpage-tableisthensearchedfora match.
3. Ifamatchisfound,atentryi-thenthephysical-address<i,offset>isgenerated.
4. Ifnomatchisfound,thenanillegaladdressaccesshasbeenattempted.
Advantage:
1. Decreasesmemoryneededtostoreeachpage-table
Disadvantages:
1. Increasesamountoftimeneededtosearchtablewhenapagereferenceoccurs.
2. Difficultyimplementingshared-memory
Segmentation
BasicMethodofSegmentation
 Thisisamemory-managementschemethatsupportsuser-viewofmemory(Figure1).
 Alogical-addressspaceisacollectionofsegments.
 Eachsegmenthasanameandalength.
 Theaddressesspecifybothsegment-nameandoffsetwithinthesegment.
 Normally, the user-programis compiled, and the compiler automaticallyconstructs
segments reflecting the input program.
 Forex:Thecode,Globalvariables,Theheap,fromwhichmemoryisallocated,The stacks used
by each thread, The standard C library
36 CSE/HKBKCE
Figure:Programmer’sviewofaprogram Hardware
support for Segmentation

 Segment-tablemaps2dimensionaluser-definedaddressesintoone-dimensionalphysical
addresses.
 Inthesegment-table,eachentryhasfollowing2fields:
1. Segment-base contains starting physical-address where the segment resides in
memory.
2. Segment-limitspecifiesthelengthofthesegment(Figure 2).
 Alogical-addressconsistsof2parts:
1. Segment-number(s)isusedasanindextothesegment-table
2. Offset(d)mustbebetween0andthesegment-limit.
 Ifoffsetisnotbetween0&segment-limit,thenwetraptotheOS(logical-addressing attempt
beyond end of segment).
 Ifoffset is legal,thenit isaddedtothe segment-basetoproducethe physical-memory address.
Figure:Segmentationhardware
37 CSE/HKBKCE
QUESTIONBANK
1. What are deadlocks? What are its characteristics? Explain the necessary conditions
foritsoccurrence.
2. Explaintheprocessofrecoveryfromdeadlock.
3. DescribeRAG:
i) Withdeadlock
ii) Withacyclebutno deadlock
4. What is Resource Allocation Graph (RAG)? Explain how RAG is very useful indescribing
deadly embrace (dead lock ) by considering your own example.
5. With the help of a system model, explain a deadlock and explain the
necessaryconditionsthatmust hold simultaneously in a system for a deadlock to occur.
6. Explainhow deadlock canbeprevented byconsidering fournecessaryconditionscannothold.
7. UsingBanker'salgorithmdetermineswhetherthesystemisinasafestate.
8. How is a systemrecovered fromdeadlock? Explain the different methods usedtorecoverfrom
deadlock.
9. Explaindeadlockdetectionwithalgorithmandexample
10. Define the terms: safe state and safe sequence. Give an algorithm to find whether or nota
system is in a safe state.
MEMORYMANAGEMENT
1. Explainthemultistepprocessingof auserprogramwithaneatblockdiagram.
2. Distinguishbetweeninternalandexternalfragmentation.
3. Explainsegmentationwithanexample.
4. Explainwithadiagram, howTLBisused tosolvetheproblemof simplepaging scheme.
5. With a supporting paging hardware, explain in detail concept of paging with an example for a
32-byte memory with 4-type pages with a process being 16-bytes. How many bits are reserved
for page number and page offset in the logical address. Suppose the logical address is 5,
calculate the corresponding physical address, after populating memory and page table.
6. Whatarethedrawbacksofcontiguousmemoryallocation?
7. Considerapagingsystemwiththepagetablestoredin memory.
i. ifamemoryreferencetakes200nanoseconds,howlongdoes apagedmemory reference take?
ii. if we add associative register and 75 percentage of all page table references are found in
theassociativeregisters,whatistheeffectivememoryaccesstime? (Assume that finding a
page table entry in the associative memory/registers takeszero time, if the entry is found).
8. Distinguishbetween:
i. Logicaladdressspaceandphysicaladdressspace.
ii. Internalfragmentationandexternalfragmentation.
iii. Pagingandsegmentation.
9. Explainwiththehelpof supportinghardwarediagramhowtheTLBimprovestheperformance of a
demand paging system.
38 CSE/HKBKCE
10. Explaintheconceptof forwardmappedpagetable.

11. Whatisfragmentation?Explaintwotypesofmemoryfragmentation
12. Whatisswapping?Explainindetail.
13. What do you mean by address binding? Explain with the necessarysteps, the binding of
instructions and data to memory addresses.
14. Systemconsistsoffivejobs(J1,J2,J3,J4,J5)andthreeresources(R1,R2,R3).Resourcetype R1 has 10
instances, resource type R2 has 5 instances and R3 has7 instances. The following snapshot of
the system has been taken.
AdditionalQuestions
1. Findneedmatrix andcalculatethesafesequencebyusingBanker'salgorithm.Mentiontheabove system

is safe or not safe.
Jobs Allocation Maximum Available
R1 R2 R3 R1 R2 R3 R1 R2 R3
J1
0 1 0 7 5 3
J2 2 0 0 3 2 2
J3 3 0 2 9 0 2 3 3 2
J4 2 1 1 2 2 2
J5 0 0 2 4 3 3
2. Whatisdeadlock?Whatarenecessaryconditionsanoperatingsystemmustsatisfyfora
deadlock to occur?
3. WhatisaResourceAllocationGraph(RAG)? ExplainhayRAGisveryusefulisdescribing deadly
embrace by considering own example.
4. Giventhememorypartitionsof100K,500K,200 K,300Kand600Kapplyfirstfit,bestfitand worst fit
algorithms to place 212K, 417K, 112K and 426K.
5. Discussthevariousapproaches used fordeadlockrecovery.
6. Explainthestructureofpagetable.
7. Assumethatthereare5processesPOthroughP4and4typesofresources. AttimeT0wehave the
following state:
Process Allocation Maximum Available
A B C D A B C D A B C D
P0
0 0 1 2 0 0 1 2 1 5 2 0
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 6 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
P5 0 0 2 4 3 3
ApplyBanker'salgorithmtoanswerthe following:
i) Whatisthecontentofneed matrix?
ii) Isthesysteminasafe state?
iii) Ifarequestfrom aprocessP1(0, 4,2,0)arrives, canitbegranted?
39 CSE/HKBKCE
8. Considerthefollowingsnapshot of a system
A B C A B C A B C
P0
0 0 2 0 0 4
P1 1 0 0 2 0 1
P2 1 3 5 1 3 7 1 0 2
P3 6 3 2 8 4 2
P4 1 4 3 1 5 7
FindtheneedmatrixandcalculatesafesequenceusingBanker'salgorithm.Mentiontheabove system is
safe or not safe.
9. Whatispaging?Explainpaginghardwarewith translationlook-aside buffer.

10. Explainthestructureofpagetablewithrespecttohierarchicalpaging.
11. ConsiderasystemwithfiveprocessesPOthrough P4andthreeresourcesA.B,CResourcesA has ten
instances, resources type B has five instance and resource type C has seven instances. Suppose
that at time. To the following snapshot of the system has been taken.
A B C A B C A B C
P0
0 1 0 7 5 3
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2 3 3 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
12. Stateandexplain banker'salgorithm fordeadlockavoidance.
13. Whatistheprinciplebehindpaging? Explainitsoperation,clearlyindicatinghowthelogical
addresses are converted to physical addresses.
40 CSE/HKBKCE

BCS303 OS - Module III Notes

Uploaded by

Copyright:

Available Formats

BCS303 OS - Module III Notes

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

BCS303 OS - Module III Notes

Uploaded by

Copyright:

Available Formats

OperatingSystems BCS303

HKBK College of Engineering

 A system consists of a finite number of resources to be distributed among a number of

3. Nopreemption: Resourcescannotbepreempted;thatis,aresource canbereleasedonly

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

ThegraphconsistsofasetofverticesVandasetofedgesE.ThesetofverticesVis partitioned into two

However,thereisnodeadlock.ObservethatprocessP4mayreleaseitsinstanceofresource type R2.

Deadlock-avoidance requires that the operating system be given in advance additional

If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm,

 To avoid deadlocks an additional information is required about how resources are to be

 Ifaresource-allocationsystemhasonlyoneinstanceofeachresource type,thena variant

Notethattheresourcesmustbeclaimedaprioriinthesystem.Thatis,beforeprocessPistarts executing, all

number of processes, and m = number of resources types

Available:Avectoroflengthmindicatesthenumberofavailableresourcesofeachtype.If available [j] =

Max:Annx mmatrix definesthe maximumdemandof eachprocess. If Max[i,j]=k, thenprocess Pi

Allocation:Annxmmatrixdefinesthenumberof resourcesof eachtypecurrentlyallocated toeach

Need:Annxmmatrixindicatestheremainingresourceneedofeachprocess.IfNeed[i,j]=k, then Pi may

Thealgorithmforfindingoutwhetherornota systemis inasafestate.Thisalgorithmcanbe described as

1. LetWorkandFinishbevectorsoflengthmandn,respectively. Initialize: Work

Thesystemiscurrentlyinasafestate.Indeed, thesequence <P1,P3,P4,P2,P0>satisfiesthe safety

Supposenowthat processP1requestsoneadditionalinstanceofresourcetypeAandtwo instances of

Adeadlockdetectionalgorithmthatis applicabletoseveralinstances of aresourcetype.The algorithm

AlgorithmrequiresanorderofO(mxn2)operationstodetect whetherthesystemisin deadlocked

Considera systemwithfiveprocessesPothroughP4andthreeresourcetypesA, B,andC.

Thesystemisnowdeadlocked.Althoughwe canreclaimtheresourcesheldbyprocess Po,the number of

To eliminatedeadlocksusingresourcepreemption,wesuccessively preemptsome resources from

1. Selecting a victim. Which resources and which processes are to be preempted? As in

3. Starvation.Howdoweensurethatstarvationwillnotoccur?Thatis,howcanwe guarantee that

 Every program to be executed has to be executed must be in memory. The instruction

Major part of swap-time is transfer-time; i.e. total transfer-time is directly proportional to

 TheOSkeeps atableindicatingwhich parts of memoryareavailable andwhichpartsare

2. BestFit:Allocatethesmallestholethatisbigenough.Wemustsearchtheentirelist, unless the

Advantage: Search operation is fast.

support for Segmentation

10. Explaintheconceptof forwardmappedpagetable.

1. Findneedmatrix andcalculatethesafesequencebyusingBanker'salgorithm.Mentiontheabove system

9. Whatispaging?Explainpaginghardwarewith translationlook-aside buffer.

You might also like