Exposición: Algoritmos de planificación
Sistemas Operativos
Trabajo
“Algoritmos de planificación”
Presentado por
Josselin Restrepo Giraldo
Mariana Paniagua Ruiz
Manuela Soto Correa
Maryeri Ramirez Cañaveral
Profesor
German Jurado Cano
TABLA DE CONTENIDO
Algoritmos de planificación …………………………...
Objetivos ……………………………………………….
FCFS…………………………………………………...
Round Robin…………………………………………...
SPN……………………………………………………..
SRR: selfish round robin………………………………..
FB: FeedBack Multilevel……………………………….
Esquemas híbridos………………………………………
Cibergrafía……………………………………………….
Algoritmos de planificación
Cuando una computadora se multiprograma, con frecuencia tiene varios procesos o hilos que compiten por la CPU al mismo tiempo. Esta situación ocurre cada vez que dos o más de estos procesos se encuentran al mismo tiempo en el estado listo. Si sólo hay una CPU disponible, hay que decidir cuál proceso se va a ejecutar a continuación. La parte del sistema operativo que realiza esa decisión se conoce como planificador de procesos y el algoritmo que utiliza se conoce como algoritmo de planificación.
Cuando se tiene que elegir a qué proceso asignar la CPU se escoge al que llevara más tiempo listo. El proceso se mantiene en la CPU hasta que se bloquea voluntariamente. La ventaja de este algoritmo es su fácil implementación, sin embargo, no es válido para entornos interactivos ya que un proceso de mucho cálculo de CPU hace aumentar el tiempo de espera de los demás procesos.
Un claro ejemplo es el siguiente:
Para implementar el algoritmo (ver Figura 1) sólo se necesita mantener una lista con los procesos listos ordenada por tiempo de llegada. Cuando un proceso pasa de bloqueado a listo se sitúa el último de la cola. En a) el proceso P7 ocupa la CPU, los procesos P2, P4 y P8 se mantienen en la lista de preparados. En b) P7 se bloquea (ya sea al realizar una E/S, una operación WAIT sobre un semáforo a cero u otra causa) y P2 pasa a ocupar la CPU. En c) ocurre un evento (finalización de la operación de E/S, operación SIGNAL, ...) que desbloquea a P7, esto lo vuelve al estado listo, pasando al final de la lista de procesos listos.
Estos procesos se conocen como injustos en el sentido de que: los trabajos largos hacen esperar a los cortos y los trabajos sin importancia hacen esperar a los importantes. Por otro lado es predecible, pero no garantiza buenos tiempos de respuesta, por ello se emplea como esquema secundario.
Los algoritmos de planificación se dividen en apropiativos y no apropiativos.
Los apropiativos son los que una vez que el proceso pasa al estado de ejecución, continúa ejecutando hasta que termina, se bloquea en espera de una E/S o al solicitar algún servicio del sistema.
Los no apropiativos son en los que el proceso se está ejecutando puede ser interrumpido y pasado al estado de listos por el sistema operativo. La decisión de sustituirlos por otro proceso puede llevarse a cabo cuando llega un nuevo proceso o cuando se produce otra interrupción del proceso actual.
Objetivos:
Equidad: Todos los procesos deben ser atendidos.
Eficacia: El procesador debe estar ocupado el 100% del tiempo.
Tiempo de respuesta: El tiempo empleado en dar respuesta a las solicitudes del usuario debe ser el menor posible.
Tiempo de regreso: Reducir al mínimo el tiempo de espera de los resultados esperados por los usuarios por lotes.
Rendimiento: Maximizar el número de tareas que se procesan por cada hora.
FCFS
Empezaremos hablando de FCFS o también llamado FIFO (del inglés First In, First Out). Este algoritmo es muy sencillo y simple, pero también el que menos rendimiento ofrece, básicamente en este algoritmo el primer proceso que llega se ejecuta y una vez terminado se ejecuta el siguiente.
Primero en entrar, primero en salir. El planificador asignará los ciclos de CPU a cada proceso en función de una cola FIFO en la que el primer proceso que llega al sistema será el primero en ser atendido. Al primer proceso que llega se le asignará tantos ciclos de CPU como necesite hasta que termine completamente. Una vez terminado con este proceso, se procederá a ejecutar el siguiente y así sucesivamente hasta terminar con el último proceso.
Ejemplo:
Round Robin
Hablaré de Round Robin, este algoritmo de planificación es uno de los más complejos y difíciles de implementar, asigna a cada proceso un tiempo equitativo tratando a todos los procesos por igual y con la misma prioridad.
Este algoritmo es circular, volviendo siempre al primer proceso una vez terminado con el último, para controlar este método a cada proceso se le asigna un intervalo de tiempo llamado quantum o cuanto (para definirlo se utiliza esta regla, el 80% de los procesos tienen que durar menos tiempo que el quantum definido).
Pueden suceder dos casos con este método (como se aprecia en la imagen inferior):
El proceso es menor que el quantum: Al terminar antes se planifica un nuevo proceso.
El proceso es mayor que el quantum: Al terminar el quantum se expulsa el proceso dando paso al siguiente proceso en la lista. Al terminar la iteración se volverá para terminar el primer proceso expulsado
En este algoritmo se asignan tiempos de ejecución de forma rotativa entre los procesos. Este algoritmo se caracteriza por la equidad, dado que se asigna a todos los procesos el mismo quantum o ciclos de CPU. La selección de los procesos se hace mediante una cola FCFS o FIFO.
SPN: (Del inglés, Shortest Process Next)
Proceso más corto Siguiente
Cuando no tenemos la posibilidad de implementar multitarea preventiva, pero requerimos de un algoritmo más justo, y contamos con información por anticipado acerca del tiempo que requieren los procesos que forman la lista, podemos elegir el más corto de los presentes.
Ahora bien, es muy difícil contar con esta información antes de ejecutar el proceso. Es más frecuente buscar caracterizar las necesidades del proceso: Ver si durante su historia de ejecución ha sido un proceso tendiente a manejar ráfagas limitadas por entrada-salida o limitadas por procesador, y cuál es su tendencia actual.
Para estimar el tiempo que requerirá un proceso, en su próxima invocación, es común emplear el promedio exponencial, Definimos un factor atenuante, que determinará qué tan reactivo será el promedio obtenido a la última duración; es común que este valor sea cercano a 0.9.
Ronda egoísta (SRR, selfish round robin)
Este método busca favorecer a los procesos que ya han pasado tiempo ejecutando que a los recién llegados. De hecho, los nuevos procesos no son programados directamente para su ejecución, sino que se les forma en la cola de procesos nuevos, y se avanza únicamente con la cola de procesos aceptados.
Se pueden cambiar las prioridades tanto de los procesos “nuevos” como de los “aceptados”
Cuando un proceso nuevo alcanza la prioridad de un proceso aceptado, este se acepta y por ende, puede ser despachado y ejecutado.
FB: FeedBack Multilevel
FB: Un planificador Multilevel-Feedback se define por ser El número de colas, el algoritmo de planificación para cada cola, el método utilizado para promover a un proceso a una cola de mayor prioridad, el método utilizado para bajar a un proceso a una cola de menor prioridad. el método utilizado para determinar a qué cola será asignado un proceso cuando este pronto, todo tiene como fin es que este mecanismo maneja no una, sino que varias colas de procesos listos, con diferentes niveles de prioridad, el despachador elige para su ejecución al proceso que esté al frente de la cola de mayor prioridad que tenga algún proceso esperando y tras un número predeterminado de ejecuciones, lo degrada a la cola de prioridad inmediata inferior,prioridad que tenga algún proceso esperando y tras un número predeterminado de ejecuciones, lo degrada a la cola de prioridad inmediata inferior
Esquemas híbridos
Un esquema híbrido es una combinación de diversas formas de representación de conocimiento para resolver un problema.
Las formas de representar conocimiento que vimos no son mutuamente exclusivas.
Hay dos formas básicas de combinar diversas representaciones: Externa e Interna.
Híbridos Externos
En este esquema dos o más módulos con diferentes formas de representación interactúan entre sí.
Cada módulo tiene una sola forma de representación y se combina con los otros módulos mediante variables de entrada/salida o mediante una estructura de datos común (Base de Datos).
En principio cada subsistema tiene la forma de representación más adecuada para resolver una parte del problema, y se combina con las demás para solucionar un problema mayor.
Este esquema da origen al sistema de pizarrón, y al hacerse en forma distribuida, a los sistemas multi-agentes.
Híbridos Internos
• En este tipo de sistemas se combinan varias formas de representación que interactúan para resolver cierto problema.
• Con esto se aprovechan diversas propiedades de las formas de representación que complementan sus capacidades.
• Por ejemplo, se combinan las reglas con prototipos aprovechando las abstracciones de marcos dentro de reglas, o marcos y redes semánticas formando redes de prototipo, etc.
Comentarios
Publicar un comentario