Cluster Based Real Time Scheduling for Distributed System

Abstract

Real time tasks scheduling on a distributed system is a complex problem. The existing real time tasks scheduling techniques are primarily based on partitioned and global scheduling. In partitioned based scheduling the tasks are assigned on a dedicated processor. The advantages of partitioned based approach is existing uni-processor scheduling techniques can be used; no migration overheads but task assignment is NP hard problem and optimal utilization of processing nodes is not possible. In global scheduling all tasks are maintained in a single tasks queue and allocated to multiple processing nodes. The advantage of global scheduling is optimal utilization of processing nodes but suffer from high migration and preemption overheads. This paper proposed cluster based real time tasks scheduling on a distributed system which is a hybrid scheduling approach where processing nodes group into cluster and scheduling using global scheduling. The simulation result shows that the proposed scheduling increases the tasks acceptance ratio, resource utilization as compared to partitioned and global scheduling and reduces migration as well as preemption overheads.
  • Referencias
  • Cómo citar
  • Del mismo autor
  • Métricas
Agrawal, K., Baruah, S., Ekberg, P., & Li, J. (2020). Optimal scheduling of measurement-based parallel real-time tasks. Real-Time Systems, 56(3), 247–253. Doi:10.1007/s11241-020-09346-z

Anderson, H., Calandrino, J. M., & Devi, U. M. C. (2006). Realtime scheduling on multicore platforms. In Proceedings of the of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'06) (pp. 179–190).

Atif, Y., & Hamidzadeh, B. (May 26–29 1998). A scalable scheduling algorithm for real-time distributed systems. Proceedings of the 18th International Conference on Distributed Computing Systems (pp. 352–359).

Bastoni, A., Brandenburg, B., & Anderson, J. (2010). An empirical comparison of global, partitioned, and clustered multiprocessor EDF schedulers. In 31st IEEE Real-Time Systems Symposium.

Bertogna, M., Fisher, N., & Baruah, S. (2009) Resource-sharing servers for open environments. IEEE Transactions on Industrial Informatics, 5(3, August), 202–219. doi:10.1109/TII.2009.2026051

Blej, M. M., & Azizi, M. (2019). Tasks parameter impacts in fuzzy real time scheduling. In. Studies in Fuzziness and Soft Computing. Cham, Germany: Springer, 69–78. doi:10.1007/978-3-030-02155-96

Block, H., Leontyev, B. B., Brandenburg, & Anderson, J. H. (Aug. 2007). A flexible real-time locking protocol for multiprocessors. In 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA) (pp. 47–56).

Brandenburg, B. B., & Anderson, J. H. (2013). The OMLP family of optimal multiprocessor real-time locking protocols. Design Automation for Embedded Systems, 17(2), 277–342. doi: 10.1007/s10617-012-9090-1

Chéramy, M., Hladik, P.-E., & Déplanche, A.-M. (2014). SimSo: A simulation tool to evaluate real-time multiprocessor scheduling algorithms.

Coulouris, G., Dollimore, J., Kindberg, T., & Blair, G. (2011). Distributed systems: Concepts and design (5th ed). New York: Addison-Wesley.

Craciunas S. S. & Oliver R. S. (2016). Combined task- and network-level scheduling for distributed time-triggered systems. Real-Time Syst 52(2):161–200. https://doi.org/10.1007/s11241-015-9244-x

Dellabani, M., Combaz, J., Bensalem, S., & Bozga, M. (2019). Local planning semantics: A semantics for distributed real-time systems. Leibniz. Trans. Embed Syst., 6(1):10.

Erickson, J. P., & Anderson, J. H. (2019). Soft real-time scheduling. Handbook of real-time computing. Berlin: Springer.

Gandhi, N., Roth, E., Gifford, R., Phan, L. T. X., & Haeberlen, A. (2020). Bounded-time recovery for distributed real-time systems. Real, Philippines: IEEE Publications-Time and Embedded Technology and Applications Symposium (RTAS), Sydney, & Australia. (2020), pp. 110–123. doi: 10.1109/RTAS48715.2020.00-13

Günzel, M., & Chen, J. (2020). Correspondence Article: Counterexample for suspension-aware schedulability analysis of EDF scheduling. Real-Time Systems, 56(4), 490–493. doi: 10.1007/s11241-020-09353-0

Gupta, K., Arora, V. K., Shukla, H., Beedu, B. K., & Nagpal, A. (2019). Dynamic scheduling of distri buted storage management tasks using predicted system characteristics, U.S Patent application 10/168, 953, filed.

Hammou, B. A., Lahcen, A. A., & Mouline, S. (2019). A distributed group recommendation system based on extreme gradient boosting and big data technologies. Applied Intelligence, 59, 1–22.

