OS 스케줄링

[CS] OS 스케줄링(Linux)

멀티 쓰레드, 멀티 코어로 발전하면서, 스케줄링이 진화되었다. 기본적인 라운드로빈 스케줄링에서 현재 리눅스에서 사용하고 있는 CFS까지 스케줄링의 발전에 대해 살펴본다. 스케줄링에 대한 고려사항은 cpu의 활용(utilization), 처리율(throughput), 교환시간최소화(turnaround time), 공정성(fairness)이다.

비선점 스케줄링

비선점으로 이뤄지니, 하나의 작업이 모두 끝날때까지 대기하며 긴급한 작업이 필요해도 우선시 할 수 없다는 단점이 있다. 비선점으로하면 컨텍스트 스위칭은 적으나 긴 실행시간을 가진 작업으로 인해 다른 프로세스들이 오래기다릴 수 있다.

1. FCFS (First Come First Served)
   • 큐에 도착한 순서대로 CPU 할당
   • 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
2. SJF (Shortest Job First)
   • 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
   • FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
3. HRN (Hightest Response-ratio Next)
   • 우선순위를 계산하여 점유 불평등을 보완한 방법(SJF의 단점 보완)
   • 우선순위 = (대기시간 + 실행시간) / (실행시간)

선점 스케줄링

우선순위 스케줄링과 라운드 로빈이 있다. 우선순위 스케줄링은 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리한다. 우선 순위가 낮은 프로세스가 무한정 기다리는 Starvation 이 생길 수 있으나 Aging 방법으로 Starvation 문제 해결 가능하다.

아래의 설명에서 RQ는 Run Queue를 의미하고, Tick은 하나의 작업당 CPU를 점유할 수 있는 최대시간을 의미한다. 즉 하나의 틱이 끝날때마다 우선순위를 따져 기존 작업을 유지하거나, 새로운 작업을 시작한다. 또한 여기서 버전은 리눅스 버전을 의미한다.

라운드호빈

라운드로빈은 FIFO로 정해진 시간 틱마다 queue에 있는 순서대로 task를 실행한다. 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 문맥 교환 (Context Switching) 잦아져서 오버헤드 증가

O(N): v2.4

O(N) 알고리즘은 신용매커니즘을 사용한다. 매 tick마다 현재 실행중인 task의 credit을 감소시키고, 가장 높은 goodness를 가진 것을 선택한다. I/O 관련 인터럽트로 인해 자신에게 부여받은 시간을 다 쓰지 못했다면 이를 다음 실행할 때 시간을 주어 보상한다. 하지만 해당 알고리즘은 O(N)으로 task의 수가 커지면 연산시간이 너무 오래걸린다.

• 알고리즘
  1. 한 Tick마다 현재 실행중인 task의 credit을 감소시킴
  2. RQ에 있는 모든 task의 goodness를 계산함
  3. 가장 높은 것을 선택하여 실행
  4. 입출력관련으로 interrupt되었을 경우처럼 자신이 실행해야하는 시간을 다 쓰지 못했을 때, Re-credit이 실행됨. 자신이 쓰지 못한 조각을 다음 epoch(실행)때 씀.
  5. 모든 task의 credit이 0이 되면 다시 Re-credit이 일어남.(우선순위에 비례하여)
• 단점
  • task의 양이 많아지면, 스케줄링연산에 시간이 너무 많이 소요
  • multi core일 때는, RQ에 대한 lock(동기화)가 필요하므로 확장성의 문제가 있음.

O(1) v2.6

O(1)알고리즘은 O(1)연산이 가능하며, 우선순위를 통해 시간을 차등적으로 분배한다. 우선순위는 정적, 동적 두가지가 있다. 정적 우선순위(Nice value)는 사전에 정의되며 시스템 콜에 의해 바뀔 수 있으나, 스케줄러는 전혀 관여하지 않는다.

동적 우선순위는 인터럽트에 의해 실행하지 못하고 남은 시간을 보상 등 여러 요소에 의해 우선순위를 변동시킨다.

