MEMORY

MANAGEMENT
Concept of address space
• Address uniquely identifies a location in memory
• Two types of addresses- logical address and physical address
Swapping
• Swapping is a method in which the process should be swapped temporarily
from the main memory to the backing store. It will be later brought back into
the memory for continue execution.
• Backing store is a hard disk or some other secondary storage device that should
be big enough in order to accommodate copies of all memory images for all
users. It is also capable of offering direct access to these memory images.
• The system maintains a ready queue consisting of all processes whose
memory images are on the backing store or in memory and are ready
to run.
• Whenever the CPU scheduler decides to execute a process, it calls the
dispatcher.
• The dispatcher checks to see whether the next process in the queue is
in memory. If it is not, and if there is no free memory region, the
dispatcher swaps out a process currently in memory and swaps in the
desired process.
• It then reloads registers and transfers control to the selected process.
Contiguous Memory Allocation
• In the Contiguous Memory Allocation, each process is contained in
a single contiguous section of memory.
• In this memory allocation, all the available memory space remains
together in one place which implies that the freely available
memory partitions are not spread over here and there across the
whole memory space.
• In Contiguous memory allocation which is a memory
management technique, whenever there is a request by the user
process for the memory then a single section of the contiguous
memory block is given to that process according to its requirement.
• Contiguous Memory allocation is achieved just by dividing the
memory into the fixed-sized partition.
• The memory can be divided either in the fixed-sized
partition or in the variable-sized partition in order
to allocate contiguous space to user processes.
Fixed-size Partition Scheme
• This technique is also known as Static partitioning. In
this scheme, the system divides the memory into fixed-
size partitions. The partitions may or may not be the
same size.
• In this partition scheme, each partition may contain
exactly one process.
• There is a problem that this technique will limit the
degree of multiprogramming because the number of
partitions will basically decide the number of processes.
• Whenever any process terminates then the partition
becomes available for another process.
Advantages of Fixed-size Partition
Scheme
• This scheme is simple and is easy to implement
• It supports multiprogramming as multiple processes can
be stored inside the main memory.
• Management is easy using this scheme
 Disadvantages
1. Internal Fragmentation
• Suppose the size of the process is
lesser than the size of the partition in
that case some size of the partition
gets wasted and remains unused.
This wastage inside the memory is
generally termed as Internal
fragmentation
• In the above diagram the 70 KB
partition is used to load a process of
50 KB so the remaining 20 KB got
wasted.
2. Limitation on the size of the process
If in a case size of a process is more than that of a
maximum-sized partition then that process cannot be loaded
into the memory. Due to this, a condition is imposed on the
size of the process and it is: the size of the process cannot
be larger than the size of the largest partition.
3. External Fragmentation
Total unused space by various partitions cannot be used in
order to load the processes even though there is the
availability of space but it is not in the contiguous fashion.
4. Degree of multiprogramming is less
As the size of the partition cannot change according to the
size of the process. Thus the degree of multiprogramming is
very less and is fixed.
Dynamic Partitioning

• Dynamic partitioning tries to overcome the problems

caused by fixed partitioning. In this technique, the
partition size is not declared initially. It is declared at the
time of process loading.
• The first partition is reserved for the operating system.
The remaining space is divided into parts. The size of
each partition will be equal to the size of the process.
• The partition size varies according to the need of the
process so that the internal fragmentation can be
avoided.
Advantages of Dynamic Partitioning over fixed partitioning

