Programa en C++ para el algoritmo de planificación FCFS

Introducción

En este laboratorio, implementaremos el algoritmo de planificación de Primer Llegado, Primer Servido (First Come First Serve, FCFS) utilizando C++. FCFS es el algoritmo de planificación de CPU más sencillo que asigna la CPU a los procesos en el orden en que la solicitan. El proceso que llega primero a la cola de listos se atiende primero.

Este algoritmo es fácil de entender e implementar, pero puede no ofrecer un rendimiento óptimo en términos de tiempo de espera promedio. Al final de este laboratorio, entenderás cómo funciona el algoritmo FCFS y podrás calcular métricas importantes como el tiempo de espera y el tiempo de respuesta de los procesos.

Skills Graph

Comprender FCFS y crear la estructura del programa

Primer Llegado, Primer Servido (First Come First Serve, FCFS) es un algoritmo de planificación no preemptivo en el que los procesos se ejecutan en el orden en que llegan a la cola de listos. En este paso, crearemos nuestro archivo de programa y configuraremos la estructura básica.

Comencemos creando un nuevo archivo de C++:

1. Abra la interfaz de WebIDE y navegue hasta el panel del explorador de archivos.
2. Haga clic derecho en el panel del explorador y seleccione "Nuevo archivo".
3. Nombre el archivo fcfs.cpp y presione Enter.

Ahora, agreguemos los archivos de encabezado necesarios y la declaración de espacio de nombres a nuestro programa:

#include <iostream>
#include <iomanip> // Para salida formateada

using namespace std;

int main() {
    cout << "Implementación del algoritmo de planificación FCFS" << endl;
    cout << "----------------------------------------" << endl;

    return 0;
}

Este código configura la estructura básica de nuestro programa con:

• #include <iostream> - Para operaciones de entrada/salida
• #include <iomanip> - Para formatear la tabla de salida
• using namespace std; - Para usar el espacio de nombres estándar
• Una función main() con la visualización de un título

Compilemos y ejecutemos el programa para asegurarnos de que todo esté configurado correctamente:

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

Debería ver la siguiente salida:

Implementación del algoritmo de planificación FCFS
----------------------------------------

Esto confirma que nuestra estructura básica de programa está funcionando correctamente. En el siguiente paso, implementaremos la funcionalidad para ingresar los detalles de los procesos.

Implementar la funcionalidad de entrada de procesos

En este paso, implementaremos la funcionalidad para recopilar información sobre los procesos que se van a programar. Para la programación FCFS, necesitamos saber:

1. El número de procesos
2. El tiempo de ráfaga (burst time) de cada proceso (tiempo de ejecución requerido por cada proceso)

Modifiquemos nuestro archivo fcfs.cpp para incluir esta funcionalidad:

#include <iostream>
#include <iomanip> // Para salida formateada

using namespace std;

int main() {
    cout << "Implementación del algoritmo de planificación FCFS" << endl;
    cout << "----------------------------------------" << endl;

    // Declaración de variables
    int n;                  // Número de procesos
    int burst_time[20];     // Arreglo para almacenar el tiempo de ráfaga de cada proceso

    // Obtener el número de procesos del usuario
    cout << "\nIngrese el número de procesos (máximo 20): ";
    cin >> n;

    // Validación de entrada
    if (n <= 0 || n > 20) {
        cout << "Número de procesos no válido. Por favor, ingrese un valor entre 1 y 20." << endl;
        return 1;
    }

    // Obtener el tiempo de ráfaga para cada proceso
    cout << "\nIngrese el Tiempo de Ráfaga para cada proceso:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Proceso P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Validación de entrada para el tiempo de ráfaga
        if (burst_time[i] <= 0) {
            cout << "El tiempo de ráfaga debe ser un entero positivo. Por favor, reinicie el programa." << endl;
            return 1;
        }
    }

    // Mostrar los datos ingresados
    cout << "\nProceso\tTiempo de Ráfaga" << endl;
    cout << "--------------------" << endl;
    for (int i = 0; i < n; i++) {
        cout << "P" << i + 1 << "\t" << burst_time[i] << endl;
    }

    return 0;
}

Veamos lo que hemos agregado:

1. Variables para almacenar el número de procesos (n) y el tiempo de ráfaga de cada proceso (burst_time[20]).
2. Mensajes de entrada para recopilar el número de procesos y el tiempo de ráfaga de cada proceso.
3. Validación de entrada para asegurar que el número de procesos esté dentro de un rango razonable (1 - 20) y que los tiempos de ráfaga sean positivos.
4. Una tabla para mostrar los datos ingresados para su verificación.

