Nonclairvoyant scheduling.

*(English)*Zbl 0820.90056Summary: Virtually all research in scheduling theory has been concerned with clairvoyant scheduling where it is assumed that the characteristics of a job (in particular, its execution time, release time and dependence on other jobs) are known a priori. This assumption is invalid for scheduling problems that arise in time-sharing operating systems where the schedular must provide fast turnaround for processes being generated by the users without any knowledge of the future behavior of these processes.

We study preemptive, nonclairvoyant scheduling schemes where the schedular has no knowledge of the jobs’ characteristics. We develop a model for evaluating scheduling strategies for single and multiprocessor systems. This model compares the nonclairvoyant schedular against the optimal clairvoyant schedular, and it takes into account various issues such as release time, execution time, preemption cost, and the inter- dependence between jobs. Within this model we study some standard scheduling algorithms described in the systems literature, and we provide some theoretical justification for their effectiveness in practice by presenting some randomized and deterministic upper and lower bounds.

We study preemptive, nonclairvoyant scheduling schemes where the schedular has no knowledge of the jobs’ characteristics. We develop a model for evaluating scheduling strategies for single and multiprocessor systems. This model compares the nonclairvoyant schedular against the optimal clairvoyant schedular, and it takes into account various issues such as release time, execution time, preemption cost, and the inter- dependence between jobs. Within this model we study some standard scheduling algorithms described in the systems literature, and we provide some theoretical justification for their effectiveness in practice by presenting some randomized and deterministic upper and lower bounds.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

68W15 | Distributed algorithms |

68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |

##### Keywords:

preemptive, nonclairvoyant scheduling schemes; release time; execution time; preemption cost; inter-dependence between jobs
PDF
BibTeX
XML
Cite

\textit{R. Motwani} et al., Theor. Comput. Sci. 130, No. 1, 17--47 (1994; Zbl 0820.90056)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Awerbuch, B.; Saks, M., A dining philosophers algorithm with polynomial response time, Proc. 30th ACM symp. on foundations of computers science, 65-74, (1990) |

[2] | Bartal, Y.; Fiat, A.; Karloff, H.; Vohra, R., New algorithms for an ancient scheduling problem, Proc. 24th ACM symp. on theory of computing, 51-58, (1992) |

[3] | Chandy, K.; Misra, J., The drinking philosophers problem, ACM toplas, 6, 632-646, (1984) |

[4] | Chernoff, H., A measure of asymptotic efficiency for tests based on the sum of observations, Ann. of math. statist., 23, 493-509, (1952) · Zbl 0048.11804 |

[5] | Coffman, E.G.; Denning, P.J., Operating systems theory, (1973), Prentice-Hall Englewood Cliffs, NJ |

[6] | Conway, R.W.; Maxwell, W.L.; Miller, L.W., Theory of scheduling, (1967), Addison-Wesley Reading, MA · Zbl 1058.90500 |

[7] | Deitel, H.M., An introduction to operating systems, (1990), Addison-Wesley Reading, MA · Zbl 0798.68003 |

[8] | Deitel, H.M.; Kogan, M.S., The design of OS/2, (1992), Addison-Wesley Reading, MA |

[9] | Dijkstra, E.W., Hierarchical ordering of sequential processes, Acta inform., 115-138, (1971) |

[10] | Feldmann, A.; Sgall, J.; Teng, S-H., Dynamic scheduling on parallel machines, Proc. 32nd IEEE symp. on foundations of computer science, 111-120, (1991) |

[11] | Goldberg, R.E.; Kenah, L.J., VAX/VMS internals and data structures, (1991), Digital Press Bedford, MA |

[12] | Graham, R.L., Bounds on multiprocessing anomalies, SIAM J. appl. math., 17, 263-269, (1969) · Zbl 0188.23101 |

[13] | Kleinrock, L., Queuing systems, vol. I: theory and vol. II: computer applications, (1976), Wiley New York |

[14] | Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G.; Shmoys, D.B., Sequencing and scheduling: algorithms and complexity, () · Zbl 0482.68035 |

[15] | Lazowska, E.D.; Zahorjan, J.; Graham, G.C.; Sevcik, K.C., Quantitative system performance, (1984), Prentice-Hall Englewood Cliffs, NJ |

[16] | Lovasz, L.; Saks, M.; Trotter, W.T., An online graph coloring algorithm with sublinear performance ratio, Discrete math., 75, 319-325, (1989) · Zbl 0679.05031 |

[17] | Lundelius, J.; Lynch, N., Synthesis of efficient drinking philosophers algorithms, (1988), unpublished manuscript |

[18] | Lynch, N., Upper bounds for static resource allocation in a distributed system, J. comput. system sci., 23, 254-278, (1981) · Zbl 0473.68022 |

[19] | McNaughton, R., Scheduling with deadlines and loss functions, Management sci., 6, 1-12, (1959) · Zbl 1047.90504 |

[20] | Motwani, R.; Phillips, S.; Torng, E., Non-clairvoyant scheduling, Proc. 4th ACM-SIAM symp. on discrete algorithms, 422-431, (1993) · Zbl 0801.68013 |

[21] | Peterson, J.L.; Silberschatz, A., Operating systems concepts, (1985), Addison-Wesley Reading, MA |

[22] | Rabin, M.; Lehmann, D., On the advantages of free choice: a symmetric and fully distributed solution to the dining philosophers problem, Proc. 8th ACM symp. POPL, 133-138, (1981) |

[23] | Shmoys, D.B.; Wein, J.; Williamson, D.P., Scheduling parallel machines on-line, Proc. 32nd IEEE symp. on foundations of computer science, 131-140, (1991) |

[24] | Sleator, D.D.; Tarjan, R.E., Amortized efficiency of List update and paging rules, Cacm, 28, 202-208, (1985) |

[25] | Smith, W.E., Various optimizers for single-stage production, Naval res. logist. quart., 3, 59-66, (1956) |

[26] | Styer, E.; Peterson, G., Improved algorithms for distributed resource allocation, Proc. 7th ACM symp. on principles of distributed computing, 105-116, (1988) |

[27] | Tanenbaum, A.S., Modern operating systems, (1992), Prentice-Hall Englewood Cliffs · Zbl 0856.68041 |

[28] | Tanenbaum, A.S.; van Renesse, R., Distributed operating systems, ACM comput. surveys, 17, 419-470, (1985) |

[29] | Vishwanathan, S., Randomized online graph coloring, Proc. 31st IEEE symp. on foundations of computer science, 464-469, (1990) |

[30] | Yao, A.C.-C., Probabilistic computations: towards a unified measure of complexity, Proc. 18th IEEE symp. on foundations of computer science, 222-227, (1977) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.