WIXLIB

LEE AND SHIN: IMPROVEMENT OF REAL-TIME MULTI-CORE SCHEDULABILITY WITH FORCED NON-PREEMPTIONTABLE 1Notationsthere is an unfinished ready job. For convenience, we willhenceforth use the term “scheduling algorithm” to mean“global work-conserving scheduling algorithm.” We alsoassume that a job cannot be executed in parallel.We will use the terms carry-in, body, and carry-out jobs ina time interval of interest, defined as follows. Then, we scrutinize an existing schedulability analysis technique for fully-preemptive scheduling algorithms in[4], which will be a basis for our schedulability analysis(Section 4) of the scheduling algorithms that employ theMPN preemption policy.2.1 System Model, Assumptions and NotationsHere we focus on a sporadic task model [9] in which atask t i 2 F is represented as ðTi ; Ci ; Di Þ, where Ti is theminimum separation between two successive invocations,Ci the worst-case execution time, and Di the relativedeadline of t i . Our discussion is confined to implicit(Ci Di ¼ Ti ) and constrained (Ci Di Ti ) deadlinetask sets.3 A task t i invokes a series of jobs, each separated from its predecessor/successor by at least Ti timeunits. Without loss of generality, we assume a quantumbased time and let the length of a quantum be one timeunit. All task parameters are specified in multiples of thequantum or time unit.For each t i 2 T , we introduce a new additional parameter Yi , indicating whether t i is preemptive (Yi ¼ 1) or non-preemptive (Yi ¼ 0). That is, if Yi ¼ 1 (Yi ¼ 0), jobs of t i can(cannot) be preempted by any other higher-priority job atany time.In this paper, we deal with two existing prioritizationpolicies: EDF (earliest deadline first) scheduling that gives ahigher priority to a job with an earlier deadline, and FP(fixed priority) scheduling in which the priority of a job isdetermined by the priority of the task that invokes the job.To express task-level fixed-priorities for FP, let HPðt k Þ andLPðt k Þ denote a set of tasks in F whose task-priority ishigher and lower than t k , respectively. Table 1 summarizesthe notations used throughout this paper.The system is assumed to have been built with multi-corechips, each of which consists of m identical cores. We alsofocus on global work-conserving algorithms, i.e., a job canbe executed on any core, and a core cannot be left idle if3. While the scheduling algorithms to be discussed in this paper canhandle arbitrary deadline task sets (no restriction between Di and Ti ),the schedulability analyses can deal with implicit and constrained deadline task sets only.1235A carry-in job is released before the interval, but itsdeadline is within the interval;A body job has its release time and deadline withinthe interval; andA carry-out job is released within the interval, but itsdeadline is after the interval.2.2 An Existing Schedulability Analysis forFully-Preemptive Scheduling AlgorithmsAs the basis for a schedulability analysis of algorithmsthat employ the MPN policy, we choose a response-timebased schedulability analysis technique for fully-preemptive scheduling algorithms [4] due to its applicability tovarious prioritization policies (e.g., fp-EDF, fp-FP andpotentially more) and schedulability performance (e.g.,the authors of [10] showed the test of fp-EDF [4] to beone of the best with respect to average schedulability). Inthe supplement, which can be found on the ComputerSociety Digital Library at 13.2297098, we summarize the existing schedulability analysis in [4].3MPN POLICY AND MPN- ALGORITHMSIn this section, we first define the MPN preemption policy,in which each task can be either (artificially) preemptiveor non-preemptive. Then, we give a formal description ofmpn- algorithms, in which MPN is employed with a prioritization policy of (e.g., EDF, FP); we present mpnEDF and mpn-FP as typical examples. Finally, we presentthe generalization property of the MPN policy and mpn- algorithms.We consider a preemption policy under which preemption decisions are made based on a task parameter Yi of t i .That is, if Yi ¼ 1 (Yi ¼ 0), a job of t i can (cannot) be preempted by any other higher-priority job during its execution. We call this the mixed preemptive/non-preemptive (MPN)policy.Let mpn- denote a scheduling algorithm that adoptsMPN and as its preemption and prioritization policies,respectively. Algorithm 1 provides a formal description ofan mpn- scheduling algorithm on a multi-core platform.Since there may be some non-preemptive tasks undermpn- , Job Release Steps 4 and 5 exempt currently-executing non-preemptive jobs from being preempted by anewly-released job, which is a main difference betweenfp- (algorithms with the fully-preemptive policy) andmpn- . The implementation overhead of mpn- is not significant in that most steps in Algorithm 1 are alsorequired by the corresponding fully-preemptive algorithm fp- . That is, mpn- additionally requires to checkthe condition of Yk ¼ 1 in Step 4 and the second “if” condition in Step 5, and to store one additional bit per taskfor Yk . On the other hand, while all tasks under fp- canbe preempted, only some tasks under mpn- can, thus