Compilémos y ejecutemos nuestro programa actualizado:

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

Cuando ejecute el programa, se le pedirá que ingrese el número de procesos y sus tiempos de ráfaga. Intente ingresar los siguientes datos:

3
5
9
4

Esto representa 3 procesos con tiempos de ráfaga de 5, 9 y 4 unidades de tiempo respectivamente. Debería ver una salida similar a:

Implementación del algoritmo de planificación FCFS
----------------------------------------

Ingrese el número de procesos (máximo 20): 3

Ingrese el Tiempo de Ráfaga para cada proceso:
Proceso P1: 5
Proceso P2: 9
Proceso P3: 4

Proceso Tiempo de Ráfaga
--------------------
P1      5
P2      9
P3      4

Esto confirma que nuestra funcionalidad de entrada está funcionando correctamente. En el siguiente paso, calcularemos el tiempo de espera y el tiempo de respuesta para cada proceso.

Cálculo del tiempo de espera y el tiempo de respuesta

En este paso, calcularemos dos métricas importantes para cada proceso:

1. Tiempo de espera (Waiting Time, WT): El tiempo que un proceso espera en la cola de listos antes de obtener tiempo de CPU.
2. Tiempo de respuesta (Turnaround Time, TAT): El tiempo total transcurrido desde la presentación del proceso hasta su finalización.

Comprendamos cómo se calculan estos valores en FCFS:

• Para el primer proceso (P1), el tiempo de espera siempre es 0 (comienza inmediatamente).
• Para los procesos subsiguientes, el tiempo de espera es la suma de los tiempos de ráfaga de todos los procesos anteriores.
• El tiempo de respuesta de cada proceso es la suma de su tiempo de ráfaga y su tiempo de espera.

Ahora, modifiquemos nuestro archivo fcfs.cpp para agregar estos cálculos:

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "Implementación del algoritmo de planificación FCFS" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                      // Number of processes
    int burst_time[20];         // Array to store burst time of each process
    int waiting_time[20];       // Array to store waiting time of each process
    int turnaround_time[20];    // Array to store turnaround time of each process
    int total_waiting_time = 0;
    int total_turnaround_time = 0;

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Calculate waiting time for each process
    waiting_time[0] = 0;    // First process has 0 waiting time

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Add burst times of all previous processes
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calculate turnaround time for each process and total times
    cout << "\nProcess\tBurst Time\tWaiting Time\tTurnaround Time" << 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;
}

Comprendamos lo que hemos agregado:

1. Dos nuevos arreglos: waiting_time[20] y turnaround_time[20] para almacenar el tiempo de espera y el tiempo de respuesta de cada proceso.
2. Variables para realizar un seguimiento del tiempo de espera total y el tiempo de respuesta total.
3. Cálculos para el tiempo de espera:
   • El primer proceso tiene un tiempo de espera de 0.
   • Para cada proceso subsiguiente, el tiempo de espera es la suma de los tiempos de ráfaga de todos los procesos anteriores.
4. Cálculos para el tiempo de respuesta:
   • Para cada proceso, tiempo de respuesta = tiempo de ráfaga + tiempo de espera.
5. Una tabla formateada para mostrar los resultados.

Compilémos y ejecutemos nuestro programa actualizado:

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

Intente ingresar los mismos datos que antes:

3
5
9
4

Debería ver una salida similar a:

Implementación del algoritmo de planificación FCFS
----------------------------------------

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

Analicemos los resultados:

• P1: Tiempo de espera = 0, Tiempo de respuesta = 5 (su tiempo de ráfaga)
• P2: Tiempo de espera = 5 (tiempo de ráfaga de P1), Tiempo de respuesta = 14 (5 + 9)
• P3: Tiempo de espera = 14 (tiempos de ráfaga de P1 + P2), Tiempo de respuesta = 18 (14 + 4)

Esto confirma que nuestros cálculos de tiempo de espera y tiempo de respuesta están funcionando correctamente. En el siguiente paso, calcularemos los tiempos promedio y mostraremos los resultados finales.

Cálculo de los tiempos promedio y visualización de los resultados finales

En este último paso, calcularemos el tiempo de espera promedio y el tiempo de respuesta promedio de todos los procesos. Estos promedios son métricas importantes para evaluar la eficiencia de un algoritmo de planificación.

