Fso - Algoritmos De Planificación - Algoritmo Sjf(shortest Job First) 5v3x3

ESCUELA SUPERIOR POLITÁCNICA DE CHIMBORAZO FACULTAD DE INFORMÁTICA Y ELECTRÓNICA ESCUELA DE INGENIERÍA ELECTRÓNICA

INGENIERÍA ELECTRÓNICA, TELECOMUNICACIONES Y REDES

FUNDAMENTOS DE SISTEMAS OPERATIVOS

ALGORITMOS DE PLANIFICACIÓN “ALGORITMO SHORTEST-JOB-FIRST (SJF)”

DOCENTE:

Ing. Katy Cabezas

INTEGRANTES: Cevallos Sánchez Liseth Parreño Ocaña Alexandra Quishpe Yambay Génova Santamaría Tapia Evelyn

RIOBAMBA 2010 – 2011

INDICE 1. Introducción………………………………………………………………………...1

2. Modelo del Sistema 2.1. Ciclo de Ráfagas de U y E/S…………………………………………….1 2.2. Planificación Expropiada……………………………………………………..2 3. Algoritmos de Planificación……………………………………………………….2

4. Algoritmo Shortest-Job-First (SJF) 4.1. Características………………………………………………………………...3 4.2. Comportamiento………………………………………………………………4 4.3. Ventajas y Desventajas………………………………………………...........4 4.4. Ejemplos……………………………………………………………………….5 5. Conclusiones……………………………………………………………………….7 6. Webgrafía…………………………………………………………………………..7

Fundamentos de Sistemas Operativos 1 Algoritmos de Planificación

1 Introducción El objetivo de la multiprogramación es tener un proceso en ejecución en todo momento para un mayor aprovechamiento de la U. En un sistema monoprocesador nunca habrá más de un proceso en ejecución. Si hay más procesos, tendrán que esperar a que la U quede libre para reasignarse. Para un mayor aprovechamiento, se mantiene varios procesos en memoria a la vez. Cuando un proceso necesita esperar, el sistema operativo le asigna e procesador a otro proceso. Casi todos los recursos del computador se planifican antes de usarse, la planificación es fundamental en el diseño del SO.

2 Modelo del Sistema 2.1Ciclo de Ráfagas de U y E/S La ejecución de un proceso consiste en un ciclo de ejecución alternado de manera sucesiva: • Ráfagas de U: (Que inicia el proceso), durante las cuales el proceso ejecuta instrucciones. • Ráfagas de E/S: Durante las cuales el proceso utiliza o espera por la E/S. Las ráfagas del U varia considerablemente de un proceso a otro y de un procesador a otro, sin embargo tienden a tener una curva de frecuencia bien tipificada. Histograma de tiempos de ráfaga de U Se observa: – Gran número de ráfagas de U cortas y pocas ráfagas de U largas. – Ráfagas de U cortas: programas limitados por E/S. – Ráfagas de U largas: programas limitados por U.

Algoritmo de Planificación SJF

Fundamentos de Sistemas Operativos 1 Algoritmos de Planificación

1.1Planificación Expropiada Las decisiones de planificación de U se toman según las cuatro situaciones siguientes: a) b) c) d)

Cuando un proceso pasa del estado en ejecución a en espera Cuando un proceso pasa del estado en ejecución a listo. Cuando un proceso pasa del estado en espera al estado listo. Cuando un proceso termina.

Los procesos a y d corresponden a una planificación no expropiada (obligatoriamente se escoge un proceso) Los casos b y c corresponden a una planificación expropiada.

1 Algoritmos de Planificación Cuando más de un proceso es ejecutable desde el punto de vista lógico, el sistema operativo debe decidir cuál de ellos debe ejecutarse en primer término. El planificador es la porción del sistema operativo que decide y el algoritmo de planificación es el utilizado. Existen dos categorías: Apropiativos El Sistema Operativo puede expulsar del procesador un proceso en ejecución (línea punteada.) No Apropiativos Estos procesos, no pueden ser expulsados por el Sistema Operativo.

