“Scheduling” refers to arranging tasks in a certain order. According toMindtools‘ casual definition, it considers scheduling in daily life, which is the art of planning your activities so that you can achieve your goals and priorities within the available time. In other words, scheduling ensures that there is enough time to handle the most important tasks. Translating to the world of hard real-time systems: the key function of scheduling is to guarantee the execution of safety-critical tasks. It is important not only for the actual execution of tasks but also for them to be executed accurately and timely.
We have previously discussed hard real-time systems and the requirements they must meet in the article “Future-Oriented Real-Time Automotive Safety Systems“. To introduce this concept, Professor Kopetz described the scheduling problem in his classic work Real-Time Systems as: meeting their specified deadlines. Each task requires computational and data resources to proceed. The scheduling problem relates to allocating these resources to meet all timing requirements.”
Let’s place this in the context of our industry, where automotive electronic and electrical systems are moving towards integrating traditionally separate domains. With the aggregation of automotive functions on general hardware, the importance of systems’ accurate timing behavior is increasing. This is especially true for Autonomous Driving (AD) systems, which combine complex functionalities with stringent safety requirements. Their software functionalities must coexist and share resources with other software-driven automotive functions without compromising their real-time safety requirements, thereby raising the standards for automotive operating systems. Moreover, AD imposes not only strict real-time requirements on individual functions but also additional requirements on priority dependencies between sensors, control software, and actuator networks. TTTech lab scientist Silviu S. hybrid critical systems require higher standards in safety-critical compliance, timing, and spatial isolation, leading to new scheduling functionalities needed at runtime and new configuration tools required at design time.
With the emergence of Automated, Connected, Electric, and Shared (ACES) mobility, these challenges increase with the growing number of digital functionalities in vehicles. To respond adequately, modern vehicles not only need additional computational power to run increasingly complex software but also mechanisms that can truly guarantee individual and collective safety levels as well as the priorities of all automotive functions. This is why safe real-time scheduling is at the core of the future of automobiles.
What is Real-Time Scheduling?
Distributed real-time computer systems execute multiple system functions simultaneously on their nodes. To ensure consistent execution of functionalities across the entire distributed system, all incoming events must be processed by their respective nodes in the order they occur.
Therefore, all interconnected components of the distributed system must be appropriately synchronized with each other to ensure reliable behavior of the entire system. For real-time distributed systems, it is also necessary to synchronize local clocks of all nodes with a reference clock that follows physical world indicators by aligning them with International Atomic Time (TAI).
Nodes in real-time distributed systems must operate under the same global time
To define “correct” synchronization, we can imagine each node ticking with its local clock, which we call micro-ticks. A subset of micro-ticks aligned within an acceptable tolerance range with the global time scale will be referred to as macro-ticks (or simply as ticks) of global time. Thus, when these macros reflect the micros selected correctly from the synchronized local physical clocks of the considered node set, the concept of global time is introduced into the system.
In addition to synchronizing tasks across nodes, coordinated communication between nodes is also essential for the successful operation of the entire system. Each task consists of multiple individual operations or steps. During each task execution, a sequential program reads input data and the internal state of the node, determines and passes output results, and updates the internal state of the node.
All this can be measured in time: the actual duration of a task is the time interval between the start and end of the task. The maximum possible duration of task execution under all possible input data and execution scenarios is called the Worst-Case Execution Time (WCET). In real-life scenarios, the closer the WCET is set to runtime, the more efficient the use of scheduling will be. Jitter is the difference between WCET and the minimum duration of the task (the minimum time interval for task execution).
In hard real-time systems, all critical tasks must be completed on time
In hard real-time computer systems, safety-critical tasks must be executed under strict timing constraints. These tasks must meet all deadlines and be executed within very tight time intervals to achieve “global” real-time end-to-end guarantees. Scheduling is the method of allocating resources of the computer system to tasks to ensure their accurate and timely execution. Based on this, real-time scheduling is a method by which tasks are allocated on the system’s nodes such that the maximum allowed jitter value for any task on any node does not exceed, ensuring predictable and hence safe behavior of the entire system.
Implementing Hard Real-Time Scheduling for Autonomous Vehicles
Real-time scheduling can be implemented in different ways. Let’s consider the available options as shown below:
Classification of Real-Time Scheduling
The main difference between dynamic and static hard real-time scheduling is that dynamic scheduling is performed online at runtime, while static scheduling is performed offline before runtime. Dynamic schedulers are flexible and can make scheduling decisions “anytime, anywhere”. This means they adapt to evolving task flows, selecting tasks to schedule from the current set of ready tasks. The overhead of finding such schedules at runtime can be significant. Dynamic schedulers allocate task start times at runtime, while static schedulers have already found these times at design time. Static schedulers generate scheduling tables containing a complete set of information about offline tasks and then schedule these tasks at runtime.
Continuing our classification diagram, we can see two different approaches to static and dynamic scheduling—preemptive and non-preemptive scheduling. In preemptive scheduling, some tasks can be interrupted (preempted) by other more urgent tasks. In non-preemptive scheduling, tasks can decide when to release resources (usually upon completion) to other tasks. If many short tasks need to be executed, it makes sense to schedule tasks in a non-preemptive manner.
Finding a feasible schedule is a complex process that can lead to higher efficiency for the entire distributed system. Certain task characteristics may aid this search. A particularly useful measure for schedulability is the task request time, which is the time at which a task is requested for execution. Based on the task request time, we can differentiate between two types of tasks: periodic and sporadic. After the first request for a periodic task, all future request times can be known by adding multiples of the known period to the initial request time. For sporadic tasks, request times are unknown until their activation. In this case, the schedulability criterion is whether there is a minimum interval between any two request times of sporadic tasks. Additionally,
Considering the available options, what is the correct method for real-time scheduling in AD systems? We have pointed out that AD heavily relies on hard real-time behavior. Looking into the “internals” of AD systems, we see many concurrent tasks sharing common resources and exchanging data. In real-world scenarios, this involves considering many dependencies, such as higher-priority tasks taking precedence over lower-priority tasks and mutual exclusion constraints between tasks to find suitable scheduling. Faced with these challenges, dynamic scheduling techniques struggle to guarantee the urgent deadlines available for these tasks, especially considering the need to manage communication between E/E architecture nodes. In other words, the expressive power of dynamic models is insufficient to effectively capture all these real-life demands, and once the system exceeds the (extremely oversimplified) assumptions in the dynamic model, it becomes nearly impossible to ensure guarantees. Therefore, to achieve the required level of predictability and effectively ensure the safety of autonomous driving functionalities, we need a static pre-runtime scheduling as a replacement.
Static scheduling is determined at design time based on the overall events and execution activities, suitable for systems of varying complexity, including distributed real-time systems. It deals with pre-planned resource usage in distributed systems and pre-planned access to communication media. Although computer systems cannot control external interrupts, the timing points at which these incoming events will be served can be defined a priori, based on assumptions about each category of events. We can view static scheduling as a search for feasible scheduling. The goal of this search is to find a complete timetable that considers all priority relationships and mutual exclusion constraints between tasks and ensures that all tasks are completed before their deadlines. Heuristic functions can be applied to the search to improve and optimize results. The award-winning paper Mapping and Scheduling Automotive Applications on ADAS (Advanced Driver-Assistance Systems) Platforms using Metaheuristics proposed this search optimization strategy.
Although static scheduling is a method for achieving high predictability in advanced systems, it can only handle situations where the dependencies between tasks are known at design time. To be able to address variable real-world use cases, certain methods have been introduced to increase the flexibility of static scheduling.
One of these efficiency measures is mode switching. ADAS applications operate in different operational modes, such as parking mode or highway mode. These two modes do not require the same services and functionalities. By scheduling tasks separately, better resource utilization can be achieved based on the active mode. Resources can then be allocated at the right time and place. System designers must identify all operational and emergency modes and compute static scheduling for each mode offline, and then the mode-switching scheduling must be activated accordingly when a mode switch is requested at runtime.
These are the elements that static real-time scheduling brings to ensure safe AD system behavior and optimal use of computational resources under a wide range of possible scenarios and their individualized requirements. They must ensure the correctness and responsiveness of the system.
Practical Safe Real-Time Scheduling with MotionWise
The aforementioned development of ACES is driving the automotive industry towards software-defined and centralized E/E architectures. With this trend, it is expected that vehicle operating systems will evolve towards supporting all vehicle functionalities in a few central computing centers while ensuring the availability and safety of the entire system. The demand for testing and verification work is increasing, and it is necessary to simulate real scenarios to achieve accurate and reliable system behavior. This integration of domains, along with the different applications of mixed-criticality integrated into the system, requires a system design that supports the guaranteed priority of critical software functionalities and their resilience against potential interferences.
Enter MotionWise, a software safety platform that combines runtime services and design-time tools to address these issues, providing end-to-end guarantees for software behavior. By defining and enforcing pre-defined execution boundaries for each application and implementing pre-runtime static scheduling, MotionWise orchestrates the mechanisms provided by lower-level operating systems to ensure real-time behavior across the entire system. With its tools, MotionWise can develop automotive software in a coordinated and seamless manner throughout the software development lifecycle, including design, integration, testing, and verification.
Let’s delve into the working techniques here: MotionWise provides an execution manager that deterministically coordinates the scheduling of multiple applications across all hosts in the system. All communication between hosts is achieved through deterministic networks and coordinated by the MotionWise Communication Manager Stack. The global scheduling concept ensures that all task scheduling on the hosts is consistent with the network scheduling of the backbone communication network connecting these hosts. Since global scheduling requires the same time concept across all hosts, it must be supported by dedicated MotionWise functionalities to achieve reliable time synchronization. Moreover, all of this is abstracted from the user’s perspective through MotionWise planning tools and the execution onboard software stack.
The complexity of modern distributed systems, combined with the extremely complex and unpredictable real driving conditions, creates a challenging starting point for finding suitable schedules that can meet the safety requirements of highly automated, software-defined vehicles. Therefore, creating effective schedules requires a global view: system-wide planning and global time considerations. This often means architectural work in multi-host, and sometimes even multi-ECU environments. The global scheduler creates schedules for heterogeneous, multi-ECU, multi-SoC, multi-core systems. This is achieved through MotionWise Creator, which generates effective schedules based on user-defined constraints. This tool can also provide information when feasible schedules cannot be formulated.
MotionWise Global Scheduler Functionality
As mentioned earlier, real-life situations often introduce highly complex task flows, where it is necessary to manage a large number of interdependent and mutually exclusive tasks properly. To ensure that all these tasks are well-organized and scheduled according to their interdependencies and delay requirements, MotionWise groups these tasks into so-called computation chains (CC). Additionally, they can be scheduled on any host and have different time slots. At runtime, the deterministic execution of the CC is ideally ensured by the WCET of its tasks and message transmissions. If the WCET cannot be accurately estimated, it cannot be guaranteed that specific tasks will not exceed their scheduled time. In practice, runtime budgets are iteratively estimated to minimize the likelihood of overruns. In the rare cases where overruns do occur, MotionWise detects, reports, and triggers appropriate error responses. Incoming tasks can be categorized as event-driven, data-driven, or time-driven. For example, planning and control are time-driven, while multiple asynchronous sensor inputs are event-driven. An example of a data-driven task is the perception layer, which consists of a series of processes that have data dependencies between them.
Computation Chain
Since different applications run on different hosts based on their requirements and priorities, ADAS system architects decide which strategies to apply to which applications to meet all functionality and safety requirements.
Time-triggered scheduling strategies can execute relevant time-driven tasks with high determinism. These tasks are activated and executed within their respective fixed-length time slots and occur periodically at predetermined points in time. Scheduling tables are generated offline and deployed statically. This approach allows for high levels of non-interference; however, tasks may not require the full allocated time budget to execute them (especially those with highly variable runtimes), thus necessitating more efficient resource use in these scenarios. Since even safety-critical tasks may have variable runtimes, it is crucial to use resources effectively on each host. Additionally, in the overall processing activities of our hard real-time systems, not only periodic tasks but also sporadic tasks need to be considered. This seems to be a weakness of static scheduling.
Clearly, the modern automotive industry requires flexible scheduling mechanisms to cover a wide range of possible use cases. As a response to real-world driving conditions, MotionWise scheduling capabilities embody the perfect synergy between flexibility and safety. Our time-aware solution architecture enables the execution of various applications by allowing the completion of event-driven and data-driven tasks while still providing time guarantees. For instance, periodic sensor inputs (camera image frames) are inherently asynchronous and must be processed in an event-driven manner. MotionWise Scheduling Service handles both time-driven and event-driven tasks by integrating event-driven tasks (sensor inputs) into the time-aware architecture. Unlike time-driven tasks with predefined time slots,
Event-driven tasks in our time-aware architecture
MotionWise also allows for data-driven scheduling, where users can define a set of data-driven tasks. The use case for data-driven methods is the dynamic sequential execution of tasks in the perception layer, where data-driven tasks can start immediately upon meeting prerequisites (input data being ready). Although the execution of individual tasks does not inherently depend on the completion of previous tasks, it is crucial that the end-to-end latency does not exceed the upper limit.
Optimizing Resources through Data-Driven Scheduling
MotionWise is both flexible and precise, showcasing different mechanisms that support this ultimate safety goal. We have mentioned that mode switching is a very useful method to improve static scheduling efficiency. To allocate resources effectively, it is important to adopt separate scheduling methods for different operational modes of the system. In other words, having a single scheduling table would lead to suboptimal resource usage, and generating schedules would take longer. MotionWise Scheduling Service supports switching between multiple pre-configured scheduling tables at runtime for mutually exclusive applications, such as highway navigation and parking assistance.
As described in this article, hard real-time scheduling is critical for ADAS and the entire development of AD. The MotionWise platform provides all the functionalities needed to plan, build, and run safe real-time E/E architectures today. As ACES mobility gradually becomes a reality in our world, it is essential to ensure that human lives are never at risk alongside technological advancements. At TTTech Auto, we understand the significance of this journey and work passionately every day to provide unconditional solutions for safety, which is the requirement for truly prosperous modern mobility.
Dear Readers, we look forward to your shares and likes!
Copyright belongs to the original author. If there is any infringement, please contact to delete.
https://www.tttech-auto.com/expert_insight/real-time-scheduling-for-safe-autonomous-driving/