UNIVERSIDAD NACIONAL DE CAJAMARCA

Escuela Académico Profesional de Ingeniería de Sistemas

SISTEMAS OPERATIVOS
PROBLEMAS DE COMUNICACIÓN ENTRE
PROCESOS

DOCENTE: Ing. Sandra Rodríguez Ávila

Cajamarca, 29 de octubre de 2014

 SISTEMAS OPERATIVOS - EAPIS

OTROS PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS

RESUMEN
La comunicación entre procesos (IPC, del inglés Inter-Process Communication) es una
función básica de los sistemas operativos. Los procesos pueden comunicarse entre sí a través
de compartir espacios de memoria, ya sean variables compartidas o buffers, o a través de las
herramientas provistas por las rutinas de IPC. La IPC provee un mecanismo que permite a los
procesos comunicarse y sincronizarse entre sí, normalmente a través de un sistema de bajo nivel
de paso de mensajes que ofrece la red subyacente.
La comunicación se establece siguiendo una serie de reglas (protocolos de comunicación). Los
protocolos desarrollados para internet son los mayormente usados: IP (capa de red), protocolo
de control de transmisión (capa de transporte) y protocolo de transferencia de
archivos , protocolo de transferencia de hipertexto (capa de aplicación).
Los procesos pueden estar ejecutándose en una o más computadoras conectadas a una red. Las
técnicas de IPC están divididas dentro de métodos para: paso de mensajes, sincronización,
memoria compartida y llamadas de procedimientos remotos (RPC). El método de IPC usado
puede variar dependiendo del ancho de banda y latencia (el tiempo desde el pedido de
información y el comienzo del envío de la misma) de la comunicación entre procesos, y del tipo
de datos que están siendo comunicados.

PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS - Pág. 1

 SISTEMAS OPERATIVOS - EAPIS

1. EL PROBLEMA DE LOS FILÓSOFOS COMENSALES

En 1965 Dijkstra planteó y resolvió un problema de sincronización llamado el

problema de la cena de los filósofos, que se puede enunciar como sigue. Cinco
filósofos se sientan a la mesa, cada uno con un plato de espagueti. El espagueti es tan
escurridizo que un filósofo necesita dos tenedores para comerlo. Entre cada dos platos
hay un tenedor. [1]

Imaginemos cinco filósofos que se pasan la vida pensando y comiendo. Los

filósofos comparten una sola mesa circular rodeada por cinco sillas cada una
de 1as cuales pertenece a un filósofo.
En el centro de la mesa hay un platón
de arroz, y la mesa está puesta con
cinco palillos chinos individuales.
Cuando un filósofo piensa, no
interactúa con sus colegas. De vez en
cuando, un filósofo siente hambre y
trata de tomar los dos palillos chinos
que le quedan más cerca (los palillos
que esta entre él y sus vecinos
izquierdo y derecho). Un filósofo
sólo puede coger un palillo a la vez
y, obviamente, no puede tomar un
palillo que ya está en la mano de uno
de sus vecinos. Cuando un filósofo
hambriento tiene sus dos palillos al mismo tiempo, come sin soltar sus
palillos; cuando termina de comer, deja sobre la mesa ambos palillos y
comienza a pensar otra vez. [3]

El problema de los filósofos comensales se considera un problema de

sincronización clásico, no por su importancia práctica, ni porque a los
computólogos1 les parezcan antipáticos los filósofos, sino porque es un
ejemplo de una clase amplia de problemas de control de concurrencia. Se
trata de una representación sencilla de la necesidad de asignar varios recursos
entre varios procesos sin que haya bloqueos mutuos ni inanición. [4]

1
Computólogo es aquella persona que abarca el estudio de las bases teóricas de la información y la computación,
así como su aplicación en sistemas computacionales

PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS - Pág. 2

 SISTEMAS OPERATIVOS - EAPIS

espera(mutex);
cuentalect := cuentalect + 1;
if cuentalect = 1then espera(escr);
señal(mutex);
…
se realiza la lectura
…
espera(mutex);
cuentalect := cuentalect - l;
if cuenta/ect = O then
señal(escr); señal(mutex);