Modifiquemos nuestro archivo fcfs.cpp para agregar estos cálculos y completar nuestro programa:

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "Implementación del algoritmo de planificación FCFS" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                      // Number of processes
    int burst_time[20];         // Array to store burst time of each process
    int waiting_time[20];       // Array to store waiting time of each process
    int turnaround_time[20];    // Array to store turnaround time of each process
    int total_waiting_time = 0;
    int total_turnaround_time = 0;
    float avg_waiting_time = 0.0;
    float avg_turnaround_time = 0.0;

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Calculate waiting time for each process
    waiting_time[0] = 0;    // First process has 0 waiting time

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Add burst times of all previous processes
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calculate turnaround time for each process and total times
    cout << "\nProcess\tBurst Time\tWaiting Time\tTurnaround Time" << 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;
    }

    // Calculate average waiting time and average turnaround time
    avg_waiting_time = (float)total_waiting_time / n;
    avg_turnaround_time = (float)total_turnaround_time / n;

    // Display the results with two decimal places
    cout << fixed << setprecision(2);
    cout << "\nAverage Waiting Time: " << avg_waiting_time << " time units" << endl;
    cout << "Average Turnaround Time: " << avg_turnaround_time << " time units" << endl;

    // Visual representation of the FCFS schedule (Gantt chart in text)
    cout << "\nGantt Chart:" << 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;
}

Comprendamos lo que hemos agregado:

1. Dos nuevas variables: avg_waiting_time y avg_turnaround_time para almacenar los tiempos promedio.
2. Cálculos de los tiempos promedio:
   • Tiempo de espera promedio = Tiempo de espera total / Número de procesos
   • Tiempo de respuesta promedio = Tiempo de respuesta total / Número de procesos
3. Salida formateada para mostrar los tiempos promedio con dos decimales.
4. Un sencillo diagrama de Gantt basado en texto para visualizar la planificación FCFS:
   • Cada proceso está representado por su ID (P1, P2, etc.)
   • El ancho de cada bloque de proceso es proporcional a su tiempo de ráfaga
   • Las marcas de tiempo se muestran en la parte inferior

Compilémos y ejecutemos nuestro programa final:

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

Intente ingresar los mismos datos que antes:

3
5
9
4

Debería ver una salida similar a:

Implementación del algoritmo de planificación FCFS
----------------------------------------

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

Al analizar los resultados:

• Tiempo de espera promedio: (0 + 5 + 14) / 3 = 6.33 unidades de tiempo
• Tiempo de respuesta promedio: (5 + 14 + 18) / 3 = 12.33 unidades de tiempo

El diagrama de Gantt representa visualmente cómo se planifican los procesos a lo largo del tiempo:

• P1 se ejecuta desde el tiempo 0 hasta el 5
• P2 se ejecuta desde el tiempo 5 hasta el 14
• P3 se ejecuta desde el tiempo 14 hasta el 18

Con esto se completa nuestra implementación del algoritmo de planificación FCFS. Puedes experimentar con diferentes números de procesos y tiempos de ráfaga para ver cómo afectan el tiempo de espera promedio y el tiempo de respuesta.

Resumen

En este laboratorio, hemos implementado con éxito el algoritmo de planificación de CPU de Primer Llegado, Primer Servido (First Come First Serve, FCFS) utilizando C++. Estos son los conceptos clave y las habilidades que has aprendido:

1. Conceptos básicos del algoritmo FCFS: Comprender cómo se planifican los procesos en el orden en que llegan.

2. Cálculo de métricas de rendimiento:

   • Tiempo de espera: El tiempo que un proceso espera antes de comenzar su ejecución.
   • Tiempo de respuesta: El tiempo total desde la presentación hasta la finalización del proceso.
   • Tiempo de espera promedio y tiempo de respuesta promedio: Indicadores clave de rendimiento para los algoritmos de planificación.

3. Conceptos de programación en C++:

   • Arreglos para almacenar información de procesos.
   • Bucles para cálculos iterativos.
   • Operaciones de entrada/salida con validación.
   • Salida formateada para una mejor presentación de datos.

4. Técnicas de visualización: Creación de un diagrama de Gantt basado en texto para visualizar la línea de tiempo de la planificación.

El algoritmo FCFS es sencillo de entender e implementar, pero no siempre proporciona un rendimiento óptimo. Puede dar lugar al "efecto convoy", en el que los procesos cortos se quedan atrapados esperando detrás de procesos largos, lo que aumenta el tiempo de espera promedio.

Esta implementación sirve como base para comprender algoritmos de planificación más complejos, como el de Menor Tiempo de Trabajo Primero (Shortest Job First, SJF), la planificación por prioridad y el algoritmo de Round Robin (RR), que buscan optimizar diferentes aspectos de la planificación de procesos.