Planificacion Procesos Gral

50 %
50 %
Information about Planificacion Procesos Gral

Published on June 24, 2007

Author: stefanosalvatori

Source: slideshare.net

Description

Planificacion de procesos

Planificación de procesos Cecilia Hernández 2007-1

Planificación de Procesos Recordando cambio de contexto Cambiando CPU de un proceso a otro Procesos cambian de estados ejecución a bloqueado (ejecución instrucción I/O) bloqueado a listo por interrupciones Proceso espera por evento, evento se produce Reloj interrumpe y SO planifica a otro proceso Planificación: Elegir que proceso de la cola de listos ejecutar Planificación implica una decisión (política) Cambio de contexto es una forma de hacerlo (mecanismo)

Recordando cambio de contexto

Cambiando CPU de un proceso a otro

Procesos cambian de estados

ejecución a bloqueado (ejecución instrucción I/O)

bloqueado a listo por interrupciones

Proceso espera por evento, evento se produce

Reloj interrumpe y SO planifica a otro proceso

Planificación: Elegir que proceso de la cola de listos ejecutar

Planificación implica una decisión (política)

Cambio de contexto es una forma de hacerlo (mecanismo)

Multiprogramación y planificación Multiprogramación permite aumentar la utilización de recursos y productividad sobreponiendo E/S y procesamiento Que procesos/hebras ejecutar y por cuanto tiempo? 2 visiones para la planificación en CPU Largo plazo : determina nivel de multiprogramación Cuantos trabajos se cargan a memoria Ingresarlo a memoria o sacarlo (swapping) Corto plazo : qué trabajo ejecutar a continuación para proporcionar un buen servicio Ocurre frecuentemente, idea minimizar sobrecarga por cambio de contexto Idea de buen servicio depende de muchas cosas

Multiprogramación permite aumentar la utilización de recursos y productividad sobreponiendo E/S y procesamiento

Que procesos/hebras ejecutar y por cuanto tiempo?

2 visiones para la planificación en CPU

Largo plazo : determina nivel de multiprogramación

Cuantos trabajos se cargan a memoria

Ingresarlo a memoria o sacarlo (swapping)

Corto plazo : qué trabajo ejecutar a continuación para proporcionar un buen servicio

Ocurre frecuentemente, idea minimizar sobrecarga por cambio de contexto

Idea de buen servicio depende de muchas cosas

Objetivos de Planificación Maximizar la utilización de CPU ( CPU Utilization ) Maximizar la Productividad número de requerimientos atendidos por unidad de tiempo ( throughput ) Minimizar tiempo de respuesta promedio ( Response time ) Desde inicio hasta obtención primera respuesta de sistema Minimizar tiempo de espera promedio ( Waiting time ) Tiempo en cola de listos Minimizar tiempo que tarda en proceso ejecutarse completamente, de inicio a fin ( Turnaround time ) Favorecer algunos procesos, prioridad ( Priority ) Evitar espera indefinida Algunos sistemas favorecen algunos objetivos frente a otros Productividad. Sistema de procesamiento de transacciones Tiempo de respuesta. Sistema interactivo

Maximizar la utilización de CPU ( CPU Utilization )

Maximizar la Productividad número de requerimientos atendidos por unidad de tiempo ( throughput )

Minimizar tiempo de respuesta promedio ( Response time )

Desde inicio hasta obtención primera respuesta de sistema

Minimizar tiempo de espera promedio ( Waiting time )

Tiempo en cola de listos

Minimizar tiempo que tarda en proceso ejecutarse completamente, de inicio a fin ( Turnaround time )

Favorecer algunos procesos, prioridad ( Priority )

Evitar espera indefinida

Algunos sistemas favorecen algunos objetivos frente a otros

Productividad. Sistema de procesamiento de transacciones

Tiempo de respuesta. Sistema interactivo

Diferencia entre sistemas batch e interactivos Sistemas batch Importa maximizar throughput y minimizar turnaround time Sistemas interactivos Importa maximizar throughput y minimizar turnaround time y response time De acuerdo a como se comportan procesos o hebras en un sistema Procesos batch ( CPU-bound ) Procesos interactivos ( I/O-bound )

Sistemas batch

Importa maximizar throughput y minimizar turnaround time

Sistemas interactivos

Importa maximizar throughput y minimizar turnaround time y response time

