Task-Based Constant Bandwidth Server in the Zephyr Operating System

Typically, real-time applications consist of a heterogeneous set of activities (i.e., tasks) with varying timing constraints and execution characteristics competing for common processing resources such as central processing unit (CPU) and memory. Some tasks may require strict temporal guarantees with a periodic execution pattern and a well-defined worst-case execution time, with any missed deadline having significant consequences, such as in control loops for industrial processes or robotic systems. On the other hand, a significant number of tasks may have a varying execution pattern, often referred to as an event-driven pattern, such as tasks related to sensor processing and computer vision tasks, with timing variations affecting performance that may eventually be recovered without compromising correctness. These two categories of tasks are typically referred to as hard and soft real-time tasks, respectively.

The theory of real-time scheduling has mostly been developed under the assumption that all tasks are periodic and that their worst-case execution times (WCET) can be bounded. However, it is well known that calculating the WCET is a difficult problem, especially for complex applications such as multimedia and data-dependent computations, where the WCET may be much longer than the actual expected time [1]. Moreover, aperiodic and sporadic tasks, which are now widespread in many embedded systems, do not easily fit into the periodic model. Hence, it is difficult to use schedulability tests when hard real-time guarantees are required.

A well-known approach to solve this problem is to use resource reservation servers, which offer temporal isolation via bandwidth allocation to each activity. In this way, soft and aperiodic tasks can be supported along with hard real-time tasks without compromising schedulability. Among these techniques, bandwidth-preserving servers have been extensively studied because of their capacity to offer utilization bounds while allowing efficient CPU utilization with dynamic scheduling algorithms like earliest deadline first (EDF). In addition to offering predictability [7], servers are also one of the main techniques to offer isolation in mixed-critical systems [8].

The Constant Bandwidth Server (CBS) is one of such reservation-based mechanisms, and allows soft or non-real-time tasks to execute together with hard real-time tasks scheduled under EDF while preserving temporal isolation [1][6]. Each served task is assigned a maximum execution budget, limiting the interference caused by execution overruns and enabling schedulability analysis of hybrid task sets.

The implementation of these servers depends in large part on the support provided by real-time operating systems (RTOS). In fact, the RTOS should provide appropriate scheduling primitives and timer support together with kernel abstractions in order to manage the execution of the server and the synchronization and deadline control of the tasks. The decisions made at the operating system (OS) level have significant effects on the integration and flexibility of the reservation techniques that are used in various scenarios.

This paper builds upon our previous proposal [16], which presented a Constant Bandwidth Server (CBS) implementation on top of the Zephyr OS [20]. In that paper, we implemented CBS as a set of kernel objects that function as a separate server accepting execution requests from tasks or interrupt handlers. This architecture, here called Decoupled CBS, does not rely on any particular task and provides a generic interface that can be shared among various execution contexts.

Based on this foundation, and motivated by the integration in a satellite software framework, we propose an alternative CBS integration model that we call Task-Based CBS, in which the reservation mechanism is mapped onto the tasks’ applications and thus each task using CBS is managed by its own private CBS. This model provides another trade-off between modularity, integration, and control. Moreover, this paper describes the novel EDF scheduling support in Zephyr that is used to support the proposed Task-Based CBS model.

The paper is structured as follows. The next section provides the background, with an overview of CBS, Zephyr, and related work. Section 3 introduces the richer EDF support provided in Zephyr, and then section 4 the Task-based CBS implementation proposed in this paper. Section 5 provides a comparative analysis of both implementations, both by performing a behaviour and performance analysis in representative test cases, as well as assessing the cases of use of the each of the approaches. Finally, Section 6 concludes with a summary and discussion of future work.

This section provides a summary of the Constant Bandwidth Server (CBS), as well as the Zephyr Operating System, before presenting the related work on the implementation of CBS in real-time operating systems, and finally describing the previous proposed implementation of CBS in Zephyr.