1. No Internal Fragmentation
• Given the fact that the partitions in dynamic partitioning are created according
to the need of the process, It is clear that there will not be any internal
fragmentation because there will not be any unused remaining space in the
partition.
2. No Limitation on the size of the process
• In Fixed partitioning, the process with the size greater than the size of the
largest partition could not be executed due to the lack of sufficient contiguous
memory. Here, In Dynamic partitioning, the process size can't be restricted
since the partition size is decided according to the process size.
3. Degree of multiprogramming is dynamic
• Due to the absence of internal fragmentation, there will not be any unused
space in the partition hence more processes can be loaded in the memory at
the same time.
Disadvantages of dynamic partitioning- External fragmentation
Absence of internal fragmentation doesn't mean that there will not be external fragmentation
Compaction
• Compaction is used to minimize the probability of
external fragmentation.
• In compaction, all the free partitions are made
contiguous and all the loaded partitions are brought
together.
• By applying this technique, we can store the bigger
processes in the memory.
• The free partitions are merged which can now be
allocated according to the needs of new processes.
• This technique is also called defragmentation.
Now P5 can be loaded into memory because the free space is now
made contiguous by compaction
Disadvantages of compaction
• The compaction is only possible when the program supports dynamic reallocation.
When the dynamic reallocation is supported by the program, the compaction process will
reallocate the program and the data and change the base register to reflect the new base
address. This is how the reallocation method takes place. So, if the program does not
support dynamic reallocation then compaction cannot be applied.
• The compaction process is time consuming and very expensive. As the simplest
algorithm of compaction requires to move all the process towards one end of the memory
and all the free space towards the other direction to produce one large hole available
memory. These all steps will first of all be costly and also this requires a lot of CPU time
therefore it decreases the efficiency of the Computer system.
Partition Allocation methods in OS
Overlays
• 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. In order to solve this problem, earlier people have
used some solution which is called as 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. Then overlays concept
says that whatever part you required, you load it and once
the part is done, then you just unload it, means just pull it
back and get the new part you required and run it.
• “The process of transferring a block of program code or
other data into internal memory, replacing what is already
stored”.
• 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
• The best example of overlays is assembler. Consider the assembler has 2
passes, 2 pass means at any time it will be doing only one thing, either the 1st
pass or the 2nd pass. Which means it will finish 1st pass first and then 2nd
pass. Let assume that available main memory size is 150KB and total code
size is 200KB

Pass1- 70 KB
Pass2- 80 KB
Symbol Table- 20 KB
Common Routine- 30KB
Loading and linking
• 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.
Multistep processing of a user program
Non-contiguous memory allocation
• Non-contiguous memory allocation is a memory allocation
technique.
• It allows to store parts of a single process in a non-contiguous
fashion.
• Thus, different parts of the same process can be stored at
different places in the main memory.
Paging
• Paging is a storage mechanism that allows OS to retrieve processes from the
secondary storage into the main memory in the form of pages.
• The main memory is divided into small fixed-size blocks of physical memory,
which is called frames and each process is divided into pages
• The size of a frame should be kept the same as that of a page to have maximum
utilization of the main memory and to avoid external fragmentation.
• The pages can be stored at the different locations of the memory
but the priority is always to find the contiguous frames or holes.
• Pages of the process are brought into the main memory only when
they are required otherwise they reside in the secondary storage.
Example

• For example, if the main memory size is 16 KB and Frame size is 1 KB. Here, the main memory will be divided into the
collection of 16 frames of 1 KB each. There are 4 separate processes in the system that is A1, A2, A3, and A4 of 4 KB each.
Here, all the processes are divided into pages of 1 KB each so that operating system can store one page in one frame. At the
beginning of the process, all the frames remain empty so that all the pages of the processes will get stored in a contiguous
way.

Main memory
In this example you can see that A2 and A4 are moved to the waiting state after some time. Therefore, eight
frames become empty, and so other pages can be loaded in that empty blocks. The process A5 of size 8 pages
(8 KB) are waiting in the ready queue.
Memory Management Unit
• The purpose of Memory Management Unit (MMU) is to convert the logical address into
the physical address. The logical address is the address generated by the CPU for every
page while the physical address is the actual address of the frame where each page
will be stored.

