서버시스템을 위한 공정하고 효율적인 스케줄링 알고리즘

학위논문 (박사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2014. 2. 조유근. ; 네트워크와 하드웨어의 발전으로 서버 시스템은 그 활용 범위가 넓어지면서 사용자의 요구가 다양해지며 동시에 높은 수준의 서비스 품질을 요구하고 있다. 이를 위해 서버 시스템은 서로 다른 요구사항을 포함하는 다양한 태스크들에게 한정된 자원을 공정하게 할당하고 대규모 요구에도 안정적으로 지원하도록 높은 효율성을 제공해야 한다. 하지만 기존 공정 스케줄링 알고리즘들은 편향 지분 분포를 가진 태스크 집합에 대해 태스크의 수가 커질수록 공정성이 낮거나 스케줄링 오버헤드가 커져 서버 시스템에 그대로 적용할 수 없다. 본 논문에서는 서버 시스템에서 공정하고 효율적인 스케줄링 알고리즘인 K-LZF를 제안한다. 새로운 태스크 만족 지수를 정의한 후, 그 기반에서 높은 공정성을 제공하며 O(N)의 시간 복잡도를 보이는 LZF 알고리즘을 제시하고 분석한다. 분석된 결과를 통해 높은 공정성을 유지하면서 상수 시간의 시간 복잡도를 갖도록 LZF 알고리즘을 근사화한다. 또한 K-LZF 알고리즘에서 K값의 변화를 통해 서버 시스템의 용도에 따라 공정성과 효율성의 성능을 조절할 수 있다. 다양한 분포를 가진 태스크 집합에 대한 시뮬레이션 결과들은 K-LZF 알고리즘이 대규모 편향 지분 분포에서도 LZF 알고리즘에 근사한 우수한 성능을 제공함을 보인다. 또한, AVOS 운영체제와 LINUX 운영체제에 구현하여 성능 평가한 결과는 K-LZF 알고리즘의 시간 복잡도가 서버 시스템에서 효율적으로 동작하기 적합한 O(K)임을 보인다. 이러한 결과들을 통해 다양한 종류의 태스크들이 혼재하거나 태스크 수가 많아지더라도 K-LZF는 확장성을 제공하여 서버 시스템의 스케줄링 알고리즘으로 적합하면서도 우수한 성능을 제공함을 입증한다. ; 제 1 장 서론 1 1.1 연구 배경 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 연구 목적 및 범위 . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 논문의 구성 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 제 2 장 관련 연구 7 2.1 가상 시간 (virtual time) 기반 스케줄링 알고리즘 . . . . . . . . . 7 2.1.1 WFQ(weighted fair queuing) 알고리즘 . . . . . . . . . . . 8 2.1.2 WF2Q(worst-case fair weighted fair queueing) 알고리즘 . . 9 2.2 라운드 로빈(round robin) 기반 스케줄링 알고리즘 . . . . . . . . 9 2.2.1 WRR(weighted round robin) 알고리즘 . . . . . . . . . . . 10 2.2.2 DRR(deficit round robin) 알고리즘 . . . . . . . . . . . . . 10 2.2.3 VTRR(virtual-time round robin) 알고리즘 . . . . . . . . . 11 2.3 혼합(hybrid) 기반 스케줄링 알고리즘 . . . . . . . . . . . . . . . . 12 ii 2.3.1 STRR(stratified round robin) 알고리즘 . . . . . . . . . . . 12 2.3.2 GR3(group ratio round robin) 알고리즘 . . . . . . . . . . . 13 2.4 기존 공정 스케줄링 알고리즘들의 비교 분석 . . . . . . . . . . . . 14 제 3 장 태스크 만족 지수와 LZF 스케줄링 알고리즘 16 3.1 시스템 모델 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 태스크 만족 지수 . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 태스크 만족 지수 기반 스케줄링 알고리즘 . . . . . . . . . . ...