with Text_IO; use Text_IO; with Translate; use Translate; with unbounded_strings; use unbounded_strings; with Scheduler; use Scheduler; with Scheduling_Analysis; use Scheduling_Analysis; use Scheduling_Analysis.Double_Tasks_Parameters_Package; with Tasks; use Tasks; use Tasks.Generic_Task_List_Package; with Task_Set; use Task_Set; package body Feasibility_Test.Wort_Case_Response_Time is -- Compute the significant S for a i-j task pair -- function Audsley_Compute_S (Current_Group : in Generic_Task_Group_Ptr; Taski : in Generic_Task_Ptr; Taskj : in Generic_Task_Ptr; Q : in Natural ) return Double is S, kj, Tj, Oj, Jj, Oi, Ji : Double; begin Tj := Double (Transaction_Task_Group_Ptr (Current_Group).period); Oj := Double (Taskj.offsets.Entries(0).offset_value); Jj := Double (Periodic_Task_Ptr (Taskj).jitter); Oi := Double (Taski.offsets.Entries(0).offset_value); Ji := Double (Periodic_Task_Ptr (Taski).jitter); kj := Double'Ceiling((Jj + Oj - Oi - Ji) / Tj); S := (Double(Q) + kj) * Tj - Oj - Jj + Oi + Ji; return S; end; function Audsley_Compute_WiS_preemptive --Audsley's tasks are premptive (My_Task_Groups: in Task_Groups_Set; --all the task Current_Group : in Generic_Task_Group_Ptr; Current_Task : in Generic_Task_Ptr; --the task examine S : in Double) return Double is Iterator_Taskj, Iterator_Taskk : Generic_Task_Iterator; Iterator_Group : Task_Groups_Iterator; Taskj, Taskk : Generic_Task_Ptr; Transt : Generic_Task_Group_Ptr; WiS, Ci, Bi, ai, Ij, Ht, Max_WiS, Wt, Oi, Ji: Double; Oj, Jj, Tj, Cj, aj, Ok, Jk, Ck, Tk, Tmp_WiS : Double; begin Ci := Double(Current_Task.capacity); Bi := Double(Current_Task.blocking_time); ai := Double'Floor(S / Double(Transaction_Task_Group_Ptr (Current_Group).period)); Oi := Double(Current_Task.offsets.Entries(0).offset_value); Ji := Double(Periodic_Task_Ptr (Current_Task).jitter); WiS := Ci + ai * Ci + Bi; --put(" Initial WiS: "); --put(Double'Image(WiS)); --Compute Sum Ij -- reset_head_iterator(Current_Group.task_list, Iterator_Taskj); loop -- Selection of the task j -- current_element (Current_Group.task_list, Taskj, Iterator_Taskj); -- Only process task with higher priority -- if (Taskj.priority <= Current_Task.priority and Taskj /= Current_Task) then Oj := Double (Taskj.offsets.Entries(0).offset_value); Jj := Double (Periodic_Task_Ptr (Taskj).jitter); Tj := Double (Transaction_Task_Group_Ptr (Current_Group).period); Cj := Double (Taskj.capacity); aj := Double'Floor ((S - Oi - Ji + Oj + Jj) / Tj); Ij := Double'Ceiling ((WiS - S + Oi - Oj + Ji + aj * Tj) / Tj) * Cj; --put(" Taskj "); --put(Natural'Image(Natural(Taskj.priority))); --put(" aj "); --put(Double'Image(aj)); --put(" Ij "); --put(Double'Image(Ij)); WiS := WiS + Ij; end if; exit when is_tail_element(Current_Group.task_list, Iterator_Taskj); next_element (Current_Group.task_list, Iterator_Taskj); end loop; -- Compute Sum Ht -- Max_WiS := 0.0; reset_iterator(My_Task_Groups, Iterator_Group); loop -- Selection of a task group -- current_element(My_Task_Groups, Transt, Iterator_Group); -- Don't process the group task i belong to -- It is already taken care of with Ij if (Transt /= Current_Group) then reset_head_iterator(Transt.task_list, Iterator_Taskj); Ht := 0.0; Tmp_WiS := WiS; Max_WiS := WiS; --put_line(""); --put("Ht group "); --put(Natural'Image(Natural(Transaction_Task_Group_Ptr(Transt).period))); loop -- Selection of task j -- current_element(Transt.task_list, Taskj, Iterator_Taskj); -- Only process tasks with higher priority -- if (Taskj.priority <= Current_Task.priority and Taskj /= Current_Task) then Oj := Double (Taskj.offsets.Entries(0).offset_value); Jj := Double (Periodic_Task_Ptr (Taskj).jitter); Wt := Oj + Jj; --put_line(""); --put("Taskj "); --put(Natural'Image(Natural(Taskj.priority))); reset_head_iterator(Transt.task_list, Iterator_Taskk); loop -- Selection of task k -- current_element(Transt.task_list, Taskk, Iterator_Taskk); Ok := Double(Taskk.offsets.Entries(0).offset_value); Jk := Double(Periodic_Task_Ptr (Taskk).jitter); Ck := Double(Taskk.capacity); Tk := Double(Transaction_Task_Group_Ptr (Transt).period); --put("Taskk "); --put(Natural'Image(Natural(Taskk.priority))); if (Ok + Jk >= Wt) then --put(" ht1 "); Ht := Double'Ceiling((Tmp_WiS + Wt - Ok) / Tk) * Ck; else --put(" ht2 "); Ht := Double'Ceiling((Tmp_WiS + Wt - Ok - Tk) / Tk) * Ck; end if; Tmp_WiS := Tmp_WiS + Ht; --put("Tmp_WiS "); --put(Double'Image(Tmp_WiS)); exit when is_tail_element(Transt.task_list, Iterator_Taskk); next_element(Transt.task_list, Iterator_Taskk); end loop; if (Tmp_WiS > Max_WiS) then Max_WiS := Tmp_WiS; end if; end if; exit when is_tail_element(Transt.task_list, Iterator_Taskj); next_element(Transt.task_list, Iterator_Taskj); end loop; WiS := Max_WiS; --put("Final WiS "); --put(Double'Image(Max_WiS)); end if; exit when is_last_element(My_Task_Groups, Iterator_Group); next_element(My_Task_Groups, Iterator_Group); end loop; return WiS; end Audsley_Compute_WiS_preemptive; procedure Audsley_Compute_Offset_Response_Time (My_Task_Groups : in Task_Groups_Set; Processor_Name : in Unbounded_String; Msg : in out Unbounded_String; Response_Time : out Response_Time_Table) is Tmp : Generic_Task_Group; Iterator_Group : Task_Groups_Iterator; Groupi : Generic_Task_Group_Ptr; Iterator_Taski, Iterator_Taskj : Generic_Task_Iterator; Taski, Taskj : Generic_Task_Ptr; I : Response_Time_Range := 0; Ri, WiS, S, Ji, Ti : Double := 0.0; Q : Integer; Q_stop : Boolean := false; begin initialize (Response_Time); Current_Processor_Name := Processor_Name; -- Set priority according to the scheduler -- But there is no scheduler (bottom-up)? Assume the tasks already have -- priority assigned to it reset_iterator (My_Task_Groups, Iterator_Group); loop current_element (My_Task_Groups, Groupi, Iterator_Group); sort(Groupi.task_list, Decreasing_Priority'Access); exit when is_last_element (My_Task_Groups, Iterator_Group); next_element (My_Task_Groups, Iterator_Group); end loop; -- Bibliographical references -- Nothing for now -- compute response time for each tasks -- reset_iterator (My_Task_Groups, Iterator_Group); loop -- Selection of the current group -- current_element (My_Task_Groups, Groupi, Iterator_Group); reset_head_iterator (Groupi.task_list, Iterator_Taski); loop -- Selection of the current task (i) -- current_element (Groupi.task_list, Taski, Iterator_Taski); -- Initialize response time for task i -- Response_Time.entries (I).data := 0.0; Response_Time.entries (I).item := Taski; Response_Time.nb_entries := Response_Time.nb_entries + 1; -- Ji := Double (Periodic_Task_Ptr (Taski).jitter); Ti := Double (Transaction_Task_Group_Ptr (Groupi).period); --put_line(""); --put_line(""); --put("Task i: "); --put_line(Natural'Image(Natural(Taski.priority))); -- Find the maximum for Ri in [0..Q] -- Q := 0; loop Q_stop := true; --put("Q: "); --put_line(Natural'Image(Q)); -- Calculate the significant S -- reset_head_iterator(Groupi.task_list, Iterator_Taskj); loop -- Selection of task j -- current_element(Groupi.task_list, Taskj, Iterator_Taskj); -- only process tasks with higher priority if (Taskj.priority <= Taski.priority) then -- Compute response time -- S := Audsley_Compute_S(Groupi, Taski, Taskj, Q); --put_line(""); --put("Task "); --put(Natural'Image(Natural(Taskj.priority))); --put(" Significant S: "); --put(Double'Image(S)); WiS := Audsley_Compute_WiS_preemptive(My_Task_Groups, Groupi, Taski, S); Ri := WiS + Ji - S; --put(" WiS: "); --put(Double'Image(WiS)); --put(" Ri: "); --put_line(Double'Image(Ri)); if (Ri > Response_Time.entries(I).data) then Response_Time.entries(I).data := Ri; end if; if (Ri > Ti) then Q_stop := false; end if; end if; exit when is_tail_element(Groupi.task_list, Iterator_Taskj); next_element(Groupi.task_list, Iterator_Taskj); end loop; exit when Q_stop; Q := Q + 1; end loop; I := I + 1; exit when is_tail_element (Groupi.task_list, Iterator_Taski); next_element (Groupi.task_list, Iterator_Taski); end loop; exit when is_last_element (My_Task_Groups, Iterator_Group); next_element (My_Task_Groups, Iterator_Group); end loop; end Audsley_Compute_Offset_Response_Time; function Tindell_Compute_Viti (Groupi : in Generic_Task_Group_Ptr; Taski : in Generic_Task_Ptr; Taskj : in Generic_Task_Ptr) return Double is Oi, Oj, Ji, Jj, Tti, Viti : Double := 0.0; begin Tti := Double (Transaction_Task_Group_Ptr (Groupi).period); Oi := Double (Taski.offsets.Entries(0).offset_value); Ji := Double (Periodic_Task_Ptr(Taski).jitter); Oj := Double (Taskj.offsets.Entries(0).offset_value); Jj := Double (Periodic_Task_Ptr(Taskj).jitter); Viti := Double'Ceiling((Oj + Jj - Oi - Ji)/Tti); return Viti; end Tindell_Compute_Viti; function Tindell_Compute_Wiq_preemptive (My_Task_Groups : in Task_Groups_Set; Groupi : in Generic_Task_Group_Ptr; Taski : in Generic_Task_Ptr) return Double is Wiq : Double := 0.0; begin return Wiq; end Tindell_Compute_Wiq_preemptive; procedure Tindell_Compute_Offset_Response_Time --tractable (My_Task_Groups : in Task_Groups_Set; Processor_Name : in Unbounded_String; Msg : in out Unbounded_String; Response_Time : out Response_Time_Table) is Tmp : Generic_Task_Group; Iterator_Group : Task_Groups_Iterator; Groupi : Generic_Task_Group_Ptr; Iterator_Taski, Iterator_Taskj : Generic_Task_Iterator; Taski, Taskj : Generic_Task_Ptr; I : Response_Time_Range := 0; Ri, Wiq, Viti, Ji, Tti, Oi, Oj, Jj, Ei : Double := 0.0; Q : Integer; Q_stop : Boolean := false; begin initialize (Response_Time); Current_Processor_Name := Processor_Name; -- Set priority according to the scheduler -- But there is no scheduler (bottom-up)? Assume the tasks already have -- priority assigned to it reset_iterator (My_Task_Groups, Iterator_Group); loop current_element (My_Task_Groups, Groupi, Iterator_Group); sort(Groupi.task_list, Decreasing_Priority'Access); exit when is_last_element (My_Task_Groups, Iterator_Group); next_element (My_Task_Groups, Iterator_Group); end loop; -- Bibliographical references -- Nothing for now -- compute response time for each tasks -- reset_iterator (My_Task_Groups, Iterator_Group); loop -- Selection of the current group -- current_element (My_Task_Groups, Groupi, Iterator_Group); reset_head_iterator (Groupi.task_list, Iterator_Taski); loop -- Selection of the current task (i) -- current_element (Groupi.task_list, Taski, Iterator_Taski); -- Initialize response time for task i -- Response_Time.entries (I).data := 0.0; Response_Time.entries (I).item := Taski; Response_Time.nb_entries := Response_Time.nb_entries + 1; -- Ji := Double (Periodic_Task_Ptr (Taski).jitter); Oi := Double (Taski.offsets.Entries(0).offset_value); --Task model need to be amended to support property e (every) Ei := 1.0; Tti := Double (Transaction_Task_Group_Ptr (Groupi).period); --put_line(""); --put_line(""); --put("Task i: "); --put_line(Natural'Image(Natural(Taski.priority))); -- Tractable analysis: find the maximum for Ri in [0..Q] -- Q := 0; loop Q_stop := true; --put("Q: "); --put_line(Natural'Image(Q)); reset_head_iterator(Groupi.task_list, Iterator_Taskj); loop -- Selection of task j -- current_element(Groupi.task_list, Taskj, Iterator_Taskj); -- Compute response time -- Viti := Tindell_Compute_Viti(Groupi, Taski, Taskj); --put_line(""); --put("Task "); --put(Natural'Image(Natural(Taskj.priority))); --put(" Viti: "); --put(Double'Image(Viti)); Wiq := Tindell_Compute_Wiq_preemptive(My_Task_Groups, Groupi, Taski); Ri := Wiq + Oj + Ji - Tti * (Double(Q) * Ei + Viti) - Oi; --put(" Wiq: "); --put(Double'Image(Wiq)); --put(" Ri: "); --put_line(Double'Image(Ri)); if (Ri > Response_Time.entries(I).data) then Response_Time.entries(I).data := Ri; end if; -- see equation (20) - stop condition if (Ri > Tti * Ei + Ji) then Q_stop := false; end if; exit when is_tail_element(Groupi.task_list, Iterator_Taskj); next_element(Groupi.task_list, Iterator_Taskj); end loop; exit when Q_stop; Q := Q + 1; end loop; I := I + 1; exit when is_tail_element (Groupi.task_list, Iterator_Taski); next_element (Groupi.task_list, Iterator_Taski); end loop; exit when is_last_element (My_Task_Groups, Iterator_Group); next_element (My_Task_Groups, Iterator_Group); end loop; end Tindell_Compute_Offset_Response_Time; end Feasibility_Test.Wort_Case_Response_Time;