------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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 Tasks; use Tasks; with Framework_Config; use Framework_Config; with Scheduling_Analysis; use Scheduling_Analysis; with Scheduling_Analysis; use Scheduling_Analysis.Task_Release_Records_Table_Package; with Scheduling_Analysis; use Scheduling_Analysis.Relative_Priority_Records_Table_Package; with integer_util; use integer_util; with Priority_Assignment.Utility; use Priority_Assignment.Utility; with Tasks.Extended; use Tasks.Extended; with Debug; use Debug; with Cache_Set; use Cache_Set; with Integer_Arrays; use Integer_Arrays; with CFG_Nodes.Extended; use CFG_Nodes.Extended; with CFG_Nodes; use CFG_Nodes.CFG_Nodes_Table_Package; with CFG_Nodes; use CFG_Nodes; with Unchecked_Deallocation; with Tables; package body Priority_Assignment.Audsley_OPA_CRPD_Tree is -------------------------------- -- -- -------------------------------- procedure Copy_Task_Release_Records_Table (src : in Task_Release_Records_Table_Ptr; dest : in out Task_Release_Records_Table_Ptr) is a_trr_ptr : Task_Release_Record_Ptr; begin for i in 0..src.Nb_Entries-1 loop a_trr_ptr := copy(src.Entries(i)); add(dest.all,a_trr_ptr); end loop; end Copy_Task_Release_Records_Table; procedure Free_Task_Release_Records_Table (my_table : in out Task_Release_Records_Table_Ptr; free_object : in Boolean := True) is procedure Free_Pointer is new Unchecked_Deallocation ( Task_Release_Records_Table, Task_Release_Records_Table_Ptr); begin if free_object then for I in 0 .. my_table.Nb_Entries - 1 loop free (my_table.Entries(i)); end loop; end if; Free_Pointer (my_table); end Free_Task_Release_Records_Table; procedure Copy_Relative_Priority_Records_Table (src : in Relative_Priority_Records_Table_Ptr; dest : in out Relative_Priority_Records_Table_Ptr) is a_rpr_ptr : Relative_Priority_Record_Ptr; begin for i in 0..src.Nb_Entries-1 loop a_rpr_ptr := copy(src.Entries(i)); add(dest.all,a_rpr_ptr); end loop; end Copy_Relative_Priority_Records_Table; procedure Free_Relative_Priority_Records_Table (my_table : in out Relative_Priority_Records_Table_Ptr; free_object : in Boolean := True) is procedure Free_Pointer is new Unchecked_Deallocation ( Relative_Priority_Records_Table, Relative_Priority_Records_Table_Ptr); begin if free_object then for I in 0 .. my_table.Nb_Entries - 1 loop free (my_table.Entries(i)); end loop; end if; Free_Pointer (my_table); end Free_Relative_Priority_Records_Table; procedure Add_Relative_Priority_Record (a_rprt : in out Relative_Priority_Records_Table; a_rpr : Relative_Priority_Record_Ptr) is flag : Boolean := True; begin if(a_rprt.Nb_Entries > 0) then for i in 0..a_rprt.Nb_Entries-1 loop if(a_rpr.hpt_index = a_rprt.Entries(i).hpt_index AND a_rpr.lpt_index = a_rprt.Entries(i).lpt_index) then flag := false; end if; end loop; end if; if(flag)then Add(a_rprt,a_rpr); end if; end Add_Relative_Priority_Record; -------------------------------- -- -------------------------------- function Compute_CRPD_of_Job_Activation (a_trrt : in out Task_Release_Records_Table_Ptr; time : in Integer; preempting_job_index : in Task_Release_Records_Range) return Integer is number_EUCB : Integer := 0; crpd : Integer := 0; begin for i in 0.. a_trrt.Nb_Entries-1 loop if(a_trrt.Entries(i).release_time < time AND a_trrt.Entries(i).capacity > 0 AND i /= preempting_job_index) then Intersect(arr_a => Task_Release_Record_Ext_Ptr(a_trrt.Entries(i)).UCBs_In_Cache, arr_b => Task_Release_Record_Ext_Ptr(a_trrt.Entries(preempting_job_index)).ECBs, n => number_EUCB); for j in 0..Task_Release_Record_Ext_Ptr(a_trrt.Entries(preempting_job_index)).ECBs.Size - 1 loop Remove_By_Value(Task_Release_Record_Ext_Ptr(a_trrt.Entries(i)).UCBs_In_Cache, Task_Release_Record_Ext_Ptr(a_trrt.Entries(preempting_job_index)).ECBs.Elements(j)); end loop; a_trrt.Entries(i).finish_time := a_trrt.Entries(i).finish_time + number_EUCB; a_trrt.Entries(i).capacity := a_trrt.Entries(i).capacity + number_EUCB; --Capacity of a task release record is REMAINING_CAPACITY a_trrt.Entries(i).finish_time := a_trrt.Entries(i).finish_time + number_EUCB; crpd := crpd + number_EUCB; end if; end loop; return crpd; end Compute_CRPD_of_Job_Activation; procedure Initialize_Next_CRPD_Node (next_crpd_node : in out CRPD_Node_Ptr; a_crpd_node : in CRPD_Node_Ptr; index : in Task_Release_Records_Range; tat : in Task_Activation_Type) is a_rpr : Relative_Priority_Record_Ptr; begin if (tat = PREEMPTION) then next_crpd_node := new CRPD_Node; next_crpd_node.a_rprt := new Relative_Priority_Records_Table; Copy_Relative_Priority_Records_Table(src => a_crpd_node.a_rprt, dest => next_crpd_node.a_rprt); next_crpd_node.a_trrt := new Task_Release_Records_Table; Copy_Task_Release_Records_Table(src => a_crpd_node.a_trrt, dest => next_crpd_node.a_trrt); next_crpd_node.job_index := Integer(index); next_crpd_node.task_name := next_crpd_node.a_trrt.Entries(index).task_name; next_crpd_node.task_index := next_crpd_node.a_trrt.Entries(index).task_index; next_crpd_node.a_trrt.Entries(Task_Release_Records_Range(a_crpd_node.job_index)).finish_time := next_crpd_node.a_trrt.Entries(Task_Release_Records_Range(a_crpd_node.job_index)).finish_time + next_crpd_node.a_trrt.Entries(index).capacity; --Save the implicit relative priority Put_Debug("III-" & To_String(a_crpd_node.task_name) & " - " & a_crpd_node.task_index'Img); Put_Debug("III-" & To_String(next_crpd_node.task_name) & " - " & next_crpd_node.task_index'Img); a_rpr := new Relative_Priority_Record; a_rpr.higher_priority_task := next_crpd_node.a_trrt.Entries(index).task_name; a_rpr.hpt_index := next_crpd_node.a_trrt.Entries(index).task_index; a_rpr.lower_priority_task := a_crpd_node.task_name; a_rpr.lpt_index := a_crpd_node.task_index; Add_Relative_Priority_Record(next_crpd_node.a_rprt.all,a_rpr); elsif (tat = DENY_PREEMPTION) then if(OPTIMIZE_NODES) then a_rpr := new Relative_Priority_Record; a_rpr.higher_priority_task := a_crpd_node.task_name; a_rpr.hpt_index := a_crpd_node.task_index; a_rpr.lower_priority_task := a_crpd_node.a_trrt.Entries(index).task_name; a_rpr.lpt_index := a_crpd_node.a_trrt.Entries(index).task_index; Add_Relative_Priority_Record(a_crpd_node.a_rprt.all,a_rpr); else next_crpd_node := new CRPD_Node; next_crpd_node.a_rprt := new Relative_Priority_Records_Table; Copy_Relative_Priority_Records_Table(src => a_crpd_node.a_rprt, dest => next_crpd_node.a_rprt); next_crpd_node.a_trrt := new Task_Release_Records_Table; Copy_Task_Release_Records_Table(src => a_crpd_node.a_trrt, dest => next_crpd_node.a_trrt); next_crpd_node.job_index := a_crpd_node.job_index; next_crpd_node.task_name := a_crpd_node.task_name; next_crpd_node.task_index := a_crpd_node.task_index; next_crpd_node.crpd_value := 0; --Save the implicit relative priority a_rpr := new Relative_Priority_Record; a_rpr.higher_priority_task := a_crpd_node.task_name; a_rpr.hpt_index := a_crpd_node.task_index; a_rpr.lower_priority_task := next_crpd_node.a_trrt.Entries(index).task_name; a_rpr.lpt_index := next_crpd_node.a_trrt.Entries(index).task_index; Add_Relative_Priority_Record(next_crpd_node.a_rprt.all,a_rpr); end if; elsif (tat = NO_EXECUTING_JOB) then if(OPTIMIZE_NODES) then a_crpd_node.job_index := Integer(index); a_crpd_node.task_name := a_crpd_node.a_trrt.Entries(index).task_name; a_crpd_node.task_index := a_crpd_node.a_trrt.Entries(index).task_index; else next_crpd_node := new CRPD_Node; next_crpd_node.a_rprt := new Relative_Priority_Records_Table; Copy_Relative_Priority_Records_Table(src => a_crpd_node.a_rprt, dest => next_crpd_node.a_rprt); next_crpd_node.a_trrt := new Task_Release_Records_Table; Copy_Task_Release_Records_Table(src => a_crpd_node.a_trrt, dest => next_crpd_node.a_trrt); next_crpd_node.job_index := Integer(index); next_crpd_node.task_name := a_crpd_node.a_trrt.Entries(index).task_name; next_crpd_node.task_index := a_crpd_node.a_trrt.Entries(index).task_index; next_crpd_node.crpd_value := 0; end if; end if; end Initialize_Next_CRPD_Node; procedure Update_Node_CRPD_Interference (a_crpd_node : in out CRPD_Node_Ptr; next_crpd_node : in out CRPD_Node_Ptr; crpd : in Integer) is begin if(crpd > 0) then next_crpd_node.crpd_value := crpd; else next_crpd_node.crpd_value := 0; end if; end Update_Node_CRPD_Interference; -------------------------------- -- -------------------------------- procedure Print_Tree (a_node : in CRPD_Node_Ptr; level : in Unbounded_String; level_n : in Integer := 0; counter : in out Integer) is temp : Unbounded_String; temp_n : Integer; begin temp := level; Append(temp,To_Unbounded_String("--")); temp_n := level_n; temp_n := temp_n + 1; counter:= counter + 1; Put_Debug(counter'Img & "| " & ASCII.HT & temp_n'Img & ASCII.HT & To_String(level) & " " & To_String(a_node.task_name) & " Release:" & a_node.a_trrt.Entries(Task_Release_Records_Range(a_node.job_index)).release_time'Img); Put_Debug(ASCII.HT & ASCII.HT & To_String(level) & " "); for i in 0..a_node.a_trrt.Nb_Entries-1 loop Put_Debug(To_String(a_node.a_trrt.Entries(i).task_name) & " " & a_node.a_trrt.Entries(i).capacity'Img & "| "); end loop; Put_Debug(ASCII.HT & ASCII.HT & To_String(level) & " "); for i in 0..a_node.a_rprt.Nb_Entries-1 loop Put_Debug(a_node.a_rprt.Entries(i).hpt_index'Img & " >" & a_node.a_rprt.Entries(i).lpt_index'Img & "| "); end loop; if(a_node.next_nodes.Nb_Entries < 0) then return; end if; for i in 0..a_node.next_nodes.Nb_Entries-1 loop Print_Tree(CRPD_Node_Ptr(a_node.next_nodes.Entries(i)),temp,temp_n, counter); end loop; end Print_Tree; procedure Get_Number_Of_Node (a_node : in CRPD_Node_Ptr; level : in Unbounded_String; level_n : in Integer := 0; counter : in out Integer) is temp : Unbounded_String; temp_n : Integer; begin --TODO: Check how to pass by value in ADA -- temp := level; Append(temp,To_Unbounded_String("--")); temp_n := level_n; temp_n := temp_n + 1; counter:= counter + 1; if(a_node.next_nodes.Nb_Entries < 0) then return; end if; for i in 0..a_node.next_nodes.Nb_Entries-1 loop Get_Number_Of_Node(CRPD_Node_Ptr(a_node.next_nodes.Entries(i)),temp,temp_n, counter); end loop; end Get_Number_Of_Node; -------------------------------- -- Solving the relative priority -- problem with Warshall Algorithm -------------------------------- function Check_Active_Condition (a_rprt : in Relative_Priority_Records_Table_Ptr; a_trrt : in Task_Release_Records_Table_Ptr; index : in Task_Release_Records_Range; number_of_task : in Integer; job_index : in Task_Release_Records_Range) return Boolean is waiting_jobs : Task_Release_Records_Table_Ptr; warshall_array : Boolean_Arr_2D_Ptr; active_flag : Boolean := True; begin --Find the set of waiting jobs waiting_jobs := new Task_Release_Records_Table; for i in reverse 0..index loop if(a_trrt.Entries(i).capacity>0) then add(waiting_jobs.all,a_trrt.Entries(i)); end if; end loop; --Initialize the array warshall_array := new Boolean_Arr_2D(0..number_of_task-1, 0..number_of_task-1); for i in 0..number_of_task-1 loop for j in 0..number_of_task-1 loop warshall_array(i,j):= false; end loop; end loop; --Set value for the array for i in 0..a_rprt.Nb_Entries-1 loop warshall_array(a_rprt.Entries(i).hpt_index, a_rprt.Entries(i).lpt_index) := True; end loop; --Solving the array warshall_algorithm(warshall_array => warshall_array, size => number_of_task); --Check task activation for i in 0..waiting_jobs.Nb_Entries-1 loop if(warshall_array(waiting_jobs.Entries(i).task_index,a_trrt.Entries(job_index).task_index))then active_flag := False; Free(waiting_jobs); Free(warshall_array); return active_flag; end if; end loop; Free(waiting_jobs); Free(warshall_array); return active_flag; end Check_Active_Condition; procedure Check_Preempting_Condition (a_rprt : in Relative_Priority_Records_Table_Ptr; preempted_task_index : in Integer; preempting_task_index : in Integer; number_of_tasks : in Integer; active_flag : in out Boolean) is warshall_array : Boolean_Arr_2D_Ptr; begin active_flag := TRUE; --Initialize the array warshall_array := new Boolean_Arr_2D(0..number_of_tasks-1, 0..number_of_tasks-1); for i in 0..number_of_tasks-1 loop for j in 0..number_of_tasks-1 loop warshall_array(i,j):= false; end loop; end loop; --Set value for the array for i in 0..a_rprt.Nb_Entries-1 loop warshall_array(a_rprt.Entries(i).hpt_index, a_rprt.Entries(i).lpt_index) := True; end loop; --Solving the array warshall_algorithm(warshall_array => warshall_array, size => number_of_tasks); if(warshall_array(preempted_task_index,preempting_task_index))then active_flag := False; Free(warshall_array); return; end if; Free(warshall_array); end Check_Preempting_Condition; -------------------------------- -- -------------------------------- procedure Check_Active_Task (tDi : in Integer; number_of_task : in Integer; assessing_job_index : in Task_Release_Records_Range; a_node : in out CRPD_Node_Ptr; index : in out Task_Release_Records_Range; -- IMPORTANT: index = a_node.index + 1; time : in Integer; flag : in out Boolean; counter : in out Integer; is_schedulable : in out Boolean) is next_node : CRPD_Node_Ptr; spare_interval : Integer; active_flag : Boolean; new_time : Integer; crpd : Integer := 0; a_rpr : Relative_Priority_Record_Ptr; begin flag := true; -- Output for Check_State procedure, true by default for j in reverse 0..index-1 loop -- Find a job is released but not finished execution if(a_node.a_trrt.Entries(j).capacity > 0) then -- Check: released jobs's capacity > 0 flag := false; active_flag := Check_Active_Condition(a_rprt => a_node.a_rprt, a_trrt => a_node.a_trrt, index => index-1, number_of_task => number_of_task, job_index => j); -- Check: is it possible for the job to be released if (active_flag) then -- Check: ok to release next_node := new CRPD_Node; next_node.a_trrt := new Task_Release_Records_Table; Copy_Task_Release_Records_Table(src => a_node.a_trrt, dest => next_node.a_trrt); next_node.job_index := Integer(j); next_node.task_name := next_node.a_trrt.Entries(j).task_name; next_node.task_index := next_node.a_trrt.Entries(j).task_index; spare_interval := next_node.a_trrt.Entries(index).release_time - time; --Get the spare interval spare_interval. if(next_node.a_trrt.Entries(j).capacity - spare_interval < 0)then new_time := time + next_node.a_trrt.Entries(j).capacity; next_node.a_trrt.Entries(j).capacity := 0; else next_node.a_trrt.Entries(j).capacity := next_node.a_trrt.Entries(j).capacity - spare_interval; new_time := next_node.a_trrt.Entries(index).release_time; end if; next_node.a_rprt := new Relative_Priority_Records_Table; Copy_Relative_Priority_Records_Table(src => a_node.a_rprt, dest => next_node.a_rprt); for k in reverse 0..index-1 loop if(next_node.a_trrt.Entries(k).capacity > 0 AND next_node.a_trrt.Entries(k).task_index /= next_node.a_trrt.Entries(j).task_index) then a_rpr := new Relative_Priority_Record; a_rpr.higher_priority_task := next_node.a_trrt.Entries(j).task_name; a_rpr.hpt_index := next_node.a_trrt.Entries(j).task_index; a_rpr.lower_priority_task := next_node.a_trrt.Entries(k).task_name; a_rpr.lpt_index := next_node.a_trrt.Entries(k).task_index; Add_Relative_Priority_Record(next_node.a_rprt.all,a_rpr); end if; end loop; Fill_Tasks_UCBs_In_Cache(Task_Release_Record_Ext_Ptr(next_node.a_trrt.Entries(j))); ------------------------------------------------ --CRPD computation ------------------------------------------------ if(CRPD_COMPUTATION) then crpd := Compute_CRPD_of_Job_Activation(a_trrt => next_node.a_trrt, time => time, preempting_job_index => j); else crpd := 0; end if; Update_Node_CRPD_Interference(a_crpd_node => a_node, next_crpd_node => next_node, crpd => crpd); Add_Next_CRPD_Node(a_CRPD_Node => a_node, a_next_CRPD_Node => next_node); Compute_CRPD_Tree(tDi => tDi, a_node => next_node, index => index, time => new_time, number_of_task => number_of_task, state => true, counter => counter, is_schedulable => is_schedulable, assessing_job_index => assessing_job_index); if (OPTIMIZE_MEMORY) then Free_Task_Release_Records_Table(next_node.a_trrt); Free_Relative_Priority_Records_Table(next_node.a_rprt); Free(CFG_Node_Ptr(next_node)); end if; end if; end if; end loop; end Check_Active_Task; procedure Compute_Final_State (a_node : in out CRPD_Node_Ptr; number_of_task : in Integer; tDi : in Integer) is time : Integer; C_i : Integer; flag : Boolean := True; active_flag : Boolean := True; begin time := a_node.a_trrt.Entries(a_node.a_trrt.Nb_Entries-1).release_time; while (time < tDi AND flag) loop flag := False; for i in 0..a_node.a_trrt.Nb_Entries-1 loop if(a_node.a_trrt.Entries(i).capacity > 0) then flag := True; active_flag := true; active_flag := Check_Active_Condition(a_rprt => a_node.a_rprt, a_trrt => a_node.a_trrt, index => a_node.a_trrt.Nb_Entries-1, number_of_task => number_of_task, job_index => i); if (active_flag) then C_i := a_node.a_trrt.Entries(i).capacity; a_node.a_trrt.Entries(i).capacity := Integer'Max(0,a_node.a_trrt.Entries(i).capacity-(tDi-time)); time := Integer'Min(tDi,time + C_i); if (time = tDi) then return; end if; end if; end if; end loop; end loop; end Compute_Final_State; -------------------------------- --1. CRPD is computed at preemption point --2. CRPS is computed at resumption point --3. Time call by compute tree: Next job's release time -------------------------------- procedure Compute_CRPD_Tree (tDi : in Integer; number_of_task : in Integer; state : in Boolean := TRUE; index : in Task_Release_Records_Range; -- IMPORTANT: index = a_node.index + 1; assessing_job_index : in Task_Release_Records_Range; counter : in out Integer; a_node : in out CRPD_Node_Ptr; time : in Integer; -- Release time of the job with index: index-1 is_schedulable : in out Boolean) is next_node : CRPD_Node_Ptr; i : Task_Release_Records_Range := index; -- i: the index of the current task release active_flag : Boolean := TRUE; -- use as an output for Check_Preemption_Condition, Check_Active_Condition function flag : Boolean := TRUE; -- use as an output for Check_State procedure time_passed : Integer := 0; crpd : Integer := 0; new_time : Integer := 0; begin counter := counter + 1; if (is_schedulable = FALSE) then return; end if; if (i = a_node.a_trrt.Nb_Entries) then Compute_Final_State(a_node => a_node, number_of_task => number_of_task, tDi => tDi); if(a_node.a_trrt.Entries(assessing_job_index).capacity > 0) then is_schedulable := FALSE; end if; return; end if; if(NOT OPTIMIZE_MEMORY) then Put_Debug("Counter:" & counter'Img & " - " & ASCII.HT); for i in 0..a_node.a_trrt.Nb_Entries-1 loop Put_Debug(To_String(a_node.a_trrt.Entries(i).task_name) & " " & a_node.a_trrt.Entries(i).capacity'Img & " " & a_node.a_trrt.Entries(i).release_time'Img & "| "); end loop; Put_Debug("---"); for i in 0..a_node.a_rprt.Nb_Entries-1 loop Put_Debug(a_node.a_rprt.Entries(i).hpt_index'Img & " >" & a_node.a_rprt.Entries(i).lpt_index'Img & "| "); end loop; Put_Debug(" - Time:" & time'Img); Put_Debug("======"); New_Line; end if; ---------------------------------------------------------- --STEP 0: Check if a task missed its deadline ---------------------------------------------------------- for j in 0..a_node.a_trrt.Nb_Entries-1 loop if (a_node.a_trrt.Entries(j).deadline < time AND a_node.a_trrt.Entries(j).capacity >0) then return; end if; end loop; ---------------------------------------------------------- -- STEP 1: Check if executing job completed before the release time of J_alpha ---------------------------------------------------------- time_passed := (a_node.a_trrt.Entries(i).release_time - time); if(a_node.a_trrt.Entries(Task_Release_Records_Range(a_node.job_index)).capacity - time_passed < 0) then new_time := time + a_node.a_trrt.Entries(Task_Release_Records_Range(a_node.job_index)).capacity; a_node.a_trrt.Entries(Task_Release_Records_Range(a_node.job_index)).capacity := 0; Check_Active_Task(tDi => tDi, a_node => a_node, index => i, time => new_time, flag => flag, number_of_task => number_of_task, counter => counter, is_schedulable => is_schedulable, assessing_job_index => assessing_job_index); if(flag = false) then -- Flag is false when the Check_State find a problem return; end if; else a_node.a_trrt.Entries(Task_Release_Records_Range(a_node.job_index)).capacity := a_node.a_trrt.Entries(Task_Release_Records_Range(a_node.job_index)).capacity - time_passed; end if; ---------------------------------------------------------- -- STEP 2: Check for preemption occurs or not because of the release of job with index i ---------------------------------------------------------- if(a_node.a_trrt.Entries(Task_Release_Records_Range(a_node.job_index)).capacity > 0) then if(a_node.task_name = a_node.a_trrt.Entries(i).task_name) then -- Check: two jobs of a same task - a task missed deadline (D_i <= T_i), stop this branch. return; end if; ------------------------------------------------ -- CASE 1: preemption occurs -- The next node presents the job with index i ------------------------------------------------- Check_Preempting_Condition(a_rprt => a_node.a_rprt, preempted_task_index => a_node.task_index, preempting_task_index => a_node.a_trrt.Entries(i).task_index, number_of_tasks => number_of_task, active_flag => active_flag); -- Check: can job be preempted by next job if (active_flag) then Initialize_Next_CRPD_Node(next_node,a_node,i,PREEMPTION); ------------------------------------------------ --CRPD computation ------------------------------------------------ if(CRPD_COMPUTATION) then crpd := Compute_CRPD_of_Job_Activation(a_trrt => next_node.a_trrt, time => next_node.a_trrt.Entries(i).release_time, preempting_job_index => i); else crpd := 0; end if; Update_Node_CRPD_Interference(a_crpd_node => a_node, next_crpd_node => next_node, crpd => crpd); Add_Next_CRPD_Node(a_CRPD_Node => a_node, a_next_CRPD_Node => next_node); ------------------------------------------------ if(i <= a_node.a_trrt.Nb_Entries-1) then Compute_CRPD_Tree(tDi => tDi, a_node => next_node, index => i+1, time => next_node.a_trrt.Entries(i).release_time, number_of_task => number_of_task, counter => counter, is_schedulable => is_schedulable, assessing_job_index => assessing_job_index); end if; if (OPTIMIZE_MEMORY) then Free_Relative_Priority_Records_Table(next_node.a_rprt); Free_Task_Release_Records_Table(next_node.a_trrt); Free(CFG_Node_Ptr(next_node)); end if; end if; ------------------------------------------------- -- CASE 2: preemption did NOT occurs ------------------------------------------------- Check_Preempting_Condition(a_rprt => a_node.a_rprt, preempted_task_index => a_node.a_trrt.Entries(i).task_index, preempting_task_index => a_node.task_index, number_of_tasks => number_of_task, active_flag => active_flag); -- Check: can job be not preempted by next job if (active_flag) then Initialize_Next_CRPD_Node(next_node,a_node,i,DENY_PREEMPTION); if(OPTIMIZE_NODES) then if(i <= a_node.a_trrt.Nb_Entries-1) then Compute_CRPD_Tree(tDi => tDi, a_node => a_node, index => i+1, time => a_node.a_trrt.Entries(i).release_time, number_of_task => number_of_task, counter => counter, is_schedulable => is_schedulable, assessing_job_index => assessing_job_index); end if; else Add_Next_CRPD_Node(a_CRPD_Node => a_node, a_next_CRPD_Node => next_node); if(i <= a_node.a_trrt.Nb_Entries-1) then Compute_CRPD_Tree(tDi => tDi, a_node => next_node, index => i+1, time => next_node.a_trrt.Entries(i).release_time, number_of_task => number_of_task, counter => counter, is_schedulable => is_schedulable, assessing_job_index => assessing_job_index); end if; end if; if (OPTIMIZE_MEMORY) then if (NOT OPTIMIZE_NODES) then Free_Relative_Priority_Records_Table(next_node.a_rprt); Free_Task_Release_Records_Table(next_node.a_trrt); end if; Free(CFG_Node_Ptr(next_node)); end if; end if; else ------------------------------------------------- -- No active job, no preemption -- THe next node presents the job with index i ------------------------------------------------- Initialize_Next_CRPD_Node(next_node,a_node,i,NO_EXECUTING_JOB); if (OPTIMIZE_NODES) then Compute_CRPD_Tree(tDi => tDi, a_node => a_node, index => i+1, time => a_node.a_trrt.Entries(i).release_time, number_of_task => number_of_task, counter => counter, is_schedulable => is_schedulable, assessing_job_index => assessing_job_index); else Add_Next_CRPD_Node(a_CRPD_Node => a_node, a_next_CRPD_Node => next_node); Compute_CRPD_Tree(tDi => tDi, a_node => next_node, index => i+1, time => next_node.a_trrt.Entries(i).release_time, number_of_task => number_of_task, counter => counter, is_schedulable => is_schedulable, assessing_job_index => assessing_job_index); end if; if (OPTIMIZE_MEMORY) then if (NOT OPTIMIZE_NODES) then Free_Task_Release_Records_Table(next_node.a_trrt); Free_Relative_Priority_Records_Table(next_node.a_rprt); end if; Free(CFG_Node_Ptr(next_node)); end if; end if; ---------------------------------------------------------- end Compute_CRPD_Tree; -------------------------------- -- -------------------------------- procedure Assess_Release_Set (a_trrt : in out Task_Release_Records_Table_Ptr; tDi : in Integer; number_of_task : in Integer := 0; assessing_job_index : in Task_Release_Records_Range; is_schedulable : in out Boolean) is k : Integer; a_node : CRPD_Node_Ptr; level : Unbounded_String; time : Integer := 0; counter : Integer := -1; a_rpr : Relative_Priority_Record_Ptr; begin Put_Debug("Number of Jobs:" & a_trrt.Nb_Entries'Img); k := a_trrt.Entries(assessing_job_index).task_index; Put_Debug("Assess Release Set"); a_node := new CRPD_Node; a_node.job_index := 0; a_node.task_name := a_trrt.Entries(0).task_name; a_node.task_index := a_trrt.Entries(0).task_index; a_node.crpd_value := 0; a_node.a_rprt := new Relative_Priority_Records_Table; a_node.a_trrt := a_trrt; time := a_trrt.Entries(0).release_time; for i in 0..number_of_task-1 loop if(i /= k) then a_rpr := new Relative_Priority_Record; a_rpr.hpt_index := i; a_rpr.lpt_index := k; Add_Relative_Priority_Record(a_node.a_rprt.all,a_rpr); end if; end loop; Compute_CRPD_Tree(tDi => tDi, number_of_task => number_of_task, counter => counter, a_node => a_node, index => 1, time => time, is_schedulable => is_schedulable, assessing_job_index => assessing_job_index); Put_Debug("Counter:" & counter'Img); if(NOT OPTIMIZE_MEMORY) then counter := 0; Put_Debug("======================="); Print_Tree(a_node,level, -1, counter); end if; end Assess_Release_Set; -------------------------------- -- Perform feasibilitty testing with CRPD Interference computed by Tree method -- -------------------------------- procedure OPA_Feasibility_Test_CRPD (priority_level : in Integer; number_of_task : in Integer; i_task : in out Generic_Task_Ptr; my_tasks : in out Tasks_Set; a_tuea : in Task_UCB_ECB_Array_Ptr; is_schedulable : out Boolean) is my_iterator_2 : Tasks_Iterator; j_task : Generic_Task_Ptr; t : Integer; refined_tasks : Tasks_Set; C_i : Integer; T_i : Integer; D_i : Integer; S_i : Integer; P_i : Integer; O_max : Integer := 0; t_start : Integer := 0; counter : Integer := 0; beta_set : Task_Release_Records_Table_Ptr; eta_set : Task_Release_Records_Table_Ptr; a_trr_ext : Task_Release_Record_Ext_Ptr; assessing_job_index : Task_Release_Records_Range; 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 := 1; else j_task.priority := Priority_Range(priority_level); end if; if(j_task.start_time > O_max) then O_max := 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; ------------------------------------------------------------------------ --Print_Task_Set(refined_tasks); ------------------------------------------------------------------------ is_schedulable := True; C_i := i_task.capacity; T_i := Periodic_Task_Ptr(i_task).period; D_i := i_task.deadline; S_i := Integer(Double'Ceiling(Double(O_max)/Double(T_i))) * (T_i) ; P_i := Calculate_Pi(priority_level => priority_level, my_tasks => refined_tasks); t := S_i; counter := 0; Put_Debug("C_i:" & C_i'Img & " T_i:" & T_i'Img & " - D_i:" & D_i'Img & " - S_i:" & S_i'Img & " - P_i:" & P_i'Img); while (t < S_i + P_i) loop Calculate_Task_Release_Records_Table(t_start => t_start, t_end => t, a_task => i_task, my_tasks => refined_tasks, a_tuea => a_tuea, a_trrt => beta_set); assessing_job_index := beta_set.Nb_Entries; a_trr_ext := new Task_Release_Record_Ext; a_trr_ext.task_name := i_task.name; a_trr_ext.capacity := i_task.capacity; a_trr_ext.release_time := t; a_trr_ext.finish_time := t + i_task.capacity; a_trr_ext.deadline := t + i_task.deadline; for i in 0..a_tuea'Length-1 loop if(a_tuea(i).Task_Name = i_task.name) then a_trr_ext.UCBs := a_tuea(i).UCBs; a_trr_ext.ECBs := a_tuea(i).ECBs; a_trr_ext.task_index := a_tuea(i).Task_Index; end if; end loop; a_trr_ext.completed := False; Fill_Tasks_UCBs_In_Cache(a_trr_ext); Add(beta_set.all, Task_Release_Record_Ptr(a_trr_ext)); Calculate_Task_Release_Records_Table(t_start => t, t_end => t + D_i, a_task => i_task, my_tasks => refined_tasks, a_tuea => a_tuea, a_trrt => eta_set); for i in 0..eta_set.Nb_Entries-1 loop Add(beta_set.all,eta_set.Entries(i)); end loop; Free(eta_set); Assess_Release_Set(a_trrt => beta_set, tDi => t+D_i, number_of_task => number_of_task, assessing_job_index => assessing_job_index, is_schedulable => is_schedulable); if(NOT is_schedulable)then return; end if; t_start := t; t := t + T_i; end loop; end OPA_Feasibility_Test_CRPD; end Priority_Assignment.Audsley_OPA_CRPD_Tree;