Performance Evaluation of a Limited Round-Robin System
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:62543", author = "Yoshiaki Shikata", title = "Performance Evaluation of a Limited Round-Robin System", 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.", volume = "7", number = "5", pages = "660-5", }