JMC: Jitter-Based Mixed-Criticality Scheduling for Distributed Real-Time Systems

These days, the term of Internet of Things (IoT) becomes popular to interact and cooperate with individual smart objects, and one of the most critical challenges for IoT is to achieve efficient resource sharing as well as ensure safety-stringent timing constraints. To design such reliable real-time IoT, this paper focuses on the concept of mixed-criticality (MC) introduced to address the low processor utilization on traditional real-time systems. Although different worst-case execution time estimates depending on criticality are proven effective on processor scheduling, the MC concept is not yet mature on distributed systems (such as IoT), especially with end-to-end deadline guarantee. To the best of our knowledge, this paper presents the first attempt to apply the MC concept into interference (or jitter), which is a complicated source of pessimism when analyzing the schedulability of distributed systems. Our goal is to guarantee the end-to-end deadlines of high-criticality flows and minimize the deadline miss ratio of low-criticality flows in distributed systems. To achieve this goal, we introduce a jitter-based MC (JMC) scheduling framework, which supports node-level mode changes in distributed systems. We present an optimal feasibility condition (subject to given schedulability analysis) and two policies to determine jitter-threshold values to achieve the goal in different conditions. Via simulation results for randomly generated workloads, JMC outperforms an existing criticality-monotonic scheme in terms of achieving higher schedulability and fewer deadline misses.

I. Introduction

Nowadays, we have witnessed significant growth in a number of smart objects (or “things”) connected to the Internet to interact and cooperate with each other, called the Internet of Things (IoT). Such a trend poses a significant challenge in achieving efficient sharing of computational/communication resources while ensuring safety-stringent timing constraints, primarily to achieve fault isolation/containment, which is also a key to design a reliable cyber-physical system, an emerging system of systems often considered as real-time IoT. To provide end-to-end timing guarantees, resource utilization estimates are required for applications; however, conservative worst-case execution time (WCET) estimates have conventionally been used for safety-critical applications, leading to a severely under-utilized system in practice. For example, a task typically exhibits a certain variation of execution times depending on the input data and different behavior of the environment. The exact value of WCET is usually unknown and can be overly estimated [1]. A task can also experience a large variation of interference from others depending on scheduling policies and execution scenarios. Though it is feasible to estimate the amount of interference tightly in some environments, it is difficult (often computationally intractable) to calculate it accurately in many complex environments such as distributed systems [2], [3].