Unidad 2

Procesos e
hilos
Paula C. Martinez
Organización
● Procesos
● Hilos
● Planificación de procesos
● Problemas clásicos de comunicación entre procesos
Pseudo-paralelismo
● Todas las computadoras modernas realizan varias tareas al mismo tiempo
● En un sistema con un único procesador, en un instante dado, el CPU está
ejecutando una sola tarea o proceso.
● Pero en sistemas multiproceso, el CPU cambia entre procesos rápidamente,
ejecutando cada uno de ellos durante varias decenas o centenas de
milisegundos.
El modelo de procesos

Figura 2.1
(a) Multiprogramación de cuatro programas.
(b) Modelo conceptual de cuatro procesos secuenciales independientes.
(c) Solo un programa se encuentra activo a la vez.
Diferencia entre proceso y programa
● Un programa en ejecución es un proceso.
● La diferencia está en que un proceso es algo dinámico, está siendo ejecutado
por la CPU, con variables que cambian en el tiempo, con un contador de
programa, registros, etc.
● Un programa son solo datos.
Creación de procesos
Eventos que generan la creación de un proceso:

● Arranque del sistema

● Cuando un proceso en ejecución llama la función del sistema para crear un
proceso
● Un usuario solicita la creación de un nuevo proceso.
● Inicio de un trabajo por lotes.
Finalización de un proceso
Eventos que provocan la finalización de un proceso:

● Finalización normal (voluntaria)

● Finalización por error (voluntaria)
● Error fatal (involuntaria)
● Eliminado por otro proceso (involuntaria)
Estado de los procesos

1. El proceso se bloquea para

recibir entrada
2. El planificador selecciona
otro proceso.
3. El planificador selecciona
este proceso.
4. La entrada ya está
disponible.

Figura 2-2. Un proceso puede estar en estado “en ejecución”, “bloqueado” o “listo”.
Se muestran las transiciones entre estos estados.
Implementación de procesos (1)

Figura 2-3. La capa más baja de un sistema operativo estructurado con procesos
maneja las interrupciones y la planificación. Por encima de esa capa se encuentran
los procesos seriales.
Implementación de procesos (2)

Figura 2-4. Algunos de los campos de una entrada típica en la tabla de procesos.
Implementación de procesos (3)

Figura 2-5. Esqueleto de lo que hace el nivel más bajo del sistema operativo cuando
ocurre una interrupción.
Modelación de la multiprogramación

Figura 2-6. Uso de la CPU como una función del número de procesos en memoria.
Hilos

Figura 2-7.Un procesador de palabras con tres hilos.

Hilos (2)

Figura 2-8. Un servidor Web con múltiples hilos.

Hilos (3)

Figura 2-9. Un bosquejo del código para la figura 2-8. (a) Hilo despachador. (b) Hilo
trabajador.
Modelo clásico de hilos

Figura 2-11. (a) Tres procesos, cada uno con un hilo. (b) Un proceso con tres hilos.
Modelo clásico de hilos

Figura 2-12. La primera columna lista algunos elementos compartidos por todos los
hilos en un proceso; la segunda, algunos elementos que son privados para cada hilo.
Modelo clásico de hilos

Figura 2-13. Cada hilo tiene su propia pila.

Hilo
● Tiene su propio contador de programa, set de registros y pila.
● Comparte el código (texto), datos globales, archivos abiertos.
○ Con otros hilos dentro de un mismo proceso pesado (HWP)
○ Pero no con hilos dentro de otros procesos pesados.
● Puede tener su propio bloque de control de proceso (PCB)
○ depende del SO.
○ El contexto involucra el ID del hilo, contador de programa, set de registros, puntero de pila.
○ Espacio de memoria RAM compartido entre los hilos del mismo proceso.
Hilos: beneficios
● Capacidad de respuesta del usuario
○ Cuando un hilo se bloquea, otro puede manejar E/S del usuario.
○ Pero depende de la implementación de hilos.

● Compartir recursos: economía

○ La memoria es compartida.
○ Archivos abiertos, sockets compartidos.

