www.elsevier.com/locate/dsw A note on comparingresponse times in the M/GI/1/FB
Available online at
OperationsResearchLetters32(2004)73–76
/locate/dsw
AnoteoncomparingresponsetimesintheM/GI/1/FB
andM/GI/1/PSqueues
AdamWierman ,NikhilBansal,MorHarchol-Balter
ComputerScienceDepartment,SchoolofComputerScience,CarnegieMellonUniversity,Pittsburgh,PA15213,USA
Received20September2002;receivedinrevisedform15April2003;accepted16April2003
Abstract
Wecomparetheoverallmeanresponsetime(a.k.a.sojourntime)oftheprocessorsharing(PS)andfeedback(FB)queuesunderanM/GI/1system.WeshowthatFBoutperformsPSunderservicedistributionshavingdecreasingfailurerates;whereasPSoutperformsFBunderservicedistributionshavingincreasingfailurerates.c2003ElsevierB.V.Allrightsreserved.
Keywords:Scheduling;M/G/1;Feedback(FB);Leastattainedservice(LAS);Shortestelapsedtime(SET);Processorsharing(PS);Sojourntime;Responsetime
Time-sharingschedulingpolicies,especiallytheprocessor-sharing(PS)discipline,areusedquitefre-quentlyinmodernsystems.UnderPStheprocessorissharedevenlyamongalljobscurrentlyinthesystem.AlthoughPSiscommonlyused,itprovidesafarfromoptimalmeanresponsetime(a.k.asojourntime).Theshortest-remaining-processing-time(SRPT)policyisknowntobeoptimalwithrespecttooverallmeanre-sponsetime[4].Thispolicyschedulesthejobhavingthesmallestremainingsizeatalltimes;thusSRPTrequiresknowledgeofthejob’ssize(a.k.aservicerequirement).Intheabsenceofthisknowledge,the
ThisworkwassupportedbyNSFCareerGrantCCR-0133077,byNSFITRGrant99-167ANI-0081396,byCiscoSystems,Spin-nakerNetworksviaPittsburghDigitalGreenhouseGrant01-1,andanIBMResearchFellowship. Correspondingauthor.
E-mailaddresses:acw@cs.cmu.edu(A.Wierman),nikhil@cs.cmu.edu(N.Bansal),harchol@cs.cmu.edu(M.Harchol-Balter).
feedback(FB)policy1haslongbeenproposedasanapproximationtoSRPT.UnderFBthejobwiththeleastattainedservice(a.k.aage)getstheprocessortoitself.Ifseveraljobsallhavetheleastattainedser-vice,theytime-sharetheprocessorviaPS.Bybiasingtowardsthejobswithsmallages,FBis,inasense,attemptingtocompletetheshortjobsasquicklyaspossible.Thegoalofthisnoteistounderstandun-derwhichservicedistributionsFBimprovesuponthemeanresponsetimeofPS.
TheresponsetimesforbothM/GI/1/PSand
def
M/GI/1/FBarewellknown.Wedeÿne = E[X]where isthearrivalrateandXisarandomvari-ablesampledfromtheservicedistributionF(x)withdensityfunctionf(x).LetE[T]PdenotethemeanresponsetimeunderpolicyPandletE[T(x)]Pdenote
NotethatFBissometimesreferredtobythreeothernames:Generalizedforeground–background(FB),least-attained-service(LAS),andshortest-elapsed-time(SET).
1
c2003ElsevierB.V.Allrightsreserved.0167-6377/03/$-seefrontmatter
doi:10.1016/S0167-6377(03)00061-0