------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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 Xml_Tag; use Xml_Tag; with double_util; use double_util; with Translate; use Translate; with unbounded_strings; use unbounded_strings; with systems; use systems; with ada.tags; use ada.tags; with text_io; use text_io; with Scheduling_Analysis; use Scheduling_Analysis; use Scheduling_Analysis.Double_Tasks_Parameters_Package; with systems; use systems; with tasks; use tasks; with task_set; use task_set; use task_set.Generic_Task_Set; with multiprocessor_services_interface; use multiprocessor_services_interface; use multiprocessor_services_interface.Periodic_Tasks_Table_Package; use multiprocessor_services_interface.run_servers_Table_Package; with id_generators; use id_generators; with debug; use debug; with Ada.Numerics.Aux; use Ada.Numerics.Aux; package body run_trees is -- To generate server name -- my_id : id; procedure pack_first_fit (current : in run_servers_table; packed : in out run_servers_table) is u : double; a_server : run_server_ptr; id_val : unbounded_string; begin u:=0.0; for i in 0..current.nb_entries-1 loop if (u = 0.0) or (u+current.entries(i).rate > 1.0) then a_server:= new run_server; a_server.server := new periodic_task; generate_id(my_id, id_val); a_server.rate:=0.0; a_server.server.name:= "run_packed_server" & id_val; add(packed, a_server); end if; a_server.rate:=a_server.rate+current.entries(i).rate; u:=a_server.rate; put_debug("Pack " & to_string(current.entries(i).server.name) & " to server " & a_server.server.name & " with Rate = " & u'img); add(a_server.childs,current.entries(i).server); end loop; end pack_first_fit; procedure initialize_run_tree(my_tasks : in tasks_set; a_processor : in unbounded_string) is A_Task : generic_Task_Ptr; My_Iterator : Tasks_Iterator; a_server : run_server_ptr; begin for i in 0 .. max_tasks loop initialize(run_tree(i)); end loop; nb_levels:=0; reset_iterator (My_Tasks, My_Iterator); loop current_element (My_Tasks, A_Task, My_Iterator); if (a_task.cpu_name = a_processor) then a_server := new run_server; a_server.server:=periodic_task_ptr(copy(periodic_task_ptr(a_task))); a_server.rate:=double(a_server.server.capacity)/double(a_server.server.period); a_server.is_ready:=false; a_server.deadline:=0; add(run_tree(nb_levels), a_server); end if; exit when is_last_element (My_Tasks, My_Iterator); next_element (My_Tasks, My_Iterator); end loop; nb_levels:=nb_levels+1; end initialize_run_tree; procedure dual(primal_server : in run_server_ptr; dual_server : out run_server_ptr) is begin dual_server:=copy(primal_server); dual_server.rate:=1.0-primal_server.rate; end dual; procedure dual(primal_server : in run_servers_table; dual_server : in out run_servers_table) is a_dual : run_server_ptr; begin for i in 0..primal_server.nb_entries-1 loop dual(primal_server.entries(i), a_dual); put_debug("Dual server " & to_string(a_dual.server.name) & " with Rate = " & a_dual.rate'img); add(dual_server, a_dual); end loop; end dual; procedure reduce is current1, current2 : run_servers_table; begin initialize (my_id); current2:=run_tree(0); loop initialize(current1); dual (primal_server => current2, dual_server => current1); run_tree(nb_levels):=current1; nb_levels:=nb_levels+1; initialize(current2); pack_first_fit (current => current1, packed => current2); run_tree(nb_levels):=current2; nb_levels:=nb_levels+1; exit when current2.nb_entries=1; end loop; end reduce; function compute_deadline(a_level : in natural; a_server : in run_server_ptr) return natural is server_names : unbounded_string := empty_string; deadline : natural := natural'last; begin -- We are a leaf : return the task deadline -- if a_level=0 then deadline:=a_server.server.deadline; -- We are not a leaf : we must return the deadline of the childs -- else for i in 0..a_server.childs.nb_entries-1 loop server_names:=server_names & " " & a_server.childs.entries(i).name; for k in 0..run_tree(a_level-2).nb_entries-1 loop if a_server.childs.entries(i).name=run_tree(a_level-2).entries(k).server.name then deadline:=natural'min(deadline, compute_deadline(a_level-2, run_tree(a_level-2).entries(k))); run_tree(a_level-1).entries(k).deadline:=deadline; end if; end loop; end loop; end if; a_server.deadline:=deadline; put_debug("Task Deadline of " & to_string(a_server.server.name) & " is " & a_server.deadline'img); if server_names /= empty_string then put_debug(" from childs " & server_names); end if; return deadline; end compute_deadline; end run_trees;