Swapping and Approaches for Memory Allocation
October 29, 2016
Categorised in: Operating System Design
SWAPPING
A process must be loaded into memory in order to execute
What If there is not enough memory available??
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
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
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
For given logical address space 2m and page size 2n
PAGING HARDWARE
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
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
Structure of the Page Table
- Hierarchical Paging
- Hashed Page Tables
- Inverted Page Tables
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
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.