یک مرور کلی از تکنیک های حسابداری وقفه برای سیستم های چند پردازنده زمان واقعی

The importance of accounting for interrupts in multiprocessor real-time schedulability analsysis is discussed and three interrupt accounting methods, namely quantum-centric, task-centric, and processor-centric accounting, are analyzed and contrasted. Additionally, two special cases, dedicated interrupt handling (i.e., all interrupts are processed by one processor) and timer multiplexing (i.e., all jobs are released by a single hardware timer), are considered and corresponding analysis is derived. All discussed approaches are evaluated in terms of schedulability based on interrupt costs previously measured on a Sun Niagara multicore processor. The results show that there is no single “best” accounting technique that is always preferable, but rather that the relative performance of each approach varies significantly based on task set composition, i.e., the number of tasks and the maximum utilization.

System overheads such as time lost to task switches and scheduling decisions must be accounted for in real-time systems if temporal correctness is to be guaranteed [1] and [2]. Of these overheads, interrupts are notoriously troublesome for real-time systems since they are not subject to scheduling and can significantly delay real-time tasks. In work on uniprocessor real-time systems, methods have been developed to account for interrupts under the two most-commonly considered real-time scheduling policies [3]: under static-priority scheduling, interrupts can be analyzed as higher-priority tasks [2], and under earliest-deadline-first (EDF) scheduling, schedulability can be tested by treating time lost to processing interrupts as a source of blocking [4]. Properly—but not too pessimistically—accounting for interrupts is even more crucial in multiprocessor real-time systems. Due to their increased processing capacity, such systems are likely to support much higher task counts, and since real-time tasks are usually invoked in response to interrupts, multiprocessor systems are likely to service interrupts much more frequently. Further, systematic pessimism in the analysis has a much larger impact on multiprocessors, as is shown below. Unfortunately, interrupts have not received sufficient attention in work on multiprocessor real-time systems. The first and, to the best of our knowledge, only published approach to date was proposed by Devi [5]. Devi presented a quantum-centric accounting method in which the length of the system’s scheduling quantum is reduced to reflect time lost to overheads. In this paper, we consider this method, as well as two others, in the context of global scheduling algorithms. When the quantum-centric method is applied in this context, it is usually necessary to assume that all possible interrupts occur on all processors in every quantum. This assumption is obviously quite pessimistic and motivates the consideration of other approaches. Motivating example. In a recent case study on a 32-processor platform involving up to 600 light1 tasks, the release overhead (i.e., the time taken to process a timer interrupt and invoke a real-time task) of a global EDF (G-EDF) implementation was measured to exceed 50 μs in the worst case [6]. Given the system’s quantum size of 1000 μs, the quantum-centric method would have deemed any task set of 20 or more tasks unschedulable—with fewer tasks than processors, this is clearly excessively pessimistic. In the above case study, a new, less pessimistic “task-centric” accounting method (see Section 4) was developed. However, even with “task-centric” accounting, G-EDF performed worse than expected. Suspecting high job release overhead to be the cause, we conducted simulations to estimate performance assuming reduced overhead. Surprisingly, we found that even with a 75% reduction in release overhead, schedulability increases very little (see Fig. 1). However, the experiments also confirmed release overhead as the leading cause of reduced schedulability—performance improved dramatically assuming overhead-free releases. This discrepancy stems from quadratically-growing pessimism in the “task-centric method,” as is shown in Section 4.3.3. Fig. 1 highlights that accurate accounting for overheads is crucial to multiprocessor real-time performance, and that systematic pessimism can have a significant impact on multiprocessor systems due to high task counts.Contributions. This paper provides an overview of all currently-known multiprocessor interrupt accounting techniques for global schedulers. In particular, we • highlight the importance of accurate interrupt accounting for multiprocessor real-time systems and survey commonly-encountered interrupt sources in current multiprocessor systems (Section 2, formalized in Section 3); • summarize “quantum-centric” interrupt accounting (Section 4.1) and describe “task-centric” interrupt accounting (Section 4.3), which has been used—but not described in detail—in previous studies [6], [7] and [8] to overcome the limitations of “quantum-centric” accounting, and show that the “task-centric” method still over-estimates interrupt delays by a factor that is quadratic in the number of tasks (Section 4.3.3); • show how interrupt accounting is fundamentally different from previous work on reduced-capacity scheduling and, by addressing these differences, propose “processor-centric” interrupt accounting, which is designed to overcome the pessimism inherent in “task-centric” accounting (Section 4.4); • discuss two common special cases, namely how job releases are delayed if interrupts are handled by a dedicated processor (Section 5.2), and further how said delays change if all job releases are triggered by a single hardware timer (Section 5.3); and • evaluate the effectiveness of all considered approaches in terms of schedulability for both hard and soft real-time systems and show that none of the proposed approaches strictly dominates the others, i.e., there is no single “best” approach (Section 6). This paper extends a previous conference version [9]; in particular, a discussion of delays due to “inter-processor interrupts” (Section 4.2) and common special cases (Section 5) has been added, and the experiments (Section 6) were augmented to include all special cases and repeated with more-recent overhead measurements [8], thus reflecting over a year of implementation improvements. Next, we provide a survey of common interrupt types and describe how they are usually serviced by operating systems.

This paper surveyed various types of interrupts that occur in multiprocessor real-time systems and summarized Devi’s quantum-based accounting method. Two recently-developed approaches to accounting for interrupt-related delays under G-EDF scheduling for both hard and soft real-time systems were presented: the task-centric method and the processor-centric method. Further, analysis for the common practice of dedicating a processor to interrupts to shield real-time jobs from delays was presented, including the special case of timer multiplexing. In an empirical comparison, the task-centric method performed well in most of the tested scenarios; however, it is subject to utilization loss that is quadratic in the number of tasks. Hence, it has inferior performance for large task sets. In contrast, in the soft real-time case, the processor-centric method performed well for task systems with many light tasks, but yielded overly pessimistic results in the presence of heavy tasks. In all considered scenarios, at least one of the two new methods performed significantly better than the previously-proposed quantum-centric method. Further, the experiments revealed that dedicating a processor to interrupt handling can be beneficial to schedulability in many cases—especially so if all job releases are time-triggered. However, dedicated interrupt handling is likely much less competitive for lower processor counts, and is also not always the best choice if overheads are low. Thus, accounting for interrupts remains an important component of schedulability analysis. In future work, we would like to refine the processor-centric method to be less pessimistic with regard to both maximum task utilization and reductions in supply. Further, it may be beneficial to investigate whether multiprocessor real-time calculus [32] can be applied to account for interrupt delays.