● Velocidad
○ Ej. en Solaris: la creacion de hilos es 30x mas rapida que la creación de procesos pesados, el
cambio de contexto es 5x más rápido con hilos.

● Utilizar paralelismo de hardware

○ Como los procesos pesados, los hilos también puede utilizar la arquitectura de
multiprocesadores
Hilos: desventajas
● Sincronización:
○ El acceso a la memoria compartida o variables compartidas debe ser controlado si la memoria o
las variables son modificadas o actualizadas.
○ Puede agregar complejidad o errores al código del programa.
○ Ej. es necesario ser muy cuidadoso para evitar condiciones de carrera, interbloqueos y otros
problemas.
● Falta de independencia:
○ Los hilos dentro de un HWP no son independientes.
○ El espacio de direcciones de memoria RAM es compartido, no hay protección de memoria entre
hilos.
○ Las pilas de cada hilo se suponen que están separadas en la memoria RAM, pero si un hilo tiene
algún problema (ej. con direccionamiento de punteros o arreglos), puede escribir sobre la pila de
otro hilo.
Hilos POSIX

Figura 2-14. Algunas de las llamadas a funciones de Pthreads.

Hilos POSIX

Figura 2-15. Un programa de ejemplo que

utiliza hilos
Implementación de hilos en espacio de usuario

Figura 2-16. (a) Un paquete de hilos de nivel usuario. (b) Un paquete de hilos administrado por el kernel.
Implementación híbrida

Figura 2-17. Multiplexado de hilos del nivel usuario sobre hilos del nivel kernel.
 Hilos emergentes

Figura 2.18. Creación de un nuevo hilo cuando llega un mensaje. (a) Antes de que llegue el mensaje. (b) Después
de que llega el mensaje.
 Conversión de código de hilado simple a multihilado

Figura 2-19. Conflictos entre los hilos por el uso de una variable global
Comunicación entre procesos (IPC)
Tres temas importantes:

● cómo un proceso puede pasar información a otro.

● hacer que dos o más procesos no se interpongan entre sí
● obtener la secuencia apropiada cuando hay dependencias presentes: si el
proceso A produce datos y el proceso B los imprime, B tiene que esperar hasta
que A haya producido algunos datos antes de empezar a imprimir.
Condiciones de carrera

Figura 2-21. Dos procesos desean acceder a la memoria compartida al mismo

tiempo.
Condiciones de carrera
● Dos o más procesos están leyendo o escribiendo datos compartidos y el
resultado final depende de cuando cada proceso ejecuta los datos compartidos.
● dos o más procesos están leyendo o escribiendo algunos datos compartidos y el
resultado final depende de quién se ejecuta y exactamente cuándo lo hace
● Depurar programas que contienen condiciones de carrera no es nada fácil, los
resultados de la mayoría de las ejecuciones de prueba están bien, pero en algún
momento poco frecuente ocurrirá algo extraño e inexplicable.
Condiciones de carrera: soluciones
● Exclusión mutua:
○ prohibir que más de un proceso esté leyendo y escribiendo datos compartidos al mismo tiempo.

● Región crítica:
○ partes de un programa donde el acceso a la memoria es compartido.
Condiciones de carrera: región crítica
Se deben cumplir las siguientes cuatro condiciones para proveer exclusión mutua:

1. No puede haber dos procesos de manera simultánea dentro de sus regiones

críticas.
2. No pueden hacerse suposiciones acerca de las velocidades o el número de
CPUs.
3. Ningún proceso que se ejecute fuera de su región crítica puede bloquear otros
procesos.
4. Ningún proceso tiene que esperar para siempre para entrar a su región crítica.
Regiones críticas

Figura 2-22. Exclusión mutua mediante el uso de regiones críticas

Caso real: condiciones de carrera
● Entre Junio de 1985 y Enero de 1987, algunos pacientes con cáncer que estaban siendo
tratados radiación fueron heridos y fallecieron debido a problemas con el software.

● Se realizaron sobredosis masivas en 6 pacientes, 3 fallecieron.

● El software tenía condiciones de carrera asociadas con la pantalla de comandos.

● El software no estaba correctamente sincronizado.

● Más información en:

