Real-time systems are those in which tasks (programs) have timing requirements in addition to requirements of logical correctness. Hard real-time systems are real-time systems in which the timing requirements must be satisfied in order to avoid catastrophic situations. Systems with periodic tasks executing in a hard real-time environment require knowledge of the worst-case execution times (WCETs) of all tasks a priori in order to guarantee schedulability. Most real-time systems are embedded. Embedded systems typically have constrained resources that need to be allocated carefully in order to utilize the system efficiently.

Static timing analysis is considered a viable approach for calculating upper bounds on the WCET of a task. Static timing analysis models the architectural components of a computing system in order to obtain the time taken by the longest path identified in a given task. Architectural features such as out-of-order pipelines and caches cause unpredictability in timing analysis, leading to overly pessimistic estimates of the WCET of a task. One such feature that is particularly hard to model is the data cache.

In the first phase of my research work, a data cache analyzer framework known as the Cache Miss Equations framework [1, 6, 7] was enhanced. The new framework provides three fundamental enhancements over the original one and thus relaxes certain constraints that the original framework imposed on tasks.

• Forced loop fusion is employed to concatenate loop bodies of sequential loop nests in order to build one single loop nest that may then be analyzed by the framework. This technique also allows non-rectangular loops in tasks.
• Certain types of data dependent conditionals (those with only if-then clauses, but no else clauses) are permitted. An upper bound on the number of data cache misses is provided in such a case.
• While the original framework gave an upper bound on the number of data cache misses incurred by a task, the new one produces reference patterns that identify the positions of each of these misses as well.

This data cache analysis framework was integrated into an existing static timing analyzer framework that calculates the WCET of a task.

Real-time systems typically have multiple tasks, each with a unique priority, executing in a preemptive environment. In analyzing such systems and answering three important questions are answered.

• What is the maximum number of preemptions a task may undergo?
By considering ranges of execution times between the best and the worst-case execution times, infeasible preemption points are eliminated and realistic worst-case scenarios are constructed.
• Where would each preemption be placed in the iteration space of the preempted task?
A range of iteration points where a task might be executing when it is preempted is identified.
• What is the additional delay incurred by the preempted task due to each of these preemptions?
The delay at each point is calculated using access chains (reuse chains) and the maximum delay among them is considered to be the preemption delay at the given point.

Some real-time tasks may have regions where they use shared resources that are non-premptable. Traditionally, such tasks have been scheduled completely non-preemptively to simplify timing analysis. This suffers from the downside of decreased schedulability. A methodology to make only critical sections non-preemptive regions (NPRs), but keep legal preemptions was proposed and implemented. This framework was enhanced to support resource-sharing policies such as the Priority Inheritance Protocol (PIP) instead of making critical sections non-preemptive. This framework may be used as a means to identify what method is suitable for what sets of tasks.

Single core processor designs have reached a clock frequency wall due to area and power considerations, leading to designs with multiple processors on a single chip, known as chip multiprocessors or simply multicore processors. The use of such multicore processors in real-time/embedded systems introduces several research challenges that need to be addressed in order to maintain safety of such systems.

Several real-time (global) scheduling policies for multicore systems assume that tasks may be migrated between cores. However, migration of tasks among cores reduces time predictability of tasks due to cache warm-up overheads while increasing traffic on the Network-on-Chip (NoC) interconnect. In order to improve time predictability of real-time tasks, several novel migration mechanisms with bounded migration overheads are proposed. In addition, novel policies to guide migration decisions in order to improve overall system utilization are proposed.