1236IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,incurring less preemptions and migrations, which is anadvantage of mpn- .VOL. 25,NO. 5, MAY 2014preemption policy, and derive some properties that arecommonly applied to any prioritization policy with theMPN policy. Then, we apply the analysis framework to twospecific mpn- algorithms, yielding schedulability analysesof mpn-EDF and mpn-FP.4.1 Schedulability Analysis Framework for mpn- AlgorithmsIn Section 2.2, schedulability analyses of fp-EDF and fp-FPhave been developed by addressing the following framework/upper-bound.F1. A response time analysis framework for a preemptivetask (i.e., Lemma 9); andU1. An upper-bound of Ik i ðlÞ if both t k and t i are preemptive (i.e., Wi ðlÞ and Ek i in Eqs. (14) and (16)).However, under any scheduling algorithm that employsthe MPN preemption policy for a mixture of preemptiveand non-preemptive tasks, we need to address the following framework/upper-bounds in addition to F1 and U1.We now show two representative examples of mpn- algorithms. When we employ EDF as a prioritization policy, mpn-EDF determines the priority of jobs according totheir deadlines. Therefore, the job deadline is used forcomparison of job priorities in Job Release Steps 4 and 5and Job Completion Step 1 of Algorithm 1. On the otherhand, mpn-FP determines job priorities based on fixedtask priorities, and therefore, the task priority is used forthe job priority comparison. Note that the description ofAlgorithm 1, for now, targets prioritization policies inwhich each job’s priority does not change over time, e.g.,EDF, FP, EQDF (earliest quasi-deadline first) [11] andSPDF (smallest pseudo-deadline first) [12]; however, wecan easily extend the algorithm for job-level dynamic prioritization policies, e.g., LLF (least laxity first) [13], inwhich a job’s priority depends on its remaining time todeadline and remaining execution time, and thus, the priority varies with time.Then, the MPN policy and mpn- are generalizationsof non-preemptive and preemptive policies, and np- andfp- , respectively, as stated in the following lemma.Lemma 1. The MPN policy subsumes non-preemptive and preemptive policies, while the mpn-EDF and mpn-FP scheduling algorithms subsume np-EDF and fp-EDF, and np-FPand fp-FP, respectively.Proof. The proof is straightforward. The non-preemptive(preemptive) policy is equivalent to the MPN policy withYi ¼ 0 (Yi ¼ 1) for all t i 2 F, and np-EDF (fp-EDF) isequivalent to mpn-EDF with Yi ¼ 0 (Yi ¼ 1) for all t i 2 F.The same holds for mpn-FP over np-FP and fp-FP.ut4SCHEDULABILITY ANALYSIS OFMPN- ALGORITHMSIn this section, we first develop a schedulability analysisframework for scheduling algorithms that employ the MPNF2. A response time analysis framework for a non-preemptive task;U2. An upper-bound of Ik i ðlÞ if t k is non-preemptivebut t i is preemptive;U3. An upper-bound of Ik i ðlÞ if both t k and t i are nonpreemptive; andU4. An upper-bound of Ik i ðlÞ if t k is preemptive but t iis non-preemptive.In this section, we will develop F2, and derive someproperties for U2, U3 and U4, which are commonly appliedto any scheduling algorithm with the MPN policy. Toaddress F2, we first introduce a non-preemptive task’sproperty. By definition, any job of a non-preemptive taskcannot be interrupted by any other job, and thus, the following property holds.Observation 1. Once a job of a non-preemptive task startsits first time unit of execution, the execution should notbe interrupted by any other job. Therefore, if a job of t kfinishes its first time unit of execution at t, it finishes itsentire execution no later than t þ Ck 1.Based on the above observation, we can derive anupper-bound of the response time of a given non-preemptive task by calculating when the first time unit ofexecution of any job of the task is finished. Then, the following lemma provides a condition for an upper-boundof the response time.Lemma 2. The response time of a non-preemptive task t k isupper-bounded by l þ Ck 1 if the following inequality holds: 1 X(1)1þmin Ik i ðlÞ; l l:m t 2F ft gikProof. We prove the lemma by contradiction. Suppose thatEq. (1) holds for a given l, but the response time of t k isstrictly greater than l þ Ck 1.In this case, there exists t such that Ik ðt; t þ lÞ l; otherwise, at least one unit of execution of any job of t k isperformed within ½t; t þ lÞ, and then the response time is