Algoritmo de Planificación SJF

Fundamentos de Sistemas Operativos 1 Algoritmos de Planificación

2 Algoritmo Shortest-Job-First (SJF) 2.1Características La palabra shortest (el más corto) se refiere al proceso que tenga el el próximo ciclo de U mas corto. La idea es escoger entre todos los procesos listos el que tenga su próximo ciclo de U más pequeño. 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 U de ese proceso. Cuando la U queda disponible, asigna al proceso cuya siguiente ráfaga de U sea más corta. Si hay dos procesos cuyas siguientes ráfagas de U 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. El problema principal del algoritmo es el conocimiento de la longitud de la siguiente ráfaga de U por tanto no puede implantarse a nivel de la planificación de la U, aunque se utilizan aproximaciones. Aunque no se conocen los valores de las siguientes ráfagas de la U podemos predecir su valor esperando que sea más o menos del mismo tamaño que las anteriores (Por ello se elige el proceso con ráfaga previa de U más breve) El algoritmo “primero el trabajo más corto” (shortest – job - first). Establece para la planificación una relación entre proceso y ráfaga de la U. Es decir, al liberarse la U ingresará el proceso con la menor ráfaga de tiempo, el más pequeño primero, y si existiera más de un proceso con igual valor, pues se aplicaría dentro de este el algoritmo anterior (FCFS). 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 U se ocupa de resolver el proceso con mayor tiempo, un algoritmo muy óptimo. Este algoritmo puede ser preemptive y nonpreemptive. En el caso de preemptive, cuando un proceso llega a la cola de procesos listos, su prioridad es comparada con la prioridad del proceso que está corriendo. Si la prioridad del nuevo proceso es mayor, entonces se atiende al nuevo proceso. 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 U y ciclos de espera por E/S. El algoritmo selecciona aquel proceso cuyo próximo ciclo de ejecución de U sea menor. El problema está en conocer dichos valores, pero podemos predecirlos usando la información de los ciclos anteriores ejecutados.

Algoritmo de Planificación SJF

Fundamentos de Sistemas Operativos 1 Algoritmos de Planificación

2.2Comportamiento El SJF se puede comportar de dos formas: • Con Desalojo: Si se incorpora un nuevo proceso a la cola de listos y este tiene un ciclo de U menor que el ciclo de U del proceso que se está ejecutando, entonces dicho proceso es desalojado y el nuevo proceso toma la U. • Sin desalojo: Cuando un proceso toma la U, ningún otro proceso podrá apropiarse de ella hasta que que el proceso que la posee termine de ejecutarse. El algoritmo SJF puede ser apropiativo (SRT) o no apropiativo. La alternativa se plantea cuando un nuevo proceso llega a la cola de procesos listos mientras se esta ejecutando otro proceso. El nuevo proceso puede tener una ráfaga de U menor que lo que resta del proceso que se ejecuta en ese momento. Un algoritmo SJF apropiativo desplazará al proceso que se ejecuta.

1.1Ventajas y Desventajas Riesgo Es probablemente quede minimiza inanición óptimo, el de tiempo los ya que procesos reduce de finalización de el tiempo larga de espera. Desventajas Ventajas Planificación por Prioridad al más corto promedio duración. promedio de cada job (SJF, Short Job First). SJFSJF El da el no mínimo es tiempo implementable de espera promedio se pueden para un conjuntoduraciones estimarlas de procesos de los procesos, según su Entra enreciente. historia U el proceso con la ráfaga de U másdificultad La breve. en el algoritmo SJF es conocer la longitud la próxima ráfagamedio. de U de un Minimiza de el tiempo de espera proceso

Algoritmo de Planificación SJF

Fundamentos de Sistemas Operativos 1 Algoritmos de Planificación

