Unit 5 - MEMORY MANAGEMENT

5.1 Basic Memory Management-Partitioning, Fixed and variable,

5.2 Free space management techniques-Bitmap, Linked List.
5.3 Introduction to page tables
5.4 Segmentation, Fragmentation, Page Fault
5.5 Virtual memory-Introduction to paging, Demand Paging
5.6 Page replacement Algorithm-FIFO, LRU, Optimal.
****************************************************************
Basic Memory Management
• Memory is second major component in computer system after processors.
• Memory System of a computer is constructed as hierarchy of layers
containing registers, cache memory, hard disks and magnetic tapes.
• These layers are differing from one another by their access speed, storage
capacity and cost.
• Disks are basically used to store all kind of information including
process- codes. All information is stored on disk in various files.
• It is more time consuming to access such information from disks because
disks are lower speed devices in comparison to processors.
• Solution to this problem is Fetch the information in main memory before
using it. (accessing speed of main memory before using it)
• Processors access this information from memory. This raises various
issues like memory – allocation and deallocation, protection sharing etc.
So much memory management is needed.

Main Memory
• It is work house of the memory System. It is also known as physical
memory.
• It comes in the form of chips internally in computer system.
• Main memory is the middle layer in the memory hierarchy of computer
system.
• It is slower and cheaper compare cache memory while
faster and costly compared to disks.
• Main Memory generally consists of RAM (Random
Access Memory).
• It is volatile it means it needs to have electrical power
in order to maintain its information..
• Random: means that any piece of data from this
memory can be accessed quickly in constant time.
• Main memory has limited storage capacity (64–512
MB – now 1 GB).
• Entire Main memory consider as sequential list of
bytes. Each byte has an address that is used to locate
it, this address is called physical address. Each byte
has an address in registers.
• The address for most computer system starts at 0 and
go up in sequence until each byte has an address.

Partitioning
• An important operation of memory management is to bring programs into
main memory for execution by the processor.
• Partitioning is a technique that divides a memory into multiple partitions.
• These partitions can be of different size or same size.
• Types of partitioning
Fixed partitioning i.e. static partitioning
Variable partitioning i.e. dynamic partitioning

Fixed Partitioning (Static Partitioning)

• Fixed Partitioning: Main memory is divided into multiple partitions of

fixed size at the time of system generation. A process may be loaded into
a partition of equal size or greater size. Partitions can be of equal size or
unequal size.
• Equal size partitioning: Main memory is divided into equal size
partitions. Any process with less or equal size can be loaded in any
available partition.
• Unequal size partitioning: Main memory is divided into multiple
partitions of unequal size. Each process can be loaded into the smallest
partition within which the process will fit.

• Memory is shared among Operating System and various simultaneously

running processes.
• Memory is divided into fixed partition size can be equal or unequal for
different partition. Generally unequal partitions are used for better
utilization of memory.
• Each partition is accommodating exactly one process.
• Whenever program needs to be loaded in memory, a free partition big
enough to hold program is found and allocated.
• If there is no free partition available of required size, which process needs
to wait such process will be put in a queue.

Fixed Partitioning Advantage & Disadvantage

Advantage of fixed partition method:
1. Implement is simple.
2. Processing overhead are low.
Disadvantage of fixed partition method:
1. Degree of multiprogramming is fixed here, the maximum number of
process can be executed simultaneously can’t be changed.
2. Partitions are of fixed size, so any space in a partition not used by a
process is wasted, this is called Internal Fragmentation.

Variable Partitioning (Dynamic Partitioning)

• When a process enters in main memory, it is allocated exact size that is
required by that process.
• So in this method, partitions can vary in size depending on memory space
required by a process entering in main memory.
• Operating system maintains a table indicating which parts of memory are
available and which are occupied.
• When new process arrives and it needs space, system searches for
available memory space in main memory.
• If it is available, then memory is allocated to the process by creating a
partition in memory.
• For example: Consider following table with process and memory space.

