Re: Does calling sched_yield() in a SCHED_DEADLINE thread guarantee wakeup at beginning of next period?

Re: Does calling sched_yield() in a SCHED_DEADLINE thread guarantee wakeup at beginning of next period?

[Tommaso Cucinotta]

[ cc-ing a few others who might have a say in this regard and linux-rt-users@ - see below for my comments... ]

On 17/08/2017 12:21, Bjarke Freund-Hansen wrote:
> Hi Tommaso
> 
> In the Linux kernel in 'Documentation/scheduler/sched-deadline.txt' you write:
> 
>  >> This behavior of sched_yield() allows the task to wake-up exactly at the beginning of the next period. Also, this may be useful in the future with bandwidth reclaiming mechanisms, where sched_yield() will make the leftoever runtime available for reclamation by other SCHED_DEADLINE tasks. <<
> 
> Does this mean that thread is guaranteed to wake up at the beginning of the next period if sched_yield() is called in the current period to relinquish the remaining runtime?

Yes, sched_yield() in such case blocks the task till the next period starts. At that time, the task is woken up (back to ready to run) with full runtime and absolute deadline set to the absolute period start-time plus its relative deadline, but it will be scheduled only once it gets among the m SCHED_DEADLINE tasks with the earliest absolute deadline, where 'm' is the number of CPUs in the scheduling domain. That's a convenience behavior that saves you setting an app-level timer if all you need is a periodic task, and lets you easily sync-up with the time(r) as seen/used by the SCHED_DEADLINE scheduler.

Note: when calling sched_yield(), one should be really sure that the leftover runtime is sufficient to not let the task be throttled during the yield() call itself. The problem being that, if I'm close enough to ending my runtime, and I call sched_yield(), but I'm throttled before sched_yield() can get to do some real work in the kernel, then I'll be throttled till the next period starts, then once I'll be unthrottled the sched_yield() will actually occur, forcing me to skipping one whole period -- guess that's NEVER what one expects. If you set-up an app-level timer instead, and you sleep till an absolute time, then in the worst-and-bad-case (of being unexpectedly throttled) you ask to sleep till a time back in time, that is a no-op returning back immediately to the task.

About the note for future extensions, AFAIK Luca Abeni (in cc) recently worked on a work-conserving extension of SCHED_DEADLINE based on GRUB (that should be [almost] mainline), but I'm not sure about what sched_yield() is doing in such extension (Luca?).

Feel free to write again, should you have further doubts about the use of SCHED_DEADLINE. With more information about your use-case, we might be able to help more of course :-)!

Bye,

	T.
-- 
Tommaso Cucinotta, Computer Engineering PhD
Associate Professor at the Real-Time Systems Laboratory (ReTiS)
Scuola Superiore Sant'Anna, Pisa, Italy
http://retis.sssup.it/people/tommaso

Re: Does calling sched_yield() in a SCHED_DEADLINE thread guarantee wakeup at beginning of next period?

[Peter Zijlstra]

On Mon, Aug 21, 2017 at 08:16:05AM +0000, Bjarke Freund-Hansen wrote:
> So what I gather from this is that the answer is yes, if and only if the
> SCHED_DEADLINE task is the one with the earliest absolute deadline.
> Otherwise, the task might not be woken up at the exact beginning of the
> next period.

'Exact' is a difficult word. The only hard guarantee we can give is that
you'll not wake up before the beginning. How long after depends on a
number of things:

 - (hardware) timer granularity
 - IRQ disabled regions
 - scheduler lock contention
 - scheduling policy (what Tomaso said)

Linux-RT aims to put bounds on things like IRQ disabled regions, but
you're still subject to them. The (scheduler) locks are FIFO fair, so
depending on the number of CPUs and the worst case section length you
can compute bounds on that.

So in practise it might be good enough (and that's all that counts), but
'exact' things are never :-)

Note that the point of Real-Time programming is to not be late
completing, we don't strictly care about when we start.

> My use case is actually quite simple. I have a period of say 20ms. Within
> this period certain things have to happen at certain points in time. These
> things being (among others) sending a network message and validating
> received messages (received asynchronously from the realtime thread.)
> 
> 0ms                  20ms                 40ms                 60ms
> |--------------------|--------------------|--------------------|
>        ^ 0+7ms              ^ 20+7ms             ^ 40+7ms                 -
> transmit message
>                      ^ 0+20ms             ^ 20+20ms            ^ 40+20ms  -
> validate received messages
> 
> Writing this I am questioning if SCHED_DEADLINE is the correct tool for the
> problem.
> 
> My current approach is to schedule the thread as an SCHED_DEADLINE task
> with period 20ms and runtime ~1ms (less than 1ms is needed).
> The task is the only SCHED_DEADLINE task on the system, so I rely on the
> task being woken up exactly at the start of the period and perform the
> received messages validation. I then calculate how long I have to sleep
> before the +7ms point, perform that sleep for the appropriate time and
> after being woken up I transmit the message. Tolerances are somewhere
> around 100μs.
> 
> Is this a valid approach? I have a sneaking suspicion that I might be
> thinking about all this the wrong way.
> 
> I am open to all and any suggestions, thank you in advance. :)

So if I understand correctly, your TX constraints are:

 - not before +7ms
 - not after  +7ms + 100us

