排队论及其应用Lecture8处理器排队模型.pptVIP

排队论及其应用Lecture 7 处理器共享排队模型 中国科学技术大学 计算机科学与技术学院 田 野 * 处理器共享的排队模型 类似M/M/1 客户单个到达，到达速率 λ 服务器服务一个客户的时间服从指数分布，服务速率是μ 当系统中有多个客户时，这些客户分享服务器的服务能力—如果有C个客户，每个客户完成服务的时间是期望为C/μ的指数分布 客户进入系统，立刻开始服务 记为M/M/1-PS，PS代表Processor Sharing 例如 计算机处理器通过分时的办法处理多个进程 多个TCP流共享链路带宽 * 求解M/M/1-PS 稳态条件λμ 关注状态i 用户单个到达，发生从i到i+1的迁移，用户到达速率是λ 一个用户完成服务离开，发生从i到i-1的迁移 当前i个客户接受服务，剩余服务时间视为i个期望为i/ μ的指数分布的随机变量，其中最小变量的分布服从期望为1/ μ的指数分布 从i到i-1的迁移速率是μ 与M/M/1相同！ * 求解M/M/1-PS 同M/M/1，稳态下，系统中有i个客户的概率 系统中平均客户人数L和客户平均逗留时间W * 单个客户的停留时间 假设在进入排队系统前，每个客户被随机分配一个服务量x，即如果这个客户独占服务器，所需要的服务时间是x，显然E[x]=1/μ 在M/M/1中，服务量x的客户在系统中停留时间E[W|x]=Wq+x 在M/M/1-PS中，E[W|x]=？ * 在M/M/1-PS中，客户无需排队，每个客户在系统中时间应严格与x成正比，W(x)=cx，c是一个常数 已知并且可知换言之，在每一个客户看来，服务器使用所有服务能力的1-ρ服务她。 * M/G/1-PS 服务器服务能力为C 几个记号 x：一个客户的服务量 FX(x)：客户服务量的CDF分布 N(x)：系统中已接受的服务量≤x的客户的平均数量 T(x)：系统中已经接受x服务量的客户在系统中平均耗时 n(x)： * 考虑一个黑盒 当客户已经完成了x的服务量，并且已经在系统中平均滞留了T(x)的时间，进入黑盒 当客户完成了x+Δx的服务量，并且平均滞留T(x+Δx)，离开黑盒 * 分析 客户进入黑盒的速率，λ(1-FX(x)) 客户在黑盒中滞留时间 根据Little’s law * 将Δx?0，有 另一方面，系统中“年龄”为x的客户人数满足 At every instant of time, the “service age” of all the customers increases at the same rate The difference in the customer density wrt to the service age arises only due to departures of customers upon completion of their service By age x the fraction FX(x) of the customers have departed and the fraction 1? FX(x) of them remains in the system * 两者结合有 考虑一个x?∞的客户，这个客户将很长时间稳定地占用C(1-ρ)的服务能力 考虑把这个“大客户”排除后的排队系统 The job stays in the system for a very long time. Meanwhile, all the other (small) jobs arriving in the system pass by; the big job sees effectively the service rate remaining from the other jobs, C(1 ? ρ). * 两式结合，n(0)/λ=1/ C(1-ρ)， 因此 考虑所有的服务量分布 * Same as M/M/1-PS 例子：Download data traffic in a cellular system The HSPDA protocol (High speed downlink packet access) of 3G cellular systems uses a time-division type multiplexing: the base station (BS) transmits at full power to only one user in each time slot. If slots are assigned in a round robin fashion to the active user