○ p. 340-341 Quinn (2006), Ethics for the Information Age
○ Nancy G. Leveson, Clark S. Turner, "An Investigation of the Therac-25 Accidents," Computer,
vol. 26, no. 7, pp. 18-41, July 1993
http://doi.ieeecomputersociety.org/10.1109/MC.1993.274940
Propuestas para conseguir exclusión mutua
● Desactivar interrupciones.
● Variables candado
● Alternancia estricta
● Solución de Peterson
● Instrucción TSL
Exclusión mutua con espera ocupada
Deshabilitar interrupciones:

● Después de ingresar en una región crítica, deshabilitar todos las interrupciones.

● Debido a que el reloj es una interrupción, el CPU no puede interrumpir.
● Desactivar las interrupciones es útil para el SO, pero no para los usuario...
Exclusión mutua con espera ocupada
Variable de candado:

● Una solución de software

● Una única variable compartida (lock), antes de ingresar en la región crítica, los
programas controlan esta variable, si es 0, no hay competición, si es 1, la región
crítica está ocupada.
● Cual es el problema?
● Esta idea contiene exactamente el mismo problema que la condición de carrera está
intentando solucionar. Quien lee o escribe primero la variable candado puede
provocar que otro proceso piense que la variable está en 0 cuando un proceso previo
está por escribirla en 1.
Exclusión mutua con espera ocupada
Alternancia estricta:

Figura 2-23. Una solución propuesta para el problema de la región crítica. (a) Proceso 0. (b)
Proceso 1. En ambos casos, asegúrese de tener en cuenta los signos de punto y coma que
terminan las instrucciones while . La variable turno es compartida entre los procesos.
Conceptos de exclusión mutua

● Espera ocupada:
○ Continuamente controlar una variable por una condición hasta que un valor especifico aparece
ej. while (turno!=0)

● Candado de giro:
○ Un candado que utiliza la espera ocupada como variable de control, ej. variable turno.
Exclusión mutua: solución de Peterson

Figura 2-24. Solución de Peterson para lograr la exclusión mutua.

Exclusión mutua: instrucción TSL

Figura 2-25. Cómo entrar y salir de una región crítica mediante la instrucción TSL
Dormir y despertar
● Desventajas de espera ocupada:
○ Un proceso con una prioridad baja entra en una región crítica
○ Un proceso con prioridad alta entra y quita el proceso con prioridad baja, el proceso con
prioridad alta desperdicia ciclos CPU mientras se queda en espera ocupada, mientras que el
proceso con prioridad baja no sale de la región crítica.
○ problema de inversión de prioridades

● Bloquear en lugar de espera ocupada:

○ dormir y despertar
El problema del productor-consumidor
● Dos procesos comparten un buffer común de tamaño fijo

● El productor guarda información en el buffer

● El consumidor lee información del buffer.

● Una solución simple utilizando dormir y despertar:

Dormir y despertar

Figura 2-27. El problema del productor-consumidor con una condición de carrera fatal.
El problema del productor-consumidor
● Cual puede ser el problema?

● Señal faltante:
○ Variable compartida: contador

○ Mismo problema causado por la concurrencia

○ Cuando el consumidor lee el contador con un 0 pero no se duerme a tiempo, la señal se perderá

○ Consumidor y productor pueden quedar ambos dormidos.

Semáforos
● Dijkstra propuso introducir un nuevo tipo de variable
● Acción atómica: una única e indivisible acción.
● Down:
○ Controla un semáforo para ver si esta en 0, si es asi, se duerme, sino, decrementa el valor y
continua.
● Up:
○ Controla el semáforo
○ Si hay procesos esperando en el semáforo, el SO decidirá proceder, y completará una acción
down previa.

● Ningún proceso se bloquea realizando una operación down o up.

Semáforos
Resuelve el problema de productor-consumidor

● Llenas: cuenta las ranuras llenas, valor inicial 0.

● Vacías: cuenta las ranuras vacías, valor inicial N.
● Mutex: previene que el consumidor y productor accedan al buffer al mismo
tiempo, valor inicial 0 (semáforo binario).
● El uso de semáforos es para proveer Sincronización, este uso es distinto al de
exclusión mutua.
Semáforos

