------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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-2016, Frank Singhoff, Alain Plantec, Jerome Legrand -- -- The Cheddar project was started in 2002 by -- Frank Singhoff, Lab-STICC UMR 6285 laboratory, 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: 1249 $ -- $Date: 2014-08-28 07:02:15 +0200 (Fri, 28 Aug 2014) $ -- $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 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 run_trees; use run_trees; package body Scheduler.multiprocessor_specific.run is function Build_Tcb (My_Scheduler : in multiprocessor_run_Scheduler; A_Task : Generic_Task_Ptr) return Tcb_Ptr is A_Tcb : run_Tcb_Ptr; begin A_Tcb := new run_Tcb; Initialize (Tcb (A_Tcb.all), A_Task); Initialize (A_Tcb.all); return Tcb_Ptr (A_Tcb); end Build_Tcb; procedure Initialize (A_Tcb : in out run_Tcb) is begin A_Tcb.Dynamic_Deadline := A_Tcb.Tsk.deadline + A_Tcb.Wake_Up_Time; end Initialize; procedure Check_Before_Scheduling (My_Scheduler : in multiprocessor_run_Scheduler; My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String) is begin Periodic_Control(my_tasks, processor_name); end Check_Before_Scheduling; procedure Specific_Scheduler_Initialization (My_Scheduler : in out multiprocessor_run_Scheduler; Si : in out Scheduling_Information; Processor_Name : in Unbounded_String; address_space_name : in Unbounded_String; My_Tasks : in out Tasks_Set; my_schedulers : in Scheduler_table; My_Resources : in out Resources_Set; My_Buffers : in out Buffers_Set; My_Messages : in Messages_Set; Msg : in out Unbounded_String) is begin null; end Specific_Scheduler_Initialization; procedure Initialize(A_Scheduler : in out multiprocessor_run_Scheduler) is begin Reset (A_Scheduler); A_Scheduler.parameters.scheduler_type := reduction_to_uniprocessor_Protocol; end Initialize; function Copy (A_Scheduler : in multiprocessor_run_Scheduler) return Generic_Scheduler_Ptr is Ptr : multiprocessor_run_Scheduler_ptr; begin Ptr := new multiprocessor_run_Scheduler; Ptr.parameters := A_Scheduler.parameters; Ptr.Previously_Elected := A_Scheduler.Previously_Elected; return Generic_Scheduler_Ptr (Ptr); end Copy; procedure Do_Election (My_Scheduler : in out multiprocessor_run_Scheduler; Si : in out Scheduling_Information; Result : in out Scheduling_Sequence_Ptr; Msg : in out Unbounded_String; Current_Time : in Natural; Processor_Name : in Unbounded_String; Address_Space_Name : in Unbounded_String; My_Dependencies : in Tasks_Dependencies_Ptr; With_Offsets : in Boolean; With_Precedencies : in Boolean; With_Resources : in Boolean; With_jitters : in Boolean; With_minimize_preemption : in Boolean; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table; Elected : in out Tasks_Range; No_Task : in out Boolean) is function check_server_is_ready(a_level : in natural; a_server : in run_server_ptr) return boolean is is_resource_ready : boolean := false; server_names : unbounded_string := empty_string; i : Tasks_Range; begin a_server.is_ready:=false; is_resource_ready:=false; -- We are a leaf : return the task deadline -- if a_level=0 then i := 0; loop if Si.Tcbs (i) = null then raise task_not_found; end if; exit when Si.Tcbs (i).tsk.name = a_server.server.name; i := i + 1; end loop; if not Si.Tcbs (i).already_run_at_current_time then if (Si.Tcbs (I).Tsk.cpu_name = Processor_Name) then if Check_Core_Assignment(my_scheduler, Si.Tcbs (I)) then if (Si.Tcbs (I).Wake_Up_Time <= Current_Time) and (Si.Tcbs (I).Rest_Of_Capacity /= 0) then if With_Resources then Check_Resource (My_Scheduler, Si, Result, Current_Time, Si.Tcbs (I), is_resource_ready, Event_To_Generate); if is_resource_ready then Check_jitter(Si.Tcbs (I), Current_Time, Si.Tcbs(I).is_jitter_ready ); if (With_jitters = False) or (Si.Tcbs (I).is_jitter_ready) then if (With_Offsets = False) or Check_Offset (Si.Tcbs (I), Current_Time) then if (With_Precedencies = False) or Check_Precedencies (Si, My_Dependencies, Current_Time, Si.Tcbs (I)) then a_server.is_ready:=true; end if; end if; end if; end if; end if; end if; end if; end if; end if; -- We are not a leaf : we call the childs : the server is ready if one of -- its childs is ready -- 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 if check_server_is_ready(a_level-2, run_tree(a_level-2).entries(k) ) then a_server.is_ready:=true; run_tree(a_level-1).entries(k).is_ready:=a_server.is_ready; end if; end if; end loop; end loop; end if; put_debug("Task ready status of " & to_string(a_server.server.name) & " is " & a_server.is_ready'img); if server_names /= empty_string then put_debug(" from childs " & server_names); end if; return a_server.is_ready; end check_server_is_ready; function select_task(a_level : in natural; current1 : in run_server_ptr) return run_server_ptr is current2 : run_server_ptr; deadline : Natural := Natural'Last; selected : run_server_ptr; is_child : boolean; begin if a_level=0 then if current1.is_ready then selected:=current1; put_debug("Election : selected leaf : " & selected.server.name); end if; else -- Pair levels are pack levels -- Unpair levels are dual levels -- level "nb_levels-1" is the top unique server level -- level 0 is the leaf, i.e the task level -- -- For pack levels : look for the ready task with the shortest deadline -- if (a_level mod 2 = 0) then put_debug("Election : pack level, analyse child from server " & current1.server.name & " from level " & a_level'img); deadline:=natural'last; selected:=null; for p in 0..current1.childs.nb_entries-1 loop for k in 0..run_tree(a_level-1).nb_entries-1 loop if current1.childs.entries(p).name=run_tree(a_level-1).entries(k).server.name then current2:=select_task(a_level-1, run_tree(a_level-1).entries(k)); if current2/=null then if current2.deadline <= deadline then selected:=current2; deadline:=current2.deadline; end if; end if; end if; end loop; end loop; if selected/=null then put_debug("Election : selected from pack level : " & selected.server.name & " from level " & a_level'img); end if; -- Now, for Dual levels only : we found the server to NOT run, look for another server to run -- else put_debug("Election : dual level, analyse child from server " & current1.server.name & " from level " & a_level'img); deadline:=natural'last; selected:=null; for k in 0..run_tree(a_level-1).nb_entries-1 loop is_child:=false; for p in 0..current1.childs.nb_entries-1 loop if current1.childs.entries(p).name=run_tree(a_level-1).entries(k).server.name then is_child:=true; end if; end loop; if not is_child then current2:=select_task(a_level-1, run_tree(a_level-1).entries(k)); if current2/=null then if current2.deadline <= deadline then selected:=current2; deadline:=current2.deadline; end if; end if; end if; end loop; if selected/=null then put_debug("Election : selected from dual level : " & selected.server.name); end if; end if; end if; return selected; end select_task; ------------------------------------- -- Main entry point of Do_Election -- deadline : Natural := Natural'Last; I : Tasks_Range := 0; has_a_ready_task : boolean := false; current1 : run_server_ptr; begin loop -- Compute all task deadlines -- if (Si.Tcbs (I).Tsk.cpu_name = Processor_Name) then run_Tcb_ptr (Si.Tcbs (i)).Dynamic_Deadline := Si.Tcbs (i).wake_up_time + Si.Tcbs (i).Tsk.deadline; end if; -- Update task deadlines in the run tree server -- for j in 0..run_tree(0).nb_entries-1 loop if run_tree(0).entries(j).server.name = Si.Tcbs (I).Tsk.name then run_tree(0).entries(j).server.deadline:=run_Tcb_ptr (Si.Tcbs (i)).Dynamic_Deadline ; end if; end loop; I := I + 1; exit when Si.Tcbs (I) = null; end loop; -- Update deadlines of elements of packed levels of the tree -- deadline:=compute_deadline(nb_levels-1, run_tree(nb_levels-1).entries(0)); -- Now as all deadlines are updated, we chose the task to run -- according to the 2 RUN rules : -- 1) choose childs of pack servers according to EDF -- 2) do not choose dual task with shortest deadline -- We add to those 2 rules a third one : any selected task must be runnable -- for Cheddar (e.g. shared resource/offset/jitter scheduling constraint are met) -- -- Check all servers/tasks ready status ... i.e. we can select -- then for scheduling -- has_a_ready_task:=check_server_is_ready(nb_levels-1, run_tree(nb_levels-1).entries(0)); if has_a_ready_task then No_Task := False; else No_Task := True; return; end if; -- Find the leaf according to the 2 RUN rules -- current1:=select_task(nb_levels-1,run_tree(nb_levels-1).entries(0) ); -- current1 now contains the task to run ... find its tcbs index now -- i := 0; loop if Si.Tcbs (i) = null then raise task_not_found; end if; exit when Si.Tcbs (i).tsk.name = current1.server.name; i := i + 1; end loop; elected:=i; end Do_Election; end Scheduler.multiprocessor_specific.run;