Weighted Round Robin - 带权轮询算法


带权轮询调度”(Weighted Round-Robin Scheduling,WRR)
http://blog.163.com/s_u/blog/static/1330836720105233102894/
由于每台服务器的配置、安装的业务应用等不同,其处理能力会不一样。所以,我们根据服务器的不同处理能力,给每个服务器分配不同的权值,使其能够接受相应权值数的服务请求。
假设有一组服务器S = {S0, S1, …, Sn-1},W(Si)表示服务器Si的权值,一个指示变量i表示上一次选择的服务器,指示变量cw表示当前调度的权值,max(S)表示集合S中所有服务器的最大权值,gcd(S)表示集合S中所有服务器权值的最大公约数。变量i初始化为-1,cw初始化为零。
带权值的轮询算法是常用的选择算法,常在对选择集合中各被选元素优先级不等的集合进行选择时使用。虽然被选集合元素的优先级(以后用权值表示)不等,但在选择时需要一个当前权值来决定应该选择哪一个元素。在选择时需要从上次选择元素之后开始进行,如果循环到集合开始开始处(也即开始新一轮的选择),需要降低当前权值,然后从集合中找到首先大于权值的元素。这样随着当前权值不断降低,能够被选中的元素的范围也就由权值从大到小的顺序不断扩张。从而实现了选择的顺序从权值由高到低的顺序进行。在当前权值变化到0时,需要再次将权值置为最高,从而进行下一轮循环。
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;
}
http://techcodecorner.blogspot.com/2014/03/the-weighted-round-robin-schedulingis.html
class WeightedRounRobin {

    Scanner sc = new Scanner(System.in);
    int[] S, W;
    int size, i = -1, cw = 0, max, gcd;

    WeightedRounRobin(int size) {
        this.size = size;
        W = new int[size];
        S = new int[size];

    }

    public void execute() {
        for (int j = 0; j < size; j++) {
            System.out.print("Enter weight of P" + (j + 1) + ":");
            W[j] = sc.nextInt();
        }
        max = getMaxValue(W);
        gcd = new GCD().getGcdOfArray(W);

//        algorithm
        System.out.println("Scheduling sequence will be as follow");
        while (true) {
            i = (i + 1) % size;
            if (i == 0) {
                cw = cw - gcd;
                if (cw <= 0) {
                    cw = max;
                    if (cw == 0) {
                        return;
                    }
                }
            }
            if (W[i] >= cw) {

                System.out.print("P" + i + "\t");
            }
        }

    }

    private int gcd(int number1, int number2) //Finds GCD of 2 numbers.
    {
        if (number2 == 0) {
            return number1;
        }
        return gcd(number2, number1 % number2);


    }

    public int getGcdOfArray(int[] arr) {
        int result = arr[0];
        for (int i = 1; i < arr.length; i++) {
            result = gcd(result, arr[i]);
        }
        return result;
    }
}




# 最大公约数
def gcd(nums):
    m = nums[0]
    for n in nums[1:]:
        while n != 0:
            m, n = n, m % n
    return m

# Weighted Round-Robin Scheduling
def wrr_select():
    current = N - 1
    current_weight = 0

    while True:
        current = (current + 1) % N
        if current == 0:
            current_weight -= gcd(weight)
            if current_weight <= 0:
                current_weight = max(weight)
        if weight[current] >= current_weight:
            yield current

wrr_test = wrr_select()
for i in range(1000):
    print(wrr_test.__next__())
http://www.jianshu.com/p/a6a56f107327
Round-Robin Scheduling,RR
N = 3

# Round-Robin Scheduling
def rr_select():
    last = N - 1
    while True:
        current = (last + 1) % N
        last = current
        yield current

rr_test = rr_select()
for i in range(1000):
    print(rr_test.__next__())
http://kb.linuxvirtualserver.org/wiki/Weighted_Round-Robin_Scheduling
https://svn.apache.org/repos/asf/cassandra/trunk/src/java/org/apache/cassandra/scheduler/RoundRobinScheduler.java
随机性考虑
WRR的运行结果是固定的,如果需要考虑随机性的话,需要再做一些额外工作。简单的话可以先对队列的顺序做随机,但这样实际的顺序还是固定的。可以按实际需要频繁暂存一定(随机)数量的结果,再随机处理后依次输出。

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts