Proportional allocation of discrete resources using divisor methods of apportionment

• Autorzy: Józefowska J. , Józefowski Ł. , Kubiak W.
• Języki publikacji: EN

Abstrakty

EN

In this paper we propose application of the divisor method of apportioning seats in a parliament to proportionally allocate any kind of discrete resources among competing clients. Motivation for this research comes from the observed similarities between the stride scheduling algorithm, used for scheduling threads in operating systems and the Jefferson method of apportioning seats in a parliament. Based on the theory of apportionment we present also the properties of the proposed method and illustrate it with an example. Analysing the class of divisor methods we focus on the parametric sub-class because it has interesting practical properties and it contains for example the Jefferson method which is the core of some resource allocation algorithms.

Słowa kluczowe

EN

apportionment theory; proportional resource allocation; thread scheduling; divisor methods; Jefferson method

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2007
• Tom: Vol. 32, No. 3
• Strony: 227--237
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Józefowska J.

autor

Józefowski Ł.

autor

Kubiak W.

• Institute of Computing Science, Poznań University of Technology, Poznań, Poland,

Bibliografia

• [1] J.E. Bresenham: Algorithm for computer control of a digital plotter. IBM systems Journal 4, 1, 1965, 25-30.
• [2] M. Balinski. H. Young: Fair Representation. Meeting the Ideal of One Man, One Vote. Yale University Press, 1982.
• [3] M. Balinski, S.T. Rachev: Rounding proportions: methods of roimdhig. Math. Sci. 22, 1997, 1-26.
• [4] M. Balinski. N. Shahidi: A simple approach to the product rate variation problem via axiomatics. Operation Research Letters. 22, 1998. 129-135.
• [5] W. Ginie, K. Marzullo: The Computational Co-op: Gathering Clusters into a Metacompiler. Proceedings of IEEE International Parallel and Distributed Processing Symposium. April 1999,
• [6] A. Arpaci-Dusseau, D. Culler: Extending Proportional-Share Scheduling to a Network of Workstation. Proceedings oj International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA' 97). Las Vegas, Nevada, June 1997.
• [7] W. Kubiak: Fair sequences. In: J. Y-T. Leung, ed. Handbook of Scheduling, Chapman fe Hall/CRC Computer and Information Science Series, 2004.
• [8] C.A. Waldspurger, E.H. Weihl: Stride Scheduling: Deterministic Proportional-Share Resource Mamagement. Technical Memorandum MIT/LCS/TM-528. MIT Laboratory for Computer Science. Cambridge, MA 02139, 1995.
• [9] M. Theimer, K. Landtz, D. Cheriton: Preemptable Remote Execution Facilities for the V System. Proceedings of the 10th ACM Symposium on Operating Systems Principles. December 1985, 2-12.