실시간 스케줄링(RM·EDF) 계산기

주기가 짧은 작업에 높은 우선순위를 고정으로 주는 스케줄링 방식입니다. 고정 우선순위 방식 중에서는 최적이라는 것이 리우와 레이랜드가 1973년에 증명했습니다. 우선순위가 변하지 않아 구현이 단순하고 과부하 때 어느 작업이 먼저 무너질지 예측할 수 있어 실시간 시스템에서 널리 쓰입니다.

아닙니다. 리우–레이랜드 한계 n(2^(1/n) − 1)은 «안 넘으면 반드시 된다»는 충분조건일 뿐입니다. 예를 들어 주기 4·실행 1과 주기 8·실행 5인 두 작업은 U = 0.875로 한계 0.828을 넘지만 실제로는 마감을 모두 지킵니다. 한계만 보고 설계를 뒤엎으면 멀쩡한 구성을 버리게 됩니다.

응답시간 분석(RTA)이 필요충분조건입니다. Rᵢ = Cᵢ + Σ ⌈Rᵢ/Tⱼ⌉·Cⱼ를 고정점까지 반복해 최악 응답시간을 구하고 Rᵢ ≤ Dᵢ인지 봅니다. 여기에 더해 이 계산기는 초주기(주기들의 최소공배수)까지 시간을 실제로 돌려 마감을 놓치는지도 확인합니다. 두 판정은 계통이 전혀 다른데도 언제나 같은 답이 나와야 합니다.

됩니다. 모든 작업이 0 시각에 함께 깨어나는 «임계 순간»이 고정 우선순위에서는 최악의 경우이고, 그 뒤로는 초주기마다 같은 패턴이 되풀이됩니다. 그래서 초주기 동안 마감을 안 놓치면 영원히 안 놓칩니다.

마감이 이른 작업부터 돌리며 우선순위가 매 순간 바뀝니다. 마감이 주기와 같을 때 U ≤ 1이 필요충분조건이라 한 CPU로 할 수 있는 최선입니다. 그런데도 RM을 많이 쓰는 것은 구현이 단순하고, 과부하에서 어느 작업이 먼저 무너질지 예측할 수 있기 때문입니다. EDF는 과부하가 걸리면 도미노처럼 다 같이 무너지는 성질이 있습니다.

주기들이 서로 배수(조화 관계)면 U ≤ 1이기만 하면 RM으로도 반드시 스케줄됩니다. 예를 들어 주기 2·4·8에 실행시간 1·1·2를 두면 U = 1인데도 딱 맞아떨어져 CPU가 한 순간도 놀지 않습니다. 실시간 시스템에서 주기를 2의 거듭제곱으로 잡는 관행이 여기서 나옵니다.

Π(Uᵢ + 1) ≤ 2를 보는 판정입니다. 리우–레이랜드보다 덜 보수적이어서, 리우–레이랜드를 통과하면 쌍곡선도 반드시 통과하고 그 반대는 아닙니다. 다만 이것도 충분조건일 뿐이라 둘 다 떨어져도 실제로는 도는 경우가 있습니다.

다루는 작업이 다릅니다. CPU 스케줄링 계산기는 도착 시각과 실행시간이 정해진 일회성 작업을 FCFS·SJF·라운드로빈 등으로 돌려 평균 대기시간을 봅니다. 이 계산기는 주기마다 되풀이되는 작업이 마감을 지킬 수 있는지를 봅니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.