마감 시한

마감 시한(deadline)은 태스크나 job이 실행을 마쳐야 하는 시각이다. 마감 시한까지 끝내지 못하는 것을 마감 시한을 놓쳤다(deadline miss)고 한다.[1][2] 마감 시한이 정하는 시간 요구는 실시간 시스템에서 다룬다.

절대와 상대

Linux 커널의 SCHED_DEADLINE 문서에 따르면 job의 절대 마감 시한은 job이 끝나야 하는 시각이고, job이 도착한 시각에 태스크의 상대 마감 시한을 더한 값이다. 도착 시각을 $r$, 상대 마감 시한을 $D_i$라 하면 절대 마감 시한은 $r+D_i$다. 태스크는 WCET, 상대 마감 시한, 주기의 세 값으로 나타낸다.[2]

Hard와 soft

hard real-time 요구는 마감 시한을 넘기면 시스템이 실패하는 요구이고, soft real-time 요구는 마감 시한을 넘겨도 시스템이 쓸모를 잃지 않는 요구다.[1][3]

Renesas 앱노트에 따르면 hard real-time에서는 마감 시한을 놓쳐도 되는 정도가 극히 작거나 0이고, 놓치면 시스템에 치명적인 결과가 생긴다. soft real-time에서는 마감 시한을 놓쳐도 회복할 수 있고, 시스템 품질이 떨어지는 것을 받아들일 수 있다.[1]

주기와의 관계

상대 마감 시한 $D_i$와 주기 $T_i$의 관계에 따라 태스크의 마감 시한을 셋으로 나눈다.[4]

• implicit deadline: 마감 시한이 주기와 같다($D_i=T_i$).
• constrained deadline: 마감 시한이 주기 이하다($D_i\le T_i$).
• arbitrary deadline: 마감 시한이 주기보다 짧을 수도, 같을 수도, 길 수도 있다.[4]

그래서 implicit deadline은 constrained deadline의 특수한 경우이고, constrained deadline은 arbitrary deadline의 특수한 경우다.[4]

Liu와 Layland는 1973년 논문에서 각 태스크가 같은 태스크의 다음 요청이 오기 전에 끝나야 한다고 가정했다. 곧 요청의 마감 시한은 같은 태스크의 다음 요청 시각이다.[5] 마감 시한이 주기와 같으므로 이 태스크의 마감 시한은 implicit deadline이다.[4] 이 모델은 주기 태스크 모델에서 다룬다.

Lehoczky는 1990년 마감 시한이 임의인 주기 태스크 집합의 고정 우선순위 스케줄링을 다뤄, 스케줄 가능성의 일반 판정 기준과 Liu와 Layland의 이용률 상한을 일반화한 최악 경우 상한을 냈다.[6]

Tindell의 1992년 응답 시간 분석에서는 태스크의 최악 응답 시간이 주기 $T_i$보다 길면, 앞 요청이 끝나기 전에 같은 태스크가 다시 도착할 수 있다. 그래서 $D_i\le T_i$인 태스크에 쓰는 응답 시간 식은 앞 요청의 계산을 넣지 않아, 마감 시한이 임의인 태스크에는 충분하지 않다.[7]

[1]

“General RTOS Concepts (R8C Family Application Note),” Renesas Electronics, 2010. Accessed: Sep. 29, 2026. [Online]. Available: https://www.renesas.com/en/document/apn/general-rtos-concepts

[2]

“Deadline Task Scheduling (The Linux Kernel documentation),” The Linux Kernel development community, 2026. Accessed: Sep. 29, 2026. [Online]. Available: https://docs.kernel.org/scheduler/sched-deadline.html

[3]

“AT04056: Getting Started with FreeRTOS on Atmel SAM Flash MCUs,” Atmel, 2014. Accessed: Sep. 29, 2026. [Online]. Available: https://ww1.microchip.com/downloads/en/AppNotes/Atmel-42382-Getting-Started-with-FreeRTOS-on-Atmel-SAM-Flash-MCUs_ApplicationNote_AT04056.pdf

[4]

R. I. Davis and A. Burns, “A Survey of Hard Real-Time Scheduling for Multiprocessor Systems,” ACM Computing Surveys, vol. 43, no. 4, p. 35:1-35:44, 2011, doi: 10.1145/1978802.1978814.

[5]

C. L. Liu and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” Journal of the ACM, vol. 20, no. 1, pp. 46–61, 1973, doi: 10.1145/321738.321743.

[6]

J. P. Lehoczky, “Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadlines,” in Proceedings 11th Real-Time Systems Symposium, 1990, pp. 201–209. doi: 10.1109/REAL.1990.128748.

[7]

K. W. Tindell, “An Extendible Approach for Analysing Fixed Priority Hard Real-Time Tasks,” Department of Computer Science, University of York, Tech. Rep. YCS 189, 1992. Accessed: Sep. 29, 2026. [Online]. Available: https://web.archive.org/web/20170815023010/https://www.cs.york.ac.uk/ftpdir/reports/92/YCS/189/YCS-92-189.pdf