Priority inversion in real-time file systems
Sara J. Graves, Joel Sherrill · 1999
The problem of priority inversion in real-time file systems is a detriment to the use of file systems in applications that have real-time requirements. Priority inversion is a form of indefinite postponement that is common in multitasking, preemptive operating systems with shared resources such as data or physical devices. Each software layer that reschedules operations acts as a priority domain and can cause priority inversion. This dissertation examines the problem of priority inversion in real-time file systems and presents disk caching and disk scheduling algorithms that are suitable for use in a real-time system. Fair Share, Priority LRU with Priority Inheritance, and Fair Share with Priority Inheritance are new real-time disk caching algorithms in this dissertation. A variety of new real-time disk scheduling algorithms are presented: Priority C-SCAN, Priority N-Step SCAN, Fair Share, Preemptive Priority N-Step SCAN, and Preemptive Fair Share. An evaluation framework for disk caching and disk scheduling algorithms is presented. A File System Simulator that models all of the layers in the file system software stack was developed to aid in the evaluation of new algorithms as well as to evaluate how the choice of file system algorithms impacts the behavior and predictability of a real-time system. Finally, the problem of how disk caching and disk scheduling deal with nearly simultaneous accesses is analyzed. This problem is not addressed in previous literature.