Performance Evaluation of Prioritized Limited Processor-Sharing System

Authors: Yoshiaki Shikata, Wataru Katagiri, Yoshitaka Takahashi

Abstract:

We propose a novel prioritized limited processor-sharing (PS) rule and a simulation algorithm for the performance evaluation of this rule. The performance measures of practical interest are evaluated using this algorithm. Suppose that there are two classes and that an arriving (class-1 or class-2) request encounters n1 class-1 and n2 class-2 requests (including the arriving one) in a single-server system. According to the proposed rule, class-1 requests individually and simultaneously receive m / (m * n1+ n2) of the service-facility capacity, whereas class-2 requests receive 1 / (m *n1 + n2) of it, if m * n1 + n2 ≤ C. Otherwise (m * n1 + n2 > C), the arriving request will be queued in the corresponding class waiting room or rejected. Here, m (
1) denotes the priority ratio, and C ( ∞), the service-facility capacity. In this rule, when a request arrives at [or departs from] the system, the extension [shortening] of the remaining sojourn time of each request receiving service can be calculated using the number of requests of each class and the priority ratio. Employing a simulation program to execute these events and calculations enables us to analyze the performance of the proposed prioritized limited PS rule, which is realistic in a time-sharing system (TSS) with a sufficiently small time slot. Moreover, this simulation algorithm is expanded for the evaluation of the prioritized limited PS system with N
3 priority classes.

Keywords: PS rule, priority ratio, service-facility capacity, simulation algorithm, sojourn time, performance measures

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

References:

[1] L. Kleinrock, "Time-Shared Systems: A Theoretical Treatment", J.A.C.M Vol.1, No.14, 242-261 (1967).
[2] G.Fayolle and I.Mitrani, "Sharing a Processor Among many Job Classes", J.A.C.M Vol.27, No.3, July 1980. Pp519-532
[3] E.Altman, K.Avrachenkov and U.Ayesta, "A survey on processor sharing", Queueing Syst(2006)53:53-63
[4] M.Haviv and J.Val, "Mean sojourn times for phase-type discriminatory processor sharing system", European Journal of Operational research, 189(2008), 375-386
[5] G. Yamazaki and H. Sakasegawa, "An optimal design problem for limited sharing systems, Management Science", vol.33(8), pp.1010--1019 (1987).
[6] K. Hoshi, Y.Shikata, Y. Takahashi and N. Komatsu, "An Approximate Formula for a GI/G/1 Processor-Sharing System" , IEICE TRANSACTIONS on Communications, Vol.E94-B, No.8, pp. 2247--2253, 2011.
[7] W. Kraemer and M. Langenbach-Beltz, "Approximate formulae for general single server systems with single and batch arrivals", Angewandte Informatik, Vol. 9, pp. 396 - 402 (1978).
[8] Y. Takahashi, "Diffusion approximation for the single-server system with batch arrivals of multi-class calls", IEICE Transactions, J69-A (3), pp. 317-324 (1986).