스케줄링

기다리는 것은 여럿인데 내줄 자원은 하나일 때, 다음 차례를 누구에게 줄지 정하는 일입니다. 그 결정을 맡은 부분을 스케줄러라고 부릅니다. 무엇을 기준으로 고를지는 정책이 정합니다. 정책이 달라지면 같은 일감이라도 도는 순서가 달라집니다.

상세

응급실에는 의사 한 명을 기다리는 환자가 여럿입니다. 접수한 순서가 아니라 더 급한 사람부터 부릅니다. 보던 환자가 있어도 그보다 급한 사람이 실려 오면, 의사는 차트에 여기까지 봤다고 적은 뒤 그쪽으로 옮겨 갑니다.

성립하려면 셋이 있어야 합니다. 나눠 쓸 자원 하나, 그 자원을 기다리는 여럿, 다음 차례를 고르는 규칙입니다. 요구가 하나뿐이면 고를 것이 없습니다. 규칙이 없으면 늦게 온 것이 언제 자기 차례를 받을지 아무도 답하지 못합니다.

고르는 대상은 지금 바로 자원을 쓸 수 있는 것뿐입니다. 다른 것이 끝나기를 기다리는 중이라면 후보에서 빠집니다. 기다리던 것이 풀리면 다시 후보로 돌아옵니다.

결정은 한 번으로 끝나지 않습니다. 자원이 비는 순간마다 되풀이됩니다.

flowchart TD
    A["차례를 기다리는 것들"] --> B["정책이 하나를 고른다"]
    B --> C["자원을 넘긴다"]
    C --> D{"자리를 언제 놓나"}
    D -->|"스스로 놓음"| A
    D -->|"기다릴 일이 생김"| A
    D -->|"몫으로 받은 시간을 다 씀"| A
    D -->|"더 급한 것이 나타남"| A

자리를 놓는 계기가 넷입니다. 스스로 양보하거나, 무언가를 기다리게 되거나, 받은 시간을 다 쓰거나, 더 급한 것이 나타나는 것입니다. 앞의 둘은 자원을 쥔 쪽이 놓는 것입니다. 뒤의 둘은 스케줄러가 뺏는 것입니다. 끝날 때까지 그대로 두면 비선점, 도중에 뺏으면 선점이라고 부릅니다. 뺏으려면 하던 자리를 어딘가에 적어 두고 나중에 그 자리부터 이어야 합니다. 그 저장과 복원에도 비용이 붙습니다.

누구를 고를지 정하는 부분과 실제로 자원의 주인을 바꾸는 부분은 다릅니다. 앞을 정책, 뒤를 메커니즘이라고 가릅니다. 정책만 갈아 끼워도 시스템의 성질이 달라지는 것은 이 둘이 갈려 있기 때문입니다.

어떤 순서가 맞는지는 하나로 정해지지 않습니다. 자원을 놀리지 않는 것, 기다린 시간을 줄이는 것, 정해진 시각을 지키는 것, 몫을 고르게 나누는 것이 서로 당깁니다. 하나를 세우면 다른 하나가 밀립니다. 정책이 여럿인 이유가 여기 있습니다.

배경

자원 하나에 요구가 여럿 몰리는 자리는 되풀이됩니다. 순서를 정하는 쪽이 없으면 먼저 잡은 것이 놓을 때까지 나머지는 멈춥니다. 몇 밀리초면 끝날 일도 앞의 긴 일이 끝나야 시작됩니다. 반대로 아무도 안 고르면 자원은 비어 있는 채로 놀게 됩니다.

그래서 결정을 한곳에 모읍니다. 요구를 모아 두고, 자원이 빌 때마다 그중 하나를 꺼내는 부분을 따로 둡니다. 결정이 한곳에 모여 있으면 그 규칙만 바꿔서 시스템 전체의 성질을 바꿀 수 있습니다. 요구하는 쪽은 자기가 몇 번째인지 몰라도 됩니다.

