98
Sistemas Operativos I Tema 3 Procesos Equipo de Sistemas Operativos DISCA / DSIC UPV

Tema3 procesos

Embed Size (px)

DESCRIPTION

GAFITA HERMOSAAAAA...!! ESTUDIALO SIII....DISCULPA LA DEMORA...!!!

Citation preview

Page 1: Tema3 procesos

Sistemas Operativos I

Tema 3

Procesos

Equipo de Sistemas Operativos DISCA / DSIC

UPV

Page 2: Tema3 procesos

2Sistemas Operativos I (00-01) Tema 3: Procesos

Tema 3: Procesos? Introducción

Existen varias razones para permitir la ejecución concurrente de procesos:

?Compartir recursos físicos

?Compartir recursos lógicos

?Acelerar los cálculos

?Modularidad

?Comodidad

? Objetivos del tema:

?Profundizar en el concepto de proceso

?Dar a conocer la implementación del modelo de procesos

?Estudiar las diferentes políticas de planificación del procesador

Page 3: Tema3 procesos

3Sistemas Operativos I (00-01) Tema 3: Procesos

Tema 3: Procesos

? Índice

1.- Concepto de proceso.

2.- Implementación de procesos.

3.- Hilos de ejecución (threads).

4.- Conceptos de planificación.

5.- Criterios de planificación.

6.- Algoritmos de planificación.

7.- Evaluación de algoritmos.

8.- S.O. dirigido por eventos.

? Bibliografía

?A. Silberschatz, P. Galvin.

Sistemas Operativos. 5ª ed.

?Tema 4

?W. Stallings.

Sistemas Operativos 2ª ed.

?Tema 3.

Page 4: Tema3 procesos

4Sistemas Operativos I (00-01) Tema 3: Procesos

Tema 3: Procesos

? Índice

1.- Concepto de proceso.

2.- Implementación de procesos.

3.- Hilos de ejecución (threads).

4.- Conceptos de planificación.

5.- Criterios de planificación.

6.- Algoritmos de planificación.

7.- Evaluación de Algoritmos.

8.- S.O. dirigido por eventos.

Page 5: Tema3 procesos

5Sistemas Operativos I (00-01) Tema 3: Procesos

1.- Concepto de proceso? Concepto de proceso:

Existen diferentes visiones complementarias del concepto de proceso:

?Programa en ejecución.

?Unidad de asignación de recursos.

?Proceso como procesador virtual.

Page 6: Tema3 procesos

6Sistemas Operativos I (00-01) Tema 3: Procesos

1.- Concepto de proceso? Proceso como programa en ejecución:

?Programa: Lista de instrucciones. Ente pasivo.

?Proceso: Programa en ejecución. Ente activo. Pasa por una serie de estados

?Un programa reside normalmente en un fichero que se encuentra físicamente en el disco y es cargado en memoria cuando se crea el proceso para ejecutarlo.

?Puede haber dos o más procesos asociados a la ejecución de un mismo programa. Es habitual que un proceso genere más procesos durante su ejecución.

Page 7: Tema3 procesos

7Sistemas Operativos I (00-01) Tema 3: Procesos

1.- Concepto de proceso? Proceso como procesador virtual:

?Proceso: cada una de las actividades paralelas que se ejecutan en la máquina. Da la apariencia de que todas ellas se ejecutan sobre procesadores diferentes en paralelo.

?Ejemplos:

?Procesos de usuario: Un proceso de edición de un sistema de tiempo compartido. Un trabajo en un sistema por lotes. La compilación de un programa fuente en Pascal: el programa que ejecuta el proceso es el propio compilador.

?Procesos del sistema: “swapper” (que decide qué procesos hay que extraer de la memoria o introducir en ella cuando la cantidad dememoria libre no llega o supera ciertos límites), “pagedeamon” (es el encargado de utilizar reemplazo para liberar marcos y pasarlos a la reserva).

Page 8: Tema3 procesos

8Sistemas Operativos I (00-01) Tema 3: Procesos

1.- Concepto de proceso? Proceso como procesador virtual:

?El sistema operativo simula la existencia de N procesadores virtuales (procesos) a partir de una CPU o procesador físico.

?Cada procesador virtual ejecuta secuencialmente un único programa.

?Todos los procesos se ejecutan concurrentemente

Page 9: Tema3 procesos

9Sistemas Operativos I (00-01) Tema 3: Procesos

1.- Concepto de proceso

? Ejecución secuencial y ejecución concurrente.

?Ejecución secuencial: La ejecución de un proceso se dice que es secuencial porque sus operaciones son ejecutadas por la CPU una tras otra, en el orden que dicte el programa.

?Ejecución concurrente: La ejecución de dos procesos se dice que es concurrente porque estos se pueden ejecutar en paralelo.

?Concurrencia real: Si cada proceso se ejecuta sobre una CPU.

?Concurrencia virtual: La CPU reparte su tiempo entre los procesos para simular su ejecución paralela.

Page 10: Tema3 procesos

10Sistemas Operativos I (00-01) Tema 3: Procesos

1.- Concepto de proceso? Proceso como unidad de asignación de recursos:

?Para ejecutar un programa se necesita un entorno formado por una serie de recursos: memoria, descriptores de ficheros y otros atributos del proceso.

?Un proceso se puede considerar como la unidad de propiedad de todos esos recursos.

Memoria

Tiempode CPU

Tabla dedescriptores

ficheros

Otrosatributos

P1

Page 11: Tema3 procesos

11Sistemas Operativos I (00-01) Tema 3: Procesos

1.- Concepto de proceso? Estados de un proceso

Al ejecutar un proceso éste va cambiando de estado. El estado de un proceso se define como el comportamiento que presenta en un instante dado:

?Activo: El proceso se puede ejecutar. No hay impedimentos en asignarlealguna CPU.

?Ejecución: El proceso tiene asignada una CPU, las instrucciones se están ejecutando.

?Preparado: El proceso puede ser ejecutado pero está esperando que se le asigne una CPU libre. Puede haber varios procesos en este estado.

?Suspendido: No puede ser ejecutado porque el proceso se encuentra esperando un evento como:

? la finalización de una operación de E/S (una lectura de teclado)

? la comunicación con otro proceso, etc.

Page 12: Tema3 procesos

12Sistemas Operativos I (00-01) Tema 3: Procesos

1.- Concepto de proceso? Estados de un proceso:

NUEVO

PREPARADO

TERMINADO

EN EJECUCIÓN

SUSPENDIDO

Admitido

Esperar E/So evento

Terminación

Expulsión

Elegido Planificador

Fin E/So

llegada evento

ACTIVO

Proceso terminadopor otro proceso

Proceso terminadopor otro proceso

Page 13: Tema3 procesos

13Sistemas Operativos I (00-01) Tema 3: Procesos

1.- Concepto de proceso

? Operaciones sobre procesos (1)

?Creación: Supone asignar todos los recursos que el proceso necesita para su ejecución, como p.e. memoria.

?Ejemplo en UNIX: fork(). La utiliza el proceso init para crear un proceso que gestione cada terminal y el shell cada vez que recibe una nueva orden del usuario (si ésta es externa).

?Terminación: Supone liberar los recursos previamente asignados al proceso. Esta terminación puede ser:

?Terminación normal: El proceso invoca su propia terminación.

Ejemplo en UNIX: exit()

?Terminación anormal: El proceso termina por iniciativa del sistema operativo al detectar alguna condición de error (violación de límites, errores aritméticos) o por iniciativa de algún otro proceso.

