Round robin 演算 法

轮询调度算法(Round-Robin Scheduling)

轮询调度算法的原理是每一次把来自用户的请求轮流分配给内部中的服务器，从1开始，直到N(内部服务器个数)，然后重新开始循环。
算法的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调度。
轮询调度算法流程
假设有一组服务器N台，S = {S1, S2, …, Sn}，一个指示变量i表示上一次选择的服务器ID。变量i被初始化为N-1。其算法如下：

j = i;
do
{ j = (j + 1) mod n; i = j; return Si; } while (j != i);
return NULL;

轮询调度算法假设所有服务器的处理性能都相同，不关心每台服务器的当前连接数和响应速度。当请求服务间隔时间变化比较大时，轮询调度算法容易导致服务器间的负载不平衡。
所以此种均衡算法适合于服务器组中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况。

权重轮询调度算法(Weighted Round-Robin Scheduling)

上面所讲的轮询调度算法并没有考虑每台服务器的处理能力，在实际情况中，可能并不是这种情况。由于每台服务器的配置、安装的业务应用等不同，其处理能力会不一样。所以，我们根据服务器的不同处理能力，给每个服务器分配不同的权值，使其能够接受相应权值数的服务请求。
权重轮询调度算法流程
假设有一组服务器S = {S0, S1, …, Sn-1}，W(Si)表示服务器Si的权值，一个指示变量i表示上一次选择的服务器，指示变量cw表示当前调度的权值，max(S)表示集合S中所有服务器的最大权值，gcd(S)表示集合S中所有服务器权值的最大公约数。变量i初始化为-1，cw初始化为零。其算法如下：

while (true) {
  i = (i + 1) mod n;
  if (i == 0) {
     cw = cw - gcd(S);
     if (cw <= 0) {
       cw = max(S);
       if (cw == 0)
         return NULL;
     }
  }
  if (W(Si) >= cw)
    return Si;
}

这种算法的逻辑实现如图2所示，图中我们假定四台服务器的处理能力为3:1:1:1。

　由于权重轮询调度算法考虑到了不同服务器的处理能力，所以这种均衡算法能确保高性能的服务器得到更多的使用率，避免低性能的服务器负载过重。所以，在实际应用中比较常见。

在分布式系统中，为了实现系统的高性能、高并发、高可用，在构架中都会进行负载均衡设计，它是分布式系统的核心和中枢，负载均衡的好坏直接影响着整个系统的性能。负载均衡分为软件均衡和硬件均衡两类，比如apache、nginx、dubbo 等属于软件负载均衡，F5属于硬件负载均衡，当然他们都会使用到负载均衡算法。

常见的负载均衡算法包含：
1、轮询法（Round Robin）
2、加权轮询法（Weight Round Robin）
3、随机法（Random）
4、加权随机法（Weight Random）
5、平滑加权轮询法（Smooth Weight Round Robin）
6、源地址哈希法（Hash）
7、最小连接数法（Least Connections）

接下来的博客中会一一介绍如上几种算法，本文介绍轮询法。

轮询法是将请求按顺序轮流地分配到服务器上，它均衡地对待后端的每一台服务器，而不关心服务器实际的连接数和当前的系统负载。

总结

轮询调度算法以及权重轮询调度算法的特点是实现起来比较简洁，并且实用。目前几乎所有的负载均衡设备均提供这种功能。

round robin是按照某种合理的顺序平等地选择一组中的所有元素的方法，通常是从列表的顶部到底部，然后再从列表的顶部开始，如此反复。一个简单的解释就是 "轮流 "。作为一个形容词，round robin变成了 "round-robin"。

在计算机操作中，让不同的程序进程轮流使用计算机资源的一种方法是限制每个进程的执行时间为一个很短的时间段，到时间后挂起该进程，轮到另一个进程执行（或 "时间片"）。这通常被描述为round-robin(RR)进程调度。

关于这个词的起源：

Round-robin是指多方在一个圆圈内签署的文件，以使其更难确定签署的顺序，从而防止头目被识别。

这个词可以追溯到17世纪的法语Rond ruban (round ribbon)。它描述了这样一种做法：反对权威的请愿书的签署者（通常是向皇室请愿的政府官员）在一份文件上以非等级性的圆圈或丝带图案（从而掩盖了他们签署的顺序）附上他们的名字，以便不会识别出带头者。