The new EDF scheduler greatly enhanced the capabilities of the pre-existing Zephyr EDF API, as the latter has an simplified implementation of EDF, lacking native support for period management, integrated deadline miss detection, and flexible runtime control over task timing behaviour. The goal of the work was to develop an API with a usability close to fixed priority approaches, so that tasks would be able to alternate between EDF and rate monotonic (RM) with minimal effort, while also providing means for synchronous deadline miss detection and the ability to run EDF on single-shot tasks as well.

A set of new methods and changed methods are provided for enabling the new EDF scheduler:

• $\mathrm{■}$

  k_thread_period_set: optionally set the period of which the EDF task should be running, in milliseconds. Note this function is merely a setter and will produce no immediate effect on the task scheduling. If configured, the period will be later enforced by calls to the k_thread_deadline_set method. If desired, the task can invoke this method more than once to update its own period. Doing so will cause the current cycle to immediately shift towards the new value ²²2The next activation is always calculated based on the most updated period, so if a shorter one is configured mid-cycle, the task will always consider the new value when calculating the time to suspend until the next cycle. Defining a period smaller than the task’s current execution time simply means no task suspension at all.

• $\mathrm{■}$

  k_thread_deadline_miss_callback_set: optionally sets a callback function, as well as a custom argument for it, to be executed whenever a task misses its absolute deadline. This method is also just a setter and will not produce any immediate effect apart from updating the EDF manager control block. A task may invoke this API more than once to update or enable/disable the synchronous track of the deadline state.

• $\mathrm{■}$

  k_thread_deadline_set: this is the most important method for enabling EDF, and it was changed to implement the new functionality. If the task has configured a period, it applies suspensions between cycles to provide regular activation intervals (also warning about period overruns, if detected). Furthermore, automatically starts/stops the EDF timer in case a deadline miss callback is configured. Although a separate function could have been provided, the decision was to reduce the number of new functions, since the new behaviour is only activated when a period is set.

Thus, the present API offers a handful of options for a task to be scheduled by EDF, allowing tasks to be non-periodic. One can configure it for a periodic section or just enable EDF for parts of its logic which execute only once. It is also possible for a task to enable a deadline miss detection, and through a custom callback decide what to do when an overrun happens. Period overflows are also detectable, and all settings can be changed or toggled mid-execution. Moreover, all these settings are put in motion by a single method, k_thread_deadline_set, and in practice any given task already fit for fixed priorities can switch to EDF with minimal adaptations required.

Figure 1 illustrates the execution flow of the k_thread_deadline_set method, central to the approach (in yellow the steps specific for the CBS, which will be explained in the next section). First, it is important to understand the flow for the EDF behaviour. When called, if no period or deadline callback is configured, this method will simply set the absolute deadline of the calling task . If a deadline callback is configured, the EDF timer will start right after the deadline is set. This flow is the upper path in the figure.

If there is a defined period, the lower path is taken instead, being responsible for both the end of the last cycle and the beginning of the next cycle. As such, the first thing to do is check if the previous cycle finished on time, and, if true, forcing the task to suspend for the remainder of the configured period. By the time that is completed, the new cycle begins and the task may set its new absolute deadline, following the same steps of the upper path. Naturally, if at every time this method is invoked the current cycle is about to end, the EDF timer must be interrupted before anything else to prevent false deadline miss detections. That is the reason why the configuration or not of a callback is verified on both routes: the same check is performed, but the outcomes derived from it are different. The method also performs a check for whether or not the task updated the period length during its last cycle, as in k_thread_deadline_set the period is an extra setting that can be altered with a call to an auxiliary k_thread_period_set function. For the EDF method, this verification only needs to take place if there was a period overflow in the latest cycle. Two possibilities arise from this event: either it happened because the task executed (or was preempted) for longer than expected, or it deliberately altered this value to be shorter than the previous execution time. The latter implies that the application knows what it is doing and it is not considered an error, but the former clearly denotes an error situation which would be considered a deadline miss. Under these terms, the k_thread_deadline_set will return an error status upon completion, allowing the calling task to take action if desired. Otherwise, the execution returns the default successful status. Thus, for the developed EDF API, deadline miss events are detected immediately (with the assistance of timers) and period overflow events are detected asynchronously, by the time the k_thread_deadline_set method gets to run again. Although undesired, period overflows are not necessarily critical in EDF, hence why it was assumed an asynchronous detection would be sufficient.

