OS Fundamentals / Ch 2

system performance depends on:
memory available and utilization of memory during job processing
the 4 types of memory allocation schemes are:
single-user systems, fixed partitions, dynamic partitions and relocatable dynamic partitions
available in 1940s & 50s, entire program loaded into memory, contiguous memory space allocated as needed, jobs processed sequentially, memory manager performs minimal work
single-user contiguous scheme
in a single-user scheme, the memory manager:
uses a register to store the base address & uses an accumulator to track program size
no support for multiprogramming or networking, not cost effective, program size must be < memory size
disadvantages of single-user scheme
commercially available in the 1950s & 60s, main memory partitioned at startup, uses 1 contiguous partition per job, allows multiprogramming, partition sizes are static
fixed partition scheme
requires contiguous loading of entire program, arbitrary partition size leads to internal fragmentation, job allocation method assigns first available partition w/ required size (wasteful), all jobs must be same size & memory size must be known ahead of time to work well
disadvantages of fixed partitions
jobs given memory requested when they are loaded, one contiguous partition per job
dynamic partition scheme
full memory utilization only during loading of first jobs, results in external fragmentation
disadvantages of dynamic partitions
memory allocation that uses the first partition that fits the job size requirements – leads to fast allocation of memory space
first-fit
memory allocation that assigns the smallest partition fitting the job size requirements – results in least wasted space, reduces internal fragmentation
best-fit
disadvantage: slow in making memory allocation
best-fit
disadvantage: leads to memory waste
first-fit
first-fit algorithm: memory manager keeps two lists:
one for free memory and one for busy memory blocks
starts searching from last allocated block for next available block when a new job arrives
next-fit
allocates largest free available block to new job
worst-fit
freeing allocated memory space is called
deallocation
straightforward process – memory manager resets the status of job’s memory block to “free” upon job completion
deallocation process in fixed-partition system
algorithm tries to combine free areas of memory, 3 types of cases arise
deallocation process in dynamic-partition system
dynamic partition deallocation – Case 1
block to be deallocated is *adjacent* to free block
dynamic partition deallocation – Case 2
block to be deallocated is *between* 2 free blocks
dynamic partition deallocation – Case 3
block to be deallocated is *isolated* from other free blocks
memory allocation scheme in which the memory manager gathers together all empty blocks & makes 1 block large enough to accommodate waiting job(s)
relocatable dynamic partitions
reclaiming fragmented sections of memory space
compaction
OS must distinguish between addresses & data values, every address is adjusted to account for the program’s new location in memory, data values are left alone.
compaction
Lists that must be updated in relocatable dynamic partitions:
free list, busy list and address list
special-purpose registers used for relocation in relocatable dynamic partitions
bounds register and relocation register
stores highest location accessible by each program
bounds register
contains the value that must be added to each address referenced in the program, must be able toe access the correct memory addresses after relocation
relocation register
compaction entails more:
overhead
common requirements of 4 memory management techniques
entire program must be loaded, contiguous storage, remain in memory until completed