Load balancing 알고리즘 비교&분석

 

github 주소:  아직 안올렸음

 

 

1          프로젝트 목표

 

그림 1 프로젝트 목표

 

 

그림과 같이 바리스타가 있고, 각 손님들이 주문을 한다. 그 주문들을 바리스타들에게 어떻게 효율적으로 분배할 것인가에 대한 것이 이번 프로젝트의 주제이다. 이러한 분배에 관한 알고리즘을 Load Balancing 알고리즘이라 한다. 이번 프로젝트에서 우리는 4개의 알고리즘을 실행하고 이를 그래픽적으로 보여주는 프로그램을 제작한다. 또 한 4개의 알고리즘을 비교하여 어느 알고리즘이 효율적인 알고리즘인지 분석한다. 효율적인 Load balancing 알고리즘이란, 바리스타, 주문과 조건이 있을 때, 같은 조건에 대해 전체 실행 시간이 가장 작은 알고리즘을 뜻한다. 뿐만 아니라, 각 손님이 기다리는 시간 까지도 고려해줘야 한다. 그러기 위해선, 각 바리스타가 최대한 놀지않도록 주문을 효율적으로 분배해야 한다. 그리고 각 알고리즘의 특징을 분석해 어떤 상황에서 유리하고 불리한지 찾아낸다.

 

 

 

2          수행 내용 및 중간 결과

2.1     계획서 상의 연구내용

 먼저 우리는 특징이 잘 드러나는 Load Balancing 알고리즘들을 찾는 작업들을 하였다. 만약 실제로 이런 상황에 놓인다면 어떻게 할까 로도 생각해보았고, 컴퓨터가 가장 효율적으로 처리할 수 있는 알고리즘은 무엇일까 도 생각해 보았다. 그래서 단순한 알고리즘부터 시작해서 복잡해지는 순서대로 알고리즘을 생각하여, 결과적으로는 다음과 같은 4개의 알고리즘을 생각하였다. 그 4가지 Load balancing Algorithm는 다음과 같다.

 

1.     각 바리스타에게 순서대로 한 명씩 주문을 할당한다.

2.     해당 음료수를 가장 빨리 만드는 바리스타에게 주문을 할당한다.

3.     만들어야 하는 주문의 걸리는 시간 총 합이 가장 낮은 바리스타에게 할당한다.

4.     현재 주문을 포함하여, 만들어야 하는 주문의 걸리는 시간 총 합이 가장 낮은 바리스타에게 할당한다.

 

 

2.2     수행 내용

 이제 위의 기술한 4개의 Load Balancing 알고리즘들을 프로그램들도 구현해야한다. 일단, 그래픽적인 요소는 생각하지 않고, 4개의 알고리즘에 대해 실행시간 결과가 나타날 수 있도록 구현했다. 그리고 결과 뿐만 아니라 프로그램 중간중간의 과정을 모두 나타내도록 구현하였다. 

 프로그램은 각 바리스타마다, 또 각 주문 마다 객체화 하여 객체지향적으로 만들었다. 그리고, 각 바리스타마다 큐를 하나씩 만들어 주었다. 문제에서 요구하는 대로 주문 정보를 파일로 입력 받아, 주문 큐에 넣도록 하였고, 그 주문들을 각 알고리즘에 따라 특정 바리스타의 큐에 넣도록 구현하였다. 그리고 이 일이 모든 주문들에 대해 행해지면, 그 다음 각 바리스타들이 주문들을 처리하는 프로세스를 만들었다. 프로세스가 모두 진행되면, 바리스타들이 주문을 모두 처리하는데 걸리는 시간을 나타내었다.

 

 

 

3          최종보고서 본문

 

3.1 프로그램 소개

 

 프로그램을 전체적으로 봤을 때, 두 부분으로 나눌 수 있다. 첫 번째는 각 주문을 어떤 바리스타가 만들지 할당하는 과정이다. 이 과정에서는 각 주문들을 알고리즘에 따라 특정한 기준을 가지고 특정 바리스타에게 할당해준다. 어떤 기준을 가지고 주문을 바리스타에게 할당하는지가 이번 과제는 Load balancing Algorithm의 핵심이다. 두 번째는 각 바리스타에게 할당한 주문들을 바리스타들이 만드는 과정이다. 이 과정은 앞에서 분류한 Load balancing Algorithm에 따라 실제로 어떠한 과정으로 어떠한 결과가 나타나는지 볼 수 있다. 

 그리고 우리 프로그램에서는 알고리즘의 과정과 결과를 그래픽적으로 나타내는 것까지 만들었다. 주문들을 바리스타들에게 나누는 과정과 그 이후 만드는 과정까지 모두 볼 수 있다. 프로그램이 모두 진행 된 이후에는 알고리즘에 따라 시간이 얼마나 걸렸는지 나타내준다, 

 

 이 프로그램의 실행 흐름은 다음과 같다.

