Improved competitive algorithms for two-processor real-time systems

被引：2
|
作者：
Leung, JYT [1 ]
机构：
[1] New Jersey Inst Technol, Dept Comp Sci, Newark, NJ 07012 USA
来源：
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2004年 / 15卷 / 05期
关键词：
real-time systems; parallel and identical processors; uniform processors; competitive on-line scheduling; preemptive scheduling; migration;
D O I：
10.1142/S0129054104002728
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The problem of competitive on-line scheduling in two-processor real-time environments is studied. The model of Koren and Shasha is followed: Every task has a deadline and a value that it obtains only if it completes by its deadline - the value being its computation time. The goal is to design, on-line schedulers with worst-case guarantees compared with a clairvoyant scheduler. Koren and Shasha gave algorithms for the migration and no-migration models, with competitive multipliers of 2 and 3, respectively. In this article, we give an algorithm for the no-migration model with an improved competitive multiplier of 2(1 + 1/root6). We also show that the competitive multiplier for the migration model can be lowered by using a fast processor and a slow processor, compared with using several parallel and identical processors with the same aggregate computing power.
引用
收藏
页码：733 / 751
页数：19
相关论文
共 50 条
  • [41] Testing real-time systems using genetic algorithms
    Wegener, J
    Sthamer, H
    Jones, BF
    Eyres, DE
    SOFTWARE QUALITY JOURNAL, 1997, 6 (02) : 127 - 135
  • [42] SCHEDULING ALGORITHMS FOR COALESCED JOBS IN REAL-TIME SYSTEMS
    CHEN, MI
    CHUNG, JY
    LIN, KJ
    PROCEEDINGS : THE THIRTEENTH ANNUAL INTERNATIONAL COMPUTER SOFTWARE & APPLICATIONS CONFERENCE, 1989, : 143 - 150
  • [43] Testing real-time systems using genetic algorithms
    Wegener, J
    Sthamer, H
    Jones, BF
    Eyres, DE
    SOFTWARE QUALITY MANAGEMENT V: THE QUALITY CHALLENGE, 1997, : 259 - 268
  • [44] Efficient real-time scheduling algorithms for multiprocessor systems
    Cho, S
    Lee, SK
    Ahn, S
    Lin, KJ
    IEICE TRANSACTIONS ON COMMUNICATIONS, 2002, E85B (12) : 2859 - 2867
  • [45] Anytime control algorithms for embedded real-time systems
    Fontanelli, Daniele
    Greco, Luca
    Bicchi, Antonio
    HYBRID SYSTEMS: COMPUTATION AND CONTROL, 2008, 4981 : 158 - 171
  • [46] Efficient scheduling algorithms for real-time multiprocessor systems
    Ramamritham, Krithi
    Stankovic, John A.
    Shiah, Perng-Fei
    IEEE Transactions on Parallel and Distributed Systems, 1990, 1 (02) : 184 - 194
  • [47] INCORPORATING UNBOUNDED ALGORITHMS INTO PREDICTABLE REAL-TIME SYSTEMS
    AUDSLEY, NC
    BURNS, A
    RICHARDSON, MF
    WELLINGS, AJ
    COMPUTING SYSTEMS, 1993, 8 (02): : 80 - 89
  • [48] CONCURRENCY-CONTROL ALGORITHMS FOR REAL-TIME SYSTEMS
    NAKAZATO, H
    LIN, KJ
    MICROPROCESSING AND MICROPROGRAMMING, 1993, 38 (1-5): : 647 - 654
  • [49] Stress testing real-time systems with genetic algorithms
    Briand, Lionel C.
    Labiche, Yvan
    Shousha, Marwa
    GECCO 2005: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOLS 1 AND 2, 2005, : 1021 - 1028
  • [50] ALGORITHMS FOR CONTROL OF COMPUTATIONAL SYSTEMS IN STRICT REAL-TIME
    BULANZHE, DY
    SUSHKOV, BG
    ENGINEERING CYBERNETICS, 1982, 20 (06): : 88 - 95
12345