Considering the above image, let's say that the CPU demands 10th
word of 4th page of process A3. Since the page number 4 of process
A3 gets stored at frame number 12 therefore the 10th word of 12th
frame will be returned as the physical address.
Translating Logical Address into Physical Address-
Advantages
• It allows to store parts of a single process in a non-contiguous
fashion.
• It solves the problem of external fragmentation.
Disadvantages
• It suffers from internal fragmentation.
• There is an overhead of maintaining a page table for each
process.
• The time taken to fetch the instruction increases since now two
memory accesses are required.
Basics of Binary Addresses

• Computer system assigns the binary addresses to the memory [Link]

system uses amount of bits to address a memory location.
• Using 1 bit, we can address two memory locations. Using 2 bits we can
address 4 and using 3 bits we can address 8 memory locations.
• A pattern can be identified in the mapping between the number of bits in the
address and the range of the memory locations.

[Link] 1 Bit we can represent 2^1 i.e 2 memory locations.

[Link] 2 bits, we can represent 2^2 i.e. 4 memory locations.
[Link] 3 bits, we can represent 2^3 i.e. 8 memory locations.
Therefore, if we generalize this,

Using n bits, we can assign 2^n memory locations.

n bits of address → 2 ^ n memory locations

Physical and Logical Address Space

Physical Address Space

• Physical address space in a
system can be defined as the
size of the main memory.
• The process size must be less than
the physical address space.
Logical Address Space

• Logical address space can be defined as the size of the

process. The size of the process should be less enough
so that it can reside in the main memory.
Page Table

• Page Table is a data structure used by the virtual

memory system to store the mapping between logical
addresses and physical addresses.
• The CPU always accesses the processes through their
logical addresses. However, the main memory
recognizes physical address only.
• MMU converts the page number of the logical address
to the frame number of the physical address. The offset
remains same in both the addresses.
• To perform this task, Memory Management unit needs a
special kind of mapping which is done by page table.
The page table stores all the Frame numbers
corresponding to the page numbers of the page table.
• In other words, the page table maps the page number
to its actual location (frame number) in the memory.
Mapping from page table to main
memory
Segmentation
• Like Paging, Segmentation is another non-contiguous memory allocation
technique.
• In segmentation, process is not divided blindly into fixed size pages, but
divided into modules for better visualization.
Characteristics-
• Segmentation is a variable size partitioning scheme.
• In segmentation, secondary memory and main memory are divided into
partitions of unequal size.
• The size of partitions depend on the length of modules.
• The partitions of secondary memory are called as segments.
Why segmentation?
• Paging is more close to the Operating system rather than the
User, It divides all the processes into the form of pages
regardless of the fact that a process can have some relative parts
of functions which need to be loaded in the same page.

• Operating system doesn't care about the User's view of the

process. It may divide the same function into different pages and
those pages may or may not be loaded at the same time into the
memory. It decreases the efficiency of the system.

• It is better to have segmentation which divides the process into

the segments. Each segment contains the same type of functions
such as the main function can be included in one segment and
the library functions can be included in the other segment.
In accordance to the above segment table, the segments are
stored in the main memory as-
Translating Logical Address into Physical Address-

• CPU always generates a logical address.

• A physical address is needed to access the main memory.
Segmentation- Advantages
• It allows to divide the program into modules which provides better
visualization.
• Segment table consumes less space as compared to Page Table in paging.
• It solves the problem of internal fragmentation.
Disadvantages
• There is an overhead of maintaining a segment table for each process.
• The time taken to fetch the instruction increases since now two memory
accesses are required.
• Segments of unequal size are not suited for swapping.
• It suffers from external fragmentation as the free space gets broken down
into smaller pieces with the processes being loaded and removed from the
main memory.
Page Table Entry
• A page table entry contains several information about the page.
• The information contained in the page table entry varies from
operating system to operating system.
• The most important information in a page table entry is frame
number.
1. Frame Number-
• Frame number specifies the frame where the page is stored in the
main memory.
• The number of bits in frame number depends on the number of
frames in the main memory.

2. Present / Absent Bit-

• This bit is also sometimes called as valid / invalid bit.

