A process in operating systems uses different resources and uses resources in the following way.

1. Requests a resource
2. Use the resource
3. Releases the resource

Deadlock: A 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.
Consider an example when two trains are coming toward each other on the same track and there is only one
track, none of the trains can move once they are in front of each other. A similar situation occurs in operating
systems when there are two or more processes that hold some resources and wait for resources held by
others.
For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is
acquired by process 2, and process 2 is waiting for resource 1.

Figure 3.1: Deadlock Example

Deadlock characterization (Necessary Conditions)

Deadlock can arise if the following four conditions hold simultaneously
• Mutual Exclusion: One or more than one resource is non-shareable (Only one process can use at a
time)
• Hold and Wait: A process is holding at least one resource and waiting for resources.
• No Pre-emption: A resource cannot be taken from a process unless the processes release the resource
• Circular Wait: A set of processes are waiting for each other in circular form.

Resource Allocation Graph (RAG).

In RAG vertices are two types –
1. Process vertex – Every process will be represented as a process vertex. Generally, the process will be
represented with a circle.
2. Resource vertex – Every resource will be represented as a resource vertex. It is also two types –
• Single instance type resource – It represents a box, inside the box, there will be one dot. So, the
number of dots indicates how many instances are present of each resource type.
• Multi-resource instance type resource – It also represents a box, inside the box, there will be many
dots present.
 Figure 3.2: Representation of Instances using Graph

There are two types of edges in RAG –

1. Assign Edge – If you already assign a resource to a process then it is called Assign edge.
2. Request Edge – It means in future the process might want some resource to complete the execution
that is called request edge.

Figure 3.3: Types of Edges in RAG

So, if a process is using a resource, an arrow is drawn from the resource node to the process node. If a process
is requesting a resource, an arrow is drawn from the process node to the resource node.

If there is a cycle in the Resource Allocation Graph and each resource in the cycle provides only one instance,
then the processes will be in a deadlock.

Example 1 (Single instances RAG) –

Explanation:

For example in figure 3.4, if process P1

holds resource R1, process P2 holds
resource R2 and process P1 is waiting for R2
and process P2 is waiting for R1, then
process P1 and process P2 will be in a
deadlock.

Figure 3.4: Single Instance RAG with Deadlock

Example 2: (Single instances RAG without Deadlock) –

 Explanation:

Here’s another example that shows

Processes P1 and P2 acquiring
resources R1 and R2 while process
P3 is waiting to acquire both
resources. In this example, there is
no deadlock because there is no
circular dependency.

Figure 3.5: Single Instance RAG without Deadlock

So cycle in single-instance resource type is the sufficient condition for deadlock.

Example 3 (Multi-instance RAG) –

Figure 3.6: Multi-Instance without Deadlock

Methods for handling deadlock
There are three ways to handle deadlock
1) Deadlock prevention or avoidance: The idea is to not let the system into a deadlock state.
2) Deadlock detection and recovery: Let deadlock occur, then do pre-emption to handle it once occurred.
3) Ignore the problem altogether: If the deadlock is very rare, then let it happen and reboot the system.

Deadlock Prevention
Deadlock prevention algorithms ensure that at least one of the necessary conditions (Mutual exclusion, hold
and wait, no pre-emption and circular wait) does not hold. However, most prevention algorithms have poor
resource utilization and hence result in reduced throughputs.
• Mutual Exclusion
Not always possible to prevent deadlock by preventing mutual exclusion (making all resources shareable) as
certain resources are cannot be shared safely.
• Hold and Wait: There are two approaches, but both have their disadvantages -
1. A resource can get all required resources before it starts execution. This will avoid deadlock but will
 result in reduced throughputs as resources are held by processes even when they are not needed.
They could have been used by other processes during this time.
2. The second approach is to request a resource only when it is not holding any other resource. This may
result in starvation as all required resources might not be available freely always.
• No pre-emption: There are two approaches
1. If a process requests a resource that is held by another waiting resource, then the resource may be
pre-empted from the other waiting resource. In the second approach, if a process requests a resource
that is not readily available, all other resources that it holds are pre-empted.
2. The challenge here is that the resources can be pre-empted only if we can save the current state can
be saved and processes could be restarted later from the saved state.
• Circular wait
To avoid the circular wait, resources may be ordered, and we can ensure that each process can request
resources only in increasing order of these numbers. The algorithm may itself increase complexity and may
also lead to poor resource utilization.

