스프린트 우선순위, 리눅스 스케줄러에게 물어봤다

2주 단위로 스프린트를 돌리는 팀이라면 다들 한 번쯤 겪어봤을 고민이 있다. “이번 스프린트, 뭐부터 하지?” 나만 그런가 싶어서 팀원들한테 물어봤는데, 다들 똑같은 고민을 하고 있었다. 사실 우선순위를 정하는 것 자체보다 진짜 어려운 건 그 다음이다 — 계획을 다 세워놓고 나서도 계속 끼어드는 일들을 어떻게 처리하느냐다.

이미 똑똑한 사람들이 풀어놓은 문제 아닐까 하는 생각이 들었다. 리눅스는 프로세스 수백 개를 CPU 하나로 어떻게 나눠 돌릴지, 수십 년째 이 문제를 붙잡고 있다. 그래서 리눅스 스케줄러한테 한번 물어보기로 했다.

정리하면 스프린트 우선순위 문제는 사실 질문이 두 개다. 첫째, 끼어드는 게 가능한지 판단하는 기준이 있는가. 둘째, 끼어들고 난 뒤 남은 스프린트 일은 어떻게 재조정하는가. 리눅스는 이 두 질문에 각각 명확한 답을 갖고 있었다. 그리고 흥미로웠던 건, 리눅스가 “마감 있는 일”과 “마감 없는 일”을 아예 다른 스케줄러 클래스로 분리해뒀다는 점이다. 형평성 하나로 퉁치지 않는다.

“얼마나 급한가”가 아니라 “얼마나 못 받았는가” — CFS

리눅스의 기본 스케줄러인 CFS(Completely Fair Scheduler)는 “중요하다”는 이유만으로 끼어드는 걸 허용하지 않는다. 새로 끼어들려는 작업의 vruntime(지금까지 실제로 받은 실행 시간)이 현재 실행 중인 작업의 vruntime보다 확실히 더 적을 때만 끼어들 수 있다. 판단 기준이 “얼마나 급한가”가 아니라 “얼마나 못 받았는가”라는 게 핵심이다.

vruntime이 정확히 어떻게 쌓이는지 보면 더 명확하다. 커널은 매번 vruntime += 실제로 실행된 시간 × (1024 / 이 작업의 weight) 식으로 vruntime을 누적한다. 여기서 1024는 기본 우선순위(nice 0)의 weight고, 우선순위가 높을수록(nice 값이 낮을수록) weight가 커진다. 그러니까 같은 시간을 실행해도 우선순위가 높은 작업은 vruntime이 더 천천히 늘고, 낮은 작업은 더 빨리 는다 — CFS는 이 값이 가장 작은, 즉 상대적으로 가장 적게 받은 작업을 골라 다음에 실행시킬 뿐이다.

여기에 sched_min_granularity(최소 실행 보장 시간)라는 하한선이 하나 더 붙는다. 아무리 vruntime이 적어도, 지금 실행 중인 작업이 최소 보장 시간을 다 못 채웠으면 끼어들 수 없다. 매번 끼어들게 두면 컨텍스트 스위칭 비용 때문에 전체가 오히려 느려지기 때문이다(이런 현상을 thrashing이라고 부른다).

스프린트로 옮겨보면, 마감이 딱히 없는 일들끼리는 “얼마나 급해 보이는가”가 아니라 “이 일이 실제로 얼마나 밀려 있었는가”, “지금 하던 일이 최소한의 완결 단위는 채웠는가”가 끼어들기를 허용하는 기준이 돼야 한다는 뜻이다.

마감이 있는 일은 완전히 다른 규칙을 쓴다 — SCHED_DEADLINE