• This bit specifies whether that page is present in the main
memory or not.
• If the page is not present in the main memory, then this bit is set
to 0 otherwise set to 1.
5. Caching Enabled / Disabled-

• This bit enables or disables the caching of page.

• Whenever freshness in the data is required, then caching is disabled using this bit.
• If caching of the page is disabled, then this bit is set to 1 otherwise set to 0.

6. Dirty Bit-

• This bit is also sometimes called as “Modified bit“.

• This bit specifies whether that page has been modified or not.
• If the page has been modified, then this bit is set to 1 otherwise set to 0.
3. Protection Bit-
• This bit is also sometimes called as “Read / Write bit“.
• This bit is concerned with the page protection.
• It specifies the permission to perform read and write operation on the
page.
• If only read operation is allowed to be performed and no writing is
allowed, then this bit is set to 0.
• If both read and write operation are allowed to be performed, then this
bit is set to 1.

4. Reference Bit-
• Reference bit specifies whether that page has been referenced in the
last clock cycle or not.
• If the page has been referenced recently, then this bit is set to 1
otherwise set to 0.
VIRTUAL MEMORY
• Virtual Memory is a storage scheme that provides user an
illusion of having a very big main memory. This is done by
treating a part of secondary memory as the main memory.
• In this scheme, User can load the bigger size processes than the
available main memory by having the illusion that the memory
is available to load the process.
• Instead of loading one big process in the main memory, the
Operating System loads the different parts of more than one
process in the main memory.
• By doing this, the degree of multiprogramming will be increased
and therefore, the CPU utilization will also be increased.
How Virtual Memory Works?

• Whenever some pages needs to be loaded in the main

memory for the execution and the memory is not
available for those many pages, then in that case,
instead of stopping the pages from entering in the main
memory, the OS search for the RAM area that are least
used in the recent times or that are not referenced and
copy that into the secondary memory to make the
space for the new pages in the main memory.
Demand Paging

• Demand Paging is a popular method of virtual memory

management.
• In demand paging, the pages of a process which are
least used, get stored in the secondary memory.
• A page is copied to the main memory when its demand
is made or page fault occurs.
• There are various page replacement algorithms which
are used to determine the pages which will be
replaced.
Translation Look aside buffer

Drawbacks of Paging
[Link] of Page table can be very big and therefore it wastes main
memory.
[Link] will take more time to read a single word from the main
memory.
How to decrease the page table size
[Link] page table size can be decreased by increasing the page
size but it will cause internal fragmentation and there will also
be page wastage.
[Link] way is to use multilevel paging but that increases the
effective access time therefore this is not a practical approach.
How to decrease the effective access time

[Link] can use a register having the page table stored

inside it so that the access time to access page table
can become quite less but the register are not cheaper
and they are very small in compare to the page table
size therefore, this is also not a practical approach.
[Link] overcome these many drawbacks in paging, we have
to look for a memory that is cheaper than the register
and faster than the main memory so that the time taken
by the CPU to access page table again and again can be
reduced and it can only focus to access the actual word.
Locality of reference

In operating systems, the concept of locality of reference

states that, instead of loading the entire process in the
main memory, OS can load only those number of pages
in the main memory that are frequently accessed by the
CPU and along with that, the OS can also load only those
page table entries which are corresponding to those
many pages.
Translation look aside buffer (TLB)

• A Translation look aside buffer can be defined as a

memory cache which can be used to reduce the time
taken to access the page table again and again.
• It is a memory cache which is closer to the CPU and the
time taken by CPU to access TLB is lesser than that taken
to access main memory.
• TLB is faster and smaller than the main memory but
cheaper and bigger than the register.
• TLB follows the concept of locality of reference which
means that it contains only the entries of those many
pages that are frequently accessed by the CPU.
• In translation look aside buffers, there are tags and keys with the
help of which, the mapping is done.
• TLB hit is a condition where the desired entry is found in
translation look aside buffer. If this happens then the CPU simply
access the actual location in the main memory.
• However, if the entry is not found in TLB (TLB miss) then CPU has
to access page table in the main memory and then access the
actual frame in the main memory.
• Therefore, in the case of TLB hit, the effective access time will be
lesser as compare to the case of TLB miss.
• If the probability of TLB hit is P% (TLB hit rate) then the
probability of TLB miss (TLB miss rate) will be (1-P) %.
Therefore, the effective access time can be defined as;
EAT = P (t + m) + (1 - p) (t + k.m + m)
Where, p → TLB hit rate
t → time taken to access TLB
m → time taken to access main memory
k = 1, if the single level paging has been implemented.

