Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Bill Huey (hui)]

Hi,

On Wed, Apr 13, 2016 at 3:08 AM, Juri Lelli  wrote:
> I'm not sure what you mean by "localized", but I believe DEADLINE should
> be used more widely to service the same kind of applications you are
> referring to. It's still a quite new addition to the scheduler, so it is
> understandable that we still have some legacy to fight. But we can get
> better in the future.

Yeah, I've known about it for a while but it's just so hard for me to imagine
using that for the kinds of cases that I'm thinking about for mixed tasks.
I just don't have an example in my head how that would work since I don't
have a view of how something like EDF would solve some of the basic
cases. That's mostly my ignorance.

The original inspiration for this was problems with how FIFO tasks would
run for long periods of time will stall with touch event handlers. The solution
in multi-media circles seemed to be that (1) using larger buffers to avoid
dropouts were the solution only to cause starvation and other problems
with other important threads.

There has to be some kind of global view of how a system should run.
It's hard for me (self ignorance) to see how something like deadline would
run for continuously running tasks like that under those scenarios and
have that define some kind of global running policy in the system.

That's why I created this for a brain dead view of how to hack this stuff,
with some kind of crude execution pattern, to somehow get some level of
acceptable interactivity yet meet basic hard requirements with audio etc.

Might be a scenario where one would use sched_switch data to help with
deciding that. We ran into a lot of problems with the Qualcomm MSM
architecture and their power management code. Some of the hacks were
pretty brutal and wasted processor time polling the second core aggressively.

I wanted to solve all of these problems more completely and outside of the
current work being done for better or worse.

>> 2) The need for a scheduler to be driven by an external interrupt from a
>> number sources directly.
>
> If you use DEADLINE to service the activity an interrupt source might
> trigger, I think you can already do this.

I'll have to think about this. Would might having a simple example here.

>> 3) The need for a global view of the system so that power management
>> decisions can be made sensibly made in multicore systems. It's not a
>> scheduler alone but ideal would have more influence over power management
>> decision on battery powered devices, etc...
>
> That's true. But it is also already something we currently are working on.
> I don't know if you are following the schedfreq/schedutil threads [1], for
> example, but there we are discussing how to integrate scheduler and
> cpufreq more closely. And you might also be interested in the EAS effort
> [2].

Not yet but I'll look for them.

> OK. Feel free to ask if you also decide to experiment with DEADLINE and
> find any problem with it.

> [1] https://lkml.org/lkml/2016/3/17/420
> https://lkml.org/lkml/2016/2/22/1037
> [2] https://lkml.org/lkml/2015/7/7/754

Thanks, reading them now but they're quite complicated and the threads
are quite long. It'll take time to digest it all

Thanks

bill

Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Bill Huey (hui)]

Hi,

On Wed, Apr 13, 2016 at 3:08 AM, Juri Lelli  wrote:
> I'm not sure what you mean by "localized", but I believe DEADLINE should
> be used more widely to service the same kind of applications you are
> referring to. It's still a quite new addition to the scheduler, so it is
> understandable that we still have some legacy to fight. But we can get
> better in the future.

Yeah, I've known about it for a while but it's just so hard for me to imagine
using that for the kinds of cases that I'm thinking about for mixed tasks.
I just don't have an example in my head how that would work since I don't
have a view of how something like EDF would solve some of the basic
cases. That's mostly my ignorance.

The original inspiration for this was problems with how FIFO tasks would
run for long periods of time will stall with touch event handlers. The solution
in multi-media circles seemed to be that (1) using larger buffers to avoid
dropouts were the solution only to cause starvation and other problems
with other important threads.

There has to be some kind of global view of how a system should run.
It's hard for me (self ignorance) to see how something like deadline would
run for continuously running tasks like that under those scenarios and
have that define some kind of global running policy in the system.

That's why I created this for a brain dead view of how to hack this stuff,
with some kind of crude execution pattern, to somehow get some level of
acceptable interactivity yet meet basic hard requirements with audio etc.

Might be a scenario where one would use sched_switch data to help with
deciding that. We ran into a lot of problems with the Qualcomm MSM
architecture and their power management code. Some of the hacks were
pretty brutal and wasted processor time polling the second core aggressively.

I wanted to solve all of these problems more completely and outside of the
current work being done for better or worse.

>> 2) The need for a scheduler to be driven by an external interrupt from a
>> number sources directly.
>
> If you use DEADLINE to service the activity an interrupt source might
> trigger, I think you can already do this.

