یک الگوریتم جدید برای اثبات قابلیت برنامه ریزی سیستم های زمان واقعی
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|7175||2000||7 صفحه PDF||سفارش دهید||3550 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Control Engineering Practice, Volume 8, Issue 6, June 2000, Pages 689–695
In hard real-time multiprocessor systems, tasks not only have timing constraints but also often have precedence constraints caused by communication among themselves. In this paper a new algorithm to prove the schedulability of real-time systems is proposed, in which both precedence constraints and communication costs are considered and represented by offsets and modified deadlines. To obtain a tight upper bound for the worst-case response time, the concepts of local critical instant and local worst-case response time are introduced. The proposed algorithm is compared with other algorithms using test cases. The comparison shows that the proposed algorithm has improved the performances to these compared algorithms.
A real-time system must be both functionally and temporally correct. This is especially true for hard real-time systems, where a key requirement is whether hard real-time conditions are fulfilled or not, i.e., whether each task is guaranteed to meet its deadline. The proof is performed by using schedulability analysis. Fixed priority preemptive scheduling methods are efficient ways of constructing and analyzing schedules for hard real-time systems. Among them, deadline monotonic scheduling is more suitable for use in parallel environments with communicating tasks, since precedence constraints caused by communication could be taken into consideration by modifying the original deadlines of the tasks. The majority of the schedulability analyses performed to date have assumed a critical instant, a concept introduced by Liu and Layland (Liu & Layland, 1973). They stated that for a task set in which all tasks are independent there is a critical instant, i.e., when all tasks are simultaneously released. If the schedulability analysis is carried out for the critical instant and all tasks are assumed to execute in their worst-case execution times, then the test is both sufficient and necessary. However, in multiprocessor systems, tasks often have precedence constraints caused by communication among them. This means that all tasks cannot be simultaneously released. Hence the schedulability analysis based on the critical instant becomes pessimistic. There are several approaches in which precedence constraints are considered (Altenbernd, 1995; Tindell, 1994; Bate & Burns, 1997; Wang & Färber, 1998). An exact analysis was presented in Audsley, Tindell and Burns (1993b). Since the exact analysis is computationally intractable, a sufficient but not necessary analysis was developed (Tindell, 1994). Recently, a non-preemptive fixed priority schedulability analysis with offset was proposed (Bate & Burns, 1997). The limitation of these analyses is that they are based on uniprocessor systems. For multiprocessor systems, an analysis using minimal–maximal offset intervals was presented (Altenbernd, 1995). In that paper, the computation of the worst-case response time is divided into two parts: transaction response time and interference of other transactions. However, the communication cost between tasks residing on different processors is not considered. Communication costs influence both the predecessor task and the successor task and make their deadlines harder to be met. An improved analysis (Wang & Färber, 1998) was proposed by the authors of this paper. In that paper the communication cost is considered and the calculation of transaction response time was more accurate. However, the calculation of interference by the other transactions was not changed and is based on a less accurate algorithm. Thus the analysis is also pessimistic in some cases. In this paper, the worst-case response time is analyzed with another method. The new analysis algorithm is based on a busy period analysis (Lehoczky, Sha & Ding, 1989;Tindell, Burns & Wellings, 1994). Simulation results show that it is more accurate than the analysis algorithm used most often in the literature. The rest of the paper is organized as follows: Section 2 briefly describes the basic assumptions that will be used in the proposed analysis algorithm. Then the new algorithm is presented in Section 3. Section 4 gives evaluation results in which the proposed schedulability analysis is compared with other approaches using test cases. Finally, Section 5 summarizes the result of this paper.
نتیجه گیری انگلیسی
In this paper, a new schedulability analysis algorithm for hard real-time multiprocessor systems is proposed. The influence of both precedence constraints and communication costs is considered. It is represented by the offsets and modified deadlines. To obtain a tight upper bound of the worst-case response time, the concept of the local critical instant is introduced. It is an extension of the Liu and Layland's original concept of the critical instant. Then the concepts of local offset and global offset are further introduced. They are used in the computation of local worst-case response time and global worst-case response time.The computation is based on a busy period analysis. The simulation results show that when the precedence constraints between tasks are ignored, the analysis results will be relatively pessimistic. Therefore in a good schedulability analysis the precedence constraints should be considered. The proposed schedulability analysis algorithm is more accurate than those in Tindell (1994) and Wang and Färber (1998). Another useful characteristic of the proposed algorithm is its consideration of the influence of communication costs that make deadlines harder to be met. However, this influence is not considered in Altenbernd (1995),Tindell (1994) and Bate and Burns, 1997.