Ejemplo en UNIX: kill() y señales.

Page 14: Tema3 procesos

14Sistemas Operativos I (00-01) Tema 3: Procesos

1.- Concepto de proceso? Operaciones sobre procesos (2):

?Suspensión: Supone pasar un proceso al estado suspendido para que espere un evento o E/S.

?Ejemplo en UNIX: read() sobre un tubo vacío.

?Activación: Pasar un proceso al estado activo cuando se produce el evento que esperaba.

?Ejemplo en UNIX: un proceso efectúa un write() sobre un tubo en el que había un lector esperando. El lector se reactiva.

Page 15: Tema3 procesos

15Sistemas Operativos I (00-01) Tema 3: Procesos

inicial

parado

En ejec.

(usuario)

En ejec.

(núcleo)

preparadosuspendido

zombie

Empieza

fork()

Acaba

fork()Cambios

decontexto

SIGSTOPSIGCONT

Espera evento

Ocurre evento

exit()

wait()

Interrupción o

llamada al sistemaFin de

interrup. o

llamada al sist.

ESTADOS

ACTIVOS

1.- Concepto de proceso? Estados de un proceso en UNIX

Page 16: Tema3 procesos

16Sistemas Operativos I (00-01) Tema 3: Procesos

Tema 3: Procesos

? Índice

1.- Concepto de proceso.

2.- Implementación de procesos.

3.- Hilos de ejecución (threads).

4.- Conceptos de planificación.

5.- Criterios de planificación.

6.- Algoritmos de planificación.

7.- Evaluación de Algoritmos.

8.- S.O. dirigido por eventos.

Page 17: Tema3 procesos

17Sistemas Operativos I (00-01) Tema 3: Procesos

2.- Implementación de procesosPara implementar procesos es conveniente pensar en un proceso como un procesador virtual que ejecuta un programa y que se implementa a partir de un procesador físico.

? La implementación de procesos requiere:

? Bloque de control de un proceso PCB (Process Control Block): es una estructura de datos para administrar el proceso. Almacena información de unproceso.

? Asignar los recursos necesarios para su ejecución, fundamentalmente la memoria para almacenar el código, los datos y la pila.

? Multiplexar la CPU entre los procesos: repartir el tiempo de la CPU entre los diferentes procesos para simular la ejecución paralela (concurrencia virtual).

? Bloque de control del sistema: es una estructura de datos que el sistema utiliza para controlar la ejecución de los procesos. Almacena información de todos los procesos.

Page 18: Tema3 procesos

18Sistemas Operativos I (00-01) Tema 3: Procesos

2.- Implementación de procesos?Bloque de Control de proceso (PCB):

Es una estructura de datos donde se almacenan los atributos de un proceso, es decir, la información asociada a un proceso. En un sistema de multiprogramación se requiere un gran cantidad de información de cada proceso para su administración.

Esta información puede agruparse en tres categorías:

? Identificación de Proceso: a cada proceso se le asigna un identificador numérico único (puede ser tan simple como un índice en la tabla de procesos).

? Información de estado del procesador (Contexto): Básicamente está formada por el contenido de los registros del procesador. Cuando se interrumpe un proceso, el contenido de los registros del procesador debe salvarse de forma que pueda restaurarse cuando el proceso reanude su ejecución

? Información de control del proceso: Información necesaria para que el sistema operativo controle y coordine los diferentes procesos.

Page 19: Tema3 procesos

19Sistemas Operativos I (00-01) Tema 3: Procesos

2.- Implementación de procesos? Identificación de Procesos. El PCB guarda:

? Identificador de este proceso.

? Identificador del proceso que creó a este proceso (proceso padre).

? Identificador del usuario.

? Información de estado del procesador

? Registros generales (visibles para el usuario).

? Contador de programa: contiene la dirección de la próxima instrucción a ejecutar.

? Códigos de condición: muestran el resultado de la operación aritmética o lógica más reciente (signo, cero, acarreo, desbordamiento).

? Información de estado: Indicadores de habilitación e inhabilitación de interrupciones.

? Puntero de Pila: Cada proceso tiene una o más pilas LIFO asociadas, para almacenar parámetros y direcciones de retorno de procedimientos y de las llamadas al sistema. El puntero de pila siempre apunta a la cima de la pila.

Page 20: Tema3 procesos

20Sistemas Operativos I (00-01) Tema 3: Procesos

2.- Implementación de procesos? Información de control de proceso.

Información necesaria para que el sistema operativo controle y coordine los diferentes procesos activos.

? Estado del proceso: preparado, en ejecución, suspendido, etc.

? Prioridad de un proceso

? Información de planificación: depende del algoritmo de planificación, por ejemplo la cantidad de tiempo que el proceso ha estado esperando y que se ejecutó la última vez.

? Suceso (evento): identidad del suceso que el proceso está esperando antes de poder reanudarse (solicitudes de E/S pendientes).

? Mapa de memoria: memoria de código, memoria de datos y memoria de pila.

Page 21: Tema3 procesos

21Sistemas Operativos I (00-01) Tema 3: Procesos

2.- Implementación de procesos? Implementación de varios procesos: Cambios de contexto

La ejecución aparentemente simultánea de varios procesos en un mismo sistema, requiere repartir el tiempo de CPU entre los procesos a ejecutar.

Ello implica desasignar la CPU al proceso en ejecución y asignarla a un proceso preparado. Esta actividad se conoce con el nombre de cambios de contexto.

Realizar un cambio de contexto lleva consigo:

? Salvar el contexto del proceso en ejecución en su PCB.

? Poner en la CPU el contexto del nuevo proceso (nuevo contador de programa).

? Actualizar la información de control de los procesos.

Page 22: Tema3 procesos

22Sistemas Operativos I (00-01) Tema 3: Procesos

2.- Implementación de procesos

CPU

PCSP

registros

1 procesadorfísico

P1 contexto

PCB #1

P2 contexto

PCB #2

Pn contexto

PCB #n

n procesadores virtuales

(3)

P1 --> P2

P2 --> P1PCSP

registros

contexto

(1)

contexto

PCSP

registros

(2)

PCSP

registros

(4)

? Cambio de contexto

Page 23: Tema3 procesos

23Sistemas Operativos I (00-01) Tema 3: Procesos

2.- Implementación de procesos? Cambio de contexto.

Los cambios de contexto no son trabajo útil e implican una sobrecarga importante si se hacen con frecuencia: reducen la utilización.

? Utilización de CPU

P1 P2 P3 P1

t

Cambios de contexto

Utilización de CPU =T(P1) + T(P2) +T(P3) + 3t

T(P1) + T(P2) +T(P3)

Page 24: Tema3 procesos

24Sistemas Operativos I (00-01) Tema 3: Procesos

2.- Implementación de procesos? Motivos que provocan cambios de contexto:

?Terminación normal del proceso, el proceso en ejecución se acaba.

?El proceso en ejecución es suspendido en espera de una E/S o de un evento.

?El proceso en ejecución es expulsado bien porque ha agotado la cantidad de tiempo de CPU asignada bien porque se decide asignarla a otro proceso más prioritario.

? El sistema se puede representar como un diagrama de colas donde

? Los círculos representan recursos

? Los rectángulos representan colas de procesos que esperan acceder a los recursos.

Page 25: Tema3 procesos

25Sistemas Operativos I (00-01) Tema 3: Procesos

2.- Implementación de procesos? Implementación de varios procesos: Estructuras de control del sistema

Procesoterminado

Cola de procesospreparados CPU

