Thread Scheduling for Preemptive LF

[edwardalee]

When there are more worker threads than cores, the underlying OS can provide preemption, where a high priority reaction can preempt a lower priority reaction that might be running for a long time. This discussion is about how to set the thread scheduling policy and priorities to make effective use of this capability. In particular, we would like EDF (earliest deadline first) scheduling.

In the retreat24 branch of reactor-c and of lingua-franca we have support for specifying the number of cores to use and the thread scheduling policy as target properties:

target C {
  cores: 1,
  thread-policy: "rt-fifo" // options are "normal", "rt-rr", "rt-fifo"
};

The (older) workers target property specifies the number of worker threads (per enclave). To get preemption, you need more worker threads than cores because a worker thread that is running a reaction cannot preempt itself.

The thread-policy property is implemented in the C target for Linux and Zephyr only, so far. It defaults to "normal", which corresponds to selecting the default SCHED_OTHER policy in Linux, which implements a "completely fair scheduler" (CFS). The "rt-rr" and "rt-fifo" policies correspond to SCHED_RR and SCHED_FIFO in Linux, respectively. See the Linux man page for good documentation of these policies.

The normal default also has priorities, but those priorities are always lower than kernel threads. Both rt-rr and rt-fifo will give threads priorities higher than the kernel threads. In this discussion, we look at how to dynamically set the priorities of worker threads for possible implementation in the reactor-c runtime.

To implement this, we can use the low-level platform API provided by @erlingrj. In particular, the lf_thread_set_priority sets the priority of a thread to number between 0 and 99, inclusive. The question we address here is how to set (and change) the priority of worker threads.

For the default thread-policy of normal, all worker threads will have priority 0 and will not be changed.
For either of the other two policies, the worker threads will have a priority between 1 and 99.
Initially, all priorities will be set to 1.
When a worker picks up a reaction with a deadline, it may increase its priority before proceeding to execute the reaction.
Here, a "deadline" may be one directly declared for the reaction or inferred because the reaction is upstream of a reaction with a declared deadline.
The inferred deadline is currently stored in the upper 48 bits of the index field of the reaction_t struct defined in lf_types.h.

How to adjust the priority?
The proposal here is to maintain a global data structure that associates assigned priorities with the inferred deadline that caused the priority to be assigned.
The first worker to encounter a reaction with a deadline will assign priority 50 and record the physical-time to deadline violation (PTDV).
When another worker selects a reaction to execute that has a deadline, then it calculates the PTDV and finds a priority to assign that is less than that of any worker that has a greater PTDV and greater than any worker that has a lesser PTDV.
Note that we will probably want to recalculate the PTDV for running threads in order to get a true EDF scheduler.
When it becomes impossible to find a priority that satisfies this, then either an equal priority could be assigned or we could reassign the priorities to spread them out more evenly.

When a worker finishes executing a reaction with a deadline, if there is another reaction available to execute, it will use the deadline (if there is one) of that reaction to determine whether it needs to change its priority. If it changes its priority, it will need to remove or adjust its entry from the global data structure and (possibly) insert the new priority.

This policy seems sufficient to deal with physical actions that are scheduled in an enclave as done in the ReflexGameEnclaves.lf example.
The reaction that blocks on getchar should be given a tight deadline so that the worker thread that picks up this reaction gets a high priority. The worker will immediately block, so its high priority will not interfere with other worker threads. But its high priority ensures that when getchar unblocks, the OS will give priority to this worker, allowing it to process the keyboard input quickly.

FIXME: Inferred deadlines should be adjusted based on execution-time measurements. This could be done by adapting the tracing mechanism to measure execution time. A step along the way could use a WCET annotation instead.

FIXME: Inferred deadlines should probably propagate upstream through connections with after delays, adjusted by the amount of delay.

Command-Line Alternatives

The goal above is to automatically handle setting scheduling policies and priorities, but an alternative that is possibly useful for experimentation is to set them on the command line.

On top of regular CFS scheduler, any thread with a SCHED_FIFO and SCHED_RR policy will have higher priority than any CFS threads (including most of the kernel threads). You can use the command line to run your program with these schedulers:

sudo chrt -f/r <0-99 / priority value> <executable>

The Linux kernel implements a safety mechanism to allow non-real-time threads (including kernel threads) to run and not suffer from starvation from real-time threads: real-time throttling. In every timeframe of 1s, real-time threads are allowed to execute for at most 950ms; if they exceed this threshold, real-time threads are throttled and yield the CPUs to CFS regular threads. The threshold can be modified by editing this virtual file:
/proc/sys/kernel/sched_rt_runtime_us.

When one uses the command line to set these schedulers and priorities, the priority value assigned is used across all reactions, but it doesn’t let you set customized priorities per reaction.

It might be convenient to restrict a given application to run on a single CPU core. The way to do this on a Linux terminal is:

sudo taskset -c <core_id> <executable>

Another optimization that one can employ in the spirit of reducing OS interference is to isolate the core that the real-time code is executing on. Other threads will be moved to other cores of the system. One can set this parameter by editing /boot/cmdline.txt to add the isolcpus parameter. The isolated CPUs should be active after reboot and can be checked using: these instructions.

[erlingrj]

See also notes here: #2261