Algorithms for Flow Time Scheduling

.AlgorithmsforFlowTimeSchedulingNikhilBansalDecember2003CMU-CS-03-209SchoolofComputerScienceComputerScienceDepartmentCarnegieMellonUniversityPittsburgh,PA15213ThesisCommittee:AvrimBlum,ChairBruceMaggsKirkPruhs,UniversityofPittsburghR.RaviSubmittedinpartialfulfillmentoftherequirementsfortheDegreeofDoctorofPhilosophyc2003NikhilBansalThisresearchwassponsoredbytheNationalScienceFoundation(NSF)undergrantnos.CCR-0105488,CCR-0122581andCCR-9902091,bythePittsburghDigitalGreenhouse(PDG)andtheIBMCorporationthroughagenerousgraduatefellowship.Theviewsandconclusionscontainedinthisdocumentarethoseoftheauthorandshouldnotbeinterpretedasrepresentingtheofficialpolicies,eitherexpressedorimplied,oftheNSF,thePDG,IBM,theU.S.governmentoranyotherentity..Keywords:ApproximationAlgorithms,On-lineAlgorithms,Scheduling,FlowTime,Non-clairvoyantSchedulingAbstractWestudyschedulingalgorithmsforproblemsarisinginclient-serversystems.Intheclient-serversetting,therearemultipleclientsthatsubmitrequestsforservicetotheserver(s)overtime.Typicalexamplesofsuchsystemsincludeoperatingsystems,web-serversanddatabasequeryservers.Astherecouldbemultipleclientsrequestingaservice,thegoalofaschedulingalgorithmistoprovideservicetotheclientsinsomereasonableway.Anaturalmeasureofthequalityofservicereceivedbyaclientisitsflowtime,definedasthetimesincetheclientsubmitsarequestuntilitiscompleted.Inthisthesis,westudysomefundamentalproblemsrelatedtominimizingflowtimeanditsvariants.Theseincludeℓpnormsofflowtime,weightedflowtime,stretch(flowtimedividedbyitsservicerequirement)andcompletiontime.Weconsidertheseproblemsinvarioussettings,suchasonline,offline,schedulingwhentheprocessingrequirementsareunknownandschedulingwhenjobscanberejectedatsomecost.ivAcknowledgmentsFirstofall,IwouldliketothankmyadvisorAvrimBlumforhisinfiniteguidance,supportandinsights.IwillbeindebtedtohimforallthewaysinwhichIhavegrownasaresearcherandespeciallyforteachingmehowtothink.Clearly,thisthesiswouldnotbepossiblewithouthim.IhavebeenreallyfortunatetohaveKirkPruhsatsuchaclosedistance.Hehasbeenlikeasecondadvisortome.Iamextremelygratefultohimforsharinghisinvaluableideasandhislimitlessenthusiasmforresearch.AlargepartofthisthesishasitsoriginsinthediscussionsatthePittlunchtrucks.IwanttothankallthetheoryfolksatCMUforprovidingsuchawonderfulandstimulatingresearchenvironment.SpecialthankstoAvrimBlum,TomBohman,AlanFrieze,AnupamGupta,RyanMartin,R.RaviandStevenRudichfortheirextraordinaryclasses.ThankstoShuchiChawla,KedarDhamdhere,AmitabhSinha,JochenKonemannandAdamWiermanforbeingsuchgreatfriends,colleaguesandcollaborators.ManythankstoAshwinBharambe,AmitManjhi,MahimMishraandBiancaSchroederforallthenicetimeIspentwiththem.Finally,Iwouldliketothankmyparentsfortheirunconditionalloveandencouragementandinstillinginmetheloveoflearning.AspecialthankstomyfriendAgeethforallherloveandunderstanding.Contents1Introduction11.1Motivation............................................11.2ModelandPreliminaries....................................21.3AnalysisFramework......................................41.3.1OfflineAnalysis....................................41.3.2OnlineAnalysis.....................................51.3.3ResourceAugmentation................................51.4Preliminaries..........................................61.5OverviewofResults.......................................81.6RelatedAreas..........................................142SchedulingtoMinimizeℓpnormsofFlowTime152.1Introduction...........................................152.2RelatedResults.........................................162.3GeneralLowerBounds.....................................172.4AnalysisofSJF.........................................172.5AnalysisofSRPT........................................202.6FlowAnalysisofSETF.....................................222.7LowerBoundforRoundRobin.................................262.8ConcludingRemarks......................................273SchedulingtoMinimizeWeightedFlowTime293.1Introduction...........................................293.2RelatedWork..........................................313.3Preliminaries..........................................313.4Algorithm............................................323.4.1Analysis........................................323.4.2ASemi-OnlineAlgorithm...............................373.5WeightedℓpnormsofFlowTime................................373.5.1TheClairvoyantCase..................................383.5.2TheNon-ClairvoyantCase...............................393.6ConclusionandOpenProblems.................................404SchedulingtoMinimizeStretch414.1Introduction...........................................414.2RelatedWork..........................................42vviCONTENTS4.3LowerBounds..........................................424.3.1ClairvoyantScheduling.................................424.3.2Non-clairvoyantScheduling..............................434.4Staticscheduling........................................454.5DynamicScheduling......................................464.6ConcludingRemarks..