Cola de procesosesperando sucesoSuceso

Cola de procesosesperando E/SE/S

Cola de procesosesperando ejecución

Proceso nuevo

Expulsión

Recursos

Colas

? Los PCBs se almacenanen colas, cada una delas cuales representa unestado particular de losprocesos.

? Los PCBs se almacenanen colas, cada una delas cuales representa unestado particular de losprocesos.

? Para implementar procesos es conveniente pensar en un sistema como una colección de recursos y colas que representan los procesos que esperan para utilizar el recurso.

? Para implementar procesos es conveniente pensar en un sistema como una colección de recursos y colas que representan los procesos que esperan para utilizar el recurso.

Page 26: Tema3 procesos

26Sistemas Operativos I (00-01) Tema 3: Procesos

2.- Implementación de procesos? Implementación de varios procesos: Estructuras de control del sistema

? Los datos que el sistema utiliza para controlar la ejecución de los procesos, se pueden considerar reunidos en una estructura que se suele conocer con el nombre de Bloque de Control del Sistema (SCB).

? El SCB contiene en la gran mayoría de casos la siguiente información:

?Tabla de procesos?Un puntero a la cola de PCBs de los procesos nuevos, que no están

activos y están esperando ejecución.?Un puntero al PCB del proceso que está haciendo uso de la CPU?Un puntero a la cola de PCBs de los procesos preparados?Un puntero a la cola de PCBs de los procesos que están esperando a

que se produzca algún evento, para poder volver a ejecutarse, nopudiendo hacerlo hasta que tenga lugar el evento esperado.?Los identificadores de las rutinas necesarias para tratar las

interrupciones producidas por el hardware, software o errores indeseados.?Estructuras de datos relacionadas con la comunicación y sincronización

de procesos?Otras tablas y datos relacionados con la gestión de memoria y ficheros.

Page 27: Tema3 procesos

27Sistemas Operativos I (00-01) Tema 3: Procesos

2.- Implementación de procesos

Proceso en ejecución

Cola de procesos preparados

Cola de procesos nuevos

Cola de procesos esperando evento i

Vectores de interrupción

ESTRUCTURAS DE

CONTROL DEL SISTEMA Identificador

Contexto

Estado: EJEC

Evento: --

Mapa de memoria

P. Siguiente -

...

PCB n

Estado: PREP

Evento: --

P. siguiente

...

Estado: SUSP

Evento: i

P. siguiente

...

?

PCB 3

PCB 6 PCB 1

PCB 4 PCB 2

Tabla de procesos

Page 28: Tema3 procesos

28Sistemas Operativos I (00-01) Tema 3: Procesos

Tema 3: Procesos

? Índice

1.- Concepto de proceso.

2.- Implementación de procesos.

3.- Hilos de ejecución (threads).

4.- Conceptos de planificación.

5.- Criterios de planificación.

6.- Algoritmos de planificación.

7.- Evaluación de Algoritmos.

8.- S.O. dirigido por eventos.

Page 29: Tema3 procesos

29Sistemas Operativos I (00-01) Tema 3: Procesos

3.- Hilos de ejecución (Threads) ?Concepto de hilo de ejecución (thread).

Hay sistemas operativos donde un proceso puede tener internamente actividades concurrentes llamadas hilos de ejecución.

Ejemplo:

? Un proceso UNIX “videojuego” puede tener un hilo de ejecución para cada uno de los elementos móviles de la pantalla.

Page 30: Tema3 procesos

30Sistemas Operativos I (00-01) Tema 3: Procesos

3.- Hilos de ejecución (Threads) ?Concepto de hilo de ejecución (thread).

El concepto de proceso que se ha presentado incluye las dos características siguientes:

?Unidad de propiedad de recursos: A cada proceso se le asigna un espacio de direcciones virtuales para albergar a la imagen del proceso y, de cuando en cuando también se le puede asignar otros recursos (canales de E/S, dispositivos de E/S y ficheros).

?Unidad de ejecución: Un proceso es un camino de ejecución a través de un programa. Esta ejecución puede ser intercalada con la de otros procesos.

Estas dos características son la esencia del proceso, pero pueden ser tratadas de manera independiente por el s.o.

Page 31: Tema3 procesos

31Sistemas Operativos I (00-01) Tema 3: Procesos

3.- Hilos de ejecución (Threads)? Se puede diferenciar entre:

?Proceso (proceso pesado): Unidad de propiedad de los recursos (memoria, descriptores de ficheros, etc). Tiene muchos atributos y es lento de crear.

?Hilo de ejecución (proceso ligero): Actividad concurrente dentro de un proceso (pesado). Todos los hilos de ejecución que pertenecen a un mismo proceso comparten sus recursos (memoria, descriptores de fichero, etc). Tiene pocos atributos y se crea rápidamente.

P1 P2

Hilos de ejecución

Page 32: Tema3 procesos

32Sistemas Operativos I (00-01) Tema 3: Procesos

3.- Hilos de ejecución (Threads)? Compartir memoria

? Los procesos UNIX no comparten memoria (código o datos). Cada uno tiene su propio espacio de direcciones.

? Los hilos de ejecución de un mismo proceso pueden tener rutinas o variables comunes.

? No obstante, cada hilo tendrá su propia pila donde se guardarán las variables locales y argumentos de invocación.

Page 33: Tema3 procesos

33Sistemas Operativos I (00-01) Tema 3: Procesos

3.- Hilos de ejecución (Threads)Los hilos de ejecución pueden implementarse de tres formas:

? Hilos a nivel de usuario (user-level threads): los hilos se crean a nivel del proceso de usuario vía un conjunto de procedimientos de biblioteca o vía el soporte de ejecución del lenguaje de programación.

? El sistema operativo sólo crea un hilo de ejecución en el núcleo por cada espacio de direcciones (proceso).

? El resto de los hilos son implementados por el run-time del lenguaje.

? Es la aproximación utilizada en sistemas operativos que no soportan hilos.

? Los cambios de contexto entre los hilos a nivel de usuario son rápidos, ya que no involucran llamadas al sistema.

? La política de planificación de estos hilos no está restringida a la propia del sistema operativo.

? Cuando este tipo de hilos invocan llamadas al sistema bloqueantes, normalmente se bloquea todo el proceso.

? No pueden explotar un sistema multiprocesador, ya que el sistema operativo ve un único proceso.

Page 34: Tema3 procesos

34Sistemas Operativos I (00-01) Tema 3: Procesos

3.- Hilos de ejecución (Threads)

Núcleo del SO

Un programa,muchos hilos

Soporte en ejecución del

lenguaje

Un programa,muchos hilos

Soporte en ejecución del

lenguaje

Hilos a nivel de usuario

= Espacio de direcciones = construcción lingüística o hilo a nivel usuario

= proceso o hilo del SO

•Implementación de hilos

Page 35: Tema3 procesos

35Sistemas Operativos I (00-01) Tema 3: Procesos

3.- Hilos de ejecución (Threads)? Implementación de hilos de

ejecución

? Hilos a nivel del núcleo (kernel-level threads):

? El sistema operativo soporta hilos de ejecución y proporciona un conjunto de llamadas al sistema para su manipulación.

? El sistema crea un hilo de ejecución por cada hilo a nivel de usuario.

? Son la unidad de planificación del sistema.

? El bloqueo y activación de hilos corre a cargo del núcleo.

? Los cambios de contexto son manejados por el kernel y son unas 10 veces más lentos que en el caso de los hilos de usuario.

Núcleo del SO