그 결정을 스케줄링이라고 부릅니다. 결정을 맡은 부분에는 스케줄러라는 이름이 붙습니다. 같은 이름이 자원마다 되풀이됩니다. 프로세서 시간을 나눌 때도, 디스크 요청의 순서를 정할 때도, 클러스터에서 일감을 올릴 기계를 고를 때도, 실행 시각을 정해 둘 때도 같은 말을 씁니다.

갈래

무엇을 기준으로 다음 차례를 고르느냐가 축입니다. 도착한 순서, 받은 시간의 길이, 미리 매겨 둔 우선순위, 지켜야 할 시각, 나눠 가질 몫이 각각 다른 정책이 됩니다. 여기에 축이 하나 더 붙습니다. 고른 것을 도중에 뺏을 수 있느냐입니다. 리눅스의 sched(7) 은 모든 스케줄링이 선점형이라고 적습니다. 정적 우선순위가 더 높은 스레드가 실행 가능해지면 지금 도는 스레드는 선점되어 자기 우선순위의 대기 목록으로 돌아갑니다.

우선순위

스케줄러는 스레드마다 스케줄링 정책 하나와 정적 우선순위 sched_priority 하나를 함께 봅니다. 개념상 스케줄러는 가능한 sched_priority 값마다 실행 가능한 스레드의 목록을 하나씩 들고 있습니다. 다음에 무엇을 돌릴지 정할 때는 비어 있지 않은 목록 중 정적 우선순위가 가장 높은 것을 찾아, 그 목록의 맨 앞에 있는 스레드를 고릅니다.

실시간 정책인 SCHED_FIFO 와 SCHED_RR 아래의 프로세스는 sched_priority 가 1부터 99까지입니다. 일반 정책인 SCHED_OTHER · SCHED_IDLE · SCHED_BATCH 아래에서는 이 값이 스케줄링 결정에 쓰이지 않고 0으로 지정해야 합니다. 정책이 정하는 것은 같은 정적 우선순위 목록 안에서의 순서뿐입니다.

선착순

먼저 온 것을 먼저 돌립니다. SCHED_FIFO 는 시간 조각 나누기가 없는 단순한 스케줄링 알고리즘이라고 sched(7) 이 적습니다. 이 정책은 0보다 높은 정적 우선순위에서만 쓸 수 있습니다. 그래서 SCHED_FIFO 스레드가 실행 가능해지면 지금 도는 SCHED_OTHER · SCHED_BATCH · SCHED_IDLE 스레드를 언제나 즉시 선점합니다.

한번 자리를 잡으면 셋 중 하나가 일어날 때까지 계속 돕니다. 입출력 요청에 막히거나, 더 높은 우선순위의 스레드에 선점되거나, 스스로 sched_yield(2) 를 부르는 것입니다. 같은 정적 우선순위 목록에 있는 나머지는 그때까지 차례를 받지 못합니다.

라운드로빈

flowchart TD
    A["차례를 받는다"] --> B["시간 양자만큼 돈다"]
    B --> C{"양자를 다 썼나"}
    C -->|"다 씀"| D["같은 우선순위 목록의 맨 뒤로"]
    C -->|"막히거나 선점됨"| E["대기 목록으로"]
    D --> A

SCHED_RR 은 SCHED_FIFO 를 조금 손본 것입니다. 앞서 말한 것이 그대로 적용되고, 한 가지만 다릅니다. 각 스레드가 최대 시간 양자만큼만 돌 수 있다는 점입니다. 시간 양자와 같거나 더 긴 시간을 돌았으면 그 스레드는 자기 우선순위 목록의 맨 뒤로 갑니다. 양자의 길이는 sched_rr_get_interval(2) 로 조회합니다.

마감시각

