Programa C++ para o Algoritmo de Escalonamento FCFS

Introdução

Neste laboratório, implementaremos o Algoritmo de Escalonamento First Come First Serve (FCFS) usando C++. FCFS é o algoritmo de escalonamento de CPU mais simples que aloca a CPU aos processos na ordem em que eles a solicitam. O processo que chega primeiro na fila de prontos é servido primeiro.

Este algoritmo é fácil de entender e implementar, mas pode não fornecer desempenho ideal em termos de tempo médio de espera. Ao final deste laboratório, você entenderá como o algoritmo FCFS funciona e será capaz de calcular métricas importantes como tempo de espera e tempo de retorno (turnaround time) para os processos.

Entendendo FCFS e Criando a Estrutura do Programa

First Come First Serve (FCFS) é um algoritmo de escalonamento não preemptivo onde os processos são executados na ordem em que chegam na fila de prontos. Nesta etapa, criaremos nosso arquivo de programa e configuraremos a estrutura básica.

Vamos começar criando um novo arquivo C++:

1. Abra a interface WebIDE e navegue até o painel do explorador de arquivos
2. Clique com o botão direito no painel do explorador e selecione "New File" (Novo Arquivo)
3. Nomeie o arquivo fcfs.cpp e pressione Enter

Agora, vamos adicionar os arquivos de cabeçalho necessários e a declaração de namespace ao nosso programa:

#include <iostream>
#include <iomanip> // Para saída formatada

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    return 0;
}

Este código configura a estrutura básica do nosso programa com:

• #include <iostream> - Para operações de entrada/saída
• #include <iomanip> - Para formatar a tabela de saída
• using namespace std; - Para usar o namespace padrão
• Uma função main() com uma exibição de título

Vamos compilar e executar o programa para garantir que tudo esteja configurado corretamente:

g++ fcfs.cpp -o fcfs
./fcfs

Você deve ver a seguinte saída:

FCFS Scheduling Algorithm Implementation
----------------------------------------

Isso confirma que nossa estrutura básica do programa está funcionando corretamente. Na próxima etapa, implementaremos a funcionalidade para inserir os detalhes do processo.

Implementando a Funcionalidade de Entrada de Processos

Nesta etapa, implementaremos a funcionalidade para coletar informações sobre os processos a serem escalonados. Para o escalonamento FCFS, precisamos saber:

1. O número de processos
2. O tempo de burst (burst time) para cada processo (tempo de execução exigido por cada processo)

Vamos modificar nosso arquivo fcfs.cpp para incluir essa funcionalidade:

#include <iostream>
#include <iomanip> // Para saída formatada

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Declaração de variáveis
    int n;                  // Número de processos
    int burst_time[20];     // Array para armazenar o tempo de burst de cada processo

    // Obter o número de processos do usuário
    cout << "\nDigite o número de processos (máximo 20): ";
    cin >> n;

    // Validação da entrada
    if (n <= 0 || n > 20) {
        cout << "Número inválido de processos. Por favor, insira um valor entre 1 e 20." << endl;
        return 1;
    }

    // Obter o tempo de burst para cada processo
    cout << "\nDigite o Tempo de Burst para cada processo:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Processo P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Validação da entrada para o tempo de burst
        if (burst_time[i] <= 0) {
            cout << "O tempo de burst deve ser um inteiro positivo. Por favor, reinicie o programa." << endl;
            return 1;
        }
    }

    // Exibir os dados inseridos
    cout << "\nProcesso\tTempo de Burst" << endl;
    cout << "--------------------" << endl;
    for (int i = 0; i < n; i++) {
        cout << "P" << i + 1 << "\t" << burst_time[i] << endl;
    }

    return 0;
}

Vamos analisar o que adicionamos:

1. Variáveis para armazenar o número de processos (n) e o tempo de burst para cada processo (burst_time[20]).
2. Solicitações de entrada para coletar o número de processos e o tempo de burst para cada processo.
3. Validação da entrada para garantir que o número de processos esteja dentro de uma faixa razoável (1-20) e que os tempos de burst sejam positivos.
4. Uma exibição em tabela para mostrar os dados inseridos para verificação.

