Minimal schedulability interval is one of the important considerations of both research motivation and practice stage. In this paper, we investigate the problem of finding a starting time point of the minimal schedulability interval for fixed priority independent periodic real-time preemptive tasks with arbitrary given release offsets (phasing). A linked list-based method is proposed for solving the problem. Each node in the linked list represents a pending-less busy period. Analysis and experimental results show that the linked list-based method outperforms the current best acyclic-idle-slot-based one.

Functional Reactive Programming (FRP) provides an elegant way to express computation in domains such as interactive animations, robotics, computer vision, user interfaces, and simulation. Priority-based (preemptive) FRP (P-FRP), a variant of FRP with more real-time characteristics, demands research in its scheduling and timing analysis. Different from the classic preemptive model, in a P-FRP system, when a task is preempted, all changes made by the task are discarded and after higher priority tasks complete their execution the preempted task will restart from the beginning (abort-and-restart). P-FRP is thus able to capture changes of the task in time and provides an option other than the classic preemptive model in certain scenarios. In the P-FRP model, previous studies use the largest execution time of a task for all its restarted jobs. In practice, however, when considering the changing/unchanging inputs/outputs of the task or the memory effects such as cache-hit in loading code and data, the restarted jobs likely consume less time than its largest execution time. In this paper, for the first time we present a multi-mode P-FRP task framework and two particular scenarios for the framework that are able to reflect such effects and then improve the performance of a developing commercial software platform. We show that the multi-mode task P-FRP system has significant schedulability improvements over the original P-FRP model.

Summary form only given. In the context of fixed priority preemptive real-time systems, for n periodic/sporadic tasks that comply with a restrictive system model and that have implicit deadlines the Rate-Monotonic (RM) scheduling is optimal. When these tasks are released simultaneously the time required by the first job of each task defines its response time. It thus needs only to make response time analysis or conduct exact schedulability test within a time length no more than the maximum task period (Tn) for RM scheduling, and these tests are thus known to be pseudo-polynomial in time complexity. Although the response time computation for RM schedules of implicit-deadline task-systems has been proved to be an NPhard problem, the scale of many commercial systems is such that pseudo-polynomial exact tests can be used, and to achieve more efficient exact tests such as for online response time analysis (RTA) is one of important considerations of both research motivation and practice stage. The innovative aspect of our solution is that we use a linked list for representing the schedule in the exact response-time schedulability test, referred to as the LList-based test. A busy period in the schedule is represented by a linked list node, recording the starting time and the end time of a busy period, and the pointer to the next node. The simulation is performed task per task in the priority order (from 1 to n), and, when the starting time or the end time of a busy period is the same as that of other busy periods, then the two nodes are merged into one node to represent a longer busy period. For improving the efficiency, memory allocation and recycle for each node are also performed in the user space. The time complexity of the LList-based test is O(N) where N is the total number of jobs within the time length Tn, while the total number of nodes in the linked list is no more than N - n + 1 in the worst case. Our experiments show that the LList-based exact test is a better candidate in exact response-time tests when task periods span no more than three orders of magnitude, since it outperforms the current best exact tests in this scenario, and the needed memory space is also affordable.

Summary form only given. Functional Reactive Programming (FRP) is playing and potentially going to play a more important role in real-time systems. Priority-based (preemptive) FRP (P-FRP), a variant of FRP with more real-time characteristics, demands more research in its scheduling and timing analysis. In a P-FRP system, similar to a classic preemptive system, a higher priority task can preempt a lower-priority one and make the latter abort. The lower-priority task will restart after the higher priority tasks complete their execution. However, unlike the classic preemptive model, when a task aborts, all the changes made by the task are discarded (Abort and Restart). In previous studies, the value of Worst Case Execution Time (WCET) of a task is used for all its restarted tasks. However, in practice restarted tasks likely consume less time than WCET when considering the memory effect such as cache-hit in loading code and data. Here we consider a typical task life cycle without being interrupted (cold started task): (1) code is loaded from hard drive and data is loaded from main memory; (2) computation is done by processor(s); (3) results are committed to main memory. In the P-FRP model, the time spent in phase (2) and (3) is wasted when a task is aborted, however, since the existence of memory hierarchy, the time spent in phase (1) can be less when a task is restarted, for example, the task code is still in cache and does not need to be read from slow main memory again. This memory effect is not considered in previous studies of P-FRP systems. In this paper, we present our preliminary memory-aware P-FRP task response time analysis and experimental results. Our ongoing research is to present more theoretical response time analysis and priority assignment research in the memory-aware P-FRP task scheduling. And since the execution time difference is likely related to data placement/locality, we will address this difference in our multi-core P-FRP task scheduling research too.

This paper studies the schedulability of real-time tasks in the Priority-based Functional Reactive Programming (P-FRP) model under fixed priority scheduling, one of the influential scheduling policies. Since the abort-and-restart execution paradigm of the P-FRP model is different from that of the classic pre-emptive model, the schedulability analysis for P-FRP tasks under fixed priority scheduling differs widely. In P-FRP, for a synchronous n-task set under fixed priority scheduling, the least common multiple (LCM) of all n task periods is the typical length of a testing interval for an exact (necessary and sufficient) schedulability test. In this paper, we propose and prove an optimal simulation based exact schedulability test in the P-FRP model under fixed priority scheduling for a given priority order, covering scenarios from synchronous task release to asynchronous task release with the initial busy condition, and from implicit deadlines to constrained deadlines. The length of a testing interval for the exact test is the LCM of the first n-1 task periods and its optimality is proved.

In real-time systems, FRP (Functional Reactive Programming) is playing and potentially going to play a more important role. Priority-based (preemptive) FRP (P-FRP), a variant of FRP with more real-time characteristics, demands more research in its scheduling and timing analysis. Its abort-andrestart nature indicates that reducing preemptions can be critical for improving system performance. In this paper, we present a non-work conserving scheduling model, Deferred Start, to reduce certain preemptions. Experiments show the improvement on schedulability and task response time.