Figura 2 Estructura de un proceso lector.

Una solución sencilla consiste en representar cada palillo chino con un

semáforo. Un filósofo trata de tomar un palillo ejecutando una operación
espera con ese semáforo, y suelta sus palillos ejecutando la operación señal
con los semáforos apropiados. Entonces, los datos compartidos son:

var palillo: array [0..4] of semáforo;

Donde todos los elementos de palillo tienen 1 como valor inicial. La

estructura del filósofo i se muestra en la siguiente figura (Ver figura 3)

repeat

espera(palillo[ i]);
espera(palillo[i+ 1 mod 5]);
…
Comer
…
señal (palillo[i]);
señal(palillo[i+ 1 mod 5]);
…
Pensar
…
until false;

Figura 3 Estructura del filósofo i.

Aunque esta solución garantiza que dos vecinos no estarán comiendo

simultáneamente, hay que rechazarla porque tiene la posibilidad de crear un
bloqueo mutuo. Supongamos que los cinco filósofos sienten hambre
simultáneamente, y cada uno toma su palillo izquierdo. En este momento
todos los elementos de palillo tendrán el valor 0. Cuando un filósofo intente
tomar su palillo derecho, sufrirá un retardo eterno. [5]

PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS - Pág. 3

 SISTEMAS OPERATIVOS - EAPIS

A continuación mencionamos varios posibles remedios al problema del

bloqueo mutuo.

 Permitir que cuando más cuatro filósofos se sienten simultáneamente a la

mesa.
 Sólo permitir que un filósofo tome sus palillos si ambos palillos están
disponibles (cabe señalar que los deberá tomar dentro de una sección
crítica).
 Usar una solución asimétrica; es decir, un filósofo impar toma primero
su palillo izquierdo y luego el derecho, mientras que un filósofo par toma
primero su palillo derecho y luego el izquierdo.

Por último, cualquier solución satisfactoria al problema de los filósofos

comensales deberá evitar la posibilidad de que uno de los filósofos muera de
hambre. Una solución libre de bloqueos mutuos no elimina necesariamente
la posibilidad de inanición2.

OTRAS POSIBLES SOLUCIONES

 Por turno cíclico

Se empieza por un filósofo, que si quiere puede comer y después pasa su turno al de la
derecha. Cada filósofo sólo puede comer en su turno. Problema: si el número de
filósofos es muy alto, uno puede morir de hambre antes de su turno.

 Varios turnos
Se establecen varios turnos. Para hacerlo más claro supongamos que cada filósofo que
puede comer (es su turno) tiene una ficha que después pasa a la derecha. Si por ejemplo
hay 7 comensales podemos poner 3 fichas en posiciones alternas (entre dos de las fichas
quedarían dos filósofos).
Se establecen turnos de tiempo fijo. Por ejemplo cada 5 minutos se pasan las fichas (y
los turnos) a la derecha.
En base al tiempo que suelen tardar los filósofos en comer y en volver a tener hambre,
el tiempo de turno establecido puede hacer que sea peor solución que la anterior. Si el
tiempo de turno se aproxima al tiempo medio que tarda un filósofo en comer esta
variante da muy buenos resultados. Si además el tiempo medio de comer es similar al
tiempo medio en volver a tener hambre la solución se aproxima al óptimo.

2
Inanición estado de extrema debilidad

PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS - Pág. 4

 SISTEMAS OPERATIVOS - EAPIS

 Colas de tenedores
Cuando un filósofo quiere comer se pone en la cola de los dos tenedores que necesita.
Cuando un tenedor está libre lo toma. Cuando toma los dos tenedores, come y deja libre
los tenedores.
Visto desde el otro lado, cada tenedor sólo puede tener dos filósofos en cola, siempre
los mismos.
Esto crea el problema comentado de que si todos quieren comer a la vez y todos
empiezan tomando el tenedor de su derecha se bloquea el sistema (deadlock).

 Resolución de conflictos en colas de tenedores

