Operating Systems Lecture Notes

29 February 2012 • Storage Management

---

Outline

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 Storage 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) storage - 30 cycles, 1 mb - 8 gb
• Secondary storage - 10⁶ cycles, 100 mb - 1 tb
• Tertiary storage - 100-500 ms, 600 mb and up
• Off-line storage - 1s - 10 m, whatever
• Our principle concern is with primary-secondary storage.

Storage 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, promote 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 process uses whatever’s not in system space.
• Storage management consists of loading each process into non-system space.

Process Size

• Process size can be checked by the compiler, the job scheduler, or by hardware protection.
  • The compiler checks compiled-program size against process space size.
  • The job scheduler does the same (necessary if programs are linked from object files).
  • The job scheduler puts programs in process space and relies on hardware protection to throw interrupts when the program wanders out of its space.

Program Code and Data

• A program is a sequence of instructions and data.
• Each instruction or datum occupies one storage unit, and each storage unit holds one of either an instruction 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

Partitions

• 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.
• Many flavors of storage protection.
  • None (rare).
  • 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?
• No process growth (static) - real time and embedded system.
• Process growth (dynamic) - 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.
  • Buddy system - take half a loaf.
  • Worst fit - ha ha ha.

Summary

---

This page last modified on 2011 October 9.