https://www.mdu.se/

Real-time systems such as industrial robots and automated guided vehicles integrate a wide range of algorithms with varying levels of timing requirements to achieve their functional behavior. Historically, in certain systems, these algorithms were deployed on dedicated single-core hardware platforms that exchanged information over a real-time network, while more recent designs have adapted an integrated architecture where these algorithms are executed on an embedded multi-core hardware platform. The advantages provided by cloud and fog architectures for non-real-time applications have prompted discussions around the possibility of achieving similar advantages for systems such as industrial robot controllers by moving from an embedded architecture to a cloud and fog native architecture. This thesis addresses a subset of challenges related to scheduling to facilitate this transition and presents three main contributions aimed at improving online scheduling methodologies in multi-server systems for applications with real-time requirements. First, an approach based on minimum parallelism reservations is proposed for scheduling sequential tasks in hierarchical multi-server systems with clairvoyant inputs, ensuring adherence to hard real-time requirements. Second, a framework is introduced that utilizes estimated processing times to enhance average throughput in distributed multi-queue multi-server systems while managing tasks with stochastic inputs and firm real-time requirements, thereby improving resource utilization. Finally, competitive algorithms are proposed that leverage estimated processing times to minimize average (modified) tardiness in centralized single-queue multi-server systems, addressing the scheduling of sequential tasks with arbitrary arrivals and soft real-time requirements. Collectively, these contributions establish a robust foundation for improving the performance of real-time systems operating in increasingly complex environments characterized by dynamic workloads and varying resource availability.

We consider the problem of scheduling $n$ jobs on $m geq 2$ parallel machines in online settings with the objective of minimizing total tardiness. Since no bounded competitive algorithms exist to minimize the general problem of weighted total tardiness of the form $sum w_j T_j$, we consider an objective of the form $sum w_j (T_j+d_j)$, where $w_j, T_j$, and $d_j$ are the weight, tardiness, and deadline of each job, respectively and develop competitive algorithms dependent on jobs' processing times.

The edge computing paradigm extends the architectural space of real-time systems by bringing the capabilities of the cloud to the edge. Unlike cloud-native systems designed for mean response times, real-time industrial embedded systems are designed to control a single physical system, such as a manipulator arm or a mobile robot, that requires temporal predictability. We consider the problem of dispatching and scheduling of jobs with deadlines that can be offloaded to the edge and propose DAL, a deadline-aware load balancing and scheduling framework that leverages the availability of on-demand computing resources along with an on-arrival dispatching scheme to manage temporal requirements of such offloaded applications. The evaluation indicates that DAL can achieve reasonably good performance even when execution times, arrival times, and deadlines vary.

We consider the problem of on-arrival dispatching and scheduling jobs with stochastic execution times, inter-arrival times, and deadlines in multi-server fog and edge computing platforms. In terms of mean response times, it has been shown that size-based scheduling policies, when combined with dispatching policies such as join-shortest-queue, provide better performance over policies such as first-in-first-out. Since job sizes may not always be known apriori, prediction-based policies have been shown to perform reasonably well. However, little is known about the performance of prediction-based policies for jobs with firm deadlines. In this paper, we address this issue by considering the number of jobs that complete within their deadlines as a performance metric and investigate, using simulations, the performance of a prediction-based shortest-job-first scheduling policy for the considered metric and compare it against scheduling policies that prioritize based on deadlines (EDF) and arrival times (FIFO). The evaluation indicates that in under-loaded conditions, the prediction-based policy is outperformed by both FIFO and EDF policies. However, in overloaded scenarios, the prediction-based policy offers slightly better performance.

The edge computing paradigm brings the capabilities of the cloud such as on-demand resource availability to the edge for applications with low-latency and real-time requirements. While cloud-native load balancing and scheduling algorithms strive to improve performance metrics like mean response times, real-time systems, that govern physical systems, must satisfy deadline requirements. This paper explores the potential of an edge computing architecture that utilizes the on-demand availability of computational resources to satisfy firm real-time requirements for applications with stochastic execution and inter-arrival times. As it might be difficult to know precise execution times of individual jobs prior to completion, we consider an admission policy that relies on single-bit execution time predictions for dispatching. We evaluate its performance in terms of the number of jobs that complete by their deadlines via simulations. The results indicate that the prediction-based admission policy can achieve reasonable performance for the considered settings.

