主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2019-2020年专刊出版计划 微信服务介绍 最新一期:2019年第2期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
金宏,王宏安,王强,戴国忠.改进的最小空闲时间优先调度算法.软件学报,2004,15(8):1116-1123
改进的最小空闲时间优先调度算法
An Improved Least-Slack-First Scheduling Algorithm
投稿时间:2003-05-15  修订日期:2003-09-26
DOI:
中文关键词:  调度  实时操作系统  颠簸  抢占阈值  截止期错失率
英文关键词:scheduling  real-time operating system  thrashing  preemption threshold  missed deadline percentage
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60374058, 60373055 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2001AA413020 (国家高技术研究发展计划(863))
作者单位
金宏 中国科学院,软件研究所,人机交互技术与智能信息处理实验室,北京,100080 
王宏安 中国科学院,软件研究所,人机交互技术与智能信息处理实验室,北京,100080 
王强 中国科学院,软件研究所,人机交互技术与智能信息处理实验室,北京,100080 
戴国忠 中国科学院,软件研究所,人机交互技术与智能信息处理实验室,北京,100080 
摘要点击次数: 3474
全文下载次数: 3956
中文摘要:
      最小空闲时间优先(least slack first,简称LSF)算法结合任务执行的缓急程度来给任务分配优先级.任务所剩的空闲时间越少,就越需要尽快执行.然而,LSF算法造成任务之间的频繁切换或严重的颠簸现象,增大了系统开销,并限制了其应用.在调度策略中设置抢占阈值可以减少任务之间的切换,但现有的抢占阈值设置方法因受到固定优先级的限制而不适用于LSF算法.为了减轻LSF算法的颠簸现象,基于抢占阈值的思想,提出适用于LSF算法的抢占阈值分配方法,动态地给每个任务配置抢占阈值.任务的抢占阈值是随着任务执行的缓急程度不同而动态地变化的,而且不受任务个数的限制.仿真结果表明,通过对LSF算法的改进,任务之间的切换大大减少,同时降低了任务截止期错失率.该改进型算法对设计和实现实时操作系统具有一定的参考价值.
英文摘要:
      The LSF (least slack first) algorithm assigns a priority to a task according to its executing urgency. The smaller the remaining slack time of a task is, the sooner it needs to be executed. However, LSF may frequently cause switching or serious thrashing among tasks, which augments the overhead of a system and restricts its application. Assigning a preemption threshold in the scheduling policy can decrease the switching among tasks, however, the existing assigning methods are limited to the fixed priority such that they are not applied to the LSF algorithm. In order to relieve the thrashing caused by LSF, some applicable assigning schemes are presented to the LSF algorithm based on the preemption threshold. Every task is dynamically assigned a preemption threshold that is dynamically changing with the executing urgency of the task and is not limited by the number of tasks. Simulations show that, by using the improved LSF policy, the switching among tasks decreases greatly while the missed deadline percentage decreases. The proposed algorithm is useful for designing and implementing a real-time operating system.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

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