Deadlock Avoidance
This requires that the system has some information available upfront. Each process declares the maximum
number of resources of each type which it may need. Dynamically examine the resource-allocation state to
ensure that there can never be a circular-wait condition.
The system's resource-allocation state is defined by the number of available and allocated resources, and the
maximum possible demands of the processes. When a process requests an available resource, the system
must decide if immediate allocation leaves the system in a safe state.
The system is in a safe state if there exist a safe sequence of all processes:
Sequence < P1, P2, ..Pn> is safe for the current allocation state if, for each Pi, the resources which Pi can
request can be satisfied by
• The currently available resources
• The resources held by all of the Pj's, where j<i.
If the system is in a safe state, there can be no deadlock. If the system is in an unsafe state, there is the
possibility of deadlock.

Deadlock Avoidance Algorithms

A deadlock avoidance algorithm can be of two types:
• Resource-allocation graph algorithm
• Banker's algorithm

Resource-allocation graph algorithm

• Only applicable when we only have 1 instance of each resource type
• Claim edge (dotted edge), like a future request edge
• When a process requests a resource, the claim edge is converted to a request edge
• When a process releases a resource, the assignment edge is converted to a claim edge

Banker's Algorithm
• A classic deadlock avoidance algorithm
• More general than resource-allocation graph algorithm (handles multiple instances of each resource
type), but Is less efficient

We call Banker's algorithm when a request for R is made. Let n be the number of processes in the system, and
m be the number of resource types.
Following are the data structure used in Banker’s Algorithm
• Available[m]: the number of units of R currently unallocated (e.g., available [3] = 2)
• Max[n][m]: describes the maximum demands of each process (e.g., max [3][1] = 2)
• Allocation[n][m]: describes the current allocation status (e.g., allocation [5][1] = 3)
• Need[n][m]: describes the remaining possible need (i.e., need[i][j] = max[i][j] - allocation[i][j])

Resource-request algorithm:
Request[n] [m]: describes the current outstanding requests of all processes (e.g., request [2][1] = 3)
1. If request [i] [j] <= need [i] [j], go to step 2; otherwise, raise an error condition.

2. If request [i] [j] > available [j], then the process must wait.

3. Otherwise, pretend to allocate the requested resources to pi :

Available [j] = available [j] – request [i] [j]
Allocation [i] [j] = allocation [i] [j] + request [i] [j]
Need [i] [j] = need [i] [j] – request [i] [j]
Once the resources are allocated, check to see if the system state is safe. If unsafe, the process must
wait, and the old resource-allocated state is restored.

Safety algorithm (to check for a safe state):

Let work be an integer array of length m, initialized to available. Let finish be a Boolean array of length n,
initialized to false.
1. Find an i such that both:
• finish[i] == false
• need[i] <= work
If no such i exists, go to step 4
2. work = work + allocation[i]; finish [i] = true; Go to step 2

3. If finish[i] == true for all i, then the system is in a safe state, otherwise unsafe.

Example: consider a system with 5 processes (P0 ... P4) and 3 resources types [A (10) B (5) C (7)]
Resource-allocation state at time t0:
Process Allocation Max Need Available
A B C A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3 3 3 2
P1 2 0 0 3 2 2 1 2 2 10 5 7-→Res

P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
Table 3.1: Numerical Example
Above the given table is in a safe state and the sequence for execution is:
< P1, P3, P4, P2, P0 >
Now suppose, P1 requests an additional instance of A and 2 more instances of type C
Request [1] = (1, 0, 2)
1. Check if request [1] <= need[i] (yes)
 2. Check if request [1] <= available[i] (yes)
3. Do pretend updates to the state
Process Allocation Max Need Available
A B C A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3 3 3 2
P1 3 0 2 3 2 2 0 2 0
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
Table 3.2: After P1 Request
Above the given table is in a safe state and the sequence for execution is:
<P1, P3, P4, P0, P2>
Hence, we immediately grant the request.

Deadlock Detection
• Requires an algorithm that examines the state of the system to determine whether a deadlock has
occurred
• Requires overhead
• Run-time cost of maintaining necessary information and executing the detection algorithm
• Potential losses inherent in recovering from deadlock
A single instance of each resource type for wait-graph
• Pi → pj = pi>rq and rq → pj
• Detect cycle: o(n²)
• Overhead: maintain the graph + invoke the algorithm
Resource-allocations graphs for deadlock detection

Figure 3.7: Resource-Allocations and Wait for Graphs for Deadlock Detection

To detect the deadlock OS uses an algorithm similar to Banker's, which simply investigates every possible
allocation sequence for the processes which remain to be completed.
Following data structure is used
• Available[m]
• Allocation[n][m]
• Request[n][m]
Algorithm:
 1. Let work be an integer array of length m, initialized to available. Let finish be a Boolean array of length
