and MGI1PS queues

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库and MGI1PS queues在线全文阅读。