I'll have to think about this. Would might having a simple example here.

>> 3) The need for a global view of the system so that power management
>> decisions can be made sensibly made in multicore systems. It's not a
>> scheduler alone but ideal would have more influence over power management
>> decision on battery powered devices, etc...
>
> That's true. But it is also already something we currently are working on.
> I don't know if you are following the schedfreq/schedutil threads [1], for
> example, but there we are discussing how to integrate scheduler and
> cpufreq more closely. And you might also be interested in the EAS effort
> [2].

Not yet but I'll look for them.

> OK. Feel free to ask if you also decide to experiment with DEADLINE and
> find any problem with it.

> [1] https://lkml.org/lkml/2016/3/17/420
> https://lkml.org/lkml/2016/2/22/1037
> [2] https://lkml.org/lkml/2015/7/7/754

Thanks, reading them now but they're quite complicated and the threads
are quite long. It'll take time to digest it all

Thanks

bill

Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Juri Lelli]

On 13/04/16 02:37, Bill Huey (hui) wrote:
> [Trying to resend this so that linux-kernel mailer doesn't reject it.
> ok just found plain text mode. Will cull the CC list in future
> responses]
> 
> Hi Juri,
> 
> It's not for replacing deadline first of all. I'm not fully aware of the
> kind of things being done with deadline and I would like links so that I
> have some kind of reference
> 

OK. You can find references in Documentation, in my first reply and
embedded in the ELC slides as well. Please, let me know if you need more
:-).

> The original motivation for doing this was for a number of reasons:
> 
> 1) Current FIFO/RR policies aren't exact enough for a lot of the mixed
> modern multimedia scenarios I saw working a real-world load on an Android
> like system. Insufficient feedback to interactive UX tasks that include
> things like jackd and pulse audio for low latency applications (music,
> keyboard controllers, touch events...) across a span of tasks across the
> system.
> 
> Deadline seems to be more localized to a specific application's need and
> seems to be hard to use but I'm inexperienced with it. The problems would
> benefit from a simpler solution.
> 

I'm not sure what you mean by "localized", but I believe DEADLINE should
be used more widely to service the same kind of applications you are
referring to. It's still a quite new addition to the scheduler, so it is
understandable that we still have some legacy to fight. But we can get
better in the future.

> 2) The need for a scheduler to be driven by an external interrupt from a
> number sources directly.
> 

If you use DEADLINE to service the activity an interrupt source might
trigger, I think you can already do this.

> 3) The need for a global view of the system so that power management
> decisions can be made sensibly made in multicore systems. It's not a
> scheduler alone but ideal would have more influence over power management
> decision on battery powered devices, etc...
> 

That's true. But it is also already something we currently are working on.
I don't know if you are following the schedfreq/schedutil threads [1], for
example, but there we are discussing how to integrate scheduler and
cpufreq more closely. And you might also be interested in the EAS effort
[2].

> 4) other reasons that should be in the docs but I got sick of writing
> exhaustive documentation on the matter...
> 

:-)

> That's the best I can do for now. I need to post new version with
> compilations fixes. There's a lot of problems with code regarding
> portability and other issues with the initial revision.
> 

OK. Feel free to ask if you also decide to experiment with DEADLINE and
find any problem with it.

Best,

- Juri

[1] https://lkml.org/lkml/2016/3/17/420
https://lkml.org/lkml/2016/2/22/1037
[2] https://lkml.org/lkml/2015/7/7/754

Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Juri Lelli]

On 13/04/16 02:37, Bill Huey (hui) wrote:
> [Trying to resend this so that linux-kernel mailer doesn't reject it.
> ok just found plain text mode. Will cull the CC list in future
> responses]
> 
> Hi Juri,
> 
> It's not for replacing deadline first of all. I'm not fully aware of the
> kind of things being done with deadline and I would like links so that I
> have some kind of reference
> 

OK. You can find references in Documentation, in my first reply and
embedded in the ELC slides as well. Please, let me know if you need more
:-).

> The original motivation for doing this was for a number of reasons:
> 
> 1) Current FIFO/RR policies aren't exact enough for a lot of the mixed
> modern multimedia scenarios I saw working a real-world load on an Android
> like system. Insufficient feedback to interactive UX tasks that include
> things like jackd and pulse audio for low latency applications (music,
> keyboard controllers, touch events...) across a span of tasks across the
> system.
> 
> Deadline seems to be more localized to a specific application's need and
> seems to be hard to use but I'm inexperienced with it. The problems would
> benefit from a simpler solution.
> 

