HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Batch arrival M/G/1 Processor Sharing with application to Multilevel Processor Sharing scheduling

Abstract : We analyze an M/G/1 Processor-Sharing queue with Batch arrivals. Our analysis is based on the integral equation derived by Kleinrock, Muntz and Rodemich. Using the contraction mapping principle, we demonstrate the existence and uniqueness of a solution to the integral equation. Then we provide asymptotical analysis as well as tight bounds for the expected response time conditioned on the job size. In particular, the asymptotics for large size jobs depends only on the first moment of the job size distribution and on the first two moments of the batch size distribution. That is, similarly to the Processor Sharing with single arrivals, in the M/G/1-PS with batch arrivals the expected conditional response time is finite even when the job size distribution has infinite second moment. Finally, we show how the present results can be applied to the Multilevel Processor Sharing scheduling.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 5:53:36 PM
Last modification on : Thursday, January 20, 2022 - 5:27:35 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:23:40 PM


  • HAL Id : inria-00071540, version 1



Konstantin Avrachenkov, Urtzi Ayesta, Patrick Brown. Batch arrival M/G/1 Processor Sharing with application to Multilevel Processor Sharing scheduling. [Research Report] RR-5043, INRIA. 2003. ⟨inria-00071540⟩



Record views


Files downloads