------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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 Ada.Text_IO; use Ada.Text_IO; with Ada.Exceptions; use Ada.Exceptions; with sets; with double_util; use double_util; with integer_util; use integer_util; with natural_util; use natural_util; with double_util; use double_util; with Ada.Numerics.Elementary_Functions; use Ada.Numerics.Elementary_Functions; with debug; use debug; with initialize_framework; use initialize_framework; with Translate; use Translate; with Objects; use Objects; with Objects.extended; use Objects.extended; with Systems; use Systems; with Task_Set; use Task_Set; with Resources; use Resources; with Core_Units; use Core_Units; with Time_Unit_Events; use Time_Unit_Events; with Processor_Interface; use Processor_Interface; with Processors; use Processors; with Processor_Set; use Processor_Set; with Task_Dependencies; use Task_Dependencies; with Scheduler_Interface; use Scheduler_Interface; ------------------------------------------------------------------------ -- - This package implements multiples algorithms in order to provide a -- feasibility interval for a given system as well as a validation of -- the calculation result. It uses a package multi_precision_integers in a -- way to manipulate big integers during calculation without loss of precision. -- To do: -- - Add precise tests on dependencies as well as preemptivity -- - Add verifications/exceptions on range violations etc. -- - Move utility functions in their proper packages -- (cf: Max_Start_Time_Of_TaskSet in task_set package) -- - Add others algorithms to proper Is_XX_Scheduler functions. --------------------------------------------------------- ------------------------------------------------------------------------ package body feasibility_test.feasibility_interval is function Is_Fixed_Job_Scheduler ( Scheduler_Type : in Schedulers_type ) return Boolean is begin if Scheduler_Type = Earliest_Deadline_First_Protocol then return True; else return False; end if; end Is_Fixed_Job_Scheduler; function Is_Fixed_Task_Scheduler ( Scheduler_Type : in Schedulers_type ) return Boolean is begin case Scheduler_Type is when Rate_Monotonic_Protocol => return True; when Deadline_Monotonic_Protocol => return True; when Posix_1003_Highest_Priority_First_Protocol => return True; when others => return False; end case; end Is_Fixed_Task_Scheduler; function Is_Work_Conserving_Scheduler ( Scheduler_Type : in Schedulers_type ) return Boolean is begin if Is_Fixed_Job_Scheduler ( Scheduler_Type ) or else Is_Fixed_Task_Scheduler ( Scheduler_Type ) then return True; else return False; end if; end Is_Work_Conserving_Scheduler; function Max_Start_Time_Of_TaskSet ( My_Tasks : in Tasks_Set; processor_name : in unbounded_string ) return Natural is Max_Start_Time : Natural := 0; My_Iterator : Tasks_Iterator; A_Task : Generic_Task_Ptr; begin reset_iterator ( My_Tasks, My_Iterator ); loop current_element ( My_Tasks, A_Task, My_Iterator ); if (processor_name = a_task.cpu_name) then Max_Start_Time := Natural'Max ( Max_Start_Time, A_Task.start_time ); end if; exit when is_last_element ( My_Tasks, My_Iterator ); next_element ( My_Tasks, My_Iterator ); end loop; return Max_Start_Time; end Max_Start_Time_Of_TaskSet; --------------------------------------------------------------------- -- Calculate_Feasibility_Interval -- Implementation Notes: -- - This routine calls the function needed for the feasibility -- interval calculation based on the characteristics of the provided -- system. A boolean was added in order to know if the procedure -- finded a corresponding algorithms for the calculation or not and -- so if the interval is valid for the user or not. --------------------------------------------------------------------- procedure Calculate_Feasibility_Interval ( Sys : in System; A_Processor : in Generic_Processor_Ptr; Validate : out Boolean; Interval : out Double; Msg : out Unbounded_String ) is Independent_Tasks : Boolean; Constrained_Deadlines : Boolean; Processor_Type : Processors_type; Scheduler_Type : Schedulers_Type; A_Core : Core_Unit_Ptr; begin Independent_Tasks := Is_Empty ( Sys.Resources ) and Is_Empty ( Sys.Dependencies.Depends ); Constrained_Deadlines := Deadline_Inferior_To_Period ( Sys.Tasks ); -- Get Scheduler Type -- Processor_Type:=a_processor.processor_type; if (Processor_Type = Monocore_type) then a_core:=Mono_Core_Processor_Ptr(a_processor).core; else a_core:=Multi_Cores_Processor_Ptr(a_processor).cores.entries(0); end if; Validate := True; Scheduler_Type := A_Core.scheduling.scheduler_type; -- Scheduling Interval Dispatch case Processor_Type is when Monocore_type => if Constrained_Deadlines then if Independent_Tasks then if Is_Fixed_Task_Scheduler(Scheduler_Type) then msg:=to_unbounded_string(", see Leung and Merill (1980) from [21]."); Interval := Scheduling_Period_With_Offset(Sys.Tasks, A_Processor.name); return; end if; if Is_Fixed_Job_Scheduler(Scheduler_Type) then msg:=to_unbounded_string(", see Goossens and Devillers (1997) from [21]."); Interval := Scheduling_Period_1997(Sys.Tasks, A_Processor.name, False); return; end if; else if Is_Work_Conserving_Scheduler(Scheduler_Type) then msg:=to_unbounded_string(", see Choquet-Geniet and Grolleau (2004), Bado et al. (2012) from [21]."); Interval := Scheduling_Period_With_Offset(Sys.Tasks, A_Processor.name); return; end if; end if; else if Is_Fixed_Job_Scheduler(Scheduler_Type) and Independent_Tasks then msg:=to_unbounded_string(", see Goossens and Devillers (1999) from [21]."); Interval := Scheduling_Period_With_Offset(Sys.Tasks, A_Processor.name); return; end if; end if; when Uniform_Multicores_Type => Put_Debug("Uniform"); if Independent_Tasks and Constrained_Deadlines and Is_Fixed_Task_Scheduler(Scheduler_Type) then msg:=to_unbounded_string(", see Cucu and Goossens (2006) from [21]."); Interval := Scheduling_Period_1997(Sys.Tasks, A_Processor.name, False); return; end if; when Unrelated_Multicores_Types => Put_Debug("Unrelated"); if Independent_Tasks and Constrained_Deadlines and Is_Fixed_Task_Scheduler(Scheduler_Type) then msg:=to_unbounded_string(", see Cucu-Grosjean and Goossens (2011) from [21]."); Interval := Scheduling_Period_1997(Sys.Tasks, A_Processor.name, False); return; end if; when Identical_Multicores_Type => Put_Debug("Identical"); if Constrained_Deadlines then msg:=to_unbounded_string(", see Baro et al. (2012), Nelis et al. (2013) from [21]."); Interval := Scheduling_Period_2012_2013(Sys.Tasks, A_Processor.name); return; else if Independent_Tasks and Is_Fixed_Task_Scheduler(Scheduler_Type) then msg:=to_unbounded_string(", see Cucu and Goossens (2007) from [21]."); Interval := Scheduling_Period_1997(Sys.Tasks, A_Processor.name, True); return; end if; msg:=to_unbounded_string(", see Goossens-Cucu-Grolleau (2016)"); Interval := Scheduling_Period_2016(Sys.Tasks, A_Processor.name); return; end if; when others => Put_Debug("Unknown Processors Type"); Validate := False; Interval := Scheduling_Period_With_Offset(Sys.Tasks, A_Processor.name); return; end case; -- No corresponding feasibility interval algorithm, use of classical Omax + 2H interval, -- Invalidated interval. Validate := False; msg:=to_unbounded_string(", see Leung and Merrill (1980) from [21]."); Interval := Scheduling_Period_With_Offset(Sys.Tasks, A_Processor.name); end Calculate_Feasibility_Interval; --------------------------------------------------------------------- -- Scheduling_Period_1997 -- @param AddPeriod Switch between interval types -- Implementation Notes: -- - --------------------------------------------------------------------- function Scheduling_Period_1997 ( My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String; AddPeriod : in Boolean ) return Double is H : Double := 0.0; Sn : Double := 0.0; Op1 : Double := 0.0; Op2 : Double := 0.0; Op3 : Double := 0.0; Period : Double := 0.0; Start_Time : Double := 0.0; Tmp_Tasks : Tasks_Set; My_Iterator : Tasks_Iterator; A_Task : Generic_Task_Ptr; First_Task_Used : Boolean := True; begin Current_Processor_Name := Processor_Name; H := 1.0; select_and_copy ( My_Tasks, Tmp_Tasks, Select_Cpu'Access ); sort ( Tmp_Tasks, Decreasing_Priority'Access ); Periodic_Control ( Tmp_Tasks, Processor_Name ); reset_iterator ( Tmp_Tasks, My_Iterator ); loop current_element (Tmp_Tasks, A_Task, My_Iterator); if A_Task.cpu_name = Processor_Name and A_Task.task_type = Periodic_Type then Start_Time := double(A_Task.start_time); H := lcm( H, double(Periodic_Task_Ptr(A_Task).period)); Period := double(Periodic_Task_Ptr(A_Task).period); if First_Task_Used then Sn := Start_Time; First_Task_Used := False; else Op1 := Sn - Start_Time; Op2 := double'Ceiling(Op1 / Period); Op1 := Op2 * Period + Start_Time; if Start_Time > Op1 then Sn := Start_Time; else Sn := Op1; end if; if AddPeriod then Op3 := Sn; Sn := Op3 + H; end if; end if; end if; exit when is_last_element ( Tmp_Tasks, My_Iterator ); next_element ( Tmp_Tasks, My_Iterator ); end loop; return Sn + H; end Scheduling_Period_1997; --------------------------------------------------------------------- -- Scheduling_Period_2012_2013 --------------------------------------------------------------------- function Scheduling_Period_2012_2013 ( My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String ) return double is H : double; Op1 : double; Period : double; Capacity : double; Maximum_Start_Time : double; My_Iterator : Tasks_Iterator; A_Task : Generic_Task_Ptr; begin Periodic_Control (My_Tasks, Processor_Name); H := 1.0; Op1 := 1.0; reset_iterator ( My_Tasks, My_Iterator ); Maximum_Start_Time := double(Max_Start_Time_Of_TaskSet (My_Tasks, processor_name)); loop current_element (My_Tasks, A_Task, My_Iterator); if A_Task.cpu_name = Processor_Name and A_Task.task_type = Periodic_Type then Period := double(Periodic_Task_Ptr(A_Task).period) ; Capacity := double(A_Task.capacity); H := lcm( H, Period ); Op1 := Op1 * (Capacity + 1.0); end if; exit when is_last_element (My_Tasks, My_Iterator); next_element (My_Tasks, My_Iterator); end loop; return Maximum_Start_Time + H * Op1; end Scheduling_Period_2012_2013; --------------------------------------------------------------------- -- Scheduling_Period_2016 -- Implementation Notes: -- - --------------------------------------------------------------------- function Scheduling_Period_2016 ( My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String ) return double is H : double; Op1 : double; Op2 : double; Op3 : double; Op4 : double; Period : double; Deadline : double; Start_Time : double; My_Iterator : Tasks_Iterator; A_Task : Generic_Task_Ptr; begin Periodic_Control (My_Tasks, Processor_Name); H := 1.0; Op1 := 1.0; Op2 := 1.0; reset_iterator (My_Tasks, My_Iterator); loop current_element (My_Tasks, A_Task, My_Iterator); if A_Task.cpu_name = Processor_Name and A_Task.task_type = Periodic_Type then Period := double(Periodic_Task_Ptr(A_Task).period); Deadline := double(A_Task.deadline); Start_Time := double(A_Task.start_time); H := lcm( H, Period ); Op3 := Start_Time + Deadline - Period + Op2; Op4 := Op1; Op1 := Op4 * Op3; end if; exit when is_last_element (My_Tasks, My_Iterator); next_element (My_Tasks, My_Iterator); end loop; return Op1 * H; end Scheduling_Period_2016; --------------------------------------------------------------------- -- Scheduling_Period_With_Offset -- Implementation Notes: -- - --------------------------------------------------------------------- function Scheduling_Period_With_Offset ( My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String ) return double is Start_Time : Natural := 0; Offset_Value : Natural := 0; A_Task : Generic_Task_Ptr; My_Iterator : Tasks_Iterator; H : double; Period : double; Max_Offset : double; begin Periodic_Control ( My_Tasks, Processor_Name ); reset_iterator ( My_Tasks, My_Iterator ); H := 1.0; loop current_element ( My_Tasks, A_Task, My_Iterator ); Offset_Value := 0; Start_Time := A_Task.start_time; Period := double(Periodic_Task_Ptr (A_Task).period); Max_Offset := 0.0; for I in 0 .. A_Task.offsets.nb_entries - 1 loop if A_Task.offsets.entries(I).activation = 0 then Offset_Value := A_Task.offsets.entries(I).offset_value; exit; end if; end loop; if Max_Offset <= double(Start_Time + Offset_Value) then Max_Offset := double(Start_Time + Offset_Value); end if; H := lcm ( H, Period ); exit when is_last_element ( My_Tasks, My_Iterator ); next_element ( My_Tasks, My_Iterator ); end loop; return H * 2.0 + Max_Offset; end Scheduling_Period_With_Offset; -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- function Scheduling_Period (My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String) return Double is Start_Time : Integer := 0; A_Task : Generic_Task_Ptr; My_Iterator : Tasks_Iterator; Res : double; begin -- Check if Tasks Are Periodic -- Periodic_Control (My_Tasks, Processor_Name); Res := 1.0; reset_iterator (My_Tasks, My_Iterator); loop current_element (My_Tasks, A_Task, My_Iterator); if (A_Task.cpu_name = Processor_Name and A_Task.task_type = Periodic_Type) then Start_Time := Natural'Max (Start_Time, A_Task.start_time); Res := lcm(res, double(Periodic_Task_Ptr (A_Task).period)); end if; exit when is_last_element (My_Tasks, My_Iterator); next_element (My_Tasks, My_Iterator); end loop; if Start_Time /= 0 then res := (res * 2.0) + double(Start_Time); end if; return res; end Scheduling_Period; function Scheduling_Period (My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String) return Natural is Period : Natural := 1; Start_Time : Natural := 0; A_Task : Generic_Task_Ptr; My_Iterator : Tasks_Iterator; begin -- Check if tasks are periodic -- Periodic_Control (My_Tasks, Processor_Name); reset_iterator (My_Tasks, My_Iterator); loop current_element (My_Tasks, A_Task, My_Iterator); if (A_Task.cpu_name = Processor_Name and A_Task.task_type = Periodic_Type) then Start_Time := Natural'Max (Start_Time, A_Task.start_time); Period := natural_util.lcm (Period, Periodic_Task_Ptr (A_Task).period); end if; exit when is_last_element (My_Tasks, My_Iterator); next_element (My_Tasks, My_Iterator); end loop; if Start_Time /= 0 then Period := (Period * 2) + Start_Time; end if; return Period; end Scheduling_Period; end feasibility_test.feasibility_interval;