The Cheap Threads Approach

Cheap Threads has its own approaches to task switching, scheduling, and interthread communication. These approaches impose a particular kind of discipline on each thread.

Task Switching

To switch execution from one task to another, Cheap Threads can use the machinery of ordinary function calls. The scheduler invokes a thread by calling a function previously installed as a callback. It passes that function a pointer by which the thread may retrieve whatever data are private to that thread. After doing whatever it needs to do for that thread, the callback function returns, and the scheduler invokes the next thread in the same manner.

Alternatively, a thread may bypass the function return mechanism and return control to the scheduler directly, through a built-in function based on longjmp(). This approach may be more convenient or more efficient in some cases.

The application may also use a mixture of these two approaches. In any case, each thread decides for itself when to give up control. Since it doesn't get interrupted unpredictably in the middle of execution, it can always leave its data in a consistent state. On the other hand, the scheduler has no defense against a thread that hogs too much CPU time or gets stuck in an endless loop.

Scheduling

The simplest possible schedule would be a round robin, invoking every thread once per iteration in a fixed cycle. Cheap Threads can implement such a simplistic scheme, but it can also invoke some threads more frequently than others, according to their assigned priorities. There are several ways to tweak the scheduling according to the particular needs of an application.

Sometimes a thread has nothing to do, because it is waiting for a message from another thread. In that case it would be a waste of time for the scheduler to keep returning to it. Cheap Threads allows a thread to put itself to sleep, taking itself out of the list of runnable threads. When a message arrives for a sleeping thread, the scheduler wakes it up and enqueues it for execution.

With a priority-based scheduler, a low-priority thread would never run if higher-priority threads were allowed to keep jumping in front of it. Cheap Threads guarantees that once a thread is ready to run (i.e. it isn't sleeping), it absolutely will run eventually, no matter how low its priority -- unless of course the application terminates first, or some other thread gets caught in an endless loop.

Interthread Communication

As in other forms of multithreading, all threads share the same address space. Consequently they can communicate with each other through that shared memory. Unlike other forms of multithreading, Cheap Threads doesn't require the use of mutexes or other devices to keep shared resources in a consistent state.

In addition, a thread may send a message to one or more other threads, or for that matter to itself. The application may define multiple message types so that a thread can respond to different messages in different ways.

In the standard version of Cheap Threads, a message may optionally contain arbitrary data of any length, subject of course to memory constraints. In Embedded Cheap Threads a message is restricted to a fixed maximum length. You can modify that maximum at compile time via the preprocessor.

The sender may send the message to a single designated recipient. Alternatively, it may send the message to all threads, or to all threads that have subscribed to messages of that type.

If the recipient is asleep, the scheduler wakes it up and enqueues it for execution. When it runs, the recipient can read any messages enqueued for it, in the order of their arrival. If a thread returns without processing all of its input messages, the scheduler enqueues it for execution again, even if the thread has tried to put itself to sleep -- unless of course it has called for its own termination.

Although you can use a message to wake up a sleeping thread, an empty message may incur unnecessary overhead. However there are ways for one thread to enqueue another for execution directly, without passing a message.

Thread Discipline

A thread may be so trivial that it can do the same thing every time it runs. For example, it might read the system clock and display the current time.

A thread is more interesting if its job is long and complicated. If you let it perform the whole job from start to finish every time it runs, it may hog too much CPU time. It may noticeably disrupt the timing of the other threads.

It is useful to divide such a job into a series of smaller steps. Every time the thread runs, let it execute one step and return. Between runs it can store whatever context it needs so that it can resume with the next step next time it runs.

With this technique, a thread's logic doesn't form a single connected strand, and may be difficult to follow. This style of programming doesn't come naturally to most people. It will helpful to have had some experience with finite state machines.

Further complications arise if the thread must respond to input messages. Such complications arise in one form or another no matter what kind of multitasking you use.

Home