bertogna_edf_theory.v 50.9 KB
Newer Older
Felipe Cerqueira's avatar
Felipe Cerqueira committed
1
Require Import rt.util.all rt.util.divround.
2 3 4 5 6 7
Require Import rt.model.arrival.basic.task rt.model.arrival.basic.job rt.model.priority rt.model.arrival.basic.task_arrival.
Require Import rt.model.schedule.global.workload rt.model.schedule.global.response_time
               rt.model.schedule.global.schedulability.
Require Import rt.model.schedule.global.basic.schedule.
Require Import rt.model.schedule.apa.platform rt.model.schedule.apa.interference
               rt.model.schedule.apa.affinity rt.model.schedule.apa.constrained_deadlines.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
8 9 10 11 12 13
Require Import rt.analysis.apa.workload_bound rt.analysis.apa.interference_bound_edf.
From mathcomp Require Import ssreflect ssrbool eqtype ssrnat seq fintype bigop div path.

Module ResponseTimeAnalysisEDF.

  Export Job SporadicTaskset ScheduleOfSporadicTask Workload Schedulability ResponseTime
14
         Priority TaskArrival WorkloadBound InterferenceBoundEDF
Felipe Cerqueira's avatar
Felipe Cerqueira committed
15 16 17 18 19 20 21 22 23 24 25 26 27 28
         Interference Platform Affinity ConstrainedDeadlines.

  (* In this section, we prove that any fixed point in the APA-reduction of
     Bertogna and Cirinei's RTA for EDF scheduling is a safe response-time bound.
     This result corresponds to Lemma 10 in the revised version of the APA paper:
     http://www.mpi-sws.org/~bbb/papers/pdf/ecrts13a-rev1.pdf *)
  Section ResponseTimeBound.

    Context {sporadic_task: eqType}.
    Variable task_cost: sporadic_task -> time.
    Variable task_period: sporadic_task -> time.
    Variable task_deadline: sporadic_task -> time.
    
    Context {Job: eqType}.
29
    Variable job_arrival: Job -> time.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
30 31 32 33 34
    Variable job_cost: Job -> time.
    Variable job_deadline: Job -> time.
    Variable job_task: Job -> sporadic_task.
    
    (* Assume any job arrival sequence... *)
35
    Variable arr_seq: arrival_sequence Job.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
36 37 38

    (* ... in which jobs arrive sporadically and have valid parameters. *)
    Hypothesis H_sporadic_tasks:
39
      sporadic_task_model task_period job_arrival job_task arr_seq.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
40
    Hypothesis H_valid_job_parameters:
41 42
      forall j,
        arrives_in arr_seq j ->
Felipe Cerqueira's avatar
Felipe Cerqueira committed
43 44 45 46 47 48 49 50 51 52 53 54
        valid_sporadic_job task_cost task_deadline job_cost job_deadline job_task j.

    (* Consider a task set ts where all tasks have valid parameters
       and constrained deadlines, ... *)
    Variable ts: taskset_of sporadic_task.
    Hypothesis H_valid_task_parameters:
      valid_sporadic_taskset task_cost task_period task_deadline ts.
    Hypothesis H_constrained_deadlines:
      forall tsk, tsk \in ts -> task_deadline tsk <= task_period tsk.

    (* ... and assume that all jobs in the arrival sequence come from the task set. *)
    Hypothesis H_all_jobs_from_taskset:
55
      forall j, arrives_in arr_seq j -> job_task j \in ts.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
56 57 58 59 60 61
    
    (* Also assume that every task has a non-empty processor affinity alpha. *)
    Context {num_cpus: nat}.
    Variable alpha: task_affinity sporadic_task num_cpus.

    (* Next, consider any schedule such that...*)
62 63 64
    Variable sched: schedule Job num_cpus.
    Hypothesis H_jobs_come_from_arrival_sequence:
      jobs_come_from_arrival_sequence sched arr_seq.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
65 66 67 68

    (* ...jobs are sequential and do not execute before their
       arrival times nor longer than their execution costs. *)
    Hypothesis H_sequential_jobs: sequential_jobs sched.
69 70
    Hypothesis H_jobs_must_arrive_to_execute: jobs_must_arrive_to_execute job_arrival sched.
    Hypothesis H_completed_jobs_dont_execute: completed_jobs_dont_execute job_cost sched.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
71 72

    (* Assume that the schedule is an work-conserving APA schedule that
73
       respects EDF priorities. *)
Felipe Cerqueira's avatar
Felipe Cerqueira committed
74
    Hypothesis H_respects_affinity: respects_affinity job_task sched alpha.
75 76
    Hypothesis H_work_conserving: apa_work_conserving job_arrival job_cost job_task arr_seq
                                                      sched alpha.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
77
    Hypothesis H_edf_policy:
78 79
      respects_JLFP_policy_under_weak_APA job_arrival job_cost job_task arr_seq
                                          sched alpha (EDF job_arrival job_deadline).
Felipe Cerqueira's avatar
Felipe Cerqueira committed
80 81 82

    (* Let's define some local names to avoid passing many parameters. *)
    Let no_deadline_is_missed_by_tsk (tsk: sporadic_task) :=
83
      task_misses_no_deadline job_arrival job_cost job_deadline job_task arr_seq sched tsk.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
84
    Let response_time_bounded_by (tsk: sporadic_task) :=
85
      is_response_time_bound_of_task job_arrival job_cost job_task arr_seq sched tsk.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125

    (* Now we consider the response-time recurrence. In the computation of
       the response-time bound, we assume that each task under analysis has
       a non-empty subaffinity alpha'.
       Note that the notation #|...| expresses the cardinality of the set. *)
    Variable alpha': task_affinity sporadic_task num_cpus.
    Hypothesis H_affinity_subset: forall tsk, tsk \in ts -> is_subaffinity (alpha' tsk) (alpha tsk).
    Hypothesis H_at_least_one_cpu : forall tsk, tsk \in ts -> #|alpha' tsk| > 0.
    
    (* Assume that a response-time bound R is known...  *)
    Let task_with_response_time := (sporadic_task * time)%type.
    Variable rt_bounds: seq task_with_response_time.

    (* ...for any task in the task set, ... *)
    Hypothesis H_rt_bounds_contains_all_tasks: unzip1 rt_bounds = ts.

    (* ... where R is a fixed-point of the response-time recurrence (with
           alpha' as the reduced affinity mask), ... *)
    Let I (tsk: sporadic_task) (delta: time) :=
      total_interference_bound_edf task_cost task_period task_deadline alpha
                                   tsk (alpha' tsk) rt_bounds delta.
    Hypothesis H_response_time_is_fixed_point :
      forall tsk R,
        (tsk, R) \in rt_bounds ->
        R = task_cost tsk + div_floor (I tsk R) #|alpha' tsk|.
    
    (* ..., and R is no larger than the deadline. *)
    Hypothesis H_tasks_miss_no_deadlines:
      forall tsk R,
        (tsk, R) \in rt_bounds -> R <= task_deadline tsk.

    (* In order to prove that R is a response-time bound, we first provide some lemmas. *)
    Section Lemmas.

      (* Let (tsk, R) be any task to be analyzed, with its response-time bound R. *)
      Variable tsk: sporadic_task.
      Variable R: time.
      Hypothesis H_tsk_R_in_rt_bounds: (tsk, R) \in rt_bounds.

      (* Consider any job j of tsk ... *)
126 127
      Variable j: Job.
      Hypothesis H_j_arrives: arrives_in arr_seq j.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
128 129 130 131 132 133 134
      Hypothesis H_job_of_tsk: job_task j = tsk.

      (* ... that did not complete on time, ... *)
      Hypothesis H_j_not_completed: ~~ completed job_cost sched j (job_arrival j + R).

      (* ... and that is the first job not to satisfy its response-time bound. *)
      Hypothesis H_all_previous_jobs_completed_on_time :
135 136
        forall j_other tsk_other R_other,
          arrives_in arr_seq j_other ->
Felipe Cerqueira's avatar
Felipe Cerqueira committed
137 138 139 140 141 142 143
          job_task j_other = tsk_other ->
          (tsk_other, R_other) \in rt_bounds ->
          job_arrival j_other + R_other < job_arrival j + R ->
          completed job_cost sched j_other (job_arrival j_other + R_other).

      (* Let's call x the interference incurred by job j due to tsk_other, ...*)
      Let x (tsk_other: sporadic_task) :=
144
        task_interference job_arrival job_cost job_task sched alpha j
Felipe Cerqueira's avatar
Felipe Cerqueira committed
145 146 147
                          tsk_other (job_arrival j) (job_arrival j + R).

      (* and X the total interference incurred by job j due to any task. *)
148
      Let X := total_interference job_arrival job_cost sched j (job_arrival j) (job_arrival j + R).
Felipe Cerqueira's avatar
Felipe Cerqueira committed
149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209

      (* Recall Bertogna and Cirinei's workload bound ... *)
      Let workload_bound (tsk_other: sporadic_task) (R_other: time) :=
        W task_cost task_period tsk_other R_other R.

      (*... and the EDF-specific bound, ... *)
      Let edf_specific_bound (tsk_other: sporadic_task) (R_other: time) :=
        edf_specific_interference_bound task_cost task_period task_deadline tsk tsk_other R_other.

      (* ... which combined form the interference bound. *)
      Let interference_bound (tsk_other: sporadic_task) (R_other: time) :=
        interference_bound_edf task_cost task_period task_deadline tsk R (tsk_other, R_other). 
      
      (* Based on the definition of a different task in subaffinity alpha', ... *)
      Let other_task_in alpha' := different_task_in alpha tsk alpha'.

      (* ...let (other_tasks_in alpha') denote the set of tasks that are different from tsk
         and that can be scheduled on subaffinity alpha'. *)
      Let other_tasks_in alpha' :=
        [seq tsk_other <- ts | other_task_in (alpha' tsk) tsk_other].

      (* Now we establish results the interfering tasks. *)
      Section LemmasAboutInterferingTasks.
        
        (* Let (tsk_other, R_other) be any pair of higher-priority task and
           response-time bound computed in previous iterations. *)
        Variable tsk_other: sporadic_task.
        Variable R_other: time.
        Hypothesis H_response_time_of_tsk_other: (tsk_other, R_other) \in rt_bounds.

        (* Note that tsk_other is in the task set, ...*)
        Lemma bertogna_edf_tsk_other_in_ts: tsk_other \in ts.
        Proof.
          by rewrite set_mem -H_rt_bounds_contains_all_tasks; apply/mapP; exists (tsk_other, R_other).
        Qed.

        (* ... and R_other is larger than the cost of tsk_other. *)
        Lemma bertogna_edf_R_other_ge_cost :
          R_other >= task_cost tsk_other.
        Proof.
          by rewrite [R_other](H_response_time_is_fixed_point tsk_other);
            first by apply leq_addr.
        Qed.

        (* Since tsk_other cannot interfere more than it executes, we show that
           the interference caused by tsk_other is no larger than workload bound W. *)
        Lemma bertogna_edf_workload_bounds_interference :
          x tsk_other <= workload_bound tsk_other R_other.
        Proof.
          unfold valid_sporadic_job in *.
          rename H_all_previous_jobs_completed_on_time into BEFOREok,
                 H_valid_job_parameters into PARAMS,
                 H_valid_task_parameters into TASK_PARAMS,
                 H_constrained_deadlines into RESTR,
                 H_tasks_miss_no_deadlines into NOMISS.
          unfold x, task_interference.
          have INts := bertogna_edf_tsk_other_in_ts.
          apply leq_trans with (n := workload job_task sched tsk_other
                                         (job_arrival j) (job_arrival j + R));
            first by apply task_interference_le_workload.
          by apply workload_bounded_by_W with (task_deadline0 := task_deadline)
210 211
             (job_arrival0 := job_arrival) (arr_seq0 := arr_seq)
             (job_cost0 := job_cost) (job_deadline0 := job_deadline); try (by ins); last 2 first;
Felipe Cerqueira's avatar
Felipe Cerqueira committed
212 213 214 215 216 217 218 219 220 221 222 223
            [ by apply bertogna_edf_R_other_ge_cost
            | by ins; apply NOMISS
            | by ins; apply TASK_PARAMS
            | by ins; apply RESTR
            | by ins; apply BEFOREok with (tsk_other := tsk_other)].
        Qed.

        (* Recall that the edf-specific interference bound also holds for tsk_other. *)
        Lemma bertogna_edf_specific_bound_holds :
          x tsk_other <= edf_specific_bound tsk_other R_other.
        Proof.
          apply interference_bound_edf_bounds_interference with (job_deadline0 := job_deadline)
224
                                                   (arr_seq0 := arr_seq) (ts0 := ts); try (by done);
Felipe Cerqueira's avatar
Felipe Cerqueira committed
225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
            [ by apply bertogna_edf_tsk_other_in_ts
            | by apply H_tasks_miss_no_deadlines
            | by apply H_tasks_miss_no_deadlines | ].
          by ins; apply H_all_previous_jobs_completed_on_time with (tsk_other := tsk_other). 
        Qed.
        
      End LemmasAboutInterferingTasks.

      (* Next we prove some lemmas that help to derive a contradiction.*)
      Section DerivingContradiction.

      (* 0) Since job j did not complete by its response time bound, it follows that
            the total interference X exceeds  R - e_k + 1. *)
      Lemma bertogna_edf_too_much_interference : X >= R - task_cost tsk + 1.
      Proof.
        rename H_completed_jobs_dont_execute into COMP,
               H_valid_job_parameters into PARAMS, H_response_time_is_fixed_point into REC,
               H_job_of_tsk into JOBtsk, H_j_not_completed into NOTCOMP.
        unfold completed, valid_sporadic_job in *.
        unfold X, total_interference; rewrite addn1.
        rewrite -(ltn_add2r (task_cost tsk)).
        rewrite subh1; last by rewrite [R](REC tsk) // leq_addr.
        rewrite -addnBA // subnn addn0.
        move: (NOTCOMP) => /negP NOTCOMP'.
        rewrite neq_ltn in NOTCOMP.
        move: NOTCOMP => /orP [LT | BUG]; last first.
        {
          exfalso; rewrite ltnNge in BUG; move: BUG => /negP BUG; apply BUG.
          by apply cumulative_service_le_job_cost.
        }
        apply leq_ltn_trans with (n := (\sum_(job_arrival j <= t < job_arrival j + R)
256
                                     backlogged job_arrival job_cost sched j t) +
Felipe Cerqueira's avatar
Felipe Cerqueira committed
257 258 259 260
                                   service sched j (job_arrival j + R)); last first.
        {
          rewrite -addn1 -addnA leq_add2l addn1.
          apply leq_trans with (n := job_cost j); first by done.
261
          by specialize (PARAMS j H_j_arrives); des; rewrite -JOBtsk.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
262 263 264 265 266 267 268
        }
        unfold service; rewrite service_before_arrival_eq_service_during //.
        rewrite -big_split /=.
        apply leq_trans with (n := \sum_(job_arrival j <= i < job_arrival j + R) 1);
          first by rewrite big_const_nat iter_addn mul1n addn0 addKn.
        rewrite big_nat_cond [\sum_(_ <= _ < _ | true) _]big_nat_cond.
        apply leq_sum; move => i /andP [/andP [GEi LTi] _].
269
        destruct (backlogged job_arrival job_cost sched j i) eqn:BACK;
Felipe Cerqueira's avatar
Felipe Cerqueira committed
270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287
          first by rewrite -addn1 addnC; apply leq_add.
        apply negbT in BACK.
        rewrite add0n lt0n -not_scheduled_no_service negbK.
        rewrite /backlogged negb_and negbK in BACK.
        move: BACK => /orP [/negP NOTPENDING | SCHED]; last by done.
        exfalso; apply NOTPENDING; unfold pending; apply/andP; split; first by done.
        apply/negP; red; intro BUG; apply NOTCOMP'.
        by apply completion_monotonic with (t := i); try (by done); apply ltnW.
      Qed.

      (* 1) Next, we prove that during the scheduling window of j, any job that is
            scheduled while j is backlogged comes from a different task.
            This follows from the fact that j is the first job not to complete
            by its response-time bound, so previous jobs of j's task must have
            completed by their periods and cannot be pending. *)
      Lemma bertogna_edf_interference_by_different_tasks :
        forall t j_other,
          job_arrival j <= t < job_arrival j + R ->
288 289
          arrives_in arr_seq j_other ->
          backlogged job_arrival job_cost sched j t ->
Felipe Cerqueira's avatar
Felipe Cerqueira committed
290 291 292 293 294 295 296 297 298 299 300
          scheduled sched j_other t ->
          job_task j_other != tsk.
      Proof.
        rename H_all_jobs_from_taskset into FROMTS,
               H_valid_task_parameters into PARAMS,
               H_job_of_tsk into JOBtsk, H_sporadic_tasks into SPO,
               H_work_conserving into WORK,
               H_tsk_R_in_rt_bounds into INbounds,
               H_all_previous_jobs_completed_on_time into BEFOREok,
               H_tasks_miss_no_deadlines into NOMISS,
               H_constrained_deadlines into RESTR.
301
        move => t j_other /andP [LEt GEt] ARRother BACK SCHED.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
302 303 304 305 306 307
        apply/eqP; red; intro SAMEtsk.
        move: SCHED => /existsP [cpu SCHED].
        assert (SCHED': scheduled sched j_other t).
          by apply/existsP; exists cpu.
        clear SCHED; rename SCHED' into SCHED.
        move: (SCHED) => PENDING.
308 309
        apply scheduled_implies_pending with (job_arrival0 := job_arrival) (job_cost0 := job_cost)
           in PENDING; try (by done).
Felipe Cerqueira's avatar
Felipe Cerqueira committed
310 311 312
        destruct (ltnP (job_arrival j_other) (job_arrival j)) as [BEFOREother | BEFOREj].
         {
          move: (BEFOREother) => LT; rewrite -(ltn_add2r R) in LT.
313
          specialize (BEFOREok j_other tsk R ARRother SAMEtsk INbounds LT).
Felipe Cerqueira's avatar
Felipe Cerqueira committed
314 315 316 317 318 319 320
          move: PENDING => /andP [_ /negP NOTCOMP]; apply NOTCOMP.
          apply completion_monotonic with (t0 := job_arrival j_other + R); try (by done).
          apply leq_trans with (n := job_arrival j); last by done.
          apply leq_trans with (n := job_arrival j_other + task_deadline tsk);
            first by rewrite leq_add2l; apply NOMISS.
          apply leq_trans with (n := job_arrival j_other + task_period tsk);
            first by rewrite leq_add2l; apply RESTR; rewrite -JOBtsk FROMTS.
321
          rewrite -SAMEtsk; apply SPO; try (by done); [ | by rewrite JOBtsk | by apply ltnW].
Felipe Cerqueira's avatar
Felipe Cerqueira committed
322 323 324 325
          by red; intro EQ; subst; rewrite ltnn in BEFOREother.
        }
        {
          move: PENDING => /andP [ARRIVED _].
326
          exploit (SPO j j_other); try (by done); [ | by rewrite SAMEtsk | ]; last first.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344
          {
            apply/negP; rewrite -ltnNge.
            apply leq_ltn_trans with (n := t); first by done.
            apply leq_trans with (n := job_arrival j + R); first by done.
            by rewrite leq_add2l; apply leq_trans with (n := task_deadline tsk);
              [by apply NOMISS | by rewrite JOBtsk RESTR // -JOBtsk FROMTS].
          }
          by red; intros EQtsk; subst; rewrite /backlogged SCHED andbF in BACK.
        }
      Qed.
        
      (* 2) In order to use the lemmas in constrained_deadlines.v, we show that
            all jobs released before the end of the interval complete by their
            periods. This follows trivially from the hypothesis that all jobs
            before (job_arrival j + R) complete by their response-time bounds. 
            With this lemma, we can conclude that during job j's scheduling
            window there cannot be multiple pending jobs of each task.*)
      Lemma bertogna_edf_all_previous_jobs_complete_by_their_period:
345 346
        forall t j0,
          arrives_in arr_seq j0 ->
Felipe Cerqueira's avatar
Felipe Cerqueira committed
347 348 349 350 351 352 353 354 355 356
          t < job_arrival j + R ->
          job_arrival j0 + task_period (job_task j0) <= t ->
          completed job_cost sched j0
             (job_arrival j0 + task_period (job_task j0)).
      Proof.
        rename H_rt_bounds_contains_all_tasks into UNZIP,
               H_constrained_deadlines into CONSTR,
               H_tasks_miss_no_deadlines into NOMISS,
               H_all_jobs_from_taskset into FROMTS,
               H_all_previous_jobs_completed_on_time into BEFOREok.
357
        intros t j0 ARR0 LEt LE.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382
        cut ((job_task j0) \in unzip1 rt_bounds = true); last by rewrite UNZIP FROMTS.
        move => /mapP [p IN EQ]; destruct p as [tsk' R0]; simpl in *; subst tsk'.
        apply completion_monotonic with (t0 := job_arrival j0 + R0); first by done.
        {
          rewrite leq_add2l; apply leq_trans with (n := task_deadline (job_task j0));
            [by apply NOMISS | by apply CONSTR; rewrite FROMTS].
        }
        apply BEFOREok with (tsk_other := (job_task j0)); try by done.
        apply leq_ltn_trans with (n := t); last by done.
        apply leq_trans with (n := job_arrival j0 + task_period (job_task j0)); last by done.
        by rewrite leq_add2l; apply leq_trans with (n := task_deadline (job_task j0));
          [by apply NOMISS | apply CONSTR; rewrite FROMTS].
      Qed.

      (* 3) Next, we prove that the sum of the interference of each task is equal to the
            total interference multiplied by the number of processors in tsk's *actual*
            affinity. This holds because interference only occurs when all processors in
            the affinity are busy.
            With this lemma we can relate per-task interference with the total interference
            incurred by j (backlogged time). *)
      Lemma bertogna_edf_all_cpus_in_affinity_busy :
        \sum_(tsk_k <- other_tasks_in alpha) x tsk_k = X * #|alpha tsk|.
      Proof.
        have DIFFTASK := bertogna_edf_interference_by_different_tasks.
        rename H_all_jobs_from_taskset into FROMTS,
383
               H_valid_task_parameters into PARAMS, H_jobs_come_from_arrival_sequence into FROMSEQ,
Felipe Cerqueira's avatar
Felipe Cerqueira committed
384 385 386 387 388 389 390 391 392 393 394
               H_job_of_tsk into JOBtsk, H_sporadic_tasks into SPO,
               H_work_conserving into WORK,
               H_tsk_R_in_rt_bounds into INbounds,
               H_all_previous_jobs_completed_on_time into BEFOREok,
               H_tasks_miss_no_deadlines into NOMISS,
               H_rt_bounds_contains_all_tasks into UNZIP,
               H_constrained_deadlines into RESTR,
               H_respects_affinity into APA.
        unfold sporadic_task_model in *.
        unfold x, X, total_interference, task_interference.
        rewrite -big_mkcond -exchange_big big_distrl /= mul1n.
395
        rewrite [\sum_(_ <= _ < _ | backlogged _ _ _ _ _) _]big_mkcond.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
396
        apply eq_big_nat; move => t /andP [GEt LTt].
397
        destruct (backlogged job_arrival job_cost sched j t) eqn:BACK; last first.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413
        {
          rewrite (eq_bigr (fun i => 0));
            first by rewrite big_const_seq iter_addn mul0n addn0.
          by intros i _; rewrite (eq_bigr (fun i => 0));
            first by rewrite big_const_seq iter_addn mul0n addn0.
        }
        rewrite big_mkcond /=.
        rewrite exchange_big /=.
        apply eq_trans with (y := \sum_(cpu < num_cpus | cpu \in alpha tsk) 1);
          last by rewrite sum1_card.
        rewrite [\sum_(_ < _ | _) 1]big_mkcond /=.
        apply eq_bigr; intros cpu _.
        unfold can_execute_on in *.
        destruct (cpu \in alpha (job_task j)) eqn:ALPHA; rewrite -?JOBtsk ALPHA;
          last by rewrite big_filter (eq_bigr (fun x => 0));
            [by simpl_sum_const | by ins].
414 415 416
        move: (WORK j t H_j_arrives BACK cpu ALPHA) => [j_other /eqP SCHED]; unfold scheduled_on in *.
        have ARRother: arrives_in arr_seq j_other.
          by apply (FROMSEQ j_other t); apply/existsP; exists cpu; apply/eqP.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
417 418 419 420 421 422 423 424 425 426 427 428 429 430
        rewrite (bigD1_seq (job_task j_other)) /=; last by rewrite filter_uniq; destruct ts.
        {
          rewrite (eq_bigr (fun i => 0));
            last by intros i DIFF; rewrite /task_scheduled_on SCHED;apply/eqP;rewrite eqb0 eq_sym.
          rewrite big_const_seq iter_addn mul0n 2!addn0; apply/eqP; rewrite eqb1.
          by unfold task_scheduled_on; rewrite SCHED.
        }
        rewrite mem_filter; apply/andP; split; last by apply FROMTS.
        unfold different_task_in, affinity_intersects.
        apply/andP; split; last first.
        {
          apply/existsP; exists cpu; rewrite -JOBtsk ALPHA andTb.
          by apply APA with (t := t); apply/eqP.
        }
431
        apply DIFFTASK with (t := t); try (by done); first by auto.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456
        by apply/existsP; exists cpu; apply/eqP.
      Qed.

      (* 4) Recall that the reduction-based analysis considers only the interfering tasks
            within subaffinity (alpha' tsk), as opposed to (alpha tsk). Therefore, we must
            reason about the task interference wihin (alpha' tsk).
            We begin by showing that the cumulative interference within (alpha' tsk) is at
            least the total interference multiplied by the number of processors in (alpha' tsk). *)
      Lemma bertogna_edf_all_cpus_in_subaffinity_busy :
        \sum_(tsk_k <- other_tasks_in alpha') x tsk_k >= X * #|alpha' tsk|.
      Proof.
        have DIFFTASK := bertogna_edf_interference_by_different_tasks.
        rename H_all_jobs_from_taskset into FROMTS,
               H_valid_task_parameters into PARAMS,
               H_job_of_tsk into JOBtsk, H_sporadic_tasks into SPO,
               H_work_conserving into WORK,
               H_tsk_R_in_rt_bounds into INbounds,
               H_all_previous_jobs_completed_on_time into BEFOREok,
               H_tasks_miss_no_deadlines into NOMISS,
               H_rt_bounds_contains_all_tasks into UNZIP,
               H_constrained_deadlines into RESTR,
               H_respects_affinity into APA, H_affinity_subset into SUB.
        unfold sporadic_task_model in *.
        unfold x, X, total_interference, task_interference.
        rewrite -big_mkcond -exchange_big big_distrl /= mul1n.
457
        rewrite [\sum_(_ <= _ < _ | backlogged _ _ _ _ _) _]big_mkcond /=.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
458
        apply leq_sum_nat; move => t /andP [GEt LTt] _.
459
        destruct (backlogged job_arrival job_cost sched j t) eqn:BACK; last first.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
460 461 462 463 464 465 466 467 468 469 470 471 472 473 474
        {
          rewrite (eq_bigr (fun i => 0));
            first by rewrite big_const_seq iter_addn mul0n addn0.
          by intros i _; rewrite (eq_bigr (fun i => 0));
            first by rewrite big_const_seq iter_addn mul0n addn0.
        }
        rewrite big_mkcond /=.
        rewrite exchange_big /=.
        apply leq_trans with (n := \sum_(cpu < num_cpus | cpu \in alpha' tsk) 1);
          first by rewrite sum1_card.
        rewrite [\sum_(_ < _ | _) 1]big_mkcond /=.
        apply leq_sum; intros cpu _.
        unfold can_execute_on in *.
        destruct (cpu \in alpha' (job_task j)) eqn:ALPHA'; rewrite -?JOBtsk ALPHA';
          last by done.
475 476 477 478 479
        feed (SUB (job_task j)); first by apply FROMTS.
        specialize (SUB cpu ALPHA').
        move: (WORK j t H_j_arrives BACK cpu SUB) => [j_other /eqP SCHED]; unfold scheduled_on in *.
        have ARRother: arrives_in arr_seq j_other.
          by apply (H_jobs_come_from_arrival_sequence j_other t); apply/existsP; exists cpu; apply/eqP.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
480 481
        rewrite (bigD1_seq (job_task j_other)) /=; last by apply filter_uniq; destruct ts.
        {
482
          by rewrite {1}/task_scheduled_on SUB SCHED eq_refl andTb.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
483 484 485 486 487 488 489 490
        }
        {
          rewrite mem_filter; apply/andP; split; last by apply FROMTS.
          apply/andP; split; last first.
          {
            apply/existsP; exists cpu; apply/andP; split; first by rewrite -JOBtsk.
            by apply APA with (t := t); apply/eqP.
          }
491
          apply DIFFTASK with (t := t); try (by done); first by auto.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
492 493 494 495 496 497 498 499 500 501 502 503 504 505 506
          by apply/existsP; exists cpu; apply/eqP.
        }
      Qed.
      
      (* Let's define a predicate for whether a task is scheduled on (alpha tsk). *)
      Let scheduled_on_alpha_tsk := fun t tsk_k =>
        task_scheduled_on_affinity job_task sched (alpha tsk) tsk_k t.
      
      (* 5) Now we prove that, at all times that j is backlogged, the number
            of tasks whose affinity intersects (alpha' tsk) that are in fact
            scheduled on (alpha' tsk) is at least the size of (alpha' tsk).
            This is required to prove lemma (6). *)
      Lemma bertogna_edf_alpha'_is_full:
        forall t,
          job_arrival j <= t < job_arrival j + R ->
507
          backlogged job_arrival job_cost sched j t ->
Felipe Cerqueira's avatar
Felipe Cerqueira committed
508 509 510 511 512
          count (scheduled_on_alpha_tsk t) (other_tasks_in alpha') >= #|alpha' tsk|.
      Proof.
        have COMP := bertogna_edf_all_previous_jobs_complete_by_their_period.       
        rename H_work_conserving into WORK, H_respects_affinity into APA,
               H_affinity_subset into SUB, H_job_of_tsk into JOBtsk,
513
               H_all_jobs_from_taskset into FROMTS, H_jobs_come_from_arrival_sequence into FROMSEQ,
Felipe Cerqueira's avatar
Felipe Cerqueira committed
514 515 516 517
               H_valid_task_parameters into PARAMS,
               H_sequential_jobs into SEQ.
        move => t /andP [GEt LTt] BACK. 
        move: WORK  => WORK.
518
        specialize (WORK j t H_j_arrives BACK).
Felipe Cerqueira's avatar
Felipe Cerqueira committed
519 520 521 522 523 524 525 526 527 528 529 530 531
        rewrite -size_filter.
        apply leq_trans with (n := size (alpha' tsk));
          first by apply card_size.
        apply leq_trans with (n := size (pmap (fun cpu => sched cpu t) (enum (alpha' tsk)))).
        {
          rewrite size_pmap -size_filter.
          apply uniq_leq_size; first by destruct (alpha' tsk).
          intros cpu IN.
          rewrite mem_filter; apply/andP; split; last by rewrite mem_enum.
          feed (WORK cpu); first by apply SUB; rewrite ?FROMTS ?JOBtsk.
          by move: WORK => [j_other /eqP SCHED]; rewrite SCHED.
        }
        {
532
          apply leq_trans with (n := size (map (fun j => job_task j) (pmap (fun cpu => sched cpu t) (enum (alpha' tsk)))));
Felipe Cerqueira's avatar
Felipe Cerqueira committed
533 534 535 536 537 538 539
            first by rewrite size_map.
          apply uniq_leq_size.
          {
            rewrite map_inj_in_uniq.
            {
              apply pmap_inj_in_uniq; last by apply enum_uniq.
              intros cpu1 cpu2 IN1 IN2 SCHED2.
540
              destruct (sched cpu1 t) as [j0|] eqn:SCHED1; symmetry in SCHED2;
Felipe Cerqueira's avatar
Felipe Cerqueira committed
541 542 543 544 545 546 547 548 549
                first by apply SEQ with (j := j0) (t := t).
              rewrite 2!mem_enum in IN1 IN2.
              exploit (WORK cpu1); first by apply SUB; rewrite ?FROMTS ?JOBtsk.
              by move => [j_other SCHED]; rewrite /scheduled_on SCHED1 in SCHED.  
            }
            {
              intros j1 j2 SCHED1 SCHED2 SAMEtsk.
              rewrite 2!mem_pmap in SCHED1 SCHED2.
              move: SCHED1 SCHED2 => /mapP [cpu1 IN1 SCHED1] /mapP [cpu2 IN2 SCHED2].
550 551 552 553 554
              have ARR1: arrives_in arr_seq j1.
                by apply (FROMSEQ j1 t); apply/existsP; exists cpu1; apply/eqP. 
              have ARR2: arrives_in arr_seq j2.
                by apply (FROMSEQ j2 t); apply/existsP; exists cpu2; apply/eqP. 
              assert (PENDING1: pending job_arrival job_cost sched j1 t).
Felipe Cerqueira's avatar
Felipe Cerqueira committed
555 556 557 558
              {
                apply scheduled_implies_pending; try by done.
                by apply/existsP; exists cpu1; rewrite /scheduled_on -SCHED1.
              }
559
              assert (SCHED2': pending job_arrival job_cost sched j2 t).
Felipe Cerqueira's avatar
Felipe Cerqueira committed
560 561 562 563 564 565
              {
                apply scheduled_implies_pending; try by done.
                by apply/existsP; exists cpu2; rewrite /scheduled_on -SCHED2. 
              }
              apply platform_at_most_one_pending_job_of_each_task with (task_cost0 := task_cost)
              (task_period0 := task_period) (task_deadline0 := task_deadline) (tsk0 := tsk)
566 567 568 569
              (job_cost0 := job_cost) (job_task0 := job_task) (sched0 := sched) (j0 := j) (t0 := t)
              (job_arrival0 := job_arrival) (arr_seq0 := arr_seq);
                rewrite ?JOBtsk ?SAMEtsk //; first by apply PARAMS; rewrite -JOBtsk FROMTS.
              intros j0 tsk0 ARR0 TSK0 LE.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
570 571 572 573 574 575 576 577 578 579 580 581 582 583
              by apply (COMP t); rewrite ?TSK0.
            }
          }
          {
            move => tsk' /mapP [j' IN EQtsk'].
            rewrite mem_pmap in IN.
            move: IN => /mapP [cpu INcpu SCHED'].
            rewrite mem_enum in INcpu.
            rewrite mem_filter; apply/andP; split.
            {
              apply/existsP; exists cpu; apply/andP; split;
                 first by apply SUB; rewrite -?JOBtsk ?FROMTS ?JOBtsk.
              by rewrite /task_scheduled_on -SCHED' EQtsk'.
            }
584 585
            have ARR': arrives_in arr_seq j'.
              by apply (FROMSEQ j' t); apply/existsP; exists cpu; apply/eqP. 
Felipe Cerqueira's avatar
Felipe Cerqueira committed
586 587 588 589 590 591 592 593 594 595 596 597 598 599
            rewrite EQtsk' mem_filter; apply/andP; split; last by apply FROMTS.
            apply/andP; split; last first.
            {
              apply/existsP; exists cpu; apply/andP; split; first by done.
              by apply APA with (t := t); rewrite /scheduled_on SCHED'.
            }
            {
              apply/eqP; intro SAMEtsk.
              move: BACK => /andP [PENDING NOTSCHED].
              assert (SCHEDULED': scheduled sched j' t).
              {
                by apply/existsP; exists cpu; rewrite /scheduled_on -SCHED'.
              }
              move: (SCHEDULED') => PENDING'.
600 601
              apply scheduled_implies_pending with (job_cost0 := job_cost) (job_arrival0:=job_arrival)
                in PENDING'; try by done.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
602 603 604 605
              assert (BUG: j = j').
              {
                apply platform_at_most_one_pending_job_of_each_task with (task_cost0 := task_cost)
                (task_period0 := task_period) (task_deadline0 := task_deadline) (tsk0 := tsk)
606 607 608 609
                (job_cost0 := job_cost) (job_task0 := job_task) (sched0 := sched) (j0 := j) (t0 := t)
                (job_arrival0 := job_arrival) (arr_seq0 := arr_seq);
                  rewrite ?JOBtsk ?SAMEtsk //; first by apply PARAMS; rewrite -JOBtsk FROMTS.
                intros j0 tsk0 ARR0 TSK0 LE.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636
                by apply (COMP t); rewrite ?TSK0.
              }
              by rewrite BUG SCHEDULED' in NOTSCHED.
            }
          }
        }
      Qed.

      (* Before stating the next lemma, let (num_tasks_exceeding delta) be the
         number of interfering tasks that can execute on (alpha' tsk) whose
         interference x is larger than delta. *)
      Let num_tasks_exceeding delta := count (fun i => x i >= delta) (other_tasks_in alpha').

      (* 6) Now we prove that, for any delta, if (num_task_exceeding delta > 0), then the
            cumulative interference caused by the complementary set of interfering tasks fills
            the remaining, not-completely-full (#|alpha' tsk| - num_tasks_exceeding delta)
            processors. *)
      Lemma bertogna_edf_interference_in_non_full_processors :
        forall delta,
          0 < num_tasks_exceeding delta < #|alpha' tsk| ->
          \sum_(i <- other_tasks_in alpha' | x i < delta) x i >= delta * (#|alpha' tsk| - num_tasks_exceeding delta).
      Proof.
        have COMP := bertogna_edf_all_previous_jobs_complete_by_their_period.
        have ATMOST := platform_at_most_one_pending_job_of_each_task.
        have INV := bertogna_edf_alpha'_is_full.
        rename H_all_jobs_from_taskset into FROMTS,
               H_valid_task_parameters into PARAMS,
637
               H_job_of_tsk into JOBtsk, H_jobs_come_from_arrival_sequence into FROMSEQ,
Felipe Cerqueira's avatar
Felipe Cerqueira committed
638 639 640 641 642 643 644 645 646 647 648
               H_sporadic_tasks into SPO,
               H_tsk_R_in_rt_bounds into INbounds,
               H_all_previous_jobs_completed_on_time into BEFOREok,
               H_tasks_miss_no_deadlines into NOMISS,
               H_constrained_deadlines into RESTR,
               H_sequential_jobs into SEQ.
        unfold sporadic_task_model in *.
        move => delta /andP [HAS LT]. 
        rewrite -has_count in HAS.

        set some_interference_A := fun t =>
649
          has (fun tsk_k => backlogged job_arrival job_cost sched j t &&
Felipe Cerqueira's avatar
Felipe Cerqueira committed
650 651 652 653
                            (x tsk_k >= delta) &&
                            scheduled_on_alpha_tsk t tsk_k)
            (other_tasks_in alpha').
        set total_interference_B := fun t =>
654
            backlogged job_arrival job_cost sched j t *
Felipe Cerqueira's avatar
Felipe Cerqueira committed
655 656 657 658 659 660 661 662 663 664 665
            count (fun tsk_k => (x tsk_k < delta) &&
                  scheduled_on_alpha_tsk t tsk_k) (other_tasks_in alpha').

        apply leq_trans with ((\sum_(job_arrival j <= t < job_arrival j + R)
                              some_interference_A t) * (#|alpha' tsk| - num_tasks_exceeding delta)).
        {
          rewrite leq_mul2r; apply/orP; right.
          move: HAS => /hasP HAS; destruct HAS as [tsk_a INa LEa].
          apply leq_trans with (n := x tsk_a); first by apply LEa.
          unfold x, task_interference, some_interference_A.
          apply leq_sum_nat; move => t /andP [GEt LTt] _.
666
          destruct (backlogged job_arrival job_cost sched j t) eqn:BACK;
Felipe Cerqueira's avatar
Felipe Cerqueira committed
667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695
            last by rewrite (eq_bigr (fun x => 0)); [by simpl_sum_const | by ins].
          destruct ([exists cpu, can_execute_on alpha (job_task j) cpu &&
                              task_scheduled_on job_task sched tsk_a cpu t]) eqn:SCHED;
            last first.
          {
            apply negbT in SCHED; rewrite negb_exists in SCHED; move: SCHED => /forallP ALL.
            rewrite (eq_bigr (fun x => 0)); first by simpl_sum_const.
            by intros cpu _; specialize (ALL cpu); apply negbTE in ALL; rewrite ALL.
          }
          move: SCHED => /existsP [cpu /andP [CAN SCHED]].
          apply leq_trans with (n := 1); last first.
          {
            rewrite lt0b; apply/hasP; exists tsk_a; first by done.
            rewrite LEa 2!andTb; apply/existsP; exists cpu.
            by apply/andP; split; first by rewrite -JOBtsk.
          }
          rewrite (bigD1 cpu) /= // SCHED.
          rewrite (eq_bigr (fun x => 0)); first by simpl_sum_const; rewrite leq_b1.
          intros cpu' DIFF.
          apply/eqP; rewrite eqb0; apply/negP.
          move => /andP [ALPHA' SCHED'].
          move: DIFF => /negP DIFF; apply DIFF; apply/eqP.
          unfold task_scheduled_on in *.
          destruct (sched cpu t) as [j1|] eqn:SCHED1; last by done.
          destruct (sched cpu' t) as [j2|] eqn:SCHED2; last by done.
          move: SCHED SCHED' => /eqP JOB /eqP JOB'.
          subst tsk_a; symmetry in JOB'.
          assert (BUG: j1 = j2).
          {
696 697 698 699 700
            have ARR1: arrives_in arr_seq j1.
              by apply (FROMSEQ j1 t); apply/existsP; exists cpu; apply/eqP. 
            have ARR2: arrives_in arr_seq j2.
              by apply (FROMSEQ j2 t); apply/existsP; exists cpu'; apply/eqP. 
            assert (PENDING1: pending job_arrival job_cost sched j1 t).
Felipe Cerqueira's avatar
Felipe Cerqueira committed
701 702 703 704
            {
              apply scheduled_implies_pending; try by done.
              by apply/existsP; exists cpu; rewrite /scheduled_on -SCHED1.
            }
705
            assert (SCHED2': pending job_arrival job_cost sched j2 t).
Felipe Cerqueira's avatar
Felipe Cerqueira committed
706 707 708 709 710 711
            {
              apply scheduled_implies_pending; try by done.
              by apply/existsP; exists cpu'; rewrite /scheduled_on -SCHED2. 
            }
            apply platform_at_most_one_pending_job_of_each_task with (task_cost0 := task_cost)
              (task_period0 := task_period) (task_deadline0 := task_deadline) (tsk0 := tsk)
712 713 714 715
              (job_cost0 := job_cost) (job_task0 := job_task) (sched0 := sched) (j0 := j) (t0 := t)
              (job_arrival0 := job_arrival) (arr_seq0 := arr_seq);
              rewrite ?JOBtsk ?SAMEtsk //; first by apply PARAMS; rewrite -JOBtsk FROMTS.
            intros j0 tsk0 ARR0 TSK0 LE.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
716 717 718 719 720 721 722 723 724 725 726
            by apply (COMP t); rewrite ?TSK0.
          }
          by subst j2; apply SEQ with (j := j1) (t := t).
        }

        apply leq_trans with (\sum_(job_arrival j <= t < job_arrival j + R)
                                   total_interference_B t).
        {
          rewrite big_distrl /=.
          apply leq_sum_nat; move => t LEt _.
          unfold some_interference_A, total_interference_B. 
727
          destruct (backlogged job_arrival job_cost sched j t) eqn:BACK;
Felipe Cerqueira's avatar
Felipe Cerqueira committed
728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754
            [rewrite mul1n /= | by rewrite has_pred0 //].
          
          destruct (has (fun tsk_k : sporadic_task => (delta <= x tsk_k) &&
                     scheduled_on_alpha_tsk t tsk_k) (other_tasks_in alpha')) eqn:HAS';
            last by done.
          rewrite mul1n; move: HAS => /hasP [tsk_k INk LEk].
          unfold num_tasks_exceeding.
          apply leq_trans with (n := #|alpha' tsk| -
                       count (fun i => (x i >= delta) &&
                          scheduled_on_alpha_tsk t i) (other_tasks_in alpha')).
          {
            apply leq_sub2l.
            rewrite -2!sum1_count big_mkcond /=.
            rewrite [\sum_(_ <- _ | _ <= _)_]big_mkcond /=.
            apply leq_sum; intros i _.
            by destruct (scheduled_on_alpha_tsk t i);
              [by rewrite andbT | by rewrite andbF].
          }
          rewrite -count_filter -[count _ (other_tasks_in _)]count_filter.
          eapply leq_trans with (n := count (predC (fun tsk => delta <= x tsk)) _);
            last by apply eq_leq, eq_in_count; red; ins; rewrite ltnNge.
          rewrite leq_subLR count_predC size_filter.
          move: INV => INV. by apply (INV t).
        }
        {
          unfold x at 2, total_interference_B.
          rewrite exchange_big /=; apply leq_sum; intros t _.
755
          destruct (backlogged job_arrival job_cost sched j t) eqn:BACK; last by ins.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959
          rewrite mul1n -sum1_count.
          rewrite big_mkcond [\sum_(i <- other_tasks_in alpha' | _ < _) _]big_mkcond /=.
          apply leq_sum_seq; move => tsk_k IN _.
          destruct (x tsk_k < delta); [rewrite andTb | by rewrite andFb].
          destruct (scheduled_on_alpha_tsk t tsk_k) eqn:SCHED; last by done.
          move: SCHED => /existsP [cpu /andP [ALPHA SCHED]].
          rewrite (bigD1 cpu) /= // JOBtsk SCHED andbT.
          by rewrite /can_execute_on ALPHA.
        }
      Qed.

      (* 7) Based on lemma (6), we prove that, for any interval delta, if the sum of per-task
            interference exceeds (delta * |alpha' tsk|), the same applies for the
            sum of the minimum of the interference and delta. *)
      Lemma bertogna_edf_minimum_exceeds_interference :
        forall delta,
          \sum_(tsk_k <- other_tasks_in alpha') x tsk_k >= delta * #|alpha' tsk| ->
             \sum_(tsk_k <- other_tasks_in alpha') minn (x tsk_k) delta >=
             delta * #|alpha' tsk|.
      Proof.
        intros delta SUMLESS.
        set more_interf := fun tsk_k => x tsk_k >= delta.
        rewrite [\sum_(_ <- _) minn _ _](bigID more_interf) /=.
        unfold more_interf, minn.
        rewrite [\sum_(_ <- _ | delta <= _)_](eq_bigr (fun i => delta));
          last by intros i COND; rewrite leqNgt in COND; destruct (delta > x i).
        rewrite [\sum_(_ <- _ | ~~_)_](eq_big (fun i => x i < delta)
                                              (fun i => x i));
          [| by red; ins; rewrite ltnNge
           | by intros i COND; rewrite -ltnNge in COND; rewrite COND].

        (* Case 1: num_tasks_exceeding = 0 *)
        destruct (~~ has (fun i => delta <= x i) (other_tasks_in alpha')) eqn:HASa.
        {
          rewrite [\sum_(_ <- _ | _ <= _) _]big_hasC; last by apply HASa.
          rewrite big_seq_cond; move: HASa => /hasPn HASa.
          rewrite add0n (eq_bigl (fun i => (i \in other_tasks_in alpha') && true));
            last by red; intros tsk_k; destruct (tsk_k \in other_tasks_in alpha') eqn:INk;
              [by rewrite andTb ltnNge; apply HASa | by rewrite andFb].
          by rewrite -big_seq_cond.
        } apply negbFE in HASa.
        
        (* Case 2: num_tasks_exceeding >= #|alpha' tsk| *)
        destruct (num_tasks_exceeding delta >= #|alpha' tsk|) eqn:CARD.
        {
          apply leq_trans with (delta * num_tasks_exceeding delta);
            first by rewrite leq_mul2l; apply/orP; right.
          unfold num_tasks_exceeding; rewrite -sum1_count big_distrr /=.
          rewrite -[\sum_(_ <- _ | _) _]addn0.
          by apply leq_add; [by apply leq_sum; ins; rewrite muln1|by ins].
        } apply negbT in CARD; rewrite -ltnNge in CARD.

        (* Case 3: num_tasks_exceeding < #|alpha' tsk| *)
        rewrite big_const_seq iter_addn addn0; fold num_tasks_exceeding.
        apply leq_trans with (n := delta * num_tasks_exceeding delta +
                                   delta * (#|alpha' tsk| - num_tasks_exceeding delta));
          first by rewrite -mulnDr subnKC //; apply ltnW.
        rewrite leq_add2l bertogna_edf_interference_in_non_full_processors //.
        by apply/andP; split; [by rewrite -has_count | by done].
      Qed.

      (* 8) Note that lemma (7) only refers to interference within subaffinity (alpha' tsk).
            To reason about the interference incurred by job j in its complete affinity,
            we prove that an exceeding interference on affinity (alpha tsk) also
            implies an exceeding interference on the subaffinity (alpha' tsk). *)
      Lemma bertogna_edf_interference_on_subaffinity :
        forall delta,
          \sum_(tsk_k <- other_tasks_in alpha) x tsk_k >= delta * #|alpha tsk| ->
          \sum_(tsk_k <- other_tasks_in alpha') x tsk_k >= delta * #|alpha' tsk|.
      Proof.
        have ALL := bertogna_edf_all_cpus_in_affinity_busy.
        have SUB := bertogna_edf_all_cpus_in_subaffinity_busy.
        rename H_at_least_one_cpu into NONEMPTY',
               H_job_of_tsk into JOBtsk, H_affinity_subset into SUBSET,
               H_all_jobs_from_taskset into FROMTS.
        intros delta LE.
        rewrite ALL in LE.
        apply leq_trans with (n := X * #|alpha' tsk|); last by apply SUB.
        rewrite leq_mul2r in LE;  move: LE => /orP [/eqP EMPTY | LEx];
          last by rewrite leq_mul2r; apply/orP; right.
        assert (NONEMPTY: #|alpha tsk| > 0).
        {
          apply leq_trans with (n := #|alpha' tsk|);
            last by apply leq_subaffinity, SUBSET; rewrite -JOBtsk FROMTS.
          by apply NONEMPTY'; rewrite -JOBtsk FROMTS.
        }
        by rewrite EMPTY ltnn in NONEMPTY.
      Qed.
 
      (* 9) Next, using lemmas (0), (3), (7) and (8), we prove that the reduction-based
            interference bound is not enough to cover the sum of the minima over all tasks
            (artifact of the proof by contradiction). *)
      Lemma bertogna_edf_sum_exceeds_total_interference:
        \sum_((tsk_other, R_other) <- rt_bounds | other_task_in (alpha' tsk) tsk_other)
          minn (x tsk_other) (R - task_cost tsk + 1) > I tsk R.
      Proof.
        have GE_COST := bertogna_edf_R_other_ge_cost.
        have EXCEEDS := bertogna_edf_minimum_exceeds_interference.
        have SUB := bertogna_edf_interference_on_subaffinity.
        have ALLBUSY := bertogna_edf_all_cpus_in_affinity_busy.
        have TOOMUCH := bertogna_edf_too_much_interference.
        rename H_rt_bounds_contains_all_tasks into UNZIP,
               H_job_of_tsk into JOBtsk,
               H_all_jobs_from_taskset into FROMTS,
               H_response_time_is_fixed_point into REC.
        apply leq_trans with (n := \sum_(tsk_other <- other_tasks_in alpha')
                                     minn (x tsk_other) (R - task_cost tsk + 1));
          last first.
        {
          rewrite (eq_bigr (fun i => minn (x (fst i)) (R - task_cost tsk + 1)));
            last by ins; destruct i.
          assert (FILTER: filter (other_task_in (alpha' tsk)) (unzip1 rt_bounds) =
                          filter (other_task_in (alpha' tsk)) ts).
            by f_equal.
          unfold other_tasks_in; rewrite -FILTER; clear FILTER.
          rewrite -[\sum_(_ <- rt_bounds | _)_]big_filter.
          assert (SUBST: [seq i <- rt_bounds
                 | let '(tsk_other, _) := i in
                   other_task_in (alpha' tsk) tsk_other] =
                         [seq i <- rt_bounds
                           | other_task_in (alpha' tsk) (fst i)]).
          {
            by apply eq_filter; red; intro i; destruct i.
          } rewrite SUBST; clear SUBST.         
          have MAP := big_map (fun x => fst x) (fun i => true)
                              (fun i => minn (x i) (R - task_cost tsk + 1)).
          by rewrite -MAP; apply eq_leq; f_equal; rewrite filter_map.
        }
        
        apply ltn_div_trunc with (d := #|alpha' tsk|);
          first by apply H_at_least_one_cpu; rewrite -JOBtsk FROMTS.
        rewrite -(ltn_add2l (task_cost tsk)) -REC; last first. by done.
        rewrite -addn1 -leq_subLR.
        rewrite -[R + 1 - _]subh1; last by apply GE_COST.
        rewrite leq_divRL;
          last by apply H_at_least_one_cpu; rewrite -JOBtsk FROMTS.
        apply EXCEEDS, SUB.
        apply leq_trans with (n := X * #|alpha tsk|); last by rewrite ALLBUSY.
        by rewrite leq_mul2r; apply/orP; right; apply TOOMUCH.
      Qed.

      (* 10) After concluding that the sum of the minima exceeds (R - e_i + 1),
            we prove that there exists a tuple (tsk_k, R_k) that satisfies
            min (x_k, R - e_i + 1) > min (W_k, I_edf, R - e_i + 1).
            This implies that either x_k > W_k or x_k > I_edf, which is a contradiction,
            since both W_k and I_edf are valid task interference bounds. *)
      Lemma bertogna_edf_exists_task_that_exceeds_bound :
        exists tsk_other R_other,
          (tsk_other, R_other) \in rt_bounds /\
          (minn (x tsk_other) (R - task_cost tsk + 1) > interference_bound tsk_other R_other).
      Proof.
        have SUM := bertogna_edf_sum_exceeds_total_interference.
        have BOUND := bertogna_edf_workload_bounds_interference.
        have EDFBOUND := bertogna_edf_specific_bound_holds.
        rename H_rt_bounds_contains_all_tasks into UNZIP.
        assert (HAS: has (fun tup : task_with_response_time =>
                            let (tsk_other, R_other) := tup in
                (tsk_other \in ts) && other_task_in (alpha' tsk) tsk_other &&
                (minn (x tsk_other) (R - task_cost tsk + 1)  > interference_bound tsk_other R_other))
                         rt_bounds).
        {
          apply/negP; unfold not; intro NOTHAS.
          move: NOTHAS => /negP /hasPn ALL.
          rewrite -[_ < _]negbK in SUM.
          move: SUM => /negP SUM; apply SUM; rewrite -leqNgt.
          unfold I, total_interference_bound_edf.
          rewrite big_seq_cond [\sum_(_ <- _ | let _ := _ in _)_]big_seq_cond.
          apply leq_sum; move => tsk_k /andP [INBOUNDSk INTERFk]; destruct tsk_k as [tsk_k R_k].
          specialize (ALL (tsk_k, R_k) INBOUNDSk).
          unfold interference_bound_edf; simpl in *.
          rewrite leq_min; apply/andP; split.
          {
            unfold interference_bound; rewrite leq_min; apply/andP; split;
              last by rewrite geq_minr.
            by apply leq_trans with (n := x tsk_k);
              [by rewrite geq_minl | by apply BOUND].
          }
          {
            apply leq_trans with (n := x tsk_k);
              [by rewrite geq_minl | by apply EDFBOUND].
          }
        }
        move: HAS => /hasP HAS; destruct HAS as [[tsk_k R_k] HPk MIN].
        move: MIN => /andP [/andP [INts INTERFk] MINk].
        by exists tsk_k, R_k; repeat split.
      Qed.

      End DerivingContradiction.
      
    End Lemmas.

    (* Using the lemmas above, we now prove that any response-time bound
       obtained from the analysis is safe. *)
    Section MainProof.
      
      (* Let (tsk, R) be any task to be analyzed, with its response-time bound R. *)
      Variable tsk: sporadic_task.
      Variable R: time.
      Hypothesis H_tsk_R_in_rt_bounds: (tsk, R) \in rt_bounds.

      (* Then, R bounds the response-time of tsk. *)
      Theorem bertogna_cirinei_response_time_bound_edf :
        response_time_bounded_by tsk R.
      Proof.
960
        intros j ARRj JOBtsk.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
961 962 963 964 965 966 967 968 969 970
       
        (* First, rewrite the claim in terms of the *absolute* response-time bound (arrival + R) *)
        remember (job_arrival j + R) as ctime.

        revert H_tsk_R_in_rt_bounds.
        generalize dependent R; generalize dependent tsk; generalize dependent j.
      
        (* Now, we apply strong induction on the absolute response-time bound. *)
        induction ctime as [ctime IH] using strong_ind.

971
        intros j ARRj tsk' JOBtsk R' EQc INbounds; subst ctime.
Felipe Cerqueira's avatar
Felipe Cerqueira committed
972 973

        (* First, let's simplify the induction hypothesis. *)
974 975 976 977 978 979
        assert (BEFOREok: forall j0 tsk R0,
                            arrives_in arr_seq j0 ->
                            job_task j0 = tsk ->
                            (tsk, R0) \in rt_bounds ->
                            job_arrival j0 + R0 < job_arrival j + R' ->
                            service sched j0 (job_arrival j0 + R0) == job_cost j0).
Felipe Cerqueira's avatar
Felipe Cerqueira committed
980 981 982 983 984 985 986 987 988 989 990 991 992
        {
            by ins; apply IH with (tsk := tsk0) (R := R0).
        }
        clear IH.
        
        (* The proof follows by contradiction. Assume that job j does not complete by its
           response-time bound. By the induction hypothesis, all jobs with absolute
           response-time bound t < (job_arrival j + R) have correct response-time bounds. *)
        destruct (completed job_cost sched j (job_arrival j + R')) eqn:NOTCOMP;
          first by done.
        apply negbT in NOTCOMP; exfalso.
        
        (* Next, we derive a contradiction using the previous lemmas. *)
993
        exploit (bertogna_edf_exists_task_that_exceeds_bound tsk' R' INbounds j ARRj JOBtsk NOTCOMP).
Felipe Cerqueira's avatar
Felipe Cerqueira committed
994 995 996 997 998 999 1000
        {
          by ins; apply IH with (tsk := tsk_other) (R := R_other).
        } 
        intro EX; destruct EX as [tsk_other [R_other [HP LTmin]]].
        unfold interference_bound_edf, interference_bound_generic in LTmin.
        rewrite minnAC in LTmin; apply min_lt_same in LTmin.
        have BASICBOUND := bertogna_edf_workload_bounds_interference R' j BEFOREok tsk_other R_other HP.
1001
        have EDFBOUND := (bertogna_edf_specific_bound_holds tsk' R' INbounds j ARRj JOBtsk BEFOREok tsk_other R_other HP).
Felipe Cerqueira's avatar
Felipe Cerqueira committed
1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015
        unfold minn in LTmin; clear -LTmin HP BASICBOUND EDFBOUND tsk; desf.
        {
          by apply (leq_ltn_trans BASICBOUND) in LTmin; rewrite ltnn in LTmin. 
        }
        {
          by apply (leq_ltn_trans EDFBOUND) in LTmin; rewrite ltnn in LTmin.
        }
      Qed.

    End MainProof.
    
  End ResponseTimeBound.

End ResponseTimeAnalysisEDF.