SCHED_EDF infos

SCHED_EDF infos

[finarfin]

Hi,
I'm new to this list,

Actually i'm near to BS degree in computer science, and for thesis my
Operating System Professor suggested to complete (or begin?) SCHED_EDF for
linux. 

Now i don't know if i'm able to do that, i'm new to linux-kernel
development:
1. Someone is already working on that? This task is still available?
2. Now there was something implemented about sched_edf?
3. Into sched-rt-groups.txt there was something that was not very clear (in
my opinion): 
   The next project will be SCHED_EDF (Earliest Deadline First scheduling)
to bring
   full deadline scheduling to the linux kernel. Deadline scheduling the
above
   groups and treating end of the period as a deadline will ensure that
they both
   get their allocated time.

   Implementing SCHED_EDF might take a while to complete. Priority
Inheritance is
   the biggest challenge as the current linux PI infrastructure is geared
towards
   the limited static priority levels 0-139. With deadline scheduling you
need to
   do deadline inheritance (since priority is inversely proportional to the
   deadline delta (deadline - now).
   
   Priority inheritance is a different task? 
4. In your opinion three months will be sufficient for that task? (yeah
probably this seems a silly question, but if working on that take me a too
long time i think i have to find another thesis :D i wish to have my degree
before the end of this year)  
5. For implement that algorithm the general EDF documentation will be
sufficient? There are some special requisites?
6. if you have any suggestion i'll be glad to receive it :)

I hope that this mail doesn't sound useless. 

Thank you, 
Ivan

Re: SCHED_EDF infos

[Henrik Austad]

[-- Attachment #1: Type: text/plain, Size: 4765 bytes --]

On Wednesday 29. April 2009 23.36.13 finarfin@dreamos.org wrote:
> Hi,
> I'm new to this list,

If you're new to Linux, may I suggest kernelnewbies as well? This is not really the place to ask beginners questions, for that, kn is really the place.

And, if you are going to look at rt-tasks, look at linux-rt:

       http://rt.wiki.kernel.org/index.php/Main_Page

> Actually i'm near to BS degree in computer science, and for thesis my
> Operating System Professor suggested to complete (or begin?) SCHED_EDF for
> linux. 

Se comment at the very end about EDF vs. other policies.

As a first step, I would have evaluated the benefits and limitations of EDF in a multicore environment. 
- What will be the major restrictions?
- What will be the major improvements? (why should the kernel care about yet another scheduling policy)
- Are there better ways of doing this? (like pfair)
- are you going for partitioned, clustered or global edf? (and remember that they all have good and bad sides).
- why is a global approcah the only way of getting an optimal scheduler, but a horrible approach from a practical point of view?
- and a lot of other issues that will be apparent once you start looking at this.

I did some work on this last year, you are more than welcome to look at that.

       http://folk.ntnu.no/henrikau/sched/rt_sched_pro.pdf

> Now i don't know if i'm able to do that, i'm new to linux-kernel
> development:
> 1. Someone is already working on that? This task is still available?

I'm working on SCHED_PFAIR :-) Which is a multicore, ratebased deadline driven global scheduling policy where I use the PD^2 rules to solve tie-breaks. In theory, it can reach 100% utilization on all cores without missing deadlines (but in practice you will only get close to 100% as it is not perfect).

> 2. Now there was something implemented about sched_edf?

No, nothing deadline driven is implemented as of yet.

> 3. Into sched-rt-groups.txt there was something that was not very clear (in
> my opinion): 

If you are going to implement something deadline driven and have some sort of deadline guarantees, I'd suggest going for a policy *above* sched_rt and let SCHED_(RR|FIFO) be best effort tasks.

>    The next project will be SCHED_EDF (Earliest Deadline First scheduling)
> to bring
>    full deadline scheduling to the linux kernel. Deadline scheduling the
> above
>    groups and treating end of the period as a deadline will ensure that
> they both
>    get their allocated time.

Are you aware that this is actually very difficult to get right? There are a *lot* of other things going on in the kernel, you will have unexpected latencies etc.

>    Implementing SCHED_EDF might take a while to complete. Priority
> Inheritance is
>    the biggest challenge as the current linux PI infrastructure is geared
> towards
>    the limited static priority levels 0-139. With deadline scheduling you
> need to
>    do deadline inheritance (since priority is inversely proportional to the
>    deadline delta (deadline - now).

I'd suggest getting the scheduler running first, then look at those problems later. If you spend all your time trying to learn the scheduler and design in every little feature you need, you'll never finish in time.

deadline inversion will be a problem, in fact, whatever you chooose to be the 'key' for picking tasks (priority, niceness, deadlines, wind direction,                  <whatever>), you can pretty much take that and add a -inversion after it. :)

>    Priority inheritance is a different task? 
> 4. In your opinion three months will be sufficient for that task? (yeah
> probably this seems a silly question, but if working on that take me a too
> long time i think i have to find another thesis :D i wish to have my degree
> before the end of this year)  

That depends on how much you know about the scheduler. And believe me, it is a *lot* of things to take care of.

> 5. For implement that algorithm the general EDF documentation will be
> sufficient? There are some special requisites?
> 6. if you have any suggestion i'll be glad to receive it :)

The problem with EDF is that it is not multicore aware. Sure, you can implement a global EDF and have it move to all cores, but then you're basically stuck at 50% utilization if you want to have any form of deadline handling. Sure there  are ways of increasing this if you make sure that all the deadlines are not a factor of another, that the hyperperiod is sufficiently large etc etc.

> I hope that this mail doesn't sound useless.

No silly questions, just silly answers. 
(well, here *are* silly questions, but they tend to be ignored)

> Thank you, 
> Ivan

Henrik

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: SCHED_EDF infos

[GeunSik Lim]

Hi Henlik,

Thank you for explanation and your doc(PDF) about SCHED_EDF implementation
 in Linux.

2009/4/30 Henrik Austad <henrik@austad.us>:
> On Wednesday 29. April 2009 23.36.13 finarfin@dreamos.org wrote:
>> Hi,
>> I'm new to this list,
>
> If you're new to Linux, may I suggest kernelnewbies as well? This is not really the place to ask beginners questions, for that, kn is really the place.
>
> And, if you are going to look at rt-tasks, look at linux-rt:
>
>       http://rt.wiki.kernel.org/index.php/Main_Page
>
>> Actually i'm near to BS degree in computer science, and for thesis my
>> Operating System Professor suggested to complete (or begin?) SCHED_EDF for
>> linux.
>
> Se comment at the very end about EDF vs. other policies.
>
> As a first step, I would have evaluated the benefits and limitations of EDF in a multicore environment.
> - What will be the major restrictions?
> - What will be the major improvements? (why should the kernel care about yet another scheduling policy)
> - Are there better ways of doing this? (like pfair)
> - are you going for partitioned, clustered or global edf? (and remember that they all have good and bad sides).
> - why is a global approcah the only way of getting an optimal scheduler, but a horrible approach from a practical point of view?
> - and a lot of other issues that will be apparent once you start looking at this.
>
> I did some work on this last year, you are more than welcome to look at that.
>
>       http://folk.ntnu.no/henrikau/sched/rt_sched_pro.pdf
>

I think so.
How can we approach  EDF implementation like Pfair as a generic solution
for Multicore in Linux?

>> Now i don't know if i'm able to do that, i'm new to linux-kernel
>> development:
>> 1. Someone is already working on that? This task is still available?
>
> I'm working on SCHED_PFAIR :-) Which is a multicore, ratebased deadline driven global scheduling policy where I use the PD^2 rules to solve tie-breaks. In theory, it can reach 100% utilization on all cores without missing deadlines (but in practice you will only get close to 100% as it is not perfect).
>
>> 2. Now there was something implemented about sched_edf?
>
> No, nothing deadline driven is implemented as of yet.
>
>> 3. Into sched-rt-groups.txt there was something that was not very clear (in
>> my opinion):
>
> If you are going to implement something deadline driven and have some sort of deadline guarantees, I'd suggest going for a policy *above* sched_rt and let SCHED_(RR|FIFO) be best effort tasks.
>
>>    The next project will be SCHED_EDF (Earliest Deadline First scheduling)
>> to bring
>>    full deadline scheduling to the linux kernel. Deadline scheduling the
>> above
>>    groups and treating end of the period as a deadline will ensure that
>> they both
>>    get their allocated time.
>
> Are you aware that this is actually very difficult to get right? There are a *lot* of other things going on in the kernel, you will have unexpected latencies etc.
>
>>    Implementing SCHED_EDF might take a while to complete. Priority
>> Inheritance is
>>    the biggest challenge as the current linux PI infrastructure is geared
>> towards
>>    the limited static priority levels 0-139. With deadline scheduling you
>> need to
>>    do deadline inheritance (since priority is inversely proportional to the
>>    deadline delta (deadline - now).
>
> I'd suggest getting the scheduler running first, then look at those problems later. If you spend all your time trying to learn the scheduler and design in every little feature you need, you'll never finish in time.
In fact, I also  don't have perfect know how to solve PI in Multicore.

>
> deadline inversion will be a problem, in fact, whatever you chooose to be the 'key' for picking tasks (priority, niceness, deadlines, wind direction,                  <whatever>), you can pretty much take that and add a -inversion after it. :)
>
>>    Priority inheritance is a different task?
>> 4. In your opinion three months will be sufficient for that task? (yeah
>> probably this seems a silly question, but if working on that take me a too
>> long time i think i have to find another thesis :D i wish to have my degree
>> before the end of this year)
>
> That depends on how much you know about the scheduler. And believe me, it is a *lot* of things to take care of.
>
>> 5. For implement that algorithm the general EDF documentation will be
>> sufficient? There are some special requisites?
>> 6. if you have any suggestion i'll be glad to receive it :)
>
> The problem with EDF is that it is not multicore aware. Sure, you can implement a global EDF and have it move to all cores, but then you're basically stuck at 50% utilization if you want to have any form of deadline handling. Sure there  are ways of increasing this if you make sure that all the deadlines are not a factor of another, that the hyperperiod is sufficiently large etc etc.
>
>> I hope that this mail doesn't sound useless.
>
> No silly questions, just silly answers.
> (well, here *are* silly questions, but they tend to be ignored)
>
>> Thank you,
>> Ivan
>
> Henrik
>



-- 
Regards,
GeunSik Lim
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: SCHED_EDF infos

[Henrik Austad]

On Fri, May 08, 2009 at 11:35:58AM +0900, GeunSik Lim wrote:
> Hi Henlik,

Hi Lim,


First off, to all of you, sorry for my last, very poorly formatted email. I 
have now tranceded into the realms of mutt.

> [..]
> I think so.
> How can we approach  EDF implementation like Pfair as a generic solution
> for Multicore in Linux?

I am working on an implementation now, and I hope to be able to release a 
prototype by the end of next week. I think we can continue the discussion 
then based on that.

> > I'm working on SCHED_PFAIR :-) Which is a multicore, ratebased deadline 
> > driven global scheduling policy where I use the PD^2 rules to solve 
> > tie-breaks. In theory, it can reach 100% utilization on all cores 
> > without missing deadlines (but in practice you will only get close to 
> > 100% as it is not perfect).

> > [..]
> > I'd suggest getting the scheduler running first, then look at those
> > problems later. If you spend all your time trying to learn the 
> > scheduler and design in every little feature you need, you'll never 
> > finish in time.

> In fact, I also  don't have perfect know how to solve PI in Multicore.
> [...]
> > deadline inversion will be a problem, in fact, whatever you chooose to 
> > be the 'key' for picking tasks (priority, niceness, deadlines, wind 
> > direction, <whatever>), you can pretty much take that and add a 
> > -inversion after it. :)

No, PI is going to be deadly no matter what you do.

Henrik

Re: SCHED_EDF infos

[GeunSik Lim]

On Fri, May 8, 2009 at 6:10 PM, Henrik Austad <henrik@austad.us> wrote:
>> [..]
>> I think so.
>> How can we approach  EDF implementation like Pfair as a generic solution
>> for Multicore in Linux?
>
> I am working on an implementation now, and I hope to be able to release a
> prototype by the end of next week. I think we can continue the discussion
> then based on that.
Hi Henrik,
Can you share EDF that you implemented with P-fair for Multicore environments?
Especially, I wonder How do you keep posix compatibility with EDF scheduler.

For example,
sched_setscheduler(2), sched_getscheduler(2),
sched_get_priority_max(2), sched_get_priority_min(2),
sched_getaffinity(2), sched_setaffinity(2),
sched_getparam(2), sched_setparam(2),
setpriority(2), getpriority(2),
sched_yield(2), sched_rr_get_interval(2)


-- 
Regards,
GeunSik Lim ( SAMSUNG ELECTRONICS)
Blog : http://blog.naver.com/invain/
e-Mail: geunsik.lim@samsung.com
           leemgs@gmail.com , leemgs1@gmail.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: SCHED_EDF infos

[Henrik Austad]

On Sat, May 30, 2009 at 08:38:29PM +0900, GeunSik Lim wrote:
> On Fri, May 8, 2009 at 6:10 PM, Henrik Austad <henrik@austad.us> wrote:
> >> [..]
> >> I think so.
> >> How can we approach  EDF implementation like Pfair as a generic solution
> >> for Multicore in Linux?
> >
> > I am working on an implementation now, and I hope to be able to release a
> > prototype by the end of next week. I think we can continue the discussion
> > then based on that.
> Hi Henrik,

Hi!

btw, that 'end of next week'.. *sigh*

> Can you share EDF that you implemented with P-fair for Multicore environments?
> Especially, I wonder How do you keep posix compatibility with EDF scheduler.

Well, what exactly do you mean by posix compatibility? What I'm doing, is adding 
another scheduling class on top of sched_rt so that sched_pfair will be polled 
before any other class. I was not aware that POSIX had an EDF standard?

> For example,
> sched_setscheduler(2), sched_getscheduler(2),
> sched_get_priority_max(2), sched_get_priority_min(2),
> sched_getaffinity(2), sched_setaffinity(2),
> sched_getparam(2), sched_setparam(2),
> setpriority(2), getpriority(2),
> sched_yield(2), sched_rr_get_interval(2)

I introduce 3 new syscalls for modifying the tasks. 

 sched_pfair_update()
 - change an existing task into a pfair task, set attributes, calculate subjob 
   values etc

 sched_pfair_release()
 - release the task, i.e. enable it to run on a CPU.

 sched_pfair_reweigh()
 - change the attributes of the task. In a lot of ways, this is very similar to 
   pfair_update, but it introduces some problems when trying to reweigh a task 
   that is running, or if the new values lead to over-utilization of the system.

At the moment, this is only for my own convenice, but I have tried to modify as 
little of the existing code as possible to avoid merge conflicts etc. So, none 
of the existing syscalls have been modified in any way.

I'm a bit unsure as to what your question actually is, perhaps you could 
elaborate a bit about what you're concered about?

henrik

Re: SCHED_EDF infos

[GeunSik Lim]

On Sat, May 30, 2009 at 10:34 PM, Henrik Austad <henrik@austad.us> wrote:
>> Can you share EDF that you implemented with P-fair for Multicore environments?
>> Especially, I wonder How do you keep posix compatibility with EDF scheduler.
>
> Well, what exactly do you mean by posix compatibility? What I'm doing, is adding
This means that We can use  realtime programming for EDF effectiveness with
current system call interface without new system call interface.

> another scheduling class on top of sched_rt so that sched_pfair will be polled
> before any other class. I was not aware that POSIX had an EDF standard?
POSIX describes common real-time specification  without EDF, RMS ,
Resource Reservation, etc.
Belows is the Linux Standard Base (LSB) specifications for Linux Distributions.
http://www.linuxfoundation.org/en/Specifications
>
>> For example,
>> sched_setscheduler(2), sched_getscheduler(2),
>> sched_get_priority_max(2), sched_get_priority_min(2),
>> sched_getaffinity(2), sched_setaffinity(2),
>> sched_getparam(2), sched_setparam(2),
>> setpriority(2), getpriority(2),
>> sched_yield(2), sched_rr_get_interval(2)
>
> I introduce 3 new syscalls for modifying the tasks.
>
>  sched_pfair_update()
>  - change an existing task into a pfair task, set attributes, calculate subjob
>   values etc
>
>  sched_pfair_release()
>  - release the task, i.e. enable it to run on a CPU.
>
>  sched_pfair_reweigh()
>  - change the attributes of the task. In a lot of ways, this is very similar to
>   pfair_update, but it introduces some problems when trying to reweigh a task
>   that is running, or if the new values lead to over-utilization of the system.
When we try to userspace realtime programming, How can we insert  systemcall api
with posix compatibility.
Um... In general, we use
sched_setscheduler    (struct task_struct *p, int policy,  struct
sched_param *param) api.

If we will make  EDF related u/s rt programming, How do we have to
insert deadline of tasks
for EDF performance?
sched_setscheduler_EDF(struct task_struct *p, int policy, period-time
, runtime)
or

struct sched_param {
       int sched_priority;
      <timespec edf-period-time>;
      <timespec edf-runtiome>;
};

I am not sue...

>
> At the moment, this is only for my own convenice, but I have tried to modify as
> little of the existing code as possible to avoid merge conflicts etc. So, none
> of the existing syscalls have been modified in any way.
>
> I'm a bit unsure as to what your question actually is, perhaps you could
> elaborate a bit about what you're concered about?
>
> henrik
>



-- 
Regards,
GeunSik Lim ( SAMSUNG ELECTRONICS)
Blog : http://blog.naver.com/invain/
e-Mail: geunsik.lim@samsung.com
           leemgs@gmail.com , leemgs1@gmail.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: SCHED_EDF infos

[Henrik Austad]

On Sat, May 30, 2009 at 11:46:43PM +0900, GeunSik Lim wrote:
> On Sat, May 30, 2009 at 10:34 PM, Henrik Austad <henrik@austad.us> wrote:
> >> Can you share EDF that you implemented with P-fair for Multicore environments?
> >> Especially, I wonder How do you keep posix compatibility with EDF scheduler.
> >
> > Well, what exactly do you mean by posix compatibility? What I'm doing, is adding

> This means that We can use  realtime programming for EDF effectiveness with
> current system call interface without new system call interface.

Well, as I said, at the moment I'm at the 'making it work'-stage, so adding 
features to the existing syscalls is not really something I'm prepared to do :-)

> > another scheduling class on top of sched_rt so that sched_pfair will be polled
> > before any other class. I was not aware that POSIX had an EDF standard?

> POSIX describes common real-time specification  without EDF, RMS ,
> Resource Reservation, etc.
> Belows is the Linux Standard Base (LSB) specifications for Linux Distributions.
> http://www.linuxfoundation.org/en/Specifications

Hoh, that was a lot of 'requried reading' :-s I'll try to have a look at it 
soon.

> >> For example,
> >> sched_setscheduler(2), sched_getscheduler(2),
> >> sched_get_priority_max(2), sched_get_priority_min(2),
> >> sched_getaffinity(2), sched_setaffinity(2),
> >> sched_getparam(2), sched_setparam(2),
> >> setpriority(2), getpriority(2),
> >> sched_yield(2), sched_rr_get_interval(2)
> >
> > I introduce 3 new syscalls for modifying the tasks.
> >
> >  sched_pfair_update()
> >  - change an existing task into a pfair task, set attributes, calculate subjob
> >   values etc
> >
> >  sched_pfair_release()
> >  - release the task, i.e. enable it to run on a CPU.
> >
> >  sched_pfair_reweigh()
> >  - change the attributes of the task. In a lot of ways, this is very similar to
> >   pfair_update, but it introduces some problems when trying to reweigh a task
> >   that is running, or if the new values lead to over-utilization of the system.

> When we try to userspace realtime programming, How can we insert  systemcall api
> with posix compatibility.

At the moment, I've created a new sched-param struct:

struct sched_pfair_params {
        u64 period_ns;
        u64 wcet_ns;
        u64 deadline_ns;
        u64 release_ns;
        u8 periodic:1;
};

so I can add this via a single variable to the syscalls.

> Um... In general, we use
> sched_setscheduler    (struct task_struct *p, int policy,  struct
> sched_param *param) api.

yes, I know, but I *really* didn't want to meddle with the exisint interface, so 
atm, I've just added my own syscalls.

> If we will make  EDF related u/s rt programming, How do we have to
> insert deadline of tasks
> for EDF performance?
> sched_setscheduler_EDF(struct task_struct *p, int policy, period-time
> , runtime)
> or
> 
> struct sched_param {
>        int sched_priority;
>       <timespec edf-period-time>;
>       <timespec edf-runtiome>;
> };

Could be, I guess this is up for debate. Having a dedicated structure for this 
is not good, but I hope my reason above can explain why it is like this at the 
moment.


henrik

Re: SCHED_EDF infos

[Peter Zijlstra]

On Fri, 2009-05-08 at 11:10 +0200, Henrik Austad wrote:
> > In fact, I also  don't have perfect know how to solve PI in Multicore.
> > [...]
> > > deadline inversion will be a problem, in fact, whatever you chooose to 
> > > be the 'key' for picking tasks (priority, niceness, deadlines, wind 
> > > direction, <whatever>), you can pretty much take that and add a 
> > > -inversion after it. :)
> 
> No, PI is going to be deadly no matter what you do.

