Re: Dealing with "past" events

Don Y <blockedofcourse@foo.invalid> wrote:

On 11/14/2024 1:54 PM, Waldek Hebisch wrote:

Don Y <blockedofcourse@foo.invalid> wrote:

Given:
N = "now"
R = task release time
D = task's deadline time
E = event time
>
The only real invariant is that R < N as code executing in a
task can't execute until the task has been released.
>
Specifically, there are no guaranteed relationship between
*most* of these times; N > E, N > D, D < R, etc. are all
possible in a generic system.
>
Though, in a nominal setting, R < N < E < D when the code tries
to initiate an event at a particular (future) time (E).
>
But, what happens when E < N -- i.e., when you try to schedule
an action (event) at a time that has already passed?  And, does
E << N lead to a different interpretation/handling?
>
I've argued that the OS shouldn't special-case such activities.
If you request something to happen in the past, then the OS
should just act as if it has *just* happened, regardless as to
whether you were a microsecond "late" in issuing your request
or *years*!  In particular, the OS shouldn't dismiss such request
unilaterally -- or, throw an error to alert the issuer to the
*apparent* inconsistency.

 
That is confusing formulation of the problem.  First, what is
"the OS"?

 
Doesn't matter.  The question is about how one should EXPECT an OS
to handle such things.

It matters.  OS kernel should implement something simple, but enough
to support higher layers.  At higher layers you may have something
more fancy.
 

Second, your "task release time", "task's deadline time",
"event time" are undefined.  In particular, one meaning of
deadline is "time when a task should stop, regarless if it is
done or not".

 
"Release time" is the time a task is made eligible to run.
 
"Deadline time" is the time at which the value of a task's
completion, changes.  I.e., this is the time that you
strive to meet -- but the consequences of failing to meet
it are dependent on the nature of the task and how "important"
you consider its completion BY that time to be.
 
In particular, you can make no assumptions about whether or
not the task should stop once that time has passed.  For this
discussion, you can assume that all deadlines are "hard"
(to simplify the argument; if NOW is past the deadline, then
the task is moribund)
 
"Event time" is the time that you would like "something" to happen.

OK

If by "the OS" you mean operating system kernel, then you want
it as simple as possible and move various functions to upper
layers.  In particular, in general purpose OS you may have
timers which activate a task some time after scheduled time
(hopefully close to scheduled time, but there is no warranty).
Maybe you are thinking of such a timer.

 
I am thinking one layer above that, in terms of abstraction.
Imagine some concurrent agency "watching the clock" and
taking action on your request to make something happen at a
particular time.  *YOU* may be busy with something else.

I take this and what you write later that you think about
library interface for "applications".

However, there may be higher level "scheduler".  For example
Unix 'cron' and 'at' are userspace programs, but are considered
part of operating system. 'cron' and 'at' are rather crude,
if you may need more.  In particular, an automations system
typically must schedule various activities with specific time
constraints.
 
Anyway, your system probably is intended to do something useful
and that will lead to some requirements.  Once you have more
concerte requirements, you can think how to best satisfy them.
If you have only handful of time-dependent tasks and each
differs a lot from other, then putting all higher level
time handling in the tasks may be reasonable.  But usually
it pays to have common handling.  As George mentioned there
can be interdependencies between task, so it is likely that
you may need a higher level scheduler to coordinate them.

 
My contention is that said service can't possibly know of all
of the interdependencies that could exist (examples provided
in other posts).  So, let the service focus on a single criteria:
the time at which you desire the action to occur.

You can not solve _all_ scheduling problems.  It does not
mean that you should not solve some.  Windows style interface
where you have a lot of specific cases and can not do anything
else than provided choices does not look attractive to me.
OTOH 'constraint language' to specify various constraints
(which may be combined in arbitrary ways) could go quite
far.  There is also time-honored approach of allowing "user"
extentions (possibly up to replacing "standard" scheduler).

Consider, however, that the service may be displaced by some higher
priority tasks executing on its hardware.  So, it can't guarantee
that it ever *sees* the specific time you've specified; other
tasks may have preempted it.  So, expecting to hit a specific
time is wishful thinking.

Again, this is question of design of your OS and your requirements.
If you have badly behaving third party code, then it may be hard to
give any warranty.  But if you have need and apropriate resurces
then there are ways to get real-time behaviour (that is hitting
specified time window).  Even if you do not have real-time
motivation, I think that time windows (as opposed to discrete
events) appear frequently.  For example, you want to turn on
a device during night tariff.

Anyway, if you can not give reasonable warranties for time
when your scheduler runs, then it means that you do not care.
By extention, you do not care when scheduled tasks run.
Which may be fine for some purposes and in such case simplistic
handling which you propose may be good enough.

