Re: Priority Inheritance Test (Real-Time Preemption)

Ingo Molnar
2004-11-26T23:15:24Z

* Esben Nielsen <simlo@phys.au.dk> wrote:

> I am running on -31-7 kernel now - it takes quite some time to run with
> the runall.sh script with 100000 samples per point so I don't have full
> data yet. [...]

btw., do you really need 100,000 samples to get statistically stable
results? I've been running with 1000 samples and it was already more
than usable - i'd say 3000-5000 samples ought to be more than enough.

> But the bounds look like
> depth observed bound theoretical
> 1 1 ms 1 ms
> 2 3 ms 2 ms :-(

are you sure the theoretical limit is 2 msec? I think it's 3 msec, for
the following reason:

there are two types of nonprivileged-task lock sequences allowed in the
2-deep case:

spin_lock(&lock2);
spin_lock(&lock1);
... loop for 1 msec ...
spin_unlock(&lock1);
spin_unlock(&lock2);

or:
spin_lock(&lock1);
... loop for 1 msec ...
spin_unlock(&lock1);

now, with the above locking, the worst case scenario is the following
one, in chronological order [task A and B are unprivileged, RT is the
highprio task]:

task-A task-B task-RT

spin_lock(&lock2);
[ gets lock2 ]
spin_lock(&lock1);
[ gets lock1 ]
spin_lock(&lock2);
[ boosts task-A ]
[ waits ]
[ gets RT prio ] .
spin_lock(&lock1); .
[ boosts task-B ] .
[ waits ] .
. [ gets RT prio ] .
. [ 1 msec loop ] .
. spin_unlock(&lock1); .
[ gets lock 1 ] .
spin_lock(&lock1); .
[ waits ] .
[ 1 msec loop ] . .
spin_unlock(&lock1); . .
[ gets lock1 ] .
spin_unlock(&lock2); .
[ gets lock2 ]
spin_lock(&lock1);
[ boosts task-B ]
[ waits ]
[ 1 msec loop ] .
spin_unlock(&lock1); .
[ gets lock1 ]

the additional 1 msec comes in because the RT task might be blocking on
a task that _itself_ has to wait 1 msec to get its second lock. So we
have 3 msec of maximum waiting altogether.

the additional +1 msec comes from the fact that 1-deep lock/unlock of
lock1 is an allowed operation too - 2 msec would be the limit if the
only sequence is the 2-deep one.

so i think the numbers, at least in the 2-deep case, are quite close to
the theoretical boundary.

agreed?

Ingo