contiguous memory
Summary
Contiguous partitioning
| Feature | Fixed Partitioning | Dynamic Partitioning |
|---|---|---|
| Partition size | Predefined, equal (or fixed set of sizes) | Created dynamically based on process size |
| Memory allocation | One process per partition | Process gets exactly what it needs |
| Fragmentation type | Internal fragmentation | External fragmentation |
| Flexibility | Low | High |
| Complexity | Simple | More complex |
| Utilization efficiency | Poor (wasted space inside partitions) | Better, but degrades over time |
Allocation algorithms
| Algorithm | Core Idea | Search Strategy | Speed | Fragmentation Behavior | Advantages | Disadvantages |
|---|---|---|---|---|---|---|
| first-fit | allocate the first hole that is large enough | scan from beginning, pick first match | fast | moderate external fragmentation | - low overhead - quick allocation | - small holes near the beginning |
| best-fit | allocate the smallest hole that fits the request | search entire list | slow | high external fragmentation (many tiny holes) | - minimizes wasted space per allocation | - expensive search - unusable small fragments |
| worst-fit | allocate the largest available hole | search entire list | slow | lower fragmentation initially, but inefficient use | - leaves large holes for future allocations | - poor overall utilization - can waste large blocks |
Concept
- load-store memory model
- assumes:
- each process occupies a contiguous region
- physical memory is large enough to containe 1 or more processes with complete memory space
Fixed partition
- fixed number of partitions
- each process occupies one partition
- easy to manage and allocate
- partition needs to be large enough to contain the largest of the processes
- smaller processes will lead to wasted memory space -> internal fragmentation
Internal fragmentation
- wasted memory inside the pertition
Dynamic partition
- partition based on actual size of process
- OS needs to keep track of occupied and free spaces(holes)
- flexible
- leads to large number of holes
- smaller holes cannot accommodate larger processes -> external fragmentation
External fragmentation
- wasted memory outside the partition
- holes that are too small
Partition info
- linked list
- store the starting physical address and the size of the partition
T- true for occupied,F- false for not occupied
Allocation algorithms
First-fit
- take the first hole that is large enough
Best-fit - take the smallest hole that is large enough
- lead to small holes, hard to fit other processes
Worst-fit - take the largest hole
- created holes are larger, hopefully other processes can fit
Merge
- join adjacent holes if possible
Compaction
- move the occupied partitions arround to consolidate holes
- less frequently used
- time consuming -> OS will take up CPU time
- moved processes have to pause
| Process | Performance |
|---|---|
| Allocation | |
| Deallocation | |
| Merging |