Variable Partitioning Advantage

1. Better Utilization of memory
2. No internal fragmentation because process gets only that much memory of its
size.
3. Degree of multiprogramming (means no. of processes
running at same time in memory) is not fixed here.

Variable Partitioning Disadvantage

1. Memory is allocated when process enters in the system and released when it
terminates. These operations externally result in small holes in the memory.
2. These holes will be small that no any process can be loaded in it, but total
size of all holes may be big enough to hold any process. But memory is
allocated contiguous here holes can’t be used this type of memory wastage is
called External Fragmentation
3. Scattered (spread) free memory partition can be combined using compaction
or De-Fragmentation

Fixed Partitioning Vs Variable Partitioning

Free Space Management Techniques
• The operating system manages the free space in the hard disk. This is
known as free space management in operating systems.
• The system keeps tracks of the free disk blocks for allocating space to
files when they are created.
• Also, to reuse the space
released from deleting the
files, free space
management becomes
crucial.
• The Operating system
maintains a free space list
which keeps track of the
free disk blocks /space that
are not allocated to some file or directory.
• The free space list can be implemented mainly as:
Bitmap or Bit vector
Linked List

Bitmap - Free Space Management Techniques

• Bitmap is a mapping from one system such as integers to bits.

• A Bitmap or Bit Vector is series or collection of bits where each bit
corresponds to a disk block. This is the most frequently used method to
implement the free space list.
• In this method, each block in the hard disk is represented by a bit (either 0
or 1). If a block has a bit 0 means that the block is allocated to a file, and
if a block has a bit 1 means that the block is not allocated to any file, i.e.,
the block is free.
• We can find the free block number from the bit vector using the following
method-

• Ex1- The first group of 8 bits (00111100) constitutes a non-zero word

since all bits are not 0. After finding the non-zero word, we will look for
the first 1 bit. This is the third character of the non-zero word. so, offset =
3.
• Therefore, 0011110011111100 the first free block number=8*0+3= 3.
• Ex2- The first group of 8 bits (00001110) constitute a non-zero word
since all bits are not 0. After the non-0 word is found, we look for the first
1 bit. This is the 5th bit of the non-zero word. So, offset = 5.Therefore,
0000111000000110, the first free block number=8*0+5=5.
• Advantages-
It is simple to understand.
It occupies less memory.
It is an efficient method to find the first free space/ block on the disk
• Disadvantages-
This technique requires a special hardware support to find the first 1 in
a word it is not 0
This technique is not useful for the large disks.

Linked List -Free Space Management Techniques

• In this approach, the free disk blocks are
linked together i.e. a free block contains a
pointer to the next free block.
• The block number of the very first disk
block is stored at a separate location on
disk and is also cached in memory.
• In Figure-2, the free space list head points
to Block 5 which points to
Block 6, the next free block and so on.
• The last free block would contain a null
pointer indicating the end of free list.
• This scheme is not efficient to traverse
the list, We must read each block, which
requires substantial I/O time
• Justify your answer whether the "Linked allocation of files on a disk
space can lead to internal fragmentation”
• Ans: Yes, Linked allocation of files in disk may lead to internal
fragmentation(in the last block). Let us assume Disk block size is 4Bytes
in the disk. If file size is of 5Bytes then it will be allocated 2 disk blocks
which is of size 8Bytes which will lead to internal fragmentation of
3Bytes.
• Advantages-
• External fragmentation is prevented by linked list allocation. As opposed
to contiguous allocation, this prevents the wasting of memory blocks.
• It is also quite simple to make our file bigger. All we have to do is link a
new file block to our linked list. The file can so expand as long as
memory blocks are available.
• Disadvantages-
• This method is inefficient since we need to read each block to traverse the
list, which takes more I/O time.
• There is an overhead in maintaining the pointer.
• There is no provision for random or direct memory access in linked list
allocation. We must search through the full linked list to locate the correct
block if we wish to access a certain file block.

Bitmap Vs Linked List