Right, we would need to extend the Priority Inheritance Protocol to
include everything the regular scheduling functions operate on.

That is, we can reduce scheduling to a single order operator that orders
all the available tasks, such that t_n < t_n+1.

For pure EDF that would be a comparison on deadlines (and available
bandwidth), for FIFO on static priority and for CFS something based on
the virtual runtimes of the involved tasks. For the combined set of
these scheduling classes the comparator uses the class hierarchy to
order between them.

Lets call the full set of data that is used to determine this order a
task's key.

If we then substitute this key for the static priority of the classic
PIP and use this generic comparison operator, it can be extended to
cover arbitrary complex scheduling functions.


This is a bit like the Proxy Execution Protocol, where we leave the
blocked task in the runqueue, but run another task in its stead. The key
point is that it donates the full task state as relevant to the
scheduling function, or even more directly, it uses the scheduler
itself, to solve the Priority Inversion.

Re: SCHED_EDF infos

[Henrik Austad]

On Sat, May 30, 2009 at 09:15:57PM +0200, Peter Zijlstra wrote:
> On Fri, 2009-05-08 at 11:10 +0200, Henrik Austad wrote:
> > > In fact, I also  don't have perfect know how to solve PI in Multicore.
> > > [...]
> > > > deadline inversion will be a problem, in fact, whatever you chooose to 
> > > > be the 'key' for picking tasks (priority, niceness, deadlines, wind 
> > > > direction, <whatever>), you can pretty much take that and add a 
> > > > -inversion after it. :)
> > 
> > No, PI is going to be deadly no matter what you do.
> 
> Right, we would need to extend the Priority Inheritance Protocol to
> include everything the regular scheduling functions operate on.
> 
> That is, we can reduce scheduling to a single order operator that orders
> all the available tasks, such that t_n < t_n+1.
> 
> For pure EDF that would be a comparison on deadlines (and available
> bandwidth), for FIFO on static priority and for CFS something based on
> the virtual runtimes of the involved tasks. For the combined set of
> these scheduling classes the comparator uses the class hierarchy to
> order between them.
> 
> Lets call the full set of data that is used to determine this order a
> task's key.
> 
> If we then substitute this key for the static priority of the classic
> PIP and use this generic comparison operator, it can be extended to
> cover arbitrary complex scheduling functions.