n. For all i,
If allocation[i]! = 0, then finish[i] = false;
Otherwise finish[i] = true.
2. Find i such that both
• Finish[i] == false // Pi is currently not involved in a deadlock
• Request[i] <= work
If no such i exists, go to step 4

3. Reclaim the resources of process Piwork = work + allocation[i]; finish[i] = true; Go to step 2

4. If finish [i] == false for some i, Then the system is in a deadlocked state.
Moreover, if finish[i] == false, then process Pi is deadlocked.

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:
Process Allocation Request Available
A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 3 0 0 0
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2
Table 3.3: Resource-allocation state
Above the given table is in a safe state and the sequence for execution is:
< P0, P2, P3, P1, P4 >

Now suppose, P2 requests an additional instance of C:

Process Allocation Request Available
A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 3 0 0 1
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2
Table 3.4: P2 requests an additional instance of C

We can reclaim the resources held by P0, the number of available resources is insufficient to fulfil the requests
of the other processes.
Thus, a deadlock exists, consisting of processes P1, P2, P3, and P4.
Deadlock Recovery:
Deadlock recovery performs when a deadlock is detected. When deadlock detected, then our system stops
working, and after the recovery of the deadlock, our system start working again. Therefore, after the
detection of deadlock, a method must require to recover that deadlock to run the system again. The method is
called as deadlock recovery.

Deadlock recovery can be of three types:

1. Deadlock recovery through pre-emption
2. Deadlock recovery through rollback
3. Deadlock recovery through killing processes

Deadlock Recovery through Pre-emption: The ability to take a resource away from a process, have another
process use it, and then give it back without the process noticing. It is highly dependent on the nature of the
resource. Deadlock recovery through pre-emption is too difficult or sometime impossible.

Deadlock Recovery through Rollback: In this case of deadlock recovery through rollback, whenever a deadlock
is detected, it is easy to see which resources are needed. To do the recovery of deadlock, a process that owns
a needed resource is rolled back to a point in time before it acquired some other resource just by starting one
of its earlier checkpoints.

Deadlock Recovery through Killing Processes: This method of deadlock recovery through killing processes is
the simplest way of deadlock recovery. Sometime it is best to kill a process that can be return from the
beginning with no ill effects.

Introduction to Memory management:

Memory management is the functionality of an operating system, which handles or manages primary memory
and moves processes back and forth between main memory and disk during execution. Memory management
keeps track of each memory location, regardless of it allocated to some process or is free. It checks how much
memory is to allocate to processes. It decides which process will get memory at what time. It tracks whenever
some memory gets freed or unallocated and correspondingly it updates the status.

Process Address Space

The process address space is the set of logical addresses that a process references in its code. For example,
when 32-bit addressing is in use, addresses can range from 0 to 0x7fffffff; that is, 2^31 possible numbers, for a
total theoretical size of 2 gigabytes.
The operating system takes care of mapping the logical addresses to physical addresses at the time of memory
allocation to the program. There are three types of addresses used in a program before and after memory
allocated −
S.N. Memory Addresses & Description

1 Symbolic addresses
The addresses used in a source code. The variable names, constants, and instruction labels are the
basic elements of the symbolic address space.

2 Relative addresses
At the time of compilation, a compiler converts symbolic addresses into relative addresses.

3 Physical addresses
The loader generates these addresses at the time when a program is loaded into the main memory.
 Table 3.5: Memory addresses
Address binding
• Memory consists of a large array of words or arrays, each of which has an address associated with it.
Now the work of the CPU is to fetch instructions from the memory-based program counter. Now
further these instructions may cause loading or store to a specific memory address.
• Address binding is the process of mapping from one address space to another address space. The
logical address is the address generated by the CPU during execution whereas Physical Address refers
to a location in a memory unit (the one that is loaded into memory).
• Note that the user deals with only a logical address (Virtual address). The logical address undergoes
translation by the MMU or address translation unit. The output of this process is the appropriate
physical address or the location of code/data in RAM.

An address binding can be done in three different ways:

Compile Time – It work is to generate a logical address (also known as virtual address). If you know that during
compile time where the process will reside in memory, then an absolute address is generated.
Load time – It will generate the physical address. If at the compile-time it is not known where the process will
reside then a relocatable address will be generated.
Execution time- It helps in differing between physical and logical address. This is used if the process can be
moved from one memory to another during execution (dynamic linking-Linking that is done during load or run
time).

Virtual and physical addresses are the same in compile-time and load-time address-binding schemes. Virtual
and physical addresses differ in the execution-time address-binding scheme.

Logical and Physical address space:

