------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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 CNRS 6285, Universite 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 Xml_Tag; use Xml_Tag; with double_util; use double_util; with Feasibility_Test.processor_utilization; use Feasibility_Test.processor_utilization; 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; with Call_Framework_Interface; use Call_Framework_Interface; with 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 Cache_Set; use Cache_Set; with Caches; use Caches; with Caches; use Caches.Cache_Blocks_Table_Package; with Cache_Access_Profile_Set; use Cache_Access_Profile_Set.Cache_Access_Profile_Set; with Integer_Arrays; use Integer_Arrays; with sets; with feasibility_test.Memory_interferences; use feasibility_test.Memory_interferences; with feasibility_test.cache_interferences; use feasibility_test.cache_interferences; package body feasibility_test.periodic_task_worst_case_response_time_fixed_priority is procedure Compute_Response_Time (My_Scheduler : in Rm_Scheduler; My_Sys : in System; Processor_Name : in Unbounded_String; Msg : in out Unbounded_String; Response_Time : out Response_Time_Table; With_memory_interferences : in Memory_Interference_Computation_Approach_Type := No_Memory_Interference; With_CRPD : in CRPD_Computation_Approach_Type := No_CRPD; Block_Reload_Time : in Natural := 0; My_Cache_Access_Profiles : in Cache_Access_Profiles_Set := no_cache_access_profile) is begin -- check if tasks are periodic -- Periodic_Control (My_sys.Tasks, Processor_Name); -- check start time -- Start_Time_Control (My_sys.Tasks, Processor_Name); -- check offset -- Offset_Control (My_sys.Tasks, Processor_Name); -- check if deadlines are equal than period -- Have_Deadlines_Equal_Than_Periods_Control (My_sys.Tasks, Processor_Name); -- Check processor utilization first -- if (Processor_Utilization_Over_Period (My_sys.Tasks, Processor_Name) > 1.0) then raise Processor_Utilization_Exceeded; end if; -- Compute response time -- Compute_Response_Time (Fixed_Priority_Scheduler (My_Scheduler), My_sys, Processor_Name, Msg, Response_Time, With_memory_interferences, With_CRPD, Block_Reload_Time, My_Cache_Access_Profiles); end Compute_Response_Time; procedure Compute_Response_Time (My_Scheduler : in Dm_Scheduler; My_Sys : in System; Processor_Name : in Unbounded_String; Msg : in out Unbounded_String; Response_Time : out Response_Time_Table; With_memory_interferences : in Memory_Interference_Computation_Approach_Type := No_Memory_Interference; With_CRPD : in CRPD_Computation_Approach_Type := No_CRPD; Block_Reload_Time : in Natural := 0; My_Cache_Access_Profiles : in Cache_Access_Profiles_Set := no_cache_access_profile) is begin -- check if tasks are periodics -- Periodic_Control (My_sys.Tasks, Processor_Name); -- Check processor utilization first -- if (Processor_Utilization_Over_Period (My_sys.Tasks, Processor_Name) > 1.0) then raise Processor_Utilization_Exceeded; end if; -- check start time -- Start_Time_Control (My_sys.Tasks, Processor_Name); -- check offset -- Offset_Control (My_sys.Tasks, Processor_Name); -- Compute response time -- Compute_Response_Time (Fixed_Priority_Scheduler (My_Scheduler), My_sys, Processor_Name, Msg, Response_Time, With_memory_interferences, With_CRPD, Block_Reload_Time, My_Cache_Access_Profiles); end Compute_Response_Time; procedure Compute_Response_Time (My_Scheduler : in Hpf_Scheduler; My_Sys : in System; Processor_Name : in Unbounded_String; Msg : in out Unbounded_String; Response_Time : out Response_Time_Table; With_memory_interferences : in Memory_Interference_Computation_Approach_Type := No_Memory_Interference; With_CRPD : in CRPD_Computation_Approach_Type := No_CRPD; Block_Reload_Time : in Natural := 0; My_Cache_Access_Profiles : in Cache_Access_Profiles_Set := no_cache_access_profile) is begin -- Check if tasks are periodics -- Periodic_Control(My_sys.Tasks, Processor_Name); -- Check processor utilization first -- if (Processor_Utilization_Over_Period (My_sys.Tasks, Processor_Name) > 1.0) then raise Processor_Utilization_Exceeded; end if; -- Check start time -- Start_Time_Control (My_sys.Tasks, Processor_Name); -- Check offset -- Offset_Control (My_sys.Tasks, Processor_Name); -- Compute response time -- Compute_Response_Time (Fixed_Priority_Scheduler (My_Scheduler), My_sys, Processor_Name, Msg, Response_Time, With_memory_interferences, With_CRPD, Block_Reload_Time, My_Cache_Access_Profiles); end Compute_Response_Time; -- compute the value of level-i busy period -- function compute_L (My_Tasks : in Tasks_Set; Current_Task : in Generic_Task_Ptr) return Double is Iterator2 : Tasks_Iterator; Taskj2 : Generic_Task_Ptr; Ln, Ln1 : Double; begin Ln := -0.1; Ln1 := 1.0; while Ln1 /= Ln loop reset_iterator (My_Tasks, Iterator2); Ln := Ln1; Ln1 := 0.0; loop current_element (My_Tasks, Taskj2, Iterator2); if (Taskj2.priority >= Current_Task.priority) then Ln1 := Ln1 + Double'Ceiling (Ln / Double (Periodic_Task_Ptr (Taskj2).period)) * Double (Taskj2.capacity); end if; exit when is_last_element (My_Tasks, Iterator2); next_element (My_Tasks, Iterator2); end loop; end loop; return Ln1; end compute_L; function Compute_Wiq_non_preemptive (My_Tasks : in Tasks_Set; --all the task Current_Task : in Generic_Task_Ptr; --the task examine q : in Integer) return Double is Iterator2 : Tasks_Iterator; Iterator3 : Tasks_Iterator; Taskk, Taskj : Generic_Task_Ptr; Ck, Ck_tmp, Wiq_k, Wiq_k1 : Double; begin --initialization -- Wiq_k := -0.1; Wiq_k1 := 1.0; Ck := 0.0; Ck_tmp := 0.0; -- approximations for Wiq -- exit loop when approximations converge -- while Wiq_k1 /= Wiq_k loop reset_iterator (My_Tasks, Iterator2); Wiq_k := Wiq_k1; Wiq_k1 := Double (q * Current_Task.capacity); -- Iterate on all tasks -- loop current_element (My_Tasks, Taskj, Iterator2); -- If Taskj is in hp(Taski) -- if (Taskj.priority > Current_Task.priority) then Wiq_k1 := Wiq_k1 + (Double'Floor (Wiq_k / Double (Periodic_Task_Ptr (Taskj).period)) + 1.0) * Double (Taskj.capacity); end if; -- exit loop when there is no more task -- exit when is_last_element (My_Tasks, Iterator2); next_element (My_Tasks, Iterator2); end loop; -- Compute the max{Ck-1} -- loop current_element (My_Tasks, Taskk, Iterator3); if (Taskk.priority < Current_Task.priority) then Ck_tmp := Double (Taskk.capacity) - 1.0; if (Ck_tmp > Ck) then Ck := Ck_tmp; end if; end if; exit when is_last_element (My_Tasks, Iterator3); next_element (My_Tasks, Iterator3); end loop; Wiq_k1 := Wiq_k1 + Ck; end loop; return Wiq_k1; end Compute_Wiq_non_preemptive; function Compute_Wiq_preemptive (My_Tasks : in Tasks_Set; --all the task Current_Task : in Generic_Task_Ptr; --the task examine q : in Integer; Response_Time : in Response_Time_Table; -- Response Time of higher priority task will be always computed With_CRPD : in CRPD_Computation_Approach_Type := No_CRPD; Block_Reload_Time : in Natural := 0; My_Cache_Access_Profiles : in Cache_Access_Profiles_Set := no_cache_access_profile) return Double is Iterator2 : Tasks_Iterator; Taskj : Generic_Task_Ptr; Wiq_k, Wiq_k1 : Double; A_CAP : Cache_Access_Profile_Ptr; Gamma_ij : Natural := 0; gamma_ucbum : Natural := 0; gamma_ecbum : Natural := 0; begin Wiq_k := -0.1; Wiq_k1 := 0.0; -- approximations for Wiq -- exit loop when approximations converge while Wiq_k1 /= Wiq_k loop reset_iterator (My_Tasks, Iterator2); Wiq_k := Wiq_k1; Wiq_k1 := Double ((q + 1) * Current_Task.capacity + Current_Task.blocking_time); -- Iterate on all tasks loop current_element (My_Tasks, Taskj, Iterator2); -- If Taskj is in hp(Taski) if (Taskj.priority > Current_Task.priority) then -- -- CRPD Computation -- if(With_CRPD /= No_CRPD)then A_CAP := Search_Cache_Access_Profile(My_Cache_Access_Profiles,taskj.cache_access_profile_name); -- Compute CRPD if task j preempting if(With_CRPD = ECB_Only) then Gamma_ij := Natural(A_CAP.ECBs.Nb_Entries) * Block_Reload_Time; elsif(With_CRPD = ECB_Union_Multiset) then Gamma_ij := Compute_Gamma_ECB_Union_Multiset(My_Tasks => My_Tasks, task_i => Current_Task, task_j => Taskj, Response_Time => Response_Time, Wiq => Wiq_k, q => q, CRPD_Computation_Approach => With_CRPD, Block_Reload_Time => Block_Reload_Time, My_Cache_Access_Profiles => My_Cache_Access_Profiles); elsif(With_CRPD = UCB_Union_Multiset) then Gamma_ij := Compute_Gamma_UCB_Union_Multiset(My_Tasks => My_Tasks, task_i => Current_Task, task_j => Taskj, Response_Time => Response_Time, Wiq => Wiq_k, q => q, CRPD_Computation_Approach => With_CRPD, Block_Reload_Time => Block_Reload_Time, My_Cache_Access_Profiles => My_Cache_Access_Profiles); elsif(With_CRPD = Combined_Multiset) then gamma_ucbum := Compute_Gamma_UCB_Union_Multiset(My_Tasks => My_Tasks, task_i => Current_Task, task_j => Taskj, Response_Time => Response_Time, Wiq => Wiq_k, q => q, CRPD_Computation_Approach => With_CRPD, Block_Reload_Time => Block_Reload_Time, My_Cache_Access_Profiles => My_Cache_Access_Profiles); gamma_ecbum := Compute_Gamma_ECB_Union_Multiset(My_Tasks => My_Tasks, task_i => Current_Task, task_j => Taskj, Response_Time => Response_Time, Wiq => Wiq_k, q => q, CRPD_Computation_Approach => With_CRPD, Block_Reload_Time => Block_Reload_Time, My_Cache_Access_Profiles => My_Cache_Access_Profiles); if(gamma_ecbum > gamma_ucbum) then Gamma_ij := gamma_ucbum; else Gamma_ij := gamma_ecbum; end if; end if; end if; -- -- -- Wiq_k1 := Wiq_k1 + Double'Ceiling ((Wiq_k + Double (Periodic_Task_Ptr (Taskj).jitter)) / Double (Periodic_Task_Ptr (Taskj).period)) * (Double (Taskj.capacity) + Double(Gamma_ij)); end if; -- exit loop when there is no more task exit when is_last_element (My_Tasks, Iterator2); next_element (My_Tasks, Iterator2); end loop; end loop; return Wiq_k1; end Compute_Wiq_preemptive; procedure Compute_Response_Time (My_Scheduler : in Fixed_Priority_Scheduler; My_Sys : in System; Processor_Name : in Unbounded_String; Msg : in out Unbounded_String; Response_Time : out Response_Time_Table; With_memory_interferences : in Memory_Interference_Computation_Approach_Type := No_Memory_Interference; With_CRPD : in CRPD_Computation_Approach_Type := No_CRPD; Block_Reload_Time : in Natural := 0; My_Cache_Access_Profiles : in Cache_Access_Profiles_Set := no_cache_access_profile) is Tmp : Tasks_Set; Iterator1 : Tasks_Iterator; Taski : Generic_Task_Ptr; I : Response_Time_Range := 0; Li, Q_double, Wiq, Ri : Double := 0.0; min_delay : Double :=0.0; Q_arrete, Q : Integer; begin initialize (Response_Time); Current_Processor_Name := Processor_Name; select_and_copy (My_sys.Tasks, Tmp, Select_Cpu'Access); -- Verify cache access profiles -- if (With_CRPD /= No_CRPD) then if (get_number_of_elements(My_Cache_Access_Profiles) <= 0) then raise Cache_Access_Profile_Must_Be_Defined; elsif (Integer(get_number_of_elements(My_Cache_Access_Profiles)) < Integer(get_number_of_elements(My_sys.Tasks))) then raise Cache_Access_Profile_Must_Be_Defined_For_All_Tasks; end if; end if; -- Set priority according to the scheduler -- if (My_Scheduler.parameters.scheduler_type = Deadline_Monotonic_Protocol) then Set_Priority_According_To_Dm (Tmp); else if (My_Scheduler.parameters.scheduler_type = Rate_Monotonic_Protocol) then Set_Priority_According_To_Rm (Tmp); end if; end if; sort (Tmp, Increasing_Priority'Access); -- Bibliographical references -- if (My_Scheduler.parameters.preemptive_type = not_preemptive) then -- Non preemptive case -- Msg := To_Unbounded_String (" (") & Lb_See (Current_Language) & To_Unbounded_String ("[1], page 36, ") & Lb_Equation (Current_Language); Msg := Msg & To_Unbounded_String ("13). "); else -- Preemptive case -- Msg := To_Unbounded_String (" (") & Lb_See (Current_Language) & To_Unbounded_String ("[2], page 3, ") & Lb_Equation (Current_Language); Msg := Msg & To_Unbounded_String ("4). "); end if; -- Sort the task in decreasing priority -- Compute Response Time of the higher priority task first -- Sort(Tmp,Decreasing_Priority'Access); -- compute response time for each tasks -- reset_iterator (Tmp, Iterator1); loop -- Selection of the current task -- current_element (Tmp, Taski, Iterator1); -- Initialize response time for current task -- Response_Time.entries (I).data := 0.0; Response_Time.entries (I).item := Taski; Response_Time.nb_entries := Response_Time.nb_entries + 1; if (My_Scheduler.parameters.preemptive_type = not_preemptive) then -- Find the maximum for Ri in [0..Q] -- Q := 0; Li := compute_L (Tmp, Taski); loop Q_double := Double'Floor (Li / Double (Periodic_Task_Ptr (Taski).period)); Q_arrete := Integer (Q_double); Wiq := Compute_Wiq_non_preemptive (Tmp, Taski, Q); --Ri = Wiq + Ci - qTi -- Ri := Wiq + Double (Periodic_Task_Ptr (Taski).capacity) - Double (Q) * Double (Periodic_Task_Ptr (Taski).period); -- Is Ri greater than current maximum for Ri ? -- if (Ri > Response_Time.entries (I).data) then Response_Time.entries (I).data := Ri; end if; exit when Q = Q_arrete; Q := Q + 1; end loop; else Q := 0; loop Wiq := Compute_Wiq_preemptive (Tmp, Taski, Q, Response_Time, With_CRPD, Block_Reload_Time, My_Cache_Access_Profiles); case Taski.task_type is when Periodic_Type => Ri := Wiq + Double (Periodic_Task_Ptr (Taski).jitter) - Double (Q) * Double (Periodic_Task_Ptr (Taski).period); when others => raise Constraint_Error; end case; if (with_memory_interferences /= No_Memory_Interference) then min_delay:=0.0; memory_interferences_delay(min_delay, Ri, Taski, my_sys, processor_name); Ri:=Ri+min_delay; end if; -- Is Ri greater than current maximum for Ri ? -- if (Ri > Response_Time.entries (I).data) then Response_Time.entries (I).data := Ri; end if; exit when Wiq <= Double (Q + 1) * Double (Periodic_Task_Ptr (Taski).period); Q := Q + 1; end loop; end if; exit when is_last_element (Tmp, Iterator1); next_element (Tmp, Iterator1); I := I + 1; end loop; end Compute_Response_Time; end feasibility_test.periodic_task_worst_case_response_time_fixed_priority;