SNN - Module 3 - Notes

Module -3 Sankhya N.
Nayak
CHAPTER 7: DEADLOCKS
A process in operating system uses resources in the following way.
1) Requests a resource
2) Use the resource
3) Releases the resource
Deadlock is a situation where a set of processes are blocked because each process is holding a resource and
waiting for another resource acquired by some other process.
In the above diagram, the process 1 has resource 2 and needs to acquire resource 1. Similarly process 2 has
Sankhya Nayak,CSE,JNNCE
resource 1 and needs to acquire resource 2. Process 1 and process 2 are in deadlock as each of them needs
the other’s resource to complete their execution but neither of them is willing to relinquish their resources.
7.2 Deadlock Characterization

7.2.1 Necessary Conditions
Deadlock can arise if the following four conditions hold simultaneously (Necessary Conditions).
• Mutual Exclusion: At least one of the resources is non-sharable (that is; only a limited number of
processes can use it at a time and if it is requested by a process while it is being used by another one,
the requesting process has to wait until the resource is released.).
• Hold and Wait: There must be at least one process that is holding at least one resource and waiting
for other resources that are being hold by other processes.
• No Preemption: No resource can be preempted before the holding process completes its task with
that resource.
• Circular Wait: There exists a set of processes: {P1, P2, ..., Pn} such that
o P1 is waiting for a resource held by P2
o P2 is waiting for a resource held by P3
o ...
o Pn-1 is waiting for a resource held by Pn
• Pn is waiting for a resource held by P1
Dept. of CS & E, JNNCE, SHIVAMOGGA 1

Module -3 Sankhya N. Nayak
7.2.2 Resource Allocation Graphs

Resource allocation graphs are drawn in order to see the allocation relations of processes and resources
easily. In these graphs, processes are represented by circles and resources are represented by boxes.
Resource boxes have some number of dots inside indicating available number of that resource, that is
number of instances.
A resource allocation graph contains a set of vertices V and a set of edges E.
V is partitioned into two types:
• P = {P1, P2, ..., Pn} is the set of all processes.

• R = {R1, R2, ..., Rm} is the set of all resources.
A request is represented by a directed edge from Pi to Rj.

An assignment is represented by a directed edge from Rj to Pi.
resource type with four Pi requests an instance of Rj Pi is holding an instance of Rj

instances:
• If the resource allocation graph contains no cycles then there is no deadlock in the system at that
instance.
• If the resource allocation graph contains a cycle, then a deadlock may exist.
• If there is a cycle, and the cycle involves only resources which have a single instance, then a deadlock
has occurred.
Examples:

7.3 Methods of Handling Deadlocks in Operating System

The first two methods are used to ensure the system never enters a deadlock.
Deadlock Prevention
• This is done by restraining the ways a request can be made. Since deadlock occurs when all the above
four conditions are met, we try to prevent any one of them, thus preventing a deadlock.
Deadlock Avoidance
• When a process requests a resource, the deadlock avoidance algorithm examines the resource-allocation
state. If allocating that resource sends the system into an unsafe state, the request is got granted.
• Therefore, it requires additional information such as how many resources of each type is required by a
process. If the system enters an unsafe state, it has to take a step back to avoid deadlock.
Deadlock Detection and Recovery

We let the system fall into a deadlock and if it happens, we detect it using a detection algorithm and try to
recover.
Deadlock Ignorance
In the method, the system assumes that deadlock never occurs. Since the problem of deadlock situation is
not frequent, some systems simply ignore it. Operating systems such as UNIX and Windows follow this
approach. However, if a deadlock occurs, we can reboot our system and the deadlock is resolved
automatically.
Note: The above approach is an example of Ostrich Algorithm. It is a strategy of ignoring potential problems
on the basis that they are extremely rare.
7.4 Deadlock Prevention

To prevent the system from deadlocks, one of the four necessary conditions that may create a deadlock
should be discarded. The methods for those conditions are as follows:
• Mutual Exclusion: In general, we do not have systems with all resources being sharable. Some
resources like printers, processing units are non-sharable. So, it is not possible to prevent deadlocks
by denying mutual exclusion.
• Hold and Wait: One protocol to ensure that hold-and-wait condition never occurs says each process
must request and get all its resources before it begins execution.
Another protocol is “Each process can request resources only when it does not occupy any
resources.”
The second protocol is better. However, both protocols cause low resource utilization and starvation.
Many resources are allocated but most of them are unused for a long period of time. A process that
requests several commonly used resources cause many others to wait indefinitely.

