more data: SCHED_ULE+PREEMPTION is the problem

Peter pmc at
Tue Apr 10 11:41:48 UTC 2018

Hi Stefan,

  I'm glad to see You're thinking along similar paths as I did. But let 
me fist answer Your question straight away, and sort out the remainder

 > I'd be interested in your results with preempt_thresh set to a value
 > of e.g.190.

There is no difference. Any value above 7 shows the problem identically.

I think this value (or preemtion as a whole) is not the actual cause for 
the problem; it just changes some conditions that make the problem 
visible. So, trying to adjust preempt_thresh in order to fix the
problem seems to be a dead end.

Stefan Esser wrote:

> The critical use of preempt_thresh is marked above. If it is 0, no preemption
> will occur. On a single processor system, this should allow the CPU bound
> thread to run for as long its quantum lasts.

I would like to contradict here.

 From what I understand, preemption is *not* the base of task switching.
AFAIK preemption is an additional feature that allows to switch threads
while they execute in kernel mode. While executing in user mode, a 
thread can be interrupted and switched at any time, and that is how
the traditional time-sharing systems did it. Traditionally a thread
would execute in kernel mode only during interrupts and syscalls, and
those last no longer than a few ms, and for long that was not an issue. 
Only when we got the fast interfaces (10Gbps etc.) and got big monsters 
executing in kernel space (traffic-shaper, ZFS, etc.), that scheme 
became problematic and preemption was invented.

According to McKusicks book, the scheduler is two-fold: an outer logic
runs few times per second and calculates priorities. And an inner logic
runs very often (at every interrupt?) and chooses the next runnable 
thread simply by priority.
The meaning of the quantum is then: when it is used up, the thread is 
moved to the end of it's queue, so that it may take a while until it 
runs again. This is for implementing round-robin behaviour within a
single queue (= a single priority). It should not prevent task-switching 
as such.

Lets have a look. sched_choose() seems to be that low-level scheduler 
function that decides which thread to run next. Lets create a log of its 

With preempt_thresh >= 12 (kernel threads left out):

  PID                COMMAND TIMESTAMP
  18196                 bash 1192.549
  18196                 bash 1192.554
  18196                 bash 1192.559
  66683                  lz4 1192.560
  18196                 bash 1192.560
  18196                 bash 1192.562
  18196                 bash 1192.563
  18196                 bash 1192.564
  79496                 ntpd 1192.569
  18196                 bash 1192.569
  18196                 bash 1192.574
  18196                 bash 1192.579
  18196                 bash 1192.584
  18196                 bash 1192.588
  18196                 bash 1192.589
  18196                 bash 1192.594
  18196                 bash 1192.599
  18196                 bash 1192.604
  18196                 bash 1192.609
  18196                 bash 1192.613
  18196                 bash 1192.614
  18196                 bash 1192.619
  18196                 bash 1192.624
  18196                 bash 1192.629
  18196                 bash 1192.634
  18196                 bash 1192.638
  18196                 bash 1192.639
  18196                 bash 1192.644
  18196                 bash 1192.649
  18196                 bash 1192.654
  66683                  lz4 1192.654
  18196                 bash 1192.655
  18196                 bash 1192.655
  18196                 bash 1192.659

The worker is indeed called only after 95ms.

And with preempt_thresh < 8:

  PID                COMMAND TIMESTAMP

  18196                 bash 1268.955
  66683                  lz4 1268.956
  18196                 bash 1268.956
  66683                  lz4 1268.956
  18196                 bash 1268.957
  66683                  lz4 1268.957
  18196                 bash 1268.957
  66683                  lz4 1268.958
  18196                 bash 1268.958
  66683                  lz4 1268.959
  18196                 bash 1268.959
  66683                  lz4 1268.959
  18196                 bash 1268.960
  66683                  lz4 1268.960
  18196                 bash 1268.961
  66683                  lz4 1268.961
  18196                 bash 1268.961
  66683                  lz4 1268.962
  18196                 bash 1268.962

Here we have 3 Csw per millisecond. (The fact that the decisions are 
over-all more frequent is easily explained: when lz4 gets to run, it 
will do disk I/O, which quickly returns and triggers new decisions.)

In the second record, things are clear: while lz4 does disk I/O, the 
scheduler MUST run bash, because nothing else is there. But when data 
arrives, it runs again lz4.
But in the first record - why does the scheduler choose bash, although
lz4 has already much higher prio (52 versus 97, usually)?

> A value of 120 (corresponding to PRI=20 in top) will allow the I/O bound
> thread to preempt any other thread with lower priority (cpri > pri). But in
> case of a high priority kernel thread being active during this test (with a
> low numeric cpri value), the I/O bound process will not preempt that higher
> priority thread (i.e. some high priority kernel thread).
> Whether the I/O bound thread will run (instead of the compute bound) after
> the higher priority thread has given up the CPU, will depend on the scheduler
> decision which thread to select. And for "timeshare" threads, this will often
> not be the higher priority (I/O bound) thread, but the compute bound thread,
> which then may execute until next being interrupted by the I/O bound thread
> (which will not happen, if no new I/O has been requested).

