정답
두 번째 작업의 시작 시점은 \(55\ \text{ms}\), 종료 시점은 \(95\ \text{ms}\)이다.
출제 의도
EDF 스케줄링에서 주기와 수행시간이 주어진 두 실시간 프로세스의 작업들이 어떤 순서로 CPU를 할당받는지 판단하고, 특정 작업의 시작 시각과 종료 시각을 계산할 수 있는지를 평가한다.
풀이 과정
주어진 조건은 다음과 같다.
프로세스 \(P_1\): 주기 \(T_1 = 30\,\text{ms}\), 수행시간 \(C_1 = 15\,\text{ms}\) 프로세스 \(P_2\): 주기 \(T_2 = 50\,\text{ms}\), 수행시간 \(C_2 = 25\,\text{ms}\)
EDF 스케줄러에서는 “가장 이른 마감시간(deadline)”을 가진 작업에 CPU를 우선 할당한다. 각 작업의 마감시간은 해당 작업이 발생한 시각에 주기를 더한 값이다.
처음 시각 \(t=0\)에 두 프로세스의 첫 작업 \(P_1^1, P_2^1\)이 동시에 발생한다고 하면, 이들의 마감시간은
$$ D(P_1^1) = 0 + 30 = 30\,\text{ms}, \quad D(P_2^1) = 0 + 50 = 50\,\text{ms} $$
따라서 \(0 \sim 15\,\text{ms}\) 구간은 마감시간이 더 이른 \(P_1^1\)이 실행된다 \((C_1 = 15\,\text{ms})\).
이후 \(15\,\text{ms}\)에서 \(P_1^1\)은 종료되고, \(P_2^1\)만 준비 상태이므로 \(15 \sim 40\,\text{ms}\)에 \(P_2^1\)이 실행되어 수행시간 \(25\,\text{ms}\)를 모두 채우고 종료한다.
\(t = 30\,\text{ms}\)에 \(P_1^2\)가 발생하지만, 이때 실행 중인 \(P_2^1\)의 마감시간은 \(50\,\text{ms}\), 새로 발생한 \(P_1^2\)의 마감시간은 \(60\,\text{ms}\)이므로, EDF에 따라 계속 \(P_2^1\)이 실행된다. \(P_2^1\)이 \(40\,\text{ms}\)에 끝나면, 그 다음에는 \(P_1^2\)만 준비 상태이므로 \(40 \sim 55\,\text{ms}\)에 \(P_1^2\)가 실행되어 종료한다.
\(t = 50\,\text{ms}\)에 \(P_2^2\)가 발생한다. 이때 \(P_1^2\)는 아직 실행 중이지만, 두 작업의 마감시간은
$$ D(P_1^2) = 30 + 30 = 60\,\text{ms}, \quad D(P_2^2) = 50 + 50 = 100\,\text{ms} $$
이므로 마감시간이 더 이른 \(P_1^2\)가 계속 실행되고, \(55\,\text{ms}\)에 \(P_1^2\)가 종료된다.
따라서 \(P_2^2\)는 \(55\,\text{ms}\)에 처음으로 CPU를 할당받아 실행을 시작한다. 이 시점에서 \(P_2^2\)의 남은 수행시간은 전체 \(25\,\text{ms}\)이다.
\(55 \sim 60\,\text{ms}\) 동안 \(P_2^2\)가 실행되다가, \(t = 60\,\text{ms}\)에 \(P_1^3\)이 발생한다. 이때 각 작업의 마감시간은
$$ D(P_2^2) = 50 + 50 = 100\,\text{ms}, \quad D(P_1^3) = 60 + 30 = 90\,\text{ms} $$
이므로 마감시간이 더 이른 \(P_1^3\)이 우선되며, EDF에 의해 \(P_2^2\)는 \(60\,\text{ms}\)에 선점된다. 그때까지 \(P_2^2\)는 \(5\,\text{ms}\)를 실행했으므로, 남은 수행시간은 \(25 – 5 = 20\,\text{ms}\)이다.
\(60 \sim 75\,\text{ms}\) 동안 \(P_1^3\)이 실행되어 종료되고, 그 뒤에는 다시 \(P_2^2\)만 준비 상태이므로 \(P_2^2\)가 재시작하여 나머지 \(20\,\text{ms}\)를 실행한다.
따라서 \(P_2^2\)의 최종 종료 시각은
$$ 75\,\text{ms} + 20\,\text{ms} = 95\,\text{ms} $$
정리하면, \(P_2\)의 두 번째 작업은
시작 시점: \(55\,\text{ms}\), 종료 시점: \(95\,\text{ms}\)
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>