고급 스케줄링 알고리즘

데스크톱에서는 편집기와 음악 재생기와 컴파일러가 함께 돌고, 서버에서는 웹 요청과 일괄 작업과 모니터링 에이전트가 함께 돕니다. 이 작업들은 원하는 것이 서로 다릅니다. 편집기는 키를 누르자마자 반응해야 하고, 컴파일러는 전체가 빨리 끝나기를 원하며, 음악 재생기는 정해진 간격마다 다음 소리를 내보내야 합니다. 앞 글의 알고리즘 하나만으로는 이 요구를 모두 맞추기 어렵습니다.

이 글에서는 실제 운영체제 스케줄러의 바탕이 되는 방법들을 살펴봅니다. 작업마다 우선순위를 매기는 방법, 작업을 성격별로 여러 큐에 나누는 방법, 작업의 행동을 지켜보며 큐를 옮겨 주는 방법, 그리고 정해진 시각 안에 반드시 끝내야 하는 실시간 작업을 다루는 방법입니다.

우선순위 스케줄링

우선순위 스케줄링(priority scheduling)은 작업마다 우선순위를 매기고, 준비된 작업 가운데 우선순위가 가장 높은 작업을 먼저 실행합니다. 대부분의 실제 운영체제 스케줄러가 이 생각을 바탕으로 합니다. 우선순위를 숫자로 나타내는 방법은 시스템마다 달라서, 숫자가 작을수록 높은 경우도 있고 클수록 높은 경우도 있습니다. Linux 안에서도 다릅니다. 일반 작업의 nice 값은 작을수록 CPU를 더 많이 받지만, 실시간 작업의 우선순위는 클수록 먼저 실행됩니다.

우선순위를 비교하는 대상은 준비 상태의 작업뿐이라는 점에 주의해야 합니다. 우선순위가 높은 작업 A가 디스크 응답을 기다리며 대기 상태에 있고 낮은 작업 B만 준비되어 있다면, CPU는 B가 씁니다. A의 높은 우선순위가 A가 기다리는 입출력을 빨리 끝내 주지는 않습니다.

우선순위를 정하는 방법은 둘입니다. 운영체제가 작업의 성질을 보고 정하는 내부적인 방법에서는, 예상되는 CPU 버스트의 길이나 지금까지 기다린 시간 같은 정보를 씁니다. 앞 글의 SJF는 버스트가 짧을수록 우선순위가 높은 우선순위 스케줄링이라고 볼 수 있습니다. 사용자나 관리자가 정하는 외부적인 방법에서는, 어떤 작업이 더 중요한지에 대한 판단을 반영합니다. Linux의 nice 명령이 대표적입니다. 우선순위 스케줄링은 선점형으로도 비선점형으로도 쓸 수 있으며, 선점형에서는 더 높은 우선순위의 작업이 준비되면 지금 작업을 멈추고 그 작업을 실행합니다.

기아와 에이징

우선순위 스케줄링의 가장 큰 문제는 기아(starvation)입니다. 우선순위가 높은 작업이 끊임없이 들어오면, 우선순위가 낮은 작업은 준비 큐에서 한없이 기다리게 됩니다. 1973년 MIT의 한 컴퓨터를 종료할 때, 1967년에 제출되어 그때까지 한 번도 실행되지 못한 작업이 발견되었다는 이야기가 이 문제를 설명할 때 자주 인용됩니다.

기아를 막는 방법으로 에이징(aging)이 있습니다. 작업이 준비 큐에서 기다린 시간에 따라 우선순위를 조금씩 올려 주는 것입니다. 오래 기다린 작업은 결국 다른 작업만큼 높은 우선순위에 이르러 실행 기회를 얻습니다. 다음 코드는 숫자가 작을수록 우선순위가 높은 시스템에서, 우선순위 1인 작업이 매 틱 준비되어 있을 때 우선순위 10인 작업이 언제 처음 실행되는지 계산합니다. 에이징을 쓰면 3틱 기다릴 때마다 우선순위를 한 단계 올립니다.