When you wrote your original post, I had someting different in
mind.  Not so long ago I looked at one of home automation
system.  I searched for some specific info and one of first
things that I found was a discussion about scheduling interface
in the system.  A user wanted simply looking thing "if washing
machine is idle for some specified time, then turn its power off".
System allowed specifying conditions which caused some actions.
But there were limitations on what could be put as a condition,
and in effect correctly specifingt needed thing was rather
awkward.

Also, a specific time may not be appropriate for code written
some days/months/years earlier.  For example, maybe I want to
ensure a task is activated when Daylight Savings Time ("Summer
Time") takes effect.  So, that time could be hard-coded into
a task without regard for when the task was initially invoked.
 
[There are lots of fixed dates/times in our lives.  So, these
could be unconditionally encoded without regard for *when*
that encoding took place]
 

Concerning kernel, you should have in kernel enough to
support higher level code.  In particular, if you have
"fast" tasks and care about their time performance, then
you may need real-time features in the kernel.  If you do
not care, than usual general-purpose approach is enough.
But if you do not care, then why are you talking about
deadlines?

 
Because deadlines are always important.  Even non-realtime
activities have some sense of timeliness.
 
I don't really care *when* the results of my checkbook balancing
program are available for inspection.  But, I /probably/ would
like them before I write my next check!  :>
 
Deadlines and value/importance let you (as a human) and
the machine decide where your efforts should be focused.
 
E.g., if you miss your spouse's birthday, should you still
attempt to recognize/celebrate it, even if late?  What if
you miss your NEIGHBOR's birthday??
 

Concerning tasks way in the past: this is very unusual case
for general purpose kernel.  Namely, the only likely reason
for long delay is because system was turned off.

 
Note that I deliberately tried to address "distant past"
vs. "not so distant past".  But, have left the magnitudes of
these differences unspecified.
 
"Not so distant past" seems like it is a condition that could
readily happen.  E.g., if you tried to schedule an event but
found yourself delayed (by competing tasks) so that the scheduled
time was upon you before you got a chance to execute that function.
"Soooooo close!"
 
Given that this can happen, how "close" to missing that time
should you consider "close enough" that you can pretend you
managed to schedule it before the specified time.  In which
case, one could argue that it should be activated "now"
(because "now" is really close to "then")
 

 But kernel
timers frequently are "volatile", that is they will be gone
when system is turned on again (if that is undesirable, then
higher level layer may restore timers that were supposed to
persist).  AFAIK general purpose kernels handled timers
as you argue, that is dully activated corresponding task.
OTOH long delays were usually delegated to userspace which
could have complicated rules.

 
You have to assume these are unprivileged (out-of-kernel)
tasks -- because you don't want to bring more code *into*
the kernel.

Out-of-kernel does not mean unprivileged.  Tasks may have
special rights which other tasks do not have.  For example
one may allow elevated scheduling priority only to system
tasks.  Even otherwise unprivileged task may be special
because it provides "well-known" interface to other tasks.

But, their importance is something you can't know, a priori
(you didn't write them!)
 
And, you can't determine if your chosen method of handling
"past" times will break the task that is making the request,
or not.
 
E.g., I can schedule a task to retrain my speech recognizer
in the wee hours of the morning (when the system load is lower),
based on input it has collected over the course of the day.
If I miss this time, it means that the quality of the recognizer
"tomorrow" will be less than it could have been.  But, if the
retraining can happen TOMORROW night (again, in the system's
"off" time), then there isn't any significant loss.
 
OTOH, if I allow the retraining to happen at some delayed time that
interferes with other system tasks ("prime time"), other activities
could be compromised.
 
So, I argue that a simple criteria be adopted and the writer of
the task requesting the scheduling (and the task being scheduled)
address their own specific criteria IN EXPLICIT CODE to enforce
these, instead of hoping some other service can be made aware of
these requirements (by embelishing that service?  by including
support fr up-calls to the task doing the scheduling??)
 
The "scheduler" can then just focus on ensuring each event gets
processed exactly once and at a time NO EARLIER than the time
specified.  This is much easier for a developer to wrap his head
around than trying to second-guess the scheduler ("What if the
scheduler is blocked for some period of time?  How will *it*
handle things when NOW is later than it *could* have been -- or,
when there are MANY competing things in the queue?")

For me important question is "who is the master?".  Do you allow
third-party code to play any tricks it wants.  Or do you give
control to the user.  As a simple example, task may decide to
do some work at night, presumably to avoid interference with
user work.  But a user may prefer to work at night, say on a
specific day.  So user may wish to delay execution of the task.
If you want to empower users, then central facility is
proferable, as this is easier to control than separate tasks.

I have my own bias, I want computers to do what I want.  For
expample, when I make a break I prefer to have some special
combination of keys to put system to sleep _immediately_.
When I work, I may think for longish time, and systems that
go to sleep based on "inactivity" distract me (especially
when I am trying to understand a text or a picture on the
screen and the screen goes blank).

--
                              Waldek Hebisch