• No Preemption: One protocol is “If a process that is holding some resources requests another
resource and that resource cannot be allocated to it, then it must release all resources that are
currently allocated to it.”
Another protocol is “When a process requests some resources, if they are available, allocate them. If
a resource it requested is not available, then we check whether it is being used or it is allocated to
some other process waiting for other resources. If that resource is not being used, then the OS
preempts it from the waiting process and allocate it to the requesting process. If that resource is
used, the requesting process must wait.” This protocol can be applied to resources whose states can
easily be saved and restored (registers, memory space). It cannot be applied to resources like
printers.
• Circular Wait: One protocol to ensure that the circular wait condition never holds is “Impose a linear
ordering of all resource types.” Then, each process can only request resources in an increasing order
of priority.
For example, set priorities for r1 = 1, r2 = 2, r3 = 3, and r4 = 4. With these priorities, if process P
wants to use r1 and r3, it should first request r1, then r3.
Another protocol is “Whenever a process requests a resource rj, it must have released all resources
rk with priority(rk) ≥ priority (rj).
7.4 Deadlock Avoidance

• Given some additional information on how each process will request resources, it is possible to
construct an algorithm that will avoid deadlock states. The algorithm will dynamically examine the
resource allocation operations to ensure that there won't be a circular wait on resources.
• When a process requests a resource that is already available, the system must decide whether that
resource can immediately be allocated or not. The resource is immediately allocated only if it leaves
the system in a safe state.
• A state is safe if the system can allocate resources to each process in some order avoiding a
deadlock. A deadlock state is an unsafe state.
o If a system is in safe state  no deadlocks
o If a system is in unsafe state  possibility of deadlock
o Avoidance  ensure that a system will never enter an unsafe state.
Fig: Safe, Unsafe and deadlock state spaces

Avoidance Algorithms
• Single instance of a resource type

o Use a resource-allocation graph algorithm
• Multiple instances of a resource type
o Use the banker’s algorithm
7.5.2 Resource allocation graph algorithm
• Claim edge Pi → Rj indicated that process Pj may request resource Rj; represented by a dashed line
• Claim edge converts to request edge when a process requests a resource
• Request edge converted to an assignment edge when the resource is allocated to the process
• When a resource is released by a process, assignment edge reconverts to a claim edge.
• Resources must be claimed a priori in the system
Resource Allocation graph where P1 and P2 Unsafe State and request by P1 will not be
request for resource R4 granted as a cycle will be formed.
• Suppose that process Pi requests a resource Rj

• The request can be granted only if converting the request edge to an assignment edge does not
result in the formation of a cycle in the resource allocation graph
7.5.3 Bankers Algorithm

It is a deadlock avoidance algorithm where multiple instances of resources are avaialable. The following data
structures are used in the algorithm:
m = number of resources n = number of processes
Available : One dimensional array of size m. It indicates the number of available resources of each type. For
example, if Available [i] is k, there are k instances of resource ri.
Max : Two dimensional array of size n*m. It defines the maximum demand of each process from each
resource type.
For example, if Max [i][j] is k, process pi may request at most k instances of resource type rj.
Allocation : Two dimensional array of size n*m. It defines the number of resources of each type currently
allocated to each process.

Need : Two dimensional array of size n*m. It indicates the remaining need of each process, of each resource
type.
If Need [i][j] is k, process pi may need k more instances of resource type rj.
Note that Need [i][j] = Max [i][j] - Allocation [i][j].
7.5.3.1 :Safety Algorithm
The algorithm for finding out whether or not a system is in a safe state can be described as follows:
1) Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
Initialize: Work = Available
Finish[i] = false; for i=1, 2, 3, 4….n
2) Find an i such that both

a) Finish[i] = false
b) Needi <= Work
if no such i exists goto step (4)
3) Work = Work + Allocation[i]
Finish[i] = true
goto step (2)

