------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- Cheddar is a GNU GPL real time scheduling analysis tool. -- This program provides services to automatically check performances -- of real time architectures. -- -- Copyright (C) 2002-2010, by Frank Singhoff, Alain Plantec, Jerome Legrand -- -- The Cheddar project was started in 2002 by -- the LISyC Team, University of Western Britanny. -- -- Since 2008, Ellidiss technologies also contributes to the development of -- Cheddar and provides industrial support. -- -- 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: 523 $ -- $Date: 2012-09-26 15:09:39 +0200 (Wed, 26 Sep 2012) $ -- $Author: fotsing $ ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ with Tasks; use Tasks; with Task_Set; use Task_Set; use Task_Set.Generic_Task_Set; with Resources; use Resources; use Resources.resource_accesses; with Resource_Set; use Resource_Set; use Resource_Set.Generic_Resource_Set; with Buffers; use Buffers; use Buffers.Buffer_Roles_package; with Buffer_Set; use Buffer_Set; use Buffer_Set.Generic_Buffer_Set; with Messages; use Messages; with Message_Set; use Message_Set; use Message_Set.Generic_Message_Set; with Ada.Strings.Unbounded; use Ada.Strings.Unbounded; with unbounded_strings; use unbounded_strings; with Framework_Config; use Framework_Config; with Ada.Numerics.Aux; use Ada.Numerics.Aux; with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random; with Time_Unit_Events; use Time_Unit_Events; use Time_Unit_Events.Time_Unit_Package; with Scheduling_Analysis; use Scheduling_Analysis; with Task_Dependencies; use Task_Dependencies; use Task_Dependencies.Half_Dep_Set; with Ada.Finalization; with indexed_tables; with natural_util; with access_lists; with Unchecked_Deallocation; with primitive_xml_strings; use primitive_xml_strings; with Scheduler_Interface; use Scheduler_Interface; with processor_interface; use processor_interface; package Scheduler is ------------------------------------------------------------- ------------------------------------------------------------- -- Basic type definitions ------------------------------------------------------------- ------------------------------------------------------------- -- Constant to be used when no resource or no dependency are -- present in a project -- No_Resource_Set : Resources_Set; No_Tasks_Dependencies : Tasks_Dependencies; ------------------------------------------------------------- ------------------------------------------------------------- -- The type definitions below are used by schedulers to store -- required information on task/processor/buffers/... in order to -- compute the scheduling ------------------------------------------------------------- ------------------------------------------------------------- -- Information related to the tasks -- type Tcb is tagged record Tsk : Generic_Task_Ptr; Wake_Up_Time : Natural; Rest_Of_Capacity : Natural; Used_Capacity : Natural; Activation : Natural; End_Time : Natural; Used_Cpu : Natural; Task_Seed : State; Suspended : Boolean; -- Give the core unit name on which the task is run -- This is required when a use a multiprocessor scheduler which does -- not allow migration of a job between several cores -- assigned_core_unit : Unbounded_String; -- Is true if the task is already run on a core unit for the -- current time unit already_run_at_current_time : Boolean; end record; type Tcb_Ptr is access all Tcb'Class; type Tcb_Table is array (Tasks_Range) of Tcb_Ptr; procedure Initialize (A_Tcb : in out Tcb; A_Task : Generic_Task_Ptr); -- Information related to the access on shared resources -- type Allocation_Table is array (Natural range 0 .. Max_Tasks_For_A_Resource) of Unbounded_String; type Shared_Resource is tagged record Shared : Generic_Resource_Ptr; Allocated_By : Allocation_Table; Nb_Allocated : Natural := 0; end record; type Shared_Resource_Ptr is access all Shared_Resource'Class; type Shared_Resource_Table is array (Resources_Range) of Shared_Resource_Ptr; -- Information related to messages exchanges -- Messages are data shared between tasks running on different processors -- type Message_Scheduling_Information is record Sended_Message : Generic_Message_Ptr; Send_Time : Natural := 0; end record; type Message_Scheduling_Information_Ptr is access all Message_Scheduling_Information; procedure Free is new Unchecked_Deallocation ( Message_Scheduling_Information, Message_Scheduling_Information_Ptr); procedure Put (M : in Message_Scheduling_Information_Ptr); function Copy (obj : Message_Scheduling_Information_Ptr) return Message_Scheduling_Information_Ptr; function XML_String(obj : in Message_Scheduling_Information_Ptr; level : in natural := 0) return Unbounded_String; package Message_Scheduling_Information_List_Package is new access_lists ( Message_Scheduling_Information, Message_Scheduling_Information_Ptr, Put, Free, Copy, xml_string); use Message_Scheduling_Information_List_Package; subtype Message_Scheduling_Information_List is Message_Scheduling_Information_List_Package.list; subtype Message_Scheduling_Information_Iterator is Message_Scheduling_Information_List_Package.iterator; -- Information related to buffer read/write -- Messages are data shared between tasks running on the same processor -- type Buffer_Scheduling_Information is record Written_Buffer : Buffer_Ptr; Current_Size : Natural := 0; end record; type Buffer_Scheduling_Information_Ptr is access all Buffer_Scheduling_Information; procedure Free is new Unchecked_Deallocation ( Buffer_Scheduling_Information, Buffer_Scheduling_Information_Ptr); procedure Put (M : in Buffer_Scheduling_Information_Ptr); function Copy (obj : Buffer_Scheduling_Information_Ptr) return Buffer_Scheduling_Information_Ptr; function XML_String(obj : in Buffer_Scheduling_Information_Ptr; level : in natural := 0) return Unbounded_String; package Buffer_Scheduling_Information_List_Package is new access_lists ( Buffer_Scheduling_Information, Buffer_Scheduling_Information_Ptr, Put, Free, Copy, xml_string); use Buffer_Scheduling_Information_List_Package; subtype Buffer_Scheduling_Information_List is Buffer_Scheduling_Information_List_Package.list; subtype Buffer_Scheduling_Information_Iterator is Buffer_Scheduling_Information_List_Package.iterator; -- Finally, the type which merge all the information declared -- Above (task, Resources, Buffers, Messages) -- type Scheduling_Information is record Simulation_Length : Natural := 0; Number_Of_Processors : Natural := 0; Number_Of_Address_Spaces : Natural := 0; Tcbs : Tcb_Table; Number_Of_Tasks : Tasks_Range := 0; Shared_Resources : Shared_Resource_Table; Number_Of_Resources : Resources_Range := 0; Sended_Messages : Message_Scheduling_Information_List; Written_Buffers : Buffer_Scheduling_Information_List; With_Specific_Task_Seed : Boolean; Global_Seed : State; end record; procedure Initialize (S : in out Scheduling_Information); ------------------------------------------------------------- ------------------------------------------------------------- -- Abstract scheduler declaration : main entry point -- for scheduling source code ------------------------------------------------------------- ------------------------------------------------------------- type Generic_Scheduler; type Generic_Scheduler_Ptr is access all Generic_Scheduler'Class; type local_scheduler is record scheduler : Generic_Scheduler_Ptr; address_space_name : Unbounded_String; used_cpu : Natural := 0; end record; type local_scheduler_Ptr is access all local_scheduler; type scheduler_range is new Integer range 0 .. Framework_Config.Max_Schedulers; type Scheduler_table is array (scheduler_range) of local_scheduler_Ptr; type Generic_Scheduler is abstract new Ada.Finalization.Controlled with record -- Scheduler parameters : period, priority, capacity, preemptivity, --quantum, ... -- parameters : Scheduling_Parameters; -- Core unit and processor corresponding to this scheduler -- (used to forbid a task capacity to be run on several coreunit -- corresponding_core_unit : Unbounded_String; corresponding_processor : Unbounded_String; -- Does the processor allow task migration between core units ? -- migration_is_allowed : migrations_type; -- Allow the scheduler to know if the previous unit of time was busy -- (for non preemptive scheduling protocols) -- previous_time_unit_was_busy : Boolean := False; -- Last scheduled task -- Previously_Elected : Tasks_Range := Tasks_Range'First; end record; procedure Reset (A_Scheduler : in out Generic_Scheduler'Class); procedure Put (My_Scheduler : in Generic_Scheduler); procedure Put (My_Scheduler : in Generic_Scheduler_Ptr); ------------------------------------------------------------- ------------------------------------------------------------- -- sub-program which can be used in order to access -- scheduler data ------------------------------------------------------------- ------------------------------------------------------------- procedure Set_Preemptive (My_Scheduler : in out Generic_Scheduler'Class; Preempt : in Preemptives_Type); function Get_Preemptive (My_Scheduler : in Generic_Scheduler'Class) return Preemptives_Type; function Get_Preemptive (My_Scheduler : in Generic_Scheduler'Class) return String; function Get_Name (My_Scheduler : in Generic_Scheduler'Class) return Schedulers_Type; function Get_Name (My_Scheduler : in Generic_Scheduler'Class) return Unbounded_String; function Get_Name (My_Scheduler : in Generic_Scheduler_Ptr) return Schedulers_Type; function Get_Name (My_Scheduler : in Generic_Scheduler_Ptr) return Unbounded_String; procedure Set_Quantum (My_Scheduler : in out Generic_Scheduler'Class; Q : in Natural); function Get_Quantum (My_Scheduler : in Generic_Scheduler'Class) return Natural; function Get_Quantum (My_Scheduler : in Generic_Scheduler'Class) return String; function Get_Quantum (My_Scheduler : in Generic_Scheduler'Class) return Unbounded_String; function Copy (A_Scheduler : in Generic_Scheduler) return Generic_Scheduler_Ptr is abstract; ------------------------------------------------------------- ------------------------------------------------------------- -- Exception raised during feasibility test or simulation ------------------------------------------------------------- ------------------------------------------------------------- -- The processor utilization factor have to bel es than 100 percent -- Processor_Utilization_Exceeded : exception; -- The required computation can not be done with such scheduler -- Invalid_Scheduler : exception; -- Raised if during a bound blocking time computation -- resources with different protocols are met -- Other_Resources_Protocol_Found : exception; -- Raised if an invalid resource protocol is found -- Invalid_Protocol : exception; -- Raised if a scheduler parameter has an invalid value -- Invalid_scheduler_parameter : exception; ------------------------------------------------------------- ------------------------------------------------------------- -- Feasiblity tests for a given scheduler -- Most of these sub-programs are declared abstract since -- they have to be provided by the implemented scheduler ------------------------------------------------------------- ------------------------------------------------------------- -- Compute the bound on processor utilization factor that the -- designed can not overflow if task deadlines must be met -- procedure Bound_On_Processor_Utilization (My_Scheduler : in Generic_Scheduler; My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String; Result : in out Double; Msg : in out Unbounded_String) is abstract; -- Apply processor utilization factor tests -- procedure Utilization_Factor_Feasibility_Test (My_Scheduler : in Generic_Scheduler; My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String; Msg : in out Unbounded_String) is abstract; -- Compute for each task its response time -- procedure Compute_Response_Time (My_Scheduler : in Generic_Scheduler; My_Tasks : in out Tasks_Set; Processor_Name : in Unbounded_String; Msg : in out Unbounded_String; Response_Time : out Response_Time_Table) is abstract; -- Compute bound on blocking time of each task -- procedure Compute_Blocking_Time (My_Scheduler : in Generic_Scheduler; My_Tasks : in Tasks_Set; My_Resources : in Resources_Set; Processor_Name : in Unbounded_String; Msg : in out Unbounded_String; Blocking_Time : out Blocking_Time_Table) is abstract; ------------------------------------------------------------- ------------------------------------------------------------- -- Procedure and functions to run a scheduling simulation ------------------------------------------------------------- ------------------------------------------------------------- -- Compute the next time on which the task will be ready to run (task --wakeup time) -- May be overidden by specific scheduler (ie parametric scheduler) -- procedure Compute_Activation_Time (My_Scheduler : in Generic_Scheduler; Si : in out Scheduling_Information; Elected : in Tasks_Range; Value : in out Natural); ---------------------------------------------------------------------------- ------ -- Update data simulation when a task is selected for scheduling -- this sub-program also generates events -- procedure Update_Task_Simulation_Properties_And_Produce_Events (My_Scheduler : in out Generic_Scheduler'Class; Processor_Name : in Unbounded_String; Si : in out Scheduling_Information; My_Dependencies : in Tasks_Dependencies_Ptr; Elected : in Tasks_Range; Result : in out Scheduling_Sequence_Ptr; Current_Time : in Natural; Last_Time : in Natural; With_Offsets : Boolean := True; With_Precedencies : Boolean := True; With_Resources : Boolean := True; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table); ---------------------------------------------------------------------------- ------ -- At scheduling simulation starting time, check that the simulation -- can be done according to the selected scheduler and the task set -- procedure Check_Before_Scheduling (My_Scheduler : in Generic_Scheduler; My_Tasks : in Tasks_Set; Processor_Name : in Unbounded_String) is abstract; ---------------------------------------------------------------------------- ------ -- The following sub-programs initialize the data simulation -- Initialization made by each scheduler (initializations which -- depend on the type of scheduler) -- procedure Specific_Scheduler_Initialization (My_Scheduler : in out Generic_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 abstract; -- Initialization made for each processor -- procedure processor_Initialization (My_Scheduler : in out Generic_Scheduler'Class; Si : in out Scheduling_Information; Processor_Name : in Unbounded_String; My_Tasks : in out Tasks_Set; My_Resources : in out Resources_Set; My_Buffers : in out Buffers_Set; Result : in out Scheduling_Sequence_Ptr; With_Offsets : Boolean; With_Precedencies : Boolean; With_Resources : Boolean; With_Task_Specific_Seed : Boolean := True; Global_Seed_Value : Integer := 0; Predictable_Global_Seed : Boolean := True; Given_Last_Time : in Natural; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table); -- Initialization made for each core unit -- procedure core_unit_Initialization (My_Scheduler : in out Generic_Scheduler'Class; Si : in out Scheduling_Information; Processor_Name : in Unbounded_String; My_Tasks : in out Tasks_Set; My_Resources : in out Resources_Set; My_Buffers : in out Buffers_Set; Result : in out Scheduling_Sequence_Ptr; With_Offsets : Boolean; With_Precedencies : Boolean; With_Resources : Boolean; With_Task_Specific_Seed : Boolean := True; Global_Seed_Value : Integer := 0; Predictable_Global_Seed : Boolean := True; Given_Last_Time : in Natural; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table); ---------------------------------------------------------------------------- ------ -- Choose the task to be run at a given time -- procedure Do_Election (My_Scheduler : in out Generic_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; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table; Elected : in out Tasks_Range; No_Task : in out Boolean) is abstract; ---------------------------------------------------------------------------- ------ -- Sub-programs used to build the scheduling information -- function Build_Tcb (My_Scheduler : in Generic_Scheduler; A_Task : Generic_Task_Ptr) return Tcb_Ptr; function Build_Resource (My_Scheduler : in Generic_Scheduler; A_Resource : Generic_Resource_Ptr) return Shared_Resource_Ptr; -- Perform treatements when we simulation shared resources access : -- allocation of the shared resource, releasing the shared resource -- and checking that the resource can be taken -- procedure Allocate_Resource (My_Scheduler : in out Generic_Scheduler; Si : in out Scheduling_Information; Result : in out Scheduling_Sequence_Ptr; Current_Time : in Natural; A_Tcb : Tcb_Ptr; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table); procedure Release_Resource (My_Scheduler : in out Generic_Scheduler; Si : in out Scheduling_Information; Result : in out Scheduling_Sequence_Ptr; Current_Time : in Natural; A_Tcb : Tcb_Ptr; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table); procedure Check_Resource (My_Scheduler : in out Generic_Scheduler; Si : in out Scheduling_Information; Result : in out Scheduling_Sequence_Ptr; Current_Time : in Natural; A_Tcb : in Tcb_Ptr; Is_Ready : out Boolean; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table); -- Check that the task can be run according to its wake up time offset -- function Check_Offset (A_Tcb : Tcb_Ptr; At_Time : Natural) return Boolean; -- Check that the task can be run to the current core -- according to core migration properties -- function Check_Task_Migration_Amoung_Cores (A_Scheduler : in Generic_Scheduler; A_Tcb : in Tcb_Ptr) return Boolean; -- Check that the task can be run according to its -- tasks precendencies -- function Check_Precedencies (Si : in Scheduling_Information; Deps : Tasks_Dependencies_Ptr; Current_Time : in Natural; A_Tcb : Tcb_Ptr) return Boolean; -- Perform treatements when we simulation messages exchanges : -- send a message to a task, and receive a message from a task -- procedure Send_Message (My_Scheduler : in out Generic_Scheduler; Si : in out Scheduling_Information; Result : in out Scheduling_Sequence_Ptr; Current_Time : in Natural; A_Tcb : Tcb_Ptr; Deps : Tasks_Dependencies_Ptr; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table); procedure Receive_Message (My_Scheduler : in out Generic_Scheduler; Si : in out Scheduling_Information; Result : in out Scheduling_Sequence_Ptr; Current_Time : in Natural; A_Tcb : Tcb_Ptr; Deps : Tasks_Dependencies_Ptr; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table); -- Perform treatements when we simulate buffer access : -- write bytes into a buffer of read bytes from a buffer -- procedure Buffer_Read (My_Scheduler : in out Generic_Scheduler; Si : in out Scheduling_Information; Result : in out Scheduling_Sequence_Ptr; Current_Time : in Natural; A_Tcb : Tcb_Ptr; Deps : Tasks_Dependencies_Ptr; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table); procedure Buffer_Write (My_Scheduler : in out Generic_Scheduler; Si : in out Scheduling_Information; Result : in out Scheduling_Sequence_Ptr; Current_Time : in Natural; A_Tcb : Tcb_Ptr; Deps : Tasks_Dependencies_Ptr; Event_To_Generate : in Time_Unit_Event_Type_Boolean_Table); ------------------------------------------------------------------- ------------------------------------------------------------------- -- Sub program to sort any kind of data managed by schedulers ------------------------------------------------------------------- ------------------------------------------------------------------- Current_Processor_Name : Unbounded_String; function Select_Cpu (Op1 : in Generic_Task_Ptr) return Boolean; function Select_Cpu (Op1 : in Generic_Resource_Ptr) return Boolean; function Select_Cpu (Op1 : in Buffer_Ptr) return Boolean; ------------------------------------------------------------- ------------------------------------------------------------- -- I/O operations ------------------------------------------------------------- ------------------------------------------------------------- -- XML/AADL export of the scheduler properties -- function Export_Aadl_Properties (My_Scheduler : in Generic_Scheduler; Number_Of_Ht : in Natural) return Unbounded_String; function Export_Xml (My_Scheduler : in Generic_Scheduler) return Unbounded_String; -- XML export of the event table -- These sub-programs can be overidden by specific scheduler -- if events must provide specific information. This information -- is carried on by XML attributes -- -- Save scheduling information at simulation time -- function Produce_Running_Task_Event (My_Scheduler : in Generic_Scheduler; A_Task : in Tcb_Ptr) return Time_Unit_Event_Ptr; -- Export XML event table -- function Export_Xml_Event_Write_To_Buffer (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function Export_Xml_Event_Read_From_Buffer (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function Export_Xml_Event_context_switch_overhead (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function Export_Xml_Event_Running_Task (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function Export_Xml_Event_Address_Space_Activation (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function Export_Xml_Event_Task_Activation (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function Export_Xml_Event_Start_Of_Task_Capacity (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function Export_Xml_Event_End_Of_Task_Capacity (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function Export_Xml_Event_Send_Message (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function Export_Xml_Event_Receive_Message (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function Export_Xml_Event_Allocate_Resource (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function Export_Xml_Event_Release_Resource (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function Export_Xml_Event_Wait_For_Resource (My_Scheduler : in Generic_Scheduler; An_Event : in Time_Unit_Event_Ptr) return Unbounded_String; function XML_String (obj : in Generic_Scheduler_Ptr; level : in Natural := 0) return Unbounded_String; procedure Build_Attributes_XML_String (obj : in Generic_Scheduler_Ptr; level : in Natural := 0; result : in out Unbounded_String); end Scheduler;