Utilization Based Schedulability Bounds for Age Constraint Process Sets in Real-Time Systems
Tóm tắt
Some real-time systems consist of a number of processes that operate under age constraints. In such systems, the maximum time from the start of process L
i in cycle k to the end in cycle k+1 must not exceed the age constraint A
i for that process. The age constraint can be met by using fixed priority scheduling and periods equal to A
i/2. However, this approach restricts the number of process sets which are schedulable. In this paper, we define a method for obtaining process periods other than A
i/2. The periods are calculated in such a way that the age constraints are met. Our approach is better in the sense that a larger number of process sets can be scheduled compared to using periods equal to A
i/2. The main results in this paper are a number of performance bounds on age constraint processes. These bounds show that there is a significant gain in worst case as well as in best case behavior by using periods other than A
i/2, particularly when there are a large number of processes in the system.
Tài liệu tham khảo
Albrecht, W., and Wisser, R. 1997. Schedulers for age constraint tasks and their performance evaluation. In Proceedings of the Third International EuroPar Conference. Passau, Germany.
Albrecht, W., and Zöbel, D. 1997. Integrating fixed priority and static scheduling to maintain external consitency. Technical report. http://www.uni-koblenz.de/fb4/publikationen/gelberihe/RR-9-97.ps.gz
Audsley, N., Burns, A., Richardson, M., and Wellings, A. 1992. Absolute and relative temporal constraints in hard real-time databases. In Proceedings of IEEE Euromicro Workshop on Real-Time Systems. Los Alamitos, California.
Audsley, N., Burns, A., Richardson, M., and Wellings, A. 1993. The end of the line for static cyclic scheduling? In Proceedings of Euromicro Workshop on Real-Time Systems. Oulu, Finland, pp. 36-41.
Burns, A., and Davis, R. 1996. Choosing task periods to minimise system utilisation in time triggered systems. Information Processing Letters 58: 223-229.
Burns, A., and Wellings, A. 1996. Real-Time Systems and Programming Languages. Addison-Wesley.
Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability—A Guide to the Theory of NP-Completeness. W.H. Freeman and company.
Hou, E. S. H., Hong, R., and Ansari, N. 1990. Efficient multiprocessor scheduling based on genetic algorithms. 16th Annual Conference of the IEEE Industrial Electronics Society, Vol II, pp. 1239-1243.
Kopetz, H. 1998. The time-triggered model of computation. In Proceedings of the IEEE Real-Time Systems Symposium. Madrid, Spain, pp. 168-177.
Lehoczky, J. P. 1990. Fixed priority scheduling of periodic task sets with arbitrary deadlines. In Proceedings of the 11th Real-Time Systems Symposium, pp. 201-209.
Lehoczky, J. P., Sha, L., and Ding, Y. 1989. The rate monotone scheduling algorithm: exact characterization and average case behavior. In Proceedings of IEEE 10th Real-Time Systems Symposium.
Leung, J., and Whitehead, J. 1980. On the complexity of fixed-priority scheduling of periodic real-time tasks. Performance Evaluation 237-250.
Liu, C., and Leyland, J. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM 46-61.
Lundberg, L. 1998a. Fixed priority scheduling of age constraint processes. In Proceedings of EuroPar-98. Southampton, England, pp. 288-296.
Lundberg, L. 1998b. Multiprocessor scheduling of age constraint processes. In Proceedings of the Fifth IEEE International Conference on Real-Time Computing Systems and Applications. Hiroshima, Japan pp. 42-47.
Lundberg, L., and Lennerstad, H. 1998. Using recorded values for bounding the minimum completion time in multiprocessors. IEEE Transactions on Parallel and Distributed Systems, pp. 346-358.
Nanda, A. K., DeGroot, D., and Stenger, D. L. 1992. Scheduling directed task graphs on multiprocessors using simulated annealing. In Proceedings of the IEEE 12th International Conference on Distributed Systems, pp. 20-27.
Nissanke, N. 1997. Realtime Systems. Prentice Hall.
Song, X., and Liu, J. 1992. How well can data temporal consistency be maintained. In Proceedings of the 1992 IEEE Symposium on Computer Aided Control Systems Design. Napa, California, USA.
Tindell, K., Burns, A., and Wellings, A. 1994. An extendible approach for analysing fixed priority hard real-time tasks. Real-Time Systems 6(2): 133-151.