문제는 스프린트에서 진짜 무서운 건 형평성이 아니라 마감이라는 점이다. 그런데 신기하게도 리눅스는 이 둘을 이미 구분해뒀다. CFS 말고, 진짜 마감이 있는 작업을 위한 별도 클래스가 있다 — SCHED_DEADLINE이다. man sched(7)에는 이렇게 적혀 있다: “SCHED_DEADLINE 스레드가 실행 가능한 상태면, 다른 어떤 정책의 스레드도 반드시 밀어낸다.” 마감 있는 일은 CFS보다, 심지어 실시간 스케줄러(SCHED_FIFO/RR)보다도 항상 우선이다.

SCHED_DEADLINE은 GEDF(Global Earliest Deadline First)와 CBS(Constant Bandwidth Server)라는 두 알고리즘을 결합해서 쓴다. 마감 있는 작업들끼리는 단순하다 — 절대 마감이 가장 가까운 것부터 실행한다(EDF). 그런데 진짜 핵심은 그 다음 장치다: admission control.

새 마감 작업을 받아들일지는 실행 중에 그때그때 판단하지 않는다. 등록하는 시점에 커널이 미리 계산한다. “지금 이미 예약된 마감들에 이 새 작업까지 합쳐서 감당 가능한가”를 따져서, 안 되면 애초에 등록 자체를 거부한다(기본적으로 마감 작업들은 CPU 대역폭의 최대 95%까지만 쓸 수 있고, 나머지 5%는 항상 비-마감 작업 몫으로 남겨둔다). 한 번 통과하면 그 뒤로는 별도 재계산 없이 파라미터 그대로 돌아간다.

이 admission control이 스프린트에도 그대로 적용된다고 생각한다. 실제로 겪었던 두 가지 경험이 정확히 이 대비를 보여준다.

하나는 admission control을 잘 지킨 경우다. 오픈일이 급박한 업무를 진행하던 중, 있으면 좋지만 없어도 크게 무리가 없는 기능이 하나 있었다 — 버튼 클릭 시 내려오는 약관을 버튼마다 다르게 세팅할 수 있는 기능이었다. 오픈일까지 이 기능까지 포함해서 개발하기엔 일정이 부족했기 때문에 미뤄뒀다. 미룬 덕분에 오픈 일정은 맞췄고, 당장은 약관 하나로만 세팅되는 걸로도 서비스에 문제가 없었다. 이미 확정된 오픈 일정에 새 스코프가 들어갈 여력이 있는지를 먼저 따져보고, 안 되면 그 자리에서 받아들이지 않은 셈이다.

반대는 admission control 없이 받았다가 곤란했던 경우다. 제휴사 요청으로, 제휴사로 호출하는 TPS를 조절해 느리게 호출하도록 하는 기능을 급하게 추가한 적이 있다. 그런데 실제로는 제휴사가 더 받을 수 있는 상황이었고, 중간 전달자들 사이의 의사소통이 원활하지 않아서 생긴 해프닝이었다. 일을 시작하기 전에 상황을 제대로 파악했다면, 불필요한 작업 없이 원래 하던 일에 집중할 수 있었을 것이다. “감당 가능한지”를 미리 계산하지 않고 그냥 받아버린 대가였다.

정리하면, 마감 있는 일은 (1) 마감이 가장 가까운 게 항상 먼저이고, (2) 마감 없는 일보다 항상 우선하지만, (3) 그 대신 새로 받을지는 반드시 사전에 계산해서 정해야 한다. 급해 보인다고 그 자리에서 우겨넣지 말고, 지금 이미 확정된 마감들과 합쳐서 감당이 되는지부터 물어야 한다는 뜻이다.

끼어든 뒤에는? — 재조정이라는 이벤트는 없다

인터럽트가 끝나면 항상 드는 생각이 있다. “이제 전체 우선순위표를 다시 짜야 하나?” 그런데 CFS를 들여다보면 답은 좀 다르다.