LEE AND SHIN: IMPROVEMENT OF REAL-TIME MULTI-CORE SCHEDULABILITY WITH FORCED NON-PREEMPTION1237upper-bounded by l þ Ck 1. By Lemma 8 and the definition of Ik i ðlÞ, the following inequality holds:Ik ðt; t þ lÞ lXminðIk,t i 2F ft k g¼)Xti 2F ft k gi ðt; t min Ik þ lÞ; lÞ m l i ðlÞ; l m l:(2)Applying the final result of Eqs. (2) to (1), we show thecontradiction, i.e., 1 þ l l.utThen, we can develop F2 using Lemma 2, and by merging F1 and F2, we develop a schedulability analysis framework for any global work-conserving scheduling algorithmthat employs the MPN policy, as stated in the followingtheorem.Theorem 1. When a task set F is scheduled by an mpn- scheduling algorithm, an upper-bound of the response time of a pre Rxkemptive task t k jYk ¼ 1 2 F is Rk ¼ Rxk such that Rxþ1kholds in the following expression, starting from R0k ¼ Ck : x x 1 XR;RRxþ1CþminI Cþ1;kkkkikkm t 2F ft gik(3)and an upper-bound of the response time of a non-preemptivetask t k jYk ¼ 0 2 F is Rk ¼ Fkx þ Ck 1 such that Fkxþ1 Fkx holds in the following expression, starting from Fk0 ¼ 1: 1 XFkxþ11þmin Ik i Fkx Þ; Fkx : (4)m t 2F ft gikThen, if Rk Dk holds for all t k 2 F, F is schedulable bythe algorithm.Note that the iteration of Eq. (4) (Eq. (3)) for a non-preemptive (preemptive) task t k halts if Fkx þ Ck 1 Dk (Rxk Dk ), meaning that t k is deemed unschedulable.Proof. By Lemma 9, Rk derived by Eq. (3) is an upper-boundof the response time of a preemptive task t k . Also, byLemma 2, the response time of a non-preemptive task t kis guaranteed to be upper-bounded by Rk ¼ Fkx þ Ck 1if Fkxþ1 Fkx . Thus, if Rk Dk holds for all t k 2 F, F isschedulable.utUsing Theorem 1, we can find whether or not a task set isschedulable under a specific mpn- scheduling algorithm,as long as the upper-bounds of Ik i ðlÞ of U1–U4 under thealgorithm can be derived. While the upper-bounds dependon the underlying scheduling algorithms, here we studysome interesting properties of the upper-bounds, which areapplicable to any mpn- scheduling algorithm. Then, theseproperties will be the key in calculating Ik i ðlÞ under specific mpn- algorithms, e.g., mpn-EDF and mpn-FP inSections 4.2 and 4.3.For U1–U4 under any mpn- scheduling algorithm, ahigher-priority job can interfere with a lower-priority job.However, it depends on the preemptiveness of lower- andhigher-priority jobs, whether a lower-priority job can interfere with a higher-priority job.Fig. 1. A case where a lower-priority job of a non-preemptive task ti caninterfere with a high-priority job of a preemptive tk when the highest-priority job of t j is released.Now, we identify some properties regarding interference, starting from the cases of U1 and U2.Observation 2 (The Cases of U1 and U2). Suppose that a jobJA is preemptive. Then JA can interfere with another jobJB only when the priority of JA is higher than that of JB .Since a preemptive lower-priority job can be blocked atany time by a higher-priority job, Observation 2 holds.However, a non-preemptive lower-priority job may interfere with a higher-priority via its non-preemptive behavior.The following observation deals with the case of U3.Observation 3 (The Case of U3). Suppose that both jobs JAand JB are non-preemptive. Then, JA can interfere withJB even if the priority of JA is lower than that of JB . Thisoccurs only when the execution of JA starts before therelease of JB . Therefore, there are at most m lower-priority non-preemptive jobs that can interfere with a higherpriority non-preemptive job.Suppose that a non-preemptive lower-priority job JAstarts its execution before tB , at which a non-preemptivehigher-priority job JB is released. Then, regardless of priorities of JA and JB , JA does not pause its execution due tonon-preemptiveness, and therefore, JA can interfere withJB . However, since JB is non-preemptive, such priorityinversion cannot occur if JA does not start its executionbefore tB ; in this case, JA cannot start its execution beforeJB ’s execution starts, and once JB starts its execution, it alsodoes not stop its execution. Therefore, the only case for JAto interfere with JB is that JA executes in ½tB 1; tB Þ andthen continues the execution after tB due to its non-preemptiveness. Since the number of jobs executed in any giventime slot is upper-bounded by m, the number of lower-priority non-preemptive jobs that interfere with a givenhigher-priority non-preemptive job is upper-bounded by m.One may think that Observation 3 holds for the casewhere JA is non-preemptive and JB is preemptive, i.e., thecase of U4. However, this is not true because priority inversion occurs more often for this case. Consider an interval½t; t þ Dk Þ where t is the release time of a job of a preemptivetask t k . Also, a job of a non-preemptive task t i is releasedafter t and has a lower priority than the job of t k . In thiscase, the job of t i can interfere with that of t k in ½t; t þ Dk Þ,although the job of t i does not start its execution before t.Fig. 1 represents the case with m ¼ 2 and three tasks t i ; t jand t k . In ½t0 ; t0 þ 1Þ, both jobs of a non-preemptive task t iand a preemptive task t k execute. When the highest-priorityjob of t j is released at t0 þ 1, the job of t k has to pause its execution due to the highest-priority job of t j , but the job of t i

