E X A C T UTILIZATION BOUNDS FOR R E A L - T I M E SYSTEMS DESIGN By Ying Fang B. Sc. (Electrical Engineering) Fudan University, 1989. A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T OF THE REQUIREMENTS FOR T H EDEGREE OF M A S T E R OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL AND COMPUTER ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH August 1998 © Ying Fang, 1998 COLUMBIA 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 ' V 6 T 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 stringent 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.2 Software Life Cycle for Real Time Systems 2 1.3 Real Time Scheduling 3 1.4 Motivation 1.5 Related Results 7 1.6 Contributions 9 1.7 Outline of the Thesis 9 ' 2 Background 1 5 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 in 2.6 2.7 3 4 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 Schedulability Analysis Tool 28 E x a c t Feasible Utilization B o u n d 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 3.7.4 The Effect on Subsystem Utilization Bound . . 46 48 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 W o r k .65 5.1 Summary of Results 65 5.2 Future Work 67 5.2.1 Utilization Bound of a Real Time System with Shorter Deadlines 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 vi 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 vii 61 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 R e a l 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 requirement: whereas soft real time environments are characterized by rising costs with increasing lateness of results, no lateness can be tolerated in hard real time environments. 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 task is activated, it should be possible to determine its completion time with 1 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 i m e 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 features that can be directly tested by executing the program. The latter includes specification of time constraints, programming language and the type of machine. 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 requirements. Chapter 1. Introduction 3 5. Maintenance phase: maintenance involves correcting errors which were not discovered in earlier stages of the life cycle, improving the implementation of system tasks and enhancing the system's services as new requirements are discovered. 1.3 Real Time Scheduling In hard real time systems, failure to meet deadlines is equivalent to producing incorrect 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 complexity 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 timing problems can be identified only in the test phase. 4 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 schedules for tasks off-line and it requires the complete prior knowledge of tasks' characteristics. 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 t c 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 identifying potential performance problems,in the design phase before they become implementation errors because fixing errors early is less expensive than fixing them later on. This thesis focuses on studying timing requirements involved in real time systems design during the "system model and analysis"phase. Currently, a simulationbased 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 computation time characteristics. The computed response times can then be compared Chapter 1. Introduction Figure 1.1: The life cycle of real time software development 6 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 corresponding 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. 1.6 Introduction 9 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 limitation 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 utilization 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. 12 Background execution 0 1 time • C •* R —D -* • T 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 r -. 4 • 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 utilization bound techniques are further defined in the following. Chapter 2. 13 Background When we discuss, a task set, the following corresponding parameter sets are assumed 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 containing the first i elements where i is less than n. Therefore the priority 1 subset of {TI, r , r } is {TI}, the priority 2 n 2 {TI,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 U = T T + T> e t where T is the execution time, and Ti is the idle time.- and the task utilization is e referred to the fraction of computation time during the period as U U task-name rri ' Chapter 2. 14 Background So, the processor utilization U , processing n tasks, is: n n /~i From another point of view, U is also the system utilization for a task set with n 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, computation times Ci and priority assignments P - is said to be just feasible if it t 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 T h e Rate M o n o t o n i c T h e o r y 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 according 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 characterizations 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 Theorem 2.1 16 (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 r - for the first request of of r- occurs when 4 t all tasks arrive at a critical instant which means h = I = = I 2 n = 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 TI,T , 2 ...,r n with Di — Ti, 1< i < n, is schedulable by the rate monotonic scheduling algorithm if n s~f U = J2^-<B(Liu) n = n(2 ? -l). 1 n (2.1) The three theorems provide a theoretical basis to study and test system schedulability. However, the threshold utilization is pessimistic. In the uniprocessor case, the bound is log 2 = 0.693, meaning that if periodic utilization is kept below this level, e the optimal fixed priority algorithm will meet all deadlines. But many task sets are schedulable with much higher utilization bounds. In fact, Liu and Layland provided an exact utilization bound formula. If a task set whose ratios between any two task periods are less than 2, the exact upper utilization bound is B ( H = l+fli[^] + E ^ ^ T r ] where g = (T - TAjT, t n i = 1,2, ...,n. (2-2) Chapter 2. Background 17 Then if a task set with one or more ratios between the period and the longest period are greater than 2, a corresponding task set with maximum period ratios less than 2 can be created where the new utilization bound is less than the previous one. Suppose for task r,-, \T /Ti] n > 2. Let T n = qT{ + r, q > 1 and r > 0. The corresponding task r- replaces the task T j , such that T- = qT{ and c = C{. In order i 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 Since q - 1 > 0 and [1/qTi + r - 1/qTi] < 0, then U' < U . n n - 3 ) Therefore the sys- tem utilization of U is equal to or greater than that in its corresponding task set n 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(2 ' -l) is the lowest value among all exact utilization bounds for 1/ ri 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 Monotonic 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 18 Chapter 2. Background 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] T h e o r e m 2.4 (Leung and Whitehead)For 1 < i < n,.the optimal fixed priority scheduling algorithm. a periodic task set r i , . . . , r scheduling algorithm with Di < Ti, is the deadline A task set is schedulable by this algorithm each task after a critical instant meets its n monotonic if the first task of 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 implementation to determine the schedulability of a task set. On the other hand, the modified rate monotonic algorithm is a semi-fixed prioritydriven algorithm i n 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 performance 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 C o n d i t i o n A n 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. 19 Background [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 A. m 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 Ti...r - up to T J . If r,- completes by any of these scheduling points, then t 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 1. Task Ti can be scheduled for all task phases ri,...,r n ; using the rate monotonic algorithm if and only if L= % min {0«<TJ ^2<l' t 2. The entire task set can be scheduled for all task phases using the rate algorithm (2.5) ~ monotonic if and only if ' max Li < 1 (2.6) {0<t'<n} The characterization of schedulability given in Theorem 2.4 requires a minimization over the continuous variables t G [0, Tj]. In fact, only a finite number of times t 20 Chapter 2. Background need to be checked. The function Wi(t)/t is strictly decreasing except at a finite set of values called the rate monotonic scheduling points where the function has a local minimum. The condition can be rewritten as: Li = mm t tes, where s £ Si = {kT \u — l..i,k 2.7) ' v = 1.. [T;/T J}, u 2.5 < 1 ~ U Response T i m e Analysis Another sufficient and necessary condition of schedulability test is the worst-case response time. The worst-case response time analysis can be applied to verify the schedulability thoroughly. The response time is the duration between a task's arrival time and its completion. When all response times of tasks in a real-time system are less than or equal to their deadlines, the system is feasible. The model of the worst-case response time analysis is more general than the rate monotonic model by relaxing the restriction that the deadline is equal to the period. Moreover, the priority assignment can be any static one. Assume a real time system with a'set of tasks {r!,T2,..,T }. N The fact that a task with higher priority preempts the execution of those with lower priority leads to the conclusion that for all priorities i > 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]: . RT = E \ ^ ] xCj + Ci t . . (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. 21 Background 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)xC j " (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. 22 Background 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 Park's Algorithm 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 Period-Specific Utilization Bound 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. 23 Background The objective of this technique is to determine the exact utilization bound without 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 , T; is less than U*. When the task deadlines 2 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 Ti, 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 = £ fc=l 7^ (2-13) ± k subject to L v m=i? v 1m J ;=i E r ^ C1 * + k=l k rmn(j, \^)C ]l t i > lT m (2.14) and i\^C -\>D k k=i l3 (2.15) k 1 and Cj > 0 . l<j<i. (2.16) Then the individual utilization bound is 17 = mini (-) (2.17) Chapter 2. 24 Background 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, lT ]. Minimization in this inequality ensures that for task T j , the m 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 iterative calculation U*- will terminate when j reaches [LC M(T\,T2, The T ) / T ; J , where n 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 B o u n d II Park further proposed the period specific utilization bound II (PSUB-II) procedure 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. C o n d i t i o n 2.1 (Park). There is no idle processor time prior to the first deadline of task Tj.. C o n d i t i o n 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 TJ. Chapter 2. Corollary 2.1 conditions are Theorem 2.6 achieved 25 Background (Park). Y!j Cj x \D{/Tj] =l = Di if and only if the previous true. (Park). The by the following utilization procedure: bound U* for the schedulable task can be Ti Minimize Ut = t^ (2-19) i=i subject two i to ± C 3 x \ ^ ] = D i (2.20) and Cj > 0 The condition Y])-i Cj x 1 < j < i. • • (2.21) = Di is intended to constrain the task set to be just feasible. The following theorem follows the Corollary 2.1. Theorem 2.7 system (Park). is the smallest The period U* among all tasks. PSUB 2.6.3 specific = utilization That bound (PSUB) for the entire is, min U* n mzzl m 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 ]. Otherwise, there is some idle time A before the first deadline. n Chapter 2. 26 Background 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 , r , r } 1 TI = { C l , 10,10,0}, . When C={C C , U 2 T = {C3,25,25,2} r = {C2,12,12,1}, 2 3 3 {TI, h = {CT,7,7,0}, 2 3 C7 }={2.5,5,2.5}, the utilization bound is 0.-7583. Instance 2:a task set When C={d,C , 2 T ,T } 2 3 r = {C2,12,12,l}, 2 r = {C3,47,47, 3 2} C }={5,3,0}, the utilization bound is 0.9640. 3 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 + [ T 3 / T l ] x C 2 + C 3 = 25 = D . 3 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 Proof. conditions are true. 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;). j < i released in the period of Di is \Di/Tj], Cj x \Di/Tj~\. Since the number of each task j the total execution time of task TJ is 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 Figure 2.2: Time lines for two task sets 27 Chapter 2. 28 Background all tasks with higher priority that arrive before the first deadline of task r - must be 4 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 . Moreover task r,- must finish t 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, E J - i Cj x \Di/Tj] However, if Y?j =1 Cj'x \Di/Tj] = D. { = Di, QED 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 r - in a task subset { r i , r , ...,T;} won't be 8 guaranteed. 2 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 Schedulability Analysis Tool 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 computation 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 algorithm. 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, response time etc. The control panel window provides the user .with buttons for inputting task parameters, assigning task priorities satisfying the rate monotonic algorithm, 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 reimplementing 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 Figure 2.3: The user interface of the schedulability analysis tool 31 Chapter 3 Exact Feasible Utilization B o u n d 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 Algorithm 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 corresponding 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 33 Bound 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 utilization 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 , Tfc i} + 1 is regarded as a constraint for its superset { r i , T k } , k > in order to calculate the bound Bk+i. Since Bi,...,Bk .the feasibilities of tasks the feasibilities of task T\,...,Tk Tk+i, guarantee and the full utilization constraints can guarantee 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 <C\ < Di < T i , then Bi=l. utilization constraints: C + C >D 1 \^]d 2 + l C >D 2 2 and task schedulability constraints: cyv, < ih and computation time constraints: 0 < C i < D i < Ti 0 < C < D <T . 2 2 2 B is processed with full 2 Chapter 3. Exact Feasible Utilization 34 Bound Then B is determined by full utilization constraints: 3 C + C + C> 1 2 \^]C J-i 3 +C + 1 + &]C i 3 + 2 ±1 l C >D 2 \%r]Ci D 2 C >D 3 2 2 and task schedulability constraints: Ti T ~ 2 and computation time constraints: 0 < Ci < Di <Ti 0<C <D <T 2 2 2 0<C <D <T . 3 3 3 Consequently, we obtain the system utilization B equal to B 3 as U\ < Bi, and U < B. 2 2 3.2 Theoretical Foundations of the Algorithm Lemma 3.1 • When the subsystem utilization bound Bi is obtained only subject to the full utilization V 771 = constraints: 1 m J=l D 3 1 the corresponding deadline Di is always met. 35 Chapter 3. Exact Feasible Utilization Bound Proof. Assume T^ j \Di/Tj~\Cj According to lemma 2.2, tasks r =1 > Di'. Ti, T 2 ,r,-_i complete their execution before Di, so task T - doesn't finish its execution until Di + 5. z 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 during 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 T - is s guaranteed. Lemma 3.2 For a task set i subset. {T\, T \n > 2}, Bi is the utilization bound of its priority n 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 t=l i < B . m 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 is also schedulable as C\jT\ + C / T < B by Lemma 3.1. 2 2 2 2 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 = B + S. Since the optimal solution of computation + C2/T2 2 time is C*, when C^/Ti + C /T 2 2 = B , the system is schedulable and any increase of 2 computation time will result i n non-feasibility. We create a computation set {C ,C }, 1 2 where C[ = C{ C 2 = ST + 2 C. 2 As 8 > 0, the fact that C is greater than C^ causes the system to be infeasible. So 2 we conclude that C\jT\ + C /T 2 Assume that tasks TI,T , 2 2 < B2. ...,Tk-i are schedulable if V/k-l v =i m m in a task set {ri, T C' 2 , • When the number of tasks is k, Bk is the utilization bound of { T I , T 2 , 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 { r i , r , T k - i , r^}. For task r^, when 2 YULiCi/Ti < B, m 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 ^ , £™ Q/Ti < B 1 m are' satisfied if tasks Chapter 3. Ti, Exact Feasible Utilization Tk-i T2,..., 37 Bound 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 C = CT x u — u 2 2 Since 5 > 0, the computation time of task its deadline in the critical instant. So Y A The condition Theorem 3.1 Xw=i Ci/Ti increases. This causes task = 1 to miss Ci/Ti < Bk must be satisfied. < Bk is called the task schedulability constraint. The subsystem utilization bound Bn for the schedulable task set {TI, T can be achieved by the following procedureMinimize ^ =E§ i=i subject to V ^ • i (3-22) j = 1 E\^Ci>D (3.23) m and \/ ~ \ n m = £ ^ < # and \C (3.24) m = 1 c- < o t Proof. From Lemma 3.2, tasks r , T 2 , . . . , r „ are feasible because of Eq. 3.20. Equa1 tion 3.19 ensures the schedule is full utilization. Consequently, B is the subsystem n utilization bound. Chapter 3. Exact Feasible Utilization Bound 38 T h e o r e m 3.2 When the individual subsystem bounds of a task set are the system utilization B -i n bound can be up to B(E) B n as U\ < B\, U < B\, B B ,..., 2 2 , B 2 U -i n n , < • The proof follows from Lemma 3.2. 3.3 P r o c e d u r e of the A l g o r i t h m We present the procedure to determine the system utilization bound. In the procedure, Bi is calculated by Equation 3.18. Assume that there are n tasks in a system. Step 1: If all Ci x, ma 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 and terminate. Step 2: If any task does not pass the test with Ci in, m C min 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, 2 i •••i C n m i n Ci < Ci m a x Chapter 3. 3.4 Exact Feasible Utilization 39 Bound Discussion and Comparison 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 _Ji__L - = 2—-1 z= l,...,n-l. A task set gains its worst case utilization bound when task's periodic times satisfy Ti = 2~^T n i = 0,1, - 1. This specific task set has the exact utilization bound equal to n(2 1/,ra — 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 Period Set {50,65,94,98} {35,63,78,79} {7,25,53,59} {5,49,107,483} 2 3 9 97 m •2 2 3 10 40 Bound 2 2 2 4 0.8385 0.9111 0.9314 0.9837 77* • 0.8100 0.8525 0.9421 0.9313 B(Park) 0.8091 0.8459 0.8772 0.9313 ui 0.8091 0.8459 0.8772 0.9447 B(Liu) 0.8091 0.8332 0.8651 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\, T , r } . The exact 2 n utilization bound can be calculated by Liu and Layland's equation: B(Liu) = 1 + (r .-r )(T -.2T ) , " n 1 n 1 lT -T )(T . ^T ) n i i 1 i Since T — 2T < 0 (because T /Ti < 2 and T;_i — Ti < 0 ), B(Liu) will decrease with n X n the increased task number, that is Bi(Liu) > B (Liu) 2 > ... > B (Liu). n algorithm, the individual task utilization bound U* is equal to Bi(Liu). In Park's 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 No Bound 41 Period Set B 2 1 {50,65,94,98} 2 2 2 2 2 2 2 3 {300,400,605, 1190} ' {19,23,39,105} 2 2 3 4 {5,9,61,68} 2 6 2 5 {14,44,50,63} 3 2 2 6 {5,28,31,74} 6 2. 3 7 {7,25,53,59} 4 3 2 8 {5,49,107,483} 10 3 4 B B us U* A 3 u; 0.8385 0.8385 0.8333 0.8333 0.8627 0.8627 0.9111 0.9111 0.9788 0.9788 0.9571 0.9571 0.9314 0.9314 0.9837 0.9837 A 0.8100 0.8091 0.8100 0.8091 0.8307 0.9860 0.8307 0.9837 0.8587 0.9097 0.8587 0.9092 0.9687 0.9089 0.9687 0.9089 0.8964 0.7932 0.8964 0.7932 0.9135 0.8717 0.9135 0.8717 0.9421 .0.8772 0.9421 0.8772 0.9313 0.9447 0.9313 0.9447 B(E) B(Park) 0.8091 0.8091 0.9860 0.8307 0.9097 0.8587 0.9089 0.9089 0.7932 0.7932 0.8717 0.8717 0.8772 0.8772 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 + C /T 2 2 + C /T 3 3 = 5/300 + 580/605 = 0.9753, which exceeds the individual utilization bound U . To calculate B4, constraint 3 Chapter 3. Exact Feasible Utilization Subset B 2 3 4 0.8333 0.8307 0.9860 42 Bound EFUB C Solution 100,200 5,200,190 0,0,502.58, 184.83 Park's C Solution 0.8333 100,200 0.8307 5,200,190 0.9837 5,0,580,10 U* 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 < B causes the feasible region (the set of all feasible points— s 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 Consideration on Some 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 lifecycle. 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 utilization bound is relatively rough. 44 Bound If some computation times are known, the system utilization bound may get larger. The procedure to estimate system utilization bound with some known computation times is different from the general one m that Cxmin — Ci x ma — 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 computation 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 realworld 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 T SS that is assigned: Chapter 3. 45 Exact Feasible Utilization Bound 1. a computation budget C , ss 2. a replenishment period T ss which is the minimum event inter-arrival time, 3. a priority P . ss When the interrupt event occurs, task T is scheduled with priority P SS until the task ss completes execution or the computation budget has been used ,up. If the request has not been serviced completely, task T SS Otherwise, task r s s will be resumed in T ss —C ss time units. is in the idle state in which the computation budget is replenished. The following request will not be scheduled during T ss —C ss 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 Task Synchronization 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 inversion, multiple blocking, and mutual deadlock because of the nature of task synchronization 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 46 Bound 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 _I, T,- I by tasks and r,-+3. TJ+I 2 time of T ; i and + + r - 3 T + and T j + 3 also access the same section, task r,- can be blocked The blocking time Cbi is the maximum worst case execution 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; = Ci+.C7 . w 3.7.3 ' (3.25) Scheduler Overhead 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 systems become more and more complex. We consider interrupt event-driven scheduling 47 Chapter 3. Exact Feasible Utilization Bound 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 triggered 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 task with lower priority, it is Cnonpreempt- C p r e e m p t and for a Besides that, each task has an exit process time. Cpreempt — Cint ~1~ C f re (3.26) ~\~ Cload s 0 (3.27) C exit — Ctrap + Cload Cnonpreempt where Ci t n — Ci t n H~ ~\~ C hed sc is the time to handle an interrupt, r e s u m (3.28) e represents the time to save Cstore the state of the active task to a task control block, active task state, and C C is the time to load the new Ci d oa i r a p equals to the time to handle the trap generated by normal completion of a task, C hed is the time to execute the scheduling code to determine the next task to run, C sc 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 C empti pre constant values'. So each task will suffer the overhead or Cnonpreempt + C uex C 0 Cnonpreempt-, up to either C and C it are p r e e m p t + Ca ex ex The effect of the overhead can be treated as C'i=Ci + C. 0 (3.29) Chapter 3.7.4 3. Exact Feasible Utilization 48 Bound 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 can be achieved by the following utilization bound B for the schedulable n task set { r i , r , procedure- Minimize n c: subject (3.30) to V:m = l '71 m 1=1 and (3.31) 1 V!'71—1 771 = 1 771 (3.32) and V:'71771 = 1 Ci < Chi, ~y C 0 Chapter 4 Case Study This chapter discusses two real time systems to demonstrate how to apply the utilization 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 subsystems 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. A n 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 M i n e P u m p and Control System The mine pump and control system is intended to monitor the levels of carbon monoxide, 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. A n 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. 51 Case Study Water-high Water-low Pump Methane sensor Mine Pump Data file and Carbon monoxide sensor Airflow sensor Control System 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. 52 Case Study 2. Recognition of monitor failure and pump shut down: the deadline is, 65 milliseconds. 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. r Case Study 53 Pump Controller Subsystem interrupt IH Environmental Monitor Subsystem s MM P AM P CM P OP s Operator Subsystem i i i i LT P Data Logging Subsystem A periodic task A sporadic task A control flow A data flow A protected shared object Figure 4.2: Design for the mine pump and control system Chapter 4. 4.1.1 Case Study 54 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 communicate 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 ( M M ) , Air_Monitor ( A M ) , 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. A n extra task Interrupt .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. 55 Case Study Name of Task Class Symbol MethaneJVfonitor AirJVIonitor COJVlonitor Safety_Checker High_Sensor Low_Sensor Interrupt JHandler Logging_Task Operator Controller Methane_Status Logging Periodic Periodic Periodic Periodic Sporadic Sporadic MM AM CM SC HS LS IH LT OP CT MS LO Periodic Sporadic PSO PSO PSO Period T (ms) 20 30 30 35 10000 10000 Deadline D (ms) 10 20 20 30 100 • 75 600 600 Priority P 1 • 2 3 4 5 6 0 7 8 1 1 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 overhead 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. 4.1.2 Case Study 56 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 percolating 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. 57 Case, Study Task Name T2 r 3 T 5 Members MM AM,CM SC HS,LS LT Period T (ms) 20 30 35 10000 600 Deadline D (ms) 10 20 30 75 600 Priority P 1 2 3 4 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 interesting result with the following subsystem utilization bounds: £ i = 0.5000 B = 0.6667 2 B = 0.7857 3 B = 0.0075 4 B = 0.8753 5 Chapter 4. 58 Case Study The utilization bound of the priority 4 subsystem B shows that more than 99% C P U 4 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 , equal to D4/T4, is much less than 1. That causes the B to be equal to or 4 4 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 u 9i = 9i + Ti + 9i r Ta 9i + r 3 4 subject to &]C 1 + & C ±1 2 + & C + C4 = D4 3 J-3 ^2 and Tr<T <T < 2 T . 3 4 Then, we have T Ti r • 4 r 2 r r 4 r 3 4 4 rjtici 1 r f t m 1 rfti^s = r 4 c 4 L>4 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 is 75 in order 4 to estimate the system utilization bound. As we shorten the period, the system load Chapter-4. 59 Case Study increases because the utilization of task r changes from C /T 4 4 to C /D . 4 4 4 In this case, the utilization bounds of all subsystems are /J, = 0.5000 B 2 = 0.6667 B = 0.7857 3 B 4 = 0.8762 B = 0.9929 5 Let us discuss the effects of the assumption that T ' S period can be decreased from 4 10,000 to 75. We distinguish the two task sets as S\ and S . Suppose the system 2 is schedulable when T = 75 with any computation set { C n , C i , C31, C41, C51} and 4 2 Ux < 0.5, U < 0.6667, U < 0.7857, U < 0.8762, U < 0.9929. Since tasks n , r , 2 3 4 5 2 and T have higher priorities than task T4's, their schedule can not be affected by the 3 request of task r , regarless of r 's period. Task r is guaranteed to be schedulable 4 4 4 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^ — Us = C41 (1/10, 000 — 1/75). As a result, the impact on task r is 2 5 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 B . Unfortunately, the response 5 time of task T is 615 which is greater than its deadline. The schedulability of task 5 T is no longer guaranteed. That means that T — 75 can not be used to calculate 5 4 the subsystem utilization bound when the subsystem includes task r . Therefore, to 4 calculate the B , we add in one more constraint for task T , U < 5 4 Ti D /T . 4 4 Chapter 4. 60 Case Study Hydraulic Motion Platform Simulator System Console Joysticks 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 , B , and B . 2 3 2. Calculate the utilization bound of B4 with T4 = D = 75. 4 3. Calculate the utilization bound of B with 5 C4/T4 < 0.0075 and U4 < B where 4 r = 10,000. 4 Finally, each task can be assigned an execution time budget based on the utilization bounds:^! < 0.5; U < B = 06667; U < B = 0.7857; U < B = 0.8753 and 2 U TI 4.2 X 3 2 4 3 < 0.0075; and T7 < B = 0.8753. 5 5 Hydraulic Motion Platform Simulator System Figure 4.3 shows a hydraulic motion platform simulator system implemented with VxWorks real time operating system on a S P A R C 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. 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. A n operator controls the hydraulic motion platform by joystick. 3. A n 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 U C is a non-critical task which does not have an associated period. As the keyboard is polled by task U C , 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 algorithm. The periods of task T P and U C are the same. Task T P is assigned a higher priority because task U C 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 T P . We choose its period as the multiple of task M C because 63 Chapter 4. Case Study Symbol Name of Task Class Interrupt .Handler Motion_Controller Trajectory .Planner User-Controller Control-Parameter Control-Command Periodic Periodic Periodic Periodic PSO PSO Period T (ms) 2.5 ms 2.5 ms IH MC TP UC CP CC 20ms 20ms Deadline D (ms) < 2.50ms < 20ms < 20ms Period P 0 1 2 3 1 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 \^-}C 1 C = D + 2 2 and Ti < T . 2 When T is the multiple of T i , the ceiling of T / T i is equal to T /Ti. 2 2 . 7i 2 r 2 _ | C i . c 2 T + 2 T 2 Then, we have Chapter 4. 64 Case Study D2 = The utilization reaches 1 when deadline D is equal to its corresponding period T . 2 2 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 D for task M C and T P , the computation 2 time distribution between tasks M C and T P is a linear equation - i d + C = D. 2 2 JL 1 The system time relationship for all tasks is p d J-1 + C + d = D. 2 3 In this case, it is convenient for developers to budget task computation times and this system is schedulable when '^C l + C + 2 C <D . 3 3 Chapter 5 Conclusions and Future Work 5.1 Summary of Results In this thesis, we have proposed a technique to calculate the exact feasible utilization bound of a task set in a real-time system. Liu and Layland's approach obtains the worst case utilization bound without considering any task information, while Park's algorithm accomplished the relatively accurate schedulability test by taking into account task information. Our approach enhances Park's algorithm by obtaining the exact utilization bound for a task set. While algorithmic-based scheduling schemes are developed to order the use of system resources, they also provide a means to predict the worst-case behavior of a system. The pioneering work of Liu and Layland offers the framework for scheduling periodic tasks and computing the worst case utilization bound for a real time system. However, the utilization bound provided by the approach is substantially less than the average case behavior in practice. Moreover, this technique is only applicable to the system that assigns task priorities by the rate monotonic scheduling algorithm which is optimal only when the task deadlines are equal to their corresponding periods. Instead, the deadline monotonic scheduling algorithm is proved to be the optimal algorithm for scheduling a real time system with shorter task deadlines than their periods. Therefore a schedulability testing method is desired for the deadline monotonic scheduling algorithm. 65 Chapter 5. Conclusions and Future Work. 66 The goal of our technique is to determine the exact utilization bound before detailed information of task computation times in a task set is known. While linear programming is used in our algorithm, the constraints are classified into three groups: 1. Full utilization constraints: guarantee that there is no idle time in the processor within the first task deadlines. 2. Task schedulability constraints: guarantee that tasks in a subsystem are schedulable. 3. Computation time constraints. Therefore, the approach can obtain the exact utilization bound by accommodating both full utilization and task schedulability.conditions. In addition, the approach has the following features: 1. Task deadlines can be arbitrary values. 2. Task priorities can be assigned by rate monotonic algorithm, deadline monotonic algorithm, or any other algorithms. This algorithm can obtain better results of utilization bound than either Liu's or Park's algorithms do. If the utilization bounds decrease as the number of tasks increase, the utilization bounds estimated by the three methods are identical. In other cases, Liu's utilization bounds are much less than those calculated using our method. Compared to Park's algorithm, our approach finds utilization bounds in a feasible region satisfying full utilization and task schedulability by applying linear programming. Because this region in evaluating the optimum does not exceed the region in Park's algorithm, the minimum value in our region is equal to or greater Chapter 5: Conclusions and Future Work 67 than that in Park's region. Therefore our approach gains a more accurate utilization bound than Park's. In addition, this thesis investigates the application of utilization bound analysis to the software design phase. Our findings indicate that utilization bound analysis provides new and useful information for the design. It is also complementary to simulation-based analysis.' In the course of applying our technique to two sample systems, we show how the approach can be adapted to handle the following situations: 1. Hard real time tasks have higher priorities than non-critical tasks do. Some non-critical tasks are designed as background jobs with a certain processor, utilization. 2. Sporadic tasks are designed as periodic tasks with the periods evaluated as the minimum arrive rates of sporadic external events. 3. When a task period is not strict, its period can be made to be a multiple of another task's period, which can increase the overall system utilization bound. 5.2 Future Work Although our algorithm can achieve the exact utilization bound for fixed-priority scheduling algorithms, there are still improvements'left to be made. 5.2.1 Utilization Bound of a Real Time System with Shorter Deadlines than Periods As task deadlines are shorter than the periods, our approach is still applicable because a task is schedulable when its first deadline is met after a critical instant. But a utilization bound deteriorates when the factor between the deadline and the period Chapter 5. Conclusions and Future Work 68 is extremely small. The utilization bound test is not applicable to these systems. Although an alternative approach has been provided in the aforementioned case study, further analysis of performance is required. 5.2.2 Utilization Bound of Deferred Real Time Systems When task deadlines are greater than their periods, a task may meet its first deadline after a critical instant but this does not ensure the task is still schedulable, A level-i busy period has been proposed by Lehoczky [Lehoczky 90] for schedulability test: A level-i busy period is a time interval [A,B] within which jobs of priority i or higher are processed throughout [A,B] but no jobs of level i or higher are processed in (c-e,a) or (b,b+e)for sufficiently small e > 0. For the interval [A,B], value A can be set to 0"at the critical instant, but B is indeterminable 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 [Burns 91] A. Burns and A . Wellings, "Scheduling Hard Real-Time Systems: A Review ", Software Engineering Journal, vol. 6, no.3, pp. 116-128, 1991. ' [Burns 96] A. Burns and A . Wellings, "Real-Time Systems and Languages second edition , Addison Wesley, 1996. Programming 11 [Cheng 88] S. Cheng, J . A . Stankovic, and K . Ramamritham, "Scheduling A l gorithm for Hard Real-Time Systems: A Brief Survey", Hard RealTime Systems: Tutorial, ed. J.A. Stankovic and K. Ramamritham, IEEE pp. 150-173, 1988. [Gomaa 93] H . Gomaa, "Software Design Methods for Concurrent and Real-time Systems''', Addison-Wesley, 1993. [Joseph 86] M . Joseph and P. Pandya, "Finding Response Times in a Real-Time Systems", Computer Journal, vol. 29, no.5, pp. 390-395, 1986. [Joseph 96] M. Joseph, Analysis", "Real-time Systems: Specification, Verification and Prentice Hall, 1996. [Katcher 93] 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, Real-Time Systems Design and Analysis: An Engineer's Handbook",, I E E E Press, 1997. [Leung 82] J . Y . T . Leung and J . Whitehead, "On the Complexity of FixedPriority Scheduling of Periodic, Real-Time Tasks", IEEE Transactions on Software Engineering, vol. 19, no. 9, pp. 920-480, 1993. [Liu 73] C. L. Liu and J.W. Layland, "Scheduling Algorithms for Multiprogramming 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. 11 69 ' 70 Bibliography [Lehoczky 89] J . Lehoczky, L. Sha and Y . Ding, "The Rate Monotonic Scheduling 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", Proceedings of IEEE Infocom, pp. 2006-2015, 1992. [Majumdar 92] S. Majumdar and R. Ramadoss, "Interval-based performance analysis of computing systems", Proceedings of MASCOTS, pp. 345-351, 1995. [Park 93] D . W . Park, " A Generalized Utilization Bound Test for FixedPriority Real-Time Scheduling", Ph.D. Thesis, Department of Computer Science, Texas A&M University, College Station, Texas, A u - gust 1993. [Park 95] D . W . Park, S. Natarajan, A . Kanevsky, and M . J . K i m , " A Generalized Utilization Bound Test for Fixed-Priority Real-Time Scheduling", 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 Computing Laboratory, University oj* Michigan,1989. [Rajkumar 91] R. Rajkumar "Synchronization in real-time systems : a priority inheritance 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 Algorithm for Scheduling Periodic Jobs with Deferred Deadline", IEEE Transactions on Software Engineering, 1179, December 1993. vol. 19, no. 12, pp. 1171- Bibliography 71 [Smith 93] C.'U. Smith and L . G . Williams, "Software performance engineering: A case study including performance comparison with design alternatives", 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 Computing: 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.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Exact utilization bounds for real-time systems design
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Exact utilization bounds for real-time systems design Fang, Ying 1998
pdf
Page Metadata
Item Metadata
Title | Exact utilization bounds for real-time systems design |
Creator |
Fang, Ying |
Date Issued | 1998 |
Description | 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 stringent periods. |
Extent | 3815487 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-06-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.0064807 |
URI | http://hdl.handle.net/2429/8922 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1999-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1999-0034.pdf [ 3.64MB ]
- Metadata
- JSON: 831-1.0064807.json
- JSON-LD: 831-1.0064807-ld.json
- RDF/XML (Pretty): 831-1.0064807-rdf.xml
- RDF/JSON: 831-1.0064807-rdf.json
- Turtle: 831-1.0064807-turtle.txt
- N-Triples: 831-1.0064807-rdf-ntriples.txt
- Original Record: 831-1.0064807-source.json
- Full Text
- 831-1.0064807-fulltext.txt
- Citation
- 831-1.0064807.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-0064807/manifest