[Link] access time will be decreased if the TLB hit rate is

increased.
[Link] access time will be increased in the case of multilevel
paging.
Demand paging
• According to the concept of Virtual Memory, in order to execute
some process, only a part of the process needs to be present in
the main memory which means that only a few pages will only be
present in the main memory at any time.

• Demand paging suggests keeping all pages of the frames in the

secondary memory until they are required. In other words, it says
that do not load any page in the main memory until it is required.

• Whenever any page is referred for the first time in the main
memory, then that page will be found in the secondary memory.
Page Fault
• If the referred page is not present in the main memory
then there will be a miss and the concept is called Page
miss or page fault.
• The CPU has to access the missed page from the
secondary memory.
• If the number of page fault is very high then the
effective access time of the system will become very
high.
Page Replacement Algorithms
• The page replacement algorithm decides which memory page is
to be replaced.
• The process of replacement is sometimes called swap out or
write to disk.
• Page replacement is done when the requested page is not found
in the main memory (page fault).
• Frame allocation is all about how many frames are to be
allocated to the process while the page replacement is all about
determining the page number which needs to be replaced in
order to make space for the requested page.
• First In First Out (FIFO)
• Least Recently Used (LRU)
• Optimal Page Replacement
First In First Out (FIFO)
This is the simplest page replacement algorithm.
In this algorithm, the operating system keeps track of all pages in the memory
in a queue, the oldest page is in the front of the queue.
When a page needs to be replaced page in the front of the queue is selected for
removal.
Example-1 Consider page reference string 1, 3, 0, 3, 5, 6 with 3 page frames.
Find number of page faults.
Initially all slots are empty, so
when 1, 3, 0 came they are
allocated to the empty slots —
> 3 Page Faults.
when 3 comes, it is already in
memory so —> 0 Page
Faults.
Then 5 comes, it is not
available in memory so it
replaces the oldest page slot i.e
1. —>1 Page Fault.
6 comes, it is also not available
in memory so it replaces the
oldest page slot i.e 3 —>1
Belady’s anomaly – Belady’s anomaly proves that it is
possible to have more page faults when increasing the
number of page frames while using the First in First Out
(FIFO) page replacement algorithm. For example, if we
consider reference string 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
and 3 slots, we get 9 total page faults, but if we increase
slots to 4, we get 10 page faults.
Least Recently Used (LRU)
• In this algorithm page will be replaced which is least
recently used.
• Example-3Consider the page reference string 7, 0, 1, 2,
0, 3, 0, 4, 2, 3, 0, 3, 2 with 4 page [Link] number
Initially all slots are empty, so
of page faults. when 7 0 1 2 are allocated to
the empty slots —> 4 Page
faults
0 is already their so —> 0
Page fault.
when 3 came it will take the
place of 7 because it is least
recently used —>1 Page fault
0 is already in memory so —
> 0 Page fault.
4 will takes place of 1 —> 1
Page Fault
Now for the further page
reference string —> 0 Page
Optimal Page Replacement

In this algorithm, pages are replaced which would not be used for
the longest duration of time in the future.
Example-2:Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3,
0, 3, 2, with 4 page frame. Find number of page fault.
Initially all slots are empty, so
when 7 0 1 2 are allocated to
the empty slots —> 4 Page
faults
0 is already there so —> 0
Page fault.
when 3 came it will take the
place of 7 because it is not
used for the longest duration of
time in the future.—>1 Page
fault.
0 is already there so —> 0
Page fault..
4 will takes place of 1 —> 1
Page Fault.
 Steps in handling page fault