Un programa,muchos hilos

Soporte en ejecución del

lenguaje

Un programa,muchos hilos

Soporte en ejecución del

lenguaje

Hilos a nivel de núcleo

= Espacio de direcciones

= construcción lingüística o hilo a nivel usuario

= proceso o hilo del SO

Page 36: Tema3 procesos

36Sistemas Operativos I (00-01) Tema 3: Procesos

3.- Hilos de ejecución (Threads)? Implementación de hilos

de ejecución

? Aproximación híbrida:

? Se implementan las dos clases de hilos anteriores.

? El sistema operativo permite más de un hilo por proceso.

? El soporte del lenguaje de programación utiliza un hilo del núcleo para implementar un grupo de hilos de usuario.

? Proporciona flexibilidad y el máximo rendimiento potencial al programador de aplicaciones.

Núcleo del SO

Soporte en ejecución del lenguaje

Un programa, muchos hilos

u1 u2

k1

= Espacio de direcciones

= construcción lingüística o hilo a nivel usuario

= proceso o hilo del SO

Page 37: Tema3 procesos

37Sistemas Operativos I (00-01) Tema 3: Procesos

3.- Hilos de ejecución (threads)? Utilización de hilos de ejecución

Los hilos de ejecución pueden ser creados y manejados:

?Utilizando un lenguaje de programación convencional y llamadas al sistema.

?Ejemplo: C y threads en POSIX

?Utilizando construcciones lingüísticas (o clases) de un lenguaje de programación que admita concurrencia

?Ejemplo: Tareas en Ada95, threads en Java

Page 38: Tema3 procesos

38Sistemas Operativos I (00-01) Tema 3: Procesos

Llamada Descripción

pthread_create(thread_id, attr, func, args) Crea un nuevo hilo de ejecución. El hilo deejecución empieza en func y se le pasan losparámetros args.

pthread_exit (status) El hilo que la invoca finaliza su ejecución.

pthread_join (thread_id) Suspende la ejecución del hilo que invocaesta llamada, hasta que el thread_id acabe.

pthread_t pthread_self() Devuelve el identificador del thread que lainvoca.

3.- Hilos de ejecución (threads)? Threads en POSIX: llamadas básicas

Page 39: Tema3 procesos

39Sistemas Operativos I (00-01) Tema 3: Procesos

3.- Hilos de ejecución (threads)

#include <stddef.h>#include <pthread.h>

void * process(void * arg){printf("%s ", (char *) arg);fflush(stdout);pthread_exit(0);

}

int main(){pthread_t th_a, th_b;

pthread_create(&th_a, NULL, process, "Hello");pthread_create(&th_b, NULL, process, "World");sleep(1);

}

#include <stddef.h>#include <pthread.h>

void * process(void * arg){printf("%s ", (char *) arg);fflush(stdout);pthread_exit(0);

}

int main(){pthread_t th_a, th_b;

pthread_create(&th_a, NULL, process, "Hello");pthread_create(&th_b, NULL, process, "World");sleep(1);

}

? Threads en POSIX: un ejemplo

Page 40: Tema3 procesos

40Sistemas Operativos I (00-01) Tema 3: Procesos

? Ada permite la programación de actividades concurrentes.

? La facilidad Ada que permite programar estas actividades es el tipo de datos task.

? El tipo tarea debe ser especificado en primer lugar y posteriormente implementado.

? Las tareas Ada comparten memoria y se comunican y sincronizan mediante citas y/o objetos protegidos.

? Pueden declararse objetos tarea directamente omitiendo type. En este caso no pueden definirse variables.

? Cada tarea dispone de una copia de las variables locales declaradas.

task type Niño;

task body NiñoisSueño: Boolean;Edad: Natural;

beginloop

Dormir;loopComer;Jugar_O_Incordiar;exit when Sueño

end loop;exit when Edad > ...

end loop;end Niño;

Victor,Santiago,Gabriela: Niño;

task type Niño;

task body NiñoisSueño: Boolean;Edad: Natural;

beginloop

Dormir;loopComer;Jugar_O_Incordiar;exit when Sueño

end loop;exit when Edad > ...

end loop;end Niño;

Victor,Santiago,Gabriela: Niño;

3.- Threads en Ada: Declaración

Page 41: Tema3 procesos

41Sistemas Operativos I (00-01) Tema 3: Procesos

? Cuando un programa Adacomienza, se crea la tarea principal, la cual ejecuta el subprogramaprincipal.

? Cuando se declara una variable del tipo task, el soporte en tiempo de ejecución del lenguaje Ada crea un hilo de ejecución (proceso ligero) dentro del proceso que está ejecutando el programa.

? Una tarea comienza su ejecución cuando comienza la ejecución de la unidad (maestra) donde se declara.

? La unidad de ejecución maestra sólo finaliza cuando finalizan todas las tareas que dependen de ella.

procedure Guarderia is

task type Niño;

task body Niñois

------end Niño;

Victor,Santiago,Gabriela: Niño;

begin

-- unidad maestra;

end Guarderia;

procedure Guarderia is

task type Niño;

task body Niñois

------end Niño;

Victor,Santiago,Gabriela: Niño;

begin

-- unidad maestra;

end Guarderia;

Inician Guarderia y los tres niños

Inician Guarderia y los tres niños

Guarderiaespera la terminación de los tres niños

Guarderiaespera la terminación de los tres niños

3.Threads en Ada: activación y finalización

Page 42: Tema3 procesos

42Sistemas Operativos I (00-01) Tema 3: Procesos

Tema 3: Procesos

? Índice

1.- Concepto de proceso.

2.- Implementación de procesos.

3.- Hilos de ejecución (threads).

4.- Conceptos de planificación.

5.- Criterios de planificación.

6.- Algoritmos de planificación.

7.- Evaluación de Algoritmos.

8.- S.O. dirigido por eventos.

Page 43: Tema3 procesos

43Sistemas Operativos I (00-01) Tema 3: Procesos

4.- Concepto de planificación? Recursos reutilizables en serie

?Escasez de recursos: el número de recursos es inferior al número de procesos que compiten por ellos.

?Recursos reutilizables en serie: aquellos que sólo pueden estar asignados a un proceso en un instante de tiempo dado. Ejemplos: Impresoras, CPU.

?Planificación de recursos: Con recursos reutilizables en serie el s.o. tiene que aplicar una política para asignar recursos a los procesos.

Page 44: Tema3 procesos

44Sistemas Operativos I (00-01) Tema 3: Procesos

4.- Concepto de planificación

Salvar contexto en PCB #1

Cargar contexto desde PCB #3

P1

P2

Sistema operativo

1

2

3

Ejecución

Ejecución

Interrup. ollamada alsistema

Interrup. ollamada al sist

P3

Ejecución

Salvar contexto en PCB #2

Cargar contexto desde PCB #2

-- Tratamiento

-- Tratamiento

PLANIFICADOR:escoger nuevo proceso

PLANIFICADOR:escoger nuevo proceso

4

Page 45: Tema3 procesos

45Sistemas Operativos I (00-01) Tema 3: Procesos

4.- Concepto de planificación? Planificador

Elemento del sistema operativo que determina a qué proceso se le asigna un determinado recurso (p. e. CPU) en cada instante de tiempo, de acuerdo con alguna política.

En el caso de que el recurso a asignar sea la CPU se distinguen entre tres planificadores:

?Planificador a largo plazo.

?Planificador a medio plazo

?Planificador a corto plazo.

Page 46: Tema3 procesos