4) if Finish [i] = true for all i , then the system is in a safe state
7.5.3.2 Resource-Request Algorithm
Let Requesti be the request array for process Pi. If Requesti [j] == k, then process Pi wants k instances of
resource type Rj. When a request for resources is made by process Pi, the following actions are taken:
1. If Requesti <= Needi ,Goto step (2) ;

otherwise, raise an error condition, since the process has exceeded its maximum claim.
2. If Requesti <= Available, Goto 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 safe  the resources are allocated to Pi
• If unsafe  Pi must wait, and the old resource-allocation state is restored

Example:
• 5 processes P0 through P4;
• resource types:
A (10 instances), B (5instances), and C (7 instances)
• Snapshot at time T0:
• The content of the matrix Need is defined to be Max – Allocation

Need
ABC
P0 743
P1 122
P2 600
P3 011
P4 431
• The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety criteria

What will happen if process P1 requests one additional instance of resource type A and two instances of
resource type C?
We must determine whether this new system state is safe. To do so, we again execute Safety algorithm on
the above data structures.

7.6 Deadlock Detection

• requires an algorithm which examines the state of the system to determine whether a deadlock has
occurred.
7.6.1 Single Instance of Each Resource Type
• Maintain wait-for graph

o Nodes are processes
o Pi → Pj if Pi is waiting for Pj
Resource-Allocation Graph Corresponding wait-for graph
• Periodically invoke an algorithm that searches for a cycle in the graph. If there is a cycle, there exists
a deadlock.
• An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of
vertices in the graph. Sankhya Nayak,CSE,JNNCE
7.6.2 Several Instances of a Resource Type
• Uses several time varying data structures similar to the ones used in Bankers algorithm.
• Available: A vector of length m indicates the number of available resources of each type
• Allocation: An n x m matrix defines the number of resources of each type currently allocated to
each process
• Request: An n x m matrix indicates the current request of each process. If Request [i][j] = k, then
process Pi is requesting k more instances of resource type Rj.
Detection Algorithm
1. Let Work and Finish be vectors of length m and n, respectively Initialize:
(a) Work = Available
(b) For i = 1,2, …, n,
if Allocationi  0, then
Finish[i] = false;
otherwise,
Finish[i] = true

2. Find an index i such that both:
(a) Finish[i] == false

(b) Requesti  Work
If no such i exists, go to step 4
3. Work = Work + Allocationi

Finish[i] = true
go to step 2
4. If Finish[i] == false, for some i, 1  i  n, then the system is in deadlock state.
Moreover, if Finish[i] == false, then Pi is deadlocked
Example:
Run-time complexity: O(m × n²).
Example: consider a system with 5 processes (P0 .. P4) and 3 resources types (A(7) B(2) C(6))
resource-allocation state at time t0:
Is the system in a deadlocked state? Yes.
If not, which sequence results in finish[i] == true for all i ?

Although we can reclaim the resources held by P0, the number of available resources is insufficient to fulfill
the requests of the other processes.
Thus, a deadlock exists, consisting of processes P1, P2, P3, and P4.
• When should we invoke the detection algorithm? Depends on:

o how often is a deadlock likely to occur
o how many processes will be affected by deadlock when it happens
• If deadlocks occur frequently, then the algorithm should be invoked frequently.
• Deadlocks only occur when some process makes a request which cannot be granted (if this request is
the completes a chain of waiting processes).

• Extreme: invoke the algorithm every time a request is denied

• Alternative: invoke the algorithm at less frequent time intervals:
o once per hour
o whenever CPU utilization < 40%
disadvantage: cannot determine exactly which process 'caused' the deadlock
7.7 Recovery from Deadlock

How to deal with deadlock:
• inform operator and let them decide how to deal with it manually
• let the system recover from the deadlock automatically:
o abort or more of the deadlocked processes to break the circular wait
o preempt some resources from one or more of the processes to break the circular wait
7.7.1 Process termination

Eliminating the deadlock by aborting a process is not easy; involves clean-up (e.g., file, printer).
• abort all deadlocked processes (disadvantage: wasteful)
• abort one process at a time until the circular wait is eliminated
o disadvantage: lot of overhead; must re-run algorithm after each kill
• how to determine which process to terminate? minimize cost

