Introduction

Generalized processor sharing is the name given to a class of problems which look at the best way to share a single processor across multiple program executables.

Aims of the GPS Algorithm.

The solutions to these problems look to create a processing schedule or 'discipline', which optimizes one or more of the following criteria:

• Fairness. Fairness refers to the ability of individual programs to get service based on predefined criteria, "independent" of the existence or demand created by other programs.
• Conservation of work refers to a property of a schedule which says that the system should always be busy if there are processes awaiting service. Intuitively obvious though this sounds, there are any number of processes, including Ethernet which fail to provide conservation of work. See Molle94

GPS algorithms in networking

The classic text in Generalized Processor Sharing was written by Abhay Parekh, a research student of Prof. Gallagher. In [Parekh94], Abhay Parekh undertook a rigorous survey of existing scheduling algorithms and studied their fairness and optimality properties. The [WFQ] class of scheduling algorithms which were determined to be GPS compatible, since it could guarantee throughput and delay bounds to individual connections regardless of the state of the entire system. Since then, many more algorithms have been discovered to be GPS compatible. See, for example A Survey of Scheduling Methods

References

[Parekh94], A.K. Parekh and R.G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: Themultiplenodecase.IEEE/ACM Transactions on Networking, 2(2):137--150, April 1994.

[WFQ]A. Demers, S. Keshav, S. Shenker "Analysis and simulation of a fair queueing algorithm", Internet Res. And Exper. Vol.1, 1990

 Create your own educational wiki!Help Add to Del.ici.ous Add to Digg Add to Reddit Add to fUrl Add to SpurlPublic, Platinum wiki Privacy Policy RSS