def first_run(aging, ticks=30):
    """숫자가 작을수록 우선순위가 높다. 우선순위 1인 작업이 매 틱 준비되어 있다."""
    priority, waited = 10, 0
    for t in range(ticks):
        if priority <= 1:                # 같아지면 오래 기다린 쪽을 먼저 고른다
            return t
        waited += 1
        if aging and waited % 3 == 0:    # 3틱 기다릴 때마다 우선순위를 한 단계 올린다
            priority -= 1
    return None

for aging in (False, True):
    t = first_run(aging)
    label = "에이징 있음" if aging else "에이징 없음"
    print(label + ":", f"{t}틱에 처음 실행" if t is not None else "30틱 동안 한 번도 실행되지 못함")

에이징 없음: 30틱 동안 한 번도 실행되지 못함
에이징 있음: 27틱에 처음 실행

에이징이 없으면 우선순위 10인 작업은 언제나 우선순위 1인 작업에 밀려 실행되지 못합니다. 에이징을 쓰면 27틱 동안 아홉 단계가 올라 우선순위 1에 이르고, 그때 실행 기회를 얻습니다. 이 모델에서는 우선순위가 같아지면 오래 기다린 작업을 고르도록 했는데, 실제로 기아를 막으려면 이처럼 같은 우선순위 안에서도 오래 기다린 작업이 언젠가는 선택되는 규칙이 함께 있어야 합니다. 우선순위를 몇 틱마다 얼마나 올릴지는 정책에 따라 정하는 값이며, 여기서 쓴 3틱은 설명을 위한 예입니다.

멀티레벨 큐

멀티레벨 큐(multilevel queue)는 준비 큐를 여러 개로 나누고, 작업을 성격에 따라 정해진 큐에 넣으며, 큐마다 다른 스케줄링 알고리즘을 씁니다. 예를 들어 다음과 같이 나눌 수 있습니다.

큐가 여럿이면 큐들 사이에서 누구를 먼저 실행할지도 정해야 합니다. 첫째 방법은 고정 우선순위로, 위의 큐가 비어 있을 때만 아래 큐의 작업을 실행합니다. 단순하지만, 시스템 큐와 대화형 큐에 일이 끊이지 않으면 일괄 처리 큐는 기아에 빠집니다. 둘째 방법은 시간 할당으로, 큐마다 CPU 시간의 몫을 정해 둡니다. 예를 들어 시스템 큐에 10%, 대화형 큐에 70%, 일괄 처리 큐에 20%를 주면, 일괄 처리 큐는 일이 있는 한 적어도 CPU 시간의 20%를 받습니다. 다만 이것은 큐 전체의 몫이므로, 큐 안의 작업 하나가 언제 실행될지는 그 큐 안의 알고리즘에 달려 있습니다.

멀티레벨 큐의 한계는 작업이 처음 넣은 큐에서 벗어날 수 없다는 것입니다. 처음에는 입력을 자주 받던 작업이 나중에 긴 계산을 시작해도 대화형 큐에 그대로 남아, 다른 대화형 작업의 응답을 늦춥니다. 작업의 성격은 실행 중에 바뀌는데, 큐는 그 변화를 따라가지 못합니다.

멀티레벨 피드백 큐

멀티레벨 피드백 큐(multilevel feedback queue, MLFQ)는 작업이 큐 사이를 옮겨 다닐 수 있게 해 이 한계를 풉니다. 작업의 다음 버스트가 얼마나 될지 미리 알 수는 없지만, 지금까지 어떻게 행동했는지는 볼 수 있습니다. MLFQ는 CPU를 오래 쓴 작업은 앞으로도 오래 쓸 것이고, CPU를 잠깐 쓰고 입출력을 하던 작업은 앞으로도 그럴 것이라고 보고 큐를 정합니다. 앞 글의 SJF처럼 짧은 작업을 앞세우는 효과를, 실행 시간을 미리 알지 못하고도 얻으려는 방법입니다.