This implementation was evaluated in [15], showcasing the correct behaviour of the EDF API implementation (available at [13]).

The original Decoupled CBS implementation presented a few limitations, which became clear when integrated in a wider project aimed at porting a satellite software framework to Zephyr [15]. First, the Decoupled CBS approach required configuring the CBS in a static manner (at compile time), whereas the satellite software framework initializes nearly all of its components at runtime. Second, the decoupled CBS in Zephyr was tailored for executing arbitrary jobs (materialized as isolated functions) within an internal thread, whereas in the framework all executive entities are explicitly defined at application level through either tasks or interrupts. Finally, the original CBS was developed around the very simple EDF implementation contained in Zephyr, not taking advantage of a richer EDF Zephyr implementation, developed for the framework [15].

The main design change between theory and this new implementation was thus to make the CBS tailored for the regulation of application tasks rather than arbitrary jobs. In this model, each task opting to be scheduled by EDF would now be able to have one exclusive CBS to modulate its execution, as if each task cycle corresponded to a job release in the theoretical model. A task-centric approach greatly simplifies the implementation and cuts some edge cases that could not be avoided in the contribution made for Zephyr in [16]. If the jobs are now cycles of one same task and cycle starts are necessarily registered, then there is never more than one job at once in the system. This means there is no need to check if the CBS was idle by the time a new job comes simply because it will always be finished with the previous cycle by the start of the next, even if it missed a deadline. Thus, the CBS can always be assumed idle when a new job is invoked and the existence of a job queue becomes redundant.

The satellite software framework itself: a) has a considerable amount of additional procedures both for ensuring data integrity (which is expected for space-grade software) and enabling the framework’s own business logic, and b) could not be made available as the framework is not public. Therefore, the Task-based CBS was separated as an independent contribution, featuring the components necessary for the periodic EDF [13] and CBS [14] to work. In this approach, there is exactly one CBS for each application task, and the task execution itself counts as the “job” to be regulated by the configured bandwidth as soon as the task declares its deadline. This alternative design was conceived to mirror the RTEMS offering, but without the hard reservations to keep the close resemblance with the theoretical CBS model. The resulting implementation was also improved to leverage the detachment from the framework and better integrate itself with the kernel while maintaining the rationale above.

Using the richer EDF support, a simple example on how to program a periodic CBS task is presented on Listing 1, and has the source code available in [14]. One can notice the time values for budget, deadline and period are now defined with Zephyr’s built-in macros, ensuring a greater flexibility than the previous approach. The periodic handling of the task that happens within Zephyr’s k_thread_deadline_set API, which received the necessary changes internally, as specified in the previous section, but will still behave exactly the same as the standard API when no period, budget or deadline callback is defined for the given task. Thus, this contribution is completely additive, without any breaking changes compared to the mainline Zephyr API. Optionally, the developer may invoke k_reschedule right after setting the task’s deadline to signal a rescheduling point to the kernel, which does not happen by default in Zephyr once the task updates its own deadline.

The CBS support in k_thread_deadline_set consists on applying extra steps (in yellow in Figure 1) at the start and end of the method to check if the task has a configured CBS, and if so, perform the necessary logic corresponding to a job’s end and beginning, respectively. When the CBS is enabled, the task will check, in the upper path right before setting the new deadline, if the bandwidth condition is met, i.e. if there is still a considerable amount of budget left from a previous execution cycle compared to the current absolute deadline. If true, the deadline is in fact recalculated and the budget is replenished to match the predefined bandwidth. If false, the task will not recalculate its deadline (or refill the budget). That happens because an unmet condition implies the task can be served with the current deadline without risking schedulability guarantees, thus making the deadline setting unnecessary. If the task has configured a period, the lower path of Figure 1 is traversed, and the CBS both stops the budget timer and updates the budget level to reflect what’s been consumed.

