Performance Evaluation of a Limited Round-Robin System

Authors: Yoshiaki Shikata

Abstract:

Performance of a limited Round-Robin (RR) rule is studied in order to clarify the characteristics of a realistic sharing model of a processor. Under the limited RR rule, the processor allocates to each request a fixed amount of time, called a quantum, in a fixed order. The sum of the requests being allocated these quanta is kept below a fixed value. Arriving requests that cannot be allocated quanta because of such a restriction are queued or rejected. Practical performance measures, such as the relationship between the mean sojourn time, the mean number of requests, or the loss probability and the quantum size are evaluated via simulation. In the evaluation, the requested service time of an arriving request is converted into a quantum number. One of these quanta is included in an RR cycle, which means a series of quanta allocated to each request in a fixed order. The service time of the arriving request can be evaluated using the number of RR cycles required to complete the service, the number of requests receiving service, and the quantum size. Then an increase or decrease in the number of quanta that are necessary before service is completed is reevaluated at the arrival or departure of other requests. Tracking these events and calculations enables us to analyze the performance of our limited RR rule. In particular, we obtain the most suitable quantum size, which minimizes the mean sojourn time, for the case in which the switching time for each quantum is considered.

Keywords: Limited RR rule, quantum, processor sharing, sojourn time, performance measures, simulation, loss probability.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081291

References:

[1] L. Kleinrock, "Time-Shared Systems: A Theoretical Treatment", J.A.C.M1.14, 242-261 (1967).
[2] K. Hoshi, Y. Shikata, Y. Takahashi and N. Komatsu, "An Approximate Formula for a GI/G/1 Processor-Sharing System", International Conference on Operations Research, September 1 - 3, 2010 Munich.
[3] G. Yamazaki and H. Sakasegawa, "An optimal design problem for limited sharing systems", Management Science, vol.33 (8), pp.1010--1019 (1987).
[4] Varun Gupta, "Finding the optimal quantum size: Sensitivity analysis of the M/G/1 round-robin queue", ACM SIGMETRICS Performance Evaluation Review archive Volume 36 Issue 2, September 2008 Pages 104-106
[5] Varun Gupta, Jim Dai, MorHarchol-Balter, and BertZwart, "The effect of higher moments of job size distribution on the performance of an M/G/Kqueueing system", Technical Report CMU-CS-08-106, School of Computer Science, Carnegie Mellon University, 2008.
[6] Ward Whitt, "On approximations for queues, I: Extremal distributions", AT&T Bell Laboratories Technical Journal, 63:115-138, 1984.
[7] Y.Shikata, W. Katagiri, and Y. Takahashi,"Performance Evaluation of Prioritized Limited Processor-Sharing System" Y. Shikata, W. Katagiri, and Y. Takahashi, WASET International Conference ICCEL2012, June 11-12, 2012, Copenhagen.