Algoritmos De Programación

*Algoritmos de Administración de CPU*

* Definición I: “Un algoritmo de planificación o administración de CPU es utilizado para calcular los recursos que consume otro algoritmo o conjunto de algoritmos (programa) al realizar una determinada tarea.”

Fuente: http://es.wikipedia.org/wiki/Algoritmo_de_planificaci%C3%B3n

*Definición II: “Conjunto de políticas y mecanismos incorporados al sistema operativo, a través de un módulo denominado planificador que decide cuál de los procesos en condiciones de ser ejecutado debe ser despachado y qué orden de ejecución debe seguirse.”

Fuente:

http://www.monografias.com/trabajos16/procesadores/procesadores.shtml

*Niveles de Planificación de CPU*

*Planificación a Largo Plazo:

*Controla el grado de multiprogramación en el sistema.

*Se ejecuta cuando empieza/acaba un proceso.

*En sistemas de tiempo compartido puede no haber.

*Planificación a Medio Plazo:

*Encargado de suspender y restaurar posteriormente procesos.

*Se ejecuta cuando hay escasez de recursos.

*Planificación a Corto Plazo:

*Selecciona el proceso a ejecutar.

*Se ejecuta frecuentemente.

-Cuando se crea/acaba un proceso.

-Cada cierto tiempo (dependiente de la planificación).

-Cuando un proceso inicia/finaliza la E/S.

-Ha de ser eficiente aunque con las nuevas CPUs cada vez se puede hacer más.

*FCFS*

*First Come First Server*

Cuando un proceso dispone de todos los recursos necesarios para su ejecución se dice que este proceso se encuentra en el estado listo, y por ende es agregado a la cola de listos en la cual se encuentran un conjunto de procesos que residen en la memoria y que esperan a que se desocupe la CPU y puedan ser atendidos.

Cuando el proceso que actualmente está ejecutando culmina su ejecución entonces el proceso que lleva más tiempo de espera en la cola es seleccionado para comenzar a ejecutarse.

Aquí es donde el algoritmo FCFS (First Come First Server) también conocido como FIFO (First In First Out) realiza su aparición, pues a través de las colas FIFO es posible asignar el proceso que encabeza la cola de listos a la CPU cuando esta queda libre.

Se dice que este algoritmo es nonpreemptive pues a la CPU se le asigna un proceso y esta puede dejar de trabajar con el de manera natural; es decir; porque el proceso finalizo ó bien porque un dispositivo de E/S tuvo algún requerimiento relacionado con la CPU.

Se puede decir que el tiempo de espera de los procesos para poder utilizar la CPU a través de este algoritmo generalmente no es mínimo y varía dependiendo de las duraciones de los ciclos de cada proceso.

Finalmente se dice que este algoritmo puede ocasionar un uso insuficiente tanto del procesador como de algunos dispositivos de E/S, sobre todo cuando los dispositivos quedan ociosos porque el trabajo que requieren otros procesos es mayor de lo esperado.

*Ejemplo Nº 1*

*Planificación de servicio por orden de llegada*

Calcular el tiempo de espera, tiempo de retorno y tiempo medio de espera si aplicamos el algoritmo FCFS suponiendo que los procesos siguientes llegan en el mismo instante y en el orden: P1, P2, P3.

¿Y si el orden de llegada es: P2, P3, P1?

Planificación de servicio por orden de llegada.

Es el algoritmo más sencillo, el primer proceso que solicita la CPU es el primero en recibirla.

Fácil de implementar con una política FIFO para la cola de preparados.

Tiempo de espera promedio bastante largo.

*Ejemplo Nº 2*

Proceso Tiempo de llegada Tiempo de Servicio Tiempo de Comienzo Tiempo de Finalización Turnaround Tiempo de Espera

A 0 1 0 1 1 0

B 1 100 1 101 100 0

C 2 1 101 102 100 101-2=99

D 3 100 102 202 199 102-3=99

Promedio 100 49.50

*Ejemplo Nº 3*

Proceso Tiempo de llegada Tiempo de Servicio Tiempo de Comienzo Tiempo de Finalización Turnaround Tiempo de Espera

B 0 100 0 100 100 0

D 1 100 100 200 199 100-1=99

A 2 1 200 201 201-2=199 200-2=198

C 3 1 201 202 202-3=199 201-3=198

Promedio 232 123.50

Aquí se presenta un efecto convoy donde los procesos esperan a que un proceso grande deje la CPU.

*SJF*

*Shortest Job First*

El algoritmo “primero el trabajo más corto (SJF /Shortest Job First) es el encargado de vincular una ráfaga de CPU a cada proceso. Cuando la CPU queda habilitada para recibir otro proceso este algoritmo le asigna el proceso que posea la ráfaga de CPU más corta. En el caso de que existan dos procesos con la misma duración de ráfaga se emplea el algoritmo tratado anteriormente (FCFS) para que deje de existir este “empate” de duraciones.

El algoritmo SJF es óptimo, pues nos

...