작업이 큐를 옮기는 규칙

큐가 세 개인 MLFQ를 예로 들어 보겠습니다.

새 작업은 우선순위가 가장 높은 Q0에서 시작합니다. 8ms 안에 끝나는 짧은 작업은 높은 우선순위에서 빨리 처리되고 끝납니다. Q0에서 CPU를 8ms 다 쓰고도 끝나지 않은 작업은 CPU를 많이 쓰는 작업으로 보고 Q1으로 내립니다. Q1에서도 16ms를 다 쓰면 Q2로 내립니다. 반대로 입출력을 하느라 CPU를 금방 내놓는 작업은 할당량을 다 쓰지 않으므로 높은 큐에 머뭅니다. 그래서 대화형 작업은 높은 큐에서 빠르게 반응하고, 계산이 긴 작업은 낮은 큐로 내려가 다른 작업에 방해가 덜 됩니다.

여기서 구분할 것이 둘 있습니다. 첫째, 퀀텀과 할당량은 다릅니다. 퀀텀은 같은 큐의 작업들이 돌아가며 실행할 때 한 번에 쓰는 시간이고, 할당량(allotment)은 작업 하나가 강등되기 전까지 그 큐에서 모두 합쳐 쓸 수 있는 CPU 시간입니다. 이 예에서는 단순하게 하려고 둘을 같게 보았지만, 일반적으로는 다를 수 있습니다. 둘째, 큐 안의 규칙과 큐 사이의 규칙도 다릅니다. Q2가 FCFS라는 것은 Q2 안의 작업들 사이의 순서일 뿐입니다. 큐 사이에서는 높은 큐의 준비된 작업이 먼저이므로, Q2의 작업이 실행 중이어도 Q0에 새 작업이 준비되면 그 작업이 먼저 실행됩니다.

CPU를 30ms 써야 하는 작업이 이 MLFQ에서 어떻게 내려가는지 단계별로 보면 다음과 같습니다.

작업은 Q0에서 8ms를 쓰고 22ms가 남은 채 Q1으로 내려가고, Q1에서 16ms를 더 쓰고 6ms가 남은 채 Q2로 내려가, Q2에서 나머지 6ms를 쓰고 끝납니다. 마지막에 끝난 것은 큐를 옮긴 것과 다른 사건입니다. 작업이 할당량을 정확히 다 쓰는 순간에 끝났다면, 더 낮은 큐로 옮길 작업 자체가 남지 않습니다.

규칙을 악용하는 작업과 회계

초기 MLFQ의 규칙에는 허점이 있었습니다. "할당량을 다 쓰기 전에 CPU를 내놓으면 같은 큐에 머문다"는 규칙만 있으면, 작업이 할당량이 끝나기 직전에 쓸모없는 입출력을 일부러 요청해 계속 높은 큐에 머물 수 있습니다. CPU를 오래 쓰는 작업이 대화형 작업처럼 보이게 꾸며 다른 작업의 몫을 가져가는 것입니다. 이처럼 스케줄러의 규칙을 악용하는 것을 게이밍(gaming)이라고 합니다.

이를 막는 방법이 회계(accounting)입니다. 작업이 입출력으로 CPU를 몇 번 내놓았든 상관없이, 각 큐에서 쓴 CPU 시간을 누적해 기록하고, 누적 시간이 할당량에 이르면 강등합니다. 입출력을 기다린 시간은 CPU를 쓴 시간이 아니므로 누적에 넣지 않습니다. 다음 코드는 30ms짜리 작업이 각 큐에서 쓰는 시간과, CPU를 7ms씩 쓰고 입출력을 하기를 네 번 되풀이하는 작업이 회계 여부에 따라 어느 큐에 머무는지 계산합니다.

ALLOTMENT = {0: 8, 1: 16}   # 큐별 누적 CPU 할당량(ms). Q2는 제한이 없다

def split(total):
    """CPU를 total만큼 이어서 쓰는 작업이 각 큐에서 쓰는 시간"""
    parts, level = [], 0
    while total:
        take = min(total, ALLOTMENT.get(level, total))
        parts.append(f"Q{level} {take}ms")
        total -= take
        level += 1
    return ", ".join(parts)

def levels(bursts, accounting):
    """버스트마다 입출력을 하며 CPU를 나누어 쓸 때, 각 버스트 뒤에 머무는 큐"""
    level, used, result = 0, 0, []
    for burst in bursts:
        used = used + burst if accounting else burst   # 회계하지 않으면 입출력 뒤 0부터 다시 센다
        while level in ALLOTMENT and used >= ALLOTMENT[level]:
            used -= ALLOTMENT[level]
            level += 1
        result.append(f"Q{level}")
    return " -> ".join(result)

print("30ms 작업:", split(30))
print("7ms씩 네 번, 회계 있음:", levels([7, 7, 7, 7], accounting=True))
print("7ms씩 네 번, 회계 없음:", levels([7, 7, 7, 7], accounting=False))

30ms 작업: Q0 8ms, Q1 16ms, Q2 6ms
7ms씩 네 번, 회계 있음: Q0 -> Q1 -> Q1 -> Q2
7ms씩 네 번, 회계 없음: Q0 -> Q0 -> Q0 -> Q0

회계를 하면 7ms씩 쓰는 작업도 누적 14ms에서 Q0의 할당량 8ms를 넘어 Q1으로 내려가고, 누적 28ms에서는 Q1의 할당량까지 다 써서 Q2로 내려갑니다. 회계를 하지 않으면 매번 할당량 8ms보다 조금 덜 쓰고 CPU를 내놓으므로, 총 28ms를 쓰고도 계속 Q0에 머뭅니다. 이 모델은 할당량을 넘긴 시간을 다음 큐로 넘겨 세도록 단순화했습니다.

낮은 큐의 기아와 주기적 부스트

MLFQ에도 기아의 위험이 있습니다. 대화형 작업이 많아 높은 큐가 계속 바쁘면, Q2로 내려간 긴 작업은 거의 실행되지 못합니다. 또 계산을 마치고 대화형으로 바뀐 작업이 Q2에 갇혀 있으면 응답이 느립니다. 이를 막으려고 일정한 주기마다 모든 작업을 Q0으로 올리는 주기적 부스트(priority boost)를 씁니다. 올라간 작업들은 다시 행동에 따라 알맞은 큐로 내려갑니다.

부스트가 있다고 모든 작업의 대기 시간에 상한이 생기는 것은 아닙니다. 부스트 뒤에도 같은 큐 안의 작업 수와 선택 규칙에 따라 기다리는 시간이 정해지기 때문입니다. 또 부스트할 때 누적 회계를 어떻게 처리할지도 정책으로 정해야 합니다. MLFQ의 규칙들이 각각 어떤 문제를 풀려고 생겼는지는 OSTEP의 MLFQ 장에 잘 정리되어 있습니다.

실시간 스케줄링

실시간 시스템(real-time system)에서 중요한 것은 빠르게가 아니라 정해진 시각 안에 끝내는 것입니다. 결과가 맞더라도 마감 시각(deadline)을 넘기면 틀린 결과로 봅니다. 마감을 반드시 지켜야 하는 시스템을 경성 실시간(hard real-time) 시스템이라고 합니다. 항공기의 비행 제어, 자동차의 ABS, 의료 장비의 제어처럼 마감을 놓치면 사고로 이어지는 경우입니다. 마감을 가끔 놓쳐도 품질이 떨어질 뿐 시스템이 실패하지는 않는 경우는 연성 실시간(soft real-time) 시스템이라고 합니다. 초당 30프레임의 영상은 33ms마다 프레임을 내보내야 하는데, 하나를 놓치면 화면이 잠깐 끊기지만 재생은 이어집니다.

주기 태스크와 job

