Memory Management Techniques

Logical versus Physical Address Space

• Logical Address
  • An address generated by the CPU while a program is running
  • The logical address is basically the address of an instruction or data used by a process.
  • User can access logical address of the process.
  • User has indirect access to the physical address through logical address
  • Logical address does not exist physically. Hence, aka, Virtual address
  • The set of all logical addresses that are generated by any program is referred to as Logical Address Space
  • Range: 0 to max

• Physical Address
  • An address loaded into the memory-address register of the physical memory.
  • User can never access the physical address of the Program.
  • The physical address is in the memory unit. It’s a location in the main memory physically.
  • A physical address can be accessed by a user indirectly but not directly.
  • The set of all physical addresses corresponding to the Logical addresses is commonly known as Physical Address Space
  • It is computed by the Memory Management Unit (MMU)
  • Range: (R + 0) to (R + max), for a base value R

Common terms

Internal Fragmentation

• If the size of the process is lesser then the total size of the partition then some size of the partition gets wasted and remain unused.
• This is wastage of the memory and called internal fragmentation.

External Fragmentation

• The total unused space of various partitions cannot be used to load the processes even though there is space available but not in the contiguous form
• Eg: 55KB unused space available, but still can't allocate to process which need 41KB or more.
• NOTE:
  • If there is Internal Fragmentation then External Fragmentation is also present
  • Vice-versa is not true

Memory management unit (MMU)

• The runtime mapping from virtual to physical address is done by a hardware device called the memory-management unit (MMU)
• Relocation register
  • Used to map logical and physical memory address in contiguous allocation.

How OS manages the isolation and protect? (Memory Mapping and Protection)

• OS provides this Virtual Address Space (VAS) concept.
• To separate memory space, we need the ability to determine the range of legal addresses that the process may access and to ensure that the process can access only these legal addresses.
• The relocation register contains value of smallest physical address (Base address [R]); the limit register contains the range of logical addresses (e.g., relocation = 100040 & limit = 74600).
• Each logical address must be less than the limit register.
• MMU maps the logical address dynamically by adding the value in the relocation register.
• When CPU scheduler selects a process for execution, the dispatcher loads the relocation and limit registers with the correct values as part of the context switch. Since every address generated by the CPU (Logical address) is checked against these registers, we can protect both OS and other users’ programs and data from being modified by running process.
• Any attempt by a program executing in user mode to access the OS memory or other uses’ memory results in a trap in the OS, which treat the attempt as a fatal error.

Memory Allocation(Management) Techniques

• Main memory can be allocated in two ways:
  • Contiguous Memory Allocation
  • Non-contiguous MemoryAllocation

Contiguous Memory Allocation

• Each process gets a single contiguous block of memory.
• Contiguous memory allocation can be categorized into two ways
  1. Fixed Partitioning
  2. Variable/Dynamic Partitioning
• Relocation register is used as MMU in contiguous allocation to map logical and physical memory address.

1. Fixed Partitioning

• In the fixed partition scheme, memory is divided into fixed number of partitions
• It can be of equal or different sizes
• Limitations:
  • Internal Fragmentation
  • External Fragmentation
  • Limitation on process size
    • If the process size is larger than the size of maximum sized partition then that process cannot be loaded into the memory.
    • Therefore, a limitation can be imposed on the process size that is it cannot be larger than the size of the largest partition.
  • Low degree of multi-programming
    • In fixed partitioning, the degree of multiprogramming is fixed and very less because the size of the partition cannot be varied according to the size of processes.

2. Dynamic Partitioning

• In this technique, the partition size is not declared initially
• It is declared at the time of process loading
• Pros
  • No internal fragmentation
  • No limit on size of process
  • Better degree of multi-programming
• Cons
  • External fragmentation
    • Eg: Two process of size 2MB and 1MB exits
      • But if another process neds 3MB it can’t be assigned
  • Allocation and deallocation of memory is complex
  • Difficult Implementation
• The main disadvantage of Dynamic partitioning is External Fragmentation.
  • Can be removed by Compaction, but with overhead

Defragmentation/Compaction

• Solution for External fragmentation in Dynamic Partitioning
• In Contiguous memory allocation we can remove external-fragmentation by using defragmentation
• It is a process, where all scattered fragments (data) are rearrange in such that they come in sequence.
• Dynamic partitioning suffers from external fragmentation
• Defragmentation is applied to minimize the probability of external fragmentation.
• Where 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.
• Cons
  • The efficiency of the system is decreased in the case of compaction since all the free spaces will be transferred from several places to a single place.

Free Space Management

• Solution for Holes management in Dynamic Partitioning
• File management system in an OS is used to keep track of free spaces to allocate and de-allocate memory blocks to files.
• Free space list is used to maintains the record of free blocks.
• When a file is created,
  • OS searches and allocates free space from the ‘free space list’
  • On deletion of file, the file system frees the given space and adds this to the ‘free space list’
• There are various approaches for free space management in os :
  • Bit vector or Bitmap
  • Linked List
  • Grouping
  • Counting
• Suppose:
  • The free block numbers are 3, 4, 5, 6, 9, 10, 11, 12, 13,14.
  • And occupied block numbers are 1, 2, 7, 8, 15,16

Bit vector or Bitmap

• 1 --> Free blocks
• O --> Occupied blocks
• Bitmap is represented as: 0011110011111100
• Pros
  • Simple and easy to understand.
  • Consumes less memory.
  • It is efficient to find free space
• Cons
  • Inefficient to find holes
    • The OS goes through all the blocks until it finds a free block
  • It is not efficient when the disk size is large

Linked List 👍

• All the free blocks inside a disk are linked together in a linked list
• Prod
  • Available space is used efficiently
  • As there is no size limit on a linked list, a new free space can be added easily
• Cons
  • In this method, the overhead of maintaining the pointer appears.
  • The Linked list is not efficient when we need to reach every block of memory.

Grouping

• The grouping technique is also called the modification of a linked list technique
• The first free block of memory contains the addresses of the n-free blocks
• And the last free block of these n-th free blocks contains the addresses of the next n free block of memory and this keeps going on
  • Then: Block 3: 4,5,6 and Block 6: 7, 8, 9, 10, 11, 12, 13, 14
• Pros
  • We can easily find addresses of a large number of free blocks easily and quickly
• Cons
  • We need to change the entire list if one block gets occupied

Counting

• Address of first free disk block (a pointer) and a number ‘n’
• From above example:
  • Block 3: 4 (i.e 3,4,5,6)
  • and Block 9: 6 (i.e 9,10,11,12,13,14)
• Pros
  • A bunch of free blocks take place fastly.
  • The list is smaller in size.
• Cons
  • The first free block stores the rest free blocks, so it requires more space.

Partitioning Algorithms in Memory Management

• Various algorithms which are implemented by the OS in order to find out the holes in the free space list and allocate them to the processes.
• First Fit 👍
  • Allocate the first hole that is big enough.
  • Simple and easy to implement.
  • Fast/Less time complexity
• Next Fit
  • Enhancement on First fit but starts search always from last allocated hole
  • Same advantages of First Fit.
• Best Fit
  • Allocate smallest hole that is big enough
  • Lesser internal fragmentation.
  • May create many small holes and cause major external fragmentation.
  • Slow, as required to iterate whole free holes list.
• Worst Fit
  • Allocate the largest hole that is big enough
  • Slow, as required to iterate whole free holes list.
  • Leaves larger holes that may accommodate other processes.
  • Lesser external fragmentation