Sistemas Operativos.

Gestión de ProcesosGestión de Procesos

Sistemas Informáticos

I.E.S. Virgen de la Paloma

2

Introducción (I)2

� Programa:� Algo estático, un conjunto de instrucciones que, una vez ejecutadas, resuelven un determinado problema .

� Proceso:� Algo dinámico, es una parte de un programa que se está

2

� Algo dinámico, es una parte de un programa que se está ejecutando con todo lo que ello conlleva: valores de registros, de variables, contenido del contador de programa, etc.

� De un programa suelen surgir varios procesos.

3

Introducción (II)3� Componentes de un proceso:

� Además de las líneas de código, un proceso precisa la imagen del proceso que podrá residir en memoria secundaria, pero debe cargarse en memoria principal a la hora de ejecutarlo:

� Ubicación de variables y constantes definidas por el proceso.

� Pila asociada a cada proceso para gestionar las llamadas a funciones.

� Atributos del proceso guardados en el BCP: Bloque de control del proceso, que contiene:

3

proceso, que contiene:

� Identificación del proceso.

� Información sobre el estado del procesador.

� Información de control del proceso.

� Se guardan en la TBCP: Tabla de bloques de control del proceso.

� Cambios de contexto: La concurrencia de procesos implica que éstos entrarán y saldrán de la CPU constantemente sin haber terminado de ejecutarse.

4

Introducción (III)4

�Estados de los procesos (modelo de 3 estados):� EJECUCIÓN: Está utilizando la CPU en este momento.

� LISTO: Con posibilidad de entrar en ejecución.

� BLOQUEADO: Sin posibilidad de entrar en ejecución.

�En un modelo de 5 estados tenemos además:� NUEVO: Se acaba de crear y aún habiendo sido admitido por el Sistema

Operativo, no está listo para la ejecución.

4

Operativo, no está listo para la ejecución.

� TERMINADO: Ha terminado su ejecución o es abandonado por el S.O.,

p.e. por un error irrecuperable. Este proceso no se volverá a ejecutar,

pero sus tablas de valores permanecerán durante un tiempo por si algún

otro programa necesitase extraer alguna información de ellas.

�Transiciones posibles (modelo de 3 estados): � Ejecución a Bloqueado

� Bloqueado a Listo

� Ejecución a Listo y viceversa

5

Control del proceso (I)5 � Creación del proceso. Pasos del S.O.

� Asignar al proceso un identificativo por el que lo reconocerá de ahora en adelante, e incluirlo en la TBCP.

� Reservar espacio de memoria suficiente para almacenar la imagen del proceso. También reservar sitio para el BCP.

� Rellenar los datos del BCP. Todos los valores a 0, el contador de programa que apuntará a la primera instrucción del

5

de programa que apuntará a la primera instrucción del programa, los punteros de pila que darán los límites de la pila del proceso, el estado se inicializará a listo, la prioridad la más baja, a menos que haya una solicitud para un valor mayor, etc.

� Establecer los enlaces adecuados de este proceso con otros.

� Crear las estructuras de datos vinculadas al propio proceso.

6

Control del proceso (II)6

� Cambios de contexto.� Se produce cuando un proceso no puede seguir ejecutándose, el

S.O. lo detecta e intenta resolver la situación, bien para volver a

reanudar el mismo proceso o para cambiar a otro.

� Conlleva las siguientes acciones:

� Salvar el contexto del proceso que abandona la ejecución

(registros del procesador).

Cambiar el estado del proceso que abandona, que ya no será en

6

� Cambiar el estado del proceso que abandona, que ya no será en

ejecución sino que, dependiendo del motivo del cambio pasará a

listo, bloqueado, terminado, etc. modificando su BCP.

� Mover el BCP a la cola que corresponda (dependiendo de su

estado).

� Solicitar otro proceso para la ejecución.

� Actualizar el BCP del proceso que ahora entrará en ejecución.

� Actualizar las estructuras de datos necesarias para la gestión de