실시간 스케줄링에서는 같은 일을 일정한 주기로 되풀이하는 작업을 주기 태스크(periodic task)라고 하고, 태스크가 한 번 도착해 실행하는 단위를 job이라고 부릅니다. 예를 들어 10ms마다 센서를 읽는 태스크는 0ms, 10ms, 20ms마다 job을 하나씩 만듭니다. 태스크는 실행 시간 $C$와 주기 $T$로 나타내며, 여기서는 각 job의 마감이 다음 job이 도착하는 시각, 곧 도착 시각에 $T$를 더한 시각이라고 가정합니다. $C$는 평균이 아니라 가장 오래 걸릴 때의 실행 시간이어야 합니다. 마감을 반드시 지킬 수 있는지 따지려면 가장 나쁜 경우를 기준으로 해야 하기 때문입니다.

태스크 하나가 CPU를 쓰는 비율은 $C / T$이며, 모든 태스크의 비율을 더한 값을 이용률(utilization) $U$라고 합니다. $U$가 1을 넘으면 CPU가 해야 할 일이 CPU의 능력보다 많으므로 어떤 방법으로도 모든 마감을 지킬 수 없습니다. 아래의 분석은 CPU가 하나이고, 선점할 수 있으며, 태스크들이 서로 기다리지 않고, 컨텍스트 스위칭 비용이 없다는 가정을 깔고 있습니다. 이 가정과 용어는 Linux 커널의 데드라인 스케줄링 문서에도 정리되어 있습니다.

Rate Monotonic: 주기가 짧을수록 높은 우선순위

Rate Monotonic(RM) 스케줄링은 주기가 짧은 태스크일수록 높은 우선순위를 주는 고정 우선순위 방식입니다. 우선순위는 태스크마다 한 번 정해지면 바뀌지 않습니다. 예를 들어 태스크 A가 $C = 5$ms, $T = 20$ms이고 태스크 B가 $C = 15$ms, $T = 50$ms라면, 주기가 짧은 A가 높은 우선순위를 받습니다.

RM에는 잘 알려진 판정 조건이 있습니다. 태스크가 $n$개일 때 이용률이 $n(2^{1/n} - 1)$ 이하이면 모든 마감을 지킬 수 있습니다. 이 값은 $n = 2$에서 약 0.828이고, $n$이 커질수록 줄어 $\ln 2 \approx 0.693$에 가까워집니다. 앞의 A와 B는 이용률이 5/20 + 15/50 = 0.55로 0.828보다 작으므로, 마감을 모두 지킬 수 있다고 판정됩니다. 주의할 점은 이것이 충분 조건이라는 것입니다. 이용률이 이 값 이하이면 반드시 지킬 수 있지만, 이 값을 넘는다고 반드시 놓치는 것은 아닙니다. 그때는 실제로 실행 순서를 따라가 봐야 합니다.

RM은 우선순위가 고정되어 구현이 단순하고 실행 중의 계산 비용이 적습니다. 그래서 고정 우선순위로 태스크를 고르는 RTOS에서 개발자가 태스크의 주기에 맞추어 우선순위를 정하는 방식으로 많이 씁니다. 다만 FreeRTOS 같은 RTOS가 우선순위 스케줄링을 제공한다고 해서, 커널이 태스크들의 주기와 실행 시간을 분석해 마감을 보장해 주는 것은 아닙니다. 그 분석은 설계하는 사람의 몫입니다.

EDF: 마감이 가장 가까운 job부터

EDF(earliest deadline first)는 지금 준비된 job 가운데 마감 시각이 가장 이른 job을 먼저 실행합니다. 같은 태스크의 job이라도 마감 시각이 job마다 다르므로, 우선순위가 실행 중에 계속 바뀌는 동적 우선순위 방식입니다. 앞의 가정 아래에서 EDF는 이용률이 1 이하이면 모든 마감을 지킬 수 있습니다. 이용률이 1 이하인 태스크 묶음을 어떤 방법으로든 지킬 수 있다면 EDF로도 지킬 수 있다는 뜻이므로, CPU 하나에서는 EDF가 가장 많은 일을 감당할 수 있는 방법입니다. 대신 job마다 마감을 비교해야 하므로 실행 중의 계산이 더 들고, 일이 넘쳐 마감을 놓치기 시작하면 어떤 job이 놓칠지 예측하기 어렵습니다.

