A policy-driven scheduler for a time-sharing system

ABSTRACT

The services received by a process from a time-sharing operating system can be characterized by a resource count ∑ wiRij where Rij is the number of units of service received by process j from resource i and wi is the cost per unit of the service. Each class of users can be characterized by a policy function which specifies the amount of service a user who belongs to this class should receive as a function of time. Priority changes dynamically as a function of the difference between the service promised to the user by the policy function and the service he actually receives. A scheduling and swapping algorithm which keeps the resource count of each process above its policy function will provide the specified level of service. Overhead can be reduced by avoiding swaps of processes which have received at least this level of service. The algorithm has been implemented in a general purpose operating system, and it has provided significantly better service to interactive and to batch jobs than the previous scheduler.

REFERENCES

• 1: KERR, R., BERNSTEIN, A., DETLEFSEN, G., AND JOHNSTON, J. Overview of R&DC operating system. TIS Report 69-C-355, General Electric, Oct. 1969.
• 2: A. J. Bernstein , G. D. Detlefsen , R. H. Kerr, Process control and communication, Proceedings of the second symposium on Operating systems principles, October 20-22, 1969, Princeton, New Jersey [doi>10.1145/961053.961078]
• 3: COFFMAN, E., AND KLEINROCK, L. Computer scheduling methods and their countermeasures. Proc. AFIPS 1968 SJCC, Vol. 32, AFIPS Press, Montvale, N. J., pp. 11-21.
• 4: KLEINROCK, L. Time-sharing systems: Analytical methods. In Critical Factors in Data Management, F. Gruenberger (Ed.), Prentice-Hall, Englewood Cliffs, N. J., 1969, pp. 3-32.
• 5: KLEINROCK, L. A continuum of time sharing scheduling algorithms. Proc. AFIPS 1970 SJCC, Vol. 36, AFIPS Press, Montvale, N. J., pp. 453-458.
• 6: DENNING, P. Thrashing: Its causes and prevention. Proc. AFIPS 1968 FJCC, Vol. 33, Pt. 1, AFIPS Press, Montvale, N. J., pp. 915-922.
• 7: Scientific Encyclopedia, 3rd ed. Van Nostrand, Princeton, New Jersey.
• 8: Saul Stimler, Some criteria for time-sharing system performance, Communications of the ACM, v.12 n.1, p.47-53, Jan. 1969 [doi>10.1145/362835.362847]

INDEX TERMS

Keywords:
operating system, resource allocation and swapping, scheduler, time-sharing