Algoritmo DE Planificacion SJF PDF

Preview

Summary

Algoritmo DE Planificacion SJF...

Description

DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN ING. EN SISTEMAS E INFORMÁTICA SISTEMAS OPERATIVOS I NRC 3980

“ALGORITMO DE PLANIFICACION SJF” Autores:

Tutor: ING. RAMIRO DELGADO.

Sangolquí, 11 de diciembre de 2017

1. ALGORITMO DE PLANIFICACION SJF “Shortest Job First” (Primero el Trabajo más Corto)

El algoritmo SJF (Shortest-Job-First) se basa en los ciclos de vida de los procesos, los cuales transcurren en dos etapas o periodos que son: ciclos de CPU y ciclos de entrada/salida, también conocidos por ráfagas. La palabra shortest (el más corto) se refiere al proceso que tenga el próximo ciclo de CPU más corto. La idea es escoger entre todos los procesos listos el que tenga su próximo ciclo de CPU más pequeño. El SJF se puede comportar de dos formas: 1. Con Desalojo: Si se incorpora un nuevo proceso a la cola de listos y este tiene un ciclo

de CPU menor que el ciclo de CPU del proceso que se está ejecutando, entonces dicho proceso es desalojado y el nuevo proceso toma la CPU.(conocido como SRTF, con implementación FIFO para coincidencias de tiempo de ejecución) 2. Sin desalojo: Cuando un proceso toma la CPU, ningún otro proceso podrá apropiarse

de ella hasta que el proceso que la posee termine de ejecutarse. (conocido como SJF, con implementación FIFO para coincidencias de tiempo ejecución)

EXPLICACIÓN: cada que terminan un proceso se fija cual es el próximo más corto para poder ejecutarlo. (Color negro: significa que está listo para ejecutar pero en espera)

En resumen, 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. El problema está en conocer dichos valores, pero podemos predecirlos usando la información de los ciclos anteriores ejecutados. CARACTERÍSTICAS El algoritmo de primero el trabajo más corto (SJF, shortest job first), que asocia a cada proceso la longitud de la siguiente ráfaga de CPU de ese proceso. Cuando la CPU queda disponible, asigna al proceso cuya siguiente ráfaga de CPU sea más corta. Si hay dos procesos cuyas siguientes ráfagas de CPU tienen la misma duración, se emplea planificación FCFS (first come, first served) para romper el empate. El problema está en conocer dichos valores, pero podemos predecirlos usando la información de los ciclos anteriores ejecutados. Puede comprobarse que el algoritmo SJF es óptimo, ya que ofrece el menor tiempo promedio para un conjunto de procesos dados.

VENTAJAS 



Este algoritmo presenta una gran ventaja, pues el tiempo de espera será mucho menor, pues mientras los procesos de tiempo inferior terminan y ocupan tiempo en operaciones de E/S, el CPU se ocupa de resolver el proceso con mayor tiempo, un algoritmo muy óptimo. La ventaja de este algoritmo es su fácil implementación, para implementar este algoritmo solo se necesita mantener una cola con los procesos listos ordenada por tiempo de llegada

DESVENTAJAS  

El tiempo medio de espera en este algoritmo es a menudo muy largo. Efecto Convoy: cuando un proceso tarda mucho los demás deben esperar en cola hasta que termine, por lo tanto no es válido para entornos interactivos

2. PREGUNTAS (ALGORITMO DE SJF, PLANIFICACION DE PROCESOS)

1. a) b) c) d)

Cuáles son las características de la asignación SJF: Primero el trabajo más cortó Selecciona el trabajo más cortó Solamente se puede aplicar si se conoce de ante mano la duración del trabajo. Todas las anteriores

Respuesta: Todas las anteriores 2.

Dado un sistema multiprogramado en el que se encuentra en estado preparado un proceso orientado a E/S y una gran cantidad de procesos orientados a cómputo, ordénese de mejor a peor las siguientes estrategias de planificación de la CPU en función de que consigan mejores tiempos de retorno del proceso orientado a E/S: a) FCFS b) SJF c) SRTF Respuesta: Las estrategias que mejoran el tiempo de los procesos orientados a E/S son aquéllas que premian a los procesos “cortos” (los de menor ciclo de CPU). Suponiendo que se aplica un buen estimador, SRTF es la mejor estrategia, después vendría SJF y por último FCFS. El orden seria C, B, A 3. ¿Qué diferencia fundamental existe entre un algoritmo SJF (primero el trabajo más breve, shortest job first) y el algoritmo SRTF (primero el de menor tiempo restante, shortest remaning time first)?