46Sistemas Operativos I (00-01) Tema 3: Procesos

Diagrama de colas del sistema

Procesoterminado

Cola de procesospreparados CPU

Cola de procesosesperando sucesoSuceso

Cola de procesosesperando E/SE/S

Planificador a largo plazo

Planificador a corto plazoCola de procesos

esperando ejecución

Proceso nuevo

Expulsión

Recursos

Colas…

Cola de procesosintercambiados

a discoPlanificador a medio plazo Planificador a

medio plazo

Page 47: Tema3 procesos

47Sistemas Operativos I (00-01) Tema 3: Procesos

4.- Concepto de planificación? Planificador a largo plazo

?En un sistema de procesos por lotes, los procesos recién incorporados permanecen detenidos en una cola de procesamiento por lotes, en el disco. El planificador a largo plazo creará procesos a partir de la cola cuando sea posible.

?Dos son las decisiones que toma el planificador a largo plazo:

?Cuando crear un nuevo proceso: controla el grado de multiprogramación.

?Cuál va a ser el siguiente proceso a admitir: algoritmo FCFS (firts_come, first-served), tener en cuenta prioridades, tiempos de ejecución esperados, exigencias E/S.

?Controla el grado de multiprogramación: conjunto de procesos que residen simultáneamente en memoria y se ejecutan concurrentemente.

?Selecciona procesos de la cola de procesos que están esperando ser ejecutados y los carga en memoria.

?Se ejecuta con poca frecuencia, ya que pueden transcurrir minutos entre la creación de nuevos procesos en el sistema.

Page 48: Tema3 procesos

48Sistemas Operativos I (00-01) Tema 3: Procesos

4.- Concepto de planificación

? Planificador a medio plazo

?Cuando un usuario se conecta al sistema, se genera una solicitud de crear un proceso, los usuarios de tiempo compartido no pueden ser puestos en una cola y esperar a que el sistema pueda aceptarlos.

?En ocasiones es interesante sacar procesos de memoria para reducir el grado de multiprogramación o para mejorar la mezcla de procesos (orientados a CPU o E/S).

?Se encarga de controlar qué procesos, de entre todos los iniciados deben estar en memoria y qué otros deben estar en el espacio de intercambio.

?El planificador a medio plazo se encarga de sacar el proceso y volverlo a introducir más tarde. El proceso continuará su ejecución a partir del punto donde se había quedado.

?A este esquema comúnmente se le denomina “swapping”.

Page 49: Tema3 procesos

49Sistemas Operativos I (00-01) Tema 3: Procesos

4.- Concepto de planificación

? Planificador a corto plazo

?Selecciona un proceso de la cola de procesos preparados para ejecución y le asigna la CPU.

?Se ejecuta con mucha frecuencia. El proceso seleccionado quizás se ejecute únicamente durante unos milisegundos antes de iniciar una solicitud de E/S.

?Se ejecuta cuando ocurre un evento que conduce a la interrupción del proceso actual, expulsando el proceso a favor de otro. Ejemplos de eventos:

?Interrupciones de reloj.

?Interrupciones de E/S.

?Llamadas al sistema operativo.

?Señales.

Page 50: Tema3 procesos

50Sistemas Operativos I (00-01) Tema 3: Procesos

4.- Concepto de planificación? Procesos orientados a CPU u orientados a E/S

?Un proceso orientado a CPU es aquel que invierte la mayor parte de su tiempo en efectuar cálculos y genera solicitudes de E/S con pocafrecuencia.

?Un proceso orientado a E/S es aquel que emplea más tiempo en realizar E/S que en efectuar cálculos.

El planificador a largo plazo debe seleccionar una mezcla adecuada de procesos orientados a CPU y orientados a E/S.

Proceso orientado a CPU

CPU E/S CPU E/S CPU

CPU E/S CPU E/S CPU

Proceso orientado a E/S

Page 51: Tema3 procesos

51Sistemas Operativos I (00-01) Tema 3: Procesos

Tema 3: Procesos

? Índice

1.- Concepto de proceso.

2.- Implementación de procesos.

3.- Hilos de ejecución (threads).

4.- Conceptos de planificación.

5.- Criterios de planificación.

6.- Algoritmos de planificación.

7.- Evaluación de Algoritmos.

8.- S.O. dirigido por eventos.

Page 52: Tema3 procesos

52Sistemas Operativos I (00-01) Tema 3: Procesos

5.- Criterios de planificación? Criterios de planificación

Algunos de los criterios y características que un planificador debe conseguir son:

? Utilización: Los recursos se han de mantener tan ocupados como sea posible.

?Tiempo_recurso_ocupado / Tiempo_total

? Rendimiento: Maximizar el número de tareas procesadas por unidad de tiempo.

?Número_de_trabajos_terminados / Tiempo_total

? Tiempo de retorno: Tiempo que tarda en ejecutarse un proceso.

?Tiempo de salida - Tiempo de entrada = ? TCPU + ? TE/S + ? TColas

Page 53: Tema3 procesos

53Sistemas Operativos I (00-01) Tema 3: Procesos

5.- Criterios de planificación? Criterios de planificación (2):

?Tiempo de espera:

?Tiempo que un proceso está en la cola de procesos preparados.

?Tiempo de respuesta:

?Tiempo que transcurre desde que se presenta una solicitud hasta que el sistema comienza a contestar (en procesos interactivos).

?Equidad:

?Garantizar que cada proceso obtiene la proporción justa de CPU. Es decir, que los procesos sean tratados de manera igualitaria. Lo opuesto a equidad sería inanición.

Page 54: Tema3 procesos

54Sistemas Operativos I (00-01) Tema 3: Procesos

5.- Criterios de planificación? Optimización de los criterios de planificación.

No se pueden optimizar todos los criterios a la vez porque algunos de ellos son contrapuestos. Cada tipo de sistema tiene sus prioridades:

?Sistema por lotes: Maximizar utilización y rendimiento y minimizar el tiempo de retorno y de espera.

?Sistemas interactivos: Proporcionar equidad y hacer el tiempo de respuesta razonable y predecible.

? La multiprogramación en sí misma supone una mejora de muchos de los criterios anteriores respecto a la ejecución secuencial.

? Los algoritmos de planificación también tienen como objetivo mejorar algunos de los criterios mencionados.

Page 55: Tema3 procesos

55Sistemas Operativos I (00-01) Tema 3: Procesos

5.- Criterios de planificación

?Ejemplo: SIN MULTIPROGRAMACIÓN

E/SCPU E/SCPU CPU E/SCPU E/SCPU CPU

Proceso P0 Proceso P1

Utilización CPU = 6/10 = 60Productividad = 2 trabajos/10 = 0.2Tiempo de retorno = (5+10)/2 = 7.5

Utilización CPU = 6/10 = 60Productividad = 2 trabajos/10 = 0.2Tiempo de retorno = (5+10)/2 = 7.5

Utilización CPU = 100%Productividad = 2 trabajos /6 = 0.33Tiempo de retorno = (5 + 6)/2 = 5.5Este representa un caso extremo. En el caso de TCPU << T E/S la utilización de la CPU sería < 100%

Utilización CPU = 100%Productividad = 2 trabajos /6 = 0.33Tiempo de retorno = (5 + 6)/2 = 5.5Este representa un caso extremo. En el caso de TCPU << T E/S la utilización de la CPU sería < 100%

CON MULTIPROGRAMACIÓN

Proceso P0

E/SCPU E/SCPU CPU

E/S E/SCPU CPU CPU

Proceso P1