Exactly. But why does this happen?

Following the trail onwards from sched_choose() we find tdq_choose(), 
and that is quite straightforward looking for something runnable.
The realtime and idle queues are simple and should grab the thread with 
highest priority, but the timeshare queue (which is the interesting 
piece here) has a special gimmick.
It calls kern_sched.c:runq_choose_from() with an extra parameter 
tdq_ridx ("Current removal index").

 From the design papers I get the clue that the heads of the timeshare 
runqueues are arranged in some kind of circular buffer - this is a 
specialty of SCHED_ULE; SCHED_4BSD does not have this feature, and does 
not call runq_choose_from(). And the tdq_ridx is the current index onto 
that circle.

This mechanism (which I do not really understand currently) is the AFAIK 
only "element of distortion", which may cause that *not* the highest 
prio thread is selected to run.

> For preemption to occur,  pri must be numerically lower than cpri, and
> pri must be numerically lower than or equal to preempt_thresh.

Maybe. But as I wrote above, preemption is only concerning threads 
running in kernel mode. And what I want, is simply a normal task 
switching between the two processes running in user mode.

> But, in fact, the same scheduler selection should have occured in test (a),
> too, if e.g. a soft interrupt preempts the compute bound thread. Not sure,
> why this does not happen ... (And this may be an indication, that I do not
> fully understand what's going on ;-) ...)

I think You do understand it - or we both don't understand it ;) - and 
there is still something else going on here which we do not yet see.

> The PRI=85 values in your test case (b) correspond to pri=185, and with
> preempt_thresh slightly higher that that, the lz4 process should still get a
> 50% share of the CPU. (If its PRI grows over that of the CPU bound process,
> it will not be able to preempt it, so its PRI should match the one of the CPU
> bound process).

As mentioned above, this does not work in practice.

What I did instead was take a look at this circular index tdq_ridx.

And what I found there is very strange:
That index indeed moves from 0 to 63 (we have only one runq every 4 
priorities) and repeats, and it takes 1/2 second to get around.

Except when the problem appears - then it suddenly takes more than
six seconds to get around!

tdq_ridx is defined within sched_ule.c, and it is modified only here:

 >         * Advance the insert index once for each tick to ensure that all
 >         * threads get a chance to run.
 >         */
 >        if (tdq->tdq_idx == tdq->tdq_ridx) {
 >                tdq->tdq_idx = (tdq->tdq_idx + 1) % RQ_NQS;
 >                if 
 >                        tdq->tdq_ridx = tdq->tdq_idx;

The comment suggests that tdq_ridx should increment with timer ticks, 
i.e. with constant speed! And, if the clock is stathz, that does figure:
64 / stathz = 0.5 seconds

Here are the logs [2] showing that indeed the speed changes greatly, but 
only in the situation when the problem appears:

preempt_thresh = 0:
           tdq_ridx    timestamp
                 0     32.948718044
                 0     33.453705474
                 0     33.998990897
                 0     34.503690368
                 0     35.003946192
                 0     35.508674863
                 0     36.016583301
                 0     36.518663899

preempt_thresh = 80:
                 0     69.056754055
                 0     69.561710522
                 0     70.066654974
                 0     70.571848226
                 0     71.076660214
                 0     71.576621653
                 0     72.081640256
                 0     72.586606139

piglet running: (and adding half-round 32 for proof)
                 0     32.100767726
                32     32.369727157
                 0     32.619581572
                32     32.965831183
                 0     33.220777200
                32     33.480751369
                 0     33.730745086
                32     33.980736953
                 0     34.235749995
                32     34.494315832
                 0     34.744162342
                32     35.050767367
                 0     35.315405397
                32     35.560715408
                 0     35.820902945
                32     36.068976384

piglet and worker running: now clock is slow!
                32     67.164163127
                 0     70.368819114
                32     73.581467022
                 0     76.817670952
                32     77.195794807
                 0     77.465528087
                32     77.778554940
                 0     78.644335854
                32     82.045835390
                 0     85.258399007
                32     88.478827844
                 0     91.746418960
                32     95.226730336

preempt_thresh back to 0:
                32     47.988086885
                 0     48.255774908
                32     48.507861276
                 0     48.765327585
                32     49.011779231
                 0     49.268056274
                32     49.515563800
                 0     49.815179616
                32     50.067504569
                 0     50.322943146
                32     50.572696557
                 0     50.823302445
                32     51.074755232

I do currently not see how (or if) this would lead to the suboptimal 
selection of a runnable thread - but it might indeed do so. And, if 
there is really a problem with the clock, this may also have further 

But then I have no clue what to make of this, or where to track it 
further. It might be that there is no problem with the scheduler, but 
instead the happening preemption does something bad with the clock.
Or whatever...


More information about the freebsd-stable mailing list