کمترین اولویت اول بر اساس تجزیه و تحلیل امکان سنجی از سیستم های زمان واقعی

The feasibility problem of periodic tasks under fixed priority systems has always been a critical research issue in real-time systems and a number of feasibility tests have been proposed to guarantee the timing requirements of real-time systems. These tests can be broadly classified into: (a) inexact and (b) exact tests. The inexact tests are applied to the task sets that present lower utilization, while the exact tests become inevitable when system utilization is high. The exact tests can be further classified into: (a) Scheduling Points Tests (SPT) and (b) Response Time Tests (RTT). The SPT analyze task set feasibility at the arrival times while the RTT utilize fixed-point techniques to determine task feasibility. All of the available exact feasibility tests, whichever class it belongs to, share pseudo-polynomial complexity. Therefore, the aforementioned tests become impractical for online systems. Currently, both SPT and RTT employ the Highest Priority First (HPF) approach, which determines the system feasibility by testing the schedulability of individual tasks in the decreasing order of priority. In contrast, this work exploits the Lowest Priority First (LPF) alternative which is an aggressive solution based on the observation that the system infeasibility is primarily due to the lower priority tasks and not because of the higher priority tasks. For the average case analysis, our technique demonstrates promising results. Moreover, in the worst case scenario our solution is no inferior to the existing state of the art alternatives. We compare our proposed technique with the existing tests: (a) by counting the number of scheduling points used by a test that belongs to the SPT, (b) by counting the number of inner-most loops executed by an algorithm for the RTT, and (c) by measuring the actual running time of the existing alternatives.

