Task priorities in non strictly real-time systems

On 2020-01-06 19:01, Hans-Bernhard Br�ker wrote:
> Am 06.01.2020 um 01:08 schrieb Don Y:
> 
>> Preemptive frameworks can be implemented in a variety of ways.
>> It need NOT mean that the processor can be pulled out from under
>> your feet at any "random" time.
> 
> I think I have to disagree with that.
> 
> Let's start with linguistics.  To "preempt" means: to get in ahead of
> someone (or something) else.
> 
> In the RT world, that something is a running task, and preemption
> happens when some other task gets to use the CPU before that task is
> done with it.  I.e. a preemptive framework, pretty much by definition of
> the words, does pull the CPU out from under you, and that _will_ happen
> at, essentially, random times.
> 
> If the running task can routinely (as opposed to exceptionally) avoid
> that happening to itself, that means it's essentially the other type of
> framework: a cooperative one.

There are lots of intermediate ideas, "limited preemption" systems. See 
"Limited Preemptive Scheduling for Real-Time Systems: a Survey", at
https://algo.ing.unimo.it/people/marko/papers/TII13.pdf

> Now we in c.a.embedded don't usually get to make that distinction quite
> so cleanly of course, because for us, ISRs are a fact of life, and those
> are always preemptive.

Except, of course, when the task that would be interrupted disables or 
masks the interrupt(s) for a while, thus delaying the 
interruption/preemption until later.

Some embedded programs run with all interrupts always disabled, and 
instead poll for inputs and events.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

On Mon, 06 Jan 2020 15:39:01 +0200, upsidedown@downunder.com wrote:

>Smells like a time sharing system, in which the quantum defines how
>much CPU time is given to each time share user before switching to
>next user.

A "jiffy" typically is a single clock increment, and a timeslice
"quantum" is some (maybe large) number of jiffies.

E.g., a modern system can have a 1 microsecond clock increment, but a
typical Linux timeslice quantum is 10 milliseconds.

George

On Sun, 5 Jan 2020 01:58:04 +0100, pozz <pozzugno@gmail.com> wrote:

>Il 03/01/2020 15:19, David Brown ha scritto:
>> With pre-emptive scheduling, you will have to go
>> through your existing code and make very sure that you have locks or
>> synchronisation in place for any shared resources or data.
>
>As I already wrote many times, I don't have experience with RTOS and 
>task sync mechanism such as semaphores, locks, mutexes, message queues 
>and so on.
>So I'm not able to understand when a sync is really needed.
>
>Could you point on a good simple material to study (online or book)?

Any book on operating systems will have a section on synchronization.
The discussions typically revolve around the "dining philosophers"
problem and/or the "producer-consumer / bounded buffer" problem:
https://en.wikipedia.org/wiki/Dining_philosophers_problem
https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem


Undertanding when to use synchronization generally is the easy part.
The hard part is that operating systems vary considerably in the
synchronization primitives they provide, what those primitives are
called, and how those primitives operate.

The term "lock" is non-specific: some systems may have something that
actually is called a "lock", but generally the term can refer to any
non-message based synchronization mechanism.

The weight and semantics of the primitive may be important: is it a
user-space or a kernel primitive?  Does the task wait (sleep) if the
lock is not available?  When the lock does become available, does it
wake all waiting tasks or only one?  Is the wait queue strictly FIFO
or is it by task priority?

Then there is the question of reentrancy: can you take a "lock"
multiple times?  And if so, do you have to release it an equal number
of times?  To both questions, the answer is implementation dependent.

A "mutex" and a "semaphore" conceptually are different in that a
semaphore is able to count and therefore it can enable some number of
concurrent accesses (perhaps to a replicated service).  However, a
mutex is a binary yes/no primitive.  But a mutex can be emulated by a
semaphore with its counter initialized to 1, so some systems provide
only semaphores.  And some systems provide what really are semaphores
but call them mutexes.


Basically you can't rely on the name of anything to understand its
semantics - you really have to study the system(s) you are writing
code for.  Particularly if you switch between different operating
systems.

YMMV,
George

On Sun, 5 Jan 2020 01:58:04 +0100, pozz <pozzugno@gmail.com> wrote:

>Could you point on a good simple material to study (online or book)?

Tony Hoare's book "Communicating Sequential Processes" is online at:
http://www.usingcsp.com/cspbook.pdf

