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, /<?» DE-6 (2/88) Abstract 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 corre-sponding 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 com-mon 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. ii Acknowledgements I would like to thank Dr. Samuel T. Chanson, my thesis supervisor, for his guidance and encouragement throughout my work on this thesis. The discussion between us improved the content and presentation of this thesis significantly. I would also like to thank Dr. Norman Hutchinson for reading through the draft of this thesis, his comments and his help in system kernels. Many thanks go to the graduate students of the Department of Computer Science, especially Ann Lo, Luping Liang, Ying Zhang and Francis Liang. I thank Scott Ralph and George Phillips for their help in PostScript. This work was partly supported by a University Graduate Fellowship from the University of British Columbia. Finally, I wish to thank my parents and my lovely Wei. They have been an endless source of encouragement. iii Contents Abstract i i Acknowledgement i i i Contents iv List of Tables v i List of Figures v i i 1 Introduction 1 1.1 The Problem and Motivations 1 1.1.1 The Problem 1 1.1.2 Goals 4 1.2 Related Work 5 1.3 Overview 7 2 Analysis of QLT and M L T Scheduling 8 2.1 Static Threshold-based Algorithms 8 2.2 Approximate Analysis of QLT and MLT 12 2.2.1 Approximate Analysis of QLT 18 2.2.2 Approximate Analysis of MLT 23 2.3 Summary 30 3 Adaptive Schemes 32 3.1 The Algorithms 32 3.1.1 Adaptive QLT 33 3.1.2 Adaptive MLT 34 3.1.3 Integration and Other Heuristics 36 3.2 Implementation Related Issues 40 3.2.1 Threshold Functions 40 3.2.2 Run-time Monitoring 41 iv 3.2.3 Real-Time Queue Implementation 44 3.3 Summary 45 4 Performance Evaluation 46 4.1 Performance Characteristics 46 4.2 Algorithms Under Comparison 47 4.3 The Simulator 48 4.4 Performance Comparisons 49 4.5 Summary 57 5 Conclusion and Future Work 60 5.1 Future Work 61 v List of Tables 4.1 Threshold Functions (LamN = 0.4) 55 4.2 NRT Average Delay (LamN = 0.4) 56 4.3 RT Loss Ratio (LamN = 0.4) 56 vi List of Figures 2.1 Static Threshold-based Model 10 2.2 QLT Loss Ratio: with Varied RT Arrival Rates 13 2.3 QLT Average Delay: with Varied RT Arrival Rates 13 2.4 QLT Loss Ratio: with Varied NRT Arrival Rates 14 2.5 QLT Average Delay: with Varied NRT Arrival Rates 14 2.6 MLT Loss Ratio: with Varied RT Arrival Rates 15 2.7 MLT Average Delay: with Varied RT Arrival Rates 15 2.8 MLT Loss Ratio: with Varied NRT Arrival Rates 16 2.9 MLT Average Delay: with Varied NRT Arrival Rates 16 2.10 Loss Ratio: Effect of Queue Length Threshold 17 2.11 Average Delay: Effect of Queue Length Threshold 17 2.12 QLT: Non-Real-Time state transition rate diagram (A = An) 18 2.13 Model Mi 24 3.1 QLT Threshold Function 34 3.2 Loss Ratio: AQLT vs QLT 35 3.3 Average Delay: AQLT vs QLT 35 3.4 MLT Threshold Function 36 3.5 Loss Ratio: AMLT vs MLT 37 3.6 Average Delay: AMLT vs MLT 37 3.7 QLT Threshold Isogram 41 3.8 Monitor and Controller 41 3.9 Lagging Effect 43 3.10 Monitoring Period 44 4.1 The Simulator 49 4.2 Loss Ratio: with constant total work load 51 4.3 Average Delay: with constant total work load 51 4.4 Average Delay vs Laxity 52 4.5 Average Delay: with constant total work load (large laxity) 52 4.6 Loss Ratio in Overloaded System : 53 4.7 Average Delay in Overloaded System 54 vii 4.8 Loss Ratio in Overloaded System (large laxity) ,. 54 4.9 Average Delay in Overloaded System (large laxity) 55 4.10 Loss Ratio: For Different Arrival Distributions (e < 0.05) 57 4.11 Average Delay: For Different Arrival Distributions 58 4.12 Average Delay: For Different Arrival Distributions (overloaded region) 58 4.13 Effect of Train Length 59 4.14 Effect of Laxity: For Different Arrival Distributions 59 viii Chapter 1 Introduction This research is motivated by the scheduling problems we encounter in designing an operating system kernel to support real-time communications. The particular applications that this kernel is going to support are distributed multi-media processing in a general purpose timesharing environment, such as voice and digital audio/video, which requires both time-critical and non-time-critical computation and communication. In this chapter, we first describe the problem, then briefly review related work in this area, and finally close this chapter with a thesis overview. 1.1 The Problem and Motivations This thesis is motivated by the performance problems encountered in supporting both time sensitive and other usual activities in a general purpose computing environment. We are interested not only in satisfying the time constraints of the real-time jobs but also in ensuring the overall system performance, especially minimizing the average delay or response time of the regular tasks. 1.1.1 The Problem Most real-time system research focuses mainly on meeting strict time constraints in a predictable way [32]. Typical examples of such applications include process control plants, aircraft and space shuttle control systems and robotics. However, with the advent of the new generation of workstations and high-speed networks providing diverse integrated services, more and more time 1 CHAPTER 1. INTRODUCTION 2 sensitive applications are run on general purpose systems. This brings increasing importance to studying scheduling policies for computer and communication systems which process/transmit both real-time and non-real-time tasks/data. A system is called a real-time system if its correctness depends on not only its logical output but also the time when the output value becomes available. A real-time task can be characterized by a few time parameters. Arrival time of a real-time task is the time when it becomes available to be scheduled for service. Either a deadline or laxity can be used to express the time urgency of a task. Deadline is the latest time a task should be completed before it is considered lost , while laxity is the time interval from the current time to the latest time a task should be started if it is to meet its deadline. The initial laxity of a task is the time interval from its arrival time to the latest time it should be started. The laxity of a real-time task deceases as the time passes. A task is lost when its laxity becomes negative. A lost real-time task may be useless or of little use. In the former case, it can be simply discarded. The main objective of real-time system is predicatability of its temporal behavior, i.e., to ensure that the system will meet the time requirements of its specification, or to ensure it will do so with a bounded high probability. The most important technique to achieve timing predicatability is real-time scheduling , i.e., assigning system resources to processes taking their timing constraints into account. Two most important performance metrics of real-time system are loss ratio and guarantee ratio : , number o f lost jobs loss ratio = - — number of total arrivals number of accepted jobs guarantee ratio = ; ; ———— number of acceptable jobs A real-time scheduling algorithm is often called optimal in two senses. One is if its guar-antee ratio is 1, i.e., it can find a feasible schedule whenever such schedule exists. Algorithms like rate monotonic 1 [19], earliest deadline first (EDF) [21] and minimum laxity first (ML) 1 Rate monotonic assigns static priority to periodic processes according to their rates. Processes with higher rate get higher priority. It is optimal only among all static priority schemes. CHAPTER 1. INTRODUCTION 3 [21] are shown to be optimal in this sense. However, in designing real-time systems, we are par-ticularly interested in minimizing the long-term loss ratio. Another (stronger) definition of an optimal algorithm then requires an algorithm to produce a schedule minimizing the loss ratio in any arrival scenario. We will use the latter criterion in this thesis. A scheduling problem is nonpreemptive if resources cannot be taken away temporary from the tasks. It is preemptive otherwise. A variation of EDF which drops lost jobs has been shown to be optimal if the jobs require equal service time [31]. More recently, Panwar and Towsley [25] proved that ML is optimal among all nonpreemptive work-conserving2 policies with respect to the fraction of jobs beginning service by their laxity for very general system models. They also obtained similar results for EDF allowing preemption. Numerous works have been published in this area. Other than the exact analysis of simple policies, there exists a growing literature on the design and evaluation of heuristic real-time scheduling policies [32] due to the difficulty in modeling com-plicated practical systems. There is an obvious assumption in conventional real-time theory that only the performance of real-time tasks is of concern. This is partially because most early real-time applications, included few or no time insensitive tasks. Unfortunately, this does not hold any more when we try to provide real-time support in general purpose systems. There is a dramatically different view of performance optimality in general purpose computing environment where the major metrics are average response time (or average waiting time ), throughput, fairness and system utilization [24, 28, 6]. Algorithms such as Round-Robin, Shortest Job First and Shortest Remaining Time First have been de-veloped to achieve these objectives [6]. But timesharing techniques obviously cannot provide satisfactory real-time support. The two paradigms, real-time and timesharing, are motivated and developed for different types of applications. It is not easy to bring them together. Therefore we face a serious problem in incorporating real-time support to timesharing sys-tems. With the emergence of new applications such as multi-media systems, there have been increasing interests for scheduling algorithms to provide good performance for both general and time critical tasks. In such systems, the performance of time sensitive jobs should not be 2 I n a work-conserving policy, a server is never idle when there is a task to process. CHAPTER 1. INTRODUCTION 4 achieved by a serious deterioration of the other tasks. A system using either timesharing tech-niques only or real-time scheduling policies only cannot achieve this. Another problem arises if real-time and non-real-time tasks are semantically related. Poor non-real-time task perfor-mance will bring the overall performance down. On the other hand, a scheduler can multiplex the processor between real-time and non-real-time tasks by taking both types of performance metrics into consideration. Instead of completely biasing toward real-time tasks, we can defer real-time tasks in favor of non-real-time activities until the real-time tasks become really urgent. If the real-time tasks have relatively large laxity, we may expect to significantly improve the performance of non-real-time tasks without much loss of real-time tasks. It is also observed that many applications (e.g., digital video) can tolerate certain degree of loss without noticeable performance deterioration. Therefore a scheduler may take advantage of this property to gain overall system performance by using the above strategy. Meanwhile, this multiplexing should be efficient, able to adapt to dynamic environments and inexpensive to implement. 1.1.2 Goals This thesis presents our development, analysis and evaluation of an adaptive scheduling method which is to provide an effective solution to the above problem. Among the works addressing the design and analysis of scheduling policies for real-time systems, there are two types of approaches: one tends to analyze the exact behavior of some simple policies, while the other tries to develop heuristic strategies and implementation methods and evaluate them through simulation or benchmarks. In our study, analytic, numerical and simulation methods are used to analyze and demonstrate the performance of the various algorithms. We restrict our attention to two main performance metrics: • the loss ratio for real-time jobs , and • the average waiting time for non-real-time jobs We have the following goals in mind: 1. To provide real-time jobs some degree of guarantee on maximum loss ratio. CHAPTER 1. INTRODUCTION 5 2. To minimize non-real-time performance penalty while achieving (1). 3. Efficient and easy implementation. 4. Stable system behavior in a dynamic environment. In particular, real-time task per-formance should not be undermined by temporary overall system overrun, or by heavy non-real-time load. The system should also behave normally under an unbalanced work load. 5. To achieve the best performance trade-off between real-time and non-real-time tasks. Further more, this trade-off decision should be explicitly available to the system designer and should be easy to control. 1.2 Related Work Numerous results on scheduling theory have been published in the early days by the researchers in areas such as operation research, automatic control, combinatorial mathematics and com-puter science. General problems of scheduling jobs with arbitrary arrivals, varied processing time and laxity (or deadline) to minimize loss ratio or optimize other performance metrics are well-known to be NP-complete in the strong sense. However, some restrictions on the prob-lem parameters may often transform them into pseudopolynomial or even polynomial-bounded problems. We refer readers to [8, 18, 10, 17] for surveys on these classic works. The development of real-time computer systems has brought new interest to scheduling algorithms that optimalize certain system metrics. In Panwar and Towsley's work [25], the Minimum laxity first (ML) policy has been shown to be optimal among all nonpreemptive work preserving policies for the G/M/c + G system3 where the time constraint is laxity. Similar results are also obtained for the earliest deadline first (EDF) policy in G/M/l + G systems when the time constraint is deadline. Hong, Tan and Towsley [12, 13] recently analyzed the 3 W e use Kendall 's notation A/B/m + L + S in this thesis, where A describes the inter-arrival process, B describes the service time requirement, and m is the number of servers. L and S represent laxity distribution and scheduling policy respectively. CHAPTER 1. INTRODUCTION 6 performance bound of M/M/l + M system when jobs have deadlines for both ML and EDF. They also proposed a class of ML(n) and EDF(n) algorithms for performance bound analysis and more efficient implementation. ML(n) schedules the first n jobs according to the minimum laxity first discipline and leaves the remaining jobs in a secondary queue from where they will be fed to the main queue in a FCFS manner. EDF(n) works similarly. It is observed that ML(n) and EDF(n) provide reasonably good approximations of the original algorithms even when n is very small. Interestingly enough, a similar idea also appears in [35], where a variant of FCFS (called IFCFS) is proposed and is later proved to have identical behavior to MX(2) [23]. Further studies of ML(n) follow in [23, 22, 9]. ML(n) can also model systems with limited resources (e.g., buffers) where overloaded jobs can be left in a secondary storage and be fed into main memory in FCFS order [27]. Among other works, Liu et al studied scheduling problems with various temporal constraints and problems with imprecise computations [14, 3, 30]. Recently, with the emergence of integrated service packet-switched networks and high-performance workstations, more work has been done in scheduling multiple classes of jobs with diverse performance objectives. In [5], Chipalkatti, Kurose and Towsley proposed two al-gorithms based on thresholds. They considered a two-queue system, one for real-time jobs and another for non-real-time jobs. The Queue Length Threshold (QLT) policy employs a threshold for the non-real-time queue length. Priority is given to real-time jobs unless the non-real-time queue length exceeds the threshold which is kept constant. On the other hand, Minimum Laxity Threshold (MLT) uses a laxity threshold so that non-real-time jobs will be served until the minimum laxity (remaining time before deadline) is below the constant threshold. This is an example of the general heuristic that gives real-time jobs priority over non-real-time jobs only when their laxities have become small. Their analytic modeling and numerical results show that MLT and QLT have little difference in the performance tradeoffs and consequently they con-cluded that QLT was more practical because queue length is easier to monitor. However, their study did not provide explicit indication of how the thresholds were related to the achievable performance. More importantly, QLT and MLT cannot provide satisfactory performance for systems with dynamic work loads. We further study these two heuristics in Section 2.1. Peha CHAPTER 1. INTRODUCTION 7 and Tobagi [26, 27] studied various scheduling algorithms handling multiple classes of network packets. They proposed a cost-based policy which employs a cost function to express different performance objectives. These efforts follow the above common idea of holding real-time tasks until they become urgent. But they did not consider how a scheduler could adapt to a dynamic unbalanced environment which is very likely in reality, nor did they deal with issues such as stability and implementation efficiency which will be addressed in this thesis. 1.3 Overview The rest of the thesis is organized as follows: Chapter 2 describes our further study on the two threshold-based scheduling policies, QLT and MLT. We first capture the major characteristics of the two algorithms by simulation, and then study the relation between system loads, threshold values and system performance. Approximate analysis is presented along with brief discussions. Chapter 3 explores the idea of adaptive scheduling based on threshold functions to over-come the problems in static QLT and MLT. Two adaptive schemes are proposed and compared with their static counterparts. We also propose integrating the two thresholds and address implementation related problems. Chapter 4 presents experimental simulation and performance evaluation of our adaptive scheme (ADP) by comparing its various performance metrics to a group of well studied algo-rithms as well as a proven optimal algorithm. Experiments are carried under various system conditions and job arrival patterns. Our simulation results show that ADP meets our design goals very well. Chapter 5 concludes this work and looks into future studies. Chapter 2 A n a l y s i s o f Q L T a n d M L T S c h e d u l i n g In this chapter, we first outline our study on two static threshold-based scheduling policies, QLT and MLT, in section 2.1. This study led us to explore the idea of adaptive threshold functions. Section 2.2 presents our approximate analysis of the dynamic behavior of the two threshold-based algorithms. The analysis is aimed at explaining our observations and providing more insight into the fundamental problems. 2.1 Static Threshold-based Algorithms In [5], two threshold-based static scheduling algorithms are proposed for scheduling mixed real-time and non-real-time tasks. Assuming geometrical distribution for real-time arrivals, a general form of transition matrices for the corresponding discrete time Markov chains is obtained from which a set of equations can be derived by making further assumptions. Though this gives us the possibility to numerically study the two algorithms, it does not provide explicit information on the relation between the system parameters. The two policies work as follows: • Minimum Laxity Threshold: In MLT, the real-time task with minimum laxity is scheduled if this laxity is below the constant threshold, Tp; or when the non-real-time queue is empty. 8 CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 9 • Queue Length Threshold: In QLT, the first non-real-time task in the waiting queue is scheduled if the non-real-time queue length exceeds the constant threshold, Tq; or when the real-time queue is empty. Figure 2.1 describes the basic model of these two policies. We have a two-queue, one server system. Real-time and non-real-time tasks arrive in a Poisson process with rates A r and A n respectively. Their service times are exponentially distributed with average l//x. Each real-time task has a laxity IT. We're interested in real-time task loss ratio e (the percentage of total lost tasks over total arrivals) and average non-real-time task delay £ (including waiting time and service time). Tq is the non-real-time queue length threshold associated with QLT, and Tp is the minimum laxity threshold associated with MLT. The scheduler multiplexes the server between the two queues according one of the above two disciplines. Note that there are still free choices for scheduling policies within the individual queues. However, we will use FCFS with the non-real-time queue and an optimal policy ML with the real-time queue throughout our discussion. Chipalkatti et al [5] studied QLT and MLT under strong assumptions including balanced real-time and non-real-time arrival rates (i.e., constant and equal), constant laxity upon arrival, and normal work load (uncongested). They concluded that QLT and MLT offer similar tradeoffs between the delay of the non-real-time tasks and the loss of the real-time tasks under the above assumptions. However, because of the bursty nature of real applications, we are interested in the performance of algorithm under unbalanced loads, with divergent laxities and in congested peak periods, as well as the effectiveness of the threshold parameters in achieving certain performance objectives. A dynamic environment and the resulting state space explosion make their approach prohibitive. This is mainly due to the difficulty in achieving acceptable accuracy over a large range of system configurations, and high computational complexity. Another inherent problem of analytic and numerical approaches is their inability to describe unstable systems. Therefore the following discussion will be based on simulation results.1 'However, we do observe that our simulation results match the numerical values well in those cases when the number of states is moderate (e.g. Figures 2.10 and 2.11). CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 10 x Tp: Minimum Laxity Threshold X n: Non-real-time Arrival Rate Tq: Queue Length Threshold X r: Real-time Arrival Rate K: Multiplexing Switch H : Service Rate Figure 2.1: Static Threshold-based Model Figures 2.2 to 2.9 illustrate the behavior of static QLT and MLT policies when the arrival rate of only one type of tasks (either real-time (RT) or non-real-time (NRT)) changes. Figures 2.102 and 2.11 show the effect of the queue length threshold for a given work load with A r = 0.2 and A n = 0.8. We have the following observations: 1. Static QLT biases towards non-real-time tasks. Figures 2.2 and 2.3 show that, with a fixed A n , loss ratio e starts to grow rapidly when the overall work-load (not real-time work-load ! ) approaches saturation point. The delay of non-real-time tasks £, however, tends to remain stable at a value determined by Tq and A„. Figures 2.4 and 2.5 provide even stronger evidence. Even with a constant A r , the loss ratio grows linearly (with a large slope) as A n increases. However, static QLT keeps E moderate over a large region until A„ itself (not the overall work-load ! ) approaches 1. Tuning the 2 T h e deviation of numerical result from simulation value is caused by accumulated inaccuracy of the program. CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 11 threshold Tq changes the relative values, but does not change the above property. Steep curves of loss ratio imply the difficulty in obtaining a Tq value so that the loss ratio can be kept below a reasonably small bound in a dynamic environment. This indicates a most undesirable property that the load of the non-real-time tasks has very strong influence on the performance of the real-time tasks. 2. Static M L T biases towards real-time tasks. Static MLT has the opposite behavior. Figures 2.7 and 2.9 show a sudden hike of £ when the total work-load approaches the saturation point. A nice property of MLT is that the loss ratio is up-bounded for a given threshold value. The dotted curve in figure 2.6 shows this upper-bound for constant A n, and Figure 2.8 shows how e reaches an upper-bound as An increases. However, the problem is that the loss ratio curve grows very fast. This implies that, to ensure low loss ratio in heavy load, Tq has to be raised very high. A high threshold value, in turn, will unnecessarily degrade non-real-time task performance when the load is light. Therefore it is difficult to select a proper threshold to ensure peak time loss ratio without loss of performance under normal conditions. 3. Static Q L T and M L T wil l perform worse with non-uniform laxity and service t ime. Minimum laxity is used as an indication of urgency for real-time tasks. It estimates the real situation less accurately when the laxity and service time are non-uniform. The length of the non-real-time queue is used as an indication of the accumulated non-real-time work load. It becomes a poor indication when the service time is non-uniform. Thus both QLT and MLT will not work well when the laxities and service times of tasks are not constant and identical. 4. QLT and M L T are effective means to adjust performance tradeoffs for fixed input rates, but not for dynamic arrivals. Figures 2.10 and 2.11 show that QLT's effect on non-real-time average delay is, as ex-pected, almost linear. The loss ratio of real-time tasks, however, drops dramatically in CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 12 the beginning, and then stays at a fairly constant level. Figures 2.10 and 2.11 also suggest that we should look at the elbow of the loss ratio curve, where the loss ratio is low with a relatively small penalty in average waiting-time. Unfortunately, this point is a function of both A r and A n and is not fixed in a dynamic environment. MLT is more effective in controlling the loss ratio, but increases average delay much more dramatically than QLT. We observe a very steep curve for both loss ratio and average delay. This is not good as it offers more coarse-grained tradeoff choices to the system designer. It means it is difficult to obtain a proper tradeoff point even for fixed arrival rates, let alone in a dynamic environment. All of these observations suggest the need of some kind of dynamic scheme to adapt to the changing environment, especially the changing work loads and the changing proportion of real-time and non-real-time tasks. In other words, the threshold value should be a function of the dynamic environment. The performance problem is particularly serious in the overloaded periods, when certain discrimination for the different classes of tasks is essential. But consis-tent discrimination will deteriorate the performance of low priority tasks unnecessarily under moderate system load. This leads us to examine the idea of adaptive schemes. But before that, we will first analyze the dynamic behavior of the two static threshold policies more formally to gain more insights into the problems. 2.2 Approximate Analysis of QLT and M L T In [5], Chipalkatti, Kurose and Towsley described a discrete time Markov chain model of both QLT and MLT. They used a combined state (x\,X2) to describe their system, where x\ denotes the number of non-real-time tasks in the system, and x2 denotes the minimum laxity among the queued real-time tasks. Though their combinatorial approach is accurate in modeling the system, it inevitably leads to unmanageably large state transition matrices in practical systems. In fact, even to solve the system numerically is not easy, especially when the load is high (because CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 13 S t a t i c Q L T L a x i t y « 1 0 . T q = 8 3- — S i m u l a t i o n o „ : - - - - A p p r o x i m a t i o n L a m N o O . 8 "co a s 3 _ e/i to j o 5 _ - J : L a m N - O . 4 O o o.i o.a o.a o.« oo o.o O.T o.s R T A r r i v a l R a t e ' • • 1 1 ' ' ' 1 O.fl l.O Figure 2.2: Q L T Loss Ratio: with Varied RT Arrival Rates S t a t i c Q L T L a x i t y *• 1 0 . T = 8 S i m u l a t i o n a -Time 8 -L « m N = 0.4 c L a m N = 0 . a Wait E— O S -o i • • ' 1 1 ' 1 1 1 i • • • • 1 1 • • • 1 • • ' 1 1 1 • • • i 1 • 1 1 1 o o.i o.s 0.3 o* o.e o.s O.T o.a o.a i.o R T A r r i v a l R a t e Figure 2.3: Q L T Average Delay: with Varied R T Arrival Rates CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 14 S t a t i c Q L T l - o x i t y m 10. T • 8 S i m u l a t i o n - - - - A p p r o x i m a t i o n io I,, nl Loss Rat 0 0.1 0.2 OJ 0.4 OS ( L a m R c O . 4 U m R " 0 . 8 0 1 1 • ' i 1 ' • ' i • • ' ' 1 • r 1 f • • • • i • • 1 • i • • o o . i o.a 0.3 o .* o o o.a O .T N R T A r r i v a l R a t e o.e o.o i .o Figure 2.4: QLT Loss Ratio: with Varied NRT Arrival Rates S t a t i c Q L T a -L a x i t y = I O , T « g \ u p p « l — b o u n d / S i m u l a t i o n \ / a - " " " " " A p p r o x i m o t l o n \ v / ing Time s - J • Wait L a m R ' O . S sJ'' Wait s -E— •z. . f U m R - O . 4 O O O.l 0.3 0.3 O 4 o.o o.a OT o.a o.o i.a N R T A r r i v a l R a t e Figure 2.5: QLT Average Delay: with Varied NRT Arrival Rates CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 15 S t a t i c M L T L a m N - O . 6 . T - 5 s J «s -S i m u l a t i o n A n a l y t i c U p — b o u n d Putin i Ad LIU t o « O - J $ J 8 J ti • 8 ' r •• ' - " V - ' o o . i a . a o.a o .* o .e o .a O . T o .a o.a i .o R T A r r i v a l R a t e Figure 2.6: MLT Loss Ratio: with Varied RT Arrival Rates S t a t i c M L T 8-L a m N - O . 6 . T - S 8 - S i m u l a t i o n — — — — A p p r o x i m a t i o n 8 -s E -a us a -3-E— • O S 8 -z j 8-° o o . i o.a 0.3 - f -r - . - . - , J . . . . | . i i . , . . . 0.4 o .e o .a o . r o .a o.a i .o R T A r r i v a l R a t e Figure 2.7: MLT Average Delay: with Varied RT Arrival Rates CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 16 S t a t i c M L T 2 - T * 6 . L»xlty = 8 5 ~ LaimR = O.O 3~ U m R — O.B 3 - ' - L i m R ™ 0 . 9 Ac u p p « r - b o u n d 100.11 o J.W 0.1 Loss Ral 8 -Loss Ral 1-8 _ 1-3 _ 8 _ 8 -2 -s I 1 ' 1 1 i • *1 • * i * ' • * i 1 * ' * r ' • • ' i • • • • i * ' ' 1 i • 1 1 • i o o . l o .a o.a o.+ o .o o .a 0.7 0 N R T A r r i v a l R a t e • o .« 1.0 Figure 2.8: MLT Loss Ratio: with Varied NRT Arrival Rates Figure 2.9: MLT Average Delay: with Varied NRT Arrival Rates CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 17 Figure 2.10: Loss Ratio: Effect of Queue Length Threshold Figure 2.11: Average Delay: Effect of Queue Length Threshold CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 18 of limited memory space) and when the load is low (because of cutting errors)3. With only a set of general equations without a closed-form solution, their result gives little information on the dynamic behavior of the two policies. Therefore, we developed a simple approximate approach in order to describe general behavior of the two threshold algorithms and explain the observations given earlier. In the following two sections, we derive analytic bounds and approximations for QLT and MLT. 2.2.1 Approximate Analysis of Q L T Recall that in figure 2.1 QLT works as follows: QLT: schedule a real-time task unless 1. NRT queue length > 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, (0<N< Tq) (2.3) PTq+k = phnPT9 = PnP*',Po, (A>1) (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<Tq = YLn=oPni w e have 7 r = p.Pr{realtime queue is not empty and NRT queue length < Tq} = /i(l-p5)P<T, (2.15) Then the loss ratio is e=hLZJL = 1_^-Po)P<Tq ( 2 1 g ) (2.14) is the special case when P<Tq ~ 1- Substituting the pn's , we have the following result: I -P5 € « 1 - Ar V (2.17) CHAPTER 2. ANALYSIS OF QLT AND MLT SCHEDULING 23 The factor prQ in (2.17) can be approximated depending on the value of A n . If A n is relatively large, then PQ can be estimated using 1 — -V+^n, where 6 is a small factor. If A n is very small, 1 — ^ may serve the purpose well. We show this in figure 2.2 and figure 2.4. We conclude that QLT offers little protection to the real-time tasks during periods of high work load. Though rather complicated, e is strongly dependent on the non-real-time load. Actually from (2.17), we have limAn_>-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 ° <a ce: GO o f -8 - i n d ?-a _ g ** o i 1 1 ' - ' " i T ' , I ' " F T •"•"^T- 1 • • > • • • ' 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 <D 5S 8-1 8-: ADP 3 3 4 S « B 1 1 S 10 T r a i n L e n g t h Figure 4.13: Effect of Train Length Figure 4.14: Effect of Laxity: For Different Arrival Distributions Chapter 5 C o n c l u s i o n a n d F u t u r e W o r k This thesis has explored scheduling mixed real-time and non-real-time tasks adaptively in a dynamic system environment. We studied two threshold-based mechanisms, Queue Length Threshold (QLT) and Minimum Laxity Threshold (MLT), in multiplexing system resources among the two classes of tasks. Our simulation and analytical results showed that neither static QLT nor MLT could provide satisfactory performance in a dynamic environment where the arrival rates are not constant, and especially for bursty arrivals. When the system load varies, QLT biases toward non-real-time tasks, while MLT favors real-time tasks. The approximate analysis in chapter 2 illustrated and proved essential characteristics of these two threshold-based policies. Based on these observation and analysis, we proposed an adaptive scheme employing thresh-old functions. Instead of trying to set one trade-off point for all situations, we capture the best trade-off points for diverse system conditions by a series of threshold values. We described two such adaptive schemes, AQLT and AMLT, and analyzed the performance they can be expected to achieve. We also discussed the idea of integrating the two threshold mechanisms to provide performance trade-offs, and addressed some important implementation related issues. Though the exact performance of our integrated adaptive algorithm (ADP) depends on the actual values of the thresholds, we showed two major performance metrics achieved by ADP, loss ratio and average delay, for typical loss ratio bounds and various load conditions. Simulation experiments were conducted to compare the strengths and weaknesses of ADP with 60 CHAPTER 5. CONCLUSION AND FUTURE WORK 61 other common scheduling policies and the optimal algorithm. We found that ADP offers the best performance trade-off under a wide range of conditions. For most cases, it offers bounded loss ratio for real-time tasks and significantly lower average delay for non-real-time tasks than the other policies under comparison. ADP also achieves the desired performance trade-off during overloaded periods. Al l of these were achieved by very simple step-wise threshold functions. In short, ADP meets our goals very well in scheduling real-time and non-real-time tasks with different performance metrics. It is a good scheduling algorithm for applications such as multi-media processing and communications where there is a mix of real-time and non-real-time tasks, and where the occasional drop of a real-time task is non-fatal. 5.1 Future Work This study can be further pursued in several ways. In order to develop a scheduling algorithm for practical use, we need to test our ideas in real systems with real applications. Many insights and understanding will result from a real implementation of our algorithm. Issues of implementation overhead and the feasibility in a real system are only addressed briefly in this thesis. The work we have done here indicates that it is worthwhile to investigate these issues further in the future. The work on mathematical analysis in chapter 2 could be developed further to obtain better approximation or even exact explicit results of the most important characteristics of the two threshold strategies. B i b l i o g r a p h y [1] Arnold 0. Allen, "Probability, Statistics, and Queueing Theory with Computer Science Applications", Academic Press, New York, 1978. [2] Richard Bellman, "Adaptive Control Processes: A Guided Tour", Princeton University Press, Princeton, New Jersey, 1961. [3] R. Bettati, D. Gillies, C. C. Han, K. J . Lin, J. W. S. Liu and W. K . Shih, "Recent Results in Real-Time Scheduling", Report No. UIUCDCS-R-90-1629, Department of Computer Science, University of Illinois at Urbana-Champaign, October 1990. [4] Partha P. Bhattacharya and Anthony Ephremides, "Optimal Scheduling with Strict Dead-lines", IEEE Transactions on Automatic Control, Volumn 34, Number 7, July 1989. [5] Renu Chipalkatti, James F. Kurose and Don Towsley, " Scheduling Policies for Real-Time and Non-Real-Time Traffic in a Statistical Multiplexer", Proceedings of IEEE Infocom'89, Ottawa, Ont., Canada, April 25-27, 1989. [6] Harvey M . Deitel, "An Introduction to Operating Systems", Addison-Wesley, 1984. [7] Domenico Ferrari, "Computer Systems Performance Evaluation", Pretice-Hall, Inc., 1978, Englewood Cliffs, New Jersey, 07632. [8] Michael R. Garey and David S. Johnson, "Computers and Intractability", W.H. Freeman and Company, New York, 1979. [9] P. Goli, James F. Kurose and Don Towsley, " Approximate Minimum Laxity Scheduling Algorithms for Real-Time Systems", Technical Report, COINS Department 90-88, Univer-sity of Massachusetts at Amherst. [10] R. L. Graham, E. F. Lawler, T. K. Lenstra and A. H. G. Rinnoy Kan, "Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey", Annals of Discrete Mathematics, Volumn 5, 1979. pp. 287-326. [11] Raff Guido Herrtwich, "An Introduction to Real-Time Scheduling", TR-90-035, Interna-tional Computer Science Institute, Berkeley, CA. 62 CHAPTER 5. CONCLUSION AND FUTURE WORK 63 [12] Jiawei Hong, Xiaonan Tan and Don Towsley, "The Binary Simulation of the Minimum Laxity and Earliest Deadline Scheduling Policies for Real-Time Systems", COINS Technical Report 89-70, Department of Comput. Inform. Sci., University of Massachusetts, July 1989. [13] Jiawei Hong, Xiaonan Tan and Don Towsley, "A Performance Analysis of Minimum Laxity and Earliest Deadline Scheduling in a Real-Time System", IEEE Transactions on Com-puters, Volume 38, Number 12, December 1989. [14] Jane W. S. Liu et al., "Algorithms for Scheduling Imprecise Computations", IEEE Com-puter, Volumn 24, Number 5, 1991. [15] Leonard Kleinrock, "Queueing Systems, Volumn I: Theory", John Wiley & Sons, 1975. [16] James F. Kurose and Renu Chipalkatti, "Load Sharing in Soft Real-Time Distributed Computer Systems", IEEE Transactions on Computers, Volume C-36, Number 8, August 1987. [17] Eugene L. Lawler, "A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness", Annals of Discrete Mathematics , Volumn 1, 1977. pp. 343-362. [18] T. K. Lenstra, A. H. G. Rinnoy Kan and P. Brucker, "Complexity of Machine Scheduling Problems", Annals of Discrete Mathematics, Volumn 1, 1977. pp. 343-362. [19] C. L. Liu and James W. Layland, "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment", Journal of ACM, Vol. 20, No. 1, Jan. 1973. [20] Henry Massalin and Calton Pu, "Fine-Grain Adaptive Scheduling using Feedback", USENIX Computing Systems, Volume 3, Number 1, Winter, 1990. [21] A. K. Mok and M . L. Dertouzos, "Multiprocessor Scheduling in a Hard Real-Time En-vironment", Proceedings of the 7th Texas Conference on Computing Systems, November 1978. [22] Philippe Nain and Don Towsley, "Comparison of Hybrid Minimum Laxity/First-in-First-out Scheduling Policies for Real-Time Multiprocessors", COINS Technical Report 90-33, University of Massachusetts at Amherst, May 1, 1990. [23] Philippe Nain and Don Towsley, "Properties of the ML(n) Policy for Scheduling Jobs with Real-Time Constraints", Proceedings of the 29th Conference on Decision and Control, Honolulu, Hawaii, December 1990. pp 915-920. [24] E. I. Organick, "The Multics System: An Examination of Its Structure", Cambridge, Mass.: MIT Press, 1972. [25] Shivendra S. Panwar, Don Towsley and Jack K. Wolf, " Optimal Scheduling Policies for a Class of Queues with Customer Deadlines", Journal of the ACM, Volume 35, Number 4, October 1988. CHAPTER 5. CONCLUSION AND FUTURE WORK 64 Jon M . Peha, Fouad A. Tobagi, "Evaluation of Scheduling Algorithms for Integrated-Services Packet-Switched Networks", Technical Report: CSL-TR-90-447, Computer Sys-tems Laboratory, Stanford University, September, 1990. Jon M . Peha, Fouad A. Tobagi, "A Cost-Based Scheduling Algorithm To Support In-tegrated Services", Technical Report: CSL-TR-90-448, Computer Systems Laboratory, Stanford University, September, 1990. D. M . Ritchie and K. Thompson, "The UNIX Timesharing System", Communications of ACM, Volume 17, Number 7, July 1974. pp 365-375. M . D. Schroeder, D. D. Clark and J. H. Saltzer, "The Multics Design Project", Proceedings of the 6th ACM Symposium on Operating System Principles, November 1978. pp43-56. W. K. Shih, J. W. S. Liu and J. Y.Chung, "Algorithms for Scheduling Imprecise Compu-tations with Timing Constraints", to be published in SIAM Journal of Computing , July 1991. Barbara Simons, "A Fast Algorithm for Single Processor Scheduling", Proceedings of 19th Annual IEEE Symposium on Foundations of Computer Science, Syracuse, NY, October 1978. pp 246-252. John A. Stankovic, "Misconceptions About Real-Time Computing", IEEE Computer, Vol-umn 21, Number 10, October 1988. John A. Stankovic and Krithi Ramamritham, "Tutorial: Hard Real-Time Systems", New York: Computer Society Press of the IEEE, 1988. Wei Zhao, Krithi Ramamritham and John A. Stankovic, " Preemptive Scheduling Un-der Time and Resource Constraints", IEEE Transactions on Computers, Volume C-36, Number 8, August 1987. Wei Zhao and John A. Stankovic, "Performance Analysis of FCFS and Improved FCFS Scheduling Algorithms for Dynamic Real-Time Computer Systems", Proceedings of Real-Time Systems Symposium, December 1989, pp.156-165.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Adaptive threshhold-based scheduling for real-time...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Adaptive threshhold-based scheduling for real-time and non-real-time tasks Zhu, Wenjing 1991
pdf
Page Metadata
Item Metadata
Title | Adaptive threshhold-based scheduling for real-time and non-real-time tasks |
Creator |
Zhu, Wenjing |
Publisher | University of British Columbia |
Date Issued | 1991 |
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. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-11-10 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051969 |
URI | http://hdl.handle.net/2429/29913 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1991_A6_7 Z58.pdf [ 3.71MB ]
- Metadata
- JSON: 831-1.0051969.json
- JSON-LD: 831-1.0051969-ld.json
- RDF/XML (Pretty): 831-1.0051969-rdf.xml
- RDF/JSON: 831-1.0051969-rdf.json
- Turtle: 831-1.0051969-turtle.txt
- N-Triples: 831-1.0051969-rdf-ntriples.txt
- Original Record: 831-1.0051969-source.json
- Full Text
- 831-1.0051969-fulltext.txt
- Citation
- 831-1.0051969.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051969/manifest