Dynamic scheduling algorithms for real-time multiprocessor systems are important components of real-time systems. The most important metric for real-time scheduling algorithms is scheduling success ratio. In this paper, based on the traditional myopic algorithm, a new dynamic scheduling algorithm, called‘hrift algorithm', is proposed for real-time multiprocessor systems. In this algorithm, a new processor selection policy is developed to improve scheduling success ratio. To study the effectiveness of thrift algorithm,an intensive simulation studyis made to analyze the impact of several task parameters on its scheduling success ratio and compare its performance to myopic algorithm.The simulation results show that the scheduling success ratio of our new scheduling algorthm is superior to thet of mypoic algorthm.
[1] Mok, A.K. Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment [Ph.D.Thesis]. Cambridge, MA: Department of Electronic Engineering and Computer Sciences, MIT, 1983.
[2] Ramamritham, K.J., Stankovic, A., Shiah, P.-F. Efficient scheduling algorithms for real-time multiprocessor systems. IEEE Transactions on Parallel and Distributed Systems, 1990,1(2):184~194.
[3] Manimaran, G., Murthy, C.S.R. An efficient dynamic scheduling algorithm for multiprocessor real-time systems. IEEE Transactions on Parallel and Distributed Systems, 1998,9(3):312~319.
[4] Mittal, A., Manimaran, G., Murthy, C.S.R. Integrated dynamic scheduling of hard and QoS degradable real-time tasks in multiprocessor systems. In: Mok, A.K., Tokuda, H., eds. Proceedings of the 5th International Conference on Real-Time Computing Systems and Applications. Los Alamitos, CA: IEEE Press, 1998. 162~172.