@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix skos: . vivo:departmentOrSchool "Science, Faculty of"@en, "Computer Science, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Zhu, Wenjing"@en ; dcterms:issued "2010-11-10T17:26:14Z"@en, "1991"@en ; vivo:relatedDegree "Master of Science - MSc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description """This thesis documents our study on scheduling mixed real-time and non-real-time tasks with different performance metrics. The work is motivated by the need to provide satisfactory performance trade-offs in a dynamic environment where the arrival rates and proportions of the real-time and non-real-time tasks vary with time. We first examine two threshold-based schemes, Queue Length Threshold and Minimum Laxity Threshold, and propose the corresponding adaptive schemes based on our results from approximate analysis and simulation. The idea is to improve performance by adjusting trade-off points adaptively as the arrival rates change. We further discuss the idea of integrating the two thresholds. The new algorithm, ADP, is evaluated by simulation under various load conditions and compared with other common scheduling disciplines as well as an optimal algorithm. Some implementation issues are also discussed. We conclude that by setting appropriate threshold functions in accordance to the requirements of applications, we can achieve satisfactory bounded loss ratio for real-time tasks and acceptably low average delay for non-real-time tasks in a wide range of workload conditions."""@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/29913?expand=metadata"@en ; skos:note "Adaptive Threshold-based Scheduling for Real-Time and Non-Real-Time Tasks By W E N J I N G Z H U B.Sc, Peking University, China, 1988 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES (DEPARTMENT OF COMPUTER SCIENCE) We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA August 1991 © Wenjing Zhu, 1991 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Co^yict^er J c w ^ c e . The University of British Columbia Vancouver, Canada Date -dcjuST df, / Ta ; or ^ 2. RT queue length = 0 . Since we have two queues in the system, a complete description of the system state requires two state variables. Such an approach will inevitably lead to state explosion. So, we decided to separate the two queues as far as we can to avoid the complexity introduced by the correlation between them. x x x x x x x x x |i* M-* M-* M-* | i * V- V- H V-Figure 2.12: QLT: Non-Real-Time state transition rate diagram (A = An) Let us first look at the non-real-time queue in QLT [figure 2.12]. By using queue length as the state variable, the non-real-time queue can be described in two stages. When its queue 3[5] described a solution using matrix geometric methods. However, without special treatment, the accuracy of the solution is l imited by space and time. As shown in some figures, our straightforward program has difficulty in producing reasonable results in the cases when the states are large. CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 19 length exceeds the threshold Tq non-real-time tasks will always be served, so it is simply an M/M/l system. However, when its queue length is below Tq, a non-real-time task (if any) can be served only if the real-time queue is empty. We make the assumption that its departure process is also Markovian when the queue length is below the threshold. We can imagine that the non-real-time queue has its own but slower server, so that the service time is scaled larger with mean l//x». Let pr0 — Pr{realtime queue is empty), we have: /*• = M (2.1) Let us also denote by pn the ratio An//z , and by p„ the ratio An/V*4. We have the following equilibrium equations : AnPo = M*Pi AnPW-l + M.PiV+l = ( A n + p*)PN, (1 < N < Tg) KpTq-i + A*Pr,+i = (A„ + H*)pTq KPN-l + PPN+1 = (An + P)PN, (N > Tq) oo £ w v - = 1 (2-2) where PN is the equilibrium probability in state N. The solutions to the above equations are : PN = P?Po, (01) (2.4) Substituting them into (2.2), we get ( T \\ — * 1 + 1 P* (2-5) 1-p, 1 - pn J Therefore, the mean queue length is OO Tq OO AT = 5 > P » = X > * + E n p n n=0 n=0 Tq+l 4 Though p = A//i is used as traffic intensity in queueing theory, there is no such meaning attached to p.. It is only used to simplify the formula. CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 20 n-0 n=Tq+l This expression seems awkward and complex. However, assuming there is extremely high or low real-time work load, or equivalently letting fi» —• 0+ or / i * —• p. respectively, we get the following bounds. Theorem 1 The average delay of non-real-time tasks in QLT is bounded by 1 < € < i - (i-T, + —L-) (2.7) - Pn) K \\Pn 1 - Pn Proof: To prove the right part, as we discussed at the beginning, we will give our system a slower server whenever its queue length is lower than Tq. We will slow it down so that the average queue length in the new system is no less than the original system. More explicitly, for any real-time arrival rate, there exists a scale ratio 1/v (0 < n < 1) such that, if /i» < T7/x, Nm > ~N. Using (2.6) and letting rj —»• 0+, we obtain TV < lim 7V7 = lim 7?7 7J—1-0+ p.—• + CO = — Ti + r^— (2-8) Pn 1 - Pn Applying Little's Law , we get the right half. The left half can be derived simply by letting n = 1. • Discussions: 1. If fi = 1, the difference between our upper-bound and lower-bound is Tq/\\n. So, as A n approaches 1, our bounds estimate the actual value very well. Meanwhile, with smaller threshold Tq, the difference decreases. In fact, when Tq -+ 0, our system becomes M/M/l. 2. More interestingly, (2.8) can be rewritten as + — ) (2.9) Pn \\ (1 - Pn)/ CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 21 Consider pn large (close to 1), the first item is the threshold Tq, and the second item is the mean queue length in an M/M/l queue. This indicates that under heavy load, the non-real-time waiting queue can be viewed as consisting of two pieces. A queue of Tq tasks followed by an M/M/l queueing system. Interpreting (2.7) in the same way, we rewrite (2.7) as - (-rTi + n 1 0 ( 2- 1 0) pn VAn /x(l - pn)} It indicates that under heavy load the waiting time for non-real-time tasks consists of two periods, one to wait for Tq tasks to arrive (j-Tq) and the other to receive service from an M/M/l system ( ^ I ^ ) ) - This agrees with our intuition. 3. Let fj, = 1 and pn = ^ = A n, (2.8) becomes i1 1 — An An 1 — A„ Consider the system as one consisting of two subsystems: the first is a Tq long waiting device and the second is an M/M/l service center. Our rough bounds represent the uncertainty of the delay time in the first device. If a task can pass through it immediately we get the lower bound. In the worst case when a task has to wait for Tq incoming tasks to push itself through, we get the upper-bound. This is of course a rough approximation. The time that a task has to spend in the waiting device is determined by the behavior of the real-time queue. We will take this into consideration below. The inaccuracy resides on the extreme values we take in evaluating (2.6). We can use a better estimation for n other than 0 or 1. One reasonable approximation is 77 = PQ = Pr{realtime queue is empty} « 1 - pr = 1 ~ — (2.12) V-Substituting p* = ^ = ^ into (2.6), we expect to achieve a better estimation. The result is especially good when Xn is small, because the length of the non-real-time queue is unlikely to exceed Tq to interrupt real-time processing. This makes (2.12) accurate. We show this in CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 22 figure 2.3 and figure 2.5. In fact, when An is small (and real-time work load is not too high) the chance for the non-real-time queue length to exceed Tq is very small, then we may even use the following simple approximation: £ « - (1 - p.) = = (2.13) P* P - K - An p - A where A = Ar + A n, is the overall arrival rate. This indicates that non-real-time tasks have to yield to real-time tasks. Therefore our conclusion regarding the average delay of the non-real-time tasks is as follows. For light work load and small A n, QLT's behavior is similar to M/M/l. For heavy work load and large Ar, QLT first makes the non-real-time tasks wait Tq units of time and then treats them as in a separate M/M/l system without real-time work load. For the cases in between, £ will be moderate and determined by Tq, An and A r. We now turn to study the real-time loss ratio in QLT. Noticing the real-time queue is approximately an M/M/l + D + ML system, we can simply use Hong's result in [13] to estimate the loss ratio: e=l- ^J^H (2.14) Ar T To get better result, let 7 r be the throughput of real-time tasks, and P-i e = 1 . 2.2.2 Approximate Analysis of M L T Recall from figure 2.1 that MLT works as follows: M L T : schedule a non-real-time task unless 1. minimum laxity < Tp ; or 2. NRT queue length = 0. Again, the complexity is introduced by the correlation between the two queues. However, MLT policy does not use any non-real-time queue information except whether it is empty or not. To reduce the complexity and obtain a clean solution, we make the following assumption: Assumption: For large A n , Pr{ NRT queue is empty } is negligible in MLT. Note that based on this assumption, the loss ratio we may obtain is an upper-bound of the actual value, because we actually give up some chances when real-time tasks may be served. In other words, as far as real-time tasks are concerned, the server can be considered unavailable when all real-time tasks have laxities larger than Tp. So, our version of MLT is equivalent to: [figure 2.13] • if task ti arrives at time rt- with initial laxity 7rt-, then the execution time e,- must be: ri + ni - Tp < ei < r,- + 7r,-, 7r; > Tp We further assume all tasks have identical initial laxity: 7Tj = 7T, 0 < i < OO CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 24 p Initial Laxity K *j Arrival Time r Ready Time Deadline to Stan Task Figure 2.13: Model Mi We will call this model system Mi. Now we describe another system M2 as follows: • M2 is same as Mi, except: 1. task t{ arrives at time r\\ = r,- + ir — Tp; 2. task ti has initial laxity 7r' = Tp; 3. tasks are scheduled FCFS. We have the following result: Lemma 1 System Mi and M2 are equivalent with regard to the fraction of lost tasks:5 ei = f2 Proof: We prove the lemma in two steps: 1. It is obvious that the FCFS scheduling policy in M2 is equivalent to ML, because all tasks have identical initial laxity value 7r. At any point in time, a task that has arrived earlier has a smaller laxity then those that come after it. Therefore, it is sufficient to prove that Mi is equivalent to a system, say M'2, which is the same as M2 but scheduled in ML instead of FCFS. 5 W e actually obtain a stronger result in the proof that follows. CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 25 2. We achieve this by proving M2 almost exactly simulates Mi'. Suppose we purposely start the M'2 server (w — Tp) later than that of Mi- Then, at instant (z — Tp), Mi and M2 will have identical tasks in their waiting queues and none has processed any task. We claim that Mi and M'2 will have completely identical states. We show this by considering M2 as a pipeline of two systems. The first (i.e., left) is just a delay device with identical input and output, while its right is Mi. Furthermore, the first two conditions of M2 ensure that the output of the left part is the same as the input of Mi. Since the initial state has no influence on the final stationary state, we conclude that, when t —• oo, Mi has identical stationary state as M'2. Thus Mi and M2 have equivalent loss ratio. • Based on Lemma 1, we consider an M/M/l + D + FCFS with arrival rate A and departure rate /i, where D denotes uniform distribution. Let us define F(u,t) to be the distribution function of waiting tasks and F(u>) to be its steady state distribution. F(u,t) = Pr{number of waiting tasks at time t < u) F(u) = lim F(u,t) Let f(u>) be the density function of F(u). The task loss ratio can be computed by: R = R+(l - F(0+)) (2.18) where R+ = Pr{a task is lost \\ server is busy} and -F^O*) is the probability that the server is idle. Following the approaches in [15, 35,16], we can derive the following equation for F(u>, t+At). In general, we have: F(u, t + At) = (1 - XAt)F{u + At, t) + XAt T(l - L(x))B(u - x)dxF(x,t) + Jo XAt f L(x)dxF(x,t) (2.19) Jo CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 26 where L(x) and B(x) are the task laxity and service time distributions respectively. In our case, B(x) is exponential and L(x) is a uniform distribution: ^ 1 otherwise On the right hand side of equation (2.19), the first term is for the case when there is no new arrival from time t to t + At. The second term is for the case when there is a new task arrival and the task is scheduled. The last term is for the case when the newly arrived task is lost. If 0 < u < Tp, (2.19) becomes: F(u, t + At) = (1 - XAt)F(u + At, t) + XAt r B(u - x)dxF(x,t) (2.20) Jo or, F(u,t + A*) - F(u + At,t) At Let At —*• 0, we get: dF(u,t) dF(u,t) = -A (^F(UJ + At,t) - j B(u - x)dxF(x,t)j . =-X^F(u,t) - J B(u- x)dxF(x,t) dt du Let t —• 0, since lim*-^ dF^'^ = 0 and lim^oo dFJ£'^ = f{u>) , we obtain: }{u) = -X (F(U) - jT B(u - x)f(x)dzj (2.21) Considering the fact that B(x) = 1 — e_tiX and B'(x) = pe'^ , and differentiating both sides of (2.21), we have: = (X - fi)dw (2.22) Therefore the solution is, for 0 < u < Tp , /(«) = Ae^~^w (2.23) where A is a constant to be determined. CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 27 When u > Tp, (2.19) becomes, F(u, t + At) = (1 - \\At)F(u> + At, t) + XAt f \" B(u - x)dxF(x,t) + Jo XAt fW dxF(x,t) (2.24) Following similar steps, we have: /(w) = A ^F(w) - j*' B(u - x)f(x)dx - f(x)dxj (2.25) and, dJ£> = X^{u)-j\\e-^f{x)dx-m^ = -fiX fTp' e-^-^ f(x)dx Jo = -fif(u) (2.26) Therefore the solution is, for u> > Tp, f(u) = A'e-^ (2.27) We need three more equations to determine the constants F(0+) , A and A'. The first will be the continuity condition at point u = Tp: l i m /(w) = l i m /(\") w-+Tp+ u>-+Tp-which leads to: f(u) = Ae-^+^P, u>Tp (2.28) The following boundary condition can then be used to solve for A: /•OO fTp TOO / /(w) = F(0+)+ f(u)du;+ f(u)du> JO Jo JTP = F(0+)-r-A(-^—--p-Te-^TA \\fi - A p. - X J = 1 (2.29) CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 28 Hence, A = / ~ F ( Q , + -* , (2.30) The third condition is the flow conservation condition: A = XR + fi(l- F(0+)) (2.31) We then get, Now we are able to compute R+ and R as follows: . l£L(z)f(x)dx f£f{x)dx IT! f(x)dx f$f{x)dx + f%f{x)dx 1 e-(n-\\)Tp Combining (2.18) and (2.32), we have R+ R = p l + pR+ p(l - p)e-(K-VTp 1 _ p2e-(n-\\)Tp The above results are summarized in the following theorem. (2.33) (2.34) Theorem 2 For given minimum laxity threshold Tp, the real-time task loss ratio in M/M/l + D + MLT6 is upper-bounded by e - R ~ 1 - A r V d - V ) T P ( 2 - 3 5 ) 6 This is not a common usage of Kendall's notation. It denotes that the real-time queue is an M/M/l queue. All tasks have a constant laxity, and are scheduled by M L T . CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 29 Proof: Substitute p. = 1 and p = A r into (2.34). The conclusion immediately follows from Lemma 1 and the above discussion. • Figure 2.6 shows an example of how this upper-bound fits the actual value. From (2.35), we can derive the following result. Let Ar —• 1\" , .. _ .. A r ( l - \\ r ) e - ^ T r hm R = hm —f— , ' 1 _ A . e ^ - W hm 1 — 1 (2.36) Tp-2 Corollary 1 The real-time task loss ratio in M/M/l + D + MLT is bounded by q^^, inde-pendent of the arrival rates (when Xr < I). This result, though not fitting the actual values very accurately, explicitly gives system designer a rough idea of the worst case performance bound. In figure 2.8, we can see an example of how this estimates the actual bound. The major shortcoming of this analysis is that we do not take the non-real-time tasks explicitly into account, and the upper-bound fits the true value well only when A n is large. This also prevents us from getting any estimates of the non-real-time task performance. To circumvent this, we take a similar approach to that for QLT. £ is expected to be small when A r is small. We are more interested in how £ grows when A r is very large. Recall that F(0+) in M2 equals the probability that the minimum laxity is below Tp in M\\. Therefore F(0+) represents the probability that the non-real-time tasks will be served. Following an approach similar to that which we used to analyze QLT, we define p, = F(0+) p.. The average delay can be estimated by £ * ,1.(1-p.) = F(0+)! - Xn ( 2 - 3 ? ) Combining (2.33) and (2.32), we have CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 30 then we obtain the following approximation for £. 1 (2.39) Note that when Tp is large, the term p2e~(fi~x)TP approaches 0, so that (2.39) becomes ^ _ x * ) _ \\ n • This indicates that non-real-time tasks have to wait until the real-time queue is empty (note the same result in (2.13)). Before ending this section, we briefly discuss the granularity of control that MLT offers. We first rewrite (2.34) as follows R= *}-p) 2. (2.40) For a given work load, this equation suggests that increasing T p will exponentially decrease R up to a point. Since Tp can only be integral, this implies that MLT offers relatively coarse-grain control in adjusting the loss ratio. Another limitation of MLT is that the maximum value of Tp will be no larger than the maximum laxity. In the case that all tasks have constant laxity, this limits Tp to be below this constant. For the case when laxity is exponentially distributed, this means that increasing Tp will have little effect on the loss ratio when Tp is large. 2.3 Summary In this chapter, the performance of two threshold-based algorithms (QLT and MLT) were analyzed. Though the two thresholds achieve roughly similar performance tradeoffs for constant and identical real-time and non-real-time work loads, they are quite different in the dynamic environment. It has been shown that when the work load is high and the arrival rates change, QLT provides bounded average delay (determined by the arrival rate of the non-real-time tasks and the threshold value) for non-real-time tasks at the cost of real-time task loss. On the other hand, MLT ensures bounded loss ratio (independent of the arrival rates) for real-time tasks at the cost of higher average delay for non-real-time tasks under heavy loads. For both QLT and MLT, we have derived analytical bounds and approximate results of the two major performance metrics, i.e., average delay for non-real-time tasks and loss ratio for real-time tasks, for different CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 31 arrival rates and threshold values. These results were shown to estimate the actual behavior well under most of the interesting conditions. Chapter 3 A d a p t i v e S c h e m e s The analysis of the previous chapter shows that the static schemes QLT and MLT cannot provide satisfactory performance in a dynamic environment. This chapter presents our exploration of the idea of adaptive scheduling based on threshold functions. We first describe two adaptive algorithms and examine how they may be integrated with other heuristics in section 3.1. Then, in section 3.2, we discuss implementation issues relating to threshold functions, monitoring and waiting queues. 3.1 The Algorithms Recall that our main objective is to achieve some degree of guarantee with respect to the loss ratio for real-time tasks even under overloaded system condition, and to minimize the non-real-time task performance penalty especially under normal load. We have seen that static QLT and MLT do not support our objective. However, two thresholds, non-real-time queue length and real-time minimum laxity do provide effective means of tuning the performance tradeoffs for given work load conditions. The problem is that there is no fixed tradeoff point providing acceptable performance under different load conditions. From our observations and analysis in the last chapter, we know how the two thresholds play their roles in determining the performance tradeoffs. Generally, both loss ratio e and average delay E are functions of arrival rates A r , A n and the threshold, Ta or Tp. Therefore, by adjusting the thresholds to correspond 32 CHAPTER 3. ADAPTIVE SCHEMES 33 to varying arrival rates, we may be able to control the system performance at different work loads. 3.1.1 Adaptive QLT Let us look at QLT first. Rewriting (2.17), we get Tq in terms of Ar, An and e: - l (3.1) where p„ = An/p£. This of course only gives a rough estimation for Tq within the region that (2.17) is valid. But nevertheless, it expresses Tq as a function of the work load conditions and the desired performance metric e. Let us denote this function by T(A r, A n, e). Note that T only remains finite over a limited area. For small constant e, 1. T(Ar,0,e) = 0; 2. T(0,An,e) = 0; 3. T is non-decreasing over An ; 4. T is non-decreasing over Ar . Therefore, a simple zero-crossing simulation program is able to compute T. A comparison of our analytic approximation with simulation results is given in figure 3.1. The problem arises when T is infinite. Since the ML scheduling policy used in real-time is optimal, this implies the loss-ratio e requirement is unreachable. A trivial solution is just to set T to be a pre-defined maximum. A more sophisticated approach is to compute the maximum achievable e for different arrival rates, i.e., e(Ar, An) = loss-ratio of the optimal algorithm for arrival rates A r, A n. A system designer may then use this information and specify the required loss-ratio bounds for different load conditions. Finally, T can be computed to satisfy the specification. The adaptive version of QLT works as follows: AQLT: schedule a real-time task unless l o g p . -Pn 1- +1 CHAPTER 3. ADAPTIVE SCHEMES 34 Q L T F u n c t i o n L a m N — O . S Loam — R a t i o — 0 . 0 6 • S i m u l a t i o n - - - - A p p r o x i m a t i o n O.a 0.3 0.4 O.S O.S 0.7 O.S O.B R T a r r i v a l r a t e Figure 3.1: QLT Threshold Function 1. NRT queue length > T ; or 2. RT queue length = 0 . According to our analysis in the last chapter, the average delay of non-real-time tasks will be approximately Tq/Xn larger than the delay in the FCFS queue without real-time tasks, as long as the system remains stationary (pn < 1). For most of the work load range, S will be moderate. A rough estimation can be obtained by substituting (3.1) into (2.6). Finally, we compare the performance of AQLT to QLT in figure 3.2 and 3.3. Note that, in all of our comparisons, the threshold function T can still be tuned better. Meanwhile T can be adjusted to achieve different loss ratio bounds and average delay for different applications. 3.1.2 Adaptive M L T Similarly, Adaptive MLT works as follows: AMLT: schedule a non-real-time task unless 1. RT minimum laxity < T ; or 2. NRT queue length = 0 . CHAPTER 3. ADAPTIVE SCHEMES 35 Q L T : S t a t i c v s A d a p t i v e U m N o O . 8 , L o M - R a t l o s * O . O S S t a t i c T-a - - - - • A d a p t l v a 33 0.4O Figure 3.2: Loss Ratio: AQLT vs QLT Q L T : S t a t i c v s A d a p t i v e L a m N o O . 0 . L o » « - R « t i o = O . O S S t a t i c T - 6 A d a p t l v a i 0.1O O.CO O.KO 0.30 R T a r r i v a l r a t e Figure 3.3: Average Delay: AQLT vs QLT CHAPTER 3. ADAPTIVE SCHEMES 36 Rewriting (2.35), we get T for AMLT: 1-A r V A r ( l - ( l - e ) A r ) e (3.2) Note that this gives an upper-bound for T. The actual value of T can also be computed by simulation. We show this in figure 3.4. M L T F u n c t i o n L a m N = O . e 1 L o i « - R a t i o O.Oft ~ L o « a — R a t i o — O . O l - - - - U p p e r — B o u n d O O O.I 0.3 0.3 0 . « O.B O.A O.T 0 .0 0 .9 I.O R T a r r i v a l r a t e Figure 3.4: MLT Threshold Function Substituting T into (2.39), we can estimate the average delay for the non-real-time tasks 1 J£-Ar_ (3.3) (xr(l-(l-<:)\\r)) Our result shows that E remains small until the system load approaches saturation. Figures 3.5 and 3.6 compare the performance of A M L T and MLT. 3.1.3 Integration and Other Heuristics Recall that QLT generally gives bounded average delay for the non-real-time tasks but fails to ensure good real-time task performance in the presence of high non-real-time load. On the contrary, MLT ensures bounded loss-ratio for the real-time tasks, but to do this, its threshold CHAPTER 3. ADAPTIVE SCHEMES 37 M L T : S t a t i c v s A d a p t i v e L a m N = 0 . f l , L o s s — R a t l o = O . O S 5 - S t a t i c T=«4 - - - - A d a p t i v e o ° • • • ' r ' • • • i • • a o.i o.a 0.3 o« oo o.a o.-r o.a R T a r r i v a l r a t e o.e 1.0 Figure 3.5: Loss Ratio: A M L T vs MLT M L T : S t a t i c v s A d a p t i v e i -I-U m N B D,a. Loss—RatiosO.OS SUUO T—4 - - - • Ad»ptiv« 1^ Del 1-Avera] Avera] s-o o. i o.s 0.3 o.* O . B o.a O . T o.a R T a r r i v a l r a t e O.B Figure 3.6: Average Delay: A M L T vs MLT CHAPTER 3. ADAPTIVE SCHEMES 38 has to be raised so high that it will unnecessarily impose a high delay penalty on the non-real-time tasks. Besides the problem associated with changing arrival rates, another problem causing difficulty in making suitable performance tradeoff is that each of the two thresholds is directly related to only one of the two waiting queues. It is difficult to select the proper value of the threshold to achieve desired performance for both queues. To tackle this issue, we observe that QLT provides satisfactory non-real-time performance under normal work loads, and MLT can provide loss-ratio bound for the real-time tasks under heavy work loads. Therefore, by combining the two algorithms it may be possible to derive a new algorithm which will behave like QLT under light loads and like MLT under heavy loads. A simple way to do this is as follows. We employ two thresholds, Tp and Tq. Both are actually functions of A r and A n . The algorithm will normally run as QLT but it will process a real-time task if the minimum laxity in the real-time queue is below the threshold Tp, i.e. MLT takes precedence over QLT. Note that the values of the two thresholds obviously will not be the same as they are used individually. This integrated version of the threshold based scheduling policy will have good performance for non-real-time tasks like QLT at normal loads but still manage to ensure reasonable loss-ratio level as does MLT. To understand how this works, let us look at some extreme cases. When Tp = 0, it schedules like QLT except if a real-time task is due immediately. It is obvious that this integrated version will be better than pure QLT. If A r is relatively large, we may expect Tp = 1 serving the same purpose better. Therefore Tp can be viewed as representing the urgency of the real-time tasks. The basic idea behind this is to multiplex limited resources between the real-time and non-real-time tasks more wisely. Resources should be devoted to the real-time tasks only when they reach a certain urgency. The minimum laxity of the real-time tasks is one indication of such urgency. Our result shows that this simple heuristic works well. Another indication of urgency is a long continuous real-time task train. Because of the bursty nature of most computing activity, this type of traffic is not unusual. A laxity threshold, however, is not good at dealing with such situations. It requires certain global information and look-ahead capability to solve this kind of problem. In the extreme case, if we have full information about the future, we can CHAPTER 3. ADAPTIVE SCHEMES 39 achieve optimal scheduling. In realty, all we know is the information on tasks in the waiting queue and what we can use is limited to a small portion of it due to the run time overhead. However, the following two simple heuristics may help: 1. Instead of using the minimum laxity of all real-time tasks, we take the sum of the two smallest laxities of the real-time tasks. We will service real-time tasks if this sum is below twice Tp. If Tp = 1, one of the two tasks that arrived at the same time would be lost in the original algorithm. This simple heuristic prevents such a loss because these two tasks will be detected two units of time ahead of their deadline. Generally, we can take the sum of k minimum laxities. If the queue is organized in order of increasing minimum laxity first, we only need to take the sum of the laxities of the first k tasks. 2. Similar to the idea of queue length threshold for the non-real-time tasks, we may organize the real-time queue into two subqueues. Incoming tasks will enter the first queue in the order of laxity. The first task in the first queue will be placed at the tail of the second queue when its laxity goes below some threshold T\\. We then compare the queue length of the second queue to another threshold T2. If the length exceeds T2, the urgency of real-time tasks is indicated. This heuristic works similarly to the previous one except we now count in another domain, queue length instead of laxity. Note that these heuristics will ease the problem of continuous loss. These two strategies work similarly in general cases, but the first one is simpler and more efficient to implement. In the next chapter, we will evaluate the performance of the integrated adaptive scheme without using any of these heuristics. A rough estimation of the performance achieved by this integrated policy (ADP) can be obtained by applying the results of chapter 2. When A n is large, ADP is similar to MLT. Then e is bounded as (2.35) indicates and £ can be estimated by (2.39). Note that (2.35) fits the true value well for large A n . Similarly, when A r is small, ADP resembles QLT. The discussion in section 2.2.1 provides equations for a rough estimation. So ADP ensures bounded loss ratio for the real-time tasks even when the non-real-time load is high, and provides similar average CHAPTER 3. ADAPTIVE SCHEMES 40 delay for the non-real-time tasks as QLT when the real-time load is light. Unfortunately, the values of the two thresholds cannot be derived independently. In fact, for given a performance requirement, the corresponding threshold values may not be unique. We will use simulation results in the next chapter for performance evaluation. 3.2 Implementation Related Issues 3.2.1 Threshold Functions Given a constant e that we wish to achieve, T can be plotted as a plane over (Ar, An). T is almost a simple step function of small values when Ar + An < 1. Depending on the requirements of the applications, the following methods may be used to implement the threshold function: 1. Analytic Approximation: The estimation or bounding results derived in the last chapter may satisfy some applications. Of course, T can be pre-computed to avoid the time required to compute those functions in real time. 2. Numerical Approximation: We can also estimate T by numerical fitting methods. Let us take QLT as an example. Let e = 0.05. After computing T numerically or by simulation, we can plot a series of isograms for different T\"s [figure 3.7]. From these isograms, we may conjecture that there is a function /(T, Ar) so that Ar + An + f(T,Xr) = 1. Our further study shows that the following formula may provide satisfactory estimation: where KQ,K and c are parameters to be determined experimentally. 3. Look-up Tables: A more practical method is to compute T by simulation or actual mea-surement. The result then can be stored in a look-up table. Since T is roughly a step function, it can be stored and retrieved very efficiently. (3.4) CHAPTER 3. ADAPTIVE SCHEMES 41 T h r e s h o l d C o n t o u r S 3 o.o 0.1 o.s 0.3 0.« 0.8 o.a 0.9 L a m R Figure 3.7: QLT Threshold Isogram 3.2.2 Run-time Monitoring Assuming the threshold function has been obtained, the next problem is how to monitor or measure the system work load. Noting that our system is a predicting control system [figure 3.8], we face a trade-off between accuracy and stability . This can be explained as follows. In a discrete and time-sharing environment the controller has to share the only processor with the server and the monitor, thus arrival rate monitoring can only be done periodically. Consequently control decisions are also made periodically. This period has to be relatively large Queueing System Figure 3.8: Monitor and Controller CHAPTER 3. ADAPTIVE SCHEMES 42 to make the scheduling process feasible. Note the following formula defines all rate quantities, where W is the number of events that occurred during time interval T. Now we have two possible approaches to measure A. If we set T constant, then the meter will count events and reset itself at the end of each time interval T. If the system has a low resolution timer but high rate of events, this event frequency approach produces better accuracy. On the other hand, we may set W to be constant. The meter then reports the time interval for every W events. Time interval monitoring is better when event frequency is low and the system has a relatively high resolution timer. [20] discussed a similar problem arising in a software feedback adaptive scheduling system. This also raises the problem of choosing a predicting or a feedback scheme. A predicting system applies input information to control, while a feedback system uses output information for control. In our case, we may also monitor loss ratio or average delay and compare them to some threshold to make scheduling decisions. It is however more difficult to analyze such a system. Furthermore, the feedback system is more vulnerable to the lagging effect discussed below. Accurate measurement of arrival rates is not sufficient. Another problem to be considered is the Lagging Effect existing in the system. Since the queueing system has a non-uniform time latency, the monitored load condition at the input stream does not necessarily match the situation faced by the server. If control is applied out of phase, it can actually magnify the effect it was designed to reduce [2]. The worst case occurs when the arrivals are wavelike and the monitor happens to lag behind a half period [figure 3.9]. More losses will occur than when there is no control at all. This is a disastrous situation that has to be prevented. The solution is to sacrifice accuracy to achieve better stability . If we set the monitoring period (W or T, whichever is applicable) long, we lose information on small variations but obtain better estimation in the global term. The worst case scenario will have a much smaller chance of occurring. On the other hand, if this period is too long, we will lose control significantly. Therefore, this is a tradeoff we have to make according to the nature of the application. CHAPTER 3. ADAPTWE SCHEMES 43 Server Load Monitor Signal Time Figure 3.9: Lagging Effect Generally, this tradeoff should be made according to the pattern of Ar. Let us assume that A r changes moderately at most times but dramatically in short periods from time to time. By considering specific applications, the system designer may know what is the shortest peak period that the system is designed to resist. Let the length of such period (either in time unit or in number of events) be to, and the length of the monitoring period be To. The worst case is when each of two continuous monitoring periods covers a half of a small pulse [figure3.10]. Then the measured value is b = ^ Jo2'0 f(x — xo)dx . This b is used to match the left side of the threshold function look-up table (A r[t], T[i]) , where T is T p or T,. A simple rule to determine To is: 6 should be large enough so that it matches the proper table item. This also directly depends on the fine-grainess of the threshold function table. If this table has many records, To should be smaller, and vice versa. More explicitly, let the error be Since S is a function of To, this gives us a means to select the proper value of To that satisfies (3.5). A rough estimation following this principle may be sufficient in practice. Note that this problem is just an instance of a common existing problem in many areas, e.g. to determine the size of a signal filter. This is an ill-posed problem because there is no clear definition of what is best. Another example is the filter used to eliminate noise in an image. There is no explicit difference between noise and data. If the filter size is too large, a lot of then the condition of accurate measurement is, for all i, *<\\\\K[i+l]-\\r\\i]\\ (3.5) CHAPTER 3. ADAPTIVE SCHEMES 44 Figure 3.10: Monitoring Period noise will remain. If the filter is too small, we take the risk of losing data along with the noise. Since we can only determine what is noise case by case, the solution to this problem relies on the specific semantics of the individual applications. 3.2.3 Real-Time Queue Implementation The complexity of the waiting queue implementation is another major issue. A sorted queue for ML requires O(n) time complexity for practical use1. In [23, 9], an efficient approximate scheme ML(n) is studied. ML(n) separates the waiting queue into two parts. Tasks enter an FCFS queue first and then enter a sorted queue with constant length n for service. By setting the constant n appropriately, this effectively reduces the time complexity to a small constant while still retaining performance competitive with ML. This scheme will work well if we can assume that later arriving tasks have larger laxity, otherwise we risk the possibility that an urgent task in the FCFS queue will be lost. Another way to reduce the complexity is to organize the waiting queue into an array of n subqueues. The ith subqueue holds tasks with laxities ranging from Z t _i to Li should be denned so that the average length of each subqueue will be approximately equal. Within each subqueue, a simple sorting algorithm can be used. If n is large enough so that the number of 1 0 ( log(n)) can be achieved by using a tree data structure. However, this does not appear to be efficient when n is small . CHAPTER 3. ADAPTIVE SCHEMES 45 tasks in each subqueue is very small, a nearly constant time is sufficient to sort the subqueue. In some processors, like the MC68020, only one instruction is needed to select the first non-empty subqueue. This reduces the total complexity to nearly constant. Note that this is actually a simple case of using a tree data structure. Though not exactly constant, it may be good enough in practise. 3.3 Summary In this chapter, two adaptive threshold-based schemes (AQLT and AMLT) were proposed. They are different from their static counterparts in that the thresholds in the adaptive schemes change as the arrival rates vary. We have shown that by setting the threshold functions properly the adaptive schemes can achieve bounded loss ratio for real-time tasks and lower average delay for non-real-times than the static schemes in the dynamic environment. The threshold values can be calculated by approximate formulas or by simulation. A new scheme (ADP) integrating AQLT and A M L T was then proposed to achieve better performance tradeoffs. ADP has good performance for non-real-time tasks like QLT at normal loads but still manage to ensure reasonable loss ratio levels as MLT does. Issues related to the implementation of the threshold functions, load monitor and waiting queue were also discussed. Chapter 4 P e r f o r m a n c e E v a l u a t i o n In this chapter, we evaluate the performance of our new scheduling algorithm (ADP) described in chapter 3 by comparing it with some other standard algorithms. The performance metrics that will be used are defined in section 4.1, the various algorithms to be compared are described in section 4.2. Section 4.3 briefly introduces our simulator. Section 4.4 presents the evaluation results along with brief discussions and section 4.5 summarizes the chapter. 4.1 Performance Characteristics Two performance metrics are of interest for systems that handle both real-time and non-real-time tasks. The major metric for real-time tasks is loss ratio defined as the fraction of lost tasks, i.e. those that do not meet their deadlines, over the total number of tasks. Non-real-time tasks will not be 'lost' but may not receive immediate service when they arrive. For these tasks, the main concern is the average delay . This delay includes the queue waiting time and the processing time. To evaluate the various scheduling algorithms, we need to define other work-load and system parameters of the queueing system. These parameters include the distribution of incoming tasks, the distribution of service times, and the distribution of laxity values for real-time tasks. A common assumption is to let all of these be exponentially distributed. We will compare the performance of the scheduling algorithms under different assumptions. Other distributions like uniform, geometric, combination of uniform and exponential, and train model 46 CHAPTER 4. PERFORMANCE EVALUATION 47 will also be used to evaluate the robustness of the various algorithms. Besides the stationary behavior of the system, we would also like to investigate the system performance in the transient state when it is congested. 4.2 Algorithms Under Comparison The algorithms that are going to be compared to our adaptive algorithm are introduced in this section. These algorithms include First Come First Serve (FCFS), Static Priority (SP), Minimum Laxity First/Earliest Deadline First (ML/EDF) , and Stanford Optimal (OPT). We describe each of the above algorithms in this section. • FCFS: This policy serves tasks in the order of their arrivals without using any timing information. • SP: This policy schedules tasks in the order of their priorities . Among tasks with the same priority, FCFS will be used. There are two levels of priorities in our case. Real-time tasks have higher priority than non-real-time tasks. Besides priority, SP knows no other timing information. • ML: Each real-time task will be associated with a latest time to start , i.e. laxity. The task with minimum laxity will be scheduled first. If a task cannot be scheduled by this time, it is lost and will not be serviced at all. This algorithm has been shown to be optimal in reducing loss ratio under certain conditions [25]. • EDF: EDF is similar to ML. The difference is that here we have a latest time to finish, i.e., deadline , associated with each real-time task. Tasks are scheduled in order of their deadlines. A task unable to finish by the deadline is considered lost. Since the scheduler can determine whether a task can make its deadline right before it is about to start the task, lost tasks can be simply dropped without receiving any service. This version of EDF is also proven to be optimal in minimizing the loss ratio [25]. Also note that EDF is equivalent to ML if all tasks have identical laxity. CHAPTER 4. PERFORMANCE EVALUATION 48 • OPT: OPT is an optimal algorithm introduced in [26]. It schedules both real-time and non-real-time tasks. It is optimal in the sense that it minimizes the loss ratio of real-time tasks and at the same time, among all such schedules, it minimizes the average delay of non-real-time tasks. Therefore this algorithm distinguishes between real-time and non-real-time tasks. It first guarantees real-time task performance, then provides the best possible delay performance for non-real-time tasks. The algorithm assumes complete knowledge of all future tasks. Therefore, it is not motivated for practical use. However, it provides a bound for best possible performance and serves as a standard for comparison. We use a special case of the original general algorithm, with two classes of tasks and equal weight within the same class. The readers are referred to [26] for a detailed description. Though its complexity has been reduced to 0(n2), the algorithm is still extremely slow especially for congested arrival and large laxities. It can take hours on a fast workstation to produce a single point on the performance graph. 4 . 3 The Simulator The study is carried out by simulation. Our simulator is of the type whose structure resembles that of the real system to be evaluated. Figure 4.1 shows the structure of the simulator. The arrival processes, and all timing properties of the tasks are modeled using independent random number generators. Different random distributions are generated using the UNIX utility randomO, which uses a non-linear additive feedback random number generator producing pseudo-random numbers with a period approximately 16 x (23 1 — 1). A logical timer is used in the simulator. Incoming tasks enter a waiting queue if they are not immediately scheduled upon arrival. This waiting queue is organized into two different subqueues for some algorithms. For example, in ADP, there is a real-time subqueue sorted in the order of laxities and a subqueue for the non-real-time tasks organized in FCFS. At each time unit, the scheduler looks at the two queues and schedules or drops tasks according to its scheduling policy. All tasks that leave the server, with or without receiving service, will pass through an output module that collects CHAPTER 4. PERFORMANCE EVALUATION 49 and reports needed information. tasks Task 1 task batch waiting queue completed Server/ \\ lost Scheduler Report Generator. (12:03:14) logical timer output Figure 4.1: The Simulator Each point in the graph was obtained from a simulation experiment with a duration equal to 10,000 units of time. Al l tasks are considered non-preemptive . The simulator was validated by checking through complete output lists of some simple examples, and by comparing to other published results. The main part of the simulator (except for the scheduling policies) is also validated by comparing the simulation outputs to the exact analytic results for some simple scheduling disciplines, e.g. FCFS and SP. 4.4 Performance Comparisons Our first set of comparisons evaluate the performance of the above scheduling policies under the following conditions. Al l tasks are of constant service time equal to one unit. Real and non-real-time task arrivals constitute two Poisson processes of rates A r and A n respectively, normalized by service time, i.e., in tasks/unit. We assume a task's laxity upon arrival to be s — B, where s is a constant and B is an exponentially distributed random variable, conditioned on 5 - B > 0. Figures 4.2 and 4.3 compare performance of the various algorithms under a constant total work load, p = A r + A„ = 0.9. A very simple Tq function (a function of A r only) and constant Tp = 7 are used in ADP. We observe that both the loss ratio and mean delay increase as the CHAPTER 4. PERFORMANCE EVALUATION 50 percentage of real-time tasks grows, with the exception that the average delay in OPT and ADP actually decrease slightly with respect to A r when Xr is small (< 0.2). This is because when a small number of real-time tasks are not near their deadlines, there is a chance that the real-time tasks can be delayed in favor of the non-real-time tasks. Using the simple settings of the threshold values, ADP achieves satisfactory loss ratio (< 0.05) and better mean delay than ML. Note that ML is optimal with regard to loss ratio in this case. We set the laxity of non-real-time tasks to be infinity for ML. While ADP does well in loss ratio performance, the mean delay in ADP is closer to that of SP and ML than that of OPT or FCFS. Of course ADP can achieve better mean delay by adjusting the threshold values, but a more important feature of ADP shown in figure 4.4 promises much better mean delay performance for larger laxities. Figure 4.4 shows that the mean delay achieved by OPT and ADP decreases significantly as the laxity increases. This is because with large laxity, OPT and ADP have greater flexibility in multiplexing the processor between real-time and non-real-time tasks. Under that circumstance, non-real-time tasks have more opportunity to get priority over real-time tasks. However, laxity is irrelevant for SP and FCFS since they do not use this information at all. ML is even worse in that mean delay slightly increases (though not significantly) with laxity because fewer real-time tasks are dropped with larger laxity. As laxity goes to infinity, ML has the same mean delay as SP because no real-time tasks are dropped. By deferring service for real-time tasks until their laxities have become small, we can greatly improve the performance of non-real-time tasks. We conclude that, for larger laxity tasks, the mean delay produced by ADP is close to that of OPT and much better than that of ML. This is shown in figure 4.5. The average delay achieved by ADP is clearly close to OPT and 3 to 5 times better than that of SP and ML until the arrival rate of the real-time tasks becomes high (> 0.75). Even with high real-time load, ADP still achieves much lower average delay than SP and ML. More importantly, for most regions when the real-time load is not very high, ADP performs significantly better than FCFS in average delay. This is again because ADP is able to speed up non-real-time tasks by holding real-time tasks until their laxities become small. Also note that the loss ratio for ADP is bounded below e = 0.05, which is much lower than that of SP and FCFS. This is a desirable property and one CHAPTER 4. PERFORMANCE EVALUATION 51 that we would like to see from a good scheduling algorithm, i.e. to ensure an upper bound for loss ratio even under high load and keep average delay down for most work load conditions. L a m R + L a m N = 0 . 9 o.o o . i D.S o.a o.« o.a o.o 0.7 O.B o.e i . o R T A r r i v a l R a t e Figure 4.2: Loss Ratio: with constant total work load Figure 4.3: Average Delay: with constant total work load The next set of simulation experiments compare the performance of the scheduling policies during congested and overloaded periods. For transient states of the system, we are interested CHAPTER 4. PERFORMANCE EVALUATION 52 E f f e c t o f L a x i t y U m R > O . S , U m N n O . 4 S P • - ^ U L cg CD Q Mean-. . . . - F C F S — — O P T 10 i s ao L a x i t y 3» Figure 4.4: Average Delay vs Laxity Figure 4.5: Average Delay: with constant total work load (large laxity) CHAPTER 4. PERFORMANCE EVALUATION 53 in the values as well as the rate of increase of the performance metrics in a fixed period of congestion. In our simulation experiments, this period is set to be 10,000 time units. Figures 4.6 and 4.7 show the loss ratio and average delay when A n = 0.2. Again, Tq is set to be a function of A r and Tp is kept constant (at 7). We observe that ADP has near optimal loss ratio and significantly smaller average delay than both ML and OPT. The rate of increase of the non-real-time average delay over A r is linear for all policies. But for real-time task loss ratio, FCFS and SP perform very poorly with a dramatic increase beyond certain points. Figures 4.8 and 4.9 show the same thing for larger laxity (5 = 40). In this case, ADP offers much smaller average delay in the overloaded region with a moderately small loss ratio. Though OPT and ML can achieve near zero loss ratio, their performance with respect to non-real-time tasks are significantly worse than ADP. For applications that can tolerate certain task loss, ADP is preferred. Note that ADP can even achieve lower average delay than FCFS over some load conditions because ADP not only drops a few real-time tasks but also gives priority to the non-real-time tasks whenever possible. When the real-time load is relatively low, this may make the performance of non-real-time tasks in ADP better than in FCFS. 8 -o ° • la C/i ° ' o S -C o n g e s t e d P e r i o d P e r f o r m a n c e F C F S L a f f l N — o.a L a x — O, B MM 3 • S P 8 o. J O o o a o . so o . a s a . T O O . T S o .eo o .es o .ao R T A r r i v a l R a t e Figure 4.6: Loss Ratio in Overloaded System We now look at a small case of performance achieved by the different scheduling algorithms. CHAPTER 4. PERFORMANCE EVALUATION 54 C o n g e s t e d P e r i o d . P e r f o r m a n c e o.ao 0.81 o.aa o.ea 0.8* o.ea o.se 0.07 o.se o.se o.eo R T A r r i v a l R a t e Figure 4.7: Average Delay in Overloaded System C o n g e s t e d P e r i o d P e r f o r m a n c e U x — +0. B — *0/3 *3-'o.SO O.BB> O.0O D.BB 0 .70 0.7(4 O.BO D.BB O.SO R T A r r i v a l R a t e Figure 4.8: Loss Ratio in Overloaded System (large laxity) CHAPTER 4. PERFORMANCE EVALUATION 55 C o n g e s t e d P e r i o d P e r f o r m a n c e ' H 1 1—' 1 1 1 1 1 i 1 1 o.ao o 81 o.as o.sa o.a* o.ao o.as o.a? o.aa o.ao o.oo R T A r r i v a l R a t e Figure 4.9: Average Delay in Overloaded System (large laxity) The simple threshold function used in ADP is shown in Table 4.1. The non-real-time task arrival rate A n is set to be constant at 0.4. The average delay of the non-real-time tasks and the real-time task loss ratio are listed in Tables 4.2 and 4.3. We can see that a very simple (therefore not expensive to implement) threshold function can achieve fairly good performance. (Note that the loss ratio bound e for ADP is set to be constant at 0.03.) Note that we are using very simple threshold functions throughout all experiments. This is because, with the timing granularity in our experiments, a simple threshold function has already obtained most benefits. We expect this to be true for most applications. Generally, more fine-grain timing in an application requires more complicated threshold functions. K 0.1 - 0.4 0.5 0.6 1 2 8 0 0 13 Table 4.1: Threshold Functions (LamN = 0.4) Finally, we examine the robustness of ADP by comparing the performance of ADP under different arrival distributions and laxities. CHAPTER 4. PERFORMANCE EVALUATION 56 K 0.1 0.2 0.3 0.4 0.5 0.6 FCFS 1.52 1.79 2.28 2.86 5.13 69.25 SP 1.57 1.98 2.88 4.09 9.30 169.87 ML 1.57 1.98 2.88 4.09 9.26 165.12 OPT 1.33 1.34 1.36 1.37 1.42 128.93 ADP 1.33 1.34 1.35 1.37 1.39 28.01 Table 4.2: NRT Average Delay (LamN = 0.4) A r 0.1 0.2 0.3 0.4 0.5 0.6 FCFS 0.01 0.01 0.02 0.03 0.06 0.83 SP 0.002 0.003 0.008 0.010 0.017 0.021 ML 0.0 0.0 0.0004 0.0005 0.0006 0.0007 OPT 0.0 0.0 0.0004 0.0005 0.0006 0.0007 ADP 0.001 0.002 0.01 0.016 0.030 0.030 Table 4.3: RT Loss Ratio (LamN = 0.4) We first compare the performance of ADP for four different arrival distributions: exponen-tial, geometric, uniform and train model. In the train model, tasks come in continuous bunches like a train. At any time slot, a train may appear with a constant probability. Al l trains are of fixed length L. We adjust the parameters of the above distributions to make their mean arrival rate identical. We observe little variation of loss ratio over most regions until the system is saturated, (figure 4.10). On the other hand, figure 4.11 shows that the average delay is quite different for different distributions. Our conclusion is that ADP performs better if arrivals come with higher randomness. For the train model with length L — 5, ADP has worst average delay and loss ratio compared to the other arrival distributions. In the overloaded region, however, the average delay has little variation (figure 4.12). To see how the other scheduling policies perform, we also let them take on train-like arrivals. Figure 4.13 shows that ADP is much better than the others. CHAPTER 4. PERFORMANCE EVALUATION 57 Since laxity has a great deal to do with the advantage that ADP can have, we compare ADP's performance under different arrival distributions and laxities. We see from figure 4.14 that there are similar decreases in mean delay for all arrival distributions. Note also that in the case of train model and geometric distributions, there is a slight increase in mean delay when laxity is small. This is because, like ML, fewer real-time tasks will be dropped as laxity increases. 4.5 Summary In summary, ADP is a flexible way of scheduling a mixture of real-time and non-real-time tasks. It offers the system designer explicit tradeoff choices depending on the needs of the applications. We found that ADP provides satisfactory performance trade-off under widely varied conditions. For most cases, it offers bounded loss ratio for real-time tasks and significantly lower average delay for non-real-time tasks compared to the other common policies. A r r i v a l D i s t r i b u t i o n s 8 _, o.a e. MLT 2 o Vi o R T A r r i v a l R a t e Figure 4.10: Loss Ratio: For Different Arrival Distributions (e < 0.05) CHAPTER 4. PERFORMANCE EVALUATION 58 A r r i v a l D i s t r i b u t i o n s U m N = o.e L a x = 0. MLT a 2 T r a i n L e n g t h •* S , _, , r , , , , , , , r- r- , 1 , 1 , , o.oo o .oa o . o* o o o O . O B a . I O o . i s o . i * o . i s o . i s o.ao R T A r r i v a l R a t e Figure 4.11: Average Delay: For Different Arrival Distributions Figure 4.12: Average Delay: For Different Arrival Distributions (overloaded region) CHAPTER 4. PERFORMANCE EVALUATION 59 E f f e c t o f T r a i n L e n g t h 8 • SP EDF 8-j UimRaO.S. LamNaO.4 / S-. e-. ; ca 8 -CD 1 s-i B ca