7-1. Task Scheduling in Linux (1)

중앙대학교 3-2 리눅스 응용 설계 (손용석 교수님) 과목 정리입니다.

Scheduling?

• OS는 한 번에 2개 이상의 task를 실행 가능한 메모리에 load할 수 있다.
• load된 task들은 time multiplexing을 사용하여 CPU 자원을 공유한다.

Goals of Scheduling

모든 scheduler는 다음의 규칙을 따르기 위한 strategy를 선택한다.

• Utilization (효율)
  • CPU가 유용한 work로 최대한 바쁜 상태로 유지한다.
• Throughput
  • 시간당 처리되는 task의 개수를 최대화한다.
• Turnaround time
  • task가 시작되는 시간과 끝나는 시간 사이의 시간을 최소화한다.
• Fairness
  • 각각의 task가 CPU를 공평하게 공유하도록 한다.

Linux Scheduler Evolution

Round Robin Scheduling

Terminology

• Time slice
  • 각 task가 preempt되지 않고 실행되도록 한다.
  • 보통 10~100ms
• Round robin interval
  • one round를 완료하기 위해 다음과 같은 시간이 소요된다.
  • round roubin interval = time slice x n
  • n : run queue에 존재하는 task의 개수
  • one round는 run queue에 존재하는 모든 task가 실행된 총 시간

Basic concept

• 간단하고, 구현하기 쉬우며 starvation이 일어나지 않는다.
• 각 task마다 time slice가 할당된다.
• one round마다 각 task는 한 번의 time slice를 실행한다.
• 기본적으로 task는 FIFO 순서로 스케줄링된다.
  • task의 time slice가 만료된 후에, task는 run queue의 끝에 추가되고 preempt 된다.

Round Robin Example

O(N) Scheduling

Terminology

• linux의 priority level
  • 총 140개의 level 존재
  • Real-Time task (1~100) , normal task (101~140)
    
    • normal task의 priority는 nice value로 불린다. (-19 ~ 20)
    • 높은 (낮은) nice value는 낮은 (높은) priority를 갖는다.
• Credit (scheduling 실행 중에 변경 가능)
  • CPU를 사용하기 위한 마일리지 포인트
  • credit의 크기 = task의 priority
• Goodness G
  • task의 CPU 사용 필요성 측정
    • G = -1000 : 절대 선택 안 함
    • G = 0 : credit을 다 쓴 것
    • 0 < G < 1000 : task credit이 남아있음
    • G ≥ 1000 : real-time task

Basic concept

• time-shared interactive system을 구현하는 가장 간단한 방법
• Throughput + interactivity
  • interactivity 향상을 위해, O(N) scheduler는 I/O bound (blocked) task에 대해 recredit mechanism을 채택한다.
• Ex. T1이 I/O bound task라고 가정한다.
  • I/O bound task의 경우 time slice를 모두 사용할 수 없을 수도 있다.
  • T1이 2초를 사용하고, Time Slice 10초인 경우, 남은 8초는 T1 의 priority를 증가시키는데 사용하여 다음 cycle에 더 길게 실행할 수 있게 해준다.

Algorithm

• at every scheduling tick,
  • 현재 실행중인 task의 credit을 감소시킨다.
  • run queue 안에 각각 task의 goodness를 계산한다.
  • highest 선택
  • 모든 time slice를 사용하지 않았다면 re-credit (I/O bound (blocked) tasks)
    • 남은 시간의 절반을 추가하여 다음 epoch에 더 길게 실행할 수 있도록 한다.
  • 모든 credit이 0이 되었다면 모든 존재하는 task를 Re-credit
    • credit 보충

Example of O(N) Scheduling

• Priority == Credit
• Goodness = Priority + Credit

T1 Goodness : 100 → highest

T2 Goodness : 80

T3 Goodness : 20

• 만약 Goodness가 같은 경우, task를 변경하는데 있어 enqueue, dequeue하는데 overhead가 발생하고 cache를 사용할 수 없게 된다. (context switching 발생)

• credit이 0이면 goodness가 0

• 모든 task의 credit이 0이 되었다면 re-credit 실행

Shortcoming of O(N) scheduler

• task의 수가 많으면, scheduler가 많은 CPU time을 사용한다.
  • 실행할 다음 task를 선택하기 위해 현재 모든 task를 반복해야 하므로 scheduler는 O(N) 시간에 실행된다. (N은 task의 수)
• multi-core의 scalability 문제
  • single run queue의 global lock을 사용하기 때문

O(1) Scheduling

Terminology

• static priority
  • 모든 normal task는 nice value라는 static priority를 갖는다.
  • nice() system call에 의해 변경될 수 있다.
  • Scheduler는 task의 static priority를 절대 바꾸지 않는다.
• Dynamic priority
  • O(1) scheduler는 I/O bound task에 보상해주고, CPU-bound task는 페널티
    • static priority를 더하고 빼서 구현 가능
    • maximum priority bonus와 penalty는 +5 / -5
• Time Slice
  • Task의 time slice는 dynamic priority에 따라 할당된다.
  • 1개의 dynamic priority level 차이 = 5ms time slice

Basic concept

• 각 CPU마다 active / expired run queue
  • 각 run queue는 priority level에 대한 linked list로 구성되어 있다.
  • 전체 140 level, real-time tasks 100개, normal tasks 40개
• 다음 task을 schedule 하려면, priority가 가장 높은 목록만 확인하면 된다.
  • task insertion, task deletion : O(1)
• normal task는 I/O binding 또는 CPU binding에 따라 priority를 동적으로 조정할 수 있다.

Algorithm

• active runqueue에 실행 가능한 task를 scheduler가 삽입한다.
  • task가 priority에 따라 실행을 시작합니다.
  • task time slice가 만료될 때마다 미리 준비되어 expired run queue에 삽입된다.
• active run queue가 비어 있으면 active run queue와 expired run queue pointer 들을 swap 한다.
• 즉, 빈 run queue가 expired run queue가 된다.
  • normal task의 priority와 time slice는 두 개의 run queue가 swap될 때 동적으로 다시 계산된다.
• swap할 때 scheduler는 task가 CPU binding인지 아니면 I/O binding인지 식별한다.

• T1, T2가 active run queue에 존재

• T1이 실행되었으므로 expired run queue로 전달

• 빈 run queue

Shortcoming of O(1) scheduler

• task fairness에 대한 개념 부족
• expired queue의 task starvation

Issues of O(1) scheduler

• Startvation
  • process가 실행될 때, active run queue에 process가 존재한다. process가 종료되면 expired run queue로 이동된다.
  • 새로운 process 들이 생성될 때마다 active run queue에 삽입된다. 그래서 expired run queue의 process들이 starvation에 빠질 위험이 있다.
• algorithm의 문제는 task를 interactive or non-interactive로 구분하는데 사용되는 복잡한 휴리스틱
  • 해당 algorithm은 process가 입력을 기다리는 시간을 분석하여 interactive process를 구별하려고 한다.
  • 장시간 sleep 중인 process는 사용자 입력을 기다리고 있을 수 있으므로 scheduler는 해당 process가 interactive라고 가정한다.
  • scheduler는 우선순위를 낮춤으로서 non-interactive task에 불이익을 주는 동시에, 처리량 향상을 위해 interactive task에 우선순위 보너스를 준다.
  • task의 상호 작용성을 결정하기 위한 모든 계산은 복잡하고 잠재적으로 오계산의 영향을 받아 interactive process에서 non-interactive behavior가 발생한다.