Time slice : 우선순위에 의해 시간이 차등적으로 분배된다.

• 알고리즘
  1. 스케줄러가 active RQ에서 우선순위가 가장 높은 task를 실행시킴
  2. 자신의 시간을 다 쓰면 expired RQ로 이동
  3. 만약 active RQ가 비게되면, expired RQ랑 바꿈(그러면 이제 비어있는 queue가 expired RQ)
  4. 할당되는 시간은 우선순위에 비례하고, 우선순위는 4번의 swap이 일어날 때, 동적으로 다시 계산됨(입출력 등에 의해 실행되지 못한 시간을 여기서 반영함)
• 단점
  • 공정성 부족
    • 낮은 우선순위랑 높은 우선순위랑 cpu time이 너무 차이가남. priority 39 = 100ms, p1 = 10ms p0 = 5ms → 1이랑 0이랑 50%가 차이나는 격.
  • expired queue에 있는 task의 기아발생
    • 계속해서 새로운 task가 생겨나면 active RQ에 들어가기때문에 expired RQ에 있는 Task가 오랫동안 실행되지 못하며 기아상태 위험이 있다.

CFS 스케줄링(Completely Fair Scheduler) v2.6.23

CFS는 O(1)의 공정성 문제를 해결하기 위해 도입된 알고리즘이다. 현재도 리눅스에서 사용한다. 우선 Task를 두개로 구분한다. 실시간 처리가 필요한 테스크와 그 외의 테스트로 구분한다. 실시간 Task는 리스트형태로 진행되고, 그외의 테스크는 Red Black Tree에서 관리한다. 최종으로 RQ는 오른쪽과 같은 모습이다. 실시간 처리 테스크는 우선순위에 의해 바로바로 실행된다. 우리는 이제 일반적인 테스크를 처리하는 방법에 대해 알아본다.

O(1)의 문제를 해결하기 위해, 실제로 작은 실행시간을 가진 프로세스를 먼저 실행하려고 한다. 즉, 우선순위상수가 아닌 전체시간 중에 실행시간에 대한 %로 시간을 할당한다. VR(가상실행시간)을 기준으로 RB 트리는 정렬된다.

여기서 $W(\tau_i)$는 Task의 가중치이고, $W_0$ 은 초기값을 의미한다. $R(\tau, t)$은 실행시간을 의미한다.

1. Task를 선택하는 기준은 가장 작은 VR(가상의 실행시간)값을 가진 프로세스이다.
2. 부여되는 시간은 Time slice는 $TS_{\tau_i} = \frac {W(\tau_i)} {W _\text{total}}\times \text{Scheduling Latency} (L)$

3. Virual Runtime은 $VR(\tau, t) = \frac{W_0}{W(\tau_i)} \times R(\tau, t)$으로 계산한다.

   $\text{VR}{next}=\text{VR}{current} + 위의 연산값$ 으로 VR의 값은 누적된다.

스케줄링 지연시간은 스케줄 단위로, 모든 Task가 한번씩은 실행될 수 있는 시간이다. 만약 스케줄링 지연시간(Scheduling Latency)이 Task의 개수 * 최소 보장시간보다 작으면 Task의 개수 * 최소 보장시간으로 바꾼다. 결국 하나의 turn에는 모든 task가 공평하게 한번씩은 실행된다. 이를 통해 공평성을 최대한 유지한다.

• 불공평
  • 새로 생성된 Task들은 VR이 0으로 초기화되기 때문에, 기존의 task가 오랫동안 실행되서 VR이 상당히 높다면 새로 생성된 Task가 너무 길게 실행됨 → 새로운 불평등 → 초기값으로 0이 아니라, 기존의 VR중 제일 작은 값을 부여!.

      static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
      {
      if (!(flags & ENQUEUE_WAKEUP || flags & ENQUEUE_WAKING))
          se->vruntime += cfs_rq->min_vruntime; // 불공평 문제 해결하는 코드
      update_curr(cfs_rq);
      }