User talk:Billhuey

From RTwiki
(Difference between revisions)
Jump to: navigation, search
(Grand Unified Scheduler Project)
(Gang Scheduling)
 
(47 intermediate revisions by 2 users not shown)
Line 1: Line 1:
=== Grand Unified Scheduler Project ===
+
=== Grand Unified Scheduler Project + QoS ===
 +
====Papers of Interest====
  
Questions I'm pondering:
+
[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5744 General theory overview paper]
  
EDF = earliest deadline first
+
[http://www.cs.unc.edu/~anderson/papers/rtss07b.pdf Generalization Tardiness Bounds] for use in the unification of FIFO, EDF and lags mechanism into a single notion of priority
  
HRT = hard real time<br>
+
====Glossary of terms====
SRT = soft real time<br>
+
BE = best effort<br>
+
  
# How does a static priority system like Linux express itself in terms of an EDF scheduler ? This potentially complicated because of non-standard real time uses of real time policies. How do things like hardness in a SCHED_FIFO task map to in EDF ? How does SCHED_RR map onto EDF ? For a special burt case of use case of SCHED_FIFO, there can be lagging or differing. This isn't considered a failure for this use the policy.
+
<b>EDF</b> = earliest deadline first
 +
 
 +
<b>HRT</b> = hard real time<br>
 +
<b>SRT</b> = soft real time<br>
 +
<b>BE</b> = best effort<br>
 +
 
 +
====Run Policies====
 +
 
 +
<b>SCHED_FIFO:</b>
 +
 
 +
Can be used (1) as a hard real time policy, but also be (2) used as a way of getting minimal lag to service a burst of events like interrupts.
 +
 
 +
<b>SCHED_RR:</b>
 +
 
 +
Cyclic/periodic in nature.
 +
 
 +
...
 +
 
 +
===EDF Questions:===
 +
# How does a static priority system like Linux express itself in terms of an EDF scheduler ? This potentially complicated because of non-standard real time uses of real time policies. How do things like hardness in a SCHED_FIFO task map to in EDF ? How does SCHED_RR map onto EDF ? For a special performance driven BE burst case of use of SCHED_FIFO, a lagging or differing is not considered a failure, how is that mapped onto EDF ? This particular use of the policy isn't consider a failure condition. <br><br> ---There is a recent paper from UNC-CH on creating a unified framework for static and dynamic priorities. Basic idea is to have a priority of a task or a job to be expressed as a single number X, and thus decouple timing constraint (the actual deadline) from how jobs are prioritized. <br><br> Suppose you have three tasks  T1, T2, T3 and each task submits jobs repeatedly. Under EDF, jobs are prioritized by their deadlines X_i=j*p, where p is the period of the task. If we consider a static-priority scheme, jobs of T1 have priority X_1=1, jobs of T2 have priority X_2=2, and jobs of T3 have priority X_3=3. So if we select a job with the smallest value of priority jobs of T1 will be favored over those of T2 and T3. Think of static priority as of EDF with constant deadline. <br><br> It is also possible to describe FIFO - jobs are just prioritized by their release times X_i=(j-1)*p (or equivalently - have same relative deadline). Some sort of fair policy is also possible to implement, as time progresses you just increase the value of priority X_i of currently running task by some amount. Priorities of sleeping tasks remain unchanged. At some point of time another task will have the minimum value of X_i. Though we did not analyze this sort of scheduling policy in details. <br> <br> Please read [http://www.cs.unc.edu/~anderson/papers/rtss07b.pdf the paper] The first three sections have many example schedules to give an idea of how this approach works.--- <br><br>
 
# Is M-CASH, EDF-HSB etc... flexible enough as an abstract container or common factor mathematically or algorithmically so that all three stock scheduler policies, SCHED_FIFO, SCHED_RR and SCHED_OTHER (CFS) can be constructed in terms of that algorithm ?
 
# Is M-CASH, EDF-HSB etc... flexible enough as an abstract container or common factor mathematically or algorithmically so that all three stock scheduler policies, SCHED_FIFO, SCHED_RR and SCHED_OTHER (CFS) can be constructed in terms of that algorithm ?
 
# How would a practical EDF system look like with overload code ? Have EDF be largely run queue localized with manual assignments and with crude not-so-rigorous aperiodic overload handling (below) ?
 
# How would a practical EDF system look like with overload code ? Have EDF be largely run queue localized with manual assignments and with crude not-so-rigorous aperiodic overload handling (below) ?
# If these algorithms overlook the problem of aperiodic overloads, then what kind of overload handling can we do ? apply what we have already with the current rt-overload logic where we scan run queues across the system (or possibly with a specific CPU set) to migrate a task to another CPU that isn't running a real time task (SCHED_FIFO/RR) ? What about the use of a cheaply precomputed slack span that can be quickly read during a cross processor run queue scan to find a suitable BE slot span to handle an overload migration ? Let's call this EDF overload (rebalancing).
+
# If these algorithms overlook the problem of aperiodic overloads, then what kind of crude not so rigorous overload handling can we do ? apply what we have already with the current rt-overload logic where we scan run queues across the system (or possibly with a specific CPU set) to migrate a task to another CPU that isn't running a real time task (SCHED_FIFO/RR) ? What about the use of a cheaply precomputed slack span that can be quickly read during a cross processor run queue search for finding a suitable BE slot span ? This is normally used to handle an overload migration in rt tasks. Let's call this EDF overload (rebalancing).
 
# How cheap is it to compute or pre-compute a span of slack slots for BE threads like irq-threads ?
 
# How cheap is it to compute or pre-compute a span of slack slots for BE threads like irq-threads ?
 +
# Localize slack computation so that we can bypass the use of a global EDF computation if possible for certain aperiodic tasks.
 +
# How does EDF deal with priority inheritance ? What happens to threads that have been boosted by the currently running EDF task but then has it switched out since its release time has been reached and it's been marked as no longer running ? Ah, what about the use of a ceiling for this purpose ? Would the rtmutex need hooks to be able to get notifications of a priority change of some sort ? What about that and the general use of priority inheritance ?
 +
 +
===QoS (Quality of Service)===
 +
 +
# Do we need EDF for QoS ? Or should we just used special manually tuned IO handling daemon servers to issue requests in terms of bandwidth ? It would construct its scheduling policy statically and/or dynamically in a custom manner with SCHED_FIFO.
 +
# How much CPU time is need to handle a single interrupt ? can this be used as a center piece for an EDF algorithm to use to help pre-compute a BE span ?
 +
 +
...
 +
 +
===Gang Scheduling===
 +
 +
Thinking about the NP complete problem of EDF scheduling, bin-packing, and how to pack things in a way so that there are contiguous chunks of time synced across all processor. This is so that an IPI can be set to force a rescheduling of all processors in the gang. An application for this is for the case where a KVM guest is spinning on spinlocks owned by threads that are not in running, therefore in the process of releasing the resource
 +
 +
# Think about a bin-packing case for a G-EDF policy where there might be a schedule mapping that is largely immutable because of the binding of a task to that processors. Do a bitwise "and" of the slots (assuming it's a cyclic task) across cores so that it builds a mapping where a gang job could fit in. G-EDF might be very useful in this scenario. Think about it more. What about creating something that's the opposite of an EDF data structure but a free slot rbtree or something like that instead ?
 +
 +
...
 +
 +
=== mplayer + SCHED_RR + /dev/rtc emulation using timerfd===
 +
 +
* [done] lock analysis of the timerfd paths, Posix locking code, etc... [It doesn't really hit locks for file descriptors that are backed with an anonymous inode]
 +
* [] think about getting SCHED_RR to be driven by a VBL interrupt and phase lock loop it so that the period is precise and correct.
 +
* [] write a ld.so preload library to emulate /dev/rtc so that there can be multiple openings of /dev/rtc from the perspective of the system. /dev/rtc is normally a single open device.
 +
* [] think about migration of SCHED_RR tasks across CPUs and synchronization with a common the VBL across those processors.

Latest revision as of 07:34, 10 April 2008

Contents

[edit] Grand Unified Scheduler Project + QoS

[edit] Papers of Interest

General theory overview paper

Generalization Tardiness Bounds for use in the unification of FIFO, EDF and lags mechanism into a single notion of priority

[edit] Glossary of terms

EDF = earliest deadline first

HRT = hard real time
SRT = soft real time
BE = best effort

[edit] Run Policies

SCHED_FIFO:

Can be used (1) as a hard real time policy, but also be (2) used as a way of getting minimal lag to service a burst of events like interrupts.

SCHED_RR:

Cyclic/periodic in nature.

...

[edit] EDF Questions:

  1. How does a static priority system like Linux express itself in terms of an EDF scheduler ? This potentially complicated because of non-standard real time uses of real time policies. How do things like hardness in a SCHED_FIFO task map to in EDF ? How does SCHED_RR map onto EDF ? For a special performance driven BE burst case of use of SCHED_FIFO, a lagging or differing is not considered a failure, how is that mapped onto EDF ? This particular use of the policy isn't consider a failure condition.

    ---There is a recent paper from UNC-CH on creating a unified framework for static and dynamic priorities. Basic idea is to have a priority of a task or a job to be expressed as a single number X, and thus decouple timing constraint (the actual deadline) from how jobs are prioritized.

    Suppose you have three tasks T1, T2, T3 and each task submits jobs repeatedly. Under EDF, jobs are prioritized by their deadlines X_i=j*p, where p is the period of the task. If we consider a static-priority scheme, jobs of T1 have priority X_1=1, jobs of T2 have priority X_2=2, and jobs of T3 have priority X_3=3. So if we select a job with the smallest value of priority jobs of T1 will be favored over those of T2 and T3. Think of static priority as of EDF with constant deadline.

    It is also possible to describe FIFO - jobs are just prioritized by their release times X_i=(j-1)*p (or equivalently - have same relative deadline). Some sort of fair policy is also possible to implement, as time progresses you just increase the value of priority X_i of currently running task by some amount. Priorities of sleeping tasks remain unchanged. At some point of time another task will have the minimum value of X_i. Though we did not analyze this sort of scheduling policy in details.

    Please read the paper The first three sections have many example schedules to give an idea of how this approach works.---

  2. Is M-CASH, EDF-HSB etc... flexible enough as an abstract container or common factor mathematically or algorithmically so that all three stock scheduler policies, SCHED_FIFO, SCHED_RR and SCHED_OTHER (CFS) can be constructed in terms of that algorithm ?
  3. How would a practical EDF system look like with overload code ? Have EDF be largely run queue localized with manual assignments and with crude not-so-rigorous aperiodic overload handling (below) ?
  4. If these algorithms overlook the problem of aperiodic overloads, then what kind of crude not so rigorous overload handling can we do ? apply what we have already with the current rt-overload logic where we scan run queues across the system (or possibly with a specific CPU set) to migrate a task to another CPU that isn't running a real time task (SCHED_FIFO/RR) ? What about the use of a cheaply precomputed slack span that can be quickly read during a cross processor run queue search for finding a suitable BE slot span ? This is normally used to handle an overload migration in rt tasks. Let's call this EDF overload (rebalancing).
  5. How cheap is it to compute or pre-compute a span of slack slots for BE threads like irq-threads ?
  6. Localize slack computation so that we can bypass the use of a global EDF computation if possible for certain aperiodic tasks.
  7. How does EDF deal with priority inheritance ? What happens to threads that have been boosted by the currently running EDF task but then has it switched out since its release time has been reached and it's been marked as no longer running ? Ah, what about the use of a ceiling for this purpose ? Would the rtmutex need hooks to be able to get notifications of a priority change of some sort ? What about that and the general use of priority inheritance ?

[edit] QoS (Quality of Service)

  1. Do we need EDF for QoS ? Or should we just used special manually tuned IO handling daemon servers to issue requests in terms of bandwidth ? It would construct its scheduling policy statically and/or dynamically in a custom manner with SCHED_FIFO.
  2. How much CPU time is need to handle a single interrupt ? can this be used as a center piece for an EDF algorithm to use to help pre-compute a BE span ?

...

[edit] Gang Scheduling

Thinking about the NP complete problem of EDF scheduling, bin-packing, and how to pack things in a way so that there are contiguous chunks of time synced across all processor. This is so that an IPI can be set to force a rescheduling of all processors in the gang. An application for this is for the case where a KVM guest is spinning on spinlocks owned by threads that are not in running, therefore in the process of releasing the resource

  1. Think about a bin-packing case for a G-EDF policy where there might be a schedule mapping that is largely immutable because of the binding of a task to that processors. Do a bitwise "and" of the slots (assuming it's a cyclic task) across cores so that it builds a mapping where a gang job could fit in. G-EDF might be very useful in this scenario. Think about it more. What about creating something that's the opposite of an EDF data structure but a free slot rbtree or something like that instead ?

...

[edit] mplayer + SCHED_RR + /dev/rtc emulation using timerfd

  • [done] lock analysis of the timerfd paths, Posix locking code, etc... [It doesn't really hit locks for file descriptors that are backed with an anonymous inode]
  • [] think about getting SCHED_RR to be driven by a VBL interrupt and phase lock loop it so that the period is precise and correct.
  • [] write a ld.so preload library to emulate /dev/rtc so that there can be multiple openings of /dev/rtc from the perspective of the system. /dev/rtc is normally a single open device.
  • [] think about migration of SCHED_RR tasks across CPUs and synchronization with a common the VBL across those processors.
Personal tools