------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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 Debug; use Debug; with batteries; use batteries; with sets; package body Scheduler.Dynamic_Priority.Edh is procedure Initialize (A_Scheduler : in out Edh_Scheduler) is begin Reset (A_Scheduler); A_Scheduler.parameters.scheduler_type := Earliest_Deadline_First_Protocol; end Initialize; function Copy (A_Scheduler : in Edh_Scheduler) return Generic_Scheduler_Ptr is Ptr : Edh_Scheduler_Ptr; begin Ptr := new Edh_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 Edh_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; Core_Name : in Unbounded_String; Options : in Scheduling_Option; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table; Elected : in out Tasks_Range; No_Task : in out Boolean) is Smallest_Deadline : Natural := Natural'Last; I : Tasks_Range := 0; K : Tasks_Range := 0; J : Tasks_Range := 0; is_ready : boolean := false; previous_task_can_be_run : boolean := false; -- Battery Battery_ok : boolean := false; Battery_iterator : batteries_Iterator; The_Battery : Battery_Ptr; -- Processor Processor_is_idle : boolean := True; -- Slack time Slack_time : Natural := Natural'Last; STti : Natural := 0; Hi : Natural := 0; ATi : Natural := 0; Inter : Natural := 0; -- Slack energy Slack_energy : Natural := Natural'Last; SEti : Natural := 0; Ep : Natural := 0; Gi : Natural := 0; begin Put_Debug("Call Do_Election: EDH"); -- Test on the battery if (not is_empty(Si.Batteries)) then reset_iterator (Si.Batteries, Battery_iterator); loop current_element (Si.Batteries, The_Battery, Battery_iterator); if (The_Battery.cpu_name = Processor_Name) then Battery_ok := True; if (Current_Time = 0) then My_scheduler.Energy := The_Battery.initial_energy; end if; end if; exit when is_last_element (Si.Batteries, Battery_iterator); next_element (Si.Batteries, Battery_iterator); end loop; end if; -- ... Put_Debug(" My_scheduler.Energy : " & My_scheduler.Energy'Img & " at : " & Current_Time'Img); -- If the battery's cpu name corresponds to the processor then we can execute the procedure -- For now, we consider that there can only be one battery if (Battery_ok) then -- Job Set Slack Time at Current_Time loop if Si.Tcbs (k) /= null then if (Si.Tcbs (k).Tsk.cpu_name = Processor_Name) then Dynamic_Priority_Tcb_ptr (Si.Tcbs (k)).Dynamic_Deadline := Si.Tcbs (k).wake_up_time + Si.Tcbs (k).Tsk.deadline; end if; Hi := 0; ATi := 0; STti := 0; -- loop if Si.Tcbs (j) /= null then if (Dynamic_Priority_Tcb_ptr (Si.Tcbs (j)).Dynamic_Deadline <= Dynamic_Priority_Tcb_ptr (Si.Tcbs (k)).Dynamic_Deadline) then -- Hi : The processor demand of a job set at time Current_Time Hi := Hi + Si.Tcbs (j).Tsk.capacity; -- ATi : Total remaining execution time for uncompleted jobs at time Current_Time ATi := ATi + Si.Tcbs (j).Rest_Of_Capacity; end if; end if; J := J + 1; exit when Si.Tcbs (J) = null; end loop; -- ... -- STti : Slack time of a job at time Current_Time Inter := Hi - ATi; STti := natural'max(0, Dynamic_Priority_Tcb_ptr (Si.Tcbs (k)).Dynamic_Deadline - Current_Time - Inter); -- ST : Slack time of a job set at time Current_Time if (STti < Slack_time) and (Dynamic_Priority_Tcb_ptr (Si.Tcbs (k)).Dynamic_Deadline > Current_Time) then Slack_time := STti; end if; end if; J := 0; K := K + 1; exit when Si.Tcbs (K) = null; end loop; -- End of Job Set Slack Time at Current_Time -- Job Set Slack Energy at Current_Time if (Si.Tcbs (My_Scheduler.Previously_Elected) /= null) then K := 0; J := 0; loop if Si.Tcbs (k) /= null then Gi := 0; Ep := 0; -- loop if Si.Tcbs (j) /= null then if ((Current_Time <= Si.Tcbs (j).Wake_Up_Time) and (Dynamic_Priority_Tcb_ptr (Si.Tcbs (j)).Dynamic_Deadline <= Dynamic_Priority_Tcb_ptr (Si.Tcbs (k)).Dynamic_Deadline)) then -- Gi : Energy demand of a job set at time Current_Time Gi := Gi + Si.Tcbs (j).Tsk.energy_consumption; end if; end if; J := J + 1; exit when Si.Tcbs (J) = null; end loop; -- ... -- Ep : Energy produced in the time interval (Current_Time,Deadline) Ep := natural'max(0, (Dynamic_Priority_Tcb_ptr (Si.Tcbs (k)).Dynamic_Deadline - Current_Time - Si.Tcbs (k).Tsk.start_time) * The_Battery.rechargeable_power); -- SEti : Slack energy of a job at time Current_Time SEti := natural'max(0, My_scheduler.Energy + Ep - Gi); -- PSE : Slack energy of the job set at time Current_Time if (SEti < Slack_energy) then if ( (Current_Time < Si.Tcbs (k).Wake_Up_Time) and (Si.Tcbs (k).Wake_Up_Time < Dynamic_Priority_Tcb_ptr (Si.Tcbs (k)).Dynamic_Deadline) and (Dynamic_Priority_Tcb_ptr (Si.Tcbs (k)).Dynamic_Deadline < Dynamic_Priority_Tcb_ptr (Si.Tcbs (my_scheduler.previously_elected)).Dynamic_Deadline)) then Slack_energy := SEti; end if; end if; end if; J := 0; K := K + 1; exit when Si.Tcbs (K) = null; end loop; end if; if (Slack_energy < The_Battery.e_max) then Slack_energy := 0; end if; -- End of Job Set Slack Energy at Current_Time Put_Debug("ST " & Slack_time'Img); Put_Debug("PSE " & Slack_energy'Img); 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 Options.With_Resources then Check_Resource (My_Scheduler, Si, Result, Current_Time, Si.Tcbs (I), is_ready, Event_To_Generate); else is_ready:=true; end if; if is_ready then Check_jitter(Si.Tcbs (I), Current_Time, Si.Tcbs(I).is_jitter_ready ); if (Options.With_jitters = False) or (Si.Tcbs (I).is_jitter_ready) then if (Options.With_Offsets = False) or Check_Offset (Si.Tcbs (I), Current_Time) then if (Options.With_Precedencies = False) or Check_Precedencies (Si, Current_Time, Si.Tcbs (I)) then if i = my_scheduler.previously_elected then previous_task_can_be_run:=true; end if; -- Rule n1 : EDF priority if (Dynamic_Priority_Tcb_Ptr (Si.Tcbs (I)).Dynamic_Deadline < Smallest_Deadline) then Smallest_Deadline := Dynamic_Priority_Tcb_Ptr (Si.Tcbs (I)).Dynamic_Deadline; Elected := I; end if; -- End of rule n1 -- Rule n3 : if (My_scheduler.Energy = 0) or (My_scheduler.Energy < Si.Tcbs (i).Tsk.capacity) or (Slack_energy = 0) then Processor_is_idle := True; end if; -- End of rule n3 -- Rule n4 : if (My_scheduler.Energy = The_Battery.capacity) or (Slack_time = 0) then Processor_is_idle := False; end if; -- End of rule n4 -- Rule n5 if (My_scheduler.Energy > 0) and (My_scheduler.Energy < The_Battery.capacity) and (My_scheduler.Energy >= Si.Tcbs (i).Tsk.capacity) and (Slack_time > 0) and (Slack_energy > 0) then -- Processor can equally be idle or busy -- For now it is busy Processor_is_idle := False; end if; -- End of rule n5 end if; end if; end if; end if; end if; end if; end if; end if; I := I + 1; exit when Si.Tcbs (I) = null; end loop; -- Rule n2 : if Smallest_Deadline = Natural'Last then Processor_is_idle := True; end if; -- End of rule n2 -- if Processor_is_idle = True then No_Task := True; My_scheduler.Energy := My_scheduler.Energy + The_Battery.rechargeable_power; if My_scheduler.Energy > The_Battery.capacity then My_scheduler.Energy := The_Battery.capacity; end if; elsif Processor_is_idle = False then No_Task := False; if (My_scheduler.Energy - Si.Tcbs (Elected).Tsk.energy_consumption + The_Battery.rechargeable_power * Si.Tcbs (Elected).Tsk.capacity < 0) then My_scheduler.Energy := 0; else My_scheduler.Energy := My_scheduler.Energy - Si.Tcbs (Elected).Tsk.energy_consumption + The_Battery.rechargeable_power * Si.Tcbs (Elected).Tsk.capacity; end if; if My_scheduler.Energy > The_Battery.capacity then My_scheduler.Energy := The_Battery.capacity; end if; end if; -- By default, as task are sorted in the set according to their name -- when we have two tasks with the same absolute deadline, we choose the first one -- in the task set, i.e. the task with the smallest name. -- This strategy can be useful has it provides a simple mean to introduce a -- tie break as a kind of fixed priority. -- However, it may introduce an extra preemption. -- If we want to reduce preemption number as much as possible, in this case -- we select the previous task ... in this task can be run again ! -- if Options.with_minimize_preemption and previous_task_can_be_run then if Dynamic_Priority_Tcb_ptr (Si.Tcbs (my_scheduler.previously_elected)).Dynamic_Deadline = Smallest_Deadline then elected := my_scheduler.previously_elected; Put_Debug("Call Do_Election: EDF : Minimize preemption"); end if; end if; Put_Debug("Call Do_Election: EDH : Elected : " & Elected'Img); end if; end Do_Election; end Scheduler.Dynamic_Priority.Edh;