▪ priority of the process
▪ how long has it executed? how much more time does it need?
▪ how many and what type of resources has the process used?
▪ how many more resources will the process need to complete?
▪ how many processes will need to be terminated?
▪ is the process interactive or batch?
7.7.2 Resource Preemption
Incrementally preempt and re-allocate resources until the circular wait is broken. During pre emption the
following issues need to be addressed.
• selecting a victim (see above)
• rollback: what should be done with process which lost the resource?
clearly it cannot continue; must rollback to a safe state (???) => total rollback
• starvation: pick victim only small (finite) number of times; use number of rollbacks in decision
*********************************************************************************

Additional problems
Example of Banker’s Algorithm
Consider the following snapshot of a system:
1. calculate the content of the need matrix?
Allocation Max Available
Processes 2. Is the system in a safe state?
A B C A B C A B C
3. Determine the total amount of resources
P0 1 1 2 4 3 3 2 1 0 of each type?
P1 2 1 2 3 2 2
P2 4 0 1 9 0 2
P3 0 2 0 7 5 3
P4 1 1 2 1 1 2
Solution:
1. Content of the need matrix can be calculated by using the below formula
Need = Max – Allocation
Now, we check for a safe state

Safe sequence:
1. For process P0, Need = (3, 2, 1) and Available = (2, 1, 0)
a. Need < Available = False So, the system will move for the next process.
2. For Process P1, Need = (1, 1, 0) Available = (2, 1, 0)
a. Need < Available = True Request of P1 is granted.
b. Available = Available +Allocation = (2, 1, 0) + (2, 1, 2) = (4, 2, 2) (New Available)
a. Need < Available = False So, the system will move to the next process.
a. Need <Available = False So, the system will move to the next process.
a. Need <Available = True Request of P4 is granted.
b. Available = Available + Allocation= (4, 2, 2) + (1, 1, 2)= (5, 3, 4) now, (New Available)
6. Now again check for Process P2, Need = (5, 0, 1) Available = (5, 3, 4)
b. Available = Available + Allocation = (5, 3, 4) + (4, 0, 1)= (9, 3, 5) now, (New Available)

7. Now again check for Process P3, Need = (7, 3, 3) Available = (9, 3, 5)
b. Available = Available +Allocation = (9, 3, 5) + (0, 2, 0) = (9, 5, 5)
8. Now again check for Process P0, = Need (3, 2, 1) Available (9, 5, 5)
a. Need < Available = True So, the request will be granted to P0.
Safe sequence: < P1, P4, P2, P3, P0>

The system allocates all the needed resources to each process. So, we can say that system is in a safe state.
The total amount of resources = sum of columns of allocation + Available
= [8 5 7] + [2 1 0] = [10 6 7]
**********************************************************
#2 )
Process Max Allocation Available
A, B, C, D A, B, C, D A, B, C, D
P0 6 0 1 2 4 0 0 1 3 2 1 1
P1 2 7 5 0 1 1 0 0
P2 2 3 5 6 1 2 5 4
P3 1 6 5 3 0 6 3 3
P4 1 6 5 6 0 2 1 2
Using Banker’s algorithm, answer the following questions:-

• i) How many resources of type A, B, C, D are there?
• ii) What are the contents of need matrix?
• iii) Find if the system is in safe state? If it is, find the safe sequence.
Solution:
1)
A = 4+1+1+3 = 9
B = 1+2+6+2+2 = 13
C = 5+3+1+1 = 10
D = 1+4+3+2+1 = 11
2) Need matrix :
-3) YES , system is in safe state Safe Sequence: P0, P2, P3, P4, P1

Chapter 8 : Memory Management

8.1: Background
• In a multiprogramming computer, the operating system resides in a part of memory and the rest is
used by multiple processes.
• The task of subdividing the memory among different processes is called memory management.
• Memory management is a method in the operating system to manage operations between main
memory and disk during process execution.
• The main aim of memory management is to achieve efficient utilization of memory.
8.1.1 Basic hardware