De acuerdo a como se comportan procesos o hebras en un sistema

Procesos batch ( CPU-bound )

Procesos interactivos ( I/O-bound )

También importante para planificadores Típicamente tratan de evitar inanición (starvation) Cuando un proceso es prevenido de progresar porque otro proceso tiene el recurso que necesita Ejemplo. Procesos de alta prioridad no permiten a procesos de baja prioridad ejecutarse Inanición también se puede producir en hebras/procesos sincronizados

Típicamente tratan de evitar inanición (starvation)

Cuando un proceso es prevenido de progresar porque otro proceso tiene el recurso que necesita

Ejemplo. Procesos de alta prioridad no permiten a procesos de baja prioridad ejecutarse

Inanición también se puede producir en hebras/procesos sincronizados

Planificador Módulo que mueve trabajos entre colas Algoritmo de planificación determina que trabajo ejecutar a continuación Se ejecuta cuando Un trabajo pasa de listo a bloqueado Ocurre una interrupción del timer Se crea o termina un trabajo 2 tipos de sistemas de planificación No apropiativa Planificador espera que trabajo termine o ceda CPU Apropiativa Planificador interrumpe trabajo en ejecución y fuerza un context switch

Módulo que mueve trabajos entre colas

Algoritmo de planificación determina que trabajo ejecutar a continuación

Se ejecuta cuando

Un trabajo pasa de listo a bloqueado

Ocurre una interrupción del timer

Se crea o termina un trabajo

2 tipos de sistemas de planificación

No apropiativa

Planificador espera que trabajo termine o ceda CPU

Apropiativa

Planificador interrumpe trabajo en ejecución y fuerza un context switch

Planificación Apropiativa/No Apropiativa No Apropiativa . Una vez que procesos adquieren CPU no la liberan, excepto Proceso pasa a estado de espera (bloqueado) Proceso termina Apropiativa . SO puede decidir quitar CPU a proceso para dársela a otro Usa interrupciones de reloj

No Apropiativa . Una vez que procesos adquieren CPU no la liberan, excepto

Proceso pasa a estado de espera (bloqueado)

Proceso termina

Apropiativa . SO puede decidir quitar CPU a proceso para dársela a otro

Usa interrupciones de reloj

Algoritmos No 1 (FCFS) FCFS (First Come, First Served) Atención por orden de llegada Justo, simula mundo real (banco, supermercado, etc) Típicamente No Apropiativo Ejemplo: P1 : 24ms, P2 : 3ms, P3 : 3ms Tiempo de respuesta promedio? Tiempo de espera promedio? Ventajas? Desventajas?

FCFS (First Come, First Served)

Atención por orden de llegada

Justo, simula mundo real (banco, supermercado, etc)

Típicamente No Apropiativo

Ejemplo: P1 : 24ms, P2 : 3ms, P3 : 3ms

Tiempo de respuesta promedio? Tiempo de espera promedio?

Ventajas?

Desventajas?

FCFS (cont) Ventajas Ningún proceso espera indefinidamente Desventajas Tiempo de espera promedio puede ser alto, depende de: tiempo de ejecución de procesos orden de llegada procesos cortos tienen espera alta si están detrás de los largos Puede producir baja utilización de recursos cuando procesos esperan podrían ocupar otros recursos

Ventajas

Ningún proceso espera indefinidamente

Desventajas

Tiempo de espera promedio puede ser alto, depende de:

tiempo de ejecución de procesos

orden de llegada

procesos cortos tienen espera alta si están detrás de los largos

Puede producir baja utilización de recursos

cuando procesos esperan podrían ocupar otros recursos

Algoritmo No2 (SJF) Short-Job-First (SJF) Asocia cada proceso con el tiempo de ejecución, tiempo que ocupo CPU la ultima vez antes de cambiarse a estado de espera CPU es asignada a proceso con el menor tiempo de ejecución Si dos procesos tienen igual tiempo de ejecución se aplica FCFS Calcule tiempo de respuesta y espera promedios usando ejemplo anterior Puede ser apropiativo y no apropiativo

Short-Job-First (SJF)

Asocia cada proceso con el tiempo de ejecución, tiempo que ocupo CPU la ultima vez antes de cambiarse a estado de espera

CPU es asignada a proceso con el menor tiempo de ejecución

Si dos procesos tienen igual tiempo de ejecución se aplica FCFS

