Analysis of Hard ReaI?'Uime Systems Abha Nioitra TR 85?693 July 19S5 Department of Computer Science Cornell University Ithaca, NY 14S53 ANALYSIS OF HARD REAL-TIME SYSTEMS Abha Moitra Department of Computer Science Cornell University ABSTRACT In this paper we study hard real-time s?stems : systems where strict time deadlines have to be met. We analyze a special case as well as a general model for hard real-time systems and study pre emptive, static, scheduling policies for a single processor. The analysis is exact and can handle any arbitrary choice of strict dead- lines. For any specification of a hard real-time system, a feasible priority assignment is one where all deadlines are met. An optimal scheduling algorithm is an algorithm that always produces a feasi- ble priority assignment if one exists. For both the special and gen- eral model we present an optimal scheduling algorithm. Index Terms - Deadline, preemptive, rate-monotonic, real-time sys- tems, scheduling policy. 1. Introduction A real-time processing system can be modelled as a set of processors handling requests that arrive from a number of sources, with the constraint that each request must be processed within some fixed time limits. For any given schedul- ing policy, it is necessary to be able to evaluate the response times for the requests. Queuing theory [8] has traditionally been used to estimate these quanti- ties. However, in systems where strict deadlines must be met, termed as hard real-time systems [10], probabilistic analysis is not adequate. -2- A hard real fimetime system P consists of n sources, S1,..,S? with n > 2 and analysis of hard real-time systems can be undertaken when the following informa- tion is available for each source 1. The inter-arrival or cycle time, T1., which is the minimum time between suc- cessive requests from source Sj. 2. The processing or run time, C\., which is the maximum amount of processing required for any request from source 3. The deadline, Dj associated with source Typically, the deadline for a source is specified by requiring that a request be processed within some fixed time interval. The scheduling policy for one processor assumes that a different process is dedi- cated to processing requests from each source and that the arrival of an input from source causes the associated process to be automatically executed. How- ever, the system has different priority levels assigned to sources; and a request from a source of higher priority causes execution of a lower priority process to be temporarily suspended (priority value 1 is the highest priority). Execution of a suspended process is resumed only when there is no higher priority process to be executed. Such a model implies that a request may not be processed immedi- ately, therefore requests have to be buffered. In this paper we will only consider real-time systems to be scheduled on a uni- processor and where a buffer of size 1 is associated with each source. We will also assume that each source is assigned to a unique priority level and that there is no cost associated with switching the processor. We call this Model 1. In general, the inter-arrival, processing and deadline times may be real numbers -3- but to take account of finite machine precision we can always scale the original problem P by multiplying all these times by a suitable constant to yield an equivalent problem with only integer parameters. We will assume t?at such a scaling is always done. We will also use LCM(Xi,..,Xm), \X1/X2] and ?1/X? to denote the least common multiple, the ceiling and the floor functions for integer arguments. We also use [t1, t2) to denote the closed-open interval from t1 up to, but not including, 12. In this paper we will first analyze a special case of Modeli obtained by setting Dj = oo for all sources. This is an important class of problems and we term this as Model 2. We will also show how the analysis for this model can be extended to handle arbitrary deadlines and hence cover the entire class of problems in Model 1. DEFINITION 1. For a given priority assignment, a request X is said to be lost or ot'erwritten if a new request from the same source arrives so that the processing for request X cannot be started. In Model 2, a priority assignment in which no requests are ever lost is acceptable. In our analysis we will make a simplification that a request is available for read- ing (and hence processing) until another request arrives from the same source. This assumption is realistic, provided a process that handles a request reads the entire request as its first action in near-zero time. Mthough we investigate scheduling algorithms under Model 1, a large number of other models have been studied in the literature. Scheduling of unit time requests has been studied by Garey et. al !4] and Frederickson [3]. Scheduling on - 4- a multiprocessor systems has been studied by Gonzalez and Soh t6], Dhall and Liu [2], Gonzalez and Sahni [5], Simons [13], Lawler and Martel [9] and Bertossi and Bonuccelli [1]. Scheduling of three source systems on a single processor with limited preemption is studied in Mok[12]; the other details of their model are also different. The remainder of the paper is organised as follows. Section 2 introduces the ter- minology used. Section 3 investigates priority assignments for AThdel2 while sec- tion 4 analyzes scheduling algorithms for AIodet2. S?tion 5 extends the analysis for Model2 to handle Afodell. Section 6 gives some possible extensions of our work, section 7 compares the work presented here with the existing work and sec- tion 8 presents some conclusions. 2. Terminology and Assumption? ?Te make the following assumption about the environment. Al. A request is available for processing until it is overwritten by the arrival of the next request from the same source. Since we are interested in dealing with strict deadlines; we will always perform a worst case analysis, where for each source S? requests arrive at times m * Tj, m = 0,1,2,.. . This will also allow us to infer that if all the requests meet their deadlines in the time interval [0, LCM( T1,.., T?)] for the worst case analysis then all requests will always meet their deadlines. In the worst case the n sources can nC;. impose a processor tttilization factor or processor load U? = --H and we i-i Tj will assume that U < 1. A schednling algorithm is a set of rules determining which request must be -5- processed at any particular moment. We shall be studying pre --Hemptive, priority--Hdriven scheduling algorithms; i.e., whenever a request arrives from a higher priority source than the one being currently served, the running process Is suspended and the requested process is started. We shall only consider static scheduling algorithms : i.e. those where the priorities assigned to sources are never changed. A scheduling algorithm generates one priority assignment for the sources of a given problem. A priority assignment for a problem is said to be feasible for a source if all requests from that source meet their deadlines. A prior- ity assignment for a problem is said to be a feasible priority assignment, fpa, if under that priority assignment requests always meet their deadlines. An optimal scheduling algorithm is a scheduling algorithm that generates a feasible priority assignment for a problem whenever one exists for that problem. DEFINITION 2. For problem P let A = (ii,..,im ? be a non-empty subset of the source indices in P and let Y = LCM(Tj1,??,Tjrn) Define Maximum Cover for A, MC)1,..?j?, to be the maximum time less than or equal to Y for which the pr? cessor can be utilized continuously by the sources named in A. LEMMA 1. Consider a problem P where source is assigned priority j. If S1,..,Sj is an fpa then T is equal to MC1,j iff the following hold = T j=1 VT' : < T: rT'/7)1*c? > T' j=I ?T+VTj]*Q < T+1 j=1 (1) (2) (3) - 6- PROOF. (1) and (2) imply that the processor can be continuously utilized up to time T by the sources 51,..,Sj. In addition if (3) is satisfied then T represents the maximum time for which the processor can be continuously utilized by requests arriving from sources S1,..,?. 1] 3. Feasible Priority Assignment for Model2 We now consider how a priority assignment can be checked for feasibility and under what general conditions a feasible priority assignment always exists for a problem under Model 2. 3.1 Checking Priority Assignment For any particular priority assignment it is a straightforward task to check whether the priority assignment is feasible or not. This can be done using a graph paper and allocating the processor to the processor according to the priority. This allocation has to be done for the interval [o,LCM( T1,.., T?)] and if each request meets its deadline then the priority assignment is feasible otherwise not. This construction can be mimicked by the following algorithm. 1. var A: array [O:YJ of boolean; (* Y = LCM( T1,.., T?) *) 2. C,T : array [1:nJ of integers; 3. FPA: array [1:n] of booleans; 4. J,K,AMT,ARRWAL: integer; 5. for J:=1 to Y do A[Jj:= true; 6. for J:= 1 to n do 7 begin 8. ARRWAL:= 0; AMT:= C[J]; FPA[J]:= true; 9. while ARRWAL 0 do 13. begin 14. if K > ARRWAL + T!J] & AMT = C(JJ 15. then FPA[JJ:= false; 16. if A[K] then begin A[KJ:= false; AMT:= AMT-1 end; 17. K:=K+ 1 18. end; 19. ARRWAL:= ARRWAL+ T(J] 20. end; 21. end; Fig. 1. Feasibility Checking AIgorithm. In the above algorithm we could have halted as soon as FPA ?JJ is set to false; however, we will later make use of the entire FPA array. The cost of the above algorithm is O(n* LCM( T1,.., T?)) (however, its average cost can be reduced considerably by rearranging the computation so that the minimal time interval required for demonstrating feasibility/infeasibility is used as opposed to the time interval [O,LCM( T1,.., T? )j). 3.2 Critical Processor Utilization Consider Ex. 1 for which we will show that no fpa exists. Ex. 1 S? ?2 ?3 ?4 C1 11 1 T 3 4 5 6 Here U = 57/60. -8- We say that a source Sj should not be assigned the lowest priority if such an assignment would lead to some request being lost. We can show that no fpa exists by showing that none of the sources should be assigned the lowest priority. For Ex. 1 we have MC1,2,3 = 7 which is greater than T4 and hence T4 cannot have lowest priority MC1,2,4 = 5 which is equal to T3 and hence T3 cannot have lowest priority MC1,3,4 = 4 which is equal to T2 and hence T2 cannot have lowest priority MC2,3,4 = 3 which is equal to T1 and hence T1 cannot have lowest priority The processor utilization factor for a problem P is said to be cntical, if no fpa exists for P but a unit decrease in the run-time of any request, or a unit increase in the cycletime of any request, makes an fpa possible. Altering the cycle?time or the run-time of a problem changes the problem being considered; but the number of sources being considered remains constant. We can therefore consider the set of all problems with the same number of sources and determine for that set the minimum load for which no fpa exists. Hence we will now define the crit- ical processor utilization factor, CLJm, for m sources such that for all m source problems that have process utilization factor below the value derived for ?LJ?, there exists an fpa. On the other hand, if the processor utilization is above the derived value of CUm, an fpa may exist if the run-times and the cydetimes for the problem are suitably related. THEOREM 1. Without loss of generality let the sources of P be numbered so that Tj < Tj+1, 1 < i 1, is assigned the lowest priority and requests from all the sources arrive at time = 0, then time T = Cj + Cj is spent by the processor j--H1 j=i+1 in processing the first requests that arrive from all the sources except Sj So MC1,2??,j?1?j+ 1,..7n > T (note if i = n then MC1,2,??,j?1,j+ 1,..,n We now consider two cases. - 10- I.C1 < Cj. In that case T < ? Cj and hence T < T1. Since j--2 Tj > T1, 1 < j < n it follows that a second request from any source in fS1,..,Sj?1, Sj+ i,..,5n) cannot arrive in time to give MC1,??,j?1,j+ i,,.,n > T Hence MC1,?,,j?1,j+ i,,.,n = T and so T < T but this yields Tj < T1 which is a contradiction. II. C1 > Cj In that case T = ? Cj and hence T = T1. Therefore a second j=2 request from source S1 can arrive in time to extend MCi,..?i?i,i+ i,..?n to T + C1. Since for 2 < j < i--H1 Tj = Tj?1 + C?j?i it follows that a second request can arrive from sources S2,. ?5i-i so as to give i--Hi n n--Hi MC1?j4j+1? > 2*? Cj + ? Cj If i = n then 2*? Cj > 2*T1 j--i j--Hi+i j--Hi and hence a third request from source S1 can arrive in time to give n--Hi MCi,?,,n?i > C1 + 2 * ? Cj. As before, we are interested in minimizing U j=i over all possible cases, and hence (4), (5) and (6) hold. 5 THEOREM 2. For problem P of n sources if n < 3, then CU? = 1 otherwise ?-? 1 1 + CU? = j=?1fl+? 2n-1 PROOF. From Theorem 1 we obtain the result that none of the sources in prob- lem P should be assigned the lowest priority and the process utilization factor is minimized if (4), (5) and (6) are satisfied. For n < 3 these imply U? > 1. Hence for n < 3 there is no way in which the cycle and run times can be arranged so that no fpa exists while U? < 1. So for n < 3 CU? = 1. For ________ 1 n > 4 (4), (5) and (6) give CU? = + 2n?1 3 flft3 i=-i - 11 - If n = 4, then from Theorems 1 and 2 we obtain that problems Pi and P2 both do not have any fpa. Pi S1 S2 S3 S4 P2 S1 S2 S3 S4 Ci 1 1 1 C 2 2 2 2 T 3 4 5 7 T 6 8 10 14 Further, problem P3 also does not have any fpa P3 S1 S2 S??1 & C 1 1 1 1 T n-i n 2*n--H3 2*n-1 In P3 if Tj is increased by any amount, d, then the process utilization factor for the altered problem falls below CU? and an fpa should exist for it. Fig. 2 shows that the assignment of priority j to when d < 1 yields an fpa (here for sim- plicity we have not scaled the problem). Similarly, if C1 is decreased by any amount, then assigning priority j to also yields an fpa. processing I 5? Sj II 1 ?l ?n-i S? S2 S? S3 fre? ____________1-dId??-d?II time 0 n+ i-2 n+ i-1+ d 2n-3+ d 2n-2 2n-1 2n 2n+ 1 2n+ 2 2n+ 3 S? arrival A A "I" accounts for the complete processing for requests from S1, S2,..,S??1, S1, 52,..'5i-1 in that order "II" accounts for the complete processing for requests from S? + Fig. 2. Processor Allocation. - 12 - 4. Scheduling Algorithms for ModeI2 Having investigated conditions under which an fpa always exists, we now derive a scheduling algorithm to generate an fpa whenever possible. A very simple and extensively used scheduling algorithm is based on the idea that sources with lower cycle times should be assigned higher priorities; this is also called rate- monotonic priority assignment. Unfortunately, for ModeI2 this scheduling algo- rithm does not always give an fpa when one exists. We illustrate such this situa- tion in Ex. 2. Ex. 2 5i ?2 53 C 4 2 1 T 5 12 30 PA 1 2 3 PA' 1 3 2 ratemonotonic priority assignment which is not fpa a priority assignment which is an fpa We will derive an optimal scheduling algorithm for Model2 which will be a vari- ant of the ratemonotonic scheduling algorithm and hence we will first investigate the ratemonotonic scheduling algorithm in more detail. 4.1 Rate-Monotonic Scheduling Algorithm We will now investigate the conditions under which the ratemonotonic schedul- ing algorithm always yields an fpa for Model 2. That is, for a problem of n sources we derive the bound TU? on the processor load, such that for any prob- lem P with load less than TU? the ratemonotonic scheduling algorithm gives an fpa while for any problem P with processor load greater than or equal to TU? the rate-monotonic scheduling algorithm may or may not give an fpa. THEOREM 3. For problem P, if MC1,?,? = y,then another problem specifica- tion P' obtained from P in which all the cycle times and the run times are - 13 - multiplied by a factor m has = m*y. PROOF. Obvious, since the multiplication of all the cycle times and the run times by a constant can be thought of as changing the unit of measurement. 0 THEOREM 4. For problem P with U? < 1 and sources numbered so that T < Tj+1, 1 < i < n; the ratemonotonic algorithm does not give an fpa if > T??1 PROOF. Let (7) x 1 - = --H where ? > ?-1 and let z = MC1,??1 iffi,1 Tj Y So, x/ y represents the maximum amount of load that can be imposed by the source so as to keep U < 1 If z > T??1 then construct another problem P, from P by scaling up the cycle and run times of the first fl--Hi sources by a factor ?fl such that m*z > y. Then P and P' have the same load and for P' is m*z (by Theorem 3). Now we can choose C? = x and T? = ? so that U ? 1 and the ratemonotonic scheduling algorithm will not result in an fpa for P,. So, a ratemonotonic scheduling algorithm does not result in an fpa if MC1,??1 > T??1 0 THEOREM 5. Consider problem P of n sources and processor load U? < 1. For n = 2, TU? = 1 otherwise TU? = (n--H1)*(21/(?-') --Hi). PROOF. Without loss of generality assume that the sources for the problem P are numbered so that Tj < Tj + 1 1 < i < n. From Theorem 4 we know that the ratemonotonic scheduling algorithm does not give an fpa if > ??1. If the problem P has only 2 sources then MC1 = C1 < T1, - 14 - which contradicts the assertion MC1,??,??1 > T??1 and hence the ratemonotonic scheduling algorithm gives an fpa if U_ < 1. So, for n = 2, TU? = 1. We now consider n > 2. MC1,..,n-1 > T??1 implies that at least a second request from all the highest n--Hi priority sources can arrive in time to extend That is, i--Hi n?1 2*?Cy+ V?C?>T 1 2*T1 = T2 *T?1 aT' au =0 ? Tj2 --H Tj4*Tj+1 2< i 2 aT??1 _ These equations can be solved to give --H 2?n4 * T'4 for 2 < i < fl--Hi 15 - Hence, U = --H 1)*(2'/(?-') --H 1) Li 4.2 Optimal Scheduling Algorithm In this section we develop an optimal scheduling algorithm for AIodet2. Consider the rate-monotonic priority assignment for the problem P If U < (n --H 1)*(2'/(?-') --H 1) then the ratemonotonic priority assignment is a fpa and we are done with a total cost = O(n logn). Otherwise, check whether this priority assignment is a fpa using the feasibility checking algorithm of section 3.1. The cost of applying this algorithm is O(n * LCM( T1,.., T?)) If the priority assignment is a fpa then the total cost is O(n logn + n * LCM(T1,,T?)) = O(n * LCM(T1,..,Tn)) If the ratemonotonic priority assignment is not a fpa then we alter the priority assignment as follows. Let Fig. 3 describe the FPA array after the initial applica- tion of the algorithm. SI Sj 11111 1 i Fig. 3. Array FPA where i is the leftmost index with FPA (i)=f alse. Now consider the subproblem of finding a fpa for the i sources, S1,..,5j of Fig. 3. Now if a fpa exists then there exist some source to which we can assign the lowest priority (i.e. ith priority). To check whether jth source can be assigned the lowest priority we consider a new priority assignment obtained by shifting Sj behind S??, i.e. Sk has j priority k if k < ?; priority i if k = j priority k--H1 if k > - 16 - and then apply the feasibility checking algorithm. We work leftwards from the (i--H1)th source until we succeed in finding a source that can be shifted behind 5? If we do not succeed then no fpa exists for this subproblem as well as for the ori- ginal problem. Suppose S? can be shifted behind S? then the sources ordered on priority are S?,. ., 5???? Sj+ i,..,S: 5?. We will now argue that this priority assign- ment is a fpa (for this subproblem). THEOREM 6. Let the sources ordered on ratemonotonic priority assignment be Sj,.., 5i--Hi' 5?'5?+i'??'5?; and let this priority assignment be feasible for 5i'??'5i--Hi but not for 5? Consider the priority assignment ?i `?" 5i-i' 5i+ ?????5??5?; this is a fpa if the priority for is feasible. PROOF. For all sources other than S? the priority assignment is feasible follows immediately. We will now prove that this priority assignment is feasible for S? We do this by proving that for all k > 1 at least 1 + (k?1)Cj units of process- ing is allocated to source S? in time interval tO,kTi]. The proof is by induction. Base Case. k = 1. Since has a feasible priority it implies that at least 1 unit of processing is allocated to in [0, Ti] However, since 5? is at a higher prior- ity than S? it implies that Ci units of processing is allocated in [0, Tj]. Hence at least 1 unit of processing is allocated to S? in 10, T,]. Induction Step. Assume that V h < m at least 1 + (h?1)Cj units of processing is allocated to S? in [O,hTjJ. Since Tj> Ti it follows that ? p : pTi < mT. and mT? <(p+l)Ti < (m+1)T?. Case 1. The amount of processing allocated to si in [pTi,mTi] is zero. Since 5i - 17 - has a feasible priority it must be allocated at least 1 unit of processing in [mT?,(p+ 1)Tjj However since Sj has a higher priority than all processing for its requests must be completed before processing can be done for Sj Hence, we obtain (m+ 1)Cj units of processing for Sj in [O,(m+ 1)T?]; i.e. at least I + mC? units of processing for Sj in [O,(in+ 1)Tj]. Case 2. The amount of processing allocated to in [pT?,mT?] is greater than zero. This implies that mC? units of processing is allocated to S? in [O,mT?j. We now have to show that we get at least one more unit of processing for Sj in [mT1,(m+ 1)Tjj For this note that MCj,4?jy+1,1?1 < T1 --H Cj --H 1 < T2 (because we obtain at least 1 unit of processing for Sj in [0,7)]). By definition of MC it follows that from time m Tj onwards the maximum amount of time for which the processor can be continously utilized by the sources Sj,.., Sj?1, Sj+ 1'??5i-1 is less than Tj and hence at least 1 more unit of processing is obtained for S? in (mT?,(m+ 1)Tj] So we obtain at least 1 + mC? units of processing for S? in [O,(m+ 1)TjJ 0 So the total cost of removing the infeasibility of 1 source out of n sources is O(n logn + n2 * LCM(T1,,T?fl = O(n2 * LCM(Tj,,T?)? If the ratemonotonic priority assignment yields the following situation SI Si1 Sj2 fi'jtIii..itIi... 1 i1 i2 Fig. 4. Mray FPA. then we can attempt to remove the infeasibility of both Sj1 and Sj2 at the same time. That is we will first attempt to move (simultaneously) Sjj?1 and ?I2--H1 over - 18 - Sj1 and Sj2 respectively. Notice that if we succeed in finding Sirn (m = 1,2) that can be moved over 5?rn then 5?m will be feasible since Tim > 7)m' This can be extended so that we attempt to remove all the infeasibilities at the same time. If at some point we have the situation Sj Sj 5i+1 It...Itifi1 Fig. 5. Mray FFA. then we would first attempt to move S??i over both S? and ?+ ?. Clearly, the worst case complexity of obtaining a fpa is when only S? is infeasible in the rat?monotonic priority assignment and a fpa can only be obtained by shifting ?i behind S? In that case the total cost is O(n logn + n2 * LCM(T1,..,T?)) = O(n2 * LCM(T1,..,Tn)) We now present the optimal scheduling algorithm developed for Model 2. Optimal Scheduling Algorithm ror Model 2: 1. Assign ratemonotonic priorities to the sources. 2. If U? < (n --H 1)*(2V(n?1) --H 1) then go to step 6. 3. Apply algorithm of section 3.1 to obtain array FPA. 4. If Vi 1 < i _ n : FPA [ij = true then go to step 6. 5. For each j such that FPA [I] = false find the leftmost index flj : flj and the fljth source can be shifted behind the jth source. If flj cannot be found then no fpa exists for the problem. - 19 - 6. Stop. 5. Handling Specific Deadlines In Model 1 So far we have dealt with problems where the deadline was specified implicitly since a buffer of size 1 was associated with a source. This implicit deadline is the weakest possible that can be allowed with buffers of size 1, but at times the prob- lem may specify stronger deadlines that have to be met. First of all, the algorithm of section 3.1 has to be altered slightly to check that that the processing of each request is completed within its deadline. The cost of this algorithm remains O(n * LGM(T1,..,Tn)). Secondly when we have an impli- cit deadline, D?1,imposed for source Sj by a buffer of size 1 then D.' > Tj Since Dj = oo , in Model2 we start the optimal scheduling algorithm by first assigning priorities according to the rat?monotonic priority assignment. In Model 1, the Dj and Tj can be related in any arbitrary way so we first define Tj? = min( Tj ,Dj) and start the optimal scheduling algorithm by assigning priorities according to T;? (i.e. higher Tj' have lower priority). The critical thing is that if any point S? is infeasible and can be shifted behind Sj then the new priority assignment for Sj is feasible. This follows from the fact that Tj? > Tj' and there are two cases that we have to consider. 1. If Tj > Tj then the argument used in the optimal scheduling algorithm for Model2 can be applied here. 2. If Dj > Dj then if Sj at a lower priority than S? can meet a stricter dead- line then Ss must also meet its deadline. So, the optimal scheduling algorithm for Model 1 is the same as the optimal - 20 scheduling algorithm for ModeI2 except that Step 2 is not used and the feasibility checking algorithm of section 3.1 is altered suitably. The cost of this algorithm is O(n2 * LCM(T1,,T?fl 6. Various Extensions In this section we indicate some of ways in which our analysis can be extended easily. Quite often in an analysis of real-time systems we are interested in obtain ing bounds for response time for each source. This can be done by a slight modification to the algorithm of section 3.1, to determine response time for source Sj we would obtain max (completion of processing of jth request of S? LCM(T1,..,Tn) - arrival of jth request of Sili = 1,.., Tj While it is necessary to go up to LCM( T1,.., T?) in checking the feasibility of an arbitrary priority assignment, we believe that for the rat?monotonic priority assignment and the priority assignments encountered in the application of the optimal scheduling algorithms for Modell and Model2 it should be possible to improve the performance of the feasibility checking algorithm. We propose to investigate this idea in future work. Throughout this paper we have assumed that a buffer of size 1 is associated with each source. But the analysis that we have presented can be extended to handle arbitrary buffer size. This work should also be extended to handle the situation where more than one source is assigned the same priority. - 21 - 7. Comparison With Other Work In this section we compare the work presented here with that existing in the literature. We confine our attention to the relevant work done on scheduling on a single processor. Liu and Layland 110] have studied a special case of Model 1 in which the deadline for some source is specified by requiring that the processing of a request be completed before the arrival of the next request from the same source, i.e. Dj = Tj for all sources ?. We shall call this the LL model. They impose an arbitrary but very specific deadline and hence are able to deal with only a subset of problems that can be dealt with in model Model 1. Even between Model2 and the LL model, we feel Model2 is more realistic since quite often the requirement for a real-time problem is that all requests be handled, in which case the buffer size imposes an implicit deadline. We present below some comparison between Model 2 and the LL model. Since the deadline imposed by the LL model is more strict than that in Model 2, it is reasonable to expect that a larger class of problems possess a fpa under Model 2. For LL model, it has been shown [10] that the critical processor utiliza- tion factor for a problem of n sources is n * (2'/? --H 1) and Table 1 summarizes the corresponding maximum values of process utilization factor which ensure the existence of fpa for LL model and Model 2. - 22 - n LL model ModeI2 CU? = n * (2?n?1) CU? = ?-? 1 _______ + 1 j=1fl+? 2*n--H1 2 3 4 5 6 7 8 9 10 100 1000 oo .828 1.0 .779 1.0 .756 .926 .743 .870 .734 .836 .728 .813 .724 .796 .720 .784 .717 .774 .695 .700 .693 .693 in 2 in 2 Table 1. Existence of fpa. The major difference is that the ratemonotonic scheduling policy is an optimal scheduling policy for the LL model. While this policy is very efficient to imple ment (cost = O(n logn)); a priority assignment obtained by it may not be a fpa for the LL model. So to compare the costs between the LL model and Modell and AIodet2; we must also include the cost of checking for feasibility. Hence the cost of the LL model is O(n logn + n * LCM(Tj,.,T?)) while the cost for Mode(1 and Mode(2 is O(n logn + n2*LCM(T1,..,T?)) The cost of Model2 does not compare favorably with that of the LL model. However, Modell can handle arbitrary deadlines and its cost is not prohibitive compared to that of LL model. The interesting thing to note is that in the LL model since Dj = Tj, the deadline Dj is more strict than the implicit deadline Pj' and no adjustment to the ratemonotonic priority assignment is required to obtain a fpa. However, in Modell and Alode(2 it is not possible to obtain exactly the implicit deadline imposed by the buffer size and hence adjustment to the ratemonotonic priority assignment is required to obtain a fpa. In fact, whenever Dj < T for all sources - 23 - then a priority assignment based on lower priority to higher Dj will be an optimal scheduling policy. In Liu, Liu and Liestman [11] it is assumed that the deadline for completion of a requested computation coincides with the earliest next arrival from that source. In contrast we impose no constraint on how the cycle time, run time and deadline are to be related with each other. The model that we have used in this paper is based on that used in Joseph [7]. The difference between [7] and our work is that we are able to do an exact analysis whereas only an approximate analysis is done in [7]. 8. Conclusions In this paper we have investigated preemptive, static scheduling policies for hard real-time systems for a single processor. An exact analysis for this class of prob- lems can be undertaken when the cycle time, run time and the deadline associ- ated with each source is known. When these values are known, we derive an optimal scheduling algorithm for this class of problems which whenever possible assigns priorities so that all the deadlines are met. The priority assignment given by the optimal scheduling algorithm is an adjustment to the well known rate monotonic priority assignment. This work must be contrasted with the previous work for this class of problems where the optimal scheduling algorithm was known only when the cycle time and the deadline for each source was the same [10]. - 24 - Acknowledgement I would like to thank M. Joseph for introducing me to this problem and many helpful comments while this work was being done. I would also like to thank R. Cleaveland and F.B. Schneider for their helpful comments on previous versions of this paper. REFERENCES [1] A.A. Bertossi and M.A. Bonuccelli, "Preemptive scheduling of periodic jobs in uniform multiprocessor systems," IPL, vol. 16, pp. 36, Jan. 1983. [2] S.K. Dhall, and C.L. Liu, "On a real time scheduling problem," Oper. Res 2, vol. 6, pp. 127-140, Jan. 1978. [3] G.N. Frederickson, "Scheduling unit-time tasks with integer release times and deadlines," IPL, vol. 16, pp. 171-173, May 1983. [4] M.R. Garey, D.S. Johnson, B.B. Simons and R.E. Tarjan, "Scheduling unit- time tasks with arbitrary release times and deadlines," SlAM J. Comput., vol. 10, pp. 25?269, May 1981. [5] T. Gonzalez and 5. Sahni, "Preemptive scheduling of uniform processor sys- tems," J. ACA', vol. 25, pp. 92-101, 1978. [6] M.J. Gonzalez and J.?V. Soh, "Periodic job scheduling in a distributed prc'- cessor system," IEEE Trans. Aerospace Etectron. Systems, vol. 12, pp. 53O? 535,1976. [7] M. Joseph, "On a problem in real-time computing," to appear in IPL. [8] L. Kleinrock, QtteueThg Systems, Vot. II : Computer Applications. Wiley Interscience, New York, 1976. 25 - [g] E.L. Lawler and C.U. Martel, "Scheduling periodically occurring tasks on multiple processors," IPL, vol. 12, pp. ?12, 1?81. 1101 C.L. Liu and J.W. Layland, "Scheduling algorithms for multiprogramming in a hard-real-time environment," J. ACM., vol. 20, pp. 4&61, Jan. 1S73. 111] C.L. Liu, J.W.S. Liu and L. Liestman, "Scheduling with slack time," Acta Informatica, vol. 17, pp. 31-41, 1?82. 112] A.K. Mok, "The design of real-time programming systems based on process models," Proc. of the IEEE Real-Time Systems Symposittm, Austin, Texas, Dec. 1984, pp. 5-17. 113] B. Simons, "A fast algorithm for multiprocessor scheduling," Proc. 21st Symp. on FoundatThns of Computer Science, Syracuse, NY, 1980, pp. 50-53.