Real-time systems such as industrial robots and autonomous navigation vehicles integrate a wide range of algorithms to achieve their functional behavior. In certain systems, these algorithms are deployed on dedicated single-core hardware platforms that exchange information over a real-time network. With the availability of current multi-core platforms, there is growing interest in an integrated architecture where these algorithms can run on a shared hardware platform. In addition, the benefits of virtualization-based cloud and fog architectures for non-real-time applications have prompted discussions about the possibility of achieving similar benefits for real-time systems. Although many useful solutions such as resource reservations and hierarchical scheduling have been proposed to facilitate hardware virtualization for real-time applications, the current state of the art is mainly concerned with applications whose timing requirements can be modelled according to the periodic or the sporadic task model. Since the computational demand of many real-time algorithms can be flexibly adjusted at runtime, e.g., by changing the periods, they can be better abstracted with the elastic task model in the context of virtualized hardware platforms.

Therefore, in this thesis, we first propose a scheduling framework with reservations based on periodic resource supply for real-time elastic applications with single-core workloads, and then extend this solution for applications with multi-core workloads  where reservations are based on the minimum-parallelism model. Since many existing applications run on dedicated single-core platforms, we simultaneously provide a systematic methodology for migrating an existing real-time software application from a single-core to a multi-core platform. In doing so, we focus on recovering the architecture of the existing software and transforming it for implementation on a multi-core platform. Next, we explore the advantages of a fog-based architecture over an existing robot control architecture and identify the key research challenges that must be addressed for the adoption of the fog computing architecture.

Scheduling of real-time applications modelled according to the periodic and the sporadic task model under hierarchical and compositional real-time systems has been widely studied to provide temporal isolation among independent applications running on shared resources. However, for some real-time applications which are amenable to variation in their timing behaviour, usage of these tasks models can result in pessimistic solutions. The elastic task model addresses this pessimism by allowing the timing requirements of an application's tasks to be specified as a range of values instead of a single value. Although the scheduling of elastic applications on dedicated resources has received considerable attention, there is limited work on scheduling of such applications in hierarchical and compositional settings. In this paper, we evaluate different earliest deadline first scheduling algorithms to schedule elastic applications in a minimum parallelism supply form reservation on a multiprocessor system. Our evaluation indicates that the proposed approach provides performance comparable to the current state-of-art algorithms for scheduling elastic applications on dedicated processors in terms of schedulability. 

This paper proposes a systematic three-stage methodology for migrating complex real-time industrial software systems from single-core to multi-core computing platforms. Single-core platforms have limited computational capabilities that prevent integration of computationally demanding applications such as image processing within the existing system. Modern multi-core processors offer a promising solution to address these limitations by providing increased computational power and allowing parallel execution of different applications within the system. However, the transition from traditional single-core to contemporary multi-core computing platforms is non-trivial and requires a systematic and well-defined migration process. This paper reviews some of the existing migration methods and provides a systematic multi-phase migration process with emphasis on software architecture recovery and transformation to explicitly address the timing and dependability attributes expected of industrial software systems. The methodology was evaluated using a survey-based approach and the results indicate that the presented methodology is feasible, useable and useful for real-time industrial software systems.

Many real-time applications have functional behaviour that requires variability in timing properties at runtime. The elastic task model provides a convenient mechanism to specify and encapsulate such variability and enables the modification of an application's periods during run-time to keep the application schedulable. Additionally, reservation-based scheduling techniques were proposed for the same purpose of taming unpredictability of timing variations, but with a different solution, i.e., by providing the spatial and temporal isolation for executing independent applications on the same hardware. In this paper, we combine the two approaches by proposing a two-level adaptive scheduling framework which is based on the elastic task model and the compositional framework based on the periodic resource model. The proposed framework minimises the number of requests for bandwidth adaption at the reservation (system) level and primarily enables schedulability by accounting for the application's elasticity by adjusting the periods. The motivation for this design choice is to rather localise the effect of the modifications within the application, without necessarily affecting all the applications at the system level compared to the changes made at the application level. The evaluation results show that the local application changes may often be enough to solve the problem of variability, significantly reducing the number of bandwidth adjustments, and therefore reducing the potential negative impact on all the applications of a system.

Low latency and on demand resource availability enable fog computing to host industrial applications in a cloud like manner. One industrial domain which stands to benefit from the advantages of fog computing is robotics. However, the challenges in developing and implementing a fog-based robotic system are manifold. To illustrate this, in this paper we discuss a system involving robots and robot cells at a factory level, and then highlight the main building blocks necessary for achieving such functionality in a fog-based system. Further, we elaborate on the challenges in implementing such an architecture, with emphasis on resource virtualization, memory interference management, real-time communication and the system scalability, dependability and safety. We then discuss the challenges from a system perspective where all these aspects are interrelated.