Distributed real-time systems play an increasingly vital role in our society. The most important aspect of such systems is the scheduling algorithm, which must guarantee that every job in the system will meet its deadline, providing high-quality (precise) results. In this paper we evaluate by simulation the performance of strategies for the scheduling of parallel jobs (gangs) in a homogeneous distributed real-time system with possible software faults. For each scheduling policy we provide an alternative version which allows imprecise computations. We propose a performance metric applicable to our problem, which takes into account the number of jobs guaranteed, as well as the precision of the results of each guaranteed job. The simulation results show that the alternative versions of the algorithms outperform their respective counterparts. To the best of our knowledge, a real-time gang scheduling approach that utilizes imprecise computations has never been discussed in the literature before.
Buttazzo, G.C.2004. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, 2nd edition, Springer, Berlin.
2.
Liu, C.L. and J.W. Layland.1973. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 20(1): 46-61.
3.
Mok, A.K.1983. Fundamental Design Problems of Distributed Systems for the Hard Real-time Environment, PhD Thesis. Massachusetts Institute of Technology.
4.
Lin, K.J. , S. Natarajan and J.W.S. Liu.1987. Imprecise results: utilizing partial computations in real-time systems. In Proceedings of the 8th IEEE Real-Time Systems Symposium (RTSS’87) , San Jose, CA, pp. 210-217.
5.
Liu, J.W.S. , K.J. Lin , W.K. Shih, A.C. Yu , J.Y. Chung and W. Zhao.1991. Algorithms for scheduling imprecise computations. IEEE Computer, 24(5): 58-68.
6.
Hull, D.L.2000. An Environment for Imprecise Computations, PhD Thesis , University of Illinois at Urbana-Champaign.
7.
Han, C.C. , K.G. Shin and J. Wu .2003. A fault-tolerant scheduling algorithm for real-time periodic tasks with possible software faults. IEEE Transactions on Computers, 52(3): 362-372.
8.
Liu, J.W.S. , W.K. Shih, K.J. Lin , R. Bettati and J.Y. Chung.1994. Imprecise computations . Proceedings of the IEEE, 82(1): 83-94.
9.
Harchol-Balter, M., M. Crovella and C.D. Murta.1998. On choosing a task assignment policy for a distributed server system. In Proceedings of the 10th International Conference on Computer Performance Evaluation: Modelling Techniques and Tools (Lecture Notes in Computer Science, Vol. 1469), Springer, Berlin, pp. 231-242.
10.
Law, A.M. and W.D. Kelton.2000. Simulation Modeling and Analysis, 3rd edition, McGraw-Hill , New York.
11.
Feitelson, D.G. and M.A. Jette.1997. Improved utilisation and responsiveness with gang scheduling. Job Scheduling Strategies for Parallel Processing (Lecture Notes in Computer Science, Vol. 1291), Springer, Berlin, pp. 23-26.
12.
Karatza, H.D.1999. A simulation-based performance analysis of gang scheduling in a distributed system. In Proceedings of the 32nd Annual Simulation Symposium, San Diego, CA, pp. 26-33.
13.
Karatza, H.D.1999. Gang scheduling in a distributed system with processor failures. In Proceedings of the UK Performance Engineering Workshop, Bristol, UK , pp. 199-208.
14.
Karatza, H.D.2000. Gang scheduling and I/O scheduling in a multiprocessor system. In Proceedings of the 2000 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS 2000), Vancouver, Canada, pp. 245-252.
15.
Karatza, H.D.2003. Gang scheduling in a distributed system under processor failures and time-varying gang size. In Proceedings of the 9th IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS’03), San Juan, Puerto Rico, pp. 330-336.
16.
Karatza, H.D.2006. Scheduling gangs in a distributed system. International Journal of Simulation: Systems, Science and Technology, 7(1): 15-22.
17.
Karatza, H.D.2006. Performance analysis of gang scheduling in a partitionable parallel system. In Proceedings of the 20th European Conference on Modelling and Simulation, Sankt Augustin, Germany, pp. 699-704.
18.
Karatza, H.D.2007. Performance of gang scheduling policies in the presence of critical sporadic jobs in distributed systems . In Proceedings of the 2007 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS’07) , San Diego, CA, pp. 547-554.
19.
Zhang, Y., A. Yang, A. Sivasubramaniam and J. Moreira.2003. Gang scheduling extensions for I/O intensive workloads . Job Scheduling Strategies for Parallel Processing (Lecture Notes in Computer Science, Vol. 2862), Springer , Berlin, pp. 83-207.
20.
Karatza, H.D.2008. The impact of critical sporadic jobs on gang scheduling performance in distributed systems. Simulation: Transactions of the Society for Modeling and Simulation International , 84(2-3): 89-102.
21.
Lee, J.K. , C.D. Lin , Y.W. Chang and W.K. Shih.1998. Real-time gang schedulings with workload models for parallel computers. In Proceedings of the 1998 IEEE International Conference on Parallel and Distributed Systems (ICPADS’98), Tainan, Taiwan, pp. 114-121.
22.
Silva, F.A.B. , E.P. Lopes, E.P.L. Aude, F. Mendes, J.T.C. Silveira, H. Serdeira, M. Martins and W. Cirne.2002. Response time analysis of gang scheduling for real time systems. In Proceedings of the 2002 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS’02), San Diego, CA, pp. 297-301.
23.
Stavrinides, G.L. and H.D. Karatza.2008. Performance evaluation of gang scheduling in distributed real-time systems with possible software faults. In Proceedings of the 2008 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS’08), Edinburgh, UK, pp. 1-7.
24.
Cottet, F., J. Delacroix, C. Kaiser and Z. Mammeri.2002. Scheduling in Real-Time Systems, John Wiley & Sons, Inc., New York.
25.
Sha, L., T. Abdelzaher, K.E. Arzen, A. Cervin, T. Baker, A. Burns, G. Buttazzo, M. Caccamo, J. Lehoczky and A.K. Mok .2004. Real time scheduling theory: a historical perspective. Real-Time Systems, 28(2-3): 101-155.
