------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- Cheddar is a GNU GPL real-time scheduling analysis tool. -- This program provides services to automatically check schedulability and -- other performance criteria of real-time architecture models. -- -- Copyright (C) 2002-2016, Frank Singhoff, Alain Plantec, Jerome Legrand -- -- The Cheddar project was started in 2002 by -- Frank Singhoff, Lab-STICC UMR 6285 laboratory, Université de Bretagne Occidentale -- -- Cheddar has been published in the "Agence de Protection des Programmes/France" in 2008. -- Since 2008, Ellidiss technologies also contributes to the development of -- Cheddar and provides industrial support. -- -- The full list of contributors and sponsors can be found in AUTHORS.txt and SPONSORS.txt -- -- This program is free software; you can redistribute it and/or modify -- it under the terms of the GNU General Public License as published by -- the Free Software Foundation; either version 2 of the License, or -- (at your option) any later version. -- -- This program is distributed in the hope that it will be useful, -- but WITHOUT ANY WARRANTY; without even the implied warranty of -- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -- GNU General Public License for more details. -- -- You should have received a copy of the GNU General Public License -- along with this program; if not, write to the Free Software -- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA -- -- -- Contact : cheddar@listes.univ-brest.fr -- ------------------------------------------------------------------------------ -- Last update : -- $Rev: 1249 $ -- $Date: 2014-08-28 07:02:15 +0200 (Fri, 28 Aug 2014) $ -- $Author: singhoff $ ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ with Translate; use Translate; with Buffer_Set; use Buffer_Set; use Buffer_Set.Generic_Buffer_Set; with Resources; use Resources; with Resource_Set; use Resource_Set; use Resource_Set.Generic_Resource_Set; with natural_util; use natural_util; with tasks.extended; use tasks.extended; with Task_Set; use Task_Set; use Task_Set.Generic_Task_Set; with Time_Unit_Events; use Time_Unit_Events; use Time_Unit_Events.Time_Unit_Lists_Package; use Time_Unit_Events.Time_Unit_Package; with Event_Analyzer_Set; use Event_Analyzer_Set; use Event_Analyzer_Set.Generic_Event_Analyzer_Set; with natural_util; use natural_util; with tables; with indexed_tables; with Unchecked_Deallocation; with Translate; use Translate; with natural_util; use natural_util; package body Scheduling_Analysis.extended.task_analysis is procedure Consumer_Response_Time (Sched : in Scheduling_Sequence_Ptr; Consumer_Resp_Time : in out Resp_Time_Consumer_Table_Ptr; My_Consumer_Task : in Generic_Task_Ptr) is My_Consumer_Task_Occurence_Table : Task_Occurence_Table_Ptr; Index : Resp_Time_Consumer_Range := 0; begin -- initialize and compute all response times -- My_Consumer_Task_Occurence_Table := new Task_Occurence_Table; All_Response_Times_By_Simulation (My_Consumer_Task, Sched, My_Consumer_Task_Occurence_Table); -- affect response time value -- for I_Occurence in Task_Occurence_Range loop if (My_Consumer_Task_Occurence_Table.entries (I_Occurence). Response_Time /= 0) then Consumer_Resp_Time.entries (Index).data := Double ( My_Consumer_Task_Occurence_Table.entries (I_Occurence). Response_Time); Index := Index + 1; end if; end loop; Consumer_Resp_Time.nb_entries := Index; Free (My_Consumer_Task_Occurence_Table); end Consumer_Response_Time; procedure Cyclic_Response_Time_By_Simulation (My_Task : in Generic_Task_Ptr; Sched : in Scheduling_Sequence_Ptr; Msg : in out Unbounded_String; Max : in out Natural; Min : in out Natural; Average : in out Double) is Current_Date : Natural := 0; My_Task_Occurence_Table : Task_Occurence_Table_Ptr; Task_Occurence_Number : Task_Occurence_Range; begin -- initialize all occurences -- dates are taken from scheduling table -- My_Task_Occurence_Table := new Task_Occurence_Table; Min := Natural'Last; Max := Natural'First; Average := 0.0; Msg := empty_string; -- Initialize activation time of the task -- Task_Occurence_Number:=0; for J in 0 .. Sched.nb_entries - 1 loop if Sched.entries (J).data.type_of_event = Task_activation then if Sched.entries (J).data.activation_task.name = My_Task.name then Initialize (My_Task_Occurence_Table.entries (Task_Occurence_Number), My_Task, Sched.entries (J).item); Task_Occurence_Number := Task_Occurence_Number + 1; end if; end if; end loop; -- Find completion time of task -- compute response time -- Task_Occurence_Number:=0; for T in 0 .. Sched.nb_entries - 1 loop -- the current date -- Current_Date := Sched.entries (T).item; if Sched.entries (T).data.type_of_event = End_Of_Task_Capacity then if Sched.entries (t).data.end_task.name = My_Task.name then My_Task_Occurence_Table.entries (Task_Occurence_Number).completion_Time := current_date; My_Task_Occurence_Table.entries (Task_Occurence_Number).Response_Time := current_date - My_Task_Occurence_Table.entries (Task_Occurence_Number).arrival_time; -- Check deadline missed and update its message -- if (My_Task_Occurence_Table.entries ( Task_Occurence_Number).Response_Time > My_Task.deadline) then Msg := Msg & Lb_Comma & Lb_Check_absolute_Deadline (Current_Language) & My_Task_Occurence_Table.entries ( task_occurence_number).Absolute_Deadline'Img & Lb_Completion_Time (Current_Language) & My_Task_Occurence_Table.entries (task_occurence_number).completion_Time'img & To_Unbounded_String (")"); end if; Task_Occurence_Number:=Task_Occurence_Number+1; -- JLE correction for ticket 146 http://beru.univ-brest.fr/WIKI-CHEDDAR/ticket/146 My_Task_Occurence_Table.nb_entries := My_Task_Occurence_Table.nb_entries + 1; end if; end if; end loop; -- Compute min/max/average -- for T in 0 .. my_task_occurence_table.nb_entries - 1 loop if (My_Task_Occurence_Table.entries ( t).Response_Time < Min) then Min := My_Task_Occurence_Table.entries ( t).Response_Time; end if; if (My_Task_Occurence_Table.entries ( t).Response_Time > Max) then Max := My_Task_Occurence_Table.entries ( t).Response_Time; end if; Average := Average + Double ( My_Task_Occurence_Table.entries ( t).Response_Time); end loop; if my_task_occurence_table.nb_entries > 0 then Average := Average / Double (my_task_occurence_table.nb_entries); end if; if Min = Natural'Last then Min := 0; end if; Free (My_Task_Occurence_Table); end Cyclic_Response_Time_By_Simulation; procedure Acyclic_Response_Time_By_Simulation (My_Task : in Aperiodic_Task_Ptr; Sched : in Scheduling_Sequence_Ptr; Msg : in out Unbounded_String; Max : in out Natural; Min : in out Natural; Average : in out Double) is My_Task_Occurence : Task_Occurence; Effective_End : Natural := 0; Current_Date : Natural := 0; begin Initialize (My_Task_Occurence, generic_task_ptr(My_Task)); Msg := To_Unbounded_String (""); for T in 0 .. Sched.nb_entries - 1 loop -- the current date -- Current_Date := Sched.entries (T).item; -- Look for task completion and task starting time -- case Sched.entries (T).data.type_of_event is when Task_activation => if Sched.entries (t).data.activation_task.name = My_Task.name then My_Task_Occurence.arrival_time:= current_date; My_Task_Occurence.absolute_deadline:= Sched.entries (t).data.activation_task.start_time + Sched.entries (t).data.activation_task.deadline; end if; when End_Of_Task_Capacity => if Sched.entries (t).data.end_task.name = My_Task.name then effective_end:=current_date; if (effective_end > My_Task_Occurence.Absolute_Deadline) then Msg := Msg & Lb_Comma & Lb_Check_absolute_Deadline (Current_Language) & My_Task_Occurence.Absolute_Deadline'Img & Lb_Completion_Time (Current_Language) & Effective_End'Img & To_Unbounded_String (")"); end if; end if; when others => null; end case; end loop; if Effective_End > 0 then Average := Double (Effective_End - My_Task_Occurence.Arrival_time); Min := Effective_End - My_Task_Occurence.Arrival_time; Max := Min; else Average := 0.0; Min := 0; Max := 0; end if; end Acyclic_Response_Time_By_Simulation; procedure Response_Time_By_Simulation (My_Task : Generic_Task_Ptr; Sched : in Scheduling_Sequence_Ptr; Msg : in out Unbounded_String; Max : in out Natural; Min : in out Natural; Average : in out Double) is begin case My_Task.task_type is when Aperiodic_Type => Acyclic_Response_Time_By_Simulation (Aperiodic_Task_Ptr (My_Task), Sched, Msg, Max, Min, Average); when others => Cyclic_Response_Time_By_Simulation (My_Task, Sched, Msg, Max, Min, Average); end case; end Response_Time_By_Simulation; function Number_Of_Preemption_From_Simulation (Sched : in Scheduling_Sequence_Ptr; My_Tasks : in Tasks_Set) return Natural is Nb : Natural := 0; A_Task : Generic_Task_Ptr; Usage_Time : Natural; begin for I in 0 .. Sched.nb_entries - 1 loop if (Sched.entries (I).data.type_of_event = Running_Task) then for K in reverse 0 .. I - 1 loop if (Sched.entries (K).data.type_of_event = Running_Task) then if ((Sched.entries (K).data.running_task.name /= Sched.entries (I).data.running_task.name) and (Sched.entries (K).item + 1 = Sched.entries (I).item)) then -- We know that the previous unit of time, another -- task was running. Check now that is was a preeemption -- -- look for the previously elected task and its state -- A_Task := Search_Task (My_Tasks, Sched.entries (I).data.running_task.name); -- Compute the running time of the task until its wake up -- time -- Usage_Time := 0; for Z in reverse 0 .. K - 1 loop if (Sched.entries (Z).data.type_of_event = Running_Task) then if A_Task.name = Sched.entries (Z).data.running_task.name then Usage_Time := Usage_Time + 1; end if; end if; if (Sched.entries (Z).data.type_of_event = Task_activation) then if A_Task.name = Sched.entries (Z).data.activation_task.name then if (Usage_Time /= A_Task.capacity) and (Usage_Time /= 0) then Nb := Nb + 1; end if; exit; end if; end if; end loop; exit; end if; end if; end loop; end if; end loop; return Nb; end Number_Of_Preemption_From_Simulation; function Number_Of_Switch_Context_From_Simulation (Sched : in Scheduling_Sequence_Ptr) return Natural is Nb : Natural := 0; begin for I in 0 .. Sched.nb_entries - 1 loop if (Sched.entries (I).data.type_of_event = Running_Task) then for K in reverse 0 .. I - 1 loop if (Sched.entries (K).data.type_of_event = Running_Task) then if (Sched.entries (K).data.running_task.name /= Sched.entries (I).data.running_task.name) then Nb := Nb + 1; end if; exit; end if; end loop; end if; end loop; return Nb; end Number_Of_Switch_Context_From_Simulation; procedure cyclic_All_Response_Times_By_Simulation (My_Task : in Generic_Task_Ptr; Sched : in Scheduling_Sequence_Ptr; Result : in out Task_Occurence_Table_Ptr) is Current_Date : Natural := 0; Task_Occurence_Number : Task_Occurence_Range:=0; begin -- Look for task release time -- Task_Occurence_Number:=0; for J in 0 .. Sched.nb_entries - 1 loop if Sched.entries (J).data.type_of_event = Task_activation then if Sched.entries (J).data.activation_task.name = My_Task.name then Initialize (result.entries (Task_Occurence_Number), My_Task, Sched.entries (J).item); Task_Occurence_Number:= Task_Occurence_Number+1; end if; end if; end loop; -- Look for completion time -- and compute response time -- Task_Occurence_Number:=0; for J in 0 .. Sched.nb_entries - 1 loop if Sched.entries (j).data.type_of_event = End_Of_Task_Capacity then Current_Date := Sched.entries (j).item; if Sched.entries (j).data.end_task.name = My_Task.name then result.entries (Task_Occurence_Number).completion_Time := current_date; result.entries (Task_Occurence_Number).Response_Time := current_date - result.entries (Task_Occurence_Number).arrival_time; Task_Occurence_Number:=Task_Occurence_Number+1; result.nb_entries:=result.nb_entries+1; end if; end if; end loop; end Cyclic_all_Response_Times_By_Simulation; procedure Acyclic_all_Response_Times_By_Simulation (My_Task : in Aperiodic_Task_Ptr; Sched : in Scheduling_Sequence_Ptr; result : in out task_occurence_table_ptr) is Current_Date : Natural := 0; begin Initialize (result.entries(0), generic_task_ptr(My_Task)); for T in 0 .. Sched.nb_entries - 1 loop -- the current date -- Current_Date := Sched.entries (T).item; -- Look for task completion and task starting time -- case Sched.entries (T).data.type_of_event is when Task_activation => if Sched.entries (t).data.activation_task.name = My_Task.name then result.entries(0).arrival_time:= current_date; end if; when End_Of_Task_Capacity => if Sched.entries (t).data.end_task.name = My_Task.name then result.entries(0).completion_time:= current_date; result.nb_entries :=1; end if; when others => null; end case; end loop; end Acyclic_all_Response_Times_By_Simulation; procedure All_Response_Times_By_Simulation (My_Task : in Generic_Task_Ptr; Sched : in Scheduling_Sequence_Ptr; Result : in out Task_Occurence_Table_Ptr) is begin case My_Task.task_type is when Aperiodic_Type => Acyclic_All_Response_Times_By_Simulation (Aperiodic_Task_Ptr (My_Task), Sched, result); when others => Cyclic_All_Response_Times_By_Simulation (My_Task, sched, result); end case; end All_Response_Times_By_Simulation; procedure Compute_Response_Time_Distribution (My_Task : in Generic_Task_Ptr; Sched : in Scheduling_Sequence_Ptr; Result : in out Density_Table) is Found : Boolean := False; A_Density : Density_Item; Number_Of_Response_Time : Double; My_Task_Occurence_Table : Task_Occurence_Table_Ptr; begin -- Compute all the response times of the task -- My_Task_Occurence_Table := new Task_Occurence_Table; All_Response_Times_By_Simulation(my_task, sched, my_task_occurence_table); -- We have the response times. We look for the -- density table -- If so, increment the frequency, if -- not, add it to the table -- for i in 0 .. my_task_occurence_table.nb_entries - 1 loop -- Check if this response is already known -- Found := False; for k in 0 .. result.nb_entries - 1 loop if result.entries (K).response_time = My_Task_Occurence_Table.entries ( i).Response_Time then Result.entries (K).probability := Result.entries (K).probability + 1.0; Found := True; end if; end loop; if not Found then A_Density.response_time := My_Task_Occurence_Table.entries ( i).Response_Time; A_Density.probability := 1.0; add (Result, A_Density); end if; end loop; -- Now, compute density : -- divide all entries of the table by the found number of response time -- Number_Of_Response_Time := 0.0; for K in 0 .. Result.nb_entries - 1 loop Number_Of_Response_Time := Number_Of_Response_Time + Result.entries (K).probability; end loop; for K in 0 .. Result.nb_entries - 1 loop Result.entries (K).probability := Result.entries (K).probability / Number_Of_Response_Time; end loop; Free (My_Task_Occurence_Table); end Compute_Response_Time_Distribution; procedure Compute_Response_Time_Distribution (My_Tasks : in Tasks_Set; Sched : in Scheduling_Sequence_Ptr; Processor_Name : Unbounded_String; Result : in out Densities_Table) is A_Task : Generic_Task_Ptr; My_Iterator : Tasks_Iterator; Working_Density : Density_Table; begin initialize (Result); reset_iterator (My_Tasks, My_Iterator); loop current_element (My_Tasks, A_Task, My_Iterator); if (Processor_Name = A_Task.cpu_name) then initialize (Working_Density); Compute_Response_Time_Distribution (A_Task, Sched, Working_Density); add (Result, A_Task, Working_Density); end if; exit when is_last_element (My_Tasks, My_Iterator); next_element (My_Tasks, My_Iterator); end loop; end Compute_Response_Time_Distribution; end Scheduling_Analysis.extended.task_analysis;