本文观点部分来自：http://blog.csdn.net/pi9nc/article/details/9883705
简言：
随着数据时代的来临，为应对大数据，高并发的数据访问量。系统架构师利用各种方法来保证系统组成运行，如建立缓存服务器器， 合理的利用各种调度算法。现在我们来介绍常见的调度算法。
调度算法：调度算法是指：根据系统的资源分配策略所规定的资源分配算法，如任务A在执行完后，选择哪个任务来执行，使得某个因素（如进程总执行时间，或者磁盘寻道时间等）最小。对于不同的系统目标，通常采用不同的调度算法。本文将从多个角度来阐述调度算法
调度方法：动态静态算法
静态调度算法：
静态算法：调度策略已经确定，不考虑系统运行的状态。对系统cpu利用率比较高。
1..轮叫调度：以轮询的调度方式来请求不同的服务器。优点是简单，无需记录链接状态，它适用于假设服务器的处理性能相同，不管服务器的当前的链接数和响应时间。改算法不使用与服务器处理性能不一的情况，当请求服务时长差异较大是，会导致服务器负载不均衡
2.加权轮叫：它解决了服务器性能不一的情况，用相应的权值来代表服务器的性能好坏。该算法将服务器高低和轮询方式分配到请求服务器。权值高的优先分配链接请求，并能处理更多的连接。但如果连接请求处理服务时间变化较大时，单独的加权轮询算法依然会对导致服务器负载不平衡。
3.目标地址散列调度:改算法是根据请求目标地址的ip地址，作为散列的静态分配的散列表找出对应的服务器。若服务器可用未超载，将请求发往服务器，否则返回为空。
4.源地址散列调度：:改算法是根据源ip地址，作为散列键从静态分配的散列表找出对应的服务器。若服务器可用未超载，将请求发往服务器，否则返回为空。
动态算法
动态算法指负载平衡系统利用系统的信息，做出负载调度决策。其适用单用户/多用户共享集群环境，运行时对系统资源实施监控，并以此来作为掉度依据。不过缺点是及其消耗系统资源。
1.队列调度
1 .1先来先服务（队列调度）
先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
缺点：比较有利于长作业，而不利于短作业。 有利于CPU繁忙的作业，而不利于I/O繁忙的作业。
1.2最短优先（优先队列）
最短优先调度算法是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
缺点：长作业的运行得不到保证。
为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。
1) 非抢占式优先权算法
在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。
2) 抢占式优先权调度算法
在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i 时，就将其优先权Pi与正在执行的进程j 的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi>Pj，则立即停止Pj的执行，做进程切换，使i 进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。
在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a 提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：
由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：
由上式可以看出：
(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。
(2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。
(3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。
简言之，该算法考虑到了系统的任务的差异性，有考虑到系统服务器的硬件差异性。因此，该算法实现了一种较好的折衷。当然，在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销。
调度系统
LVS：
1.静态方法：
（1）、轮询:轮询调度是一种注重调度过程的调度算法。只在乎访问是否调度到后端服务器，不过后端服务器的性能是否能处理的过来。
（2）、加权：又叫加权轮询，是一种注重结果的调度算法。它会考虑后端服务器的的性能，
根据性能，管理者可以对服务器所的权重来合理的进行调度，
（3）、SH：Source Hashing，实现session sticky，源IP地址hash；将来自于同一个IP地址的请求始终发往第一次挑中的RS，从而实现会话绑定
（4）、DH：Destination Hashing；目标地址哈希，将发往同一个目标地址的请求始终转发至第一次挑中的RS，典型使用场景是正向代理缓存场景中的负载均衡，如：宽带运营商
动态方法：主要根据每RS当前的负载状态及调度算法进行调度Overhead=value较小的RS将被调度
（1）、LC：least connections 适用于长连接应用
Overhead=activeconns*256+inactiveconns
（2）、WLC：Weighted LC，默认调度方法
Overhead=(activeconns*256+inactiveconns)/weight
（3）、SED：Shortest Expection Delay,初始连接高权重优先
Overhead=(activeconns+1)*256/weight
（4）、NQ：Never Queue，第一轮均匀分配，后续SED
（5）、LBLC：Locality-Based LC，动态的DH算法，使用场景：根据负载状态实现正向代理
（6）、LBLCR：LBLC with Replication，带复制功能的LBLC
解决LBLC负载不均衡问题，从负载重的复制到负载轻的RS
Nginx
ip_hash源地址hash调度方法
(1)、least_conn最少连接调度算法，当server拥有不同的权重时其为wlc，当所有后端主机连接数相同时，则使用wrr，适用于长连接
(2)、hash key [consistent]基于指定的key的hash表来实现对请求的调度，此处的key可以直接文本、变量或二者组合
作用：将请求分类，同一类请求将发往同一个upstream server，使用consistent参数，将使用ketama一致性hash算法，适用于后端是Cache服务器（如varnish）时使用
hash $request_uriconsistent;
hash $remote_addr;
haproxy:
roundrobin：基于权重轮询，动态算法，支持权重的运行时调整，支持慢启动；每个后端backend中最多支持4095个server
server options：weight #
static-rr：基于权重轮询，静态算法，不支持权重的运行时调整及慢启动；后端主机数量无上限
leastconn：加权最少连接，动态算法，最少连接的后端服务器优先分配接收新连接，相同连接时轮询，推荐在较长会话的场景使用，例如MySQL、LDAP等，不适合http
first：根据服务器在列表中的位置，自上而下进行调度；前面服务器的连接数达到上限，新请求才会分配给下一台服务
source：源地址hash，新连接先按权重分配，后续连接按source分配请求
uri：对URI的左半部分或整个uri做hash计算，并除以服务器总权重取模，以后派发至某挑出的服务器,适用于后端缓存服务器://:@:/;?#左半部分：/;整个uri：/;?#url_param：对用户请求的uri听部分中的参数的值作hash计算，并由服务器总权重相除以后派发至某挑出的服务器；通常用于追踪用户，以确保来自同一个用户的请求始终发往同一个Backend Server
hdr()：对于每个http请求，此处由指定的http首部将会被取出做hash计算；并由服务器总权重相除以后派发至某挑出的服务器；无有效值的会被轮询调度
hdr(Cookie)
网友评论