CN-121996383-A - Response time analysis method of ROS2 chain-aware scheduling strategy

CN121996383ACN 121996383 ACN121996383 ACN 121996383ACN-121996383-A

Abstract

The invention discloses a response time analysis method of a ROS2 chain perception scheduling strategy, which takes a task chain, callback and parameter information of a directed acyclic graph of an RO2 program, parameter information of an actuator and the scheduling strategy as inputs, calculates blocking workload generated by an internal precursor dependency relationship of a target task chain, calculates an upper limit of interference workload generated by a high priority callback of the directed acyclic graph and an upper limit of blocking workload generated by a low priority callback caused by non-preemptive scheduling, constructs a total demand boundary function according to the blocking workload, the upper limit of interference workload and the upper limit of blocking workload, calculates a key time interval according to the total demand boundary function, and obtains a response time upper limit of the target task chain according to the calculated key time interval and an inverse supply boundary function. The shared instance and priority inheritance effect in the directed acyclic graph can be accurately carved, the interference workload can be accurately estimated, and the reliability of the upper bound of the response time is improved.

Inventors

HUANG HANYAN
WU ZHENGDA
SU TIANJUN

Assignees

中山大学

Dates

Publication Date: 20260508
Application Date: 20260128

Claims (10)

1. A method of response time analysis for ROS 2-chain-aware scheduling policy, comprising: acquiring a task chain, callback and parameter information of a directed acyclic graph of an RO2 program, parameter information of an executor and a scheduling strategy as input; determining a target task chain to be analyzed and a target directed acyclic graph to which the target task chain belongs; calculating blocking workload of a target task chain due to internal precursor dependency according to the input; Calculating a first interference workload upper bound generated by high-priority callbacks from other non-target directed acyclic graphs than the target directed acyclic graph according to the input; calculating a second interference workload upper bound generated by a high priority callback from the target directed acyclic graph according to the input; Calculating a blocking workload upper bound caused by low priority callbacks due to non-preemptive scheduling of an actuator according to the input; constructing a total demand boundary function according to the blocking workload, the first interference workload upper bound, the second interference workload upper bound and the blocking workload upper bound, and calculating a key time interval according to the total demand boundary function; and obtaining the response time upper bound of the target task chain according to the calculated key time interval and the inverse supply boundary function of the actuator thread.
2. The method of claim 1, wherein calculating a first interference workload upper bound from high priority callbacks from non-target directed acyclic graphs other than target directed acyclic graphs based on inputs comprises: Calculating the workload upper bound of a single callback in a constraint deadline chain; determining selector variables of callback interference in the directed acyclic graph; and calculating a first interference workload upper bound according to the workload upper bound of the single callback in the constraint deadline chain and the selector variable.
3. The method of response time analysis of ROS2 chain-aware scheduling policy of claim 2, wherein the workload bound of a single callback in the constraint deadline chain is derived according to the following formula: ; in constraint deadline chaining for single callbacks Is used as an upper bound on the workload of the users, To belong to constraint deadline chains Callback of (2) Is used to determine the worst-case execution time of (a), To constrain the deadline chain Is used in the release period of the (c) in the (c), In order to provide for the time interval of time, Linking additional time parameters for capturing constraint deadline incorporations; the selector variable of callback interference in the directed acyclic graph is obtained according to the following formula: wherein, the method comprises the steps of, To call back the interfering selector variable in the directed acyclic graph, For a set of callbacks in the directed acyclic graph that do not belong to any converging callback successor, To belong to any set of call-backs subsequent to the converging call-backs in the directed acyclic graph, A constraint deadline chain with the highest priority and containing the callback; For inter-chain interference indication functions, for determining whether an instance of a callback from a constraint deadline chain would interfere with a target task chain, , To indicate a function, the value is 1 when the condition in brackets is true, 0 when the condition in brackets is false, To constrain the priority of the deadline chain, For the priority of the target task chain, For callback Is set according to the priority of (1), Priority for the u-th callback in the target task chain.
4. The method of claim 3, wherein the first interference workload upper bound comprises an interference workload upper bound from a non-end instance of other non-target directed acyclic graphs, expressed according to the following formula: wherein, the method comprises the steps of, For the upper bound of interference workload from the non-ending instances of other non-target directed acyclic graphs, For a single callback to be a workload upper bound in the constraint deadline chain, In order for the selector variable to be selected, For a set of callbacks in a directed acyclic graph, Is a collection of task chains in a directed acyclic graph.
5. The method of claim 3, wherein the first interference workload upper bound comprises an interference workload upper bound from an end instance of other non-target directed acyclic graphs, expressed according to the following formula: wherein, the method comprises the steps of, For the upper bound of interference workload from the last instance of other non-target directed acyclic graphs, For a set of callbacks in a directed acyclic graph, , In order for the selector variable to be selected, For a set of task chains in a directed acyclic graph, The release period is called back for the only source in the directed acyclic graph.
6. The method of claim 3, wherein the second interference workload upper bound generated by the high priority callback of the target directed acyclic graph is derived according to the following formula: wherein, the method comprises the steps of, A second interfering workload upper bound generated for the high priority callback of the target directed acyclic graph, For a set of callbacks in the directed acyclic graph, Is a collection of task chains in a directed acyclic graph.
7. The method of claim 1, wherein the blocking workload upper bound is derived from the following formula: wherein, the method comprises the steps of, In order to block the upper bound of the workload, Low priority callback sets for blocking for screening out Is provided.
8. The method of claim 1, wherein the total demand boundary function is derived from the following formula: wherein, the method comprises the steps of, As a function of the overall demand boundary, In order to achieve the number of threads of the actuator, For blocking workload of the target task chain due to internal precursor dependencies, For the upper bound of interference workload from the non-ending instances of other non-target directed acyclic graphs, For the upper bound of interference workload from the last instance of other non-target directed acyclic graphs, The second interfering workload upper bound generated for the high priority callback from the target directed acyclic graph, In order to block the upper bound of the workload, For a set of callbacks in a directed acyclic graph, In the form of a directed acyclic graph, Directed acyclic graphs are targets.
9. The method of claim 8, wherein calculating a critical time interval from the total demand boundary function comprises iteratively solving for satisfying a condition by a fixed point As critical time intervals, wherein, The boundary function is supplied for the population of actuators.
10. The method of claim 1, wherein the upper bound of response time is obtained according to the following formula: wherein, the method comprises the steps of, In order for the response time to be in the upper bound, In order to provide for the time interval of time, For the inverse supply boundary function of the actuator, And callback execution time for the sink of the target task chain.

