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.Task_Release_Records_Table_Package; with integer_util; use integer_util; with Tables; with Priority_Assignment.Utility; use Priority_Assignment.Utility; with Priority_Assignment.Audsley_OPA; use Priority_Assignment.Audsley_OPA; with Tasks.Extended; use Tasks.Extended; with Debug; use Debug; with Integer_Arrays; use Integer_Arrays; with Cache_Set; use Cache_Set; with audsley_opa_crpd_test; use audsley_opa_crpd_test; package body Priority_Assignment.Audsley_OPA_CRPD_PT is procedure Compute_Potential_CRPD (i : in Task_Release_Records_Range; a_task : in Generic_Task_Ptr; a_task_ucb_ecb_array_ptr : in Task_UCB_ECB_Array_Ptr; BE_Complexity : in Boolean := FALSE; arr_utility : in out Integer_Array; beta_set : in out Task_Release_Records_Table_Ptr; crpd_total : in out Integer; crpd : out Integer) is size : Integer; npt : Integer; arr_crpds : Integer_Array; arr_eucb : Integer_Array; max_completion : Integer := 0; max_release : Integer; k : Integer; tmp : Integer; tmp_crpd : Integer := 0; crpd_ECB : Integer := 0; ia_sets : IAs_Ptr; max_finish_time : Integer := 0; begin --Put_debug("---"); --Put_debug("Task: " & To_String(beta_set.Entries(i).task_name)); --Put_debug("release time: " & beta_set.Entries(i).release_time'Img); --Put_debug("finish time: " & beta_set.Entries(i).finish_time'Img); size := arr_utility.Size; npt := 0; crpd := 0; Initialize(arr_crpds); for j in 0..i-1 loop if(beta_set.Entries(j).finish_time < beta_set.Entries(i).release_time) then beta_set.Entries(j).completed := true; end if; end loop; max_finish_time := beta_set.Entries(i).finish_time; for j in 0..i-1 loop if (beta_set.Entries(j).task_name /= a_task.name) then max_finish_time := Integer'Max(beta_set.Entries(j).finish_time,max_finish_time); end if; end loop; ---------------------------------------------------------- -- Compute the maximum number of preempted tasks ---------------------------------------------------------- for j in reverse 0..arr_utility.Size - 1 loop if (beta_set.Entries(i).release_time < arr_utility.Elements(j) AND beta_set.Entries(i).release_time >= arr_utility.Elements(0)) then npt := npt + 1; end if; end loop; --Print(arr_utility); -- Put_Line(ASCII.HT & "Task: " & To_String(beta_set.Entries(i).task_name) & " - Release time: " & beta_set.Entries(i).release_time'Img & " - NPT:" & npt'Img); if(npt > 5) then npt := 5; end if; ---------------------------------------------------------- -- Compute the maximum CRPD ---------------------------------------------------------- if (BE_Complexity) then Initialize(ia_sets); --Computation with Binomial Coefficient Complexity --Put_Line(ASCII.HT & ASCII.HT & "- Not completed tasks:"); for j in 0..i-1 loop if(NOT beta_set.Entries(j).completed) then Get_EUCBs(a_task_ucb_ecb_array => a_task_ucb_ecb_array_ptr, preempting_task => beta_set.Entries(i).task_name, preempted_task => beta_set.Entries(j).task_name, arr_eucbs => arr_eucb); Add(ia_sets,arr_eucb); --Put_Line(ASCII.HT & ASCII.HT & To_String(beta_set.Entries(j).task_name)); end if; end loop; crpd := Compute_CRPD_Potential_Preempted(sets => ia_sets, k => npt, n => ia_sets'Length); for j in 0..ia_sets'Length-1 loop Free(ia_sets(j)); end loop; Free(ia_sets); -------------------------------------------------------------------------- else --Put_Line(ASCII.HT & ASCII.HT & "- Not completed tasks:"); for j in 0..i-1 loop if(NOT beta_set.Entries(j).completed) then Check_CCB(a_task_ucb_ecb_array => a_task_ucb_ecb_array_ptr, preempting_task => beta_set.Entries(i).task_name, preempted_task => beta_set.Entries(j).task_name, n_ccb => tmp_crpd); if(tmp_crpd >= 0) then Add(arr_crpds,tmp_crpd); end if; --Put_Line(ASCII.HT & ASCII.HT & To_String(beta_set.Entries(j).task_name)); end if; end loop; Sort_ASC(arr_crpds); for j in 0..npt-1 loop if(arr_crpds.Size-1 - j >= 0) then crpd := crpd + arr_crpds.Elements(arr_crpds.Size-1 - j); end if; end loop; end if; for j in 0..a_task_ucb_ecb_array_ptr'Length-1 loop if (a_task_ucb_ecb_array_ptr(j).Task_Name = beta_set.Entries(i).task_name) then crpd_ECB := a_task_ucb_ecb_array_ptr(j).CRPD_ECB; end if; end loop; if(crpd > crpd_ECB) then crpd := crpd_ECB; end if; crpd_Total := crpd_Total + crpd; for j in 0..i-1 loop if(NOT beta_set.Entries(j).completed) then beta_set.Entries(j).finish_time := beta_set.Entries(j).finish_time + crpd + beta_set.Entries(i).capacity; end if; end loop; ---------------------------------------------------------- -- Compute the array ---------------------------------------------------------- max_release := beta_set.Entries(i).release_time; --The table is sorted by release time, as a result, it is always the release time of the J_i; max_completion := Integer'Max(max_finish_time + crpd, beta_set.Entries(i).finish_time); beta_set.Entries(i).finish_time := max_finish_time + beta_set.Entries(i).capacity; arr_utility.Elements(0) := max_release; --The first element k := 1; --Remove element smaller than release time of J_i while(k < size)loop if(arr_utility.Elements(k) < max_release) then Remove(arr_utility,k); size := arr_utility.Size; else k := k+1; end if; end loop; --Print(arr_utility); for j in 0..i-1 loop if(beta_set.Entries(j).finish_time < max_release OR beta_set.Entries(j).deadline < max_release) then beta_set.Entries(j).completed := true; end if; end loop; size := arr_utility.Size; tmp := arr_utility.Elements(size-1) + beta_set.Entries(i).capacity; --The last element add(arr_utility, tmp); --Print(arr_utility); for j in reverse 2..size-1 loop --Other element of the array arr_utility.Elements(j) := arr_utility.Elements(j-1) + beta_set.Entries(i).capacity; end loop; --Print(arr_utility); for j in 2..arr_utility.Size-1 loop arr_utility.Elements(j) := arr_utility.Elements(j) + crpd; end loop; arr_utility.Elements(1) := max_completion; --The second element --Print(arr_utility); --Put_Line(ASCII.HT & ASCII.HT & "- CRPD:" & crpd'Img); end Compute_Potential_CRPD; procedure Remaining_Interference_CRPD_Upperbound (t_start : in Integer; t : in Integer; L_tTi_i : in Integer; a_task_ucb_ecb_array_ptr : in Task_UCB_ECB_Array_Ptr; BE_Complexity : in Boolean := FALSE; a_task : in Generic_Task_Ptr; my_tasks : in out Tasks_Set; R_t_i : out Integer; r_releases : out Task_Release_Records_Table_Ptr; r_arr_utility : out Integer_Array) is ---------------------------------------------------------- -- Variables of original Remaining Interference computation ---------------------------------------------------------- time : Integer := 0; T_i : Integer := 0; D_i : Integer := 0; t_r : Integer := 0; C : Integer := 0; beta_set : Task_Release_Records_Table_Ptr; ---------------------------------------------------------- -- Variables of CRPD computation ---------------------------------------------------------- arr_utility : Integer_Array; crpd : Integer := 0; crpd_Total : Integer := 0; 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; ----------------------------------------- Calculate_Task_Release_Records_Table(t_start => t_start, t_end => t, a_task => a_task, my_tasks => my_tasks, a_tuea => a_task_ucb_ecb_array_ptr, a_trrt => beta_set); --Put_Line("===Remaining Interference: TTR:"); --Print_Task_Release_Records_Table(beta_set); ----------------------------------------- if(beta_set.Nb_Entries > 0) then Initialize(arr_utility); Add(arr_utility, beta_set.Entries(0).release_time); --Initilize the array Add(arr_utility, beta_set.Entries(0).finish_time); ----------------------------------------- for i in 0..beta_set.Nb_Entries-1 loop ---------------------------------------------------------- -- CRPD ---------------------------------------------------------- if (i>0) then Compute_Potential_CRPD(i => i, a_task => a_task, a_task_ucb_ecb_array_ptr => a_task_ucb_ecb_array_ptr, arr_utility => arr_utility, beta_set => beta_set, crpd_total => crpd_Total, crpd => crpd, BE_Complexity => BE_Complexity); end if; ---------------------------------------------------------- -- Remaining Inteference Computation ---------------------------------------------------------- C := beta_set.Entries(i).capacity + crpd; 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; end if; ----------------------------------------- R_t_i := R_t_i - (t - t_r); if(R_t_i < 0) then R_t_i := 0; end if; ---------------------------------------------------------- -- Pass the remaining release and crpd_utility to Created_Interference ---------------------------------------------------------- for j in 0..beta_set.Nb_Entries-1 loop if(beta_set.Entries(j).finish_time < t_start+D_i) then beta_set.Entries(j).completed := true; end if; end loop; r_releases := new Task_Release_Records_Table; for j in 0..beta_set.Nb_Entries-1 loop if(NOT beta_set.Entries(j).completed) then Add(r_releases.all, beta_set.Entries(j)); end if; end loop; r_arr_utility := arr_utility; end Remaining_Interference_CRPD_Upperbound; procedure Created_Interference_CRPD_Upperbound (t : in Integer; R_t_i : in Integer; a_task_ucb_ecb_array_ptr : in Task_UCB_ECB_Array_Ptr; r_releases : in Task_Release_Records_Table_Ptr; r_arr_utility : in Integer_Array; BE_Complexity : in Boolean := FALSE; a_task : in Generic_Task_Ptr; my_tasks : in out Tasks_Set; K_t_i : out Integer; L_tTi_i : out Integer) is ---------------------------------------------------------- -- Variables of original Created Interference computation ---------------------------------------------------------- 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_Ptr; a_task_release_record : Task_Release_Record_Ptr; finished : Boolean; ---------------------------------------------------------- -- Variables of CRPD computation ---------------------------------------------------------- arr_utility : Integer_Array; crpd : Integer := 0; crpd_Total : Integer := 0; 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; Calculate_Task_Release_Records_Table(t_start => t, t_end => t + D_i, a_task => a_task, my_tasks => my_tasks, a_tuea => a_task_ucb_ecb_array_ptr, a_trrt => eta_set); ---------------------------------------------------------- --Ghost release, used to compute the CRPD caused to the release of the task ---------------------------------------------------------- a_task_release_record := new Task_Release_Record; a_task_release_record.task_name := a_task.name; a_task_release_record.capacity := 0; a_task_release_record.release_time := t; a_task_release_record.finish_time := t + a_task.capacity + R_t_i; a_task_release_record.deadline := t + a_task.deadline; Add(eta_set.all, a_task_release_record); loop finished := true; for j in 0 .. eta_set.Nb_Entries-2 loop if(eta_set.Entries(j+1).release_time < eta_set.Entries(j).release_time) then finished := false; a_task_release_record := eta_set.Entries(j+1); eta_set.Entries(j+1) := eta_set.Entries(j); eta_set.Entries(j) := a_task_release_record; end if; end loop; exit when finished; end loop; --Implement to fix a bug: a release has the same release time with release of the assessing task --if job of assessing task share the same release time with another job, it must have a lower index --2 blocks of this code are needed. for j in 0 .. eta_set.Nb_Entries-2 loop if(eta_set.Entries(j).release_time = eta_set.Entries(j+1).release_time AND eta_set.Entries(j+1).task_name = a_task.name) then a_task_release_record := eta_set.Entries(j+1); eta_set.Entries(j+1) := eta_set.Entries(j); eta_set.Entries(j) := a_task_release_record; end if; end loop; ----------------------------------------- if(eta_set.Nb_Entries > 0) then Initialize(arr_utility); Add(arr_utility, eta_set.Entries(0).release_time); --Initilize the array Add(arr_utility, eta_set.Entries(0).finish_time); --Print(arr_utility); ---------------------------------------------------------- -- Merge the two array ---------------------------------------------------------- for j in 0..r_arr_utility.Size-1 loop if(r_arr_utility.Elements(j) > eta_set.Entries(0).release_time) then Add(arr_utility, r_arr_utility.Elements(j)); end if; end loop; Sort_ASC(arr_utility); ---------------------------------------------------------- -- Merge the two set ---------------------------------------------------------- for j in 0..r_releases.Nb_Entries-1 loop if (NOT r_releases.Entries(j).completed) then Add(eta_set.all, r_releases.Entries(j)); end if; end loop; loop finished := true; for j in 0 .. eta_set.Nb_Entries-2 loop if(eta_set.Entries(j+1).release_time < eta_set.Entries(j).release_time) then finished := false; a_task_release_record := eta_set.Entries(j+1); eta_set.Entries(j+1) := eta_set.Entries(j); eta_set.Entries(j) := a_task_release_record; end if; end loop; exit when finished; end loop; --Implement to fix a bug: a release has the same release time with release of the assessing task --if job of assessing task share the same release time with another job, it must have a lower index for j in 0 .. eta_set.Nb_Entries-2 loop if(eta_set.Entries(j).release_time = eta_set.Entries(j+1).release_time AND eta_set.Entries(j+1).task_name = a_task.name) then a_task_release_record := eta_set.Entries(j+1); eta_set.Entries(j+1) := eta_set.Entries(j); eta_set.Entries(j) := a_task_release_record; end if; end loop; --Put_Line("===Created Interference: TTR:"); --Print_Task_Release_Records_Table(eta_set); ----------------------------------------- for i in r_releases.Nb_Entries+1..eta_set.Nb_Entries-1 loop --We added one ghost release, so it is r_releases.Nb_Entries -1 + 1 ---------------------------------------------------------- -- CRPD ---------------------------------------------------------- Compute_Potential_CRPD(i => i, a_task => a_task, a_task_ucb_ecb_array_ptr => a_task_ucb_ecb_array_ptr, arr_utility => arr_utility, beta_set => eta_set, crpd_total => crpd_Total, crpd => crpd, BE_Complexity => BE_Complexity); ---------------------------------------------------------- -- K_t_i = CRPD ---------------------------------------------------------- C := eta_set.Entries(i).capacity + crpd; --Add the CRPD to the capacity of job 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; end if; ----------------------------------------- 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; ----------------------------------------- --Put_Line("crpd_Total:" & crpd_Total'Img); --Put_Line(""); end Created_Interference_CRPD_Upperbound; procedure OPA_Feasibility_Test_CRPD_Upperbound (priority_level : in Integer; a_task_ucb_ecb_array_ptr : in Task_UCB_ECB_Array_Ptr; BE_Complexity : in Boolean := FALSE; 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; index : Integer := 0; r_releases : Task_Release_Records_Table_Ptr; r_arr_utility : Integer_Array; begin Refine_Offset(a_task => i_task, my_tasks => my_tasks, refined_tasks => refined_tasks); --Put_Line("===REFINED TASK SETS:"); --Print_Task_Set(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 := 0; while (t < S_i + P_i) loop index := index + 1; Remaining_Interference_CRPD_Upperbound(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, a_task_ucb_ecb_array_ptr => a_task_ucb_ecb_array_ptr, r_releases => r_releases, r_arr_utility => r_arr_utility, BE_Complexity => BE_Complexity); Created_Interference_CRPD_Upperbound(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, a_task_ucb_ecb_array_ptr => a_task_ucb_ecb_array_ptr, r_releases => r_releases, r_arr_utility => r_arr_utility, BE_Complexity => BE_Complexity); --Put_Line(index'Img & ":Remaining I:" & R_t_i'Img & " - Created I:" & K_t_i'Img & " - Capacity:" & i_task.capacity'Img & " - L_tTi_i:" & L_tTi_i'Img & " - Deadline:" & i_task.deadline'Img & " - S_i:" & S_i'Img & " - P_i:" & P_i'Img); if (C_i + R_t_i + K_t_i > D_i) then --Put_Line(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_CRPD_Upperbound; end Priority_Assignment.Audsley_OPA_CRPD_PT;