Memory Management

Address uniquely identifies a location in the memory. There are two types of
addresses that are logical address and physical address. The logical address
is a virtual address and can be viewed by the user. The user can’t view the
physical address directly. The logical address is used like a reference, to
access the physical address.

The fundamental difference between logical and physical address is

that logical address is generated by CPU during a program execution whereas,
the physical address refers to a location in the memory unit.

BASIS FOR
LOGICAL ADDRESS PHYSICAL ADDRESS
COMPARISON

Basic It is the virtual The physical address is

address generated a location in a memory
by CPU unit.

Address Set of all logical Set of all physical

Space addresses addresses mapped to
generated by CPU the corresponding
in reference to a logical addresses is
program is referred referred as Physical
as Logical Address Address.
Space.
Visibility The user can view The user can never
the logical address view physical address
of a program. of program

Access The user uses the The user can not

logical address to directly access
access the physical physical address.
address.
 BASIS FOR
LOGICAL ADDRESS PHYSICAL ADDRESS
COMPARISON

Generation The Logical Physical Address is

Address is Computed by Memory
generated by the Management Unit
CPU

Definition of Logical Address

Address generated by CPU while a program is running is referred as Logical
Address. The logical address is virtual as it does not exist physically. Hence,
it is also called as Virtual Address. This address is used as a reference to
access the physical memory location. The set of all logical addresses
generated by a programs perspective is called Logical Address Space.

The logical address is mapped to its corresponding physical address by a

hardware device called Memory-Management Unit. The address-binding
methods used by MMU generates identical logical and physical address
during compile time and load time. However, while run-time the address-
binding methods generate different logical and physical address.

Definition of Physical Address

Physical Address identifies a physical location in a memory. MMU (Memory-

Management Unit) computes the physical address for the corresponding
logical address. MMU also uses logical address computing physical address.
The user never deals with the physical address. Instead, the physical address
is accessed by its corresponding logical address by the user.

The user program generates the logical address and thinks that the program
is running in this logical address. But the program needs physical memory
for its execution. Hence, the logical address must be mapped to the physical
address before they are used.

The logical address is mapped to the physical address using a hardware

called Memory-Management Unit. The set of all physical addresses
corresponding to the logical addresses in a Logical address space is
called Physical Address Space.

Base register and Limit register

Base register: Specifies the smallest legal physical memory address.
Limit register: Specifies the size of the range.
A pair of base and limit registers specifies the logical address space.
The base and limit registers can be loaded only by the operating system.

Ex:If the base register holds 300040 and the limit register is 120900, then
the program can legally access all addresses from 300040 through 420939

Address Binding

Address binding is the process of mapping from one address space to

another address space. Logical address is address generated by CPU during
execution whereas Physical Address refers to location in memory unit.

An address binding can be done in three different ways:

Compile-time Address Binding:

 If the compiler is responsible for performing address binding then it is

called compile-time address binding.
 It will be done before loading the program into memory.
 The compiler requires interacts with an OS memory manager to
perform compile-time address binding

Load time Address Binding:

 It will be done after loading the program into memory.

 This type of address binding will be done by the OS memory manager i.e
loader.

Execution time or dynamic Address Binding:

 It will be postponed even after loading the program into memory.
 The program will be kept on changing the locations in memory until the
time of program execution.
 The dynamic type of address binding done by the processor at the time of
program execution.

MMU (Memory Management Unit)

The run time mapping between Virtual address and Physical Address is done
by hardware device known as MMU.
In memory management, Operating System will handle the processes and
moves the processes between disk and memory for execution. It keeps the
track of available and used memory.
Instruction-execution cycle Follows steps:
1. First instruction is fetched from memory e.g. ADD A,B
2. Then these instructions are decoded i.e., Addition of A and B
3. And further loading or storing at some particular memory location takes
place.

Multistep Processing of a User Program

Program is a sequence of instructions written by the user that instruct the
computer to perform the task of solving some problem. Before the
program executed, the various steps are:
Basic Hardware
As main memory and registers are built into processor and CPU can access
these only. So every instructions should be written in direct access storage
devices. If CPU access instruction from register then it can be done in one
CPU clock cycle as registers are built into CPU.

If instruction resides in main memory then it will be accessed via memory

