首页 | 官方网站   微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 125 毫秒
1.
Rate monotonic and deadline monotonic scheduling are commonly used for periodic real-time task systems. This paper discusses a feasibility decision for a given real-time task system when the system is scheduled by rate monotonic and deadline monotonic scheduling. The time complexity of existing feasibility decision algorithms depends on both the number of tasks and maximum periods or deadlines when the periods and deadlines are integers. This paper presents a new necessary and sufficient condition for a given task system to be feasible and proposes a new feasibility decision algorithm based on that condition. The time complexity of this algorithm depends solely on the number of tasks. This condition can also be applied as a sufficient condition for a task system using priority inheritance protocols to be feasible with rate monotonic and deadline monotonic scheduling.  相似文献   

2.
Neural networks for process scheduling in real-time communicationsystems   总被引:1,自引:0,他引:1  
This paper presents the use of Hopfield-type neural networks for process scheduling in the area of factory automation, where bus-based communication systems, called FieldBuses, are widely used to connect sensors and actuators to the control systems. We show how it overcomes the problem of the computational complexity of the algorithmic solution. The neural model proposed allows several processes to be scheduled simultaneously; the time required is polynomial with respect to the number of processes being scheduled. This feature allows real-time process scheduling and makes it possible for the scheduling table to adapt to changes in process control features. The paper presents the neural model for process scheduling and assesses its computational complexity, pointing out the drastic reduction in the time needed to generate a schedule as compared with the algorithmic scheduling solution. Finally, the authors propose an on-line scheduling strategy based on the neural model which can achieve real-time adaptation of the scheduling table to changes in the manufacturing environment.  相似文献   

3.
对于具有相关性的任务,调度顺序不合理将影响任务的执行时间和实时性。结合物联网终端任务间依赖关系复杂的特点提出了一种利用任务相关性的调度策略。该策略设计了以作业轮询组为主体的任务模型,根据任务时限建立了优先级因子矩阵作为任务调度的凭据,对于周期任务,在每个任务执行完毕后生成,以任务相关性为参数的增量矩阵用以动态修改任务优先级,使前驱任务能优先执行;对于非周期任务采用了构建临时作业轮询组的方式进行抢占调度。测试结果表明,该策略能够有效减少具有相关性的周期任务集执行时间和调度失败次数,缩短非周期任务响应时间。  相似文献   

4.
檀明 《计算机工程与科学》2015,37(10):1862-1868
针对FTT-SE协议在单Master多交换机的网络扩展结构中存在的消息跨多Switch传输调度问题,给出了消息在每个基本调度周期内到达各交换机输出端口时间的计算方法,提出了单EC内的消息可调度性判定算法,并对算法的可行性进行了证明。在此基础上,设计了基于EDF的消息实时调度算法和准入控制算法。通过确定消息在每个基本调度周期内到达各交换机输出端口时间,所提出的调度算法能针对COTS交换机输出端口的FCFS消息传输机制,实现对单EC内消息传输的精确控制和调度。相对已有的调度算法,仿真实验表明,所提出的算法能更有效地利用网络带宽,提高了主从交换式以太网通信的实时性。  相似文献   

5.
一种双匹配动态调度算法   总被引:6,自引:0,他引:6  
支青  蒋昌俊 《信息与控制》2005,34(5):532-538
提出了适于异构环境独立任务调度的双匹配动态调度算法(BM算法).BM算法将任务与处理机实现双匹配,使大部分任务在执行时间最短而且完成时间最早的处理机上执行.对于无法实现双匹配的任务,采用最早完成时间最小者优先的策略进行调度.BM算法可以同时满足负载均衡和高吞吐率两个目标.BM算法与通常用作评测基准的Min-min算法的比较结果表明,BM算法的运行时间远少于Min-min算法,其调度跨度比Min-min算法减少约9%.  相似文献   

6.
Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems   总被引:1,自引:3,他引:1  
The utilization bound for earliest deadline first (EDF) scheduling is extended from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. Since the multiprocessor utilization bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms. As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account. Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing, release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches, and mode changes.  相似文献   

7.
在建立的区分服务网络模型的基础上,提出一种针对实时变比特率突发业务的调度算法,称为加权开关赤字轮循(weighted switch deficit round robin,WSDRR)算法.根据不同的队列等级分配加权的带宽,并根据队列中分组状况动态调节服务量.该策略是针对网络拥塞下传输实时突发视频业务而提出的.基于一种吞吐量公平测度的比较,WSDRR算法与传统赤字轮循DRR算法具备相同的公平性.实验结果表明,与DRR算法相比,WSDRR算法能够降低实时突发视频业务的端对端延时和延时抖动,从而进一步使实时视频传输的要求得到满足.  相似文献   

8.
We consider a single-machine scheduling problem with periodic maintenance activities. Although the scheduling problem with maintenance has attracted researchers’ attention, most of past studies considered only one maintenance period. In this research several maintenance periods are considered where each maintenance activity is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the makespan, subject to periodic maintenance and nonresumable jobs. We first prove that the worst-case ratio of the classical LPT   algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case ratio less than 2 unless P=NPP=NP, which implies that the LPT algorithm is the best possible.  相似文献   

9.
分析了DeltaOS的设备驱动基本框架,设计实现了多通道PMC-CAN驱动程序。针对DeltaOS实时多任务的特点,基于看门狗定时器方法,有效简化了多任务环境下周期任务轮询程序的设计;设计了一种多通道中断处理的方法,提高了多通道数据传输效率及通道利用率;针对多个CAN通道的调度提出了一种基于动态调度表的调度方法;通过实验验证了CAN驱动的正确性及多通道调度的有效性。  相似文献   

10.
一种求解异构DAG调度问题的置换蚁群   总被引:1,自引:1,他引:0  
邓蓉  陈闳中  王博  王小明  李灿 《计算机科学》2010,37(12):193-196
减少分布式程序的执行时间,是网格调度系统需要解决的重要问题。因分布式程序常建模为DAG图,故该问题又称异构DAG调度问题。提出的置换调度蚁群PSACS(Permutation Scheduling Ant Colony System)将DAG调度方案表示为任务置换列表,使用标准蚁群搜索技术探索解空间。实验表明,该算法明显优于遗传算法和粒子群算法,能够一次求出大部分(65%)同构DAG调度问题的最优解并获得非常好的异构DAG调度方案。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号