Background

Basic Hardware

• There are only two general-purpose storage devices that the CPU may directly access: main memory and registers
  • All data must be moved to these devices in order for the CPU to operate on them
• Registers and register operations typically only take one clock cycle
  • Main memory is only accessible via the memory bus, which takes many clock cycles - The CPU will stall until it has the data required to complete the current instruction
  • To alleviate this, a faster memory called cache is built into the CPU and managed without any OS control
• It is the hardware’s responsibility to ensure that processes have different memory spaces
  • This is because OS memory intervention has too much performance penalty
  • This provides protection between kernel and user processes, and user processes from one another
• All processes have a range of legal addresses
  • Base register sets the smallest memory address the process can access
  • Limit register specifies the size of the range of addressable memory for the process
• To protect the memory, CPU compares all addresses generated in user mode with the registers
  • Any attempt at accessing privileged memory will result in a trap
  • Base and limit registers may only be loaded via a special privileged instruction from the kernel
• The kernel has unrestricted access to user and OS memory

Address Binding

• Programs are usually binary executables on the disk that are brought into memory and placed within a process for execution
  • The input queue is all the processes on the disk waiting to be brought into memory
• Compilers bind symbolic memory locations (variables) from source code into offsets from a relative memory location
• The linkage editor/loader binds offsets from compilation into absolute memory addresses
• The binding of instructions and data into memory can be done at any step:
  • Compile time: If the process memory location is known at compile time, then absolute code may be generated (example MS-DOS .COM file format); thus, their memory locations are bound at compile time
  • Load time: The compiler generates relocatable code, and the final binding to absolute addresses is delayed until load time
  • Execution time: Many processes need to be moved from one segment to another during execution; in order for this to occur, the binding is delayed until the instruction is accessed at execution time
    • Most OSes use this method, as it is the most versatile, but it requires special hardware for memory management

Logical vs. Physical Address Space

• Addresses generated by the CPU are logical addresses
• Addresses seen by the memory unit (memory-address register) are physical addresses
• Compile-time and load-time binding methods produce logical and physical addresses that are identical
  • Execution-time binding has different logical and physical addresses, however; in this case, we usually call the logical addresses virtual addresses (they are interchangeable)
• The set of all logical/virtual addresses generated by a program is its logical address space, and vice-versa for physical addresses
• The mapping of logical address space to physical address space for execution-time binding is performed by the memory management unit (MMU) hardware device
  • The base register is now referred to as the relocation register
  • Whenever a process sends a new address into memory, the value in the relocation register is added to it
• The program never sees the physical addresses; it only sees and works with logical addresses (which has a range 0 to max)
  • All logical addresses must first be mapped to physical addresses before they may be utilized

Dynamic Loading

• So far, we have assumed that processes are limited by the amount of physical memory available on a system
  • We have also assumed that the entire program and all of its data must be contained in physical memory for the process to execute
  • This, however, is not the case in real systems
• The solution: dynamic loading
  • Routines are not loaded until called; they are kept on disk in a relocatable load format
  • Whenever a routine needs to load another routine, the caller first checks whether the callee has already been loaded
    • If the callee has not been loaded yet, the program’s relocatable linker loads the callee into memory and updates the program’s address tables
  • Control is then passed into the newly loaded routine
• Advantage: routines are only loaded when needed
• Does not require kernel intervention; the developers must implement dynamic loading themselves, but the kernel may provide some APIs to help

Dynamic Linking and Shared Libraries

• Dynamically linked libraries are system libraries that are linked to running user programs
  • Static linking: system libraries are combined by the loader into the binary
  • Dynamic linking: linking is postponed until execution time; a stub is in the memory image for every library-routine reference, which includes where to locate the library routine in memory or how to load it if not present
    • When the stub is executed, it checks whether the routine is in memory and loads it otherwise
    • The stub replaces itself with the address of the routine and executes the routine
    • The next time that code segment is reached, the routine is executed directly without needing to check anything
    • Can be extended to library updates; without dynamic linking, all programs would have to be relinked to get access to the new library
    • More than one library version may be loaded at one time, but as long as at least one of them is compatible with the running program, it should be good
    • This system is also known as shared libraries, and generally requires help from the kernel, since the OS is the only entity that can check whether the needed routine is in another process’s memory space, or allow multiple processes to use the same memory address

Swapping

• Processes may be swapped temporarily into a backing store then brought back into memory for continued execution
• Makes it possible for the total physical address of all processes to exceed the memory of the system, which permits multiprogramming

Standard Swapping

• Moving processes between main memory and a backing store (commonly a fast disk)
• Backing store must be large enough to accommodate copies of process memory images for all users and provide direct access to those memory images
• Kernel keeps a ready queue of all process memory images on the backing store or in memory and ready to run
  • If the CPU scheduler decides to execute a process, it calls the dispatcher
  • The dispatcher checks whether the next process in the ready queue is in memory
    • If not, and there is no free memory, it swaps out a process currently in memory with the desired process
    • It also reloads registers and transfers control to the desired process
  • Context-switch time for swaps is pretty high; the latency would be the size of the memory image divided by the transfer rate of the backing store
    • This is only considering one-way swap. Since “swapping” is really two swaps (swapping in and swapping out), you actually need to multiply by 2
