------------------------------------------------------------ -------------------- ------------------------------------------------------------------------------ -- Cheddar is a GNU GPL real time scheduling analysis tool. -- This program provides services to automatically check performances -- of real time architectures. -- -- Copyright (C) 2002-2010, by Frank Singhoff, Alain Plantec, Jerome Legrand -- -- The Cheddar project was started in 2002 by -- the LISyC Team, University of Western Britanny. -- -- Since 2008, Ellidiss technologies also contributes to the development of -- Cheddar and provides industrial support. -- -- 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: 523 $ -- $Date: 2012-09-26 15:09:39 +0200 (Wed, 26 Sep 2012) $ -- $Author: fotsing $ ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ with Tasks; use Tasks; with unbounded_strings; use unbounded_strings; with Ada.Numerics.Aux; use Ada.Numerics.Aux; with Framework_Config; use Framework_Config; with Processors; use Processors; with Processors.extended; use Processors.extended; with Scheduler; use Scheduler; with Buffers; use Buffers; use Buffers.Buffer_Roles_package; package body Dependency_Services is procedure Set_Parameters_According_To_Chetto (My_Dependencies : in Tasks_Dependencies_Ptr; My_Tasks : in out Tasks_Set; Compute_Deadlines : in Boolean; Compute_Priorities : in Boolean) is Leaf, Step : Tasks_Set; Previous : Tasks_Set; Real_Left, Real_Right, Left, Right : Generic_Task_Ptr; Ite1, Ite2 : Tasks_Iterator; begin if Is_Cyclic (My_Dependencies) then raise Cyclic_Graph_Error; end if; Dependencies_Periods_Control (My_Tasks, My_Dependencies, empty_string); -- Assume the graph is acyclic. -- Extract leaves of the graph and update deadline -- of previous node -- Step := Get_Leaf_Tasks (My_Dependencies); while not is_empty (Step) loop reset (Leaf); duplicate (Step, Leaf); reset (Step); reset_iterator (Leaf, Ite1); for I in 0 .. get_number_of_elements (Leaf) - 1 loop -- The task to be updated -- current_element (Leaf, Right, Ite1); -- Take previous tasks -- if Has_Predecessor (My_Dependencies, Right) then reset (Previous); Previous := Get_Predecessors_List (My_Dependencies, Right); reset_iterator (Previous, Ite2); for J in 0 .. get_number_of_elements (Previous) - 1 loop current_element (Previous, Left, Ite2); add (Step, Left); Real_Left := Search_Task (My_Tasks, Left.name); Real_Right := Search_Task (My_Tasks, Right.name); if Compute_Priorities then if Right.priority >= 1 then Real_Left.priority := Priority_Range'Max (Real_Left.priority, Real_Right.priority + 1); end if; end if; if Compute_Deadlines then Real_Left.deadline := Natural'Min (Real_Left.deadline, Real_Right.deadline - Real_Right.capacity); end if; next_element (Previous, Ite2); end loop; end if; next_element (Leaf, Ite1); end loop; end loop; end Set_Parameters_According_To_Chetto; function Get_Response_Time (Rtn : in Response_Time_Table; A_Task : Generic_Task_Ptr) return Double is begin for I in Response_Time_Range loop if (Rtn.entries (I).item.name = A_Task.name) then return Rtn.entries (I).data; end if; end loop; raise Task_Set.Task_Not_Found; end Get_Response_Time; procedure Inject_Response_Time_Into_Jitter (My_Dependencies : in Tasks_Dependencies_Ptr; My_Tasks : in out Tasks_Set; Rtn : in Response_Time_Table) is Max_Jitter : Double := 0.0; Ite1, Ite2 : Tasks_Iterator; Previous, A_Task : Generic_Task_Ptr; Pred : Tasks_Set; begin -- Scan each task. If a task has a predecessor, set its jitter -- to the response time of its predecessors -- reset_iterator (My_Tasks, Ite1); loop current_element (My_Tasks, A_Task, Ite1); -- Find maximum response time of predecessors -- if Has_Predecessor (My_Dependencies, A_Task) then reset (Pred); Pred := Get_Predecessors_List (My_Dependencies, A_Task); if not is_empty (Pred) then reset_iterator (Pred, Ite2); Max_Jitter := 0.0; for I in 0 .. get_number_of_elements (Pred) - 1 loop current_element (Pred, Previous, Ite2); Max_Jitter := Double'Max (Max_Jitter, Get_Response_Time (Rtn, Previous)); next_element (Pred, Ite2); end loop; -- set jitter with max_jitter -- case A_Task.task_type is when Periodic_Type => Periodic_Task_Ptr (A_Task).jitter := Natural'Max (Periodic_Task_Ptr (A_Task).jitter, Natural (Max_Jitter)); when Poisson_Type => Poisson_Task_Ptr (A_Task).jitter := Natural'Max (Poisson_Task_Ptr (A_Task).jitter, Natural (Max_Jitter)); when others => raise Constraint_Error; end case; end if; end if; exit when is_last_element (My_Tasks, Ite1); next_element (My_Tasks, Ite1); end loop; end Inject_Response_Time_Into_Jitter; procedure Compute_All_Response_Times (My_Processors : in Processors_Set; My_Tasks : in out Tasks_Set; Msg : in out Unbounded_String; Rtn : in out Response_Time_Table) is I : Natural; K, J : Response_Time_Range; A_Processor : Generic_Processor_Ptr; My_Iterator : Processors_Iterator; type Rt is array (0 .. Max_Processors - 1) of Response_Time_Table; Rt_By_Processor : Rt; begin -- Compute tasks -- I := 0; reset_iterator (My_Processors, My_Iterator); loop current_element (My_Processors, A_Processor, My_Iterator); Msg := empty_string; if Get_Number_Of_Task_From_Processor (My_Tasks, A_Processor.name) > 0 then Compute_Response_Time ( extended_Core_Unit_Ptr (get_a_Core(A_Processor)).scheduler.all, My_Tasks, A_Processor.name, Msg, Rt_By_Processor (I)); end if; exit when is_last_element (My_Processors, My_Iterator); next_element (My_Processors, My_Iterator); I := I + 1; end loop; I := 0; K := 0; reset_iterator (My_Processors, My_Iterator); loop J := 0; current_element (My_Processors, A_Processor, My_Iterator); for L in 0 .. (Get_Number_Of_Task_From_Processor (My_Tasks, A_Processor.name) - 1) loop Rtn.entries (K) := Rt_By_Processor (I).entries (J); Rtn.nb_entries := Rtn.nb_entries + 1; K := K + 1; J := J + 1; end loop; exit when is_last_element (My_Processors, My_Iterator); next_element (My_Processors, My_Iterator); I := I + 1; end loop; end Compute_All_Response_Times; procedure Compute_End_To_End_Response_Time (My_Dependencies : in Tasks_Dependencies_Ptr; My_Processors : in Processors_Set; My_Tasks : in out Tasks_Set; One_Step : in Boolean; Update_Tasks_Set : in Boolean; Msg : in out Unbounded_String; Rt : in out Response_Time_Table) is Rtn, Rtn1 : Response_Time_Table; Tmp_Tasks : Tasks_Set; begin initialize (Rtn); initialize (Rtn1); if not Update_Tasks_Set then duplicate (My_Tasks, Tmp_Tasks); end if; Compute_All_Response_Times (My_Processors, My_Tasks, Msg, Rtn); loop -- Stop when end to end response time do not change -- from an iteration to another -- exit when Is_Equal (Rtn, Rtn1); -- Update jitter .... -- if not Update_Tasks_Set then Inject_Response_Time_Into_Jitter (My_Dependencies, Tmp_Tasks, Rtn); else Inject_Response_Time_Into_Jitter (My_Dependencies, My_Tasks, Rtn); end if; if One_Step then exit; end if; Rtn1 := Rtn; initialize (Rtn); if not Update_Tasks_Set then Compute_All_Response_Times (My_Processors, Tmp_Tasks, Msg, Rtn); else Compute_All_Response_Times (My_Processors, My_Tasks, Msg, Rtn); end if; -- Stop when all deadlines are missed -- exit when All_Deadlines_Missed (Rtn); end loop; Rt := Rtn; end Compute_End_To_End_Response_Time; function All_Deadlines_Missed (Rtn : in Response_Time_Table) return Boolean is begin for I in 0 .. Rtn.nb_entries - 1 loop if Rtn.entries (I).data < Double (Rtn.entries (I).item.deadline) then return False; end if; end loop; return True; end All_Deadlines_Missed; function Is_Equal (Rtn : in Response_Time_Table; Rtn1 : in Response_Time_Table) return Boolean is begin if Rtn.nb_entries /= Rtn1.nb_entries then return False; end if; for I in 0 .. Rtn.nb_entries - 1 loop if Rtn.entries (I).data /= Rtn1.entries (I).data then return False; end if; end loop; return True; end Is_Equal; -- To schedule with precedencies -- all task of a dag must have the same period -- procedure Dependencies_Periods_Control (My_Tasks : in Tasks_Set; My_Deps : in Tasks_Dependencies_Ptr; Processor_Name : in Unbounded_String) is Next : Tasks_Set; Real_Task1, Real_Right, Right : Generic_Task_Ptr; Ite1, Ite2 : Tasks_Iterator; Task1 : Generic_Task_Ptr; begin reset_iterator (My_Tasks, Ite1); loop current_element (My_Tasks, Task1, Ite1); if (Task1.cpu_name = Processor_Name) or (Processor_Name = empty_string) then -- Check period of successors -- if Has_Successor (My_Deps, Task1) then reset (Next); Next := Get_Successors_List (My_Deps, Task1); reset_iterator (Next, Ite2); for J in 0 .. get_number_of_elements (Next) - 1 loop current_element (Next, Right, Ite2); Real_Task1 := Search_Task (My_Tasks, Task1.name); Real_Right := Search_Task (My_Tasks, Right.name); if (Real_Right.task_type /= Real_Task1.task_type) then raise Dependencies_Period_Error; end if; if (Real_Right.task_type = Parametric_Type) then raise Dependencies_Period_Error; end if; if (Real_Right.task_type = Periodic_Type) then if (Periodic_Task_Ptr (Real_Right).period /= Periodic_Task_Ptr (Real_Task1).period) then raise Dependencies_Period_Error; end if; end if; if (Real_Right.task_type = Poisson_Type) then if (Poisson_Task_Ptr (Real_Right).period /= Poisson_Task_Ptr (Real_Task1).period) then raise Dependencies_Period_Error; end if; end if; next_element (Next, Ite2); end loop; end if; -- Check period of predecessors -- if Has_Predecessor (My_Deps, Task1) then reset (Next); Next := Get_Predecessors_List (My_Deps, Task1); reset_iterator (Next, Ite2); for J in 0 .. get_number_of_elements (Next) - 1 loop current_element (Next, Right, Ite2); Real_Task1 := Search_Task (My_Tasks, Task1.name); Real_Right := Search_Task (My_Tasks, Right.name); if (Real_Right.task_type /= Real_Task1.task_type) then raise Dependencies_Period_Error; end if; if (Real_Right.task_type = Parametric_Type) then raise Dependencies_Period_Error; end if; if (Real_Right.task_type = Periodic_Type) then if (Periodic_Task_Ptr (Real_Right).period /= Periodic_Task_Ptr (Real_Task1).period) then raise Dependencies_Period_Error; end if; end if; if (Real_Right.task_type = Poisson_Type) then if (Poisson_Task_Ptr (Real_Right).period /= Poisson_Task_Ptr (Real_Task1).period) then raise Dependencies_Period_Error; end if; end if; next_element (Next, Ite2); end loop; end if; end if; exit when is_last_element (My_Tasks, Ite1); next_element (My_Tasks, Ite1); end loop; end Dependencies_Periods_Control; procedure Periodic_Buffer_Control (My_Tasks : in Tasks_Set; A_Buffer : in Buffer_Ptr) is Iterator1 : Tasks_Iterator; Task1 : Generic_Task_Ptr; begin for I in 0 .. A_Buffer.roles.nb_entries - 1 loop reset_iterator (My_Tasks, Iterator1); loop current_element (My_Tasks, Task1, Iterator1); if (Task1.name = A_Buffer.roles.entries (I).item) then if (Task1.task_type /= Periodic_Type) then raise Task_Must_Be_Periodic; end if; end if; exit when is_last_element (My_Tasks, Iterator1); next_element (My_Tasks, Iterator1); end loop; end loop; end Periodic_Buffer_Control; end Dependency_Services;