Re: RFC for a new Scheduling policy/class in the Linux-kernel

[Giuseppe Lipari]

Dear all,

a few consideration on the BWI scheme, that was mentioned by 
Peter and by Raistlin a few messages ago. I do not know very 
well the PEP scheme, from the discussion until now the basic 
idea looks pretty similar to our protocol. The BWI is described 
in this paper:

[1] http://feanor.sssup.it/~lipari/papers/rtss2001-bwi.ps.gz

(I just removed the password, feel free to download it, I hope IEEE
lawyers will not chase me!).

In essence, when a task is blocked on a lock, its budget may be
consumed by the task holding the lock. A task can be assigned one or
more pairs (budget,deadline), one is its original one, the others are
"inherited" when holding a lock on which other tasks are blocked.

This scheme has advantages and disadvantages.  The advantages are:

1) Isolation. It is easy to see that the budget of a task can be
stolen only by tasks that share common locks, directly or
indirectly. For the sake simplicity, consider only non nested
locks. If two tasks A and B do not share any lock, then they cannot
influence each other. (In the paper, this property is generalized to
nested locks).  This property is useful if we want to isolate the
behavior of one (group of) task(s) from the others. For example, a
"hard real-time" task (group) must be isolated from soft real-time
tasks.  Under EDF other classical protocols (like PI, SRP) do not have
the same property, because letting a task use a critical section for
longer than expected can jeopardize the schedulability of the any
other tasks.


2) Simpler admission test. With other schemes (PI, SRP), it is
necessary to compute blocking times for all tasks, which depend on the
length of the critical sections.  The blocking times are then used in
the admission test formula. However, if one blocking time is wrongly
calculated, at run-time any task can miss its deadline. With BWI,
instead, the admission test is the simpler \sum U_i \leq 1, and
doesnot depend on the length of the critical section.

3) Under the assumption that tasks do not block inside a critical
section, BWI can be implemented in a fairly simple way.

4) It is indeed possible (under certain conditions) to verify the
schedulability of a hard real-time task H by knowing the length of all
critical sections of all tasks that share some lock with H. The very
complex procedure is explained in the paper.

However, BWI has some disadvantages

1) It is only for single processors.

2) From a schedulability point of view, if we want to guarantee that
every task always respects its deadline, when computing its budget we
must calculate the "interference" of other tasks. Since, we have to do
this for every "hard" task, we may end up counting the same critical
section several times, thus wasting some bandwidth.  This is better
explained in the paper (section 6.4.1).

3) If a task is allowed to block in the middle of a critical section
(for example, due to a page fault), the implementation becomes much
more complex.

Concerning point 1, as Raistlin pointed out (see its e-mails), he is
working on extending BWI to multiprocessors, also from a theoretical
point of view. It is possible that the result will be similar to the
one obtained by the Dougleas Niehaus with PEP. We hope he will be able
to add some "theoretical spice"!

Concerning point 2, this cannot be avoided. We believe that BWI is
useful for open systems (where tasks are created/killed dynamically)
and for soft real-time systems. However, under certain conditions, it
allows to schedule and analyse hard real-time tasks, even when mixed
with soft real-time tasks.

Concerning point 3, this is the most difficult point. In fact,
achieving an efficient implementation in this case seems very
unlikely. However, we believe that blocking inside a critical section
it is probably a rare event, and then maybe it is possible to afford
some extra overhead in such unfortunate cases.

I hope I clarified some obscure issues with BWI! 

Regards,

Giuseppe Lipari


begin:vcard
fn:Giuseppe Lipari
n:Lipari;Giuseppe
email;internet:giuseppe.lipari@xxxxxxxx
tel;work:+39 050882030
tel;fax:+39 050882003
tel;cell:+39 3480718908
version:2.1
end:vcard