Kimaya Bedarkar authored 2 years ago and Björn Brandenburg committed 2 years ago

As described in #92, the name `np_uni_schedule` is problematic. This
patch renames the scheduler to the more appropriate `pmc_uni_schedule`.

Closes: #92

Marco Maida authored 2 years ago and Björn Brandenburg committed 2 years ago

- Slightly change `valid_nonpreemptive_readiness` so that `sched` is a
  parameter. This way, the proposition can be assumed to hold only for a
  certain schedule (making weaker assumptions).

- Modify `prev_job_nonpreemptive, to unconditionally get
  `jobs_must_be_ready_to_execute`.
  
- Revise lemmas accordingly. 

Kimaya Bedarkar authored 3 years ago and Björn Brandenburg committed 3 years ago

From a spec readability PoV, it's unfortunate that the policy that is
being respected doesn't show up in the code. The subject of definitions
should show up as an explicit argument, even if it is implicit
everywhere else. This is however difficult to realize for the current
`respects_policy_at_preemption_time` predicate due to difficulties with
coercion technicalities (see further details below).

Therefore, instead of `respects_policy_at_preemption_time`, we now have:

* `respects_JLDP_policy_at_preemption_point`
* `respects_JLFP_policy_at_preemption_point`
* `respects_FP_policy_at_preemption_point`

Further details: RT-PROOFS/rt-proofs!188 (comment 78569)

Closes: #82

It was a parameter but that wasn't of any use,
it was just making everything more noisy.

Sergey Bozhko authored 3 years ago and Björn Brandenburg committed 3 years ago

Add an implementation of arrival curves via fast
extrapolation of a finite arrival-curve prefix. 

LailaElbeheiry authored 4 years ago and Björn Brandenburg committed 4 years ago

With help from Marco Maida <mmaida@mpi-sws.org>, Sergey Bozhko <sbozhko@mpi-sws.org>, Björn Brandenburg <bbb@mpi-sws.org>.

This is a general definition and not specific to a particular
implementation.

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.)

- 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.

- 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

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).

- 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

- Implemented concrete job and tasks.
- Added a periodic arrival sequence.
- Created examples of applying a schedulability
  test to small task sets and concluding that
  no task misses a deadline.

- Now we have two definitions of work conserving, a simple version
  and another one based on count, along with a proof of equivalence.

- Implemented a concrete scheduler (basic and jitter)