CFS의 run queue는 vruntime 기준으로 정렬된 레드-블랙 트리다. 끼어든 작업이 실행을 마치면, 그 작업은 늘어난 vruntime 값을 들고 트리의 “제자리”로 다시 들어간다. 트리는 항상 “지금까지 가장 못 받은 작업이 다음 차례”라는 원칙을 유지하고 있을 뿐, 인터럽트가 끝났다고 전체를 처음부터 다시 정렬하지 않는다. 재조정은 별도의 이벤트가 아니라, 애초에 “각 작업이 지금까지 얼마나 받았는가”를 계속 추적하고 있기 때문에 자동으로 따라오는 결과다. (참고로 마감 있는 일이 끼어든 경우엔 이런 재조정이랄 것도 없다 — 애초에 우선순위 계층에서 항상 위이기 때문이다. 재조정이 필요한 건 마감 없는 일들 사이에서뿐이다.)

여기에 컨텍스트 저장/복원이 재조정 비용을 한 번 더 낮춰준다. 끼어들었던 작업도, 끼어들려고 멈췄던 작업도 처음부터 다시 시작하지 않고, 정확히 멈췄던 지점 — 레지스터, 스택, 프로그램 카운터 — 부터 재개된다.

이것도 실제로 겪은 일이다. 팀에서 맡은 역할 특성상 여러 업무를 번갈아 가면서 진행하는 경우가 많다. 하던 업무 중간에 다른 업무를 쭉 진행하고 나면, 원래 업무를 다시 이어갈 때 어떤 상황이었는지 기억이 안 나는 경험이 잦았다. 그런데 지금까지 뭘 했고 앞으로 뭘 할지를 정리해둔 적이 있었는데, 그때는 다시 돌아왔을 때 복귀 속도가 확실히 빨랐다. 이게 딱 컨텍스트 저장이다 — 우선순위표를 다시 짜는 게 아니라, 멈췄던 지점을 값싸게 복원할 수 있게만 해두면 된다.

정리

결국 세 가지만 미리 정해두면 된다.

• 마감 없는 일의 판단 기준: “이 정도는 끼어들어도 된다”의 기준을 급함이 아니라, 얼마나 밀려 있었는지 그리고 지금 하던 일이 최소 완결 단위를 채웠는지로 삼는다.
• 마감 있는 일의 판단 기준: 마감이 가장 가까운 게 항상 먼저고, 마감 없는 일보다 항상 우선한다. 대신 새 마감 있는 일을 받을 때는 지금 이미 확정된 마감들까지 합쳐서 감당 가능한지 미리 계산하고, 안 되면 그 자리에서 거절한다.
• 재조정 습관: 우선순위표를 통째로 다시 짜려 하지 말고, 각 작업이 지금까지 얼마나 진행됐는지를 계속 보이게 해두면 재조정은 자동으로 따라온다. 그리고 하던 일은 언제든 짧은 시간 안에 복구 가능한 상태로 남겨둔다.

스프린트 우선순위표를 아무리 정교하게 짜도, 결국 중간에 끼어드는 일은 생긴다. 그럴 때 감으로 판단하지 않게 해주는 규칙 하나, 그리고 하던 일을 값싸게 복구할 수 있게 해주는 습관 하나 — 리눅스가 이미 수십 년 전에 찾아둔 답이었다.

참고

• CFS Scheduler — The Linux Kernel documentation — vruntime, 레드-블랙 트리 기반 run queue 등 CFS 설계 원문
• Deadline Task Scheduling — The Linux Kernel documentation — SCHED_DEADLINE의 GEDF+CBS 알고리즘, admission control 대역폭 계산
• sched(7) — Linux manual page — 스케줄링 정책 전체 계층과 우선순위 규칙

---

이 글은 업무든 일상이든, 거기서 얻은 통찰을 컴퓨터 과학 개념에 빗대어 풀어보는 '경험 디버깅(exp-debug)' 연재입니다. 실제 경험에서 얻은 인사이트를 바탕으로, AI와 함께 정리하고 다듬었습니다.