The steps added for the CBS are responsible for updating a task’s budget based on how much was spent during the previous execution cycle. However, they assume for calculations that the task remained uninterrupted in the CPU between calls to k_thread_deadline_set, which is not true if a preemption ever happens in between. Some additional procedure was therefore required to suspend the consumption when preemptions take place; in practical terms, this meant introducing some code on context switches to pause the budget timer when a CBS task is forced to leave the CPU, and resume it once it returns. This is exactly the strategy adopted in [16], from where the CBS timer was also taken from. To that effect, the first step then was to include a reference to the task’s CBS in its own control block, thus enabling the kernel to fetch the CBS data from the thread when performing a switch. Then, the methods shown in Listing 2 were placed in the relevant context switching paths: z_cbs_switched_in to update the incoming thread’s CBS, and z_cbs_switched_out to handle the outgoing counterpart. Both took as argument the CBS pointer inserted in the thread control block.

As for the executed logic, it goes as follows. When a CBS-enabled task leaves the CPU, the scheduler checks if the CBS in question was active (consuming budget) or not. If so, it simply stops the budget timer (which will prevent deadline recalculations) and updates the budget left by subtracting the delta since the cycle start. Later on, when the task returns to the CPU, the budget timer is re-started with the updated value as expiration interval and the starting tick is also updated for future calculations. These steps guarantee that on the possibility of subsequent preemptions in one same cycle, the consumed budget will always reflect the actual execution time.

This task-based approach for the CBS, as explained in [15], has some particularities which surprisingly enable a simplification of the decoupled design (without altering any of the theoretical model properties). The most significant one is that, as each CBS is exclusive to a task, there is always at most one job for each CBS in the system, and thus no longer a need for a queue to store incoming jobs. Furthermore, since the job release coincides with the call to k_thread_deadline_set, which itself accepts the relative deadline of the task as a parameter, it made perfect sense to consider this value as the CBS period, ultimately sparing the need for an extra method in the API just for this effect.

​​​Finally, the CBS condition would always be checked by the end of k_thread_deadline_set, independently of whether the task had or not periodic behaviour. This check would not be strictly needed every time: for example, on subsequent calls of this method for a non-periodic task, it would be still active by the second call (thus, the condition check was not necessary). However this would require additional checks for both the task state and a comparison between the new relative deadline and the last, which together would likely take the same amount of overhead as just checking the condition for every case. This is just an heuristic assumption, however, and verification is reserved for future work.

In order to assess the CBS implementation, a comparative analysis was performed, focusing on the algorithm behaviour correctness as well as the impact of the runtime overheads. This analysis is based on data collected from representative test cases running on a real device, a Seeed Studio XIAO ESP32C3, a 32-bits RISC-V microcontroller officially supported by Zephyr, the same cases and platform as in [16], therefore allowing a direct performance comparison between the two approaches. The code sample used for these tests is available on GitHub [14].

The test cases were:

• $\mathrm{■}$

  Test Case 1: A simple combination of one hard task with $(C_1,T_1)=(4,7)$ time units and one CBS with $(Q,T)=(3,8)$ time units, yielding a combined utilization factor of approximately $0.95$. The hard task begins its periodic releases at $t=0$. Two jobs are pushed to the CBS: $J_1(C=4)$ at instant $t=3$ and $J_2(C=3)$ at $t=13$.

• $\mathrm{■}$

  Test Case 2: A combination of two hard tasks with $(C_1,T_1)=(2,6)$ and $(C_2,T_2)=(3,9)$ time units, respectively, and one CBS with $(Q,T)=(2,6)$ time units, yielding a combined utilization factor of 1. Both hard tasks begin their periodic releases at $t=0$. Three jobs are pushed to the CBS: $J_1(C=3)$ at instant $t=2$, $J_2(C=3)$ at $t=12$ and $J_3(C=1)$ at $t=20$.