Calcule tiempo de respuesta y espera promedios usando ejemplo anterior

Puede ser apropiativo y no apropiativo

SJF (cont) Versión apropiativa Shortest-Remaining-Time-First Calcula tiempo de ejecución mas corto y tiempo de llegada Ejemplo: Calcular tiempo de respuesta y espera promedio Proceso Tiempo llegada Tiempo ejecución P1 0 8 P2 1 4 P3 2 9 P4 3 5

Versión apropiativa Shortest-Remaining-Time-First

Calcula tiempo de ejecución mas corto y tiempo de llegada

Ejemplo: Calcular tiempo de respuesta y espera promedio

Proceso Tiempo llegada Tiempo ejecución

P1 0 8

P2 1 4

P3 2 9

P4 3 5

SJF (cont) Ventajas Parece perfecto Mejor tiempo de espera promedio que FCFS Desventajas Espera indefinida? Como estimar tiempo de procesamiento de próximo requerimiento de proceso?

Ventajas

Parece perfecto

Mejor tiempo de espera promedio que FCFS

Desventajas

Espera indefinida?

Como estimar tiempo de procesamiento de próximo requerimiento de proceso?

Algoritmo No 3: (RR) Round Robin (RR) Cola de procesos listos tratada como cola FIFO circular A cada proceso se le entrega CPU por un periodo de tiempo, llamado quantum Proceso se ejecuta por la duración del quantum o hasta que pasa a bloqueado Ejemplo P1 : 24 ms, P2 : 3ms, P3 : 3ms, quantum 4ms Ventajas ? Estupendo para procesos interactivos (sistemas de tiempo compartido)

Round Robin (RR)

Cola de procesos listos tratada como cola FIFO circular

A cada proceso se le entrega CPU por un periodo de tiempo, llamado quantum

Proceso se ejecuta por la duración del quantum o hasta que pasa a bloqueado

Ejemplo P1 : 24 ms, P2 : 3ms, P3 : 3ms, quantum 4ms

Ventajas ?

Estupendo para procesos interactivos (sistemas de tiempo compartido)

RR (cont) Desventajas Valor del quantum muy importante en rendimiento de RR Problemas si es muy chico? Tiempo de overhead por cambio de contexto Problemas si es muy grande? Se acerca a FCFS Recomendación 80% de tiempo de ejecución de procesos (cada requerimiento antes de bloquearse) debería ser mas cortas que quantum

Desventajas

Valor del quantum muy importante en rendimiento de RR

Problemas si es muy chico?

Tiempo de overhead por cambio de contexto

Problemas si es muy grande?

Se acerca a FCFS

Recomendación

80% de tiempo de ejecución de procesos (cada requerimiento antes de bloquearse) debería ser mas cortas que quantum

Algoritmo No 4 : Prioridades Asignar prioridades a procesos Ejecutar proceso con mayor prioridad Si hay procesos con igual prioridad, aplicar FCFS SJF, prioridad es tiempo de próximo requerimiento Ejemplo: Proceso Tiempo Ejecución Prioridad P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2

Asignar prioridades a procesos

Ejecutar proceso con mayor prioridad

Si hay procesos con igual prioridad, aplicar FCFS

SJF, prioridad es tiempo de próximo requerimiento

Ejemplo:

Proceso Tiempo Ejecución Prioridad

P1 10 3

P2 1 1

P3 2 4

P4 1 5

P5 5 2

Prioridades (cont) Como asignar prioridades Internamente por SO, en base a uso de recursos (memoria, archivos, etc) Externamente (no por SO) de acuerdo a importancia de procesos Espera indefinida Si continuamente llegan procesos de alta prioridad, los de baja prioridad esperan indefinidamente Solución Espera indefinida Envejecimiento aumentar prioridad como función acumulada en el tiempo decrementar prioridad como función acumulada de tiempo de procesamiento

Como asignar prioridades

Internamente por SO, en base a uso de recursos (memoria, archivos, etc)

Externamente (no por SO) de acuerdo a importancia de procesos

Espera indefinida

Si continuamente llegan procesos de alta prioridad, los de baja prioridad esperan indefinidamente

Solución Espera indefinida

Envejecimiento

aumentar prioridad como función acumulada en el tiempo

decrementar prioridad como función acumulada de tiempo de procesamiento

