Lecture Notes for Operating Systems

Memory Management, 2 November 2004

Early Memory

• Physical representations, such as pegs, holes and wires.

• Acoustic delay lines.

• CRT displays (Williams tube storage).

• Magnetic drum storage.

• vacuum tubes and relays

• Core storage.

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 - 10⁶ 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.

Memory Manager

• Merge both ends of the hierarchy: have register-speed storage in disk-like quantities.

• 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.

Memory Models

• The difference between primary and secondary store is the sizes of N and the storage units.

• For primary store, N is around 512*10⁶ and sizeof(storage unit) = 1, 4, or 8.

• For disk store, N is around 50*10⁹ and sizeof(storage unit) = 2ⁱ for 9 <= i <= 12.

Process Storage

• 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.

OS Storage

• 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.

Monoprogramming

• 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 space.

• Process size can be checked by the compiler, the job scheduler, or by hardware protection.

  • 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 or datum.

  • Branch to an instruction, or load the value of some datum into a register, for example.

  • Data may contain pointers to other data.

Multiprogramming

• primary storage shared among several processes - partitioning

• fixed partitions - possibly of different sizes

Paritions

• Assigning incoming processes to partitions.

• Queues of waiting processes - single vs. multiple queues

• Finding the best fit between process and partition size - any, best, worst.

Program Relocation

• 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.

Storage Protection

• Prevent concurrent processes from accessing each other's storage.

• Key bits - capabilities.

• Base register and limit registers - segments.

Partitionless Allocation

• Pack processes more tightly

• Eliminate process size restrictions (up to the size of primary storage).

• Really big idle processes

• Fragmentation - holes of idle storage

Process Swapping

• Swapping moves processes between primary and secondary storage.

• Big, idle processes? Move them to disk.

• Fragmentation - compress running processes to one end of primary storage.

• But defragmentation is slow and CPU intensive.

Process Storage

• What is a process's storage requirements?

• Static process growth - real time system, fortran programs

• Dynamic process growth - everything else

  • Stack and heap storage.

• allocate near holes

• Overestimate requirements and manage extra space within the process itself.

Free-Space Management

• Allocation - return a block of free space of at least k units

  • Minimize fragmentation.

• Deallocation.

• Coalescing - reassemble fragments

Bit Maps

• 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

Linked Lists

• alternating sequences of allocated and free storage

• small allocation units - bytes even

• allocation is easy

• deallocation is a bit less easy - free-space coalescing

Free-Space Allocation

• 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.