Encontre a ordem de execução de determinados N processos no agendamento Round Robin
Neste artigo, você aprenderá como encontrar a ordem de execução para os N processos fornecidos no algoritmo Round Robin Scheduling. Mas antes de começar com o código, vamos entender um pouco como funciona esse algoritmo.
Round Robin Scheduling é um algoritmo popular de escalonamento de CPU usado em sistemas operacionais para alocar tempo de CPU para vários processos de maneira justa e eficiente. Neste blog, exploraremos como funciona o agendamento round-robin, suas vantagens e desvantagens, e forneceremos um exemplo para ajudá-lo a entender melhor o conceito.
O que é agendamento Round Robin?
Round Robin Scheduling é um algoritmo de agendamento preemptivo onde cada processo recebe um intervalo de tempo fixo ou quantum para ser executado. O escalonador da CPU aloca o tempo da CPU aos processos em ordem circular, daí o nome 'round robin'. Depois que um processo esgota seu intervalo de tempo, ele é interrompido e adicionado ao final da fila de processos prontos. O próximo processo na fila recebe então a CPU para seu intervalo de tempo.
A fatia de tempo ou quantum para cada processo é geralmente pequena, normalmente entre 10 a 100 milissegundos. A vantagem de um intervalo de tempo pequeno é que cada processo obtém uma quantidade razoável de tempo de CPU e a CPU é utilizada de forma eficiente alternando entre processos com frequência.
Cenário
Para entender como funciona o agendamento Round Robin, vamos considerar um exemplo. Suponha que temos quatro processos que precisam ser executados:
-
Processo 1: Requer 6 unidades de tempo de CPU
Processo 2: Requer 4 unidades de tempo de CPU
Processo 3: Requer 2 unidades de tempo de CPU
Processo 4: Requer 8 unidades de tempo de CPU
Assumiremos que o quantum de tempo para o algoritmo Round Robin Scheduling está definido como 3 unidades de tempo. No início do processo de agendamento, todos os quatro processos são adicionados à fila de prontos na ordem em que chegaram:
Ready queue: [Process 1, Process 2, Process 3, Process 4]
O algoritmo de escalonamento então começa a executar os processos de maneira cíclica, dando a cada processo um quantum de tempo de 3 unidades:
Tempo 0: O processo 1 começa a ser executado (requer 3 unidades de tempo de CPU)
Tempo 3: O processo 2 começa a ser executado (requer 3 unidades de tempo de CPU)
Tempo 6: O processo 3 começa a ser executado (requer 2 unidades de tempo de CPU)
Tempo 8: O processo 1 retoma a execução (requer 3 unidades de tempo de CPU)
-
Tempo 11: O processo 4 começa a ser executado (requer 3 unidades de tempo de CPU)
Tempo 14: O processo 2 retoma a execução (requer 1 unidade de tempo de CPU)
Tempo 15: Processo 1 termina a execução
Tempo 15: Processo 3 retoma a execução (requer 1 unidade de tempo de CPU)
Tempo 16: Processo 2 termina a execução
Tempo 16: O processo 4 retoma a execução (requer 3 unidades de tempo de CPU)
Tempo 19: Processo 3 termina a execução
Tempo 19: O processo 4 retoma a execução (requer 2 unidades de tempo de CPU)
Tempo 21: Processo 4 termina a execução
Process Queue: P1 P2 P3 P1 P4 P2 P1 P3 P2 P4 P3 P4 P4
Como você pode ver no exemplo, cada processo recebe um quantum de tempo de 3 unidades, independentemente de quanto tempo de CPU ele requer para ser concluído. Depois que um processo completa seu quantum de tempo, ele é antecipado e movido para o final da fila de processos prontos, onde espera até que seja sua vez de executar novamente.
Pseudo-código
Vamos dar uma olhada no pseudocódigo para implementar o agendamento round-robin. Aqui criamos uma função chamada round_robin() e variáveis como "waiting_time", "turnaround_time", "remaining", "current", "order_of_execution" e "ready_queue" são inicializadas pela função. Depois que todas as operações forem realizadas, um loop é iniciado.
A função adiciona todos os processos que chegaram no horário atual à fila de prontos ao longo de cada iteração do loop. O primeiro processo na fila de prontos é então executado pelo quantum de tempo ou até ser concluído, o que ocorrer primeiro.
Se o processo não terminar dentro do quantum de tempo, ele será adicionado novamente à fila de prontos. Se terminar, são calculados o tempo de espera e o tempo de resposta.
Após a execução de todos os processos, a função calcula o tempo médio de espera e o tempo de resposta e retorna a ordem de execução como um array.
function round_robin(processes, quantum):
//Initialize variables
n = length of processes
waiting_time = an array of n elements, initialized to 0
turnaround_time = an array of n elements, initialized to 0
remaining_time = an array of n elements, initialized to the CPU burst time of each process
current_time = 0
order_of_execution = an empty array
ready_queue = an empty array
index = 0
//Loop until all processes are executed
while true:
//Add all processes that have arrived at the current time to the ready queue
for i from index to n-1:
if processes[i].arrival_time <= current_time:
add i to ready_queue
increment index
//Break the loop if all processes have been executed
if the ready_queue is empty and the sum of remaining_time is 0:
break
// Execute the first process in the ready queue
if the ready_queue is not empty:
process_index = the first element in ready_queue
remove the first element from ready_queue
add process_index to order_of_execution
if remaining_time[process_index] > quantum:
increment current_time by quantum
decrement remaining_time[process_index] by quantum
add process_index to ready_queue
else:
increment current_time by remaining_time[process_index]
set waiting_time[process_index] to current_time - processes[process_index].burst_time
set remaining_time[process_index] to 0
set turnaround_time[process_index] to current_time - processes[process_index].arrival_time
else:
increment current_time by 1
// Calculate average waiting time and turnaround time
avg_waiting_time = sum of waiting_time divided by n
avg_turnaround_time = sum of turnaround_time divided by n
// Return the order of execution and average waiting/turnaround time
return order_of_execution, avg_waiting_time, avg_turnaround_time
Implementação
Aqui você pode encontrar a implementação do pseudocódigo acima em Python e Java
Exemplo de Python
def round_robin(processes, quantum):
# Initialize variables
n = len(processes)
waiting_time = [0] * n
turnaround_time = [0] * n
remaining_time = [processes[i][1] for i in range(n)]
current_time = 0
order_of_execution = []
ready_queue = []
index = 0
# Loop until all processes are executed
while True:
# Add all processes that have arrived at the current time to the ready queue
for i in range(index, n):
if processes[i][0] <= current_time:
ready_queue.append(i)
index += 1
# Break the loop if all processes have been executed
if not ready_queue and sum(remaining_time) == 0:
break
# Execute the first process in the ready queue
if ready_queue:
process_index = ready_queue.pop(0)
order_of_execution.append(process_index)
if remaining_time[process_index] > quantum:
current_time += quantum
remaining_time[process_index] -= quantum
ready_queue.append(process_index)
else:
current_time += remaining_time[process_index]
waiting_time[process_index] = current_time - processes[process_index][1]
remaining_time[process_index] = 0
turnaround_time[process_index] = current_time - processes[process_index][0]
else:
current_time += 1
# Calculate average waiting time and turnaround time
avg_waiting_time = sum(waiting_time) / n
avg_turnaround_time = sum(turnaround_time) / n
return order_of_execution, avg_waiting_time, avg_turnaround_time
processes = [(0, 5), (1, 3), (2, 8), (3, 6)]
time_quantum = 2
order_of_execution, avg_waiting_time, avg_turnaround_time = round_robin(processes, time_quantum)
print("Order of execution:", order_of_execution)
print("Average waiting time:", avg_waiting_time)
print("Average turnaround time:", avg_turnaround_time)
Saída
Este código produzirá a ordem de execução dos processos, juntamente com o tempo médio de espera e o tempo médio de resposta para o algoritmo Round Robin Scheduling com o quantum de tempo determinado. Observe que este é apenas um exemplo de implementação e pode precisar ser modificado para diferentes casos de uso ou requisitos.
Order of execution: [0, 0, 1, 2, 0, 3, 1, 2, 3, 2, 3, 2]
Average waiting time: 10.25
Average turnaround time: 14.25
Exemplo Java
import java.util.*;
class Process {
int pid; // process ID
int arrival_time; // arrival time of process
int burst_time; // CPU burst time of process
Process(int pid, int arrival_time, int burst_time) {
this.pid = pid;
this.arrival_time = arrival_time;
this.burst_time = burst_time;
}
}
public class RoundRobinScheduling {
//Driver method
public static void main(String[] args) {
Process[] processes = new Process[] {
new Process(1, 0, 10),
new Process(2, 3, 5),
new Process(3, 5, 8),
new Process(4, 6, 3),
new Process(5, 8, 6)
};
// Time quantum
int quantum = 2;
// Run Round Robin Scheduling algorithm
int[] order_of_execution = round_robin(processes, quantum);
// Print order of execution
System.out.println("Order of Execution: " + Arrays.toString(order_of_execution));
}
//method to implement round-robin cpu scheduling
public static int[] round_robin(Process[] processes, int quantum) {
// Initialize variables
int n = processes.length;
int[] waiting_time = new int[n];
int[] turnaround_time = new int[n];
int[] remaining_time = new int[n];
for (int i = 0; i < n; i++) {
remaining_time[i] = processes[i].burst_time;
}
int current_time = 0;
List<Integer> order_of_execution = new ArrayList<Integer>();
Queue<Integer> ready_queue = new LinkedList<Integer>();
int index = 0;
// Loop until all processes are executed
while (true) {
// Add all processes that have arrived at the current time to the ready queue
for (int i = index; i < n; i++) {
if (processes[i].arrival_time <= current_time) {
ready_queue.add(i);
index++;
}
}
// Break the loop if all processes have been executed
if (ready_queue.isEmpty() && Arrays.stream(remaining_time).sum() == 0) {
break;
}
// Execute the first process in the ready queue
if (!ready_queue.isEmpty()) {
int process_index = ready_queue.remove();
order_of_execution.add(process_index);
if (remaining_time[process_index] > quantum) {
current_time += quantum;
remaining_time[process_index] -= quantum;
ready_queue.add(process_index);
} else {
current_time += remaining_time[process_index];
waiting_time[process_index] = current_time - processes[process_index].burst_time - processes[process_index].arrival_time;
remaining_time[process_index] = 0;
turnaround_time[process_index] = current_time - processes[process_index].arrival_time;
}
} else {
current_time++;
}
}
// Convert order of execution from list to array
int[] order_of_execution_arr = new int[order_of_execution.size()];
for (int i = 0; i < order_of_execution.size(); i++) {
order_of_execution_arr[i] = order_of_execution.get(i);
}
// Print average waiting time and turnaround time
float avg_waiting_time = Arrays.stream(waiting_time).sum() / (float) n;
float avg_turnaround_time = Arrays.stream(turnaround_time).sum() / (float) n;
System.out.println("Average Waiting Time: " + avg_waiting_time);
System.out.println("Average Turnaround Time: " + avg_turnaround_time);
// Return order of execution
return order_of_execution_arr;
}
}
Saída
Average Waiting Time: 15.0
Average Turnaround Time: 21.4
Order of Execution: [0, 0, 0, 1, 0, 2, 3, 1, 4, 0, 2, 3, 1, 4, 2, 4, 2]
Conclusão
Round Robin Scheduling é um algoritmo popular de escalonamento de CPU usado em sistemas operacionais para alocar tempo de CPU para vários processos de maneira justa e eficiente. É um algoritmo de escalonamento preemptivo onde cada processo recebe um intervalo de tempo fixo ou quantum para ser executado.
O agendamento Round Robin garante que cada processo receba uma parcela justa do tempo de CPU e que a CPU seja utilizada de forma eficiente, alternando entre processos com frequência. No entanto, o agendamento Round Robin pode causar alguma sobrecarga devido à frequente alternância de contexto entre processos e pode resultar em tempos de espera mais longos para alguns processos.