• The CPU can only access its registers and main memory. It cannot, for example, make direct access to
the hard drive, so any data stored there must first be transferred into the main memory chips before
the CPU can work with it.
• User processes must be restricted so that they only access memory locations that "belong" to that
process.
• This is usually implemented using a base register and a limit register for each process, as shown in
Figures 8.1 and 8.2 below.
• Every memory access made by a user process is checked against these two registers, and if a
memory access is attempted outside the valid range, then a fatal error is generated.
Figure 8.1 - A base and a limit register Figure 8.2 - Hardware address protection with base
define a logical address space and limit registers
8.1.2 Address Binding

• User programs typically refer to memory addresses with symbolic names such as "i", "count" etc.
These symbolic names must be mapped or bound to physical memory addresses, which typically
occurs in several stages:
o 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. DOS .COM programs use compile time binding.
o 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.
o Execution Time - If a program can be moved around in memory during its execution, then
binding must be delayed until execution time. This requires special hardware, and is the
method implemented by most modern OSes.
• Figure 8.3 shows the various stages of the binding processes and the units involved in each stage:
Figure 8.3 - Multistep processing of a user program
8.1.3 Logical Versus Physical Address Space

• The address generated by the CPU is a logical address, whereas the address seen by the memory
hardware is a physical address.
• Addresses bound at compile time or load time have identical logical and physical addresses.
• Addresses created at execution time, however, have different logical and physical addresses.
o In this case the logical address is also known as a virtual address.
o 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.
• The run time mapping of logical to physical addresses is handled by the memory-management unit,
MMU.
• The base register is now termed a relocation register, whose value is added to every memory
request at the hardware level.

• Note that user programs never see physical addresses. User programs work entirely in logical
address space, and any memory references or manipulations are done using purely logical addresses.
Only when the address gets sent to the physical memory chips is the physical memory address
generated.
Figure 8.4 - Dynamic relocation using a relocation register

8.1.4 Dynamic Loading
• Rather than loading an entire program into memory at once, dynamic loading loads up each routine
as it is called. The advantage is that unused routines need never be loaded, reducing total memory
usage and generating faster program startup times. The downside is the added complexity and
overhead of checking to see if a routine is loaded every time it is called and then then loading it up if
it is not already loaded.
8.1.5 Dynamic Linking and Shared Libraries Sankhya Nayak,CSE,JNNCE
1. 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.
2. 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.
o This method saves disk space, because the library routines do not need to be fully included in
the executable modules, only the stubs.
o If the code section of the library routines is reentrant, ( meaning it does not modify the code
while it runs, making it safe to re-enter it ), then main memory can be saved by loading only one copy
of dynamically linked routines into memory and sharing the code amongst all processes that are
concurrently using it.
8.2 Swapping
• A process must be loaded into memory to execute.
• If there is not enough memory available to keep all running processes in memory at the same time,
then some processes who are not currently using the CPU may have their memory swapped out to a
fast local disk called the backing store.
• If compile-time or load-time address binding is used, then processes must be swapped back into the
same memory location from which they were swapped out.
• If execution time binding is used, then the processes can be swapped back into any available
location.

