Agendamento de CPU de Taxa de Resposta Mais Alta Próxima (HRRN)
Pré-requisito - Programação de CPU
Dados n processos com seus tempos de chegada e tempos de burst, a tarefa é encontrar o tempo médio de espera e o tempo médio de retorno usando o algoritmo de programação HRRN.
O próprio nome indica que precisamos encontrar a taxa de resposta de todos os processos disponíveis e selecionar aquele com a taxa de resposta mais alta. Um processo, uma vez selecionado, será executado até a conclusão.
Critérios - Modo de Razão de Resposta
- Não Preemptivo
Response Ratio = (W + S)/S
Aqui, W é o tempo de espera do processo até o momento e S é o tempo de burst do processo.
Desempenho do HRRN -
- Processos mais curtos são favorecidos.
- Envelhecer sem serviço aumenta a proporção, empregos mais longos podem superar os empregos mais curtos.
Gráfico de Gantt -
Explicação -
- Em t = 0, temos apenas um processo disponível, portanto, A é programado.
- Da mesma forma, em t = 3, temos apenas um processo disponível, então B é programado.
- Agora, em t = 9, temos 3 processos disponíveis, C, D e E. Uma vez que, C, D e E estavam disponíveis após 4, 6 e 8 unidades, respectivamente. Portanto, o tempo de espera para C, D e E são (9 - 4 =) 5, (9 - 6 =) 3 e (9 - 8 =) 1 unidade, respectivamente.
- Usando a fórmula fornecida acima, calculamos as Razões de Resposta de C, D e E, respectivamente, como 2,25, 1,6 e 1,5.
- Claramente, C tem a maior taxa de resposta e por isso é programado
- Em seguida, em t = 13, temos 2 empregos disponíveis D e E.
- As razões de resposta de D e E são 2,4 e 3,5, respectivamente.
- Portanto, o processo E é selecionado em seguida e o processo D é selecionado por último.
Implementação de Agendamento HRRN -
- Insira o número de processos, seus tempos de chegada e tempos de burst.
- Classifique-os de acordo com os horários de chegada.
- A qualquer momento, calcule as taxas de resposta e selecione o processo apropriado a ser programado.
- Calcule o tempo de resposta como tempo de conclusão - tempo de chegada.
- Calcule o tempo de espera como tempo de resposta - tempo de burst.
- O tempo de rotação dividido pelo tempo de burst fornece o tempo de rotação normalizado.
- Some os tempos de espera e de retorno de todos os processos e divida pelo número de processos para obter o tempo médio de espera e de retorno.
Abaixo está a implementação da abordagem acima:
// C++ program for Highest Response Ratio Next (HRRN) Scheduling
#include <bits/stdc++.h>
using namespace std;
// Defining process details
struct process {
char name;
int at, bt, ct, wt, tt;
int completed;
float ntt;
} p[10];
int n;
// Sorting Processes by Arrival Time
void sortByArrival()
{
struct process temp;
int i, j;
// Selection Sort applied
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
// Check for lesser arrival time
if (p[i].at > p[j].at) {
// Swap earlier process to front
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
}
}
}
int main()
{
int i, j, t, sum_bt = 0;
char c;
float avgwt = 0, avgtt = 0;
n = 5;
// predefined arrival times
int arriv[] = { 0, 2, 4, 6, 8 };
// predefined burst times
int burst[] = { 3, 6, 4, 5, 2 };
// Initializing the structure variables
for (i = 0, c = 'A'; i < n; i++, c++) {
p[i].name = c;
p[i].at = arriv[i];
p[i].bt = burst[i];
// Variable for Completion status
// Pending = 0
// Completed = 1
p[i].completed = 0;
// Variable for sum of all Burst Times
sum_bt += p[i].bt;
}
// Sorting the structure by arrival times
sortByArrival();
cout << "Name " << " Arrival Time " << " Burst Time " << " Waiting Time "
<< " TurnAround Time " << " Normalized TT" ;
for (t = p[0].at; t < sum_bt;) {
// Set lower limit to response ratio
float hrr = -9999;
// Response Ratio Variable
float temp;
// Variable to store next processs selected
int loc;
for (i = 0; i < n; i++) {
// Checking if process has arrived and is Incomplete
if (p[i].at <= t && p[i].completed != 1) {
// Calculating Response Ratio
temp = (p[i].bt + (t - p[i].at)) / p[i].bt;
// Checking for Highest Response Ratio
if (hrr < temp) {
// Storing Response Ratio
hrr = temp;
// Storing Location
loc = i;
}
}
}
// Updating time value
t += p[loc].bt;
// Calculation of waiting time
p[loc].wt = t - p[loc].at - p[loc].bt;
// Calculation of Turn Around Time
p[loc].tt = t - p[loc].at;
// Sum Turn Around Time for average
avgtt += p[loc].tt;
// Calculation of Normalized Turn Around Time
p[loc].ntt = ((float)p[loc].tt / p[loc].bt);
// Updating Completion Status
p[loc].completed = 1;
// Sum Waiting Time for average
avgwt += p[loc].wt;
cout<< "\n" << p[loc].name <<"\t" << p[loc].at;
cout << "\t\t" << p[loc].bt <<"\t\t"<< p[loc].wt;
cout <<"\t\t"<< p[loc].tt <<"\t\t"<< p[loc].ntt;
}
cout << "\nAverage waiting time: " << avgwt / n << endl;
cout <<"Average Turn Around time:"<< avgtt / n;
}
//This code is contributed by shivi_Aggarwal// C program for Highest Response Ratio Next (HRRN) Scheduling
#include <stdio.h>
// Defining process details
struct process {
char name;
int at, bt, ct, wt, tt;
int completed;
float ntt;
} p[10];
int n;
// Sorting Processes by Arrival Time
void sortByArrival()
{
struct process temp;
int i, j;
// Selection Sort applied
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
// Check for lesser arrival time
if (p[i].at > p[j].at) {
// Swap earlier process to front
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
}
}
}
void main()
{
int i, j, t, sum_bt = 0;
char c;
float avgwt = 0, avgtt = 0;
n = 5;
// predefined arrival times
int arriv[] = { 0, 2, 4, 6, 8 };
// predefined burst times
int burst[] = { 3, 6, 4, 5, 2 };
// Initializing the structure variables
for (i = 0, c = 'A'; i < n; i++, c++) {
p[i].name = c;
p[i].at = arriv[i];
p[i].bt = burst[i];
// Variable for Completion status
// Pending = 0
// Completed = 1
p[i].completed = 0;
// Variable for sum of all Burst Times
sum_bt += p[i].bt;
}
// Sorting the structure by arrival times
sortByArrival();
printf("\nName\tArrival Time\tBurst Time\tWaiting Time");
printf("\tTurnAround Time\t Normalized TT");
for (t = p[0].at; t < sum_bt;) {
// Set lower limit to response ratio
float hrr = -9999;
// Response Ratio Variable
float temp;
// Variable to store next processs selected
int loc;
for (i = 0; i < n; i++) {
// Checking if process has arrived and is Incomplete
if (p[i].at <= t && p[i].completed != 1) {
// Calculating Response Ratio
temp = (p[i].bt + (t - p[i].at)) / p[i].bt;
// Checking for Highest Response Ratio
if (hrr < temp) {
// Storing Response Ratio
hrr = temp;
// Storing Location
loc = i;
}
}
}
// Updating time value
t += p[loc].bt;
// Calculation of waiting time
p[loc].wt = t - p[loc].at - p[loc].bt;
// Calculation of Turn Around Time
p[loc].tt = t - p[loc].at;
// Sum Turn Around Time for average
avgtt += p[loc].tt;
// Calculation of Normalized Turn Around Time
p[loc].ntt = ((float)p[loc].tt / p[loc].bt);
// Updating Completion Status
p[loc].completed = 1;
// Sum Waiting Time for average
avgwt += p[loc].wt;
printf("\n%c\t\t%d\t\t", p[loc].name, p[loc].at);
printf("%d\t\t%d\t\t", p[loc].bt, p[loc].wt);
printf("%d\t\t%f", p[loc].tt, p[loc].ntt);
}
printf("\nAverage waiting time:%f\n", avgwt / n);
printf("Average Turn Around time:%f\n", avgtt / n);
}# Python3 program for Highest Response Ratio
# Next (HRRN) Scheduling
# Function to sort process by arrival time
def sortByArrival(at, n):
# Selection Sort applied
for i in range(0, n - 1):
for j in range(i + 1, n):
# Check for lesser arrival time
if at[i] > at[j]:
# Swap earlier process to front
at[i], at[j] = at[j], at[i]
# Driver code
if __name__ == '__main__':
sum_bt = 0
avgwt = 0
avgTT = 0
n = 5
completed =[0] * n
waiting_time = [0] * n
turnaround_time = [0] * n
normalised_TT = [0] * n
# Predefined arrival times
arrival_time = [ 0, 2, 4, 6, 8 ]
# Predefined burst times
burst_time = [ 3, 6, 4, 5, 2 ]
process = []
# Initializing the structure variables
for i in range(0, n):
process.append(chr(65 + i))
sum_bt += burst_time[i]
# Sorting the structure by arrival times
sortByArrival(arrival_time, n)
print("Name", "Arrival time",
"Burst time", "Waiting Time",
"Turnaround ", "Normalized TT")
t = arrival_time[0]
while(t < sum_bt):
# Set lower limit to response ratio
hrr = -9999
temp, loc = 0, 0
for i in range(0, n):
# Checking if process has arrived
# and is Incomplete
if arrival_time[i] <= t and completed[i] != 1:
# Calculating Response Ratio
temp = ((burst_time[i] +
(t - arrival_time[i])) /
burst_time[i])
# Checking for Highest Response Ratio
if hrr < temp:
# Storing Response Ratio
hrr = temp
# Storing Location
loc = i
# Updating time value
t += burst_time[loc]
# Calculation of waiting time
waiting_time[loc] = (t - arrival_time[loc] -
burst_time[loc])
# Calculation of Turn Around Time
turnaround_time[loc] = t - arrival_time[loc]
# Sum Turn Around Time for average
avgTT += turnaround_time[loc]
# Calculation of Normalized Turn Around Time
normalised_TT = float(turnaround_time[loc] /
burst_time[loc])
# Updating Completion Status
completed[loc] = 1
# Sum Waiting Time for average
avgwt += waiting_time[loc]
print(process[loc], "\t\t", arrival_time[loc],
"\t\t", burst_time[loc], "\t\t",
waiting_time[loc], "\t\t",
turnaround_time[loc], "\t\t",
"{0:.6f}".format(normalised_TT))
print("Average waiting time: {0:.6f}".format(avgwt / n))
print("Average Turn Around time: {0:.6f}".format(avgTT / n))
# This code is contributed by etcharla revanth raoSaída:
Name Arrival Time Burst Time Waiting Time TurnAround Time Normalized TT A 0 3 0 3 1.000000 B 2 6 1 7 1.166667 C 4 4 5 9 2.250000 E 8 2 5 7 3.500000 D 6 5 9 14 2.800000 Average waiting time:4.000000 Average Turn Around time:8.000000
Este artigo é uma contribuição de Siddhant Bajaj . Se você gosta de GeeksforGeeks e gostaria de contribuir, você também pode escrever um artigo usando write.geeksforgeeks.org ou enviar seu artigo para review-team@geeksforgeeks.org. Veja o seu artigo na página principal do GeeksforGeeks e ajude outros Geeks.
Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima.
Aprenda todos os conceitos do GATE CS com aulas gratuitas ao vivo em nosso canal do youtube.
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva
