------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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.Exceptions; use Ada.Exceptions; with Resources; use Resources; use Resources.Resource_accesses; with Time_Unit_Events; use Time_Unit_Events; use Time_Unit_Events.Time_Unit_Package; with natural_util; use natural_util; with double_util; use double_util; with integer_util; use integer_util; with Ada.Numerics.Elementary_Functions; use Ada.Numerics.Elementary_Functions; with Objects; use Objects; with Objects.extended; use Objects.extended; with initialize_framework; use initialize_framework; with Text_IO; use Text_IO; with Translate; use Translate; with unbounded_strings; use unbounded_strings; with Scheduler; use Scheduler; with Scheduling_Analysis; use Scheduling_Analysis; use Scheduling_Analysis.Double_Tasks_Parameters_Package; with priority_assignment.rm; use priority_assignment.rm; with priority_assignment.dm; use priority_assignment.dm; with systems; use systems; with Xml_Tag; use Xml_Tag; with Translate; use Translate; with Ada.Numerics.Aux; use Ada.Numerics.Aux; with scheduler.dynamic_priority; use scheduler.dynamic_priority; with feasibility_test.processor_utilization; use feasibility_test.processor_utilization; with Debug; use Debug; package body feasibility_test.processor_demand is --------------------------------------------------------------------- -- Max_Deadlirnbe_Of_TaskSet -- Implementation Notes: -- S. Rubini -- should already exist somewhere ? --------------------------------------------------------------------- function Max_Deadline_Of_TaskSet (My_Tasks : in Tasks_Set ; Processor_Name : in Unbounded_String) return Natural is Max_Deadline : 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 (A_Task.cpu_name = Processor_Name) then Max_Deadline := Natural'Max ( Max_Deadline, A_Task.Deadline ); end if; exit when is_last_element ( My_Tasks, My_Iterator ); next_element ( My_Tasks, My_Iterator ); end loop; return Max_Deadline; end Max_Deadline_of_TaskSet; --------------------------------------------------------------------- -- Has_A_Deadline_Less_Than_Period -- Implementation Notes: -- S. Rubini 11/2018 -- Check whether a task has a deadline after its period time --------------------------------------------------------------------- function Has_A_Deadline_Less_Than_Period (My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String) return Boolean is My_Iterator : Tasks_Iterator; A_Task : Generic_Task_Ptr; Deadline_Less_Than_Period : Boolean; begin Deadline_Less_Than_Period := False; 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 /= Aperiodic_Type) then if (Periodic_Task_Ptr (A_Task).Period > A_Task.Deadline) then Deadline_Less_Than_Period := True; end if; end if; exit when is_last_element (My_Tasks, My_Iterator); next_element (My_Tasks, My_Iterator); end loop; return Deadline_Less_Than_Period; end Has_A_Deadline_Less_Than_Period; ------------------------------------------------------------------ -- Processor_Utilization_Over_Period applies on periodic tasks only. -- function Processor_Utilization_Over_Period_without_Periodic_Control (My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String) return Double is Utilization : Double := 0.0; My_Iterator : Tasks_Iterator; A_Task : Generic_Task_Ptr; begin -- Check if tasks are periodics -- reset_iterator (My_Tasks, My_Iterator); loop current_element (My_Tasks, A_Task, My_Iterator); if (A_Task.cpu_name = Processor_Name) then if A_Task.task_type /= Aperiodic_Type then Utilization := Utilization + (Double (A_Task.capacity) / Double (Periodic_Task_Ptr (A_Task).period)); end if; end if; exit when is_last_element (My_Tasks, My_Iterator); next_element (My_Tasks, My_Iterator); end loop; return Utilization; end Processor_Utilization_Over_Period_without_Periodic_Control; ------------------------------------------------------------------ -- Processor_Utilization_Over_Period applies on periodic tasks only. -- function Compute_Hyperperiod_without_periodic_control (My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String := empty_string) return Integer is Iterator1 : Tasks_Iterator; Task1 : Generic_Task_Ptr; Hyperperiod : Integer := 1; begin reset_iterator (My_Tasks, Iterator1); loop current_element (My_Tasks, Task1, Iterator1); if (Task1.cpu_name = Processor_Name) or (Processor_Name = empty_string) then Hyperperiod := natural_util.lcm(Hyperperiod,Periodic_Task_Ptr(Task1).period); end if; exit when is_last_element (My_Tasks, Iterator1); next_element (My_Tasks, Iterator1); end loop; return Hyperperiod; end Compute_Hyperperiod_without_periodic_control; --------------------------------------------------------------------- -- Sporadic_Periodic_Task_Set_Feasibility_Test -- Implementation Notes: -- S. Rubini 11/2018 --------------------------------------------------------------------- procedure Sporadic_Periodic_Task_Set_Feasibility_Test (My_Scheduler : in Generic_Scheduler_Ptr; My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String; Result : in out Feasibility_Test_Report) is Bound : Double := 0.0; Utilpi : Double := 0.0; Check_Time_Interval : Integer := 0; -- T in the algo Tighten_Deadline : Integer := 0; Dbf : Integer := 0; M : Integer := 0; -- M in the algo Msg : Unbounded_String := empty_string; My_Iterator : Tasks_Iterator; A_Task : Generic_Task_Ptr; Over_CPU_Demand : Boolean := False; Over_CPU_Demand_Instant : Natural; begin -- TODO Hyp C < P and C < D -- offsets and start must be 0 Start_Time_Control (My_Tasks, Processor_Name); Offset_Control (My_Tasks, Processor_Name); -- sporadic or periodic tasks Sporadic_Or_Periodic_Control (My_Tasks, Processor_Name); -- report init Result.Feasible := False; Result.Motivation := Unknown; Result.Processor_Utilization := 0.0; -- unknown Result.Check_Interval := 0 ; -- unknown Result.Overrun_Time := 0 ; -- unknown -- for EDF preeemptive schedule if my_scheduler.parameters.scheduler_type /= Earliest_Deadline_First_Protocol or Get_Preemptive (My_Scheduler.all) /= preemptive then raise Invalid_Scheduler; end if; -- classical test based on processor utilization <= 1 Bound_On_Processor_Utilization (dynamic_priority_scheduler(My_Scheduler.all), My_Tasks, Processor_Name, Bound, Msg); Utilpi := Processor_Utilization_Over_Period_without_Periodic_Control (My_Tasks, Processor_Name); if Utilpi > Bound then -- Bound value should be one for EDF scheduler Result.Feasible := False; Result.Motivation := By_Processor_Utilization_Factor; Result.Processor_Utilization := Utilpi; Result.Processor_Utilization_Bound := Bound; else -- check if all the deadlines are after interarrival time or period if Has_A_Deadline_Less_Than_Period(My_Tasks, Processor_Name) = False then Result.Feasible := True; Result.Motivation := By_Processor_Utilization_Factor; Result.Processor_Utilization := Utilpi; Result.Processor_Utilization_Bound := Bound; else -- No constraints on deadlines versus period -- compute check interval T -- P= lcm+max deadline M := Compute_Hyperperiod_without_periodic_control( My_Tasks, Processor_Name ) + Max_Deadline_of_TaskSet( My_Tasks, Processor_Name ); -- We have tested before that Uilpi <=1 -- avoid 0 divisor later, if Utilpi = 1.0 then Check_Time_Interval := M ; else Tighten_Deadline := 0; reset_iterator ( My_Tasks, My_Iterator ); loop current_element ( My_Tasks, A_Task, My_Iterator ); if A_Task.cpu_name = Processor_Name then Tighten_Deadline := Natural'Max ( Tighten_Deadline, Periodic_Task_Ptr (A_Task).Period - A_Task.Deadline ); end if; exit when is_last_element ( My_Tasks, My_Iterator ); next_element ( My_Tasks, My_Iterator ); end loop; Check_Time_Interval := Natural'min(M, Natural(Utilpi / (1.0-Utilpi) * double(Tighten_Deadline))); end if; -- compute the dbf at all instant of the check_time_interval Dbf := 0; Over_CPU_Demand := False; for t in 1 .. Check_Time_Interval loop Update_Demand_Bound_Function(My_Tasks, Processor_Name, t, Dbf); if Dbf > t then Over_CPU_Demand := True; Over_CPU_Demand_Instant := t; end if; exit when Over_CPU_Demand; -- too much CPU demand end loop; if Over_CPU_Demand then Result.Feasible := False; Result.Motivation := By_Dbf; Result.Processor_Utilization := Utilpi; Result.Processor_Utilization_Bound := Bound; Result.Overrun_Time := Over_CPU_Demand_Instant; Result.Check_Interval := Check_Time_Interval; else Result.Feasible := True; Result.Motivation := By_Dbf; Result.Processor_Utilization := Utilpi; Result.Processor_Utilization_Bound := Bound; Result.Check_Interval := Check_Time_Interval; end if; end if; end if; end Sporadic_Periodic_Task_Set_Feasibility_Test; procedure Update_Demand_Bound_Function (My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String; t : in Natural; DBF : in out Natural ) is My_Iterator : Tasks_Iterator; A_Task : Generic_Task_Ptr; Release_Relative_Time : Natural; begin reset_iterator ( My_Tasks, My_Iterator ); loop current_element ( My_Tasks, A_Task, My_Iterator ); if A_Task.cpu_name = Processor_Name then Release_Relative_Time := t mod Periodic_Task_Ptr (A_Task).Period; if t >= A_Task.Deadline and t mod Periodic_Task_Ptr (A_Task).Period = A_Task.Deadline mod Periodic_Task_Ptr (A_Task).Period then DBF := DBF + A_Task.Capacity ; Put_Debug("Dbf at t" & t'Img & " is " & Dbf'Img); end if; end if; exit when is_last_element ( My_Tasks, My_Iterator ); next_element ( My_Tasks, My_Iterator ); end loop; end Update_Demand_Bound_Function; end feasibility_test.processor_demand;