Introduction to page tables
• Page Table is a data structure used by the virtual memory system to store
the mapping between logical addresses and physical addresses.
• Logical addresses are generated by the CPU for the pages of the
processes therefore they are generally used by the processes.
• Physical addresses are the actual frame address of the memory. They are
generally used by the hardware or more specifically by RAM subsystems.
• The CPU always accesses the processes through their logical addresses.
However, the main memory recognizes physical address only.
• Thus page table mainly provides the corresponding frame number (base
address of the frame) where that page is stored in the main memory.
• Characteristics of the Page Table
• It is stored in the main memory.
• Generally; the Number of entries in the page table = the Number of Pages
in which the process is divided.
• PTBR means page table base register and it is basically used to hold the
base address for the page table of the current process.
• Each process has its own independent page table.

Page tables
Physical Address Space = M words
Logical Address Space = L words
Page Size = P words
Physical Address = log 2 M = m bits
Logical Address = log 2 L = l bits
page offset = log 2 P = p bits
Difference–Logical Address Vs Physical Address

Types of Memory Allocation

Segmentation
• The logical address space of any process is a collection of code, data and
stack. Code can be main function, user define function library function.
Data can be local and global variable, array, symbol table or other data
structure.
• The logical address space of a process is divided into blocks of varying
size, called Segments.
• Each segment contains a logical unit of a process.
• Logical unit can be main function, other functions or procedures, stack,
array, symbol table etc.
• Each segment can be considered as a independent address space
• All segments are given unique numbers to identify them.
• When process is to be executed its segments are moved from secondary
storage to main memory.
• Each entry of the segment table has a segment base & segment limit.
• A segment base contains the starting physical address where the segment
resides in memory.
• The segment limit specifies length of segment
• Operating system maintains a table, called segment table, for each
process. Segment table contains two information about each process.
• The logical address is divided into two/three parts-
➔ Segment number, which identifies a segment and
➔ Size of segment
➔ An offset, which gives the actual location within a segments.
• Segmentation is a memory management technique in which each job is
divided into several segments of different sizes, one for each module that
contains pieces that perform related functions.
• Each segment is actually a different logical address space of the program.
• When a process is to be executed, its corresponding segmentation are
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 where as in paging pages are of
fixed size.
• 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.

• Ex1- Suppose CPU has generates some logical address, and is given
form of(segment no , offset )- L=(2,125)
• To get physical address related to logical address, segment table will be
searched to get entry of segment no 2.
• For segment 2 ,base is 4300 and limit is 400,
• Offset compared with limit value ( 125 < 400)
• So, offset is valid
• Physical address (P) = offset + base = 125 + 4300=4425
• Ex2- Suppose CPU has generates some logical address, and is given
form of (segment no , offset )- L=(2,410)
• To get physical address related to logical address, segment table will be
searched to get entry of segment no 2.
• For segment 2 ,base is 4300 and limit is 410,
• Offset compared with limit value ( 125 > 410)
• So, offset is not valid.
• so physical address can not be generated.

Segmentation Advantages
• All segments are independent from each other, so segments can grow and
shrink without affecting other segments.
• If procedure in one segment is modified and recompiled, no other
segments need to be changed or recompiled.
• Sharing of procedure and data between various processes is simple.
• Different segment of a single process can be given different kind of
protection. One segment can be read only, while another can be writable.
• No internal fragmentation because segments are allocated exactly as
much memory as required.

Segmentation Disadvantages
• It is still expensive to allocate contiguous free memory to segments.
• External fragmentation is possible, which requires memory
defragmentation or compaction.

Fragmentation (Wastage Of Memory)

• Memory is allocated when process enters in the system and released
when it terminates.
• The primary goal is to utilize as much memory as possible.
• No any single piece of free memory should go wasted. But, We can’t
utilize (100%) full memory due to some problem.
• Such kind of problems is called Fragmentation.
• Fragmentation refers to unused(free) memory that cannot be allocated to
any process. Means, there is free memory available but it can’t be used.
• Two types of fragmentations:
1. External Fragmentation 2. Internal Fragmentation

