header

HRRN(Highest Response Ratio Next) : Deciding which process should be allocated CPU time when there are more than one process waiting and competing the resources.
Tag:
Edit edit   Starstar

Program Information

Name: HRRN(Highest Response Ratio Next)
Domain: Algorithm
Functionality: Deciding which process should be allocated CPU time when there are more than one process waiting and competing the resources.
Input:
     $I(P_{s_{1}},P_{s_{1}},\cdots,P_{s_n})$:where n is the number of the scheduled processes and $P_{s_i}=P_i(arrived-time_i,service-time_i)(1 \le i \le n)$ presents the information of the $i^{th}$ process which is waiting to be scheduled.(Type:Set) In order to simplify our illustration, we would use the previous sample input I as their common source test case $I_s$, that is, $I_s= [P_{1}(43,39), P_{2}(1,37), P_{3}(35,48), P_{4}(43,49), P_{5}(0,11), P_{6}(0,20), P_{7}(7,27), P_{8}(36,24), P_{9}(49,21), P_{10}(19,29)]$.
Output:
     $O(P'_{s_{1}},P'_{s_{2}},\cdots,P'_{s_n},)$:where $P'_{s_j}(1 \le j \le n)$ is the name of the $j^{th}$ scheduled process, and we use $P_{jc}$ to denote the corresponding process of $P'_j$ in I.(Type: Set)

Reference

          Techniques for Testing Scientific Programs Without an Oracle http://dx.doi.org/10.1109/SECSE.2013.6615099

MR Information


MR1


    Source input: $I_s$ ; Source output: $O_s$
    Follow-up input: $I_f$ ; Follow-up output: $O_f$
    Input relation: $I_f=Permutating elements of I_s$
    Output relation: $O_f=O_s$

MR2


    Source input: $I_s$ ; Source output: $O_s$
    Follow-up input: $I_f$ ; Follow-up output: $O_f$
    Input relation: $I_f$=Delaying the arrival time or increasing the service time of the last scheduled process of $O_s$ in $I_s$
    Output relation: $O_f=O_s$

MR3


    Source input: $I_s$ ; Source output: $O_s$
    Follow-up input: $I_f$ ; Follow-up output: $O_f$
    Input relation: $I_f$ is constructed based on $I_s$ but with the following changes: randomly choose $P'_{s_j}$ and $P'_{s_k} (1 \le k \le j \le n)$ from $O_s$ find their corresponding process $P_{s_{jc}}$ and $P_{s_{kc}}$ reset the parameters of $P_{s_{jc}}$ such that $P_{s_{jc}.arrival_time=P_{s_{kc}.arrival_time-1$, $P_{s_{jc}.service_time=P_{s_{kc}.service_time-1$.
    Output relation: $P_{s_{jc}}$ will be scheduled earlier than$P_{s_{kc}}$ in $O_f$, while it is opposite in $O_s$.

MR4


    Source input: $I_s$ ; Source output: $O_s$
    Follow-up input: $I_f$ ; Follow-up output: $O_f$
    Input relation: $I_f$ is constructed based on $I_s$ but with the following changes: randomly choose any two process $P'_{s_j}$ and $P'_{s_{j+1}} (1 \le j \le n)$ from $O_s$ find their corresponding process $P_{s_{jc}}$ and $P_{s_{(j+1)c}}$ in $I_s$ apply following operations: If $P_{s_{jc}}.arrival-time < P_{s_{(j+1)c}}.arrival -time$, Then (if $P_{s_{jc}}.service-time \ge 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}}$.
    Output relation: The order between$P_{s_{jc}}$ and $P_{s_{(j+1)c}}$ in $O_f$ is opposite to .that of $O_s$.

MR5


    Source input: $I_s$ ; Source output: $O_s$
    Follow-up input: $I_f$ ; Follow-up output: $O_f$
    Input relation: $I_f$ is constructed by adding a new process P which arrives at the same time as a selected process $P_{s_i} (1 \le i \le n)$ while its service time is longer than $P_{s_i}$ or adding a process P whose service time is the same as the selected process $P_{s_i} (1 \le i \le n)$ while it arrives later than $P_{s_i} $.
    Output relation: P will be scheduled later than $P_{s_i} $.

MR6


    Source input: $I_s$ ; Source output: $O_s$
    Follow-up input: $I_f$ ; Follow-up output: $O_f$
    Input relation: $I_f$ = Deleting one process from $I_s$
    Output relation: The execution sequences before the deleted process of $O_s$ will remain the same as those in $O_f$.

Related

Insert title here