Figura 2-28. El problema del productor-consumidor mediante el uso de semáforos.

Mutexes
● Cuando no se necesita la habilidad del semáforo de contar, algunas veces se utiliza una versión
simplificada, llamada mutex.
● Los mutexes son buenos sólo para administrar la exclusión mutua para cierto recurso compartido o
pieza de código.
● Un mutex es una variable que puede estar en uno de dos estados: abierto (desbloqueado) o cerrado
(bloqueado) (solo requiere un bit)
● Se utilizan dos procedimientos con los mutexes: mutex_lock y mutex_unlock
● Cuando un hilo (o proceso) necesita acceso a una región crítica, llama a mutex_lock. Si el mutex está
actualmente abierto (lo que significa que la región crítica está disponible), la llamada tiene éxito y
entonces el hilo llamador puede entrar a la región crítica.
● Por otro lado, si el mutex ya se encuentra cerrado, el hilo que hizo la llamada se bloquea hasta que el
hilo que está en la región crítica termine y llame a mutex_unlock.
● Si se bloquean varios hilos por el mutex, se selecciona uno de ellos al azar y se permite que adquiera el
mutex.
Mutexes

Figura 2-29. Implementaciones de mutex_lock y mutex_unlock.

Mutexes con Pthreads (1)

Figura 2-30. Algunas de las llamadas de Pthreads relacionadas con mutexes.

Mutexes con Pthreads (2)

Figura 2-31. Algunas de las llamadas a Pthreads que se relacionan con las variables de condición.
Mutexes con Pthreads (3)

Figura 2-32. Uso de hilos para resolver el problema del productor-consumidor.

Monitores
● Con los semáforos y los mutexes la comunicación entre procesos se ve sencilla.

● Analice de cerca el orden de las operaciones down antes de insertar o quitar elementos del búfer en la
figura 2-28.

● Suponga que se invirtió el orden de las dos operaciones down en el código del productor, de manera
que mutex se disminuyó antes de vacías, en vez de hacerlo después.

● Si el búfer estuviera completamente lleno el productor se bloquearía, con mutex establecida en 0.

● En consecuencia, la próxima vez que el consumidor tratará de acceder al búfer, realizaría una
operación down en mutex (que ahora es 0) y se bloquearía también.

● Ambos procesos permanecerán bloqueados de manera indefinida y no se realizaría más trabajo.

● Esta desafortunada situación se conoce como interbloqueo (deadlock).

● Mas adelante en otra unidad se tratará el problema de Interbloqueo.

Monitores
● Hansen y Hoare propusieron una primitiva de sincronización de mayor nivel
que los semáforos, denominada monitores.
Monitores

Figura 2-34. Un esquema del problema

productor-consumidor con monitores. Sólo hay
un procedimiento de monitor activo a la vez. El
búfer tiene N ranuras.
Pasaje de mensajes (1)

Figura 2-35 Parte 1. Una solución al problema del productor-consumidor en Java.

Pasaje de mensajes (2)

Figura 2-35 Parte 2. Una solución al problema del productor-consumidor en Java.

El problema del productor-consumidor con pasaje de mensajes

Figura 2-36 Parte 1. El problema del productor-consumidor con N mensajes

El problema del productor-consumidor con pasaje de mensajes

Figura 2-36 Parte 2. El problema del productor-consumidor con N mensajes.

Barreras
● Mecanismo de sincronización destinado a los grupos de procesos
● Algunas aplicaciones se dividen en fases y tienen la regla de que ningún proceso
puede continuar a la siguiente fase sino hasta que todos los procesos estén
listos para hacerlo.
● Para lograr este comportamiento, se coloca una barrera al final de cada fase.
● Cuando un proceso llega a la barrera, se bloquea hasta que todos los procesos
han llegado a ella.
Barreras

Figura 2-37. Uso de una barrera. (a) Procesos acercándose a una barrera. (b) Todos los procesos, excepto
uno, bloqueados en la barrera. (c) Cuando el último proceso llega a la barrera, todos se dejan pasar.
Planificación
● Cuando una computadora se multiprograma, con frecuencia tiene varios procesos o hilos que
compiten por la CPU al mismo tiempo.