External Fragmentation
• It refers to the wastage of free memory
between partitions, caused by scattered non-
contiguous free space.
• This is a severe problem in contiguous
memory allocation method with dynamic
partitioning.
• Memory allocation and de-allocation
operations eventually result in small holes in
the memory.
• These holes will be so small that no any
processes can be loaded in it. But, total size
of all memory wastage is called External
• Fragmentation.
• Solution- the occupied memory by processes
are shuffled, to this problem is to collect all
the free memory together in one larger block
or linked representation.

Internal Fragmentation
• It refers to the wastage of free memory within an partitions, caused by the
difference between the size of a partition and the size of a process loaded.
• This is a severe problem in contiguous memory
allocation method with fixed partitioning.
• The partitions are of fixed size. So any space in
a partition not used by a process is wasted. This
is called Internal Fragmentation.
• Ex- A process of 10 mb is allocated to a fixed
size partition of 12MB. SO here remaining 2MB
space remains unused and it will be wasted. It
cannot be used for any othe process.
• The Solution to this problem is to use dynamic
partitioning where a process is allocated exactly
as much memory as required

External Fragmentation Vs Internal Fragmentation

Page Fault
• Page fault dominates more like an error. It mainly occurs when any
program tries to access the data or the code that is in the address space of
the program, but that data is not currently located in the RAM of the
system.
• So basically when the page referenced by the CPU is not found in the
main memory then the situation is termed as Page Fault.
• Whenever any page fault occurs, then the required page has to be fetched
from the secondary memory into the main memory.
• In case if the required page is not loaded into the memory, then a page
fault trap arises.
• The page fault mainly generates an exception, which is used to notify the
operating system that it must have to retrieve the "pages" from the virtual
memory in order to continue the execution.
• Once all the data is moved into the physical memory the program
continues its execution normally.
• The Page fault process takes place in the background and thus goes
unnoticed by the user.
o The hardware of the computer tracks to the kernel and the program
counter (PC) is generally saved on the stack. CPU registers store the
information of the current state of instruction.
o An assembly program is started that usually saves the general
registers and also saves the other volatile information to prevent the
OS from destroying it.
• If you will access a page that is marked as invalid then it also causes a
Page Fault. Then the Paging hardware during translating the address
through the page table will notice that the invalid bit is set that will cause
a trap to the Operating system.
• This trap is mainly the result of the failure of the Operating system in
order to bring the desired page into memory

Handling Page Fault

Steps1. First of all, internal table(that is usually the process control block) for
this process in order to determine whether the reference was valid or invalid
memory access.
2. If the reference is invalid, then we will terminate the process. If the reference
is valid, but we have no bought in that page so now we just page it in.
3. Then we locate the free frame list in order to find the free frame.
4. Now a disk operation is scheduled in order to read the desired page into the
newly allocated frame.
5. When the disk is completely read, then the internal table is modified that is
kept with the process, and the page table that mainly indicates the page is now
in memory.
6. Now we will restart the instruction that was interrupted due to the trap. Now
the process can access the page as though it had always been in memory.

Virtual Memory
o Virtual memory is a memory management capability of an
operating system (OS) that uses hardware and software to allow a
computer to compensate for physical memory shortages by
temporarily transferring data from random access memory
(RAM) to disk storage.
OR
o Virtual memory is the separation of user logical memory from physical
memory.
o This separation allows an extremely large virtual memory to be provided
for programmers when only a smaller physical memory is available.
o Virtual memory makes the task of programming much easier, because the
programmer no longer needs to worry about the amount of physical
memory available, or about what code can be placed in overlays, but can
concentrate instead on the problem to be programmed.
o A virtual memory is a technique that allows a process to execute even
though it is partially loaded in main memory.
o Virtual memory removes the requirement that an entire process should be
in main memory for its execution.
o Process size can be larger than the size of main memory.
o Logical addresses are referred as virtual addresses.
o Logical address space of a process is referred as virtual address space.
Virtual address space can be larger than the physical memory.

