Ihsan Ayyub QaziPlan for the PresentationSome Basics…Why minimize sojourn time?Optimizing the average sojourn timeOptimality of SRPTSlide 7Disadvantages of SRPT“On the average sojourn time under M/M/1/SRPT” by Nikhil BansalPlanProblemClassical ResultProblem Definition (revisited)Slide 14Main result of the Paper…Improvement FactorContribution of the paperSlide 18Some Previous work…Mean Waiting and Residence times for a job of size (Intuition)Slide 21Analysis: Expressions with exponentially distributed job sizesExpression for the sojourn time under SRPT for exponential distributed job sizesResultsSketch of the proofUpper Bounding the Sojourn TimeComparison between the bounds on E[R] and E[W]Lower Bounding the Sojourn TimeSketch of the proof (contd)Upper Bound for Theorem 1ThankyouSlide 32Slide 33Slide 34Slide 35Main result of the paperImprovement Factor of SRPT against the Best Blind Scheduling PolicyBackground and MotivationDifference in the analyses of M/M/1 and G1/G1/1 queuing systemsSo why is the analysis of a G1/G1/1 queuing system different and more difficult?Slide 41What to do? So why is the analysis of a G1/G1/1 queuing system so difficult?Hmmm…Slide 44Competitive AnalysisSlide 46Slide 47Yao’s Minimax Theorem (Contrapositive) [Minimization Problem]Slide 49Some known results for competitive ratio of blind scheduling algorithmBreakThrough….AnalysisSlide 53Analysis (Basic Idea)Slide 55Slide 56Slide 57Few Lemmas…Slide 59Proof of lemma 3Proof of Theorem 1SummaryReferencesQuestionsSlide 65CS 3150 PresentationCS 3150 Presentation11Ihsan Ayyub Qazi“Achievable sojourn times in M/M/1 and GI/GI/1 systems: A Comparison between SRPT and Blind Policies”A(t), Q(t)D(t)CS 3150 PresentationCS 3150 Presentation22Plan for the PresentationSome basics Some basics Motivation for minimizing sojourn timesMotivation for minimizing sojourn timesIntuition for the Optimality of SRPTIntuition for the Optimality of SRPTPaper 1: “Paper 1: “On the average sojourn time under M/M/1/SRPT” by Nikhil BansalPaper 2: “Paper 2: “Achievable sojourn times by non-size based policies in a GI/GI/1 queue” by Nikhil BansalCS 3150 PresentationCS 3150 Presentation33Some Basics…The The sojourn timesojourn time of a job is the time of a job is the time since a job arrives until the time it since a job arrives until the time it completes its service requirement.completes its service requirement.CS 3150 PresentationCS 3150 Presentation44Why minimize sojourn time?Sojourn time is one of the most Sojourn time is one of the most useful measures of useful measures of  user satisfaction and user satisfaction and  performance in a scheduling system.performance in a scheduling system.Keeping the Keeping the average sojourn timeaverage sojourn time low is often an important criteria in low is often an important criteria in the choice of a scheduling policy.the choice of a scheduling policy.CS 3150 PresentationCS 3150 Presentation55Optimizing the average sojourn timeSRPT policy that at any works on the SRPT policy that at any works on the job with the smallest remaining job with the smallest remaining service requirement, achieves the service requirement, achieves the optimum possible average sojourn optimum possible average sojourn time for all possible instances of the time for all possible instances of the problem [1], [2] problem [1], [2]CS 3150 PresentationCS 3150 Presentation66Optimality of SRPTShortest Job First (SJF) is a non-preemptive policy that schedules the jobs in increasing order of their sizes. It is optimal for all non-preemptive policesHowever, the SJF policy is optimal only when all the jobs are present at the server at once. Total Completion Time = 20+25 = 45Average Completion Time = 45/2 = 22.5SchedulerSchedulerTotal Completion Time = 5+25 = 30Average Completion Time = 30/2 = 15205205CS 3150 PresentationCS 3150 Presentation77Optimality of SRPTOne can view SRPT as a preemptive version of SJF.Hence one can get an idea about the optimality of SRPTScheduler20515 5Total Completion Time = 5+20 = 25Average Completion Time = 25/2 = 12.5 Total Completion Time = 15+20 = 35Average Completion Time = 35/2 = 17.5 However, one can consider the remaining processing time (i.e. 15) as a separate job and hence swap it with 5CS 3150 PresentationCS 3150 Presentation88Disadvantages of SRPTSRPT requires exact knowledge of the SRPT requires exact knowledge of the service requirement for each jobservice requirement for each jobIt is unfair to Jobs with large service It is unfair to Jobs with large service requirements and may even starve requirements and may even starve them.them.Blind policies have many attractive Blind policies have many attractive properties such as properties such as  they are stateless andthey are stateless and easier to implement in a real system.easier to implement in a real system.CS 3150 PresentationCS 3150 Presentation99“On the average sojourn time under M/M/1/SRPT” by Nikhil BansalCS 3150 PresentationCS 3150 Presentation1010Plan ProblemProblem ResultsResults BackgroundBackground AnalysisAnalysisCS 3150 PresentationCS 3150 Presentation1111Problem““How much more can the sojourn How much more can the sojourn time improve if the knowledge of time improve if the knowledge of job sizes is used while scheduling?”job sizes is used while scheduling?”CS 3150 PresentationCS 3150 Presentation1212Classical ResultIt is a well-known result that the It is a well-known result that the average sojourn time in an M/M/1 average sojourn time in an M/M/1 system issystem isThis holds for all scheduling policies This holds for all scheduling policies that do not make use of the job sizes that do not make use of the job sizes while scheduling [3].while scheduling [3].)1(1CS 3150 PresentationCS 3150 Presentation1313Problem Definition (revisited)““How much more can the sojourn time improve if the How much more can the sojourn time improve if the knowledge of job sizes is used while scheduling?”knowledge of job sizes is used while scheduling?”In essence, this question reduces to finding the expression for the average sojourn time in a M/M/1/SRPT systemCS 3150 PresentationCS 3150 Presentation1414Plan ProblemProblem ResultsResults BackgroundBackground AnalysisAnalysisCS 3150 PresentationCS 3150 Presentation1515Main result of the Paper…The average sojourn time [under