No description available.

No description available.

No description available.

No description available.

Real-time systems are those whose correctness depends not only on logical results of computations, but also on the time at which the results are produced. This thesis provides a formal definition for real-time systems and includes the following original contributions on real-time scheduling algorithms. The first topic studied in the thesis is minimizing the total penalty to be paid in scheduling a set of soft real-time tasks. The problem is NP-hard. We prove the properties of any optimal scheduling algorithm. We also derive a number of heuristic algorithms which satisfy the properties obtained. Moreover, we obtain a tight upper bound for the optimal solution to the problem. Numerical results that compare the upper bound with the optimal solution and the heuristic algorithms are provided. In the second part of this thesis, we study the problem of minimizing the number of processors required for scheduling a set of periodic preemptive independent hard real-time tasks. We use a partitioning strategy with an EDF scheduling algorithm on each processor. The problem is NP-hard. We derive lower and upper bounds for the number of processors required to satisfy the constraints of the problem. We also compare a number of heuristic algorithms with each other and with the bounds derived in this research. Numerical results demonstrate that our lower bound is very tight. In the third part of the thesis, we study the problem of uplink scheduling in telecommunication systems with two dimensional resources. Our goal is to maximize the total value of the packets sent in uplink subframe such that system constraints and requirements are satisfied. The packets have various QoS requirements and have either soft or hard deadlines. We take two approaches, namely 0-1 and fractional approaches, to model the problem. Considering the properties of the application, we derive globally optimal solutions in polynomial time for the models. We also present a method to fine-tune the models. Numerical results are provided to compare the performance of the various optimal algorithms each corresponding to a model. / Thesis (Ph.D, Computing) -- Queen's University, 2009-04-24 08:22:04.238

The increasing complexity of time-critical Cyber-Physical Systems (CPS) presents significant challenges in designing optimization algorithms that balance generality, scalability, and performance. Traditional approaches often compromise one or more of these properties: general metaheuristic algorithms lack scalability and performance guarantees, while problem-specific methods sacrifice generality for improved efficiency or optimality. However, due to the NP-hard nature of many real-time scheduling and optimization problems, it is highly unlikely to design optimization algorithms that are simultaneously general, scalable, and optimal. Therefore, this dissertation addresses these challenges by developing novel optimization frameworks tailored for time-critical CPS and try to improve the trade-off among the three factors. The first contribution focuses on general and scalable optimization techniques, introducing frameworks such as NORTH, which operates with black-box schedulability constraints while achieving very good scalability and reasonably good performance. Additionally, another optimization framework targets at general robotic working environments by performing dynamic resource allocation. It demonstrates 20–50\% improvements in safety-performance metrics with low computational overhead. The second contribution advances domain-specific optimization techniques by relaxing the general requirements. For instance, flexible Logical Execution Time (LET) optimization achieves significant improvements in end-to-end latency, time disparity, and jitter by leveraging symbolic operations and efficient exploration of solution spaces. Similarly, a novel scheduling approach for DAG-based task models minimizes worst-case end-to-end latency and time disparity through 1-opt solutions with polynomial runtime complexity, achieving up to 40\% performance gains over existing methods. These contributions push the boundaries of generality, scalability, and optimality in real-time systems optimization, providing practical solutions to complex scheduling and resource allocation problems. The proposed frameworks are validated through extensive experimental studies, demonstrating their applicability and impact across a range of real-world scenarios. / Doctor of Philosophy / Cyber-Physical Systems (CPS) are transformative technologies that seamlessly integrate computation, networking, and physical processes, forming the backbone of innovations like autonomous vehicles, smart grids, and advanced medical devices. Among them, time-critical CPS, or real-time systems, are uniquely challenging as they require not only logical correctness but also strict adherence to timing constraints. Failing to meet these constraints in applications like flight control or automotive systems can lead to catastrophic outcomes. The design of time-critical CPS involves solving complex optimization problems to balance competing goals such as latency, energy, reliability, and cost. However, the growing system complexity, driven by trends like parallel computing and heterogeneous platforms, makes achieving scalability, optimality, and general applicability in optimization algorithms increasingly difficult. Traditional optimization methods either lack scalability, fail to generalize across diverse problems, or provide optimal solutions. This dissertation addresses these challenges by proposing novel optimization frameworks tailored to time-critical CPS. It introduces general and scalable techniques capable of achieving good performance across diverse scenarios, including methods for optimizing systems with complex schedulability constraints and dynamic task environments. It also presents domain-specific solutions that prioritize optimality and scalability for specific problems, such as flexible Logical Execution Time (LET) scheduling and time-triggered scheduling for directed acyclic graph (DAG)-based systems. Extensive experiment evaluation show that these novel techniques significantly improved various metrics, such as energy, schedulability, end-to-end latency, time disparity, and safety-performance trade-offs.

No description available.

No description available.

Execution time control is a technique that allows execution time budgets to be set and overruns to be handled dynamically to prevent deadline misses. This removes the need for the worst-case execution time (WCET) of tasks to be found by offline timing analysis – a problem that can be very hard to solve for modern computer architectures. Execution time control can also increase the processor utilization, as the WCET will often be much higher than the average execution time. This thesis describes how the GNU Ada Compiler and a bare-board Ravenscar run-time environment were ported to the Atmel AVR32 UC3 microcontroller series making the Ada programming language available on this architecture for the first time, and an implementation of Ada execution time control for this system that supports full execution time control for interrupt handling. Usage patterns for this brand new feature are demonstrated in Ada by extending the object-oriented real-time framework with execution time servers for interrupt handling, allowing the system to be protected against unexpected bursts of interrupts that could otherwise result in deadline misses. Separate execution time measurement for interrupt handling also improves the accuracy of measurement for tasks. As a direct result of the work presented in this thesis separate execution time measurement for interrupts will be included in the forthcoming ISO-standard for Ada 2012. While the implementation of execution time control is for the Ada programming language and the UC3 microcontroller series, the design and implementation should be portable to other architectures, and the principles of execution time control for interrupt handling applicable to other programming languages. Low run-time overhead is important for execution time control to be useful for real-time systems. Therefore a hardware Time Management Unit (TMU) was designed to reduce the overhead of execution time control. This design has been implemented for the UC3 and performance tests with the developed run-time environment shows that it gives a significant reduction of overhead. The memory-mapped design of the TMU also allows it to be implemented on other architectures.

No description available.