Decay-usage scheduling in multiprocessors

D.H.J. Epema

    Research output: Contribution to journalArticleAcademicpeer-review

    14 Citations (Scopus)

    Abstract

    Decay-usage scheduling is a priority-aging time-sharing scheduling policy capable of dealing with a workload of both interactive and batch jobs by decreasing the priority of a job when it acquires CPU time, and by increasing its priority when it does not use the (a) CPU. In this article we deal with a decay-usage scheduling policy in multiprocessors modeled after widely used systems. The priority of a job consists of a base priority and a time-dependent component based on processor usage. Because t he priorities in our model are time dependent, a queuing-theoretic analysis—for instance, for the mean job response time—seems impossible. Still, it turns out that as a consequence of the scheduling policy, the shares of the available CPU time obtained by jobs converge, and a deterministic analysis for these shares is feasible: We show how for a fixed set of jobs with large processing demands, the steady-state shares can be obtained given the base priorities, and conversely, how to set the base priorities given the required shares. In addition, we analyze the relation between the values of the scheduler parameters and the level of control it can exercise over the steady-state share ratios, and we deal with the rate of convergence. We validate the model by simulations and by measurements of actual systems.
    Original languageEnglish
    Pages (from-to)367-415
    JournalACM Transactions on Computer Systems
    Volume16
    Issue number4
    DOIs
    Publication statusPublished - 1998

    Fingerprint Dive into the research topics of 'Decay-usage scheduling in multiprocessors'. Together they form a unique fingerprint.

  • Cite this