Se intercalan ráfagas de CPU con ráfagas de E/S

Page 56: Tema3 procesos

56Sistemas Operativos I (00-01) Tema 3: Procesos

5.- Criterios de planificación?Histograma de intervalos de tiempo de CPU

?Gran número de ráfagas de CPU de corta duración

?Pequeño número de ráfagas de CPU de larga duración.

duración de ràfaga (pulsos de reloj)

frecuencia

20

40

60

80

100

120

140

160

8 16 24 32

Page 57: Tema3 procesos

57Sistemas Operativos I (00-01) Tema 3: Procesos

5.- Criterios de planificación? Para mejorar la utilización de la CPU se podría:

? Aumentar el grado de multiprogramación (mientras la memoria lo permita).

? Adoptar un algoritmo de planificación adecuado que optimice el orden de ejecución de los procesos.

? Para conseguir un algoritmo de planificación óptimo se podría:

? Determinar qué parámetros se quiere optimizar.

? Conocer el tipo de comportamiento de los procesos.

Page 58: Tema3 procesos

58Sistemas Operativos I (00-01) Tema 3: Procesos

Tema 3: Procesos

? Índice

1.- Concepto de proceso.

2.- Implementación de procesos.

3.- Hilos de ejecución (threads).

4.- Conceptos de planificación.

5.- Criterios de planificación.

6.- Algoritmos de planificación.

7.- Evaluación de Algoritmos.

8.- S.O. dirigido por eventos.

Page 59: Tema3 procesos

59Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación?Objetivo

Decidir a cuál de los procesos que están en la cola de procesos listos se le asignará la CPU.

?Clasificación de algoritmos de planificación:

?Por orden de llegada (FCFS).

?Circular (RR, round-robin)

?Por prioridades

?Sin expulsión (“Non preemptive”) / Con expulsión (“Preemptive”)

?Estáticos / Dinámicos

?Combinación de algoritmos: Clases de prioridades.

Page 60: Tema3 procesos

60Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Servicio por orden de llegada (FCFS : “first-come, first-served”)

La CPU es asignada a todos los procesos en el mismo orden que lo solicitan.

Proceso T. llegada T. CPUP1 0 24P2 0 3P3 0 3

0 24 27 30

P1 P2 P3

Caso 1) Orden de llegadaP1, P2, P3

T. de espera medio:(0 + 24 + 27) / 3 = 17

0 3 6 30

P1P2 P3

Caso 2) Orden de llegadaP2, P3, P1

T. de espera medio:(6 + 0 + 3) / 3 = 3

Page 61: Tema3 procesos

61Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Servicio por orden de llegada (FCFS : “first-come, first-served”)

? Propiedades

? Sin expulsión: Cuando un proceso tiene asignada la CPU, la conserva hasta que desee liberarla, bien sea porque finaliza o por solicitud de una E/S.

? Ventajas

? Fácil de implementar

? Inconvenientes

? No optimiza el tiempo de espera: es muy variable en función del orden de llegada de los procesos y la duración de los intervalos de CPU.

? Efecto convoy: Los trabajos largos retrasan a los cortos (por ejemplo: piense en un sistema con un único trabajo con largas ráfagas de CPU y muchos trabajos con ráfagas cortas de CPU).

? No es adecuado para sistemas interactivos: Por ser sin expulsión un trabajo con una ráfaga de CPU larga puede provocar una espera larga a otros usuarios.

Page 62: Tema3 procesos

62Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación?Prioridad al trabajo más breve ( SJF: shortest job first )

?Se asocia a cada trabajo (proceso) el tiempo del siguiente intervalo de CPU.

?Se asigna la CPU al trabajo con menor tiempo asociado.

?Sin expulsión: cuando un proceso tiene asignada la CPU, la conserva hasta que desee liberarla.

Page 63: Tema3 procesos

63Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Ejemplo: Prioridad al trabajo más breve (SJF).

Procesos Instante de llegada DuraciónP1 0 7P2 2 4P3 4 1P4 5 4

SJF (sin expulsión)

•Media del tiempo de espera: (0 + 6 + 3 + 7) / 4 = 4

0 7 8 12

P1 P2P3 P4

16

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

Page 64: Tema3 procesos

64Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Variante con expulsión del SJF ( SRTF: Shortest Remaining Time First )

Prioridad al que le resta menos tiempo (para finalizar).

? La CPU es asignada al proceso que le queda menos tiempo para acabar la ráfaga de CPU en curso.

?Variante con expulsión de SJF: Si llega un proceso con un intervalo de CPU inferior al tiempo que le falta al proceso en ejecución paraabandonar la CPU, entonces el nuevo proceso se hace con la CPU.

Page 65: Tema3 procesos

65Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Ejemplo del SRTF. Procesos T. Llegada Duración

P1 0 7P2 2 4P3 4 1P4 5 4

0 7 11

P1 P2 P3 P4

16

P1P2

2 4 5

Diagrama de Gantt

Media del tiempo de espera: (9 + 1 + 0 + 2 ) / 4 = 3

Cronograma por procesos

P1

P2

P3

P4

Page 66: Tema3 procesos

66Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? SRTF: Shortest Remaining Time First

? Ventajas

?SRTF optimiza la media de tiempo de espera.

? Inconvenientes

?El tiempo del siguiente intervalo de CPU es difícil de predecir. Esto lo hace difícil de implementar para un planificador a corto plazo.(En los sistemas por lotes el usuario puede aportar información).

?Posibilidad de inanición: los trabajos largos no se ejecutarán mientras haya trabajos cortos.

Page 67: Tema3 procesos

67Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación SJF/SRTF

Aunque no se conoce la longitud de la siguiente ráfaga se puede predecir su valor esperando que sea de longitud similar a las anteriores.

? Estimación del siguiente intervalo de CPU

Se utiliza la media exponencial:

T n+1 = ? tn + (1 - ? ) Tn

? tn: tamaño real del n-ésimo intervalo de CPU

? Tn: Tamaño estimado del n-ésimo intervalo de CPU.

? ? : coeficiente exponencial 0 ??? ?? ?

? Caso ? ?= 1, los datos históricos son irrelevantes y sólo tiene importancia la ráfaga más reciente de CPU. T n+1 = tn

? Caso ? = 0, la historia reciente no tienen efecto, se supone que las condiciones actuales son transitorias. T n+1 = Tn

? Es habitual que ? = 1/2, por lo que la historia reciente y antigua se ponderan de igual manera.

Page 68: Tema3 procesos

68Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación SJF/SRTF

? Estimación del siguiente intervalo de CPU

Desarrollando la fórmula y sustituyendo T n+1 por tn llegamos a:

T n+1 = ? tn + (1 - ? ) ? tn-1 + … + (1 - ? )j ? tn-j + … + (1 - ? )n+1 T0

Puesto que tanto (1 - ? ) como ? son menores o iguales que 1 cada término sucesivo tiene menos peso que el anterior.

Ejemplo de promedio exponencial para ? = 1/2, y T0= 10

Ráfaga de CPU: 6 4 6 4 13 13 13Predicción: 10 8 6 6 5 9 11

2

4

6

8

10

12

long

itud

de r

áfag

a

tiempo

Page 69: Tema3 procesos

69Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación por prioridades

?Se asocia a cada proceso un número (entero), llamado prioridad de acuerdo con algún criterio.

?Se asigna la CPU al trabajo con mayor prioridad (normalmente, mayor número).

?Ejemplo:

?SJF es un caso particular de prioridades en el que la prioridad es 1/T.