• A logical Address is address generated by the CPU while a program is running. The logical address is
also called a virtual address as it does not exist physically. The set of all logical address space is called
logical address space. The logical address is mapped to the corresponding physical address
using MMU (Memory Management Unit).
• Compile-time and load time address binding produces the same logical and physical address,
while run time address binding produces different.
• Physical address is the actual address location in a memory unit. This is computed by MMU. Users can
access physical address in the memory unit using the corresponding logical address.
• The set of all logical addresses generated by a program referred to as a logical address space the set of
all physical addresses corresponding to these logical addresses referred to as physical address space

Static vs. Dynamic Loading

• The choice between Static or Dynamic Loading is to make at the time of computer program
development. If you have to load your program statically, then at the time of compilation, the
complete programs compiled, linked without leaving any external program or module dependency the
linker combines the object program with other necessary object modules into an absolute program,
which also includes logical addresses.
• If you are writing a dynamically loaded program, then your compiler will compile the program and for
all the modules, which you want to include dynamically, only references provided and the rest of the
work done at the time of execution
• At the time of loading, with static loading, the absolute program (and data) is loaded into memory for
execution to start.
• If you are using dynamic loading, dynamic routines of the library are stored on a disk in re-locatable
form and are loaded into memory only when they are needed by the program
Static vs. Dynamic Linking
• When static linking is used, the linker combines all other modules needed by a program into a single
executable program to avoid any runtime dependency.
• When dynamic linking used, it is not required to link the actual module or library with the program,
rather a reference to the dynamic module provided at the time of compilation and linking.

Memory Management Unit (MMU)

• The CPU scheduler selects a process for execution, the dispatcher loads the relocation and limit
registers with the correct values as part of the context switch. Because every address generated by the
CPU is checked against these registers, we can protect both the operating system and the other users'
programs and data from being modified by this running process.
• The relocation-register scheme provides an effective way to allow the operating-system size to change
dynamically. This flexibility is desirable in many situations. For example, the operating system contains
code and buffer space for device drivers. If a device driver is not commonly used, we do not want to
keep the code and data in memory, as we might be able to use that space for other purposes. Such
code is sometimes called transient operating-system code; it comes and goes as needed. Thus, using
this code changes the size of the operating system during program execution.

To protect the operating system code and data by the user processes as well as protect user processes from
one another using relocation register and limit register. This is depicted in the figure below:

Figure 3.8: MMU

Contiguous Memory Allocation:

• In Contiguous Memory allocation strategies, the Operating System allocates memory to a process that
is always in a sequence for faster retrieval and less overhead, but this strategy supports static memory
allocation only.
• This strategy is inconvenient in the sense that there are more instances of internal memory
fragmentation than compared to contiguous memory allocation strategies.
• The Operating System can also allocate memory dynamically to a process if the memory is not in
sequence; i.e. they are placed in non–contiguous memory segments.
• Memory is allotted to a process as it is required. When a process no longer needs to be in memory, it
is released from the memory to produce a free region of memory or a memory hole. These memory
holes and the allocated memory to the other processes remain scattered in memory.
 • The Operating System can compact this memory at a later point in time to ensure that the allocated
memory is in a sequence and the memory holes are not scattered. This strategy has support for
dynamic memory allocation and facilitates the usage of Virtual Memory. In dynamic memory
allocation, there are no instances of internal fragmentation.

