• DocumentCode
    3347857
  • Title

    Dover; an optimal on-line scheduling algorithm for overloaded real-time systems

  • Author

    Koren, Gilad ; Shasha, Dennis

  • Author_Institution
    Courant Inst., New York Univ., NY, USA
  • fYear
    1992
  • fDate
    2-4 Dec 1992
  • Firstpage
    290
  • Lastpage
    299
  • Abstract
    An optimal online scheduling algorithm for overloaded systems is presented. It is optimal in the sense that it gives the best competitive factor possible relative to an offline (i.e., clairvoyant) scheduler. It also gives 100% of the value of a clairvoyant scheduler when the system is underloaded. In fact the performance guarantee of Dover is even stronger: Dover schedules to completion all tasks in underloaded periods and achieves at least 1/(1+√k)2 of the value a clairvoyant algorithm can get during overloaded periods. The model accounts for different value densities and generalizes to soft deadlines
  • Keywords
    fault tolerant computing; performance evaluation; real-time systems; scheduling; Dover; clairvoyant scheduler; optimal on-line scheduling algorithm; overloaded real-time systems; soft deadlines; Algorithm design and analysis; Optimal scheduling; Real time systems; Scheduling algorithm;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Real-Time Systems Symposium, 1992
  • Conference_Location
    Phoenix, AZ
  • Print_ISBN
    0-8186-3195-3
  • Type

    conf

  • DOI
    10.1109/REAL.1992.242650
  • Filename
    242650
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3347857