As an effective method for detecting the schedulability of real-time tasks on multiprocessor platforms, Response time analysis (RTA) has been deeply researched in recent decades. Most of the existing RTA methods are designed for tasks that can be preempted at any time. However, in some real-time systems, a task may have some fixed preemption points (FPPs) that divide its execution into a series of non-preemptive regions (NPRs). In such environments, the task can only be preempted at its FPPs, which makes existing RTA methods for arbitrary preemption tasks not applicable. In this article, we study the schedulability analysis on tasks with FPPs under both global fixed-priority (G-FP) scheduling and global earliest deadline first (G-EDF) scheduling. First, based on the idea of limiting the time interval between two consecutive executions of an NPR, a novel RTA method for tasks with FPPs under G-FP scheduling is proposed. Second, we propose an effective RTA method for tasks with FPPs under G-EDF scheduling. Finally, extensive simulations are conducted and the results validate the effectiveness of the proposed methods.

Response time analysis (RTA) is an important and fundamental tool for analyzing the schedulability of real-time tasks on multiprocessor platforms, and many promising techniques have been developed during the past few years. However, most of the existing researches focus on improving the analysis precision, while less has been done on enhancing the execution efficiency. In this paper, we take, to our best knowledge, the first effort towards improving the efficiency of the state-of-the-art RTA methods for sporadic tasks under both global fixed-priority (G-FP) and global earliest deadline first (G-EDF) scheduling. Specifically, three factors that impact the efficiency of existing global RTA tests are identified: 1) pessimistic initial value when computing the worst-case response time (WCRT) of tasks under both G-FP and G-EDF; 2) conservative interference upper bound under both G-FP and G-EDF; and 3) unnecessary recalculation of WCRTs when there is update of any task WCRT under G-EDF. By addressing these three limitations, we propose two efficient RTA methods for G-FP and G-EDF scheduling, respectively, which achieve better run-time performance but without sacrificing any analysis precision. Experimental evaluations with randomly generated task sets show that the proposed methods exhibit remarkable performance improvements and can save on average 60 and 61 percent run time, as compared to the state-of-the-art technologies under G-FP and G-EDF scheduling, respectively.

Deriving deadline and period for update transactions to maintain temporal consistency has long been recognized as an important problem in real-time database research. Despite years of active study, most of the past work only focuses on the scheduling of update transactions, and neglects the impact of control transactions by assuming anUpdate Firstpolicy where control transactions are always assigned lower priorities than the update transactions. On the other hand, most existing work on co-scheduling of update and control transactions has been focused on meeting the deadlines of all the control transactions while maximizing the quality of data of the real-time data objects. In this paper, we study the co-scheduling problem of update and control transactions by satisfying the deadline constraints of control transactions and the temporal validity constraints of update transactions simultaneously. Specifically, we consider the problem of how to derive deadline and period for update transactions to maintain the temporal consistency of real-time data objects, while guaranteeing the hybrid transaction set to be EDF-schedulable. To address this problem, we first borrow the idea from$\mathsf{minD}$[14]to derive a solution called$\mathsf{minD}^\ast$, which can compute deadline and period for update transactions effectively. Next, based on a sufficient condition to derive the minimum possible deadline for each update transaction, we propose a more efficient algorithmMinimum Deadline Calculation($\mathsf{MDC}$), which can guarantee to derive a solution, given that one does exist. Finally, the effectiveness and efficiency of the proposed algorithms are validated through extensive simulation experiments.