1.     이 카페에 존재하는 음료 리스트를 입력 받는다.(coffee.txt)

2.     바리스타의 명 수와 각 바리스타가 각 음료를 만드는 시간을 입력 받는다.(barista.txt)

3.     문제에서 제시한 형태로 주문들을 입력 받는다.(order.txt)

4.     받은 주문을 순서대로 특정 바리스타에게 할당해준다. (Load balancing Algorithm)

5.     모든 주문에 대해 4가 완료되었으면 음료 제작을 시작한다.

6.     음료 제작에 걸린 시간을 표시하며, 프로그램은 종료된다.

 

 

 

그림 2 coffee.txt

 

 

 

 

그림 3 barista.txt

 

 

 

 

그림 4 order.txt

 

 

 

3.2 알고리즘 설명

 

 M 명의 바리스타가 있고 N 개의 음료 주문이 있을 때, 주문들을 바리스타에게 할당하는 4가지 Load balancing Algorithm 을 구현, 분석하였다. 그 4가지 Load balancing Algorithm는 다음과 같다.

 

1.     각 바리스타에게 순서대로 한 명씩 주문을 할당한다.

2.     해당 음료수를 가장 빨리 만드는 바리스타에게 주문을 할당한다.

3.     만들어야 하는 주문의 걸리는 시간 총 합이 가장 낮은 바리스타에게 할당한다.

4.     현재 주문을 포함하여, 만들어야 하는 주문의 걸리는 시간 총 합이 가장 낮은 바리스타에게 할당한다.

 

1.  각 바리스타에게 순서대로 한 명씩 주문을 할당한다.

 개념: 이 알고리즘은 M명의 바리스타에게 0번 바리스타부터 M-1번 바리스타까지             순서대로 주문을 할당하는 방식이다.

  구현: 주문 큐에서 주문을 하나 뽑은 후, 각 바리스타의 큐에 순서대로 주문을 넣는다.

 

 

 

그림 5 순서대로 할당

 

 

2.  해당 음료수를 가장 빨리 만드는 바리스타에게 주문을 할당한다.

 개념: 이 알고리즘은 Load balancing Algorithm 을 실행하기 전에 미리 각 바리스타가 각각의 음료를 만드는 시간을  받아 놓는다. 그리고 각 음료수에 대해 가장 빨리 만드는 바리스타를 미리 1:1 맵핑 시켜 놓는다. 그리고 각 주문에 해당하는 음료를 가장 빨리 만들 수 있는 바리스타에게 주문을 할당한다.

 구현: barista.txt 파일을 읽어 각 바리스타가 각 음료를 만드는 시간을 2차원 배열형태로 저장해 놓는다. 그리고, 각 주문에 대해 가장 빨리만드는 바리스타의 넘버를 1:1맵핑시킨 테이블을 만든다. 그리고 주문 큐에서 주문을 하나 뽑은 후, 테이블을 검색하여 그 음료를 가장 빨리 만드는 바리스타의 주문 큐에 넣는다.

 

 

 

그림 6 잘 만드는 바리스타에게 할당

 

 

3.  만들어야 하는 주문의 걸리는 시간 총 합이 가장 낮은 바리스타에게 할당한다.

 개념: 이 알고리즘은 현재 각 바리스타에게 할당된 음료 주문을 모두 만드는데 필요한 시간이 가장 적은 바리스타에게 주문을 할당하는 방식이다. 

 구현: barista.txt 파일을 읽어 각 바리스타가 각 음료를 만드는 시간을 2차원 배열형태로 저장해 놓는다. 또 한 음료를 할당할 때 마다 현재 바리스타에게 할당된 모든 음료를 만드는데 걸리는 시간을 계속 더한다. 그렇게 하면서 주문 큐에서 주문을 하나 뽑은 후, 음료 제작 총 시간이 가장 적은 바리스타를 찾아 그 바리스타의 주문 큐에 넣는다.

 

 

 

