- Date:30 Aug 2020
- Views:6
- Downloads:0
- Size:878.00 KB

Transcription:

SchedulingScheduling inServer FarmsMor Harchol BalterComputer Science Dept.

Carnegie Mellon Universityharchol cs cmu eduOutline tomorrowI Review of schedulingin single server.

II Supercomputi III Web server farmng FCFS model PSRouter RouterIV Towards Optimality SRPT Metric .

Single Server Model M G 1 Poisson Load E X 1w rate X job size service requirement Bounded Pareto.

Job sizes with huge variance are everywhere1 Pr Job size x x Downey 96 CPU Lifetimes of UNIX jobs Harchol Balter Supercomputing job sizes Schroeder Harchol Balter 00 .

Web file sizes Crovella Bestavros 98 Barford Crovella 98 Huge Shin 99 IP Flow durations Shaikh Rexford Variability D F R 2Var X .

E X 2 Top heavy 8 C X2 50 is typical top 1 jobsk x p make up half Scheduling Single Server M G 1 Poisson Load 1 Huge.

arrival VariancQuestion Order these scheduling policies formean response time E T 1 FCFS First Come First Served non preemptive 2 PS Processor Sharing preemptive .

3 SJF Shortest Job First a k a SPT non preemptive 4 SRPT Shortest Remaining Processing... preemptive 5 LAS Least Attained Service a k a FB preemptive Scheduling Single Server M G 1 Poisson Load 1 Huge.

arrival VariancLOW E T HIGH E T SRPT LAS PS SJF FCFSOPT for all Insensitive Surprisingly bad E X2 Requires D F R .

arrival to E X2 E X2 term shortssequences Shanthikumar89 caught Schrage 67 behindNo Starvation Even the biggest jobs prefer SRPT to PS Bansal Harchol Balter 01 Wierman Harchol Balter 03 .

THM E T x SRPT E T x PS for all x for Bounded Pareto 9 Effect of VariabilityBounded Pareto job sizes Closed vs OpenOpen System.

Closed System What s theThink effect ofscheduling Send Receive Closed vs Open.

Open System Results Closed System ResultsClosed open systems analyzed under same job sizedistribution with same average load Schroeder Wierman Harchol Balter NSDI 06 .

Summary Single Single server system LESSONS LEARNED Smart scheduling greatlyimproves mean response time Variability of job size.

distribution is key X job size highly variable Closed system sees muchreduced effect Multiserver ModelServer farms .

Scalable capacitySched policy assignment Incoming policy Sched policyPoisson Router.

Process Sched policy2 Policy Decisions Sometimes scheduling policy is fixed legacy system 10I Review of schedulingin single server.

II Supercomputi III Web server farmng FCFS model PSRouter RouterIV Towards Optimality SRPT Metric .

Supercomputing Model assignment policy FCFSProcess Router Jobs are not preemptible .

Jobs processed in FCFS order Assume hosts are identical Jobs i i d G highly variable size distribution Size may or may not be known Initially assume known 12 Q Compare Routing Policies for.

E T Supercomputing1 Round Robin FCFS2 Join Shortest Queue policy FCFSGo to host w fewest jobs Router3 Least Work Left .

equivalent to M G k FCFS Jobs i i d G highly variableGo to host with least total work 4 Central Queue Shortest Job M G k SJF .

Host grabs shortest job when free 5 Size Interval SplittingJobs are split up by size among hosts A Size Interval Splitting best soHigh Supercomputing.

E T 1 Round Robin FCFS2 Join Shortest Queue FCFSGo to host w fewest jobs Router3 Least Work Left equivalent to M G k FCFS Highly variable job sizes.

Go to host with least total work 4 Central Queue Shortest Job M G k SJF Host grabs shortest job when free 5 Size Interval Splitting Harchol Balter Crovella .

Low Jobs are split up by size among hosts Murta JPDC 99 Routing Policies High Remarks Central Queue E T 1 Round Robin Good utilization.

of servers 2 Join Shortest Queue Some isolationGo to host w fewest jobs for smalls3 Least Work Left equivalent to M G k FCFS.

Go to host with least total work Size Interval WAY Better 4 Central Queue Shortest Job Worse utilizationof servers M G k SJF Great isolation.

