swap-sched consists of two parts: the automatic dependency detection component and the dependency based scheduling component. swap-sched detects the dependency among tasks by monitoring/instrumenting the inter-process communication/synchronization related system calls. Since all the inter-process communications/synchronizations (except shared-memory) are done via system calls, the dynamic dependencies can be effectively detected by instrumenting these system calls.
In a conventional CPU scheduler, a task is removed from the runqueue once it's blocked. This is a PROBLEM since a high priority task's request is ignored once it's blocked, even though it's blocked because of waiting for the execution of another task. Based on this observation, swap-sched solves the priority inversion problem by make two simple changes to the existing CPU scheduler. First, it keeps all the tasks that are blocked but depends on some other tasks that are runnable in runqueue. (We call such tasks are virtual runnable tasks). Second, the existing CPU scheduler is called as usual. But since the virtual runnable tasks are in runqueue, they may be scheduled. In this case the swap scheduler is called to choose one of the providers of the task (the task that the virtual runnable task depends on) to run.
Our results show that SWAP has low overhead, effectively solves the priority inversion problem and can provide substantial improvements in system performance in scheduling processes with dependencies. For the mpeg player + X scenario discussed above, mpeg player can play at 23 frm/s with swap-sched enabled!!!
This swap-sched project is based on our paper published on NSDI'04 [2]. The paper is available as (PDF), (HTML). The results presented in our paper is based on our implementation for Linux 2.4.18-8 (Redhat 8.0). But now we have upgraded SWAP to support Linux 2.6.