Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.arch.embedded > #29074
| From | pozz <pozzugno@gmail.com> |
|---|---|
| Newsgroups | comp.arch.embedded |
| Subject | Re: From cooperative to preemptive scheduler: a real example |
| Date | 2020-01-08 00:02 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <qv32lj$ko6$1@dont-email.me> (permalink) |
| References | <qv0lmu$up1$1@dont-email.me> <h7iqr4F6k9uU1@mid.individual.net> |
Il 07/01/2020 08:38, Niklas Holsti ha scritto:
> 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.
The only real-time is that the new message sent through the serial line
appears on the display in a reasonable time: 100ms? 1s? Something similar.
The second requirement is that the display mustn't show a hybrid message
composed by two parts of the successive messages.
>> 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.
No, serial driver works in interrupt mode and already use a FIFO buffer,
sufficiently big. serial_rx() pop a single element from the FIFO, if any.
> 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.
Why? I think the user can change the message only when he wants.
Normally no activity is present on the serial line.
> 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.
Serial driver interrupts guarantees no loss of input during
display_printat() or other functions.
>> 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.
I was thinking to a refresh made at regular intervals, such as every 100ms.
>> 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.
>
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