Memory management Techniques: In an operating system, the following are four common memory
management techniques.
1. Single contiguous allocation: Simplest allocation method used by MS-DOS. All memory (except some
reserved for OS) is available to a process.
2. Partitioned allocation: Memory is divided into different blocks
3. Paged memory management: Memory is divided into fixed-sized units called page frames, used in a
virtual memory environment.
4. Segmented memory management: Memory is divided into different segments (a segment is a logical
grouping of process' data or code) in this management, allocated memory doesn’t have to be
contiguous.

Memory Allocation:
Single Partition Allocation: In this memory allocation method, the operating system resides in the low
memory, and the remaining memory is treated as a single partition. This single partition is available for user -
space, only one job can be loaded in this user space.

Figure 3.9: Single Partition Allocation

Multiple Partitions Memory Management: This method can be implemented in 3 ways. These are:
1. Fixed-equal Multiple Partitions
2. Fixed-variable Partitions
3. Dynamic Partitions

Fixed-equal Multiple Partitions: In this memory management, the operating system occupies the low memory
and the rest of the main memory is available for user-space. The user space is divided into fixed partitions. The
partition sizes are depending on the operating system.

Fixed-variable Partitions: In this memory management, the user space of the main memory is divided into the
number of partitions, but the partition sizes are different lengths. The operating system keeps a table
indicating which partitions of memory are available and which are occupied.

Dynamic Partitions: To eliminate some of the problems with fixed partitions, an approach known as Dynamic
Partitions. In this method, partitions are created dynamically, so that each process is loaded into the partition
of the same size at that process.

Figure 3.10: Multiple Partition Allocation

Placement Algorithm
• If the free memory is present within a partition, then it is called "internal fragmentation". Similarly, if
the free blocks are present outside the partition, then it is called "external fragmentation". The
solution to the "external fragmentation" is compaction.
• The solution to the "internal fragmentation" is the "placement" algorithm only. Because memory
compaction is time-consuming when it is time to load or swap a process into main memory and if there
is more than one free block of memory of sufficient size, then the operating system must decide which
free block to allocate by using three different placement algorithms.

Types of placement algorithms:

• Best-fit: - It chooses the block that is closest in size to the given request from the beginning to the
ending free blocks. We must search the entire list unless it is ordered by size. This strategy produces
the smallest leftover hole.
• Worst-fit: - It allocates the largest block. We must search the entire list unless it is sorted by size. This
strategy produces the largest leftover hole, which may be more useful than the smaller leftover hole
from a best-fit approach.
• First-fit: - It begins to scan memory from the beginning and chooses the first available block which is
large enough. Searching can start either at the beginning of the set of blocks or where the previous
first-fit search ended. We can stop searching as soon as we find a free block that is large enough.
Fragmentation
As processes are loaded and removed from memory, the free memory space is broken into little pieces. It
happens after sometimes that processes cannot be allocated to memory blocks considering their small size
and memory blocks remain unused this problem is known as Fragmentation.
Fragmentation is of two types –
1. External fragmentation: Total memory space is enough to satisfy a request or to reside a process in it,
but it is not contiguous, so it cannot be used
 2. Internal fragmentation: The memory block assigned to the process is bigger. Some portion of memory
left unused, as it cannot be used by another process.

The following diagram shows how fragmentation can cause waste of memory and a compaction technique
can be used to create more free memory out of fragmented memory

Figure 3.11: Fragmentation

External fragmentation can be reduced by compaction or shuffle memory contents to place all free memory
together in one large block. To make compaction feasible, relocation should be dynamic
The internal fragmentation can be reduced by effectively assigning the smallest partition but large enough for
the process.

Paging
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical
memory. This scheme permits the physical address space of a process to be non – contiguous.
● Logical Address or Virtual Address (represented in bits): An address generated by the CPU
● Logical Address Space or Virtual Address Space (represented in words or bytes): The set of all logical
addresses generated by a program
● Physical Address (represented in bits): An address available on the memory unit
● Physical Address Space (represented in words or bytes): The set of all physical addresses corresponding
to the logical addresses

Example:
● If Logical Address = 31 bit, then Logical Address Space = 231 words = 2 G words (1 G = 230)
● If Logical Address Space = 128 M words = 27 * 220 words, then Logical Address = log2 227 = 27 bits
● If Physical Address = 22 bit, then Physical Address Space = 222 words = 4 M words (1 M = 220)
● If Physical Address Space = 16 M words = 24 * 220 words, then Physical Address = log2 224 = 24 bits

The mapping from virtual to physical address is done by the memory management unit (MMU) which is a
hardware device and this mapping is known as the paging technique.
● The Physical Address Space is conceptually divided into a number of fixed-size blocks, called frames.
● The Logical Address Space is also split into fixed-size blocks, called pages.
● Page Size = Frame Size

Let us consider an example:

● Physical Address = 12 bits, then Physical Address Space = 4 K words
● Logical Address = 13 bits, then Logical Address Space = 8 K words
● Page size = frame size = 1 K words (assumption)
 Figure 3.12: Paging

The address generated by the CPU is divided into

● Page number(p): Number of bits required to represent the pages in Logical Address Space or Page
number
● Page offset(d): Number of bits required to represent a particular word in a page or page size of Logical
Address Space or word number of a page or page offset.
Physical Address is divided into
● Frame number (f): Number of bits required to represent the frame of Physical Address Space or Frame
number.
● Frame offset (d): Number of bits required to represent a particular word in a frame or frame size of
Physical Address Space or word number of a frame or frame offset.

Advantages and Disadvantages of Paging

Here is a list of advantages and disadvantages of paging −
● Paging reduces external fragmentation but still suffers from internal fragmentation.
● Paging is simple to implement and assumed as an efficient memory management technique.
● Due to the equal size of the pages and frames, swapping becomes very easy.
● Page table requires extra memory space, so may not be good for a system having small RAM.

TLB (Translation Look aside buffer)

The hardware implementation of the page table can be done by using dedicated registers. But the usage of
register for the page table is satisfactory only if the page table is small. If the page table contains a large
number of entries then we can use TLB (Translation Look aside buffer), a special, small, fast lookup hardware
cache.
● The TLB is associative, high-speed memory.
● Each entry in TLB consists of two parts: a tag and a value.
● When this memory is used, then an item is compared with all tags simultaneously. If the item is found,
 then the corresponding value is returned.

Figure 3.13: TLB

Page Fault
• A page fault occurs when a program attempts to access a block of memory that is not stored in the
physical memory or RAM.
• The fault notifies the operating system that it must locate the data in virtual memory, and then
transfer it from the storage device, such as an HDD or SSD, to the system RAM. Though the term "page
fault" sounds like an error, page faults are common and are part of the normal way computers handle
virtual memory.
• In programming terms, a page fault generates an exception, which notifies the operating system that it
must retrieve the memory blocks or "pages" from virtual memory for the program to continue. Once
the data is moved into physical memory, the program continues as normal.
• This process takes place in the background and usually goes unnoticed by the user.
So when a page fault occurs then the following sequence of events happens:
 Figure 3.14: Page fault
Segmentation
• Segmentation is a memory management technique in which each job is divided into several segments
of different sizes; each segment is a different logical address space of the program.
• When a process is to be executed, its corresponding segmentation is loaded into non-contiguous
memory though every segment is loaded into a contiguous block of available memory.
• Segmentation memory management works very similar to paging but here segments are of variable
length whereas in paging pages are of fixed size.
• A program segment contains the program's main function, utility functions, data structures, and so on.
The operating system maintains a segment map table for every process and a list of free memory
blocks along with segment numbers, their size and corresponding memory locations in the main
memory. For each segment, the table stores the starting address of the segment and the length of the
segment. A reference to a memory location includes a value that identifies a segment and an offset.

Figure 3.15: Segmentation

Segmentation with paging
● Treat virtual address space as a collection of segments (logical units) of arbitrary sizes.
● Treat physical memory as a sequence of fixed-size page frames.
● Segments are typically larger than page frames
 ◦ Map a logical segment onto multiple page frames by paging the segments

Addresses in a Segmented Paging System

● A virtual address becomes a segment number, a page within that segment, and an offset within the page.
● The segment number indexes into the segment table which yields the base address of the page table for
that segment.
● Check the remainder of the address (page number and offset) against the limit of the segment.
● Use the page number to index the page table. The entry is the frame. (The rest of this is just like paging.)
● Add the frame and the offset to get the physical address.

Figure 3.16: Segmented Paging

Effective access time:
Main memory access time = m
If page tables are kept in the main memory
Effective access time = m (for page table) + m (for particular page in page table)

The percentage of times that the page number of interest is found in the TLB is called the hit ratio. An 80-per
cent hit ratio, for example, means that we find the desired page number in the TLB 80 percent of the time. If it
takes 100 nanoseconds to access memory, then mapped-memory access takes 100 nanoseconds when the
page number is in the TLB. If we fail to find the page number in the TLB then we must first access memory for
the page table and frame number (100 nanoseconds) and then access the desired byte in memory (100
nanoseconds), for a total of 200 nanoseconds. (We are assuming that a page-table lookup takes only one
memory access)
To find the effective memory-access time, we weight the case by its probability: effective access time = 0.80 ×
100 + 0.20 × 200 = 120 nanoseconds

Concept of virtual memory

A computer can address more memory than the amount physically installed on the system. This extra memory
is called virtual memory and it is a section of a hard disk that's set up to emulate the computer's RAM.
The main visible advantage of this scheme is that programs can be larger than physical memory. Virtual
memory serves two purposes. First, it allows us to extend the use of physical memory by using the disk.
Second, it allows us to have memory protection because each virtual address is translated to a physical
address.
Following are the situations, when the entire program is not required to be loaded fully in the main memory.
● Many tables are assigned a fixed amount of address space even though only a small amount of the
table is used.
● The ability to execute a program that is only partially in memory would counter many benefits.
● Less number of I/O would be needed to load or swap each user program into memory.
● A program would no longer be constrained by the amount of physical memory that is available.
● Each user program could take less physical memory; more programs could be run at the same time,
with a corresponding increase in CPU utilization and throughput.
Modern microprocessors intended for general-purpose use, a memory management unit, or MMU, is built
into the hardware. The MMU's job is to translate virtual addresses into physical addresses. A basic example is
given below −

Figure 4.1: Virtual Addresses Mapping to Physical Address

Cache memory organization

Cache memory is a fast random access memory where the computer hardware stores copies of information
currently used by programs (data and instructions), loaded from the main memory. The cache has a
significantly shorter access time than the main memory due to the applied faster but more expensive
implementation technology. The cache has a limited volume that also results from the properties of the
applied technology. If information fetched to the cache memory is used again, the access time to it will be
much shorter than in the case if this information were stored in the main memory and the program will
execute faster.

Time efficiency of using cache memories results from the locality of access to data that is observed during
program execution.

Time locality: Time locality consists of a tendency to use many times the same instructions and data in
programs during neighbouring time intervals.
Space locality: Space locality is a tendency to store instructions and data used in a program in short distances
of time under neighbouring addresses in the main memory.

• Due to these localities, the information loaded to the cache memory is used several times and the
execution time of programs is much reduced.
• The cache can be implemented as a multi-level memory. Contemporary computers usually have two
levels of caches. In older computer models, a cache memory was installed outside a processor (in
separate integrated circuits than the processor itself).
• The access to it was organized over the processor external system bus. In today's computers, the first
level of the cache memory is installed in the same integrated circuit as the processor.
• It significantly speeds up the processor's cooperation with the cache. Some microprocessors have the
second level of cache memory placed also in the processor's integrated circuit.
• The volume of the first-level cache memory is from several thousand to several tens of thousands of
bytes. The second-level cache memory has a volume of several hundred thousand bytes.
• Cache memory is maintained by a special processor subsystem called cache controller.

Read implementation in cache memory on hit

If there is cache memory in a computer system, then at each access to the main memory address to fetch data
or instructions, processor hardware sends the address first to the cache memory. The cache control unit
checks if the requested information resides in the cache. If so, we have a "hit" and the requested information
is fetched from the cache. The actions concerned with a reading with a hit are shown in the figure below.

Figure 4.2: Read implementation in cache memory on hit

Read implementation in cache memory on miss

If the requested information does not reside in the cache, we have a "miss" and the necessary information is
fetched from the main memory to the cache and the requesting processor unit. The information is not copied
in the cache as single words but as a larger block of a fixed volume. Together with the information block, a
part of the address of the beginning of the block is always copied into the cache. This part of the address is
next used at readout during identification of the proper information block. The actions executed in cache
memory on "miss" are shown below.
Figure 4.3: Read implementation in cache memory on miss

Memory updating methods after cache modification:

A cache memory contains copies of data stored in the main memory. When a change of data in a cache takes
place (ex. a modification due to a processor write) the contents of the main memory and cache memory cells
with the same address, are different. To eliminate this lack of data coherency two methods are applied:

• Write through, the new cache contents are written down to the main memory immediately after the
write to the cache memory,
• Write back, the new cache contents are not written down to the main memory immediately after the
change, but only when the given block of data is replaced by a new block fetched from the main
memory or an upper-level cache. After a data write to the cache, only state bits are changed in the
modified block, indicating that the block has been modified (a dirty block).

Demand Paging
A demand paging system is quite similar to a paging system with swapping where processes reside in
secondary memory and pages are loaded only on demand, not in advance. When a context switch occurs, the
operating system does not copy any of the old program’s pages out to the disk or any of the new program’s
pages into the main memory Instead, it just begins executing the new program after loading the first page and
fetches that program’s pages as they are referenced.

Figure 4.4: Demand Paging

While executing a program, if the program references a page that is not available in the main memory because
it was swapped out a little ago, the processor treats this invalid memory reference as a page fault and
transfers control from the program to the operating system to demand the page back into the memory.
Advantages
Following are the advantages of Demand Paging −
● Large virtual memory.
● More efficient use of memory.
● There is no limit on the degree of multiprogramming.
Disadvantages
● The number of tables and the amount of processor overhead for handling page interrupts are greater
than in the case of the simple paged management techniques.

Page Replacement Algorithm

Page replacement algorithms are the techniques using which an Operating System decides which memory
pages to swap out, write to disk when a page of memory needs to be allocated. Paging happens whenever a
page fault occurs and a free page cannot be used for allocation purposes accounting for to reason that pages
are not available or the number of free pages is lower than required pages.
When the page that was selected for replacement and was paged out, is referenced again, it has to read in
from disk, and this requires I/O completion. This process determines the quality of the page replacement
algorithm: the lesser the time waiting for page-ins, the better is the algorithm.
A page replacement algorithm looks at the limited information about accessing the pages provided by
hardware and tries to select which pages should be replaced to minimize the total number of page misses
while balancing it with the costs of primary storage and processor time of the algorithm itself. There are many
different page replacement algorithms. We evaluate an algorithm by running it on a particular string of
memory references and computing the number of page faults,
Reference String
The string of memory references is called reference string. Reference strings are generated artificially or by
tracing a given system and recording the address of each memory reference. The latter choice produces a
large number of data, where we note two things.
● For a given page size, we need to consider only the page number, not the entire address.
● If we have a reference to page p, then any immediately following references to page p will never cause
a page fault. Page p will be in memory after the first reference; the immediately following references
will not fault.
For example, consider the following sequence of addresses − 123, 215, 600, 1234, 76, 96. If page size is 100,
then the reference string is 1,2,6,12,0,0

First in First Out (FIFO) algorithm

● The oldest page in the main memory is the one that will be selected for replacement.
● Easy to implement, keep a list, replace pages from the tail and add new pages at the head.
Figure 4.5: FIFO Algorithm Example
Optimal Page algorithm
● An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms. An optimal
page-replacement algorithm exists and has been called OPT or MIN.
● Replace the page that will not be used for the longest period. Use the time when a page is to be used.

Figure 4.6: Optimal Algorithm Example

The Least Recently Used (LRU) algorithm

● The page which has not been used for the longest time in the main memory is the one that will be
selected for replacement.
● Easy to implement, keep a list, replace pages by looking back into time.
Figure 4.7: Least Recently Used Algorithm Example

Allocation of Frames

Frame allocation algorithms are used if OS uses multiple processes; it helps decide how many frames to
allocate to each process.
There are various constraints to the strategies for the allocation of frames:
● OS cannot allocate more than the total number of available frames.
● At least a minimum number of frames should be allocated to each process. This constraint is supported
by two reasons. The first reason is, as less number of frames are allocated, there is an increase in the
page fault ratio, decreasing the performance of the execution of the process. Secondly, there should be
enough frames to hold all the different pages that any single instruction can reference.

Frame allocation algorithms: The two algorithms commonly used to allocate frames to a process are
1. Equal allocation: In a system with x frames and y processes, each process gets equal number of frames,
i.e. x/y. For instance, if the system has 48 frames and 9 processes, each process will get 5 frames. The
three frames which are not allocated to any process can be used as a free-frame buffer pool.
2. Proportional allocation: Frames are allocated to each process according to the process size. For a
process pi of size si, the number of allocated frames is ai = (si/S)*m, where S is the sum of the sizes of
all the processes and m is the number of frames in the system. For instance, in a system with 62
frames, if there is a process of 10KB and another process of 127KB, then the first process will be
allocated (10/137)*62 = 4 frames and the other process will get (127/137)*62 = 57 frames.

Global and Local Allocation

The number of frames allocated to a process can also dynamically change depending on whether OS used
global replacement or local replacement for replacing pages in case of a page fault.

● Global: When a process needs a page which is not in the memory, it can bring in the new page and
allocate it a frame from the set of all frames, even if that frame is currently allocated to some other
process; that is, one process can take a frame from another.
● Local: When a process needs a page which is not in the memory, it can bring in the new page and
allocate it a frame from its own set of allocated frames only.

Thrashing
Whenever a page fault happens, operating system will try to fetch that page from secondary memory and try
to swap it with one of the page in RAM. This is called swapping.
If this page fault and then swapping happening very frequently at higher rate, then operating system has to
spend more time to swap these pages. This state is called thrashing. Because of this, CPU utilization is going to
be reduced.

Figure 4.8: Thrashing

Example: If any process does not have the number of frames that it needs to support pages in active use then
it will quickly page fault. And at this point, the process must replace some pages. As all the pages of the
process are actively in use, it must replace a page that will be needed again right away. Consequently, the
process will quickly fault again, and again, replacing pages that it must bring back in immediately. This high
paging activity by a process is called thrashing.

Causes of Thrashing
● Thrashing affects the performance of execution in the Operating system. Also, thrashing results in
severe performance problems in the Operating system.
● When the utilization of CPU is low, then the process scheduling mechanism tries to load many
processes into the memory at the same time due to which degree of multiprogramming can be
increased. Now in this situation, there are more processes in the memory as compared to the available
number of frames in the memory. Allocation of the limited amount of frames to each process.
● Whenever any process with high priority arrives in the memory and if the frame is not freely available
at that time then the other process that has occupied the frame is residing in the frame will move to
secondary storage and after that this free frame will be allocated to higher priority process.

Demand Segmentation: Same idea as demand paging applied to segments.

• If a segment is loaded, the base and limit are stored in the STE and the valid bit is set in the PTE.
• The PTE is accessed for each memory reference.
• If the segment is not loaded, the valid bit is unset. The base and limit as well as the disk address of the
segment are stored in the OS table.
• A reference to a non-loaded segment generates a segment fault (analogous to page fault).
• To load a segment, we must solve both the placement question and the replacement question (for
demand paging, there is no placement question).