다음 코드는 두 태스크 묶음을 1ms 단위로 실행해 보며 RM과 EDF를 비교합니다. 출력에는 처음 20ms의 실행 구간과, 정해진 시간 동안 놓친 마감이 나옵니다. 마감이 같은 job이 여럿이면 먼저 도착한 job을 고릅니다.

def simulate(tasks, policy, horizon):
    """tasks는 {이름: (실행 시간 C, 주기 T)}이고 마감은 다음 주기 시작이다. 1ms씩 진행한다."""
    jobs, misses, timeline = [], [], []
    for t in range(horizon + 1):
        for job in [j for j in jobs if j["deadline"] <= t]:
            misses.append(f"{job['task']}(마감 {job['deadline']})")
            jobs.remove(job)
        if t == horizon:
            break
        for name, (cost, period) in tasks.items():
            if t % period == 0:
                jobs.append({"task": name, "deadline": t + period, "left": cost})
        if not jobs:
            name = "쉼"
        else:
            if policy == "RM":           # 주기가 짧은 태스크가 늘 우선
                job = min(jobs, key=lambda j: tasks[j["task"]][1])
            else:                        # EDF: 이번 마감이 가장 이른 job이 우선
                job = min(jobs, key=lambda j: j["deadline"])
            job["left"] -= 1
            if job["left"] == 0:
                jobs.remove(job)
            name = job["task"]
        if timeline and timeline[-1][0] == name:
            timeline[-1][2] = t + 1
        else:
            timeline.append([name, t, t + 1])
    return timeline, misses

def show(tasks, horizon):
    use = sum(c / t for c, t in tasks.values())
    print(f"작업 {tasks}, 이용률 {use:.3f}")
    for policy in ("RM", "EDF"):
        timeline, misses = simulate(tasks, policy, horizon)
        gantt = " ".join(f"{n}{s}-{e}" for n, s, e in timeline if e <= 20)
        print(f"  {policy}: {gantt} ... 놓친 마감 {misses if misses else '없음'}")

show({"A": (5, 10), "B": (8, 20)}, 20)
show({"A": (2, 5), "B": (4, 7)}, 35)

작업 {'A': (5, 10), 'B': (8, 20)}, 이용률 0.900
  RM: A0-5 B5-10 A10-15 B15-18 쉼18-20 ... 놓친 마감 없음
  EDF: A0-5 B5-13 A13-18 쉼18-20 ... 놓친 마감 없음
작업 {'A': (2, 5), 'B': (4, 7)}, 이용률 0.971
  RM: A0-2 B2-5 A5-7 B7-10 A10-12 B12-13 쉼13-14 B14-15 A15-17 B17-20 ... 놓친 마감 ['B(마감 7)']
  EDF: A0-2 B2-6 A6-8 B8-12 A12-14 B14-15 A15-17 B17-20 ... 놓친 마감 없음

첫째 묶음은 이용률이 0.9로 RM의 판정 조건 0.828을 넘지만, RM으로도 마감을 하나도 놓치지 않습니다. A가 0–5ms, B가 5–10ms, 다음 A가 10–15ms, B의 남은 3ms가 15–18ms에 실행되고, 20ms에 두 태스크가 함께 다시 도착하므로 같은 모양이 되풀이됩니다. 판정 조건을 넘는다는 것과 실제로 마감을 놓친다는 것이 다르다는 것을 보여 주는 예입니다. 두 태스크의 주기가 서로 배수 관계일 때는 RM도 이용률 1까지 감당할 수 있다는 것이 알려져 있습니다.