● Esta situación ocurre cada vez que dos o más de estos procesos se encuentran al mismo tiempo en el
estado listo.

● Si sólo hay una CPU disponible, hay que decidir cuál proceso se va a ejecutar a continuación.

● La parte del sistema operativo que realiza esa decisión se conoce como planificador de procesos y el
algoritmo que utiliza se conoce como algoritmo de planificación.

● Muchas de las mismas cuestiones que se aplican a la planificación de procesos también se aplican a la
planificación de hilos, aunque algunas son distintas.

● Cuando el kernel administra hilos, por lo general la planificación se lleva a cabo por hilo, e importa muy
poco (o nada) a cuál proceso pertenece ese hilo.
Planificación - comportamiento de un proceso

Figura 2-38. Las ráfagas de uso de la CPU se alternan con los periodos de espera por la E/S. (a) Un proceso
ligado a la CPU. (b) Un proceso ligado a la E/S
Planificación - comportamiento de un proceso
● Mientras las CPUs sean más rápidas, los procesos tendrán tiempos de espera
mayores cuando se realice E/S.
● Si un proceso con tiempos de E/S altos quiere ejecutarse, deberia tener que
ejecutarse rapido.
Planificación - conceptos
● Algoritmo preventivo:
○ Si un proceso todavía está ejecutándose después de su intervalo de tiempo, este es suspendido y
otro proceso pasa a ejecutarse.

● Algoritmo no preventivo:
○ Elige un proceso para ser ejecutado y este se ejecuta hasta que se bloquea o voluntariamente
libera la CPU.
Categorías de los algoritmos de planificación
● Distintos entornos requieren algoritmos de planificación diferentes.

● Esta situación se presenta debido a que las diferentes áreas de aplicación (y los distintos
tipos de sistemas operativos) tienen diferentes objetivos.

● Tres de los entornos que vale la pena mencionar son:

1. Procesamiento por lotes:

a. Todavía se utiliza en el ambiente de negocios
b. Algoritmos no preventivos reducen los intercambios entre procesos

2. Interactivo:
a. Es necesario utilizar algoritmos preventivos

3. De tiempo real:
a. Los procesos se ejecutan rápido y bloquean
Metas de los algoritmos de planificación

Figura 2-39. Algunas metas del algoritmo de planificación bajo distintas circunstancias.
Planificación en sistemas de procesamiento por lotes

● Primero en entrar, primero en ser atendido (FCFS)

● El trabajo más corto primero (SJF)

● El menor tiempo restante a continuación (SRTN)

El trabajo más corto primero (SJF)

Figura 2-40. Un ejemplo de planificación tipo el trabajo más corto primero. (a) Ejecución de cuatro trabajos
en el orden original. (b) Ejecución de cuatro trabajos en el orden del tipo “el trabajo más corto primero”.
Planificación en sistemas interactivos
● Planificación por turno circular (round-robin)
● Planificación por prioridad
● Múltiples colas
● El proceso más corto a continuación
● Planificación garantizada
● Planificación por sorteo
● Planificación por partes equitativas.
Planificación por turno circular

Figura 2-41. Planificación de turno circular. (a) La lista de procesos ejecutables. (b) La lista de
procesos ejecutables una vez que B utiliza su quántum (intervalo de tiempo asignado a cada
proceso).
Planificación por prioridad

Figura 2-42. Un algoritmo de planificación con cuatro clases de prioridad.

Planificación de hilos (1)

Figura 2-43. (a) Posible planificación de hilos a nivel usuario con un quántum de 50 mseg para cada proceso e
hilos que se ejecutan durante 5 mseg por cada ráfaga de la CPU. (b) Posible planificación de hilos a nivel
kernel con las mismas características que (a).
Problemas clásicos de comunicación entre procesos (IPC)

● El problema de los filósofos comelones

● El problema de los lectores y escritores

El problema de los filósofos comelones (1)
● Cinco filósofos están sentados alrededor de una mesa circular.

● Cada filósofo tiene un plato de espagueti.

● El espagueti es tan resbaloso, que un filósofo necesita dos tenedores para comerlo.

