排队论(Queuing theory)简介

大家好，我是讯享网，很高兴认识大家。

Preliminary Questions

1.What does affect the performance of

——a computer system?

——a computer network?

——an Internet service?

2 How do we measure the performance of

——a computer system?

——a computer network?

——an Internet service?

想象如果我们只有一个作业，性能将仅仅会取决于系统硬件以及执行作业的程序。但是如果我们的作业多于一个呢？

Queueing Theory

讯享网

排队论可以运用在任何队列中，是一门研究如何产生队列以及如何让队列消失的学科。

Queue Examples

disk,memory,CPU-有时候更好的设备并不会导致更好的更佳的性能

rates in a network

lock queue in a database -在队列中等待进行数据库的修改

virtual network functions in a service chain

access to bandwidth in cellular net

purpose

1 预测系统性能

2 设计来提高系统性能

3 测量系统性能

4 优化系统性能

Stochastic Modeling and analysis

排队论是基于更广泛的数学领域：随机建模和分析。系统中最重要的部分通过随机变量来表示，如：interarrival time(1/λ),service time(1/μ),waiting time( $T_{Q}$ )

A motiving example

上图为一个系统，包括了：单一CPU,一个无限(或者有限)的queue，并且为FCFS

平均到达率average arrival rate:λ=3 jobs/sec

平均服务率average service rate:μ=5 jobs/sec

当λ<μ时不会overload，但是由于随机性，依然可能会产生队列

Q1：如果我们知道了 ${\lambda }'$ = $2\lambda$ (到达率加倍)。你需要买一个更快的CPU来保证有同样的响应时间、那么你应该如何增加CPU的速度呢？

A1:Less than double

到目前为止我们还没有工具能准确的计算出来，但是我们可以预想如果同时加倍CPU速度和到达率，那么响应时间会减半。原因：假设在A,B两个世界里的科学家进行同样的工作。A世界的科学家使用更慢的时钟，B世界的科学家使用更快的时钟，A世界的时钟过1s，B世界的时钟则过2s。两个科学家使用相同的标准并且是本地测量λ(即A,B的λ和μ对于他们来说从数值上都是一样的)。所以A到了一个作业的时间，B到达了两倍多的作业。同样，A处理完一个作业的时间，B处理完了两倍多的作业。但是响应时间却不相同而是减半了(因为同样标准下对于他们自身时钟来看，A,B的响应时间应该也是一样的，但是B中的时间比A中的快一倍)。

Q2：如果CPU采用了不同的服务原则呢？

A2：nothing changes 。同样，有时候硬件的提升也无法提升系统性能。