I think you can do this in pick_next_task, actually.

I wonder, will it be enough to add a single task_struct *blocker to task_struct? 

Then you will end up with a list (or tree of tasks) all ending in a single task 
that holds the required resource. Say task A,B,C,D and E holds some critical 
resource, then you can end up with (awful ascii-art to starboard!):

   A -> B -> E
             ^
             |
        C -> D

So, whenever A-D is being scheduled, E will be picked by pick_next_task as it 
detects that it is blocked, so it follows the blocker untill it finds an 
unblocked task. That task  must then be the holder of the resource.

Now, the 'only' thing that needs to be done, is to let the kernel update the 
blocker with the correct task, and detect the moment it releases the resource.

Or am I missing some crazy racecondition here?

> This is a bit like the Proxy Execution Protocol, where we leave the
> blocked task in the runqueue, but run another task in its stead. The key
> point is that it donates the full task state as relevant to the
> scheduling function, or even more directly, it uses the scheduler
> itself, to solve the Priority Inversion.

come to think of it, this should be doable in pfair. Basically, the task can be 
picked as you suggest, and it would not interfere with *any* other tasks other 
than the task it blocks. And, if you do it recursively, for each task it blocks 
(that depend on the resource or the release of another blocked task), it will 
gradually consume more and more of the timeslices. So you will not get unbounded 
execution for non-pfair tasks.

