Please disable adblock to view this page.

← Go home

Swapping and Approaches for Memory Allocation

swapping

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

SWAPPING

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

swapping

APPROACHES FOR MEMORY ALLOCATION

  • 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?

FIXED PARTITIONING

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

EQUAL SIZE FIXED PARTITION

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

UNEQUAL SIZE 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

fixed-partitioning

DYNAMIC PARTITIONING

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

effect-of-dynamic-partitioning

effect-of-dynamic-partitioning1

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

First-fit: Allocate the first hole that is big enough
Fastest
May have many process loaded in the front end of memory that must be searched over when trying to find a free block
Best-fit
–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
Worst-fit:
–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.

FRAGMENTATION

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

PAGING

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

page-address

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

PAGING HARDWARE

paging-hardware

Paging Model of Logical and Physical Memory

logical-physical-memory-model

Paging Example

paging-example

Free Frames

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

Protection

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

protection

Structure of the Page Table

  • Hierarchical Paging

     

  • Hashed Page Tables

     

  • Inverted Page Tables

Translation Look-Aside Buffer

translation-look-aside-buffer

SEGMENTATION

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

segmentation

Logical View of Segmentation

logical-view-segmentation

Segmented Address Space Diagram

segmented-address-space-diagram

Segmentation Hardware

segmentation-hardware

Combining Segmentation with Paging

segmentation-paging

Pratik Kataria is a budding programmer, web designer and developer.