Rapid scheduling of interrupt-driven tasks in general-purpose operating systems

Abstract

In this thesis, we propose several techniques that aim to minimize the scheduling latency of high-priority interrupt-driven tasks in the general-purpose operating systems. First, we propose a novel scheduling technique to improve the responsiveness of a real-time process while maintaining relative execution rates of non-real-time processes, called the $\textit{prediction-based micro-scheduler}$. It runs upon existing macro-scheduler and it conditionally rearranges the scheduling pattern generated by the macro-scheduler based on urgent interval prediction and lock hold time prediction. The rearrangement occurs if one process seeks to enter a long non-preemptible section and the operation is predicted to significantly disturb the future execution of a real-time process. To build a theoretical guideline for using the micro-scheduler, we derive a sufficient condition under which the starvation problem does not arise and the relative execution rates can be maintained. We implemented the prototype on Linux 2.6.19. Experimental results show that the average OS latency of a real-time process is reduced up to 34% of the original one while still maintaining relative execution rates of non-real-time processes. Moreover, the performance degradation caused by the micro-scheduler does not exceed 5%. One of key advantages of the micro-scheduler is that it is orthogonal to most related techniques, and this advantage is demonstrated experimentally by combining it with two widely used techniques. Next, we propose two techniques that also aim to minimize the scheduling latency of high-priority interrupt-driven tasks, named the $\textit{interrupt handler migration}$ (IHM) and $\textit{direct interrupt scheduling}$ (DIS). The IHM allows the interrupt handler to be migrated from the interrupt handler thread to the corresponding target process so that additional context switch can be avoided and the cache hit ratio with respect to the data generated by the interrupt han...