Non-migratory Online Deadline Scheduling on Multiprocessors Ho-Leung Chan Abstract In this paper we consider multiprocessor scheduling with hard deadlines and investigate the cost of eliminating migration in the online setting. Let I be any set of jobs that can be completed by some migratory offline schedule on m pro cessors. We show that I can also be completed by a non-migratory online schedule using m speed-5.828 pro cessors (i.e., pro cessors of 5.828 times faster). This result supplements the previous results that I can also be completed by a non-migratory offline schedule using 6m unit-speed pro cessors [8] or a migratory online schedule using m speed-2 pro cessors [13]. Our result is based on a simple conservative scheduling algorithm called PARK which commits a pro cessor to a job only when the pro cessor has zero commitment before its deadline. A careful analysis of PARK further shows that the pro cessor speed can be reduced arbitrarily close to 1 by exploiting more pro cessors (say, using 16m speed-1.8 pro cessors). PARK also finds application in overloaded systems; it gives the first online nonmigratory algorithm that can exploit moderately faster processors to match the performance of any migratory offline algorithm. 1 Intro duction Tak-Wah Lam Kar-Keung To In this paper we consider the online hard-deadline scheduling problem on multiprocessors; our focus is on eliminating migration among the pro cessors. The hard-deadline scheduling problem is defined as follows: There are m identical pro cessors. Given a set of jobs, each characterized by its release time, deadline, and processing time (work), the ob jective is to schedule all the jobs on the pro cessors so that each job can be completed by its deadline. Note that each job can be scheduled on at most one pro cessor at any time. Preemption is allowed and a preempted job can resume later from the point of preemption. If migration is allowed, a job can resume on a different pro cessor. From a practical point of view, non-migratory schedules Department of Computer Science, University of Hong Kong. Email: {hlchan, twlam, kkto}@cs.hku.hk. Supp orted in part by Hong Kong RGC Grant HKU-7024/01E. are preferable since migration may incur significant overhead. Yet allowing migration simplifies the design of scheduling algorithms. Let I be a set of jobs that can be completed by an offline schedule that allows migration. Kalyanasundaram and Pruhs [8] showed that migration is actually of limited power in offline scheduling; given a migratory offline schedule on m pro cessors, it is always possible to construct a non-migratory offline schedule on 6m - 5 pro cessors.1 On the other hand, scheduling I online (i.e., the information about a job is known only when it is released) is very difficult even if migration is allowed. In fact, I does not admit any online schedule on m pro cessors if m 2 [5].2 Nevertheless, Phillips et al. showed that I can be completed by a migratory online schedule on m pro cessors that are two times faster [13]. Migration seems to be a necessary tool in all online algorithms that are known to be able to complete I on m moderately faster pro cessors (e.g., earliest deadline first, least laxity first, FR [13, 11]). Main result: In this paper we devise a conservative online algorithm to show that I can be completed by a non-migratory online schedule on m speed-5.828 processors. This result supplements the result of Kalyanasundaram and Pruhs [8] as it illustrates that allowing migration in the online setting also gives limited power. A careful analysis of the new algorithm further shows that the speed requirement of 5.828 can also be reduced arbitrarily close to 1 by exploiting more pro cessors (say, using 16m speed-1.8 pro cessors). More precisely, we show that for any > 0, I can be compm ted by a nonle ( speed-(1+)2 migratory online schedule on 1 + 1 )2 pro cessors. Laxity assumption: It is widely believed that jobs with very tight deadlines or very small laxity (i.e., deadline minus release time minus work) make online scheduling difficult. Our non-migratory online scheduling is no exception; in this paper we show 1 The construction runs in pseudo-p olynomial time, but can be improved to run in polynomial time if the processor bound is raised from 6m - 5 to 12m - 5. 2 When m = 1, the earliest deadline first (EDF) strategy guarantees to complete I [4]. Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 970 that advance knowledge of the laxity of jobs in I can reduce the speed or processor requirement for a non-migratory online schedule. For example, if the work requested for every job in I is at most one eighth of its span (i.e., deadline minus release time), then we can have a non-migratory online schedule for I on m speed-2.5 processors or on 4m unit-speed processors. Note that the latter result does not demand the presence of faster processors. In general, if the work-span ratio is at most w, then I can be completed by a non-migratory online schedule on m speed-(4w + 2) processors or 2/(1 - 4w) m unit-speed processors. (The latter result holds only for w < 1/4.) PARK: The core of our results is a simple conservative online scheduling algorithm called PARK; it does not commit a processor to any job unless the processor has zero commitment before its deadline. This algorithm often lets a job wait for a while before admitting it to a processor. The conservative nature of PARK avoids over crowding any processor and being tricked by the offline adversary. Like many other online algorithms, PARK is very simple but the analysis of its performance is relatively complicated. In this paper we present two different analyses of PARK, showing different dimensions of its performance. Firm-deadline scheduling: PARK also finds applications in scheduling overloaded systems, in which there may be too many jobs to be completed and the deadlines are firm (instead of hard) in the sense that failing to complete a job by its deadline only loses the value due to that job and does not cause a system failure. Given a set I of such jobs, the ob jective of a scheduler is to maximize the value obtained from completing the jobs. For any c 1, an online algorithm is said to be c-competitive if for any job sequence, it can obtain at least a fraction of 1/c of the total value obtained by any offline schedule on m speed-1 processors. Consider the special case when the value of a job is proportional to its processing time. The work of Koren and Shasha [10] gave a non-migratory online algorithm on m speed-1 processors that is 3-competitive. If migration is allowed, Lam and To [12] showed that it is possible to devise an online algorithm on m speed-3 processors that is 1competitive. Based on the latter result, we can actually extend PARK to give a non-migratory online algorithm on m speed-10 processors that is 1-competitive. In the context of offline scheduling, the study of the power of migration is centered on the notion m , which is defined as the maximum over all input I , the ratio of the value attained by the optimal migratory offline schedule for I to the value attained by the optimal non-migratory offline schedule for I [9, 8]. For jobs with arbitrary values, the best upper bound of m is (6m - 5)/m [8]. This paper contributes to the knowledge of m when jobs are assumed to have a certain laxity. More precisely, our work implies that 2) m min(6, 1-4w if the work-span ratio is at most w < 1/4. Organization of the paper: Section 2 presents the new online algorithm PARK and discusses several interesting properties of PARK. Section 3 gives the first analysis of PARK, showing how to obtain a nonmigratory online schedule on m speed-5.828 processors. As a by-product, we show how to improve the resource bounds when all jobs are assumed to have a certain laxity. Section 4 gives a slightly more complicated analysis of PARK, showing that the speed requirement of 5.828 can be reduced arbitrarily close to one when extra processors are used. Section 5 shows a simple lower bound result that non-migratory schedule is not feasible on m speed-s processor if s < 2m/(m + 1). Also, the extension of PARK to firm-deadline scheduling is discussed. Notation: Throughout this paper, we denote the release time, work (processing time), and deadline of a job J as r(J ), p(J ), and d(J ), respectively. We also assume that jobs have distinct deadlines (ties are broken using the job IDs). The laxity and span of J is defined as d(J ) - r(J ) - p(J ) and d(J ) - p(J ), respectively. For any s 1, a speed-s processor refers to a processor that can process s units of work in one unit of time. EDF refers to the strategy of scheduling jobs with earliest deadlines. Note that when a new job J is released, the current job J on a processor will be preempted if J has a deadline later than J 's as well as the deadlines of the current jobs on all other processors. When we say an algorithm completes a job sequence, we mean that the algorithm completes all jobs in the sequence within their respective deadlines. 2 The PARK algorithm In this section, we describe a non-migratory online algorithm called PARK and discuss several interesting properties of PARK. We will show in the next section that for any sequence I of jobs that can be completed by a migratory offline schedule on m unit-speed processors, I can also be completed by PARK on m speed-5.828 processors. PARK is a very conservative algorithm. Roughly speaking, whenever PARK admits a job J to a processor, it ensures that the processor has no commitment to other admitted jobs before the deadline of J . This concept of zero commitment is made formal through the following notion of due. Definition 2.1. Let t be the current time. Consider 971 any job J . · Denote xt (J ) and pt (J ) as the amount of work done on J up to time t and the remaining work, respectively (note that pt (J ) = p(J ) - xt (J )). · Define the Latest Processing Interval (LPI) of J as the interval [d(J ) - pt (J ), d(J )]. If d(J ) - pt (J ) < t, we say that J expires. · For any t > t, define duet (J, t ) as the minimum amount of J 's remaining work a speed-1 processor needs to do by time t , in order to complete J by its deadline. More formally, duet (J, t ) = max{0, t - (d(J ) - pt (J ))} if t d(J ), and pt (J ) otherwise. PARK is a non-migratory algorithm using pm speed-s processors, where p and m are positive integers and s 1 is any real number. It maintains a central pool to store jobs that have been released but not yet admitted to any processor. PARK is non-migratory and each processor has its own queue of admitted jobs. Before describing the algorithm, we have one more definition. jobs may overlap with each other. For example, if two jobs have the same deadline, their LPIs always share a common right end. Yet the way PARK admits jobs aims to guarantee that at any time, all jobs admitted to the same processor have non-overlapping LPIs. This can be observed as follows. When a job J is admitted by a processor Pi at time t, all the previously admitted jobs have zero work due at d(J ). It means that at time t, the LPI of any previously admitted job starts no earlier than d(J ) and cannot overlap the LPI of J . As time passes, the LPI of each individual job might shrink (if Pi has worked on it) but cannot get bigger; thus, the non-overlapping property remains. The following is a precise statement about the non-overlapping property. Figure 1 shows the LPIs of the jobs at different times when PARK is given a sequence of five jobs. Property 2.1. (Non-overlapping property) Let t be the current time. Consider any processor Pi . Let Ju and Jv be two jobs in the queue of Pi . The LPIs of Ju and Jv do not overlap. The non-overlapping property allows us to bound Definition 2.2. Let t be the current time. Consider the commitment of each processor easily. any processor Pi used by PARK. For any t > t, we Property 2.2. (Bounded-commitment property) define duet (Pi , t ) as the sum of duet (J, t ) over each job Let t be the current time. Consider any processor Pi . J in the queue of Pi at time t. (a) For every job in the queue of Pi , its LPI starts no In the rest of the paper, we say that at time t, (i) a job J earlier than t. That is, no job in the queue of Pi has w units of work due at time t > t if duet (J, t ) = w; expires. (ii) a processor Pi has w units of work due at t if (b) For any t > t, Pi has at most (t - t) units of work duet (Pi , t ) = w; (iii) a processor Pi is doing some work due at time t . due at t if Pi is processing a job J with duet (J, t ) > 0. Proof. (a) For the sake of contradiction, assume that J is the first job that expires in the queue of a processor Pi . Algorithm 1 PARK When J is admitted to Pi , J has not yet expired. Let t0 Job Release: A job upon release is put into the po ol if be the moment just before the first time J is found to it cannot be admitted to one of the processors. expire. That is, at t0 , the LPI of J starts exactly at t0 ; Job Admission: At any time t, let S be the set of jobs in the pool plus possibly the job just released at t. all other jobs in the queue of Pi have not yet expired and If S is non-empty, we attempt to admit such jobs their LPIs, due to the non-overlapping property, must as follows: Let J S be the job with the earliest start after J 's LPI. In other words, all jobs except J have deadlines later than d(J ). Recall that Pi schedules deadline. jobs using EDF and its speed is s 1. Thus, J must · If J expires, discard J . · Else if there exists a processor Pi such that be processed by Pi at t0 and cannot expire immediately after t0 . A contradiction occurs. duet (Pi , d(J )) = 0, admit J into the queue of Pi . (b) At any time t, consider the LPIs of all the jobs Individual Processor Scheduling: Each processor in queue of Pi . The LPIs are non-overlapping and by schedules the jobs in its queue using EDF. (a), the first LPI starts no earlier than t. For any t > t, the amount of work due at t for Pi is equal to the total It is worth-mentioning that though PARK is using length of each LPI (or its portion) that ends on or before speed-s processors, the definitions of duet (Pi , t ) as t . The latter is obviously upper bounded by t - t. £ well as LPI are based on a unit-speed processor. To Since a job admitted by a processor Pi never understand the admission policy of PARK, we need to focus on the LPIs of the jobs. In general, the LPIs of expires, it can be completed by Pi by its deadline. In 972 Figure 1: Figure (a) shows a sequence of five jobs to be scheduled by PARK on two speed-4 processors. Figures (b)-(e) show the LPIs (not the schedules) of the jobs in each processor at different times. release time 0 0 1 1 2 work 16 16 12 12 12 deadline 32 32 16 36 28 (a) Input job sequence J1 J2 J3 J4 J5 current time = 0 0 4 8 12 16 20 24 28 32 36 P1 P2 J1 J2 The pool (b) At time 0, P1 admits J1 but it does not admit J2 because after admitting J1 , P1 has non-zero work due at d(J2 ). P2 admits J2 . current time = 1 0 4 8 12 16 20 24 28 32 36 P1 P2 J3 J1 J2 J4 The pool (c) At time 1, P1 admits J3 as it has no work due at d(J3 ). Both processors have work due at d(J4 ), so J4 has to wait in the pool. current time = 2 0 4 8 12 16 20 24 28 32 36 P1 P2 J3 J1 J2 J4 J5 (d) At time 2, both processors have work due at d(J5 ), so J5 has to wait in the pool. The pool current time = 3 0 4 8 12 16 20 24 28 32 36 P1 P2 J3 J5 J1 J2 J4 The pool (e) At time 3, P2 admits J5 because J5 is the job with earliest deadline in the pool, and P2 has no work due at d(J5 ). 973 For the sake of contradiction, we assume that in the course of scheduling I with PARK, some job expires in the pool and is discarded. Let J be the first such job. Let t0 = d(J ) - w(d(J ) - r(J )) = r(J ) + (1 - w)(d(J ) - r(J )). Since J has a work-span ratio at most w, J cannot expire on or before t0 and J is in the pool during the time interval [r(J ), t0 ]. Let l 0 be the biggest number such that at any time throughout the interval [r(J ) - l, t0 ], there is at Property 2.3. (Waiting property) At any time t, least one job in the pool with deadline on or before if there is a job J left in the pool, then, d(J ). By the waiting property, during [r(J ) - l, t0 ], all the m processors of PARK are busy and the total work · all processors are busy; and done by PARK is exactly · all processors are doing some work due at d(J ). the next section, we will show that for a sequence of jobs that can be completed by some offline schedule, PARK will admit every job to a processor before it expires. PARK seems to be conservative in admitting jobs and often let jobs wait in the pool. The next property shows that whenever a job is waiting, all processors are actually productive. In other words, such waiting is reasonable. Proof. Suppose on the contrary that at time t, there exists a processor Pi being idle. Then Pi should admit J or another job from the pool and become busy at t. A contradiction occurs. If Pi at t is working on a job Je that has no work due at d(J ), then the LPI of Je starts no earlier than d(J ). Pi is using EDF and Je has the earliest deadline among all jobs in Pi . By the non-overlapping property, at t, every job in Pi has no work due at d(J ), and Pi should admit J or another job with deadline earlier than d(J ) from the pool. This £ contradicts that at t, Pi is working on Je . 3 Analysis of PARK In this section, we prove the main result that any job sequence that can be completed by some migratory offline schedule on m speed-1 processors can also be completed by PAK on m speed-(3 + 2 2) processors. R Note that 3 + 2 2 5.828. We also show how to improve the resource bounds when jobs are assumed to have a certain laxity. To ease our discussion, this section will first present a lemma for the special case where every job has non-zero laxity, or equivalently, a work-span ratio strictly less than one. This is to illustrate the core idea of our analysis of PARK. Then we make use of a scaling technique to prove the general theorem, followed by two corollaries that capture the results stated earlier. Lemma 3.1. Let I be any job sequence that can be completed by some migratory offline schedule on m speed-1 processors. Let 0 < w < 1. If al l jobs in I have a work-span ratio at most w, then PARK can complete 2 I on m speed- 1-w processors. Proof. Note that the speed of the processors used by PARK is 2/(1 - w) > 1. As mentioned in the previous section, every job admitted by PARK to a processor can be completed by its deadline. To prove Lemma 3.1, it suffices to show that every job in I gets admitted rather than discarded in the admission step of PARK. m× 2l m 2 × (t0 - (r(J ) - l)) = 2m(d(J ) - r(J )) + . 1-w 1-w By the waiting property again, at any time in [r(J ) - l, t0 ], PARK schedules all processors to do some work due at d(J ). Such work can be classified into two types: 1. Work owing to jobs that are admitted to processors before r(J ) - l. 2. Work owing to jobs admitted during [r(J ) - l, t0 ]. By the bounded-commitment property, at time r(J ) - l, each processor has at most d(J ) - (r(J ) - l) units of work due at d(J ), and hence the amount of type 1 work is at most m × (d(J ) - (r(J ) - l)). Consider any job J admitted during [r(J ) - l, t0 ]. J has a deadline no later than d(J ) and by definition of l, J must be released no earlier than r(J ) - l. Note that the total work of jobs with release time at least r(J ) - l and deadline at most d(J ) cannot exceed m(d(J ) - (r(J ) - l)); otherwise such jobs cannot be completed by any offline schedule on m unit-speed processors. On the other hand, J is one of such jobs but does not get admitted by PARK. The amount of type 2 work is at most m × (d(J ) - (r(J ) - l)) - p(J ). In summary, the total amount of work done by PARK during [r(J ) - l, t0 ] is at most m(d(J ) - (r(J ) - l)) + m(d(J ) - (r(J ) - l)) - p(J ) < 2m(d(J ) - r(J )) + 2lm 2l m . 2m(d(J ) - r(J )) + 1-w This leads to a contradiction and Lemma 3.1 follows. £ In the following, we present an extension to PARK so as to remove the assumption that the work-span ratio must be less than one. This extension also allows a tradeoff between the processor speed and the number of processors used by PARK. 974 PARK(u) is a scaled version of PARK, characterized by a real number u > 0. Intuitively, PARK(u) scales every job by a factor of u and follow the schedules of PARK for the scaled jobs. When u = 1, PARK(u) is identical to PARK. More specifically, to schedule a job sequence I on n speed-s processors, PARK(u) simulates a copy of PARK that uses n speed-s processors, where s = us . Whenever PARK(u) receives a new job J , it releases a job J for PARK with r(J ) = r(J ), d(J ) = d(J ) and p(J ) = u × p(J ). Denote the processors used by PARK(u) as P1 , · · · , Pn and those used by PARK as P1 , · · · , Pn . At any time, PARK(u) admits a job J to a processor Pi if PARK admits the corresponding job J to Pi ; PARK(u) discards J if PARK discards J ; and PARK(u) runs a job J on a processor Pi if PARK runs J on Pi . We notice that PARK(u) can always synchronize with the simulated copy of PARK, because the amount of time for PARK(u) to complete a job J is exactly the same as that for PARK to complete the corresponding job J . The following is the main theorem of this section. I as stated in the theorem, PARK(u) simulates a copy p+u of PARK that uses pm speed- p(1-wu) processors. Let I be the sequence of the jobs created for PARK while PARK(u) schedules I . As I can be completed by some offline schedule on m speed-1 processors; I can also be completed by some offline schedule on m speed-u processors. Each job in I has a work-span ratio at most wu. To show that PARK(u) can complete I , it suffices to show that PARK meets the deadlines of all jobs in I . The proof is a straightforward generalization of Lemma 3.1. p+u First, note that p(1-wu) > 1 as both u > 0 and 1 > wu > 0. Suppose, for the sake of contradiction, that PARK fails to complete a job in I . This job must expire in the pool. Let J be the first such job. Let t0 = r(J ) + (1 - wu)(d(J ) - r(J )). As the work-span ratio of J is at most wu, J expires no earlier than t0 and must have resided in the pool during the interval [r(J ), t0 ]. Again, let l 0 be the largest number such that at any time throughout the interval [r(J ) - l, t0 ], there is at least one job in PARK's pool with deadline on or before d(J ). Note that l 0. During [r(J ) - l, t0 ], Theorem 3.1. Let I be any job sequence that can be all m processors are busy and the total work done by completed by some migratory offline schedule on m PARK is exactly speed-1 processors. Let 0 < w 1. If al l jobs in I have a work-span ratio at most w, then PARK(u) can pm × s × (t0 - (r(J ) - l)) complete I using pm speed- pu(p+u u) processors, where (p + u)lm 1-w . = (p + u)m(d(J ) - r(J )) + p is any positive integer and u is any real number such 1 - wu that 0 < wu < 1. Furthermore, at any time in [r(J )-l, t0 ], every processor Before proving Theorem 3.1, we illustrate how to of PARK is always doing work due at d(J ) and such choose the parameters in Theorem 3.1 so as to obtain work belongs to either a job admitted before r(J ) - l the results claimed in the introduction. onsider the or during [r(J ) - l, t0 ]. Thus, the total work done by C case where w = p = 1. Choosing u = 2 - 1 would PARK during [r(J ) - l, t0 ] is at most minimize the speed requirement and gives the following pm(d(J ) - (r(J ) - l)) + mu(d(J ) - (r(J ) - l)) - p(J ) corollary. < (p + u)m(d(J ) - r(J )) + l(p + u)m Corollary 3.1. Let I be any job sequence that can (p + u)lm (p + u)m(d(J ) - r(J )) + . be completed by some migratory offline schedule on m 1 - wu speed-1 processors. PARK(u) with u = 2 - 1 can This leads to a contradiction and PARK must be able complete I using m speed-(3 + 2 2) processors. £ to complete I . Hence, the theorem follows. Putting u = 1/(2w) gives a more general corollary. 4 Alternative analysis of PARK Corollary 3.2. Let I be any job sequence that can In this section, we show a more complicated analysis be completed by some migratory offline schedule on m of PARK, resulting in the following theorem, which enspeed-1 processors. Let 0 < w 1. If al l jobs in I have a ables us to construct a non-migratory online algorithm work-span ratio at most w, then PARK(u) with u = 21 for hard deadline scheduling that can exploit extra prow can complete I using (i) pm speed-(4w + 2/p) processors cessors to reduce the speed requirement arbitrarily close for any positive integer p, or (ii) 2/(s - 4w)m speed-s to one (see Corollary 4.1). processors for any s > 4w. Theorem 4.1. Let 0 < w < 1 be a real number. Let Proof of Theorem 3.1. Recall that PARK(u) uses pm I be a job sequence that can be completed by some speed- pu(p+u u) processors. To schedule a job sequence migratory offline schedule on m speed-1 processors. If 1-w 975 all jobs in I have a work-span ratio at most w, then I can be completed by PARK using pm speed-s processors, where p is any positive integer such that p(1 - w) > 1 and s = 1 + p(1-1 )-1 . w Using the scaling technique, we can remove the assumption of work-span ratios and extend Theorem 4.1 to any job sequence I . Recall that PARK(u) scales every job of I by a factor of u and schedules the scaled jobs 1 using PARK. Let u = 1+ for some > 0, and denote the scaled version of I as I . Every job in I has a work1 span ratio at most 1+ . By Theorem 4.1, I can be completed by PARK using pm speed-s processors where s = 1 + p(1- 11 )-1 . PARK(u), using pm speed-s/u r(J ), then J will be eventually admitted by PARK (see Lemma 4.2). Lemma 4.1. In the course of scheduling I , at any time t, PARK is safe. Lemma 4.2. Let J be any job in I . If PARK is safe at r(J ), then J wil l be admitted by PARK on or before t0 = r(J ) + (1 - w)(d(J ) - r(J )). Lemma 4.1 and 4.2 together guarantee that every job in I must be admitted by PARK. As mentioned in Section 2, PARK meets the deadlines of all admitted jobs. Thus, Theorem 4.1 follows. To ease our discussion, 1+ we will first present the proof for Lemma 4.2. We start processors, can synchronize with PARK and complete with a more technical lemma, which will also be used in I . In particular, choos/ng p = (1 + 1 )2 , we have i 1 the proof of Lemma 4.1. s/ u = + p(1- 11 )-1 u (1 + )2 . This relationship 1+ is stated in the following corollary. Note that choosing Proposition 4.1. Consider any time interval [a, b] and any time d > b. Assume that PARK is d-safe a small means using more and slower processors. at time a and at any time in [a, b], there exists a job Corollary 4.1. Let I be a job sequence that can be in PARK's pool with dead line no later than d. Then completed by some migratory offline schedule on m b - a < p(s1 1) (d - a). (Recal l that s is chosen as - 1 1 1 speed-1 processors. Let > 0 be any real number. 1 + p(1-w )-1 ; thus, p(s-1) = 1 - w - p .) 1 PARK(u) with u = 1+ can complete I using (1 + 12 2 Proof. Due to the waiting property, at any time in the ) × m speed-(1 + ) processors. time interval [a, b], all the pm processors of PARK are We are ready to prove Theorem 4.1. In the rest of busy and doing work due at d. The total work done by this section, we assume that I is a job sequence that PARK during [a, b] is exactly can be completed by some migratory offline schedule OPT on m speed-1 processors and all jobs in I have (4.1) pm × s × (b - a) . a work-span ratio at most w < 1. PARK is using pm speed-s processors, where p is an positive integer such PARK is d-safe at a and L(a, d) < sm1 (d - a). At a, - that p(1 - w) > 1 and s = 1 + p(1-1 )-1 . PARK and OPT has C (a, d) and O(a, d) units of work w To prove Theorem 4.1, we need to compare the due at d, respectively. Consider all the jobs that are total amount of work due at any particular time in released from a to b; the sum of their work due at d PARK and in OPT. At any time t, for any t > t, we is at most m(d - a) - O(a, d) (otherwise, even OPT let C (t, t ) be the total amount of work due at t in cannot complete these works by d). During the interval PARK, and similarly O(t, t ) for OPT. Let L(t, t ) = [a, b], the total amount of work due at d that PARK can C (t, t ) - O(t, t ). If L(t, t ) = w, we say that at time t, possibly work on is at most PARK lags behind OPT by w units of work due at t . C (a, d) + m(d - a) - O(a, d) Furthermore, PARK is said to be safe at time t if for any t > t, L(t, t ) is proportional to the duration from = L(a, d) + m(d - a) t to t (see the following definition). m (4.2) (d - a) + m(d - a) < s-1 Definition 4.1. In the course of scheduling I , at any ms (d - a) . = time t, for any t > t, PARK is t -safe if L(t, t ) < s-1 m s-1 (t - t). At any time t, PARK is safe if PARK is Combining Inequalities (1) and (2), we have pms(b - t -safe for all t > t. m a) < s-s (d - a), or equivalently, (b - a) < p(s1 1) (d - a). 1 - The most non-trivial observation in analyzing £ PARK is that at any time, PARK is safe (see Lemma 4.2 is in fact a corollary of Proposition 4.1. Lemma 4.1). It is then relatively easy to see that whenever a job J is released to PARK, if PARK is safe at Details are as follows. 976 Proof of Lemma 4.2. Suppose on the contrary that at time t0 = r(J ) + (1 - w)(d(J ) - r(J )), J has not been admitted. As J is assumed to have a work-span ratio at most w, J has not yet expired at t0 and it is in the pool during the interval [r(J ), t0 ]. Note that t0 - r(J ) = (1 - w)(d(J ) - r(J )), and by Proposition 4.1 (with a = r(J ), b = t0 , and d = d(J )), we have 1 (t0 - r(J )) < (1 - w - p )(d(J ) - r(J )). This implies 1 that p < 0, contradicting that p 1. £ The rest of this section is devoted to the proof of Lemma 4.1, which is further broken into two lemmas. We first state a simple fact about how the value of L(t, t ) changes over time. Fact 4.1. Let [t1 , t2 ] be a time interval before a certain time t . Assume that during the interval [t1 , t2 ], PARK has done at least x units of work due at t and OPT has done at most y units of work due at t . Then, L(t2 , t ) L(t1 , t ) - x + y . Intuitively, we prove Lemma 4.1 inductively over time. Assume that PARK is safe at time a. We first consider two basic types of time intervals [a, b] and show that in either case, PARK is safe at time b. Precisely, for any t > b, we call [a, b] · a t -quiet period if at any time in [a, b], there is no job in PARK's pool with work due at t ; and · a t -hectic period if at any time in [a, b], there is at least one job in PARK's pool with work due at t . During a t -quiet period, any job with work due at t in PARK is admitted to some processor. Since PARK is using speed-s processors, we can argue that PARK will not lag behind OPT too much on work due at t during a t -quiet period (see Lemma 4.3). A hectic period is more complicated. In Lemma 4.4 we first show that with the extra speed and number of processors given to PARK, a t -hectic period cannot last for too long. Then we notice that within such a short period, the amount of work due at t that PARK lags behind OPT cannot change too drastically and PARK is still t -safe at b. Below we prove the above observations regarding quiet and hectic periods (see Lemmas 4.3 and 4.4). Then it is easy to show that PARK is safe at any time (i.e., Lemma 4.1). Lemma 4.3. Consider a time interval [a, b] and a certain time t > b. Assume that at any time in the interval [a, b], there is no job in PARK's pool with work due at t . If PARK is safe at a, then PARK is t -safe at b. released; if no jobs are released on or before b, let r = b. Below we first show that PARK is t -safe at time r, i.e., L(r, t ) sm1 (t - r). Note that at time r, if a job J - is released, it contributes exactly p(J ) to both C (r, t ) and O(r, t ) and does not affect the value of L(r, t ). To derive an upper bound of L(r, t ), it suffices to consider the amount of work released before r. In particular, we can tighten the trivial upper bound of L(r, t ) from ^ ^ C (r, t ) to C (r, t ), where C (r, t ) denotes, at time r, the amount of work in PARK that has been released before r and due at t . Denote r the set of PARK's processors which, at r, have work released before r and due at t . Then ^ C (r, t ) |r |(t - r). If |r | < sm1 , then L(r, t ) - ^ C (r, t ) < sm1 (t - r). Bound L(r, t ) for the case when - |r | sm1 is more complicated. During [a, r], the pool - contains no job due at t and no job is released until r. Thus, at any time t where a t < r, if a processor of PARK does not have any work due at t , this processor cannot be in r . In other words, throughout the interval [a, r], every processor in r has work due at t and PARK has done at least |r |s(r - a) units of work due at t . Note that OPT achieves at most m(r - a). Thus, L(r, t ) L(a, t ) - |r |s(r - a) + m(r - a) m m (t - a) - s(r - a) + m(r - a) < s-1 s-1 (At time a, PARK is t -safe.) = m (t - r) . s-1 In summary, we have proven that at time r, PARK is t -safe. If r < b, we can repeat the above argument to prove that PARK is t -safe at each subsequent release time and eventually at time b. £ Next, we consider the case of hectic periods. Lemma 4.4. Consider a time interval [a, b] and a certain time t > b. Assume that just before a, there is no job in PARK's pool with work due at t and at any time in [a, b], there is at least one job in PARK's pool with work due at t . If PARK is safe at a, then (i) (b - a) < 1 (t - a), and s (ii) PARK is t -safe at b. Proof. Statement (i): Due to the condition of Lemma 4.4, we know that at any time in [a, b], there is a job J in the pool with work due at t and J must be released on or after a. Due to the work-span ratio assumption, any job released after a and with work due 1 Proof. We prove inductively that at any time in [a, b], at t must have deadline on or before a + 1-w (t - a) t . 1 PARK is t -safe. Let r > a be the first time a job is Let d = a + 1-w (t - a). At time a, PARK is safe 977 and in particular, d-safe. By Proposition 4.1, (b - a) < 1 (1 - w - p )(d - a) = (1 - w - 1 )(t - a)/(1 - w). Note that p w) 1 s = 1+ p(1-1 )-1 and 1 = p(1--w-1 = (1-w- p )/(1-w). w s p(1 ) Thus, (b - a) < 1 (t - a) and Statement (i) follows. s Statement (ii): Consider the pm processors used by PARK. Let be the set of PARK's processors which, at any time in the interval [a, b], are doing work due at t . Let || = . If sm1 , then, - L(b, t ) < = Next, we consider < sm1 . Label the processors - in as P1 , P2 , ..., P . At a, each of these processors has at most t - a units of work due at t . Label the remaining processors as P+1 , · · · , Ppm . At a, for each of such processor Pi , let wi be the amount of work due pm at t . Let W = i=+1 wi . Then L(a, t ) C (a, t ) (t - a) + W . From a to b, each of P1 , P2 , · · · , P , has done exactly s(b - a) units of work due at t . For each Pi where i = + 1, ..., pm, Pi at some point in [a, b] is doing some work due at a time later than t ; thus Pi has done at least wi units of work due at t . In summary, during [a, b], PARK, by time b, must have done at least × s(b - a) + W units of work due at t ; note that OPT has done at most m(b - a) units of work due at t . Hence, we have the following conclusion. + L(b, t ) L(a, t ) - s(b - a) + W m(b - a) + (t - a) + W - s(b - a) + W L(a, t ) - s(b - a) + m(b - a) m m (t - a) - s(b - a) + m(b - a) s-1 s-1 m (t - b) s-1 At time , PARK switches from a t -quiet period to a t -hectic period for some t > . }. Consider any time t 1 . For any t > t, [0 , t] is a t -quiet period, and by Lemma 4.3, PARK is t -safe. Thus, PARK is safe at any time t 1 . We can repeat the above argument to show inductively that PARK is safe at any time. In general, let i+1 = min{ > i | At time , PARK switches from a t -quiet period to a t -hectic period for some t > , or vice versa}. Consider any time t i+1 . For any t > t, let j i be the smallest integer such that [j , t] is entirely a t -quiet period or a t -hectic period. By Lemma 4.3 or 4.4, PARK is t -safe. It is worth-mentioning that at any i , a job is either released or admitted by PARK. Thus, in the course of scheduling I , there are only a finite number of i 's. The above argument will complete eventually to show that PARK is safe at any time. £ 5 Remarks Lower b ound: Consider the following job sequence: m + 1 identical jobs are released at time 0, each with m units of work and deadline m + 1. The set of jobs can be completed by a migratory schedule on m speed1 processors. For a non-migratory (online or offline) schedule to complete the jobs on m processors, some processor must admit at least two jobs, thus the speed requirement is at least 2m/(m + 1) = 2 - m2 1 . + PARK plus EDF-AC: Recall that in the firm deadline scheduling problem, there may be too many jobs to be completed and failing to complete a job only loses the value due to that job and does not cause a system failure. Given a set I of such jobs, the ob jective of a scheduler is to maximize the value obtained from completing the jobs. An online algorithm is said to be c-competitive for some c 1 if for any job sequence I , the algorithm can obtain at least a fraction of 1/c of m(b - a) t + the value obtained by the optimal offline schedule on m = - a - s(b - a) m(b - a) speed-1 processors. + m t Consider the special case when the value of a job - a - s(b - a) m(b - a) < s-1 is proportional to its processing time. If migration (by Lemma 4.4(i), (t - a - s(b - a)) > 0) is allowed, EDF-AC using m speed-3 processors is 1m competitive [12]. Since EDF-AC decides whether to (t - b) = s-1 complete or discard a job once the job is released, we can use it to select jobs for scheduling in PARK In summary, no matter what the value of is, L(b, t ) < g a on. a al sl m £ without emiErDti-AC The idctuto ocperatlieotn ias aobfoJl,owse. s-1 (t - b). Thus, PARK is t -safe at time b. Whenev r F dec es omp e j w release J to PARK with p(J ) scaled down to p(J )/3. With the observations on the quiet and hectic periods, proving that PARK is safe at any time (i.e., The job sequence selected by EDF-AC can be completed by m speed-3 processors, so the scaled job sequence can Lemma 4.1) is straightforward. be completed by m speed-1 processors and all jobs in Proof of Lemma 4.1. We first notice that at time 0, the scaled sequence have work-span ratio at most 1/3. L(0, t ) is equal to zero for any t > 0. Thus, PARK is By Corollary 3.2 with p = 1 and w = 1/3, the scaled job 10 safe at time 0. Let 0 = 0 and let 1 = min{ > 0 | sequence can be completed by PARK using m speed- 3 978 processors. As any job in the scaled sequence has References work only one third of the original, to complete the job actually selected by EDF-AC, we need to further [1] S. Baruah, G. Koren, B. Mishra, A. Raghunathan, increase the speed of the processors by a factor of 3. L. Rosier, and D. Shasha. On-line scheduling in the Thus, we have a 1-competitive algorithm for the firm presence of overload. In Proc. 1991 IEEE Real-Time deadline scheduling problem on m speed-10 processors. Systems Symposium, pages 101­110, 1991. Effect of laxity on m : Consider the offline [2] P. Berman and C. Coulston. Sp eed is more p owerful scheduling problem. Recall that m is the maximum than clairvoyance. In Proc. 6th SWAT, pages 255­263, ratio, over all possible inputs, between the value at1998. [3] M. Chrobak, L. Epstein, J. Noga, J. Sgall, R. van Stee, tained by the optimal migratory schedule and that by T. Tichy, and N. Vakhania. Preemptive scheduling in ´ the the optimal non-migratory schedule. The analysis overloaded systems. In Proc. ICALP, pages 800-811, of PARK reveals some information about the value of 2002. m when all jobs are assumed to have a certain amount [4] M. L. Dertouzos. Control rob otics: the procedural of laxity. More precisely, if all jobs have work-span ratio control of physical processes. In Proc. IFIP Congress, no greater than w, where w < 1 , Corollary 3.2 shows 4 pages 807­813, 1974. that for any job sequence, the subset of jobs that can be [5] M. L. Dertouzos and A. K. L. Mok. Multiprocessor completed by the optimal offline migratory schedule on On-Line Scheduling of Hard-Real-Time Tasks. IEEE m processors can also be completed by 2/(1 - 4w)m Transactions on Software Engineering, 15(12): 1497­ (unit-speed) processors. By selecting the m proces1506, 1989. sors that achieve the highest values, we obtain a non[6] J. Edmonds. Scheduling in the dark. In Proc. STOC, pages 179­188, 1999. migratory offline schedule attaining a value of at least 1 [7] B. Kalyanasundaram and K. R. Pruhs. Sp eed is as of the value of the optimal migratory sched2/(1-4w ) p owerful as clairvoyance. J. ACM, 47(4):617­643, ule. Hence, m 2/(1 - 4w). 2000. Implementation of PARK: We notice that [8] B. Kalyanasundaram and K. R. Pruhs. Eliminating PARK admits a simple distributed implementation migration in multi-processor scheduling. Journal of which does not require a centralized scheduler. InAlgorithms, 38(1):2­24, 2001. stead, each processor can monitor the pool and admit [9] G. Koren, E. Dar, and A. Amir. The p ower of a job according to its own status, i.e., each processor migration in multiprocessor scheduling of real-time does not need to inquire the status of other processors. systems. SIAM Journal on Computing, 30(2):511­527, This is different from many other scheduling algorithms 2000. (e.g., EDF, LLF) in which the status of all processors [10] G. Koren and D. Shasha. MOCA: A multiprocessor on-line comp etitive algorithm for real-time system is needed in order to make a scheduling decision. Thus, scheduling. Theoretical Computer Science, 128:75­97, PARK is particularly useful when it is difficult to obtain 1994. the complete information of all processors. [11] T. W. Lam and K. K. To. Trade-offs b etween sp eed Op en Problems: Let I be a job sequence that and processor in hard-deadline scheduling. In Proc. can be completed by some migratory offline schedule SODA, pages 623­632, 1999. on m speed-1 processors. Consider the processor speed [12] T. W. Lam and K. K. To. Performance Guarantee required to obtain a non-migratory online schedule for Online Deadline Scheduling in the Presence of for I . There is a gap between the upper bound of Overload. In Proc. SODA, pages 755­764, 2001. 5.828 and the lower bound of 2 - m2 1 . The current [13] C. A. Phillips, C. Stein, E. Torng, and J. Wein. Opti+ analysis of PARK seems to be quite loose and we believe mal time-critical scheduling via resource augmentation. In Proc. STOC, pages 140­149, 1997. that a better analysis could possibly reduce the speed requirement to 4. We have shown that when extra [14] J. Sgall. On-line scheduling -- a survey. In A. Fiat and G. Woeginger, editors, On-line Algorithms: The State processors are given, the speed requirement of PARK of the Art, pages 196­231. Lecture Notes in Computer can be reduced arbitrarily close to 1. However, we Science, Springer Verlag, 1998. do not know any (migratory or non-migratory) online [15] J. A. Stankovic, M. Spuri, K. Ramamritham, and G. C. algorithm that can guarantee to complete I using only Buttazzo. Dead line scheduling for real-time systems: f (m) speed-1 processors, where f (m) is a function EDF and related algorithms. Kluwer Academic Pubof m. For the problem of firm deadline scheduling, lishers, 1998. the current analysis depends on EDF-AC as the job selection module. In fact, we conjecture that PARK alone (say, with m speed-9 processors) is sufficient to match the performance of any offline schedule. 979