Decay-Usage Scheduling in Multiprocessor and Distributed Systems. 1: Theory

摘要

Priority aging or decay usage scheduling is a widely used time sharing schedulingpolicy which can deal with a workload of both interactive and batch jobs by degrading the priority of a job when it acquires CPU (Central Processing Unit) time, and by increasing its priority when it does not use the CPU. A decay usage scheduling policy in multiprocessor systems modeled after popular real systems is addressed. The priority of a job consists of a base priority and a time dependent part based on processor usage. Because the priorities in the model are time dependent, a stochastic analysis, for instance for (mean, service time dependent) response times seems impossible. However, a deterministic analysis is feasible. It is shown how for a fixed set of jobs with a very large (infinite) processing demand, the steady state service fractions can be obtained given the base priorities, and conversely, how to set the base priorities given required service fractions. The tradeoffs between multiprocessors, partitioned multiprocessors, and distributed systems are considered.