멀티코어 시스템에서 공정성 보장을 위한 가상런타임 기반 로드밸런싱 알고리즘

• 배경지식
1. CFS (Complete fair cheduler)
• RSDL(Rotating Staircase Deadline Scheduler)
• 상위 우선 순위의 모든 프로세스가 라운드로빈실행
      -->할당 시간을 고갈시에 낮은 우선순위로 이동된다. 
• 우선순위 큐는 큐별로 CPU사용량이 제한된다.
     -->낮은 우선순위의 작업도 일정 대기시간 이후에는 작업가능
      -->순서 보장이 되지않아서 지연이 생길 수도 있다.
• CFS
• 실행 큐 배열을 사용하지 않는다.
      --> 모든 프로세스의 관리를 위해서 RB-TREE를 사용
  
• jiffies를 사용하지 않는다.
• HZ상수에 의존하지 않는다. 
• 나노초 단위의 정밀도를 갖는다. (기존 지피값의존, 밀리초 단위 정밀로)
• 자발적인 CPU반환(sleep, 우선순위)을 하지 않을 경우에는 모든 프로세스는 동일한 실행시간을 갖게된다. 
2. O(1) Scheduler
1. OS상에서 얼마든지 많은 process가 존재하더라도 연속된 시간 상으로 스케줄 가능하도록 설계된 스케줄러
2. Overhead 최소화 및 jitter최소화
3. fixed upper bound 실행 시간이 가능함을 보였다. 
4. 우선순위 값에 대해서 run queue를 사용해서 구형
• 본문
1. 리눅스 기본 스케줄러인 CFS는 클라우드 서비스와 같은 대규모 시스템에서 공정성 보장 안됨
   --> 공정성 보장 실패 원인 분석 및 해결책 제안
2. CFS의 scalability지원 미흡
       --> 수 많은 테스크에서 기아현상도 발생
       --> 논문에서는 CFS가 멀티코에서 공정성 보장 못함을 증명