Re: SCHED_EDF infos

[Peter Zijlstra]

On Sat, 2009-05-30 at 22:40 +0200, Henrik Austad wrote:
> On Sat, May 30, 2009 at 09:15:57PM +0200, Peter Zijlstra wrote:
> > On Fri, 2009-05-08 at 11:10 +0200, Henrik Austad wrote:
> > > > In fact, I also  don't have perfect know how to solve PI in Multicore.
> > > > [...]
> > > > > deadline inversion will be a problem, in fact, whatever you chooose to 
> > > > > be the 'key' for picking tasks (priority, niceness, deadlines, wind 
> > > > > direction, <whatever>), you can pretty much take that and add a 
> > > > > -inversion after it. :)
> > > 
> > > No, PI is going to be deadly no matter what you do.
> > 
> > Right, we would need to extend the Priority Inheritance Protocol to
> > include everything the regular scheduling functions operate on.
> > 
> > That is, we can reduce scheduling to a single order operator that orders
> > all the available tasks, such that t_n < t_n+1.
> > 
> > For pure EDF that would be a comparison on deadlines (and available
> > bandwidth), for FIFO on static priority and for CFS something based on
> > the virtual runtimes of the involved tasks. For the combined set of
> > these scheduling classes the comparator uses the class hierarchy to
> > order between them.
> > 
> > Lets call the full set of data that is used to determine this order a
> > task's key.
> > 
> > If we then substitute this key for the static priority of the classic
> > PIP and use this generic comparison operator, it can be extended to
> > cover arbitrary complex scheduling functions.
> 
> I think you can do this in pick_next_task, actually.
> 
> I wonder, will it be enough to add a single task_struct *blocker to task_struct? 
> 
> Then you will end up with a list (or tree of tasks) all ending in a single task 
> that holds the required resource. Say task A,B,C,D and E holds some critical 
> resource, then you can end up with (awful ascii-art to starboard!):
> 
>    A -> B -> E
>              ^
>              |
>         C -> D
> 
> So, whenever A-D is being scheduled, E will be picked by pick_next_task as it 
> detects that it is blocked, so it follows the blocker untill it finds an 
> unblocked task. That task  must then be the holder of the resource.
> 
> Now, the 'only' thing that needs to be done, is to let the kernel update the 
> blocker with the correct task, and detect the moment it releases the resource.
> 
> Or am I missing some crazy racecondition here?

Except for the bit where you avoid multiple cpus trying to run the same
task :-)

It's tracktable, but it really complicates the matter. But yes, PEP is
very attractive.