• Swapping is a very slow process compared to other operations. For example, if a user process
occupied 10 MB and the transfer rate for the backing store were 40 MB per second, then it would
take 1/4 second ( 250 milliseconds ) just to do the data transfer. Adding in a latency lag of 8
milliseconds and ignoring head seek time for the moment, and further recognizing that swapping
involves moving old data out as well as new data in, the overall transfer time required for this swap is
512 milliseconds, or over half a second. For efficient processor scheduling the CPU time slice should
be significantly longer than this lost transfer time.
• To reduce swapping transfer overhead, it is desired to transfer as little information as possible, which
requires that the system know how much memory a process is using, as opposed to how much
it might use. Programmers can help with this by freeing up dynamic memory that they are no longer
using.
• It is important to swap processes out of memory only when they are idle, or more to the point,
only when there are no pending I/O operations. ( Otherwise, the pending I/O operation could write
into the wrong process's memory space. ) The solution is to either swap only totally idle processes or
do I/O operations only into and out of OS buffers, which are then transferred to or from process's
main memory as a second step.
• Most modern OSes no longer use swapping, because it is too slow and there are faster alternatives
available. ( e.g. Paging. )
Figure 8.5 - Swapping of two processes using a disk as a backing store
8.3 Contiguous memory allocation

• 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:
o One for the resident OS.
o One for the user processes.
• Each process is contained in a single
contiguous section of memory.
8.3.1.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 physical-address.
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. Sankhya Nayak,CSE,JNNCE
• 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 memory-space and overhead for
unnecessary swapping.
Figure 8.6: Hardware support for relocation and limit-registers
8.3.2. Memory Allocation

Two types of memory partitioning are:
1. Fixed-sized partitioning
2. Variable-sized partitioning

1.
Fixed-sized Partitioning 2. Variable-sized Partitioning
• The memory is divided into fixed-sized • The OS keeps a table indicating which parts of
partitions. memory are available and which parts are occupied.
• Each partition may contain exactly one • A hole is a block of available memory.
process. Normally, memory contains a set of holes of various
• The degree of multiprogramming is sizes.
bound by the number of partitions. • Initially, all memory is available for user-
• When a partition is free, a process is processes and considered one large hole.
selected from the input queue and • When a process arrives, the process is allocated
loaded into the free partition. memory from a large hole.
When the process terminates, the • If we find the hole, we allocate only as much
partition becomes available for memory as is needed and keep the remaining
another process. memory available to satisfy future requests.
Three strategies used to select a free hole from the set of available holes:
1. 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.
2. 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.
3. 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.
• First-fit and best fit are better than worst fit in terms of decreasing time and storage utilization.

8.3.3 Fragmentation
Two types of memory fragmentation:
1. Internal fragmentation 2. External fragmentation
Internal Fragmentation External Fragmentation
• The general approach is to break the • External fragmentation occurs when there is enough
physical-memory into fixed-sized blocks total memory-space to satisfy a request but the
and allocate memory in units based on available-spaces are not contiguous. (i.e. storage is
block size. fragmented into a large number of small holes).
• The allocated-memory to a process • Both the first-fit and best-fit strategies for memory-
may be slightly larger than the allocation suffer from external fragmentation.
requested-memory. • Statistical analysis of first-fit reveals that given N
• The difference between requested- allocated blocks, another 0.5 N blocks will be lost to
memory and allocated-memory is fragmentation. This property is known as the 50-
called internal fragmentation i.e. percent rule.
Unused memory that is internal to a
partition.

Difference between Internal fragmentation and External fragmentation
Avoiding Internal Fragmentation

The primary problem of internal fragmentation may occur because of the fixed memory block sizes. It can be
solved by assigning spaces to the process through dynamic partitioning. Now, dynamic partitioning only
allocates the amount of space that has been requested by the process. Thus, there is no internal
fragmentation in this case.
Two solutions to external fragmentation:

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

8.4 Paging
• Paging is a memory-management scheme which permits the physical-address space of a process to be
non-contiguous.
• This also solves the considerable problem of fitting memory-chunks of varying sizes onto the backing-
store.
• Traditionally: Support for paging has been handled by hardware.
• Recent designs: The hardware & OS are closely integrated.
8.4.1 Basic Method of Paging

• 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 any available memory frames from the
backing store.
• The backing store is divided into fixed-sized blocks that are of the same size as the memory frames.
The hardware support for paging is shown in Figure 8.7.
Address generated by CPU is divided into 2 parts (Figure 8.8):
1. Page-number (p) is used as an index to the page-table. The page-table contains the 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.
Figure 8.7: Paging hardware

• The page table maps the page number to a frame number, to yield a physical address
which also has two parts: The frame number and the offset within that frame.
• The number of bits in the frame number determines how many frames the system can address, and
the number of bits in the offset determines the size of each frame.
The paging model of memory is shown in Figure 8.8.
Figure 8.8: Paging model of logical and physical memory

• The page size (like the frame size) is defined by the hardware.
• 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. Sankhya Nayak,CSE,JNNCE
• 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, the logical address is as follows:
Ex: n=2 and m=4 32-byte memory and 4-byte pages
• When a process requests memory (e.g. when its code is loaded in from disk), free frames are
allocated from a free-frame list, and inserted into that process's page table.
• Processes are blocked from accessing anyone else's memory because all 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.
• The operating system must keep track of each individual process's page table, 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.

Figure 8.10: Free frames (a) before allocation and (b) after allocation.
8.4.2. Hardware Support

Translation Look aside Buffer(TLB)
• 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 8.11).
• 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.
Figure 8.11: Paging hardware with TLB

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.
EFFECTIVE MEMORY ACCESS TIMES with TLB
8.4.3.Protection
• Memory-protection is achieved by protection-bits for each frame kept in the page-table.
• One protection-bit can define a page to be read-write or read-only.
• Every reference to memory goes through the page-table to find the correct frame number.
• Firstly, the physical-address is computed. At the same time, the protection-bit is checked to verify
that no writes are being made to a read-only page.
• An attempt to write to a read-only page causes a hardware-trap to the OS (or memory protection
violation).
Valid Invalid Bit: This bit is attached to each entry in the page-table.
• Valid bit: “valid” indicates that the associated page is in the process’ logical address space, and is
thus a legal page
• Invalid bit: “invalid” indicates that the page is not in the process’ logical address space Illegal
addresses are trapped by use of valid-invalid bit.
• The OS sets this bit for each page to allow or disallow access to the page.
Figure 8.12: Valid (v) or invalid (i) bit in a page-table

