Skip to content

The project page provides all MATLAB source codes of the algorithms and simulation environments defined in the paper: An FTPAS for Response Time Analysis of Fixed Priority Real-Time Tasks with Resource Augmentation, Thi Huyen Chau Nguyen, Pascal Richard, Emmanuel Grolleau, +IEEE Transactions on Computers+, 2014, accepted for publication, http://…

lias-laboratory/rt-approx-fpps

main
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 

An FTPAS for Response Time Analysis of Fixed Priority Real-Time Tasks with Resource Agmentation

The project page provides all MATLAB source codes of the algorithms and simulation environments defined in the paper "An FTPAS for Response Time Analysis of Fixed Priority Real-Time Tasks with Resource Augmentation", Thi Huyen Chau Nguyen, Pascal Richard, Emmanuel Grolleau, +IEEE Transactions on Computers+, 2014, accepted for publication.http://dx.doi.org/10.1109/TC.2014.2346178

The paper presents a best possible Fully Polynomial Time Approximation Scheme under resource augmentation for computing worst-case response time upper bounds of fixed-priority tasks with arbitrary deadlines to be executed upon a uniprocessor platform.

Download

Download both files (Approx.zip and Graphs_of_all_Experiments.zip) at https://github.com/lias-laboratory/RT-Approx-FPPS/releases

Installation instructions

All MATLAB code files must be extracted in the same folder for execution.

File descriptions

  • Approx.zip - MATLAB source codes by categories:

    • FTPAS - MATLAB codes of the Fully Polynimial Time Approximation Scheme
      • Approx.m - main function of FTPAS algorithm (Algorithm 3 in the paper)
      • ApproxFirstStage.m - FirstStage algorithm (Algorithm 1 in the paper)
      • ApproxSecondStage.m - SecondStage algorithm (Algorithm 2 in the paper)
      • ApproxSchedPoints.m - list of scheduling points considered in the first stage (Equation 13 in the paper)
      • Approx_wil.m - cumulative approximate workload (Equation 8 in the paper)
      • jobindex.m - Index of the most recently released job of tau_i (Equation 16 in the paper)
      • intersection.m - intersection of approximate workload and processor capacity (see Fig. 2 in the paper)
    • Exact Response Time Analysis - MATLAB codes (Lehoczky's algorithm)
      • ResponseTime.m - main function of exact RTA
      • JobResponseTime.m - worst-case response time of Job l of Task i in the level-i busy period
    • Linear Response Time Upper Bound (LRTUB) - MATLAB codes (Bini, Nguyen, Richard, Baruah Algorithm, 2009)
      • UpperBoundBB.m - function computing LRTUB (Equation 6 in the paper)
    • Taskset Generator - MATLAB codes for generating tasksets for experiments
      • GenTasks.m - main function for generating taskset under various parameters (see Section 6.1 in the paper)
      • UUniFast.m - Bini's UUniFast function for generating unbiased utilization factors
      • rm.m - Sort task according to Rate Monotonic scheduling algorithm (implicit deadline tasks)
      • dm.m - Sort task according to Rate Monotonic scheduling algorithm (constrained-deadline tasks)
      • Audsley.m - - Sort task according to Audsley's scheduling algorithm (arbitrary deadline tasks)
    • Experiment 1 - MATLAB codes for monitoring the average accuracy parameter of the FPTAS for beating LRTUB (graph generator in Section 6.2 in the paper)
      • PlotMinK.m - main file for generating graphs under various parameter of controls
      • ComputeMinK.m - Compute minimum FPTAS accuracy parameter to beat LRTUB
    • Experiment 2 - MATLAB codes for monitoring the average speedup factor of FTPAS and LRTUB (graph generator in Section 6.3 in the paper)
      • PlotSdf.m - main file for generating graphs under various parameter of controls
      • ComputeSdf.m - replication of experiments that call the following to functions
      • SlowdownFactor.m - resource augmentation for FTPAS to achieve performance of exact RTA
      • SlowdownFactor_bb.m - resource augmentation for LRTUB to achieve performance of exact RTA
    • Experiment 3 - MATLAB codes for monitoring the average acceptance ratio of FTPAS, LRTUB, Liu and Layland's utilization bound against exact RTA (graph generator in Section 6.4 in the paper).
      • PlotAccept.m - main file for generating graphs under various parameter of controls
      • ComputeAccept.m - Compute average schedulable tasksets according to FPTAS and LRTUB
    • Experiment 4 - MATLAB codes for monitoring the average error (UB - Exact)/Exact for the FPTAS and LRTUB (graph generator in Section 6.5 in the paper)
      • PlotError.m - main file for generating graphs under various parameter of controls
      • ComputeError.m - Compute the average error for the FPTAS against Exact RTA
      • ComputeErrorBB.m - Compute the average error for the LRTUB against Exact RTA
  • Graphs.zip - MATLAB figure files (.fig) generated during the experiments (only some of them are presented in the paper). These files can be directly opened using MATLAB.

Historic Contributors

Code Analysis

  • Programming Languages: MATLAB

About

The project page provides all MATLAB source codes of the algorithms and simulation environments defined in the paper: An FTPAS for Response Time Analysis of Fixed Priority Real-Time Tasks with Resource Augmentation, Thi Huyen Chau Nguyen, Pascal Richard, Emmanuel Grolleau, +IEEE Transactions on Computers+, 2014, accepted for publication, http://…

Resources

Stars

Watchers

Forks

Packages

No packages published