------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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;