E X A C T UTILIZATION B O U N D S F O R R E A L - T I M E S Y S T E M S DESIGN By Ying Fang B. Sc. (Electrical Engineering) Fudan University, 1989. A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F A P P L I E D S C I E N C E in T H E F A C U L T Y O F G R A D U A T E S T U D I E S D E P A R T M E N T O F E L E C T R I C A L A N D C O M P U T E R E N G I N E E R I N G We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A August 1998 © Ying Fang, 1998 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 Electrical and Computer Engineering The University of British Columbia 2075 Wesbrook Place. Vancouver, Canada ' V6T 1W5 Date: t Abstract Guaranteeing satisfaction of timing constraints of a real time system is an important aspect in hard real time systems design. The utilization test is an effective means to determine schedulability of a real time system prior to implementation and to assign the time budget to individual tasks in the design phase. In this thesis, a novel approach is proposed to compute the exact utilization bound for a task set with known task periods and deadlines using a fixed priority scheduling algorithm. Compared to Park's period-specific utilization bound algorithm, this approach can obtain a more accurate utilization bound without knowledge of the exact task computation times. In addition, this thesis presents two case studies that apply utilization bound analysis to the design phase of real-world real time systems. It also addresses some practical issues such as non-critical tasks, non-periodic tasks, and tasks without strin-gent periods. 11 Table of Contents Abstract ii List of Tables vi List of Figures vii Acknowledgments viii 1 Introduction 1 1.1 Real Time Systems . . • • 1 1.2 Software Life Cycle for Real Time Systems 2 1.3 Real Time Scheduling 3 1.4 Motivation ' 5 1.5 Related Results 7 1.6 Contributions 9 1.7 Outline of the Thesis 9 2 Background 11 2.1 . Notations and Concepts 11 2.2 The Rate Monotonic Theory 15 2.3 The Deadline Monotonic Algorithm and the Modified Rate Monotonic Algorithm 17 2.4 A Sufficient and Necessary Condition 18 2.5 Response Time Analysis 20 i n 2.6 Park's Algorithm • 22 2.6.1 Period-Specific Utilization Bound I . . 22 2.6.2 Period-Specific Utilization Bound II 24 2.6.3 Discussion 25 2.7 Schedulability Analysis Tool 28 3 Exact Feasible Utilization Bound 32 3.1 Overview of the Algorithm 32 3.2 Theoretical Foundations of the Algorithm 34 3.3 Procedure of the Algorithm 38 3.4 Discussion and Comparison . . . 39 3.5 Perspective on Utilization Bounds 42 3.6 Consideration on Some Known Computation Times 43 3.7 Environmental Issues 44 3.7.1 Sporadic Tasks 44 3.7.2 Task Synchronization . . . . . . . . 45 3.7.3 Scheduler Overhead . 46 3.7.4 The Effect on Subsystem Utilization Bound . 48 4 Case Study 49 4.1 Mine Pump and Control System 50 4.1.1 System Model 54 4.1.2 Non-Critical Tasks 56 4.1.3 Schedulability Analysis 57 4.2 Hydraulic Motion Platform Simulator System 60 4.2.1 System Model 62 4.2.2 Real Time Systems with Harmonic Periods 62 iv 5 Conclusions and Future Work .65 5.1 Summary of Results 65 5.2 Future Work 67 5.2.1 Utilization Bound of a Real Time System with Shorter Dead-lines than Periods 67 5.2.2 Utilization Bound of Deferred Real Time Systems . " 68 5.2.3 Soft Real Time Systems 68 Bibliography 69 List of Tables 3.1 The comparison of Park's and Liu's algorithms 40 3.2 The comparison of Park's and Our algorithms 41 3.3 The comparison of computation times in Park's and our algorithms. . 42 4.1 Mine control tasks and protected shared objects 55 4.2 The task set of the mine control system 57 4.3 Hydraulic motion system tasks and protected objects. 63 v i List of Figures 1.1 The life cycle of real time software development 6 2.1 The diagram of the time notations in real time systems 12 2.2 Time lines for two task sets 27 2.3. The user interface of the schedulability analysis tool . . . 31 3T The perspective of utilization bounds 42 4.1 The system diagram of the mine pump and control system 51 4.2 Design for the. mine pump and control system 53 4.3 The system diagram of the hydraulic motion platform simulator system 60 4.4 Design for the hydraulic motion platform simulator system 61 vii Acknowledgments First and foremost, I would like to thank my supervisor, Dr. Greg W. Bond. He has introduced and guided me into this research, and provided sound advice and invaluable feedback at every stage of this project. Without my family's enormous support, I would not have been able to complete my study and research. In particular, I appreciate my husband Yi's encouragement and support during my master's program. I also would like to thank my parents and parents-in-law for taking care of my lovely girl Jane. In addition, I would like to thank Dr. Hua Jin for being on my committee and Kendra Cooper for numerous valuable suggestions and discussions. I. also wish to acknowledge Icarus Chau, Paria Noorkami, Buke Otkunc and Andrew Watkins for their help and friendship. vm Chapter 1 Introduction 1.1 Real T i m e Systems Real time systems, which operate in concert with real physical systems, react to externally generated input stimuli within a given deadline. A typical real time system performs one or a number of control and monitoring functions in parallel, such as data sampling, data processing and communication. Therefore, concurrent processing is a key feature of real time systems. Moreover, the response time of each event is often constrained by physical laws or. conventional rules. For example, a delayed response in an air traffic control system could result in a mid-air collision of two aircraft. Real-time systems are generally classified as hard and soft real-time systems [Burns 91]. The distinction lies in the consequences of violating the timeliness re-quirement: whereas soft real time environments are characterized by rising costs with increasing lateness of results, no lateness can be tolerated in hard real time environ-ments. In other words, a late response, even if correct, is unacceptable in a hard real time system. Hard time constraints can be determined precisely by using the physical laws governing the technical processes being controlled. To satisfy timing requirements, predictability is required in hard real time systems, which means that when a task1 is activated, it should be possible to determine its completion time with certainty, that is, it requires the execution times and its run time schedule to be : -A task is a software module that can be invoked to perform a particular function. A task, like a process in Unix, is the scheduling entity in a system. 1 Chapter 1. Introduction 2 predictable. In the thesis, we will focus on discussing hard real time systems. 1.2 Software Life Cycle for Real T ime Systems As the cost of developing software has grown steadily, effective software engineering techniques and technology have drawn enormous attention since the late 1960s. One popular type of software design is a phased approach, called a software life cycle. This approach is also applied in developing real time systems. The most widely-used software life cycle is the Waterfall Model in which the following steps in time order are considered [Gomaa 93]: 1. Requirements phase: decide what the product must do and define system's services, constraints and goals. The requirements are classified into functional requirements and non-functional requirements. The former includes system fea-tures that can be directly tested by executing the program. The latter includes specification of time constraints, programming language and the type of ma-chine. Among them, timing requirements play a significant role in real time systems. 2. Design phase: show how the product will meet the requirements. The design process partitions the requirements to either hardware or software systems and establishes a system architecture. Furthermore, it decomposes the system into tasks. 3. Implementation phase: build the system. 4. Test phase: check if the system meets both functional and non-functional re-quirements. Chapter 1. Introduction 3 5. Maintenance phase: maintenance involves correcting errors which were not dis-covered in earlier stages of the life cycle, improving the implementation of sys-tem tasks and enhancing the system's services as new requirements are discov-ered. 1.3 Real Time Scheduling In hard real time systems, failure to meet deadlines is equivalent to producing incor-rect results. The sources of timing violation can be classified into three groups: • Computation causes (corresponds to the. running state): the time needed to perform task processing,' • Scheduling causes (corresponds to the ready state): the time yielded to higher priority tasks • Synchronization cause (corresponds to the waiting state): the delay time caused by communication with the other tasks While the computation time and synchronization time are determined by system com-plexity and processing load, scheduling theory defines the efficiency of exploiting the underlying system's processor. Two types of scheduling methods are widely exploited in industry and institutes. Cyclic schedulers used to be dominant in real time design [Burns 96] and are still popular in assembly-line processing control. In this theory, after real time tasks are implemented, hand-crafted techniques are used to ensure the timing correctness by statically binding task executions to fixed slots via time lines. Under this scheduler, task periods in a real time system are harmonic and aperiodic tasks can not be handled. But, this method has turned out to be error-prone and inflexible. Moreover Chapter 1. Introduction 4 timing problems can be identified only in the test phase. The iterations involved may require extensive changes to the system architecture causing cost increase and delivery delay. Process-based scheduling algorithms, also referred as algorithmic-based scheduling theories, are developed to support task execution directly and determine which task to execute at run time based on scheduling algorithms. The advantages of process-based scheduling are as follows • it provides analytical guarantees and gives insight into hardware and software design errors that degrade schedulability, • it can predict run time behavior in the face of concurrency, • it allows separation of timing and functional concerns, • it provides an engineering basis for designing real time systems. Process-based scheduling algorithms are usually grouped into two categories: static scheduling algorithms and dynamic algorithms. A static approach calculates sched-ules for tasks off-line and it requires the complete prior knowledge of tasks' charac-teristics. A dynamic approach determines schedules for tasks on the fly and allows tasks to be dynamically invoked. Although dynamic approaches are flexible and can adapt to changes in environment, a static scheduling technique is desirable in hard real time systems. This is because no event should be unpredicted and schedulability should be guaranteed before execution for a hard real time system. Since our concern in the thesis is hard real time systems, we will restrict ourselves to only discussing of static scheduling techniques. The main goal of real time task scheduling is to provide a schedule that allows all tasks to be processed in time according to tasks' deadlines, so the scheduling algorithm Chapter 1. Introduction 5 must map tasks onto resources such that all tasks meet their time requirements. Therefore, it must be possible to show that a scheduling algorithm applied to real time systems fulfills the timing requirements of tasks. 1.4 Motivation Attempts have been made to address real time scheduling problems and tc test the timing requirements since 1970s. The process-based scheduling algorithms have been accommodated in the conventional life cycle of software development. By doing so, the life cycle for real time software development is extended to separately analyze timing requirements to construct a system model and to estimate the utilization threshold of the processor as shown in Figure 1.1. The benefit of performing analysis in the early development life-cycle is identify-ing potential performance problems,in the design phase before they become imple-mentation errors because fixing errors early is less expensive than fixing them later on. This thesis focuses on studying timing requirements involved in real time sys-tems design during the "system model and analysis"phase. Currently, a simulation-based approach is the only approach applied at the analysis stage.. This technique first uses a domain expert to estimate task execution times. Then a simulator (e.g. [Smith 93, Woodside 95]) uses this information to analyze system performance and identify potential bottlenecks. The validity of the simulation results are only as valid as the estimated task execution times. Furthermore, the simulation results provide no information regarding the overall utilization requirements of processing elements. In' a related approach [MajumdarEtA 92, Majumdar 92], the bounds on task response times are stochastically characterized and computed given estimations of their com-putation time characteristics. The computed response times can then be compared Chapter 1. Introduction 6 Figure 1.1: The life cycle of real time software development Chapter 1. Introduction 7 with the required deadlines in order to identify requirements violations. This approach uses an inefficient "generate and test" method to real-time systems design. First, task execution times are generated by domain experts, and then the ability of a system to meet its deadlines is tested. If the test fails ( i.e. if the system misses one or more deadlines), then new task execution times are generated and the system is re-tested. This process stops when a set of task execution times is identified that ensures system deadlines are met. Alternately, when no realistic task deadlines can be identified, the system is re-designed, at which point the process begins again. In contrast, this thesis investigates a novel approach to design analysis called utilization bound analysis. Compared to simulation-based analysis, utilization bound analysis is more relevant for the design or maintenance of a real-time system since it is important to know as early as possible the permissible execution time bounds of tasks. With this information, designers and maintainers are able to assess for a given design whether the predicted execution time bounds are realistic for the tasks with unknown execution times or whether a modified design is required. This information can also be used as execution time guidelines for implementors of system components during design or maintenance. 1.5 Related Results When a real time system is scheduled by a static scheduling algorithm, the processor utilization is upper bounded. This bound depends on task parameters such as the number of tasks, task execution times, task periods, and task deadlines. A utilization test was first used by Liu and Layland [Liu 73] to examine whether hard real time periodic tasks are schedulable using the rate monotonic scheduling algorithm. They demonstrated that all tasks are schedulable when the utilization of Chapter 1. Introduction 8 processor is less than the worst case utilization bound. However, their computational model is very restrictive: the deadline of a task must be the same as its period; and the utilization threshold is pessimistic: many task sets are schedulable with much higher utilization than the estimated utilization bound from Liu and Layland's theory. Following Liu and Layland's pioneering work, a fair amount of literature has been dedicated to extending the original system utilization bound theory. • Leung and Whitehead introduced a new fixed priority scheduling algorithm to deal with a real time system whose task deadlines are less than the correspond-ing periods. • Lehoczky and Sha [Lehoczky 86], and Peng and Shin[Peng 89] generated an approach to calculate the utilization bound for the case in which task deadlines are a constant factor A of the corresponding task periods in a real time system. • Park [Park 93] developed a technique to determine the utilization bound by using linear programming for fixed priority scheduling algorithm and arbitrary task deadlines. Park's work extended the utilization test to any static scheduling theory and obtained more accurate utilization bound than Liu's work did. But his approach is not capable of finding the exact utilization bound for some task sets with known periods and deadlines. Furthermore, although Park suggests that utilization bound analysis can be used for design analysis, the utility of this approach has not yet been investigated. Chapter 1. Introduction 9 1.6 Contributions As part of the evaluation, we uncover a flaw in one of Park's corollaries [Park 96]. We show that this flaw causes his procedure to calculate incorrect utilization bound in some instances. We then present a corrected version of the corollary. We describe a graphical schedulability analysis tool that was implemented to investigate the run-time system behaviors. This tool can verify the schedulability of a given hard deadline task set for a given fixed priority scheduling algorithm. Furthermore, we propose an extension to Park's procedure that has following advantages: • 1. The calculated utilization bound is accurate. 2. Task deadline can be less than its period. 3. It is applicable to all fixed-priority realtime systems. Finally, we apply the extended approach to two realistic real time systems designs to demonstrate the capability of this approach. We also analyze the common limita-tion in utilization bound estimation methodology by using linear programming for a real time system with very short deadlines. A suggestion is also given to work around this limitation. 1.7 Outline of the Thesis Following the introduction of the thesis topic in the first chapter, Chapter 2 reviews the related previous work on real time scheduling and schedulability tests based on fixed priority assignments. It also introduces a schedulability analysis tool developed during thesis study to visualize the task run time behaviors. Chapter 1. Introduction 10 Chapter 3 presents the exact utilization bound procedure to evaluate exact uti-lization bounds based on the parameters of a task set available at the design phase of development. Chapter 4 demonstrates the application of the exact utilization bound procedure to two case studies. In addition, it also discusses some practical problems raised during the process of design and timing requirement validation. We summarize our work and recommend future work in Chapter 5. Chapter 2 Background In this chapter, we provide an overview of the widely used approaches for scheduling hard.real time systems and for testing the schedulability of a real time system. We also describe how one published approach is flawed and describe how the flaw can be corrected. In addition, a graphic schedulability tool is outlined which facilitates not only the thesis research, but also real time systems design by graphically depicting run-time behaviors. 2.1 Notations and Concepts A real time system with n tasks is represented as a task set {TI, T 2 , T„} in which the tasks are sorted in the decreasing order of the priorities to be scheduled by fixed priority assignment. In this thesis, we will use the convention that r\ has the highest priority and r n has the lowest priority. The timing constraints of each task T; are specified in terms of the following parameters, shown in Figure 2.1: • d is the computation (or execution) time of task r,-—in hard real time systems, it requests the worst case computation time, • Ti is the period time of task r,-, • Pi is the deadline of task T ; , • / , is the phase of task TJ , referred to initial release time relative to some common 11 Chapter 2. Background 12 execution 0 1 • C •* R -— - D -* • T time 0: the critical instant t1: the first arrival time t2: the second arrival time Figure 2.1: The diagram of the time notations in real time systems origin, • Ai is the arrival time or release time of the task. The kth arrival time of periodic task is defined as kTi + /; and the event is called as kth request of task r4-. • Ri is the response time which is between the arrival time and the complete time of task Ti. Each parameter forms its own set such as periodic set T, deadline set D, computation set C, and etc. In real time systems, the ability to meet deadlines is paramount. We describe a task as schedulable when it meets its deadline or its maximum response time is less than the deadline. A real time system is schedulable when all tasks in the system are schedulable. The terms "feasible" and "schedulable" are interchangeably used in the thesis. Special notations for the exact feasible utilization bound and period-specific uti-lization bound techniques are further defined in the following. Chapter 2. Background 13 When we discuss, a task set, the following corresponding parameter sets are as-sumed to be known: • Period time set: T, • Deadline time set: D, .• The phase of each task is set to zero. Since computation time is not required for utilization evaluation, the computation time set is treated as an unknown. In the remainder of this thesis, a task set will be understood to represent the task set itself along with the sets of known parameters. If, however, computation time constraints are known for a task, then these can be included as known parameters. Therefore, any computation time can be either a constant value or a range. Initially the range is set as [0,T,-]. The priority i subset of a task set is defined as the subset of the task set con-taining the first i elements where i is less than n. Therefore the priority 1 subset of { T I , r 2 , r n } is {TI}, the priority 2 { T I , T 2 } , and the priority i is {TI , r 2 , ...Ti}. The total number of the subsets are n. A system consisting of the priority i subset is also called as priority i subsystem. The processor utilization is defined as the fraction of processor time spent in the execution of the task set as T U = Te + Tt> where Te is the execution time, and Ti is the idle time.- and the task utilization is referred to the fraction of computation time during the period as U U task-name rri ' Chapter 2. Background 14 So, the processor utilization Un, processing n tasks, is: n /~i From another point of view, Un is also the system utilization for a task set with n tasks. Informally, the utilization bound in a real time system is the maximum utilization with the requirement that all tasks satisfy their deadlines at any instant. And the exact utilization bound means that a real time system is just feasible with a special computation time set. When the system utilization is above the exact utilization bound, there exists a possible set of computation times for which the task set is not feasible. Just feasible is defined in [Park 93]: A particular task set with some given periods T, deadlines Di, computa-tion times Ci and priority assignments Pt- is said to be just feasible if it meets the following conditions: 1. the task set meets all its deadlines in its present form, 2. 3j that if the computation time Cj of task TJ were changed to Cj + £, where positive e —> 0, then at least one of the tasks in the task set would miss at least one of its deadlines. In summary, there are two key factors in the utilization bound model: feasibility (or schedulability) and full utilization (no idle time during a time interval). When the utilization of the task set with any computation set is below this bound, a fixed priority assignment will make the system feasible. In the remainder of this chapter, we will provide an overview of the following definitions of utilization bounds to distinguish the different approaches: Chapter 2. Background 15 • B(E): the exact feasible utilization bound. • Bf. the utilization bound of the priority i subsystem. • B(Park): Park's periodic-specific utilization bound. • UI'. the ith individual utilization bound calculated by Park's algorithm. • B(Liu): Liu and Layland's bound for the rate monotonic algorithm. 2.2 The Rate Monotonic Theory The rate monotonic scheduling algorithm is a preemptive priority-driven algorithm developed by Liu and Layland [Liu 73]. In this model, a system receives periodic events from the external environment and these events are not buffered. Each event initiates a task to handle it. The priority of each task is statically assigned accord-ing to the task period where tasks with shorter periods have higher priorities. The following assumptions are also made about the environment: 1. The application consists of a fixed set of tasks. 2. All tasks are periodic. 3. All tasks are independent. 4. All system overheads, context switching times and so on are ignored. 5. All tasks have a deadline equal to their periods. 6. All tasks have a fixed worst-case execution time. Although these assumptions are very stringent, the theory focuses on the character-izations of a task by two parameters: its request period and its computation time. Based on the above assumptions, Liu and Layland derived three important results: Chapter 2. Background 16 Theorem 2.1 (Liu and Layland) A critical instant for any task occurs whenever the task is requested simultaneously with requests for all higher priority tasks. The longest response time for any task of r4- for the first request of of rt- occurs when all tasks arrive at a critical instant which means h = I2 = = In = 0. So a real-time system is schedulable if all tasks arriving at their critical instants meet thesis respective first deadlines. Theorem 2.2 (Liu and Layland) If a feasible priority assignment exists for some task set, the rate-monotonic priority assignment is feasible for that task set. This means that the rate monotonic scheduling scheme, is an optimal algorithm. Theorem 2.3 (Liu and Layland) A periodic task set T I , T 2 , . . . , r n with Di — Ti, 1 < i < n, is schedulable by the rate monotonic scheduling algorithm if n s~f Un = J2^- 2. Let Tn = qT{ + r, q > 1 and r > 0. The corresponding task r- replaces the task T j , such that T- = qT{ and ci = C{. In order to maintain the full utilization feature, the computation time of the lowest priority task, Cn, is increased at most Ci(q — 1). The utilization of the corresponding task set is denoted as U'n. v.- = - D ^ - ^ I ( 2 - 3 ) Since q - 1 > 0 and [1/qTi + r - 1/qTi] < 0, then U'n < Un. Therefore the sys-tem utilization of Un is equal to or greater than that in its corresponding task set which has the exact utilization bound. As a result the exact utilization bound of the corresponding task set is regarded as the utilization bound of this task set. Furthermore, n(21/'r i-l) is the lowest value among all exact utilization bounds for any task sets with n tasks. Therefore, the gap between the utilization bound given in Equation 2.1 and. the exact value is due to 1. the transformation of a task set td meet the' requirement that ratios of any periods is less than 2, 2. the minimization of the exact utilization bound. 2.3 The Deadline Monotonic Algorithm and the Modified Rate Mono-tonic Algorithm Since the rate monotonic algorithm is optimal under- the condition that the task deadline must be the same as its period and the schedulability test formula is only Chapter 2. Background 18 suitable for a system using rate monotonic priority ordering, a more exact criterion is required for general circumstances. Leung and Whitehead introduced the deadline monotonic algorithm for real time systems in which task deadline is less than its period [Leung 82] and Shih et al. showed a modified rate-monotonic algorithm when tasks have deferred deadline [Shih 93]. The deadline monotonic algorithm is another fixed priority scheduling algorithm. It assigns the task priority inversely with respect to task deadlines, that is task r,-has a higher priority than task TJ if Di < Dj. Leung and Whitehead proved the optimality of the deadline monotonic algorithm in [Leung 82] Theorem 2.4 (Leung and Whitehead)For a periodic task set r i , . . . , r n with Di < Ti, 1 < i < n,.the optimal fixed priority scheduling algorithm is the deadline monotonic scheduling algorithm. A task set is schedulable by this algorithm if the first task of each task after a critical instant meets its deadline. Since there is no effective schedulability test for the deadline monotonic algorithm, each task must be checked if it meets its deadline in the worst case after implemen-tation to determine the schedulability of a task set. On the other hand, the modified rate monotonic algorithm is a semi-fixed priority-driven algorithm in which each task is assigned two fixed priorities, the higher priority for its old requests and the lower priority for the current request. Since the perfor-mance of the modified rate monotonic algorithm becomes worse when the period ratio increases, we will not cover it in the thesis. 2.4 A Sufficient and Necessary Cond i t ion An exact analysis of the schedulability of a task set with a known computation time set using a fixed priority scheduling algorithm is proposed by Lehoczky et al Chapter 2. Background 19 [Lehoczky 89]. This technique examines a specific set of schedules at a finite number of times, one schedule for each task. If task Tj completes execution at one of these specific times using the schedule constructed for that task, then, all fixed-priority preemptive schedules for' that workload are feasible. This result is exact when task arrivals are assumed to be independent and might occur simultaneously, that is, no assumptions are made about the initial arrival times of the tasks, and this result is said to be exact for all task phasings. The schedule used to analyze the feasibility of a task rj is defined by the workload Wiit) at a critical instant. The workload due to all tasks with higher priority than TJ is referred as a function of time m A. m) = ECA¥l (2-4) i=i J The times at which this schedule must be checked are the scheduling points (arrival times) for tasks T i . . . r t - up to T J . If r,- completes by any of these scheduling points, then Ti will always be feasibly scheduled. Theorem 2.4 gives a necessary and sufficient condition for the first request of each task to meet its deadline. Theorem 2.5 (Lehoczky) Given periodic tasks r i , . . . , r n ; 1. Task Ti can be scheduled for all task phases using the rate monotonic algorithm if and only if L%= min ^ 2 < l ' (2.5) { 0 « < T J t ~ 2. The entire task set can be scheduled for all task phases using the rate monotonic algorithm if and only if ' max Li < 1 (2.6) {0 j, the response time of task i is greater than that of task j and the response time of i is effected by all the tasks with higher priority when all tasks release at the critical instant. This analysis requires calculating the worst-case response time of each task by the following equation [Joseph 86]: . . . RTt = E \ ^ ] xCj + Ci (2.8) where the RTi is the worst-case response time. In the equation, the first part is the sum of the computational requirements for all tasks with higher priority occuring in Chapter 2. Background 21 the interval [0, RTi), and the second part is the computational requirement for itself. Unfortunately, the response time is hard to solve from Equation 2.8. Joseph and Pandya [Joseph 86] introduced an approach to calculate the response times for a task set using the rate monotonic scheduling algorithm. The approach is based on the recognition that once the execution of task i is preempted, the instance of its resumption is independent of the order of arrival of requests at higher priority level. First we define a time interval [t,t') which contains all values from t up to t', but not including t'. During this interval the maximum number of requests from task j is . Inputs([t,t'),j)=\^-\^ (2.9) and its required computation time is Comp([t,t'),j) = Inputs([t,t'),j) x Cj (2.10) So the computation time needed for all invocations at levels greater than i can be defined i-1 Comp({t,t')) = J2lnputs([t,t'),j)xCj " (2.11) j=i For calculation of the response time of task i, we first initialize t'=to+Ci. If Comp([to,t')) is zero, no preemption occurs. Task i uses the whole time from t to t'. Then the response time is t'-t. Otherwise we extend t' to i'+CompQirj+i')) which means extra time is needed to handle the interference of preemption. We substitute t with f and t' with i'+CompQto+i')) a n < ^ calculate the Comp([t,t')) until we find Comp([t,t')) or t' exceeds the deadline of task i which means the task i couldn't finish its execution before its deadline. The above procedure can be generalized to the following recursive definition of function R(t,t',i) Chapter 2. Background 22 Response(t,t',i)= if Comp([t,t'))=0 then t' else Response(t,t'+Comp([t,t')),i) The worst-case response time at level i can be defined as Ri = Response(0,Ci,i) (2.12) where the task i releases at the critical instant. 2.6 P a r k ' s A l g o r i t h m Park et al. published two articles [Park 95, Park 96] on period-specific utilization bound algorithm. The first one focuses on the detailed procedure of calculating utilization bound and the second one talks about the proofs of the algorithm. First, the overview is presented. Then, we discuss a flaw in the second paper. • 2.6.1 P e r i o d - S p e c i f i c U t i l i z a t i o n B o u n d I The period-specific utilization bound I procedure (PSUB-I) [Park 95} provides a more accurate utilization bound than Liu and Layland's theory -by accommodating task periods and deadlines. It also extends its usage range to any fixed-priority scheduling algorithm. The following assumptions are made in this model: 1. A l l tasks are periodic. 2. A l l tasks are independent. 3. A l l system overheads are ignored. 4. A l l tasks are assigned a fixed unique priority, and scheduled by priority-based preemptive algorithm. Chapter 2. Background 23 The objective of this technique is to determine the exact utilization bound with-out the knowledge of task computation times.. In order to determine the system utilization bound B(Park), a series of individual utilization bounds [/*, , U* are determined such that individual task TJ will meet all its deadlines whenever the combined utilization of tasks 7~i, T 2 , T; is less than U*. When the task deadlines are deferred, U*j is defined as the utilization bound of the jth request of task r,-which means the jth request of task r, meets its deadline whenever the utilization of T i , r 2 , T ; is below U*j. So, the individual utilization bound depends on £/*•. Linear programming is used to evaluate Bij by formulating a set of constraints with the deadline requirement for the scheduling algorithm. The procedure to evaluate U*- is minimize = £ 7 ^ (2-13) fc=l ± k subject to L 1 m J v m = i ? v ; = i and E r ^ C * + rmn(j, \^)Ct] > lTm (2.14) k=l 1k li i\^Ck-\>Dl3 (2.15) k=i 1k and Cj > 0 . l < j < i . (2.16) Then the individual utilization bound is 17 = mini (-) (2.17) Chapter 2. Background 24 and the utilization bound is B{Park) = min(U*) , - (2.18). Equation 2.14 ensures no idle time is permitted prior to the release point of each task in the interval [0, lTm]. Minimization in this inequality ensures that for task T j , the executions of requests later than the jth request are not taken into consideration in the process of determining that there is no idle time because considering up to request j is required as the deadline is greater than the corresponding period. The inequality in Equation 2.15 states that there should be no idle time during deadline The iterative calculation U*- will terminate when j reaches [LC M(T\,T2, T n ) / T ; J , where L C M represents the least common multiple, or there is no solution for the jth request. This means r,- has finished by the time jT{ for any set of computation times so there will be no extra computation demand subsequent to the request of T J . In some circumstances, this approach calculates the exact utilization bound. This will be discussed further in chapter 3. 2.6.2 Period-Specific Utilization Bound II Park further proposed the period specific utilization bound II (PSUB-II) proce-dure in which he focused on a model that task deadlines are not greater than their periods[Park 96]. He also gave some useful conditions and theorems. Condition 2.1 (Park). There is no idle processor time prior to the first deadline of task T j . . Condition 2.2 (Park). All tasks with higher priority that arrive before the first deadline of task Tj must be finished before the first deadline of task T J . Chapter 2. Background 25 Corollary 2.1 (Park). Y!j=lCj x \D{/Tj] = Di if and only if the previous two conditions are true. Theorem 2.6 (Park). The utilization bound U* for the schedulable task Ti can be achieved by the following procedure: Minimize Ut = t^ (2-19) i = i i subject to ± C 3 x \ ^ ] = D i (2.20) and Cj > 0 1 < j < i. • • (2.21) The condition Y])-i Cj x = Di is intended to constrain the task set to be just feasible. The following theorem follows the Corollary 2.1. Theorem 2.7 (Park). The period specific utilization bound (PSUB) for the entire system is the smallest U* among all tasks. That is, PSUB = minnmzzlU*m 2.6.3 Discussion Park's PSUB-II procedure, as published, has a problem in Corollary 2.1 which we illustrate here by two examples. The first example shows that the solutions obtained using Park's procedure permit idle time during the first deadlines of some tasks, which means that the solution is sub-optimal. The second example shows that the procedure does not guarantee the schedulability of the task set. According to the definition of a just feasible task set, there should be no idle time in the interval [0,D n]. Otherwise, there is some idle time A before the first deadline. Chapter 2. Background 26 Then, the computation time of.task r„ can be increased up to A and the task set is still feasible. But Park's procedure does not lead to correct results in the following two instances: Instance 1: a task set {r 1 ,r 2 , r3} TI = {Cl , 10,10,0}, r 2 = {C2,12,12,1}, T 3 = {C3,25,25,2} . When C={CUC2, C73}={2.5,5,2.5}, the utilization bound is 0.-7583. Instance 2:a task set {TI, T 2 , T 3 } h = {CT,7,7,0}, r 2 = {C2,12,12,l}, r 3 = {C3,47,47, 2} When C={d,C2, C3}={5,3,0}, the utilization bound is 0.9640. Here each task is represented by four parameters in order: computation time, period, deadline, and priority. Both examples satisfy the condition \T3/Tl] x C l + [T3/Tl] xC2+C3 = 25 = D3. Figure 2.2 demonstrates the run time behavior of the two systems. In A, task 2 delays its completion for 4.5 units which is equal to the sum of total idle time so the condition does not recognize the existence of idle time. The deferred completion violates Condition 2.1 as well. In B, besides the ignored idle time, task 2 misses its first deadline which can not be guaranteed by the constraints. As a solution to the idle time problem, Corollary 2.1 should be modified as Corollary 2.2 Yl)=i Cj x [Di/Tj] = Di if the two previous conditions are true. Proof. If there is no idle time prior to the first deadline of task r,-, there exists-one task running at any instance during [0,D;). Since the number of each task j j < i released in the period of Di is \Di/Tj], the total execution time of task TJ is Cj x \Di/Tj~\. Therefore the total execution time at priority levels equal to or less than i is Y?j=i Cj x \DijTf\ should be greater than or equal to Di. In Condition 2, Chapter 2. Background 27 Figure 2.2: Time lines for two task sets Chapter 2. Background 28 all tasks with higher priority that arrive before the first deadline of task r4- must be finished before the first deadline of task TJ . Then the total execution times of all tasks with higher priority should be less than or equal to D t . Moreover task r,- must finish its own computation before Di, otherwise its deadline is missed. So TJj = 1 Cj x \Di/Tj] should be less than or equal to Di. Therefore, EJ - i Cj x \Di/Tj] = D{. QED However, if Y?j=1 Cj'x \Di/Tj] = Di, it's possible that there might exist idle time prior to the first deadline of task T ; as illustrated by the aforementioned examples. The condition that there is no idle time at each task release points is therefore required to constrain the solution. In both of Park's procedures to calculate U*, feasibility constraints are excluded. Therefore the feasibilities of all tasks but r8- in a task subset { r i , r 2 , . . . ,T ; } won't be guaranteed. Due to the nature of the linear programming, the inequalities ensure that one of the deadlines will just be met. That means that the linear programming will obtain the optimum value when it reaches one of the inequalities. In the. case of Di < T, each individual utilization bound U* only guarantees the deadline of task Ti is met. Since only one task is guaranteed to meet its deadline, the procedures are. iteratively performed for each task to ensure that all deadlines will be met. 2.7 S c h e d u l a b i l i t y A n a l y s i s T o o l In contrast to the aforementioned mathematical treatments of schedulability tests, the graphic method for schedulability test is not only sufficient and necessary, but it also gives detailed indication of the actual response times of tasks and the compu-tation time left after a task misses its deadline. The schedulability tests only give a Chapter 2. Background 29 "yes" or "no" answer to a tested system. A graphic schedulability analysis tool also can illustrate the run time behavior of a process according to the scheduling algo-rithm. Gantt charts and time-lines, such as those represented in Figure 2.2, are two useful ways of demonstrating execution patterns. Schedulability analysis proceeds by starting the execution in the critical instant represented at time 0. The schedulability analysis tool (SAT) developed for the thesis is an extended graphic test tool to automatically create a Gantt chart for a given real time system under a given scheduling algorithm to test the schedulability of the system, illustrated in Figure 2.3. SAT provides an X windows-based colored graphical user interface environment. The graphical user interface consists of three types of windows: the display window, the task information window and the control panel window. In the display window, Gantt charts illustrate the execution slots of each task over time. Different tasks are denoted by different colors. The heights of rectangles of task execution are classified into 3 types where the highest rectangle represents the execution of the first request; the shortest one is for consecutive requests; and the rectangle with medium height denotes the idle time in the processor. Only the first request is illustrated in the graph because this is sufficient to test the schedulability of a real time system with the rate monotonic or deadline monotonic algorithms. The time interval is up to the least common multiple of all task periods which is required for a real time system with deferred deadlines. The task information windows present task parameters such as task name, re-sponse time etc. The control panel window provides the user .with buttons for in-putting task parameters, assigning task priorities satisfying the rate monotonic algo-rithm, plotting the Gantt chart and performing other related functions. The schedulability analysis tool is written in T C L / T k because of its flexibility and productivity. Since T C L / T k is an interpreted language, it's convenient to design Chapter 2. Background 30 a prototype and fix bugs. The low execution efficiency can be circumvented by re-implementing parts of scripts in C, because T C L / T K provides the interfaces to other languages such as C. Moreover, with the help of Tk, a toolkit for the X windows system, building user interface becomes a pleasurable job. Chapter 2. Background 31 Figure 2.3: The user interface of the schedulability analysis tool Chapter 3 Exact Feasible Utilization Bound The estimated system utilization bound based on Park's algorithm departs from the actual value because of the minimization of the individual utilization bounds. The minimization step must be performed since the constraints in the Park's procedure to obtain the individual utilization bound do not guarantee the feasibility of tasks other than the one with the lowest priority. Our proposed algorithm of exact feasible utilization bound takes into account the feasibility constraints of other tasks. In our model, the task deadlines do not exceed their corresponding periods. 3.1 Overview of the Algori thm Our algorithm is based on linear programming to compute the exact utilization bound with three sets of constraints for a real time system: 1. Full utilization constraints which guarantee no idle time is allowed during the assigned time interval. 2. Task schedulability constraints which guarantee all tasks meet their correspond-ing deadlines. 3. Computation time constraints which limit the computation time ranges. We set the computation time of each task to be not less than 0 and not greater than . its deadline. , 32 Chapter 3. Exact Feasible Utilization Bound 33 Then minimization is performed on the system utilization to determine the lowest utilization for a specific task set. Our algorithm accommodates task schedulability constraints which do not exist in Park's algorithm. Both full utilization and task schedulability constraints guarantee the feasibility of a real time system' whose uti-lization is under the minimal utilization. To find a set of task schedulability constraints we adopt the iterative method to obtain system utilization bounds of its priority subsets. Each subsystem utilization bound Bk of a subset { r i , T k } , k > 1 is regarded as a constraint for its superset { r i , T k , T f c + i } in order to calculate the bound Bk+i. Since Bi,...,Bk guarantee .the feasibilities of tasks T\,...,Tk and the full utilization constraints can guarantee the feasibilities of task Tk+i, then we obtain a feasible subsystem utilization bound. Hence, the system utilization bound is the least priority task set utilization bound. This method is demonstrated below. Assume there are three tasks { n , T 2 , T 3 } in . a system along with a periodic time set and a deadline set where the ratio of any two periods is less than 2. Since 0 Dl \^]d + C2>D2 and task schedulability constraints: c y v , < ih and computation time constraints: 0 < C i < D i < Ti 0 < C2 < D2 < T 2 . Chapter 3. Exact Feasible Utilization Bound 34 Then B3 is determined by full utilization constraints: C1 + C2 + C3> Dl \^]C1 + C2 + C3>D2 J-i \%r]Ci + &]C2 + C3>D2 ±1 i2 and task schedulability constraints: Ti T2 ~ and computation time constraints: 0 < Ci < Di Di'. According to lemma 2.2, tasks T i , T 2 , r , - _ i complete their execution before Di, so task Tz- doesn't finish its execution until Di + 5. We also, know there is no idle time before Di, otherwise task r,- would execute during the idle time. We create a different set of computation times so that •' . C\ = C%-& We also know there is no idle time before Di, otherwise task TJ would execute dur-ing the idle time. In this case, the new computation set still maintains full utilization. This transformation, as well, preserves the schedulability of the task set because task Ti completes before its deadline D{. Hence, the new utilization bound is «-«-* Since S/Ti is always positive, the new utilization can only be smaller than or equal to the original one. This violates the assumption that Bi is minimal. Therefore, with the full utilization constraints, the schedulability of task Ts- is guaranteed. Lemma 3.2 For a task set {T\, Tn\n > 2}, Bi is the utilization bound of its priority i subset. In fixed-priority preemptive real time systems, tasks T i , T 2 , T n are still schedulable if and only if V n . 771 = 1 m £ f J^TjT < B m . t = l i l Proof. First the sufficiency is proved by induction on number of tasks. The system utilization of one task is 1. When C\jT\ < 1, task T\ is schedulable. For a 2-task system, task T 2 is also schedulable as C\jT\ + C 2 / T 2 < B2 by Lemma 3.1. Chapter 3. Exact Feasible Utilization Bound 36 On the other hand, when task T\ is schedulable, the computation time must be less that its deadline. Therefore, the utilization of task T\ is less than or equal to 1. Assume Ci/Ti + C2/T2 = B2 + S. Since the optimal solution of computation time is C*, when C^/Ti + C2/T2 = B2, the system is schedulable and any increase of computation time will result in non-feasibility. We create a computation set {C1,C2}, where C[ = C{ C2 = ST2 + C2. As 8 > 0, the fact that C2 is greater than C^ causes the system to be infeasible. So we conclude that C\jT\ + C2/T2 < B2. Assume that tasks TI,T2, ...,Tk-i are schedulable if V/k-l v m = i m C' in a task set {ri, T 2 , • When the number of tasks is k, Bk is the utilization bound of {T I , T2 , T ^ - I , T ^ } . For preemptive fixed-priority scheduling, the higher priority task can preempt the current processing task with lower priority. Hence tasks Ti, T 2 , . . . , r&_i are schedulable if v m = l m in a task set {ri, r 2 , T k - i , r^}. For task r^, when YULiCi/Ti < Bm, it meets its deadline. Therefore, all tasks are schedulable. Now we prove the necessity of the condition. Assume one priority subset has a higher utilization than its corresponding utilization bound arid all tasks are still schedulable in any case. We know that V ^ , £™ 1 Q/Ti < Bm are' satisfied if tasks Chapter 3. Exact Feasible Utilization Bound 37 T i , T 2 , . . . , Tk-i are schedulable. We suppose a priority k subset has a higher utiliza-tion, that is, YJl=i Ci/Ti = Bk + S. As the optimal solution is C**, there exists a computation time set in which Cx = CT u 2 — u 2 Since 5 > 0, the computation time of task increases. This causes task to miss its deadline in the critical instant. So Y A = 1 Ci/Ti < Bk must be satisfied. The condition Xw=i Ci/Ti < Bk is called the task schedulability constraint. Theorem 3.1 The subsystem utilization bound Bn for the schedulable task set { T I , T can be achieved by the following procedure-Minimize ^ = E § • (3-22) i=i i j subject to V ^ = 1 and \/nm~=\ and \ C = 1 E\^Ci>Dm (3.23) £ ^ < # m (3.24) ct- < o Proof. From Lemma 3.2, tasks r 1 , T 2 , . . . , r „ are feasible because of Eq. 3.20. Equa-tion 3.19 ensures the schedule is full utilization. Consequently, Bn is the subsystem utilization bound. Chapter 3. Exact Feasible Utilization Bound 38 Theorem 3.2 When the individual subsystem bounds of a task set are B\, B 2 , B n , the system utilization bound B(E) can be up to Bn as U\ < B\, U2 < B2,..., Un-i < Bn-i • The proof follows from Lemma 3.2. 3.3 Procedure of the A l g o r i t h m We present the procedure to determine the system utilization bound. In the proce-dure, Bi is calculated by Equation 3.18. Assume that there are n tasks in a system. Step 1: If all Cimax, C 2 m a x , C n m a x is bounded then perform the exact shedulability test by Equation 2.7 if feasible, then JB(£) = 100% meaning the system is alway feasible when Ci < C i m a x and terminate. Step 2: If any task does not pass the test with Cimin, C2 min i • • • i C n m i n Terminate (because the system is not feasible)' Step 3: For i = l to n Calculate the priority i subsystem utilization bound Bi Step 4: B{E)=B, Chapter 3. Exact Feasible Utilization Bound 39 3.4 D i s c u s s i o n a n d C o m p a r i s o n In this section, we first take a look at the specific task sets which lead to the worst case utilization bound in Liu and Layland's- algorithm. Then, Park's approach, is compared to Liu's to demonstrate its improvement. Finally, exact feasible utilization bounds are compared to Park's utilization bounds. This section also discusses the cause of the pessimism in Liu and Layland's and Park's techniques. Liu and Layland showed that a task set { r 1 ? . . . , T N } has a relatively low utilization bound when the ratio between two request periods is less than 2. The worst case utilization bound occurs when -_ J i _ _ L = 2 — - 1 z = l , . . . , n - l . A task set gains its worst case utilization bound when task's periodic times satisfy Ti = 2~^Tn i = 0,1, - 1. This specific task set has the exact utilization bound equal to n(2 1 / , r a — 1). Therefore, the utilization bounds of all task sets with 2 tasks are the utilization of a specialtask set that has corresponding task periods {0.707,1}. As for a system with 4 tasks, the special task period set is {0.595,0.707,0.8409,1} or a task set whose members are the multiple of the corresponding member in the special task period set, such as {1.19,1.414,1.6818,2}.' ' Park has taken account of task periods to determine the utilization bound because task periods in hard real time systems depend on physical laws and/or requirements which may be known before the design. Park has proved in [Park 93] that.his approach can obtain the same or better utilization bound of a real time system than Liu and Layland's algorithm. Chapter 3. Exact Feasible Utilization Bound 40 Period Set m 77* • ui B(Park) B(Liu) {50,65,94,98} 2 •2 2 0.8385 0.8100 0.8091 0.8091 0.8091 {35,63,78,79} 3 2 2 0.9111 0.8525 0.8459 0.8459 0.8332 {7,25,53,59} 9 3 2 0.9314 0.9421 0.8772 0.8772 0.8651 {5,49,107,483} 97 10 4 0.9837 0.9313 0.9447 0.9313 0.8651 Table 3.1: The comparison of Park's and Liu's algorithms. First, the two algorithms lead to the same exact utilization bounds when the ratio between any two periods is less than 2 for a given task set {T\, T2, r n } . The exact utilization bound can be calculated by Liu and Layland's equation: ( r n . - r 1 ) ( T n - . 2 T 1 ) , " lTn-Ti)(Ti.1^Ti) B(Liu) = 1 + Since Tn — 2TX < 0 (because Tn/Ti < 2 and T;_i — Ti < 0 ), B(Liu) will decrease with the increased task number, that is Bi(Liu) > B2(Liu) > ... > Bn(Liu). In Park's algorithm, the individual task utilization bound U* is equal to Bi(Liu). Therefore the minimization in Park's algorithm does.not affect the accuracy of the system utilization bound. Both methods obtain the same results. However, Park's approach shows its advantage when the minimum ratio between' task periods is greater than 2, as illustrated in Table 3.1. In the table, the exact utilization bound in the last column is obtained by multiplying the task periods that are less than half of the longest period to make all ratio of any two tasks to be less than 2, and then applying Liu's exact utilization bound formula to the modified system. Although the performance of Park's technique is generally better than Liu's, it is not able to obtain the exact utilization bound for the last task set in Table 3.1. When the system utilization bound is 0.9313, there exists idle time during the time [0,483]. can not be the system utilization bound since the feasibilities of all tasks are not guaranteed.' Chapter 3. Exact Feasible Utilization Bound 41 No Period Set B2 B3 BA B(E) u; us U*A B(Park) 1 {50,65,94,98} 2 2 2 0.8385 0.8100 0.8091 0.8091 0.8385 0.8100 0.8091 0.8091 2 {300,400,605, 2 2 2 0.8333 0.8307 0.9860 0.9860 1190} ' 0.8333 0.8307 0.9837 0.8307 3 {19,23,39,105} 2 2 3 0.8627 0.8587 0.9097 0.9097 0.8627 0.8587 0.9092 0.8587 4 {5,9,61,68} 2 6 2 0.9111 0.9687 0.9089 0.9089 0.9111 0.9687 0.9089 0.9089 5 {14,44,50,63} 3 2 2 0.9788 0.8964 0.7932 0.7932 0.9788 0.8964 0.7932 0.7932 6 {5,28,31,74} 6 2. 3 0.9571 0.9135 0.8717 0.8717 0.9571 0.9135 0.8717 0.8717 7 {7,25,53,59} 4 3 2 0.9314 0.9421 .0.8772 0.8772 0.9314 0.9421 0.8772 0.8772 8 {5,49,107,483} 10 3 4 0.9837 0.9313 0.9447 0.9447 0.9837 0.9313 0.9447 0.9313 . Table 3.2: The comparison of Park's and Our algorithms. Table 3.2 shows the comparison between our technique and Park's approach. As the individual utilization decreases with the increased number of tasks, items 1 and 4 show that our approach can obtain the same subsystem (individual) utilization bounds and system utilization bound as Park's algorithm. When there is no decreasing function of the subsystem utilization bounds, Park's algorithm gives a relatively poor result due to minimization as shown in item 8. Items 2 and 3 indicate that the two approaches have different system utilization bounds when B4 and U%- are no longer the same. We take a close look at item 2 in Table 3.3. As the optimal solution of U% is computation time set {5,0,580,10}, the utilization of the first three tasks is C?i/Ti + C2/T2 + C3/T3 = 5/300 + 580/605 = 0.9753, which exceeds the individual utilization bound U3. To calculate B4, constraint Chapter 3. Exact Feasible Utilization Bound 42 Subset E F U B Park's B C Solution U* C Solution 2 0.8333 100,200 0.8333 100,200 3 0.8307 5,200,190 0.8307 5,200,190 4 0.9860 0,0,502.58, 184.83 0.9837 5,0,580,10 Table 3.3: The comparison of computation times in Park's and our algorithms. Figure 3.1: The perspective of utilization bounds C\jT\ + C2/T2 + C^jTz < Bs causes the feasible region (the set of all feasible points— a point is feasible if it satisfies all constraints) to shrink in linear programming and the optimal value varies. Consequently, B4 > U%. 3.5 Perspective on Utilization Bounds In the perspective on utilization bounds shown in 3.1, the universal set includes all real time task sets being scheduled by fixed priority scheduling algorithms. This set is classified into 2 subsets: feasible task sets F and infeasible task sets I. The feasible Chapter 3. Exact Feasible Utilization Bound 43 subset also consists of another subset, just feasible task set J. For a task set S, there exists an assignment of computation times which makes the system just feasible. The system utilization in S with this specific computation time set is the utilization bound of S. When the task set has a different computation set, the corresponding system will fall in either the infeasible area or the feasible area. If the utilization of a computation set is less than the utilization bound, the schedulability of the system including the computation set is guaranteed. Liu and Layland's theory only considers the utilization bound for a particular subset L of J , in which a specific task set represents all task sets with the same number of tasks, no matter what their periodic times are. Park's approach covers a larger area W where individual task's periodic times are taken into consideration but the system utilization bounds of some task sets are forced to be the values of their corresponding- subsystems. For example, the utilization bounds of the task sets with periodic sets {19,23,39,105} and {19,23,39,105,220} are determined by a task set with periodic sets {19,23,39}. From the above discussion, our algorithm is an extension of both Liu and Park's algorithm. The exact feasible utilization bound for a subset E of J covers L and W. 3.6 C o n s i d e r a t i o n on S o m e K n o w n C o m p u t a t i o n T i m e s In the preceding section, we have discussed how to estimate system schedulabilities in a real time system with unknown computation times in the design phase. Our approach can also be used in the successive phases of software development life-cycle. After a few tasks have been implemented in the coding phase or redesigned during maintenance, some tasks' execution times are known. Since we adopt a range for all computation times, the feasible region is relatively large and the calculated Chapter 3. Exact Feasible Utilization Bound 44 utilization bound is relatively rough. If some computation times are known, the system utilization bound may get larger. The procedure to estimate system utilization bound with some known computa-tion times is different from the general one m that Cxmin — Cimax — C\ m steps 1 and 2 (of our procedure in Section 3.3) and the priority i utilization bound is set to 100% without calculation. The increased system utilization bound may be achieved by using precise com-putation times, which is demonstrated in the following example. Assume a period set in a task set is {14,44,50,63}. We know the system utilization bound reaches' 0.7931 when the computation time set is {0,6,13,25} under the condition U\ < 1, Ui < 0.9610, and U3 < 0.8792. It is reasonable to assume that the system utilization can be over 0.7931 because the computation time of task 7~i can not be 0. If C l is 5, the system utilization bound is increased to 0.8393. This utilization bound also belongs to the subset J in Figure 3.3 but is not covered by subset E. 3.7 Environmental Issues Now we will examine how our utilization analysis approach can be applied to real-world real time systems. 3.7.1 Sporadic Tasks Sporadic tasks play an important role in real time systems. A sporadic task is released by an event originating either from another task or from the environment of the system through interrupts. The common idea to deal with sporadic tasks is the sporadic server algorithm [Tilborg 90]. The sporadic server algorithm creates a periodic task TSS that is assigned: Chapter 3. Exact Feasible Utilization Bound 45 1. a computation budget Css, 2. a replenishment period Tss which is the minimum event inter-arrival time, 3. a priority Pss. When the interrupt event occurs, task TSS is scheduled with priority Pss until the task completes execution or the computation budget has been used ,up. If the request has not been serviced completely, task TSS will be resumed in Tss — Css time units. Otherwise, task r s s is in the idle state in which the computation budget is replenished. The following request will not be scheduled during Tss — Css time units. By applying the sporadic server algorithm, a sporadic task is treated like a periodic task and several sporadic servers can be defined at different priority levels to handle different aperiodic events. The discussed scheduling algorithm and schedulability analysis can be carried out in a system with both periodic and aperiodic tasks. 3.7.2 T a s k S y n c h r o n i z a t i o n Priority-based preemptive scheduling assumes that a higher priority task can preempt a lower priority task being run with no penalties in time. The problem of blocking is caused by the synchronization of tasks that share physical or logical resources when a process is suspended waiting for a low-priority task to complete some required computation. Synchronization mechanisms may lead to an unbounded duration of priority inver-sion, multiple blocking, and mutual deadlock because of the nature of task synchro-nization including semaphores, locks, monitors, and rendezvous which is necessary to protect the consistency of shared data and the correctness of computation. The run time behavior of each task becomes unpredictable. Chapter 3. Exact Feasible Utilization Bound 46 In this thesis the priority ceiling protocol [Rajkumar 91] is considered because it addresses the above problems. In this protocol, besides the static priorities of each task, each critical section has a static ceiling priority value which is the maximum priority of the tasks accessing the critical section. The underlying idea of this protocol is to ensure that when a task r preempts the critical section SI of another task and executes its own critical section, the priority of task r is guaranteed to be higher'than the priority of ST. This idea is realized by first assigning a priority ceiling to each semaphore, which is equal to the highest priority task that may use this semaphore. Then task r starts a new section only if r's priority is higher than an priority ceilings of all the semaphores locked by tasks other than r. The blocking is bounded to the maximum critical sections, bk, 1 < k < n. Each task but one with the least priority may experience the blocking if they synchronized with other tasks. The blocking of task T{ is equal to maximum worst case execution time of all lower priority level tasks in the same critical section. Therefore when task r,- has to access the critical section Si and tasks T 2 _ I , T,- +I and T j + 3 also access the same section, task r,- can be blocked by tasks TJ+I and r,-+3. The blocking time Cbi is the maximum worst case execution time of T ; + i and rT-+3 in S\. In the schedulability test, the" blocking time can be treated as part of the worst case computation time, so.the new computation time becomes C ; = C i + . C 7 w . ' (3.25) 3 . 7 . 3 S c h e d u l e r O v e r h e a d The context switch and queue manipulation time has not been considered yet in a scheduler, which may be of significance and affects the schedulability as the sys-tems become more and more complex. We consider interrupt event-driven scheduling Chapter 3. Exact Feasible Utilization Bound 47 which is quite popular and can be adopted by schedulers using rate monotonic and deadline monotonic algorithms in which periodic tasks are activated by system timers [Katcher 93]. In this scheduling, every interrupt is responded to and all tasks are trig-gered by external interrupts. If the arriving task has a higher priority, it preempts the current task. Otherwise, the arriving task is rescheduled and put in the ready queue and the current task continues running after a brief interference. Hence the overhead for a task with higher priority than the current one is C p r e e m p t and for a task with lower priority, it is Cnonpreempt- Besides that, each task has an exit process time. Cpreempt — Cint ~1~ Csf0re ~\~ Cload (3.26) C exit — Ctrap + Cload (3.27) Cnonpreempt — Cint ~\~ Csched H~ C r e s u m e (3.28) where Cint is the time to handle an interrupt, Cstore represents the time to save the state of the active task to a task control block, Cioad is the time to load the new active task state, and C i r a p equals to the time to handle the trap generated by normal completion of a task, Csched is the time to execute the scheduling code to determine the next task to run, C r e s u m e represents the time to return to the previously active task when a preemption does not occur. As the execution time of system overhead is deterministic in hard real time systems, the time of Cpreempti Cnonpreempt-, and Cexit are constant values'. So each task will suffer the overhead C0 up to either C p r e e m p t + Cexa or Cnonpreempt + Cexu- The effect of the overhead can be treated as C'i=Ci + C0. (3.29) Chapter 3. Exact Feasible Utilization Bound 48 3.7.4 The Effect on Subsystem Utilization Bound The blocking and overhead time effect the calculation of the subsystem utilization bound as follows: Theorem 3.3 The subsystem utilization bound Bn for the schedulable task set { r i , r , can be achieved by the following procedure-Minimize n c: (3.30) subject to V: '71 m = l 1=1 1 m (3.31) and V! '71—1 771 = 1 771 (3.32) and V: '71 771 = 1 Ci < Chi, ~y C0 Chapter 4 Case Study This chapter discusses two real time systems to demonstrate how to apply the utiliza-tion bound analysis technique developed in the previous chapter in the design phase. The two systems are respectively a mine pump control system and a hydraulic motion platform simulator. We follow the procedure of software engineering to identify and analyze functional and timing requirements, then decompose the system into subsys-tems and structure subsystems into concurrent tasks. Furthermore, we construct a system model that determines each task's period and deadline according to the timing requirements, and then assign a unique priority to each task. With the system model, we apply the exact utilization bound approach to calculate the utilization bound. Throughout the case study, several practical issues in hard real time systems are addressed including • Non-critical tasks. Non-critical tasks often exist to perform housekeeping work in hard real time system. When we design this kind of task, we must ensure the schedulability of critical tasks and assign a reasonable computation time to non-critical tasks. • Non-periodic tasks. • Tasks without a stringent period. When the minimum arrival rates of some tasks is in a range, such as tasks interacting with operators, we can assign their periods as a multiple of another task's period. In this case, the C P U resource 49 Chapter 4. Case Study 50 can be fully exploited and schedulability analysis is simplified. • Task deadline much less than its period. An extended approach of the exact utilization bound is suggested to analyze the utilization budget of a task with very low maximum task, utilization. 4.1 Mine P u m p and Control System The mine pump and control system is intended to monitor the levels of carbon monox-ide, methane and airflow and to pump water out of a sump if percolating water is high and to set an alarm if necessary [Joseph 86]. The system is depicted in Figure 4.1. The functional requirements are as follows: 1. Water is pumped out of the mine if water is above the high level D under the condition that the methane level is below a critical level. 2. The pump is switched off when the water goes down below the low level E and the level of methane exceeds the critical value. 3. The mine must be evacuated within one hour of the pump failing. 4. An alarm is raised and operator is informed within one second when any level of carbon monoxide, methane and airflow exceeds the corresponding critical value. These data are sampled periodically. 5. Human operators can control the operation of the pump if the water is between the low and high water levels under the condition that the methane level is below a critical level. 6. The supervisor can operate the pump under the condition that the methane level is below a critical level. Both supervisor and operator can check the current Chapter 4. Case Study 51 Water-high Water-low Methane sensor Carbon monoxide sensor Airflow sensor Mine Pump and Control System Pump Data file Alarm Monitor display Operator Figure 4.1: The system diagram of the mine pump and control system sampling data at any time. 7. Data from all sensors and a record of the operation of the pump must be logged for later analysis.. In addition the timing requirements of nonfunctional requirements are also listed: 1. Emergency shut down following a high methane value reading: the deadline is 30 milliseconds. Chapter 4. Case Study 52 2. Recognition of monitor failure and pump shut down: the deadline is, 65 millisec-onds. 3. Turning the pump on again when it is safe: the deadline is 100 milliseconds. 4. Turning the pump on (if safe) when the water is high: the deadline is 100 milliseconds. 5. Turning the pump off when the low water level has been reached: the deadline is 75 milliseconds. 6. Signaling an alarm if any environmental condition warrants it: the deadline is 50 milliseconds. Since the software design methods of a real time system [Gomaa 93] is not a concern in this thesis , the design procedure is not detailed and only the design of functional requirements are outlined. H R T - R O O M (Hard Real Time-Real Time Object Oriented Modeling) is used to design this real time system [Joseph 86]. Based on H R T - R O O M the mine pump and control system can be decomposed into four subsystems: • . the pump controller • the environmental monitors(for airflow, methane and carbon monoxide) • the data logging subsystem • the operator's subsystem ' .. - . Figure 4.2 shows the task modules and communications among the tasks. Then we will construct the system model based on the timing requirements and task modules. Chapter 4. Case Study 53 r Pump Controller Subsystem interrupt IH s Environmental Monitor Subsystem OP s i i i LT Operator i P Subsystem Data Logging Subsystem MM P AM P CM P A periodic task A control flow A protected shared object A sporadic task A data flow Figure 4.2: Design for the mine pump and control system Chapter 4. Case Study 54 4.1.1 System M o d e l To meet both the functional and non-functional requirements, the system can be modelled as a set'of concurrent tasks and shared objects through-which tasks com-municate with each other. Tasks may be periodic or sporadic. A periodic task is released by a timer event and a sporadic task is activated by external interrupt or another task. In the mine pump and control system, tasks Methane ^ Monitor (MM), Air_Monitor (AM), CO_Monitor (CM), and Safety .Checker (SC) are periodic tasks. The first three tasks sample data periodically from the corresponding sensors and process the data because most of signal processing algorithms are based on evenly spaced samplings. The periods of the tasks are decided according to the timing requirements. Since the emergency shut down must be performed within 30 milliseconds when the level of methane is high, the worst case is considered when the level of methane exceeds the threshold just after the sampling. Therefore the sum of sampling interval and response time is set to be 30ms. We can either set both the period and deadline to 15ms or period 20ms and deadline 10ms by reducing the task service times. Because the task M M has a relative high priority in the system, we adopt the latter assignment. Tasks A M and C M are designed with both the period and deadline of 25ms due to the fifth timing requirement. Task SC detecting the failure of pump and monitors within 65ms is assigned a period of 35ms and deadline of 30ms. Tasks HS and LS are sporadic tasks triggered by interrupts. An extra task In-terrupt .handler (IH) is created to respond to the hardware interrupts and invoke the corresponding task. Task IH can be regarded as system overhead to other tasks as its function is to make the system reschedule between the running task and ready tasks. Chapter 4. Case Study 55 Name of Task Class Symbol Period T (ms) Deadline D (ms) Priority P MethaneJVfonitor Periodic M M 20 10 1 • AirJVIonitor Periodic A M 30 20 2 COJVlonitor Periodic C M 30 20 3 Safety_Checker Periodic SC 35 30 4 High_Sensor Sporadic HS 10000 100 5 Low_Sensor Sporadic LS 10000 • 75 6 Interrupt JHandler IH 0 Logging_Task Periodic LT 600 600 7 Operator Sporadic OP 8 Controller PSO CT 1 Methane_Status PSO MS 1 Logging PSO LO 1 Table 4.1: Mine control tasks and protected shared objects. The equations from 3.26 to 3.29 are suitable for task IH to calculate the system over-head of tasks HS and LS. The period of task IH depends on period of tasks HS and LS. The minimal inter-arrival time of tasks HS and LS is related to.the rate of water percolating that comes from the previous records. Suppose that it takes 10 minutes for water to raise from the low level to high level in the sump, that is, the minimum inter-arrival interval of external interrupt is 10 minutes. The periods of HS and LS are predicted to be 10,000ms. Their deadlines are 100ms and 75ms respectively. Tasks Operator (OP) and Logging.Task (LT) do not have associated deadlines and are considered as non-critical tasks which are discussed later. After task periods and deadlines are determined, the priorities are allocated to them. In this case both rate monotonic and deadline monotonic algorithms will obtain the same priority order in Table 4.1. The table also lists all protected shared objects (PSO) in the system and their ceiling priorities. Chapter 4. Case Study 56 4.1.2 Non-Critical Tasks In hard real time systems, the consequences of missing deadlines with non-critical tasks are not serious. Task OP is an aperiodic task with no specified period and provides the service to display system status and to control the pump manually by an operator. This task does not have timing requirement and willnot cause a catastrophe if its deadline is missed. This task can be designed as a background job that activates when the C P U is in the idle state. In this case, the utilization bound can not be up to 1. Since the operation in task OP is simple, a 5 percent utilization margin will satisfy its usage. Therefore when we calculate utilization bound, we do not include task OP. However, the utilization bound for the remaining tasks is limited to 95%. Task LT is different from task OP in that task LT must record the data before the buffer storing the sampling data is overfilled, that is, there exists a hard deadline. This task can be deferred if sufficient buffer space is provided. Thus, task LT is designed as a periodic task with two alternately used blocks of data buffers. The size of each buffer is determined by the data structure of sampling data. The priority of task LT is lower than any other critical tasks so that the execution of task LT does effect the schedulability of other critical tasks. In this system, both the period and deadline of task LT are assigned to be 600ms. Another reason to give task LT a low priority is the concern of system overload. The periods of tasks HS and LS result from heuristics. It is possible .that the per-colating rate is higher than anticipated. Under this special circumstance, there are two requests of task HS and LS during the minimum inter-arrival interval and the execution of tasks HS and LS may exceed the predicted time. To keep the safety of the mine, we ensure that these two tasks can take some time from task LT. After the critical instant, new periods of task HS and LS are'created and the system's Chapter 4. Case, Study 57 Task Name Members Period Deadline Priority T (ms) D (ms) P M M 20 10 1 T2 A M , C M 30 20 2 r3 SC 35 30 3 HS,LS 10000 75 4 T5 LT 600 600 5 Table 4.2: The task set of the mine control system, performance should be re-checked. 4.1.3 Schedulability Analysis Before the schedulability is analyzed, all tasks are re-organized by merging two tasks with the same periods in to one to simplify the analysis. As tasks A M and C M have the same periods and deadlines, they are combined into one. Tasks HS and LS emerge with the period of 10000ms and deadline of 75ms for simplicity. The new task set is listed in Table 4.2. Applying our exact utilization bound approach to this task set, we obtain an in-teresting result with the following subsystem utilization bounds: £ i = 0.5000 B2 = 0.6667 B3 = 0.7857 B4 = 0.0075 B5 = 0.8753 Chapter 4. Case Study 58 The utilization bound of the priority 4 subsystem B4 shows that more than 99% C P U resource can not be used for the execution of the first four tasks. That is not practical. An alternative approach is required to circumvent the problem. The reason for the low utilization bound B4 is that the maximum task utilization of task r 4 , equal to D4/T4, is much less than 1. That causes the B4 to be equal to or less than the maximum utilization of task r 4 . To explain this observation, in the linear programming to calculate utilization bound, the objective function of the minimization is subject to and u = 9i + 9i + 9i + 9i T i Ta r 3 r 4 &]C1 + & C 2 + & C 3 + C4 = D4 ±1 ^2 J-3 Tr4 T4 Consequently, we can conclude that the utilization bound approach is suitable for a system in which the maximum utilization of each task is close to 1. As a solution to this problem, we assume that the period of task r 4 is 75 in order to estimate the system utilization bound. As we shorten the period, the system load Chapter-4. Case Study 59 increases because the utilization of task r 4 changes from C4/T4 to C4/D4. In this case, the utilization bounds of all subsystems are /J, = 0.5000 B2 = 0.6667 B3 = 0.7857 B4 = 0.8762 B5 = 0.9929 Let us discuss the effects of the assumption that T 4 ' S period can be decreased from 10,000 to 75. We distinguish the two task sets as S\ and S2. Suppose the system is schedulable when T4 = 75 with any computation set { C n , C 2 i , C31, C41, C51} and Ux < 0.5, U2 < 0.6667, U3 < 0.7857, U4 < 0.8762, U5 < 0.9929. Since tasks n , r 2 , and T3 have higher priorities than task T4 ' s , their schedule can not be affected by the request of task r 4 , regarless of r 4 's period. Task r 4 is guaranteed to be schedulable when the period is 75 and it is still schedulable when its period is increased to 10,000. So far, the scheduler can ensure that the first four tasks meet their deadlines. The only difference is that the two task sets have different utilization when C41 is not zero because Us^ — Us2 = C41 (1/10, 000 — 1/75). As a result, the impact on task r 5 is not favorable because the utilization of task T4 increases dramatically as its period is decreased. When C n = 10, C21 = C31 = 0, C41 = 75, and C51 = 240, the utilization of the system is 0.9075 which is less than bound B5. Unfortunately, the response time of task T 5 is 615 which is greater than its deadline. The schedulability of task T 5 is no longer guaranteed. That means that T4 — 75 can not be used to calculate the subsystem utilization bound when the subsystem includes task r 4 . Therefore, to calculate the B5, we add in one more constraint for task T4, UTi < D4/T4. Chapter 4. Case Study 60 Motion simulator Figure 4.3: The system diagram of the hydraulic motion platform simulator system We summarize our procedure to calculate the utilization bound of a system in which a task's deadline is much less than its period: 1. Calculate the utilization bound of S i , B2, and B3. 2. Calculate the utilization bound of B4 with T4 = D4 = 75. 3. Calculate the utilization bound of B5 with C 4 / T 4 < 0.0075 and U4 < B4 where r 4 = 10,000. Finally, each task can be assigned an execution time budget based on the utiliza-tion bounds:^! < 0.5; U2 < BX = 06667; U3 < B2 = 0.7857; U4 < B3 = 0.8753 and UTI < 0.0075; and T75 < B5 = 0.8753. 4.2 Hydraulic Motion Platform Simulator System Figure 4.3 shows a hydraulic motion platform simulator system implemented with VxWorks real time operating system on a SPARC target board. This system has been developed by the Robotics Laboratory in the Department of Electrical and Computer Engineering at U B C . The system controls the hydraulic platform through console and/or joysticks with the following functional requirements. Console Joysticks Hydraulic Motion Platform Simulator System Chapter 4. Case Study 61 Figure 4.4: Design for the hydraulic motion platform simulator system 1. The system controls the hydraulic valves on the motion simulator via D / A converters and detects the position of the platform through the digitized signals of the magnetic sensors. 2. An operator controls the hydraulic motion platform by joystick. 3. An operator can send commands to the system through console keyboard. The timing requirements are 1. The A / D converter rate is up to 400Hz. 2. The human commands must be responded to within 50ms. The system consists of four periodic tasks: interrupt service request handler, motion controller, trajectory planner, and user controller. 1. Interrupt handler (IH) is triggered by a hardware timer to invoke periodic tasks according their time periods. The execution time of IH is regarded as system overhead. Chapter 4. Case Study 62 2. Motion controller (MC) samples the current platform position, compares the data to the required one, and updates hydraulic valve parameters. 3. Trajectory planner (TP) samples joysticks and generates the parameters of the hydraulic valves from the sampling data. It also converts commands from the console keyboard to the specific parameters. 4. User (UC) validates commands. 4.2.1 System Model The period of task M C depends on the A / D convert rate. If the task period is less than that of A / D convert, task M C overwrites the previous data. The period of task M C is assigned as 2.5ms. The response time of a signal from the joystick must be less than 50ms. We set the period of task T P to a multiple of the period of task M C . Task UC is a non-critical task which does not have an associated period. As the keyboard is polled by task UC, we assign the period to be 20ms by using short command length with one or two letters. The priority of each task is assigned using the rate monotonic scheduling algo-rithm. The periods of task T P and UC are the same. Task T P is assigned a higher priority because task UC is a non-critical task. To communicate among the tasks, protected shared data controLparameter (CP) and controLcommand (CC) are used. A l l task parameters are listed in Table 4.3. 4.2.2 Real Time Systems with Harmonic Periods In the hydraulic motion platform simulator system, there is no constant periodic requirement for task TP. We choose its period as the multiple of task M C because Chapter 4. Case Study 63 Name of Task Class Symbol Period Deadline Period T (ms) D (ms) P Interrupt .Handler Periodic IH 2.5 ms 0 Motion_Controller Periodic M C 2.5 ms < 2.50ms 1 Trajectory .Planner Periodic TP 20ms < 20ms 2 User-Controller Periodic UC 20ms < 20ms 3 Control-Parameter PSO CP 1 Control-Command PSO CC 1 Table 4.3: Hydraulic motion system tasks and protected objects. 1. the utilization can be up to 1 when all task periods are harmonically related. 2. the computation times of the tasks can be budgeted linearly. The first property has been noticed by Liu and Layland [Liu 73]. As an example of the two properties, consider that for linear programming to calculate utilization bound, the objective function of the minimization is , subject to and \^-}C1 + C2 = D2 Ti < T2. When T2 is the multiple of T i , the ceiling of T 2 / T i is equal to T2/Ti. Then, we have . 7i r 2 _ | C i . c2 T2 + T2 Chapter 4. Case Study 64 = D2 The utilization reaches 1 when deadline D2 is equal to its corresponding period T2. So it is possible to design a real time system with harmonic periods to use all C P U resources and still guarantee feasibility. When the total executable interval is D2 for task M C and TP, the computation time distribution between tasks M C and TP is a linear equation - i d + C2 = D2. JL 1 The system time relationship for all tasks is p d + C 2 + d = D3. J-1 In this case, it is convenient for developers to budget task computation times and this system is schedulable when '^Cl + C2 + C3 0. For the interval [A,B], value A can be set to 0"at the critical instant, but B is in-determinable without the knowledge of computation times. The task schedulability constraints must be revisited to ensure that those constraints are still valid. 5.2.3 Soft Real Time Systems Unlike in hard real time systems, the value of a task result decreases gradually after the deadline expires in soft real time systems. Therefore, software design of soft real time systems place more emphasis on system average performance. Validity of the utilization test is yet determined and extended. Bibliography A. Burns and A. Wellings, "Scheduling Hard Real-Time Systems: A Review ", Software Engineering Journal, vol. 6, no.3, pp. 116-128, 1991. ' A. Burns and A. Wellings, "Real-Time Systems and Programming Languages second edition11, Addison Wesley, 1996. S. Cheng, J .A. Stankovic, and K . Ramamritham, "Scheduling A l -gorithm for Hard Real-Time Systems: A Brief Survey", Hard Real-Time Systems: Tutorial, ed. J.A. Stankovic and K. Ramamritham, IEEE pp. 150-173, 1988. H . Gomaa, "Software Design Methods for Concurrent and Real-time Systems''', Addison-Wesley, 1993. M . Joseph and P. Pandya, "Finding Response Times in a Real-Time Systems", Computer Journal, vol. 29, no.5, pp. 390-395, 1986. M . Joseph, "Real-time Systems: Specification, Verification and Analysis", Prentice Hall, 1996. D.I. Katcher and H. Arakawa, "Engineering and Analysis of Fixed Priority Scedulers", IEEE Transactions on Software Engineering, vol. 19, no. 9, pp. 920-480, 1993. [Laplante 97] P.A. Laplante, 11 Real-Time Systems Design and Analysis: An Engi-neer's Handbook",, IEEE Press, 1997. [Leung 82] J .Y .T . Leung and J. Whitehead, "On the Complexity of Fixed-Priority Scheduling of Periodic, Real-Time Tasks", IEEE Transac-tions on Software Engineering, vol. 19, no. 9, pp. 920-480, 1993. [Liu 73] C. L. Liu and J.W. Layland, "Scheduling Algorithms for Multipro-gramming in a Hard Real-Time Environment", JACM, vol. 20, no. I, pp. 46-61, 1973. [Lehoczky 86] J . Lehoczky and L. Sha, "Performance of Real-Time Bus Scheduling Algorithm", ACM Performance Evaluation Review, vol.14, 1986. 69 ' [Burns 91] [Burns 96] [Cheng 88] [Gomaa 93] [Joseph 86] [Joseph 96] [Katcher 93] Bibliography 70 [Lehoczky 89] J . Lehoczky, L. Sha and Y . Ding, "The Rate Monotonic Schedul-ing Algorithm:Exact Characterization And Average Case Behavior", Real-Time Systems Symposium, pp. 166-171, 1989. [Lehoczky 90] J.P. Lehoczky, "Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadlines", Real-Time Systems Symposium, pp. 201-209, 1990. [MajumdarEtA 92] S. Majumdar, C M . Woodside, J .E. Neilson and D.C. Petriu, "Robust box bounds: throughput guarantees for closed multiclass queuing networks with minimal stochastic assumptions", Proceed-ings of IEEE Infocom, pp. 2006-2015, 1992. [Majumdar 92] S. Majumdar and R. Ramadoss, "Interval-based performance analy-sis of computing systems", Proceedings of MASCOTS, pp. 345-351, 1995. [Park 93] D.W. Park, "A Generalized Utilization Bound Test for Fixed-Priority Real-Time Scheduling", Ph.D. Thesis, Department of Com-puter Science, Texas A&M University, College Station, Texas, Au-gust 1993. [Park 95] D.W. Park, S. Natarajan, A. Kanevsky, and M . J . K i m , "A General-ized Utilization Bound Test for Fixed-Priority Real-Time Schedul-ing", IEEE Computer Society Press, pp 73-77, 1995. / • . ' [Park 96] D.W. Park, S. Natarajan, and A. Kanevsky, "Fixed-Priority Scheduling of Real-Time Systems Using Utilization bound", The Journal of System and Software, vol. 33, no. 1, pp.57-63, 1996. [Peng 89] D.T. Peng and L. Sha, "A New Performance Measure for Scheduling Independent Real-Time Tasks", Technical Report,'Real-Time Com-puting Laboratory, University oj* Michigan,1989. [Rajkumar 91] R. Rajkumar "Synchronization in real-time systems : a priority in-heritance approach", Kluwer Academic Publishers, 1991. [Sha 90] L. Sha and J. B . Goodenough, "Real-Time Scheduling Theory and Ada", Computer, no. 4, pp. 53-62, 1990. [Shih 93] W.J . Shih, J.W. Liu, and C L . Liu, "Modified Rate-Monotonic Algo-rithm for Scheduling Periodic Jobs with Deferred Deadline", IEEE Transactions on Software Engineering, vol. 19, no. 12, pp. 1171-1179, December 1993. Bibliography 71 [Smith 93] C.'U. Smith and L .G . Williams, "Software performance engineering: A case study including performance comparison with design alter-natives", IEEE Transactions on Software Engineering, vol. 19, no. 7, pp.720-741, 1993. [Spmmerville 92] I. Sommerville, "Software Engineering", Addison-Wesley,1992. [Tilborg 90] edited by A. Tilborg and G. Koob, "Foundations of Real-Time Com-puting: Scheduling and Resource Management", Kluwer Academic Publishers, 1990. [Vestal 94] S. Vestal, "Fixed-Priority Sensitivity Analysis for Linear Compute Time Models", IEEE Transactions on Software Engineering, vol. 20, no. 4, pp. 53-62, 1994. [Woodside 95] C M . Woodside "A three-view model for performance engineering of concurrent software", IEEE Transactions on Software Engineering, vol. 21, no. 9, pp.754-767, 1995. [VxWorks 93] "Vxworks Programmer's Guide", 1993.