You are previewing Advanced Operating Systems and Kernel Applications: Techniques and Technologies.
O'Reilly logo
Advanced Operating Systems and Kernel Applications: Techniques and Technologies

Book Description

Advanced Operating Systems and Kernel Applications: Techniques and Technologies discusses non-distributed operating systems that benefit researchers, academicians, and practitioners. This innovative publication includes an overview of topical issues, methods, and advancements in the field of one-processor operating systems.

Table of Contents

  1. Copyright
  2. Editorial Advisory Board
  3. List of Reviewers
  4. Preface
    1. KERNEL SECURITY AND RELIABILITY
        1. Kernel Stack Overflows Elimination
        2. Device Driver Reliability
        3. Identifying Systemic Threats to Kernel Data: Attacks and Defense Techniques
    2. EFFICIENT MEMORY MANAGEMENT
        1. Swap Token: Rethink the Application of the LRU Principle on Paging to Remove System Thrashing
        2. Application of both Temporal and Spatial Localities in the Management of Kernel Buffer Cache
        3. Alleviating the Trashing by Adding Medium-Term Scheduler
    3. KERNEL FLEXIBILITY
        1. The Exokernel Operating System and Active Networks
    4. I/O PREFETCHING
        1. Exploiting Disk Layout and Block Access History for I/O Prefetch
        2. Sequential File Prefetching in Linux
    5. PAGE REPLACEMENT ALGORITHMS
        1. Adaptive Replacement Algorithm Templates and EELRU
        2. Enhancing the Efficiency of Memory Management in a Super-Paging Environment by AMSQM
  5. Acknowledgment
  6. 1. Kernel Security and Reliability
    1. 1. Kernel Stack Overflows Elimination
      1. ABSTRACT
      2. INTRODUCTION
      3. VIRTUAL MEMORY
      4. STACK ALLOCATIONS
        1. Fixed Size Allocations
        2. Current Solutions
        3. Dynamic Size Allocations
        4. Real Time Considerations
      5. IMPLEMENTATION
        1. Process Descriptor
        2. Exceptions
        3. Interrupt Task
      6. EVALUATION
      7. CONCLUSION
      8. REFERENCES
    2. 2. Device Driver Reliability
      1. ABSTRACT
      2. INTRODUCTION
      3. DEVICE DRIVER OVERVIEW
        1. Driver Software Structure
      4. NOOKS RELIABILITY LAYER
        1. Design
          1. Interposition
          2. Isolation
          3. Communication
          4. Object Tracking
          5. Recovery
        2. Implementation
          1. Interposition
          2. Isolation
          3. Communication
          4. Object Tracking
          5. Recovery
            1. Failure Detection
            2. Recovery Managers
          6. Summary of Nooks
        3. Shadow Driver Recovery
          1. Shadow Driver Operation
          2. Taps
          3. The Shadow Recovery Manager
          4. Shadow Drivers
            1. Passive-Mode Monitoring
            2. Active-Mode Recovery
            3. Stopping the Failed Driver
            4. Reinitializing the Driver
            5. Transferring State to the New Driver
            6. Active-Mode Proxying of Kernel Requests
          5. Shadow Driver Summary
      5. EVALUATION OF NOOKS AND SHADOW DRIVERS
        1. Code Size and Complexity
        2. Reliability
          1. System Survival
          2. Application Survival
            1. Application Survival Results
            2. Application Behavior During Driver Recovery
          3. Performance
            1. Performance Summary
          4. Summary of Nooks and Shadow Drivers
      6. DRIVER FAULT TOLERANCE IN COMMERCIAL SYSTEMS
        1. User-Mode Drivers
          1. Microsoft Windows UMDF
          2. Linux UIO
        2. Xen Hypervisor Drivers
      7. RESEARCH DIRECTIONS
        1. User-Mode Drivers in Microkernels
        2. Type-Safe Drivers
      8. CHAPTER SUMMARY
      9. REFERENCES
    3. 3. Identifying Systemic Threats to Kernel Data: Attacks and Defense Techniques
      1. ABSTRACT
      2. INTRODUCTION
        1. Rootkit Evolution
        2. Our Contribution
      3. ATTACKS
        1. Disable Firewall
        2. Resource Wastage
        3. Entropy Pool Contamination
        4. Disable Pseudo-Random Number Generator
        5. Adding a New Binary Format
      4. ROOTKIT DETECTION VIA AUTOMATED INVARIANT INFERENCE
        1. The Page Fetcher
        2. The Data Structure Extractor
        3. The Invariant Generator
        4. The Monitor
        5. Persistent vs. Transient Invariants
      5. EXPERIMENTAL RESULTS
        1. Experimental Methodology
        2. Detection Accuracy
          1. Disable Firewall Attack
          2. Resource Wastage Attack
          3. Entropy Pool Contamination Attack
          4. Disable PRNG Attack
          5. Adding Binary Format Attack
        3. Invariants and False Positives
        4. Performance
      6. CONCLUSION
      7. FUTURE WORK
        1. Data Structure Repair
        2. Mining Complex Invariants
      8. REFERENCES
    4. 4. The Last Line of Defense: A Comparison of Windows and Linux Authentication and Authorization Features
      1. ABSTRACT
      2. THE LAST LINE OF DEFENSE: THE OPERATING SYSTEM
        1. Security and Operating System Security Architecture
        2. Apples to Oranges: Comparing Windows and Linux
      3. AUTHENTICATION
        1. Windows Authentication
        2. Linux Authentication
      4. AUTHORIZATION
        1. Windows Authorization
        2. Linux Authorization
        3. Linux Security Modules and Mandatory Access Controls
      5. ASSESSMENT
        1. Evaluation of OS Implementation of Security Principles
      6. SUMMARY AND CONCLUSION
      7. REFERENCES
  7. 2. Efficient Memory Management
    1. 5. Swap Token: Rethink the Application of the LRU Principle on Paging to Remove System Thrashing
      1. ABSTRACT
      2. INTRODUCTION
      3. BACKGROUNDS OF THRASHING PROTECTIONS
        1. Local Page Replacement
        2. The Working Set Model
        3. Load Controls
        4. Advantages of a Lightweight Thrashing Prevention Mechanism
      4. EXPERIMENTAL OBSERVATION OF PROGRAM'S ACCESS PATTERNS
        1. The Benchmark Programs
        2. Experimental System Setup
        3. Memory Access Behavior in The Dedicated Environment
      5. MEMORY PERFORMANCE DUE TO INTERACTIONS OF DIFFERENT TYPES OF PROGRAMS
        1. Performance Metrics
        2. Memory Performance of Program Interactions
        3. Development of Thrashing
      6. DESIGN AND IMPLEMENTATIONS OF SWAP TOKEN
        1. The LRU Page Replacement in Linux
        2. The Implementation of the Swap Token in Linux
        3. Fairness Issue in Memory Usage
        4. A Close Look at the Effect of Swap Token
      7. PERFORMANCE OF THE SWAP TOKEN MECHANISM
      8. CONCLUDING REMARKS
      9. REFERENCES
    2. 6. Application of both Temporal and Spatial Localities in the Management of Kernel Buffer Cache
      1. ABSTRACT
      2. INTRODUCTION
      3. CHALLENGES WITH DUAL LOCALITY
      4. THE DULO SCHEME
        1. Structuring LRU Stack
        2. Block Table: A Data Structure For Dual Locality
        3. Forming Sequences
        4. The DULO Replacement Algorithm
      5. PERFORMANCE RESULTS
        1. The DULO Implementation
          1. Linux Caching
          2. Implementation Issues
          3. Experiment Results on File Accesses
          4. Experiment Results with an Aged File System
          5. Experiments on Virtual Memory Paging
      6. RESEARCH ON IMPROVING AND EXPOSING ON-DISK LAYOUT FOR UPPER-LEVEL SOFTWARES
      7. CONCLUSION
      8. REFERENCES
    3. 7. Alleviating the Thrashing by Adding Medium – Term Scheduler
      1. ABSTRACT
      2. INTRODUCTION
      3. THRASHING IN THE LINUX OPERATING SYSTEM
      4. BIN PACKING
      5. BIN PACKING BASED PAGING
        1. Medium-Term Scheduler
        2. Swapping Management
        3. Shared Memory
        4. Group Time Slice
        5. Interactive Processes
        6. Real Time Processes
        7. Priority
      6. PERFORMANCE RESULTS
      7. TESTBED
        1. Execution Time
        2. The Bin Packing Approximations
        3. Priority Implementation Evaluation
        4. Interactive and Real Time Implementation Evaluation
      8. CONCLUSION
      9. REFERENCES
  8. 3. Systems Profiling
    1. 8. The Exokernel Operating System and Active Networks
      1. ABSTRACT
      2. INTRODUCTION
      3. PROBLEM DESCRIPTION
        1. The Need for Flexibility
        2. The Need for Speed
        3. The Approach
      4. THE EXOKERNEL SOLUTION
        1. Tracking Ownership of Resources
        2. Ensuring Protection by Guarding all Resource Usage or Binding Points
        3. Revoking Access to Resources
        4. Management by User Level Library
        5. Shared Libraries
        6. Implementing a Shared Library
        7. The Shared Library Server
        8. Interprocess Communication (IPC)
        9. Exceptions and Interrupts
        10. Disk I/O
        11. Downloading Code into the Kernel
        12. Packet Sending and Receiving
        13. Naming and Routing of Packets
        14. Network Error Reporting
      5. PERFORMANCE RESULTS
        1. Common Applications Benefit from an Exokernel
        2. Exokernel's Flexibility is not Costly
        3. Aggressive Applications are Significantly Times Faster
        4. Local Control can Lead to Enhanced Global Performance
        5. Exokernel's File Storage Scheme Enhances Run-Time
      6. ACTIVE NETWORKING
      7. ANALYSIS AND DISCUSSION
        1. Customer-Support
        2. Eliminating Management
        3. Optimizing Usage
        4. Is Extensibility the Answer?
      8. CONCLUSION
      9. REFERENCES
    2. 9. Dynamic Analysis and Profiling of Multithreaded Systems
      1. ABSTRACT
      2. INTRODUCTION
        1. Understanding Multithreaded System Behavior
        2. Approaches to Extracting Multithreaded Behavioral Characteristics
      3. BACKGROUND
        1. Nondeterministic Behavior in Multithreaded Systems
        2. Behavioral Characteristics Relevant to Multithreaded Programs
        3. Challenges of Multithreaded System Profiling
      4. COMPILER-BASED INSTRUMENTATION TECHNIQUES
        1. Source-code instrumentation
        2. Static Binary-Code Instrumentation
        3. Dynamic Binary-Code Instrumentation
        4. Summary of Compiler-Based Instrumentation Techniques
      5. OPERATING SYSTEM AND MIDDLEWARE PROFILING TECHNIQUES
        1. Profiling System Call Interception
        2. Microsoft Windows Performance Counters
        3. Distributed System Profiling
          1. Monitoring of Component-Based Systems (MCBS)
          2. OVATION
        4. Summary of operating System and Middleware Profiling Techniques
      6. VIRTUAL MACHINE PROFILING TECHNIQUES
        1. Sampling-Based VM Profiling
          1. Bytecode Counting
        2. Profiling via VM Hooks
          1. CLR Profiler
          2. JVMTI Profiler
        3. Application Code Instrumentation
        4. Aspect-Oriented Techniques Used for Instrumentation
        5. Summary of Virtual machine Profiling Techniques
      7. HARDWARE-BASED PROFILING TECHNIQUES
        1. On-Chip Performance Counters
        2. On-Chip Debugging Interfaces and In-Circuit Emulators (ICE)
        3. Summary of hardware-based Profiling Techniques
      8. FUTURE TRENDS
        1. Increased Focus on Synergies between Static and Dynamic Analysis Techniques and Tools
        2. Greater Emphasis on Probabilistic Assurance of Dynamic System Behavior
        3. Implicit Support for Measurement of Infrastructure Software and Processors
        4. Total-System Measurement that Relates and Combines Microscopic Measurements Together to Give a Unified view of System Behavior
      9. CONCLUDING REMARKS
      10. REFERENCES
      11. ADDITIONAL READING
  9. 4. I/O Prefetching
    1. 10. Exploiting Disk Layout and Block Access History for I/O Prefetch
      1. ABSTRACT
      2. INTRODUCTION
      3. BACKGROUND
        1. Prefetching
        2. Prefetching at Logic File Level
        3. Prefetching in Disk Firmware
        4. A Disk-Level Prefetch Policy – Diskseen
      4. TRACKING DISK ACCESSES
        1. Disk Layout Information
        2. The Block Table
      5. THE DESIGN OF DISKSEEN
        1. Overview
        2. Recording Access Indices
        3. Coordinating with File-Level Prefetching
        4. Sequence-Based Prefetching
          1. Sequence Detection
          2. Sequence-Based Prefetching
          3. Managing Prefetched Blocks
        5. History-Aware Prefetching
          1. Disk Access Trails
          2. Matching Trails
          3. History-Aware Prefetching
        6. Balancing Memory Allocation
      6. IMPLEMENTATION ISSUES
      7. PERFORMANCE EVALUATION
        1. Workloads
        2. Experimental Results
          1. Strided and Reversed
          2. CVS and Diff
          3. Grep
          4. TPC-H
          5. Disk Request Size
      8. CONCLUSION
      9. REFERENCES
    2. 11. Sequential File Prefetching in Linux
      1. ABSTRACT
      2. INTRODUCTION
      3. PRINCIPLES OF I/O PREFETCHING
        1. Storage Devices
          1. 2.2 I/O Optimization and Prefetching
        2. Basic Approaches to Prefetching
        3. Design Tradeoffs of Prefetching
      4. READAHEAD IN LINUX
        1. The Page Cache
        2. Readahead Windows and Pipelining
        3. Call Convention
        4. Sequentiality
        5. Concurrent Streams
        6. Readahead Sequence
      5. CASE STUDY
        1. A Typical Readahead Stream
        2. Readahead Cache Hits
        3. Readahead Thrashing
        4. Non-Trivial Sequential Reads
        5. Locally Disordered Reads
      6. PERFORMANCE EVALUATION
        1. Intermixed Random and Sequential Reads
        2. Interleaved Sequential Streams
        3. Readahead Thrashing
      7. CONCLUSION
      8. REFERENCES
    3. 12. Peer–Based Collaborative Caching and Prefetching in Mobile Broadcast
      1. ABSTRACT
      2. INTRODUCTION
      3. BACKGROUND
        1. Mobile Broadcast
        2. System Model
        3. Sample Applications
        4. Data Access Process
        5. KR: Keep Requesting
        6. Caching and Prefetching
          1. Individual Caching
          2. Individual Prefetching
          3. Cooperative Caching
          4. Cooperative Prefetching
      4. ISSUES, CONTROVERSIES, PROBLEMS
      5. EFFECTIVE COLLABORATIVE CACHING AND PREFETCHING SCHEMES
        1. CPIX: Cooperative Caching
        2. ACP: Cooperative Prefetching
          1. Deciding Whether to Send Out Announcement
          2. Making Final Decision
        3. Discussion on Relying on Neighbors
      6. EVALUATION OF COLLABORATIVE CACHING AND PREFETCHING SCHEMES
        1. Simulation Model
          1. Broadcast Server
          2. Mobile Peers
          3. List of Parameters
        2. Experimental Results
          1. Basic Performance Study
          2. Adaptability to Non-Uniform Broadcast
          3. Effect of Moving Speed
          4. Effect of Transmission Range
          5. Effect of Cache Size
      7. CONCLUSION
      8. REFERENCES
  10. 5. Page Replacement Algorithms
    1. 13. Adaptive Replacement Algorithm Templates and EELRU
      1. ABSTRACT
      2. INTRODUCTION
      3. ADAPTIVE REPLACEMENT TEMPLATES
      4. IMPLEMENTING ADAPTIVE REPLACEMENT ALGORITHMS—THE EELRU ALGORITHM
      5. EMPIRICAL PERFORMANCE OF EELRU
      6. CONCLUSION
      7. REFERENCES
    2. 14. Enhancing the Efficiency of Memory Management in a Super–Paging Environment by AMSQM
      1. ABSTRACT
      2. INTRODUCTION
      3. SUPER-PAGES OF THE SUN MICROSYSTEM'S SPARC MACHINES
      4. PAGE REPLACEMENT ALGORITHMS
        1. The "Clock" Page Replacement Algorithm
        2. The Arc Page Replacement Algorithm
      5. SUPER-PAGES AND ARC
        1. Larger Pages
        2. Fragmentation
        3. Thrashing
        4. Coarse Granularity
        5. Gathering the Accesses
      6. THE AMSQM PAGE REPLACEMENT ALGORITHM
      7. EVALUATION AND RESULTS
        1. Testbed and Benchmarking
        2. Benchmarking Using SPEC-2000
        3. The Threshold Setting Considerations
        4. The βEta Setting Considerations
        5. Heavy Memory Consuming Benchmarks
      8. CONCLUSION AND FUTURE WORK
      9. ACKNOWLEDGMENT
      10. REFERENCES
  11. Compilation of References
  12. About the Contributors