Cada vez que un filósofo tiene un tenedor espera un tiempo aleatorio para conseguir el
segundo tenedor. Si en ese tiempo no queda libre el segundo tenedor, suelta el que tiene
y vuelve a ponerse en cola para sus dos tenedores.
Si un filósofo A suelta un tenedor (porque ha comido o porque ha esperado demasiado
tiempo con el tenedor en la mano) pero todavía desea comer, vuelve a ponerse en cola
para ese tenedor. Si el filósofo adyacente B está ya en esa cola de tenedor (tiene hambre)
lo toma y si no vuelve a cogerlo A.
Es importante que el tiempo de espera sea aleatorio o se mantendrá el bloqueo del
sistema.

 El portero del comedor

Se indica a los filósofos que abandonen la mesa cuando no tengan hambre y que no
regresen a ella hasta que vuelvan a estar hambrientos (cada filósofo siempre se sienta
en la misma silla). La misión del portero es controlar el número de filósofos en la sala,
limitando su número a n-1, pues si hay n-1 comensales seguro que al menos uno puede
comer con los dos tenedores.

PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS - Pág. 5

 SISTEMAS OPERATIVOS - EAPIS

2. EL PROBLEMA DE LECTORES Y ESCRITORES

Un objeto de datos se va a compartir entre varios procesos concurrentes.
Algunos de esos procesos quizá sólo deseen leer el contenido del objeto
compartido, pero otros podrían querer actualizarlo. Es decir, leer y escribir.

repeat
espera(llenos);
espera(mutex);
…
quitar un elemento de buffer y ponerlo en sigc

señal(mutex);
señal(vacíos);
…
consumir el elemento que está en sigc

until false;

Figura 4 Estructura del proceso consumidor.

Distinguimos entre estos dos tipos de procesos llamando lectores a los que
sólo están interesados en leer, y escritores a los demás. Obviamente, si dos
lectores acceden al objeto de datos compartido simultáneamente, no pasará
nada malo. Sin embargo, si un escritor y algún otro proceso (sea lector o
escritor) acceden al objeto compartido simultáneamente, el resultado puede
ser un caos. [6]

Para asegurar que tales dificultades no se presenten, exigimos que los

escritores tengan acceso exclusivo al objeto compartido. Este problema de
sincronización se denomina problema de lectores y escritores. Desde que se
planteó originalmente, este problema se ha usado para probar casi todas las
primitivas de sincronización nuevas.

El problema de lectores y escritores tiene varias variaciones, en todas las

cuales intervienen prioridades. La más sencilla, denominada primer
problema de lectores y escritores, exige que no se mantenga esperando
ningún lector a menos que un escritor ya haya obtenido permiso para usar el
objeto compartido. En otras palabras, ningún lector deberá esperar que otros
lectores terminen simplemente porque un escritor está esperando. El segundo
problema de lectores y escritores requiere que, una vez que un escritor está
listo, realice su escritura lo antes posible. Dicho de otro modo, si un escritor
está esperando acceder al objeto, ningún lector nuevo puede comenzar a leer.
[7]

PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS - Pág. 6

 SISTEMAS OPERATIVOS - EAPIS

Es evidente que una solución a cualquiera de estos problemas puede dar lugar a
inanición. En el primer caso, los escritores podrían sufrir inanición; en el
segundo, los lectores serían las víctimas. Por esta razón, se han propuesto otras
variantes del problema. En esta sección presentaremos una solución al primer
problema de lectores y escritores. [8]
En la solución al primer problema de lectores y escritores, los procesos lectores
comparten las estructuras de datos siguientes:

var mutex, eser: semáforo;

cuentalect: integer;

Fig 5

 Los semáforos mutex y escr inician en 1;

 cuentalect inicia en 0.
 El semáforo escr es común a los procesos lectores y escritores.
El semáforo mutex sirve para asegurar la mutua exclusión cuando se
actualice la variable cuentalect, la cual lleva la cuenta de los procesos que
están leyendo actualmente el objeto. El semáforo escr funciona como
semáforo de mutua exclusión para los escritores, pero también lo usan el
primer o el último escritor que ingresa en, o egresa de, la sección crítica; no
lo utilizan los lectores que ingresan o egresan mientras otros lectores están
en sus secciones críticas. [9]

