Skip to content
Snippets Groups Projects
  1. Apr 05, 2019
  2. Sep 04, 2018
  3. Jul 17, 2018
    • Felipe Cerqueira's avatar
      Formalization of Weakly Sustainable Policy · 258edf49
      Felipe Cerqueira authored
      1) Formalize the notion of weakly sustainable policy, along with
      its contrapositive, and prove the equivalence between the two.
      
      2) Establish weak sustainability of self-suspending tasks w.r.t.
      execution times and variable suspension times, based on the
      transformation we had formalized.
      v0.3
      258edf49
  4. Jan 05, 2018
  5. Dec 14, 2017
  6. Dec 07, 2017
    • Felipe Cerqueira's avatar
      Major Commit: Suspension-aware Scheduling · 3f39fe20
      Felipe Cerqueira authored
      1) Definition of a generic model for job suspensions based on
         received service (e.g., job j_1 should suspend for 4ms as
         soon as service reaches 5ms).
      
      2) Definition of the dynamic suspension model (i.e., cumulative
         suspension of job j_1 <= X).
      
      3) Analysis of suspension-aware scheduling by inflation of job
         costs (via schedule reduction). In the literature, this is
         called suspension-oblivious analysis.
      
      4) Analysis of suspension-aware scheduling by adjusting job
         jitter (via schedule reduction).
      
      5) Proof of (weak) sustainability of job costs under suspension-aware
         scheduling. We show that if we increase the costs of all jobs while
         reducing their suspension times in a certain way, the response times
         of all jobs do not decrease.
      
         This has an important implication regarding worst-case schedules: if
         some schedulability analysis already accounts for the fact that job
         suspension times can vary from 0 to the task suspension bound, then
         it's perfectly safe to assume that jobs execute for their WCET.
      
      6) Proof of sustainability of the cost of a single job under
         suspension-aware scheduling. That is, we show that increasing the
         cost of a single job does not reduce its own response time.
         (Note that this is a very basic result that applies to many
         work-conserving, JLFP schedulers. We don't claim anything about
         the response time of other jobs.)
      3f39fe20
    • Felipe Cerqueira's avatar
      Make Prosa compatible with Coq 8.7.0 and Mathcomp 1.6.4 · b6c93d38
      Felipe Cerqueira authored
      - Remove Require declarations from Modules.
      - Small fixes due to changes in the type checker.
      - Generate _CoqProject with Makefile and remove spurious warnings from ssreflect.
      b6c93d38
  7. Jan 10, 2017
  8. Nov 25, 2016
    • Felipe Cerqueira's avatar
      Restructure directory + Add jitter-aware RTA · a5f12a43
      Felipe Cerqueira authored
      - Added definitions and implementation of jitter-aware RTA for
        uniprocessor scheduling.
      - The Prosa directory was restructured to better accomodate the different
        types of arrival sequences and schedules.
      a5f12a43
  9. Oct 26, 2016
  10. Oct 18, 2016
    • Felipe Cerqueira's avatar
      Major commit: Suspension-Oblivious Analysis · 843c6ffc
      Felipe Cerqueira authored
      - Add generic definition of job suspension based on the cumulative service
      - Define the dynamic suspension model (based on task suspension bounds)
      - Add suspension semantics for uniprocessor schedules
      - Formalize reduction from suspension-aware schedule to suspension-oblivious
        schedule by inflating costs (works with JLDP policies and non-unique priorities)
      - Formalize suspension-oblivious FP RTA using the reduction
      - Add implementation of a concrete suspension-aware scheduler
      - Test suspension-oblivious FP RTA with an actual task set
      - Add simpler definition for JLFP policies
      - Generalize busy interval lemmas from FP to JLFP scheduling
      843c6ffc
  11. Sep 06, 2016
    • Felipe Cerqueira's avatar
      Major commit: Uniprocessor RTA · ac6f0d4e
      Felipe Cerqueira authored
      This commit contains several updates related to uniprocessor scheduling.
      
      - Basic definitions of uniprocessor scheduling (see model/uni)
      - Definitions of worload and service for generic sets of jobs (see service.v and workload.v in model/uni)
      - Definitions and lemmas about busy intervals (see model/uni/basic/busy_interval.v)
      - Definition of an arrival bound for sporadic tasks (see model/arrival_bounds.v)
      - Definitions and correctness proofs of the RTA for FP scheduling
        (also works with non-unique priorities and arbitrary deadlines, but gives pessimistic bounds)
      - Implementation of the FP RTA to check for contradictory assumptions
      
      In addition, we have also defined partitioned scheduling and proven how it relates
      with uniprocessor (see model/partitioned).
      ac6f0d4e
  12. Aug 05, 2016
  13. Jun 08, 2016
  14. Jun 06, 2016
    • Felipe Cerqueira's avatar
      Major Commit - Prosa v0.2 · f7a79913
      Felipe Cerqueira authored
      - Add definitions related to APA scheduling
      - Prove correctness of reduction-based RTA for APA scheduling (FP and EDF)
      - Add implementation of a weak APA scheduler
      - Update definition of taskset to assume uniqueness
      - Modify names and comments to improve readability
      - Remove strong assumptions about priority order in FP scheduling
      - Add tests with FP RTA for every model
      - Add tests for RTA with parallel jobs
      f7a79913
  15. May 05, 2016
  16. May 04, 2016
  17. Mar 31, 2016
  18. Mar 01, 2016
  19. Feb 23, 2016
  20. Feb 16, 2016
  21. Feb 14, 2016
  22. Feb 12, 2016
  23. Feb 06, 2016
  24. Feb 01, 2016
    • Felipe Cerqueira's avatar
      Major Changes in RTA and Directory Structure · 32126a75
      Felipe Cerqueira authored
      - Removed unnecessary assumption in RTA about task precedence/no intra-task parallelism.
      - Scheduler models and analyses are organized in separate modules/folders.
      - Added RTA for FP and EDF for schedulers with release jitter.
      - The scheduling invariants were split into more fine-grained assumptions:
        (a) scheduler is work-conserving
        (b) scheduler enforces FP/JLDP priority X
      - New helper lemmas about counting, and sorted/uniq lists
      - Inclusion of tactics feed and feed_n (see documentation).
      - Added a Makefile generator
      32126a75
Loading