둘째 묶음에서는 차이가 드러납니다. RM은 주기가 짧은 A를 늘 앞세우므로, B는 2ms부터 5ms까지 3ms를 실행한 뒤 A의 둘째 job에 밀려 7ms의 마감까지 남은 1ms를 끝내지 못합니다. EDF는 5ms에 A의 둘째 job이 도착해도 그 마감 10ms가 B의 마감 7ms보다 늦으므로 B를 계속 실행해 6ms에 끝내고, 이후로도 마감을 놓치지 않습니다. 이용률이 1 이하라면 EDF는 마감을 지킬 수 있지만, 이 묶음의 이용률 0.971은 RM이 감당하지 못하는 수준입니다.

Linux의 실시간 정책

Linux는 범용 운영체제지만 실시간 정책 SCHED_FIFO와 SCHED_RR을 제공합니다. 실시간 우선순위는 1부터 99까지이며 숫자가 클수록 먼저 실행됩니다. 실행할 수 있는 실시간 작업이 있으면 일반 작업보다 먼저 실행됩니다. SCHED_FIFO는 같은 우선순위 안에서 먼저 온 작업이 스스로 내놓을 때까지 실행하고, SCHED_RR은 같은 우선순위 안에서 퀀텀씩 돌아갑니다. 마감 시각을 직접 다루는 SCHED_DEADLINE도 있는데, EDF로 고르면서 작업마다 실행 예산을 정해 두고, 새 작업을 받아들일 때 전체 이용률을 넘지 않는지 확인합니다.

sudo chrt -f 50 ./realtime_app   # SCHED_FIFO, 우선순위 50으로 실행
chrt -p 1234                     # PID 1234의 스케줄링 정책과 우선순위 확인

실시간 우선순위를 주려면 보통 root 권한이나 CAP_SYS_NICE 능력이 필요합니다. 무한 루프를 도는 실시간 작업은 일반 작업을 모두 굶길 수 있으므로, Linux는 실시간 작업이 쓸 수 있는 CPU 시간을 제한합니다. /proc/sys/kernel/sched_rt_period_us와 sched_rt_runtime_us의 기본값은 각각 1,000,000과 950,000으로, 1초 가운데 0.95초까지만 실시간 작업이 쓰고 나머지 0.05초는 일반 작업에 남겨 둔다는 뜻입니다. 이 제한은 시스템을 지키기 위한 안전장치이지, 실시간 작업의 마감을 보장해 주는 장치는 아닙니다. 정책별 규칙은 sched(7)에 있습니다.

더 깊이: 우선순위 역전과 우선순위 상속

우선순위 스케줄링은 잠금과 만나면 뜻밖의 결과를 낳습니다. 우선순위가 낮은 작업 C가 잠금을 쥔 상태에서 가장 높은 작업 A가 그 잠금을 기다린다고 합시다. 이때 잠금과 상관없는 중간 우선순위의 작업 B가 준비되면, 스케줄러는 C 대신 B를 실행합니다. B가 CPU를 계속 쓰면 C는 잠금을 풀 기회를 얻지 못하고, A는 자기보다 낮은 B 때문에 언제까지일지 모르게 기다립니다. Linux의 RT-mutex 설계 문서는 이를 무한 우선순위 역전(unbounded priority inversion)이라고 부릅니다.

이를 푸는 방법 가운데 하나가 우선순위 상속(priority inheritance, PI)입니다. 잠금을 쥔 작업이 그 잠금을 기다리는 작업의 우선순위를 잠금을 쥐고 있는 동안 물려받는 것입니다. 앞의 예에서 C는 A의 우선순위로 실행되므로 B에 밀리지 않고 잠금을 풀 수 있고, 잠금을 풀면 원래 우선순위로 돌아갑니다. POSIX는 이를 뮤텍스의 프로토콜 속성으로 정해 두었습니다. 기본값인 PTHREAD_PRIO_NONE은 잠금을 쥐어도 우선순위가 바뀌지 않고, PTHREAD_PRIO_INHERIT는 우선순위 상속을 쓰며, PTHREAD_PRIO_PROTECT는 뮤텍스마다 정해 둔 우선순위 상한(priority ceiling)으로 올려 실행합니다.