그림 7 가장 작은 시간에 할당

 

 

4.  현재 할당 할 주문을 포함하여, 만들어야하는 주문의 걸리는 시간 총 합이 가장 낮은 바리스타에게 할당한다.

 개념: 3번 개념과 비슷하다. 3번 알고리즘이 할당된 음료 제작 총 시간만을 따졌다면, 이 알고리즘은 할당 할 음료의 제작시간까지 함께 고려하여 최소인 바리스타를 찾아, 그 바리스타에게 주문을 할당한다.

 구현: 3번과 동일하지만, 최소 시간을 따질 때, 현재 음료의 주문 시간까지 생각하였을 때 최소인 바리스타를 찾는다.

 

 

 

그림 8 할당했을 때 가장 작은 시간에 할당

 

 

3.3 알고리즘 분석.

 

효율적인 Load balancing Algorithm이란, 같은 조건에 대해 전체 실행 시간이 가장 작은 알고리즘을 뜻한다. 뿐만 아니라, 각 손님이 기다리는 시간 까지도 고려해줘야 한다. 그러기 위해선, 각 바리스타가 최대한 놀지않도록 음료를 만드는 시간이 비슷해야 한다. 누구는 음료를 만들고 있고, 누구는 놀고 있으면 필연적으로 실행시간이 클 수밖에 없다.

 

1.  순서대로 할당 

-       장점: 딱히 없다. 굳이 따지자면 구현하기 쉽다.

-       단점: 매우 비효율적이다. 음료를 균형적으로 분배할 수 있는 가능성이 전혀 없다

-       아래 그림을 보면 바리스타 3은 이미 음료를 다 만들고 놀고 있다.

 

 

 

그림 9 순서대로 할당

 

 

2.  가장 잘 만드는 바리스타에게 할당

-       장점: 각 바리스타가 자신이 가장 잘 만드는 음료가 하나씩 있으면 효율적일 가능성이 높다.

-       단점: 주문이 한 품목에 치우쳐져 있으면, 그 품목을 가장 잘 만드는 사람만 일하게 된다.

음료의 수보다 바리스타의 수가 많을 경우 필연적으로 아무 것도 하지 않은 바리스타가 반드시 생긴다.

-       아래 그림을 보면 바리스타0 과 바리스타1은 아예 주문을 하나도 할당 받지 못하고 놀고있다.

 

 

 

그림 10 잘 만드는 바리스타에게 할당

 

 

3.     음료 제작의 총 시간이 가장 적은 바리스타에게 할당

-       장점: 주문이 모든 바리스타에게 균등하게 분배 될 확률이 높다.

-       단점: 할당할 때 마다 최소 음료 제작 시간을 가진 바리스타를 찾는다. 이 작업은 바리스타의 수n에 대하여 O(n)시 간이 소요된다. 1,2번 알고리즘은 할당 작업이 O(1)에 걸리는 데 반해, n의 수가 크면 비교적 프로그램의 실행 시간이 커질 수 있다. 

-       아래 그림을 보면 모든 바리스타가 비슷한 시점에 일이 끝나가는 것을 볼 수 있다.

 

 

 

그림 11 가장 작은 시간에 할당

 

 

4.     할당할 음료의 제작 시간을 포함했을 때, 총 시간이 가장 적은 바리스타에게 할당

-       장점: 3번 알고리즘처럼 비교적 균등하게 분배 될 것이다.

-       단점: 3번 알고리즘과 동일하다.

-       아래 그림을 보면 모든 바리스타가 거의 비슷한 시점에 일이 끝났다는 것을 알 수 있다.

 

 

 

그림 12 할당했을 때 가장 작은 시간에 할당

 

 

3.4 알고리즘 비교

 

 가장 일반적인 동일한 인풋에 대해 4개의 알고리즘 실행 결과는 다음과 같다.

 

 

 

그림 13 1번 알고리즘 결과

 

 

 

 

그림 14 2번 알고리즘 결과

 

 

 

 

그림 15 3번 알고리즘 결과

 

 

 

 

그림 16 4번 알고리즘 결과

 

 

 

 