Hluchy, L., Dobrucky, M., Viet, T. D., & Astalos, J. (2001). ‘The Mapping, Scheduling andLoadBalancing Tools of GRADE', parallel program development for cluster computing, advances in computation: Theory and practice, 5 (pp. 265–279).: Nova Science Publishers, Inc.

Ismail, D., Mahbubur Rahman, V. P., Modekurthy, & Saifullah, A. (2017). Work-in-Progress: Utilization based schedulability analysis for wireless sensor-actuator networks. In (pp. 137–140). Real, Philippines: IEEE Publications-Time and Embedded Technology and Applications Symposium (RTAS). Institute of Electrical and Electronics Engineers. (2017).

Leng, C., Qiao, Y., Hu, X. S., & Wang, H. (2020). Co-scheduling aperiodic real-time tasks with end-to-end firm and soft deadlines in two-stage systems. Real-Time Systems, 56(4), 391–451. doi:10.1007/s11241-020-09352-1

Leoncini, M., Montangero, M., & Valente, P. (2019). A parallel branch-and-bound algorithm to compute a tighter tardiness bound for preemptive global EDF. Real-Time Systems, 55(2), 349–386. doi:10.1007/s11241-018-9319-6

Mohaqeqi, M., Nasri, M., Xu, Y., Cervin, A., & Arzén, K. (2018). Optimal harmonic period assignment: Complexity results and approximation algorithms. Real-Time Systems, 54(4), 830–860. doi:10.1007/s11241-018-9304-0

Nemitz, C. E., Amert, T., & Anderson, J. H. (2019). Real-time multiprocessor locks with nesting: Optimizing the common case. Real-Time Systems, 55(2), 296–348. doi:10.1007/s11241-019-09328-w

Puffitsch, W., Noulard E., Pagetti C. (2015). Off-line mapping of multi-rate dependent task sets to manycore platforms. Real-Time Syst 51(5):526–565. https://doi.org/10.1007/s11241-015-9232-1

Qamhieh, M., George, L., & Midonnet, S. (2019). Stretching algorithm for global scheduling of real-time DAG tasks. Real-Time Systems, 55(1), 32–62. doi:10.1007/s11241-018-9311-1

Saifullah, A., Ferry, D., Li, J., Agrawal, K., Lu, C., & Gill, C. D. (2014). Parallel real-time scheduling of DAGs. IEEE Transactions on Parallel and Distributed Systems, 25(12, December), 3242–3252. doi: 10.1109/TPDS.2013.2297919

Sharma, R., Nitin, N., Rahman, M. A., & Dahiya, D. (2020) Priority-based joint EDF-RM scheduling algorithm for individual real-time task on distributed systems. Journal of Supercomputing, Issue 1 2020.

Van den Heuvel, M. M. H. P., Bril, R. J., & Lukkien, J. J. (May 2012). Transparent synchronization protocols for compositional real-time systems. IEEE Transactions on Industrial Informatics, 8(2), 322–336. doi:10.1109/TII.2011.2172448

Ward, C., & Anderson, J. H. (2012). Supporting nested locking in multiprocessor real-time systems. In Proceedings of the of the 24th Euromicro conference on Real-Time Systems (ECRTS2012) (pp. 223–232).

Zhang, F., & Burns, A. (2009). Improvement to quick processor demand analysis for edf-scheduled realtime systems. In Real-Time Systems. ECRTS'09. 21st Euromicro Conference on (pp. 76–86). IEEE.

Zhang, L., Goswami, D., Schneider, R., Chakraborty, S. (2014). Task- and network-level schedule co-synthesis of ethernet-based time-triggered systems. In: 19th Asia and South Pacific design automation conference (ASP-DAC), pp 119–124

Zhang, T., Gong, T., Han, S., Deng, Q., & Hu, X. S. (2018). Distributed dynamic packet scheduling framework for handling disturbances in real-time wireless networks. IEEE Transactions on Mobile Computing, 18(11), 2502–2517. doi:10.1109/TMC.2018.2877681

Zhao, Y., Zeng, H., & H. (2019). The concept of Maximal Unschedulable Deadline Assignment for optimization in fixed-priority scheduled real-time systems. Real-Time Systems, 55(3), 667–707. doi:10.1007/s11241-019-09332-0

Zhuravlev, S., Saez, J. C., & Prieto, M. (2011). Survey of Scheduling Techniques for Addressing Shared Resources in multicore Processors. ACM Computing Surveys, V(N, September), 1–31.
Talmale, G., & Shrawankar, U. (2021). Cluster Based Real Time Scheduling for Distributed System. ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal, 10(2). https://doi.org/10.14201/ADCAIJ2021102137156

Downloads

Download data is not yet available.
+