PQRST  1.1
Priority Queue for Running Simple Tasks
pqrst
Author
Norman Gray https://nxg.me.uk

This module implements a Priority Queue for Running Simple Tasks. It is intended to support a simple but very flexible threading framework for Arduino tasks.

When code uses this module, it should declare one or more subclasses of the Task class, and in each of those declare and implement at least the Task::run method. These can then be queued using the Task::start method. There is a pre-existing subclass called LoopTask, which is a task which automatically re-queues itself at a specified cadence.

The main loop of the program should then call TaskQueue::run_ready when it has nothing else to do, which will run any task which has become due.

Usage

For example, here is the Arduino ‘blink’ program, implemented with a task loop:

#include "pqrst.h"

class BlinkTask : public LoopTask {
private:
    int my_pin_;
    bool light_on_p_;
public:
    BlinkTask(int pin, ms_t cadence);
    void run(ms_t) override;
};

BlinkTask::BlinkTask(int pin, ms_t cadence)
    : LoopTask(cadence),
      my_pin_(pin),
      light_on_p_(false)
{
    // empty
}
void BlinkTask::run(ms_t t)
{
    // toggle the LED state every time we are called
    light_on_p_ = !light_on_p_;
    digitalWrite(my_pin_, light_on_p_);
}

// flash the built-in LED at a 500ms cadence
BlinkTask flasher(LED_BUILTIN, 500);

void setup()
{
    pinMode(LED_BUILTIN, OUTPUT);
    flasher.start(2000);  // start after 2000ms (=2s)
}

void loop()
{
    Queue.run_ready(millis());
}

Since there is limited support for dynamic allocation on the Arduino (unless this is carefully implemented by the programmer), the module effectively assumes that all Task objects are statically allocated, so there is no discussion of object ownership, below. There may be some other C++ subtleties that we currently ignore for much the same reason.

Although the module is currently targeted at the Arduino, it has only a rather loose dependence on the Arduino framework (it uses the Serial object for some non-essential debugging and the PROGMEM type for a version string in Flash). It could therefore be ported to a different framework without much difficulty. In particular, the library does not depend on the Arduino millis() function.

Times

Since the module does not depend on the millis() function, it does not depend on any timescale for the times. The integer passed to TaskQueue::run_ready is the module's only idea of the ‘current time’. Although it is convenient to think of the times as milliseconds – they are typed as ms_t, and discussed as milliseconds in this documentation – they can be any timescale that is convenient, from microseconds to whatever jiffies are useful for your program. Any references to ‘milliseconds’ in this documentation should similarly be taken to refer to this arbitrary timescale. In other words, the ms_t type in this module is in fact any 32-bit unsigned int (which is what millis() returns on the Arduino).

You need not care much about the value of the current time, in general, and in general you should typically not use Task::run_at (though you might occasionally use something like run_at(millis() + offset)). You will generally schedule events with a relative time, using Task::run_after or TaskQueue::push_after.

The current time (as passed to the Task::run method), may be different from the TaskQueue ‘reference time’, if the task has been delayed.

Overflow: This ms_t counter will overflow at (hex) ffffffff milliseconds (decimal 4294967295). At the overflow time, the ms_t counter resets to zero without error. The module will deal correctly with this time overflowing, in the sense that tasks scheduled some time in the future after the overflow, will occur with the correct delay. The largest safe relative time offset is half of this range: scheduling a task with a larger offset risks the task being effectively scheduled in the past, making it immediately due.

For information, note that 32-bit milliseconds roll over in 49.7 days, and 32-bit microseconds roll over in 71.6 minutes.

Configuring

The module can be configured in a couple of different ways, using the compiler defines PQRST_SELF_QUEUE, PQRST_TASK_PRIORITIES and PQRST_TASK_IDENT. These can be set in the usual variety of ways, but it is not unreasonable to set them by editing the top of pqrst.h when it is incorporated into your source tree.

All three of PQRST_SELF_QUEUE, PQRST_TASK_IDENT and PQRST_TASK_PRIORITIES default to 0.

If PQRST_SELF_QUEUE is zero, then the header declares (and pqrst.cpp defines) a single global queue, called Queue. If PQRST_SELF_QUEUE is non-zero, on the other hand, then each Task must be associated with a TaskQueue when it is created. The mode with the per-Task queue may be useful if one wishes to manage more than one distinct queue, perhaps a ‘fast’ queue and an ‘idle’ quuee. The prototype for the Task constructor, and for each of its subclasses, is different in the two cases: when PQRST_SELF_QUEUE is non-zero, each has a TaskQueue* first argument (not otherwise shown in this documentation).

The cost of the ‘self-queue’ mode is that each task is larger by the size of a memory pointer (sizeof(TaskQueue*) is four or eight bytes, depending on the platform) . However, even in the ‘global-queue’ mode it is possible to maintain multiple queues as long as one uses TaskQueue::push_after instead of Task::run_after to schedule tasks explicitly on the extra queue. Note that in this case the LoopTask is not useful, since, when PQRST_SELF_QUEUE=0, that always reschedules itself on the global queue.

If PQRST_TASK_PRIORITIES is non-zero, then each task has a priority (separate from its time priority) which helps prevent longer-running low-priority tasks from delaying high-priority ones. See the Task::set_priority method for more discussion.

If PQRST_TASK_IDENT is set non-zero, then each Task object has an identification string which can be set with the method Task::set_task_ident and retrieved with Task::get_task_ident, and which will be reported at various places if DEBUG is true. See also TaskQueue::traverse_queue, the callback for which changes its signature in this case.