For each test case the timer tick resolution was fixed at 100us, and for each task set different values were selected for the time unit multiplier, being 1000ms, 100ms, 10ms and 1ms, to verify possible variations in performance caused by overheads. Figures 2(a) and 2(b) present example executions for the two range end cases. The bottom line shows the available budget, with associated events (B_COND: condition for replenishing the budget met, and B_ROUT: budget replenished).

Execution varies with the chosen time unit, mainly due to inaccuracies in k_busy_wait, which causes tasks to run slightly shorter than configured at finer granularities (e.g., 10% less at 1 ms) [16]. While this affects actual execution times, it also shifts the timing of CBS events, leading to different scheduling outcomes across configurations.

Despite these differences, the CBS mechanism behaves correctly. Changes in execution duration and task start times alter when conditions like budget exhaustion and deadline recalculation occur, sometimes triggering events (e.g., B_ROUT) earlier or not at all. However, in both test cases, the CBS consistently adapts to these variations, preserving its intended semantics even though the resulting schedules differ.

Both tests cases are based on examples provided by one of the CBS authors [7] and are available on GitHub, alongside with the kernel implementation itself, as a sample code [12]. The defined values of $C$ were implemented as calls to the k_busy_wait() Zephyr API function, which allows a thread to remain in CPU for the approximate time passed to it. The tracing events were recorded synchronously as each task was triggered, started and finished, but only logged after a predefined amount of time to decrease the overhead.

Application-wise, the main difference between the former implementation and the task-based one is that the CBS emulated the irregular job arrivals by setting a new period at the end of every cycle, whereas the previous version used a timer to trigger the jobs. If desired, one could employ a timer for both solutions, however that would not leverage the new implementation features, which would not make much sense. The task sets were subjected to the same time unit multipliers of $1000ms$, $100ms$, $10ms$ and $1ms$ as before.

The scheduling outcome (i.e. the order of execution of the tasks), as expected, remained exactly the same as illustrated in Figures 2(a) and 2(b), with the k_busy_wait inaccuracies once again driving the only changes between theory and practice (due to actual execution times decreasing as the unit multiplier went down to $1ms$). Thus, the observed behavior equally matched the theoretical one in regards to scheduling events, and the task-based implementation can be considered adequate.

As for the overhead analysis, one could also expect the outcome to be similar as before, since the kernel interactions required for the CBS to function accordingly remained identical between implementations: the CBS timer would still need to be paused on “switched away” (SWT_AY) events, and resumed on “switched to” (SWT_TO) events. The budget replenishing routines also remained the same, leaving no obvious culprits to explain significative differences between the approaches. However, they use different data structures and kernel objects in their implementation which could possibly change the compilation and resource optimization strategies, therefore impacting the overheads.

Figures 3 present a side-by-side comparison between the results reported in [16] and the updated implementation. Overall, the new approach demonstrates improvements in both overhead reduction and temporal consistency. In particular, SWT_TO is reduced by up to 32.7% in Test Case 1, while B_ROUT decreases by as much as 37.9% for larger time units, indicating a more efficient handling of CBS events. Additionally, the updated results exhibit smoother and more predictable trends across different time granularities, suggesting reduced sensitivity to timing artifacts. Although some localized increases remain (e.g., B_ROUT in Test Case 2 at specific time units) these are limited in scope.

Moreover, Table 1 complements the collected data by including the most frequent maximum overheads for each batch of samples ($O_f$) and the absolute highest values observed throughout all samples ($O_{max}$). Once again there are noticeable differences when compared to the results for the previous approach (from [16]).

By inspecting the average overheads, one can see the worst case for switching in to the CPU (SWT_TO) is now of 91.70 clock cycles and happens at the $10ms$ range, whereas for the previous approach it was of 110.92 clock cycles in the $1ms$ range. That is a reduction of 17.33%, and a worst case shifted to a less impactful time unit. A similar story is observed for the SWT_AY event, where the time unit remained $10ms$ for both approaches but the task-based CBS fared 80.06 clock cycles, versus the previous 90.94 clock cycles for the version in [16]. That is a reduction of 11.96%.