Combinando Algoritmos En la práctica los sistemas actuales usan una combinación de estos algoritmos (RR, Prioridad, SJF) Ejemplo: Múltiples colas retroalimentadas Tiene jerarquía de colas Tiene prioridades para ordenar las colas Nuevos procesos entran a cola de mayor prioridad Cada cola planificada con RR Quantums son distintos en cada cola Procesos se cambian de colas en base a historia

En la práctica los sistemas actuales usan una combinación de estos algoritmos (RR, Prioridad, SJF)

Ejemplo: Múltiples colas retroalimentadas

Tiene jerarquía de colas

Tiene prioridades para ordenar las colas

Nuevos procesos entran a cola de mayor prioridad

Cada cola planificada con RR

Quantums son distintos en cada cola

Procesos se cambian de colas en base a historia

Múltiples Colas Retroalimentadas Idea, separar procesos en base a sus necesidades de ejecución Procesos interactivos están en las colas de mayor prioridad Procesos que usan mucha CPU se cambian a colas de menor prioridad Procesos que llevan mucho tiempo en el sistema se cambian a colas de mayor prioridad

Idea, separar procesos en base a sus necesidades de ejecución

Procesos interactivos están en las colas de mayor prioridad

Procesos que usan mucha CPU se cambian a colas de menor prioridad

Procesos que llevan mucho tiempo en el sistema se cambian a colas de mayor prioridad

Planificación en UNIX Usa múltiples colas realimentadas De acuerdo a tipo de proceso procesos de tiempo compartido procesos de sistema Procesos de tiempo real Planificación por prioridad entre distintas colas y RR dentro de cada cola Procesos con alta prioridad siempre se ejecutan primero Procesos con la misma prioridad se planifican con RR Procesos cambian prioridad dinámicamente Se incrementa si proceso hace E/S antes de terminar quantum Se decrementa si proceso usa todo su quantum Objetivo? Premiar procesos interactivos Típicamente usan CPU por periodos pequeños de tiempo

Usa múltiples colas realimentadas

De acuerdo a tipo de proceso

procesos de tiempo compartido

procesos de sistema

Procesos de tiempo real

Planificación por prioridad entre distintas colas y RR dentro de cada cola

Procesos con alta prioridad siempre se ejecutan primero

Procesos con la misma prioridad se planifican con RR

Procesos cambian prioridad dinámicamente

Se incrementa si proceso hace E/S antes de terminar quantum

Se decrementa si proceso usa todo su quantum

Objetivo?

Premiar procesos interactivos

Típicamente usan CPU por periodos pequeños de tiempo

Planificador Linux Soporta: una CPU SMP (Simultaneous Multi-Processors) Multiprocesadores en un chip o no, cada uno con caches y compartiendo Memoria Principal SMT (Simultaneous Multi-Threading) Procesador con recursos adicionales para soportar hebras. Sistema con Memoria principal compartida NUMA (Non- Uniform Memory Access) Unico sistema usando mas de un nodo (una máquina con un procesador o un multiprocesador es decir con propia CPU o set de CPUs y memorias)

Soporta:

una CPU

SMP (Simultaneous Multi-Processors)

Multiprocesadores en un chip o no, cada uno con caches y compartiendo Memoria Principal

SMT (Simultaneous Multi-Threading)

Procesador con recursos adicionales para soportar hebras. Sistema con Memoria principal compartida

NUMA (Non- Uniform Memory Access)

Unico sistema usando mas de un nodo (una máquina con un procesador o un multiprocesador es decir con propia CPU o set de CPUs y memorias)

Planificador de CPU en Linux 2.4 2 algoritmos para planificación de procesos Uno para procesos de tiempo compartido, en donde CPU se multiplexa en forma justa entre procesos Una para procesos con requermientos de tiempo real, donde prioridades absolutas son más importantes que justicia Algoritmo para procesos que comparten tiempo Prioridades y créditos asociadas a proceso Proceso con más créditos se ejecuta primero A cada interrupción del timer se decrementan créditos de proceso en ejecución. Cuando llega a 0 se planifica el siguiente proceso Cuando créditos de todos los procesos listos es 0, créditos se recalculan para todos los procesos (incluyendo los bloqueados) créditos = (créditos/2) + prioridad

2 algoritmos para planificación de procesos

Uno para procesos de tiempo compartido, en donde CPU se multiplexa en forma justa entre procesos

