An Algorithm to Reduce the Time Complexity of Earliest Deadline First Scheduling Algorithm in Real-Time System

被引:0
|
作者
Singh, Jagbeer [1 ]
Patra, Bichitrananda [2 ]
Singh, Satyendra Prasad [3 ,4 ]
机构
[1] Gandhi Inst Engg & Technol, Dept Comp Sci & Engn, Gunupur 765022, India
[2] Gandhi Inst Engg & Tech, Dept Informat Technol, Gunupur 765022, Orissa, India
[3] Gandhi Inst Compt Studies, Dept Master Comp Applicat, Gunupur 765022, Orissa, India
[4] Minist Def, Def Res & Dev Org, New Delhi, India
关键词
Real-time system; task migration; earliest deadline first; earliest feasible deadline first;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
To this paper we have study to Reduce the time Complexity of Earliest Deadline First (EDF), a global scheduling scheme for Earliest Deadline First in Real Time System tasks on a Multiprocessors system. Several admission control algorithms for earliest deadline first are presented, both for hard and soft real-time tasks. The average performance of these admission control algorithms is compared with the performance of known partitioning schemes. We have applied some modification to the global earliest deadline first algorithms to decrease the number of task migration and also to add predictability to its behavior. The Aim of this work is to provide a sensitivity analysis for task deadline context of multiprocessor system by using a new approach of EFDF (Earliest Feasible Deadline First) algorithm. In order to decrease the number of migrations we prevent a job from moving one processor to another processor if it is among the m higher priority jobs. Therefore, a job will continue its execution on the same processor if possible (processor affinity). The result of these comparisons outlines some situations where one scheme is preferable over the other. Partitioning schemes are better suited for hard real-time systems, while a global scheme is preferable for soft real-time systems.
引用
收藏
页码:31 / 37
页数:7
相关论文
共 50 条
  • [41] An LP-Based Algorithm for Scheduling Preemptive and/or Non-Preemptive Real-Time Tasks
    Hashimoto, Hideki
    Yagiura, Mutsunori
    JOURNAL OF ADVANCED MECHANICAL DESIGN SYSTEMS AND MANUFACTURING, 2010, 4 (03): : 578 - 587
  • [42] A fault-tolerant dynamic scheduling algorithm for multiprocessor real-time systems and its analysis
    Manimaran, G
    Murthy, CSR
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1998, 9 (11) : 1137 - 1152
  • [43] A new algorithm to prove the schedulability of real-time systems
    Wang, SH
    Färber, G
    CONTROL ENGINEERING PRACTICE, 2000, 8 (06) : 689 - 695
  • [44] Design and Evaluation of Sectional Real-Time Scheduling Algorithms Based on System Load
    Ding, Wanfu
    Guo, Ruifeng
    PROCEEDINGS OF THE 9TH INTERNATIONAL CONFERENCE FOR YOUNG COMPUTER SCIENTISTS, VOLS 1-5, 2008, : 14 - +
  • [45] An EDF-based restricted-migration scheduling algorithm for multiprocessor soft real-time systems
    Anderson, James H.
    Bud, Vasile
    Devi, UmaMaheswari C.
    REAL-TIME SYSTEMS, 2008, 38 (02) : 85 - 131
  • [46] A Dynamic Scheduling Model for Real-Time Tasks in Reliable System
    Zhang Jie
    Yang Fumin
    Tu Gang
    NSWCTC 2009: INTERNATIONAL CONFERENCE ON NETWORKS SECURITY, WIRELESS COMMUNICATIONS AND TRUSTED COMPUTING, VOL 2, PROCEEDINGS, 2009, : 185 - 188
  • [47] Real Time Streaming Algorithm
    Margarov, Gevorg
    Markosyan, Mher
    Alaverdyan, Yeghisabet
    MEETING SECURITY CHALLENGES THROUGH DATA ANALYTICS AND DECISION SUPPORT, 2016, 47 : 248 - 255
  • [48] DAG-based parallel real time task scheduling algorithm on a cluster
    He, LG
    Han, ZF
    Jin, H
    Pang, LP
    Li, SL
    PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS I-V, 2000, : 437 - 443
  • [49] A Genetic Algorithm based Approach to Maximizing Real-Time System Value under Resource Constraints
    Wang, Li
    Li, Zheng
    Song, Miao
    Ren, Shangping
    2012 IEEE 31ST INTERNATIONAL PERFORMANCE COMPUTING AND COMMUNICATIONS CONFERENCE (IPCCC), 2012, : 285 - 294
  • [50] Storage capacity for EDF-ASAP algorithm in energy-harvesting systems with periodic implicit deadline hard real-time tasks
    Ghadaksaz, Ehsan
    Safari, Saeed
    JOURNAL OF SYSTEMS ARCHITECTURE, 2018, 89 : 10 - 17