1238IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,does not pause due to its non-preemptiveness. In this casethe job of t i interferes with the job of t k after t0 þ 1 regardless of its priority, and this can happen for any job of t i .We summarize the above observation as follows.VOL. 25,NO. 5, MAY 2014TABLE 2Upper-Bounds of Ik i ðlÞ under mpn-EDFObservation 4 (The Case of U4). Suppose that a job JA isnon-preemptive, and another job JB is preemptive. Then,JA can interfere with JB even if the priority of JA is lowerthan that of JB . This may occur regardless of the releasetime of JA .Note that the case in Fig. 1 cannot occur when both t k andt i are non-preemptive (i.e., the case of U3). This is becausethe job of t k in the figure cannot be preempted once it startsexecution (since the job of t k is non-preemptive). Therefore,the job of t k cannot be preempted at t0 þ 1, meaning that a jobof t i released at t0 cannot interfere with the job of t k .While the schedulability analysis framework in Theorem1, and Observations 2, 3 and 4 can be applied to any mpn- algorithm with existing prioritization policies (e.g., EDF, FP,EQDF, and SPDF), we will present schedulability analysesof mpn-EDF and mpn-FP as examples, in the followingsections.4.2 Schedulability Analysis of mpn-EDFIn this section, we develop the schedulability analysis ofmpn-EDF by calculating upper-bounds of Ik i ðlÞ undermpn-EDF, based on the observations in Section 4.1 andproperties of the prioritization policy of EDF.As presented in the supplement, available online, Ek iin Eq. (16) is the maximum amount of execution of higherpriority jobs of a task t i than a job of another task t k in aninterval between the release and the deadline of the t k ’s jobunder EDF. Therefore, Ek i can be used for an upperbound of U1–U4 when only higher-priority jobs of t i caninterfere with a lower-priority job of t k .By Observation 2, a lower-priority job of a preemptivetask t i cannot interfere with a higher-priority job of a task t kfor the cases of U1 and U2; the remaining step is to calculateU3 and U4 when at least one lower-priority job of t i interfere with the job of t k . As stated in Observation 3, a lowerpriority job of a non-preemptive task t i can interfere with ahigher-priority job of a non-preemptive task t k only if thejob of t i starts its execution before the release of the job oft k . Therefore, Ik i ðlÞ is upper-bounded by Ci 1 in thiscase, and there are at most m jobs of such t i . Under the prioritization policy of EDF, Di Dk is a necessary conditionfor a job of t i to start its execution before a job of t k ’s releaseand to have a lower priority than the job of t k .When it comes to U4, Observation 4 represents that anyjob of a non-preemptive task t i can interfere with a job of apreemptive task t k . Therefore, we use Wi ðlÞ in Eq. (14) (anupper-bound applicable to all cases) as an upper-bound ofIk i ðlÞ.We summarize upper-bounds of Ik i ðlÞ under mpnEDF for different cases in Table 2.Considering the fact that Wi ðlÞ in Eq. (14) is an upperbound for all cases, Ik i ðlÞ

nique for fully-preemptive scheduling algorithms in [4], which will be a basis for our schedulability analysis (Section 4) of the scheduling algorithms that employ the MPN preemption policy. 2.1 System Model, Assumptions and Notations Here we focus on a sporadic task model [9] in which a task t i 2F is represented as ðT i;C i;D iÞ,whereT i is the