Introdução
Neste laboratório, aprenderemos como implementar o Algoritmo de Escalonamento Round Robin em C++. O algoritmo de escalonamento Round Robin é um algoritmo preemptivo no qual um processo é executado por uma fatia de tempo fixa, conhecida como quantum de tempo (time quantum). Se o processo concluir sua execução dentro do quantum de tempo, ele é terminado; caso contrário, ele é movido para o final da fila de prontos (ready queue).
Criar um novo arquivo C++
Primeiro, crie um novo arquivo C++ no diretório ~/project. Você pode nomeá-lo round_robin.cpp.
cd ~/project
touch round_robin.cpp
Incluir as bibliotecas necessárias
Inclua as bibliotecas necessárias no arquivo round_robin.cpp.
#include <iostream>
using namespace std;
Definir a função main()
Defina a função main() e inicialize os IDs dos processos, os tempos de burst (burst times), o quantum e o número de processos.
int main()
{
// Process IDs
int processes[] = { 1, 2, 3, 4 };
// Burst time of all processes
int burst_time[] = { 5, 9, 6, 8 };
// Time quantum
int quantum = 2;
// Number of processes
int n = sizeof processes / sizeof processes[0];
return 0;
}
Implementar a função para encontrar o tempo de espera
A função findWaitingTime() é usada para encontrar o tempo de espera para todos os processos. Esta função é definida para iterar sobre os processos de forma round-robin.
void findWaitingTime(int processes[], int n, int bt[], int wt[], int quantum)
{
// Make a copy of burst times bt[] to store remaining
// burst times.
int rem_bt[n];
for (int i = 0; i < n; i++)
rem_bt[i] = bt[i];
int t = 0; // Current time
// Keep traversing processes in round-robin manner
// until all of them are not done.
while (1) {
bool done = true;
// Traverse all processes one by one repeatedly
for (int i = 0; i < n; i++) {
// If burst time of a process is greater than 0
// then only need to process further
if (rem_bt[i] > 0) {
done = false; // There is a pending process
/* If remaining burst time is greater than
quantum then decrease the time slice
from remaining burst time */
if (rem_bt[i] > quantum) {
// Increase the value of t i.e. shows
// how much time a process has been processed
t += quantum;
// Decrease the burst_time of current process
// by quantum
rem_bt[i] -= quantum;
}
/* If remaining burst time is smaller than
or equal to quantum then the remaining
burst time for this process is 0.*/
else {
// Increase the value of t i.e. shows
// how much time a process has been processed
t += rem_bt[i];
// Waiting time is current time minus time
// used by this process
wt[i] = t - bt[i];
// As the process gets fully executed
// make its remaining burst time = 0
rem_bt[i] = 0;
}
}
}
// If all processes are done
if (done == true)
break;
}
}
Implementar a função para encontrar o tempo de retorno (turn around time)
A função findTurnAroundTime() é usada para encontrar o tempo de retorno (turn around time) para todos os processos.
void findTurnAroundTime(int processes[], int n,
int bt[], int wt[], int tat[])
{
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n; i++)
tat[i] = bt[i] + wt[i];
}
Implementar a função para calcular o tempo médio
A função findavgTime() é usada para calcular o tempo médio de espera (average waiting time) e o tempo médio de retorno (average turn around time) para todos os processos.
void findavgTime(int processes[], int n, int bt[],
int quantum)
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;
// Function to find waiting time of all processes
findWaitingTime(processes, n, bt, wt, quantum);
// Function to find turn around time for all processes
findTurnAroundTime(processes, n, bt, wt, tat);
// Display processes along with all details
cout << "Processes "
<< " Burst time "
<< " Waiting time "
<< " Turn around time\n";
// Calculate total waiting time and total turn
// around time
for (int i = 0; i < n; i++) {
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << i + 1 << "\t\t" << bt[i] << "\t "
<< wt[i] << "\t\t " << tat[i] << endl;
}
cout << "Average waiting time = "
<< (float)total_wt / (float)n;
cout << "\nAverage turn around time = "
<< (float)total_tat / (float)n;
}
Chamar a função findavgTime()
Chame a função findavgTime() para calcular o tempo médio de espera (average waiting time) e o tempo médio de retorno (average turn around time) para os processos.
int main()
{
int processes[] = { 1, 2, 3, 4 };
// Burst time of all processes
int burst_time[] = { 5, 9, 6, 8 };
// Time quantum
int quantum = 2;
// Number of processes
int n = sizeof processes / sizeof processes[0];
// Function to find average time
findavgTime(processes, n, burst_time, quantum);
return 0;
}
Para executar o código em um terminal, execute o seguinte comando a partir do diretório ~/project.
g++ round_robin.cpp -o round_robin && ./round_robin
Resumo
Neste laboratório, aprendemos como implementar o Algoritmo de Escalonamento Round Robin em C++. O algoritmo é usado para escalonar processos em um sistema operacional por uma fatia de tempo conhecida como quantum de tempo (time quantum). Também vimos como calcular o tempo médio de espera (average waiting time) e o tempo médio de retorno (average turn around time) para um conjunto de processos.