Note: the 2015 date on the book refers to the online PDF - the
material in the book was published in 1985.

It will teach you everything you need to know about how to use message
passing to solve synchronization and coordination problems.  It won't
teach you about your specific operating system's messaging facilities.

George

Hi George,

On 1/6/2020 11:29 AM, George Neuner wrote:
> On Mon, 06 Jan 2020 15:39:01 +0200, upsidedown@downunder.com wrote:
> 
>> Smells like a time sharing system, in which the quantum defines how
>> much CPU time is given to each time share user before switching to
>> next user.
> 
> A "jiffy" typically is a single clock increment, and a timeslice
> "quantum" is some (maybe large) number of jiffies.

Yes, as long as you note that a "clock increment" need not have a
one-to-one correspondence with a "clock INTERRUPT".

> E.g., a modern system can have a 1 microsecond clock increment, but a
> typical Linux timeslice quantum is 10 milliseconds.

In other systems, the norm might be 16/20ms (e.g., the field rate on
a low cost CRT display), 100ms (common of legacy UN*X boxen) or some
completely "random" (appearing!) rate that just happens to fit nicely with
the hardware implementation (e.g., TV colorburst crystals).

In some systems, there are other timing resources that can give you
finer-grained time measurements/delays (with or without the O/S's
support).

[As with much of the taxonomy, "clock" is heavily overloaded]

In article <5d471fdcau3l6fvdu22lb3d51dl9kqap7a@4ax.com>,
George Neuner  <gneuner2@comcast.net> wrote:
>
>Tony Hoare's book "Communicating Sequential Processes" is online at:
>http://www.usingcsp.com/cspbook.pdf
>
>Note: the 2015 date on the book refers to the online PDF - the
>material in the book was published in 1985.
>
>It will teach you everything you need to know about how to use message
>passing to solve synchronization and coordination problems.  It won't
>teach you about your specific operating system's messaging facilities.

George

It's gems like this why I keep browsing the newsgroups...

Thanks for the reference to Hoare's book.  I've just skimmed it now, and
will spend some more detailed reading in the coming weeks (and
months)...

Regards,

Mark

[attrs elided]

On 1/6/2020 6:39 AM, upsidedown@downunder.com wrote:
>> [There are certain contexts where it takes on very specific -- and
>> numerical -- meanings]
>>
>> There's nothing magical about the jiffy.  But, it's typically
>> wired to an IRQ (directly or indirectly).  With all the right
>> mechanisms in place for a preemptive system, the jiffy can just
>> raise an event (JIFFY_OCCURRED) and a very high priority "task"
>> *in* the kernel will be dispatched which will run the scheduler.
> 
> Unless you want to update a time of day time clock, what is the use of
> regular timer interrupts ?

It gives you a quantifiable way of accounting for the passage of time.

How do you blink an indicator at a nominal rate without some notion of
when it's next time to turn it on/off?

How do you detect a long SPACE on a serial port line?

A "regular" timer IRQ typically drives your timing system.  Apps
then use *that* for their notion of elapsed time (both to measure and
to wait/delay)

> In some systems an I/O may arm a one shot clock interrupt waiting for
> the I/O or until a timeout occurs. If the I/O is completed in time,
> the receiver routine disables the timer request and the timer
> interrupt never occurs.

Wonderful if you have a HARDWARE timer to dedicate to each such use.

How do you decide when to drop a TELNET connection because you've not
received a keep-alive in the required interval?  How many such sessions
can you keep active at a time?

[Sharing hardware timers is fraught with opportunities to f*ck up.
You inevitably end up missing events because they occur to close
in time *or* they occur before you can finish the bookkeeping to
set up the timer for "them"!]

> The scheduler needs to be executed only when a "significant event"
> such as an interrupt or task going to wait for a significant event
> will occur,  no need to run it for routine clock interrupts, unless a
> timeout has occurred.

The scheduler SHOULD be run any time something that COULD alter the
run-queue has happened.  (There are lots of opportunities to inject
hints that can dramatically reduce the need to run when nothing
really HAS happened to the run queue)

E.g., if your system doesn't allow tasks to block awaiting memory
resources (imagine blocking INSIDE a malloc!), then there's no need
for the scheduler to be run when the current memory allocation
changes (e.g., in free()).

