Advanced Analysis Framework for Queues and Processors
Explore the complex world of queueing systems, processor sharing, and threshold parallelism in this insightful analysis framework. Discover unexpected similarities and open problems in managing workload distribution efficiently across multiserver setups.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
WCFS Queues: A new analysis framework Isaac Grosof Mor Harchol-Balter Alan Scheller-Wolf 1
Unexpected Similarity between Queues Threshold Parallelism Heterogeneous M/G/k Limited Processor Sharing Speed: 0.4 Multiserver Jobs under ServerFilling 4 = 4 0.3 4 4 0.2 2 2 2 1 2 2 =2 1 0.1 =1 =1 4 Open problem! Open problem! Open problem! Open problem! Discover commonality Use commonality to tightly characterize 2
Warmup: M/G/1 Fraction of time busy: Load: = E[S]<1 FCFS Poisson arrivals (memoryless), arrival rate: General job size distribution: S, i.i.d. Response time: T ?~Hyperexp 3 10 8 2 ? ?2 2? ? 6 E[T] E[T](1- ) 4 1 M/G/1 2 0 0 1 1 0.25 0 0.25 0.75 0.5 Load 0 0.75 0.5 3 Load
k servers M/G/k Speed 1/k Speed 1/k Speed 1/k 3 Speed 1/k M/G/k 2 ? ?2 2? ? ? 1 limit: ? ?2 2? ? E[T](1- ) [Kollerstrom 84] 1 M/G/1 0 1 0.25 0 0.75 0.5 Load 4
Heterogeneous M/G/k Speed ?1 Speed ?2 Speed ?3 3 Speed ?? Het. M/G/k M/G/k 2 ? ?2 2? ? Mean response time behavior: Open problem! E[T](1- ) 1 M/G/1 0 1 0.25 0 0.75 0.5 Load 5
M/G/1/Limited Processor Sharing Multi-programming level k 3 Het. M/G/k M/G/k 2 ? ?2 2? ? Open problem! (Unlimited) Processor Sharing: Known, different limit: E[S] E[T](1- ) 1 M/G/1 LPS Unlimited PS 0 1 0.25 0 0.75 0.5 Load 6
Threshold Parallelism 4 4 2 4 2 2 1 7
Threshold Parallelism 4 4 2 2 2 2 1 8
Threshold Parallelism 2 4 4 2 2 1 2 1 9
Threshold Parallelism 2 4 4 2 2 1 3 Het. M/G/k TP Many first M/G/k 2 TP FCFS Open problem! Few first or many first: Different limits ? ?2 2? ? E[T](1- ) 1 TP Few first M/G/1 LPS 0 1 0.25 0 0.75 0.5 Load 10
Multiserver Job Model = 1 = 1 4 = 2 =4 2 2 1 MSJ FCFS 3 Het. M/G/k M/G/k MSJ ServerFilling 2 TP FCFS All existing policies: open problem! All different limits, many unstable We create new policy: ServerFilling ? ?2 2? ? E[T](1- ) 1 M/G/1 LPS 0 1 0.25 0 0.75 0.5 Load 11
Result: Response time bound 3 Het. M/G/k M/G/k E[T](1- ) MSJ ServerFilling Theorem: All models ? WCFS*: 2 TP FCFS ? ?2 2? ? ? ?2 2? ? ? 1? ?? Even stronger theorem: ? ?? ? ??/?/1 [?? lim 1 ? = 1 M/G/1 LPS 0 1 0.25 0 0.75 0.5 Load ?,? ?] Goals: Define WCFS, prove result (Subject to minor condition on job size distribution S) 12
Base Queueing Model Service policy 0.5 0.3 0.2 Age Service policy serves jobs at some service rate Work completes at service rate, age increases 13
Base Queueing Model Service policy 0.5 0.3 0.2 Age Service policy serves jobs at some service rate Work completes at service rate, age increases Job completes when age reaches size 14
Base Queueing Model Service policy 0.5 0.3 0.2 Age Service policy serves jobs at some service rate Work completes at service rate, age increases Job completes when age reaches size Convention: normalize maximum service rate to 1. 15
Finite Skip Front Service policy 0.6 0.4 Front size: n Finite skip: Only serve jobs among the n oldest jobs in arrival order. 16
Work conserving (for Finite Skip policies) Service policy 0.2 0.2 17
Work conserving (for Finite Skip policies) Service policy 0.3 0.2 0.3 0.2 Work conserving: If n jobs present, total service rate 1 (maximum) 18
WCFS Policies Polices that don t converge: M/G/1/SRPT (Unlimited) Processor Sharing Threshold Parallelism, most servers first Multiserver-job FCFS Polices that converge: M/G/1 M/G/k Heterogeneous M/G/k Limited Processor Sharing Threshold Parallelism FCFS Multiserver-job ServerFilling 3 Het. M/G/k M/G/k E[T](1- ) MSJ ServerFilling 2 TP FCFS ? ?2 2? ? 1 M/G/1 LPS 0 1 0.25 0 0.75 0.5 Load 19
WCFS Example: Heterogeneous M/G/k Speed 0.4 Speed 0.3 Speed 0.2 Speed 0.1 Is this model WCFS? Is this model WCFS? Yes! 20
WCFS Example: Multiserver-Job FCFS 2 1 2 1 1 1 Is this model WCFS? Is this model WCFS? No, not work conserving. 21
Define ServerFilling for Multiserver-Job model ServerFilling setting: requirements powers of 2, k is power of 2. k=8 ServerFilling 1/8 1/8 1/2 1 1/4 1 2 1 1 4 1 2 1 1 2 2 1. Find minimal prefix M containing jobs that require k servers 2. Among prefix M, serve largest requirement first Finite skip: ? ? Work conserving: Theorem: ServerFilling always fills all k servers. Is this model WCFS? Is this model WCFS? Yes! 22
Key ideas behind response time bound Want to prove: ? ?? ? ??/?/1 [?? ?,? ?] Key ideas based on work W. 1. ?[??] ?[??] 2. ?[??] ?[??/?/1] 23
Idea 1: E[T] E[W] * Q: Starred job s response time? 24
Idea 1: E[T] E[W] * Thm: Time in front bounded in expectation over all jobs. Time in queue Time in front Max time in queue: ??, because completion rate 1. Min time in queue: ?? ? jobs Differ by constant in expectation. 25
Idea 2: ?[?] ? ??/?/1 - Intuition Job arrives: +S work All servers full: rate 1 Identical to M/G/1! Work W Time Too few jobs: lower rate 26
Proof of ?[?] ? ??/?/1 Consider ? ?2 Consider d dt? ?2 d dt?2 = 0 Expected stationary rate of change: ? Increases: Jump up by S, at rate . E[inc.]: ?? ? + ?2 ?2= 2?? ? ? ? + ?? ?2= 2?? ? + ?? ?2 Decreases: Work completes at rate B(t). Rate 1 if n jobs. E[dec.]: 2?[??] = 2?[?] 2?[?(1 ?)] ? 1 ? 1 ? ? ?2 2? ? +? ? 1 ? = ? ??/?/1 +? ? 1 ? ? ? = 1 ? 27
Proof of ?[?] ? ??/?/1 ? ? 1 ? 1 ? ? ? = ? ??/?/1 + If ? < 1, W consists of < ? jobs, so ? < ?. ? ? 1 ? ? ?[1 ?] = ?(1 ?) ? ? ? ??/?/1 + ? ? ? ? ??/?/1 Completes proof that ? ?? ? ??/?/1 [?? ?,? ?] 28
Empirical validation Threshold Parallelism 2 MSJ ServerFilling 1 Heterogeneous M/G/k ? ?? ? ??/?/1 0 -1 Limited Processor Sharing -2 1 0.8 0.7 0.9 Load ? 29
Future questions Work conserving and finite skip, relative to a different job ordering, e.g. SRPT? Finite skip but not work conserving? Finite skip in expectation? 30
Conclusion Explained unexpected similarity between queues Defined work conserving finite skip models Tightly bounded mean response for all WCFS models. 3 Het. M/G/k M/G/k E[T](1- ) MSJ ServerFilling 2 TP FCFS ? ?2 2? ? 1 M/G/1 LPS 0 1 0.25 0 0.75 0.5 Load 31
Extra: Condition on S Bounded expected remaining size: Exists constant c such that for all ages a, ?[? ? | ? > ?] < ? 32
Extra: DivisorFilling Like ServerFilling, MSJ policy that fills all servers if enough jobs available. In particular, WCFS policy. DivisorFilling works whenever all requirements divide the number of servers k. If k jobs present, will fill all servers. If jobs can have requirements that don t divide k, WCFS not possible. 33
