计算机组成原理试题及答案doc计算机组

Scheduling Algorithms to Minimize Session Delays,Nandita DukkipatiDavid Gutierrez,Introduction,Provision of QoS in the InternetQoS measure for short flows: Response time seen by the userImportant to minimize average session delays for short flowsScheduling algorithms provide QoS at a single nodeCoordinate QoS at each network element to provide end-to-end QoS,Problem,Optimal schedule of sessions in the single node case and the network case for a known traffic arrival patternWeight (or ) allocations for sessions in Generalized Processor Sharing schedulers to minimize delaysComparison of average session delays in Generalized Processor Sharing and Shortest Job First schedulers,Arrival process: deterministic and knownFluid arrivals and fluid serviceSession delay, di = Di - AiAverage session delay, Optimal scheduling policy,Background,Minimizing Delays in Single Node,N SessionsAi(t) : Arrival rate of session i at time tSi(t) : Size of session iOptimal schedule ?,Shortest Job First,Optimal policy when all jobs are present in the server at once in the systemNot optimal in our system of interest,Shortest Time to Finish First (STFF),2 sessionsNon unique optimal schedule,STFF-2:TAi: Maximum time to arrival of last bitCompute the minimum time to finish, Tfi = max(TAi, Si / C)Determine the priorities of the sessions,Optimality of STFF-2,Lemma 1: The STFF-2 discipline minimizes the session delay of 2 sessions at a single node serverSketch of Proof :,STFF - N,Definition: Pair wise STFFLemma 2: Every optimal discipline must be pair wise STFFSTFF-N:,Initialization Np : Set of all sessions whose priorities have been decided = j = 1 to | N |Compute the minimum time to finish, TFi, for unprioritized sessionsAssign priority j to the session with min(TFi)Update Np and remaining capacity C(t) = C(t) (capacity taken by sessions belonging to Np),STFF - N,Not optimalExample:,Minimizing Delays in GPS,Problem: Find weights i in GPS to minimize session delays i1, i2, ., iN: Increasing order of session sizes Find i such that:,Minimizing Delays in GPS,GPS can realize any strict priority based schedule,1.For every session identify the bottleneck router along its path2.For a session i:Ni : Set of sessions bottlenecked at router iCi : Capacity of router3.4.Minimum average delay,Scheduling Sessions - Network Case,Equivalent to Job Shop Scheduling problem: NP-hardA lower bound on average session delay:,STFF - Network 1.j = 1 to |N|2. 3. Assign priority j to the session with min(Fi),Heuristic Schedule - Network Case,Motivation:Littles lawBlocking Factor,Summary,STFF - 2: Optimal scheduling discipline for 2 sessions at a single nodeSTFF - N: A heuristic for N sessions at a single nodeGeneralized Process Sharing can realize any strict priority based scheduleWeight allocation in GPS schedul