Description

Response time analysis method of ROS2 chain-aware scheduling strategy Technical Field The invention relates to the field of computers, in particular to a response time analysis method of an ROS2 chain-aware scheduling strategy. Background In the robot field, ROS2 (Robot Operating System 2) is a mainstream framework facing to robot manufacturing, an ROS2 application program is composed of a plurality of nodes, the nodes trigger different types of callbacks (such as timer callbacks, subscription/service/client event callbacks) through a communication mechanism such as subscription and the like, and an executor uniformly manages an operating system thread to schedule and execute callback instances, in the environment, message propagation and front-back dependence among callbacks can be represented by a directed acyclic graph, and a chain is an execution path from a source callback to a converged callback. PiCAS (Priority-DRIVEN CHAIN-Aware Scheduling) is a chain-Aware Scheduling strategy for improving the real-time performance of ROS2 executors, which is to assign static priorities to the links first, piCAS assigns static priorities to the callbacks in the offline stage and schedules them accordingly, so that the end-to-end response time of the high-Priority links is better guaranteed, but PiCAS will preempt the real high-Priority links when the workload extends from a chain topology where each callback belongs to only a single chain to a directed acyclic graph topology (where the callbacks may belong to multiple chains and even multiple direct precursors) because of the fact that the callback is "fixed with a highest Priority" to the callback. PiCAS-DAG is an improvement to DAG topology based on PiCAS, which proposes "static-runtime priority allocation, keeps fixed priority with callbacks belonging only to single chains as static callbacks, and propagates and determines the priority to be adopted by this instance by triggering its precursor callback at runtime as runtime callback, and simultaneously, adapts callback structure and executor architecture to support dynamic priority propagation and determination, thereby avoiding inter-chain priority inversion of PiCAS in DAG topology, and making scheduling semantics consistent with" chain-by-chain priority guarantee key chain ". The constrained deadline chain is a processing chain with deadline constraints, i.e. a pair chainIts parameters include release periodAnd relative deadlinesWherein constraint relationships are satisfiedIs a constrained deadline chain. The existing PiCAS-oriented response time analysis framework mainly takes independent chains as a basic view of modeling and interference workload analysis, and defaults callback instances of different chains to be independent of each other and interference is only determined by a chain priority relation. However, when the execution constraint between callbacks is no longer a simple independent chain, but forms a directed acyclic graph topology (branches and confluences exist, and callbacks are shared by multiple chains), the disturbance workload estimation is inaccurate, and the reliability of the upper bound of response time is affected, which is particularly typical of two types, namely (1) overestimation that when the branch callbacks exist, multiple chains may share the same segment of precursor subchain (shared prefix path), the callback instances of the shared subchain actually only execute once and are jointly multiplexed by the multiple chains in the running process, but the existing framework still calculates the disturbance according to the fact that each chain has one part, so that the workload of the shared part is repeatedly accumulated, and the disturbance is exaggerated, and (2) underestimation that when the confluence exists, the multiple chains may share the same segment of subsequent subchain (shared suffix path), and the priority allocation policy of PiCAS may enable sharing to inherit the highest link priority in the links to which the callback belongs, so that the shared callback instances released by the low priority link may also execute at a high priority and be blocked by the shared callback instances, and the other callback instances are blocked by the high priority, and the existing callback instances are ignored, and the disturbance is actually ignored, so that the disturbance is caused by the high priority and the priority is spread by the existing callback frame. In general, independent chain views cannot correctly score shared instances and priority inheritance effects in directed acyclic graphs. Disclosure of Invention The following is a summary of the subject matter described in detail herein. The application aims to solve one of the technical problems existing in the related technology to at least a certain extent, and the embodiment of the application provides a response time analysis method of an ROS2 chain-aware scheduling strategy, which can accurately draw a shared in