Sistemas Operativos
72.11
Inter process communication (IPC)
IPC
● Proceso independiente vs cooperativo
● Motivación
○ Compartir información
○ Acelerar computación
○ Modularidad
○ Conveniencia
● 2 modelos fundamentales
○ Memoria compartida
○ Pasaje de mensajes
Silberschatz, Operating Systems Concepts 9e, 2012 Wiley
IPC
IPC
Memoria compartida
● Procesos acuerdan compartir memoria física, ¿con quién hay que hablar?
● Generalmente no requiere de syscalls para acceder a la información
● La organización de la información y sincronización es determinada por los procesos
● Problemas de cache coherency al aumentar los núcleos
IPC
Pasaje de mensajes
● Más simple en sistemas distribuidos
● Útil para pequeñas cantidades de información
● Intervención del kernel
● Tamaño de mensaje fijo vs variable
● Operaciones:
○ send(message), receive(message)
● Es necesario un canal de comunicación (memoria, bus, red)
IPC
Pasaje de mensajes: identidad
● Los procesos deben tener un mecanismo para referirse entre sí:
○ Comunicación directa - simétrica
■ send(P, message) , receive(Q, message) (P y Q procesos)
■ Cada proceso debe conocer la identidad del otro proceso
■ El canal de comunicación se hace explícito entre un par de procesos
■ El canal de comunicación asocia exactamente a 2 procesos
■ 2 procesos pueden tener un único canal de comunicación
○ Comunicación directa - asimétrica
■ send(P, message) , receive(id, message)
La identidad de un proceso naturalmente cambia
IPC
Pasaje de mensajes: identidad
○ Comunicación indirecta
■ Los mensajes se envían a puertos o casillas de correo
■ send(A, message) , receive(A, message) (A casilla de correo)
■ El canal de comunicación se establece entre procesos que comparten una casilla
■ El canal de comunicación puede asociar más de 2 procesos
■ 2 procesos pueden tener más de 1 canal de comunicación
Ejemplo: P1 envía mensaje a la casilla A y P2 y P3 reciben de la casilla A
P1: send(A, message)
P2: receive(A, message) / P3: receive(A, message)
¿Quién recibe el mensaje?
● Restringir un canal a 2 procesos
● Restringir cuántos procesos pueden recibir
● Elección arbitraria y notificación
● Pertenencia de la casilla a un proceso específico
IPC
Pasaje de mensajes: sincronización
send y receive pueden ser bloqueantes o no bloqueantes
● send bloqueante: hasta que llega a la casilla / proceso
● send no bloqueante: resume inmediatamente
● receive bloqueante: hasta que hay mensaje disponible
● receive no bloqueante: recibe mensaje o null
IPC
Pasaje de mensajes: buffering
Los mensajes residen en en un buffer
● Capacidad 0: no buffering -> send debe bloquear
● Capacidad acotada: send debe bloquear si se agota el espacio
● Capacidad no acotada: send no bloquea
IPC
Files (memoria compartida)
● Ejemplos
vim main.c [edit]
gcc -Wall main.c
ls > files.txt
grep “*.c” files.txt > sources.txt
sort sources.txt
IPC
Pipes (pasaje de mensajes)
● Permite que 2 procesos se comuniquen bajo el esquema productor-consumidor
● Uno de los primeros mecanismos de IPC en UNIX
● Buffering: acotado
● Sincronización: send bloquea al llenarse el pipe, receive bloquea hasta que haya algo
● Identidad: …
Doeppner, Operating Systems in Depth, 2011 Wiley
IPC
Pipes: consideraciones de implementación
● Comunicación unidireccional o bidireccional
● Si es bidireccional, ¿es half duplex o full duplex?
● ¿Debe existir relación padre-hijo?
● ¿Los procesos deben estar en la misma computadora?
https://www.totalphase.com/blog/2022/10/difference-between-half-duplex-vs-full-duplex/
IPC
Pipes: anónimos / ordinarios
● Permite comunicar 2 procesos emparentados
● UNIX: unidireccionales
● UNIX: se crean con pipe(2) y se heredan al hacer fork(2) y execve(2)
● Identidad: … -> File descriptors
● UNIX: Consultar pipe(7)
IPC
Pipes: named pipes
● Permite comunicar 2 procesos arbitrarios
● UNIX: FIFOs
● UNIX: unidireccionales
● UNIX: se crean con mkfifo(3) y se abren con open(2)
● Identidad: … -> Path en el file system
● UNIX: Consultar fifo(7)
IPC
Files vs pipes
ls > files.txt
grep "*.c" files.txt > sources.txt
ls | grep "*.c" | sort
sort sources.txt
rm files.txt sources.txt
Ventajas de los pipes
● Se eliminan automáticamente (anónimos)
● Cantidad arbitraria de información
● Ejecución paralela
● Sincronización implícita
IPC
Shared memory (memoria compartida)
● Permite que procesos arbitrarios compartan memoria
● UNIX: smh_open(3) ftruncate(2) mmap(2)
● Intervención del kernel para crearla?
● Intervención del kernel para usarla (R/W)?
● UNIX: Consultar smh_overview(7)
// ...
char buf[1024];
char *buf = (char *) malloc(1024);
char *buf = createSHM(..., 1024, ...);
sprintf(p, "Hola mundo\n");
// ...
https://www.oreilly.com/library/view/mastering-embedded-linux/9781787283282/7732a483-9260-4511-a063-896f66d37bb4.xhtml
IPC
Shared memory: punteros
● Queremos estructurar la información dentro de la shared memory, por ejemplo, una lista:
IPC
Shared memory: punteros
0x1400
0x900
0x1000 1
0x500
0x500 + offset 0x900 + offset
IPC
Sockets (pasaje de mensajes)
● Permite comunicar procesos a través de una red
● Bidireccional - full duplex
● UNIX: socket(2), listen(2), accept(2), bind(2), send(2), recv(2)
● Un socket se identifica con una IP y un puerto
● Generalmente aplicación cliente - servidor
● UNIX: Consultar socket(7)
IPC
IPC
IPC
FIFOs vs Unix Domain Sockets
● Un socket es bidireccional
● Pueden ser usados por muchos procesos a la vez. Aceptar muchas conecciones en el mismo
socket y atender a muchos clientes simultáneamente
● UNIX: consultar unix(7)
● Son necesarios 2 FIFOs para comunicación bidireccional
● Por cada cliente necesitamos 2 FIFOs
● No hay forma de leer o escribir de forma selectiva
IPC
Signals
●
Race condition
● 2 instancias de home banking intentando debitar
//...
int saldo_en_cuenta;
void debitar(int *saldo, int debito){
if (*saldo >= debito)
*saldo -= debito;
}
//...
Race condition
Situación ideal
int saldo_en_cuenta = 100;
Home banking 1 Home banking 2
debitar(&saldo_en_cuenta, 100); debitar(&saldo_en_cuenta, 100);
Context switch
if (*saldo >= debito) // true
*saldo -= debito;
if (*saldo >= debito) // false
*saldo -= debito;
int saldo_en_cuenta = 0;
Race condition
Situación patológica
int saldo_en_cuenta = 100;
Home banking 1 Home banking 2
debitar(&saldo_en_cuenta, 100); debitar(&saldo_en_cuenta, 100);
Context switch
if (*saldo >= debito) // true
if (*saldo >= debito) // true
*saldo -= debito;
*saldo -= debito;
int saldo_en_cuenta = -100;
Race condition
Definición
Una situación en las que dos o más procesos están leyendo o escribiendo datos
compartidos y el resultado final depende de quién corre en cada momento
Race condition
Solución: exclusión mutua
int saldo_en_cuenta = 100;
Home banking 1 Home banking 2
debitar(&saldo_en_cuenta, 100); debitar(&saldo_en_cuenta, 100);
// Pido acceso exclusivo - OK
Context switch
if (*saldo >= debito) // true
// Pido acceso exclusivo - BLOCK …
*saldo -= debito; // Blocked …
// Libero acceso exclusivo // Blocked …
if (*saldo >= debito) // true
*saldo -= debito;
// Libero acceso exclusivo
int saldo_en_cuenta = 0;
Región crítica
Definición
Parte del programa que accede a la memoria compartida
//...
int saldo_en_cuenta;
void debitar(int *saldo, int debito){
if (*saldo >= debito)
Región crítica
*saldo -= debito;
}
//...
Región crítica
Race condition
Otro ejemplo
● sleep bloquea al proceso
hasta que alguien ejecuta
wakeup
● wakeup toma como
parámetro el id del proceso a
despertar
¿syscalls?
● Signal lost
● Wakeup waiting bit
Mecanismos de sincronización
Semáforos
● El Wakeup waiting bit se plantea (Dijkstra - 1965) como un entero representando la cantidad de
wakeups disponibles [0-n], el cual llamaremos semáforo
● Se proponen 2 operaciones
○ down (sleep): atómicamente decrementa el semáforo o bloquea al caller si ya es 0
○ up (wakeup): atómicamente incrementa el semáforo y desbloquea a algún bloqueado si
existe
Mecanismos de sincronización
Semáforos
● 2 instancias de home banking intentando debitar… pero esta vez con semáforos
//...
int saldo_en_cuenta;
semaphore mutex = 1;
void debitar(int *saldo, int debito){
down(mutex);
if (*saldo >= debito)
*saldo -= debito;
up(mutex);
}
//...
Mecanismos de
sincronización
Semáforos
● Semántica del semáforo
● Inicialización del semáforo
● Contar vs acceso exclusivo
Región crítica
int main(){ int main(){
// code down(mutex);
// code // code
// code // code
// code // code
// code // code
down(mutex); // code
// code that access shared data // code that access shared data
// code that access shared data // code that access shared data
up(mutex); // code
// code // code
// code // code
// code // code
// code up(mutex);
} }
Problemas clásicos de IPC
Filósofos comensales
Deadlock
Definición
Un conjunto de procesos está bloqueado (en estado de deadlock) si cada proceso del conjunto está
esperando un evento que solo puede causar otro proceso del conjunto.
Deadlock
Ejemplos
//... //...
//... semaphore mutexA = 1; semaphore mutexA = 1;
semaphore mutex = 1; semaphore mutexB = 1; semaphore mutexB = 1;
void foo(){ void P1(){ void P2(){
down(mutex); down(mutexA); down(mutexB);
down(mutex); down(mutexB); down(mutexA);
} } }
//... //... //...
Problemas clásicos de
IPC
Filósofos comensales
Problemas clásicos de
IPC
Filósofos comensales
Problemas clásicos de
IPC
Lectores y escritores
Ejercicio 1
Asumiendo que dispone de semáforos en su sistema:
init(sem_t s, int value);
down(sem_t s);
up(sem_t s);
Implemente su propia librería de semáforos haciendo uso de la ya disponible:
my_init(int s, int value);
my_down(int s);
my_up(int s);
● Notar que por simplicidad esta nueva librería puede tomar un int en lugar de sem_t.
● El int s puede ser una variable global.
● Puede recurrir a espera activa (busy waiting) para simular el bloqueo usual de un proceso al ejecutar down.
Ejercicio 2
La solución presentada al problema de los filósofos está libre de deadlocks, pero no está libre de (starvation) inanición.
“no estar libre de inanición” significa que existe al menos una traza infinita de ejecución en la que un proceso no progresa. Casualmente
los procesos modelan filósofos comiendo, pero eso es solo una coincidencia.
Analice la solución en busca de esta traza. Es recomendable definir a priori qué filósofo vamos a intentar “matar de hambre”, por
ejemplo, el filósofo 0. Luego, tomar decisiones de scheduling (qué proceso ejecutará en cada momento) apuntando a la inanición del
filósofo elegido. Si bien la traza debe ser infinita, la cantidad de estados no isomorfos que contiene esta traza es finita, lo que implica
que la traza será un ciclo infinito a través de estos estados.
Proponga una solución al problema
Ejercicio 3
Un pequeño local comercial del centro tiene un único baño para sus empleados, los cuales son de ambos sexos. El dueño desea que su
uso sea exclusivo para un único sexo y para ello instaló una señal con 3 posiciones en la puerta:
LIBRE, MUJERES, HOMBRES
Ahora necesita capacitar al personal para que use el baño de forma adecuada. Para esto solicita instrucciones precisas (código) para
ambos sexos, que garanticen que en ningún momento habrá personas de distintos sexos dentro del baño.
Ejercicio 4
La siguiente función incrementa el número almacenado en el Ahora ejecute el siguiente script que llama a la función inc 4
archivo file 100 veces veces y consulte el valor final del archivo.
inc100() { echo 0 > file
for i in {1..100}; do for i in {1..4}; do
n=$(tail -n 1 file); inc100
n=$(($n + 1)); done
sed -i "s/.*/$n/g" file;
done & ¿Qué observa?
} Si repite el último ejercicio, ¿el resultado es siempre el mismo?
¿Cómo se conoce a esta situación?
El siguiente script bash guarda el número 0 en el archivo file y
luego ejecuta inc100
echo 0 > file
inc100
Ejecute este script (puede copiar y pegar en la terminal) y
consulte el valor final del archivo, por ejemplo con cat.
Ejercicio 5
Dos procesos A y B ejecutan 2 instrucciones cada uno
A: a1;a2
B: a1;a2
Sincronice ambos procesos utilizando semáforos de manera tal que a1 ocurra antes que b2 y que b1 ocurra antes que a2.
Ejercicio 6
El problema de los lectores y escritores como está presentado favorece a los lectores, ya que pueden seguir accediendo a la base de
datos mientras haya uno presente. Los escritores no tienen otra opción más que esperar a que salgan todos los lectores para poder
entrar. Modifique la solución de manera que un escritor solo tenga que esperar a los lectores presentes al momento de su llegada, es
decir, los lectores que lleguen luego del escritor deberán esperar a que el escritor finalice.
