Smooth scheduling under variable rates or the analog-digital confinement game

ABSTRACT

This work considers non-terminating scheduling problems in which a system of multiple resources serves clients having variable needs. The system has m identical resources and n clients; in each time slot each resource may serve at most one client; in each such slot t each client γ has a rate, a real number ρ_γ(t), that specifies his needs in this slot. The rates satisfy the restriction Ε_γρ_γ(t) ≤ m for any slot t. Except of this restriction, the rates can vary in arbitrary fashion. (This contrasts most prior works in this area in which the rates of the clients are constant.) The schedule is required to be smooth as follows: a schedule is Δ-smooth if for all time intervals I the absolute difference between the amount of service received by each client γ to his nominal needs of Ε_t∈I ρ_γ(t) is less than Δ. Our objective are online schedulers that produce Δ-smooth schedules where Δ is a small constant which is independent of m and n.Our paper constructs such schedulers; these are the first online Δ-smooth schedulers, with a constant Δ, for clients with arbitrarily variable rates in a single or multiple resource system. Furthermore, the paper also considers a non-concurrent environment in which there is an additional restriction that each client is served at most once in each time slot; it presents the first online smooth schedulers for variable rates under this restriction.The above non-concurrent restriction is crucial in some applications (e.g., CPU scheduling). It has been pointed out that this restriction "adds a surprising amount of difficulty" to the scheduling problem. However, this observation was never formalized and, of course, was never proved. This paper formalizes and proves some aspects of this observation.Another contribution of this paper is the introduction of a complete information, two player game called the analog-digital confinement game. In such a game pebbles are located on the real line; the two players, the analog player and the digital player, take alternating turns and each one, in his turn, moves some of the pebbles; the digital player moves the pebbles backwards by discrete distances while the analog player moves the pebbles forward by analog distances; the aim of the analog player is to cause one pebble (or more) to escape a pre-defined real interval while the aim of the digital player is to confine the pebbles into the interval. This game is a convenient framework to study the general question of how to approximate an analog process by a digital one. All the above scheduling results are established via this game. In this derivation, the pebbles represent the clients, the analog player represents the needs of the clients and the digital player represents the scheduler.

REFERENCES

• 1: Micah Adler , Petra Berenbrink , Tom Friedetzky , Leslie Ann Goldberg , Paul Goldberg , Mike Paterson, A proportionate fair scheduling rule with good worst-case performance, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777430]
• 2: Matthew Andrews , Antonio Fernández , Mor Harchol-Balter , Tom Leighton , Lisa Zhang, General Dynamic Routing with Per-Packet Delay Guarantees of O(Distance + 1/Session Rate), SIAM Journal on Computing, v.30 n.5, p.1594-1623, 2000 [doi>10.1137/S009753979935061X]
• 3: Amotz Bar-Noy , Aviv Nisgav , Boaz Patt-Shamir, Nearly optimal perfectly-periodic schedules, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.107-116, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383998]
• 4: S. K. Baruah , N. K. Cohen , C. G. Plaxton , D. A. Varvel, Proportionate progress: a notion of fairness in resource allocation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.345-354, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167194]
• 5: Sanjoy K. Baruah , Johannes Gehrke , C. Greg Plaxton, Fast scheduling of periodic tasks on multiple resources, Proceedings of the 9th International Symposium on Parallel Processing, p.280-288, April 25-28, 1995
• 6: S. K. Baruah, J. Gehrke, G. Plax ton, I. Stoica, H. Abdel-Wahab, and K. Jeffay. Fair on-line scheduling of a dynamic set of tasks on a single resource. Information Processing Letters, 64(1):43--51, 1997.
• 7: A. Litman and S. Moran-Schein. Smooth scheduling under variable rates or the analog-digital confinement game. This is the full version of this extended abstract; available at: www.cs.technion.ac.il /users/wwwb/cgibin/tr-info.cgi?2006/CS/CS-2006-13.
• 8: A. Litman and S. Moran-Schein. On centralized smooth scheduling. Technical Report CS-2005-04, Department of Computer Science, Technion - Israel Institute of Technology, 2005. Available at: www.cs.technion.ac.il/users/wwwb/cgi-bin/trinfo. cgi?2005/CS/CS-2005-04.
• 9: Ami Litman , Shiri Moran-Schein, On distributed smooth scheduling, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073982]
• 10: A. Litman and S. Moran-Schein. On smooth sets of integers. Technical Report CS-2005-02, Department of Computer Science, Technion - Israel Institute of Technology, 2005. Available at: www.cs.technion.ac.il/users/wwwb/cgi-bin/trinfo. cgi?2005/CS/CS-2005-02.
• 11: C. L. Liu. Scheduling algorithms for multiprocessors in hard-real-time enviroment. JPL space program summary 37-60, vol. II, Propulsion Lab., Calif. Inst. of Tech., Pasadena, CA, pages 28--37, 1969.
• 12: Mark Moir , Srikanth Ramamurthy, Pfair Scheduling of Fixed and Migrating Periodic Tasks on Multiple Resources, Proceedings of the 20th IEEE Real-Time Systems Symposium, p.294, December 01-03, 1999
• 13: G. Moran. Size direction games over the real line ii. Israel Journal of Mathematics, 14:418--441, 1973.
• 14: R. Tijdeman. The chairman assignment problem. Discrete Mathematics, 32:323--330, 1980.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms

Keywords:
EDF schemes, EDF strategies, concurrent confinement games, confinement games, non-concurrent confinement games, online scheduling, smooth scheduling, two players games, variable rates