Page 70: Tema3 procesos

70Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Ejemplo:

? Planificación prioridades

0 7 11

P1 P2 P3 P4

16

P1P2

2 4 5

Diagrama de Gantt

Cronograma por procesos

P1

P2

P3

P4

Procesos T. Llegada Duración Prioridad

P1 0 7 5

P2 2 4 10

P3 4 1 15

P4 5 4 10

Page 71: Tema3 procesos

71Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación por Prioridades: Variantes

? Algoritmos con expulsión/sin expulsión.

? Prioridades estáticas/dinámicas.

?Prioridades estáticas: La prioridad se asigna antes de la ejecución y no cambia.

?Prioridades dinámicas: La prioridad cambia con el tiempo.

Page 72: Tema3 procesos

72Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación por prioridades

? Problema de inanición

Un algoritmo de prioridades es inherentemente poco equitativo. El problema extremo es:

? Inanición: Los procesos con baja prioridad no se ejecutan nunca.

? Solución:

? Actualización de prioridades: Esquema de prioridades dinámicas, donde la prioridad de un proceso aumenta con el tiempo de espera.

Page 73: Tema3 procesos

73Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación circular ( RR: Round Robin )

?A cada proceso se le asigna una pequeña cantidad de tiempo de CPU, llamada “quantum” de tiempo, normalmente 10-100mseg.

Si el proceso tiene un intervalo de CPU mayor que el “quantum”, entonces es expulsado de la CPU y añadido a la cola de procesos listos.

?Si hay n procesos, cada uno obtiene 1/n del tiempo de la CPU en intervalos de q unidades, como máximo.

Page 74: Tema3 procesos

74Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Ejemplo:

? Planificación circular

0 15 19

P1 P2

304 7 11

Diagrama de Gantt

P3 P1 P3 P1 P3 P1

23 26

Cronograma por procesos

P1

P2

P3

Procesos T. Llegada DuraciónP1 0 16P2 0 3P3 0 11Quantum q=4

Page 75: Tema3 procesos

75Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación circular

? Valor del “quantum” de tiempo

?Para q grandes: el algoritmo degenera en un algoritmo FCFS.

?Para q pequeños: q ha de ser grande respecto al tiempo necesario para el cambio de contexto, sino la sobrecarga introducida es muy alta.

Regla práctica: El 80% de los intervalos de CPU han de ser inferiores al “quantum” de tiempo.

Page 76: Tema3 procesos

76Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación circular

? Propiedades:

?Equitativo.

?El tiempo de espera máximo está limitado por (n -1)q, antes de recibir su siguiente cuanto de tiempo.

?El tiempo de retorno medio varía con el cuanto de tiempo.

En general es peor que el del algoritmo SRTF. Mejora si un porcentaje alto de trabajos acaban antes de que acabe el cuanto de tiempo.

Page 77: Tema3 procesos

77Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación con múltiples colas

Los procesos se pueden clasificar fácilmente en distintos grupos (interactivos, por lotes, etc.). La cola de procesos preparados consiste en realidad en diversas colas

?Cada cola ha de tener su propio algoritmo de planificación.

?Ha de haber un algoritmo de planificación entre colas.

Page 78: Tema3 procesos

78Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Ejemplo de algoritmo de

planificación entre colas:

? Prioridades estáticas: Los procesos en cola con menor prioridad no se ejecutan mientras haya procesos en cola con mayor prioridad. Posibilidad de inanición.

? Cuotas de tiempo: Cada cola está asignada a un porcentaje del tiempo de CPU. Ejemplo: el 80% a trabajos interactivos y el 20% a trabajos por lotes. Colas de procesos preparados

FCFS (prio. 10)

PRIO (prio. 8)

RR (prio. 6)

SJF (prio. 4)

ProcesosSistema

Usuariosprivilegiados

ProcesosInteractivos

ProcesosPor Lotes

Page 79: Tema3 procesos

79Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación con múltiples colas realimentadas.

?Existen diferentes colas de procesos preparados.

?Cada cola posee:

?Política de planificación.

?Una prioridad asignada.

?Un proceso puede cambiar de cola de acuerdo con un esquema de actualización de prioridades:

?Los procesos con un tiempo de espera acumulado elevado son promocionados a una cola con prioridad superior.

?Los procesos con un tiempo de utilización de la CPU elevado son degradados a una cola con prioridad inferior.

Page 80: Tema3 procesos

80Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación

? Planificación con múltiples colas realimentadas.

? Ejemplo

Colas de procesos preparados

RR [q=8] (prio. 10)

RR [q=16] (prio. 8)

FCFS (prio. 6)

Page 81: Tema3 procesos

81Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Múltiples colas realimentadas

? Parámetros de las colas realimentadas:

?Número de colas.

?Prioridad de cada cola.

?Método de promoción de un proceso.

?Método de degradación de un proceso.

?Método para determinar la cola de entrada de un proceso.

Page 82: Tema3 procesos

82Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificaciónPlanificación en UNIX SVR2

? Algoritmo de colas multinivel realimentadas.

? La prioridad es mayor cuanto menor sea el número asignado.

? Los procesos que se ejecutan a nivel de usuario tienen prioridades por encima del valor base (base = 60 en UNIX SVR2).

? Los procesos que se ejecutan en el núcleo (debido a que han efectuado una llamada al sistema) tienen una prioridad cuyo valor se encuentra comprendido entre 0 y valor base-1.

Page 83: Tema3 procesos

83Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificaciónPlanificación en UNIX SVR2

? Las colas tienen un algoritmo RR con quantum de 1seg.

? Asignación dinámica de prioridades, de acuerdo con:

? El proceso en ejecución incrementa su uso de CPU en una unidad, cada pulso de reloj (60 veces por segundo).

? Cada segundo se divide el uso de CPU por 2 y se recalcula la nueva prioridad con:

?Uso CPU= uso CPU/2

?Nueva prioridad = valor base + uso CPU /2

?La base puede empeorarse con la llamada “nice”

Page 84: Tema3 procesos

84Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificaciónPlanificación en UNIX SVR2

? Cambios entre modo usuario y núcleo.

?Cuando un proceso realiza una llamada al sistema, no altera su prioridad a menos que deba suspenderse.

?Cuando un proceso es suspendido en el núcleo adquiere una prioridad de núcleo (< 60) que únicamente depende de la razón que le ha llevado a suspenderse y no de su prioridad de usuario.

?Ejemplo: (A>>B, significa que A es más prioritario que B, y por tanto A tiene menor número de prioridad que B)

?Espera de operación en disco >> Espera de entrada de teclado >> Espera de finalización de escritura en pantalla >> Espera de terminación de proceso hijo (ver figura transparencia 85).

?Cuando un proceso finaliza una llamada al sistema, recupera la prioridad que tenía antes de suspenderse dentro del núcleo.

?Aunque el planificador sea expulsivo, un proceso no puede ser expulsado mientras se ejecute dentro del núcleo.

Page 85: Tema3 procesos

85Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación

Esperando finalización hijo

Espera E/S por terminal

Esperando buffer de disco

Esperando E/S de disco

Prioridad de usuario 0

Prioridad de usuario 1

Prioridad de usuario 2

Prioridad de usuario 3

60

61

62

63

59

58

57

56

Procesos esperandoen modo usuario

Procesos esperandoen modo kernel

.

.

.

.

.

.Prioridadmás alta

Prioridadmás baja

Planificación en UNIX

Page 86: Tema3 procesos

86Sistemas Operativos I (00-01) Tema 3: Procesos

