------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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 Translate; use Translate; with Buffer_Set; use Buffer_Set; use Buffer_Set.Generic_Buffer_Set; with Resources; use Resources; use Resources.Resource_Accesses; with natural_util; use natural_util; with systems; use systems; package body Scheduling_Analysis.extended.resource_analysis is procedure Blocking_Time_From_Simulation (My_Task : in Generic_Task_Ptr; My_Resources : in Resources_Set; Sched : in Scheduling_Sequence_Ptr; Max : in out Natural; Min : in out Natural; Average : in out Double) is A_Resource : Generic_Resource_Ptr; Resource_Ite : Resources_Iterator; Nb_Blocking_Time, start_time, blocking_time : Natural; use_resource, has_wait : boolean; begin Max := 0; Min := Natural'Last; Average := 0.0; Nb_Blocking_Time := 0; if not is_empty(my_resources) then reset_iterator (My_Resources, Resource_Ite); loop current_element (My_Resources, A_Resource, Resource_Ite); -- Compute blocking time fo a given resource -- use_resource:=false; for i in 0..A_Resource.critical_sections.nb_entries-1 loop if (A_Resource.critical_sections.entries (i).item = My_Task.name) then use_resource:=true; end if; end loop; -- The task use this resource ... make the analysis -- has_wait:=false; if use_resource then for T in 0 .. Sched.nb_entries - 1 loop -- we store wait_for_resource events -- if not has_wait then if (Sched.entries (T).data.type_of_event = Wait_For_Resource) then if (Sched.entries (T).data.wait_for_resource_task.name=my_task.name) and (Sched.entries (T).data.wait_for_resource.name=a_resource.name) then start_time:= Sched.entries (T).item; has_wait:=true; end if; end if; end if; -- We look for an allocate event and then, we compute blocking time -- if (Sched.entries (T).data.type_of_event = allocate_Resource) then if (Sched.entries (T).data.allocate_task.name=my_task.name) and (Sched.entries (T).data.allocate_resource.name=a_resource.name) then if has_wait then -- compute maximum, minimum and average blocking time -- blocking_time := Sched.entries (T).item - start_time; Max := Natural'Max (Max, blocking_time); Min := Natural'Min (Min, blocking_time); Average := Average + Double (blocking_time); Nb_Blocking_Time := Nb_Blocking_Time + 1; has_wait:=false; end if; end if; end if; end loop; end if; exit when is_last_element (My_Resources, Resource_Ite); next_element (My_Resources, Resource_Ite); end loop; end if; if Min = Natural'Last then Min := 0; end if; if Nb_Blocking_Time /= 0 then Average := Average / Double (Nb_Blocking_Time); end if; end Blocking_Time_From_Simulation; -- Data for deadlock analysis -- deadlock_Result : Deadlock_List; function Deadlock_From_Simulation (My_Tasks : in Tasks_Set; My_Resources : in Resources_Set; Processor_Name : in Unbounded_String; Sched : in Scheduling_Sequence_Ptr) return Deadlock_List is -- Variables required to scan the task -- Item : Deadlock_Item_Ptr; A_task : Generic_task_Ptr; My_Iterator : tasks_Iterator; -- Store the event of the resource allocation -- Allocation : Time_Unit_Event_Ptr; at_time : integer:= 0; is_waiting : boolean; -- Index on the scheduling table -- Current_Time : Time_Unit_Range := 0; procedure Perform_Analysis_Of_one_task is begin Current_Time := 0; is_waiting := false; -- First, find an Allocation Event -- loop if (Current_Time >= Sched.nb_entries - 1) then if (is_waiting) then Item := new Deadlock_Item; Item.time := natural(At_Time); Item.task_name := allocation.wait_for_resource_task.name; Item.resource_name := allocation.wait_for_resource.name; add (deadlock_Result, Item); end if; return; end if; if (Sched.entries (Current_Time).data.type_of_event = wait_for_Resource) then if (Sched.entries (Current_Time).data.wait_for_resource_task.name = A_task.name) then if (is_waiting = false) then Allocation := Sched.entries (Current_Time).data; is_waiting:=true; at_time:=Sched.entries (Current_Time).item; end if; end if; end if; if (Sched.entries (Current_Time).data.type_of_event = running_task) then if (Sched.entries (Current_Time).data.running_task.name = A_task.name) then is_waiting:=false; end if; end if; Current_Time := Current_Time + 1; end loop; end Perform_Analysis_Of_one_task; begin reset_iterator (My_tasks, My_Iterator); initialize (deadlock_Result); loop current_element (My_tasks, A_task, My_Iterator); if (Processor_Name = A_task.cpu_name) then Perform_Analysis_Of_One_task; end if; exit when is_last_element (My_tasks, My_Iterator); next_element (My_tasks, My_Iterator); end loop; return deadlock_Result; end Deadlock_From_Simulation; -- Data for priority inversion -- inv_prio_Result : Priority_Inversion_List; inv_prio_Wait_Events : array (Time_Unit_Range) of Time_Unit_Event_Ptr; inv_prio_Wait_Event_Time : array (Time_Unit_Range) of Natural; function Priority_Inversion_From_Simulation (My_Tasks : in Tasks_Set; My_Resources : in Resources_Set; Processor_Name : in Unbounded_String; Sched : in Scheduling_Sequence_Ptr) return Priority_Inversion_List is -- Variables required to scan the resource set -- Item : Priority_Inversion_Item_Ptr; A_Resource : Generic_Resource_Ptr; My_Iterator : Resources_Iterator; -- Store the event of the resource allocation -- Allocation : Time_Unit_Event_Ptr; -- Index on Wait_Events and Indexes tables -- Index : Time_Unit_Range := 0; -- Index on the scheduling table -- Current_Time : Time_Unit_Range := 0; procedure Perform_Analysis_Of_One_Resource is begin Current_Time := 0; -- First, find an Allocation Event -- loop if (Current_Time >= Sched.nb_entries - 1) then return; end if; if (Sched.entries (Current_Time).data.type_of_event = Allocate_Resource) then if (Sched.entries (Current_Time).data.allocate_resource.name = A_Resource.name) then Allocation := Sched.entries (Current_Time).data; exit; end if; end if; Current_Time := Current_Time + 1; end loop; loop Current_Time := Current_Time + 1; -- Search all Wait_For_Resource events upto the next allocation -- if (Current_Time >= Sched.nb_entries - 1) then return; end if; if (Sched.entries (Current_Time).data.type_of_event = Allocate_Resource) then if (Sched.entries (Current_Time).data.allocate_resource.name = A_Resource.name) then -- The next Allocate event is found, stop collecting data -- and do analysis -- -- Check that between the two "Allocate" events when -- the priority of the first allocating task -- is less than -- second one. -- if (Allocation.allocate_task.priority < Sched.entries (Current_Time).data.allocate_task.priority) then declare -- Start time of the priority inversion -- Start_Time : Natural := Sched.entries (Current_Time).item; begin -- look for the start time of the priority inversion -- for Z in reverse 0 .. Index - 1 loop if inv_prio_Wait_Events (Z).wait_for_resource_task.name = Sched.entries (Current_Time).data.allocate_task. name then Start_Time := inv_prio_Wait_Event_Time (Z); end if; end loop; -- Store the detected priority inversion -- if Start_Time < Sched.entries (Current_Time).item then Item := new Priority_Inversion_Item; Item.start_time := Start_Time; Item.end_time := Sched.entries (Current_Time).item; Item.task_name := Sched.entries (Current_Time).data.allocate_task. name; Item.resource_name := Sched.entries (Current_Time).data. allocate_resource.name; add (inv_prio_Result, Item); end if; end; end if; -- Ready for the next priority inversion analysis -- Index := 0; Allocation := Sched.entries (Current_Time).data; end if; end if; if (Sched.entries (Current_Time).data.type_of_event = Wait_For_Resource) then if (Sched.entries (Current_Time).data.wait_for_resource.name = A_Resource.name) then inv_prio_Wait_Events (Index) := Sched.entries (Current_Time).data; inv_prio_Wait_Event_Time (Index) := Sched.entries (Current_Time).item; Index := Index + 1; end if; end if; end loop; end Perform_Analysis_Of_One_Resource; begin reset_iterator (My_Resources, My_Iterator); initialize (inv_prio_Result); loop current_element (My_Resources, A_Resource, My_Iterator); if (Processor_Name = A_Resource.cpu_name) then Perform_Analysis_Of_One_Resource; end if; exit when is_last_element (My_Resources, My_Iterator); next_element (My_Resources, My_Iterator); end loop; return inv_prio_Result; end Priority_Inversion_From_Simulation; end Scheduling_Analysis.extended.resource_analysis;