Channels ▼

Al Williams

Dr. Dobb's Bloggers

The Long Jump

November 11, 2012

There are quite a few examples of cooperative multitasking or coroutines on the Web based on this technique. Unfortunately, they generally fall into one of several categories:

  1. Implementations that know the internal structure of a jmp_buf and use it to do context switching. This is robust but nonportable, of course.
  2. Implementations that understand that you can't jump "forward" on the stack (I'll explain that in a minute) and impose limitations on your code.
  3. Naïve implementations that just rely on the stack not getting corrupted for simple test cases and won't work reliably in many practical cases.

Oh, and one outlier: There is at least one implementation that probes the stack at runtime to deduce how the jmp_buf is set up and then uses that information. That violates my simplicity goal, however.

The forward-jumping problem is an abstract perception problem. The C library bills these functions as goto statements, but that's not really accurate. It is better to think of them as stack bookmarks. Just before the longjmp call in my example, the stack looks something like this:

<stuff from main><return address><stuff from helper><empty space for future use>

After the longjmp it should look like it did just before the original call to setjmp:

<stuff from main><empty space for future use>

Suppose I had used setjmp from inside helper to fill in another jump buffer and then had main try to go back to that bookmark. If any of that supposedly empty space got reused, it would put bad data on the stack for the recall of helper.

There is at least one implementation on the Web that accepts this problem and admonishes the programmer to avoid local variables. However, this isn't really sufficient. If helper had made calls, the return information on the stack could be corrupt. Of course, in a simple example, you probably only have one function per task with no local variables. That might work, but it is pretty risky (keep in mind, that things like interrupts are going to use the same stack, too).

One other problem with setjmp: not all compilers support it. The Microchip XC compilers, for example, support it for 18F and DSPIC devices, but not for the 16F family. This is one of the compilers I am interested in targeting, so that's another concern.

Since I wanted portable and simple, I decided to converge on a few simplifications:

  • Each task function would start fresh each time it is scheduled.
  • Task local memory would be easy to use and on the heap, not the stack.
  • If setjmp is available, a task could yield from inside a subroutine (even though on reschedule, the task will start back at the top)
  • If no setjmp is available, tasks can only yield from their top-level function

I made one other simplifying decision. To deal with time, the operating system would handle abstract "ticks" defined by the user. The user has to update the ticks from a user task, so a tick could be anything. If you don't want to use time-based waits, you don't have to supply a tick updating task.

As I have been doing a lot lately, I started development on Linux to shake out problems and bugs. When I'm pretty happy with it, I'll branch to the XC compiler and then possibly some other microcontroller targets as well.

I'll talk about the prototype of LWOS (light-weight operating system) next time. If you want a sneak peek, you can find my work in progress on Google Code.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video