[Lumiera] Question about Scheduler capabilities

[Christian Thaeter]

Am Sat, 09 Jul 2011 04:31:48 +0200
schrieb Ichthyostega <prg at ichthyostega.de>:

> 
> Hi Christian,
> 
> thanks for the detailed explanation (much appreciated);
> for now I'll just concentrate on one detail...
> 
> Christian Thaeter schrieb:
> ...
> > The 'hard' queue is ordered by *start* times for jobs, a job there
> > will not be scheduled *earlier* than this time. Each job can also
> > have a 'expire' time. So scheduling may happen at or later than the
> > 'start' time but the job will be handled specially (configureable)
> > when the expire time is missed. I am not finally decided how to
> > implement this 'special' handling, likely something like "abort if
> > no other job depends on it, otherwise keep if the other job still
> > can reach its goals", likely this will be implemented by a functor
> > to make this very flexible and leave some room for experimentation
> > and design. This is what you call 'marked as failure'.
> 
> yeah, leaving this configurable for future extensions sounds like a
> good idea. At the moment, I'm not aware of any situation where a
> dependent job has lower timing requirements than its prerequisite
> jobs.
> 
> That is, I expect the last job in a dependency chain to have the most
> stringent constraints; i.e. the last job, who actually delivers data
> will likely be scheduled with a very tight timing window, because in
> the general case I really want to avoid unnecessary buffering.

for waiting jobs time doesn't matter anyways, only scheduled jobs (all
prerequisites fulfilled) are ordered by time. This has the conincidence
that you can use the same time for all jobs belonging to some biggier
work and don't need to care about ordering them by time. Except later
we will add some profile feedback to adjust times.

> 
> To give a catchy example: if we deliver video frames with a double
> buffering scheme, likely we want the last job in the chain to run
> /after/ the current back-buffer has been "opened", and up to
> /just before/ the flip happens and the back-buffer is swapped into
> display. (of course we need to take the timing uncertainties
> into account, thus our time window will be much smaller than one
> frame)

For this really hard time constrained things I proposed a 3rd (not
mentioned in the mail before) schedule queue. This schedule queue is
lightweight (no dependency/waits), possibly served by specially
allocated threads and should be kept small. So back to your double
buffering thing you schedule the last rendering step as normal job in
the hard queue but the final flip is put into this realtime queue (we
need to settle some terms here)

another thing i have in mind is not double but 'multi' buffering later
on. This means the memory subsystem can then manage and allocate
buffers directly on the graphics hardware but for the rest of the
application this looks like normal memory, so instead doing a buffer
copy we can render directly into the graphics memory. (the final
flip/activation of this buffer still has to be done by the realtime
queue, possibly managed by the player?)

> 
> Of course this works only if this "last job" doesn't do much and thus
> can be expected to run quickly and predictably (e.g. just doing some
> copy into the external output buffer or such or similar).
> 
> The timing deadlines for prerequisite jobs are way more "soft"; we can
> use these timings to adjust the throughput of the engine etc. Just,
> by going backwards from the final deadline, we can derive deadlines
> for the prerequisites. And if a prerequisite isn't there at that
> point, there is no way the final job can catch up, given the tight
> requirements there.

the softness should be archived by putting those into the background
scheduler, possibly (for unimportant frames we may drop) only there,
then jobs we can not serve because of load automatically fall off and
get aborted.

> 
> Ichthyo wrote...
> >> failure propagation when a job fails, either due to an job
> >> internal error, or by timing glitch, any dependent jobs need to
> >> receive that failure state. Usually this means that these jobs are
> >> marked as failure too, and the propagation continues....
> 
> > yes, question: i think its easily possible to go the reverse here,
> > that is: when a job receives a failure from a dependent job and
> > this failure is because (for example) a missed deadline, but this
> > job is still fine in time, it might reschedule the dependent job
> > "Do it again Harry!" ... to be investigated
> 
> > I am a bit worried that we must watch carefully that there are no 
> > failure-avalances,
> 
> Why, what would be the problem?
> My expectation was rather that we don't propagate in forward direction
> (i.e. we don't notify successor jobs if a predecessor fails). Rather,
> for a given job now able to be scheduled, we check if all
> prerequisites are there and only at that point even notice that a
> prerequisite was marked as failure. This way, there can't be an
> avalanche of recursive calls. Rather, we just mark this one as
> failure too and go ahead with the next job able to be scheduled?
> 
> Well, that's just guessing of implementation details on my
> side ... ;-)

you are partially right, of course if something fails then this
propagates forward, everything dependent fails and we can look at real
work to do. But thats an ideal, I don't expect this to be real. There
are other things running on the system which eat cpu, the core
frequencies are modulated and so on .. and we don't want jobs with
excessive huge time windows, for once rendering way to early poisons
caches, they may be even become cold when we finally need the data and
next we want low latency for the GUI which means that there are
relative tight timings. So when this system isn't well tuned/profiled
we can still run into cases where we have to drop work. This dropped
work eats the cpu cycles for the work we would like to do and may miss
deadlines again and so on. Well i only say we have to watch that, i
think its manageable.


