Skip to content
Snippets Groups Projects

cumulative_hep_interference split

Closed Kimaya Bedarkar requested to merge kbedarka/rt-proofs:hep_intf_split into master
  • Move some general definitions and lemmas about interference to the new introduced analysis.facts.interference
  • Generalize one lemma in ideal_jlfp_rta that relates cumulative interference to service. Previously there were two lemmas that proved slightly different statements and had mostly similar proof scripts.
  • Add lemma proving cumulative interference from higher-or-equal priority jobs as equivalent to the sum of cumulative interference from strictly higher and equal priority jobs
  • Stating the above lemma requires definitions of another_task_hp_job and another_task_ep_job
Edited by Kimaya Bedarkar

Merge request reports

Loading
Loading

Activity

Filter activity
  • Approvals
  • Assignees & reviewers
  • Comments (from bots)
  • Comments (from users)
  • Commits & branches
  • Edits
  • Labels
  • Lock status
  • Mentions
  • Merge request status
  • Tracking
  • 243 244 rewrite (eq_big (fun j=> pred_task (job_task j)) job_cost) //;
    244 245 last by move=> j'; rewrite /pred_task; move: TSK => /eqP ->.
    245 246 erewrite (eq_big pred_task); [|by done|by move=> tsk'; eauto].
    246 by apply: sum_of_jobs_le_sum_rbf; eauto. } }
    247 by apply: sum_of_jobs_le_sum_rbf; eauto. }
    248 by unfold quiet_time; move: BUSY => [[_ [T1 T2]] _].
  • 195 164 (** ... and assume that the schedule is idle at [t]. *)
    196 165 Hypothesis H_idle : is_idle sched t.
    197 166
    198 (** We prove that in this case: ... *)
    199
    200 (** ... interference from higher-or-equal priority jobs from
    201 another task is equal to [false], ... *)
    202 Lemma idle_implies_no_hep_task_interference :
    203 forall j, is_interference_from_hep_job_from_another_task j t = false.
    204 Proof.
    205 intros j.
    206 unfold is_interference_from_hep_job_from_another_task.
    207 by move: (H_idle) => /eqP ->.
    208 Qed.
    209
    167 (* can be potentially moved, if [task_interference_received_before] is moved *)
  • Björn Brandenburg
  • Björn Brandenburg
  • 690 464 erewrite service_of_jobs_case_on_pred with (P2 := fun j' => j' != j); rt_eauto.
    691 465 erewrite workload_of_jobs_case_on_pred with (P' := fun j' => j' != j); rt_eauto.
    692 466 replace ((fun j0 : Job => hep_job j0 j && (j0 != j))) with (another_hep_job^~j); last by rewrite /another_hep_job.
    693 rewrite -/(service_of_other_hep_jobs j 0 t) -cumulative_i_ohep_eq_service_of_ohep; eauto.
    467 rewrite /service_of_jobs.
    468 rewrite -cumulative_pred_eq_service; rt_eauto.
    469 replace (\sum_(j0 <- arrivals_between arr_seq 0 t | hep_job j0 j && ~~ (j0 != j))
    470 service_during sched j0 0 t) with ( service_of_jobs sched (fun j0 : Job => hep_job j0 j && ~~ (j0 != j))
    471 (arrivals_between arr_seq 0 t) 0 t).
  • Björn Brandenburg
  • 23
    24 (** ... where jobs do not execute before their arrival nor after completion. *)
    25 Hypothesis H_jobs_must_arrive_to_execute : jobs_must_arrive_to_execute sched.
    26 Hypothesis H_completed_jobs_dont_execute : completed_jobs_dont_execute sched.
    27
    28 (** Consider a JLFP-policy that indicates a higher-or-equal priority relation,
    29 and assume that this relation is reflexive and transitive. *)
    30 Context `{JLFP_policy Job}.
    31 Hypothesis H_priority_is_reflexive : reflexive_priorities.
    32 Hypothesis H_priority_is_transitive : transitive_priorities.
    33
    34 (** Next, we say that job [j] is incurring interference from another
    35 job with higher or equal priority at time [t], if there exists a
    36 job [jhp] (different from [j]) with higher or equal priority
    37 that executes at time [t]. *)
    38 Definition is_interference_from_another_hep_job (j : Job) (t : instant) :=
    • The naming throughout this file is a bit cumbersome, and the identifier are getting ever longer. is_interference_from_another_hep_job would more naturally be called another_hep_job_interferes or, slightly more verbose but consistent with scheduled_at, another_hep_job_interferes_at.

      Generally, let's try to avoid "nounifcation" of verbs when naming predicates.

    • Please register or sign in to reply
  • Loading
  • Loading
  • Loading
  • Loading
  • Loading
  • Loading
  • Loading
  • Loading
  • Loading
  • Loading
  • Please register or sign in to reply
    Loading