Computer Science: Address Binding

Addresses represented in different ways at different stages of a program's life:
- Source code addresses are usually symbolic
- Compiled code addresses are bound to relocatable addresses
- Linker or loader binds relocatable addresses to absolute addresses
- Each binding maps one address space to another

Address binding of instructions and data to memory addresses can happen at three different stages:
- Compile time
- Load time
- Execution time

Binding delayed until run time if the process can be moved during its execution from one memory segment to another
Need hardware support for address maps (e.g., base and limit registers)

Logical address space is the set of all logical addresses generated by a program
Physical address space is the set of all physical addresses generated by a program
Logical and physical addresses are the same in compile-time and load-time address-binding schemes
Logical (virtual) and physical addresses differ in execution-time address-binding scheme

Hardware device that at run time maps virtual to physical address
The value in the relocation register is added to every address generated by a user process at the time it is sent to memory
Execution-time binding occurs when reference is made to location in memory
Logical address bound to physical addresses

Static linking – system libraries and program code combined by the loader into the binary program image
Dynamic linking – linking postponed until execution time
Small piece of code, stub, used to locate the appropriate memory-resident library routine
Stub replaces itself with the address of the routine, and executes the routine

A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution
Total physical memory space of processes can exceed physical memory
Backing store – fast disk large enough to accommodate copies of all memory images for all users
Roll out, roll in – swapping variant used for priority-based scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed

If next process to be put on CPU is not in memory, need to swap out a process and swap in target process
Context switch time can then be very high
Can reduce if reduce size of memory swapped – by knowing how much memory really being used### Page Table Implementation
Each page table entry takes memory to track
Page sizes are growing over time, e.g., Solaris supports 8 KB and 4 MB page sizes
The process view and physical memory are now very different
Each process can only access its own memory by implementation

The page table is kept in main memory
Page-table base register (PTBR) points to the page table
Page-table length register (PTLR) indicates the size of the page table
Every data/instruction access requires two memory accesses: one for the page table and one for the data/instruction
This two-memory-access problem can be solved using a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs)

TLBs store address-space identifiers (ASIDs) in each TLB entry to uniquely identify each process and provide address-space protection
Otherwise, the TLB would need to be flushed at every context switch
TLBs are typically small (64 to 1,024 entries)
On a TLB miss, the value is loaded into the TLB for faster access next time
Replacement policies must be considered, and some entries can be wired down for permanent fast access

Associative memory allows for parallel search
Address translation (p, d) involves searching for p in associative registers; if found, the frame number is retrieved
Otherwise, the frame number is retrieved from the page table in memory

Associative lookup takes ε time units
Hit ratio (α) is the percentage of times a page number is found in the associative registers, which relates to the number of associative registers
Effective access time (EAT) = (1 + ε)α + (2 + ε)(1 – α)
For example, with a hit ratio of 80% and ε = 20ns, EAT = 120ns
With a more realistic hit ratio of 99%, EAT = 101ns

Memory protection is implemented by associating a protection bit with each frame to indicate if read-only or read-write access is allowed
A valid-invalid bit is attached to each entry in the page table: "valid" indicates the page is in the process' logical address space, and "invalid" indicates the page is not in the process' logical address space
Any violations result in a trap to the kernel

Shared code allows multiple processes to share the same copy of read-only (reentrant) code
Private code and data have each process keeping a separate copy
Shared pages can be useful for interprocess communication if sharing of read-write pages is allowed

Breaking up the logical address space into multiple page tables can reduce memory usage
A two-level page table is a simple technique to implement hierarchical paging
We then page the page table

Hashed page tables are used in address spaces > 32 bits
The virtual page number is hashed into a page table, which contains a chain of elements hashing to the same location
Each element contains the virtual page number, the mapped page frame, and a pointer to the next element

Inverted page tables track all physical pages, rather than each process having a page table
Each entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page
Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs
A hash table can be used to limit the search to one – or at most a few – page-table entries