● Entre cada par de platos hay un tenedor.

● La vida de un filósofo consiste en periodos alternos de comer y pensar

● Cuando un filósofo tiene hambre, trata de adquirir sus tenedores izquierdo y derecho, uno a la
vez, en cualquier orden.

● Si tiene éxito al adquirir dos tenedores, come por un momento, después deja los tenedores y
continúa pensando.

● La pregunta clave es: ¿puede usted escribir un programa para cada filósofo, que haga lo que se
supone debe hacer y nunca se trabe?
El problema de los filósofos comelones (2)

Figura 2-44. El problema de los filósofos comelones

El problema de los filósofos comelones (3)

Figura 2-45. Una solución incorrecta para el problema de los filósofos comelones.
El problema de los filósofos comelones (4)

Figura 2-46 Parte 1. Una solución al problema de los filósofos comelones.

El problema de los filósofos comelones (5)

Figura 2-46 Parte 2. Una solución al problema de los filósofos comelones.

El problema de los filósofos comelones (6)

Figura 2-46 Parte 3. Una solución al problema de los filósofos comelones.

El problema de los lectores y escritores (1)
● El problema de los filósofos comelones es útil para modelar procesos que compiten por el
acceso exclusivo a un número limitado de recursos, como los dispositivos de E/S.

● Otro problema famoso es de los lectores y escritores (Courtois y colaboradores, 1971),

que modela el acceso a una base de datos.

● Por ejemplo, imagine un sistema de reservación de aerolíneas, con muchos procesos en

competencia que desean leer y escribir en él.

● Es aceptable tener varios procesos que lean la base de datos al mismo tiempo, pero si un
proceso está actualizando (escribiendo) la base de datos, ningún otro proceso puede
tener acceso a la base de datos, ni siquiera los lectores.

● ¿cómo se programan los lectores y escritores?

 El problema de los lectores y escritores (2)

Figura 2-47 Parte 1. Una solución al problema de los lectores y escritores.

 El problema de los lectores y escritores (3)

Figura 2-47 Parte 2. Una solución al problema de los lectores y escritores.

Casos de estudio:
Procesos en Linux
Llamada fork() en Linux
● Fork() crea un nuevo proceso duplicando el proceso que realiza la llamada. El
nuevo proceso se llama proceso hijo.
● El proceso padre y el hijo se ejecutan en espacios de memoria distintos.
● En el momento en que se produce el fork(), ambos espacios de memoria tienen
el mismo contenido.
● Las escrituras a memoria y mapeos que realiza un proceso no afectan al otro
proceso.
Llamada fork() en Linux
El proceso hijo es un duplicado exacto del padre, excepto en los siguientes aspectos:

★ Cada uno tiene su propio identificador.

★ Para el proceso hijo, se setean a cero la utilización de recursos y contadores de CPU.
★ Los procesos padre e hijo no comparten memoria.

Todo proceso padre es responsable de los procesos hijos que lanza, por ello, todo proceso
padre debe recoger el resultado de la ejecución de los procesos hijos para que estos finalicen
adecuadamente.

Si un proceso padre no recupera el resultado de la ejecución de su hijo, se dice que el proceso

queda en estado zombi. Un proceso hijo zombi es un proceso que ha terminado su ejecución y
que está pendiente de que su padre recoja el resultado de su ejecución.
 Casos de estudio:
Procesos en Windows
Procesos e Hilos en Windows
● Cada proceso tiene los recursos necesarios para ejecutar un programa (memoria virtual,
código ejecutable, objetos del sistema abiertos, seguridad, pid, variables de ambiente,
etc).

● Cada proceso inicia con un único hilo, luego puede crear más hilos según sea necesario.

● Un hilo es una entidad dentro de un proceso que puede gestionarse para ser ejecutado.

● Todos los hilos comparten el espacio virtual de direcciones y recursos del sistema.

● Cada hilo mantiene valores de manejo de excepciones, valores de prioridad,

almacenamiento local, identificador único de hilo, set de estructuras para guardar los
datos cuando ocurre un cambio de contexto o para preparar el hilo para su ejecución.
Prioridades de ejecución en Windows
● La planificación de ejecución de hilos se basa en su prioridad de ejecución.

