主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第8期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
王 健,孙建伶,王新宇,杨小虎,王申康,陈俊波.容错多处理机中一种高效的实时调度算法.软件学报,2009,20(10):2628-2636
容错多处理机中一种高效的实时调度算法
Efficient Scheduling Algorithm for Hard Real-Time Tasks in Primary-Backup Based Multiprocessor Systems
投稿时间:2008-07-11  修订日期:2009-01-14
DOI:
中文关键词:  硬实时  主副版本  容错  调度算法  多处理机  周期任务
英文关键词:hard real-time  primary-backup  fault-tolerant  scheduling algorithm  multiprocessor  periodic task
基金项目:
作者单位
王 健 浙江大学 计算机科学与技术学院,浙江 杭州 310027 
孙建伶  
王新宇  
杨小虎  
王申康  
陈俊波  
摘要点击次数: 2874
全文下载次数: 3752
中文摘要:
      针对基于主副版本容错的多处理机中独立的、抢占性的硬实时任务,提出了一种高效的调度算法——TPFTRM(task partition based fault tolerant rate-monotonic)算法.该算法将单机实时RM 算法扩展到容错多处理机上,并且调度过程中从不使用主动执行的任务副版本,而仅使用被动执行和主副重叠方式执行的任务副版本,从而最大限度地利用副版本重叠和分离技术提高了算法调度性能.此外,TPFTRM 根据任务负载不同将任务集合划分成两个不相交的子集进行分配;还根据处理机调度的任务版本不同,将处理机集合划分成3 个不相交的子集进行调度,从而使TPFTRM 调度算法便于理解、实现以及减少了调度所需要的运行时间.模拟实验对各种具有不同周期和任务负载的任务集合进行了调度测试.实验结果表明,TPFTRM与目前所知同类算法相比,在调度相同参数的任务集合时不仅明显减少了调度所需要的处理机数目,还减少了调度所需要的运行时间,从而证实了TPFTRM 算法的高效性.
英文摘要:
      This paper has considered the problem of preemptively scheduling a set of independent periodic hard real-time tasks in primary-backup based multiprocessor systems. An efficient scheduling algorithm—Task Partition based Fault Tolerant Rate-Monotonic (TPFTRM) is proposed which extends RM algorithm to primary-backup based multiprocessor to provide fault tolerance. Compared with previous scheduling algorithms in this area, TPFTRM abandons active backup copies and only uses passive and overlapping backup copies to maximize the backup over-booking and deallocation, thus improves the scheduling performance. Moreover, TPFTRM proposes the task partitioning and processors grouping technique, which reduce the scheduling computation time and also make an easy way to understand and implement it. Extensive simulations experiments are also carried out based on task sets with different parameters. And the simulation result shows a remarkable saving of processors as well as scheduling computation time compared with previous algorithms, which proves the feasibility and effectiveness of the oposed TPFTRM algorithm.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利