Background

• Typical instruction-execution cycle:
  • fetch instruction from memory
  • decode instruction and fetch operands from memroy
  • execute instructions on operands
  • store results back in memory
• Memory only sees a stream of memory addresses—doesn’t know how they are generated or what they are for

Basic Hardware

• CPU can only operate on data in memory and CPU registers

  • CPU registers are accessible within one cycle of the CPU clock
  • Main memory access requires a transaction on the memory bus, which may take many cycles of the CPU clock
    • CPU may need to stall while it waits for memory access to complete
    • Remedy: add a cache (fast memory between CPU and main memory)

• Important to protect operating system from user processes, and user processes from one another

  • Accomplished by providing seperate memory space for each process

  • Memory space given by a base memory address and the range of the space; each number is stored in its own register

  • The value of these registers can only be modified by the OS via priviledged instruction in kernel mode

  • CPU hardware checks each address generated in user mode to ensure it is in the correct memory space for the process (not accessing OS or another user’s memory)

    

• The OS executing in kernel mode is given unrestricted access to both OS memory and users’ memory

  • so the OS can do its job, eg:
    • context switches,
    • I/O to and from user memory,
    • load users’ programs into users’ memory,
    • dump programs in case of errors,
    • etc.

Address Binding

• Most systems allow user processes to reside in any part of the physical memory

• User program goes through several steps (some optional) before execution

  

• Addresses may be represented differently at each step:

  • Addresses in source program are symbolic (eg. variable names)
  • Compiler binds symbolic addresses to relocatable addresses (eg. 14 bytes from beginning of the module)
  • Linker or loader binds relocatable addresses to absolute addresses

• Binding instructions & data to memory addresses can happen at different steps:

  • Compile time
    • you know where the process will reside in memory at compile time
    • so you generate absolute code with hardcoded (absolute) addresses
    • If starting location changes at some later time, code must be recompiled
  • Load time
    • Location of process in memory is not known at compile time
    • Compiler must generate relocatable code
    • Final binding is delayed until load time
    • If starting address changes, you only need to reload the code to incorporate the changed value
  • Execution time
    • If process can be moved during its execution, binding must be delayed until run time
    • Requires special hardware to work
    • Most operating systems use this method

Logic vs. Physical Address Space

• The user program deals with logical addresses from $0$ to $\text{max}$; it does not know about the physical addresses

• The memory management unit (MMU) maps these logical addresses to physical addresses using the relocation register value

  • Value in the relocation register is added to each logical addr. to get the physical addr.
    • Logical addresses in the range $0$ to $\text{max}$
    • Physical addresses in the range $0 + R$ to $\text{max} + R$ for a base register value $R$

• The MMU dynamically relocates a logical address to the correct physical address

  

Dynamic Loading

• Assumption so far: the entire program and associated data must be in physical memory to execute a process
• Instead, use dynamic loading to load routines dynamically from disk to memory only when needed to optimize memory-space utilization
  • All routines kept on disk in a relocatable load format
  • Main program is loaded into memory and executed
  • When routine calls another routine, checks if the target routine is loaded in memory
    • if NOT, the relocatable linking loader:
      • loads the target routine into memory
      • updates the program’s address tables
      • pass control to the target routine (now in memory)