espera( eser);
…
se realiza la escritura
…
señal(escr);
Figura 6: Estructura de un proceso escritor

En la figura 6 se muestra el código para un proceso escritor; el de un lector está

en la figura 7.
Cabe señalar que, si un escritor está en la sección crítica y n lectores están
esperando, un lector se encola en eser, y n - 1 lectores se encolan en mutex.
Observe también que, cuando un escritor ejecuta señal(escr), podemos reanudar
la ejecución ya sea de los lectores que esperan o de un solo escritor que espera.
El planificador toma esta decisión. [10]

PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS - Pág. 7

 SISTEMAS OPERATIVOS - EAPIS

espera(mutex);
cuentalect := cuentalect + 1;
if cuentalect = 1then
espera(escr); señal(mutex);
…
se realiza la lectura
…
espera(mutex);
cuentalect := cuentalect - l;
if cuenta/ect = O then señal(escr);
señal(mutex);

Figura 7 Estructura de un proceso lector

3. PROBLEMA DEL PELUQUERO DORMIDO

Hay una peluquería, un peluquero,

una silla de peluquero, y n sillas para
que:

 Los clientes esperen su atención si

el peluquero está ocupado.
 Si no hay clientes, el peluquero
toma su silla y se sienta a dormir.
 El peluquero y los clientes
corresponden a procesos, y las
sillas a recursos

Al llegar un cliente tiene que:

 Despertar al peluquero para su

atención, o
 Tomar asiento para esperar, o bien
 Salir de la peluquería, si están todos los asientos ocupados

La solución implica el uso de semáforos y objetos de exclusión mutua para proteger

la sección crítica.

Un semáforo es una variable protegida (o tipo abstracto de datos) que constituye el

método clásico para restringir o permitir el acceso a recursos compartidos (por ejemplo,
un recurso de almacenamiento) en un entorno de multiprocesamiento. Fueron
inventados por Edsger Dijkstra y se usaron por primera vez en el sistema
operativo THEOS.

PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS - Pág. 8

 SISTEMAS OPERATIVOS - EAPIS

En electrónica y en programación concurrente, se conoce como condición de carrera al

error que se produce en programas o circuitos lógicos que no se han construido
adecuadamente para su ejecución simultánea con otros procesos.

IMPLEMENTACIÓN

 El próximo pseudo-código garantiza la sincronización entre el barbero y el cliente,

pero puede llevar a inanición del cliente. wait() y signal() son funciones provistas
por el semáforo.
 Se necesita:

Semáforo barberoListo = 0 // (Mutex, sólo 1 ó 0)

Semáforo sillasAccesibles = 1 // (Mutex) Cuando sea 1, el numero de
sillas libres puede aumentar o disminuir
Semáforo clientes = 0 // Número de clientes en la sala de espera
int sillasLibres = N // N es el número total de sillas

 Función barbero (Proceso/hilo-thread):

while(true) // Ciclo infinito

{
wait(clientes) // Tratar de atender a un cliente. Si no
hay, ir a dormir.
wait(sillasAccesibles) // (Ya está despierto) Tratar de modificar
el nro. de sillas disponibles.
sillasLibres += 1 // Queda disponible una silla en la sala.
signal(barberoListo) // El barbero está listo para cortar.
signal(sillasAccesibles) // Ya no se modificará el nro. de sillas
libres. Desbloquear.
// Aquí el barbero corta el pelo de un cliente (zona de código no
crítico).
}

PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS - Pág. 9

 SISTEMAS OPERATIVOS - EAPIS

 Función cliente (Proceso/hilo-thread)

wait(sillasAccesibles) // Trata de acceder a una silla.

if (sillasLibres > 0) // Si hay sillas disponibles.
{
sillasLibres =- 1 // Se sienta en una silla.
signal(clientes) // Avisar al barbero (el cual está
esperando) que hay un cliente.
signal(sillasAccesibles) // Ya no se necesita bloquear el nro de
sillas libres.
wait(barberoListo) // El cliente espera a que el barbero esté
listo para atenderlo.
// Se le corta el pelo al cliente.
}
else // Si no hay sillas libres.
{
signal(sillasAccesibles) // Desbloquear la modificación de sillas
libres para otros procesos/hebras.
// El cliente se va de la barbería
}