memoria.

� Volcar en el procesador el contexto del proceso que ahora pasa a ejecutarse.

7

Procesos e Hilos7� Proceso: Unidad de recursos

� Hilo: Línea de ejecución o proceso ligero. Ventajas:

� La mayoría de la información del BCP es compartida por los hilos.

� El S.O. tarda mucho menos en crear, intercambiar y terminar

7

El S.O. tarda mucho menos en crear, intercambiar y terminar hilos.

� Los cambios entre hilos no incluyen el intercambio de información de administración de la memoria.

�Al compartir memoria, la comunicación entre hilos en inmediata.

�Varios hilos de un proceso podrían ejecutarse de forma paralela.

8

Comunicación entre procesos (I)8

� En los sistemas multiproceso, la Concurrenciaentre procesos es una tarea compleja.

� El objetivo de la concurrencia es garantizar la Sincronización entre procesos.� Sincronización en el acceso a recursos compartidos

8

� Sincronización en el acceso a recursos compartidos

�Asignar los recursos de forma óptima (evitar Bloqueos)

� La solución a estos problemas es proteger a los recursos compartidos controlando el código que accede a cada uno.

9

Comunicación entre procesos (II)9� Si existe competencia entre procesos, el S.O. debeabordar tres problemas:

� Necesidad de la exclusión mutua: Sección Crítica: parte de losprocesos donde se hace uso de un recurso no compartible Nuncahabrá más de un proceso ejecutando su sección crítica.

� Interbloqueo, se produce si dos procesos necesitan dos

9

� Interbloqueo, se produce si dos procesos necesitan dosdispositivos para poder entrar en su sección crítica y el S.O. leasigna uno a cada uno. Los dos procesos se quedaránbloqueados indefinidamente, ya que ninguno va a poderacceder al otro dispositivo para poder continuar su ejecución.

� Inanición, se presenta cuando a un proceso no llega aasignársele un dispositivo y. por lo tanto, no puede entrar en susección crítica porque, por ejemplo, existen otros dos procesos alos que se les está asignando de forma alternante.

10

Comunicación entre procesos (III)10� Para poder lograr una sincronización de los procesos, el sistema deberá ser capaz de cumplir con la exclusión mutua además de satisfacer los siguientes objetivos :

� Si un proceso se interrumpe en una sección no crítica, no debe

estorbar al resto de los procesos.

� Deben controlarse el interbloqueo y la inanición.

10

� Deben controlarse el interbloqueo y la inanición.

� Un proceso podrá poder entrar en su sección crítica si no hay otros

procesos que estén en la suya.

� Un proceso no puede permanecer de forma indefinida en su

sección crítica.

11

Comunicación entre procesos (IV)11� Hay varias formas de hacer cumplir esas condiciones :

� Soluciones software: dejar la responsabilidad a los mismos

procesos, que cooperen para cumplir con estos objetivos sin

ayuda del S.O.

� Algoritmos de Dekker y Peterson: algoritmos de exclusión mutua

mediante variables Turno y Señal.

Soluciones hardware: utilizar instrucciones de la máquina para

11

� Soluciones hardware: utilizar instrucciones de la máquina para

este control.

� Inhabilitación de interrupciones

� Instrucciones especiales. Se ejecutan seguidas sin soltar el control CPU

� Hacer responsable al Sistema Operativo.

� Semáforos

� Monitores

� Paso de mensajes

12

Comunicación entre procesos (V)12� Semáforos :

� Un mecanismo semáforo consta básicamente de dos operacionesprimitivas Signal(S) y Wait(S) que operan sobre un tipo especialde variable semáforo S, que sólo puede tomar valores enteros.

� El semáforo se inicializa a 1.

� El primer proceso que entra, ejecuta Wait(S) y lo baja a 0.

Un proceso se bloquea si deja el semáforo en <0.

12

� Un proceso se bloquea si deja el semáforo en <0.

� El segundo proceso que entra, ejecuta Wait(S) y lo baja a -1. Sebloquea.