Vamos compilar e executar nosso programa atualizado:

g++ fcfs.cpp -o fcfs
./fcfs

Quando você executar o programa, será solicitado que você insira o número de processos e seus tempos de burst. Tente inserir os seguintes dados:

3
5
9
4

Isso representa 3 processos com tempos de burst de 5, 9 e 4 unidades de tempo, respectivamente. Você deve ver uma saída semelhante a:

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time
--------------------
P1      5
P2      9
P3      4

Isso confirma que nossa funcionalidade de entrada está funcionando corretamente. Na próxima etapa, calcularemos o tempo de espera e o tempo de retorno (turnaround time) para cada processo.

Calculando o Tempo de Espera e o Tempo de Retorno

Nesta etapa, calcularemos duas métricas importantes para cada processo:

1. Tempo de Espera (WT): O tempo que um processo espera na fila de prontos antes de obter tempo de CPU.
2. Tempo de Retorno (TAT): O tempo total decorrido desde a submissão do processo até a conclusão.

Vamos entender como esses são calculados em FCFS:

• Para o primeiro processo (P1), o tempo de espera é sempre 0 (ele começa imediatamente).
• Para os processos subsequentes, o tempo de espera é a soma dos tempos de burst de todos os processos anteriores.
• O tempo de retorno para cada processo é a soma de seu tempo de burst e tempo de espera.

Agora, vamos modificar nosso arquivo fcfs.cpp para adicionar esses cálculos:

#include <iostream>
#include <iomanip> // Para saída formatada

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Declaração de variáveis
    int n;                      // Número de processos
    int burst_time[20];         // Array para armazenar o tempo de burst de cada processo
    int waiting_time[20];       // Array para armazenar o tempo de espera de cada processo
    int turnaround_time[20];    // Array para armazenar o tempo de retorno de cada processo
    int total_waiting_time = 0;
    int total_turnaround_time = 0;

    // Obter o número de processos do usuário
    cout << "\nDigite o número de processos (máximo 20): ";
    cin >> n;

    // Validação da entrada
    if (n <= 0 || n > 20) {
        cout << "Número inválido de processos. Por favor, insira um valor entre 1 e 20." << endl;
        return 1;
    }

    // Obter o tempo de burst para cada processo
    cout << "\nDigite o Tempo de Burst para cada processo:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Processo P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Validação da entrada para o tempo de burst
        if (burst_time[i] <= 0) {
            cout << "O tempo de burst deve ser um inteiro positivo. Por favor, reinicie o programa." << endl;
            return 1;
        }
    }

    // Calcular o tempo de espera para cada processo
    waiting_time[0] = 0;    // O primeiro processo tem tempo de espera 0

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Adicionar os tempos de burst de todos os processos anteriores
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calcular o tempo de retorno para cada processo e os tempos totais
    cout << "\nProcesso\tTempo de Burst\tTempo de Espera\tTempo de Retorno" << endl;
    cout << "----------------------------------------------------" << endl;

    for (int i = 0; i < n; i++) {
        turnaround_time[i] = burst_time[i] + waiting_time[i];
        total_waiting_time += waiting_time[i];
        total_turnaround_time += turnaround_time[i];

        cout << "P" << i + 1 << "\t" << burst_time[i] << "\t\t"
             << waiting_time[i] << "\t\t" << turnaround_time[i] << endl;
    }

    return 0;
}

Vamos entender o que adicionamos:

1. Dois novos arrays: waiting_time[20] e turnaround_time[20] para armazenar os tempos de espera e retorno para cada processo.
2. Variáveis para rastrear o tempo total de espera e o tempo total de retorno.
3. Cálculos para o tempo de espera:
   • O primeiro processo tem um tempo de espera de 0.
   • Para cada processo subsequente, o tempo de espera é a soma dos tempos de burst de todos os processos anteriores.
4. Cálculos para o tempo de retorno:
   • Para cada processo, tempo de retorno = tempo de burst + tempo de espera.
5. Uma tabela formatada para exibir os resultados.

