Method of managing Primary memory (Main Memory) for Isolation and Protection
Logical vs Physical Address Space
Logical Address (Virtual Address)
Address of an instruction or data used by a process, generated by the CPU
User can access logical address of the process
User has indirect access to the physical address through logical address
The set of all logical addresses that are generated by any program is referred to as Logical/Virtual Address Space
Range => 0 to max
Physical Address
Address loaded into the memory-address register of the physical memory
User can never access the physical address of the Program
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
Range => (R + 0) to (R + max), for a base value R
Virtual Address Space (VAS) => Memory Mapping and Protection
Runtime mapping from virtual to physical address is done by a hardware device called the memory-management unit (MMU)
Relocation register contains value of smallest physical address (Base address, R)
Limit register contains the range of logical addresses
Each logical address must be less than the limit register
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
Fragmentation => Large no. of non-contiguous free spaces available
Degree of Multiprogramming => Number of processes being executed at a time
Overlay
Process by which a large size process can be put into MM
User divide the Process, Used in Embedded systems, Division should be independent
Memory Allocation Strategies
Contiguous => Each process is contained in a single contiguous block of memory
Fixed/Static Partition
MM is divided into partitions of equal or different sizes
Spanning is not allowed => Process can't be divided
Disadvantages
Internal Fragmentation => Wasted memory when alloted Process size is lower than of partition
Limit in Process size => Can't be more than the maximum size of Partition
Limitation of Degree of Multiprogramming => No. of Process can't be more than no. of Partition
Variable/Dynamic Partition
Partition size is declared at the time of process loading
Advantages
No Internal Fragmentation
No limit on size of Processes
Better Degree of Multiprogramming
Disadvantages
External Fragmentation
Process can't be alloted even when space is available because of the Hole created when a process leaves containing no contiguous space
Free holes/space in the memory are represented by a free list (Linked-List data structure)
Defragmentation/Compaction
Minimize the probability of external fragmentation
All the free partitions are made contiguous/merged, and all the loaded partitions are brought together
Efficiency of the system is decreased since all the free spaces will be transferred from several places to a single place
Free Space Management => How to satisfy a request of n size from a list of free holes?
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
Best Fit
Allocate smallest hole that is big enough
Slow, as required to iterate whole free holes list
Lesser internal fragmentation
May create many small holes and cause major external fragmentation
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
Non-Contiguous
Paging
In logical memory Process is divided into Pages & In physical memory RAM is divided into Frames of fixed sizes
Page Size = Frame Size
Page size is usually determined by the processor architecture
Size of PT = No. of Pages x No. of Bits used to represent Frames (Frame no.)
Generally Word = Byte
In a 32-bit system 1 Word = 4 Byte
Page Table
A Data structure stores which page is mapped to which frame
The page table contains the base address of each page in the physical memory
Stored in RAM, changes with context-switching
Page table is stored in main memory at the time of process creation and its base address is stored in process control block (PCB)
A page table base register (PTBR) is present in the system that points to the current page table
Structure
Frame Number => Mandatory Field
Valid/Invalid or Present/Absent or 1/0 => Page Fault
Reference => Least Recently Used (LRU) => If we have called the Page before
Caching => Kept in Cache => Not used for Dynamic data
Dirty/Modify => If this Page is modified but not changed in Hard Disk
Logical Address = Page number (p) + Page offset (d)
The p is used as an index into page table to get base address of the corresponding frame
Page Fault
Process tries to access a page which is not currently present in a frame and OS must bring the page from swap-space to a frame
OS must do page replacement to accommodate new page, using a page replacement algorithm
Page fault service time => Overhead when PF occurs
Hit Ratio = No. of hits/No. of References
Disadvantages
Too many memory references to access the desired location in physical memory makes Paging slow
Internal fragmentation
Translation Look-aside Buffer (TLB)
Hardware which uses Cache Memory => Faster than RAM
Has key and value
TLB hit => TLB contains the mapping for the requested logical address
Stores Tags
If TLB Hit then directly access from MM
If TLB miss than use PT to access from MM
If Page Fault then PT access HD for Data and put in MM
EMAT for no Page Fault = Hit(TLB + MM) + Miss(TLB + MM/PT + MM)
Address space identifier (ASIDs) => For context switching
Stored in each entry of TLB, uniquely identifies each process and is used to provide address space protection and allow to TLB to contain entries for several different processes
When TLB attempts to resolve virtual page numbers, it ensures that the ASID for the currently executing process matches the ASID associated with virtual page
If it doesn’t match, the attempt is treated as TLB miss
Paging is closer to the Operating system rather than the User
Segmentation
Logical address space is a collection of segments, these segments are based on user view of logical memory
Each segment has segment number (s) and offset (d), defining a segment
Operating system doesn't care about the User's view of the process, may divide the same function into different pages and those pages may or may not be loaded at the same time into the memory, decreasing the efficiency of the system
Segmentation divides the process into the segments
Each segment contains the same type of functions
Advantages
No internal fragmentation
One segment has a contiguous allocation, hence efficient working within segment
The size of segment table is generally less than the size of page table
It results in a more efficient system because the compiler keeps the same type of functions in one segment
Disadvantages
External fragmentation
The different size of segment is not good for the time of swapping
