Name
Abstract | ||
|---|---|---|
The analysis of multiprocessor scheduling strategies has been the focus of substantial research in recent years. Because of the inherent complexity of the general scheduling problem, many researchers have proposed simple mathematical models of computing systems and analyzed the worst-case performance bounds of heuristic scheduling algorithms. This paper presents the analysis of simple scheduling strategies on a model of a computer system with an arbitrary number of identical but independent processors each with a possibly different storage capacity. Most simple strategies are shown to be unattractive as the bound on their worst-case behavior increases without limit. However, two strategies are presented with worst-case bounds asymptotically approaching 2. In addition, if the system has a preemptive-resume feature, a simple optimal strategy exists that will produce minimal-length schedules for any given task set. |
Year | DOI | Venue |
|---|---|---|
1974 | 10.1145/800182.810397 | ACM Annual Conference |
Keywords | Field | DocType |
general scheduling problem,simple strategy,minimizing completion time,worst-case performance bound,simple optimal strategy,different storage capacity,scheduling algorithms,deterministic scheduling models,multiprocessor scheduling strategy,simple mathematical model,simple scheduling strategy,independent processor,worst-case behavior increase,heuristic scheduling algorithm,worst-case bound,scheduling problem,scheduling algorithm,multiprocessor scheduling,mathematical model | Fixed-priority pre-emptive scheduling,Mathematical optimization,Multiprocessor scheduling,Fair-share scheduling,Computer science,Gang scheduling,Two-level scheduling,Rate-monotonic scheduling,Dynamic priority scheduling,Round-robin scheduling,Distributed computing | Conference |
Citations | PageRank | References |
4 | 2.19 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| dennis kafura | 1 | 78 | 10.01 |
| V. Y. Shen | 2 | 293 | 50.74 |