I'm not sure what you mean by "localized", but I believe DEADLINE should
be used more widely to service the same kind of applications you are
referring to. It's still a quite new addition to the scheduler, so it is
understandable that we still have some legacy to fight. But we can get
better in the future.

> 2) The need for a scheduler to be driven by an external interrupt from a
> number sources directly.
> 

If you use DEADLINE to service the activity an interrupt source might
trigger, I think you can already do this.

> 3) The need for a global view of the system so that power management
> decisions can be made sensibly made in multicore systems. It's not a
> scheduler alone but ideal would have more influence over power management
> decision on battery powered devices, etc...
> 

That's true. But it is also already something we currently are working on.
I don't know if you are following the schedfreq/schedutil threads [1], for
example, but there we are discussing how to integrate scheduler and
cpufreq more closely. And you might also be interested in the EAS effort
[2].

> 4) other reasons that should be in the docs but I got sick of writing
> exhaustive documentation on the matter...
> 

:-)

> That's the best I can do for now. I need to post new version with
> compilations fixes. There's a lot of problems with code regarding
> portability and other issues with the initial revision.
> 

OK. Feel free to ask if you also decide to experiment with DEADLINE and
find any problem with it.

Best,

- Juri

[1] https://lkml.org/lkml/2016/3/17/420
https://lkml.org/lkml/2016/2/22/1037
[2] https://lkml.org/lkml/2015/7/7/754

Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Bill Huey (hui)]

[Trying to resend this so that linux-kernel mailer doesn't reject it.
ok just found plain text mode. Will cull the CC list in future
responses]

Hi Juri,

It's not for replacing deadline first of all. I'm not fully aware of the
kind of things being done with deadline and I would like links so that I
have some kind of reference

The original motivation for doing this was for a number of reasons:

1) Current FIFO/RR policies aren't exact enough for a lot of the mixed
modern multimedia scenarios I saw working a real-world load on an Android
like system. Insufficient feedback to interactive UX tasks that include
things like jackd and pulse audio for low latency applications (music,
keyboard controllers, touch events...) across a span of tasks across the
system.

Deadline seems to be more localized to a specific application's need and
seems to be hard to use but I'm inexperienced with it. The problems would
benefit from a simpler solution.

2) The need for a scheduler to be driven by an external interrupt from a
number sources directly.

3) The need for a global view of the system so that power management
decisions can be made sensibly made in multicore systems. It's not a
scheduler alone but ideal would have more influence over power management
decision on battery powered devices, etc...

4) other reasons that should be in the docs but I got sick of writing
exhaustive documentation on the matter...

That's the best I can do for now. I need to post new version with
compilations fixes. There's a lot of problems with code regarding
portability and other issues with the initial revision.

bill

Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Bill Huey (hui)]

[Trying to resend this so that linux-kernel mailer doesn't reject it.
ok just found plain text mode. Will cull the CC list in future
responses]

Hi Juri,

It's not for replacing deadline first of all. I'm not fully aware of the
kind of things being done with deadline and I would like links so that I
have some kind of reference

The original motivation for doing this was for a number of reasons:

1) Current FIFO/RR policies aren't exact enough for a lot of the mixed
modern multimedia scenarios I saw working a real-world load on an Android
like system. Insufficient feedback to interactive UX tasks that include
things like jackd and pulse audio for low latency applications (music,
keyboard controllers, touch events...) across a span of tasks across the
system.

Deadline seems to be more localized to a specific application's need and
seems to be hard to use but I'm inexperienced with it. The problems would
benefit from a simpler solution.

2) The need for a scheduler to be driven by an external interrupt from a
number sources directly.

3) The need for a global view of the system so that power management
decisions can be made sensibly made in multicore systems. It's not a
scheduler alone but ideal would have more influence over power management
decision on battery powered devices, etc...

4) other reasons that should be in the docs but I got sick of writing
exhaustive documentation on the matter...

That's the best I can do for now. I need to post new version with
compilations fixes. There's a lot of problems with code regarding
portability and other issues with the initial revision.

bill

Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Juri Lelli]

[+Luca, as he might be interested]

Hi,