� Si llegan más, se sigue decrementando. El valor absoluto nos dicecuántos procesos están esperando.

� Cuando el primer proceso termina, ejecuta Signal(S), subiendo 1 elvalor y desbloqueando el segundo proceso.

� Existen semáforos binarios: sólo toman los valores 0 y 1.

13

Comunicación entre procesos (VI)13� Monitores :

� Estructuras de lenguajes de programación que permitenexclusión mutua y sincronización de procesos . No los realiza elprogramador como los semáforos.

� CWAIT(C): el proceso que efectúe un CWAIT sobre una variable decondición, C, se suspende, se encola sobre la cola de procesos dedicha variable y libera el monitor, es decir, aunque no se haya

13

dicha variable y libera el monitor, es decir, aunque no se hayacompletado un procedimiento, el proceso deja de estar activo dentrodel monitor y por lo tanto otro proceso podrá entrar.

� CSIGNAL(C): sobre una variable condición C, activa un proceso de lossituados en la cola de dicha variable, si hay varios elegirá uno. En elcaso de que no haya procesos encolados, CSIGNAL(C) no hará nada.

14

Comunicación entre procesos (VII)14� Paso de mensajes :

� Las primitivas vistas hasta ahora tienen cada una suslimitaciones:

� los semáforos son de un nivel muy bajo.

� los monitores sólo los permiten unos pocos lenguajes de programación.

� ninguno de ellos sirve para el intercambio de información entreordenadores.

14

ordenadores.

� La técnica de paso de mensajes permite la sincronización deprocesos y facilita la comunicación entre ellos.

� Existen dos operaciones básicas para el paso de mensajes:

� SEND (destino, mensaje): la utilizan los procesos para enviar unmensaje a un proceso destino.

� RECEIVE (origen, mensaje): la utilizan los procesos para recibir unmensaje desde otro proceso origen.

15

Comunicación entre procesos (VIII)15� Exclusión mutua :

� Un conjunto de procesos concurrentes comparte un buzón(exmut) que contiene inicialmente un único mensaje decontenido nulo.

� Cuando un proceso pretende entrar en su sección crítica primerointenta recibir un mensaje, y si encuentra el buzón vacío el procesose bloquea.

15

se bloquea.

� Cuando el proceso logra el mensaje entra a ejecutar su seccióncrítica y al terminar devuelve el mensaje al buzón .

� El mensaje actúa como testigo o token.

� Cuando existen varios procesos ejecutando la orden receive

concurrentemente se entrega el mensaje, si lo hubiera, a uno de losprocesos y los demás se bloquean y si no hubiera mensaje todosquedarían bloqueados.

16

Interbloqueo (I)16

� Condiciones necesarias, pero no suficientes

�Exclusión mutua.

�No apropiación.

�Retención y Espera.

16

� Condición necesaria y suficiente si se da con las anteriores.

�Espera Circular.

17

Interbloqueo (II)17 � Mecanismos para evitar el Interbloqueo

� Prevención: evitar cada una de las condiciones anteriores.

� Detección: si se detecta interbloqueo se pueden eliminardirectamente los procesos implicados, ir eliminando uno auno o retornar los procesos a su último breakpoint yvolverlos a lanzar.

17

volverlos a lanzar.

� Evitación: “Algoritmo del banquero” si se descubre algúnpeligro de Interbloqueo, no se dan los recursos..

18

Planificación de Procesos (I)18 � La planificación de procesos no sólo abarca la

decisión del proceso que entrará en ejecucióninmediatamente, sino que también abarca otro tipode decisiones:

� Planificación a largo plazo: el S.O. decide crear un procesonuevo y lo añade al grupo de procesos a ejecutar,

18

nuevo y lo añade al grupo de procesos a ejecutar,controlando así el grado de multiprogramación.

� Planificación a medio plazo: afecta a los programas quepodrán pasar a memoria principal pera entrar enejecución, teniendo en cuenta las necesidades de memoriadel proceso.

