------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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 Ada.Numerics; use Ada.Numerics; with Ada.Numerics.Elementary_Functions; use Ada.Numerics.Elementary_Functions; with scheduler_io; use scheduler_io; with Statements; use Statements; with Expressions; use Expressions; use Expressions.Variables_Type_Package; with processor_interface; use processor_interface; with core_units; use core_units; use core_units.Core_Units_Table_Package; with Tasks; use Tasks; with Ada.Strings.Unbounded.Text_IO; use Ada.Strings.Unbounded.Text_IO; with unbounded_strings; use unbounded_strings; with Scheduler; use Scheduler; with Scheduler_Interface; use Scheduler_Interface; with Interpreter.extended; use Interpreter.extended; with Dependency_Services; use Dependency_Services; with Translate; use Translate; with io_tools; use io_tools; with Ada.IO_Exceptions; use Ada.IO_Exceptions; with Ada.Exceptions; use Ada.Exceptions; with Xml_generic_Parsers; use Xml_generic_Parsers; with Xml_generic_Parsers.event_table; use Xml_generic_Parsers.event_table; with Input_Sources.File; use Input_Sources.File; with Sax.Readers; use Sax.Readers; with Text_IO; use Text_IO; with Parser; use Parser; with Sections; use Sections; with section_Set; use section_Set; with Address_Spaces; use Address_Spaces; with Debug; use Debug; package body partitioning_Services is procedure Partition_Small_Task (Src_Processors : in Processors_Set; Src_Tasks : in Tasks_Set; Msg : in out Unbounded_String; Result_Tasks : in out Tasks_Set; Processor_Result : out Processors_Iterator) is A_Task_Result : Periodic_Task_Ptr; My_Task_Iterator_Result : Tasks_Iterator; A_Processor : Generic_Processor_Ptr; My_Processor_Iterator : Processors_Iterator; Processor_Util, Beta : Float := 0.0; S_Cur : Float := 1.0; First_Run : Boolean := True; begin Validate_Multiprocessor_Tasks (Src_Processors, Src_Tasks); duplicate (Src_Tasks, Result_Tasks); sort (Result_Tasks, Increasing_Si'Access); reset_iterator (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); reset_iterator (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); loop if First_Run = False then if is_last_element (Src_Processors, My_Processor_Iterator) then duplicate (Src_Tasks, Result_Tasks); raise No_Such_Processors; end if; next_element (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); end if; First_Run := False; if Float (A_Task_Result.capacity) / Float (A_Task_Result.period) > 1.0 then duplicate (Src_Tasks, Result_Tasks); raise No_Such_Processors; end if; A_Task_Result.cpu_name := A_Processor.name; Processor_Util := Float (A_Task_Result.capacity) / Float (A_Task_Result.period); S_Cur := Float (Log (Float (A_Task_Result.period), 2.0)) - Float'Floor (Float (Log (Float (A_Task_Result.period), 2.0))); Beta := 0.0; exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); loop if is_last_element (Result_Tasks, My_Task_Iterator_Result) then First_Run := True; exit; end if; next_element (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); Beta := (Float (Log (Float (A_Task_Result.period), 2.0)) - Float'Floor (Float (Log (Float (A_Task_Result.period), 2.0)))) - S_Cur; Processor_Util := Processor_Util + Float (A_Task_Result.capacity) / Float (A_Task_Result.period); if (Processor_Util <= Float'Max (Float (Log (2.0, e)), 1.0 - Beta * Float (Log (2.0, e)))) then A_Task_Result.cpu_name := A_Processor.name; else exit; end if; end loop; end loop; Processor_Result := My_Processor_Iterator; sort (Result_Tasks, Increasing_Name'Access); end Partition_Small_Task; procedure Partition_Small_Task (Src_Processors : in Processors_Set; Src_Tasks : in Tasks_Set; Msg : in out Unbounded_String; Result_Tasks : in out Tasks_Set) is Tmp : Processors_Iterator; begin Msg := To_Unbounded_String (" (") & Lb_See (Current_Language) & To_Unbounded_String ("[9], [10]) "); Partition_Small_Task (Src_Processors, Src_Tasks, Msg, Result_Tasks, Tmp); end Partition_Small_Task; procedure Partition_Small_Task (Src_Processors : in Processors_Set; Result_Tasks : in out Tasks_Set; Processor_Result : out Processors_Iterator) is Src_Tasks : Tasks_Set; Msg : Unbounded_String; begin duplicate (Result_Tasks, Src_Tasks); Partition_Small_Task (Src_Processors, Src_Tasks, Msg, Result_Tasks, Processor_Result); end Partition_Small_Task; procedure Rm_General_Tasks (Src_Processors : in Processors_Set; Result_Tasks : in out Tasks_Set) is A_Task_Result : Periodic_Task_Ptr; A_Task_Tmp : Periodic_Task_Ptr; A_Task_Iterator : Tasks_Iterator; My_Task_Iterator_Result : Tasks_Iterator; Tmp_Iterator : Tasks_Iterator; A_Processor : Generic_Processor_Ptr; My_Processor_Iterator : Processors_Iterator; Src_Tasks : Tasks_Set; Num_Of_Tasks : Integer := 0; Task_Utilization, Total_Utilization : Float := 0.0; Goto_First_Loop : Boolean := False; begin duplicate (Result_Tasks, Src_Tasks); reset_iterator (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); reset_iterator (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); sort (Result_Tasks, Increasing_Period'Access); -- Zero processor locations -- loop A_Task_Result.cpu_name := To_Unbounded_String (""); exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); next_element (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); end loop; reset_iterator (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); loop loop if Goto_First_Loop then Goto_First_Loop := False; exit; end if; -- Fetch information for condition-IP -- Tmp_Iterator := My_Task_Iterator_Result; reset_iterator (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); Num_Of_Tasks := 0; Total_Utilization := 0.0; loop if A_Task_Result.cpu_name = A_Processor.name then Num_Of_Tasks := Num_Of_Tasks + 1; Total_Utilization := Total_Utilization + Float (A_Task_Result.capacity) / Float (A_Task_Result.period); end if; exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); next_element (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); end loop; My_Task_Iterator_Result := Tmp_Iterator; current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); Task_Utilization := Float (A_Task_Result.capacity) / Float (A_Task_Result.period); if Task_Utilization <= 2.0 * (1.0 / ((1.0 + Total_Utilization / Float (Num_Of_Tasks))) ** Num_Of_Tasks) - 1.0 then if Total_Utilization = 0.0 then A_Task_Result.cpu_name := A_Processor.name; exit; end if; reset_iterator (Result_Tasks, A_Task_Iterator); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Tmp), A_Task_Iterator); loop if A_Task_Tmp.cpu_name = A_Processor.name and A_Task_Tmp /= A_Task_Result then if A_Task_Result.period < A_Task_Tmp.period and (Integer (Float'Floor (Float (A_Task_Tmp.period) / Float (A_Task_Result.period))) * (A_Task_Tmp.period - A_Task_Result.capacity) >= A_Task_Tmp.capacity or A_Task_Tmp.period >= Integer (Float'Ceiling (Float (A_Task_Tmp.period) / Float (A_Task_Result.period))) * A_Task_Result.capacity + A_Task_Tmp.capacity) then A_Task_Result.cpu_name := A_Processor.name; reset_iterator (Src_Processors, My_Processor_Iterator); Goto_First_Loop := True; exit; else if A_Task_Result.period >= A_Task_Tmp.period and (((Integer (Float'Floor (Float (A_Task_Result.period) / Float (A_Task_Tmp.period))) * (A_Task_Result.period - A_Task_Tmp.capacity)) >= A_Task_Result.capacity) or (A_Task_Result.period >= (Integer (Float'Ceiling (Float (A_Task_Result.period) / Float (A_Task_Tmp.period))) * A_Task_Tmp.capacity + A_Task_Result.capacity))) then A_Task_Result.cpu_name := A_Processor.name; reset_iterator (Src_Processors, My_Processor_Iterator); Goto_First_Loop := True; exit; else if is_last_element (Src_Processors, My_Processor_Iterator) then duplicate (Src_Tasks, Result_Tasks); raise No_Such_Processors; end if; next_element (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); exit; end if; end if; end if; exit when is_last_element (Result_Tasks, A_Task_Iterator); next_element (Result_Tasks, A_Task_Iterator); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Tmp), A_Task_Iterator); end loop; else if is_last_element (Src_Processors, My_Processor_Iterator) then duplicate (Src_Tasks, Result_Tasks); raise No_Such_Processors; end if; next_element (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); end if; end loop; exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); next_element (Result_Tasks, My_Task_Iterator_Result); end loop; end Rm_General_Tasks; procedure Partition_General_Task (Src_Processors : in Processors_Set; Src_Tasks : in Tasks_Set; Msg : in out Unbounded_String; Result_Tasks : in out Tasks_Set) is A_Task_Result : Periodic_Task_Ptr; My_Task_Iterator_Result : Tasks_Iterator; My_Processor_Iterator : Processors_Iterator; A_Processor : Generic_Processor_Ptr; Rmst_Tasks : Tasks_Set; Rmgt_Tasks : Tasks_Set; Tmp_Cpus : Processors_Set; Rmst_Index, Rmgt, Num_Of_Tasks : Integer := 0; begin Validate_Multiprocessor_Tasks (Src_Processors, Src_Tasks); Msg := To_Unbounded_String (" (") & Lb_See (Current_Language) & To_Unbounded_String ("[9], [10]) "); duplicate (Src_Tasks, Result_Tasks); sort (Result_Tasks, Increasing_Utilization'Access); -- Scan for max Alfa to make division between RMST and RMGT tasks -- reset_iterator (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); loop if Float (A_Task_Result.capacity) / Float (A_Task_Result.period) > 1.0 / 3.0 then exit; else Rmgt := Rmgt + 1; end if; exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); next_element (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); end loop; -- Make bin-packing for RMST and RMGT -- reset_iterator (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); loop exit when Rmst_Index = Rmgt; add (Rmst_Tasks, Generic_Task_Ptr (A_Task_Result)); Rmst_Index := Rmst_Index + 1; next_element (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); end loop; Num_Of_Tasks := Integer (get_number_of_elements (Result_Tasks)); if Rmgt /= Num_Of_Tasks then loop current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); add (Rmgt_Tasks, Generic_Task_Ptr (A_Task_Result)); exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); next_element (Result_Tasks, My_Task_Iterator_Result); end loop; end if; -- Call RMST and RMGT functions respectively -- if (is_empty (Rmst_Tasks) = False) then Partition_Small_Task (Src_Processors, Rmst_Tasks, My_Processor_Iterator); end if; if False = is_last_element (Src_Processors, My_Processor_Iterator) and is_empty (Rmgt_Tasks) = False then -- Make processor set for RMGT -- next_element (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); loop add (Tmp_Cpus, A_Processor); exit when is_last_element (Src_Processors, My_Processor_Iterator); next_element (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); end loop; Rm_General_Tasks (Tmp_Cpus, Rmgt_Tasks); else if is_last_element (Src_Processors, My_Processor_Iterator) and is_empty (Rmgt_Tasks) = False then duplicate (Src_Tasks, Result_Tasks); raise No_Such_Processors; end if; end if; -- Put results of two functions to returning task set -- if not is_empty (Rmst_Tasks) then duplicate (Rmst_Tasks, Result_Tasks); end if; if not is_empty (Rmgt_Tasks) then reset_iterator (Rmgt_Tasks, My_Task_Iterator_Result); current_element (Rmgt_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); loop add (Result_Tasks, Generic_Task_Ptr (A_Task_Result)); exit when is_last_element (Rmgt_Tasks, My_Task_Iterator_Result); next_element (Rmgt_Tasks, My_Task_Iterator_Result); current_element (Rmgt_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); end loop; end if; sort (Result_Tasks, Increasing_Name'Access); end Partition_General_Task; procedure Partition_Next_Fit (Src_Processors : in Processors_Set; Src_Tasks : in Tasks_Set; Msg : in out Unbounded_String; Result_Tasks : in out Tasks_Set) is A_Task_Result : Periodic_Task_Ptr; My_Task_Iterator_Result : Tasks_Iterator; A_Processor : Generic_Processor_Ptr; My_Processor_Iterator : Processors_Iterator; M : Integer := 2; Total_Utilization : Float := 0.0; Condition_Ip : Boolean := False; begin Validate_Multiprocessor_Tasks (Src_Processors, Src_Tasks); Msg := To_Unbounded_String (" (") & Lb_See (Current_Language) & To_Unbounded_String ("[9], [10]) "); duplicate (Src_Tasks, Result_Tasks); sort (Result_Tasks, Increasing_Period'Access); reset_iterator (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); reset_iterator (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); loop if Float (A_Task_Result.capacity) / Float (A_Task_Result.period) <= 1.0 then A_Task_Result.cpu_name := A_Processor.name; else duplicate (Src_Tasks, Result_Tasks); raise No_Such_Processors; end if; exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); loop exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); Total_Utilization := Total_Utilization + Float (A_Task_Result.capacity) / Float (A_Task_Result.period); next_element (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); if Float (A_Task_Result.capacity) / Float (A_Task_Result.period) <= 2.0 * (1.0 / (1.0 + Total_Utilization / Float ((M - 1))) ** (M - 1)) - 1.0 and Total_Utilization <= Float (M - 1) * (2.0 ** (1.0 / Float (M - 1)) - 1.0) then Condition_Ip := True; else Condition_Ip := False; end if; if Condition_Ip then A_Task_Result.cpu_name := A_Processor.name; M := M + 1; else if is_last_element (Src_Processors, My_Processor_Iterator) then duplicate (Src_Tasks, Result_Tasks); raise No_Such_Processors; end if; next_element (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); Total_Utilization := 0.0; M := 2; exit; end if; end loop; end loop; sort (Result_Tasks, Increasing_Name'Access); end Partition_Next_Fit; procedure Partition_First_Fit (Src_Processors : in Processors_Set; Src_Tasks : in Tasks_Set; Msg : in out Unbounded_String; Result_Tasks : in out Tasks_Set) is A_Task_Result : Periodic_Task_Ptr; My_Task_Iterator_Result : Tasks_Iterator; Temp_Task_Iterator : Tasks_Iterator; A_Processor : Generic_Processor_Ptr; My_Processor_Iterator : Processors_Iterator; Num_Of_Tasks : Integer := 0; Task_Utilization, Total_Utilization : Float := 0.0; begin Validate_Multiprocessor_Tasks (Src_Processors, Src_Tasks); Msg := To_Unbounded_String (" (") & Lb_See (Current_Language) & To_Unbounded_String ("[9], [10]) "); duplicate (Src_Tasks, Result_Tasks); sort (Result_Tasks, Increasing_Period'Access); reset_iterator (Result_Tasks, My_Task_Iterator_Result); Temp_Task_Iterator := My_Task_Iterator_Result; current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); reset_iterator (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); -- Zero processor locations -- loop A_Task_Result.cpu_name := To_Unbounded_String (""); exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); next_element (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); end loop; reset_iterator (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); loop loop -- Fetch information for condition-IP -- reset_iterator (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); Num_Of_Tasks := 0; Total_Utilization := 0.0; loop if A_Task_Result.cpu_name = A_Processor.name then Num_Of_Tasks := Num_Of_Tasks + 1; Total_Utilization := Total_Utilization + Float (A_Task_Result.capacity) / Float (A_Task_Result.period); end if; exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); next_element (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); end loop; My_Task_Iterator_Result := Temp_Task_Iterator; current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); Task_Utilization := Float (A_Task_Result.capacity) / Float (A_Task_Result.period); if (Task_Utilization <= 2.0 * (1.0 / (1.0 + Total_Utilization / Float (Num_Of_Tasks)) ** Num_Of_Tasks) - 1.0) then A_Task_Result.cpu_name := A_Processor.name; reset_iterator (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); exit; else if is_last_element (Src_Processors, My_Processor_Iterator) then duplicate (Src_Tasks, Result_Tasks); raise No_Such_Processors; end if; next_element (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); end if; end loop; exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); next_element (Result_Tasks, My_Task_Iterator_Result); Temp_Task_Iterator := My_Task_Iterator_Result; end loop; sort (Result_Tasks, Increasing_Name'Access); end Partition_First_Fit; procedure Partition_Best_Fit (Src_Processors : in Processors_Set; Src_Tasks : in Tasks_Set; Msg : in out Unbounded_String; Result_Tasks : in out Tasks_Set) is A_Task_Result : Periodic_Task_Ptr; My_Task_Iterator_Result : Tasks_Iterator; A_Processor : Generic_Processor_Ptr; My_Processor_Iterator : Processors_Iterator; Temp_Task_Iterator : Tasks_Iterator; Best_Cpu : Processors_Iterator; M : Integer := 1; Best_Fit_Value : Float := 2.0; Best_Fit_Tmp_Value, Tot_Util : Float; First_Task : Boolean := True; Assignable : Boolean; begin Validate_Multiprocessor_Tasks (Src_Processors, Src_Tasks); Msg := To_Unbounded_String (" (") & Lb_See (Current_Language) & To_Unbounded_String ("[9], [10]) "); duplicate (Src_Tasks, Result_Tasks); sort (Result_Tasks, Increasing_Period'Access); reset_iterator (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); -- Zero processor locations -- loop A_Task_Result.cpu_name := To_Unbounded_String (""); exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); next_element (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); end loop; reset_iterator (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); loop reset_iterator (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); -- Loop scans best processor for task to be placed -- loop Temp_Task_Iterator := My_Task_Iterator_Result; -- get CPU data -- reset_iterator (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); M := 1; Tot_Util := 0.0; loop if A_Task_Result.cpu_name = A_Processor.name then M := M + 1; Tot_Util := Tot_Util + Float (A_Task_Result.capacity) / Float (A_Task_Result.period); end if; exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); next_element (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); end loop; My_Task_Iterator_Result := Temp_Task_Iterator; current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); -- test for condition IP -- if First_Task then if Float (A_Task_Result.capacity) / Float (A_Task_Result.period) <= 1.0 then reset_iterator (Src_Processors, Best_Cpu); My_Processor_Iterator := Best_Cpu; First_Task := False; Assignable := True; exit; else Assignable := False; exit; end if; else if Float (A_Task_Result.capacity) / Float (A_Task_Result.period) <= 2.0 * (1.0 / (1.0 + Tot_Util / Float ((M - 1))) ** (M - 1)) - 1.0 then -- Tricky Condition IP testing because mathematics function -- doesn't seem to understand handle -- zero number very well in following check (M := 0 -- happens when processor is empty) -- if M > 1 then if Tot_Util <= Float (M - 1) * (2.0 ** Float (1.0 / Float (M - 1)) - 1.0) then Best_Fit_Tmp_Value := 2.0 * (1.0 / ((1.0 + Tot_Util / Float (M - 1)) ** (M - 1))) - 1.0; if Best_Fit_Tmp_Value < Best_Fit_Value then Best_Fit_Value := Best_Fit_Tmp_Value; Best_Cpu := My_Processor_Iterator; Assignable := True; end if; end if; else Best_Fit_Tmp_Value := 2.0 * (1.0 / (1.0 + Tot_Util / Float (M - 1) ** (M - 1))) - 1.0; if Best_Fit_Tmp_Value < Best_Fit_Value then Best_Fit_Value := Best_Fit_Tmp_Value; Best_Cpu := My_Processor_Iterator; Assignable := True; end if; end if; -- End of tricky testing -- end if; end if; exit when is_last_element (Src_Processors, My_Processor_Iterator); next_element (Src_Processors, My_Processor_Iterator); current_element (Src_Processors, A_Processor, My_Processor_Iterator); end loop; if Assignable then -- save task to best CPU -- current_element (Src_Processors, A_Processor, Best_Cpu); A_Task_Result.cpu_name := A_Processor.name; Assignable := False; Best_Fit_Value := 2.0; else duplicate (Src_Tasks, Result_Tasks); raise No_Such_Processors; end if; exit when is_last_element (Result_Tasks, My_Task_Iterator_Result); next_element (Result_Tasks, My_Task_Iterator_Result); current_element (Result_Tasks, Generic_Task_Ptr (A_Task_Result), My_Task_Iterator_Result); end loop; sort (Result_Tasks, Increasing_Name'Access); end Partition_Best_Fit; procedure Validate_Multiprocessor_Tasks (Src_Processors : in Processors_Set; Src_Tasks : in Tasks_Set) is A_Processor : Generic_Processor_Ptr; My_Processor_Iterator : Processors_Iterator; a_core : core_unit_ptr; begin -- check if tasks are periodic -- reset_iterator (Src_Processors, My_Processor_Iterator); loop current_element (Src_Processors, A_Processor, My_Processor_Iterator); Periodic_Control (Src_Tasks, A_Processor.name); exit when True = is_last_element (Src_Processors, My_Processor_Iterator); next_element (Src_Processors, My_Processor_Iterator); end loop; -- check if processors are rate-monotonic and non pre-emptive -- reset_iterator (Src_Processors, My_Processor_Iterator); loop current_element (Src_Processors, A_Processor, My_Processor_Iterator); a_core:= get_a_core(A_Processor); if a_core.scheduling.scheduler_type /= Rate_Monotonic_Protocol then raise Invalid_Scheduler_Multiprocessors; end if; if A_core.scheduling.preemptive_type = not_preemptive then raise Invalid_Scheduler_Multiprocessors; end if; exit when is_last_element (Src_Processors, My_Processor_Iterator); next_element (Src_Processors, My_Processor_Iterator); end loop; end Validate_Multiprocessor_Tasks; end partitioning_Services;