Storage Requirements for Fair Scheduling.

Abstract

A scheduler is strongly fair if each process which requests service infinitely often is served infinitely often, and it is weakly fair if each process which requests service all but finitely often is served infinitely often. We show that any strongly fair scheduling algorithm for n processes requires at least n! storage states (i.e., space proportional to n log n). Similarly, and weakly fair scheduling algorithm requires at least n storage states. Both bounds are optimal. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1982
Accession Number
ADA121313

Entities

People

  • Michael J. Fischer
  • Michael S. Paterson

Organizations

  • Yale University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Connecticut
  • Contracts
  • Information Systems
  • Marine Corps
  • Mathematical Analysis
  • Mathematics
  • Military Research
  • Numbers
  • Program Management
  • Scheduling (Production)
  • Technical Information Centers
  • Universities

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Government Contracting/Procurement.
  • Plasma Physics / Magnetohydrodynamics

Technology Areas

  • Space
  • Space - Space Objects