Planificación de monoprocesadoresumh2812.edu.umh.es/wp-content/uploads/sites/510/2013/02/... · • FCFS • SJF • SRT • Prioridades • Round Robin • Colas Multinivel. DSO

DSO 2015

Planificación demonoprocesadores

DSO 2015 2 Planificación

Índice

1) Objetivos de la PlanificaciónColas Planificación

2) Tipos de Planificación3) Criterios Planificación

Prioridades

4) Políticas de Planificación• FCFS• SJF• SRT• Prioridades• Round Robin• Colas Multinivel


Objetivos de la planificación

Comportamiento de un proceso durante su ejecución

•La ejecución típica de un proceso consta de fases en las que se alternan la ejecución en CPU y los periodos de espera debido a operaciones de entrada/salida.


Objetivos de la planificación• Se ha visto el

concepto de multiprogramación como técnica para ejecutar simultáneamente varios procesos

• ¿Como decide el so que proceso ejecutar en cada momento?


Objetivos de la planificación

• El propósito de la planificación es asignar recursos de manera q se cumplan una serie de objetivos

• Reparto de CPU equitativo (entre todos los procesos)• Eficiencia (optimizar uso CPU)• Mejor tiempo de respuesta en uso interactivo (consola remota)• Mayor número de trabajos por unidad de tiempo• Evitar la sobrecarga del sistema• Optimización de diversos parámetros (tr,te,..


Tipos de Planificación� Existen tres tipos de planificadores de procesador

� Planificador a largo plazo� Controla el grado de multiprogramación

� Planificador a corto plazo� Selecciona entre los trabajos cargados en memoria y que están

preparados para ejecutarse cual hará uso del procesador� El planificador a corto plazo debe ser muy rápido ya que entra en

juego con una frecuencia muy alta

� Planificador a medio plazo� Carga y descarga trabajos desde el disco a la memoria y de la

memoria al disco en función del grado de sobrecarga del sistema.


Planificación a largo plazo

l Determina cuáles son los programas admitidos en el sistema. Una vez admitidos se añade a listos si hay RAM, sino a SUSPENDIDOS

l Controla el numero de procesos en el sistema.

l Cuantos más procesos se crean, menor es el porcentaje de tiempo en el que cada proceso se puede ejecutar (mas se tarda en terminar).


Planificación a medio plazo

l Forma parte de la función de intercambio.

l Se basa en la necesidad de controlar el grado de multiprogramación.


Planificación a corto plazo

l También conocido como distribuidor.

l Es el de ejecución más frecuente.

l Se ejecuta cuando ocurre un suceso:– Interrupciones del reloj.– Interrupciones de E/S.– Llamadas al sistema operativo.– Señales

• El principal objetivo es repartir el tiempo de procesador de manera que se optimicen diversos parametros:


Planificación

a largo plazo

Planificación

a largo plazo

Planificación

a medio plazo

Planificación

a corto plazo

Planificación

a medio plazo

Nuevo

Listo/suspendido

Bloqueado

Listo Ejecutando Salida

Bloqueado/suspendido

Figura 9.1. Planificación y transiciones de estado de los procesos.


Planificacióna largo plazo

Usuariosinteractivos

Planificacióna medio plazo

Planificacióna corto plazo

Planificacióna medio plazo

Ocurre un suceso

Trabajospor lotes

Quantum

Cola de listos

Cola de listos suspendidos

Cola de bloqueados suspendidos

Cola de bloqueados

TerminaciónProcesador

Espera de un suceso

Figura 9.3. Diagrama de colas de planificación.


Criterios de planificación

• Cola de Trabajos nuevos• Trabajos a la espera de ser admitidos en el sistema

• Colas de Listos• Procesos con memoria y otros recursos, a la espera de ser

ejecutados en CPU

• Cola de bloqueados por E/S• Procesos en espera de asignación dispositivo

• Cola de Suspendidos• Procesos en memoria secundaria

COMO SE ORDENAN?


� Utilización del procesador� Maximizar el rendimiento del procesador

� Rendimiento (“Throughput”)� Trabajos completados por unidad de tiempo

� Tiempo de estancia (“Turnaround time”)� Tiempo transcurrido desde que se lanza hasta que

finaliza� Tiempo de espera

� Por operaciones de E/S o por otros aspectos� Tiempo de respuesta

� Importante en aplicaciones interactivas o de TR

Criterios de planificación


Criterios de la planificación a corto plazo

– Tiempo de respuesta: Tr• Tiempo q tarda un proceso en tomar el procesador despues del

estado Bloqueado.– Tiempo de retorno-estancia-permanencia Tt

• T transcurrido entre el lanzamiento de un proceso y su finalizacion, T q tarda en ejecutarse

– Tiempo de espera Tw• Tiempo q el proceso pasa en la cola listos

– Productividad• Procesos terminados por unidad de tiempo

– Utlizacion de CPU


Tiempo de estancia de C


Tiempo de Espera


Tiempo de Respuesta

Políticas de Planificación


Planificación FCFS

� Primero en entrar, primero en salir� Se lleva a cabo manejando la cola de procesos

preparados como una cola FIFO� Es el algoritmo más sencillo de codificar� Características y prestaciones:

– Puede que un proceso corto tenga que esperar mucho tiempo antes de que pueda ser ejecutado.

– Favorece a los procesos con carga de CPU:• Los procesos con carga de E/S tienen que esperar a que se

completen los procesos con carga de CPU.


Eficiencia FIFO

� Los tiempos de estancia y respuesta varían fuertemente de un momento a otro

� Los tiempos medios de retorno son menores en el segundo caso que en el primero

Trabajo 1 Trabajo 2 Trabajo 3

0 20 24 32

Trabajo 1Trabajo 2 Trabajo 3

0 104 32


Shortest Job First (SJF)

� Asocia de forma dinámica a cada proceso la longitud de su siguiente ráfaga de CPU

� Asigna la CPU al trabajo con la ráfaga más pequeña

� Este algoritmo es óptimo para reducir los tiempos medios de espera

� Su dificultad es conocer cuáles van a ser las duraciones de las próximas ráfagas de CPU de cada proceso

� ¿Cómo se estima la duración de la siguiente ráfaga de CPU?


Método de predicción

� La siguiente ráfaga de CPU se predice como una media exponencial de las longitudes medias en anteriores ráfagas

� Sea:� tn: longitud de la n-ésima ráfaga de CPU� τn: valor predicho para la n-ésima ráfaga de CPU� α : parámetro de ajuste

τn+1 = α tn + (1-α) τn� tn: contiene la información más reciente� τn: contiene la historia pasada


Shortest Job First (SJF)

• Se reduce la previsibilidad de los procesos largos. • Si la estimación de tiempo del proceso no es

correcta, el sistema puede abandonar el trabajo. • Posibilidad de inanición para los procesos largos.


Algoritmos de prioridad

� Se asocia una prioridad a cada proceso y la CPU se asigna al trabajo con la prioridad más alta

� Las prioridades pueden definirse de dos formas:� Internamente� Externamente

� Problema: posible inanición (“starvation”) de determinadas solicitudes


Prioridad

• Las prioridades son estaticas permanecen fijas con un valor asignado previamente. Son fáciles de implementar y tienen un coste asociado bajo, aunque no son sensibles a la carga.

• Las dinamicas se asignan dinamicamente. Tienen una implementación más elaborada y una sobrecarga en cambios de contexto, pero se adaptan mejor a los cambios de carga y al comportamiento de los procesos.

• Los procesos de prioridad más baja pueden sufrir inanición, SOLUCION

» Permitir que un proceso cambie su prioridad en función de su permanencia en la cola de listos


Algoritmos expulsores

� En los algoritmos anteriores, una vez que la CPU ha sido asignada a un proceso, éste la mantiene hasta que pide una E/S o termina

� ¿Cómo hacer que la CPU sea retirada a un proceso una vez asignada?

� Prioridad con requisa (“preemption”):

Trabajo 3Trabajo 2Trabajo 1

0 73 23

Trabajo 1

Llega el Trabajo 2

12


Politicas expulsoras

l No expulsora: (No preferente-No preemptiva-)

l Una vez que el proceso pasa al estado de Ejecución, continúa ejecutandose hasta que termina o se bloquea en espera de una E/S.

l Expulsora: (Preferente-preemptiva)

l El proceso que se está ejecutando actualmente puede ser interrumpido y pasado al estado de Listos por el sistema operativo.

l Permiten dar un mejor servicio ya que evitan que un proceso pueda monopolizar el procesador durante mucho tiempo.

l La decision de apropiarse de la CPU, se lleva a cabo:§ Cuando llega un nuevo proceso§ Cuando un proceso pasa de estado Bloqueado a Listo § Por una interrupcion periodica


Algoritmos “round robin”

� Usados en sistemas de tiempo compartido� La CPU se asigna a cada proceso

preparado durante un cuanto de tiempo “q”� La cola de procesos preparados es FIFO

� Si la ráfaga de CPU > q ⇒ Interrupción TIME-OUT� Si la ráfaga de CPU < q ⇒ Liberación de CPU

� Prestaciones: dependen fuertemente de q� q → ∞ ⇒ round-robin degenera en FCFS� q → 0 ⇒ CPU/n


Algoritmos “round robin”

� Si “q” es muy pequeño se pierde mucho tiempo en el cambio de contexto. Disminuye la eficacia del procesador

� Si “q” es grande, los tiempos de respuesta aumentan

� Regla empírica: el 80% de las ráfagas de CPU deben ser menores que el cuanto

� Problema: sólo existe una cola de trabajos preparados, no distingo entre tipos de trabajos


Colas multinivel

� Dividen la cola de preparados en colas separadas en función del tipo de trabajo

� Cada cola tiene su propio algoritmo de planificación

� Debe existir otro algoritmo para elegir la cola en cada momento

Tareas del sistema

Prioridad baja

Prioridad alta

Tareas interactivas

Tareas de edición

Tareas batch


Colas multinivel realimentadas

� Los trabajos se mueven. Consideraciones:� El algoritmo de planificación de cada cola� Métodos para “ascender” y “descender”� Dónde poner inicialmente a los trabajos

Quantum = 10

Quantum = 20

FCFS


Diagramas de Gantt

•Para simplificar la explicación de las diferentes políticas de planificación se consideran tan sólo las fases de CPU de un proceso.•La planificación de un conjunto de procesos se representa mediante los diagramas de Gantt•Un diagrama de Gantt es una secuencia de rectángulos horizontales con una escala de tiempo que comienza en cero en la izquierda y que representa la ejecución secuencial de un conjunto de procesos.•La separación entre dos rectángulos adyacentes representa la ejecución del cambio de contexto y del algoritmo de planificación


Ejemplo Diagrama Gantt


Algoritmos de planificación de procesos

Proceso Instante de llegada Tiempo de servicio


Ejemplo FCFS (I)


Ejemplo FCFS (II)

Penaliza los cortos


Planificación en LINUX

Documents

Planificación de monoprocesadoresumh2812.edu.umh.es/wp-content/uploads/sites/510/2013/02/... · • FCFS • SJF • SRT • Prioridades • Round Robin • Colas Multinivel. DSO