Virtual Memory Advantage-

o Programs (processes) are not controlled by physical memory size. A
process larger than the main memory can also execute. Means the process
of 40-MB executing in 32-MB memory.
o Also, logical address space of a process is referred as virtual address
space. Virtual address space can be larger than the physical memory.
o Degree of multiprogramming (means no. of process that can loaded into
main memory at a time) can be different over a large range. There is no
need to keep an entire process in memory; more and more process can be
contain in memory.

Ways of Virtual Memory Implementation

The Virtual memory can be implemented in one of the following three ways:
Paging
Demand Paging
Demand Segmentation
Paging
o Paging is a function of memory management where a computer will store
and retrieve data from a device’s secondary storage to the primary
storage.
o In the Paging method, the main memory is split into small fixedsize
blocks of physical memory, which is known as frames.
o The size of a frame must be preserved the same as that of a page to have
maximum use of the main memory and to prevent external fragmentation.
o Paging changes pages from the swap disk to frames of the physical
memory therefore data can be accessed by the processor. Any page can
involve any frame.

o Address generated by CPU is divided into:

o Page number (p) – used as an index into a page table which contains base
address of each page in physical memory.
o Page offset (d) – combined with base address to define the physical
memory address that is sent to the memory unit.
o Address Translation - Page address is called logical address and
represented by page number and the offset.
o Logical Address = Page
Number + Page Offset
o Frame address is called
physical address and
represented by a frame
number and the offset.
o Physical Address =
Frame Number +Page
Offset
o A data structure called page map table is used to keep track of the relation
between a page of a process to a frame in physical memory.
Paging Logical and Physical Address
o Logical Address -

o Physical Address –

o The following fig is address

translation in Paging
o Address translation:
o Page size and frame size =
2n bytes.
o Logical address (L) :
o Page no (p) : L / 2n
o offset (d) : L % 2n
o Physical address (P ) : f *
2n + d
Paging Advantages
o Allocation and de-allocation of process is very fast .only list of free
frames need to be maintained .No any page algorithm is needed like first
fits, best fits etc.
o Swap-in and swap-out operations are very fast.(because a page size
matches disk block size, data can be moved to and from disk very easily.)
o Each and every frame from memory can be allocated to processes.
o Here, available memory is divided into fixed sized block and no wastage
of memory between partitions, so there is no External fragmentation

Paging Disadvantages
o Additional memory reference is required to read information from page
table .Two memory access required one for page table and second for
instruction or data.
o If process is of large size then page table of that process also have large
size. It may be too large to keep such page table in memory.
o A process size may not be an exact multiple of the page size. it may be
possible that space within partitions (page) remain unused by process
because of differ in page size and part of process loaded in that page . So
this paging result in from internal fragmentation

Demand Paging
o Demand paging system is similar to paging with swapping.
o The processes are kept on secondary storage, i.e. on disk.
o To execute a process, it is swapped into the memory.
o But, rather swapping the entire process into memory, only pages, which
are required for execution, are swapped.
o Page table includes the valid-invalid Bit for each page entry.
o If it is set to valid, it indicates that the page is currently present in the
memory.
o If it is set to invalid, it indicates that the page is still not loaded in the
memory.
o When a process starts its execution, this bit is set to invalid for all the
entries in the page table.
o When a page is loaded in memory, its corresponding frame number is
entered and page validity bit is set to valid.
o Whenever a logical address (virtual address) is generated, the system
operates as follows:
1. Page table is searched. If the page validity bit is set to valid,
corresponding frame number is fetched, page offset is added to it, and
physical address is determined.
2. If the page validity bit is set to invalid, then operating system reads the
page into a free frame from disk. If no frame is available, it uses a
replacement algorithm to replace an occupied frame.

****************************************************************