Vamos compilar e executar nosso programa atualizado:

g++ fcfs.cpp -o fcfs
./fcfs

Tente inserir os mesmos dados de antes:

3
5
9
4

Você deve ver uma saída semelhante a:

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time      Waiting Time    Turnaround Time
----------------------------------------------------
P1      5               0               5
P2      9               5               14
P3      4               14              18

Vamos analisar os resultados:

• P1: Tempo de espera = 0, Tempo de retorno = 5 (seu tempo de burst)
• P2: Tempo de espera = 5 (tempo de burst de P1), Tempo de retorno = 14 (5 + 9)
• P3: Tempo de espera = 14 (tempos de burst de P1 + P2), Tempo de retorno = 18 (14 + 4)

Isso confirma que nossos cálculos de tempo de espera e tempo de retorno estão funcionando corretamente. Na próxima etapa, calcularemos os tempos médios e exibiremos os resultados finais.

Calculando Tempos Médios e Exibindo Resultados Finais

Nesta etapa final, calcularemos o tempo médio de espera e o tempo médio de retorno para todos os processos. Essas médias são métricas importantes para avaliar a eficiência de um algoritmo de escalonamento.

Vamos modificar nosso arquivo fcfs.cpp para adicionar esses cálculos e completar nosso programa:

#include <iostream>
#include <iomanip> // Para saída formatada

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Declaração de variáveis
    int n;                      // Número de processos
    int burst_time[20];         // Array para armazenar o tempo de burst de cada processo
    int waiting_time[20];       // Array para armazenar o tempo de espera de cada processo
    int turnaround_time[20];    // Array para armazenar o tempo de retorno de cada processo
    int total_waiting_time = 0;
    int total_turnaround_time = 0;
    float avg_waiting_time = 0.0;
    float avg_turnaround_time = 0.0;

    // Obter o número de processos do usuário
    cout << "\nDigite o número de processos (máximo 20): ";
    cin >> n;

    // Validação da entrada
    if (n <= 0 || n > 20) {
        cout << "Número inválido de processos. Por favor, insira um valor entre 1 e 20." << endl;
        return 1;
    }

    // Obter o tempo de burst para cada processo
    cout << "\nDigite o Tempo de Burst para cada processo:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Processo P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Validação da entrada para o tempo de burst
        if (burst_time[i] <= 0) {
            cout << "O tempo de burst deve ser um inteiro positivo. Por favor, reinicie o programa." << endl;
            return 1;
        }
    }

    // Calcular o tempo de espera para cada processo
    waiting_time[0] = 0;    // O primeiro processo tem tempo de espera 0

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Adicionar os tempos de burst de todos os processos anteriores
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calcular o tempo de retorno para cada processo e os tempos totais
    cout << "\nProcesso\tTempo de Burst\tTempo de Espera\tTempo de Retorno" << endl;
    cout << "----------------------------------------------------" << endl;

    for (int i = 0; i < n; i++) {
        turnaround_time[i] = burst_time[i] + waiting_time[i];
        total_waiting_time += waiting_time[i];
        total_turnaround_time += turnaround_time[i];

        cout << "P" << i + 1 << "\t" << burst_time[i] << "\t\t"
             << waiting_time[i] << "\t\t" << turnaround_time[i] << endl;
    }

    // Calcular o tempo médio de espera e o tempo médio de retorno
    avg_waiting_time = (float)total_waiting_time / n;
    avg_turnaround_time = (float)total_turnaround_time / n;

    // Exibir os resultados com duas casas decimais
    cout << fixed << setprecision(2);
    cout << "\nTempo Médio de Espera: " << avg_waiting_time << " unidades de tempo" << endl;
    cout << "Tempo Médio de Retorno: " << avg_turnaround_time << " unidades de tempo" << endl;

    // Representação visual do cronograma FCFS (gráfico de Gantt em texto)
    cout << "\nGráfico de Gantt:" << endl;
    cout << " ";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i]; j++) {
            cout << "--";
        }
    }
    cout << endl << "|";

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i] - 1; j++) {
            cout << " ";
        }
        cout << "P" << i + 1;
        for (int j = 0; j < burst_time[i] - 1; j++) {
            cout << " ";
        }
        cout << "|";
    }

    cout << endl << " ";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i]; j++) {
            cout << "--";
        }
    }

    cout << endl;
    cout << "0";
    int current_time = 0;
    for (int i = 0; i < n; i++) {
        current_time += burst_time[i];
        for (int j = 0; j < burst_time[i] * 2 - 1; j++) {
            cout << " ";
        }
        if (current_time < 10) cout << " ";
        cout << current_time;
    }
    cout << endl;

    return 0;
}

