[메소스] DRF 알고리즘

아파치 메소스의 DRF 관련

 최대 작업 수를 실행하고 자원을 가장 효율적으로 사용하기 위해 두 사용자의 자원을 어떻게 분배할 것인가 이다. 기존 알고리즘을 사용한다면 두 사용자 모두에게 동일한 크기의 자원을 할당할 수 있지만 이는 원하는 것이 아니다. 이러한 상황을 이기종 환경(heterogeneous environment)이라고 부른다.

아파치 메소스는 DRF(Dominant Resource Fairness)라는 알고리즘을 구현하며, DRF 알고리즘을 메소스의 자원 할당의 기본 정책으로 사용하고 있다.

대개 DRF 알고리즘을 대학 수준의 운영 체제 과목에서 가르친다. 작업 스케줄링(job scheduling)은 CPU에만 제한되지 않으며 메모리, 네트워크, 디스크와 같은 여러 자원이 존재한다. 그러나 자원 유형을 줄여 문제를 단순화하면 어떤 작업은 프로세서 집약적이고 다른 작업은 디스크 집약적이고, 또 다른 작업은 메모리 집약적이기 때문에 최대-최소 공정성(max-min fairness) 알고리즘이 실패(강력하지 않고 효율적이지 않음)하는 것을 볼 수 있다.

여기에 이기종 환경의 각 사용자에게 자원을 공평하게 분배할 수 있는 자원 스케줄링 메커니즘이 필요하다. 요컨대 DRF 알고리즘은 이기종 자원을 가진 시스템에 최대-최소 공평성 알고리즘을 적용한 것이다.

자원이 사용자 간에 동등하게 분배되지 않으면 DRF 알고리즘에 가중치가 적용된다고 말한다. 공유는 사용자별, 자원 수준별로 가중치를 적용할 수 있으며 사용자별이 더 많이 사용된다.

가중치가 적용된 알고리즘에는 가중치 외에 다음 기능을 더 가진다.

* 공정한 분배(envy freeness) : DRF 알고리즘은 다른 사용자의 자원 할당을 부러워할 필요가 없기 때문에 자유롭다. 가장 낮은 지배 점유율을 가진 사용자에게 자원을 제공하기 때문에 모든 사용자는 동일한 기회를 가질 수 있다.

* 파레토 효율(Pareto efficiency) : 특정 사용자의 통제 관심도를 높이면 자원에 대한 다른 사용자의 지배적인 참가가 비례적으로 감소한다. 한 사용자에게 더 많은 자원을 할당하면 다른 사용자에게 피해를 준다.

* 점진적인 충전(progressive filling) : DRF 알고리즘은 모든 사용자에 대해 동일한 비율로 지배 점유율을 증가시킨다. 다른 알고리즘은 수요에 따라 자원을 할당한다. DRF는 자원이 고갈되면 사용자가 자원을 해제하고, 다른 사용자가 재귀적으로 진행될 때 종료되며, 지배 점유율을 가진 사용자가 증가할 때까지 프로세스는  계속된다.

* 점유율 보장(share guarantee) : 모든 사용자의 지배 점유율 할당은 동일한 비율로 증가하므로 사용자를 동등하게 대우하고, 적어도 하나의 자원 일부는 보장된다.

* 전략 증명(strategy proof) : 사용자는 사용자 자신의 자원 요구를 위조할 수 없다. 한 사용자가 더 많은 자원을 요구하면 DRF 알고리즘은 사용자를 방해하지 않는다.

* 참고 자료

DRF 관련 논문

https://cs.stanford.edu/~matei/papers/2011/nsdi_drf.pdf

여기에 좋은 psedo 코드가 있다.

https://en.wikipedia.org/wiki/Envy-free_cake-cutting

분배 개념은 사회학적으로 나온 얘기였다. 전문용어를 여기서 배울 줄이야.

http://s-space.snu.ac.kr/bitstream/10371/52804/3/04%20envy-free.pdf