Embed Size (px)
Citation preview
Programas vs Procesos
Curso 2009/2010
• Programa: datos e instrucciones.• Un proceso es un programa en ejecución: datos, instrucciones, recursos y
estado.• El SO carga el programa en memoria para su ejecución: las instrucciones
van accediendo a los datos que necesiten y guardando resultados en la zonade memoria asignada.
Instrucciones
Instrucciones
Datos
Datos
PROGRAMA
MEMORIA
SISTEMA OPERATIVO
Concepto de Multiprogramación
Curso 2009/2010
• El objetivo es aprovechar los tiempos muertos de la CPU paraejecutar otros programas, consiguiendo con ello un mejoraprovechamiento de los recursos del ordenador (gracias al incrementode uso del procesador).
• Crea la falsa apariencia de ejecución simultánea de varios programas:en cada instante sólo podrá ejecutarse un programa en la CPU, perocomo los restantes están realizando operaciones de E/S sobre losdispositivos, el usuario tendrá la sensación de que todos están enejecución.
Gestión de Ejecución de Programas
Curso 2009/2010
• El SO crea las estructuras necesarias para gestionar todos los recursosnecesarios durante la ejecución de los programas cargados en memoria.
• Estos datos se reúnen en el Bloque de Control del Sistema (SCB):• Lista de descriptores de los procesos.• Puntero al descriptor del proceso que ocupa actualmente la CPU
(proceso en ejecución).• Puntero a la cola de descriptores de los procesos que están esperando
para poder usar el procesador (procesos preparados).• Puntero a la cola de descriptores de los procesos que no están usando la
CPU, y que están esperando a que se produzca algún evento, como lafinalización de una operación de E/S (procesos en espera)).
• Puntero a la cola de descriptores de los procesos que no están usando laCPU por no estar activos pero que, ante una orden de activación, podríanseguir ejecutándose (interrupciones).
Estado del Proceso
Curso 2009/2010
• Nuevo: El proceso está siendo creado.• En ejecución: Se están ejecutando las instrucciones.• En espera: El proceso está esperando a que se produzca un suceso
(fin de operación E/S o recepción de señal).• Preparado: El proceso está a la espera de que le asignen a un
procesador.• Terminado: Ha terminado la ejecución del proceso.
nuevo
preparado en ejecución
en espera
terminado
admitido salidainterrupción
terminación deoperaciónE/S
en espera de sucesoo de operación E/S
Información del Proceso
Curso 2009/2010
• Se almacena en el Bloque de Control del Proceso (PCB):• Identificador del proceso (PID).• Tipo de proceso.• Privilegios.• Prioridad.• Estado CPU.• Contador de programa.• Registros.• Estado del proceso.• Recursos.• Mapa de memoria donde se haya cargado el proceso.• Ficheros abiertos.• Jerarquía de procesos: proceso padre y procesos hijos.
• Objetivo: Preservar la información del proceso en el caso de que suejecución tenga que ser temporalmente suspendida (cambio decontexto).
Prioridades
Curso 2009/2010
• Mecanismo que permite definir la urgencia con la que debe ejecutarse unproceso (la prioridad que tiene frente a otros procesos).
• Número entero: típicamente si Prioridad (A) > Prioridad (B) ⇒ A es másprioritario que B.
• Tipos de prioridades:• Asignadas por el SO.• Asignadas por el propietario.• Estáticas: no pueden ser modificadas durante la ejecución del proceso.
Nunca en sistemas de tiempo real.• Dinámicas: Un proceso puede modificar su prioridad para poder atender
adecuadamente a todos los eventos que se produzcan.
Interrupciones
Curso 2009/2010
• Señal del HW ante un evento ajeno a la ejecución normal del proceso.• Tras tratar la interrupción, el SO debe recuperar la ejecución del proceso en
el punto en el que estaba antes de la misma.
Cambio de Contexto
Curso 2009/2010
• Se produce cuando se requiere la atención de algún servicio del SO(interrupción, llamada al SO, ejecución de instrucción privilegiada, etc).
• El SO salva el estado del proceso en su PCB, o lo restaura desde los datosalmacenados en dicho bloque para continuar su ejecución en la CPU.
Salva elestado delproceso
Repone elestado delproceso
Ejecucióndel SO
Cambio de contexto
Cambio de contexto
Llamada al SOo interrupción
Cambio de Proceso
Curso 2009/2010
Salva elestado delproceso A
Repone elestado delproceso B
Ejecucióndel SO
Salva elestado delproceso B
Repone elestado delproceso A
Ejecucióndel SO
Llamada al SOo interrupción
Proceso A Proceso B
Planificación de Procesos
Curso 2009/2010
• Multiprogramación: tener en ejecución varios procesos al mismo tiempo paramaximizar utilización de CPU.
• Sistemas de tiempo compartido: conmutar rápidamente la CPU entre losprocesos en memoria de forma que los usuarios puedan interactuar con losprogramas en ejecución.
• Planificador de CPU: decide cuál de los procesos cargados en memoriapasará a ejecutarse en la CPU.• El planificador no le da a cada proceso el tiempo de CPU que precisa de
forma consecutiva ⇒ ráfaga de CPU.• Sucesión de ráfagas de CPU y operaciones E/S.
• Agenda de contenidos:1. Colas de planificación.2. Tipos de planificadores.3. Criterios de planificación.4. Algoritmos de planificación.
Colas de Planificación
Curso 2009/2010
• Cola de trabajos: almacena los procesos que entran en el sistema.• Cola de procesos preparados: lista enlazada de los PCBs de los procesos
que están cargados en memoria esperando a ocupar la CPU.• Cola del dispositivo: lista enlazada de PCBs de los procesos que están
esperando para poder acceder al dispositivo.
Tipos de Planificadores
Curso 2009/2010
• Planificador a largo plazo o planificador de trabajos:• ¿Qué trabajos se cargan en memoria para ser ejecutados en CPU?• Controla el grado de multiprogramación del sistema.• Alcanzar equilibrio entre procesos limitados por E/S (muchas
operaciones de E/S y pocos cálculos) y procesos limitados por la CPU(muchos cálculos y operaciones E/S esporádicas).
• Planificador a corto plazo o planificador de CPU:• ¿Cuál de los procesos cargados en memoria se ejecutará en CPU?• Con apropiación (un proceso puede desalojar a otro de la CPU) o sin
apropiación (el proceso que ocupa la CPU no puede ser desalojado hastaterminar su ejecución o conmutar a estado de espera).
• Mayor frecuencia de ejecución que el planificador de trabajos.
• Planificador a medio plazo:• Intercambio: Elimina procesos de la memoria (dejando de contender por
la CPU) para luego volver a cargarlos.• Para mejorar la combinación de procesos E/S y limitados por CPU o por
restricciones de la memoria del sistema.
Criterios para elegir un Algoritmo de Planificación
Curso 2009/2010
• Tiempo de servicio: tiempo de carga en memoria + tiempo de espera en colade procesos preparados + tiempo en CPU + tiempo consumido enoperaciones E/S
• Tiempo de ejecución: tiempo en CPU + tiempo consumido en operacionesE/S
• Tiempo de procesador : tiempo de ejecución en CPU• Tiempo de espera: tiempo en cola de procesos preparados + tiempo
consumido en operaciones de E/S• Rendimiento: tiempo de CPU de todos los procesos
tiempo total de CPU
• Eficiencia: Número de procesos ejecutados por unidad de tiempo.
Algoritmos de Planificación
Curso 2009/2010
• FCFS (First-Come, First-Served)• RR (Round-Robin)• SJF (Shortest-Job-First)• Planificadores por prioridades• Planificación mediante colas multinivel• Planificación mediante colas multinivel realimentadas
FCFS: First-Come, First-Served
Curso 2009/2010
• Se asigna en primer lugar la CPU al proceso que primero la solicite.• Cuando un proceso entra en la cola de procesos preparados, su PCB se
coloca al final de la cola FIFO.• Cuando la CPU queda libre, se asigna el procesador al proceso cuyo PCB
está al principio de la cola (y se elimina de la misma).• Tiempo medio de espera en cola varía significativamente si la duración de
las ráfagas de CPU de los procesos es muy variable.• Produce efecto convoy :
• Procesos intensivos en E/S están esperando a que un proceso conráfaga de CPU larga deje libre el procesador.
• Consecuencias: Utilización de CPU y dispositivos de E/S menor que laque se conseguiría si se permitiera a los procesos más cortos ejecutarseprimero.
• Es un algoritmo colaborativo (sin apropiación) ⇒ Inapropiado para sistemasde tiempo compartido.
SJF: Shortest-Job-First
Curso 2009/2010
• El algoritmo asocia a cada proceso la duración de su siguiente ráfaga deCPU.
• El planificador asigna la CPU al proceso (de la cola de procesos preparados)que tiene menor ráfaga de CPU.
• En caso de empate, se resuelve mediante FCFS.• SJF proporciona el tiempo medio de espera mínimo para un conjunto de
procesos.• SJF puede ser apropiativo o colaborativo.• SJF con apropiación se llama SRT (Shortest-Remaining-Time):
apropiación cuando la ráfaga de CPU del proceso que acaba de llegar esmenor que el tiempo de ejecución que le queda al que ocupa el procesador.
• Problema: ¿cómo conocer la duración de la siguiente ráfaga de CPU delproceso?• En planificador a largo plazo en un sistema por lotes, se usa como
duración de la ráfaga el límite de tiempo del proceso que especifique elusuario en el momento de enviar el trabajo.
• En planificador a corto plazo se predice la duración de la siguiente ráfaga(porque no hay forma de conocerla).
SJF: Mecanismo de predicción de la siguiente ráfaga de CPU
Curso 2009/2010
• Se asigna la CPU al proceso que tenga la siguiente ráfaga de CPU predichamás corta.
• Se predice el valor de la siguiente ráfaga asumiendo que su duración serásimilar a la de las ráfagas anteriores.
• La siguiente ráfaga se predice como la media exponencial de las duracionesmedias de las anteriores ráfagas de CPU.
• Sean tn la duración de la n-ésima ráfaga de CPU y τn+1 el valor predichopara la siguiente ráfaga del proceso. Para α ∈ [0, 1], se tiene que:
τn+1 = α · tn + (1 − α) · τn (1)
• tn contiene la información más reciente y τn el historial pasado.• Si α = 0: τn+1 = τn ⇒ el historial reciente no tiene efecto.• Si α = 1: τn+1 = tn ⇒ sólo la ráfaga de CPU más reciente importa
(historial obsoleto).
RR: Round-Robin o Planificación por Turnos
Curso 2009/2010
• Algoritmo con apropiación diseñado especialmente para sistemas de tiempocompartido.
• Los procesos nuevos se añaden al final de la cola (FIFO) de procesospreparados.
• El planificador toma el primer proceso de la cola y se asigna la CPU duranteun quantum de tiempo (típicamente entre 10 y 100 ms).
• Si la ráfaga del proceso es menor que el quantum ⇒ el proceso liberavoluntariamente la CPU.
• Si la ráfaga es mayor que el quantum ⇒ interrupción al SO, cambio decontexto y el proceso se coloca al final de la cola de procesos preparados.
• Si hay n procesos en la cola de procesos preparados y el quantum es q,cada proceso obtiene 1
ndel tiempo de CPU en partes de como máximo q
unidades de tiempo. Cada proceso no tiene que esperar más de (n − 1) · qunidades de tiempo hasta obtener su siguiente turno.
RR: Dimensionando el Quantum
Curso 2009/2010
• Si quantum muy largo ⇒ RR degenera en FCFS.• Si quantum muy corto ⇒ compartición del procesador (impresión de que
cada proceso tiene su propio procesador ejecutándose 1
nde la velocidad del
procesador real).• El quantum conviene que sea grande con respecto al tiempo requerido por
un cambio de contexto (si el quantum es corto, los procesos no acaban deejecutarse en la CPU y se ralentiza la ejecución debido a cambios decontexto).
• Si quantum excesivamente corto ⇒ vapuleo: el rendimiento de CPU sereduce mucho porque sólo se hacen cambios de contexto (trabajo no útil).
• El tiempo medio de ejecución mejora si la mayor parte de los procesosterminan su siguiente ráfaga de CPU en un quantum.
• Regla práctica: 80% de las ráfagas de CPU deben ser más cortas que elquantum de tiempo.
Planificación por prioridades
Curso 2009/2010
• A cada proceso se le asigna una prioridad y el planificador asigna la CPU alproceso más prioritario.
• Ejemplos: FCFS (orden de llegada) y SJF (duración siguiente ráfaga deCPU).
• Típicamente se expresa mediante rango de números fijos.• No hay consenso sobre si el mayor número corresponde a la mayor o a la
menor prioridad.• Las prioridades pueden definirse interna o externamente:
• Prioridades internas = f(requisitos de memoria, número de archivosabiertos, relación entre ráfaga promedio E/S y ráfaga promedio CPU, etc)
• Prioridades externas = f(criterios externos al SO)
• Puede ser sin apropiación o con apropiación (un proceso expulsa de la CPUa otro si es más prioritario).
• Problema: bloqueo indefinido o inanición ⇒ los procesos menos prioritariospueden esperar indefinidamente.
• Solución: envejecimiento ⇒ aumentar progresivamente las prioridades delos procesos que llevan más tiempo esperando por CPU.
Planificación mediante colas multinivel
Curso 2009/2010
• Consiste en separar los procesos según su naturaleza/tipo (por ejemplo,interactivos vs. por lotes).
• La cola de procesos preparados se divide en varias colas (niveles) conalgoritmos de planificación diferentes.
• Requiere un algoritmo de planificación entre colas:• ¿De qué cola se extraen procesos en primer lugar?• Típicamente con apropiación y prioridad fija.• Otra posibilidad: repartir el tiempo de CPU entre las colas (80% vs 20%).
Procesos del sistema
Procesos interactivos
Procesos por lotes
prioridad más alta
prioridad más baja
Planificación mediante Colas Multinivel Realimentadas
Curso 2009/2010
• Permite mover los procesos de una cola a otra.• Consiste en separar los procesos según las características de sus ráfagas
de CPU (si uso de CPU es excesivo ⇒ cola menos prioritaria).• Mecanismo de envejecimiento implícito para evitar el bloqueo indefinido.• Parámetros a definir:
• Número de colas.• Algoritmo de planificación de cada cola.• Mecanismo para determinar cuándo mover un proceso a una cola más
prioritaria.• Mecanismo para determinar cuándo mover un proceso a una cola menos
prioritaria.• Mecanismo para determinar en qué cola se colocará un proceso mientras
espera por la CPU.
• Es el algoritmo de planificación de CPU más flexible ⇒ más complejo.
Ejemplo de Planificación mediante Colas Multinivel Realimentadas
Curso 2009/2010
Quantum = 8
Quantum = 16
FCFS
cola 0
cola 1
cola 2
• Se ejecutan los procesos de cola 2 sólo si cola 0 y 1 están vacías.• Procesos de cola 0 desalojan a procesos de cola 1 y 2.• Prioridad a procesos cortos (ráfaga ≤ 8ms) y semicortos (ráfaga ≤ 24ms).• Los procesos largos (ráfaga > 24ms) usan ciclos de CPU no usados por los
cortos y semicortos.
Evaluación de los Algoritmos de Planificación
Curso 2009/2010
• Elección del criterio:• Conocer los tipos de trabajos a realizar.• Conocer los parámetros modificables.• Definir el objetivo del sistema.
• Evaluación formal:• Evaluación analítica:
• Prestaciones del algoritmo = f(carga, parámetros del sistema).• Difícil de realizar.
• Modelación determinista:• Resultados exactos para una configuración de trabajos dada.• Difícil de extrapolar.
• Modelos de colas:• Permite evaluar las longitudes de las colas.
• Evaluación por simulación.