On 11/04/16 22:29, Bill Huey (hui) wrote:
> Hi,
> 
> This a crude cyclic scheduler implementation. It uses SCHED_FIFO tasks
> and runs them according to a map pattern specified by a 64 bit mask. Each
> bit corresponds to an entry into an 64 entry array of
> 'struct task_struct'. This works single core CPU 0 only for now.
> 
> Threads are 'admitted' to this map by an extension to the ioctl() via the
> of (rtc) real-time clock interface. The bit pattern then determines when
> the task will run or activate next.
> 
> The /dev/rtc interface is choosen for this purpose because of its
> accessibilty to userspace. For example, the mplayer program already use
> it as a timer source and could possibly benefit from being sync to a
> vertical retrace interrupt during decoding. Could be an OpenGL program
> needing precisely scheduler support for those same handling vertical
> retrace interrupts, low latency audio and timely handling of touch
> events amognst other uses.
> 

Interesting! I read doc patch and only skimmed through the others, but
I seem to already have a general type of question.

Since you seem familiar with SCHED_DEADLINE [1] (you refer to deadline
scheduling in the doc patch and Dario is in CC :-)), what do you think
is wrong with just use that for this type of workloads?

AFAIK, mplayer (like) type of workloads already play well with deadline
scheduling, and SCHED_DEADLINE is mainline and actively maintained and
developed [2].

Best,

- Juri

[1] http://onlinelibrary.wiley.com/doi/10.1002/spe.2335/abstract
[2] 
http://events.linuxfoundation.org/sites/events/files/slides/SCHED_DEADLINE-20160404.pdf

> There is also a need for some kind of blocking/yielding interface that can
> return an overrun count for when the thread utilizes more time than
> allocated for that frame. The read() function in rtc is overloaded for this
> purpose and reports overrun events. Yield functionality has yet to be fully
> tested.
> 
> I apologize for any informal or misused of terminology as I haven't fully
> reviewed all of the academic literature regarding these kind of schedulers.
> I welcome suggestions and corrects etc
> 
> Special thanks to includes...
> 
> Peter Ziljstra (Intel), Steve Rostedt (Red Hat), Rik van Riel (Red Hat) for
> encouraging me to continue working in the Linux kernel community and being
> generally positive and supportive.
> 
> KY Srinivasan (formerly Novell now Microsoft) for discussion of real-time
> schedulers and pointers to specifics on that topic. It was just a single
> discussion but was basically the inspiration for this kind of work.
> 
> Amir Frenkel (Palm), Kenneth Albanowski (Palm), Bdale Garbee (HP) for the
> amazing place that was Palm, Kenneth for being a co-conspirator with this
> scheduler. This scheduler was inspired by performance work that I did
> at Palm's kernel group along with discussions with the multimedia team
> before HP kill webOS off. Sad and infuriating moment.
> 
> Maybe, in a short while, the community will understand the value of these
> patches for -rt and start solving the general phenomenon of high performance
> multi-media and user interactivity problems more properly with both a
> scheduler like this and -rt shipped as default in the near future.
> 
> [Also, I'd love some kind of sponsorship to continue what I think is
> critical work versus heading back into the valley]
> 
> ---
> 
> Bill Huey (hui) (12):
>   Kconfig change
>   Reroute rtc update irqs to the cyclic scheduler handler
>   Add cyclic support to rtc-dev.c
>   Anonymous struct initialization
>   Task tracking per file descriptor
>   Add anonymous struct to sched_rt_entity
>   kernel/userspace additions for addition ioctl() support for rtc
>   Compilation support
>   Add priority support for the cyclic scheduler
>   Export SCHED_FIFO/RT requeuing functions
>   Cyclic scheduler support
>   Cyclic/rtc documentation
> 
>  Documentation/scheduler/sched-cyclic-rtc.txt | 468 
>  drivers/rtc/Kconfig  |   5 +
>  drivers/rtc/class.c  |   3 +
>  drivers/rtc/interface.c  |  23 +
>  drivers/rtc/rtc-dev.c| 161 +++
>  include/linux/init_task.h|  18 +
>  include/linux/rtc.h  |   3 +
>  include/linux/sched.h|  15 +
>  include/uapi/linux/rtc.h |   4 +
>  kernel/sched/Makefile|   1 +
>  kernel/sched/core.c  |  13 +
>  kernel/sched/cyclic.c| 620 
> +++
>  kernel/sched/cyclic.h|  86 
>  kernel/sched/cyclic_rt.h |   7 +
>  kernel/sched/rt.c|  41 ++
>  15 files changed, 1468 insertions(+)
>  create mode 100644 Documentation/scheduler/sched-cyclic-rtc.txt
>  create mode 100644 kernel/sched/cyclic.c
>  create 

Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Juri Lelli]