A real-time system (RTS) is a system where the timing constraints are vital to performing the assigned tasks [34], [23] and [22]. The two main classes of real-time systems are (a) hard and (b) soft real-time systems. Meeting deadlines is absolutely necessary for hard real-time systems. Embedded systems are often hard real-time systems. However, in soft real-time systems there is some room for lateness and a delayed process may not cause an entire system failure. Instead, it may affect the quality of the process or system. Typically, real-time systems are built from concurrent programs, called tasks [18]. There exist a number of task models for real-time systems [14], but in a simple periodic model of hard real-time systems, a task τiτi is represented by the following parameters: • A task period pipi, which is the interval between two instances (or jobs) of τiτi. • A worst case execution time cici. • Relative deadline didi, which is measured from the release time. Let Γ={τ1,…,τn}Γ={τ1,…,τn} denote a set of independent, preemptable periodic tasks, where each task τiτi generates an instance (or a job) at each multiple of pipi. While in operation, all of the tasks immediately get ready for execution on a single processor system as soon as they are released. Moreover, the deadlines are equal to or less than the periods and we assume that there are nn number of priority levels available. Therefore, every task has an associated priority. A rational approach of designing a periodic task set is that for each task τiτi, the expression ci≤pici≤pi, must always hold. This is due to the fact that the utilization of more than 100% is impractical under a uniprocessor system for any task model. The set ΓΓ is scheduled on a uniprocessor system according to a predetermined scheduling algorithm. Among the existing scheduling mechanisms, priority driven scheduling is the choice for real-time systems [11], [21], [22], [7], [31], [15], [14], [17], [20], [3], [4], [30] and [16] which run the task with the highest priority at all scheduling points. The priority driven scheduling is further categorized into: (a) static priority assignment and (b) dynamic priority assignment. From the utilization perspective, the dynamic priority assignment has advantage over static priority counterpart. However, the static priority assignment outclass the dynamic priority policy when it comes to system predictability. Among the (previously known) scheduling algorithms, the fixed priority scheduling is considered to be the choice of the modern real-time systems because of its simplicity and applicability [5] and [6] and hence the focus of this paper. The most popular scheduling algorithm under the category of the fixed priority scheduling is the Rate Monotonic (RM) algorithm [23]. The RM scheduling algorithm assigns fixed priorities to all of the tasks on their activation rates (periods). The RM scheduling algorithm is being used widely in real-world systems due to its simplicity and reliability [6] and [13]. According to RM priority assignment policy, for any two tasks τiτi and τjτj, priorities are assigned to tasks in a simple fashion, View the MathML sourcepriority(τi)>priority(τj)⇒pi<pj. If there occur ties, then the ties are broken arbitrarily but in a consistent manner. For each task τiτi, its system utilization is defined by: ui=ci/piui=ci/pi. The cumulative utilization U(n)U(n) of a periodic task system ΓΓ is defined by: equation(1) View the MathML sourceU(n)=∑i=1ncipi. Turn MathJax on The RM approach is optimal for the implicit-deadline model, in which the deadlines coincide with their respective periods. However, for the constrained deadline systems, in which the deadlines are not greater than the periods, an optimal priority ordering has been shown to be that of the Deadline Monotonic (DM) scheduling [21]. In the DM scheduling approach, priorities are assigned to tasks which are inversely proportional to the relative deadlines. The RM and DM approaches exhibit identical properties when the relative deadline of every task is proportional to its corresponding period. Although both the RM and DM techniques can be used (interchangeably) for our constrained-deadline (where every task has its deadline not larger than its period), to align with previous literature, we use RM in this work. To determine if a given set of periodic tasks meet all of their deadlines, is considered a special case of the validation problem: We are given • a periodic task set (ΓΓ), • a constrained deadline task model, and • an RM scheduling algorithm. We must utilize the aforementioned items to determine if all of the deadlines didi of every task View the MathML sourceτi∀i,1≤i≤n will be met on an underlying uniprocessor system. To determine whether a feasible schedule exists for ΓΓ, schedulability tests are performed that fall into three main classes [1] and [9]: (a) Sufficient Condition: the ΓΓ is definitely schedulable if the schedulability test belongs to this class is satisfied and it is indecisive when the schedulability test fails, (b) Necessary Condition: if the schedulability test is passed then we do not know whether ΓΓ is schedulable or not, however the task set is definitely unschedulable if the test fails, (c) Exact Conditions: are both sufficient and necessary at the same time. In rest of the paper, we use schedulability test and feasibility analysis interchangeably. The feasibility analysis can be performed either offline or online [22]. For offline systems, the computational complexity is not deemed to be a major issue. Therefore, the corresponding algorithms are evaluated from the perspective of the quality of the feasibility tests. Conversely, in online systems, task scheduling is determined on arrival, which means that the corresponding feasibility tests must be performed at run time. Therefore, the online tests must be fast — an online algorithm that takes so long that it leaves insufficient time for the tasks to meet their deadlines is deemed useless [17], [33], [29], [19], [26], [28] and [10]. The feasibility of ΓΓ, which has a low system utilization can be determined with the sufficient conditions that are available in the real-time system literature, such as U(n)≤ln(2)U(n)≤ln(2) [22] and/or View the MathML source∏i=1n(ui+1)≤2 [15]. However, the feasibility of ΓΓ having a higher system utilization must be determined by utilizing both the necessary and sufficient conditions. This being the focus of this paper. The necessary and sufficient conditions determine the RM schedulability of a task on the basis of a task’s worst case response time. Two approaches, namely: (a) scheduling point and (b) fixed-point techniques, are used to determine a task’s maximum possible response time. However, both of the aforementioned techniques are known to be computationally expensive and are deemed impractical to be used for online analysis. Although the order in which the system feasibility is evaluated does not matter [30], these necessary and sufficient conditions [5], [6], [23], [11], [21], [14], [20], [3], [4], [30], [16], [8], [25], [32], [33], [29] and [28] traditionally use the Highest Priority First (HPF) approach. It is worth mentioning that the main attraction for testing system feasibility with HPF is to check if the system is feasible and concluding this takes a considerably longer time [22], [19] and [26]. The aforementioned is attributed to the fact that higher priority tasks are always schedulable and finding the infeasible task (normally lower priority task) means evaluating the feasibility of all higher priority tasks before that infeasible task. Guarantee scheduling of higher priority task is due to the implicit characteristics of RM scheduling algorithm because CPU is assigned to higher priority task when the overloading situations occurs. In contrast, the Lowest Priority First (LPF) counterpart evaluate system from infeasibility perspective and hence system feasibility is determined in reverse order i.e., starting with lowest priority. The advantage of LPF over HPF approach is implicitly highlighted in [12] and [2] where schedulability of the system is addressed through Response Time Tests (RTT) class and results are established to obtain higher initial values for the tasks. However, as per existing literature, no study has been made so far on the feasibility tests belonging to scheduling point class. In this paper, we investigate the feasibility problem by presenting LPF based feasibility test and compare results with both RTT and Scheduling Points Tests (SPT) classes. Moreover, we provide the necessary foundation for the LPF strategy and make explicit analysis of LPF with HPF counterpart. We also must note that the HPF approach is a well respected and widely used technique for real-time systems and other computing systems where the focus is on determining the system feasibility [24], [9] and [22]. Our prior work in [26] explored the concept of composite deadlines for obtaining higher systems utilization by making tasks deadlines in a harmonic fashion. Using the HPF approach, the work presented in [26] guarantees 100% CPU utilization for larger deadlines under dynamic priority scheduling. In [29], we revisited the fixed priority scheduling domain and performed a comparative analysis of feasibility tests. Similarly, a procedure was developed in [28] for obtaining the optimal values for task computation times so that any given performance index such as system utilization or mission life is maximized. By task shifting approach, we identified a suitable systems speed in [27] that enables all the cores to run on a uniform speed and hence reduces the power consumption of the overall system. All of the aforementioned works done are based on the HPF policy. However, when the (real-time or computing) system is viewed from infeasibility perspective, the HPF technique reveals poor performance. This observation suggests to tackle the RM-feasibility problem of unschedulable task sets with the LPF approach that works in an aggressive manner. This LPF approach is under investigation in this paper. The supremacy of LPF over HPF is discussed in detail through both qualitative and quantitative analysis. It can be observed from Table 1 that when the system utilization is below 69%, the inexact tests are applicable and the whole task set is RM feasible (on uniprocessor systems). On one hand, this predictability is obtained on the price of system utilization. That is to say that 31% system utilization is compromised and hence the system remains underutilized. On the other hand, when the system utilization is higher, only the exact tests can determine the system feasibility and in such cases the systems are generally infeasible as shown in Table 1. Based on the aforementioned observations, in this research, we analyze the task set from the point of view of system infeasibility. Moreover, we also illustrate that the LPF [12] and [2] approach is more suitable for the aforementioned task model, as it needs to determine the system infeasibility by probing fewer number of tasks compared to the HPF approach. The effectiveness of the LPF approach is measured by recording the number of points where a task’s schedulability is tested for the SPTs and the number of the inner-most loops for RTTs, in addition to measuring the actual run times of RTA, RTI and HET. Table 1 summarizes the CPU utilizations and the corresponding usability. The table also reports that the real-time systems depicting high system utilization are more susceptible to deadline misses. Therefore, the authors conclude that such systems would be more appropriate for our study of investigating real-time (or computing) systems from the perspective of system infeasibility.In this work, the authors propose the following two mechanisms to decide the RM feasibility/infeasibility of a task set: (a) Faster Feasibility Test: We observed that if there is a common scheduling point for all of the tasks in the systems and if the lowest priority task is RM feasible at that point, then the entire task set is feasible. This is due to the fact that the value of workloads are non-decreasing, as the RM feasibility of tasks in decreasing priority order are considered. Therefore, testing the feasibility of the lowest priority task at a common scheduling point for all of the tasks result in a faster feasibility test. (b) Faster Infeasibility Test: A task set is RM infeasible when at least one task is RM infeasible. A lower priority task is more vulnerable to a deadline miss than that of a higher priority task because a lower priority task suffers from interference from all the higher priority tasks. Therefore, the Lowest Priority First (LPF) approach to test the RM infeasibility results in faster decisions. The remainder of this article is organized as follows: a motivational example is described in Section 2 and then in Section 3, we provide the necessary definitions and some background information about the topic. The related work is discussed in Section 4 that encapsulates both SPT and RTT in detail. This is followed by the details of the proposed analysis scheme in Section 5, which is based on the observation that lower priority tasks are more vulnerable to deadline misses than the higher priority tasks. Experiments have been performed and the results are shown for the performance assessment in Section 6, followed by worst/best case analysis for the proposed scheme. Finally, we conclude the work in Section 7.

In this work, we explored a new dimension for the feasibility analysis of hard real-time systems under fixed priority scheduling. The proposed method was based on the observation that the lower priority tasks were more susceptible to deadline violations. The lowest priority first approach was tailored for scheduling points as well as the response time based tests. The experimental results showed that our proposed technique outperforms existing alternatives in terms of three criteria: the number of scheduling points tested, the calls to the inner-most loops, and the actual analysis time. It was observed that under higher system utilization when the intuition is that the task set has at least one unschedulable task, LPF offers better results as compared to tests based on SPT and RTT solutions. The performance of LPF becomes more dominant when applied to a real-time system with higher system utilization.