Note that a lot of dubious systems DON'T run the scheduler as
often as they should.  Instead, they rely on a lazier evaluation strategy
and may delay the scheduler's execution to some other convenient
"happening" -- like a periodic interrupt (in a "time-sliced" system)

IMO, this results in clumsier applications.  If I "do something"
(e.g., raise an event) then I should be able to KNOW that the next line
of code won't have been executed until the task (of higher priority,
BY DESIGN) *waiting* on that event has had a chance to run.

[There's no guarantee that it will run *immediately* -- there may be
other tasks that are higher priority than "I" that could also sneak
in; but, the intended task WILL run before I get another chance!
Unless it's not currently waiting!]

>> An event raised by a UART IRQ can be handled identically.  The
>> task(s) that are waiting on the assertion of that event are
>> "immediately" run as the scheduler discovers them to be ready
>> (and, presumably, of sufficient "priority" to cause the currently
>> running task to be preempted).
> 
> In a typical RT system nearly all (and most of the time all) task are
> in some sort of wait state waiting for a hardware (or software)

Misconception.  That depends on the system's utilization factor
which, in turn, depends on the pairing of hardware resources to application
needs.

I build an STB.  Two conceptual tasks:  one records video (when needed);
the other elides commercials in recorded video (which may be "live"
from the recording task *or* clips that have been accumulated, over
time.)

Yeah, the "recording" task may sleep waiting for an "alarm clock event"
to command it to record an upcoming broadcast.  But, the commercial
zapper is willing to use every possible CPU cycle available to
finish its job.

In applications where the hardware is under-provisioned, the system
runs "in overload", at times, and plays catch-up when the load
decreases.  It may NEVER be able to twiddle its thumbs!

> interrupt. Some time one or more tasks can become runnable due to some
> event and on a single processor system the one runnable task with
> highest priority (first in the runnable task list) is running
> (executing).

>> As an "event" carries no real information (data) beyond the fact
>> that it *occurred*, it is typically a very lightweight mechanism.
>> There are typically very few of them supported by the OS -- often
>> defined by the number of bits in the native "word size" (this
>> allows a task to specify a *set* of events in which it may have
>> an interest -- as a bit-vector; any ONE will suffice).  This
>> simplifies the work of deciding if ANY of the waiting task's
>> significant events have made it eligible to run.
> 
> In a more complicated systems each task could be waiting for a mask of
> events and if the system wide mask has one of the same mask (wait for
> logical OR) or until all (wait for logical AND) required bits are set.
> However, this still needs scanning the task list in priority order.

"Scanning" implies a sequential activity.  Most systems store the
run queue in priority-sorted order.  So, the head of the queue *is*
the next task to select.  (after the effects of the "event" have
been reflected to the LIST of tasks enqueued on those events)

[These sorts of algorithm optimizations differentiate MTOS implementations
from RTOS as the "professional" RTOS implementations go to pains to
make operations predictable in their timeliness; an MTOS just has to
implement *functionality*]

>> [Note that events are transient; they aren't stored like "flags".
>> So, if an event happens and you're not watching for it, you never
>> *see* it!]
> 
> Depends on implementation.

If events "latch", then you have to store the fact that a waiting
task has *seen* its assertion.  AND, you have to be able to differentiate
between it having seen the FIRST assertion vs. the NEXT assertion.

By contrast, a "flag" is just a bit of state that can be examined.

>>> Here is example how a very simple pre-emptive RT kernel worked:
>>>
>>> In the original version for a processor with only a few registers and
>>> when the hardware saved all registers on the stack before the
>>> interrupt service routine (ISR) was executed and restored after the
>>> return from interrupt instruction was executed.
>>>
>>> When the system was started in the main program, a subroutine call was
>>> executed for each task to be created. This subroutine allocated a
>>> local stack for the task as well as a 3 byte task control block
>>> consisting of 1 byte task state and 2 byte saved stack pointer. The
>>> task was started, which then performed a software interrupt storing
>>> original registers for that task on the local stack.
>>
>> This (storing present state on the task's stack) is a common approach.
>> It is also possible to store the register state *in* the TCB (a larger
>> structure being needed for that).  But, these are just efficiency tradeoffs.
> 
> If you put the local stack in the TCB, you either have to use a fixed
> size stack for each task or use a linked list to access the next TCP.

No.

There need be NO stacks (see my other comments on this).

There's no requirement that the processor state must reside ON
the TOS.

The TCBs can be implemented as an array, indexed by the "task id"
(or, referenced by a "TCB*").

The state can be "manually" stored (in the context switch) into
the "current" TCB (by dereferencing TCB* or index into array)
and the state of the newly selected task can be "manually restored"
from its TCB as it is activated.

The TCB has everything pertinent to the task accessible through it.
The task's "priority" (or other scheduling criteria), state, list
of resources held by it, etc.

In my RTOSs, I keep the state of the floating point unit (regardless of
whether it is a piece of hardware or a software emulation) in a set
of separate structures.  If a task declares that it has no need of the
FPU, then it has no need for such a structure.  OTOH, if a task DOES
use the FPU, then the TCB contains a link to that structure.

[This allows for lazy updates to the FPU as well as support for
true concurrent processing in the FPU.  I.e., what if the FPU
hasn't finished a computation when you decide it's time to switch
tasks?  Do you spin waiting for it?  What if the next scheduled
task has no need for the FPU resource?  Why sit there waiting
if you could just leave the FPU as an independent actor to work
as/how it wants??]

> In the scheduler walking through a linked list is often less effective
> than selecting the next entry in an array on a small microprocessor.

Then the scheduler has to manipulate that list as "happenings"
alter it.

>>> executed using the local stack, potentially altering the runnability
>>> of some other dormant task.
>>>
>>> Before performing a return from interrupt the scheduler was executed.
>>
>> The problem with this is that the scheduler may end up being bulky
>> and take a nontrivial amount of time to make up its mind.
> 
> The RT kernel described above for 6809 was about 1-2 KB and even with
> a dozen tasks took 36 instructions (worst case) to find which the next
> task should be executing. Stack manipulation in task swathing required
> some additional instructions.

On small processors, you can implement the basics of an MTOS in
a few hundred bytes -- depending on what you decide you NEED to
code in that environment.  On a Z180, I think I could yield()
from the current task to the next task in ~8 microseconds (?).

If you can keep this overhead low/fast, then you can engage in
vary different programming styles without compromising the
application.

["Programming in the small" is an educational experience as you
question EVERY assumption as to its actual "essentialness" and
effectiveness.]

>> Another approach is to "schedule" the scheduler to run at the COMPLETION
>> of the ISR.  I.e., interpose the scheduler's invocation between the
>> "return-from-interrupt" and the actual "return to task that was interrupted".
> 
> I just tried to explain that the scheduler is executed after the ISR
> code but before executing the return from interrupt instruction either
> to the just interrupted task or to a separate task interrupted seconds
> or days earlier.

But you need to take special steps to ensure the ISR returns to the SCHEDULER
and not to the interrupted task.  The norm is to let the ISR return to the
task and wait for the scheduler to be invoked at some time later (e.g.,
in a time-slicing system)

>>> The scheduler checked the task state byte of each created task
>>> (requiring just 3 instructions/task). If no new higher priority task
>>> had become runnable, the scheduler performed a simple return from
>>> interrupt restoring the registers from the local stack and the
>>> suspended task was resumed.
>>
>> Deciding and picking can often be far more complicated actions.
>> And, the criteria used to make that selection are often not simple
>> (static?) priorities.
> 
> Why complicate things with dynamically changing priorities ? For
> avoiding priority inversion or improve user responsiveness ? But as I

I find the whole notion of "priorities" to be abhorrent.  It suggests
that you KNOW what the priorities SHOULD be -- as part of the DESIGN
of the system.  In practice, they tend to be twiddled after-the-fact
when things don't quite work as you'd HOPED (i.e., you screwed up
the design and are now using a rejiggering of priorities to try to
coax it into behaving the way you'd HOPED)

When you assign arbitrary numeric values to impose an ordering on
tasks ("relative importance"), do you prepare a formal justification
for those choices?  A *rationale* that defends your choices?

(If you put a 1/2W resistor in a circuit, you'd be prepared to explain
EXACTLY why it was needed, wouldn't you?)

And, any ordering of "relative importances" means that each new addition
to the system ("task list") *or* refactoring means you have to reevaluate
those decisions.

You should schedule based on some other, more defensible criteria (e.g.,
deadlines in an RT system).

> said, having separate lists is justifiable only with a large number of
> tasks.

If the task that ends up being ready is always at the (far!) end of the
list, then your context switch takes artificially longer.

> Try to avoid risk for priority inversion by avoiding complicated
> locks.
> 
> Just use fixed priorities.

Priority inversion doesn't ONLY manifest with "complicated locks".
It can happen any time you have competing uses for a "lock" by
tasks executing at different priorities.

A > B > C

C takes lock (because it just happened to get to that line of
code before anybody else got to THEIR line of code).  A preempts
C (perhaps it was waiting on some "happening" that only recently
came to pass).  A tries to take lock but is forced to block
because C is holding it.  IN THEORY, C would then be able to
run and finish up it's need for the lock, releasing it -- which
would "immediately" cause A to gain control of the processor
("preemption").  But, before C can release the lock, B runs
and twiddles its thumbs, thus preventing C from running
(which, in turn, prevents A from running).

> With hundreds of tasks it would make sense to have a separate lists of
> runnable tasks in priority order. There is no need to check for
> non-runnable tasks. When a task becomes runnable, it is moved from the
> waiting list to runnable list. In a well behaving RT systems, there
> are only one  or a small number of tasks in the runnable list.

Another misconception.  The number of runnable tasks has no bearing on
how "well behaved" the system is!

In a *small* system, I'll typically have:
- a task to "handle" each UART (a step above the ISR, implements line protocol)
- a task to scan the keypad switches (to detect and debounce key closures)
- a task to generate sounds
- a task to refresh the display (line by line, digit by digit, etc.)
- a task to interact with the user
- a task to interact with each mechanism/actuator
- a task to provide timekeeping services
- a task to monitor AC mains power
- a task to monitor battery charge level (charging and discharging)
etc.

Each of these tries to be greedy as how quickly they can achieve their goals
is directly reflected in the device's performance.  Granted, UART handlers are
effectively rate-limited by the line-rate in use -- but, that can always be
changed (configuration) by the user/operator (and the handlers would have
to keep up with any new rate!)

Such systems can continue to run well into overload -- but, with noticeable
impact on their performance.  (if there is NO impact on performance, it
suggests that the system is overprovisioned for "nominal" use!)

>> Imagine how you'd implement multitasking in a *tiny* PIC!
>>
>> [This last restriction proves to be of little consequence when
>> designing for small processors -- that often can't AFFORD a stack
>> per process and would be content to share the same stack for ALL
>> processes!]
> 
> I do not know about PICs but even primitive processors like 6502 with
> 256 byte stack pointer addressability range could support multiple
> stacks. With simple processors with a few registers a 32 bytes/task
> stack was more than enough.

Some devices have TINY stacks (e.g., a handful of levels) and/or don't
let you alter or examine the stack's contents (it's just a BAL mechanism)

>>> Thus, a RT kernel can be really simple.
>>
>> The semantic issue becomes one of deciding whether or not the
>> implementation really provides RT services and guarantees.
> 
> What services ? The RMX-80 for 8080/8085 was quite adequate, the
> RMX-86 for 8086/8088 was bloatware :-).
> 
> The RT kernel doesn't give any timeliness quarantees other than
> execution in priority order, it is up to the application programmer to
> make sure that the high priority tasks do not consume too much time.

I adopt the convention that an RT solution provides timeliness guarantees;
otherwise, it's not RT.  Nor is RT "real fast".  (a Mars mission will be
real-time -- despite taking months!)  Nor is RT "life/mission critical".

(In RT, time is a primary aspect of the solution's "correctness")

This is yet another instance of how loose-goosey the taxonomy is (and
continues to become).  Having more rigid definitions of what terms mean
(and their implications) makes design easier -- because your thoughts
carry consequences instead of just "fuzziness".

Hi Les,

[much elided as this thread is consuming more time than I'd
prepared to spend on it...]

On 1/6/2020 6:37 AM, Les Cargill wrote:
>>>> Preemption happens whenever the scheduler is invoked.  In a system
>>>> with a time-driven scheduler, then the possibility of the processor
>>>> being rescheduled at any time exists -- whenever the jiffy dictates.
>>>
>>> That seems to me to be incorrect. "Preemptive" means "the scheduler runs on 
>>> the timer tick." I'd say "inherently".
>>
>> Then, by your definition, any system without a scheduler tied to
>> the jiffy is "cooperative"?  And, any system without a jiffy (at
>> all!) would also have to be considered cooperative?
> 
> There may be a jiffy because we always need a global free-running timer
> from which other timers can be derived.

What if you DON'T need any notion of time?

Build a box that has some flavor of communication port (with protocols
that do not rely on time -- serial, bytewide, etc.).  Accept messages
on those ports intended to query a datastore hosted in the device.
Parse incoming messages.  Act as commanded.  Issue replies.  Await
next message/request.

The content of the replies don't change based on any notion of time
(presumably, the client will wait until the reply is issued; OR, will
initiate another request as an indication that it is no longer willing
to continue waiting for the previous request's resolution)

>> How do you further refine systems wherein OS calls run the
>> scheduler if the run queue has been altered as opposed to
>> those that only run the scheduler when "yield()" is invoked?
>>
>> Do you expect the current task to EVER lose control of the
>> processor in the following code fragment (in a cooperative
>> system)?
>>
>>       process(...);
>>       raise_event(...);
>>       send_message(...);      // consider case of message queue "full"!
>>       receive_message(...);   // consider case of no message is pending!
> 
> Absolutely.

I suspect many would be surprised if the processor "went away"
in the absence of any yield()s.

>> If I disable the timer interrupt (e.g., assume timer fails!)
>> in a preemptive system, do you expect the processor to ever
>> transfer control to any other task (same code fragment)?
> 
> Yep. There are a lot of options, but I'd expect each case there to
> potentially reshuffle the queue.
> 
> "Cooperative" just means the thread must explicitly yield at some point.
> That means you have to know which entry points in the O/S call stack
> can yield and when.

The whole point of NONpreemptive is that the developer is freed from
contemplating the "what ifs" of losing control of the processor -- because
those are exactly the situations where intermittent (and hard to test)
bugs creep into the system.
     "Hmmm, lets's see if the code works properly if I yank the
     processor away *here*!  OK, how about HERE?!  And, here?!!"

With a cooperative system, you are forced to consider how every
action that could, by its nature, "block" (e.g., character not
available at UART when you go to look for it) is handled.

E.g., instead of "getchar()", you'd be more inclined to write
a testchar() that returned a status and a grabchar() that ALWAYS
returned (something, even if no character available).

Or, you would adopt the discipline of KNOWING that anything that could
potentially block WOULD explicitly yield.

E.g., I have a FSM implementation that I keep reusing.  I *know*
that it yield's after each iteration (i.e., the yield is built
into the FSM interpreter).  This is highly intuitive, once you've
coded under it -- you wouldn't expect the FSM to hog the CPU
hoping that something would come along to be processed!

>> If the developer tries to transmit a character via a UART and the
>> UART Tx register is presently full, should he expect his task to
>> lock up the processor while waiting for the UART ISR to (eventually)
>> make the Tx register "ready"?  (in a cooperative system?  in a
>> preemptive system with the timer IRQ disabled?)
>>
>> [What does the putchar() code look like in each of these cases?
>> Do you *spin* waiting on the UART? ]
> 
> That is about context. There are three expected outcomes ( all IMO ):
> 
> - Increment a "oops, dropped send to UART" counter.
> - "spinlock" and wait
> - Go around and try again later.

Ans:  the developer, cognizant of HIS OBLIGATION not to hog the CPU,
crafts the putchar() implementation to satisfy this obligation in
a manner that will "fit" his coding style and the needs of the
application.

E.g., when I use timers in cooperative systems, I rarely implement a
"wait_on_timer()" -- which would obviously have to contain a yield()
to be well-behaved.  Instead, I *test* the timer and decide what to do
in light of the result:  do I want to spend time working on something
else WHILE waiting for it to expire (e.g., maybe it is a timeout
that tells me when I should abort the current operation); or, do I want
to stop further progress on my algorithm UNTIL the timer expires
(in which case, I insert a yield() in the "timer not expired" branch).
This makes it very clear to me where my code is losing control of
the processor -- and where it's NOT!

>> A more natural expectation (re: cooperative) is that the absence
>> of an explicit "yield()" means the task retains control of the
>> processor.
> 
> By what nature? :) I think that's mildly naive more than natural.

Which operations should tolerate "buried" yield()'s?  If I call
on the math library to multiply two values, should I expect to lose
control of the processor?  (imagine it's handling 80 bit floats!
would you want it to monopolize the processor for all that time?
would the developer EXPECT the multiply to have a buried/concealed
yield??)

It's safer (IMO) to let the user decide when he's monopolized the
processor too much.  It might be more prudent for him to write
    yield();
    fmul();
    yield();
    fadd();
    yield();
    fmul();
than to bury the yield()'s in those floating point operations beyond
the control of the developer.

[How would the developer implement an atomic SET of FPU operations
if the operations internally relinquish the CPU?  Or, do you propose
ADDING a "ignore_yields()" to your preemptive system??  :>  ]

>> In a cooperative environment (using my above definition), I
>> could raise dozens of events, sequentially, without fear of
>> any of them being acted upon /until I explicitly yield()-ed/.
>> I wouldn't worry about adding some sort of mechanism to
>> treat the series of raise()'s as an atomic operation -- because
>> my postponing of the yield() effectively guarantees this atomicity.
>>
>> Effectively, this becomes:
>>       priority = get_priority();
>>       set_priority(MAX+1);
>>       raise_event(...);
>>       ...
>>       raise_event(...);
>>       set_priority(priority);
>> (i.e., running the scheduler in each raise() will still not
>> steal the processor away from the current task)
> 
> First, any mucking around with priority at all is at best risky.
> 
> Second, I still don't see what value is preserved by doing this.
> Just yield and go on.

In the above, I've ensured that the highest priority task waiting
for ANY of these events runs next -- not necessarily the task
waiting on the first event raised!

And, why do I want to yield if Ive got other things that I could be doing?

>> I'd wager that most folks using cooperative multitasking DON'T expect
>> a task switch to occur at any time other than yield().  And, have
>> probably not coded to guard against these possibilities.
> 
> I suspect we've all seen purely round-robin systems, which conform to that 
> expectation. That basically means "no priority".
> 
> But you have to yield some time. You are around the campfire, you Get the 
> Stick, you can talk, you yield the stick.

But, *you* decide when to pass the stick; imagine if you went to
blow your nose and someone ASSUMED control of the stick!  "Hey!!!  I
wasn't DONE YET!!!"

>> The "big loop" serves the function of (crude, naive, simplistic)
>> scheduler.  It's presence is not required for a cooperative system.
>> E.g., yield() could call a function that saves the current PC/state
>> on the current stack, examines a list of TCBs on the run queue,
>> selects the most runnable, restores the stack from that TCB,
>> restores the state for that task and "returns" to the PC resident
>> on that stack.
>>
>> No timer.  No loop.  100% cooperative.
>>
>> The earliest designs I worked on saved NO task state (besides PC),
>> supported different "task priorities" and didn't require any
>> special mechanisms to ensure the statements in a task() were
>> processed sequentially.  So:
>>
>>      while(FOREVER) {
>>           task1();
>>           task2();
>>           task3();
>>      }
>>
>>      task1() {
>>           foo = 0;
>>           yield();
>>           foo++;
>>           yield();
>>           foo++;
>>           yield();
>>
>>           if (2 != foo) {
>>              panic();
>>
>>           <blah>
>>           }
>>       }
>>
>> would behave as you'd expect (i.e., no panic).  You can do this
>> on all sorts of super-tiny processors that don't seem like they'd
>> lend themselves to multitasking, otherwise.
> 
> Exactly.

But, it need not!  All yield() says is you want to give up your
control of the processor.

      ...
      if (timer != expired)
          yield();

      do_something();

is a common coding technique that I use.  Everything up to the conditional
will be re-executed the next time I get control of the processor.  And,
this pattern will continue until the timer expires -- at which time, I
will advance to do_something ELSE.

Imagine the ... was:

wait_for_motor_to_home()
{
      if (limit == detected) {
         motor(OFF);
         return;
      }

      if (timer != expired)
          yield();

      motor(OFF);
      signal(ALARM);
      display("Limit switch failure in motor 3.  Shutting down!")
      shutdown();
}

> but as you say - an explicit "yield()" sort of seems hack-ey. We've
> all done it but it's a sign that improvement is possible.

No!  It's THE sign of cooperative multitasking.  YOU have control
over the processor once it's been given to you.  Seeing a yield()
in a *preemptive* implementation should have you asking "why did
the developer decide he didn't have anything else to do, here?
Is this task, possibly, incorrectly engineered (perhaps it should
be DONE at this point and the balance of its actions relegated to
some OTHER task that might be started on its completion?)

>> Where are the routines that one would consider "O/S calls" enumerated
>> (so I know if it's safe to call them without risk of a reschedule())?
>> Do all the debug() mechanisms exist within the O/S framework?  Or,
>> outside it?
> 
> Those are open questions. It depends.

See my FPU example.  Also, keep in mind that cooperative approaches TEND to
be favored in SMALL/resource-starved environments -- that can't afford
the resources of more supportive O/Ss.

>> You'll be amused at how LITTLE you need to actually solve many
>> problems.  Then, start to wonder why you're "expecting so much"!  :>
> 
> Isn't that funny? We seem to be perfectly driven to get in our own way in so 
> many cases.

I recall reading a <mumble> text that talked about this phenomenon.
You have to continually question your assumptions as you progress
towards a solution.

This is why I favor creating RIGID definitions for terms -- despite
what may be common practice (which is often wrong or subject to revision;
look at how "real time" has evolved from "non batch" or "real world").

One of my favorite amusements at parties is to set 3 beer bottles
(preferably long-neck) on the table -- along with 3 "butter/steak
knives" (or, chop sticks or any other similar item).  Then, task
folks with "balancing the three knives atop the three bottles".

Invariably, the solver arranges the bottles in an equilateral
triangle (depending on their level of sobriety) and then
arranging the knives connecting the mouths of the three bottles
(again, can be amusing depending on sobriety!  :> )

After they congratulate themselves on this feat, I take away
one of the bottles:  "Balance the three knives atop the TWO
bottles".

[there are obvious solutions]

Remove another bottle!

Then, "balance the three knives atop the ONE bottle"!

[again, more solutions]

Then, the kicker:  the last solution ALSO satisfies the criteria that
I stated in the beginning -- as well as the first revision of that
criteria.  So, why didn't they just come up with THAT solution in
the first (and second and third!) place??  Why are they imposing
additional constraints on their solution that weren't part of the
problem specification?

[How much hardware and software gets included in designs that doesn't
NEED to be there?  If you need FADD, do you *really* need FSUB?  Or,
FDIV?  Do you even need FADD, at all??]

Just a notice that the generally accepted definition of a "Cooperative" 
scheduling system, vs a "Preemptive" one is that a Cooperative system 
will only invoke the scheduler at defined points in the program, that 
generally includes most 'system calls', as opposed to preemptive, where 
the scheduler can be invoked at almost any point (except for limited 
critical sections).

A system that only runs the scheduler at explicit calls to it isn't the 
normal definition of a cooperative system, I would call that more of a 
manually scheduled system.

The advantage of a cooperative system is that since the scheduler 
happens at discrete points, most of the asynchronous interaction issues 
(races) go away (as it is very unlikely that the code will call the 
system functions in the middle of such an operation.

The advantage of a preemptive system is that, while you need to be more 
careful of race conditions, low priority code doesn't need to worry 
about the scheduling requirements of the high priority code.

Hi George,

On 1/6/2020 1:05 PM, George Neuner wrote:
> On Sun, 5 Jan 2020 01:58:04 +0100, pozz <pozzugno@gmail.com> wrote:
> 
>> Could you point on a good simple material to study (online or book)?
> 
> Tony Hoare's book "Communicating Sequential Processes" is online at:
> http://www.usingcsp.com/cspbook.pdf
> 
> It will teach you everything you need to know about how to use message
> passing to solve synchronization and coordination problems.  It won't
> teach you about your specific operating system's messaging facilities.

It's not a panacea.  It introduces design and run-time overhead, as well
as adding another opportunity to "get things wrong".  <frown>

And, can complicate the cause-effect understanding of what's happening
in your system (esp if you support asynchronous messages... note how
many folks have trouble handling "signal()"!)

*But*, the UNDERstated appeal is that it exposes the interactions between
entities (that can be largely *isolated*, otherwise).  If you engineer
those entities well, this "goodness" will be apparent in the nature of
the messages and their frequency.

E.g., in my world, looking at the IDL goes a LONG way to telling you
what CAN happen -- and WHERE!