unit III

Memory?

• Computer memory can be defined as a collection of

some data represented in the binary format.
• Machine understands only binary language that is 0 or
1. Computer converts every data into binary language
first and then stores it into the memory.
• That means if we have a program line written as int α =
10 then the computer converts it into the binary
language and then store it into the memory blocks.
• The representation of inti = 10 is shown below.
Definition of Process Address Space

• Address space may also denote a range of physical or

virtual addresses which can be accessed by a processor.
• The OS here also has an additional job to map the logical
addresses to the actual physical addresses too.
Physical address
The physical address is the actual location in the memory
that exist physically.
Logical Address
The address is always generated by CPU while running a
program
Swapping in Operating System

• To increase CPU utilization in multiprogramming, a

memory management scheme known as swapping can
be used. Swapping is the process of bringing a process
into memory and then temporarily copying it to the disc
after it has run for a while.
• The purpose of swapping in an operating system is to
access data on a hard disc and move it to RAM so that
application programs can use it.
Swapping in Operating System
• The CPU scheduler determines which processes are
swapped in and which are swapped out.
• When a high-priority process enters the input queue, a
low-priority process is swapped out so the high-priority
process can be loaded and executed.
• When this process terminates, the low priority process is
swapped back into memory to continue its execution.
Swapping
• Swapping has been subdivided into two concepts: swap-
in and swap-out.
• Swap-out is a technique for moving a process from RAM
to the hard disc.
• Swap-in is a method of transferring a program from a
hard disc to main memory, or RAM.
Memory Allocation

• To gain proper memory utilization, memory allocation

must be allocated efficient manner. One of the simplest
methods for allocating memory is to divide memory into
several fixed-sized partitions and each partition
contains exactly one process.
• Multiple partition allocation: In this method, a
process is selected from the input queue and loaded
into the free partition. When the process terminates, the
partition becomes available for other processes.
Fixed partition allocation:
• Fixed partition allocation: In this method, the operating
system maintains a table that indicates which parts of
memory are available and which are occupied by processes.
• Initially, all memory is available for user processes and is
considered one large block of available memory.
• This available memory is known as a “Hole”. When the
process arrives and needs memory, we search for a hole
that is large enough to store this process.
• If the requirement is fulfilled then we allocate memory to
process, otherwise keeping the rest available to satisfy
future requests.
First Fit
• In the First Fit, the first available free
hole fulfil the requirement of the process
allocated.

Here, in this diagram, a 40 KB memory

block is the first available free hole that can
store process A (size of 25 KB), because the
first two blocks did not have sufficient
memory space.
Best Fit

• In the Best Fit, allocate the smallest

hole that is big enough to process
requirements. For this, we search
the entire list, unless the list is
ordered by size.
•
Here in this example, first, we
traverse the complete list and find
the last hole 25KB is the best
suitable hole for Process A(size
25KB). In this method, memory
utilization is maximum as compared
to other memory allocation
techniques.
Worst Fit

• In the Worst Fit, allocate the largest

available hole to process. This method
produces the largest leftover hole.
• Here in this example, Process A (Size 25
KB) is allocated to the largest available
memory block which is 60KB. Inefficient
memory utilization is a major issue in the
worst fit.
Fragmentation

• Fragmentation is defined as when the process is loaded

and removed after execution from memory, it creates a
small free hole. These holes can not be assigned to new
processes because holes are not combined or do not
fulfill the memory requirement of the process.
• In the operating systems two types of fragmentation:
[Link] fragmentation
2. External fragmentation
 Internal Fragmentation
When a process is allocated to a
Types Of memory block, and if the process is
Fragmentatio smaller than the amount of memory
n: requested, a free space is created in
the given memory block. Due to this,
the free space of the memory block
is unused, which
causes internal fragmentation.
External fragmentation
• External fragmentation happens when a dynamic
memory allocation method allocates some memory but
leaves a small amount of memory unusable. There is
enough memory space to complete a request, but it is
not contiguous. It's known as external fragmentation.
Paging in Operating System