Planificación en UNIXProceso A Proceso B Proceso CTiempo

Prioridad t. CPU Prioridad t. CPU Prioridad t. CPU0 60 0

1.

60

60 0 60 0

1 75 30 60 01.

60

60 0

2 67 15 75 30 60 01.

603 63 7

8.

67

67 15 75 30

4 76 33 63 78.

67

67 15

5 68 16 76 33 63 7

? SUPUESTOS:

? A, B, C se crean simult. Los procesos no hacen llamadas al sistema

? Prioridad inicial = Prioridad base = 60

? El menor valor para la prioridad de usuario es el valor base (60), que a su vez indica la clase de mayor prioridad.

? El reloj interrumpe al sistema 60 veces/seg.

? Cada segundo calcula:

t.CPU= t.CPU/2

prioridad= (t.CPU/2) + 60

Page 87: Tema3 procesos

87Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Un ejemplo: Planificación de hilos

I/Ot10

t11

t12

0 1 32

P1

t20

0 5

P2

? Algoritmo del sistema operativo

?Round Robin (RR)

cuanto = 2

? Algoritmo biblioteca threads

? Turno de llegada (FCFS)

? Algoritmo del sistema operativo

?Round Robin (RR)

cuanto = 2

? Algoritmo biblioteca threads

? Turno de llegada (FCFS)

Page 88: Tema3 procesos

88Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación

Threads a nivelde núcleo

Threads de usuario

_

P1 P2

Núcleo

t10t11

t12 t20

tn1 tn2

_

P1 P2

Núcleo

tn1 tn4

t10t11

t12 t20

tn2tn3

_

P1 P2

Núcleo

Threads híbridos

t10t11

t12 t20

tn1 tn2tn3

? Un ejemplo: Planificación de hilos

Page 89: Tema3 procesos

89Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación de hilos a nivel de núcleo

0 1 3 4 6 8 117

tn1 tn4

t10 t11 t12 t20

tn2 tn3 tn1 tn2 tn4

t20t10 t11

Usuario

Núcleo

I/Ot10

t11

t12

0 1 32

P1

t20

0 5

P2 _

P1 P2

Núcleo

tn1 tn4

t10t11

t12 t20

tn2tn3

Page 90: Tema3 procesos

90Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación de hilos a nivel de usuario

0 1 3 5 7 8 9 10 11

tn1

t10 t20 t11 t20

tn2 tn1 tn2 tn1 tn2

t20t11 t12

Usuario

Núcleo

t10

tn1

I/Ot10

t11

t12

0 1 32

P1

t20

0 5

P2 _

P1 P2

Núcleo

t10t11

t12 t20

tn1 tn2

Page 91: Tema3 procesos

91Sistemas Operativos I (00-01) Tema 3: Procesos

6.- Algoritmos de planificación? Planificación de hilos en la aproximación híbrida

0 1 3 5 7 8 9 10 11

tn1

t10 t20 t11 t20

tn2 tn3 tn1 tn2 tn3

t20t12 t10

Usuario

Núcleo

t11

tn2

_

P1 P2

Núcleo

t10t11

t12 t20

tn1 tn2tn3

I/Ot10

t11

t12

0 1 32

P1

t20

0 5

P2

Page 92: Tema3 procesos

92Sistemas Operativos I (00-01) Tema 3: Procesos

Tema 3: Procesos

? Índice

1.- Concepto de proceso.

2.- Implementación de procesos.

3.- Hilos de ejecución (threads).

4.- Conceptos de planificación.

5.- Criterios de planificación.

6.- Algoritmos de planificación.

7.- Evaluación de Algoritmos.

8.- S.O. dirigido por eventos.

Page 93: Tema3 procesos

93Sistemas Operativos I (00-01) Tema 3: Procesos

7.- Evaluación de algoritmos ? Procesos en la selección de un algoritmo:

? (1) Selección de criterios (utilización CPU, t. respuesta, etc.).

? (2) Estudiar la adaptación de cada algoritmo a esos criterios.

Es necesario evaluar para cada sistema cual es el algoritmo de planificación más adecuado.

Page 94: Tema3 procesos

94Sistemas Operativos I (00-01) Tema 3: Procesos

7.- Evaluación de algoritmos? Existen diferentes métodos para llevar a cabo dicha evaluación:

?Evaluación analítica: Dada la carga de trabajos producir una fórmula matemática del rendimiento para cada algoritmo de planificación.

?Modelo determinista: Evaluar el rendimiento para cada caso particular de carga.

?Modelos de colas: Caracterizar la carga con una distribución estadística (distribución exponencial).

– Caracterizar la tasa de llegada de trabajos.

– Caracterizar el tiempo de servicio de un recurso.

– Hacer análisis estadístico de las redes de colas.

Ejemplo: Fórmula de Little n = ? * E

n: tamaño medio de la cola, ? tasa media de llegada, E: tiempo medio de espera en la cola.

?Simulaciones: Hacer un modelo, programarlo y ejecutarlo.

Page 95: Tema3 procesos

95Sistemas Operativos I (00-01) Tema 3: Procesos

Tema 3: Procesos

? Índice

1.- Concepto de proceso.

2.- Implementación de procesos.

3.- Hilos de ejecución (threads).

4.- Conceptos de planificación.

5.- Criterios de planificación.

6.- Algoritmos de planificación.

7.- Evaluación de Algoritmos.

8.- S.O. dirigido por eventos.

Page 96: Tema3 procesos

96Sistemas Operativos I (00-01) Tema 3: Procesos

8.- S.O. dirigido por eventos? El S.O. puede verse como un programa que atiende y sirve los eventos

producidos por los procesos y los dispositivos.

? Cuando se da alguno de estos eventos cambia el estado de alguno de los procesos existentes en el sistema o el propio estado del sistema operativo.

? ¿ Qué podemos considerar un evento de este tipo ?

?Una llamada al sistema.

?Una interrupción de un dispositivo de E/S.

?Una interrupción de reloj.

?Una excepción provocada por el código de un proceso (Instrucciones ilegales, acceso a memoria no asignada, divisiones por cero, ...).

Page 97: Tema3 procesos

97Sistemas Operativos I (00-01) Tema 3: Procesos

8.- S.O. dirigido por eventos

Proceso actual

Atención de llamadas

Atención deexcepciones

Suspensióndel proceso

Terminacióndel proceso

Activacióndel proceso

Atención de interrupciones

Llamada

Excepción

IPC

IPC, espera E/S

Terminación

Instr. ilegal,div. por cero

Fallo de página

Fin de E/S

InterrupciónHW

SISTEMAOPERATIVO

Fin de esperatemporal

Planificación

Fin de quantum

Page 98: Tema3 procesos

98Sistemas Operativos I (00-01) Tema 3: Procesos

Flujo de control del S.O.

Reloj Interrupción deperiférico

Llamada alSistema

Excepción delProcesador

Realizar cambio de modo de ejecución (núcleo -> usuario). Recuperar contexto de usuario.

Anotar elavance del

tiempo

Si tiempo límiteexcedido:

Proceso en ejecución

a preparado

Planificador:Selección del próximo proceso.

Realizar cambio de contexto

Pasar a preparadoal proceso

que esperaba elfin de la E/S

Finalizar elproceso en ejecución

Resolver lallamada al

sistema

Pasar asuspendido al

proceso enejecución

Crear hijo.Hijo a

preparado

Guardar parte del contexto de usuario, para realizar cambio de modo de ejecución (usuario->núcleo)

Activación delSistema Operativo