지켜야 할 시각을 기준으로 고릅니다. 리눅스는 3.14부터 SCHED_DEADLINE 정책을 제공합니다. 이 정책은 지금은 GEDF(Global Earliest Deadline First, 전역 최단 마감 우선)를 CBS(Constant Bandwidth Server, 고정 대역폭 서버)와 함께 써서 구현되어 있습니다. 대상은 산발 작업 모델입니다. 각 작업은 주기마다 최대 한 번 활성화되는 잡의 연속이고, 잡마다 끝내야 할 상대 마감시각과 실행에 필요한 계산 시간을 함께 갖습니다.

받아들일 때 한 약속을 지키려고 SCHED_DEADLINE 스레드는 사용자가 다룰 수 있는 스레드 중 가장 높은 우선순위를 갖습니다. SCHED_DEADLINE 스레드가 하나라도 실행 가능하면 다른 정책 아래의 스레드를 전부 선점합니다. 같은 기준이 블록 장치에도 나타납니다. mq-deadline 은 읽기 요청이 들어올 때 현재 시각에 read_expire 를 더한 값을 그 요청의 마감으로 매깁니다.

몫 나누기

SCHED_OTHER 는 정적 우선순위 0 목록 안에서만 통하는 동적 우선순위로 다음 스레드를 고릅니다. 동적 우선순위는 nice 값에 기반합니다. 그리고 그 스레드가 실행 가능한데도 스케줄러가 돌려주지 않은 시간 양자마다 올라갑니다. sched(7) 은 이것이 모든 SCHED_OTHER 스레드의 공정한 진행을 보장한다고 적습니다. 커널 소스 안에서 이 정책의 실제 이름은 SCHED_NORMAL 입니다.

같은 목록 안에서도 다르게 다뤄지는 자리가 있습니다. SCHED_BATCH 는 스케줄러가 그 스레드를 언제나 프로세서를 많이 쓰는 것으로 가정하게 만듭니다. 깨어남 동작에 작은 벌점이 붙어 스케줄링 결정에서 약간 불리해집니다. SCHED_IDLE 은 SCHED_OTHER 나 SCHED_BATCH 의 nice 값 +19보다도 낮은 우선순위로 잡을 돌리려는 자리입니다. 몫을 시간이 아니라 대역폭으로 나누는 갈래도 있습니다. BFQ(Budget Fair Queueing, 예산 공정 큐잉)는 시간만이 아니라 대역폭을 프로세스나 그룹 사이에 나눕니다. 처리량을 높게 유지해야 할 때는 시간 분배로 되돌아갑니다.

예시

프로세서 시간

chrt(1) 이 이미 도는 프로세스의 실시간 스케줄링 속성을 설정하거나 조회합니다. 주어진 속성으로 명령을 새로 띄우기도 합니다. 기본 형태는 이렇습니다.

chrt priority command [arguments]

정책은 옵션이 고릅니다. -o 는 SCHED_OTHER, -f 는 SCHED_FIFO, -r 는 SCHED_RR, -b 는 SCHED_BATCH, -i 는 SCHED_IDLE, -d 는 SCHED_DEADLINE 입니다. 정책을 안 적으면 SCHED_RR 이 쓰입니다. -b · -i · -d 에서는 우선순위 인자를 0으로 넣어야 합니다. -d 로 마감 정책을 고를 때 커널이 요구하는 세 값의 관계는 runtime <= deadline <= period 입니다.

클러스터의 파드 배치

kube-scheduler 는 쿠버네티스의 기본 스케줄러이고 컨트롤 플레인의 일부로 돕니다. 새로 만들어졌거나 아직 배치되지 않은 파드를 놓을 노드를 고릅니다. 결정은 두 단계입니다. 필터링 단계에서 파드의 요구를 못 채우는 노드를 걸러냅니다. PodFitsResources 필터는 후보 노드에 파드가 요청한 자원이 남아 있는지 봅니다. 걸러낸 목록이 비면 그 파드는 아직 배치할 수 없습니다. 스코어링 단계에서는 살아남은 노드에 점수를 매기고 가장 높은 노드를 고릅니다. 그 결정을 API(Application Programming Interface) 서버에 알리는 과정을 바인딩이라고 부릅니다.

