## Abstract

Every task in a real-time system has a deadline by which time it should complete and a vaJue that it obtains only if it completes by its deadline. The problem is to design an on-line scheduling algorithm (i.e., the scheduler has no knowledge of a task until it is released) that maximizes the obtained value. When such a system is underloaded (i.e. there exists a schedule for which all tasks meet their deadlines), Dertouzos showed that the earliest deadline first algorithm will achieve 100% of the possible value. Locke showed that earliest deadline first performs very badly when the system is overloaded and proposed heuristics to deal with overload. Baruah et al. showed that the best that an on-line algorithm can guarantee is 1/(1+k)^{2} of the value that an off-line (clairvoyant) algorithm can obtain where k is the ratio between the highest value density and the lowest value density task in the system (where the value density of a task is its value divided by its computation time). We present an on-line algorithm that achieves the above best possible guarantee in this model. This algorithm also obtains 100% of the possible value when the system is underloaded.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - Real-Time Systems Symposium, RTSS 1992 |

Pages | 290-299 |

Number of pages | 10 |

DOIs | |

State | Published - 1992 |

Event | 1992 Real-Time Systems Symposium, RTSS 1992 - Phoenix, AZ, United States Duration: Dec 2 1992 → Dec 4 1992 |

### Publication series

Name | Proceedings - Real-Time Systems Symposium |
---|---|

ISSN (Print) | 1052-8725 |

### Other

Other | 1992 Real-Time Systems Symposium, RTSS 1992 |
---|---|

Country/Territory | United States |

City | Phoenix, AZ |

Period | 12/2/92 → 12/4/92 |

## ASJC Scopus subject areas

- Software
- Hardware and Architecture
- Computer Networks and Communications

## Fingerprint

Dive into the research topics of 'D^{over}: An optimal on-line scheduling algorithm for overloaded real-time systems'. Together they form a unique fingerprint.