• Paging is a memory management scheme that eliminates the need for

a contiguous allocation of physical memory.
• The process of retrieving processes in the form of pages from the
secondary storage into the main memory is known as paging.
• The basic purpose of paging is to separate each procedure into pages.
Additionally, frames will be used to split the main memory. This
scheme permits the physical address space of a process to be non –
contiguous.
• In paging, the physical memory is divided into fixed-size blocks called
page frames, which are the same size as the pages used by the
process.
Difference between Contiguous and Noncontiguous Memory
Allocation

• Contiguous Memory Allocation : Contiguous memory allocation is

basically a method in which a single contiguous section/part of memory is
allocated to a process or file needing it. Because of this all the available
memory space resides at the same place together, which means that the
freely/unused available memory partitions are not distributed
• Non-Contiguous Memory Allocation : Non-Contiguous memory
allocation is basically a method on the contrary to contiguous allocation
method, allocates the memory space present in different locations to the
process as per it’s requirements. As all the available memory space is in a
distributed pattern so the freely available memory space is also scattered
here and there. This technique of memory allocation helps to reduce the
wastage of memory.
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
exact sizes are called segments.
• Types of Segmentation in Operating System
• Virtual Memory Segmentation: Each process is divided
into a number of segments, but the segmentation is not
done all at once. This segmentation may or may not take
place at the run time of the program.
• 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.
Virtual Memory in Operating
System
• Virtual Memory is a storage allocation scheme in which
secondary memory can be addressed as though it were
part of the main memory.
• Demand Paging
The process of loading the page into memory on demand
(whenever a page fault occurs) is known as demand
paging.
First In First Out (FIFO)
• In this algorithm, operating system keeps track of all pages in the
memory in a queue, 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 and 3
page slots. 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. —>1Page Fault.
• Finally 6 comes, it is also not available in memory so it replaces the
oldest page slot i.e 3 —>6
Optical page algorithm
• In operating systems, whenever a new page is referred
and not present in memory, page fault occurs and
Operating System replaces one of the existing pages
with newly needed page.
• Different page replacement algorithms suggest different
ways to decide which page to replace.
• The target for all algorithms is to reduce number of
page faults.
• In this algorithm, OS replaces the page that will not be
used for the longest period of time in future.
Optical page algorithm
• The idea is simple, for every reference we do following :
[Link] referred page is already present, increment hit count.
[Link] not present, find if a page that is never referenced in
future. If such a page exists, replace this page with new
page. If no such page exists, find a page that is
referenced farthest in future. Replace this page with
new page.
Least Recently Used (LRU)

• In Least Recently Used (LRU) algorithm is a Greedy algorithm where the page to be replaced
is least recently used. The idea is based on locality of reference, the least recently used page
is not likely
Let say the page reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 . Initially we have 4 page slots
empty.
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 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 fault because they are already
available in the memory.
LRU
Page • The Page Buffering Algorithm’s
Buffering primary goal is to reduce the
latency associated with accessing

Algorithm
data from a disc, which is much
slower than doing it from main
memory. The approach optimizes
in system performance by
intelligently buffering frequently

Operating visited pages in memory,

minimizing the requirement for
disc I/O operations.
System • Latency is the time delay between
input and output.
(MFU)
Algorithm • MFU Algorithm is a Page

in Replacement Algorithm in the

Operating System that replaces the
page accessed a maximum
Operating number of times in the past. If
more than one page is accessed

System
the same number of times, then
the page which occupied the frame
first will be replaced.
Allocation of frames in
Operating System
• Frame allocation algorithms are used if you have
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:
[Link] cannot allocate more than the total number of
available frames.
[Link] least a minimum number of frames should be
allocated to each process.
Frame allocation algorithms –
• The two algorithms commonly used to allocate frames to
a process are:
• 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.
Frame allocation algorithms –
• 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.