[+Luca, as he might be interested]

Hi,

On 11/04/16 22:29, Bill Huey (hui) wrote:
> Hi,
> 
> This a crude cyclic scheduler implementation. It uses SCHED_FIFO tasks
> and runs them according to a map pattern specified by a 64 bit mask. Each
> bit corresponds to an entry into an 64 entry array of
> 'struct task_struct'. This works single core CPU 0 only for now.
> 
> Threads are 'admitted' to this map by an extension to the ioctl() via the
> of (rtc) real-time clock interface. The bit pattern then determines when
> the task will run or activate next.
> 
> The /dev/rtc interface is choosen for this purpose because of its
> accessibilty to userspace. For example, the mplayer program already use
> it as a timer source and could possibly benefit from being sync to a
> vertical retrace interrupt during decoding. Could be an OpenGL program
> needing precisely scheduler support for those same handling vertical
> retrace interrupts, low latency audio and timely handling of touch
> events amognst other uses.
> 

Interesting! I read doc patch and only skimmed through the others, but
I seem to already have a general type of question.

Since you seem familiar with SCHED_DEADLINE [1] (you refer to deadline
scheduling in the doc patch and Dario is in CC :-)), what do you think
is wrong with just use that for this type of workloads?

AFAIK, mplayer (like) type of workloads already play well with deadline
scheduling, and SCHED_DEADLINE is mainline and actively maintained and
developed [2].

Best,

- Juri

[1] http://onlinelibrary.wiley.com/doi/10.1002/spe.2335/abstract
[2] 
http://events.linuxfoundation.org/sites/events/files/slides/SCHED_DEADLINE-20160404.pdf

> There is also a need for some kind of blocking/yielding interface that can
> return an overrun count for when the thread utilizes more time than
> allocated for that frame. The read() function in rtc is overloaded for this
> purpose and reports overrun events. Yield functionality has yet to be fully
> tested.
> 
> I apologize for any informal or misused of terminology as I haven't fully
> reviewed all of the academic literature regarding these kind of schedulers.
> I welcome suggestions and corrects etc
> 
> Special thanks to includes...
> 
> Peter Ziljstra (Intel), Steve Rostedt (Red Hat), Rik van Riel (Red Hat) for
> encouraging me to continue working in the Linux kernel community and being
> generally positive and supportive.
> 
> KY Srinivasan (formerly Novell now Microsoft) for discussion of real-time
> schedulers and pointers to specifics on that topic. It was just a single
> discussion but was basically the inspiration for this kind of work.
> 
> Amir Frenkel (Palm), Kenneth Albanowski (Palm), Bdale Garbee (HP) for the
> amazing place that was Palm, Kenneth for being a co-conspirator with this
> scheduler. This scheduler was inspired by performance work that I did
> at Palm's kernel group along with discussions with the multimedia team
> before HP kill webOS off. Sad and infuriating moment.
> 
> Maybe, in a short while, the community will understand the value of these
> patches for -rt and start solving the general phenomenon of high performance
> multi-media and user interactivity problems more properly with both a
> scheduler like this and -rt shipped as default in the near future.
> 
> [Also, I'd love some kind of sponsorship to continue what I think is
> critical work versus heading back into the valley]
> 
> ---
> 
> Bill Huey (hui) (12):
>   Kconfig change
>   Reroute rtc update irqs to the cyclic scheduler handler
>   Add cyclic support to rtc-dev.c
>   Anonymous struct initialization
>   Task tracking per file descriptor
>   Add anonymous struct to sched_rt_entity
>   kernel/userspace additions for addition ioctl() support for rtc
>   Compilation support
>   Add priority support for the cyclic scheduler
>   Export SCHED_FIFO/RT requeuing functions
>   Cyclic scheduler support
>   Cyclic/rtc documentation
> 
>  Documentation/scheduler/sched-cyclic-rtc.txt | 468 
>  drivers/rtc/Kconfig  |   5 +
>  drivers/rtc/class.c  |   3 +
>  drivers/rtc/interface.c  |  23 +
>  drivers/rtc/rtc-dev.c| 161 +++
>  include/linux/init_task.h|  18 +
>  include/linux/rtc.h  |   3 +
>  include/linux/sched.h|  15 +
>  include/uapi/linux/rtc.h |   4 +
>  kernel/sched/Makefile|   1 +
>  kernel/sched/core.c  |  13 +
>  kernel/sched/cyclic.c| 620 
> +++
>  kernel/sched/cyclic.h|  86 
>  kernel/sched/cyclic_rt.h |   7 +
>  kernel/sched/rt.c|  41 ++
>  15 files changed, 1468 insertions(+)
>  create mode 100644 Documentation/scheduler/sched-cyclic-rtc.txt
>  create mode 100644 kernel/sched/cyclic.c
>  create 

Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Mike Galbraith]

