hilos y procesos proceso ● un proceso es un programa en ejecución junto con su ambiente de...
TRANSCRIPT
Hilos y Procesos
Proceso
● Un proceso es un programa en ejecución junto con su ambiente de trabajo
Ambiente de trabajo
● Valores de los registros del CPU asociados al proceso
● Memoria asignada
● Otros recursos asignados al proceso: ej. archivos abiertos
Hilos y Procesos
Registros del CPU. Cambian de valor durante la ejecución del programa
●Contador de programa
●Puntero de pila
●Marco de pila (stack frame pointer)
●Otros (depende de cada CPU)
Estos valores constituyen el contexto del proceso
●Cambio de contexto (context switch)
●El S.O. lleva registro del contexto de cada proceso en una tabla llamada tabla de procesos
Hilos y Procesos
Memoria
● Cuando un proceso es creado se le asigna cierta cantidad de memoria
Estos bloques de memoria contendrán tanto el código como los datos del al proceso
Hilos y Procesos
Los sistemas operativos están formados por
●Núcleo (kernel)
●Manejador de memoria
●Manejador de entrada y salida
●Sistema de archivos
Hilos y Procesos
El núcleo es la parte central del S.O.
● Función: manejo de los procesos
– Crear procesos– Destruir procesos– Planificar la ejecución de los procesos– Ofrecer e implementar mecanismos de comunicación entre
procesos
Hilos y Procesos
Llamadas al sistema
● Los procesos invocan al S.O. mediante llamadas al sistema (system calls)
● Una llamada al sistema es similar a una llamada a un procedimiento, pero el código que se ejecuta no está en el programa, sino dentro del S.O.
● El sistema operativo y los programas de usuario se ejecutan en niveles diferentes desde el punto de vista del CPU
● La transición de un nivel a otro consume ciclos de CPU: es mucho mas lenta una llamada al sistema que una llamada a un procedimiento dentro del mismo programa
Hilos y Procesos
Estados de los procesos
● Ejecutándose. El proceso está usando la CPU
● Listo. No está en ejecución pero no hay nada que lo impida. El proceso está esperando su turno para usar la CPU
● Bloqueado. No está en ejecución. No puede ejecutarse mientras no ocurra cierto evento externo
Posibles transiciones
1. Un proceso se bloquea para aceptar entrada de datos
• El planificador selecciona otro proceso para ejecutarlo
1. El planificador selecciona este proceso para ejecutarlo
• Hay datos disponibles. El proceso se desbloquea
Hilos y Procesos
El planificador (scheduler)● Es la parte del núcleo que maneja las transiciones
de estado de los procesos● Planificación expropiativa (preemtive). Cuando el
reloj del sistema genera una interrupción, el planficador es invocado para que determine cual proceso se ejecutará a continuación
● Planificación no expropiativa (non preemtive). Los procesos invocan al planificador
Hilos y Procesos
Algoritimos de planificación● Round robin● Planificación por prioridad● Combinación de prioridad y round robin● Otros
Hilos y Procesos
Hilos
● Hilos de ejecución. Procesos ligeros
● Subprocesos de un proceso
● La memoria y los recursos son asignados a los procesos
● Todos los hilos de un proceso comparten la memoria y los recursos asignados a dicho proceso
● Cada hilo tiene un contexto diferente
● Puede decirse que el recurso CPU no es compartido
● Cada hilo tiene una pila diferente
Hilos y Procesos
● Hilos
Hilos y Procesos
Tipos de hilos
● Hilos manejados por el kernel
● Hilos manejados a nivel del usuario (green threads)
Hilos manejados por el kernel
● El sistema operativo conoce la existencia de los hilos.
● El planificador no selecciona procesos para ser ejecutados sino hilos.
● El hilo seleccionado puede pertenecer al mismo proceso o a un proceso diferente
Hilos y Procesos
Hilos manejados a nivel del usuario
● El S.O. no conoce la existencia de los hilos
● Existe un único hilo por proceso
● Hay un paquete de hilos que corre en el espacio del usuario
– Consiste de una biblioteca de funciones para● Crear y destruir hilos ● Planificación de los hilos
Hilos y Procesos
Hilos del kernel Hilos de usuarioCambio de contexto Lento Rápido
Bloqueos
Planificación Expropiativa No expropiativa
Al bloquearse un hilo el proceso no tiene que bloquearse
Al bloquearse un hilo el proceso debe bloquearse
Hilos y Procesos
Memoria compartida● Varios procesos pueden acceder a bloques de
memoria compartida utilizando servicios del sistema
● Los hilos de un proceso pueden acceder a datos comunes
Hilos y Procesos
● Cuando varios procesos tratan de acceder al mismo tiempo a los datos se presentan problemas de acceso simultáno
● Ejemplo
¿Que pasa si dos procesos tratan de acceder al un arreglo simultáneamente?
●Sección crítica del programa●Exclusión mutua●Inhabilitación de interrupciones●Alternancia estricta●Espera ocupada●Sleep y Wakeup
Hilos y Procesos
Alternancia estricta
/* Proceso A */
while(TRUE) {
while (turno != 0);
region_critica();
turno = 1;
region_no_critica();
}
/* Proceso B */
while(TRUE) {
while (turno != 1);
region_critica();
turno = 0;
region_no_critica();
}
Hilos y Procesos
El problema del productor y el consumidor
● Se tiene un buffer que dos procesos (el productor y el consumidor comparten)
● El productor genera datos y los coloca en el buffer
● El consumidor saca datos del buffer y los usa
● Hay una variable que indica la cantidad de elementos que hay en el buffer
Hilos y Procesos
#define N 100
int cuenta = 0;
void productor() {
while(TRUE) {
producir_item();
if (cuenta == N) sleep();
agregar_item();
cuenta = cuenta + 1;
if (cuenta == 1) wakeup
(consumidor);
}
}
void consumidor() {
while(TRUE) {
if (cuenta==0)sleep();
sacar_item();
cuenta = cuenta - 1;
if (cuenta==N-1)
wakeup(productor);
consumir_item();
}
}
Solución usando sleep y wakeup
Hilos y Procesos
Se puede presentar el siguiente problema:
● El buffer está vacío. El consumidor se dispone a sacar un item
● Lee la variable cuenta (valor=0). El planificador decide ejecutar al productor
● El productor agrega un ítem, incrementa el contador, y como es igual a 1 llama a wakeup para despertar al consumidor (que debe estar dormido)
● La llamada se pierde porque el consumidor no está dormido
● El productor se despierta y al ver que cuenta es 0 se duerme
● Tarde o temprano el productor llenará el buffer y se dormirá también
● Los dos procesos están dormidos y no hay nadie que los despierte
● La solución es usar semáforos
Hilos y Procesos
Semáforos
● Un semáforo es una variable especial cuyo valor se modifica únicamente mediante dos operaciones: up y down
● Cuando se invoca la operación up el valor de la variable se incrementa
● Cuando se invoca la operación down se resta 1 a la variable, a menos que el valor sea 0, en cuyo caso el proceso se bloquea (sleep)
● Si al invocar la operación up hay procesos bloqueados en el semáforo se desbloquea el primer proceso. El valor de la variable no se incrementa
● Después de un up con un semáforo que tiene procesos esperando, el semáforo seguirá estando en 0, pero habrá un proceso menos esperando
● Para que los semáforos sean efectivos, las operaciones up y down deben ser atómicas. Esto puede hacerse mediante diversos mecanismos. Ej. deshabilitar interrupciones.
Hilos y Procesos
#define N 100
typedef int semaphore;
semaphore mutex=1;
semaphore empty=N;
semaphore full=0;
void productor() {
int item;
while(TRUE) {
producir_item(&item);
down(&empty);
down(&mutex);
agregar_item(item);
up(&mutex);
up(&full);
}
}
void consumidor() {
int item;
while(TRUE) {
down(&full);
down(&mutex);
sacar_item(&item);
up(&mutex);
up(&empty);
consumir_item(item);
}
}
Solución usando usando semáforos
Hilos y Procesos
Monitores
● El uso de semáforos es propenso a errores
● Los monitores son primitivas de sincronización de más alto nivel
● Monitor: una colección de procedimientos, variables y estructuras de datos que se agrupan en un tipo especial de módulo
● Los procesos pueden invocar los procedimientos del monitor pero no acceder a las estructuras de dato internas
● Solo un proceso o hilo puede invocar un método del monitor a la vez
● Desventaja. Los monitores tienen que estar implementados a nivel del lenguaje. No pueden implementarse mediante bibliotecas
Hilos y Procesos
Monitor example
integer count;
condition full, empty;
procedure enter;
begin
if count = N then wait(full);
enter_item;
count = count + 1;
if count = 1 then signal(empty)
end;
procedure remove;
begin
if count = 0 then wait(empty);
remove_item;
count = count - 1;
if count = N - 1 then signal(full)
end;
end monitor;
Hilos y Procesos
procedure producer;
begin
while true do begin
produce_item;
ProducerConsumer.enter
end
end;
procedure consumer;
begin
while true do begin
produce_item;
ProducerConsumer.remove
end
end;
Hilos y Procesos
Hilos en Java● Java permite la creación de aplicaciones
multihilo.● La especificación no determina el tipo de hilos
(hilos del nucleo o hilos de usuario). Ambos son posibles
● Utiliza monitores para la sincronización cuando hay posibilidades de acceso simultáneo a variables
Hilos y Procesos
● La clase Thread es un manejador de hilos. Permite– Crear hilos– Destruir hilos
● Se pueden crear hilos de dos maneras– Declarando una subclase de Thread– Declarando una clase que implemente la interfaz Runnable
Hilos y Procesos● Declarar una subclase de Thread
public class SimpleThread extends Thread {
public SimpleThread(String str) {
super(str);
}
public void run() {
for (int i = 0; i < 10; i++) {
System.out.println(i + " " + getName());
try {
sleep((long)(Math.random() * 1000));
} catch (InterruptedException e) {}
}
System.out.println("DONE! " + getName());
}
}
Hilos y Procesos● Declarar una subclase de Thread
public class TwoThreadsDemo {
public static void main (String[] args) {
Thread t1 = new SimpleThread("Jamaica");
Thread t2 = new SimpleThread("Fiji");
t1.start();
t2.start();
}
}
Hilos y Procesos● Declarar una clase que implementa la interfaz Runnable
public class MyClass extends MySuper implements Runnable {
public MyClass () {
}
public void run() {
for (int i = 0; i < 10; i++) {
System.out.println(i + " " + getName());
try {
sleep((long)(Math.random() * 1000));
} catch (InterruptedException e) {}
}
System.out.println("DONE! " + getName());
}
}
Hilos y Procesos● Declarar una clase que implementa la interfaz Runnable
public class TwoThreadsDemo {
public static void main (String[] args) {
MyClass m1 = new MyClass();
MyClass m2 = new MyClass();
Thread t1 = new Thread(m1, "Hilo 1");
Thread t2 = new Thread(m2, "Hilo 2");
t1.start();
new Thread(m1, "Hilo 3");
}
}
Hilos y Procesos
● Cada programa tiene por lo menos un hilo
● Constructores
Thread()
Thread(Runnable target)
Thread(Runnable target, String name)
Thread(String name)
Thread(ThreadGroup group, Runnable target)
Thread(ThreadGroup group, Runnable target, String name)
Thread(ThreadGroup group, String name)
Hilos y Procesos
● Ciclo de vida de los hilos en Java● Los hilos se crean pasando el mensaje start() a
un objeto de tipo Thread● Los hilos pueden estar en ejecución, listos o
bloqueados● Un hilo se puede bloquear al hacer entrada/salida ● También ejecutando el método sleep de la clase
Thread● Un hilo muere cuando termina el método run
Hilos y Procesos
Ejemplos
● Ejecutar para siempre
void run() { while (true) { ... } }● Variable de control
boolean continuar=true; void finalizar { continuar = false; } void run() { while (continuar) { ... } }
Hilos y Procesos
Sincronización en Java● La palabra syncronized se puede usar para
definir métodos que sean “thread safe“.● Sólo un hilo a la vez puede invocar un método
que sea syncronized● Las variables privadas del objeto no pueden ser
modificadas simultáneamente● Los métodos wait y notify, definidos en la clase
object permiten la sincronización
Hilos y Procesos● Problema del productor y el consumidor en Java
public class CubbyHole { private int contents; private boolean available = false; public synchronized int get() { while (available == false) { try { wait(); } catch (InterruptedException e) { } } available = false; notifyAll(); return contents; } public synchronized void put(int value) { while (available == true) { try { wait(); } catch (InterruptedException e) { } } contents = value; available = true; notifyAll(); }}
Hilos y Procesos● Problema del productor y el consumidor en Java
public class Producer extends Thread {
private CubbyHole cubbyhole;
private int number;
public Producer(CubbyHole c, int number) {
cubbyhole = c;
this.number = number;
}
public void run() {
for (int i = 0; i < 10; i++) {
cubbyhole.put(i);
try {
sleep((int)(Math.random() * 100));
} catch (InterruptedException e) { }
}
}
}
Hilos y Procesos● Problema del productor y el consumidor en Java
public class Consumer extends Thread {
private CubbyHole cubbyhole;
private int number;
public Consumer(CubbyHole c, int number) {
cubbyhole = c;
this.number = number;
}
public void run() {
int value = 0;
for (int i = 0; i < 10; i++) {
value = cubbyhole.get();
}
}
}
Hilos y Procesos● Problema del productor y el consumidor en Java
public class ProducerConsumerTest {
public static void main(String[] args) {
CubbyHole c = new CubbyHole();
Producer p1 = new Producer(c, 1);
Consumer c1 = new Consumer(c, 1);
p1.start();
c1.start();
}
}
Hilos y Procesos
Prioridades
● La máquina virtual no especifica el algoritmo de planificación
● Cada hilo tiene una prioridad entre Thread.MAX_PRIORITY (10) y Thread.MIN_PRIORITY (1)
● Inicialmente cada hilo tiene la misma prioridad que el hilo desde donde fue creado. El hilo inicial tiene prioriad 5
● getPriority(). Devuelve la prioridad del hilo
● setPriority(int p). Permite modificar la prioridad del hilo
Hilos y Procesos
Prioridades recomendadas por tipo de tarea● 10. Manejo de crisis● 7-9. Tareas interactivas, manejadas por eventos● 4-6. Tareas intensas en entrada/salida● 2-3. Procesamiento en background● 1. Corre sólo cuando nadie más puede correr
Hilos y Procesos
Métodos de control
● thead.interrupt(). Coloca el estatus de interrupción en true. Si el hilo está dentro de wait(), sleep() o join() se lanza la excepción InterruptedException
● thread.isInterrupted(). Devuelve true si el hilo ha sido interrumpido y no se a ejecutado Thread.Interrupted().
● Thread.interrupted() (estático). Devuelve true si el hilo actual ha sido interrumpido y coloca el estatus en false.
● thread.join(). Bloquea el hilo que hace la llamada hasta que termine el hilo thread.
Hilos y Procesos
Métodos estáticos de la clase Thread● Thread.currentThread()● Thread.interrupted()● Thread.sleep()● Thread.yield()
Hilos y Procesos
● Cada hilo pertenencen a un grupo● Por defecto el hilo pertenece al mismo grupo que
el hilo que lo creó● Son poco utilizados● Es preferible utilizar clases de colección tales
como Vector, etc.
Hilos y Procesos● Implementación de semáforos en Java
class Semaphore { private int value; Semaphore (int initial) { value_ = initial; } synchronized public void up() { ++value; notify(); } synchronized public void down() { while (value == 0) { try { wait(); } catch (InterruptedException e){} } --value_; }}
Hilos y Procesos● Mutex
class Mutex {
private Semaphore s = new Semaphore(1);
public void aquire() { s.down(); }
public void release() { s.up(); }}
Hilos y Procesos● Otra implementación de Mutex
public class Mutex implements Semaphore {
private Thread owner = null; private int lockCount = 0; public boolean acquire(long timeout) throws InterruptedException, TimedOut { if (timeout == 0) { return acquireWithoutBlocking(); } else if (timeout == FOREVER) { while (! acquireWithoutBlocking()) this.wait(FOREVER); } else { long expiration = System.currentTimeMillis() + timeout; while (! acquireWithoutBlocking()) { long timeRemaining = expiration - System.currentTimeMillis(); if (timeRemaining <= 0) throw new TimedOut("Timed out waiting for Mutex"); this.wait(timeRemaining); } } return true;}
Hilos y Procesos● Otra implementación de Mutexpublic void release() { if (owner != Thread.currentThread()) { throw new Ownership(); } if (--lockCount <= 0) { owner = null; notify(); }}public void acquire() throws InterruptedException { acquire(FOREVER); }private boolean acquireWithoutBlocking() { Thread current = Thread.currentThread();
if (owner == null) { owner = current; lockCount = 1; } else if (owner == current) { ++lockCount; } return owner == current;}
}
Hilos y Procesos● Porqué se requiere colocar wait() dentro de un ciclo while
public class SimpleQueue { private static final int QUEUE_SIZE = 10; private Object[] queue = new Object[QUEUE_SIZE]; private int head = 0; private int tail = 0; public synchronized void insert(Object item) { tail = ++tail % QUEUE_SIZE; queue[tail] = item; this.notify(); } public synchronized Object remove(Object item) { try { while (head == tail) { this.wait(); } } catch (InterruptedException e) { return null; } head = ++head % QUEUE_SIZE; Object removedObject = queue[head]; queue[head] = null; return removedObject; }}
Hilos y Procesos
● Cuando un hilo A entra a un método synchronized adquiere un semáforo mutex para excluir a otros hilos
this.mutex.acquire();● La llamada a wait() libera el semáforo mutex para permitir que otros
hilos puedan entrar al método
this.mutex.release();this.condition.wait_for_true();this.mutex.acquire();
● Si un hilo B invoca notify(), condition es colocado en true
● El hilo A avanza a mutex.acquire() y se bloquea porque el hilo B todavía tiene el mutex
● Cuando el hilo B sale del método synchronized libera el mutex. El hilo A adquiere el mutex y la llamada a wait() retorna
Hilos y Procesos
Problema 1. notifyAll().
● Si varios hilos llama a remove y la cola está vacía todos se bloquearan en condition.wait_for_true().
● Si el método insert usa notify all, todos los hilos se desbloquerán simultáneamente todos tratarán de adquirir el mutex, pero solo uno ganará
● El ganador saca un elemento de la cola (la cual queda vaciá) y sale de remove, liberando el mutex
● Los otros hilos se desbloquearán uno tras otro y todos sacarán elementos de una cola vacía
Hilos y Procesos
Problema no. 2. notify()
● Si se usa notify() solo un hilo saldrá del bloqueo en condition.wait_for_true. El problema 1 no se presenta. Pero se puede presentar este:
● Un hilo A llama a remove() se bloquea en wait()
● Un hilo B llama a insert y por lo tanto a notify, liberando el mutex. El hilo A avanza hasta aquí
this.mutex.release();this.condition.wait_for_true();this.mutex.acquire(); // A se bloquea aquí
● A es expropiado. El método insert no ha terminado por lo que B tiene el mutex
● Un hilo C llama a remove() y se bloquea al tratar de adquirir el mutex
● A se ejecuta (porque B y C) están bloqueados y libera el mutex
Hilos y Procesos
Problema no. 2. notify() (cont.)
● No hay forma de determinar quién obtiene el mutex (A o C)
● Si el hilo C obtiene el mutex sacará de la cola el objeto que B insertó (no se llama a wait() porque la cola no está vacía
● Ahora el hilo A se despierta. Si existe el wait() está dentro de ciclo while se bloquerá en wait porque la cola está vacía (porque C sacó el objeto que A insertó)
● Si ho hay un ciclo while sino una instrucción if, A continuará y sacará un objeto de una cola vacía
● El problema se presenta porque la operación wait() no tiene que ser atómica.