bus that will take lot of time. So remedy to this add fast memory in between
CPU and main memory i.e. adding cache for transaction.
Legal address consists of base register (holds smallest physical address) and
limit register(size of range).
For example:
Base register = 300040
limit register = 120900
then legal address = (300040+120900)= 420940(inclusive).
legal address = base register+ limit register
How processes are mapped from disk to memory
1. Usually process resides in disk in form of binary executable file.
2. So to execute process it should reside in main memory.
3. Process is moved from disk to memory based on memory management in
use.
4. The processes waits in disk in form of ready queue to acquire memory .

Procedure of mapping of disk and memory

Normal procedure is that process is selected from input queue and loaded in
memory. As process executes it accesses data and instructions from memory
and as soon as it completes it will release memory and now memory will be
available for other processes.
MMU scheme – CPU------- MMU------Memory

1. CPU will generate logical address for eg: 346

2. MMU will generate relocation register(base register) for eg:14000
3. In Memory physical address is located eg:(346+14000= 14346)

Dynamic loading and Dynamic linking

To run a process, the entire process and its data must be in physical
memory. Thus, the size of a process is limited to the size of physical
memory. The dynamic loading and linking are run-time operations.

Linking and Loading: are the utility programs that play a important role
in the execution of a program. Linking intakes the object codes generated by
the assembler and combines them to generate the executable module. On
the other hand, the loading loads this executable module to the main
memory for execution.
Loading: Bringing the program from secondary memory to main memory
is called Loading.
Linking: Establishing the linking between all the modules or all the
functions of the program in order to continue the program execution is called
linking.
Differences between Linking and Loading:
1. The key difference between linking and loading is that the linking
generates the executable file of a program whereas, the loading loads
the executable file obtained from the linking into main memory for
execution.
2. The linking intakes the object module of a program generated by the
assembler. However, the loading intakes the executable module
generated by the linking.
3. The linking combines all object modules of a program to generate
executable modules it also links the library function in the object module
to built-in libraries of the high-level programming language. On the other
hand, loading allocates space to an executable module in main memory.

Dynamic Loading
The dynamic binding is a method to obtain better memory-space utilization.
A routine is not loaded until it is called, until then all routine remains in the
disk as relocatable code format.

A routing can call another routine, but it checks if another routine is loaded
or not. If not, then relocatable linking loader is called to load the routine into
memory and update program’s address tables to reflect this change. The
control is passed to the newly loaded routine.

The total program may be large but only a small portion is loaded. The
unused routine is never loaded into memory.

It is the programmer’s responsibility to implement dynamic loading, the OS

can provide library routines to implement the dynamic loading.

Dynamic Linking
The dynamic linking, similar to dynamic loading is delayed until run-time.
This feature is used with system libraries such as language subroutine
libraries. Without this facility, each program must include a copy of its
language library in the executable image which wastes memory space.

There are several benefits of dynamic linking:

– library routines not part of program code. A program is much smaller
without the routines and loads faster into the memory.
– One copy of library routing is referred by many programs, therefore, saving
disk space and memory space.

Overlays in Memory Management

The main problem in Fixed partitioning is the size of a process has to be
limited by the maximum size of the partition, which means a process can
never be span over another. Solution to this problem is Overlays.
The concept of overlays is that whenever a process is running it will not use
the complete program at the same time, it will use only some part of it. So
overlay is a technique to run a program that is bigger than the size of the
physical memory by keeping only those instructions and data that are
needed at any given time. Divide the program into modules in such a way
that not all modules need to be in the memory at the same time.

Advantage –
 Reduce memory requirement
 Reduce time requirement

Disadvantage –
 Overlap map must be specified by programmer
 Programmer must know memory requirement
 Overlaped module must be completely disjoint
 Programmming design of overlays structure is complex and not possible
in all cases

Swapping
Swapping is a mechanism in which a process can be swapped temporarily
out of main memory (or move) to secondary storage (disk) and make that
memory available to other processes. At some later time, the system swaps
back the process from the secondary storage to main memory.
Though performance is usually affected by swapping process but it helps in
running multiple and big processes in parallel.
Benefits of Swapping

Here, are major benefits/pros of swapping:

 It offers a higher degree of multiprogramming.

 Allows dynamic relocation. For example, if address binding at
execution time is being used, then processes can be swap in different
locations. Else in case of compile and load time bindings, processes
should be moved to the same location.
 It helps to get better utilization of memory.
 Minimum wastage of CPU time on completion so it can easily be
applied to a priority-based scheduling method to improve its
performance.
What is Memory allocation?

Memory allocation is a process by which computer programs are assigned

memory or [Link], main memory is divided into two types of partitions