• With demand-paged virtual memory, pages are loaded only when they are demanded
during program execution.
• Access to a page marked invalid causes a page fault. The paging hardware, in
translating the address through the page table, will notice that the invalid bit is set,
causing a trap to the operating system. This trap is the result of the operating system’s
failure to bring the desired page into memory.

Procedure for handling page fault

Thrashing
• Thrashing is when the page fault and swapping
happens very frequently at a higher rate, and then the
operating system has to spend more time swapping
these pages. This state in the operating system is
known as thrashing.
• Because of thrashing, the CPU utilization is going to be
reduced or negligible.
• The basic concept involved is that if a process is
allocated too few frames, then there will be too many
and too frequent page faults.
• As a result, no valuable work would be done by the
CPU, and the CPU utilization would fall drastically.
• The long-term scheduler would then try to improve the
CPU utilization by loading some more processes into the
memory, thereby increasing the degree of
multiprogramming. Unfortunately, this would result in a
further decrease in the CPU utilization, triggering a
chained reaction of higher page faults followed by an
increase in the degree of multiprogramming, called
Paging and segmentation-
Fragmentation
• Paging may lead to internal fragmentation as the
page is of fixed block size, but it may happen that the
process does not acquire the entire block size which will
generate the internal fragment in memory.
• The segmentation may lead to external
fragmentation as the memory is filled with the
variable sized blocks. Thus if there are blocks which is
not utilized by any process (because no process can be
fit into the block) it leads to an unused fragment.
Inverted page table
• Most of the Operating Systems implement a separate pagetable
for each process, i.e. for ‘n’ number of processes , there are ‘n’
number of pagetables stored in the memory.
• Sometimes when a process is very large in size and it occupies
virtual memory then with the size of the process, it’s pagetable
size also increases substantially.
• The amount of memory occupied by the page tables can turn out
to be a huge overhead and is always unacceptable as main
memory is always a scarce resource.
A process of size 2 GB with: Page size = 512 Bytes
Size of page table entry = 4 Bytes
Number of pages in the process = 2 GB / 512 B = 2^22
PageTable Size = 2^22 * 2^2 = 2^24 bytes
• Inverted Page Table is the global page table which is maintained by
the Operating System for all the processes. In inverted page table,
the number of entries is equal to the number of frames in the main
memory. It can be used to overcome the drawbacks of page table.
• There is always a space reserved for the page regardless of the
fact that whether it is present in the main memory or not.
• Through the inverted page table, the overhead of storing an
individual page table for every process gets eliminated and only a
fixed portion of memory is required to store the paging information
of all the processes together. This technique is called as inverted
paging as the indexing is done with respect to the frame number
instead of the logical page number.
Multilevel page table
The need for multilevel paging arises when-
• The size of page table is greater than the frame size.
• As a result, the page table can not be stored in a single frame in main memory.
Working
In multilevel paging,
• The page table having size greater than the frame size is divided into several parts.
• The size of each part is same as frame size except possibly the last part.
• The pages of page table are then stored in different frames of the main memory.
• To keep track of the frames storing the pages of the divided page table, another
page table is maintained.
• As a result, the hierarchy of page tables get generated.
• Multilevel paging is done till the level is reached where the entire page table can be
stored in a single frame.
• Multilevel Paging is a paging scheme which consist of
two or more levels of page tables in a hierarchical
manner. It is also known as hierarchical paging. The
entries of the level 1 page table are pointers to a level 2
page table and entries of the level 2 page tables are
pointers to a level 3 page table and so on. The entries of
the last level page table are stores actual frame
information.
• In multilevel paging whatever may be levels of paging
all the page tables will be stored in main memory. So it
requires more than one memory access to get the
physical address of page frame. One access for each
level needed.
• Each page table entry except the last level page table
entry contains base address of the next level page
table.