• Standard swapping is only as effective as the information that programs provide it
  • The programs running on the system must keep the kernel informed of any changes in memory requirements with request_memory() and release_memory() syscalls
  • Otherwise, the choice of process selection for the swap is completely arbitrary, and not ideal, since the process being swapped out could still require memory
• Problem: processes being swapped out may have pending I/O, which would cause the devices to access memory for a different process than intended after the swap occurs
  • Solution 1: never swap out processes with pending I/O
  • Solution 2: double buffering
    • All I/O operations may only occur in kernel space
    • If an I/O operation is requested by a process, the instruction is copied into the kernel buffer
    • The request in the kernel buffer may only be executed while the process that requested it is active in memory
    • The requesting process may now be swapped, since the I/O request is in a stable memory location (kernel space)
    • Adds overhead, since you have to copy the I/O data from kernel memory to user memory before the user process can access it
• Not used in modern operating systems due to too much swapping time and too little execution time
  • Modified implementations exist; commonly, swapping is disabled by default but will occur if the amount of free memory is drastically low; or also swapping portions of processes rather than entire processes to decrease the time spent swapping

Contiguous Memory Allocation

• Memory is divided into two sections: one for the kernel and another for user processes
  • Since the interrupt vector is typically in lowest memory addresses, the kernel is typically also placed in low memory
• Since several user processes may reside in memory simultaneously, we must consider to how allocate the remaining available memory to processes awaiting execution in the input queue
  • In contiguous memory allocation, every process is contained in a single block of memory that is contiguous to blocks containing subsequent processes

Memory Protection

• How do we prevent a process from accessing memory it doesn’t own?
  • When the CPU scheduler selects a process for execution, the dispatcher loads the relocation and limit registers with the context switch
  • All the logical addresses generated by the CPU are cross-referenced against those registers
  • This effectively protects both the kernel and other users’ programs and data from being modified by the running process
• The relocation-register scheme allows the OS size to change dynamically; this is desirable because:
  • Device drivers are infrequently used, so we shouldn’t keep their data/code in emory
  • A lot of the kernel code is just not used that commonly in general; such is called transient OS code and comes and goes as needed

Memory Allocation

• Memory is allocated into partitions for processes to occupy
• There are many multiple-partition schemes:
  • Fixed-size
    • Each partition contains exactly one process
    • When a partition is free, a process is selected from the input queue and loaded into the free partition
    • When the process terminates, the partition becomes freely available for another process to occupy it
  • Variable-partition
    • The OS keeps a table indicating which parts of memory are available and occupied
    • At system initialization, all memory is available for user processes and is considered “one block” of available memory, or a hole
      • The memory table will overall contain a set of holes of various sizes
    • As processes instantiate, they are put into the input queue
    • The OS keeps track of the memory requirements of each process in the ready queue and the amount of memory available when determining which processes are allocated memory
    • The process is allocated space in memory and competes for CPU time with other processes
    • Whenever the process terminates, it releases memory, which the kernel can fill with another process from the input queue
    • At any given time, there is a list of available block sizes and an input queue
      • The kernel decides on the appropriate scheduling algorithm for the input queue
      • Memory is allocated until the memory requirements of the next process cannot be satisfied (there is no hole large enough to hold that process)
        • Actions the OS can take: wait until a large enough block frees or skip through the input queue to see if there is another process with smaller memory requirements that can be put into memory
    • Bigger holes can be split and recombined accordingly to satisfy a process’s needs
    • This is an instance of the dynamic storage-allocation problem, which deals with satisfying requests of size $n$ from a list of free holes; the solutions are as follows:
      • First fit: allocate the first hole that is large enough
      • Best fit: allocate the smallest hole that is big enough, producing the smallest leftover hole; potential downside: must search the entire list unless it is already ordered by size
      • Worst fit: Allocate the largest hole, producing the largest leftover hole
        • Generally worse than first/best fit in terms of decreasing time and storage utilization

Fragmentation

• The first/best-fit strategies suffer from external fragmentation
  • As processes are loaded/removed from memory, the free memory is broken into little pieces
  • As a result, there can be enough total free space to satisfy a request, but since the holes are not contiguous and cannot be recombined, the request cannot be satisfied
  • Solution: compaction
    • Shuffle the memory contents such that all free memory is contained in one block
    • Only possible if memory relocation is dynamic and performed at execution time
    • The cost of compaction
      • The simplest algorithm is to move all processes towards one end of memory and all holes in the other direction (expensive)
  • Another solution: permit noncontiguous segments
    • Processes can be allocated physical memory wherever free memory is available
    • Complementary techniques for this to occur: segmentation and paging
• For first fit, even after optimization, if you have $n$ blocks, another $0.5n$ blocks will be lost to fragmentation (known as the 50-percent rule)
• Internal fragmentation
  • Arises when keeping track of small holes adds more memory overhead than the size of the holes themself
  • Solution: break the physical memory into fixed-size partitions and allocate the memory in units based on each partition’s size
    • With this approach, the memory allocated to a process may be slightly larger than requested
    • The difference between those values is the internal fragmentation: unused memory internal to a partition

Segmentation

Basic Method

References

• Main Memory [Silberschatz, Galvin & Gagne, Operating System Concepts Essentials, p. 347]
• Course slides: MainMemory
• Practice 7 solutions