1. Low Memory - Operating system resides in this type of memory.

2. High Memory- User processes are held in high memory.

Partition Allocation

Memory is divided into different blocks or partitions. Each process is

allocated according to the requirement. Partition allocation is an ideal
method to avoid internal fragmentation.

Below are the various partition allocation schemes :

 First Fit: In this type fit, the partition is allocated, which is the first
sufficient block from the beginning of the main memory.

let us assume the jobs and the memory requirements as the following:
 Job 1 90k
Job 2 20k
Job 3 50k
Job 4 10k
 Let the free pace memory allocation blocks be:
 Block 1 50k
Block 2 100k
Block 3 90k
Block 4 200k
Block 5 50k
 50k 100k 90k 200k 50k
 [Link] 1 (size – 90k)
The job cannot fit in the first block as 50k (block size) < 90k (job size).
 • Goes to block 2 as can fit in block 2 as 100K > 90K (Size of the block more
than the size of the process).
• The job is assigned to the second block.
• 10K remains empty in this block now.
 2. Job 2 (size 20K)
 • The job can easily fit in the first block 20K < 100k•Job is assigned to the first
block.
• 30k remains empty in this block now
 [Link] 3 (size 50 K)
• The next empty memory block is the third block with condition 50k < 90k.
• The job is thus allocated to the third block.
• 40k remains empty in this block.
 [Link] 4 (10k)
• The first, second, and the third blocks in the memory are already occupied.
• The fourth job thus reaches the fourth empty memory block.
• The size of the block is greater than the size of the job (200k > 10 k).
• The memory block is assigned to the fourth job.
• 190k remains empty in this block.
 [Link] 5 (100k)
• Memory blocks one to five are already occupied.
• Job 5 reaches the fifth memory block but cannot be assigned to it as the
block is smaller than the required memory space.
• Thus, the job has to wait until a job is finished and an empty space is
released.
 Job 5 remains do not get a memory, and the last memory block remains
unallocated.
The following diagrammatic representation shows memory allocation after the
first fit method.
Job 2(20k) Job 1(90k) Job 3 (50k) Job 4 (10


50k 100k 90k 200k 50k
 Unused memory
Block 1= 30 K
Block 2= 10 K
Block 3= 40 K
Block 4= 190 K
Block 5= 50 K

 Best Fit: It allocates the process to the partition that is the first
smallest partition among the free partitions.

let us assume the jobs and the memory requirements as the following:

 Job 1 90k
Job 2 20k
Job 3 50k
Job 4 200k

 Let the free space memory allocation blocks be:

 Block 1 50k
Block 2 100k
Block 3 90k
 Block 4 200k
Block 5 50k

 50k 100k 90k 200k 50k

 1. Job 1 (size – 90k)

• The memory is traversed searching for the memory space with minimum
wastage.
• The first block is not assigned as it is smaller than the demanded memory.
50k (block size) < 90k (job size).
• The second block is also not allocated as it will cause memory wastage.
• Control moves to the third block which is then allocated as the process size
and the memory sizes are equal.
• Job 1 is assigned to block 3 with no memory wastage.

 2. Job 2 (size – 20k)

• The CPU searches the memory for an empty memory slot which is either
equal to or more than 100k.
• The first block is selected as it is slightly greater than the process size.
• Block 1 is allocated to the second process.
• Waste in size is of 30k

 3. Job 3 (size – 50k)

• The CPU searches the entire memory block to allocate free memory.
• The first block is already allocated to job 2. Hence it is skipped.
• The CPU moves to the second block but is greater in size than the
demanded memory (50 k < 100 k).
• The third block is already occupied, and hence it is skipped.
• The CPU now moves to the fourth block which is also greater than the
demanded size. Hence it is also skipped.
 • Now the fifth block is accessed. In this case, the demanded memory and the
available memory sizes are equal (50k = 50k).
• Hence the block five are allocated to job 3.

 4. Job 4 (size- 200k)

• The CPU searches the memory blocks for allocation.
• It skips the first block as it is already occupied.
• The second block in the memory is skipped as it is smaller than the
demanded memory.
• The third memory block is also skipped as it is already occupied.
• CPU then moves to the fourth memory block which is finally allocated as its
size exactly meets the demanded memory size of the process (200k = 200k).
• Block four is allocated to the memory which no memory wastage.

 5. All the processes are assigned memory blocks.

6. Block second remains unoccupied at the end of the memory allocation
procedure.

 Worst Fit: It allocates the process to the partition, which is the largest
sufficient freely available partition in the main memory.

let us assume the jobs and the memory requirements as the following:
 Job 1 10k
Job 2 20k
 Job 3 30k
Job 4 70k
 Let the free space memory allocation blocks be:
 Block 1 50k
Block 2 100k
Block 3 90k
Block 4 200k
Block 5 50k
 50k 100k 90k 200k 50k
 1. Job1 (Size – 10k)
• The CPU searches the empty memory slots which is greater than the
demanded memory.
• It skips memory block one, two, and three to find the largest empty memory
space.
• The CPU allocated memory block four which is of 200k and is the largest
among all the slots.
• Job 1 is assigned to block four.
• The wasted memory is 190k.
 2. Job 2 (size – 20k)
• The CPU searches for the largest empty block.
• It skips the first memory block and reaches to the second.
• As the second is the largest empty block available, it is allotted to the
second job.
• The memory wastage, in this case, is 80k.
 3. Job 3 (size- 30k)
• The CPU skips the first memory block as an empty block of 90k remains
empty.
• It skips the second block as it is already occupied by job 2.
 • CPU finds an empty block of size 90k and assigns it to job 3.
• The third block is assigned to job 3.
• The amount of wasted memory, in this case, is 60k.
 4. Job 4 (size -70k)
• The CPU skips the first memory block as it is smaller than the demanded
memory.
• It further skips the second, third and fourth blocks as they are already
occupied.
• The CPU cannot allocate the fifth and the last block as it is smaller than the
demanded memory.
• Job 4 remains unassigned.
 5. Block one and six remain unoccupied, and Job 4 remains unassigned.
 Memory allocation at the end of the algorithm can be seen as follows.

Job 2 (20k) Job 3 (30k) Job 1 (10k)

 50k 100k 90k 200k 50k

 Unused memory
Block 1= 50k
Block 2= 80k
Block 3= 60 K
Block 4= 190 K
Block 5= 50 K
 Hence, the method involves a maximum amount of wastage memory and
hence is known as the Worst Fit method.

a) Contiguous memory allocation