Una para procesos con requermientos de tiempo real, donde prioridades absolutas son más importantes que justicia

Algoritmo para procesos que comparten tiempo

Prioridades y créditos asociadas a proceso

Proceso con más créditos se ejecuta primero

A cada interrupción del timer se decrementan créditos de proceso en ejecución. Cuando llega a 0 se planifica el siguiente proceso

Cuando créditos de todos los procesos listos es 0, créditos se recalculan para todos los procesos (incluyendo los bloqueados)

créditos = (créditos/2) + prioridad

Algoritmo Planificador Linux 2.4 vs 2.6 Diferencias entre version 2.4 y 2.6 Algoritmos de 2.4 del orden O(n) Tiempo ejecución varía linealmente al aumentar tamaño entrada Algoritmos de 2.6 del orden O(1) Tiempo ejecución constante independiente del número de tareas a ejecutar en sistema Estructuras básicas en 2.6 Runqueues Priority arrays

Diferencias entre version 2.4 y 2.6

Algoritmos de 2.4 del orden O(n)

Tiempo ejecución varía linealmente al aumentar tamaño entrada

Algoritmos de 2.6 del orden O(1)

Tiempo ejecución constante independiente del número de tareas a ejecutar en sistema

Estructuras básicas en 2.6

Runqueues

Priority arrays

Algunos problemas mejorados en 2.6 Planificación de tareas de tiempo real (soft) Mayor rapidez en atender este tipo de tareas Algunos problemas para procesos que parecen interactivos (I/O-bound) Procesos/hebras que usan mucho E/S considerados como interactivos A veces están relacionados con BD no necesariamente interactivos Procesos/hebras que son CPU-bound e I/O-bound pueden anular efectos de boost y penalidad de planificador Mayor información http://www.inf.udec.cl/~chernand/links/ linux_cpu_scheduler.pdf

Planificación de tareas de tiempo real (soft)

Mayor rapidez en atender este tipo de tareas

Algunos problemas para procesos que parecen interactivos (I/O-bound)

Procesos/hebras que usan mucho E/S considerados como interactivos

A veces están relacionados con BD no necesariamente interactivos

Procesos/hebras que son CPU-bound e I/O-bound pueden anular efectos de boost y penalidad de planificador

Mayor información

http://www.inf.udec.cl/~chernand/links/ linux_cpu_scheduler.pdf

Resumen Planificación de procesos puede influenciar fuertemente el rendimiento Como? Generalmente, múltiples objetivos tienen conflictos Como? Existen diversos algoritmos puros, pero normalmente los sistemas implementan lo bueno de varios

Planificación de procesos puede influenciar fuertemente el rendimiento

Como?

Generalmente, múltiples objetivos tienen conflictos

Como?

Existen diversos algoritmos puros, pero normalmente los sistemas implementan lo bueno de varios

Add a comment

Related presentations

Related pages

planificación gral + objs y recursos

procesos interrelacionados, son distintos y deben considerarse analítica y ... Microsoft Word - planificación gral + objs y recursos.doc Author: Fer
Read more

Planificación de Procesos

Planificación de procesos Cecilia Hernández 2007-1 Multiprogramación y planificación Multiprogramación permite aumentar la utilización de recursos y ...
Read more

PLANIFICACIÓN, COMUNICACIÓN Y GESTIÓN by Agustina ...

PROCESOS DE PLANIFICACIÓN Y GESTIÓN Proyecto Extensión BRAINSTORM ELEMENTS copy and paste as needed and take advantage of an infinite canvas! COMUNICACIÓN
Read more

DOCUMENTOS DE LECTURA: planificación, una hipótesis para ...

Dirección Gral. de Cultura y Educación Dirección de Educación Física 1 La planificación, una hipótesis para orientar la enseñanza en Educación ...
Read more

Planificación y presupuestación de programas de ...

Flujo de procesos... 1. Introduce valores de planificación al nivel de medidas y solicitudes de medida. 2. Transfiere los ...
Read more

Ministerio de Educación del Ecuador Ministerio de ...

Av. Amazonas N34-451 entre Av. Atahualpa y Juan Pablo Sanz, Telf. 3961300/1400/1500 Quito Ecuador www.educacion.gob.ec 5 PROCESOS ADJETIVOS DE ASESOR˝A
Read more