Algoritmos de planificación de procesos



[Escribir la dirección de la compañía]

Contenido



Algoritmos de planificación
Introducción
Cuando un usuario pide ejecutar programas o segmentos de programas a la computadora, solicita el acceso al procesador y a los recursos de esta. Si la computadora fuera a ejecutar un programa a la vez hasta su terminación, el resto de los programas tendrían que aguardar ociosamente. Parafinalizar todos los programas en un tiempo razonable, el sistema operativo debe organizar las operaciones sobre el hardware de una manera eficiente. Todas las computadoras pueden realizar varias tareas al mismo tiempo. La CPU debe cambiar de un programa a otro, ejecutando cada uno en decenas o cientos de milisegundos. Pero en cualquier instante de tiempo la CPU puede estar ejecutando solo unprograma.
Pero, ¿quién decide qué procesos se deben ejecutar?
En este caso existe un planificador que se encarga, por medio de un algoritmo de planificación decidir cuál es el que debe ejecutarse en primer lugar.
Definición de algoritmo
Se puede definir como un conjunto de instrucciones que realizadas en orden conducen a obtener la solución de un problema. Por lo tanto podemos decir que es unconjunto ordenado y finito de pasos que nos permite solucionar un problema.
El algoritmo es la infraestructura de cualquier solución.
Existen distintos algoritmos de planificación.
Planificación no apropiativa: deja ejecutar al proceso en CPU hasta que éste para por bloqueo (inicio E/S), espera por otro proceso o terminación voluntaria.
Planificación apropiativa: el planificador puede desalojar alproceso en CPU durante su ejecución y cambiarlo por otro.
Necesita una interrupción de reloj para poder ejecutarse en períodos regulares de tiempo (quantum).
Algoritmos no apropiativos
Algoritmo First-Come-First-Served (FCFS): Primero en llegar, primero en ser servido
Con este esquema, el proceso que primero solicita el procesador es el primero al que se le asigna. Esta política se implementamuy fácilmente con una cola FIFO. Cuando un proceso entra en la cola de procesos listos su PCB se enlaza con el proceso que está al final de la cola. Cuando el procesador está libre se asigna el proceso colocado al inicio de la cola de procesos listos, esto es, se selecciona el proceso más antiguo de la cola
Ventajas
Fácil de implementar. Basta una cola FIFO.
Es bastante justo, si entendemos queprocesos con menos CPU tienen menos derecho a usarla.
Desventaja
Puede provocar baja productividad; efecto “convoy”.
Problemático en los sistemas de tiempo compartido, donde es importante que cada usuario reciba una porción del procesador a intervalos regulares. El tiempo promedio de espera es bastante largo en este algoritmo
Ejemplo
un proceso limitado por CPU y muchos procesos con E/S muyfrecuente.




Algoritmo Shortest Job First (SJF): Primero el más corto.
Este algoritmo selecciona al proceso con el próximo tiempo de ejecución más corto. Un proceso corto saltará a la cabeza de la cola. La ejecución de un proceso consiste en ciclos de ejecución de CPU y ciclos de espera por E/S. El algoritmo selecciona aquel proceso cuyo próximo ciclo de ejecución de CPU sea menor.
Tienesólo utilidad teórica, ya que precisa conocer el tiempo que va a usarse la CPU antes de usarla.
Se asocia a cada proceso la longitud de su siguiente ráfaga de CPU.
Si la CPU está disponible se le asigna al proceso de menor longitud de ráfaga. Si hay dos con igual longitud de ráfaga se usa FCFS.
Ventajas
Es el óptimo para minimizar el tiempo de paso o de retorno (turnaround) con varios procesoslistos en llegada simultánea.
A tiempos iguales, se usa FCFS.
Desventajas
Si los procesos llegan en distintos instantes, deja de ser óptimo.
Ejemplo
Supongamos 4 procesos con ráfagas entrantes de 8, 4, 4 y 4 ms.
Si los colocamos en orden de llegada: 8 4 4 4
P1 tarda 8, P2 tarda 8 + 4 = 12, P3 tarda 12 + 4 = 16, P4 tarda 16 + 4 = 20.
El plazo de entrega medio es: (8 + 12 + 16 + 20)=4 = 14...