Abstract

Mixed-criticality (MC) scheduling is necessary for many safety-critical real-time embedded systems, as a failure of high-criticality jobs could lead to fatal accidents. With the emergence of software technologies in software-defined vehicles in the automotive and avionics industries, studying Mixed-Critically (MC) systems is essential to their safety standards, similar to ISO26262. The real-time operation of MC systems makes it an inherently online problem, such that the scheduler is only aware of the jobs that are currently released at any point in time and has no knowledge of future jobs. Due to the overhead cost of preemption, this study focuses on enforcing non-preemption, which makes the problem NP-hard. The literature presents solutions for offline models that allow the scheduler to know about all jobs that are yet to be scheduled from time unit zero and also for systems that allow preemption. Researchers also simplify the modeling of the dynamic elements of the problem, e.g., varying-speed processors, by using simple assumptions that the processor's speed doesn’t recover from degradation, which simplifies the problem but is not very realistic. To the extent of our knowledge, we are the first to schedule dual-criticality systems upon non-preemptive, varying-speed processors online. With plenty of researchers approaching the schedulability of such systems with various objectives, our aim in this study is to shed light on the promising nature of emergent machine learning technologies, specifically Reinforcement Learning. We propose a somewhat unconventional approach, where we tackle the modeling complexities using deep reinforcement learning, particularly suitable for problems that generate a sequence of decisions in dynamic environments. Our customized Ape-X model is capable of successfully scheduling sets of jobs of size 50 with an average accuracy of 95% in comparison to other Reinforcement learning algorithms benchmarks conducted, e.g., Augmented Random Search, Proximal Policy Optimization, and Deep Q Networks. Sensitivity analysis shows that training the model with randomized parameters yields a stable performance that is relatively robust to some changes in the generated instances. As part of our future work, we also introduced a simple preemptive version of our system and showed its potential, which reached an average accuracy of 96%. We hope that our study and results motivate the scheduling community to explore the adoption of this effective approach as a promising potential for other dynamic scheduling problems. Thus, we also introduce our recommendations on modeling variants of the problem and discuss possible future extensions.

School

School of Sciences and Engineering

Department

Computer Science & Engineering Department

Degree Name

MS in Computer Science

Graduation Date

Spring 6-1-2023

Submission Date

2-23-2023

First Advisor

Nouri Sakr

Committee Member 1

Hossam Sharara

Committee Member 2

Yiran Chen

Extent

51 p.

Document Type

Master's Thesis

Institutional Review Board (IRB) Approval

Not necessary for this item

Download

Share

COinS