------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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; package body feasibility_test.cache_interferences is function Compute_Gamma_UCB_Union_Multiset (My_Tasks : in Tasks_Set; task_i : in Generic_Task_Ptr; task_j : in Generic_Task_Ptr; Response_Time : in Response_Time_Table; Wiq : in Double; q : in Natural; CRPD_Computation_Approach : in CRPD_Computation_Approach_Type := ECB_Only; Block_Reload_Time : in Natural := 0; My_Cache_Access_Profiles : in Cache_Access_Profiles_Set := no_cache_access_profile) return Natural is cap_j : Cache_Access_Profile_Ptr; cap_k : Cache_Access_Profile_Ptr; task_k : Generic_Task_Ptr; my_iterator : Tasks_Iterator; n : Natural := 0; gamma_ij : Natural := 0; R_i : Natural := 0; R_k : Natural := 0; EkRi : Natural := 0; EjRk : Natural := 0; EjRi : Natural := 0; M_UCB_ij : Integer_Array; M_ECB_j : Integer_Array; M : Integer_Array; begin Initialize(M); ----------------------------- -- Compute: M_UCB_ij ----------------------------- reset_iterator (My_Tasks, my_iterator); loop current_element (My_Tasks, task_k, my_iterator); --aff(i,j) = hep(i) \cap lp(j) if (task_k.priority >= task_i.priority AND task_k.priority < task_j.priority AND task_k.name /= task_j.name) then -- E_k(R_i) = ceiling((R_i + J_k / T_k) EkRi := Natural(Double'Ceiling((Double(R_i) + Double(Periodic_Task_Ptr(task_k).jitter))/Double(Periodic_Task_Ptr(task_k).period))); Put_line("R_i:" & R_i'Img); Put_Line("Periodic_Task_Ptr(task_k).jitter:" & Periodic_Task_Ptr(task_k).jitter'Img); Put_Line("Periodic_Task_Ptr(task_k).period:" & Periodic_Task_Ptr(task_k).period'Img); Put_Line("EkRi:" & EkRi'Img); -- E_j(R_k) = ceiling((R_k + J_j / T_j)) for i in 0..Response_Time.nb_entries-1 loop if(Response_Time.entries(i).item.name = task_k.name) then R_k := Natural(Response_Time.entries(i).data); end if; end loop; if(task_k.name = task_i.name) then R_k := R_i; end if; EjRk := Natural(Double'Ceiling((Double(R_k) + Double(Periodic_Task_Ptr(task_j).jitter))/Double(Periodic_Task_Ptr(task_j).period))); Put_Line("R_k: " & R_k'Img); Put_Line("EjRk:" & EjRk'Img); cap_k := Search_Cache_Access_Profile(My_Cache_Access_Profiles, task_k.cache_access_profile_name); for i in 0..EkRi*EjRk-1 loop for i in 0..cap_k.UCBs.Nb_Entries-1 loop Add(M_UCB_ij, cap_k.UCBs.Entries(i).cache_block_number); end loop; end loop; end if; exit when is_last_element (My_Tasks, my_iterator); next_element (My_Tasks, my_iterator); end loop; ----------------------------- -- Compute: M_ECB_j ----------------------------- -- E_j(R_i) = ceiling((R_i + J_j / T_j) EjRi := Natural(Double'Ceiling((Double(R_i) + Double(Periodic_Task_Ptr(task_j).jitter))/Double(Periodic_Task_Ptr(task_j).period))); Put_Line("EjRi:"& EjRi'Img); cap_j := Search_Cache_Access_Profile(My_Cache_Access_Profiles,task_j.cache_access_profile_name); for l in 0..EjRi-1 loop for i in 0..cap_j.ECBs.Nb_Entries-1 loop Add(M_ECB_j, true, cap_j.ECBs.Entries(i).cache_block_number); end loop; end loop; ----------------------------- -- Union ----------------------------- M := Multiset_Intersection(M_UCB_ij,M_ECB_j); gamma_ij := Block_Reload_Time*M.Size; return gamma_ij; end Compute_Gamma_UCB_Union_Multiset; function Compute_Gamma_ECB_Union_Multiset (My_Tasks : in Tasks_Set; task_i : in Generic_Task_Ptr; task_j : in Generic_Task_Ptr; Response_Time : in Response_Time_Table; Wiq : in Double; q : in Natural; CRPD_Computation_Approach : in CRPD_Computation_Approach_Type := ECB_Only; Block_Reload_Time : in Natural := 0; My_Cache_Access_Profiles : in Cache_Access_Profiles_Set := no_cache_access_profile) return Natural is cap_j : Cache_Access_Profile_Ptr; cap_h : Cache_Access_Profile_Ptr; cap_k : Cache_Access_Profile_Ptr; task_h : Generic_Task_Ptr; task_k : Generic_Task_Ptr; my_iterator : Tasks_Iterator; arr_ecbu : Integer_Array; arr_ucb_k : Integer_Array; arr_intersect : Integer_Array; arr_cost : Integer_Array; n : Natural := 0; gamma_ij : Natural := 0; R_i : Natural := 0; R_k : Natural := 0; EkRi : Natural := 0; EjRk : Natural := 0; EjRi : Natural := 0; M : Integer_Array; begin Initialize(arr_ecbu); initialize(arr_ucb_k); initialize(arr_intersect); initialize(arr_cost); initialize(M); R_i := Natural(Wiq) - q * task_i.capacity; Put_Line("R_i: " & R_i'Img); Put_line("Task_i: " & To_String(task_i.name)); Put_line("Task_j: " & To_String(task_j.name)); ----------------------------------------------- --Compute (Union (h \in hp(j) \cup {j}) ECB_h) ----------------------------------------------- --hp(j) reset_iterator (My_Tasks, my_iterator); loop current_element (My_Tasks, task_h, my_iterator); if (task_h.priority >= task_j.priority AND task_h.name /= task_j.name) then cap_h := Search_Cache_Access_Profile(My_Cache_Access_Profiles,task_h.cache_access_profile_name); for i in 0..cap_h.ECBs.Nb_Entries-1 loop Integer_Arrays.Add(arr_ecbu, true, cap_h.ECBs.Entries(i).cache_block_number); end loop; end if; exit when is_last_element (My_Tasks, my_iterator); next_element (My_Tasks, my_iterator); end loop; --{j} cap_j := Search_Cache_Access_Profile(My_Cache_Access_Profiles,task_j.cache_access_profile_name); for i in 0..cap_j.ECBs.Nb_Entries-1 loop Integer_Arrays.Add(arr_ecbu, true, cap_j.ECBs.Entries(i).cache_block_number); end loop; Put("ECB Union Array: "); Print(arr_ecbu); ----------------------------------------------- --Compute UCB_k \cap arr_ecbu ----------------------------------------------- reset_iterator (My_Tasks, my_iterator); loop current_element (My_Tasks, task_k, my_iterator); --aff(i,j) = hep(i) \cap lp(j) if (task_k.priority >= task_i.priority AND task_k.priority < task_j.priority AND task_k.name /= task_j.name) then Put_Line("Task_k: " & To_String(task_k.name)); cap_k := Search_Cache_Access_Profile(My_Cache_Access_Profiles, task_k.cache_access_profile_name); for i in 0..cap_k.UCBs.Nb_Entries-1 loop Add(arr_ucb_k, cap_k.UCBs.Entries(i).cache_block_number); end loop; Put("Arr_UCB_k: "); Print(arr_ucb_k); --UCB_k \cap arr_ecbu Intersect(arr_a => arr_ucb_k, arr_b => arr_ecbu, arr_c => arr_intersect, n => n); -- n is number of evicting UCBs of k Put_Line("N:" & n'Img); -- E_k(R_i) = ceiling((R_i + J_k / T_k) EkRi := Natural(Double'Ceiling((Double(R_i) + Double(Periodic_Task_Ptr(task_k).jitter))/Double(Periodic_Task_Ptr(task_k).period))); Put_line("R_i:" & R_i'Img); Put_Line("Periodic_Task_Ptr(task_k).jitter:" & Periodic_Task_Ptr(task_k).jitter'Img); Put_Line("Periodic_Task_Ptr(task_k).period:" & Periodic_Task_Ptr(task_k).period'Img); Put_Line("EkRi:" & EkRi'Img); -- E_j(R_k) = ceiling((R_k + J_j / T_j)) for i in 0..Response_Time.nb_entries-1 loop if(Response_Time.entries(i).item.name = task_k.name) then R_k := Natural(Response_Time.entries(i).data); end if; end loop; if(task_k.name = task_i.name) then R_k := R_i; end if; EjRk := Natural(Double'Ceiling((Double(R_k) + Double(Periodic_Task_Ptr(task_j).jitter))/Double(Periodic_Task_Ptr(task_j).period))); Put_Line("R_k: " & R_k'Img); Put_Line("EjRk:" & EjRk'Img); for i in 0..EkRi*EjRk-1 loop Add(M,n); end loop; end if; exit when is_last_element (My_Tasks, my_iterator); next_element (My_Tasks, my_iterator); end loop; -- E_j(R_i) = ceiling((R_i + J_j / T_j) EjRi := Natural(Double'Ceiling((Double(R_i) + Double(Periodic_Task_Ptr(task_j).jitter))/Double(Periodic_Task_Ptr(task_j).period))); Put_Line("EjRi:"& EjRi'Img); -- CRPD computation Sort_DESC(M); Put("==Multi set: "); Print(M); for l in 0..EjRi-1 loop gamma_ij := gamma_ij + Block_Reload_Time * M.Elements(l); end loop; Put_Line("==Result:" & gamma_ij'Img); New_Line; return gamma_ij; end Compute_Gamma_ECB_Union_Multiset; end feasibility_test.cache_interferences;