By comparing the new results (1) with the overheads in [16], it is also noticeable the absolute worst measures have reduced dramatically for the context switching, from 128 and 139 clock cycles in the previous approach to 107 and 99 clock cycles in the task-based CBS for the SWT_TO and SWT_AY events, respectively. Thus, the task-based CBS appears to cause less impact on context switches, and since those are fairly frequent events on multiprogramming environments, it may be considered a significative advantage over the approach in [16] (especially on large task sets).

However, the less frequent budget exhaustion event, B_ROUT, seemed to tell a different story. The average values for Test Case 1 indeed remained lower than 75 clock cycles for all time units, which is a slightly better result than the previous approach for the same conditions, however in Test Case 2 the task-based option yielded considerably higher overheads than the previous approach, for all time units except $1ms$. The worst average measure reached 130.31 clock cycles on $10ms$, and the absolute worst overhead observed throughout all samples ($O_{max}$) reached 261 clock cycles, or 69% more than the 154 clock cycles for the approach in [16].

Thus, assuming the same circumstance of the three events happening one after the other in their worst case scenario, the maximum overhead associated with the task-based approach would be of 467 clock cycles, or $2.91us$ considering the ESP32C3’s 160MHz clock speed. That is very close to the $2.63us$ of the previous implementation, and still much lower than the tick rate employed for tests (10kHz or $100us$). Performance-wise, this implementation is also considered acceptable.

The performed evaluation allows to conclude that both implementations correctly support bandwidth reservations and follow the expected CBS theoretical model behaviour when employing EDF scheduling. Although differences were observed with respect to their behaviour and overhead, both implementations proved to be effective in supporting aperiodic execution while maintaining temporal isolation. Also, the measured worst-case overhead of CBS operations was below $3us$ for both approaches, demonstrating that both proposed solutions are viable for use in a real-world setting.

It is important to note that the previous approach and the newly-presented task-based approach can be used interchangeably to some extent (for example, the tests conducted make use of the same task sets), however they also pose intrinsic differences that might be considered by system developers when crafting their applications. The previous version requires a background thread and a message queue to function and can be leveraged by interrupts to offload work into a deadline-controlled environment, whereas the new task-based approach requires some extra adaptation to fulfil this usage.

It is also hardly possible to have a task-based CBS running different workloads, as it is exclusive to a single task. A handful of tasks can be set to operate with their own CBS, each with a different job that would otherwise could be pushed to a single CBS in the previous approach. However, for other applications the task-based approach might be better suited, for example when there is a desire to provide bandwidth guarantees for all EDF tasks in the system, and as for resource usage, the task-based strategy might consume less memory and generate less preemptions than the previous approach for the same amount of servers in the application due to no requirement for a message queue or external job dispatchers for each.

In essence, the previous version is recommended for offloading asynchronously-generated work and the new task-based CBS is recommended for establishing additional execution guards on systems with more unpredictable tasks.

In this paper, we examine the integration of CBS within the Zephyr RTOS, suggesting a new Task-Based CBS, which involves embedding a private CBS entity within each individual application task. In order to support the proposed approach, a richer EDF implementation for Zephyr is also provided. The new CBS approach provide a different architectural trade-offs with respect to modularity, integration, and control, in relation to previous work. The CBS implementation has been developed within the Zephyr kernel and tested against representative sets of tasks, showing that it correctly supports bandwidth reservations and follows expected CBS theoretical model behaviour when employing EDF scheduling. Although differences were observed with respect to the behaviour and overhead, in relation to the previous approach, the new approach proved to be effective in supporting aperiodic execution while maintaining temporal isolation. The runtime overhead was found to be below $3us$, demonstrating that the proposed solution is viable for use in a real-world setting. As part of future work, an extension of the proposed approaches to multiprocessor systems will be carried out, including support for bandwidth inheritance, thereby extending the applicability of CBS-based scheduling within Zephyr.