● Cada hilo tiene asignada una prioridad que puede ser desde 0 (prioridad más baja) a 31
(prioridad más alta).

● El sistema trata todos los hilos con la misma prioridad como iguales.

● El sistema asigna porciones de tiempo de procesamiento de forma round-robin (por

turnos) a todos los hilos con la prioridad más alta.

● Si ninguno de estos hilos está listo para ser ejecutado, el sistema asigna la porción de
tiempo de forma round-robin a los hilos del siguiente nivel de prioridad.

● Si hilos de prioridad más alta están listos para ser ejecutados, el sistema deja de ejecutar
los hilos de menor nivel de prioridad y asigna la porción de tiempo completa a los hilos de
mayor nivel de prioridad.
Hilos: estados y transiciones
Hilos: estados y transiciones
● Ready: un hilo en el estado Ready está esperando ser ejecutado. Cuando el sistema busca hilos para
ejecutar solo mira el conjunto de hilos que están en este estado para ejecutarlos.

● Deferred ready: Este estado es para hilos que han sido seleccionados para ejecución pero todavía no
se les ha asignado un procesador específico.

● Standby: Un hilo esta en este estado cuando a sido seleccionado para ejecutarse en un procesador
específico. Cuando se cumplen las condiciones, el sistema realiza un cambio de contexto hacia este
hilo. Solo un hilo puede estar en el estado standby por cada procesador existente. Un hilo en este
estado puede ser sacado de este estado si aparece un hilo con mayor prioridad de ejecución

● Running: Una vez que el sistema realiza el cambio de contexto al hilo, el hilo ingresa al estado running y
es ejecutado. El hilo se ejecuta hasta que:
○ Finaliza la porción de tiempo de CPU asignada.
○ El procesador es apropiado (preempted) por un hilo de mayor prioridad.
○ Finaliza su ejecución.
○ Voluntariamente ingresa en el estado de espera.
Hilos: estados y transiciones
● Waiting: Un hilo puede ingresar a este estado por varios motivos: un hilo puede
voluntariamente estar en espera de sincronización, el SO puede esperar en nombre del hilo (ej,
mientras espera por paginacion E/S), o un subsistema puede indicarle al hilo que debe pasar al
estado de espera. Cuando la espera finaliza, el hilo puede comenzar su ejecución o pasar al
estado Ready.

● Transition: Un hilo entra en este estado si está listo para ejecutarse pero su pila del kernel ha
sido paginada fuera de la memoria. Un vez que la pila es traída nuevamente hacia la memoria, el
hilo puede entrar en el estado Ready.

● Terminated: Cuando un hilo finaliza su ejecución, entra en este estado. Luego el sistema puede
(o no, dependiendo de la configuración del administrador de objetos del sistema) recuperar el
espacio en memoria de ocupado por el hilo.

● Initialized: estado utilizado internamente mientras el hilo es creado.

 Casos de estudio:
Sistemas
distribuidos/Paralelos
Modelos de programación paralela
● Memoria compartida (UMA o NUMA)
● Memoria distribuida
● Híbrida (Multi-CPU/GPU)
Memoria Compartida - UMA

● Multiprocesadores: memoria
compartida por un bus.
● UMA - Uniform Memory Access
● Manejo coherente de la memoria
● sobrecarga del bus -> necesidad de
cache
Memoria Distribuida
Computadores conectadas mediante tecnología Ethernet o Infiniband.
Memoria compartida NUMA
Procesadores con memoria RAM local y memoria RAM “remota”, ciertas áreas de memoria serán de más
rápido acceso para un procesador que otras. NUMA: Non-Uniform Memory Access
Modelo Híbrido: multi-CPU/GPU
Ej. Servidor multi-núcleo AMD Opteron
● Mother SuperMicro H8QG
● 4 sockets AMD Opteron 6000 (G34)
● 32 slots de memoria quad-channel (1
TB máximo) DDR3
● 2 slots PCI-E x16 v2.
● 6 SATA
● 8 SAS
● 1 LAN IPMI
● 2 LAN Gigabit