That's a fairly tight set. The traditional way to represent that would
be a task with:

  sched_attr = {
	.sched_period   = 20ms,
	.sched_deadline = 100us,
	.sched_runtime  = ... /* something <= 100us */
  }

Which will get woken at the +7ms edge.

I'm not entirely clear on the RX constraints, are they at all correlated
to the TX other than needing to happen in the same period? If not,
they're an independent task:

  sched_attr = {
	.sched_period   = 20ms,
	.sched_deadline = 20ms,
	.sched_runtime  = ... /* something <= 20ms */
  }

Which get woken at the period edge. But writing that it seems wrong,
supposedly you want to process the packets received in _this_ period, so
you need to better specify by which time you expect them to have been
received and when you need to be done validating them.

In any case, the important point being that you need to specify when you
want to be _done_.

Re: Does calling sched_yield() in a SCHED_DEADLINE thread guarantee wakeup at beginning of next period?

[Luca Abeni]

Hi all,

On Mon, 21 Aug 2017 13:24:51 +0200
Peter Zijlstra <peterz@infradead.org> wrote:

> On Mon, Aug 21, 2017 at 08:16:05AM +0000, Bjarke Freund-Hansen wrote:
> > So what I gather from this is that the answer is yes, if and only if the
> > SCHED_DEADLINE task is the one with the earliest absolute deadline.
> > Otherwise, the task might not be woken up at the exact beginning of the
> > next period.  
> 
> 'Exact' is a difficult word. The only hard guarantee we can give is that
> you'll not wake up before the beginning.

I suspect there might be some terminology issues, here...
When I read "the task is woken up" I think about the task moving from a
"blocked" state to a "ready" state (that is, the task entering the
runqueue). So, I would say that the task is woken up (or, even better,
"untrhottled") at the beginning of the next period (modulo interrupt
disabling and timer granularity).

Then, the task is scheduled later (due to scheduler lock contention and
due to the scheduling algorithm) and might be dispatched even later
(due to other sources of kernel latencies).

I think what Tommaso wrote is that the task (ignoring kernel latencies)
the task enters the runqueue at the beginning of the next period, but
could be scheduled later (if there are tasks with earlier deadlines).

Then, if we do not ignore the kernel latencies the dispatching of the
task can be delayed even more by the effects pointed out by Peter.



				Luca

> How long after depends on a
> number of things:
> 
>  - (hardware) timer granularity
>  - IRQ disabled regions
>  - scheduler lock contention
>  - scheduling policy (what Tomaso said)
> 
> Linux-RT aims to put bounds on things like IRQ disabled regions, but
> you're still subject to them. The (scheduler) locks are FIFO fair, so
> depending on the number of CPUs and the worst case section length you
> can compute bounds on that.
> 
> So in practise it might be good enough (and that's all that counts), but
> 'exact' things are never :-)
> 
> Note that the point of Real-Time programming is to not be late
> completing, we don't strictly care about when we start.
> 
> > My use case is actually quite simple. I have a period of say 20ms. Within
> > this period certain things have to happen at certain points in time. These
> > things being (among others) sending a network message and validating
> > received messages (received asynchronously from the realtime thread.)
> > 
> > 0ms                  20ms                 40ms                 60ms
> > |--------------------|--------------------|--------------------|
> >        ^ 0+7ms              ^ 20+7ms             ^ 40+7ms                 -
> > transmit message
> >                      ^ 0+20ms             ^ 20+20ms            ^ 40+20ms  -
> > validate received messages
> > 
> > Writing this I am questioning if SCHED_DEADLINE is the correct tool for the
> > problem.
> > 
> > My current approach is to schedule the thread as an SCHED_DEADLINE task
> > with period 20ms and runtime ~1ms (less than 1ms is needed).
> > The task is the only SCHED_DEADLINE task on the system, so I rely on the
> > task being woken up exactly at the start of the period and perform the
> > received messages validation. I then calculate how long I have to sleep
> > before the +7ms point, perform that sleep for the appropriate time and
> > after being woken up I transmit the message. Tolerances are somewhere
> > around 100μs.
> > 
> > Is this a valid approach? I have a sneaking suspicion that I might be
> > thinking about all this the wrong way.
> > 
> > I am open to all and any suggestions, thank you in advance. :)  
> 
> So if I understand correctly, your TX constraints are:
> 
>  - not before +7ms
>  - not after  +7ms + 100us
> 
> That's a fairly tight set. The traditional way to represent that would
> be a task with:
> 
>   sched_attr = {
> 	.sched_period   = 20ms,
> 	.sched_deadline = 100us,
> 	.sched_runtime  = ... /* something <= 100us */
>   }
> 
> Which will get woken at the +7ms edge.
> 
> I'm not entirely clear on the RX constraints, are they at all correlated
> to the TX other than needing to happen in the same period? If not,
> they're an independent task:
> 
>   sched_attr = {
> 	.sched_period   = 20ms,
> 	.sched_deadline = 20ms,
> 	.sched_runtime  = ... /* something <= 20ms */
>   }
> 
> Which get woken at the period edge. But writing that it seems wrong,
> supposedly you want to process the packets received in _this_ period, so
> you need to better specify by which time you expect them to have been
> received and when you need to be done validating them.
> 
> In any case, the important point being that you need to specify when you
> want to be _done_.