Skip to content

Tasks

Jump to bottom
Cliff L. Biffle edited this page Apr 3, 2011 · 9 revisions

Tasks

Task Concepts

LILOS supports an arbitrary number of user tasks, limited only by available RAM. The data structures used to track tasks will grow as needed --- there are no tables to enlarge or shrink.

Each task has its own copy of the register file, status register, stack pointer, and instruction pointer. These are the only "task-local" resources; everything else, including memory and I/O registers, are shared among all tasks.

A task can be in one of two states:

  1. Ready: the task is either running on the CPU, or is queued up to do so.
  2. Blocked: the task is waiting for some other task or hardware resource to do something, and can't be run right now.

A task can save its state and pass control to another task using any of LILOS's primitive blocking operations: lilos::yield, lilos::send, or lilos::receive. More on these later.

Creating a Static Task

Static tasks are declared at compile time and initialized during system startup. The easiest way to declare a static task is using the TASK macro, which takes a name and a stack size (in bytes):

TASK(myTask, 64) {
  while (1) {
    doWork();
  }
}

Static tasks are initialized during system startup, but not scheduled. Scheduling must be explicit:

lilos::schedule(&myTask);

Creating a Dynamic Task

Tasks are simply objects, so they can be created at runtime using new or on the stack (if the stack is quite large). For example,

uint8_t taskStack = new uint8_t[64];
lilos::Task *myDynamicTask = new lilos::Task(taskMain, taskStack, 64);

Again, the task must be scheduled before it can run. Syntax is the same:

lilos::schedule(myDynamicTask);

Cooperating With Other Tasks

LILOS tasks are cooperative: they explicitly pass control to one another. Here's an example of an "uncooperative" task that won't let other tasks run:

TASK(uncooperative, 32) {
  while (1);  // Loop forever, mwa ha ha!
}

There are two ways that a task can allow other tasks to run:

  1. Using lilos::yield to give up the CPU but stay in the ready state.
  2. Using any blocking API, such as lilos::send, to give up the CPU and enter the blocked state.

We can rewrite the task above using the first approach:

TASK(cooperative, 32) {
  while (1) lilos::yield();
}

Calls to yield, send, and friends don't have to be in the task's outer loop: they can be in any function called by the task, or any function called by that function, and so forth:

int yieldAndReturnANumber() {
  lilos::yield();
  return 6;
}

TASK(cooperative2, 32) {
  int counter = 0;
  while (1) {
    counter += yieldAndReturnANumber();
  }
}

Messaging

Tasks can communicate with each other by sending messages. The messaging API consists of three functions (and some variations of them for convenience):

  • lilos::send sends a message to another task, blocking the current task.
  • lilos::receive blocks until a message for the current task arrives.
  • lilos::answer sends a response to a message, unblocking the task that sent it (but not blocking the current task).

Here's an example of communicating by messages. The task, accumulator, is a trivial "message server" that keeps a 16-bit counter. The function beneath accumulator provides an API to clients and hides the fact that accumulator is a task. This is an example of the Actor pattern: accumulator manipulates its internal state in response to messages from a single thread at a time.

TASK(accumulator, 32) {
  uint16_t counter = 0;
  while (1) {
    Task *sender = lilos::receive();
    counter += sender->message();
    lilos::answer(sender, counter);
  }
}

uint16_t atomicAdd(uint16_t amt) {
  return lilos::send(accumulator, amt);
}

This example is too simple to justify a task in real life --- it could be more cheaply implemented using the ATOMIC block defined in <lilos/atomic.hh> --- but examples tend to be that way.

Using TaskLists

Rather than sending messages directly to a Task, tasks can send the message to a TaskList. This causes the sender to queue itself onto the TaskList until someone answers the message.

This can be used to implement mutexes and other synchronization methods without an expensive dedicated task and stack. For example, here is a simple mutex that takes five bytes of RAM:

bool mutexLocked;
lilos::TaskList mutexWaiters;

void lock() {
  if (mutexLocked) {
    lilos::sendVoid(&mutexWaiters);
  }
  mutexLocked = true;
}

void unlock() {
  mutexLocked = false;
  Task *firstWaiter = mutexWaiters->head();
  if (firstWaiter) lilos::answerVoid(firstWaiter);
}

Tasks and Interrupt Handlers

LILOS intends that interrupt handlers do as little as possible: most work should be done by tasks instead. No function that may block or yield may be called from an interrupt handler.

The main task-related function that may be called from an interrupt handler is lilos::answer (and variations like lilos::answerVoid). Some accessors on Task and TaskList are also provided in NonAtomic variations that are safe for use from interrupt handlers.

Here is a simple example that receives bytes from a USART using lilos::answer in an interrupt handler; note that this is not complete, since it doesn't initialize the USART:

#include <avr/io.h>
#include <lilos/task.hh>

TaskList waitingOnUSART;

uint8_t receive() {
  return lilos::sendVoid(&waitingOnUSART);
}

ISR(USART_RX_vect) {
  Task *waiter = waitingOnUSART.headNonAtomic();
  if (waiter) lilos::answer(waiter, UDR0);
}

For a more complete version of the same code, see https://github.com/cbiffle/lilos/blob/master/src/usart.cc.

Choosing Stack Sizes

The RAM for a task consists of two parts:

  • The Task object, which is fixed-size (at this writing, 14 bytes).
  • The task's stack, which is chosen by the user.

Each task needs its own dedicated stack. If RAM is plentiful, most simple tasks can be accomodated with stacks of 64 bytes --- but the AVRs are not exactly swimming in RAM, so it can be useful to compute a more precise stack size.

There are two things to consider when computing stack sizes.

  1. When a task isn't running, its registers and instruction pointer are stashed on its stack. This takes 23 bytes.
  2. When a task is running, and interrupts are enabled, an interrupt frame may appear on the task's stack at any time. The size of the interrupt frame will depend on the program's interrupt handlers; LILOS's built-in interrupt handlers allocate up to 20 bytes.

Thus, the stack size required is the larger of either

  • The stack size at the deepest call to a blocking primitive plus 23 bytes, or
  • The stack size at the deepest point, plus the size of the largest interrupt frame.

In most cases, the practical minimum task stack size is 32 bytes: some blocking primitives like lilos::send require a few bytes of stack in addition to the context save. Carefully-written assembly language tasks which don't use messaging can run in as little as 24 bytes of stack.

Clone this wiki locally