8.4.4 Shared Pages

• An advantage of paging is the possibility of sharing common code.
• Re-entrant code (Pure Code) is non-self-modifying code, it never changes during execution.
• Two or more processes can execute the same code at the same time.
• Each process has its own copy of registers and data-storage to hold the data for the process's
execution.
• The data for 2 different processes will be different.
• Only one copy of the editor need be kept in physical memory (Figure 8.13).
• Each user's page-table maps onto the same physical copy of the editor, but data pages are mapped
onto different frames.
Disadvantage:
Systems that use inverted page-tables have difficulty implementing shared-memory.
Figure 8.13 : Sharing of code in a paging environment

8.5 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
8.5.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.

Figure 8.14: A two-level page-table scheme

For example:
Consider the system with a 32-bit logical-address space and a page-size 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 logical-address is as follows: Sankhya Nayak,CSE,JNNCE
• p1 is an index into the outer page table
• p2 is the displacement within the page of the inner page

table
• The address-translation method for this architecture is shown in figure 8.15. Because address
translation works from the outer page table inward, this scheme is also known as a forward mapped
page table.
Figure 8.15: Address translation for a two-level 32-bit paging architecture

8.5.2. Hashed Page Tables
• This approach is used for handling address spaces larger than 32 bits.
• The hash-value is the virtual page-number.

• Each entry in the hash-table contains a linked-list of elements that hash to the same location (to
handle collisions).
Each element consists of 3 fields:
1. Virtual page-number
2. Value of the mapped page-frame and
3. Pointer to the next element in the linked-list.
The algorithm works as follows:
• The virtual page-number is hashed into the hash-table.
• The virtual page-number is compared with the first element in the linked-list.
• If there is a match, the corresponding page-frame (field 2) is used to form the desired
physical-address.
• If there is no match, subsequent entries in the linked-list are searched for a matching virtual page-
number.
Figure 8.16: Hashed page-table

8.5. 3. Inverted Page Tables
• Has one entry for each real page of memory.
• Each entry consists of virtual-address of the page stored in that real memory-location and
information about the process that owns the page.
• Each virtual-address consists of a triplet <process-id, page-number, offset>.
• Each inverted page-table entry is a pair <process-id, page-number>
Figure 8.17: Inverted page-table

The algorithm works as follows:

1. When a memory-reference occurs, part of the virtual-address, consisting of <process-id,
page-number>, is presented to the memory subsystem.
2. The inverted page-table is then searched for a match.
3. If a match is found, at entry i-then the physical-address <i, offset> is generated.
4. If no match is found, then an illegal address access has been attempted.
Advantage:
1. Decreases memory needed to store each page-table
Disadvantages:
1. Increases amount of time needed to search table when a page reference occurs.
2. Difficulty implementing shared-memory.
8.6. Segmentation
Basic Method of Segmentation

• This is a memory-management scheme that supports user-view of memory (Figure 8.18).
• 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.
Figure 8.18 : Programmer’s view of a program