In contiguous memory allocation, all the available memory space remain

together in one place. It means freely available memory partitions are not
scattered here and there across the whole memory space.
In the contiguous memory allocation, both the operating system and the user
must reside in the main memory. The main memory is divided into two
portions one portion is for the operating and other is for the user program.

In the contiguous memory allocation when any user process request for the
memory a single section of the contiguous memory block is given to that
process according to its need. We can achieve contiguous memory allocation
by dividing memory into the fixed-sized partition.

A single process is allocated in that fixed sized single partition. But this will
increase the degree of multiprogramming means more than one process in
the main memory that bounds the number of fixed partition done in memory.
Internal fragmentation increases because of the contiguous memory
allocation.

→ Fixed sized partition

In the fixed sized partition the system divides memory into fixed size
partition (may or may not be of the same size) here entire partition is
allowed to a process and if there is some wastage inside the partition then it
is called internal fragmentation.

→ Variable size partition

In the variable size partition, the memory is treated as one unit and space
allocated to a process is exactly the same as required and the leftover space
can be reused again.
b) Non-contiguous memory allocation

In the non-contiguous memory allocation the available free memory space

are scattered here and there and all the free memory space is not at one
place. So this is time-consuming. In the non-contiguous memory allocation, a
process will acquire the memory space but it is not at one place it is at the
different locations according to the process requirement. This technique
of non-contiguous memory allocation reduces the wastage of memory which
leads to internal and external fragmentation. This utilizes all the free
memory space which is created by a different process.

Difference between Contiguous and Non-contiguous Memory Allocation :

CONTIGUOUS NON-CONTIGUOUS

[Link] MEMORY MEMORY

. ALLOCATION ALLOCATION

Contiguous memory Non-Contiguous

allocation allocates memory allocation

consecutive blocks of allocates separate

memory to a blocks of memory to a

1. file/process. file/process.

2. Faster in Execution. Slower in Execution.

3. It is easier for the OS It is difficult for the OS

 CONTIGUOUS NON-CONTIGUOUS

[Link] MEMORY MEMORY

. ALLOCATION ALLOCATION

to control. to control.

Overhead is minimum

as not much address More Overheads are

translations are there there as there are

while executing a more address

4. process. translations.

External

Internal fragmentation fragmentation occurs

occurs in Contiguous in Non-Contiguous

