Memory Management

  1. Virtual Memory
    1. Core Concepts and Motivations
      1. Virtual Address Space
        1. Separation of User Logical Memory from Physical Memory
          1. Running Programs Larger than Physical Memory
            1. Illusion of Large Memory
              1. Memory Sharing Benefits
              2. Demand Paging
                1. Basic Concept
                  1. Lazy Swapper
                    1. Page Table Entries for Demand Paging
                      1. Present Bit Usage
                        1. Swap Space Pointers
                        2. Pure Demand Paging
                          1. Prepaging Strategies
                          2. Handling Page Faults
                            1. The Page-Fault Trap
                              1. Steps in Servicing a Page Fault
                                1. Trap to Operating System
                                  1. Check Validity of Reference
                                    1. Find Free Frame
                                      1. Read Page from Disk
                                        1. Update Page Table
                                          1. Restart Instruction
                                          2. Page Fault Handling Optimizations
                                            1. Copy-on-Write Page Faults
                                            2. Performance of Demand Paging
                                              1. Effective Access Time Calculation
                                                1. Page Fault Rate Impact
                                                  1. Impact on System Performance
                                                    1. Memory Access Time Components
                                                    2. Page Replacement
                                                      1. The Need for Page Replacement
                                                        1. Basic Page Replacement Process
                                                          1. Selecting a Victim Page
                                                            1. Writing Back if Modified
                                                              1. Updating Data Structures
                                                                1. Loading New Page
                                                                2. Modify Bit Optimization
                                                                3. Page Replacement Algorithms
                                                                  1. Evaluation of Algorithms
                                                                    1. Reference String Analysis
                                                                      1. Page Fault Rate Metrics
                                                                      2. First-In, First-Out (FIFO) Algorithm
                                                                        1. Operation and Implementation
                                                                          1. Queue-Based Implementation
                                                                            1. Performance Characteristics
                                                                            2. Optimal (OPT) Algorithm
                                                                              1. Theoretical Basis
                                                                                1. Lookahead Requirements
                                                                                  1. Benchmark for Comparison
                                                                                  2. Least Recently Used (LRU) Algorithm
                                                                                    1. Implementation Methods
                                                                                      1. Counter Implementation
                                                                                        1. Stack Implementation
                                                                                        2. Hardware Support Requirements
                                                                                        3. LRU Approximation Algorithms
                                                                                          1. Additional-Reference-Bits Algorithm
                                                                                            1. Second-Chance (Clock) Algorithm
                                                                                              1. Circular Queue Implementation
                                                                                                1. Reference Bit Usage
                                                                                                2. Enhanced Second-Chance Algorithm
                                                                                                  1. Reference and Modify Bits
                                                                                                    1. Four-Class Classification
                                                                                                  2. Counting-Based Algorithms
                                                                                                    1. Least Frequently Used (LFU)
                                                                                                      1. Most Frequently Used (MFU)
                                                                                                        1. Implementation Challenges
                                                                                                        2. Belady's Anomaly
                                                                                                          1. Definition and Examples
                                                                                                            1. FIFO Algorithm Susceptibility
                                                                                                              1. Stack Algorithms
                                                                                                            2. Frame Allocation
                                                                                                              1. Minimum Number of Frames
                                                                                                                1. Hardware Constraints
                                                                                                                  1. Instruction Set Requirements
                                                                                                                    1. Multi-Word Instructions
                                                                                                                    2. Allocation Policies
                                                                                                                      1. Equal Allocation
                                                                                                                        1. Proportional Allocation
                                                                                                                          1. Size-Based Allocation
                                                                                                                            1. Priority-Based Allocation
                                                                                                                            2. Priority Allocation
                                                                                                                            3. Global vs Local Replacement
                                                                                                                              1. Global Replacement Strategy
                                                                                                                                1. Local Replacement Strategy
                                                                                                                                  1. Performance Implications
                                                                                                                                2. Thrashing
                                                                                                                                  1. Definition of Thrashing
                                                                                                                                    1. Causes of Thrashing
                                                                                                                                      1. High Degree of Multiprogramming
                                                                                                                                        1. Insufficient Frame Allocation
                                                                                                                                        2. Detection of Thrashing
                                                                                                                                          1. Working-Set Model
                                                                                                                                            1. Definition of Working Set
                                                                                                                                              1. Working Set Window
                                                                                                                                                1. Working Set Size Estimation
                                                                                                                                                2. Page-Fault Frequency (PFF)
                                                                                                                                                  1. Monitoring Mechanisms
                                                                                                                                                    1. Control Strategies
                                                                                                                                                      1. Threshold Management
                                                                                                                                                      2. Prevention and Recovery
                                                                                                                                                        1. Process Suspension
                                                                                                                                                          1. Frame Reallocation

                                                                                                                                                      Previous

                                                                                                                                                      5. Non-Contiguous Memory Allocation: Segmentation

                                                                                                                                                      Go to top

                                                                                                                                                      Next

                                                                                                                                                      7. Advanced Memory Management Topics