On Mon, 2016-04-11 at 22:59 -0700, Bill Huey (hui) wrote:
> 
> 
> On Mon, Apr 11, 2016 at 10:58 PM, Mike Galbraith  
> wrote:
> > On Mon, 2016-04-11 at 22:29 -0700, Bill Huey (hui) wrote:
> > > Hi,
> > >
> > > This a crude cyclic scheduler implementation. It uses SCHED_FIFO tasks
> > > and runs them according to a map pattern specified by a 64 bit mask. Each
> > > bit corresponds to an entry into an 64 entry array of
> > > 'struct task_struct'. This works single core CPU 0 only for now.
> > >
> > > Threads are 'admitted' to this map by an extension to the ioctl() via the
> > > of (rtc) real-time clock interface. The bit pattern then determines when
> > > the task will run or activate next.
> > >
> > > The /dev/rtc interface is choosen for this purpose because of its
> > > accessibilty to userspace. For example, the mplayer program already use
> > > it as a timer source and could possibly benefit from being sync to a
> > > vertical retrace interrupt during decoding. Could be an OpenGL program
> > > needing precisely scheduler support for those same handling vertical
> > > retrace interrupts, low latency audio and timely handling of touch
> > > events amognst other uses.
> > 
> > Sounds like you want SGI's frame rate scheduler.

And an echo free mailer :)

Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Mike Galbraith]

On Mon, 2016-04-11 at 22:59 -0700, Bill Huey (hui) wrote:
> 
> 
> On Mon, Apr 11, 2016 at 10:58 PM, Mike Galbraith  
> wrote:
> > On Mon, 2016-04-11 at 22:29 -0700, Bill Huey (hui) wrote:
> > > Hi,
> > >
> > > This a crude cyclic scheduler implementation. It uses SCHED_FIFO tasks
> > > and runs them according to a map pattern specified by a 64 bit mask. Each
> > > bit corresponds to an entry into an 64 entry array of
> > > 'struct task_struct'. This works single core CPU 0 only for now.
> > >
> > > Threads are 'admitted' to this map by an extension to the ioctl() via the
> > > of (rtc) real-time clock interface. The bit pattern then determines when
> > > the task will run or activate next.
> > >
> > > The /dev/rtc interface is choosen for this purpose because of its
> > > accessibilty to userspace. For example, the mplayer program already use
> > > it as a timer source and could possibly benefit from being sync to a
> > > vertical retrace interrupt during decoding. Could be an OpenGL program
> > > needing precisely scheduler support for those same handling vertical
> > > retrace interrupts, low latency audio and timely handling of touch
> > > events amognst other uses.
> > 
> > Sounds like you want SGI's frame rate scheduler.

And an echo free mailer :)

Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Mike Galbraith]

On Mon, 2016-04-11 at 22:29 -0700, Bill Huey (hui) wrote:
> Hi,
> 
> This a crude cyclic scheduler implementation. It uses SCHED_FIFO tasks
> and runs them according to a map pattern specified by a 64 bit mask. Each
> bit corresponds to an entry into an 64 entry array of
> 'struct task_struct'. This works single core CPU 0 only for now.
> 
> Threads are 'admitted' to this map by an extension to the ioctl() via the
> of (rtc) real-time clock interface. The bit pattern then determines when
> the task will run or activate next.
> 
> The /dev/rtc interface is choosen for this purpose because of its
> accessibilty to userspace. For example, the mplayer program already use
> it as a timer source and could possibly benefit from being sync to a
> vertical retrace interrupt during decoding. Could be an OpenGL program
> needing precisely scheduler support for those same handling vertical
> retrace interrupts, low latency audio and timely handling of touch
> events amognst other uses.

Sounds like you want SGI's frame rate scheduler.

