CFP last date
15 July 2024
Reseach Article

Preemptive Task Partitioning Strategy (PTPS) with Fast Preemption in Heterogeneous Distributed Environment

by Rafiqul Zaman Khan, Javed Ali
journal cover thumbnail
International Journal of Applied Information Systems
Foundation of Computer Science (FCS), NY, USA
Volume 6 - Number 1
Year of Publication: 2013
Authors: Rafiqul Zaman Khan, Javed Ali

Rafiqul Zaman Khan, Javed Ali . Preemptive Task Partitioning Strategy (PTPS) with Fast Preemption in Heterogeneous Distributed Environment. International Journal of Applied Information Systems. 6, 1 ( September 2013), 25-31. DOI=10.5120/ijais13-450995

@article{ 10.5120/ijais13-450995,
author = { Rafiqul Zaman Khan, Javed Ali },
title = { Preemptive Task Partitioning Strategy (PTPS) with Fast Preemption in Heterogeneous Distributed Environment },
journal = { International Journal of Applied Information Systems },
issue_date = { September 2013 },
volume = { 6 },
number = { 1 },
month = { September },
year = { 2013 },
issn = { 2249-0868 },
pages = { 25-31 },
numpages = {9},
url = { },
doi = { 10.5120/ijais13-450995 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
%0 Journal Article
%1 2023-07-05T17:59:26.308405+05:30
%A Rafiqul Zaman Khan
%A Javed Ali
%T Preemptive Task Partitioning Strategy (PTPS) with Fast Preemption in Heterogeneous Distributed Environment
%J International Journal of Applied Information Systems
%@ 2249-0868
%V 6
%N 1
%P 25-31
%D 2013
%I Foundation of Computer Science (FCS), NY, USA

Efficient preemptions in the scheduling of real time systems cause optimal overhead in parallel computing systems. Periodic and sporadic tasks are exists in the real time systems. The periodic tasks may be divided into the synchronous and asynchronous categories. The management of the resource sharing in the parallel computing can be powerfully achieved by preemptive scheduling. Fast preemptions are necessary to achieve the high degree parallelism. In this paper, Earliest Starting Time parameter expended up to a large degree of heterogeneity. We compare the proposed algorithm with the existed well known algorithms: preemptive MCP and FPS algorithms. The result shows better performance of the PTPS in terms of average NSL and running time complexities.

  1. L. George, N. Rivierre, and M. Spuri, (1996). Preemptive and Non-Preemptive Real-Time Uni- Processor Scheduling, Institut National de Rechercheen Informatique et en Automatique, Tech. Rep. , 45-50.
  2. S. Baruah and S. Chakraborty,(2006). Schedulability analysis of non-preemptive recurring real-time tasks. Parallel and Distributed Processing Symposium, 2006. IPDPS 2006. 20th International, 12-15.
  3. L. George, N. Rivierre, and M. Spuri. ,(1996). Preemptive and non-preemptive real-time uniprocessor scheduling. Research Report RR-2966, INRIA, 89-90.
  4. K. Jeffay, D. Stanat, and C. Martel. , (1991). On non-preemptive scheduling of period and sporadic tasks. Real-Time Systems Symposium, 1991. Proceedings. , Twelfth,129–139.
  5. Ramaprasad and F. Mueller. , (2008). Bounding worst-case response time for tasks with non-preemptive regions. Real- Time and Embedded Technology and Applications Symposium, 2008. RTAS '08. IEEE, 58–67.
  6. R. Dobrin and G. Fohler. , (2004). Reducing the number of preemptions in fixed priority scheduling. Real-Time Systems, 2004. ECRTS 2004. Proceedings. 16th Euromicro Conference on, pages 144–152.
  7. C. -G. Lee, J. Hahn, Y. -M. Seo, S. L. Min, R. Ha, S. Hong, C. Y. Park, M. Lee, and C. S. Kim. (1998). Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Trans. Comput. , 47(6):700–713.
  8. A. Burns. ,(1994). Preemptive priority based scheduling: An appropriate engineering approach. In S. Son, editor, Advances in Real-Time Systems, 225–248.
  9. N. Megow, M. Uetz, and T. Vredeveld, (2006). Models and algorithms for stochastic online scheduling", Mathematics of Operations Research, vol. 31, 513-525.
  10. R. H. Moring, A. S. Schulz, and M. Uetz, (1999). Approximation in stochastic scheduling: the power of LP-based priority policies, 1. ACM , vol. 46, 924-942.
  11. Sahni, S. K, (1976). Algorithms for scheduling independent tasks. ACM, vol. 23, 116-127.
  12. R. I. Davis and A. Burns, (2009). Priority Assignment for Global Fixed Priority Pre-Emptive Scheduling in Multiprocessor Real-Time Systems," in 2009 30th IEEE Real-Time Systems Symposium, Technical report YCS-2010-451, Department of Computer Science, University of York. IEEE, 398–409.
  13. E. Bini and G. Buttazzo, (2005). Measuring the performance of schedulability tests. Real-Time Systems, vol. 30, no. 1, 129–154.
  14. C. Li, C. Ding, and K. Shen, (2007) . Quantifying The Cost of Context Switch. In Proceedings of the 2007 workshop on Experimental computer science, no. June. ACM, 67-69.
  15. A. Bastoni, (2010). Cache-Related Preemption and Migration Delays : Empirical approximation and Impact on Schedulability. In Sixth International Workshop on Operating Systems Platforms for Embedded Real-Time Applications, 33–34.
  16. C. L. Liu and J. W. Layland, (1973). Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, vol. 20, no. 1,46–61.
  17. N. Guan, W. Yi, Q. Deng, Z. Gu, and G. Yu, (2011). Schedulability analysis for non-preemptive fixed-priority multiprocessor scheduling. Journal of Systems Architecture, vol. 57, no. 5, 536 – 546.
  18. D. I. Katcher, H. Arakawa, J. K. Strosnider. , (1993). Engineering and analysis of fixed priority schedulers. IEEE Transactions on Software Engineering, 19(9),920-934.
  19. M. Bertogna and S. Baruah, (2010). Limited preemption of scheduling of sporadic task systems. IEEE Transactions on Industrial Informatics, 45-49.
  20. S. Altmeyer, R. Davis, and C. Maiza, (2011). Cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. In Proc. 32nd IEEE Real-Time Syst. Symp. (RTSS. 11), Vienna,Austria, 23-28.
  21. M. Bertogna, O. Xhani, M. Marinoni, F. Esposito, and G. Buttazzo, (2011). Optimal selection of preemption points to minimize preemption overhead. In Proc. 23rd Euromicro Conf. Real-Time Syst. (ECRTS'11), Porto, Portugal, Jul. 6–8, , 217–227.
  22. Cheng, R. , Gen, M. , And Tsujimura, Y. , (1996). A tutorial survey of job-shop scheduling problems using genetic algorithms—I: representation. Comput. Ind. Eng. 30, 4, 983–997.
  23. Gonzalez, M. J. , Jr. ,(1977). Deterministic processor scheduling. ACM Comput. Surv. 9, 3 (Sept. ), 173–204.
  24. Horvath, E. C. , Lam, S. , Sethi, R. , (1977). A level algorithm for preemptive scheduling. J. ACM 24, 1 (Jan. ), 36–47.
  25. Rayward-Smith, V. J. , (1987). The complexity of preemptive scheduling given interprocessor communication delays. Inf. Process. Lett. 25, 120–128.
  26. Coffman, E. G. and Graham, R. L. (1972). Optimal scheduling for two-processor systems. Acta Inf. 1, 200–213.
  27. Blazewicz, J. , Weglarz, J. , and Drabowski, M. (1984). Scheduling independent 2-processor tasks to minimize schedule length. Inf. Process. Lett. 18, 267–273.
  28. Chung, Y. -C. and Ranka, S. (1992). Applications and performance analysis of a compile-time optimization approach for list scheduling algorithm on distributed memory multiprocessors. In Proceedings of the 1992 Conference on Supercomputing (Supercomputing '92, Minneapolis, MN, Nov. 16–20), R. Werner, Ed. IEEE Computer Society Press, Los Alamitos, CA, 515–525
Index Terms

Computer Science
Information Sciences


Preemptive Scheduling Normalized Schedule Length Directed Acyclic Graph Parallel Computing etc.