这种做法被皇家海军中向官员请愿的水手所采用（首次记录为1731年）。

1895年开始在体育比赛中使用，作为循环赛的一种赛制。

参考：

What is round robin? - Definition from WhatIs.com

为什么轮询调度算法称为 Round Robin ？ - 知乎

https://en.wiktionary.org/wiki/round_robin

round robin | Etymology, origin and meaning of phrase round robin by etymonline

The saying 'Round Robin' - meaning and origin.

https://en.wikipedia.org/wiki/Round-robin_(document)

1.先到先處理:
先來先做之排班方法 (First-Come, First-Served Scheduling)

目前最簡單的CPU排班演算法就是先來先做(FCFS)演算法，就是把CPU分配給第一個要求CPU的行程。我們可以用FIFO（先進先出）佇列來執FCFS的工作。當一個行程進入就緒佇列之後，它的行程控制區段就鏈接到串列的尾端。當CPU有空的時候，它就分配給在就緒佇列首端的行程。執行中行程就從就緒佇列中剔除。FCFS排班的程式很容易寫也容易瞭解。但在FCFS方法下的平均等待時間經常是很長的。

2.最短工作先處理:
最短的工作先做之排班方式(Shortest-Job-First Scheduling)

另一種不同的CPU排班方式就是最短的工作先做(SJF)演算法。這種演算法將每一個行程的下一個CPU分割長度和該行程相結合。當CPU有空時，就指定給下一個CPU分割最短的行程。如果兩個行程具有相同長度的下一個CPU分割，那麼就採用先來先做(FCFS)的方法。請注意！比較適當的稱呼應該是最短的下一個CPU分割(shortest next CPU burst)，因為這種排班演算法是藉由檢查每一個行程的下一次CPU分割來決定。我們採用SJF一詞的原因，是因為大多數的人和教科書都將這一類型的排班方式叫做SJF。

3.優先排班權:
優先權排班方式 (Priority Scheduling)

最短的工作先做(SJF)是一般優先權排班演算法的一個特例。每一個行程都有它的優先順序。CPU將分配給具有最高優先權的行程，具有相同優先順序的行程則按照FCFS來排班。

最短的工作先做演算法就是一種優先權的演算法，其中優先權(p)就是（預估的）下一個CPU分割的倒數。CPU分割愈大的，優先順序就愈低，反之亦然。

要注意的是我們討論排班是以高優先權和低優先權來決定。優先權一般是一些固定範圍的數字，譬如0到7或0至4095 o。但是，到底0是最高優先權還是最低優先權並沒有一致的看法。有些系統使用低數值表示低優先次序；其他的則恰好相反，這種差異可能會導致一些混亂。在書本之中，我們則假設低數值代表高優先次序。

4.依序循環排班:
依序循環之排班方式 (Round-Robin Scheduling)

依序循環(round-robin, RR)排班演算法是特別為了分時作業系統而設計的，這種排班方法和FCFS排班法相類似，但是加入可搶先的規則以便讓行程互相交換使用CPU。我們定義一個小的時間單位，稱為一個時間量(time quantum)或是時間片段(time slice)。一般一個時間量是10到100個百萬分之一秒。就緒佇列視為一個環狀佇列。CPU排班程式繞著這個就緒佇列走，CPU在時間間隔到達一個時間量時就分配給下一個行程。

5.即時排班 (Real Time Scheduling)

即時計算可分為兩種型式。硬性即時系統(hard real-time system)必須在一定量的時間內完成一項很重要的任務。通常，一個行程交付執行時會附帶一行，描述它所需要計算或執行I/O的時間量。排班程式可能會接受這個行程，並保證這個行程可以準時完成；或是拒絕這個不可能的執行要求。這就是所謂的資源預約(resource reservation)。這種保證要求排班程式正確地知道每一種型式的作業系統函數要花多少時間執行；而由此每一項操作必須保證花費最多的時間。這種保證對於擁有次要記憶體或虛擬記憶體的系統絕不可能達到，這一點我們將在以後幾章看到，因為這些子系統會造成執行某一特殊行程不可避免和不可預期的時間量變化。因此，硬性即時系統是由在專為重要行程的硬體所執行之特殊軟體所組成，因此缺乏現代電腦和作業系統的全功能性。