-Mike

Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Mike Galbraith]

On Mon, 2016-04-11 at 22:29 -0700, Bill Huey (hui) wrote:
> Hi,
> 
> This a crude cyclic scheduler implementation. It uses SCHED_FIFO tasks
> and runs them according to a map pattern specified by a 64 bit mask. Each
> bit corresponds to an entry into an 64 entry array of
> 'struct task_struct'. This works single core CPU 0 only for now.
> 
> Threads are 'admitted' to this map by an extension to the ioctl() via the
> of (rtc) real-time clock interface. The bit pattern then determines when
> the task will run or activate next.
> 
> The /dev/rtc interface is choosen for this purpose because of its
> accessibilty to userspace. For example, the mplayer program already use
> it as a timer source and could possibly benefit from being sync to a
> vertical retrace interrupt during decoding. Could be an OpenGL program
> needing precisely scheduler support for those same handling vertical
> retrace interrupts, low latency audio and timely handling of touch
> events amognst other uses.

Sounds like you want SGI's frame rate scheduler.

-Mike

[PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Bill Huey (hui)]

Hi,

This a crude cyclic scheduler implementation. It uses SCHED_FIFO tasks
and runs them according to a map pattern specified by a 64 bit mask. Each
bit corresponds to an entry into an 64 entry array of
'struct task_struct'. This works single core CPU 0 only for now.

Threads are 'admitted' to this map by an extension to the ioctl() via the
of (rtc) real-time clock interface. The bit pattern then determines when
the task will run or activate next.

The /dev/rtc interface is choosen for this purpose because of its
accessibilty to userspace. For example, the mplayer program already use
it as a timer source and could possibly benefit from being sync to a
vertical retrace interrupt during decoding. Could be an OpenGL program
needing precisely scheduler support for those same handling vertical
retrace interrupts, low latency audio and timely handling of touch
events amognst other uses.

There is also a need for some kind of blocking/yielding interface that can
return an overrun count for when the thread utilizes more time than
allocated for that frame. The read() function in rtc is overloaded for this
purpose and reports overrun events. Yield functionality has yet to be fully
tested.

I apologize for any informal or misused of terminology as I haven't fully
reviewed all of the academic literature regarding these kind of schedulers.
I welcome suggestions and corrects etc

Special thanks to includes...

Peter Ziljstra (Intel), Steve Rostedt (Red Hat), Rik van Riel (Red Hat) for
encouraging me to continue working in the Linux kernel community and being
generally positive and supportive.

KY Srinivasan (formerly Novell now Microsoft) for discussion of real-time
schedulers and pointers to specifics on that topic. It was just a single
discussion but was basically the inspiration for this kind of work.

Amir Frenkel (Palm), Kenneth Albanowski (Palm), Bdale Garbee (HP) for the
amazing place that was Palm, Kenneth for being a co-conspirator with this
scheduler. This scheduler was inspired by performance work that I did
at Palm's kernel group along with discussions with the multimedia team
before HP kill webOS off. Sad and infuriating moment.

Maybe, in a short while, the community will understand the value of these
patches for -rt and start solving the general phenomenon of high performance
multi-media and user interactivity problems more properly with both a
scheduler like this and -rt shipped as default in the near future.

[Also, I'd love some kind of sponsorship to continue what I think is
critical work versus heading back into the valley]

---

Bill Huey (hui) (12):
  Kconfig change
  Reroute rtc update irqs to the cyclic scheduler handler
  Add cyclic support to rtc-dev.c
  Anonymous struct initialization
  Task tracking per file descriptor
  Add anonymous struct to sched_rt_entity
  kernel/userspace additions for addition ioctl() support for rtc
  Compilation support
  Add priority support for the cyclic scheduler
  Export SCHED_FIFO/RT requeuing functions
  Cyclic scheduler support
  Cyclic/rtc documentation

 Documentation/scheduler/sched-cyclic-rtc.txt | 468 
 drivers/rtc/Kconfig  |   5 +
 drivers/rtc/class.c  |   3 +
 drivers/rtc/interface.c  |  23 +
 drivers/rtc/rtc-dev.c| 161 +++
 include/linux/init_task.h|  18 +
 include/linux/rtc.h  |   3 +
 include/linux/sched.h|  15 +
 include/uapi/linux/rtc.h |   4 +
 kernel/sched/Makefile|   1 +
 kernel/sched/core.c  |  13 +
 kernel/sched/cyclic.c| 620 +++
 kernel/sched/cyclic.h|  86 
 kernel/sched/cyclic_rt.h |   7 +
 kernel/sched/rt.c|  41 ++
 15 files changed, 1468 insertions(+)
 create mode 100644 Documentation/scheduler/sched-cyclic-rtc.txt
 create mode 100644 kernel/sched/cyclic.c
 create mode 100644 kernel/sched/cyclic.h
 create mode 100644 kernel/sched/cyclic_rt.h

