Real-Time Systems project

Dependencies and Usage

This project requires C++23, make, Boost, GMP

Run make all to compile all programs.

Objectives

• Create a random periodic taskset generator using UUniFast algorithm
  • Implicit deadline (deadline = period)
  • Constrained deadline (deadline <= period)
  • Integer task parameters: period, worst case compute time, deadline
    • 100 <= period <= 1,0000
    • worst case compute time > 0
    • deadline >= 0.8 * period
• Create a uniprocessor simulator for the generated tasksets
  • Test up to 100,000 time units
  • Report first missed deadline if applicable
  • Assume the following:
    • No context switch overhead
    • Synchronous task release at start time
    • No dependency / shared resource between tasks
  • Preemption & Nonpreemption
  • Support FCFS, SJF, RM, EDF
• Create a schedulability analyzer for the generated tasksets
  • Implicit Preemptive EDF: Utilization bound analysis
  • Implicit Preemptive RM: Response time analysis
  • Constrained Preemptive EDF: Processor demand analysis
  • Constrained Preemptive DM: Response time analysis

Task 1: Taskset Generation

• Original UUniFast algorithm allocates utilization per task
  • Does not generate task parameters that match the allocated utilization
• Task parameter requirements cause actual utilization to drift
  • Utilization error can occur on every task upon parameter generation
  • Error accumulates as task count increases
• Modify UUniFast algorithm to generate task parameters on the fly

Original UUniFast algorithm

function vectU = UUniFast(n, UBar)
sumU = UBar;
for i=1:n-1,
    nextSumU = sumU.*randˆ(1/(n-i));
    vectU(i) = sumU - nextSumU;
    sumU = nextSumU;
end
vectU(n) = sumU;

Modified UUniFast algorithm

% Deadline generation omitted for brevity
function vectTask = UUniFast(n, UBar, Uerr)
while 1
    accU = 0;
    for i=1:n-1,
        remU = UBar - accU;
        nextU = remU .* (1 - randˆ(1 / (n-i)));
        T = randi([100, 1000])
        C = max(floor(nextU * T), 1);
        accU = accU + (C / T);
        vectTask(i) = [T, C];
    end
    nextU = UBar - accU;
    T = randi([100, 1000])
    C = max(floor(nextU * T), 1);
    accU = accU + (C / T);
    vectTask(n) = [T, C];
    if abs(UBar - accU) <= Uerr
        break
end

Shortcomings

For constrained deadline, the deadline is randomly selected in [0.8 * period, period]. If 0.8 * period < compute time, it is possible to generate an impossible task.

Task 2: Priority Scheduling Simulator

Priority metric

Every pending task is assigned a priority metric independently by the selected scheduling policy based on its task and job parameters.

• Task parameters
  • Period
  • Worst case compute time
  • Deadline
• Job parameters
  • Release time
  • Remaining compute time

For tasks that have missed their deadline, their metric is set to deadline - MAX_TIME. This ensures all missed tasks are ordered by deadline in the negative range while all pending tasks are ordered by priority in the positive range.

Preemption and Non-preemption

Under preemptive scheduling, the simulator advances time until the next job is released. This is implemented using an event generator managed in a priority queue. As there is no context switch overhead, it is ok for the simulator to be interrupted and reselect the same task for the next time slice.

Under non-preemptive scheduling, the simulator advances time until the current job is completed. This can result in the simulator skipping ahead in time without processing a deadline miss. However, the ordering guarantees made by the priority metric allows the simulator to correctly identify the first missed task in the next time slice.

Task 3: Schedulability analysis

Utilization bound for EDF

The actual utilization of the taskset is already computed during task generation in the modified UUniFast algorithm. Therefore this result is reused to avoid redundant computation.

Procesor demand for EDF

For large task count, the hyper-period can exceed the range of 64 bit integer very quickly. Therefore, multi-precision library was used to avoid integer overflow errors.

For taskset utilization of 1.0, error handling is required for division by zero.

Response time analysis for RM, DM

The algorithm fails to converge on overloaded systems. Therefore, the algorithm is forcefully terminated when a task's response time exceeds its period.

Bonus: Optimization

Multi-threading

In order to repeat multiple iterations without excessive complexity, a homogenous task model, or data parallelism is used. For processing N iterations on P threads, each thread processes N/P iterations.

To support this program model, every component is designed to produce an output for a given iteration number.

• Taskset generator(i) -> produce i-th taskset
• Simulator(i) -> produce simulation result of i-th taskset
• Schedulability analyzer(i) -> produce analysis result of i-th taskset

Serialization

For the same taskset to be simulated and analyzed for schedulability, the generated taskset must be serialized and saved to disk. To facilitate multi-threading described above, each taskset is serialized into separate files in the same directory, named by their number.

This avoids the complexity associated with dividing a single input into equal workloads and allows parallel IO.