Vamos entender o que adicionamos:

1. Duas novas variáveis: avg_waiting_time e avg_turnaround_time para armazenar os tempos médios.
2. Cálculos para os tempos médios:
   • Tempo médio de espera = Tempo total de espera / Número de processos
   • Tempo médio de retorno = Tempo total de retorno / Número de processos
3. Saída formatada para exibir os tempos médios com duas casas decimais.
4. Um gráfico de Gantt simples baseado em texto para visualizar o cronograma FCFS:
   • Cada processo é representado por seu ID (P1, P2, etc.)
   • A largura de cada bloco de processo é proporcional ao seu tempo de burst
   • Marcadores de tempo são mostrados na parte inferior

Vamos compilar e executar nosso programa final:

g++ fcfs.cpp -o fcfs
./fcfs

Tente inserir os mesmos dados de antes:

3
5
9
4

Você deve ver uma saída semelhante a:

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time      Waiting Time    Turnaround Time
----------------------------------------------------
P1      5               0               5
P2      9               5               14
P3      4               14              18

Average Waiting Time: 6.33 time units
Average Turnaround Time: 12.33 time units

Gantt Chart:
 --------------------
|   P1    |    P2    |  P3  |
 --------------------
0         5         14     18

Analisando os resultados:

• Tempo Médio de Espera: (0 + 5 + 14) / 3 = 6.33 unidades de tempo
• Tempo Médio de Retorno: (5 + 14 + 18) / 3 = 12.33 unidades de tempo

O gráfico de Gantt representa visualmente como os processos são escalonados ao longo do tempo:

• P1 é executado do tempo 0 a 5
• P2 é executado do tempo 5 a 14
• P3 é executado do tempo 14 a 18

Isso completa nossa implementação do algoritmo de escalonamento FCFS. Você pode experimentar com diferentes números de processos e tempos de burst para ver como isso afeta o tempo médio de espera e o tempo de retorno.

Resumo

Neste laboratório, implementamos com sucesso o algoritmo de escalonamento de CPU First Come First Serve (FCFS) usando C++. Aqui estão os principais conceitos e habilidades que você aprendeu:

1. Fundamentos do Algoritmo FCFS: Compreensão de como os processos são escalonados na ordem em que chegam.

2. Cálculo de Métricas de Desempenho:

   • Tempo de Espera (Waiting Time): O tempo que um processo espera antes do início da execução
   • Tempo de Retorno (Turnaround Time): O tempo total desde a submissão até a conclusão
   • Tempo Médio de Espera e Tempo Médio de Retorno: Indicadores-chave de desempenho para algoritmos de escalonamento

3. Conceitos de Programação C++:

   • Arrays para armazenar informações do processo
   • Loops para cálculos iterativos
   • Operações de entrada/saída com validação
   • Saída formatada para melhor apresentação de dados

4. Técnicas de Visualização: Criação de um gráfico de Gantt baseado em texto para visualizar a linha do tempo de escalonamento

O algoritmo FCFS é simples de entender e implementar, mas nem sempre fornece o desempenho ideal. Ele pode levar ao "efeito comboio" (convoy effect), onde processos curtos ficam presos esperando atrás de processos longos, aumentando o tempo médio de espera.

Esta implementação serve como base para a compreensão de algoritmos de escalonamento mais complexos, como Shortest Job First (SJF), Priority Scheduling e Round Robin (RR), que visam otimizar diferentes aspectos do escalonamento de processos.