파드 쪽에서 갈 곳을 좁히는 필드가 있습니다. nodeSelector 는 파드 명세에 넣는 가장 단순한 노드 선택 제약입니다. 여기에 노드 레이블을 적으면 그 레이블을 전부 가진 노드에만 파드가 배치됩니다. 어피니티와 안티 어피니티는 정의할 수 있는 제약의 종류를 넓힙니다. 공식 문서는 어피니티 쪽 표현이 더 풍부하다는 것을 이점으로 듭니다. 반대 방향도 있습니다. 테인트는 노드가 파드를 밀어내게 합니다.

kubectl taint nodes node1 key1=value1:NoSchedule

이 명령이 노드 node1 에 테인트를 하나 붙입니다. 그 테인트를 견디지 못하는 파드는 이 노드를 받지 않습니다. 톨러레이션은 파드에 붙습니다. 톨러레이션이 있으면 스케줄링이 허용되기는 하지만 보장되지는 않습니다. 스케줄러가 다른 조건도 함께 따지기 때문입니다.

실행 시각

crontab 파일은 "이 명령을 이 날짜 이 시각에 돌려라"라는 지시를 담습니다. 한 줄은 시각과 날짜 필드 다섯 개, 명령, 줄바꿈 순서입니다.

필드	허용 값
minute	0-59
hour	0-23
day of month	0-31
month	0-12 또는 이름
day of week	0-7, 0과 7은 일요일, 또는 이름

별표는 언제나 "처음부터 끝까지"를 뜻합니다. 범위는 8-11 처럼 붙임표로 적고 양 끝을 포함합니다. 목록은 1,2,5,9 처럼 쉼표로 잇습니다. 범위 뒤에 /2 를 붙이면 그 폭만큼 건너뜁니다. 시 필드의 0-23/2 는 두 시간마다 실행입니다. cron 은 분·시·월 필드가 현재 시각과 맞고 두 날짜 필드 중 하나가 맞을 때 명령을 실행합니다. 항목은 1분에 한 번씩 확인합니다.

쿠버네티스의 CronJob 은 되풀이되는 일정에 따라 일회성 잡을 만듭니다. 문서는 CronJob 객체 하나가 유닉스 시스템 crontab 파일의 한 줄과 같다고 적습니다. 일정은 cron 형식으로 적습니다.

블록 장치의 입출력

입출력 큐마다 스케줄러 손잡이가 딸려 있습니다. 장치마다 스케줄러를 돌아가는 중에 바꿀 수 있습니다. 고를 수 있는 것은 mq-deadline · none · bfq · kyber 입니다.

echo schedname > /sys/block/dev/queue/scheduler

schedname 자리에 스케줄러 이름을, dev 자리에 장치 이름을 넣습니다. 손잡이는 /sys/block/<device>/queue/iosched 아래에 있습니다. mq-deadline 의 목표는 요청의 서비스 시작 시각을 보장해 보려는 것입니다. 읽기 지연에 초점이 있어서 read_expire 가 밀리초 단위로 조절 가능합니다. 쓰기에는 write_expire 가 같은 자리에 있습니다.

상세

배경

갈래

우선순위

선착순

라운드로빈

마감시각

몫 나누기

예시

프로세서 시간

클러스터의 파드 배치

실행 시각

블록 장치의 입출력

관련 항목

차례를 기다리는 실행 단위

결정에 쓰는 재료

이것과 맞세워지는 대립 개념

이것의 하위 종류

마감시각 정책의 이론적 바탕

결정을 맡는 주체

이것을 호출·실행하는 명령

스케줄러가 참고하는 조정 값

블록 장치가 고르는 입출력 스케줄러

갈 곳을 좁히는 제약

쿠버네티스 스케줄러가 다루는 세부 기능

이것이 나쁠 때 나타나는 신호

이것이 걸쳐 있는 자원·분야