� Planificación a corto plazo: qué proceso (listo) deberálanzarse a continuación.

19

Planificación de Procesos (II)19

� Objetivos de la Planificación a Corto Plazo� Justicia: asegurarse que todos los procesos tengan su tomo de CPU.

� Eficiencia: mantener la CPU ocupada todo el tiempo.

� Tiempo de respuesta: minimizar el tiempo de respuesta de

19

� Tiempo de respuesta: minimizar el tiempo de respuesta de los usuarios interactivos.

� Rendimiento o productividad: maximizar el número de trabajos terminados por hora.

� Tiempo de regreso: minimizar el tiempo medio de espera de los usuarios por lotes para obtener los resultados.

20

Planificación de Procesos (III)20 � Todos los procesos alternan entre una fase de

ejecución de CPU y otra de espera por E/S.

� Intensivos en E/S (I/O-bound)

� Intensivos en CPU (CPU-bound)

� Prioridades. Cada proceso tiene asignada una prioridad y siempre tendrá preferencia un proceso

20

prioridad y siempre tendrá preferencia un proceso de prioridad más alta sobre uno de prioridad menor

� Transiciones entre estados de un proceso:

� a) Ejecución a bloqueado.

� b) Ejecución a terminado.

� c) Ejecución a listo.

� d) Bloqueado a listo.

21

Algoritmos de Planificación (I)21

� FCFS (First come, first server): El primero que llega se atiende primero.

� Atención por orden de llegada.

� Justo. Simula el mundo real (cola del supermercado).

� Típicamente no apropiativo

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

� Orden de llegada: P1, P2 y P3

21

� Orden de llegada: P1, P2 y P3

� Tiempo de espera: P1 = 0; P2 = 24; P3 = 27

�Ventajas:

� Ningún proceso espera indefinidamente

�Desventajas:

� El tiempo de espera promedio suele ser alto

� Puede producir baja utilización de recursos

22

Algoritmos de Planificación (II)22 � SJN (Shortest Job next): El trabajo más corto primero.

� Asocia cada proceso con su tiempo de ejecución.

� La CPU se asigna al proceso con el menor tiempo de ejecución.

� Si hay dos procesos con el mismo Tejecución se aplicará FCFS.

� Puede ser de dos tipos: apropiativo y no apropiativo

� Tabla de tiempos de ejemplo

22

� Tabla de tiempos de ejemplo

Proceso T. Llegada T. Ejecución

P1 0 7

P2 2 4

P3 4 1

P4 5 4

23

Algoritmos de Planificación (III)23 �No apropiativo

23

�Apropiativo (Shortest Remaining Time First)

24

Algoritmos de Planificación (IV)24

�Ventajas:

� Parece perfecto.

� Consigue mejor tiempo de respuesta que FCFS.

�Desventajas:

� Puede producir alguna espera indefinida si llegan trabajos muy

24

� Puede producir alguna espera indefinida si llegan trabajos muycortos.

� ¿Cómo puedo estimar el tiempo de ejecución del próximoproceso?.

25

Algoritmos de Planificación (V)25

� RR: Carrusel o Round Robin: como FCFS, pero conexpropiación. Después de un tiempo se pasa al siguiente.

� La cola de proceso se trata como una FIFO circular.

� A cada proceso se le entrega la CPU por un espacio de tiempollamado quantum.

Un proceso se ejecuta hasta que acaba o hasta que termina su

25

� Un proceso se ejecuta hasta que acaba o hasta que termina suquantum.

� Ejemplo de procesos anteriores, con un quantum de 4ms

�Ventajas:

� Perfecto para procesos interactivos (Sist. Tiempo Compartido)

26

Algoritmos de Planificación (VI)26

�Desventajas: Dependiendo del valor del quantum

� Si es muy pequeño: Tiempo overhead por cambio de contexto.

� Si es muy grande: Se acerca a FCFS

� Recomendación: 80% de los tiempos de ejecución de losprocesos deberían ser más cortos que el quantum.

