2.5.2 Algoritmos
- Primero en entrar-primero en salir: También denominado FCFS (First-Come First-Served), es un algoritmo que utiliza una fila de procesos determinando el funcionamiento de cada proceso por el orden de llegada. Al llegar el proceso es puesto detrás del que llegó antes que él. Se resalta que al comenzar a ejecutarse un proceso, su ejecución no es interrumpida hasta terminar.
- Prioridad al más corto: Conocido como SJF (Shortest Job First). Este proceso se distingue porque cuando un proceso se encuentra en ejecución, voluntariamente cambia de estado, es decir que el tiempo de ejecución del proceso no es determinado. Por lo cual cada proceso tiene una asignación de tiempo cuando vuelve a ser ejecutado y va ejecutando el proceso con la menor cantidad de tiempo asignada. Al encontrarse que dos algoritmos poseen la misma cantidad de tiempo, se utilizará el algoritmo FCFS.
- Planificación por turno rotatorio: Llamado Round Robin, es un algoritmo donde se determina el mismo tiempo para la ejecución de todos los procesos. Si un proceso no puede ejecutarse por completo en el tiempo asignado su ejecución será después de la ejecución de todos los procesos que se ejecuten con el tiempo asignado. Este algoritmo se fundamenta en FCFS y ordena la cola de procesos circularmente cuando se hallan en estado de listos.
- Planificación por prioridad: Esta planificación se caracteriza porque a cada proceso se le asigna una prioridad y se continúan con un criterio determinado. Los procesos serán atendidos de acuerdo con la prioridad determinada.
- Planificación garantizada: En esta planificación el sistema se enfoca en la cantidad de usuarios que debe atender. Donde en un número n de usuarios se asignará a cada usuario 1/n de tiempo de ejecución.
- Planificación de colas múltiples: Derivado de MQS (Multilevel Queue Scheduling). Es un algoritmo donde la cola de procesos en estado de listos se divide en varias colas más pequeñas. Los procesos se clasifican a partir de un criterio que determina en qué cola se ubicará el proceso cuando se encuentre en estado de listo.
Tipos de planificación
La planificación de procesos busca la eficacia y la equidad de los tiempos, tanto de respuesta como de regreso, además del rendimiento.
En la planificación de procesos podemos encontrar tres tipos principales:
- Planificación a largo plazo: En esta planificación se determina cuáles procesos serán los siguientes en ser ejecutados. La toma de decisiones es realizada bajo los requisitos de los procesos previamente anunciados y los que se encuentran libres en el sistema luego de finalizar otro proceso.
- Planificación a mediano plazo: En la Planificación a mediano plazo se decide cuáles tiempos deben ser bloqueados y en qué momento determinado ya sea por la falta o la saturación de algún recurso o porque la solicitud exigida no puede atenderse en el momento. La toma de decisiones es efectuada de acuerdo a la entrada y a la salida de los procesos que se encuentran en estado bloqueado.
- Planificación a corto plazo: En este tipo de planificación se determina en cada instante el procedimiento para compartir al equipo que recursos necesitan todos los procesos. Es de resaltar que este tipo de planificación es ejecutado decenas de veces por segundo.
- Se resalta que en la planificación de procesos se debe tener en cuenta los tiempos que se pueden calcular, tales como: El tiempo de espera medio, el tiempo de retorno del proceso y el tiempo de retorno medio.
Figura 23. La planificación de procesos es importante para poder sincronizar.
// Ejemplo de código de algoritmo FIFO function saludar() { console.log("¡Hola, mundo!"); } int main() { // Crear la FIFO mkfifo(FIFO_FILE, 0666); // Abrir la FIFO para escribir int fd = open(FIFO_FILE, O_WRONLY); if (fd == -1) { perror("Error al abrir la FIFO para escribir"); exit(EXIT_FAILURE); } // Escribir datos en la FIFO char message[] = "Hola, FIFO!"; write(fd, message, strlen(message) + 1); // Cerrar el extremo de escritura de la FIFO close(fd); // Abrir la FIFO para leer fd = open(FIFO_FILE, O_RDONLY); if (fd == -1) { perror("Error al abrir la FIFO para leer"); exit(EXIT_FAILURE); } // Leer datos de la FIFO char buffer[100]; read(fd, buffer, sizeof(buffer)); printf("Mensaje leído: %s\n", buffer); // Cerrar el extremo de lectura de la FIFO close(fd); // Eliminar la FIFO unlink(FIFO_FILE); return 0; }
Código 9. Algoritmo FIFO.
#include <stdio.h> // Estructura para representar un proceso struct Process { int id; // Identificador del proceso int arrivalTime; // Tiempo de llegada del proceso int burstTime; // Tiempo de ráfaga del proceso }; // Función para la planificación SJF void sjf(struct Process processes[], int n) { int remainingTime[n]; for (int i = 0; i < n; i++) { remainingTime[i] = processes[i].burstTime; } int completed = 0, t = 0, minIndex; while (completed != n) { minIndex = -1; // Encontrar el proceso con el tiempo de ráfaga más corto que ha llegado for (int i = 0; i < n; i++) { if (processes[i].arrivalTime <= t && (minIndex == -1 || remainingTime[i] < remainingTime[minIndex])) { minIndex = i; } } // Si no se encuentra ningún proceso listo, avanzar en el tiempo if (minIndex == -1) { t++; continue; } // Ejecutar el proceso seleccionado remainingTime[minIndex]--; t++; // Si la ráfaga ha terminado, imprimir el mensaje y marcar el proceso como completado if (remainingTime[minIndex] == 0) { printf("Proceso %d ejecutado en el tiempo %d\n", processes[minIndex].id, t); completed++; } } } int main() { // Ejemplo con tres procesos struct Process processes[] = {{1, 0, 6}, {2, 2, 8}, {3, 3, 7}}; int n = sizeof(processes) / sizeof(processes[0]); printf("Planificación SJF:\n"); sjf(processes, n); return 0; }
Código 10. Planificación SFJ.
Reflexiona la siguiente pregunta que será tratada en la sesión de clase.
¿Cuál planificación consideras que es la más básica?