-- 
2.5.0

[PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

[Bill Huey (hui)]

Hi,

This a crude cyclic scheduler implementation. It uses SCHED_FIFO tasks
and runs them according to a map pattern specified by a 64 bit mask. Each
bit corresponds to an entry into an 64 entry array of
'struct task_struct'. This works single core CPU 0 only for now.

Threads are 'admitted' to this map by an extension to the ioctl() via the
of (rtc) real-time clock interface. The bit pattern then determines when
the task will run or activate next.

The /dev/rtc interface is choosen for this purpose because of its
accessibilty to userspace. For example, the mplayer program already use
it as a timer source and could possibly benefit from being sync to a
vertical retrace interrupt during decoding. Could be an OpenGL program
needing precisely scheduler support for those same handling vertical
retrace interrupts, low latency audio and timely handling of touch
events amognst other uses.

There is also a need for some kind of blocking/yielding interface that can
return an overrun count for when the thread utilizes more time than
allocated for that frame. The read() function in rtc is overloaded for this
purpose and reports overrun events. Yield functionality has yet to be fully
tested.

I apologize for any informal or misused of terminology as I haven't fully
reviewed all of the academic literature regarding these kind of schedulers.
I welcome suggestions and corrects etc

Special thanks to includes...

Peter Ziljstra (Intel), Steve Rostedt (Red Hat), Rik van Riel (Red Hat) for
encouraging me to continue working in the Linux kernel community and being
generally positive and supportive.

KY Srinivasan (formerly Novell now Microsoft) for discussion of real-time
schedulers and pointers to specifics on that topic. It was just a single
discussion but was basically the inspiration for this kind of work.

Amir Frenkel (Palm), Kenneth Albanowski (Palm), Bdale Garbee (HP) for the
amazing place that was Palm, Kenneth for being a co-conspirator with this
scheduler. This scheduler was inspired by performance work that I did
at Palm's kernel group along with discussions with the multimedia team
before HP kill webOS off. Sad and infuriating moment.

Maybe, in a short while, the community will understand the value of these
patches for -rt and start solving the general phenomenon of high performance
multi-media and user interactivity problems more properly with both a
scheduler like this and -rt shipped as default in the near future.

[Also, I'd love some kind of sponsorship to continue what I think is
critical work versus heading back into the valley]

---

Bill Huey (hui) (12):
  Kconfig change
  Reroute rtc update irqs to the cyclic scheduler handler
  Add cyclic support to rtc-dev.c
  Anonymous struct initialization
  Task tracking per file descriptor
  Add anonymous struct to sched_rt_entity
  kernel/userspace additions for addition ioctl() support for rtc
  Compilation support
  Add priority support for the cyclic scheduler
  Export SCHED_FIFO/RT requeuing functions
  Cyclic scheduler support
  Cyclic/rtc documentation

 Documentation/scheduler/sched-cyclic-rtc.txt | 468 
 drivers/rtc/Kconfig  |   5 +
 drivers/rtc/class.c  |   3 +
 drivers/rtc/interface.c  |  23 +
 drivers/rtc/rtc-dev.c| 161 +++
 include/linux/init_task.h|  18 +
 include/linux/rtc.h  |   3 +
 include/linux/sched.h|  15 +
 include/uapi/linux/rtc.h |   4 +
 kernel/sched/Makefile|   1 +
 kernel/sched/core.c  |  13 +
 kernel/sched/cyclic.c| 620 +++
 kernel/sched/cyclic.h|  86 
 kernel/sched/cyclic_rt.h |   7 +
 kernel/sched/rt.c|  41 ++
 15 files changed, 1468 insertions(+)
 create mode 100644 Documentation/scheduler/sched-cyclic-rtc.txt
 create mode 100644 kernel/sched/cyclic.c
 create mode 100644 kernel/sched/cyclic.h
 create mode 100644 kernel/sched/cyclic_rt.h

-- 
2.5.0