From Jobs to Resources: Solving the Multiple Visit Problem in Real-Time Systems

TL;DR

Distributed real-time systems, such as automotive ECUs connected via CAN, rely on "Holistic Analysis" to guarantee deadlines. However, traditional methods are notoriously pessimistic when a transaction visits the same resource multiple times. This paper proposes a Per-Resource Analysis that shifts the focus from individual jobs to cumulative resource interference, tightening response time bounds by up to 77% and doubling the supportable system utilization.

The "Multiple Visit" Bottleneck

In modern Cyber-Physical Systems (CPS), a single transaction (like a sensor-to-actuator signal) might hop between various processors and buses. Specifically, it often revisits a central communication bus multiple times.

Traditional Per-Job Analysis calculates the worst-case delay for each step. If a transaction visits the CAN bus twice, the analysis assumes the worst-case high-priority interference occurs for both visits. In reality, a high-priority task with a long period might only be able to trigger once during the entire span of that transaction's bus usage. This "double counting" makes systems appear unschedulable on paper, even when they are perfectly safe in practice.

Figure 1: Traditional horizontal addition of per-job delays vs. the proposed vertical aggregation of per-resource delays.

Methodology: The Per-Resource Viewpoint

The paper introduces two critical concepts to break the cycle of pessimism:

1. Per-Resource Total Window ($T{W}_i$): The total time span between the release of the first task and the completion of the last task on a specific resource $R$.
2. Per-Resource Total Delay ($T{D}_i^j$): The maximum cumulative interference caused by high-priority transaction ${\Gamma }_j$ across the entire window $T{W}_i$.

The Core Intuition

Instead of calculating $w_{i,1},w_{i,2},\dots$ separately, the method uses an iterative convergence approach. It estimates the total window, calculates how many high-priority instances can actually fit into that window, and then uses that to refine the end-to-end response time.

If a high-priority task has a period longer than the $T{W}_i$, the per-resource analysis correctly limits the interference count to 1, whereas per-job analysis would count it for every visit.

Figure 2: Visualizing how the total window $TW$ is constructed by summing execution times and total delays across resources.

Experimental Validation

The authors tested their approach using an automotive-style model (9 ECUs + 1 CAN bus).

• Accuracy: As transaction length increased, traditional methods (Tindell, WCDO) saw response times skyrocket. The Per-Resource analysis stayed significantly closer to simulation results (see Figure 3).
• Utilization: Under traditional analysis, the system failed schedulability tests at just 30% utilization. With the proposed method, the system was provably schedulable up to 60% utilization.

Figure 3: End-to-end response time vs. transaction length. Note the massive gap between per-job methods and the proposed per-resource approach.

Critical Insight & Future Outlook

The beauty of this work lies in its orthogonality. Existing improvements like "Dynamic Offsets" (WCDO) focus on how to calculate interference between two specific tasks. This paper focuses on where the viewpoint of the entire summation should sit.

Limitations: The current model assumes deadlines are less than or equal to periods and does not yet integrate inter-task offsets. However, the authors suggest that combining offset-aware analysis with this per-resource viewpoint will likely provide the tightest possible theoretical bounds for distributed systems.

Conclusion

For engineers designing safety-critical systems like autonomous robots or aircraft, this per-resource transformation is a game-changer. It allows for more features and higher software complexity without requiring expensive hardware upgrades, simply by applying a smarter mathematical lens to the timing analysis.