Random Articles
Reseach Article
Real-Time Workload Allocation on a Uni-Processor
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 53 - Number 12 |
| Year of Publication: 2012 |
| Authors: Abeer Hamdy, Ahmed E. Youssef, Reda Ammar |
10.5120/8473-2401
|
Abeer Hamdy, Ahmed E. Youssef, Reda Ammar . Real-Time Workload Allocation on a Uni-Processor. International Journal of Computer Applications. 53, 12 ( September 2012), 17-24. DOI=10.5120/8473-2401
Abstract
The paper presents a novel allocation algorithm to allocate independent real time tasks on a processor in a way that improves the processor's throughput (Processor's throughput is the number of tasks the processor can accept for execution). The proposed approach allocates tasks' workloads (task's workload is the percentage of work required by the processor to execute the task) instead of their processing powers (Processing power assigned to a task is a percentage of the processor reserved to execute the task such that its deadline is satisfied). To achieve our objective a variable processing power is assigned to the task under consideration over its deadline to satisfy its timing requirements instead of rejecting it if a constant processing power cannot be guaranteed as in previous CPU reservation approaches. Simulation results revealed that the acceptance rate of the admitted tasks to a certain processor using the new approach is superior to that achieved using the traditional processing power reservation approach.
References
- Aydin, H. , Melhem, R. , Mosse, D. and Meja-Alvarez, P. , 2001, Dynamic and Aggressive Scheduling techniques for power-aware real-time systems, In Proceedings of the 22nd IEEE Real-Time systems Symposium.
- Birkenheuer, G. and Brinkmann, A. , 2011, Reservation based overbooking for HPC clusters, In Proceedings of IEEE International Conference on Cluster computing.
- Caniou, Y. , Charrier, G. , Desprez F. , 2010 ,Analysis of tasks reallocation in a dedicated grid environment, In Proceedings of IEEE international conference on cluster computing.
- Deng, Z. , Liu, J. W. -s and Sun, S. , 1996, Dynamic scheduling of hard real-time applications in open system environment, Technical Report, University of Illinois, USA.
- Ford, B. and Susarla, S. , 1996, CPU inheritance scheduling, operating systems review.
- Gioiosa, R. , McKee, S. A. , Valero, M. , 2010, Designing OS for HPC Applications: Scheduling, In Proceedings of IEEE International conference on cluster computing.
- H. Heidari and A. Chalechale, "Scheduling in Multiprocessor System using Genetic Algorithm", International Journal of Advanced Science and Technology, june 2012.
- Jones, M. B. , Ro?u, D. , Ro?u, M. , 1997, CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities, In Proceedings of the 16th ACM Symposium on Operating System Principles.
- Jones, M. B. 2001, Two case studies in predictable application scheduling using Rialto/NT , In Proceedings of 7th Real-Time Technology and Applications Symposium.
- M. Lombardi, M. Milano, L. Benini, "Robust Scheduling of Task Graphs under Execution Time Uncertainty", IEEE transactions on computers, 2011.
- Niemeier, M. , Wiese, A. , Baruah, S. , 2011, Partitioned real-time scheduling on heterogeneous shared-memory multiprocessors, In Proceedings of the 23rd Euromicro Conference on Real-Time Systems.
- O. Jaewon and W. Chisu, "Genetic Algorithm Based Real Time Task Scheduling with Multiple Goals", Journal of systems and software, 2004.
- R. Ammar, A. Alhamdan, "Scheduling real-time fork-join structures in cluster computing", Int. Journal of High Performance Computing and Networking , Vol. 3, No. 4, 2005, pp. 262 – 271.
- Regehr, J. , J. and Stankovic, J. A. , 2001, Augmented CPU reservations: Towards predictable execution on general-purpose operating systems, In Proceedings of the IEEE Real-Time Technology and Applications.
- Stoica, I. , Abdelwahab, H. , Effay, K. , Baruah, S. K. , Gehrke, J. E. and Plaxton, C. G. , 1996, A proportional share resource allocation algorithm for real-time, time-shared systems, In Proceedings of 17th IEEE real-time systems symposium.
- Satish, N. R. , Ravindran, K. , Keutzer, K. , 2008, Scheduling task dependence graphs with variable task execution times onto heterogeneous multiprocessors, In Proceedings of the 8th ACM international conference on Embedded software.
- S. Baskaran, P. Thambidurai, "Energy efficient real-time scheduling in distributed systems", IJCSI International journal of computer science issues, 2010.
- S. Jin, G. Schiavone • D. Turgut, "A performance study of multiprocessor task scheduling algorithms", Journal of Supercomputer, 2008.
- W. Y. Lee, "Energy-Efficient Scheduling of Periodic Real-Time Taks on Lightly Loaded Multicore Processors", IEEE Transactions on Parallel and Distributed Systems, 2012.
- W. Y. Lee, S. J. Hong, J. Kim, "On-line scheduling of scalable real-time tasks on multiprocessor systems", Journal of Parallel and Distributed Computing, 2003.
- X. Lin, A. Mamat, Y. Lu, J. Deogun, S. Goddard , "Real-time scheduling of divisible loads in cluster computing environments", International Journal of Parallel and Distributed Computing, Elsevier, 2010.
- X. Zhu, X. Qin, M. Qiu, "QoS- Aware fault-Tolerant Scheduling for Real Time Tasks on Heterogeneous clusters" IEEE transactions on Computers, 2011.
- X. Zhu, C. He, K. Li, X. Kin, "Adaptive energy-efficient scheduling for real-time tasks on DVS-enabled heterogeneous clusters" , Journal of parallel and distributed computing, 2012.
- Zhu, X. , Zhu, J. , Ma, M. , Qiu, D. , 2010 ,SAQA: A self adaptive QoS-aware Scheduling Algorithms for Real Time Tasks on Heterogeneous Clusters, In Proceedings of the 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing.
Index Terms
Keywords