Host grabs shortest job when free for smalls 5 Size Interval SplittingLow Jobs are split up by size among hosts E T Harchol Balter Crovella .

Murta JPDC 99 Size Interval Splittingx f x job size xQuestion How to choose the size cutoffs .

To Balance Load or Not to BalanceLoad xf x dx xf x dx xf x dx xf x dx Size Interval SplittingFCFS x f x .

job size xAnswer Recent Research for case of Boundedjob size Pr X x x 1 1 1UNBALANCE BALANCE LOAD UNBALANCE.

favor smalls favor larges Harchol Balter Vesilo 06 Glynn Harchol Balter Ramanan 06 Beyond Size Interval SplittingFCFS x f x job size x.

Q Is Size Interval Splitting as good as it Size Interval Splitting with StealingAnswer Allow CycleS Send Shorts HereL Send Longs Here .

Size But if idle send Short Cycle Gain to Shorts is high Pain to Longs is very small Cycle Stealing analysis very hard Fayolle Iasnogorodski Konheim Meilijson Melkman Cohen Boxma van Uitert Jelenkovic Foley McDonald .

Harrison Borst Williams New easy approach Dimensionality Reduction 2D 1D Harchol Balter Osogami Scheller Wolf Squillante SPAA03 What if Don t Know JobSize FCFS.

1 Round Robinpolicy FCFS2 Join Shortest QueueGo to host w fewest jobs 3 Least Work Left .

equivalent to M G k FCFS Highly variable job sizesGo to host with least total work 4 Central Queue Shortest Job M G k SJF Host grabs shortest job when free .

Q What can we do tominimize E T when5 Size Interval Splittingdon t know job size Jobs are split up by size among hosts .

The TAGS algorithm Task Assignment by Guessing Size When job reaches size limit for host then itis killed and restarted from scratch at next host Harchol Balter JACM 02 .

Results ofLeast Work LeftHigh Lowervariability variability Summary Part I.

Single server system LESSONS LEARNED Smart scheduling greatlyimproves mean response time Variability of job sizedistribution is key .

X job size highly variable Closed system sees muchreduced effect LESSONS LEARNED Supercomputing Greedy routing policies .

FCFS like JSQ LWL are poor To combat variability needRouter size interval splitting FCFS By isolating smalls canachieve effects of smart.

single server policies Load UN balancing Don t need to know size 23 Tomorrow Review of scheduling in single server.

II Supercomputing III Web server farmManufacturing FCFS modelRouter RouterV Towards Optimality Scheduling.

Scheduling inin MultiserverMultiserverMor Harchol BalterComputer Science Dept.

Carnegie Mellon Universityharchol cs cmu eduI Review of schedulingin single serverII Supercomputi III Web server farm.

ng FCFS model PSRouter RouterIV Towards Optimality I Review of schedulingin single server.

II Supercomputi III Web server farmng FCFS model PSRouter RouterIV Towards Optimality Web Server Farm.

Cisco LocalRouting Directorpolicy IBM NetworkPoisson DispatcherProcess Router Microsoft.

PS SharePoint F5 Labs BIG IP HTTP requests are immediately dispatched to server Requests are fully preemptible Commodity servers utilized Do Processor Sharing .

Jobs i i d G highly variable size distribution 7 orders magnitude difference in job size Crovella Bestavros 98 Q Compare Routing Policies forHigh Web Server Farm.

2 Join Shortest QueueGo to host w fewest jobs High variance job size3 Least Work LeftGo to host with least total4 Size Interval Splitting.

Low Jobs are split up by size Central Queue policies aren tE T FCFS among hosts possible for PS farms Q Compare Routing Policies for1 Random PS2 Join Shortest Queue.

Go to host w fewest jobs Answer Same for E T but not great Also want to3 Least Work Left better 8 servers 9 C2 50.

E T balance load Go to host with least total RAND SIZEwork 1 E T M G 1 PS 1 .

4 Size Interval Splitting PS farm 1 E T pi Jobs are split up by size p 1 i i among hosts .

Prior Analysis of JSQAll prior JSQ analysis assumes FCFS servers2 server 2 server approximations Kingman 61 Flatto McKean 77 Nelson Philips Sigmetrics 89 Wessels Adan Zijm 91 Nelson Philips Perf Eval 93 .

