cflCopyright by Hidenori Nakazato 1993 ISSUES ON SYNCHRONIZING AND SCHEDULING TASKS IN REAL-TIME DATABASE SYSTEMS BY HIDENORI NAKAZATO B.Engr., Waseda University, 1982 M.S., University of Illinois, 1989 THESIS Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science in the Graduate College of the University of Illinois at Urbana-Champaign, 1993 Urbana, Illinois ISSUES ON SYNCHRONIZING AND SCHEDULING TASKS IN REAL-TIME DATABASE SYSTEMS Hidenori Nakazato, Ph.D. Department of Computer Science University of Illinois at Urbana-Champaign, 1993 Kwei-Jay Lin, Advisor Real-time systems have timing requirements. In database systems, database operations are performed in a sequence so as to maintain database consistency. By combining the features of a real-time system and a database system, a real-time database system must satisfy requirements from both models. Unfortunately, the requirements from the two models are not always compatible. In order to satisfy the timing requirements, transactions must be scheduled in a temporally predictable fashion. On the other hand, some transactions may have to be suspended in order to maintain the database consistency. The suspension causes disturbances in scheduling and may result in temporally unpredictable behavior. The priority ceiling protocol has been proposed to satisfy the timing requirements under the existence of suspension. However, the priority ceiling protocol does not maintain database consistency. We propose a set of algorithms integrating scheduling and concurrency control in order to maintain database consistency and still satisfy the timing requirements. We describe the properties of the algorithms and compare them with the priority ceiling protocol. For real-time database systems with monitoring and controlling operations, there are additional requirements for data consistency. We therefore define external consistency and temporal consistency. In order to satisfy these additional requirements, we propose design strategies for the temporal aspect of a real-time database system. Finally, we describe how to assign specific deadlines to transactions from the timing requirements while utilizing the processor effectively. iii To my parents, Hideo and Tomi, for their love and encouragement. And to my mother, Ai, peacefully sleeping in Heaven. iv Acknowledgements I would like to express my sincere gratitude to my Ph.D. thesis advisor Professor Kwei-Jay Lin for his guidance, encouragement, and patience without which this thesis would not be possible. I especially appreciate his spending much time with me discussing problems, research, and life. I appreciate the hospitality of his family. I would like to thank the other members of my thesis committee: Professors Geneva Belford, Andrew Chien, Jane Liu, and Marianne Winslett, and Doctor Tony Ng for their suggestions, time, and interest. Special thanks go to Professor Jane Liu. She took care of me while Professor Kwei-Jay Lin was absent and gave me a chance to work on interesting problems. She also gave me many opportunities to meet people in the real-time system research community. This will be a great help in my career. I am grateful to all the members of the real-time research group for their friendship. It was a pleasant experience to be surrounded by those wonderful people. Exchanging research ideas and discussing problems with them have enriched my knowledge. In particular, the discussions with Min-Ih Chen and Ching-Chih Han brought me important ideas for my research work. I highly appreciate the hospitality of Professor Saburo Muroga and his family. I thank Professor Dave Liu and other tennis friends for providing me chances to refresh myself. Also I thank Kathy Johnson for her help in much paperwork and enjoyable conversation. Without them, my stay in this non-native culture must not be this enjoyable. The love and encouragement of my family sustained me over ups and downs in the pursuit of the Ph.D. degree. My parents taught me the importance of knowledge and education. I cannot be too grateful for their unconditional love and support. I thank my brother Hiroyuki for his support of our parents and for his wonderful personality. Talking with him over international phone line made me feel like I was at home. Without the financial support of the Oki Electric Industry, it would have been impossible to complete this thesis. They gave me the opportunity to pursue the Ph.D. degree. I greatly appreciate their generosity. v Table of Contents Chapter 1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 1.1 Real-Time Systems : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 1.2 Database Systems : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 1.3 Real-Time Database Systems : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 1.4 Period Assignment : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5 1.5 Organization of the Thesis : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 2 Past Research : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 2.1 Scheduling in Real-Time Systems : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 2.2 Concurrency Control : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 2.3 Priority Ceiling Protocols : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10 2.3.1 The Original Priority Ceiling Protocol : : : : : : : : : : : : : : : : : : : : 11 2.3.2 Priority Ceiling Protocols with Dynamic Priority Assignment : : : : : : : 15 3 The Convex Ceiling Protocol : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19 3.1 Priority Ceiling Function : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19 3.2 The Convex Ceiling Protocol : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22 3.3 Properties of CCP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 3.3.1 Single-Blocking and No-Deadlock Properties : : : : : : : : : : : : : : : : : 25 3.3.2 Serializability : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30 3.4 The Schedulability Condition : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 32 3.4.1 The Schedulability Condition for the RM Priority Assignment : : : : : : 32 3.4.2 The Schedulability Condition for General Static Priority Assignment : : : 33 3.5 Comparison with PCP+2PL : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 37 4 Optimization and Extension of CCP : : : : : : : : : : : : : : : : : : : : : : : : 41 4.1 Optimality of the RM Priority Assignment : : : : : : : : : : : : : : : : : : : : : 41 4.1.1 Worst Case Blocking Lengths of CCP : : : : : : : : : : : : : : : : : : : : 43 4.1.2 Optimality of the RM Priority Assignment in CCP : : : : : : : : : : : : : 45 4.2 Type-Specific CCP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 48 4.2.1 Algorithm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 49 4.2.2 Properties of TCCP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 52 5 Dynamic Priority Convex Ceiling Protocol : : : : : : : : : : : : : : : : : : : : 55 5.1 Algorithm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 55 5.2 Properties of ECCP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 58 5.2.1 Single-Blocking and No-Deadlock Properties : : : : : : : : : : : : : : : : : 58 5.2.2 Serializability : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 64 5.3 The Schedulability Condition : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 66 vi 6 Other Consistency Requirements : : : : : : : : : : : : : : : : : : : : : : : : : : 68 6.1 External Consistency : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 70 6.1.1 System Thresholds : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 71 6.1.2 Maintaining External Consistency : : : : : : : : : : : : : : : : : : : : : : 72 6.2 Temporal Consistency : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 74 6.2.1 Using Time Stamps : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 75 6.2.2 Using Locks : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 76 6.2.3 Using Priority Ceiling Functions : : : : : : : : : : : : : : : : : : : : : : : 78 6.2.4 Example : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 79 6.3 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 79 7 The Period Assignment Problem : : : : : : : : : : : : : : : : : : : : : : : : : : 81 7.1 System Model : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 81 7.2 Period Assignment with External Tasks Only : : : : : : : : : : : : : : : : : : : : 83 7.2.1 Maximizing the Weighted Sum of External Consistencies : : : : : : : : : 84 7.2.2 Maximizing the Uniform External Consistency : : : : : : : : : : : : : : : 88 7.3 Period Assignment with Both External and Internal Tasks : : : : : : : : : : : : : 90 7.3.1 Maximizing the Weighted Sum of External Consistencies : : : : : : : : : 90 7.3.2 Maximizing the Uniform External Consistency : : : : : : : : : : : : : : : 93 7.4 Examples : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 94 8 Conclusions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 97 8.1 Summary of Results : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 98 8.2 Directions for Future Research : : : : : : : : : : : : : : : : : : : : : : : : : : : : 100 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 102 Vita : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 105 vii List of Symbols Symbol Explanation Ti A task. A task is a program segment that implements a set of functions. A task may be executed once or repeatedly. Ji A job. Job Ji is an execution of task Ti. ei The execution time of Ti. pi The period of Ti when Ti is a periodic task. U The total processor utilization of a system. aej A data object, a data item, or a resource. Li(aej) A lock operation by Ji on aej (or the time the lock operation is performed). Ui(aej) An unlock operation by Ji on aej (or the time the unlock operation is performed). Dj A demand class. It is described by a pair: (data item, access type). ssi The original priority of Ji. ss\Lambda i The augmented priority of Ji. It is the execution priority of Ji. *i The preemption level of Ti. Ti with a shorter relative deadline is assigned a higher preemption level. OEj The priority ceiling of aej in PCP, CCP and ECCP and the priority ceiling of Dj in TCCP. In PCP and CCP, it is the highest original priority of tasks that access aej. In TCCP, it is the highest original priority of tasks that access Dj. In ECCP, it is the highest preemption level of tasks that access aej. ^Ri(t) The highest priority ceiling of all data items locked by Ji at time t. \Phi i(t) The priority ceiling function of Ji (or Ti). It is a function of time. \Omega i(t) The maximum remainder priority. It is the maximum priority ceiling of data items that Ji (or Ti) uses after time t. CP CPi (t) The highest priority ceiling among resources locked by jobs other than Ji in the system at time t. CCCPi (t) The maximum \Phi j(t) of all jobs Jj 's in the system except Ji. (It is used in CCP.) CT CCPi (t) The maximum \Phi j(t) of all jobs Jj 's in the system except Ji. (It is used in TCCP.) CECCPi (t) The maximum \Phi j(t) of all jobs Jj's in the system except Ji. (It is used in ECCP.) tiniti (aej) The initial access instant of Ji on aej. It is the time Ji accesses data item aej for the first time. tfini (aej) The final access instant of Ji on aej. It is the time Ji accesses data item aej for the last time. tiniti (Dj) The initial access instant of Ji on Dj. It is the time Ji accesses a pair: (data item, access type) that belongs to Dj for the first time. viii tfini (Dj) The final access instant of Ji on Dj. It is the time Ji accesses a pair: (data item, access type) that belongs to Dj for the last time. Bi The worst case blocking length of Ti. filh The effective blocking unit of Jl against Jh. It is the maximum duration for which Jl may block Jh. ii The blocking task set of Ti. It is the set of tasks that may block jobs of Ti. RUi The upper resource set of Ti. It is the set of all data items accessed by tasks whose priorities are higher than or equal to the priority of Ti. RLi The lower resource set of Ti. It is the set of all data items accessed by tasks whose priorities are lower than the priority of Ti. RBi The blocking resource set of Ti. It is the set of all data items that may cause jobs of Ti to be blocked. Ri The set of data items accessed by Ti. T Li The set of tasks whose priorities are lower than the priority of Ti. `A The accuracy threshold. `T The tolerance threshold. `E The effect threshold. v The maximum evolution rate of an external data object. \Phi Ri (t) The read priority ceiling function of Ti. \Phi Wi (t) The write priority ceiling function of Ti. \Omega Ri (t) The read maximum remainder priority of Ti. It is the maximum priority ceiling of data items to be read by Ti after time t. \Omega Wi (t) The write maximum remainder priority of Ti. It is the maximum priority ceiling of data items to be updated by Ti after time t. O/i An external data object. It is a value about a certain aspect of an object in the physical world. oi The external period of O/i. O/i has a new value in every oi. wi The importance of i-th internal data object. ri The goodness of the external consistency of i-th internal data object. (= oi=pi) ai The maximum acceptable period to update i-th internal data object. bi The minimum degree of the external consistency of i-th internal data object. (= oi=ai) fi (= 1=bi) Xi The set of external tasks that derived data object aei depends on. ix Chapter 1 Introduction 1.1 Real-Time Systems As computer performance increases and hardware cost continues to drop, many computers are being adopted in embedded systems to monitor or to control physical instruments and devices. Since the state of the physical world is constantly evolving, embedded systems must be designed to keep up with the physical world. Keeping up with the physical world means that each piece of work to be done has a deadline. Systems that have timing requirements are called real-time systems. An example of a real-time system is an air traffic control system. In a conventional non-real-time system, we say that the system works correctly if it produces logically correct results from input data. However, the correctness of the results from a real-time system depends not only on logical correctness but also on temporal correctness. By temporal correctness, we mean that all the timing requirements specified by the application are satisfied. If a collision detection subsystem in an air traffic control system does not produce a collision alarm in time, two airplanes may collide. If a control instruction for a robot arm on an assembly line is not produced in time, the arm may destroy a product. In the conventional real-time system design process, the temporal behavior of a system needs to be extensively tested and examined after the implementation is completed [Gla80]. The test is necessary because no mechanism to guarantee the timing requirements is provided in the design. Even after extensive testing, the system may still have some probability of violating the timing requirements. In addition, a system usually evolves as time goes by. Whenever the system is modified, another round of tests is required to verify its temporal behavior. Because of the cost involved in the examination process and the possibility of timing violations even after testing, alternative approaches are being sought [Mok83, Sta88]. In these new approaches, some mechanisms to guarantee meeting the timing requirements are implanted in the system. One such mechanism is to adopt scheduling algorithms that can analytically guarantee the temporal behavior of the system. Much research has been conducted on scheduling algorithms for real1 time systems [LSS87, LL73, Mok83, MC70]. The scheduling algorithms for real-time systems usually provide closed form schedulability conditions. Such a scheduling algorithm guarantees that timing constraints are satisfied, provided that its schedulability condition is satisfied. Sha and Goodenough [SG90] show examples which apply the schedulability conditions to real-time system design in order to guarantee timing behavior of the system. 1.2 Database Systems In database systems, many concurrent executions of transactions share data objects. For example, many travel agents access the airline reservation system simultaneously. The shared data access must be controlled using concurrency control algorithms in order to avoid undesirable interference among the executions. We assume each transaction produces "correct" results if it is executed by itself. However, when there is an interference, the same transaction may produce "incorrect" results. For example, suppose two transactions update the same bank account. Transaction T1 withdraws $100 from account A and deposits it to account B. Transaction T2 deposits $50 to account A. Suppose account A's balance is $1000 and account B's balance is $500 at the beginning. If T1 is completed before T2, the final balance is $950 and $600 for accounts A and B, respectively. However, if the two transaction executions interleave as follows: T1 reads the balance ($1000) of A, T2 reads the balance ($1000) of A, T1 writes the new balance ($900) into A, T2 writes the new balance ($1050) into A, T1 reads the balance ($500) of B, T1 writes the new balance ($600) into B, the final balances are $1050 and $600 for accounts A and B, respectively. Thus, if transaction executions are interleaved and interfere with each other, the results may not be correct. It has been shown that a serializable schedule [BHG87] which has the same execution ordering of interfering operations as some serial execution will produce correct results. In the above example, account A is read by T2, written by T1, and then written by T2. From this sequence of events, we cannot decide the serial ordering of the two transactions. Therefore, the above example is not serializable. Executing transactions in a serializable schedule is considered to be 2 mandatory in most conventional database systems. We say that the database maintains logical consistency if transactions are executed in a serializable fashion. Although database systems have always been designed to provide adequate performance, the main concern in non-real-time settings has been logical consistency. To prevent the database from becoming logically inconsistent, many concurrency control and error recovery protocols have been designed [EGLT76, BHG87]. In contrast, the database performance issue is often treated as an optimization problem which is studied only after a logically consistent system has been built. 1.3 Real-Time Database Systems Many database applications have timing constraints. In an air traffic control system, a large amount of data on airplanes, airports, and weather conditions must be maintained. The system also needs to send instructions to airplanes by certain deadlines in order to maintain their safety. Computers that monitor the stock market or conduct program trading manage huge amounts of stock information and require timely executions of transactions. When a client asks for stock prices and requests a transaction, the system must respond in a timely fashion in order to have the result the client expects. A factory automation system may contain an inventory control sub-system. As requests to the inventory controller come from many assembly lines, concurrency control is necessary. In order to keep the assembly lines in uninterrupted operation, the inventory controller must respond in a timely fashion to each line's request. A real-time computation is not correct unless it can satisfy its timing requirements. A database system is not correct unless the system maintains its logical consistency. Thus, a realtime database system may not be correct unless the system can satisfy the timing requirements as well as the logical consistency. Data objects are shared among transactions in a database system. We must control access to the shared data objects to maintain the logical consistency using a concurrency control algorithm. Controlling data access means that some transaction executions may require exclusive access to the data objects, and other transaction executions may be suspended while waiting for the data objects. The suspension introduces unpredictability into the temporal behavior of the transactions. Mok [Mok83] has shown that the problem of deciding whether a set of periodically 3 executed transactions with exclusive accesses to shared data objects can be completed before their deadlines is NP-hard. In other words, we may not be able to find a schedule satisfying all deadlines of the transaction set in a reasonable amount of time even if such a schedule exists. We need a scheduling algorithm that can produce good but sub-optimal performances, and still maintain logical consistency as well as meet all timing requirements. Many researchers [AGM88, BMHD89, CJL89, HCL90, HSTR89, LS90] have taken heuristic approaches to integrating scheduling and concurrency control. However, their algorithms may not guarantee timely completions even for critical transactions. We believe that guaranteeing a predictable performance for critical transactions is one of the major design goals for realtime systems. Sha et al. [SRL90] have proposed an algorithm that can guarantee meeting all timing constraints even when there are exclusive accesses to shared data objects. However, their algorithm does not guarantee logical consistency. In this thesis, we propose scheduling algorithms that maintain logical consistency and have a predictable temporal behavior. The algorithms proposed by Sha et al. and proposed in this thesis assume that data objects accessed by transactions are known before the transactions start executions. This assumption may be too restrictive for conventional database management systems. However, it may be acceptable for real-time database systems because the designers of real-time systems must know in what environment the systems operate in order to design systems satisfying timing requirements. In addition to the timing constraints and logical consistency, there are other requirements for real-time database systems. Many embedded systems monitor the physical world and generate control instructions. To generate a control instruction, several sensor readouts are used. Since the control instructions are generated to adapt to the change in the physical world, the information used to generate the instruction must be up-to-date. Otherwise, the instruction may be obsolete. We call this requirement of up-to-dateness external consistency [Lin89]. The data values used to produce a control instruction may be read from several sensors. Ideally, the system should view a snapshot of the physical world, i.e., all data values should be read simultaneously. However, it is not always possible. Instead, we should minimize the discrepancy of update times between data values that are used by one execution of a transaction. Song and Liu [SL90, SL92] call the discrepancy dispersion. If the dispersion of the data values 4 used by a transaction is reasonably small, we say the data values are temporally consistent [LLS88]. Some real-time systems require the temporal consistency to be maintained. External consistency and temporal consistency are additional requirements for real-time database systems. We will discuss these two consistency issues from the system design perspective in this thesis. 1.4 Period Assignment A system needs to read sensor data, do computations, store data in storage devices, and generate control instructions. These activities are made up of many program segments, each of which implements a set of functions as shown in the example in Section 1.2. We call such a program segment a task. We use a task as a unit to enforce the timing requirements. As stated earlier, real-time database systems must satisfy timing requirements. These system timing requirements are usually transformed into timing constraints for each task. We need a systematic way to assign timing requirements to tasks from the timing requirements of the system. In many applications, the timing requirements are given as ranges and not as fixed values. For example, a control instruction for a robot arm may need to be generated at least every one hundred milliseconds. But a shorter interval is usually acceptable. From the range, we need to decide a specific period to each task [NL91]. When we assign periods to tasks, we want to divide system resources among tasks so that the system provides the most useful results while satisfying the timing requirements of the system. Since some data in the physical world change their values more frequently than others, the tasks recording these values should also be executed more frequently. Airplanes closer to airports need to be tracked with shorter periods than farther-away ones. On the other hand, computations in a real-time system may be more sensitive to changes in certain data than others, which in turn defines the different timing constraints on different tasks. For example, although a thermometer may produce a new temperature reading every second, computations may need to use the reading only once in every ten minutes. Given that most real-time systems have insufficient computing resources, we need to intelligently divide the computing resources among different tasks in order for the database system to produce the "best" result. In this thesis, we have studied strategies that provide effective utilization of the system resources. 5 1.5 Organization of the Thesis The goal of our research is to study design methodologies for real-time database systems. We have stated some of the requirements and the problems of real-time database systems in this chapter. In this thesis, we focus on the temporal aspect of real-time database systems. We propose scheduling and concurrency control algorithms to satisfy timing requirements and logical consistency. We also describe a design strategy to maintain external and temporal consistency and a method to assign timing constraints to tasks to effectively utilize resources. In the next chapter, we review related work in real-time system scheduling and database concurrency control. We describe in detail priority ceiling protocols as they are closely related to the algorithms we propose in this thesis. In Chapter 3, we propose an integrated scheduling and concurrency control algorithm for real-time database systems that guarantees a predictable temporal behavior and a serializable schedule. The algorithm in the chapter uses a static priority assignment scheduling algorithm. We prove the optimality of using the rate monotonic priority assignment [LL73] in the algorithm among static priority assignments in Chapter 4. Also in Chapter 4, we extend the algorithm to systems that allow different access types, such as read and write, for their data. We further extend the algorithm to a dynamic priority assignment scheme in Chapter 5. We then describe the impact of external consistency and temporal consistency on defining the temporal behavior of tasks in Chapter 6. In Chapter 7, we propose a method to assign timing constraints to tasks in order to utilize the CPU effectively. The thesis is concluded and future work discussed in Chapter 8. 6 Chapter 2 Past Research A real-time computer system has a set of tasks which are executed either only once or repeatedly. We use Ti to express the i-th task in the system. We call a single execution of a task a job. We express a job of a task Ti by Ji. Each real-time job has a ready time and a deadline which are usually specified in the task timing definition. A job can only be executed after its ready time and must be completed before the deadline. A job is active after the job becomes ready for execution, or arrives, and before the job execution completes. We show a job execution with rectangles as in Figure 2.1. In the diagram, time progresses from left to right. An up arrow expresses the arrival of a job and a down arrow expresses the deadline of the job. A task can be either periodic or aperiodic. A periodic task becomes active repeatedly in a constant interval. Monitoring and controlling tasks are usually performed periodically. A job of an aperiodic task is activated by pre-defined but irregular events. For example, the event can be an operator pushing a button or temperature exceeding a threshold value. For periodic tasks, computations usually must be finished by the end of each period. For aperiodic tasks, deadlines are individually defined. 2.1 Scheduling in Real-Time Systems Scheduling algorithms for real-time systems must provide predictable temporal behavior of jobs. A commonly used strategy in real-time scheduling algorithms is the priority-driven approach. job start completion time ready time preemption active deadline Figure 2.1: Execution of a Job 7 Using priority-driven algorithms, each job is assigned a priority based on some attributes of the job, such as the deadline and the period length. If a job execution can be interrupted anytime to allow the execution of other jobs, we say the scheduling policy is preemptive. The system always executes the ready job with the highest priority first if a priority-driven preemptive algorithm is used. The rate monotonic (RM) algorithm and the earliest deadline first (EDF) algorithm are two well-known priority-driven preemptive scheduling algorithms. RM is used for periodic tasks and assigns priorities to tasks according to period lengths of the tasks. A task with a shorter period is assigned a higher priority. Each job of a task is scheduled using the priority of the task. Since every job of a task has the same priority, we call this priority assignment static. Liu and Layland [LL73] show that the RM priority assignment is optimal among all static priority assignments in the sense that if a task set is feasible using the priority-driven preemptive approach with a static priority assignment, the task set is also feasible with RM. We say a task set is feasible in a schedule if all jobs of the task set can complete before their deadlines. EDF handles both periodic and aperiodic tasks and assigns priorities according to the deadlines of jobs. A job with an earlier deadline is assigned a higher priority. With the EDF priority assignment, jobs of the same task do not have the same priority. The priority assignment thus is dynamic. Liu and Layland [LL73] also show that the EDF priority assignment is optimal among dynamic priority assignments. EDF can schedule more tasks than RM [LL73] without missing the tasks' deadlines. It may however cause more jobs to miss their deadlines than RM under overload conditions because the algorithm executes jobs with missed deadlines first. On the other hand, RM has a predictable behavior under overload since tasks have fixed priorities. Suppose there are n periodic tasks, T1; T2; \Delta \Delta \Delta ; Tn. Let pj and ej be the period and the execution time of task Tj. We define ej=pj as the processor utilization of Tj. It has been shown [LL73] that if the total processor utilization of n periodic tasks in a processor is less than or equal to n(21=n \Gamma 1), i.e., U j nX i=1 ei pi ^ n(2 1=n \Gamma 1); (2.1) RM guarantees that the task set is feasible. In fact, the RM algorithm can often schedule a set of tasks with a total utilization greater than the said bound. Lehoczky et al. [LSD89] have derived an exact condition for a task set to be feasible by RM. Assuming the tasks are 8 pre-sorted so that p1 ! p2 ! \Delta \Delta \Delta ! pn, the feasibility condition is expressed with Li j min0!t^p i iX j=1 ej t & t pj ' ^ 1; for all i, 1 ^ i ^ n: (2.2) In Eq.(2.2), we need to find the minimum in the continuous interval of 0 ! t ^ pi. However, we only need to look at discrete t because of the characteristics of the ceiling function. We can rewrite Eq.(2.2) as follows: Li j mint2S i iX j=1 ej t & t pj ' ^ 1; for all i, 1 ^ i ^ n; (2.3) where Si = fkpjjj = 1; 2; \Delta \Delta \Delta ; i; k = 1; 2; \Delta \Delta \Delta ; bpi=pjcg: We call condition (2.1) the LL condition and both Eq.(2.2) and Eq.(2.3) the LSD condition. Although the LSD condition provides a higher processor utilization bound, it is much more complicated to check. EDF guarantees the feasibility of a task set if U = nX i=1 ei pi ^ 1 (2.4) is satisfied. 2.2 Concurrency Control Jobs share data objects in database systems. Many jobs may compete for data objects at any time. They cannot be randomly interleaved because some interleaving may cause erroneous results even if each job produces a correct result when it is executed by itself. A mechanism often used for concurrency control is the locking mechanism. Using the locking mechanism, a set of data objects is protected by a lock. We call the set of data objects a data item. The size of a data item, which is often called granularity, is defined by other criteria [BHG87]. Usually, a data item can be locked in different access types in database systems. For example, a data item can be locked in either read or write type. Whenever a job accesses a data item, the job must acquire the lock of the data item in the appropriate access type. Two accesses on the same data item may or may not be compatible. It depends on the type of the lock. For example, a read lock and a write lock are usually incompatible because the execution order of a read access and a write access makes a difference in the result database state. In this thesis, we assume 9 that there is only one access type for each lock and accesses on the same data item are always incompatible except in Chapter 4 where we discuss an algorithm for different access types. The job must release locks after using the data items so that other jobs can get the locks. The order of acquiring and releasing locks is defined by other criteria, such as the two-phase locking protocol [EGLT76], so that tasks produce "correct" results. We call acquiring and releasing a lock a lock operation and an unlock operation, respectively. If job Ji has the lock for data item aek when another job Jj requests the same lock, either Jj waits until the lock is released by Ji or Ji is aborted so that Jj can acquire the lock. The duration between a lock operation and the corresponding unlock operation defines a critical section. Serializability is a commonly used correctness criterion for interleaved job executions. An execution is serializable if it produces the same result and transforms the database to the same state as some serial execution does. Without knowing what each job does at each step of the execution, we can only guarantee serializability by ordering conflicting accesses in the same order as in a serial execution. An interleaved job execution is serializable if and only if the serialization graph of the execution schedule is acyclic [BHG87]. The serialization graph is a directed graph whose nodes are jobs. An edge Ji ! Jj indicates that a data access by Ji precedes a data access by Jj in the schedule, i.e., there exists a data item aek such that Ji accesses aek before Jj in the schedule. A commonly used protocol to maintain serializability is the two-phase locking protocol (2PL) [EGLT76]. 2PL requires that a job performs lock and unlock operations in two phases: a growing phase and a shrinking phase. During the growing phase, the job can acquire new locks. At the first unlock operation, the job enters into the shrinking phase and cannot receive any more new locks. 2.3 Priority Ceiling Protocols 2PL guarantees serializability. However, deadlocks may occur [BHG87]. Deadlocks are fatal in real-time systems since no jobs involved in the deadlocks can complete. The other problem is that priority inversions [SRL90] may occur. Priority inversion is a state of a system in which a higher priority job is forced to wait while a lower priority job is executing. We say that job Jh is blocked by job Jl when there are a higher priority ready job Jh and a lower priority 10 12345678901234567891234567890123456789 123456789012345678912345671234567 123 123 1234512345 12345 rk rj Ji Li(rj) Ui(rj) Ui(rk) Li(rk) 1234567812345678 1234567812345678 12345678rl 1234567812345678 1234567812345678 1234567812345678 1234567812345678 Li(rl) Ui(rl) Figure 2.2: Lock Operation Ordering Policy of PCP ready job Jl in a system, and Jh is waiting while Jl is executing. Jobs are usually assigned priorities in real-time database systems. A low priority job may lock a data item before a high priority job needs it and cause a priority inversion. Uncontrolled priority inversion causes unpredictable delay for jobs. There is a class of algorithms that integrates scheduling and concurrency control algorithms and utilizes the idea of priority ceiling [SRL90, CL90, Bak90]. We call this class of algorithms priority ceiling protocols. With the priority ceiling protocols, deadlocks are avoided and the priority inversion delay is limited to at most the duration of a single critical section. Priority ceiling protocols are applicable not only to databases but also to systems with exclusively accessed resources. Therefore, we use "resource" instead of "data item" in the following discussions. We discuss priority ceiling protocols in detail in this section because the algorithms we are proposing are based on these algorithms. 2.3.1 The Original Priority Ceiling Protocol The original priority ceiling protocol (PCP) [SRL90] prevents deadlocks and has a predictable temporal behavior. PCP is made of three parts: a scheduling algorithm, a concurrency control algorithm, and an interaction protocol between the scheduling algorithm and the concurrency control algorithm. PCP uses a priority-driven approach as its scheduling algorithm and is designed for systems with static task priorities. Similar algorithms using dynamic priority schemes have also been proposed [CL90, Bak90]. They will be discussed later. PCP assumes that critical sections are properly nested (Figure 2.2). Let Li(aej) and Ui(aej) be the lock and unlock operations by job Ji for resource aej. Properly nested critical sections mean that, for all j and k, Ui(aek) is performed between Li(aej) and Ui(aej) if and only if Li(aek) is 11 performed between Li(aej) and Ui(aej). Also, a job can have critical sections that do not overlap. PCP cannot handle partially overlapped critical sections. In PCP, a priority ceiling is defined for each resource. The priority ceiling of a resource is the highest task priority among the tasks that may access the resource. For example, if there are three tasks T1, T2, and T3 that will lock resource aej and T1 has the highest priority, the priority ceiling of aej is defined to be the priority of T1. We express the priority ceiling of aej by OEj. Note that the priority of a job is equal to the priority of a task which the job is an execution of, since PCP assumes a static priority assignment. Let CP CPi (t) denote the highest priority ceiling among resources whose locks are held by jobs other than Ji in the system at time t. Assuming all priorities are positive numbers, we define CP CPi (t) = 0 while no lock is held by any job other than Ji. In PCP, when Ji requests a lock on any resource at time t, Ji's priority ssi and CP CPi (t) are compared. If ssi is less than or equal to CP CPi (t), the lock request is rejected and Ji is suspended. When a lock request of a job is rejected, the system suspends the job and starts executing the highest priority job among other active jobs. When job Jh's blocking condition is resolved, the system checks whether Jh has the highest priority. If it has, the system suspends the currently running job and resumes the execution of Jh. In real-time systems, the concurrency control algorithm must interact with the scheduling algorithm. PCP adopts priority inheritance for this purpose. According to priority inheritance, when a job Ji is suspended, the job that holds the lock of a resource with the priority ceiling CP CPi (t) inherits job Ji's priority ssi. We call the execution priority of Ji, which is the maximum of Ji's original priority and its inherited priorities, augmented priority. We express the augmented priority of Ji with ss\Lambda i . PCP is summarized as follows. Priority Ceiling Protocol (PCP) 1. (Scheduling Algorithm) A static priority assignment priority-driven algorithm. 2. (Lock Operation Ordering) Critical sections are properly nested. 3. (Concurrency Control Algorithm) (a) A request for Li(aej) is granted if ssi ? CP CPi (t). Otherwise, it is rejected. (b) A request for Ui(aej) is always granted. 12 T1 T3 T2 12341234 12341234 1234 12345671234567 123123 123 0 2 4 time T1 T3 T2 12341234 12341234 0 2 4 123456123456 6 8 10 1234512345 123123 r1 r2 1234567812345678 1234567812345678 6 12341234 12341234 1234 1234512345 1234512345 12345 123123 123 14 12 (a) Task Set (b) Schedule 1234567812345678 1234567812345678 1234567812345678 1234567812345678 123456789123456789 123456789123456789 123456789r3 1234567812345678 1234567812345678 1234567812345678 1234567812345678 8 time 1234512345 12341234 1234 16 critical sections 12341234 12341234 18 20 123123 123 10 f1=p1 f2=p2 f3=p3 Figure 2.3: Example 1 4. (Interaction Protocol) (a) If the request for Li(aej) is rejected, job Ji is blocked. Job Jk that holds the lock for resource aeh whose priority ceiling is CP CPi (t) inherits Ji's priority. (b) When Ji performs Ui(aej), Ji's augmented priority becomes the highest among Ji's original priority ssi and the priorities of jobs which Ji still blocks after releasing the lock for aej. 2 Example 1 In Figure 2.3, there are three tasks T1, T2, and T3. T1, T2, and T3 have priorities ss1, ss2, and ss3 respectively. ss1 is the highest priority and ss3 is the lowest. Periods of T1, T2, and T3 are 8, 26, and 65, respectively. A job of T3 arrives at time 0, a job of T2 arrives at 2, and a job of T1 arrives at 5. Resource ae1 is used by T1, T2, and T3. ae2 is used by T2 and T3. ae3 is accessed by T3. Then, the priority ceilings of ae1, ae2, and ae3 are ss1, ss2, and ss3, respectively. The start and end of the critical sections and execution times of the tasks are shown in Figure 2.3 (a). 13 Using PCP, the example task set is scheduled as in Figure 2.3 (b). J3 starts to execute at time 0. J3 enters into the critical section for ae1 at time 1 since CP CP3 (1) = 0. At time 2, J2 arrives. Since ss\Lambda 2 = ss2 ? ss\Lambda 3 = ss3, J2 starts execution. When J2 requests the lock for ae2 at time 3, J2 is blocked because J2's priority ss2 is lower than CP CP2 (3) = ss1. J3 inherits J2's priority ss2 and now ss\Lambda 3 = ss2. J3 resumes execution. J3 releases ae1 at time 4. Since CP CP2 (4) = 0, J2's blocking is resolved and J2 is granted the lock for ae2. Also, ss\Lambda 3 returns to its original priority ss3. J2 preempts J3 and resumes execution. At time 5, J1 arrives and starts execution. J1 requests the lock for ae1 at time 6. At this time, CP CP1 (6) = ss2 is lower than J1's original priority ss1. J1 is allowed to enter into the critical section and continues the execution. J1 exits from its critical section at time 7 and completes execution at time 8. J2 resumes execution and requests the lock for ae1 at time 9. Since CP CP2 (9) = 0, the lock is granted. J2 releases the locks for ae1 and ae2 at time 10 and completes execution at time 11. J3 resumes execution. The second job J1 of T1 arrives at time 13 and starts execution. At time 14, J1 requests the lock for ae1. Since CP CP1 (14) = 0, J1 enters into the critical section. J1 exits from the critical section at time 15 and completes at time 16. J3 resumes execution and requests the lock for ae2 at time 16. Since CP CP3 (16) = 0, the lock is granted. J3 releases the lock for ae2 at time 17. J3 requests the lock for ae3 at time 19, releases the lock at time 20, and completes its execution at time 21. 2 PCP guarantees that a job is blocked at most once by one outermost critical section of a lower priority job (single-blocking property). Because of this property, we can determine whether a task set satisfies all deadlines when the RM priority assignment and PCP are used [SRL90]. If a task set satisfies the following condition for all tasks Ti in the task set, the task set is feasible by the combination of the RM priority assignment and PCP: e1 p1 + e2 p2 + \Delta \Delta \Delta + ei pi + Bi pi ^ i(2 1=i \Gamma 1); for all i, 1 ^ i ^ n; (2.5) where ei and pi are the execution time and the period of task Ti. Bi is the worst-case blocking length of task Ti, i.e., the duration of the longest critical section that can cause Ti to be blocked. Since we know that only the critical sections that are in a lower priority task and lock resources with higher priority ceilings than ssi can block Ti, we can decide Bi for each Ti before the system becomes operational. 14 Sha et al. [SRL90] also provide a tighter condition than Eq.(2.5). The condition is an extension of Eq.(2.2). If a task set satisfies the following condition for all tasks Ti in the task set, the task set is feasible by the combination of the RM priority assignment and PCP: min0!t^p i 0@ iX j=1 ej t & t pj ' + Bi t 1A ^ 1; for all i, 1 ^ i ^ n: (2.6) PCP avoids deadlock (no-deadlock property) and allows only one blocking by a single critical section in a lower priority job (single-blocking property). However, it does not guarantee serializability. For example, in Figure 2.3 (b), resource ae1 is first used by J3, then J1, and finally J2. Resource ae2 is first accessed by J2 and then J3. Therefore, there is a cycle J1 ! J2 ! J3 ! J1 in its serialization graph and the schedule is not serializable. In order to avoid the serializability violation, we can use 2PL along with PCP. However, 2PL tends to make blocking longer because it forces jobs to hold locks until all locks are acquired, even if some of the resources are only used much earlier than the job is allowed to release locks. With longer blocking, we can schedule fewer jobs in order to satisfy their timing constraints. In Section 3.5, we will compare the combination of PCP and 2PL with the algorithm we propose in the next chapter. 2.3.2 Priority Ceiling Protocols with Dynamic Priority Assignment PCP assumes that task priorities are static. With a static priority assignment, the processor utilization needs to be lower than the utilization with a dynamic priority assignment in order to satisfy timing constraints. Modified algorithms of PCP that can use a dynamic priority assignment and are applicable to both periodic and aperiodic tasks have been proposed by Chen and Lin [CL90], and Baker [Bak90]. The Dynamic priority ceiling protocol (DPCP), proposed by Chen and Lin [CL90], uses the EDF algorithm for the priority assignment of jobs. The priority of a job is defined by the deadline of the job. In addition to jobs, each task has a priority. The task priority is the priority of its current job if the job is active. Otherwise, it is the priority of the next job to arrive in the next period. Priority ceilings of resources are defined based on the task priority definition. Since the priority of a task changes when a job of the task completes, some priority ceilings may change as well. 15 T1 T2 1234512345 1234512345 12345671234567 0 2 4 time T1 T2 12341234 12341234 0 2 4 6 8 10 1234512345 12345 123123r1 r2 6 14 12 (a) Task Set (b) Schedule time 1234567812345678 12345678 12345671234567 123456789123456789 123456789 16 critical sections 1234512345 1234512345 12341234 12341234 123123 12341234 1234 12341234 1234512345 12345 Figure 2.4: Example 2 Example 2 There are two periodic tasks T1 and T2 (Figure 2.4). T1 uses resource ae1 and T2 uses resources ae1 and ae2. T1's period is 7. T2 has a period of 12. ffl At time 0, the priorities of T1 and T2 are 71 and 12. The priority ceilings of ae1 and ae2 are 7 and 12. ffl At time 3, T1 completes its first job and its priority becomes 14. The priority ceilings of ae1 and ae2 both become 12 because ae1's priority ceiling is now the maximum of T1's priority 14 and T2's priority 12. 2 The concurrency control algorithm is the same as PCP. A lock request is granted if the priority of the requesting job is higher than the highest priority ceiling of all locks currently locked by other jobs. DPCP also uses priority inheritance as the interaction protocol. Baker [Bak90] proposes another approach to dynamic priority assignment scheduling. The algorithm is called stack resource policy (SRP). There are three major differences between PCP and SRP in addition to using a dynamic priority assignment. The first difference is the time that blocking occurs. In SRP, blocking occurs at the beginning of job executions instead of on the resource requests. A job is blocked before it starts to execute if the priority of the job is not higher than the highest priority ceiling of all resources locked by other jobs. In this way, we can reduce the number of context switches. 1Although we use a larger number to express a higher priority in the rest of the thesis, we use a smaller number for a higher priority in this example for convenience. 16 Tj Ti higher priority late arrival Figure 2.5: High Priority with Late Arrival The second difference is that SRP uses a different criterion to assign the priority ceilings. The criterion is called preemption level. The preemption level is defined for each task. Task Ti has a higher preemption level than task Tj if and only if Ti can have a higher priority than Tj and can arrive after Tj. When the EDF algorithm is used, Ti can have a higher priority than Tj and can arrive after Tj if and only if Ti has a shorter relative deadline than Tj (Figure 2.5). The relative deadline of a job is defined by the duration between the ready time and the deadline. A task with a shorter relative deadline has a higher preemption level. Therefore, if every aperiodic task has a fixed relative deadline, we can assign a preemption level to each aperiodic task. The priority ceiling of a resource is defined by the maximum preemption level of tasks that use the resource. If we use the relative deadline to express the preemption level, the preemption levels of T1 and T2 in Figure 2.4 are the fixed values 7 and 12, respectively. Priority ceilings of ae1 and ae2 are 7 and 12. In SRP, a job is blocked from starting its execution if its preemption level is not higher than the maximum priority ceiling of all resources locked by other jobs. As the third contribution of SRP, Baker extends the algorithm to be applicable to multi-unit resources. The priority ceiling is assigned to each resource type with the number of available resources of the type as a parameter of the priority ceiling. When there are i units of resources available, the priority ceiling of the resource type is the maximum preemption level of the tasks that require more than i units of the resources. Suppose there are three tasks, T1, T2, and T3 and three units of resource ae. T1, T2, and T3 use 1 unit, 2 units, and 3 units of resource ae, respectively. Let OE(i) be the priority ceiling of resource ae when there are i units available. Assuming that T1 has the highest preemption level and T3 has the lowest, the priority ceiling OE(i) is defined as follows: OE(0) = (preemption level of T1), OE(1) = (preemption level of T2), OE(2) = (preemption level of T3), and OE(3) = 0. 17 Both DPCP and SRP have the same two properties that PCP has. They avoid deadlocks and each job is blocked at most once. They also share the same shortcoming of not guaranteeing serializability. From the no-deadlock and the single-blocking properties, we can determine the schedulability of a task set. Let T1, T2, \Delta \Delta \Delta , Tn be a task set in ascending order of relative deadline lengths, i.e., Tn has the longest relative deadline. Baker [Bak91] proved that a task set is feasible using SRP if the task set satisfies the following condition: iX j=1 ei pi + Bi pi ^ 1; for all i, 1 ^ i ^ n: (2.7) Chen [Che91] further analyzes the schedulability condition of both DPCP and SRP. 18 Chapter 3 The Convex Ceiling Protocol As we have explained in Chapter 2, PCP, DPCP, and SRP can only guarantee a predictable temporal behavior, not serializability. In other words, they can satisfy the timing requirements, but not the need for logical consistency. For some applications, however, logical consistency is necessary. In this chapter, we propose a concurrency control algorithm that ensures the serializability property in addition to the no-deadlock and the single-blocking properties. In this chapter, we assume that the system has a single processor and all tasks in the system are periodic tasks. Each job must complete its execution by the end of its period. Tasks are assigned fixed priorities and the priority-driven algorithm is used for scheduling. The periodic task assumption will be removed in a later chapter. 3.1 Priority Ceiling Function The priority ceiling is defined in PCP. Let ^Ri(t) be the highest priority ceiling of all data items locked by job Ji at time t. If no data item is locked by Ji, ^Ri(t) = 0. A lock operation Li(aex) and an unlock operation Ui(aey) may change ^Ri(t). The ^R3(t) of Example 1 in Chapter 2 is shown in Figure 3.1. Here an empty circle means an open end, while a filled square means a closed end. The reason for the serializability violation in Example 1 is that ^R3(t) has more than one peak. J2 can enter into a critical section when ^R3(t) drops below ss2 between time 3 and 5. Generally, if ^Ri(t) of a job Ji has more than one peak, serializability may not be guaranteed in PCP. Suppose there is a job Jj with priority ssj, ssj ? ssi. If Ji accesses data items aek and ael in two non-overlapped critical sections and ^Ri(t) drops below ssj between the two critical sections as shown in Figure 3.2, then there is a possibility that Jj enters its critical sections for both aek and ael in the ^Ri(t) valley. With this observation, if we control ^Ri(t) to have only one peak, serializability may be ensured. We define a function \Phi i(t) for each task such that \Phi i(t) * ^Ri(t) 19 p1 p2 p3 2 4 6 R3( t) time t T3 123123 123 1234567812345678 1234567812345678 1234567812345678 1234567812345678 1234567812345678 1234567812345678 0 0 8 12341234 1234 123123 r1 r2 1234567812345678 1234567812345678 12345678r3 f1=p1 f2=p2 f3=p3 ^ 10 Figure 3.1: ^R3(t) in Example 1 and \Phi i(t) has no valley. Our intention is to use \Phi i(t) instead of ^Ri(t) for concurrency control. We call \Phi i(t) the priority ceiling function of task Ti. In order to define \Phi i(t), we define the maximum remainder priority \Omega i(t) for each task Ti. \Omega i(t) is the maximum priority ceiling of data items that task Ti will use after time t. If no data item will be used after time t, \Omega i(t) = 0. For example, the maximum remainder priority of task T3 in Example 1 is shown in Figure 3.3. Note that \Omega i(t) is a monotonically decreasing function. Let tiniti (aej) and tfini (aej) be the times a job Ji of a task Ti accesses data item aej for the first time and the last time, respectively. We call tiniti (aej) and tfini (aej) the initial and final access instants of Ji on aej. When a job Ji accesses a data item aej, if the priority ceiling of aej is higher than \Phi i(t), \Phi i(t) is set to the priority ceiling of aej. Therefore, \Phi i(t) * ^Ri(t). When Ji accesses aej for the last time, \Phi i(t) is set to the highest priority ceiling of data items that Ji accesses after that time. \Phi i(t) is the function used in our concurrency control algorithm explained in the next section. \Phi i(t) is defined as follows. Priority Ceiling Function: \Phi i(t) (\Phi 1) When a job of Ti starts execution, \Phi i(t) = 0. (\Phi 2) At t = tiniti (aej), if \Phi i(t) is less than the priority ceiling of aej, \Phi i(t) is set to the priority ceiling of aej. 20 fkfl flflp jfl pifl 0fl Ri( t)fl^fl Li(rl)fl Ui(rl)flUi(rk)flLi(rk)fl time tfl Figure 3.2: ^Ri(t) with Two Peaks (\Phi 3) At t = tfini (aej), if \Phi i(t) ? \Omega i(t), \Phi i(t) is set to \Omega i(t). 2 \Phi i(t) increases only in the event of (\Phi 2) and decreases only in the event of (\Phi 3) in the above definition. \Phi i(t) = 0 before a job of Ti accesses any data item and after a job of Ti accesses all data items. The priority ceiling function of T3 in Example 1 is defined as in Figure 3.4. Theorem 3.1 \Phi i(t) has at most one peak. p1 p2 p3 \Omega 3(t) time t T3 123123 123 1234567812345678 1234567812345678 1234567812345678 1234567812345678 1234567812345678 1234567812345678 0 1234512345 12345 123123 r1 r2 1234567812345678 1234567812345678r3 f1=p1 f2=p2 f3=p3 0 2 4 6 8 10 Figure 3.3: Maximum Remainder Priority 21 \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma f1= p1fl r2fl r3fl f2= p2fl f3= p3fl time tfl8fl p1fl p2fl p3fl 0fl \Phi 3 (t)fl 6fl4fl2fl 10fl0fl r1fl T3fl Figure 3.4: Priority Ceiling Function Proof: Suppose \Phi i(t) has two peaks. Since \Phi i(t) decreases only when (\Phi 3) is applied and increases only when (\Phi 2) is applied, there are times t1 and t2, t1 ! t2, such that (\Phi 3) is applied at time t1 and (\Phi 2) is applied at time t2. Without loss of generality, let us assume that there is no event (\Phi 2) or (\Phi 3) between t1 and t2. From the definition of \Omega i(t), Ti does not access any data item with a priority ceiling higher than \Omega i(t1) = \Phi i(t1+) after time t1. By t1+, we mean immediately after \Phi i(t) is set to \Omega i(t1). At time t2, Ti accesses a data item aej such that \Phi i(t2) is less than the priority ceiling of aej. Since neither (\Phi 2) nor (\Phi 3) happens between t1 and t2, \Phi i(t1+) = \Phi i(t2). Since \Phi i(t1+) = \Omega i(t1), \Omega i(t1) must be less than the priority ceiling of aej which is used after t1. This is a contradiction. Therefore, \Phi i(t) has only one peak. 2 3.2 The Convex Ceiling Protocol The Convex ceiling protocol (CCP) is an integrated scheduling and concurrency control algorithm. CCP avoids any deadlock and guarantees a single blocking by one lower priority job. In addition, CCP guarantees serializability. When a job Ji requests its first access to a data item, the system checks if job Ji's priority ssi is higher than all other jobs' priority ceiling function values. We express the maximum \Phi j(t) of all jobs Jj , j 6= i, by CCCPi (t). If ssi ? CCCPi (t), Ji is allowed to proceed. Otherwise, Ji is suspended. The priority of the suspended job is inherited by the job Jj that has the maximum \Phi j(t). Therefore, Jj 's execution priority may be different from its original priority ssj. We call the execution priority the augmented priority and denote it by ss\Lambda j . 22 CCP is defined as follows. Note that \Phi i(t), and consequently CCCPi (t), changes according to the definition of \Phi i(t) as the execution progresses. Convex Ceiling Protocol (CCP) 1. (Scheduling Algorithm) A static priority assignment priority-driven algorithm. 2. (Concurrency Control Algorithm) When a job Ji requests the first data access to a data item, (a) if Ji's original priority ssi is higher than CCCPi (t), Ji is allowed to proceed to the initial access instant on the data item. (b) Otherwise, Ji is suspended until ssi ? CCCPi (t) is satisfied. 3. (Interaction Protocol) If Ji is suspended, the augmented priority ss\Lambda i of Ji is assigned to job Jk which has the maximum \Phi k(t). 2 CCP does not use locks. However, since the scheduler needs to know the first access and the last access to each data item in a job execution in order to control \Phi i(t) and CCCPi (t), it is convenient to assume that each job sends messages to the scheduler before the first access and after the last access. We call a message of the first access an initial access notice and a message of the last access a final access notice. Between an initial access notice and the corresponding initial access instant of a job, a lower priority job may execute if the former job is blocked. Between a final access instant and the corresponding final access notice of a job, no lower priority job can execute. We call the duration between an initial access instant and the corresponding final access instant a resource demand section. For example, the tasks of the task set in Example 1 (Figure 3.5(a)) are assigned priority ceiling functions as shown in Figure 3.5(b). T3's priority ceiling function is equal to 0 for the first time unit, then it goes up to ss1 until the third time unit. Then, \Phi 3(t) goes down to ss2, and so on. If a job J3 of T3 arrives at time 0 and both a job J1 of T1 and a job J2 of T2 arrive at time 2, the task set is scheduled as in Figure 3.5(c). When J1 arrives at time 2, C1(2) is ss1. However, since J1 does not request any data item for the first time unit of the execution, J1 executes. At time 3, J1 sends an initial access notice for ae1. Since C1(3) = ss1, J1 is blocked. J3 sends its final access notice for ae1 at time 4. Since C1(4) is equal to 0 now, J1 resumes its execution. Time 4 is the initial access instant of J1 on ae1. 23 \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma T1fl 8fl 10fl4fl0fl 2fl T2fl T3fl r1fl r2fl r3fl 6fl p3flp2flp1fl f2=p2fl f3=p3fl f1=p1fl p1fl p1fl p1fl p1flp2fl p3flp3flp2flp1flp1fl timefl timefl 0fl 2fl 4fl 6fl 8fl 10fl 12fl 10fl 16fl 18fl 20fl 22fl 24fl p1fl p1flp2fl (a) Task Setfl (b) Priority Ceiling Functionfl (c) Schedulefl initial access notice for r1fl initial access instant on r1fl final access notice for r1fl 0fl 0fl 0fl 0fl 0fl 0flT3fl T2fl T1fl T1fl T2fl T3fl 8fl 10fl4fl0fl 2fl 6fl timefl Figure 3.5: Example of Convex Ceiling Protocol 24 3.3 Properties of CCP Since CCP is an extension of PCP, it inherits and preserves the desirable properties of PCP. In addition, CCP guarantees the serializability of application processes. In this section, we prove the properties of CCP. 3.3.1 Single-Blocking and No-Deadlock Properties We assume tasks T1, T2, \Delta \Delta \Delta , Tn, are sorted in descending order of priority, i.e., ss1 ? ss2 ? \Delta \Delta \Delta ? ssn. Also, we assume, for simplicity of proofs, that there is no tie in priorities. Modification of the proofs to include ties in priorities is straightforward. The blocking condition is summarized in the next lemma. From the blocking condition, we prove that a job cannot block other jobs before entering any of its resource demand sections. Also, we prove that a job can be blocked only before entering any of its resource demand sections. From these two properties, we see that a job cannot wait for a data item while holding another data item, i.e., CCP avoids deadlocks. We prove the single-blocking property by contradiction. If a job Ji is blocked by two lower priority jobs, Jj and Jk, the lower priority jobs' priority ceiling functions must have higher values than the priority of Ji. Then, one of the lower priority jobs, for example Jj , must enter its resource demand section while Jk's priority ceiling function is higher than the priority of Ji. This contradicts CCP. The formal proofs are described below. Lemma 3.2 A job Jh is blocked by a lower priority job Jl at time tb if and only if the following four conditions are satisfied: 1. a job Ji with its augmented priority ss\Lambda i higher than or equal to ss\Lambda h sends an initial access notice at some time ta, ta ! tb, 2. ssi ^ CCCPi (t), for all t, ta ^ t ^ tb, 3. CCCPi (tb) = \Phi l(tb), and 4. ss\Lambda l is the highest priority in the system at tb. Proof: From the definition of the blocking, job Jh is blocked by job Jl when Jh is waiting while Jl is executing. With CCP, this situation occurs if and only if Jl inherits an augmented priority higher than or equal to the augmented priority ss\Lambda h of Jh and it is the highest augmented 25 priority in the system. Jl inherits an augmented priority higher than or equal to ss\Lambda h at time tb if and only if a job Ji with its augmented priority ss\Lambda i higher than or equal to ss\Lambda h sends an initial access notice at time ta, ta ! tb, ssi ? CCCPi (t) is not satisfied between ta and tb, and CCCPi (tb) = \Phi l(tb): Therefore, the lemma holds. 2 Lemma 3.3 If the execution of a job is at an instant either before the first initial access instant or after the last final access instant, the job cannot block any other jobs with higher original priorities. Proof: From Lemma 3.2, a job Jh is blocked by a lower priority job Jl at time tb only if there is a job Ji such that ssi ^ CCCPi (t); for all t, ta ^ t ^ tb, and CCCPi (tb) = \Phi l(tb): From the definition of \Phi l(t), if the execution of Jl is at an instant either before the first initial access instant or after the last final access instant, \Phi l(t) = 0. ssi ^ \Phi l(tb) = 0 cannot be true because ssi ? 0 for every job Ji from the definition of the priority. Therefore, Jl cannot block Jh. 2 Let us call the duration between the first initial access instant and the last final access instant the outermost demand section. Lemma 3.4 If time t1 is the first initial access instant of a job Ji, then CCCPi (t1) = maxi!k^n \Phi k(t1); i.e., no higher priority job than Ji is in its outermost demand section at time t1. Proof: Since Ji is not in its outermost demand section before t1, Ji is not blocking any other job from Lemma 3.3. The augmented priority ss\Lambda i of Ji is equal to ssi. Because ss\Lambda i = ssi is the highest priority among priorities of active jobs at t1, all jobs with higher priorities than Ji are not ready and cannot be in their outermost demand sections, i.e., max1^k!i \Phi k(t1) = 0. Therefore, CCCPi (t1) = max 1^k^n k6=i \Phi k(t1) = maxi!k^n \Phi k(t1): 2 26 Theorem 3.5 A job may be blocked only before the first initial access instant. Proof: Let t1 be the first initial access instant of job Ji. Since Ji is allowed to proceed at t1, we know ssi ? CCCPi (t1): (3.1) From Lemma 3.4 and Eq.(3.1), ssi ? maxi!k^n \Phi k(t1): (3.2) Suppose Ji is blocked by a lower priority job Jl at t2 for the first time after t1. From Lemma 3.2, Ji is blocked by a lower priority job Jl at time t2 if and only if there is a job Jj with its augmented priority ss\Lambda j higher than or equal to ss\Lambda i , Jj sends an initial access notice just before time t2, and ssj ^ CCCPj (t2) = max 1^k^n k6=j \Phi k(t2) = \Phi l(t2): (3.3) No job with a lower original priority than ssi is executed between t1 and t2 because Ji is blocked for the first time at t2 after t1. Therefore, the original priority ssj of Jj must be higher than or equal to ssi, i.e., ssj * ssi: (3.4) Since we assume ss1 ? ss2 ? \Delta \Delta \Delta ? ssn, ssi ? ssl means i ! l. Therefore, max 1^k^n k6=j \Phi k(t2) = \Phi l(t2) = maxi!k^n \Phi k(t2): (3.5) Since no job with its priority lower than ssi is executed from t1 to t2, maxi!k^n \Phi k(t2) = maxi!k^n \Phi k(t1): (3.6) From Eq.(3.3), (3.4), (3.5), and (3.6), we have ssi ^ maxi!k^n \Phi k(t1): This inequality contradicts Eq.(3.2). 2 Corollary 3.6 Suppose t1 is the first initial access instant of Ji. Then, maxi!k^n \Phi k(t) = maxi!k^n \Phi k(t1); for all t, t1 ! t ^ tc; where tc is the completion time of Ji. 27 Proof: From Theorem 3.5, Ji is not blocked for t1 ^ t ^ tc. This means that a job Jk whose original priority is less than ssi has no chance to be performed in this interval. Hence, the corollary holds. 2 Corollary 3.7 When job Ji is blocked, Ji's augmented priority ss\Lambda i is equal to its original priority ssi. Proof: From Theorem 3.5, Ji can be blocked only before its first initial access instant. Since Ji is not in its outermost demand section, Ji cannot block jobs from Lemma 3.3. Hence, ss\Lambda i = ssi. 2 When there is a deadlock, there must be a circular wait condition [CES71]. In the circular wait condition, each job in the cycle is in at least one resource demand section while waiting to enter into another resource demand section of a data item and the data item is being accessed by another job in its resource demand section. Theorem 3.8 CCP prevents deadlocks. Proof: Suppose there is a deadlock. Then, there must be a circular wait condition. Let Ji be the highest priority job in the cycle. From Theorem 3.5, Ji will not be blocked once it enters into a resource demand section. However, since Ji is the highest priority job in the cycle, no blocking means that Ji need not wait in order to enter into additional resource demand sections. In other words, there is no circular wait condition. Therefore, there is no deadlock. 2 Theorem 3.9 A job Jl blocks a higher priority job Jh at time tb if and only if the following four conditions are satisfied: 1. a job Ji with its original priority ssi higher than or equal to ssh sends an initial access notice at some time ta, ta ! tb, 2. ssi ^ CCCPi (t); for all t, ta ^ t ^ tb; 3. CCCPi (tb) = \Phi l(tb), and 4. ss\Lambda l is the highest priority in the system at tb. Proof: From Lemma 3.2, a job Jh is blocked by a lower priority job Jl at time tb if and only if a job Ji with its augmented priority ss\Lambda i higher than or equal to ss\Lambda h sends an initial access 28 notice at time ta, ta ! tb, and the conditions 2, 3, and 4 are satisfied. Since both Jh and Ji are being blocked between ta and tb, ss\Lambda i = ssi and ss\Lambda h = ssh at ta from Corollary 3.7. Therefore, ss\Lambda h = ssh ^ ss\Lambda i = ssi at ta. 2 Theorem 3.9 will be used in the next section to discuss the schedulability condition. Lemma 3.10 If a job Jl blocks a higher priority job Jh, \Phi l(t) * ssh holds when Jh arrives at time t. Proof: Suppose \Phi l(t1) ! ssh where t1 is the arrival time of Jh and Jl blocks Jh at time t2, t2 ? t1. Let t2 be the first time Jl blocks Jh. Then, from Theorem 3.9, a job Ji such that ssh ^ ssi ^ CCCPi (t2) = \Phi l(t2) is sending its first initial access notice just before t2. Because \Phi l(t1) ! ssh ^ \Phi l(t2), Jl must be executed sometime between t1 and t2 in order to have \Phi l(t) increased. However, since t2 is the first time Jh is blocked by Jl, Jl cannot be executed in the duration between t1 and t2. This is a contradiction. 2 Lemma 3.11 If we assume tiniti (aex) ! tfini (aey), it must be true that \Phi i(t) * min(OEx; OEy) for tiniti (aex) ! t ^ tfini (aey) in any schedule produced by CCP. Proof: From the definition of \Phi i(t), \Phi i(t) is at least as high as OEx at time t just after tiniti (aex) and is at least as high as OEy at t = tfini (aey). Since \Phi i(t) has only one peak from Theorem 3.1, the lemma holds. 2 Theorem 3.12 A job is blocked by at most one lower priority job. Proof: Suppose Jh is blocked by lower priority jobs Jl1 and Jl2. Then, from Lemma 3.10, \Phi l1(th) * ssh and \Phi l2(th) * ssh where th is the time Jh arrives. Both Jl1 and Jl2 are in their outermost demand sections when they block Jh from Lemma 3.3. Without loss of generality, we can assume that Jl1 enters into its outermost demand section before Jl2 does. Let tl1 and tl2 be the times Jl1 and Jl2 enter into their outermost demand sections. While Jl1 is in its outermost demand section, \Phi l1(t) is at least as high as ssl1 from Lemma 3.11. Therefore, CCCPl2 (t) is also at least as high as ssl1. Since Jl2 enters into its outermost demand section after Jl1 has entered its outermost demand section, ssl2 ? CCCPl2 (tl2) * ssl1. From Lemma 3.4, ssl2 ? CCCPl2 (tl2) = maxl2!k^n \Phi k(tl2): (3.7) 29 From Corollary 3.6, maxl2!k^n \Phi k(t) = maxl2!k^n \Phi k(tl2) for all t, tl2 ! t ^ (completion time of Jl2). Since Jl2 blocks Jh, Jl2 has not completed when Jh arrives. Therefore, maxl2!k^n \Phi k(th) = maxl2!k^n \Phi k(tl2): (3.8) Since l1 ? l2 from the assumption ss1 ? ss2 ? \Delta \Delta \Delta ? ssn and ssl1 ^ ssl2, maxl2!k^n \Phi k(th) * \Phi l1(th) (3.9) From Eq.(3.7), (3.8), and (3.9), and the assumption \Phi l1(th) * ssh, ssl2 ? \Phi l1(th) * ssh: However, Jl2 must have a lower priority than Jh. This is a contradiction. 2 3.3.2 Serializability If CCP does not guarantee serializability, there may be a cycle Jn ! J1 ! \Delta \Delta \Delta ! Jn\Gamma 1 ! Jn in the serialization graph of a schedule generated by CCP. Suppose Jn is the lowest priority job in the cycle. Then, J1, \Delta \Delta \Delta , Jn\Gamma 1 must be executed between two data accesses of Jn. Since the priority ceiling function of Jn has at most one peak, CCP cannot generate this schedule. The detailed proof follows. Lemma 3.13 When two jobs Ji and Jj use the same data item aek, we must have either tfini (aek) ! tinitj (aek) or tfinj (aek) ! tiniti (aek) in any schedule produced by CCP. Proof: Suppose Ji first uses aek and Jj requests aek before the final access instant of Ji on aek. From Lemma 3.11, \Phi i(t) * OEk for tiniti (aek) ! t ^ tfini (aek). Since Jj uses aek, the priority ceiling of aek is at least as high as the priority of Jj , i.e., OEk * ssj. Therefore, \Phi i(t) * ssj for tiniti (aek) ! t ^ tfini (aek), and Jj cannot access aek at least until tfini (aek). Therefore, tfini (aek) ! tinitj (aek) must hold. Similarly, if Jj enters into the resource demand section for aek first, tfinj (aek) ! tiniti (aek) must hold. 2 Theorem 3.14 Any schedule produced by CCP is serializable. 30 Proof: Suppose the serialization graph of a schedule produced by CCP contains a cycle Jn ! J1 ! \Delta \Delta \Delta ! Jn\Gamma 1 ! Jn, where n ? 1 and Jn has the lowest priority. This means there must exist data items aex and aey such that tfinn (aex) ! tinit1 (aex) and tfinn\Gamma 1(aey) ! tinitn (aey) (3.10) from Lemma 3.13. We first show that, for any job Ji, i = 1; 2; \Delta \Delta \Delta ; n \Gamma 1, either none of its accesses to any of the data items is performed before tinitn (aex) or all of its accesses are performed before tinitn (aex). Suppose otherwise, i.e., the first access to data item aej by Ji is performed before tinitn (aex) and the last access to data item aek by Ji is performed after tinitn (aex), i.e., tiniti (aej) ! tinitn (aex) ! tfini (aek): (3.11) From Lemma 3.11, we know that \Phi i(t) * min(OEj; OEk) for tiniti (aej) ! t ^ tfini (aek). min(OEj; OEk) is greater than or equal to the priority of Jn because both aej and aek are used by other jobs in the cycle and Jn has the lowest priority among jobs in the cycle. In other words, Jn cannot access aex in the duration between tiniti (aej) and tfini (aek) since ssn is not high enough. This is a contradiction of Eq.(3.11). Using the same argument and replacing tinitn (aex) by tinitn (aey), we can show that either no access or all accesses of job Ji for i = 1; 2; \Delta \Delta \Delta ; n \Gamma 1 are performed before tinitn (aey). Since tinitn (aex) must be before tfinn (aex) and Eq.(3.10) holds, tinitn (aex) ! tfinn (aex) ! tinit1 (aex). That is, all data accesses by J1 must be after tinitn (aex). Some data accesses of Ji+1 must come after some data accesses of Ji when there is a relation Ji ! Ji+1 in the serialization graph. If all data accesses of Ji come after tinitn (aex), all data accesses of Ji+1 must be after tinitn (aex) as well. Using induction, we can conclude that all data accesses of Jn\Gamma 1 must be performed after tinitn (aex), i.e. tinitn (aex) ! tinitn\Gamma 1(aey) ! tfinn\Gamma 1(aey). Using Eq.(3.10), tinitn (aex) ! tinitn\Gamma 1(aey) ! tfinn\Gamma 1(aey) ! tinitn (aey) ! tfinn (aey): (3.12) Similarly, from tfinn\Gamma 1(aey) ! tinitn (aey), all data accesses of Jn\Gamma 1 must be performed before tinitn (aey). Continuing the same argument, we can conclude that all data accesses of J1 must be before tinitn (aey), i.e., tinit1 (aex) ! tfin1 (aex) ! tinitn (aey). From Eq.(3.10), tinitn (aex) ! tfinn (aex) ! tinit1 (aex) ! tfin1 (aex) ! tinitn (aey) ! tfinn (aey): (3.13) 31 fflHlfl pflhfl pfllfl\Phi fl lfl(fltfl) fl timefltfl bfllhfl 0fl Figure 3.6: Blocking Task However, from Lemma 3.11, \Phi n(t) * min(OEx; OEy) for tinitn (aex) ! t ^ tfinn (aey). If OEx * OEy, \Phi n(t) * OEy for tinitn (aex) ! t ^ tfinn (aey). Since aey is accessed by Jn\Gamma 1, OEy is at least as high as ssn\Gamma 1. Therefore, tinitn\Gamma 1(aey) cannot happen between tinitn (aex) and tfinn (aey), and Eq.(3.12) is not possible. If OEx ! OEy, \Phi n(t) * OEx for tinitn (aex) ! t ^ tfinn (aey). Since aex is accessed by J1, OEx is at least as high as ss1. tinitn (aex) ! tinit1 (aex) ! tfinn (aey) in Eq.(3.13) is not possible. Eq.(3.12) and Eq.(3.13) cannot be satisfied simultaneously. Therefore, no cycle can exist in the serialization graph. 2 3.4 The Schedulability Condition In real-time systems, predictable temporal behaviors of the systems are the most important system design goal. In particular, the system must satisfy all deadlines of tasks if the tasks have hard deadlines. In this section, we discuss the condition for a task set to satisfy all deadlines when the task set is scheduled with CCP. We assume the deadline of a periodic task is at the end of each period. 3.4.1 The Schedulability Condition for the RM Priority Assignment As we have proved in Theorem 3.9, Jh can be blocked by Jl if ssh ^ \Phi l(tb) and Jh itself sends the initial access notice at ta. Jl may block Jh at most for the duration during which ssh ^ \Phi l(t) holds. Let us call the duration the effective blocking unit of Jl against Jh. The effective blocking unit of Tl against Th is shown as the duration specified by filh in Figure 3.6. Since \Phi l(t) has only one peak, each lower priority job Jl has at most one effective blocking unit with length jfilhj against a higher priority job Jh. We call the set of tasks that may block jobs 32 of task Th a blocking task set of task Th, denoted by ih. Task Tl is in ih if ssl ^ ssh ^ OEHl where OEHl is the maximum priority ceiling of data items that Tl uses. Then, the worst case blocking length of Th is given by Bh = 8?!?: maxTl2ih jfi lhj; if ih 6= OE; 0; if ih = OE: A job is blocked at most once by a lower priority job when CCP is used. Therefore, when a task set T1, T2, \Delta \Delta \Delta , Tn is scheduled by CCP with the RM priority assignment, and if we know all Bis, the schedulability condition of the task set is given by iX k=1 ek pk + Bi pi ^ i(2 1=i \Gamma 1); for all i, 1 ^ i ^ n; with similar reasoning as in [SRL90]. Here ek and pk are the execution time and the period of task Tk. This condition has the same form as the condition Eq.(2.5) for PCP with the RM priority assignment. Similarly, we can use Eq.(2.6) as the schedulability condition for CCP with the RM priority assignment. In either condition, shorter worst case blocking lengths are desirable in order to utilize the processor more efficiently. As we will see in Section 3.5, CCP may shorten the worst case blocking lengths. 3.4.2 The Schedulability Condition for General Static Priority Assignment When there is no blocking, a periodic task set is feasible for all task phasings with the RM algorithm if and only if Eq.(2.2): min0!t^p i 0@ iX j=1 ej t & t pj '1A ^ 1; for all i, 1 ^ i ^ n; is satisfied. However, we claim that this condition is applicable for periodic task scheduling with any static priority assignment. Theorem 3.15 Given periodic tasks T1, T2, \Delta \Delta \Delta , Tn with fixed priorities ss1, ss2, \Delta \Delta \Delta , ssn where ss1 ? ss2 ? \Delta \Delta \Delta ? ssn, we can schedule Ti, 1 ^ i ^ n, without missing its deadline for all task phasings if and only if min0!t^p i 0@ iX j=1 ej t & t pj '1A ^ 1: (3.14) 33 Proof: Liu and Layland [LL73] prove that a task has the longest response time when a job of the task becomes active simultaneously with requests of all higher priority tasks. If the longest response time of Ti is within its period pi, Ti is schedulable. Since only higher priority jobs can preempt Ti, we only need to consider T1, T2, \Delta \Delta \Delta , Ti in order to determine the schedulability of Ti. Suppose all T1, T2, \Delta \Delta \Delta , Ti become active at time 0 and Ti completes at time t. Since a job of Ti is executing just before t, all requests by T1, T2, \Delta \Delta \Delta , Ti\Gamma 1 are completed by t. Since a job of Ti also completes at t, the total computation time by T1, T2, \Delta \Delta \Delta , Ti between time 0 and time t is iX j=1 ej & tp j ' : The total computation time is less than or equal to t. In other words, iX j=1 ej t & t pj ' ^ 1: Ti meets its deadline if and only if 0 ! t ^ pi. The theorem follows. 2 If all tasks satisfy the condition of Eq.(3.14), the task set is feasible. Corollary 3.16 Let T1, T2, \Delta \Delta \Delta , Tn be a set of tasks in descending order of fixed priorities. The task set is feasible for all task phasings if and only if min0!t^p i 0@ iX j=1 ej t & t pj '1A ^ 1; for all i, 1 ^ i ^ n: (3.15) 2 Note that the task phasings for the longest response time for all tasks coincide, i.e., a phasing which causes all tasks to experience their longest response time exists. If the worst case task phasing does not occur with a particular task phasing, a task set may be schedulable with that particular task phasing even if the task set does not satisfy Eq.(3.15). The above theorem can be extended to a schedulability condition of a task set scheduled by CCP. Theorem 3.17 Let T1, T2, \Delta \Delta \Delta , Tn be periodic tasks with fixed priorities ss1, ss2, \Delta \Delta \Delta , ssn where ss1 ? ss2 ? \Delta \Delta \Delta ? ssn. Ti has the worst case blocking length Bi. Then, CCP can schedule Ti, 34 \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma Tjfl Tifl Ti-1fl T1fl Figure 3.7: Worst Case Task Phasing for CCP 1 ^ i ^ n, without missing its deadline for all task phasings if and only if min0!t^p i 0@ iX j=1 ej t & t pj ' + Bi t 1A ^ 1: (3.16) Proof: Let Ti and Tj be two tasks. Ti has a higher priority than Tj and Tj's effective blocking unit causes the worst case blocking length of Ti. Ti's execution is preempted only by all higher priority jobs and at most one lower priority job using CCP. Therefore, we only need to consider T1, T2, \Delta \Delta \Delta , Ti, and Tj in order to determine the schedulability of Ti. Without blocking, Ti experiences the longest response time when Ti arrives simultaneously with all higher priority tasks. When there is a blocking, we only need to consider the effect of the blocking additionally. Since at most one effective blocking unit of a lower priority job is possible before the completion of a job of Ti, Ti experiences the longest response time when a job of Ti becomes active simultaneously with all higher priority tasks and Tj has just entered its effective blocking unit as shown in Figure 3.7. Suppose all T1, T2, \Delta \Delta \Delta , Ti become active at time 0 and a job of Tj enters into its effective blocking unit against Ti just before time 0. Let t be the time the job of Ti completes. Since all requests by T1, T2, \Delta \Delta \Delta , Ti\Gamma 1 must be completed before Ti, the total computation time by jobs of T1, T2, \Delta \Delta \Delta , Ti between time 0 and time t is iX j=1 ej & tp j ' : In addition, since the job of Ti needs to access data items before it can complete, the job of Tj must exit from the effective blocking unit before the job of Ti completes. The length of the effective blocking unit of Tj against Ti is Bi. Therefore, in order to complete execution of the 35 job of Ti, at most the computation time iX j=1 ej & tp j ' + Bi; is required. Since this much computation is completed at time t, the total computation time is less than or equal to t. If t is less than the period of Ti, Ti satisfies its deadline. In other words, Ti meets its deadline for all task phasings if and only if iX j=1 ej t & t pj ' + Bi t ^ 1; for some t, 0 ! t ^ pi: 2 Since a task set is feasible if all the tasks satisfy their deadlines, we have the following corollary. Corollary 3.18 Let T1, T2, \Delta \Delta \Delta , Tn be a periodic task set in descending order of fixed priorities. Ti has the worst case blocking length Bi. Then, the task set is feasible for all task phasings using CCP if and only if min0!t^p i 0@ iX j=1 ej t & t pj ' + Bi t 1A ^ 1; for all i, 1 ^ i ^ n: (3.17) 2 Note that the worst case task phasing for each task may not be the same. Suppose Ti's effective blocking unit causes the worst case blocking for Ti\Gamma 1 and Ti's worst case blocking is caused by the effective blocking unit of Tj. Then, the worst case task phasing for Ti\Gamma 1 occurs as in Figure 3.8(a). On the other hand, Ti's worst case task phasing occurs as in Figure 3.8(b). These two situations cannot occur simultaneously. Therefore, a task phasing which causes all tasks to experience their worst case blocking does not exist for a task set in general. By satisfying Eq.(3.17), all tasks are schedulable for all task phasings even if the worst case task phasing exists. However, if the worst case task phasing does not exist for a task set or the task set is executed in a certain task phasing in which the worst case task phasing does not occur, the task set may be schedulable without satisfying Eq.(3.17). We can similarly prove that Eq.(3.17) is the schedulability condition for PCP. 36 \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma Tjfl Tifl Ti-1fl T1fl \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma Tifl Ti-1fl T1fl (b) Worst Case for Tifl (a) Worst Case for Ti-1fl Figure 3.8: Worst Case Task Phasing 3.5 Comparison with PCP+2PL PCP has no-deadlock and single-blocking properties. Since it cannot guarantee serializability, we can combine it with 2PL. In this section, we compare the performance of CCP with the combination of 2PL and PCP. PCP assumes that critical sections are properly nested. However, we can prove that no-deadlock and single-blocking properties still hold in PCP without that assumption if we consider one continuous blocking by one lower priority job as a single blocking. For example, in Figure 3.9, job Jj uses three data items, ae1, ae2, and ae3, and their critical sections 1234567812345678123456789012345678901234561234567890123456789012345612345678901234567890123456 12345678901234567890123456 123456789012123456789012 1234512345 123123 1234567812345678 1234567812345678r1 r3 r2 Jj bji Figure 3.9: Overlapped Critical Sections 37 are overlapped. If ae2 and ae3 have higher priority ceilings than the priority of a job Ji, Jj may block Ji for the duration specified as fiji if PCP is used. For our discussion, we consider blockings of Ti in fiji as one blocking. The proof for the no-deadlock and the single-blocking properties is similar to the one in [CL90]. In this section, we assume jobs do not have properly nested critical sections. Example 3 Figure 3.10 (a) is the same task set as we used previously. The shaded rectangles in the figure are resource demand sections, i.e., at least the shaded part of the execution must be protected by locks if a locking mechanism is used. Figure 3.10 (b) shows the critical sections defined by the combination of 2PL and PCP and effective blocking units defined by CCP. Note that ae1 and ae2 are unlocked only after locking ae3 by 2PL. With the combination algorithm, the worst case blocking lengths of T1 and T2 are both 7 time units. In the worst case, T1 and T2 may be blocked after T3 finishes 1 time unit of execution until T3 finishes 8 time units of execution. For CCP, the worst case blocking lengths of T1 and T2 are 2 time units and 5 time units respectively. This is because T1 may be blocked after T3 finishes 1 time unit of execution until T3 completes 3 time units of execution, while T2 may be blocked after T3 completes 1 time unit of execution until T3 finishes 6 time units of execution. CCP provides shorter worst case blocking and, consequently, a better schedulability condition. Schedules for both algorithms are shown in Figure 3.11 assuming T3 arrives at time 0 and both T1 and T2 arrive at time 2. With the combination algorithm, the first job J1 of the highest priority task T1 is blocked by job J3 of low priority task T3 from time 3 to 9 and J1 misses its deadline. This blocking is shortened using CCP so that J1 meets the deadline. 2 According to 2PL, a job can request locks whenever they are necessary. On the other hand, the job cannot release locks until all locks are acquired. Assume a job accesses a data item with a high priority ceiling early in the execution of the job and does not access it later. Then, the data item with a high priority ceiling is locked early in the execution and the job must hold the lock unnecessarily until all necessary locks are acquired. CCP alleviates this problem. With CCP, a job can request a data access whenever it is necessary, as with 2PL. However, CCP allows other jobs with higher priorities to use some data items even before the rest of the data items are completely locked by the job. CCP allows more flexible scheduling and achieves a higher processor utilization. 38 1234512345 1234512345 12345 12345671234567 1234567812345678 1234567812345678 123123 123 T1 T2 T3 12341234 12341234 1234 123123 123 1234567812345678 1234567812345678 1234567812345678 1234567812345678 r1 r2 r3 0 2 4 6 1234567890123456789012345612345678901234567890123456 12345678901234567890123456 1234567812345678 1234567812345678 1234567812345678 1234567812345678 1234567812345678 1234567812345678 1234567812345678 12345678T3 T3 2PL +PCP CCP (a) Task Set Blocking Length (b) resource demand sections time t 1234512345 8 p1 p3 p1 p2 (critical sections) p3 10 T3 R3(t) ^ \Phi 3(t) Figure 3.10: Example 3 1234512345 1234512345 12345 12345671234567 T1 T2 T3 0 2 4 6 1234567890123456789012312345678901234567890123 12345678901234567890123 8 10 12 T1 T2 T3 0 2 4 6 8 10 12 14 14 (a) 2PL+PCP (b) CCP time time 12341234 1234 16 16 p1 p1 p2 p1 p2 p1 1234512345 1234512345 18 20 12341234 12341234 p1 18 20 1234512345 1234512345 p1 12345671234567 22 22 p3 critical section effective blocking unit p3 missed deadline 1234567812345678 1234567812345678 1234567812345678 1234567812345678 Figure 3.11: Schedule (Example 3) 39 \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma Resouce DemandflSectionfl Critical Sectionfl modifyflT 3fl \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma r2fl f2= p2fl \Gamma \Gamma \Gamma \Gamma r3fl f3= p3fl \Gamma \Gamma f1= p1flr1fl p1fl p2fl p3flp3flp1fl0fl 0fl 0fl 0flR3(t)fl^fl Figure 3.12: Minimum Blocking Lock Request In fact, the combination of 2PL and PCP can achieve the same worst case blocking as CCP if we are allowed to modify the resource demand sections, i.e., the times that lock operations and unlock operations are requested. For example, if we modify the resource demand sections of T3 in Example 3 as shown in Figure 3.12, the worst case blocking lengths of T1 and T2 will be the same as the worst case blocking lengths by CCP shown in Figure 3.10. However, in some real-time systems with mode change, database systems may require dynamic change of their task sets and periods of the tasks. For example, in an air traffic control system, we may be required to shorten the tracking period of an airplane as the airplane is approaching an airport. In a space shuttle, the set of tasks running in the landing process should be different from the set of tasks running while the shuttle is traveling in space. If we use the combination of 2PL and PCP and reduce the worst case blocking length by changing the placement of lock requests and unlock requests, the programs must be modified or different versions of the programs must be used in order to shorten the worst case blocking when the systems change their task sets. CCP can alleviate this difficulty. If a scheduler is given a list of data items that each task accesses and the order of the initial access and final access notices, the scheduler can dynamically construct the priority ceiling function for each task. Based on the priority ceiling functions, the system can use CCP. In this way, CCP can adapt to the dynamic change of the task set and still produce shorter worst case blocking lengths than the combination of 2PL and PCP. 40 Chapter 4 Optimization and Extension of CCP In CCP, tasks have fixed priorities. There are many ways the priorities can be assigned to tasks. Some of them will make the tasks more schedulable. In this chapter, we prove that the RM priority assignment is optimal among static priority assignments. Also, we extend CCP to handle access types on data items such as "read" and "write" in this chapter. 4.1 Optimality of the RM Priority Assignment Liu and Layland [LL73] have proved that the RM priority assignment is optimal among static priority assignments when there are no shared data. The optimality is in the sense that a task set that is not feasible with the RM priority assignment cannot be feasible with any other static priority assignment. In this section, we prove that the RM priority assignment is also optimal when there are shared data and CCP is used. When there are no shared data, we can easily see the optimality from Theorem 3.15. Let T1, T2, \Delta \Delta \Delta , Tn be a feasible task set for all task phasings with priorities ss1, ss2, \Delta \Delta \Delta , ssn where ss1 ? ss2 ? \Delta \Delta \Delta ? ssn. Suppose pi ? pi+1, i.e., Ti and Ti+1 do not follow the RM priority assignment. Since Ti+1 is schedulable for all task phasings, the following condition must hold: min0!t^p i+1 0@ i+1X j=1 ej t & t pj '1A ^ 1: (4.1) Suppose we exchange the priorities of Ti and Ti+1 so that the priority assignment is RM. We must prove that min0!t^p i 0@ i+1X j=1 ej t & t pj '1A ^ 1 (4.2) is satisfied if Ti is to be schedulable for all task phasings after the priority exchange. Since a value derived by taking the minimum over a shorter interval (0; pi+1] is greater than or equal to the minimum value over a longer interval (0; pi] as shown in Figure 4.1, we know, min0!t^p i 0@ i+1X j=1 ej t & t pj '1A ^ min0!t^pi+1 0@ i+1X j=1 ej t & t pj '1A : (4.3) 41 pi+1fl pifl0fl val uefl durationfl Figure 4.1: Minimum Value Function From Eq.(4.1) and (4.3), Eq.(4.2) holds. If condition min0!t^p i+1 0@ i\Gamma 1X j=1 ej t & t pj ' + ei+1 t , t pi+1 ss1A ^ 1 (4.4) is satisfied, Ti+1 is schedulable for all task phasings after the priority exchange. Eq.(4.4) holds because min0!t^p i+1 0@ i\Gamma 1X j=1 ej t & t pj ' + ei+1 t , t pi+1 ss1A ^ min0!t^pi+1 0@ i+1X j=1 ej t & t pj '1A : The schedulability condition of task Tk, k 6= i; i + 1, does not change before and after the priority exchange. Since Tk is schedulable before the priority exchange, it is also schedulable after the exchange. Therefore, all tasks are schedulable after the priority exchange, i.e., the task set is schedulable with the RM priority assignment. However, the optimality of the RM priority assignment is not obvious when blockings caused by CCP exist. When there are blockings, schedulability conditions of Ti and Ti+1 become as follows: min0!t^p i 0@ iX j=1 ej t & t pj ' + Bi t 1A ^ 1 and min0!t^pi+1 0@ i+1X j=1 ej t & t pj ' + Bi+1 t 1A ^ 1: Exchanging priorities of Ti and Ti+1 changes Bi and Bi+1 to B0i and B0i+1. Hence, it is not obvious if schedulability conditions of Ti and Ti+1 after exchanging the priorities can be satisfied without further investigation on how exchanging priorities affects the value of Bi in general. For the rest of this section, we investigate how priority exchange may affect Bi, and thus the schedulability condition. 42 4.1.1 Worst Case Blocking Lengths of CCP Let Ri be the set of data items that Ti accesses. Let RUi be the set of data items accessed by tasks whose priorities are higher than or equal to task Ti and RLi be the set of data items accessed by lower priority tasks than Ti. Thus, Ri `RUi . We call RUi and RLi the upper resource set and the lower resource set of Ti, respectively. Let RBi be the blocking resource set of Ti which is the set of data items that may cause jobs of Ti to be blocked. In other words, RBi is the set of data items that are accessed by lower priority tasks than Ti and have priority ceilings higher than or equal to the priority of Ti. Thus, RBi = RUi " RLi : For example, suppose T1, T2, and T3 are three tasks with priorities ss1 ? ss2 ? ss3. T1 uses data item ae1, T2 uses ae2 and ae3, and T3 uses ae3. Then, RU1 = fae1g, RL1 = fae2; ae3g, RB1 = OE, RU2 = fae1; ae2; ae3g, RL2 = fae3g, RB2 = fae3g, RU3 = fae1; ae2; ae3g, RL3 = OE, and RB3 = OE. Using RBi , we can define the blocking task set as follows: the blocking task set ii of Ti is a set of lower priority tasks that use data items in RBi . Let T Li be the set of tasks whose priorities are lower than Ti's. Then, ii = fTkjTk is in T Li and accesses aej 2 RBi g = fTkjTk is in T Li and accesses aej 2 (RUi " RLi )g (4.5) Since aej is in RLi if aej is accessed by Tk 2 T Li , we can rewrite Eq.(4.5) as follows: ii = fTkjTk is in T Li and accesses aej 2 RUi g: (4.6) Lemma 4.1 The effective blocking unit fiji of Tj 2 ii against Ti depends only on RUi and the resource demand sections of Tj. fiji depends on neither Ti's resource demand sections nor Ri. Proof: From the definition of the effective blocking unit, fiji is defined by the duration that \Phi j(t) * ssi. From the definition of \Phi j(t), the beginning of fiji is defined by the first initial access instant on all data items in RUi and the end of fiji is defined by the last final access instant on all data items in RUi . Therefore, fiji is defined only by RUi and the resource demand sections of Tj. Ti's resource demand sections have nothing to do with fiji. Ri may affect fiji since Ri `RUi . However, as long as RUi has the same elements, fiji does not change even if the elements of Ri change. 2 43 Lemma 4.2 Let T1, T2, \Delta \Delta \Delta , Tn be tasks in descending order of priorities and T1 have the highest priority. If Tj is in both ii and ii+1, then jfijij ^ jfij(i+1)j: Proof: From Lemma 4.1, given a task Tj 2 ik, jfijkj depends only on RUk and the resource demand sections of Tj. Since RUi+1 = RUi [ Ri+1 ' RUi from the definition of RUi , the set of resource demand sections of Tj for data items in RUi+1 contains the resource demand sections for data items in RUi . This means that the duration in which \Phi j (t) is greater than or equal to ssi+1 is not shorter than the duration in which \Phi j(t) is greater than or equal to ssi, i.e., jfijij ^ jfij(i+1)j. 2 Lemma 4.3 Let T1, T2, \Delta \Delta \Delta , Tn be tasks in descending order of fixed priorities. If the worst case blocking lengths Bi and Bi+1 of tasks Ti and Ti+1 have a relation Bi ? Bi+1, then Bi = jfi(i+1)ij. Proof: Since T Li = T Li+1 [ fTi+1g, ii can be decomposed as ii = fTkjTk is in T Li and accesses aej 2 RUi g = fTkjTk is in T Li+1 and accesses aej 2 RUi g [ fTkjTk = Ti+1 and accesses aej 2 RUi g: Since RUi+1 = RUi [ Ri+1, ii+1 can be decomposed as ii+1 = fTkjTk is in T Li+1 and accesses aej 2 RUi+1g = fTkjTk is in T Li+1 and accesses aej 2 RUi g [fTkjTk is in T Li+1 and accesses aej 2 Ri+1g: Let iC, i0, and i00 be the sets fTkjTk is in T Li+1 and accesses aej 2 RUi g, fTkjTk = Ti+1 and accesses aej 2 RUi g, and fTkjTk is in T Li+1 and accesses aej 2 Ri+1g, respectively. Then, the worst case blocking length of Ti is Bi = 8??!??: maxTj2ii jfi jij = max maxT j2iC jfijij, maxTj2i0 jfijij! ; if ii 6= OE; 0; if ii = OE: 44 Also, the worst case blocking length of Ti+1 is Bi+1 = 8??!??: maxTj2ii+1 jfi j(i+1)j = max maxT j2iC jfij(i+1)j, maxTj2i00 jfij(i+1)j! ; if ii+1 6= OE; 0; if ii+1 = OE: Since iC ` ii and iC ` ii+1, Tj 2 iC is in both ii and ii+1. From Lemma 4.2, jfijij ^ jfij(i+1)j. Since maxT j2iC jfijij and maxTj2iC jfij(i+1)j are taking the maximum over the same set of tasks, max Tj2iC jfijij ^ maxTj2iC jfij(i+1)j: Case 1: Suppose ii+1 = OE. Then, Bi must be equal to maxT j2i0 jfijij and i 0 6= OE in order to have Bi ? Bi+1 since iC = OE. Case 2: Suppose Bi+1 = max Tj2iC jfij(i+1)j. Since Bi ? Bi+1 = max Tj2iC jfij(i+1)j * maxTj2iC jfijij; Bi must be equal to maxT j2i0 jfijij and i 0 6= OE. Case 3: Suppose Bi+1 = maxT j2i00 jfij(i+1)j. Then, maxTj2iC jfij(i+1)j ^ maxTj2i00 jfij(i+1)j. Since maxT j2iC jfijij ^ maxTj2iC jfij(i+1)j ^ maxTj2i00 jfij(i+1)j = Bi+1; Bi must be equal to maxT j2i0 jfijij and i 0 6= OE in order to have Bi ? Bi+1. In all cases, Bi must be equal to maxT j2i0 jfijij and i 0 cannot be empty. Therefore, i0 must be fTi+1g and Bi = jfi(i+1)ij. 2 4.1.2 Optimality of the RM Priority Assignment in CCP Lemma 4.4 Let T1, T2, \Delta \Delta \Delta , Tn be tasks in descending order of fixed priorities and Ti and Ti+1 be two tasks among them. Suppose we exchange the priorities of Ti and Ti+1. Using CCP, the worst case blocking length Bi+1 of Ti+1 before exchanging priorities is equal to the worst case blocking length B0i of Ti after the priority exchange. Proof: RUi+1 is the upper resource set of Ti+1. Ti has a lower priority than Ti+1 after exchanging priorities of the two tasks. Let RU0i be the upper resource set of Ti after exchanging the priorities. Since RUi+1 includes data items used by both Ti+1 and Ti, it contains the same data items as RU0i . Also, the set T Li+1 of tasks with lower priorities than Ti+1 before the priority exchange is equal 45 to the set T L0i of tasks with lower priorities than Ti after the priority exchange. Therefore, the blocking task set ii+1 of Ti+1 before the priority exchange is equal to the blocking task set i0i of Ti after the priority exchange: ii+1 = fTkjTk is in T Li+1 and accesses aej 2 RUi+1g = fTkjTk is in T L0i and accesses aej 2 RU0i g = i0i: From Lemma 4.1, jfij(i+1)j for all Tj 2 ii+1 only depends on RUi+1 and the resource demand sections of Tj. Similarly, jfi0jij for all Tj 2 i0i only depends on RU0i and the resource demand sections of Tj where fi0ji is the effective blocking unit of Tj against Ti after the priority exchange. Since RUi+1 = RU0i , jfij(i+1)j = jfi0jij for all Tj 2 ii+1 = i0i. Therefore, Bi+1 = maxT j2ii+1 jfij(i+1)j = maxTj2i0i jfi 0jij = B0i: 2 Theorem 4.5 Let T1, T2, \Delta \Delta \Delta , Tn be a periodic task set in descending order of priorities. The task set can be feasibly scheduled using CCP for all task phasings. Suppose Ti for some i, 1 ^ i ! n, has a longer period than Ti+1, i.e., pi ? pi+1. This task set is still feasible using CCP after exchanging the priorities of Ti and Ti+1. Proof: Since Ti+1 is schedulable for all task phasings before the priority exchange, min0!t^p i+1 0@ i+1X j=1 ej t & t pj ' + Bi+1 t 1A ^ 1 (4.7) from Theorem 3.17. After exchanging the priorities of Ti and Ti+1, if both min0!t^p i 0@ i+1X j=1 ej t & t pj ' + B0i t 1A ^ 1, and (4.8) min0!t^p i+1 0@ i\Gamma 1X j=1 ej t & t pj ' + ei+1 t , t pi+1 ss + B0i+1 t 1A ^ 1 (4.9) are satisfied, both Ti and Ti+1 are schedulable. Here, B0i and B0i+1 are the worst case blocking lengths of Ti and Ti+1 after the priority exchange. 46 From Lemma 4.4, Bi+1 = B0i. Therefore, min0!t^p i 0@ i+1X j=1 ej t & t pj ' + B0i t 1A = min0!t^pi 0@ i+1X j=1 ej t & t pj ' + Bi+1 t 1A : (4.10) Since pi ? pi+1, a value derived by taking minimum over the interval 0 ! t ^ pi+1 is greater than or equal to a value derived by taking minimum over the interval 0 ! t ^ pi, i.e., min0!t^p i 0@ i+1X j=1 ej t & t pj ' + Bi+1 t 1A ^ min0!t^pi+1 0@ i+1X j=1 ej t & t pj ' + Bi+1 t 1A : (4.11) From Eq.(4.7), (4.10), and (4.11), min0!t^p i 0@ i+1X j=1 ej t & t pj ' + B0i t 1A ^ 1; i.e., Eq.(4.8) holds. By comparing Eq.(4.7) and (4.9), if ei t , t pi ss + Bi+1 t * B0i+1 t (4.12) is satisfied, Eq.(4.9) holds. Suppose B0i+1 ^ B0i. Then, B0i+1 ^ Bi+1 from Lemma 4.4. Therefore, B0i+1 t ^ Bi+1 t ! ei t , t pi ss + Bi+1 t : Eq.(4.12) holds. Suppose B0i+1 ? B0i. From Lemma 4.3, Ti's effective blocking unit against Ti+1 defines B0i+1, i.e., B0i+1 = jfi0i(i+1)j where fi0i(i+1) is the effective blocking unit of Ti against Ti+1 after the priority exchange. Since the effective blocking unit of Ti must be less than or equal to the execution time of Ti, ei * jfi0i(i+1)j = B0i+1. Therefore, B0i+1 t ^ ei t ! ei t , t pi ss + Bi+1 t : Eq.(4.12) holds. Therefore, both Eq.(4.8) and (4.9) are satisfied. Both Ti and Ti+1 are schedulable after the priority exchange. Since task Tk, k 6= i; i + 1, is schedulable before the priority exchange, min0!t^p k 0@ kX j=1 ej t & t pj ' + Bk t 1A ^ 1 (4.13) 47 is satisfied. Let B0k and i0k be the worst case blocking length and the blocking task set of Tk after the priority exchange, respectively. Since T Lk and RUk do not change after the priority exchange, i0k = fTxjTx is in T L0k and accesses aey 2 RU0k g = fTxjTx is in T Lk and accesses aey 2 RUk g = ik where T L0k is the set of tasks whose priorities are lower than Tk and RU0k is the upper resource set of Tk after the priority exchange. jfijkj only depends on Tj and RUk and jfi0jkj only depends on Tj and RU0k . Since RU0k = RUk , jfi0jkj = jfijkj for all Tj 2 i0k = ik. Therefore, B0k = maxT j2i0k jfi 0jkj = max Tj2ik jfijkj = Bk: Tk is schedulable after the priority exchange because min0!t^p k 0@ kX j=1 ej t & t pj ' + B0k t 1A = min0!t^pk 0@ kX j=1 ej t & t pj ' + Bk t 1A ^ 1: (4.14) Since Eq.(4.8) and (4.9) are satisfied and Eq.(4.14) holds, the task set is feasible after the priority exchange. 2 Theorem 4.5 tells us that if a task set is feasible with a certain static priority assignment, the task set is also feasible after exchanging priorities which do not follow the RM priority assignment. Therefore, the RM priority assignment is optimal among static priority assignments when CCP is used. A similar argument is also applicable to PCP. 4.2 Type-Specific CCP In database systems, read accesses and write accesses may be distinguished in order to increase concurrency. A read access to a data item does not conflict with other read accesses to the same data item. On the other hand, a write access conflicts with both read and write accesses. If two tasks only access data items with the read access type, they can be freely interleaved without a serializability violation. In general, a data item can be accessed by several different access types. For example, a data item may be accessed by write, read, or increment type. The 48 Table 4.1: Compatibility Matrix Read Write Increment Read y n n Write n n n Increment n n y conflict of access types can be described by a compatibility matrix. Table 4.1 shows an example of the compatibility matrix. In this chapter, we describe an extension of CCP for a system that has several access types for data accesses. We assume in this section that all tasks are periodic and are assigned fixed priorities. 4.2.1 Algorithm We define a demand class as a class of data accesses on the same data item with the same access type. It serves as a handle for concurrency control since we need to know both the data item and the access type in order to decide if an access is in conflict with another access. A demand class can be expressed as a pair (data item identifier, access type). (ae1, write) expresses a demand class that accesses data item ae1 with write access type. Also, we use Di to specify i-th demand class. A demand class (aex, Ax) conflicts with another demand class (aey, Ay) if aex is the same data item as aey and the access types Ax and Ay conflict. We define the initial and the final access instants of a job for each demand class. A resource demand section is the duration between an initial access instant and the corresponding final access instant. The resource demand sections are classified into the demand classes. For each demand class, we define a priority ceiling as follows: Definition: The priority ceiling OEi of a demand class Di is defined by the maximum priority of tasks that have resource demand sections in conflict with Di. 2 For example, a task set in Figure 4.2 has three tasks and T1 has the highest priority and T3 has the lowest priority. Each task has resource demand sections as shown in the figure. Suppose the compatibility matrix in Table 4.1 is applicable among the access types. Demand class Da which accesses data item ae1 with "read" access type only conflicts with demand class Db which accesses ae1 with "write" access type. Since T3 has the highest priority among tasks 49 \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma Da: (r1, read)fl Db: (r1, write)fl Dc: (r2, read)fl Dd: (r2, write)fl De: (r3, read)fl T1fl T2fl T3fl 0fl 2fl 4fl 6fl timefl fa=p3fl fb=p1fl fc=p1fl fd=p1fl fe=0fl resourcefldemandfl sectionfl Figure 4.2: Example Task Set with resource demand sections of Db, the priority ceiling of Da is ss3. Db conflicts with both Da and Db itself. Since T1 has the highest priority among tasks with resource demand sections of Da and Db, the priority ceiling of Db is ss1. The priority ceilings of Dc, Dd, and De are ss1, ss1, and 0 respectively. We call the convex ceiling protocol which differentiates access types the type-specific convex ceiling protocol (TCCP). Based on the definition of priority ceilings given above, we can define the maximum remainder priority in a similar way to CCP as follows: Definition: The maximum remainder priority \Omega i(t) of task Ti is the maximum priority ceiling of all demand classes of which task Ti has resource demand sections after time t. 2 Let tiniti (Dj) and tfini (Dj) be the initial and the final access instants of Ji on Dj. Then, the priority ceiling function of a task Ti for TCCP is defined as follows. Priority Ceiling Function of TCCP: \Phi i(t) (\Phi 1) When a job of task Ti starts execution, \Phi i(t) = 0. (\Phi 2) At t = tiniti (Dj), if \Phi i(t) is less than the priority ceiling of Dj, \Phi i(t) is set to the priority ceiling of Dj. (\Phi 3) At t = tfini (Dj), if \Phi i(t) ? \Omega i(t), \Phi i(t) is set to \Omega i(t). 2 For example, the maximum remainder priority and the priority ceiling function of T3 in Figure 4.2 are as shown in Figure 4.3. We can prove that \Phi i(t) has at most one peak in the same way as in Theorem 3.1. We use CT CCPi (t) to express the maximum \Phi j(t) of all job Jjs in the system except Ji itself. We can define TCCP as follows. 50 12341234 1234 123456123456 123456123456 123456123456T3 1234567812345678 1234567812345678 12345678 p1 p2 p3 \Omega 3(t) time t 0 12341234 1234 123456123456 123456 Da Db 12341234De fa=p3 fb=p1 fe= 0 0 2 4 6 12341234 1234 123456123456 123456123456 123456123456T3 1234567812345678 1234567812345678 12345678 p1 p2 p3 \Phi 3(t) time t 0 0 2 4 6 Maximum Remainder Priority Priority Ceiling Function Figure 4.3: Maximum Remainder Priority and Priority Ceiling Function Type-Specific Convex Ceiling Protocol (TCCP) 1. (Scheduling Algorithm) A static priority assignment priority-driven algorithm. 2. (Concurrency Control Algorithm) When a job Ji requests the first data access to a data item, (a) if Ji's original priority ssi is higher than CT CCPi (t), Ji is allowed to proceed to the initial access instant on the data item. (b) Otherwise, Ji is suspended until ssi ? CT CCPi (t) is satisfied. 3. (Interaction Protocol) If Ji is suspended, the augmented priority ss\Lambda i of Ji is assigned to job Jk that has the maximum \Phi k(t). 2 With TCCP, the example task set in Figure 4.2 may be scheduled as in Figure 4.4. T3 becomes active at time 0, and enters into a resource demand section of Da at time 1. At time 2, T2 becomes active and preempts T1. At time 3, T2 requests to enter a resource demand section of Dc. Since C2(3) is ss3, T2 enters into the resource demand section. At time 4, T1 becomes active and preempts T2. T1 requests to enter a resource demand section of Dc at time 5, but since C1(5) = ss1, it is blocked. T2 resumes execution and exits from the resource demand section of Dc at time 6. Now, C1(6) = ss3 and T1 resumes execution. T1 enters into its resource demand section of Dc at time 6. T1 also requests to enter into a resource demand section of Da 51 12341234 12341234 1234 123123 123 123123 123 123123 123 1234512345 1234512345 123456789123456789 123456789123456789 123456789123456789 123456789123456789 1234567812345678 12345678 123456123456 123456123456 123456123456 123456123456 1234512345 1234512345 12345 123123 123123 0 2 4 6 8 10 12 14 16 18 time T1 T3 T2 1234512345 12345Da: (r1,read) 123456123456 123456Db: (r1,write) 123123Dc: (r2,read) 1234567812345678 1234567812345678 12345678Dd: (r2,write) 12341234De: (r3,read) Figure 4.4: Example Schedule of TCCP at time 7. Although T3 is in the resource demand section of Da, i.e., T3 is using resource ae1 in "read" access type, T1 is allowed to "read" as well. 4.2.2 Properties of TCCP We can prove the no-deadlock and the single-blocking properties of TCCP in the same way as in Chapter 3. Also, the schedulability condition for CCP is applicable for TCCP. The only difference in the schedulability condition is the length of the worst case blocking. In the rest of this section, we prove the serializability property of TCCP with a similar proof strategy to the one for CCP. Lemma 4.6 Let Dx and Dy be any demand classes that Ji has resource demand sections of. If we assume tiniti (Dx) ! tfini (Dy), it must be true that \Phi i(t) * min(OEx; OEy) for tiniti (Dx) ! t ^ tfini (Dy) in any schedule produced by TCCP. Proof: From the definition of \Phi i(t), \Phi i(t) is at least as high as OEx at time t just after tiniti (Dx) and is at least as high as OEy at t = tfini (Dy). Since \Phi i(t) has only one peak, the lemma holds. 2 Lemma 4.7 If job Ji has a resource demand section of demand class Dx, job Jj has a resource demand section of demand class Dy, and Dx and Dy conflict, we must have either tfini (Dx) ! tinitj (Dy) or tfinj (Dy) ! tiniti (Dx) in any schedule produced by TCCP. 52 Proof: Suppose Jj requests to enter into the resource demand section of demand class Dy after Ji enters into the resource demand section of demand class Dx but before the final access instant of Ji on Dx. From Lemma 4.6, \Phi i(t) * OEx for tiniti (Dx) ! t ^ tfini (Dx). Since Jj has a resource demand section of demand class Dy which conflicts with Dx, the priority ceiling of Dx is at least as high as the priority of Jj , i.e., OEx * ssj. Therefore, \Phi i(t) * ssj for tiniti (Dx) ! t ^ tfini (Dx), and Jj cannot enter the resource demand section of Dy in the duration. Therefore, tfini (Dx) ! tinitj (Dy) must hold. Similarly, if Jj enters the resource demand section of demand class Dy first, tfinj (Dy) ! tiniti (Dx) must hold. 2 Theorem 4.8 Any schedule produced by TCCP is serializable. Proof: Suppose the serialization graph contains a cycle Jn ! J1 ! \Delta \Delta \Delta ! Jn\Gamma 1 ! Jn where n ? 1 and Jn has the lowest priority. It means that Jn has a resource demand section of demand class Da, J1 has a resource demand section of demand class Db, and Da and Db conflict. Also, Jn\Gamma 1 has a resource demand section of demand class Dc, Jn has a resource demand section of demand class Dd, and Dc and Dd conflict. From Lemma 4.7, accesses on those resource demand sections have the following precedence: tfinn (Da) ! tinit1 (Db) and tfinn\Gamma 1(Dc) ! tinitn (Dd): (4.15) We first show that either none or all of the resource demand sections in each job Ji, i = 1; 2; \Delta \Delta \Delta ; n \Gamma 1 that conflict with other resource demand sections in job Jj , j = 1; 2; \Delta \Delta \Delta ; n and j 6= i, must be before tinitn (Da). Suppose otherwise. A job Ji, i = 1; 2; \Delta \Delta \Delta ; n \Gamma 1, has two resource demand sections that conflict with other resource demand sections in job Ji, j = 1; 2; \Delta \Delta \Delta ; n and j 6= i. One of them starts before tinitn (Da) and belongs to demand class Dx. The other ends after tinitn (Da) and belongs to demand class Dy. Then, tiniti (Dx) ! tinitn (Da) ! tfini (Dy): (4.16) Since both Dx and Dy conflict with resource demand sections in job Jj, j = 1; 2; \Delta \Delta \Delta ; n and j 6= i, and Jn has the lowest priority, min(OEx; OEy) * ssn. Therefore, \Phi i(t) * ssn for tiniti (Dx) ! t ^ tfini (Dy) from Lemma 4.6. In other words, Jn cannot enter the resource demand section of Da after tiniti (Dx) and before tfini (Dy) since ssn is not high enough. This is a contradiction to Eq.(4.16). 53 Using the same argument and replacing tinitn (Da) by tinitn (Dd), we can show that either no or all resource demand sections of each job Ji, i = 1; 2; \Delta \Delta \Delta ; n \Gamma 1, that conflict with other resource demand sections in job Jj , j = 1; 2; \Delta \Delta \Delta ; n and j 6= i, must be before tinitn (Dd). From Eq.(4.15), we know that tinitn (Da) ! tfinn (Da) ! tinit1 (Db). That is, all resource demand sections in J1 that conflict with other resource demand sections in Jj, i = 2; 3; \Delta \Delta \Delta ; n must be after tinitn (Da). A resource demand section of Ji+1 that conflicts with a resource demand section of job Ji must come after the resource demand section of Ji when there is a relation Ji ! Ji+1 in the serialization graph. If all resource demand sections of Ji that conflict with resource demand sections of job Jj , j = 1; 2; \Delta \Delta \Delta ; n and i 6= j, come after tinitn (Da), all resource demand sections of Ji+1 that conflict with resource demand sections of job Jj , j = 1; 2; \Delta \Delta \Delta ; n and j 6= i + 1, must be after tinitn (Da) as well. Using induction, we can conclude that all resource demand sections of Jn\Gamma 1 that conflict with resource demand sections of job Jj, j = 1; 2; \Delta \Delta \Delta ; n \Gamma 2; n must be after tinitn (Da), i.e. tinitn (Da) ! tinitn\Gamma 1(Dc) ! tfinn\Gamma 1(Dc). Using Eq.(4.15), tinitn (Da) ! tinitn\Gamma 1(Dc) ! tfinn\Gamma 1(Dc) ! tinitn (Dd) ! tfinn (Dd): (4.17) Similarly, from tfinn\Gamma 1(Dc) ! tinitn (Dd), all resource demand sections of Jn\Gamma 1 that conflict with resource demand sections of job Jj , j = 1; 2; \Delta \Delta \Delta ; n \Gamma 2; n, must be before tinitn (Dd). Continuing the same argument, we can conclude that all resource demand sections of J1 that conflict with resource demand sections of job Jj, j = 2; 3; \Delta \Delta \Delta ; n, must be before tinitn (Dd), i.e., tinit1 (Db) ! tfin1 (Db) ! tinitn (Dd). From Eq.(4.15), tinitn (Da) ! tfinn (Da) ! tinit1 (Db) ! tfin1 (Db) ! tinitn (Dd) ! tfinn (Dd): (4.18) However, from Lemma 4.6, \Phi n(t) * min(OEa; OEd) for tinitn (Da) ! t ^ tfinn (Dd). Suppose OEa * OEd. Dd conflicts with Dc. Since Jn\Gamma 1 has a resource demand section of Dc, OEd * ssn\Gamma 1. Therefore, \Phi n(t) * ssn\Gamma 1 for tinitn (Da) ! t ^ tfinn (Dd). Eq.(4.17) is not possible since tinitn\Gamma 1(Dc) cannot happen between tinitn (Da) and tfinn (Dd). Suppose OEa ! OEd. Since Da conflicts with Db and J1 has a resource demand section of Db, OEa * ss1. Therefore, \Phi n(t) * ss1 for tinitn (Da) ! t ^ tfinn (Dd). Then, Eq.(4.18) is not possible since tinit1 (Db) cannot happen between tinitn (Da) and tfinn (Dd). Eq.(4.17) and (4.18) cannot be satisfied simultaneously. Therefore, no cycle can exist in the serialization graph. 2 54 Chapter 5 Dynamic Priority Convex Ceiling Protocol CCP as defined in Chapter 3 uses static priority assignment for scheduling. However, dynamic priority assignment schemes may achieve higher processor utilization without missing deadlines. In this chapter, we extend CCP in order to use a dynamic priority scheduling algorithm, the EDF algorithm. Also, we include aperiodic tasks into consideration in this algorithm. 5.1 Algorithm The EDF algorithm assigns priorities to jobs according to their deadlines. A job with an earlier deadline is assigned a higher priority. Hence, jobs from the same periodic task have different priorities. For aperiodic tasks, we do not know their ready times and deadlines, and consequently priorities, before the arrival of the tasks. Therefore, we cannot assign priority ceilings to data items statically. This dynamically changing priority ceiling imposes difficulties on CCP. For example, suppose a new job Jj becomes active while job Ji is accessing data item aek. If Jj also uses aek and Jj has an earlier deadline, the priority ceiling of aek, and consequently \Phi i(t), suddenly increases to Jj 's priority. Also, every time a higher priority job arrives, priority ceilings, maximum remainder priorities, and priority ceiling functions must be re-calculated. However, as pointed out by Chen and Lin [CL90] and by Baker [Bak90], a job can be blocked only by jobs with longer relative deadlines when EDF is used. In general, we may know the relative deadlines of all tasks from the system specification even though we may not know exactly when jobs become active. In this chapter, we assume all jobs of a task have the same relative deadlines. By using the relative deadlines to define the priority ceilings, and consequently the maximum remainder priorities and the priority ceiling functions, we can modify CCP to accommodate EDF. A task with a shorter relative deadline is assigned a higher preemption level. The concept of preemption level was proposed in [Bak90]. We express the preemption level of task Ti by *i. 55 A task Ti with a shorter relative deadline is assigned a higher preemption level *i. We use positive numbers as the preemption levels, i.e., *i ? 0 for all i. All jobs of a task have the same preemption level. The priority ceiling and the maximum remainder priority are defined as follows. Definition: The priority ceiling of a data item aej is the maximum preemption level of tasks that access aej. 2 Definition: The maximum remainder priority \Omega i(t) of a task Ti is the maximum priority ceiling of all data items that Ti will access after time t. If no data item will be accessed after time t, \Omega i(t) = 0. 2 The priority ceiling function \Phi i(t) of a task Ti can be defined in the same way as in CCP. We use tiniti (aej) and tfini (aej) to express the initial access instant and the final access instant of a job Ji of Ti on aej as before. The duration between an initial access instant and the corresponding final access instant is a resource demand section. Also, the duration between the first initial access instant and the last final access instant of a job is the outermost demand section of the job. Priority Ceiling Function: \Phi i(t) (\Phi 1) When a job of Ti starts execution, \Phi i(t) = 0. (\Phi 2) At t = tiniti (aej), if \Phi i(t) is less than the priority ceiling of aej, \Phi i(t) is set to the priority ceiling of aej. (\Phi 3) At t = tfini (aej), if \Phi i(t) ? \Omega i(t), \Phi i(t) is set to \Omega i(t). 2 We can prove that \Phi i(t) has at most one peak as in Theorem 3.1. Let CECCPi (t) be the maximum \Phi j(t) of all jobs except Ji itself at time t. With this modification, we can define the EDF based CCP as follows. EDF Based Convex Ceiling Protocol (ECCP) 1. (Scheduling Algorithm) The EDF algorithm. 2. (Concurrency Control Algorithm) When job Ji requests the first data access to a data item, 56 \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma timefl 4fl0fl 2fl T1fl T2fl T3fl r2fl r1fl (a) Task Setfl f1= l1fl f2= l2fl timefl 4fl0fl 2fl T1fl T2fl T3fl (b) Priority Ceiling Functionfl 0fl 0fl 0fl 0fl l1fl l1fl l2fl l2fl timefl 4fl0fl 2fl T1fl T2fl T3fl (c) Schedulefl 0fl 0fl l1fl l1fl l2fl 0fl 0fll2fl l1fl 6fl 8fl 10fl 12fl 14fl 16fl Figure 5.1: Example 4 (a) if Ji's preemption level *i is higher than CECCPi (t), Ji is allowed to proceed to the initial access instant on the data item. (b) Otherwise, Ji is suspended until *i ? CECCPi (t) is satisfied. 3. (Interaction Protocol) If Ji is suspended, the augmented priority ss\Lambda i of Ji is assigned to job Jk that has the maximum \Phi k(t). 2 As in Chapter 3, we assume that each job sends the scheduler a message indicating the first access to a data item before the first access and a message indicating the last access to the data item after the last access. We call those messages initial access notices and final access notices as before. Example 4 In Figure 5.1, there are three tasks T1, T2, and T3. As shown in Figure 5.1(a), T1 accesses data item ae1, T2 accesses data item ae2, and T3 accesses both ae1 and ae2. T1 arrives at 57 time 1 and its deadline is time 12. T2 arrives at time 3 and its deadline is time 17. T3 arrives at time 0 and its deadline is time 16. The preemption levels of T1, T2, and T3 are *1, *2, and *3 respectively. Since the relative deadlines of T1, T2, and T3 are 11, 14, and 16 respectively, T1 has the highest preemption level and T3 has the lowest, i.e., *1 ? *2 ? *3. The priority ceiling OE1 of ae1 is *1 and the priority ceiling OE2 of ae2 is *2. The priority ceiling functions of tasks are as shown in Figure 5.1(b). In the priority ceiling function of T3, the value of the function is kept at *2 between times 2 and 3 although no data item is used at that time. The schedule is as shown in Figure 5.1(c). When T1 arrives at time 1, T1 preempts T3 because the deadline of T1 is earlier than the deadline of T3. When T1 sends the initial access notice for ae1 at time 2, T1 is blocked since CECCP1 (2) = *1 and T1's preemption level is *1. T3 inherits the priority of T1 and resumes execution. T3 sends the final access notice for ae1 at time 3 and CECCP1 (3) is now *2. The priority of T3 returns to its original priority. T1 enters into its resource demand section for ae1 and exits from it at time 4. T2 is ready at time 4. However, T2 cannot execute because T2 has a later deadline than T3, i.e., T2 has a lower priority than T3, although T2 has a higher preemption level. After T3 completes, T2 starts to execute. 2 5.2 Properties of ECCP ECCP has the same three properties as CCP. ECCP guarantees no deadlock. A job is blocked by at most one lower priority job. ECCP produces serializable schedules. In this section, we prove these properties. 5.2.1 Single-Blocking and No-Deadlock Properties In the following discussion, we assume tasks, T1, T2, \Delta \Delta \Delta , Tn, are sorted in descending order of preemption levels and T1 has the highest preemption level. Also, we assume, for simplicity of proofs, that there is no tie in preemption levels. The strategies to prove the single-blocking and the no-deadlock properties are the same as the proofs for CCP, but the preemption levels require additional consideration. Lemma 5.1 After a job Ji starts its execution and before Ji completes, every active job Jl with a lower preemption level than Ji has a lower original priority than Ji. 58 Jifl Jlfl longer relative deadlinefl earlier deadlinefl timefl Figure 5.2: Deadline and Relative Deadline Proof: When Ji starts to execute, Ji has the highest augmented priority ss\Lambda i = ssi in the system. Suppose Jl