------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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 Text_IO; use Text_IO; with Ada.Strings.Unbounded; use Ada.Strings.Unbounded; with Ada.Strings.Bounded; use Ada.Strings.Bounded; with unbounded_strings; use unbounded_strings; with Framework_Config; use Framework_Config; with Tasks; use Tasks; with Offsets; use Offsets.Offsets_Table_Package; with Scheduling_Analysis; use Scheduling_Analysis.Task_Release_Records_Table_Package; with Scheduling_Analysis; use Scheduling_Analysis; with Sets; with Priority_Assignment; use Priority_Assignment; with Priority_Assignment.Utility; use Priority_Assignment.Utility; with integer_util; use integer_util; with Systems; use Systems; with Cache_Set; use Cache_Set; with Priority_Assignment.Audsley_OPA_CRPD_PT; use Priority_Assignment.Audsley_OPA_CRPD_PT; with Priority_Assignment.Audsley_OPA_CRPD_Tree; use Priority_Assignment.Audsley_OPA_CRPD_Tree; with Caches; use Caches; with Debug; use Debug; package body Priority_Assignment.Audsley_OPA is procedure Check_Input_Data (my_tasks : in Tasks_Set) is a_task : Generic_Task_Ptr; my_iterator : Tasks_Iterator; begin reset_iterator (my_tasks, my_iterator); loop current_element (my_tasks, a_task, my_iterator); if(a_task.task_type /= Periodic_Type)then raise Task_Must_Be_Periodic; end if; -- TODO: check START_TIME -- if(a_task.offsets.Nb_Entries <= 0) then -- raise Offset_Must_Be_Defined; -- end if; exit when is_last_element (my_tasks, my_iterator); next_element (my_tasks, my_iterator); end loop; end Check_Input_Data; procedure Remaining_Interference (t_start : in Integer; t : in Integer; L_tTi_i : in Integer; a_task : in out Generic_Task_Ptr; my_tasks : in out Tasks_Set; R_t_i : out Integer) is time : Integer := 0; T_i : Integer := 0; D_i : Integer := 0; t_r : Integer := 0; C : Integer := 0; beta_set : Task_Release_Records_Table; begin T_i := Periodic_Task_Ptr(a_task).period; D_i := a_task.deadline; ----------------------------------------- time := t - T_i + D_i; R_t_i := L_tTi_i; ----------------------------------------- Initialize(beta_set); Calculate_Task_Release_Records_Table(t_start => t_start, t_end => t, a_task => a_task, my_tasks => my_tasks, a_task_release_records_table => beta_set); ----------------------------------------- for i in 0..beta_set.Nb_Entries-1 loop C := beta_set.Entries(i).capacity; t_r := beta_set.Entries(i).release_time; if(t_r > time + R_t_i) then R_t_i := 0; end if; if(t_r > time AND R_t_i /= 0) then R_t_i := R_t_i + C - (t_r - time); else R_t_i := R_t_i + C; end if; time := t_r; end loop; ----------------------------------------- R_t_i := R_t_i - (t - t_r); if(R_t_i < 0) then R_t_i := 0; end if; end Remaining_Interference; procedure Created_Interference (t : in Integer; R_t_i : in Integer; a_task : in out Generic_Task_Ptr; my_tasks : in out Tasks_Set; K_t_i : out Integer; L_tTi_i : out Integer) is T_i : Integer := 0; D_i : Integer := 0; t_r : Integer := 0; C : Integer := 0; next_free : Integer; total_created : Integer; eta_set : Task_Release_Records_Table; begin T_i := Periodic_Task_Ptr(a_task).period; D_i := a_task.deadline; ----------------------------------------- next_free:= R_t_i + t; K_t_i := 0; total_created := R_t_i; ----------------------------------------- Initialize(eta_set); Calculate_Task_Release_Records_Table(t_start => t, t_end => t + D_i, a_task => a_task, my_tasks => my_tasks, a_task_release_records_table => eta_set); ----------------------------------------- for i in 0..eta_set.Nb_Entries-1 loop C := eta_set.Entries(i).capacity; t_r := eta_set.Entries(i).release_time; total_created := total_created + C; if (next_free < t_r) then next_free := t_r; end if; K_t_i := K_t_i + Integer'Min(t + D_i - next_free,C); next_free := Integer'Min(next_free + C, t + D_i); end loop; --This is an implementation which was not explained in the paper --In the next release, the remaining interference will be computed --with the time variable start from: time := t - T_i + D_i; --so, we substract the Integer'Max(D_i, R_t_i); L_tTi_i := total_created - K_t_i - Integer'Max(D_i, R_t_i); if(L_tTi_i < 0)then L_tTi_i := 0; end if; end Created_Interference; procedure OPA_Feasibility_Test (priority_level : in Integer; i_task : in out Generic_Task_Ptr; my_tasks : in out Tasks_Set; is_schedulable : out Boolean) is my_iterator_2 : Tasks_Iterator; j_task : Generic_Task_Ptr; t : Integer; refined_tasks : Tasks_Set; R_t_i : Integer :=0; K_t_i : Integer :=0; C_i : Integer; T_i : Integer; D_i : Integer; S_i : Integer; P_i : Integer; O_max : Integer := 0; L_tTi_i : Integer :=0; t_start : Integer := 0; begin Refine_Offset(a_task => i_task, my_tasks => my_tasks, refined_tasks => refined_tasks); --Assign priority to tasks, the checking task has lowest priority level. --Also find the O_max i_task.priority := Priority_Range(priority_level); reset_iterator (refined_tasks, my_iterator_2); loop current_element (refined_tasks, j_task, my_iterator_2); if(j_task.name /= i_task.name) then j_task.priority := Priority_Range'Last; else j_task.priority := Priority_Range(priority_level); end if; if(j_task.start_time > O_max) then O_max := Integer(j_task.start_time); end if; exit when is_last_element (refined_tasks, my_iterator_2); next_element (refined_tasks, my_iterator_2); end loop; ------------------------------------------------------------------------ is_schedulable := True; C_i := i_task.capacity; T_i := Periodic_Task_Ptr(i_task).period; D_i := i_task.deadline; S_i := Integer(Float'Ceiling(Float(O_max)/Float(T_i))) * (T_i) ; P_i := Calculate_Pi(priority_level => priority_level, my_tasks => refined_tasks); t := S_i; while (t < S_i + P_i) loop R_t_i := 0; K_t_i := 0; Remaining_Interference(t_start => t_start, t => t, L_tTi_i => L_tTi_i, a_task => i_task, my_tasks => refined_tasks, R_t_i => R_t_i); Created_Interference(t => t, R_t_i => R_t_i, a_task => i_task, my_tasks => refined_tasks, K_t_i => K_t_i, L_tTi_i => L_tTi_i); Put_Debug("Remaining I:" & R_t_i'Img & " - Created I:" & K_t_i'Img & " - Capacity:" & i_task.capacity'Img & " - Deadline:" & i_task.deadline'Img & " - P_i:" & P_i'Img); if (C_i + R_t_i + K_t_i > D_i) then Put_Debug(To_String(i_task.name) & " Unschedulable with priority level: "& priority_level'Img); is_schedulable := False; exit; end if; t_start := t; t := t + T_i; end loop; end OPA_Feasibility_Test; procedure OPA (my_tasks : in out Tasks_Set) is delta_set : Tasks_Set; my_iterator : Tasks_Iterator; a_task : Generic_Task_Ptr; temp_task : Generic_Task_Ptr; n : Integer := 1; unassigned : Boolean; is_schedulable : Boolean; begin duplicate(src => my_tasks, dest => delta_set); n := Integer(delta_set.get_number_of_elements); for j in 1..n loop unassigned := True; Sort(delta_set,Decreasing_Period_Deadline'Access); reset_iterator (delta_set, my_iterator); loop current_element (delta_set, a_task, my_iterator); OPA_Feasibility_Test(priority_level => j, i_task => a_task, my_tasks => delta_set, is_schedulable => is_schedulable); if(is_schedulable) then Put_Debug("Assign priority level:" & j'Img & " to task: " & To_String(a_task.name) & ASCII.LF & "---"); Delete(delta_set,a_task); temp_task := Search_Task(My_Tasks => my_tasks, Name => a_task.name); temp_task.priority := Priority_Range(j); unassigned := False; exit; end if; exit when is_last_element (delta_set, my_iterator); next_element (delta_set, my_iterator); end loop; if(unassigned) then raise NO_FEASIBLE_PRIORITY_ASSIGNMENT_EXCEPTION; end if; end loop; end OPA; --------------------------------------- -- --------------------------------------- procedure Set_Priority_According_To_Audsley_OPA (My_Tasks : in out Tasks_Set; Processor_Name : in Unbounded_String := empty_string) is Iterator1 : Tasks_Iterator; Task1 : Generic_Task_Ptr; Iterator2 : Tasks_Iterator; Task2 : Generic_Task_Ptr; Current_Prio : Priority_Range := 1; Tmp : Tasks_Set; begin if Processor_Name = empty_string then duplicate (My_Tasks, Tmp); else Current_Processor_Name := Processor_Name; select_and_copy (My_Tasks, Tmp, Select_Cpu'Access); end if; Periodic_Control (Tmp, Processor_Name); Check_Input_Data(Tmp); -- Assign priorities -- OPA(Tmp); -- Copy resulting task objects in My_Tasks -- reset_iterator (Tmp, Iterator1); loop current_element (Tmp, Task1, Iterator1); reset_iterator (My_Tasks, Iterator2); loop current_element (My_Tasks, Task2, Iterator2); if (Task2.name = Task1.name) then Task2.priority := Task1.priority; end if; exit when Task2.name = Task1.name; exit when is_last_element (My_Tasks, Iterator2); next_element (My_Tasks, Iterator2); end loop; exit when is_last_element (Tmp, Iterator1); next_element (Tmp, Iterator1); end loop; free (Tmp); end Set_Priority_According_To_Audsley_OPA; end Priority_Assignment.Audsley_OPA;