� Ejemplo:

quantum = 20

Proceso T. Ejecución

P1 53

26

� quantum = 20 P1 53

P2 17

P3 68

P4 24

27

Algoritmos de Planificación (VII)27

� Por Prioridad:

� Se ejecuta el proceso de mayor prioridad

� Si hay procesos con igual prioridad, aplicar FCFS

� En SJF la prioridad es el tiempo de ejecución

� Ejemplo: ¿Cómo se ejecutarían los siguientes procesos siguiendouna planificación por prioridad?

27

una planificación por prioridad?

Proceso Tiempo Ejecución Prioridad

P1 10 3

P2 1 1

P3 2 4

P4 1 5

P5 5 2

28

Algoritmos de Planificación (VIII)28

�Cómo Asignar Prioridades: .

� Internamente por Sistema Operativo: en base al uso de recursos(memoria, archivos, etc…)

� Externamente dependiendo de la importancia de los procesos

� Suelen aumentar la prioridad por edad del proceso,

28

Suelen aumentar la prioridad por edad del proceso,para que no haya inanición por prioridad baja(Envejecimiento).

29

Algoritmos de Planificación (IX)29 �Múltiples colas: algoritmos intra-cola e inter-colas.

� Tiene una jerarquía de varias colas de procesos.

� Asigna prioridades para ordenar las colas.

� Cada cola se puede planificar con un algoritmo.

� Los quantums pueden ser distintos para cada cola (Si utiliza RR)

� Los procesos pueden cambiar de cola en base a su historia.

29

� Los procesos pueden cambiar de cola en base a su historia.

�Caso: Múltiples colas retroalimentadas (Utiliza RR)

� Su idea es separar los procesos en base a sus necesidades deejecución.

� Los procesos interactivos en las colas de mayor prioridad.

� Los procesos intensivos en CPU en las colas de menor prioridad.

� Aplica el “envejecimiento”.

30

Algoritmos de Planificación (X)30

� Planificación en dos niveles

� Unos procesos en memoria y otros en disco.

� A corto plazo decide a qué proceso se le asigna la CPU(Cualquiera de los algoritmos anteriores).

� A largo plazo decide qué procesos pasan a disco (Cualquierade los algoritmos anteriores). Muy similar al funcionamiento de la

30

de los algoritmos anteriores). Muy similar al funcionamiento de lamemoria caché.

31

Según los Sistemas Operativos (I)31� Planificación de Procesos en UNIX

�Usa múltiples colas realimentadas.

� Dependiendo del tipo de proceso

� Procesos de Tiempo Compartido

� Procesos del Sistema

� Procesos de Tiempo Real

31

� Procesos de Tiempo Real

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

� Los procesos cambian su prioridad dinámicamente

� Se incrementa la prioridad si el proceso hace E/S antes de terminar su quantum.

� Se decrementa si el proceso utiliza todo su quantum.

32

Según los Sistemas Operativos (II)32� Planificación de Procesos en Linux

�Utiliza dos algoritmos para la planificación de procesos

�Algoritmo para procesos en tiempo compartido

� Prioridades y créditos asociados a cada proceso.

� Proceso con más créditos se ejecuta primero.

32

� Proceso con más créditos se ejecuta primero.

� A cada interrupción del timer se decrementan créditos del proceso en ejecución. Si llega a 0, siguiente proceso.

� Cuando todos los procesos llegan a crédito 0, se recalculan.

�Algoritmo para procesos en tiempo real

� Las prioridades absolutas son más importantes que la justicia.

33

Según los Sistemas Operativos (II)33

� Planificación de Procesos en Windows

�Utiliza un enfoque basado en Prioridades.

� Modela de esta forma los distintos grados de urgencia en el tratamiento de los dispositivos.

� Implementa Hilos.

33

� Implementa Hilos.

�Tiene un sistema de gestión de excepciones complejo:

� Estructurado.

� Similar al que utilizan lenguajes como C++ o Java