4. COMUNICACIÓN CLIENTE-SERVIDOR

En el modelo cliente-servidor, los procesos llamados servidores ofrecen una serie de

servicios a otros procesos que se denominan clientes (Figura 4.1). El proceso servidor
puede residir en la misma máquina que el cliente o en una distinta, en cuyo caso la
comunicación deberá realizarse a través de una red de interconexión. Muchas
aplicaciones y servicios de red, como el correo electrónico y la transferencia de
archivos, se basan en este modelo.

Figura 4.1. Comunicación cliente-servidor.

PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS - Pág. 10

 SISTEMAS OPERATIVOS - EAPIS

En el modelo cliente-servidor, los procesos llamados servidores ofrecen una serie de

servicios a otros procesos que se denominan clientes (Figura 4.2). El proceso servidor
puede residir en la misma máquina que el cliente o en una distinta, en cuyo caso la
comunicación deberá realizarse a través de una red de interconexión. Muchas
aplicaciones y servicios de red, como el correo electrónico y la transferencia de
archivos, se basan en este modelo.

CONCLUSIÓNES
 Los procesos son creados y destruidos por el sistema operativo, así como también este se
debe hacer cargo de la comunicación entre procesos.
 El mecanismo por el cual un proceso crea otro proceso se denomina bifurcación.
 El sistema operativo es el responsable de determinar las pautas de intercalado y asignación
de recursos a cada proceso.
 Si existe un esquema con diferentes niveles de prioridad de procesos es conveniente
mantener varias colas de procesos listos, una para cada nivel de prioridad, lo que ayuda a
determinar cuál es el proceso que más conviene ejecutar a continuación.

PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS - Pág. 11

 SISTEMAS OPERATIVOS - EAPIS

REFERENCIAS BIBLIOGRAFÍA Y WEBGRAFIA

 [1]http://lsi.vc.ehu.es/pablogn/docencia/manuales/SO/TemasSOuJaen/CONCURREN
CIA/4ProblemasClasicosdeComunicacionentreProcesos.htm

 [2] [3] [4] SILBERSCHATZ, ABRAHAM y BAER, PETER. Sistemas Operativos.

Addison Wesley Longman de México, S.A. de C.V. México, 1999. Pág. 175 - 177

 [5] Joaquín Aranda, Alamansa M, Antonia Canto Díaz, Jesús Manuel de la Cruz
García, Sebastián Dormido Bencomo, Carolina Mañoso Hierro. SISTEMAS
OPERATIVOS - TEORÍA Y PROBLEMAS. EDITORIAL SANZ Y
TORRES, S.L. Pinos Alta, 49 - 28029 Madrid. Pág. 101 - 167

 [6] [7] [8] SILBERSCHATZ, ABRAHAM y BAER, PETER. Sistemas Operativos.

Addison Wesley Longman de México, S.A. de C.V. México, 1999. Pag. 174

 [9] [10]TANENBAUM, ANDREW S. Sistemas operativos modernos.

Tercera edición. PEARSON EDUCACIÓN, México, 2009. Páginas de 117 a
167.

 http://prezi.com/buwzgisi-v3d/peluquero-dormilon/

 http://fermat.usach.cl/~fmoreno/SOE/07-vi25.04.2008-conceptos-procesos.pdf

 https://sopes1usac.wordpress.com/2012/11/05/5-2-problemas-clasicos-semaforos/

 http://lml.ls.fi.upm.es/pc/Anteriores/Examenes/1993sep/node4.html.

 http://es.wikipedia.org/wiki/Problema_de_la_cena_de_los_fil%C3%B3sofos

 http://www.arcos.inf.uc3m.es/~ssoo-va/ssoo-prac/libro/cap04.pdf

PROBLEMAS DE COMUNICACIÓN ENTRE PROCESOS - Pág. 12