Run-time WCET Determination for Real-Time Scheduling Using Machine Learning

Abstract

Determining the precise worst-case execution time has proven difficult due to the tasks’ increasing complexity (WCET). Inaccurate WCET estimations cause deadline misses, which may result in catastrophic accidents. This can be particularly fatal in the safety-critical systems. In this thesis, a scheduling methodology based on machine learning that can dynamically forecast the WCET of a job has been presented. Since it takes into account both the execution time and job sequence, the proposed method can accurately predict the amount of time needed to finish a task. It employs machine learning to compute the task’s progress rate and allow additional time for execution before the deadline when a task has reached its predetermined bound without being completed, which can prevent a deadline miss caused by inaccurate WCET determination. Additionally, it can reduce the sacrifice of low-criticality tasks by optimizing the HI-mode that guarantees the execution of high-criticality tasks by preempting low-criticality tasks in mixed-criticality systems. This preserves functional safety of the low-criticality task. For the evaluation, C benchmarks and Linux systems were used to investigate the trade-offs between the latency and the accuracy of the proposed technique. The result shows the simple linear regression by ordinary least squares (OLS) with the coefficient of determination (R^2) as a percentage was 82%. However, the proposed technique was approximately 99.7% prediction accuracy. This was 3.83% scheduling overhead based on a period of 1 ms in a real automotive task.|태스크의 복잡성이 증가함에 따라 정확한 WCET(Worst-Case Execution Time)을 결정하는 것이 어려워지고 있다. 부정확한 WCET 결정값은 데드라인을 놓쳐 치명적인 사고를 초래할 수 있기 때문에 이는 안전 중요 시스템(Safety Critical System)에서 치명적일 수 있다. 본 연구에서는 미리 결정된 한계치를 위반했을 때 태스크의 WCET을 동적으로 예측할 수 있는 머신 러닝 메소드 기반의 스케줄링 기법을 제안한다. 제안된 기법은 실행 시간과 작업 시퀀스의 결합된 특징을 기반으로 하며, 이는 작업에 필요한 실행 시간을 정확하게 예측하기 위한 새로운 접근 방식이다. 태스크가 완료되지 않고 미리 결정된 한계치를 모두 소진하게 되면 제안된 기법은 머신 러닝을 사용하여 태스크의 진행률을 계산하고 데드라인 전에 실행을 위한 추가 시간을 할당한다. 이 기법을 사용하여 부정확한 WCET로 인한 데드라인 미스를 방지할 수 있다. 또한, 이 기술은 혼합 중요도 시스템(Mixed-Criticality System)에서 중요도가 높은 작업의 HI 모드 실행 시간을 최적화하여 중요도가 낮은 작업의 희생을 줄일 수 있다. 따라서 시스템의 기능성을 향상시킬 수 있으며, 중요한 작업의 실행을 보존할 수 있다. 평가를 위해 C 벤치마크와 리눅스 시스템을 사용하여 제안된 기법의 지연 시간과 정확도 사이의 트레이드-오프 관계를 조사하였다. 그 결과 결정 계수(R^2, Coefficient of Determination)의 백분율 값이 최소제곱법(OLS, Ordinary Least Squares)을 이용한 단순 선형 회귀는 82%인 반면, 제안된 기법은 최대 99.7%의 예측 정확도를 보였다. 그리고 이것은 실제 세계의 자동차 태스크에서 1 ms의 주기(period)를 기준으로 3.83%의 스케줄링 오버헤드를 가지고 있었다.