Contents

• List of Figures
• 1 Introduction
  • 1 Thesis contributions
  • 2 Structure of this thesis
  
  
• 2 Background
  • 1 Basics of disk scheduling
    • 1 The scheduling framework
    • 2 Seek-reducing scheduling policies
    • 3 Proportional-share scheduling policies
  • 2 Terminology
  • 3 The underlying problem: deceptive idleness
  
  
• 3 Sources of deceptive idleness
  • 1 Request dependencies
  • 2 Resource contention
  • 3 Experimental characterization of deceptive idleness
    • 1 No deceptive idleness
    • 2 Explicit request dependencies
    • 3 Consequences of metadata sharing
    • 4 Resource contention for memory
  
  
• 4 Effects of deceptive idleness
  • 1 Seek-reducing disk schedulers
  • 2 Proportional-share disk schedulers
    • 1 Experimental characterization on Stride
    • 2 More than two resource containers
    • 3 Simultaneous seek reduction
  
  
• 5 Workarounds for deceptive idleness
  • 1 Application-driven prefetch
    • 1 Multi-process architecture
    • 2 Asynchronous I/O
    • 3 An mmap/mincore/read interface
    • 4 Metadata caching
  • 2 Kernel-driven prefetch
    • 1 Async prefetch may be completely impossible
    • 2 Async prefetch may be impossible from the OS
    • 3 Async prefetch may need large files to detect
    • 4 Async prefetch may not be implemented: practical difficulties
    • 5 Summary of this section
  
  
• 6 Non-work-conserving scheduler solution
  • 1 The NWCS waiting mechanism
  • 2 Process-granularity assumptions
    • 1 Synchronous requests issued by processes
    • 2 Request homogeneity within a process
  • 3 Seek reducing schedulers
    • 1 Variant: ASPTF: Aged SPTF
    • 2 Variant: C-LOOK: Cyclic look
  • 4 Proportional-share schedulers
    • 1 Variant: YFQ: Yet-another Fair Queueing
  • 5 Heuristic combination
  • 6 Real-time schedulers
  • 7 Implementation notes
    • 1 Tagged queueing in SCSI controllers
  • 8 Potential improvements
    • 1 Accumulate more statistics
    • 2 Fix the process-granularity assumptions
  
  
• 7 Experimental evaluation
  • 1 Microbenchmarks
    • 1 Different access patterns
    • 2 Varying thinktimes
    • 3 Proportional-share scheduling
  • 2 Real workloads
    • 1 The Andrew Benchmark
    • 2 The Apache webserver
    • 3 The GnuLD linker
    • 4 The TPC-B database benchmark
  
  
• 8 Related work
  • 1 Scheduling algorithms
    • 8.1.1   Seek-reducing scheduling algorithms
    • 8.1.2   Proportional-share scheduling algorithms
  • 2 Improved I/O processing outside the scheduling policy
  • 3 Other scheduling domains
    • 8.3.1   CPU scheduling
    • 8.3.2   Network packet scheduling
  
  
• 9 Conclusion
• Appendix: Detailed NWCS pseudocode
  • I.  Generic NWCS scheduling framework
  • II.  NWCS heuristic for SPTF
  • III.  NWCS heuristic for Stride
  
  
• Bibliography