------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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 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 : select which method according to -- architecture property -- if (scheduler_type = reduction_to_uniprocessor_protocol) 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; -- Partitionned (monoprocessor or multiprocessor) -- if (processor_type = monocore_type) or (a_processor.migration_type = no_migration_type) then if constrained_deadlines and independent_tasks and 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 constrained_deadlines and independent_tasks and 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; if constrained_deadlines and (not independent_tasks) and 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; if (not constrained_deadlines) and is_fixed_job_scheduler (scheduler_type) 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; -- 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); return; end if; -- Multiprocessor cases only -- if (processor_type = uniform_multicores_type) then 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; end if; if (processor_type = unrelated_multicores_type) then 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; end if; if (processor_type = identical_multicores_type) then 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; end if; -- 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; 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;