Memory Management I
Tom Kelliher, CS42
Oct. 25, 1996
Assumption: several processes competing for memory. Questions:
- How is memory allocated among processes?
- Fixed- or variable-sized allocation chunks?
- Contiguous/non-contiguous allocation?
- Over-commitment. What happens?
- Sometimes, a program can't be loaded ``just anywhere'' in memory.
- When does a symbolic name become associated with a memory location?
- How is that location addressed? (Direct, indexed, indirect, etc.)
Address binding options and consequences
- Compile time. Absolute (direct) addressing used. Program
must be loaded into memory at a fixed location. MS-DOS .COM
- Load time. Compiler/linker insert ``dummy'' references in code.
Loader knows load address at run time, finds and fixes-up dummy references.
- Addressing modes?
- Re-location? Must re-load to re-locate.
- Run time. Pc-relative or base addressing. Base register points to
- On-demand module loading --- ``lazy'' loading.
- Load only what's necessary.
- Static linking --- link at compile-time.
- Larger binaries --- wasted disk space.
- Must re-link source when updating libraries.
- Dynamic linking (shared libraries) --- link at run-time.
- Smaller binaries.
- Automatic library updates.
- In-memory library sharing.
Umm, my program is larger than physical memory. What do I do?
Logical = Virtual
- Program (CPU) generates logical addresses.
- MMU converts them to physical addresses.
- Compile-time, load-time binding: physical address = logical address.
Simple MMU scheme:
Note: Program can utilize compile-time binding.
- Process must be entirely in memory to execute.
- If in ready Q, can swap-out to ``backing store.''
- If in I/O wait must ``lock'' in memory. Why?
- What needs to be swapped out, exactly? The entire partition? The
entire process space?
- Swapping in Unix occurs:
- The system page map has become too fragmented to allocate page
tables for some process.
- There are at least two runnable processes, the average amount of
free memory has been less than that desired ( desfree) over the
last 5 and 30 seconds, and either the paging rate is excessive or the
short-term average memory is less than minfree.
- A swapped-out process is ready to run and a process is found in
memory that has been sleeping for at least 20 seconds; or the
swapped-out process has been out for at least 10 seconds and the process
chosen for swapping out has been in memory at least 20 seconds.
What are we leading up to, here?
- Only one process in memory at a time.
- Must swap to do a context switch. Speed?
- Unused Memory: internal fragmentation.
- Partitions usually of differing sizes.
- Job placement policy.
- Can swap jobs in and out of partitions.
- Internal fragmentation.
- Number of partitions varies.
- Partitions allocated according to process requirements.
- What if a process grows?
- Free list of unallocated holes.
- Placement policies:
- First fit.
- Best fit.
- Worst fit --- worst time, storage utilization.
- External fragmentation.
- Combining adjacent holes.
- Memory compaction --- must be using relocatable code. Minimizing
Thomas P. Kelliher
Thu Oct 24 23:22:18 EDT 1996