Re: percentage based CPU scheduling

From: Nick Landsberg (SPAMhukolauTRAP_at_SPAMworldnetTRAP.att.net)
Date: 08/06/04 

Date: Fri, 06 Aug 2004 21:42:42 GMT

Jean-David Beyer wrote:

> Juhan Leemet wrote (in part):
>
>> BTW, sometimes SMP helps responsiveness of systems, by having more CPUs
>> available for runnable processes or interrupts. Tho under really heavy
>> loads all CPUs will get evenly loaded. That's as it should be!
>>
>> As an example, if I'm running setiathome twice on a dual SMP machine, I
>> do "feel it". The system is not quite as responsive as when that
>> constant background CPU load isn't there. I interpret that as the
>> higher probability of some task having to run until the end of its time
>> slice before that CPU is vailable for another process at the same
>> (normal) priority.
>>
> I have two hyperthreaded Xeon processors in this machine. Linux treats
> this as four processors, so I run four instances of setiathome. I run them
> at nice level 19, giving them the lowest probability of running.
>
> If a higher priority process becomes runnable, this is surely because some
> interrupt or another changed something to take it out of the wait state
> and stuck it in a ready queue. I do not believe the Linux kernel would
> allow a setiathome process to run until the end of its time slot before
> running a higher priority process.
>
> But I do not dispute your feeling that the system becomes less responsive.
>
> E.g., I have an extremely IO intensive application (populating a
> database). If I run it with no instances of setiathome running, it takes
> about 35 minutes to run. If 4 instances of setiathome are running, it
> dakes between 45 and 50 minutes to run even though the dbms servers run at
> nice level 0 and PRI 15 to 25.
>
> It is my view that what is happening is not that the scheduler is failing
> to honor the priorities, but that when the IO limited process(es) start an
> IO, they lose the processor until the IO completes and during that time,
> setiathome dirtys up the L1, L2, and L3 caches so that the IO limited
> process, once it gets a processor, finds the cache hit ratio is zero;
> i.e., it is running out of the main RAM (533 MHz) instead of the Caches
> (running at the 3.06GHz processor speed), for about a 5.75x slowdown.

It may be that, Jean-David or it may be something else.

As I recall the scheduling algorithm (which may have changed
since the time I was familiar with it) you are absolutely
right when you say that the I/O limited processes lose the
processor(s) when they start an I/O.

The algorithm I remember is that these processes are marked
"not-runnable" in the process table. When this occurs,
the scheduling algorithm is consulted to determine the next
process to run. When the I/O interrupt
occurs signalling that the I/O is done, the low-level
interrupt routine does a few things and does a wakeup()
(which marks the process as runnable).

When next the scheduler kicks-in, all runnable processes
are scanned and scheduled according to the priority scheme
i.e. - one of them gets the CPU. The others are still marked
runnable but have to wait out the time-slice or wait until
the running process relinquishes the CPU.

Just for argument's sake, assume that the I/O wait time
for a disk is 5 milliseconds and the time-slice is 10 ms.
The first process does a disk read and is put to "sleep"
waiting for the interrupt.

Also assume that the second process is CPU-bound and never
does a blocking system call. Thus, the process which
was blocked on I/O would not be scheduled when the
interrupt happened, but only when the time-slice of
the second process expired. Using these (fictitious)
numbers, the throughput of the first process would
effectively be halved.

(All this is from memory of how the scheduler worked
may years ago. Things probably changed since then.)

>
>>
>>> Neither nice nor the total cpu time are usable for this. I found two
>>> schedulers in the internet:
>>
>>
>
> What two schedulers?
>
> 

-- 
"It is impossible to make anything foolproof
because fools are so ingenious"
  - A. Bloch

Relevant Pages

  • Re: em network issues
    ... | cheaper to run a task than it is to run an ithread. ... configurations (mainly ones with more CPU than I/O) it gives more I/O ... identical interrupt handler.) ...
    (freebsd-net)
  • Re: Concurrent Sequential
    ... Part B could be "starved" of the CPU. ... interrupt" it seems inflexible. ... OK, lets look at a simplified transaction system. ... There are usually dozens of transactions "in process" at any one time; most of them are waiting for an I/O completion. ...
    (comp.arch)
  • Re: [PATCH] O13int for interactivity
    ... >> I have been hearing of people complaining the scheduler is worse ... >CPU time not spent in I/O and other overhead. ... >between CPU and I/O is a formidable challenge. ...
    (Linux-Kernel)
  • Re: 21st Century ISA goals?
    ... memory to do I/O. ... that live down in the SouthBridge chip of are accessed through the ... device driver codes, and interrupt codes, (using existing CPU MMU ...
    (comp.arch)
  • Re: SMP performance degradation with sysbench
    ... because userspace could not keep up enough load to the scheduler. ... There simply were fewer runnable tasks than CPU cores. ... When you said idle I thought idle and not waiting for I/O. ...
    (Linux-Kernel)