The Memory Hierarchy
- Registers - one cycle, 64-512 bytes
- On-chip cache (L1 or L2) - 2 cycles, 1-32 kb
- Off-chip cache (L2) - 5 cycles, 32-512 kb
- Main (primary) memory - 30 cycles, 1 mb - 8 gb
- Secondary memory - 106 cycles, 100 mb - 1 tb
- Tertiary memory - 100-500 ms, 600 mb and up
- Off-line memory - 1s - 10 m, whatever
- Our principle concern is with primary-secondary memory.
- Merge both ends of the hierarchy: have register-speed storage in
- Also, fit ten pounds of process into five pounds of memory.
- Also hide latency, promete sharing, provide protection.
The Memory Model
- Storage is modeled as a fixed array of elements.
- The array has constant size N.
- The array element is the storage unit.
- The element is not further divisible by the array.
- The element's index is its address.
- The difference between primary and secondary store is the sizes of
N and the storage units.
- For primary store, N is around 512*106 and
sizeof(storage unit) = 1, 4, or 8.
- For disk store, N is around 50*109 and
unit) = 2i for 9 <= i <= 12.
- Initially a process's storage requirements are simple.
- A process occupies a contiguous, constant-size block of storage.
- The storage block does not change size during process execution.
- The OS, as a process, also needs storage.
- OS storage has a fixed size, and a fixed location.
- However, it need not be contiguous.
- OS occupied storage is called system space.
- Hardware and the OS prevent non-OS access to system space.
- Any storage not in system space can be used by non-OS processes.
- Begin simply, with at most
one non-OS process
running at a time.
- There is no storage management; each non-OS proces can use whatever's
not in system space.
- Storage management consists of loading each process into non-system
- Process size can be checked by the compiler, the job scheduler, or by
- The compiler can check the size of the compiled program against the
size of the process space.
- The job scheduler can do the same (necessary if programs are linked
together from several object files).
- The job scheduler can just lay the programs in process space and rely
on hardware protection to throw an interrupt when the program
intrudes on system storage or falls off the end of primary store.
Program Code and Data
- A program is a sequence of instructions and data.
- Each instruction or datum occupies one storage unit, and each storge
unit holds one of either an instrution or a datum.
- An instruction or datum may contain an address of another instruction
- Branch to an instruction, or load the value of some datum into a
register, for example.
- Data may contain pointers to other data.
- primary storage shared among several processes - partitioning
- fixed partitions - possibly of different sizes
- Assigning incoming processes to partitions.
- Queues of waiting processes - single vs. multiple queues
- Finding the best fit between process and partition size - any,
- Compile - link - load.
- Absolute and relative addresses.
- Relocation - adjusting absolute addresses to match assigned addresses.
- Linking - modifying the program.
- Base register - addresses are absolute relative to a base.
- Prevent concurrent processes from accessing each other's storage.
- Key bits - capabilities.
- Base register and limit registers - segments.
- Pack processes more tightly
- Eliminate process size restrictions (up to the size of primary
- Really big idle processes
- Fragmentation - holes of idle storage
- Swapping moves processes between primary and secondary storage.
- Big, idle processes? Move them to disk.
- Fragmentation - compress running processes to one end of primary
- But defragmentation is slow and CPU intensive.
- What is a process's storage requirements?
- Static process growth - real time system, fortran programs
- Dynamic process growth - everything else
- allocate near holes
- Overestimate requirements and manage extra space within the process
- Allocation - return a block of free space of at least k units
- Coalescing - reassemble fragments
- block storage into chunks - allocation unit; bit count
vs. wasted space
- fast and simple for small amounts of storage
- deallocation is easy
- allocation can be difficult - look for a k-unit chunk
- alternating sequences of allocated and free storage
- small allocation units - bytes even
- allocation is easy
- deallocation is a bit less easy - free-space coalescing
- what's the relation between the size of the request and the size
of the allocated block
- first fit - fast
- next fit - fast, larger-grain fragmentation (in theory)
- best fit - slow, prone to fine-grain fragmentation
- worst fit - ha ha ha
- buddy system allocation - allocate one-half a hole
Multiple Free Lists
- process and free space
- by size
- quick fit - allocation very fast, deallocation very slow
This page last modified on 25 November 2004.