header
HRRN scheduling algorithm

Tag:
Edit edit   Starstar

Program Information

Name: HRRN scheduling algorithm
Domain: Algorithm
Functionality: Highest Response Ratio Next (HRRN) scheduling algorithm(non-preemptive), which is one of the dynamic priority algorithms.
Input:   The input to HRRN scheduler is a list of processes, each of which has 3 parameters, denoted as $$P(arrival - time, service-time)$$, where $P$ represents the name of the process. Given a source test case $I_s=[P_{s_1}, P_{s_2},\ldots ,P_{s_n}]$, where $n$ is the number of the scheduled processes and $$P_{s_i} = Pi (arrival-time_i, service-time_i)(1\leq i \leq n)$$ represents the information of the  $i^{th}$  process which is waiting to be scheduled.  We use $P_{s_{jc}}$ to denote the corresponding process of $P_{s_j}'$ in $I_s$, and $P_{f_{jc}}$ to denote the corresponding process of $P_{f_j}'$ in $I_f$, where $1\leq jc \leq n$. We use $I_f=[P_{f_1},P_{f_2},\ldots , P_{f_n}]$ to denote the follow-up test case. In order to simplify our illustration,we use the sample $I_s=[P_1(43,39),P_2(1,37),P_3(35,48),P_4(43,49),P_5(O,11),P_6(O,20),P_7(7,27),P_8(36,24), P_9(49,21) ,P_{10}(19,29)]$. 
Output:   The output of the HRRN simulator is the execution sequence of processes, that is, the execution orders of processes. The output of executing HRRN by $I_s$ is $O_s=[P_{s_1}',P_{s_2}',\ldots ,P_{s_n}']$, where $P_{s_i}'(1\leq j \leq n)$ is the name of the $j^{th}$ scheduled process. We use $O_f=[P_{f_1}',P_{f_2}',\ldots ,P_{f_n}']$ to denote the follow-up test case's output. For a real input $I_s$,it's corresponding output is  $O_s=[P_5,P_6,P_7,P_2,P_{10},P_8,P_9,P_1,P_3,P_4]$ 

Reference

   Testing Central Processing Unit Scheduling Algorithms Using Metamorphic Testing https://doi.org/10.1109/ICSESS.2013.6615365 

MR Information

MR1------

Description:
Property:   $I_f$ is constructed by permutating elements of $I_s$ $\Rightarrow$ $O_f=O_s$
Source input:   $I_s$
Source output:   $O_s$
Follow-up input:   $I_f=[P_1(43,39),P_2(1,37),P_8(36,24),P_3(35,48),P_4(43,49),P_6(O,20),P_7(7,27), P_9(49,21) ,P_{10}(19,29),P_5(O,11)]$
Follow-up output:   $O_f=[P_5,P_6,P_7,P_2,P_{10},P_8,P_9,P_1,P_3,P_4]$
Input relation:   $I_f$ is constructed by permutating elements of $I_s$
Output relation:   $O_f=O_s$
Pattern:

MR2------

Description:
Property:   $I_f$ is constructed by delaying the arrival time or increasing the service time of the last scheduled process of $O_s$ in $I_s$ $\Rightarrow$ $O_f=O_s$
Source input:   $I_s$
Source output:   $O_s$
Follow-up input:   $I_f=[P_1(43,39),P_2(1,37),P_3(35,48),P_4(43,59),P_5(O,11),P_6(O,20),P_7(7,27),P_8(36,24), P_9(49,21) ,P_{10}(19,29)]$
Follow-up output:   $O_f=[P_5,P_6,P_7,P_2,P_{10},P_8,P_9,P_1,P_3,P_4]$
Input relation:   increase the service time of $P_4$ to construct $I_f$,that is, $\Rightarrow P_4(43,59)$
Output relation:   $O_f=O_s$
Pattern:

MR3------

Description:
Property:   $I_f$ is constructed based on $I_s$ but with the following changes: (1)randomly choose $P_{s_j}'$  and $P_{s_k}'(1\leq k\leq j \leq n)$ from $O_s$ (2)find their corresponding processes $P_{s_{jc}}$ and $P_{s_{kc}}$ (3)reset the parameters of $P_{s_{jc}}$ such that $P_{s_{jc}}.arrival-time = P_{s_{kc}}.arrival-time - 1$ and $P_{s_{jc}}.service-time = P_{s_{kc}}.service-time - 1$ $\Rightarrow$ $P_{s_{jc}}$ will be scheduled earlier than $P_{s_{kc}}$ in $O_f$ 
Source input:   $I_s$
Source output:   $O_s$ where $P_7$ is scheduled before $P_{10}$
Follow-up input:   $I_f=[P_1(43,39),P_2(1,37),P_3(35,48),P_4(43,59),P_5(O,11),P_6(O,20),P_7(7,27),P_8(36,24), P_9(49,21) ,P_{10}(6,26)]$
Follow-up output:   $O_f=[P_5,P_6,P_10,P_7,P_2,P_8,P_9,P_1,P_3,P_4]$
Input relation:   $I_f$ is constructed by resetting the parameters of $P_{10}$ using that of $P_7$,that is, $\Rightarrow P_{10}(6,26)$
Output relation:   In $O_f$ $P_{10}$ is scheduled before $P_7$
Pattern:

MR4------

Description:
Property:   $I_f$ is constructed based on $I_s$ but with the following changes: (1)randomly choose two processes $P_{s_j}'$ and $P_{s_{j+1}}' (1 \leq j \leq n-1)$ in $O_s$ (2)find $P_{s_{jc}}$ and $P_{s_{(j+1)c}}$ in $I_s$ (3)apply following operations (i)If $P_{s_{jc}}.arrival-time < P_{s_{(j+1)c}}.arrival-time$, then(if $P_{s_{jc}}.service-time \geq P_{s_{(j+1)c}}.service-time$ then swap the arrival time of $P_{s_{jc}} and  P_{s_{(j+1)c}}$, else set $P_{s_{(j+1)c}}.arrival-time = P_{s_{jc}}.arrival-time - 1$, $P_{s_{(j+1)c}}.service-time = P_{s_{jc}}.service-time - 1$) else swap the service time of $P_{s_{jc}}$ and $P_{s_{(j+1)c}}$ $\Rightarrow$ $P_{s_{jc}}$ and $P_{s_{(j+1)c}}$ in $O_f$ is swapped. 
Source input:   $I_s$
Source output:   $O_s$
Follow-up input:   $I_f=[P_1(43,39),P_2(1,27),P_3(35,48),P_4(43,49),P_5(O,11),P_6(O,20),P_7(7,37),P_8(36,24), P_9(49,21) ,P_{10}(19,29)]$
Follow-up output:   $O_f=[P_5,P_6,P_2,P_10,P_7,P_8,P_9,P_1,P_3,P_4]$
Input relation:   $I_f$ is constructed by swapping the service time of $P_7$ and $P_2$
Output relation:   The relative order between $P_7$ and $P_2$ is opposite to that of $O_s$,that is, the relative execution order between these two processes is swapped.
Pattern:

MR5------

Description:
Property:   $I_f$ is constructed by adding a new process with reference to a selected process of $I_s$ as follows:  (1)Adding a process $P$ which arrives at the same time as a selected process $P_{s_i} (l \leq i \leq n)$ while its service time is longer than $P_{s_i}$ Then, $P$ will be scheduled later than $P_{s_i}$ (2)Adding a process $P$ whose service time is the same as the selected process $P_{s_i}(l\leq i \leq n)$ while it arrives later than $P_{s_i}$. Then, $P$ will be scheduled later than $P_{s_i}$. 
Source input:      $I_s$
Source output:      $O_s$
Follow-up input:  $I_{f_1}=[P_1(43,39),P_2(1,37),P_3(35,48),P_4(43,49),P_5(O,11),P_6(O,20),P_7(7,27),P_8(36,24), P_9(49,21) ,P_{10}(19,29),P_{11}(49,30)]$ $I_{f_2}=[P_1(43,39),P_2(1,37),P_3(35,48),P_4(43,49),P_5(O,11),P_6(O,20),P_7(7,27),P_8(36,24), P_9(49,21) ,P_{10}(19,29),P_{11}(50,21)]$   
Follow-up output: $O_{f_1}=[P_5,P_6,P_7,P_2,P_{10},P_8,P_9,[],P_1,[],P_3,[],P_4,[]]$  $O_{f_2}=[P_5,P_6,P_7,P_2,P_{10},P_8,P_9,[],P_1,[],P_3,[],P_4,[]]$ where [] denotes a possible location for $P_{11}$
Input relation: Choose $P_9$,and $I_{f_1}$ is constructed by adding a new process $P_{11}(49,30)$;$I_{f_2}$ is constructed by adding a new process $P_{11}(50,21)$
Output relation: For (1) $P_{11}$ will be scheduled later than $P_9$;For (2) $P_{11}$ will be scheduled later than $P_9$
Pattern:

MR6------

Description:
Property: $I_f$ is constructed by deleting one process from $I_s$,then the execution sequences before the deleted process of $O_s$ will remain the same as those in $O_f$.
Source input: $I_s$
Source output: $O_s$ 
Follow-up input: $I_f=[P_1(43,39),P_2(1,37),P_3(35,48),P_4(43,49),P_5(O,11),P_6(O,20),P_7(7,27),P_9(49,21) ,P_{10}(19,29)]$
Follow-up output: $O_f=[P_5,P_6,P_7,P_2,P_{10},P_9,P_1,P_3,P_4]$
Input relation: $I_f$ is constructed by deleting $P_8$ from $I_s$ 
Output relation: $O_f=O_s-P_8$ where the relative orders between the former five processes keep unchanged. 
Pattern:
Insert title here