Memory Management

Address Space

Solving protection and relocation problems When a process runs, the starting physical address of the program is loaded into the base register, and the length is loaded into the limit register Dynamic relocation: Memory access instructions are reinterpreted by adding the value of the base register, checking if the address exceeds the limit, which will generate an error and terminate access Disadvantage: Requires addition and comparison operations, which can be slow without special circuits

Memory Overload

Swapping technique: Idle processes are stored on disk and do not occupy memory when not running Virtual memory: Running with only part of the process loaded into memory

Free Memory Management

By maintaining a linked list that records allocated memory segments and free memory segments, nodes in the linked list either contain a process or a free area between two processes

First fit: Scan through the linked list, split the free area into two halves to allocate unless sizes match exactly Next fit: Record the position of scanned free areas Best fit: Scan from beginning to end, find the smallest free area that can accommodate the process

Virtual Memory

Dividing the process address space into multiple pages, each having a continuous address range When the program waits for part of it to be read into memory, the CPU can be given to other processes to use

Virtual address: Virtual page number (high bits, used as page table index) + offset (low bits) Virtual page number -> Page table entry in page table -> Page frame number -> Replace virtual page number == Real physical address In using virtual addresses, when a process uses instructions to read memory, the virtual address is first sent to the MMU (Memory Management Unit that maintains the page table) to be mapped to a physical address. If not found (flag bit in page table entry is 0), a page fault interrupt occurs; if found, then send the physical address to the memory bus

Physical memory is divided into page frames, virtual address space is divided into pages, page frames and pages are usually the same size, and swapping with disk is done in whole page units

The page table for virtual addresses becomes larger and larger, easily causing performance problems, so TLB is introduced as a local cache for the page table. Modern operating systems can load TLB cache, and when the cache can hold enough entries, it is sufficient

Soft miss: In memory but not in TLB, just update TLB, no need to access disk Hard miss: Not in memory and not in TLB, read page from disk to memory 32-bit address space operating systems use multi-level page tables, 64-bit operating systems can design TLB as a hash table, virtual page tables with the same hash value will be in one bucket, with values as page frame numbers

Page Replacement Algorithms

LRU When page fault occurs, replace the page that has not been used for the longest time C++ implementation

class LRUCache 
{ 
    // store keys of cache 
    list<int> dq; 
  
    // store references of key in cache 
    unordered_map<int, list<int>::iterator> ma; 
    int csize; //maximum capacity of cache 
  
public: 
    LRUCache(int); 
    void refer(int); 
    void display(); 
};

LRUCache::LRUCache(int n) 
{ 
    csize = n; 
}

void LRUCache::refer(int x) 
{ 
    // not in cache
    if (ma.find(x) == ma.end()) 
    { 
        // full, delete tail element 
        if (dq.size() == csize) 
        { 
            //delete tail (longest unused) 
            int last = dq.back(); 
            dq.pop_back(); 
            ma.erase(last); 
        } 
    } 
  
    // also delete if in cache
    else
        dq.erase(ma[x]); 
  
    // insert at head and update reference 
    dq.push_front(x); 
    ma[x] = dq.begin(); 
}

Separating Data Space and Instruction Space

Paging data space and instruction space separately, using linker to determine when to use which space, can double the available address space Shared pages: Separated address spaces can better allow multiple processes to share read-only program pages Avoid releasing shared page tables: Let processes have their own page tables, but point to the same set of page tables If writing to read-only parts, the operating system’s copy-on-write mechanism will be triggered to create a copy

Dynamic Linking

Linking: Scanning .a files, searching for external functions undefined in the program, loading them to binary file when found Static linking wastes a lot of memory space because the system doesn’t know it can share these libraries Dynamic linking compilation process loads stubs that can dynamically bind called functions at runtime. If other processes have loaded this library when running, the library can be shared, avoiding duplicate loading of static linking Also, redistributing DLLs doesn’t require clients to recompile programs Multiple processes sharing the same library can be solved by generating relative address instructions during compilation, or using mmap to map files to part of their virtual address space, allowing inter-process communication through such shared memory

Segmentation of Virtual Address Space

Each segment constitutes an independent address space, requiring programs to provide segment number and address within segment, allowing stack segments to stretch freely, improving space utilization, and helping with protection and sharing

Combining Segmentation and Paging

In x86, CS register stores code segment selector, DS stores data segment selector. Segments are further divided into local segments (program segments) and global segments (system segments including the operating system itself), paging can be enabled or disabled, linear address composition == directory, page, offset

• Text Segment: Memory mapping of executable file code
• Data Segment: Memory mapping of initialized global variables of executable file
• BSS Segment: Uninitialized global variables or static variables (initialized with zero page)
• Heap: Store dynamic memory allocation, anonymous memory mapping
• Stack: Process user space stack, automatically allocated and released by compiler, storing function parameter values, local variable values, etc.
• Memory Mapping Segment: Any memory-mapped file

Differences Between Stack and Heap

Stack: Automatically allocated and released by compiler, storing function parameter values, local variable values, etc. Its operation method is similar to the stack in data structures Heap: Generally allocated and released by programmers, if programmers don’t release it, it may be reclaimed by OS when program ends

The Nature of Functions

The value of a function pointer is the address of the first instruction in the machine code representation of the function A function call requires: passing control (function pointer), passing data (passing 6 parameters through registers, exceeding ones placed on stack frame), recording the address of the next instruction after function returns, allocating space (stack pointer moves to lower address)