Operating Systems Lecture Notes

2014 October 21 • Primary Storage

---

Outline

• Primary storage and addresses.
  • The storage hierarchy.
• Programs, processes and address spaces.
  • Logical and physical addresses.
  • Binding, linking and loading.
• Primary store management.

Primary Store

• Primary store (main memory) is a byte array.

  

• A byte is the smallest indexable unit of primary store.
• A byte's address is its index.
• Typically, n = 2^m.
  • m is the address size in bits.

Storage Hierarchy

• Programs executed from primary store (main memory).
  • Instead of from secondary or tertiary store.
• CPUs access (on-chip) registers and (off-chip) primary store directly.
  • Registers: ≤ 1 CPU cycle, 64–512 bytes.
  • Primary store: ≈ 50 CPU cycles, 100 Mbytes to low Gbytes.
• On-chip cache buffers primary store
  • 5-10 CPU cycles, low kbytes to 0.5 Mbytes.

Storage Example

Address Spaces

• A process's address space is a contiguous range of addresses.
• The hardware base register defines the address space's lowest legal address.
• The hardware limit register defines the address space size.
• An address a is legal address for process P iff

  base-register ≤ a < limit-register

• Illegal address accesses cause an interrupt.

Physical Addresses

• Addresses in compiled programs could be physical addresses.
  • That is, are primary-store indices.
  • addi r1,@100
• Such programs are absolute or non-relocatable code.
• The compiler binds code and data locations to primary-store addresses.
  • Compile-time binding.

Relocatable Addressing

• Absolute code is inflexible; it can only run in a specific primary store region.
• Programs use different addresses:
  • Symbolic source addresses.
  • Compiled into relocatable addresses.
  • Linked or loaded into absolute addresses.
• One address space maps into the next.

Binding

• Three address binding times:
  1. At compilation: absolute addressing.
  2. At program link or load time: resolving relocatable addresses.
  3. At run time: like linking or loading, except at execution time.
• Linking may also relocate relocatable addresses.

Logical and Physical Addresses

• It is convenient (later necessary) to think of CPUs as issuing logical addresses.
  • A physical address for an imaginary, ideal primary store.
• The mapping between logical and physical addresses opens up opportunities.
• Logical addresses can be (are) brought back into the compiler tool chain.

Logical-Physical Mappings

• The logical-physical mapping must be fast; that is, done in hardware.
• The memory-management unit (MMU) does the mapping.
• The mapping (and so the MMU) varies depending on logical addresses.
  • And less frequently on physical addresses.
• The mapping makes logical addresses available to the compilation tool chain.
  • And to programmers.

Dynamic Loading

• Loading all a program's code is wasteful.
  • It ignores the 80-20 rule.
• Instead load code as it's needed; that is, going to be executed.
• Uses execution-time binding.
• No particular OS support needed.
  • Although dynamic linking-loading libraries are helpful.

Dynamic Linking

• Linking merges execution units into other execution units.
• Static linking is done before execution time.
• Dynamic linking is done during execution time.
• Automate dynamic loading using stubs that call dynamic-load library code.
• Dynamically-linked code becomes the basis for shared libraries.

Swapping

• A blocked process is wasting primary store.
• Swapping moves processes out of primary store into secondary store.
• The sum of executing process address spaces exceeds primary store.
• Extend priority scheduling to waiting processes.
  • Lower priority processes get swapped out.
• Relieve over-committed primary store by swapping out processes.

Backing Store

• Programs get swapped out to backing store.
  • A special disk (or special part of a disk) holding process images.
• Disk I-O is orders of magnitude slower (msec) than primary-store access.
  • Wise swapping requires tricky calculations.
• Swapping management is another form of scheduling.
  • Context switching becomes more complicated.

Recapitulation

• Base registers set the lowest legal process address.
• Limit registers set the highest legal process address.
• The MMU maps between process addresses and physical addresses.
• The restriction to a process address space provides inter-process protection.
  • And the operating system is a process too.

Process Space Allocation

• A new process needs a contiguous chunk of primary store to execute.
  • The size of the program's address space.
• Relocatable code can appear anywhere in primary store.
  • Primary store is a sequential (non-sharable) resource.
• This kind of storage management is called contiguous allocation.

Static Partitioning

• Periodically partition primary store in partitions.
  • Daily or weekly.
• New processes get fit into available partitions.
  • Left-over space goes unused.
• Old processes leave (swapped or terminated), new processes enter.

Dynamic Partitioning

• Static partitioning is inflexible and wasteful.
• Carve out partitions as needed by incoming processes.
• Dynamic partitions defined by process address spaces.
• A free list of primary store blocks.
  • Blocks enter and leave the free list.
  • Adjacent blocks coalesce into larger blocks, and are split into smaller blocks.

Block Allocations

• Given an address-space demand, which free block should satisfy it?
• First fit: the first large-enough free block found.
  • An arbitrary-sized left-over block.
• Best fit: the smallest free block large enough.
  • The smallest left-over block.
• Worst fit: the largest free block large enough.
  • The largest left-over block.

Fragmentation

• A pristine block of free space gets splits into unusable fragments.
  • Fragmentation
• External fragmentation: Enough free space, but not in one place.
  • Dynamic partitioning.
• Internal fragmentation: Extra space in a single allocation.
  • Static partitioning.

Compaction

• External fragmentation can be dealt with by compaction.
• Relocatable code is shifted to one end of primary store.
  • Free space moves to the other end.
• Some processes have to be fixed temporarily.
  • During I-O, for example.
• Fragmentation occurs in backing store too.

Summary

• Primary storage and addresses.
  • The storage hierarchy.
• Programs, processes and address spaces.
  • Logical and physical addresses.
  • Binding, linking and loading.
• Primary store management.

References

• The Computer and the Brain by John von Neumann, Yale, 1958.

---

This page last modified on 2014 October 23.