Please enable JavaScript.

Coggle requires JavaScript to display documents.

Memory Management - Coggle Diagram

- - - - Memory Space
        Every process has a separate memory space.
        
        If a process try to access the other memory space, they will be rejected.
        
        Registers
        
        Base register: 'smallest' physical memory assigned to a process
        
        Also called relocation register
        
        Limit register: 'size' of the assigned section.
        
        Note that this is length, not the address of the largest physical memory
    - - solutions
        
        Worst-fit
        Allocate the hole that is the largest among all the holes that are big enough
        
        Best-fit
        Allocate the hole that is smallest among all the holes that are big enough
        
        First-fit
        Allocate the first hole that is big enough
    - - External Fragmentation
        There is enough total memory space to satisfy a request yet is not contiguous.
      - Internal Fragmentation
        In a fixed-size block scheme, there can be unwanted extra spaces allocated
      - Compaction
        To deal with External Fragmentation, shuffle the memory contents to place all free memory together in one large block.
        
        Not possible if relocation is static and is done at assembly or load time.
  - - - Memory Protection
        Each entry in page table has a bit attached to it
        
        Valid bit
        Associated page is in the process' logical address space, so it's in the physical memory
        
        Invalid bit
        The page is not in the process' logical address space, so it's not in the physical memory (in the secondary device or not owned by this process)
      - Dealing with large logical address
        
        Hashed Page Table
        Hierarchical Paging might not be ideal for large addressing. Instead, page goes through hash function, and the hash value is queried against the hash table, which contains the linked-list of the hashes.
        
        Hierarchical Paging
        Instead of one page table, we can have multiple page table, so one page table can be used to map to other page table.
        
        Inverted Page Tables
        One page table per frame of the main memory.
      - Dirty(modify) Bit
        Dirty bit is set when a write operation occur for the page
        
        If not set, the contents in memory and secondary devices are the exact same, so page out isn't necessary.
    - - Page-Table Base Register/Page-Table Length Register (PTBR/PTLR)
        For machines with large page table, instead of storing all page index in the register, we store them in main memory, and use PTBR to point to the page table.
      - Translation Look-aside Buffer (TLB)
        PTBR requires two memory access (access register and then access the page table pointed by PTBR), TLB is a specialized associative, high-speed memory, which supports simultaneous key comparison.
        
        Hit Ratio
        Percentage of times we could find the page index from TLB instead of the page table.
        
        Effective Memory-Access Time
        Assuming memory access takes 10ns
        \(EMAT = HitRate * 10ns + (1 - HitRate) * 20ns\)
        
        Look-up for TLB take 10ns, and if missed, take another 10ns to look-up the memory
        
        Address-Space Identifiers (ASIDs)
        Some TLB stores ASIDs to uniquely identifies each process to provide address-space protection.
    - - Locality
        related locations are frequently accessed
      - Reference String
        Evaluation metric to test the performance of the replacement algorithm
      - Algorithms
        
        FIFO
        
        Second Chance
        
        OPT
        
        LRU
      - Local Replacement
        replacement frame can be chosen from its own set of allocated frames.
      - Policy
        
        Global Page-replacement Policy
        Keep the amount of free memory above and minimum threshold
        
        Reapers
        
        May apply any of the page-replacement algorithms to reclaim pages from processes if the maximum threshold is reached.
        
        Reaper routine is suspended once free memory drops below minimum threshold
        
        OOM Killer
        Keeps the OOM score of the processes. Higher score increases the likelihood that the process could be terminated by the OOM killer routine.
      - Global Replacement
        allows a process to select a replacement frame from the set of all frames.
        
        Can also select the frame that is currently allocated
        
        The target frame to replace may behave differently (ex. takes more time executing some part)
    - - Minimum/Maximum number of frames
        
        Minimum number of frames per process is defined by the architecture
        
        Maximum number of frames is defined by the amount of available physical memory
      - Algorithms
        
        Equal Allocation
        Split m frames among n processes all equally.
        
        \(m / n\)
        
        Proportional Allocation
        Allocate \(a_i\) to process \(p_i\) proportional to the size of the virtual memory of the process
        
        \(a_i = \frac{s_i}{\sum{s_j}} * m\)
    - - Cause
        
        As faulting processes waiting in the queue for the paging device, the ready queue empties
        
        As CPU utilization decreases, the CPU scheduler increases the degree of multi-programming.
      - Prevention
        We need to know how many frames a process needs.
        
        Page-fault Frequency
        
        If page-fault rate exceeds the upper limit, allocate the process another frame
        
        If page-fault rate falls below the lower limit, remove a frame from the process
        
        Locality Model
        If we allocate less than the size of the current locality, the process will thrash.
        
        Locality: a set of pages that are actively used together.
        
        Overlap: two or more processes has the same pages in their active set
        
        Working-set Model
        Prevents thrashing while keeping the degree of multiprogramming as high as possible
        Working-set: set of pages in the most recent \(\delta \) page referenced. Working-set is also an approximation of the program's locality.
        Working-set size (WSS): The size of the working set
        
        If \(\delta\) is too small, it will not encompass the entire locality
        
        If \(\delta\) is too large, it may overlap several localities
        
        Thrashing will occur if \(\sum{WSS_i} > m\) where m is number of frames
        
        Page Compression
        Compress several frames into a single frame