JAIST Repository
https://dspace.jaist.ac.jp/Title

Hybrid Overloading and Fault Tolerant Task
Scheduling in Multiprocessor systems Based onPrimary and Backup SchemeAuthor(s)Sun, Wei

CitationIssue Date

2008‑03‑04

TypeConference Paper

Text version

publisher

URL

http://hdl.handle.net/10119/8242

RightsDescription

JAIST 21世紀COEシンポジウム2008「検証進化可能電子社会」= JAIST 21st Century COE Symposium 2008
Verifiable and Evolvable e‑Society, 開催：2008年
3月3日〜4日, 開催場所：北陸先端科学技術大学院大学, GRP研究員発表会 セッションC‑1発表資料

Japan Advanced Institute of Science and TechnologyHybrid Overloading and Fault Tolerant Task Scheduling inMultiprocessor systems Based on Primary and Backup Scheme
Wei SunD3 student, Inoguchi Lab
sun-wei@jaist.ac.jp

Aim of researchWith multiprocessor systems, redundant scheduling is a technique that trades processing power forincreased reliability through redundancy. One approach, called primary-backup task scheduling, isoften used in real-time multiprocessor systems to guarantee the deadlines of tasks in site of faults.
Briefly, it consists in scheduling a secondary task conditionally in such a way that the secondary task is
actually executed only if the primary task (or the processor executing it) fails to terminate properly.
Doing so avoids wasting CPU resources in the failure-free case, but the difficulty comes from the factthat primary and secondary tasks must compete for resources in case of failure. To address this point,
overloading strategies, such as primary and backup overloading (PB) and backup-backup overloading(BB), were developed to improve schedulability while retaining a certain degree of reliability. The aimof our research is to develop a good tradeoff between PB overloading and BB overloading. Then, wewill use the new overloading technique to develop a new fault tolerance task scheduling approach.

Idea, approach, and progress
Real-time multiprocessor systems are defined as those systems in which the correctness of systems
depends on not only the logical result of computation but also the time at which the results areproduced. Thus, it is essential that tasks are completed before their deadlines even in the presence ofprocessor failures. This makes fault tolerance an inherent requirement of real-time systems. In a
multiprocessor system, fault tolerance can be provided by scheduling multiple copies of tasks on
different processors. Primary-backup technique is one of fault tolerant scheduling techniques. In thePB-based task scheduling two versions of a task, primary version and backup version, are scheduled on
two different processors and the acceptance test is used to check the correctness of the execution results.
In order to improve the schedulability, overloading techniques are often used. PB overloadingschedules the primary of a task onto the same or overlapping time slot with the backup of another task
on a processor. BB overloading schedules the backups of multiple tasks onto the same or overlapping
time slot on a processor. R. Al-Omari et al. drew a conclusion that the PB overloading is able toachieve better performance than BB overloading, and BB overloading strategy is better thannon-overloading strategy.
We proposed a hybrid overloading technique, based on extended PB overloading [6]. In short, hybrid
overloading is a new technique which combines the advantages of both PB and BB overloading. All
three overloading strategies are compared through a stochastic analysis, as well as by simulating themunder diverse system conditions. The performance analysis shows that hybrid overloading provides anexcellent tradeoff between schedulability and reliability. We also proposed a dynamic PB-based taskscheduling approach [2, 5], wherein an allocation parameter is used to search the available time slots
for a newly arriving task, and the previously scheduled tasks can be rescheduled when there is noavailable time slot for the newly arriving task.

1Our proposed task scheduling algorithm is compared with some existing scheduling algorithms in theliterature through simulation studies. The results have shown that the task rejection ratio of ourreal-time task scheduling algorithm is lower than the compared algorithms.

Future Direction
The theoretical analysis can prove the advantage of hybrid overloading. In the future work, the detailed
Markov model will be produced based on the results in 2007. Moreover, the analysis method in ourpublications and the Markov model can be used to evaluate more fault tolerance technologies. For
example, a primary can have two or more backups to tolerate more faults. Thus, the overloading chain
will be evolved to overloading tree.

Publications:[1]W. Sun and Y. Inoguchi: “Time Constrained Job Admission and Scheduling in Service OrientedGrid,” J. Future Generation Computer Systems, submitted for the second review.
[2]W. Sun, C. Yu, X. Défago and Y. Inoguchi: “Dynamic Scheduling Real-time Task Using
Primary-backup Overloading Strategy for Multiprocessor Systems," IEICE Trans. Information andSystems, Vol.E91-D, No.3, 2008.
[3]Y. Zhang, W. Sun, Y. Inoguchi: “Predicting Task Running Time in Grid Environment Based on CPU
Load Predictions," J. Future Generation Computer Systems, pp.95-102, 2007.
[4]W. Sun and Y. Inoguchi: “Optimizing Average Response Time for Task Flow in Heterogeneous
Systems," HPSRN 2008, accepted.
[5]W. Sun, C. Yu, X. Défago and Y. Inoguchi: “Real-time Task Scheduling Using Extended
Overloading Technique for Multiprocessor Systems," 11th IEEE Int'l Symp. Distributed Simulation
and Real Time Applications (DSRT), pp.95-102, 2007. Nominated for the best paper award.
[6]W. Sun, C. Yu, X. Défago and Y. Inoguchi: “Hybrid Overloading and Stochastic Analysis for
Redundant Scheduling in Real-time Multiprocessor Systems," 26th IEEE Int'l Symp. Reliable
Distributed Systems (SRDS), pp.265-274, 2007.

2