memory allocation memory allocation

5. method. method.

It includes single

partition allocation

and multi-partition It includes paging and

6. allocation. segmentation.

Wastage of memory No memory wastage

7. is there. is there.

8. In contiguous In non-contiguous

memory allocation, memory allocation,

swapped-in swapped-in processes

processes are can be arranged in

arranged in the any place in the

originally allocated memory.

 CONTIGUOUS NON-CONTIGUOUS

[Link] MEMORY MEMORY

. ALLOCATION ALLOCATION

space.

What is Fragmentation?

Processes are stored and removed from memory, which creates free memory
space, which are too small to use by other processes.

After sometimes, that processes not able to allocate to memory blocks

because its small size and memory blocks always remain unused is called
fragmentation.

This type of problem happens during a dynamic memory allocation system

when free blocks are quite small, so it is not able to fulfill any request.

Two types of Fragmentation methods are:

 External fragmentation

 Internal fragmentation

Internal Fragmentation:
 Internal fragmentation happens when the memory is split into
mounted sized blocks. Whenever a method request for the memory,
the mounted sized block is allotted to the method. just in case the
memory allotted to the method is somewhat larger than the memory
requested, then the distinction between allotted and requested
memory is that the Internal fragmentation.

The above diagram clearly shows the internal fragmentation because the
difference between memory allocated and required space or memory is
called Internal fragmentation.

External Fragmentation:
External fragmentation happens when there’s a sufficient quantity of area
within the memory to satisfy the memory request of a method. however the
process’s memory request cannot be fulfilled because the memory offered is
during a non-contiguous manner. Either you apply first-fit or best-fit memory
allocation strategy it’ll cause external fragmentation.
In above diagram, we can see that, there is enough space (55 KB) to run a
process-07 (required 50 KB) but the memory (fragment) is not contiguous.
Here, we use compaction, paging or segmentation to use the free space to
run a process.
Difference between Internal fragmentation and External
fragmentation:-

S.N

O INTERNAL EXTERNAL
FRAGMENTATION FRAGMENTATION
In internal
fragmentation In external
fixed-sized fragmentation,
memory, blocks variable-sized
square measure memory blocks
appointed to square measure
1. process. appointed to method.
Internal
fragmentation External
happens when the fragmentation
method or process happens when the
is larger than the method or process is
2. memory. removed.
The solution of Solution of external
internal fragmentation is
fragmentation is compaction, paging
3. best-fit block. and segmentation.
4. Internal External
fragmentation fragmentation occurs
occurs when when memory is
memory is divided divided into variable
 S.N

O INTERNAL EXTERNAL
FRAGMENTATION FRAGMENTATION
size partitions based
into fixed sized on the size of
partitions. processes.
The unused spaces
The difference formed between non-
between memory contiguous memory
allocated and fragments are too
required space or small to serve a new
memory is called process, is called
Internal External
5. fragmentation. fragmentation .

Compaction
A possible remedy to the problem of external fragmentation is compaction.
The idea is to move all processes towards one end of memory and all the free
blocks of memory towards the other end.
For example, consider the case in which the blocks are distributed between 2
processes as shown in the below image.
 Using the compaction algorithm, we move process P2 upwards and the free block of
100K between P1 and P2 downwards thus forming a big block of 500K [(1600L-
2000K)400K+(800K-900K)100K]. However, compaction is possible only when
dynamic relocation is used i.e. when the address binding is done at runtime.

Segmentation in Operating System

A process is divided into Segments. The chunks that a program is divided into which are not
necessarily all of the same sizes are called segments. Segmentation gives user’s view of the
process which paging does not give.

There are types of segmentation:

1. Virtual memory segmentation –
Each process is divided into a number of segments, not all of which are resident at any one
point in time.
2. Simple segmentation –
Each process is divided into a number of segments, all of which are loaded into memory at
run time, though not necessarily contiguously.
 There is no simple relationship between logical addresses and physical addresses in
segmentation. A table stores the information about all such segments and is called Segment
Table.
Segment Table – It maps two-dimensional Logical address into one-dimensional Physical
address. It’s each table entry has:
 Base Address: It contains the starting physical address where the segments reside in
memory.
 Limit: It specifies the length of the segment.

Translation of Two dimensional Logical Address to one dimensional Physical Address.

 Address generated by the CPU is divided into:
 Segment number (s): Number of bits required to represent the segment.
 Segment offset (d): Number of bits required to represent the size of the segment.
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.