Respuesta: La diferencia fundamental es que el SJF no es expulsivo y el SRTF sí lo es. 4. El SJF se puede comportar de dos formas y estas son: a) Desalojo b) Con desalojo c) Sin desalojo d) Ninguna Respuesta: a) Con desalojo, y b) Sin desaojo 5. Se incorpora un nuevo proceso a la cola de listos y este tiene un ciclo de CPU menor el ciclo de CPU del proceso que se está ejecutando, entonces dicho proceso es desalojado y el nuevo proceso toma la CPU. El concepto es de: a) SJF b) SRTF c) Forma de SJF con desalojo d) Ninguno

Respuesta: c) Forma de SJF con desalojo

3. EJEMPLOS Calcular el tiempo medio de espera que resulta de aplicar: 1. Un algoritmo SJF no expulsivo 2. Un algoritmo SJF expulsivo (STR, Shortest Remainning Time First) PROCESO

LLEGADA

DURACIÓN

ESPERA SJF

ESPERA SRTF

P1

0

7

0

9

P2

2

4

6

1

P3

4

1

3

0

P4

5

4

7

2

1. SJF no expulsivo espera media: (0+6+3+7) / 4 = 4

2. SJF expulsivo espera media: (9+1+0+2) / 4 = 3

PROBLEMA 1. Se tienen los siguientes procesos: Word con un tiempo de llegada de 0 y una ráfaga de CPU de 25 Excel con un tiempo de llegada de 4 y una ráfaga de CPU de 10 PowerPoint con un tiempo de llegada de 3 y una ráfaga de CPU de 10 Photoshop con un tiempo de llegada de 2 y una ráfaga de CPU de 4 Paint con un tiempo de llegada de 1 y una ráfaga de CPU de 4 Resolver por Algoritmo de planificación SJF Tabla de Solución

Procesos Word Excel PowerPoint Photoshop Paint

Tiempo de llegada 0 4 3 2 1

Ráfaga de CPU 25 10 10 4 4

Diagrama de Grantt: Word 0 25

Paint

Photoshop 29

PowerPoint 33

Excel 43

Formulas

Dónde:

TE = TEJ – TLL TR = TRaf + TRProAnt TEProm = ( ∑ TE ) / NP TRProm = ( ∑ TR ) / NP

TE = Tiempo de Espera TLL = Tiempo de Llegada TR = Tiempo de Respuesta TEJ = Tiempo de Ejecución TEProm = Tiempo de Espera Promedio TRaf = Rafaga de CPU TRProAnt = Tiempo de Respuesta del Proceso Anterior NP = Numero de Procesos TRProm = Tiempo de Respuesta Promedio

Tiempo de Espera

Tiempo de Respuesta

TE (Word) = 0 – 0 = 0 TE (Paint) = 25 – 1 = 24 TE (Photoshop) = 29 – 2 = 27 TE (PowerPoint) = 33 – 3 = 30 TE (Excel) = 43 – 4 = 39 TEProm = ( 0 + 24 + 27 + 30 + 39 ) / 5 TEProm = 24 ut

TR (Word) = 25 + 0 = 25 TR (Paint) = 4 + 25 = 29 TR (Photoshop) = 4 + 29 = 33 TR (PowerPoint) = 10 + 33 = 43 TR (Excel) = 10 + 43 = 53 TRProm = ( 25 + 29 + 33 + 43 + 53 ) / 5 TRProm = 36.6 ut

53

CONCLUSIONES 

Debemos considerar que este algoritmo no se puede implementar en cualquier sistema operativo, solo en aquellos que funcionan por lotes. En la actualidad no son muy utilizadas ya que existen algoritmos mucho más eficientes y fáciles de implementar para un mejor rendimiento del CPU.



Se debe tomar en cuenta que por defecto se realiza el primer proceso en entrar, y a continuación los siguientes aplicando criterios del algoritmo SJF, si existe un empate en las ráfagas de dos procesos, se puede utilizar FIFO, para desempatarlos.



El algoritmo SJF se puede comportar de dos maneras, en la una cuando ingresas procesos más cortos al que se está ejecutando, lo suspende y realiza el que entro, este es un problema, ya que puede provocar inanición

REFERENCIAS

Chimborazo, U. (10 de Diciembre de 2017). scribd. Obtenido de https://es.scribd.com/doc/44358964/FSO-Algoritmos-de-Planificacion-Algoritmo-SJFShortest-Job-First Lopez, R. (2011). iesjuandelacierva. Obtenido de ftp://iesjuandelacierva.com/pub/pilarsimm/temas%20teor%EDa%20SSOO/Ejemplo %20Algoritmo%20SJF.htm Ramirez, J. (2010). academia. Obtenido de https://www.academia.edu/3728099/El_trabajo_mas_corto Udg. (10 de Diciembre de 2017). Obtenido de http://www.udg.co.cu/cmap/sistemas_operativos/planificacion_cpu/sjf/sjf.html...