8.6.2 Hardware support for Segmentation
• Segment-table maps 2 dimensional user-defined addresses into one-dimensional 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 8.19).
• 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(logical-addressing attempt beyond
end of segment).
• If offset is legal, then it is added to the segment-base to produce the physical-memory address.
Figure 8.19: Segmentation hardware
Example: Consider Figure 8.20.

• 5 segments numbered from 0 to 4.
• They are stored in physical memory.
• Segment table contains entry for base and limit for each segment.
• For ex, segment 2 is 400 bytes long and begins at address 4300.
• Thus, a reference to byte 53 of segment 2 is mapped into location 4300+53=4353.
• A reference to byte 1222 of segment 0 would result in TRAP to OS, as segment is only 1000 bytes
long.
Figure 8.20: Example of Segmentation
Advantages of Segmentation
• No Internal fragmentation.
• Segment Table consumes less space in comparison to Page table in paging.
Disadvantage of Segmentation
• As processes are loaded and removed from the memory, the free memory space is broken into little
pieces, causing External fragmentation.

SNN - Module 3 - Notes

Uploaded by

Copyright:

Available Formats

SNN - Module 3 - Notes

Uploaded by

Document Information

Original Title

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

SNN - Module 3 - Notes

Uploaded by

Copyright:

Available Formats

Module -3 Sankhya N.

7.2 Deadlock Characterization

Dept. of CS & E, JNNCE, SHIVAMOGGA 1

7.2.2 Resource Allocation Graphs

A resource allocation graph contains a set of vertices V and a set of edges E.

V is partitioned into two types:

• P = {P1, P2, ..., Pn} is the set of all processes.

A request is represented by a directed edge from Pi to Rj.

resource type with four Pi requests an instance of Rj Pi is holding an instance of Rj

Dept. of CS & E, JNNCE, SHIVAMOGGA 2

7.3 Methods of Handling Deadlocks in Operating System

Deadlock Detection and Recovery

7.4 Deadlock Prevention

Dept. of CS & E, JNNCE, SHIVAMOGGA 3

7.4 Deadlock Avoidance

Fig: Safe, Unsafe and deadlock state spaces

Dept. of CS & E, JNNCE, SHIVAMOGGA 4

• Single instance of a resource type

7.5.2 Resource allocation graph algorithm

request for resource R4 granted as a cycle will be formed.

• Suppose that process Pi requests a resource Rj

7.5.3 Bankers Algorithm

m = number of resources n = number of processes

Dept. of CS & E, JNNCE, SHIVAMOGGA 5

Note that Need [i][j] = Max [i][j] - Allocation [i][j].

7.5.3.1 :Safety Algorithm

Initialize: Work = Available

Finish[i] = false; for i=1, 2, 3, 4….n

2) Find an i such that both

if no such i exists goto step (4)

3) Work = Work + Allocation[i]

goto step (2)

7.5.3.2 Resource-Request Algorithm

1. If Requesti <= Needi ,Goto step (2) ;

Dept. of CS & E, JNNCE, SHIVAMOGGA 6

• The content of the matrix Need is defined to be Max – Allocation

Dept. of CS & E, JNNCE, SHIVAMOGGA 7

Dept. of CS & E, JNNCE, SHIVAMOGGA 8

7.6 Deadlock Detection

7.6.1 Single Instance of Each Resource Type

• Maintain wait-for graph

Resource-Allocation Graph Corresponding wait-for graph

7.6.2 Several Instances of a Resource Type

(b) For i = 1,2, …, n,

Dept. of CS & E, JNNCE, SHIVAMOGGA 9

2. Find an index i such that both:

(a) Finish[i] == false

If no such i exists, go to step 4

3. Work = Work + Allocationi

resource-allocation state at time t0:

Is the system in a deadlocked state? Yes.

If not, which sequence results in finish[i] == true for all i ?

• When should we invoke the detection algorithm? Depends on:

Dept. of CS & E, JNNCE, SHIVAMOGGA 10

• Extreme: invoke the algorithm every time a request is denied

7.7 Recovery from Deadlock

7.7.1 Process termination

• how to determine which process to terminate? minimize cost

Dept. of CS & E, JNNCE, SHIVAMOGGA 11