Foschini Salz 78 Lin Raghavendra TPDS 96 Knessl Makkowsky Schuss Tier 87 Conolly 84 Rao Posner 87 Blanc 87 Grassmann 80 Muntz Lui Towsley 95 Cohen Boxma 83 31.

Nelson Philips E Waiting Time E JobSize Pr n total in all E length shortest queue n total Assume this is Assume thisM M k is .

n k k servers First Analysis of JSQ for Gupta Harchol Balter Sigman Whitt 06 Process JSQ.

Near insensitivity to C2 PS server farm with General service PS server farm w Exponential service FCFS server farm w Exponential serviceSingle queue equivalence .

For PS server farm w Exponential service Multiserver system Single queue w contingent arrival rate Summary so farLESSONS LEARNED Supercomput Greedy routing policies .

ing like JSQ LWL are poor To combat variability needsize interval splitting Router By isolating smalls canachieve effects of smart.

single server policies Load UN balancing Don t need to know size Web server farmPS LESSONS LEARNED .

JSQ routing is good PS Job size variabilityRouter not a problem PS Load Balancing Review of scheduling in single server.

II Supercomputing III Web server farmManufacturing FCFS modelRouter RouterIV Towards Optimality What is Optimal.

Routing Scheduling Sched policySched policyjobs RouterSched policy.

2 Policy DecisionsAssume no restrictions Jobs are fully preemptible Can have central queue if want it or not Know job size.

of course don t know future jobs 36 What is OptimalRouting Scheduling Central Queue SRPTRecall minimizes E T on every sample path .

Schrage 67 Question Central Queue SRPT looks prettyDoes it minimize E T 37 Central Queue SRPTAnswer This does not minimize E T on every arrival sequence .

Bad Arrival Sequence time 0 2 jobs size 29 1 job size 210 time 210 2 jobs size 28 1 job size 29 time 210 29 2 jobs size 27 1 job size 28 OPT Central Queue SRPT.

28 28 29 29 28 2929 210 29 28 210 29preempted 38 Central Queue SRPTAdversarial Worst Case Guarantees .

THM Leonardi Raz STOC 97 Central Queue SRPT is O log min biggest sizesmallest size serverscompetitive for E T and no online policy can improve upon.

this by more than constant factor log biggest smallest could be factor 7 in practice Closest stochastic result analyzes only central queuew priorities Harchol Balter Wierman Osogami Scheller Wolf QUESTA 05 .

What is OptimalRouting Schedulingwith Immediate Dispatch Sched policySched policy.

jobs RouterSched policy2 Policy DecisionsPractical Assumption jobs must be immediately dispatched Jobs are fully preemptible within queue .

Know job size What is OptimalRouting Schedulingwhen ImmediatelyImmediately SRPT Claim Dispatch .

Dispatch Jobs The optimal routing sched jobs Router SRPT pair given immed dispatchuses SRPT at the hosts Assuming an opt pair exists Let A optimal routing scheduling pair wrt E T .

Suppose by contradiction A does not use SRPT at the hosts Let policy pair B mimic A with respect to A s dispatching of jobs to I e policy B may be different from A but sends the same jobs to thesame hosts at the same times as A But after the dispatching B does SRPT scheduling at the hosts .

Thus B improves upon A with respect to E T Contradiction IMPACT Claim narrow search to policies with SRPT at 41 In search of goodImmediate Dispatch RoutingImmediately.

Dispatch JobsIncoming SRPTjobs RouterQ What should immediate dispatch routingpolicy be given SRPT sched at hosts .

In search of goodRao and M. Posner, â€œAlgorithmic and approximate analysis of the shorter queue,â€ Model Naval Research Logistics, Vol. 34, 1987, pp. 381-398. R. Righter and J. Shanthikumar, â€œScheduling multiclass single server queueing systems to stochastically maximize the number of successful departures," Probability in the Engineering and Informational ...

Recent Views:

- Msp 430 micro processor project utk
- The service product
- An overview india energy forum
- Assistive technology a modified perspective
- A fellowship of differents
- Powerpoint macrojournals
- Wp2 summary
- Galloper clarification meeting onshore cable system
- San jos state university english 1a composition i
- Chapter 2 the world of science weebly