------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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-2020, Frank Singhoff, Alain Plantec, Jerome Legrand, -- Hai Nam Tran, Stephane Rubini -- -- The Cheddar project was started in 2002 by -- Frank Singhoff, Lab-STICC UMR 6285, 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$ -- $Date$ -- $Author: singhoff $ ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ with unbounded_strings; use unbounded_strings; with Translate; use Translate; with text_io; use text_io; with ada.strings.unbounded; use ada.strings.unbounded; with unbounded_strings; use unbounded_strings; package body Scheduler.dag.highest_level_first_estimated_times is procedure Initialize (A_Scheduler : in out dag_highest_level_first_estimated_times_Scheduler) is begin Reset (A_Scheduler); A_Scheduler.parameters.scheduler_type := dag_highest_level_first_estimated_times_protocol; end Initialize; function Copy (A_Scheduler : in dag_highest_level_first_estimated_times_Scheduler) return Generic_Scheduler_Ptr is Ptr : dag_highest_level_first_estimated_times_Scheduler_Ptr; begin Ptr := new dag_highest_level_first_estimated_times_Scheduler; Ptr.parameters := A_Scheduler.parameters; Ptr.Previously_Elected := A_Scheduler.Previously_Elected; return Generic_Scheduler_Ptr (Ptr); end Copy; procedure Check_Before_Scheduling (My_Scheduler : in dag_highest_level_first_estimated_times_Scheduler; My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String) is begin null; end Check_Before_Scheduling; procedure Do_Election (My_Scheduler : in out dag_highest_level_first_estimated_times_Scheduler; Si : in out Scheduling_Information; Result : in out Scheduling_Sequence_Ptr; Msg : in out Unbounded_String; Current_Time : in Natural; Processor_Name : in Unbounded_String; Address_Space_Name : in Unbounded_String; Core_Name : in Unbounded_String; Options : in Scheduling_Option; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table; Elected : in out Tasks_Range; No_Task : in out Boolean) is Highiest_Priority : Natural := Natural'First ; I, J, K : Tasks_Range := 0 ; a_task, Right, Left, Successor_task, Real_task : Generic_Task_Ptr ; My_successors : Tasks_set ; My_Iterator1, Ite0, Ite1, Ite2, Ite3 : Tasks_Iterator ; maxi : Natural ; My_tasks : Tasks_Set ; Step, Leaf, Previous : Tasks_Set ; begin ----------------------- -- compute b_level -- -- for each task --- ----------------------- ------------------------------ -- construction de My_tasks -- ------------------------------ reset (My_tasks); J := 0; loop add (My_tasks, Si.Tcbs (J).Tsk) ; J := J + 1; exit when Si.Tcbs (J) = null; end loop; -- Compute b_level for each task; b_level is stored in task.criticality -- Parcourir My_tasks de bas vers le haut de droite vers gauche ... -- a chaque fois, on calcule b_level qui est egale : b-level = capacity + max (blevel des successeurs) Step := Get_Leaf_Tasks (Si.dependencies); -- Extract leaves of the graph and update reset_iterator (step, Ite0); loop current_element (step, a_task, Ite0) ; Real_task := Search_Task (My_Tasks, a_task.name) ; Real_task.criticality := Real_task.capacity ; exit when is_last_element (step, Ite0); next_element (step, Ite0); end loop; -- update b-level value for leaves of the graph 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 current_element (Leaf, Right, Ite1); if Has_Predecessor_Asynchronous (Si.dependencies, Right) then reset (Previous); Previous := Get_Predecessors_List_Asynchronous (Si.dependencies, Right); -- Take previous tasks reset_iterator (Previous, Ite2); for J in 0 .. get_number_of_elements (Previous) - 1 loop maxi := 0 ; current_element (Previous, Left, Ite2); add (Step, Left); -- update Step reset (My_successors); My_successors := Get_Successors_List_Asynchronous (Si.dependencies, Left) ; K := 0 ; reset_iterator (My_successors, Ite3); loop current_element (My_successors, Successor_task, Ite3); Real_task := Search_Task (My_Tasks, Successor_task.name) ; if Real_task.criticality > maxi then maxi := Real_task.criticality ; end if ; K := K + 1 ; exit when is_last_element (My_successors, Ite3); next_element (My_successors, Ite3); end loop; -- find max (b-level of succesor task) Real_task := Search_Task (My_Tasks, Left.name) ; Real_task.criticality := Real_task.capacity + maxi; next_element (Previous, Ite2); end loop; end if; next_element (Leaf, Ite1); end loop; end loop; -- update Si K:= 0 ; loop Real_task := Search_Task (My_Tasks, Si.Tcbs (K).tsk.name ) ; Si.Tcbs (K).tsk.criticality := Real_task.criticality ; K := K + 1; exit when Si.Tcbs (K) = null; end loop ; ----------------------------- -- selection of ready ----- -- task with highest ----- -- b_level ----- ----------------------------- I := 0; loop -- Tcbs is a Tcb_Table where Tcb_Table is array (Tasks_Range) of Tcb_Ptr -- Tcb presents information related to the tasks if not Si.Tcbs (I).already_run_at_current_time then -- Is true if the task is already run on a core unit for the -- current time unit (boolean) if (Si.Tcbs (I).Tsk.cpu_name = Processor_Name) and ((Address_Space_Name = To_Unbounded_String ("")) or (Address_Space_Name = Si.Tcbs (I).Tsk.address_space_name)) then -- Si.Tcbs (I).Tsk = Cheddar ADL properties of the task if Check_Core_Assignment(my_scheduler, Si.Tcbs (I)) then -- Check that the task can be run to the current core -- according to core migration properties -- Wake_Up_Time = Current release time of the task if (Si.Tcbs (I).Wake_Up_Time <= Current_Time) and (Si.Tcbs (I).Tsk.criticality >= Highiest_Priority) and (Si.Tcbs (I).Rest_Of_Capacity /= 0) then if (Options.With_jitters = False) or (Si.Tcbs (I).is_jitter_ready) then if (Options.With_Offsets = False) or Check_Offset (Si.Tcbs (I), Current_Time) then if (Options.With_Precedencies = False) or Check_Precedencies (Si, Current_Time, Si.Tcbs (I)) then ---------------------------------------------------- ---------------------------------------------------- Highiest_Priority := Si.Tcbs (I).Tsk.criticality ; Elected := I ; ----------------------------------------------------- ----------------------------------------------------- end if; end if; end if; end if; end if; end if; end if; I := I + 1; exit when Si.Tcbs (I) = null; end loop; if Highiest_Priority = Natural'First then No_Task := True; else No_Task := False; end if; end Do_Election; procedure Specific_Scheduler_Initialization (My_Scheduler : in out dag_highest_level_first_estimated_times_Scheduler; Si : in out Scheduling_Information; Processor_Name : in Unbounded_String; address_space_name : in Unbounded_String; My_Tasks : in out Tasks_Set; my_schedulers : in Scheduler_table; My_Resources : in out Resources_Set; My_Buffers : in out Buffers_Set; My_Messages : in Messages_Set; Msg : in out Unbounded_String) is begin null; end Specific_Scheduler_Initialization; end Scheduler.dag.highest_level_first_estimated_times;