> 
> 
> >> guaranteed execution ... some special jobs are marked as "run
> >> reliably". These need to run in any case, even when prerequisite
> >> jobs fail — moreover it could be necessary that these special jobs
> >> receive a flag indicating normal state or failure. (I don't think
> >> we ever need to propagate more specific error information)
> > 
> > I think we should avoid this, a prerequisite is a prerequisite, by
> > definition we can go if something is missing because this just will
> > result in an error. Do you have an case where you need this?
> 
> Yes, several different.
> One thing is, who does the page flip, or who actually emits to the
> external interface? In case of Jack, this is a separate thread which
> we don't control, same for GTK. But for other output interfaces we
> might want to run the actual output handling also as job (maybe).
> Besides that, we have to care for de-clicking / de-flickering in case
> of failure.
> 
> Bottom line: for some external interfaces there might be a tiny job,
> which runs reliably /after/ the delivery job, and which somehow
> detects if the delivery was successful or failed

If it failed there is just no final job for it, or, instead of a
buffer flip we schedule a buffer-hold in the realtime queue for the
failure handler. This failure handler can as well just set a flag that
data is not available or whatever it needs to notify some external
thing.


> 
> There are several other concerns too (we discussed them on one of the
> last meetings): I need a way to know reliably when certain "mark
> points" in the frame sequence are passed, especially for all those
> nasty cases when the "playback plan" has been changed on-the fly
> (live changes of looping, framerate, scrubbing, life changes to the
> edit). Another thing is that we need to enqueue the next chunk of
> jobs reliably. Like it or not, at some point inevitably we need to
> know when some things are done.

for me this looks rather like a pure functional problem, instead a
'imperative' if(fail) command! this just picks a alternative path then:
 if(success) this; else that; .. either branch to take is well
defined without side effects, just working forward.

> 
> > If really required i could add some kind of 'weak' resources to
> > jobs, but i urge to avoid this. On the other hand, as i described
> > above, if the 'failure' handler is a functor, then you already can
> > remove this failed resource from a target job in its handler,
> > possibly allow the target job to become scheduled since no
> > resources are missing anymore.
> 
> As said, wouldn't it be much simpler just to have a flag in the job
> to determine, if it dies in case prerequisites did fail, or otherwise
> if it runs anyway?

implementation wise this will rather result in lists,
each job has a lists of other jobs blocking it, when this list becomes
empty then the job becomes scheduled, for handling this failures there
will be a 2nd list for all failed prerequisites, if that is not empty
(but the blocking list is) then the failure branch is taken. Well and
yes there is a state enum, taking multiple values (blocked,
scheduled, running ... and failed). But operating on this lists and
with a failure handler (which finally should be responsible to set the
state to 'failed') is way nicer, for example you don't only know that
the job failed and this is not hardcoded in the scheduler but you can
figure out why it failed and react on it by walking the list. This will
be also some kind of join operation, you have to consume the failure
list in the handler to free (or restart) the prerequisite jobs.

> 
> See for comparison the Actors in Erlang: some of them die if a linked
> Actor dies, others get a special (asynchronous) message in that case.
> Well -- we don't have messages in Lumiera, but instead we have a
> guaranteed sequencing through prerequisite jobs. I can't see how
> anyone would be able to build reliable asynchronous systems without
> any such feature.

yes finally I am thinking about implementing it this way .. but
i want to make the scheduler even more simple and not to hardwire this.
Later on we may provide a few stock 'failure-handlers' as drop ins, but
these don't belong to the core scheduler.


little oversimplified scratch (only one queue):

struct scheduler
{
  llist waiting_job_pool;
  llist running_jobs;
  llist completed_jobs;
  priqueue runable_by_time;
}


struct job
{
  time_t when;
  // all prerequisites are managed in 3 lists
  llist waiting;
  llist failed;
  llist completed;

  enum state {blocked, scheduled, running, finished, failure} jobstate;

  void (*jobfn)();
  void (*failfn)();
}


jobfn will be scheduled and executed at time, failfn will not be
scheduled but executed as soon as the job isn't waiting anymore and
the failed list is non-empty.

after failfn the scheduler takes care for propagating the outcome
state, that is depending on the state the failfn set (possibly through
some api) all other jobs waiting for this job get their
wait/failed/complete lists adjusted and by that recursively this jobs
may get scheduled (or jump into the failure mode) .. the same happens
when the jobfn completes too, orthogonally the jobfn may set a failure
too. At a close look jobfn and failfn are just branches which join
afterwards with the only exception that jobfn gets scheduled in time
and failfn gets called synchronously. *Maybe* I reduce this to only one
function which gets a parameter telling it about its reason of the
call (background, hard, realtime queue or failure wakeup). I didnt
thought about this much yet, and one may notice that it is all the same
behind different cosmetics.

sidenote: the waiting_job_pool may grow in case of bugs which
don't release jobs, i am planning to have a incremental reaper job to
clean this up, it would be worthwhile to discuss if this should be the
exception and handle ill behaviour or if we want to bless this as
feature.


	Christian

> 
> 	Hermann
> 
> 
> 
> _______________________________________________
> Lumiera mailing list
> Lumiera at lists.lumiera.org
> http://lists.lumiera.org/cgi-bin/mailman/listinfo/lumiera
> http://lumiera.org/donations.html