1.1Ejemplos Algoritmo SJF con Desalojo Para el siguiente ejemplo se tienen 4 procesos (P1, P2,P3 y P4). A medida que estos se van incorporando a la cola de listos, se les calcula su próximo ciclo de U. Para calcular el próximo ciclo de U se pueden emplear: métodos estadísticos, cálculos probabilísticos, entre otros. Proceso

Tiempo de llegada

P1

0

P2

2

P3

4

P4

5

En el ejemplo se toma como criterio que la cola de procesos listos está inicialmente vacía. En la figura se representa la llegada de P1 a la cola de listos con un tiempo de llegada (0,0). Luego a P1 se le calcula su CU (CU = 7) y en ese instante se comienza a ejecutar.

Estando en ejecución el proceso P1, se incorpora a la cola de listos P2, al cual se le calcula su CU (CU = 4). Pero como el CU de P2 es menor que el CU de P1, entonces P1 es desalojado y P2 toma la U. En este caso P1 se reincorpora a la cola de listos porque no ha terminado su ejecución, y en ese instante se le vuelve a calcular el valor del CU (CU = 6).

Algoritmo de Planificación SJF

Fundamentos de Sistemas Operativos 1 Algoritmos de Planificación Luego llega el proceso P3 a la cola de listos y se le calcula el CU (CU = 1). Por lo que sucede igual que el caso anterior, el CU de P3 es menor que el CU de P2, por lo que se desaloja P2 para cederle la U a P3. P2 es reincorporado a la cola de listos porque no ha terminado su ejecución CU y se le vuelve a calcular su CU (CU = 3).

El proceso P4 se incorpora a la cola de listos y se le calcula su CU (CU = 4). Luego P3 termina su ejecución para cederle la U al próximo proceso que le corresponda según el criterio que establece el algoritmo. Para el ejemplo le corresponde el turno a P2, luego a P4 y finalmente a P1.

Algoritmo SJF sin Desalojo

Proceso

Tiempo de llegada

Ráfaga U (ms)

P1

0

7

P2

2

4

P3

4

1

P4

5

4

Tiempo de espera medio = (0 + 6 + 3 + 7)/4 = 4

2 Conclusiones ➢

Debemos tomar en consideración que este algoritmo SJF no se puede implementar en cualquier Sistema Operativo, sólo en aquellos que funcionan por lotes. En la actualidad no son muy utilizados ya que existen algoritmos

Algoritmo de Planificación SJF

Fundamentos de Sistemas Operativos 2 Algoritmos de Planificación mucho más eficientes y fáciles de implementar en cualquier sistema operativo para un mejor rendimiento del U ➢

Es importante tomar en cuenta que, por defecto, se realiza el primer proceso en entrar, y a continuación los siguientes aplicando los criterios del algoritmo SJF. Además cuanto existe un empate en las ráfagas de dos procesos, se necesita de otro algoritmo, normalmente FIFO, para desempatarles.

➢

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

➢

El algoritmo SJF nos da el mínimo tiempo de espera, por lo que en un sistema por lotes es muy óptimo. Pero los procesos sufren riesgo de inanición ya que los procesos lagos se mantienen mucho tiempo en tiempos muertos, además si se maneja el comportamiento con desalojo, los procesos largos no se ejecutarían.

1 Webgrafía ➢ ➢ ➢ ➢ ➢ ➢

http://www.slideshare.net/search/slideshow? searchfrom=header&q=algoritmo+sjf http://es.wikiversity.org/wiki/Sistemas_operativos#Curso_de_Sistemas_Opera tivos: http://www.slideshare.net/joss1991/planificacin-de-la-u/ http://www.slideshare.net/stefanosalvatori/planificacion-procesos-gral http://literaturafyr.blogspot.com/ http://bloglibros.com/categoria/juveniles/

Algoritmo de Planificación SJF