Linux 커널은 사용자 공간의 우선순위 상속 잠금을 위해 PI-futex를 제공합니다. 경쟁이 없을 때는 원자적 명령어만으로 커널에 들어가지 않고 잠그고 풀며, 경쟁이 생기면 FUTEX_LOCK_PI와 FUTEX_UNLOCK_PI로 커널에 들어가 우선순위 상속을 아는 rt-mutex가 나머지 일을 처리합니다. 커널 문서는 이것이 사용자 공간의 실시간 프로그램이 동작을 예측할 수 있게 하는 데 쓰인다고 설명합니다.

정리

• 우선순위 스케줄링은 준비된 작업 가운데 우선순위가 가장 높은 작업을 먼저 실행하며, 낮은 작업의 기아는 기다린 시간에 따라 우선순위를 올리는 에이징으로 막습니다.
• 멀티레벨 큐는 작업을 성격별로 여러 큐에 나누고 큐마다 다른 알고리즘을 씁니다. 큐 사이는 고정 우선순위나 시간 할당으로 정하며, 작업이 큐를 옮길 수 없다는 한계가 있습니다.
• MLFQ는 할당량을 다 쓴 작업을 낮은 큐로 내려, 실행 시간을 미리 알지 못하고도 짧은 작업과 대화형 작업을 우대합니다. 누적 회계로 규칙의 악용을 막고, 주기적 부스트로 낮은 큐의 기아를 줄입니다.
• 실시간 스케줄링은 마감을 지키는 것이 목표입니다. RM은 주기가 짧을수록 높은 고정 우선순위를 주고, EDF는 마감이 가장 이른 job을 먼저 실행합니다. CPU 하나에서 EDF는 이용률 1까지 마감을 지킬 수 있습니다.
• Linux는 SCHED_FIFO, SCHED_RR, SCHED_DEADLINE 같은 실시간 정책을 제공하며, 실시간 작업이 CPU를 독차지하지 못하도록 사용 시간을 제한합니다.

연습 문제

1. 입출력을 끼운 작업의 회계

할당량이 8ms인 Q0에서 작업 P가 CPU를 3ms 쓰고, 입출력을 20ms 기다린 뒤, CPU를 4ms 더 썼습니다. 부스트나 다른 작업은 없고 P는 아직 끝나지 않았습니다. 회계에 기록되는 CPU 시간, 그동안 흐른 시간, Q0에서 더 쓸 수 있는 시간을 각각 구하세요. 이어서 1ms를 더 쓰면 어떻게 될까요?

2. RM과 EDF가 고르는 job

8ms에 두 job이 준비되어 있고 각각 CPU를 1ms씩 남겼습니다. job A는 주기 4ms인 태스크가 8ms에 만든 것이고, job B는 주기 10ms인 태스크가 0ms에 만든 것입니다. 각 job의 마감은 도착 시각에 주기를 더한 시각이고, 더 도착하는 job은 없습니다. RM과 EDF가 각각 어느 job을 먼저 실행하는지, 두 job이 언제 끝나고 마감을 지키는지 답하세요.

3. Q2에서 실행 중인 작업과 새 작업

큐 사이에서는 높은 큐의 준비된 작업이 먼저이고 선점할 수 있으며, Q2 안에서는 FCFS를 쓰는 MLFQ가 있습니다. Q2의 작업 X가 실행 중일 때 Q0의 작업 Y가 준비 상태가 되었습니다. Y는 X가 끝날 때까지 기다려야 할까요? Y가 준비 상태가 아니라 입출력을 기다리는 대기 상태라면 어떻게 될까요?

다음 글 현대 OS의 스케줄링에서는 Linux의 CFS와 EEVDF, Windows의 스케줄러, 그리고 여러 코어에 작업을 나누어 주는 멀티코어 스케줄링을 살펴봅니다.