Importante: ocupar todos los canales de

memoria por CPU para obtener el mejor
rendimiento
Ej. Servidor multi-núcleo AMD Opteron
● Arq. tipo “Bulldozer”:
2 “núcleos” por
módulo.
● Cache L2 compartida
dentro del módulo.
● Cache L3 compartida
entre todos los
módulos
● Micro de 16 núcleos:
en realidad son dos
chips de 8 núcleos en
un mismo paquete
 Clusters HPC

Cluster Tupac, Centro de Simulación Computacional para

Aplicaciones Tecnológicas (CSC) dependiente del CONICET,
ARG. Dell, 4.352 cores AMD Opteron Serie 6200, 16.384
cores Nvidia CUDA cores, 8.704 GB de memoria RAM
Summit cluster - Oak Ridge National Laboratory,
USA
IBM Power9 3.07GHz, 2.282.544 núcleos,
2.801.664 GB RAM.
Modelos de programación
● Memoria compartida: OpenMP, pthreads, etc.
● Memoria distribuida: MPI
● Híbrido CPU: OpenMP para ejecutar dentro de un mismo nodo (o CPU) y MPI
para ejecutar utilizando varios nodos a través de la red.
● GPU: ejecución de código utilizando una o varias GPU con CUDA/OpenCL.
● Híbrido multi-GPU/CPU: las tareas a ejecutar o los datos, se separan en varias
partes, se ejecuta tanto en CPU como en GPU de forma simultánea. Se
combinan varias tecnologias como OpenMP, MPI y CUDA/OpenCL.
OpenMP: modelo fork-join
● OpenMP utiliza el modelo paralelo de ejecución fork-join

● Todos los programas OpenMP comienzan con un único proceso, el hilo maestro.

● El hilo maestro ejecuta secuencialmente hasta que se encuentra la primer región paralela.

● FORK: el hilo maestro crea un grupo de hilos paralelos.

● Las sentencias del programa que están encerradas dentro de la región paralela son
ejecutadas en paralelo por todos los hilos del grupo.

● JOIN: cuando los hilos del grupo finalizan su ejecución, se sincronizan y terminan, dejando
solo el hilo maestro en ejecución.

● El número de regiones paralelas y los hilos que las componen es arbitrario.

OpenMP: modelo fork-join
OpenMP y MPI
Ejemplo OpenMP
Ejemplo OpenMP
Compilación en Linux:
# gcc -o omp_ejemplo -fopenmp -lm ejemplo_omp.c

Ejecución en un solo núcleo:

# time OMP_NUM_THREADS= 1 ./omp_ejemplo
OMP_NUM_THREADS=1 ./omp_ejemplo 27.01s user 0.67s system 99% cpu 27.688
total

Ejecución en dos y cuatro núcleos:

# time OMP_NUM_THREADS= 2 ./omp_ejemplo
OMP_NUM_THREADS=2 ./omp_ejemplo 29.05s user 1.01s system 184% cpu 16.253
total

# time OMP_NUM_THREADS= 4 ./omp_ejemplo

OMP_NUM_THREADS=4 ./omp_ejemplo 31.52s user 1.63s system 313% cpu 10.571
Links y referencias
● Resumen del Capítulo 2 del libro Sistemas Operativos Modernos, Tanenbaum, tercera edición, 2008 Prentice-Hall, Inc.
All rights reserved. 0-13-6006639
● Emmanuelle Saillard, Static/Dynamic Analyses for Validation and Improvements of Multi-Model HPC Applications.
Distributed, Parallel, and Cluster Computing [cs.DC]. Université de Bordeaux, 2015. English.
● Tutorial de OpenMP https://computing.llnl.gov/tutorials/openMP/
● Cluster Tupac: https://www.tupac.gob.ar/stories/home/
● Cluster Summit Top500 list: https://www.top500.org/system/179397
● Processes and Threads, Microsoft Docs:
https://docs.microsoft.com/es-es/windows/desktop/ProcThread/processes-and-threads
● Processes, Threads, and Jobs in the Windows Operating System:
https://www.microsoftpressstore.com/articles/article.aspx?p=2233328&seqNum=7