Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.arch.embedded > #29052
| From | Niklas Holsti <niklas.holsti@tidorum.invalid> |
|---|---|
| Newsgroups | comp.arch.embedded |
| Subject | Re: From cooperative to preemptive scheduler: a real example |
| Date | 2020-01-07 09:38 +0200 |
| Organization | Tidorum Ltd |
| Message-ID | <h7iqr4F6k9uU1@mid.individual.net> (permalink) |
| References | <qv0lmu$up1$1@dont-email.me> |
On 2020-01-07 3:08, pozz wrote:
> I noticed my previous post about preemptive OS involved many people and
> started many discussions, most of them theoric.
>
> Someone wrote the synchronization of tasks in preemptive scheduler is
> not so difficult, after understanding some things.
I made some such statement.
> Others suggested to
> abandon at all preemptive scheduler, considering its pitfalls.
>
> Because I know my limits, I don't think I can produce a well-written
> preemption system. However I'd like to understand a little more about
> them. Starting from an example.
>
> Suppose my system is a display where a message is written. The message
> can be customized by a serial line.
So, this system consists of a display and a serial input line and has
requirements as follows:
1. The display shall at all times show a message, of at most 31 characters.
- To be defined: what the initial message should be at system reset.
2. The SW shall receive characters from the serial line, buffering them
in a "frame buffer" in memory, which can hold up to 64 characters.
3. After each received (and buffered) serial-line character, the SW
shall check if the buffered characters form a complete "frame".
- To be defined: what to do if the frame buffer is full but does not
form a complete frame. (This may of course be impossible by design of
the "frame_is_complete" function.)
4. When the buffered characters form a complete frame, the SW shall
convert (decode) the contents of the frame into a message, of at most 31
characters, display that message until another, new frame is received,
and erase the frame-buffer in preparation for the next frame.
The real-time aspects are undefined, except that each message is
displayed until the next frame is received.
> In cooperative approach, I would
> write something:
>
> --- main.c ---
> ...
> while(1) {
> task_display();
> task_serial();
> }
> --- end of main.c ---
>
> --- display.c ---
> static const char msg[32];
> void display_set_message(const char *new_msg) {
> strncpy(msg, new_msg, sizeof(msg));
> }
> void task_display(void) {
> if (refresh_is_needed()) {
> display_printat(0, 0, msg);
> }
> }
> --- end of display.c ---
>
> --- serial.c ---
> static unsigned char rxbuf[64];
> static size_t rxlen;
> void task_serial(void)
> {
> unsigned char b = serial_rx();
> if (b != EOF) {
> rxbuf[rxlen++] = b;
> if (frame_is_complete(rxbuf, rxlen)) {
> char new_msg[32];
> /* decode new message from received frame from serial line */
> display_set_message(new_msg);
> rxlen = 0;
> }
> }
> }
> --- end of serial.c ---
>
> The display needs to be refreshed. display_printat() is blocking: when
> it returns, all the display was refreshed. So the display always shows
> the entire message: there's no risk the display shows a part of the
> previous message and a part of the new message.
>
> How to convert these two tasks in a preemptive scheduler? Which priority
> to assign to them?
Before that conversion one must think about the real-time requirements:
deadlines, response-times. This is difficult for this example, because
you have not stated any requirements.
Let's assume these requirements and properties of the environment:
A. The function "serial_rx" polls the one-character reception buffer of
the serial line once, and returns the received character, if any, and
EOF otherwise. It must be called at least as often as characters arrive
(that is, depending on baud rate) to avoid overrun and loss of some
characters.
B. A pause in the serial-line character arrival cannot be assumed after
the completion of a frame. The first character of the next frame can
arrive as quickly as the baud rate allows.
C. The functions "frame_is_complete" and "display_set_message" take,
together, so much less time than the serial-line character period that
the whole "task_serial" function also takes less time than the character
period.
D. The function "display_printat" can take longer than the serial-line
character period.
Under these assumptions, the cooperative solution does not work, because
when a frame is completed, "display_printat" is called which may mean
too much delay for the next "serial_rx" call and cause loss of input
characters.
> The simplest approach is...
>
> --- display.c ---
> static const char msg[32];
> void display_set_message(const char *new_msg) {
> strncpy(msg, new_msg, sizeof(msg));
> }
> void task_display(void) {
> while(1) {
> if (refresh_is_needed()) {
> display_printat(0, 0, msg);
> }
> }
> }
> --- end of display.c ---
>
> --- serial.c ---
> static unsigned char rxbuf[32];
> static size_t rxlen;
> void task_serial(void)
> {
> while(1) {
> unsigned char b = serial_rx();
> if (b != EOF) {
> rxbuf[rxlen++] = b;
> if (frame_is_complete(rxbuf, rxlen)) {
> char new_msg[32];
> /* decode new message from received frame from serial line */
> display_set_message(new_msg);
> rxlen = 0;
> }
> }
> }
> }
> --- end of serial.c ---
>
> This code works most of the time, but the display sometime can show a
> mix of old/new messages.
Because the "msg" variable in display.c is accessed from both tasks, as
an unprotected shared variable.
In addition to that problem, you have written both tasks to use polling,
with no delay, which wastes processor resources, especially for
"task_display". The "task_serial" task does need to poll "serial_rx"
(per the assumptions above), but it could certainly do so at some
non-zero period, computed from the baud rate and the execution times to
ensure that "serial_rx" calls are frequent enough to avoid loss of input
data.
Of course, a serious design would use serial-line interrupts and trigger
the "task_serial" only when a character has been received.
For "task_display", you could replace the "refresh is needed" flag with
another semaphore, which is initially zero, is "given" in "task_serial"
when a new message is to be displayed, and is "taken" by "task_display"
before it displays the new message. Then "task_display" consumes no
processing resources until it actually has to.
> Here the solution is to take a binary semaphore before using the shared
> resource (and give the semaphore after the job is done).
>
> void display_set_message(const char *new_msg) {
> semaphore_take_forever();
> strncpy(msg, new_msg, sizeof(msg));
Here you need some code to set "refresh is needed" to true. That flag is
also a shared variable.
> semaphore_give();
If you have semaphore calls here, in "display_set_message", ...
> }
>
> ...
> if (frame_is_complete(rxbuf)) {
> char new_msg[32];
> /* decode new message from received frame from serial line */
> semaphore_take_forever();
> display_set_message(new_msg);
> semaphore_give();
... then you do not need themn (and should not have them) here, around
the call of "display_set_message".
> rxlen = 0;
> }
> ...
You also need to use the mutex semaphore from "task_display", for
example as follows:
void task_display(void) {
while(1) {
if (refresh_is_needed()) {
char new_msg[32];
semaphore_take_forever();
strncpy (new_msg, msg, sizeof (new_msg));
// Here something to set "refresh is needed" to false.
semaphore_give();
display_printat(0, 0, new_msg);
}
}
}
Otherwise the "task_serial" could still overwrite the message with a new
one, during the call of "display_printat".
To assign priorities, you look at the deadlines of the tasks:
- task_serial: deadline = serial-line character period (actually
one-half of it)
- task_display: no deadline defined: infinite deadline.
Then you assign priorities in order of deadlines: higher priorities for
shorter deadlines, hence "task_serial" will have higher priority than
"task_display". The numerical values of the priorities do not matter,
only their ordering.
With "task_serial" having a higher priority, it can pre-empt the slow
"display_printat" function whenever it needs to, and thus call
"serial_rx" often enough.
> My impression is that a very simple code is cluttered with
> synchronization things that decrease readability and maintainability and
> increase complexity. Why? Just to use preemption?
No -- to make the SW work, where the cooperative design did not work.
Maintenance is eased because the pre-emptive design continues to work
even if the execution time of "display_printat" was initially short, but
then increased to become longer than the serial-line character period.
In larger programs there are important advantages of preemption in
helping decouple modules from each other.
> From what I have understood, preemption could solve real-time requirement.
>
> Suppose display_printat() takes too much time to finish. This increases
> the worst-case superloop duration and could delay some system reaction.
> For example, if display_printat() takes 1 second to finish, the system
> could react after 1 second from an event (the press of a button, for
> example).
Or it could lose serial input data (under my assumptions).
> If this isn't acceptable, preemption could help. Is it correct?
Yes.
--
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
. @ .
Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-07 02:08 +0100
Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-06 19:37 -0700
Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-07 10:11 +0100
Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-07 07:51 -0700
Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-07 23:51 +0100
Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-09 01:39 +0200
Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-10 00:42 +0100
Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-15 18:39 +0200
Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-08 23:12 -0700
Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-10 00:49 +0100
Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-08 23:12 -0700
Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-09 01:33 -0700
Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-07 09:38 +0200
Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-08 00:02 +0100
Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-09 00:54 +0200
Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-09 12:19 +0100
Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-09 14:03 +0200
Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-10 00:32 +0100
Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-15 18:53 +0200
Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-16 14:48 +0100
Re: From cooperative to preemptive scheduler: a real example upsidedown@downunder.com - 2020-01-16 21:04 +0200
Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-16 22:24 +0200
Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-17 02:05 +0100
Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-18 23:03 +0200
Re: From cooperative to preemptive scheduler [Stack] pozz <pozzugno@gmail.com> - 2020-01-14 13:27 +0100
Re: From cooperative to preemptive scheduler [Stack] Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2020-01-14 20:10 +0100
Re: From cooperative to preemptive scheduler [Stack] pozz <pozzugno@gmail.com> - 2020-01-15 09:36 +0100
Re: From cooperative to preemptive scheduler [Stack] Stef <stef33d@yahooI-N-V-A-L-I-D.com.invalid> - 2020-01-15 11:30 +0100
Re: From cooperative to preemptive scheduler [Stack] pozz <pozzugno@gmail.com> - 2020-01-15 11:51 +0100
Re: From cooperative to preemptive scheduler [Stack] Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2020-01-15 21:51 +0100
Re: From cooperative to preemptive scheduler [Stack] Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-15 21:26 +0200
Re: From cooperative to preemptive scheduler [Stack] Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2020-01-15 22:12 +0100
Re: From cooperative to preemptive scheduler [Stack] Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-15 23:30 +0200
csiph-web