On Sun, 8 May 2005 16:11, Haoqiang Zheng wrote: > swap-sched is a patch that solves dynamic priority inversion problem. > > Run X at normal priority (nice 0) and keep the system really busy by > running a lot of interactive jobs (with dynamic priority at 115), or > simply run some CPU bound tasks at nice -10. Then start a mpeg player > at a high priority (nice -20). What would you expect? In my machine, > the mpeg player runs at poorly 4 frm/s. Why the tasks running at > dynamic priorities of 115 can have such dramatic impact on the > performance of mpeg player running at nice -20? What happens is the > mpeg player often blocks to wait the normal priority X to render the > frames. Without knowing such dependency between mpeg player and X, the > existing Linux scheduler would select other tasks to run and thus > results in poor video playback quality. This problem is generally > known as priority inversion. > > Certainly, this very problem can be solved by setting the priority of > X to nice -10 (like what Redhat etc. does). However, inter-process > communication mechanisms like pipe, socket and signal etc. are widely > used in modern applications, and thus the inter-process dependencies > are everywhere in today's computer systems. It's not possible for a > system administrator to find out all the dependencies and set the > priorities properly. Obviously, we need a system that can dynamically > detects the dependencies among the tasks and take the dependency > information into account when scheduling. swap-sched is such a system. > > swap-sched consists of two components: 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!!! > > Please visit our swap-sched project homepage at > http://swap-sched.sourceforge.net/ for details and latest > patches. Suggestions/Comments are welcomed. Very interesting code. How do you prevent a ring of dependent tasks from DoSing the entire system? eg what happens with process_load in contest - since you asked about this recently I assume you have already tested it. Cheers, Con
Attachment:
pgpuKCs2LPSV1.pgp
Description: PGP signature
- Follow-Ups:
- References:
- [RFC PATCH] swap-sched: schedule with dynamic dependency detection (2.6.12-rc3)
- From: Haoqiang Zheng <[email protected]>
- [RFC PATCH] swap-sched: schedule with dynamic dependency detection (2.6.12-rc3)
- Prev by Date: [RFT/PATCH] KVMS, mouse losing sync and going crazy
- Next by Date: Re: [RFC PATCH] swap-sched: schedule with dynamic dependency detection (2.6.12-rc3)
- Previous by thread: [RFC PATCH] swap-sched: schedule with dynamic dependency detection (2.6.12-rc3)
- Next by thread: Re: [RFC PATCH] swap-sched: schedule with dynamic dependency detection (2.6.12-rc3)
- Index(es):