1번 알고리즘은 나머지 알고리즘과의 비교를 위해 넣었기 때문에, 단순한 만큼 비효율적이다.

2번 알고리즘은 특수한 상황에서만 효율적 이기 때문에 평균적으로는 굉장히 비효율적이다.

3번 알고리즘은 일반적인 상황에서 효율적이다.

4번 알고리즘도 일반적인 상황에서 효율적이다.

 

 위의 결과를 통해 3번, 4번 알고리즘이 효율적인 Load balancing 알고리즘이라는 것을 볼 수 있다. 3번 알고리즘과 4번 알고리즘은 상황마다 시간이 더 적게 걸리는 알고리즘이 다르기 때문에 서로 뭐가 더 좋은 알고리즘인지 우열을 가릴 수 없다. 하지만, 그 둘의 차이는 1번, 2번 알고리즘에 비하면 미세하기 때문에 3번, 4번 알고리즘 둘다 충분히 효율적인 알고리즘이라고 할 수 있다.

 하지만 두 알고리즘이 항상 최선의 결과라고 할 수는 없다. 그 이유는 현재의 선택이 어떤 식으로든 뒤의 선택들에 영향을 미치기 때문이다. 즉, 미래를 예측할 수 없기 때문에 매 순간 최선의 선택을 하는 알고리즘은 존재하지 않는다.

 

4. 결론

 

 이 프로젝트에서는 프로그램 실행 시간에 주문을 각 바리스타에게 분배하는 시간은 전혀 고려하지 않았다. 분배가 완료 된 후, 바리스타들이 음료를 만들기 시작하는 순간부터 시간을 계산하였다. 그 이유는 문제 자체가 바리스타가 커피를 만드는 일이었기 때문이다. 굳이 사람이 커피를 만드는 과정이 아니더라도 분배하는 과정은 컴퓨터가 계산하는 과정이고, 만드는 과정은 방법에 따라 제품을 제작하는 일이기 때문에 컴퓨터의 계산 속도는 이에 비하면 매우 작은 속도이다. 그렇기 때문에, 이 프로그램에서는 분배 완료 후, 제품 제작 시의 시간만을 비교하여 효율적인 알고리즘을 탐색하였다. 

 만약 제작의 과정도 컴퓨터가 하는 일이라는 등의 이유로, 분배 과정의 시간이 제작 과정의 시간에 비해 충분히 작지 않는 시간이라면, 3,4번 알고리즘도 결코 좋은 알고리즘이라고 할 수 없다. 이 프로그램에서 분배의 과정만 봤을 때, 바리스타의 수를 M, 주문의 수를 N이라 해보자. 이 때, 1번, 2번 알고리즘은 분배의 시간 복잡도가 O(N)인 반면, 3번, 4번 알고리즘은 분배의 시간 복잡도가 O(NM)이 된다. 그렇기 때문에 3번, 4번 알고리즘도 효율적인 알고리즘이라고 할 수 없다. 

 하지만, 문제의 특성을 생각했을 때, 제품의 주문 수(N)는 무수히 커질 수 있지만, 제품을 만드는 사람 또는 기계(M)가 무수히 많아질 리가 없기 때문에, 이 프로젝트에서는 3번, 4번 알고리즘이 효율적인 알고리즘이라고 할 수 있다.

 

5. 자기평가

 

 이번 프로젝트에서 4개의 알고리즘을 생각해보고 구현하면서, 이상적인 선택을 하는 것은 그 만큼 따져야 할 조건이 많다는 것을 알았다. 그리고 그 조건들을 따지는 것이 결국 알고리즘 실행 시간의 영향을 미친다는 것을 깨달았다. 실질적으로 이런 문제가 일어난다면 위의 4개와 같은 알고리즘 외의 많은 알고리즘의 장점을 뽑아낸 복합적인 알고리즘을 사용할 것이라고 생각한다.

 

 제시된 구체적인 상황에 대해서는 매우 잘 분석하였고, 잘 프로그래밍 되었다고 생각한다. 하지만, Load balancing 알고리즘들을 비교, 분석하는 것이 주제인 만큼, 프로그램적으로 세부적인 부족함은 많이 존재한다. 복합적인 알고리즘도 구현해보면 어땠을까 하는 아쉬움이 조금 남는다.