Please disable adblock to view this page.

← Go home

Swapping and Approaches for Memory Allocation


October 29, 2016
Published By : Pratik Kataria
Categorised in:


A process must be loaded into memory in order to execute
What If there is not enough memory available??



  • Contiguous Memory Allocation
  • Paging
  • Segmentation

Loading Program into Main Memory
(Contiguous Memory Location)

It is assumed that OS occupies some fixed portion of memory and rest is available to user processes.
Based on requirement and functionality different memory management methods are adopted.
–Should the process be allocated memory in contiguous manner?


Main memory is divided into number of fixed size partition at system generation time.
A processes can be loaded into a partition of equal or greater size


Easy to implement

If total user memory space is X and size of partition is Y, ( Y< X) then number of partitions in system will be X / Y. This is the maximum number of processes that can be loaded in the memory at any given time

If program size is much smaller than the size of partition, the remaining space is unutilized

A program may be too big to fit into a partition


We create fixed number of unequal size partition
Program is loaded into best fit partition
–processes are assigned in such a way as to minimize wasted memory within a partition
queue for each partition



Partitions are of variable length and number
Process is allocated exactly as much memory as required
Eventually we get holes in the memory. This is called external fragmentation
Must use compaction to shift processes so they are contiguous and all free memory is in one block

Effect of Dynamic Partitioning



How to satisfy a request of size n from a list of free holes

First-fit: Allocate the first hole that is big enough
May have many process loaded in the front end of memory that must be searched over when trying to find a free block
–Allocate the smallest hole that is big enough; must search entire list, unless ordered by size. Produces the smallest leftover hole
–Compaction is required to obtain a large block at the end of memory
–Allocate the largest hole; must also search entire list. Produces the largest leftover hole.

First-fit , next-fit and best-fit perform better than worst-fit in terms of speed and storage utilization.


External Fragmentation – total memory space exists to satisfy a request, but it is not contiguous
Internal Fragmentation – allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used
Reduce external fragmentation by compaction
-Shuffle memory contents to place all free memory together in one large block


Logical address space of a process can be noncontiguous; process is allocated physical memory whenever the latter is available
Divide physical memory into fixed-sized blocks called frames (size is power of 2, between 512 bytes and 8,192 bytes)
Divide logical memory into blocks of same size called pages
Keep track of all free frames
To run a program of size n pages, need to find n free frames and load program
Set up a page table to translate logical to physical addresses
Internal fragmentation

Address Translation Scheme

Page number (p) – used as an index into a page table which contains base address of each page in physical memory
Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit


For given logical address space 2m and page size 2n



Paging Model of Logical and Physical Memory


Paging Example


Free Frames


Implementation of Page Table

Page table is kept in main memory
Page-table base register (PTBR) points to the page table
Page-table length register (PRLR) indicates size of the page table
In this scheme every data/instruction access requires two memory accesses. One for the page table and one for the data/instruction.
The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs)
Some TLBs store address-space identifiers (ASIDs) in each TLB entry – uniquely identifies each process to provide address-space protection for that process


Memory protection implemented by associating protection bit with each frame
Valid-invalid bit attached to each entry in the page table:

  • “valid” indicates that the associated page is in the process’ logical address space, and is thus a legal page
  • “invalid” indicates that the page is not in the process’ logical address space


Structure of the Page Table

  • Hierarchical Paging


  • Hashed Page Tables


  • Inverted Page Tables

Translation Look-Aside Buffer



A memory management technique
Memory-management scheme that supports user view of memory
A program is a collection of segments.
A segment is a logical unit such as: main program, procedure, function, method, object, local variables, global variables, common block, stack,symbol table, arrays


Logical View of Segmentation


Segmented Address Space Diagram


Segmentation Hardware


Combining Segmentation with Paging


Pratik Kataria is currently learning Springboot and Hibernate.
Technologies known and worked on: C/C++, Java, Python, JavaScript, HTML, CSS, WordPress, Angular, Ionic, MongoDB, SQL and Android.
Softwares known and worked on: Adobe Photoshop, Adobe Illustrator and Adobe After Effects.