cap1_Conceptos fundamentales_Pogramacion concurrente

Vista previa del material en texto

M.E Carmen Cerón G Programación Concurrente BUAP 1
CAPÍTULO 1. CONCEPTOS FUNDAMENTALES 
 
1.1 Introducción 
La idea de programación concurrente siempre estuvo asociada al mundo de los 
Sistemas Operativos (SSOO). No en vano, los primeros programas concurrentes 
fueron los propios Sistemas Operativos de multiprogramación en los que un solo 
procesador de gran capacidad debía repartir su tiempo entre muchos usuarios. 
Para cada usuario, la sensación era que el procesador estaba dedicado para él. 
Durante la década de los sesenta y setenta esto fue así. La programación de 
sistemas con capacidades de concurrencia se hacía a bajo nivel, en ensamblador, 
pues aparte de no disponer de lenguajes de alto nivel con capacidades de 
concurrencia, se primaba la supuesta eficiencia del código escrito directamente en 
ensamblador. La aparición en 1972 del lenguaje de alto nivel Concurrent Pascal 
[Brinch-Hansen, 1975], desarrollado por Brinch Hansen, se encargó de romper 
este mito y abrir la puerta a otros lenguajes de alto nivel que incorporaban 
concurrencia. 
Desde entonces la programación concurrente ha ido ganando interés y 
actualmente se utiliza muy a menudo en la implementación de numerosos 
sistemas. Tres grandes hitos se nos antojan importantes para que la programación 
concurrente actualmente sea tan importante: 
 
 La aparición del concepto de thread o hilo que hace que los programas 
puedan ejecutarse con mayor velocidad comparados con aquellos que 
utilizan el concepto de proceso. 
 La aparición más reciente de lenguajes como Java, lenguaje orientado a 
objetos de propósito general que da soporte directamente a la programación 
concurrente mediante la inclusión de primitivas específicas. 
 La aparición de Internet que es un campo abonado para el desarrollo y la 
utilización de programas concurrentes. Cualquier programa de Internet en el 
que podamos pensar tales como un navegador, un chat, etc, están 
programados usando técnicas de programación concurrente. 
 
En lo que resta de capítulo introduciremos el concepto de programación 
concurrente, los beneficios que reporta, el hardware en el que puede ejecutarse, la 
forma de especificarlo en un lenguaje y las características, problemas y 
propiedades de corrección de un programa concurrente. 
1.2 Concepto de programación concurrente 
Según el diccionario de la Real Academia Española, una de las acepciones de la 
palabra concurrencia es 
“Acaecimiento o concurso de varios sucesos en un mismo tiempo”. 
 
M.E Carmen Cerón G Programación Concurrente BUAP 2
Si en esta definición sustituimos la palabra suceso por proceso ya tenemos una 
primera aproximación a lo que va a ser la concurrencia en computación. 
Puesto que en la definición anterior y en la que daremos posteriormente de 
programación concurrente aparece la palabra proceso y ésta está basada en el 
concepto de programa, se hace necesario dejar claro en este punto qué se va a 
entender tanto por programa como por proceso. 
1.2.1 Programa y proceso 
Un programa es un conjunto de instrucciones. Es, simplemente, un texto que 
consiste en una secuencia de líneas de código que dicen qué hacer con un 
conjunto de datos de entrada para producir algún tipo de salida. Se trata de algo 
estático. Puede compararse con el concepto de clase en el ámbito de la 
Programación Orientada a Objetos (POO). Para que el programa pueda hacer 
algo de verdad hay que ponerlo en ejecución. 
Una primera definición incompleta de proceso sería la de un programa en 
ejecución. Es decir, un proceso es algo más que las líneas de código de un 
programa. Un proceso es algo dinámico. Está representado por el valor del 
contador de programa, el contenido de los registros del procesador, un pila y una 
sección de datos que contiene variables globales. Un proceso es una entidad 
dinámica. Puede compararse con el concepto de objeto en el ámbito de la POO. 
De igual manera que en POO puede haber múltiples objetos de una clase 
determinada, aquí puede haber múltiples procesos que corresponden al mismo 
programa. Como ejemplo consideremos un servidor de aplicaciones donde reside 
una aplicación de navegador de Internet y existen varios usuarios ejecutando ese 
navegador, cada uno de ellos navegando por un sitio diferente. Cada instancia del 
programa es un proceso. Cada proceso tendrá su propio contador de programa, 
así como sus propios registros, pila y variables. 
 
En la Figura 1 puede observarse el ejemplo mencionado donde existe un 
programa almacenado en disco y tres instancias de ese programa ejecutándose. 
Son tres procesos, cada uno con su propia información. 
 
 
navegador 
Internet 
 
SISTEMA OPERATIVO 
 
proceso
p1 
 
proceso
p2 
 
proceso
p3 
 
Figura 1 Programa y procesos. 
 
M.E Carmen Cerón G Programación Concurrente BUAP 3
1.2.2 Concurrencia 
Dos procesos serán concurrentes cuando la primera instrucción de uno de ellos 
se ejecuta después de la primera instrucción del otro y antes de la última. Es decir, 
existe un solapamiento en la ejecución de sus instrucciones. No tienen por qué 
ejecutarse exactamente al mismo tiempo, simplemente es suficiente con el hecho 
de que exista un intercalado entre la ejecución de sus instrucciones. Si se ejecutan 
al mismo tiempo los dos procesos, entonces tenemos una situación de 
programación paralela. La programación concurrente es un paralelismo 
potencial. Dependerá del hardware subyacente como veremos más adelante. 
De esta forma, en la Figura 1 tendríamos tres procesos concurrentes si se diese 
la circunstancia anterior. Se trata de un primer nivel de concurrencia1, donde 
existen 3 procesos independientes ejecutándose al mismo tiempo sobre el 
Sistema Operativo. Cada proceso corresponde a una instancia de un programa. 
Sin embargo, esto sólo es una parte de la verdad. No necesariamente un 
proceso tiene por qué ser todo el programa en ejecución sino que puede ser parte 
de él. Dicho de otra forma, un programa, al ponerse en ejecución, puede dar lugar 
a más de un proceso, cada uno de ellos ejecutando una parte del programa. 
Continuando con el mismo ejemplo, el programa de navegador de Internet puede 
dar lugar a más de un proceso: uno que controla las acciones del usuario con la 
interfaz, otro que hace las peticiones al servidor, etc. De esta forma, la Figura 1 se 
convertiría en la Figura 2, suponiendo que se crean dos procesos cada vez que se 
ejecuta el programa. Todos estos procesos también pueden ejecutarse 
concurrentemente. 
 
 
navegador 
Internet 
 
SISTEMA OPERATIVO 
p1.1 p1.2 p2.1 p2.2 p3.1 p3.2
 
Figura 2 Un programa dando lugar a más de un proceso. 
 
Así pues, una definición más acertada de proceso es la de una actividad 
asíncrona susceptible de ser asignada a un procesador. Una definición bastante 
extendida es que un proceso es un programa en ejecución, pero no es muy exacto 
pues realmente un programa puede estar compuesto por diversos procesos. Un 
Sistema Operativo no deja de ser un programa con varios procesos que se 
ejecutan al mismo tiempo. 
 
1 En el siguiente capítulo se verá que existe un segundo nivel de concurrencia. 
 
M.E Carmen Cerón G Programación Concurrente BUAP 4
Cuando varios procesos se ejecutan concurrentemente puede haber procesos 
que colaboren para un determinado fin mientras que puede haber otros que 
compitan por los recursos del sistema. Incluso aquellos procesos que colaboran 
deberán competir a la hora de obtener tiempo de procesador. Por ejemplo, en la 
Figura 2, p1.1 y p1.2 pueden estar colaborando para hacerle la vida más fácil al 
usuario mientras que p1.2 y p2.2 pueden estar compitiendo para acceder al disco. 
Para llevar a cabo estas tareas de colaboración y competencia por los recursos 
se hace necesaria la introducción de mecanismos de comunicación y 
sincronización entre procesos. Precisamente del estudio de estos mecanismos 
trata la programación concurrente. 
1.2.3 Programación Concurrente 
La programaciónconcurrente es la disciplina que se encarga del estudio de las 
notaciones que permiten especificar la ejecución concurrente de las acciones de 
un programa, así como las técnicas para resolver los problemas inherentes a la 
ejecución concurrente, que son básicamente comunicación y sincronización. 
Como puede intuirse, el trabajar con procesos concurrentes va a añadir 
complejidad a la tarea de programar. Cabe entonces hacerse la pregunta de 
¿cuáles son los beneficios que aporta la programación concurrente? 
1.3 Beneficios de la programación concurrente 
Existen diversos motivos por los que la programación concurrente es útil. 
Destacaremos aquí dos de ellos: velocidad de ejecución y solución de problemas 
de naturaleza concurrente. Otros beneficios adicionales como el mejor 
aprovechamiento de la CPU saldrán a lo largo del capítulo. 
1.3.1 Velocidad de ejecución 
Cuando la puesta en ejecución de un programa conlleva la creación de varios 
procesos y el sistema consta de más de un procesador, existe la posibilidad de 
asignar un proceso a cada procesador de tal forma que el programa se ejecuta de 
una forma más rápida. Los programas de cálculo numérico son grandes 
beneficiados de este hecho. 
1.3.2 Solución de problemas inherentemente concurrentes 
Existen algunos problemas cuya solución es más fácil de abordar mediante el uso 
de programación concurrente pues su naturaleza es eminentemente concurrente. 
Destacamos algunos de ellos, pero para una discusión más detallada se sugiere 
consultar [Bacon, 1998]. 
Sistemas de control 
Son aquellos sistemas en los que hay una captura de datos, normalmente a través 
de sensores, un análisis de esos datos y una posible actuación posterior en 
función del resultado del análisis. La recolección de datos se puede estar haciendo 
de diversas entidades físicas como por ejemplo edificios o estancias dentro de 
edificios. No sería tolerable un sistema secuencial que vaya capturando los datos 
 
M.E Carmen Cerón G Programación Concurrente BUAP 5
uno a uno de las distintas estancias. Podría ocurrir que al llegar a capturar los 
datos de la última estancia, la primera ya haya sido pasto de las llamas. Tanto la 
captura de datos desde cada estancia como su tratamiento y posterior actuación 
son candidatos a ser procesos distintos y de naturaleza concurrente. Esto nos 
garantiza que nuestro sistema de control pueda responder a las alarmas que se 
produzcan. 
Tecnologías web 
La mayoría de los programas relacionados con la web son concurrentes: los 
servidores web que son capaces de atender concurrentemente múltiples 
conexiones de usuarios; los programas de chat que permiten mantener la 
conversación de varios usuarios; los servidores de correo que permiten que 
múltiples usuarios puedan mandar y recibir mensajes al mismo tiempo; los propios 
navegadores que permiten que un usuario pueda estar haciendo una descarga 
mientras navega por otras páginas, o se ejecuta un applet de Java, etc. 
Aplicaciones basadas en interfaces de usuarios 
La concurrencia en este tipo de aplicaciones va a permitir que el usuario pueda 
interaccionar con la aplicación aunque ésta esté realizando alguna tarea que 
consume mucho tiempo de procesador. Un proceso controla la interfaz mientras 
otro hace la tarea que requiere un uso intensivo de la CPU. Esto facilitará que 
tareas largas puedan ser abortadas a mitad de ejecución. 
Simulación 
Los programas secuenciales encuentran problemas al simular sistemas en los que 
existen objetos físicos que tienen un comportamiento autónomo independiente. La 
programación concurrente permitirá modelar esos objetos físicos y ponerlos en 
ejecución de forma independiente y concurrente, sincronizándolos de la forma 
apropiada. 
SGBD 
En Sistemas Gestores de Bases de Datos la concurrencia juega un papel muy 
importante cuando se va a permitir a varios usuarios interactuar con el sistema. 
Cada usuario puede ser visto como un proceso. Obviamente hay que implementar 
la política adecuada para evitar situaciones en las que dos usuarios modifican al 
mismo tiempo un registro. Sin embargo, a varios usuarios que quieran acceder a 
un mismo registro para consultarlo y no modificarlo, debe permitírseles un acceso 
concurrente. 
1.4 Concurrencia y arquitecturas hardware 
Hasta ahora sólo hemos hablado de procesos, es decir, de software. No hemos 
dicho nada del hardware en el que se van a ejecutar nuestros procesos 
concurrentes. Parece obvio pensar que sin dos procesos van a ejecutarse de 
forma concurrente vamos a necesitar dos procesadores, uno para cada proceso. 
 
M.E Carmen Cerón G Programación Concurrente BUAP 6
Sin embargo, esto no tiene por qué ser así. Dependerá, aunque no 
exclusivamente, del hardware disponible y su topología. 
No es el propósito de este libro el hablar de hardware, pero sí que es necesario 
hacer una pequeña incursión para posteriormente entender algunos conceptos. 
Cuando hablamos de hardware nos estamos refiriendo fundamentalmente al 
número de procesadores en el sistema. Así, se puede hacer una primera distinción 
entre aquellos sistemas donde sólo hay un procesador, sistemas 
monoprocesador, y aquellos en los que hay más de un procesador, sistemas 
multiprocesador. En ambos sistemas es posible tener concurrencia. 
1.4.1 Sistemas monoprocesador 
Incluso en un sistema con un solo procesador podemos tener una ejecución 
concurrente de procesos. Evidentemente todos los procesos no pueden estar 
ejecutándose al mismo tiempo sobre el procesador, sólo uno de ellos podrá estar 
haciéndolo, pero la sensación que le da al usuario o grupo de usuarios es la de 
estar ejecutándose al mismo tiempo. Esto es debido a que el Sistema Operativo 
(SO) va alternando el tiempo de procesador entre los distintos procesos. De esta 
forma, cuando un proceso que ocupa el procesador en un momento determinado 
necesita hacer una operación de entrada/salida, puede abandonar el procesador 
para que otro proceso pueda ocuparlo y aprovechar ciclos de procesador. En la 
Figura 3 puede verse cómo el tiempo de procesador es repartido entre tres 
procesos. Esta forma de gestionar los procesos en un sistema monoprocesador 
recibe el nombre de multiprogramación y es otro de los beneficios de la 
programación concurrente: un mayor aprovechamiento del procesador. 
Esto es lo que ocurre en los SO que estamos acostumbrados a manejar con los 
ordenadores de sobremesa tales como Windows o Linux. 
 
 P1 
P2 
P3 
 
Figura 3 Concurrencia. 
Aparte de la situación en la que un proceso puede aprovechar ciclos de CPU 
mientras otro proceso hace operaciones de entrada/salida, existen otros posibles 
beneficios del uso de concurrencia en sistemas monoprocesador: 
 
 La posibilidad de proporcionar un servicio interactivo a múltiples usuarios. 
Este sería el caso por ejemplo de un Sistema Operativo multiusuario 
ejecutándose sobre una máquina monoprocesador. 
 
 La posibilidad de dar una solución adecuada a problemas que son de 
naturaleza eminentemente concurrente tal y como se mencionó en la 
sección 1.3.2. 
 
 
M.E Carmen Cerón G Programación Concurrente BUAP 7
En un sistema monoprocesador todos los procesos comparten la misma 
memoria. La forma de sincronizar y comunicar procesos será pues mediante el 
uso de variables compartidas. Tal y como muestra la Figura 4 cuando un 
proceso A quiere comunicar algo a un proceso B lo deja en una variable conocida 
y compartida por ambos procesos de tal forma que el proceso B lo pueda leer. 
 
 
proceso
A 
proceso
B 
proceso
C 
Variable 
compartida MEMORIA común a 
todos los procesos 
escribe lee
SISTEMA OPERATIVO 
procesador
 
Figura 4 Sistema monoprocesador con variables compartidas. 
 
1.4.2 Sistemas multiprocesador 
Un sistema multiprocesador es aquel en el que existe más de un procesador. Esto 
permite que exista un paralelismo real entre los procesos ya que idealmente cada 
procesador podría ejecutar un proceso. Si tuviésemos un sistema con tres 
procesadores en vez de tenerla Figura 3 el resultado podría ser el de la Figura 5 
en el que realmente los tres procesos se ejecutan de forma paralela. 
 P1
P2
P3
 
Figura 5 Paralelismo. 
 
Sin embargo, y siendo realistas, lo normal en un sistema concurrente es tener 
más procesos que procesadores por lo que, de alguna forma, tiene que haber 
algún esquema de multiprogramación en uno o más procesadores. 
 
Dentro de los sistemas multiprocesadores se puede hacer una pequeña 
clasificación: 
 
 
M.E Carmen Cerón G Programación Concurrente BUAP 8
 Sistemas fuertemente acoplados: tanto los procesadores como otros 
dispositivos (incluida la memoria) están conectados a un bus. Esto permite 
que todos los procesadores puedan compartir la misma memoria. Puede 
ocurrir que cada procesador tenga su propia memoria local, pero la 
sincronización y comunicación entre procesos se hará mediante variables 
situadas en la memoria compartida, es decir, mediante variables 
compartidas (Figura 6). 
 
 Sistemas débilmente acoplados: aquí no existe una memoria compartida 
por los procesadores. Cada procesador tiene su propia memoria local y está 
conectado con otros procesadores mediante algún tipo de enlace de 
comunicación. Un tipo especial de estos sistemas lo constituyen los 
sistemas distribuidos, que están formados por un conjunto de nodos 
distribuidos geográficamente y conectados de alguna forma. Estos nodos 
pueden ser a su vez mono o multiprocesador. El sistema distribuido por 
antonomasia es Internet. 
 
 
proceso 
A 
proceso 
B 
proceso
C 
Variable 
compartida MEMORIA común a 
todos los procesos 
escribe lee
SISTEMA OPERATIVO 
procesador procesador procesador 
 
Figura 6 Sistema multiprocesador con 
memoria compartida. 
procesador procesador 
nodo 
A 
procesador 
nodo 
B 
procesador 
nodo 
C 
paso de mensaje 
 
Figura 7 Sistema distribuido.
 
Suele denominarse multiproceso a la gestión de varios procesos dentro de un 
sistema multiprocesador donde cada procesador puede acceder a una memoria 
común y procesamiento distribuido a la gestión de varios procesos en 
procesadores separados, cada uno con su memoria local. 
Mientras que en los sistemas de multiproceso el esquema de la Figura 4 se 
puede seguir manteniendo tal y como se muestra en la Figura 6, en el 
procesamiento distribuido este esquema ya no es válido. En un sistema distribuido 
la forma natural de comunicar y sincronizar procesos es mediante el uso de paso 
de mensaje tal y como se aprecia en la Figura 7. El paso de mensaje no sólo es 
aplicable a los sistemas distribuidos sino que también puede usarse en sistemas 
de multiproceso y de multiprogramación. Es por esta razón por la que actualmente 
 
M.E Carmen Cerón G Programación Concurrente BUAP 9
los mecanismos de paso de mensaje son más utilizados en los lenguajes 
concurrentes, aparte de la buena sintonía que este mecanismo guarda con la 
Programación Orientada a Objetos. No en vano, la unión de ambos paradigmas, 
concurrente y objetos, ha dado lugar a lo que se conoce como Programación 
Concurrente Orientada a Objetos. El lenguaje Java no deja de ser un ejemplo. 
Para terminar este apartado es bueno dejar claras algunas definiciones 
adicionales que a veces llevan a confusión y en las que no todos los autores 
pueden estar de acuerdo: 
 un programa concurrente define un conjunto de acciones que pueden ser 
ejecutadas simultáneamente 
 un programa paralelo es un tipo de programa concurrente diseñado para 
ejecutarse en un sistema multiprocesador 
 un programa distribuido es un tipo de programa paralelo que está 
diseñado para ejecutarse en un sistema distribuido, es decir, en una red de 
procesadores autónomos que no comparten una memoria común 
 
En este libro nos ocuparemos de los programas concurrentes, no haciendo 
ningún tipo de suposición sobre el número de procesadores y su topología. Un 
programa concurrente debe funcionar independientemente de que lo ejecutemos 
en un sistema monoprocesador o en un sistema multiprocesador, ya sea éste 
fuerte o débilmente acoplado. 
1.5 Especificación de ejecución concurrente 
Una vez que sabemos qué es un programa concurrente y las distintas 
arquitecturas hardware que pueden soportarlo, es el momento de ver qué partes 
de un programa se pueden ejecutar concurrentemente y qué partes no, y cómo 
especificarlo en un lenguaje de programación. 
1.5.1 ¿Qué se puede ejecutar concurrentemente? 
Obviamente, no todas las partes de un programa pueden ejecutarse de forma 
concurrente. Consideremos el siguiente fragmento de programa: 
 
x:=x+1; 
y:=x+2; 
 
Está claro que la primera sentencia se tiene que ejecutar antes que la segunda. 
Sin embargo consideremos ahora: 
 
x:=1; 
y:=2; 
z:=3; 
 
Queda claro que el orden en que se ejecuten no interviene en el resultado final. 
Si dispusiésemos de tres procesadores podríamos ejecutar cada una de las líneas 
en uno de ellos incrementando la velocidad del sistema. 
En el caso anterior, el sentido común es el que nos ha hecho ver qué se podía y 
qué no se podía ejecutar concurrentemente. Sin embargo, A. J. Bernstein 
 
M.E Carmen Cerón G Programación Concurrente BUAP 10
[Bernstein, 1966] definió unas condiciones para determinar si dos conjuntos de 
instrucciones Si y Sj se pueden ejecutar concurrentemente. 
Condiciones de Bernstein 
Para poder determinar si dos conjuntos de instrucciones se pueden ejecutar de 
forma concurrente, se definen en primer lugar los siguientes conjuntos: 
 L (Sk) = {a1, a2, ... , an}, como el conjunto de lectura del conjunto de 
instrucciones Sk y que está formado por todas las variables cuyos valores 
son referenciados (se leen) durante la ejecución de las instrucciones en Sk. 
 E (Sk) = {b1, b2, ... , bm}, como el conjunto de escritura del conjunto de 
instrucciones Sk y que está formado por todas las variables cuyos valores 
son actualizados (se escriben) durante la ejecución de las instrucciones en 
Sk. 
 
Para que dos conjuntos de instrucciones Si y Sj se puedan ejecutar 
concurrentemente, se tiene que cumplir que: 
 
1. L(Si) ∩ E(Sj) = ∅ 
2. E(Si) ∩ L(Sj) = ∅ 
3. E(Si) ∩ E(Sj) = ∅ 
 
Como ejemplo supongamos que tenemos: 
 
S1 → a := x+y; 
S2 → b := z-1; 
S3 → c := a-b; 
S4 → w := c+1; 
 
Utilizando las condiciones de Bernstein veremos qué sentencias pueden 
ejecutarse de forma concurrente y cuáles no. Para ello, en primer lugar calculamos 
los conjuntos de lectura y escritura: 
 
L (S1) = {x, y} E (S1) = {a} 
L (S2) = {z} E (S2) = {b} 
L (S3) = {a, b} E (S3) = {c} 
L (S4) = {c} E (S4) = {w} 
 
Ahora aplicamos las condiciones de Bernstein a cada par de sentencias: 
 
Entre S1 y S2: 
L(S1) ∩ E(S2) = ∅ 
E(S1) ∩ L(S2) = ∅ 
E(S1) ∩ E(S2) = ∅ 
 
 
Entre S1 y S3: 
L(S1) ∩ E(S3) = ∅ 
E(S1) ∩ L(S3) = a ≠ ∅ 
E(S1) ∩ E(S3) = ∅ 
 
 
Entre S1 y S4: 
 
M.E Carmen Cerón G Programación Concurrente BUAP 11
L(S1) ∩ E(S4) = ∅ 
E(S1) ∩ L(S4) = ∅ 
E(S1) ∩ E(S4) = ∅ 
 
Entre S2 y S3: 
L(S2) ∩ E(S3) = ∅ 
E(S2) ∩ L(S3) = b ≠ ∅ 
E(S2) ∩ E(S3) = ∅ 
 
Entre S2 y S4: 
L(S2) ∩ E(S4) = ∅ 
E(S2) ∩ L(S4) = ∅ 
E(S2) ∩ E(S4) = ∅ 
 
Entre S3 y S4: 
L(S3) ∩ E(S4) = ∅ 
E(S3) ∩ L(S4) = c ≠ ∅ 
E(S3) ∩ E(S4) = ∅ 
De todo esto se deduce la siguiente tabla en la que puede verse qué pares de 
sentencias pueden ejecutarse de forma concurrente: 
 
 S1 S2 S3 S4 
S1 -- Sí No Sí 
S2 -- -- No Sí 
S3 -- -- -- No
S4 -- -- -- -- 
 
Una vez que sabemos qué se puede y qué no se puede ejecutar 
concurrentemente, se hace necesario algún tipo de notación para especificar qué 
partes de un programa pueden ejecutarse concurrentemente y qué partes no. 
1.5.2 Cómo especificar la ejecución concurrente 
Veremos dos posibles formas de especificar la ejecución concurrente de 
instrucciones: una basada en una notación gráfica y otra basada en lo que suelen 
utilizar diversos lenguajes de programación, el par cobegin/coend. 
Grafos de precedencia 
Se trata de una notación gráfica. Es un grafo dirigido acíclico. Cada nodo 
representará una parte (conjunto de instrucciones)de nuestro sistema. Una flecha 
desde A hasta B representa que B sólo puede ejecutarse cuando A haya 
finalizado. Si aparecen dos nodos en paralelo querrá decir que se pueden ejecutar 
concurrentemente. 
Para el ejemplo anterior el grafo de precedencia sería el de la Figura 8. 
 
 
M.E Carmen Cerón G Programación Concurrente BUAP 12
 
S1 S2
S3
S4
 
Figura 8 Grafo de precedencia. 
Sentencias COBEGIN-COEND 
Todas aquellas acciones que puedan ejecutarse concurrentemente las 
introducimos dentro del par cobegin/coend. El ejemplo anterior quedaría de la 
siguiente forma: 
 
begin 
cobegin 
 a:=x+y; 
 b:=z+1; 
coend; 
c:=a-b; 
w:=c+1; 
 end. 
 
Las instrucciones dentro del par cobegin/coend pueden ejecutarse en cualquier 
orden, mientras que el resto se ejecuta de manera secuencial. 
1.6 Características de los sistemas concurrentes 
La ejecución de sistemas concurrentes tiene algunas características que los 
diferencian claramente de los sistemas secuenciales. Destacamos dos: 
1.6.1 Orden de ejecución de las instrucciones 
En los programas secuenciales hay un orden total en la ejecución de las líneas 
de código. Ante un conjunto de datos de entrada se sabe siempre por dónde va a 
ir el programa (su flujo de ejecución). En la Figura 9, por muchas veces que se 
ejecute el programa, el hilo de ejecución siempre tendrá el mismo recorrido, es 
decir, las instrucciones siempre se ejecutarán en el mismo orden. 
 
M.E Carmen Cerón G Programación Concurrente BUAP 13
 hilo de ejecución 
programa 
i1 
i2 
i3 
i4 
i5 
i6 
i7 
 
Figura 9 Orden total. 
 
 
 
i1 
i2 
i3 
i4 
i5 
i6 
i7 
i1
i2
i3
i4
i5
i6
i7
 
Figura 10 Orden parcial.
 
En los programas concurrentes, sin embargo, hay un orden parcial. Ante el 
mismo conjunto de datos de entrada no se puede saber cuál va a ser el flujo de 
ejecución. En cada ejecución del programa el flujo puede ir por distinto sitio. En la 
Figura 10, donde se supone que todas las instrucciones pueden ejecutarse 
concurrentemente, podemos ver cómo en dos ejecuciones distintas el orden en el 
que se ejecutan las instrucciones puede variar. 
En la Figura 11 podemos observar el grafo de precedencia y el código con el 
par cobegin/coend para el caso de la Figura 10. 
 
 
i1 i2 i3 i4 i5 i6 i7
 
 
 
begin 
 cobegin 
 i1; i2; i3; i4; i5; i6; i7; 
 coned; 
end. 
Figura 11 Orden parcial: grafo de precedencia y código. 
1.6.2 Indeterminismo 
Este orden parcial lleva a que los programas concurrentes puedan tener un 
comportamiento indeterminista, es decir, puedan arrojar diferentes resultados 
cuando se ejecutan repetidamente sobre el mismo conjunto de datos de entrada. 
Esto suele llevar a muchas sorpresas cuando uno se inicia en la programación 
concurrente. 
Consideremos el siguiente programa en el que dos procesos se ejecutan 
concurrentemente para sumar 1 a la variable x. Esa variable x es compartida por 
ambos procesos pues ha sido declarada como global. La sintaxis utilizada es la 
del lenguaje Pascal-FC. 
 
 program Incognita; 
 var x: integer; 
 
M.E Carmen Cerón G Programación Concurrente BUAP 14
 
process P1; 
 var i: integer; 
begin 
 for i:=1 to 5 do x:=x+1; 
end; 
 
process P2; 
 var j: integer; 
begin 
 for j:=1 to 5 do x:=x+1 
end; 
 
 
 
 
begin 
 x:=0; 
 cobegin 
 P1; 
 P2; 
 coend; 
end. 
 
 
 
¿Qué valor tendrá la variable x al terminar el programa? Todo hace pensar que 
el valor debería ser 10. Sin embargo, el valor de x puede ser 5, 6, 7, 8, 9 ó 10. 
Esta característica hace muy difícil la labor de depuración en los programas 
concurrentes. Podemos ejecutar el programa 1.000 veces y podría dar como 
resultado 10 y al ejecutarlo 1.001 veces nos podría dar 8. 
Intuitivamente podemos ver que el error se encuentra en el acceso incontrolado 
a una variable compartida por parte de 2 procesos. En la siguiente sección vemos 
más a fondo la raíz del problema. 
1.7 Problemas inherentes a la programación concurrente 
Dos son básicamente los problemas con los que nos vamos a encontrar a la hora 
de confeccionar un programa concurrente: el problema de la exclusión mutua y el 
de la condición de sincronización. 
1.7.1 Exclusión mutua 
Este problema es el que se nos da en el ejemplo anterior de los bucles. Antes de 
pasar a explicar el problema hay que tener en cuenta que lo que realmente se 
ejecuta concurrentemente son las líneas de código generadas por el compilador. 
En nuestro caso, supongamos que una instrucción como x:=x+1 da lugar a tres 
instrucciones de un lenguaje ensamblador cualquiera, que es lo que realmente va 
a ejecutar el procesador. Tendríamos los siguientes pasos: 
1. Cargar desde memoria el valor de x en un registro (LOAD X R1). 
2. Incrementar el valor del registro (ADD R1 1). 
3. Almacenar el contenido del registro en la posición de memoria de x 
(STORE R1 X). 
Así pues, lo que realmente se va a ejecutar de forma concurrente dentro de 
cada bucle es: 
 
P1 
(1) LOAD X R1 
(2) ADD R1 1 
(3) STORE R1 X 
P2 
(1) LOAD X R1 
(2) ADD R1 1 
(3) STORE R1 X 
 
 
M.E Carmen Cerón G Programación Concurrente BUAP 15
Cada una de estas instrucciones es atómica o indivisible, es decir, se va a 
ejecutar en un ciclo de reloj del procesador sin poder ser interrumpidas. Puesto 
que hemos dicho que en programación concurrente existe un orden parcial, 
cualquier intercalado entre estas instrucciones es válido. En la Figura 12 puede 
verse una traza para un intercalado particular de estas seis líneas de código en el 
que el valor final de la variable x no es el esperado. Se ha perdido un incremento. 
Si tenemos en cuenta que estas líneas de código están en un bucle ahora 
podremos entender por qué son posible resultados menores de 10 para la variable 
x. Todo dependerá del número de incrementos perdidos, que en cada ejecución 
puede ser distinto e incluso no producirse. 
 
 
x 0 0 0 0 1 1 1
P1 1 2 3 
P2 1 2 3 
Tiempo 
Figura 12 Traza de una posible ejecución concurrente para P1 y P2. 
 
En cualquier caso, el hecho de que P1 y P2 no puedan ejecutarse 
concurrentemente viene determinado por las condiciones de Bernstein pues sus 
conjuntos de escritura no son disjuntos. El problema estriba en que dos procesos 
distintos están accediendo al mismo tiempo a una variable compartida entre los 
dos para actualizarla. Nos hubiese interesado que las tres líneas de cada proceso 
se hubiesen ejecutado en un solo paso, sin ningún tipo de intercalado con las 
otras líneas del otro proceso. A la porción de código que queremos que se ejecute 
de forma indivisible se le denomina sección crítica. Nos interesa asegurarnos que 
las secciones críticas se ejecuten en exclusión mutua, es decir, sólo uno de los 
procesos debe estar en la sección crítica en un instante dado. En la Figura 13 
puede verse cómo cuando los dos procesos llegan a la sección crítica sólo uno de 
ellos podrá entrar, teniendo que esperar el otro. En la Figura 14 puede verse que 
una vez que un proceso ha salido de la sección crítica, el otro proceso puede 
entrar y de esta forma seguir ejecutándose los dos de manera concurrente. 
 P1 P2 
Sección crítica 
x:=x+1 
 
Figura 13 Sección crítica (1). 
 
M.E Carmen Cerón G Programación Concurrente BUAP 16
 P1 P2 
Sección crítica 
x:=x+1 
 
Figura 14 Sección crítica (2). 
La programación concurrente deberá ofrecernos mecanismos para especificar 
qué partes del código han de ejecutarse en exclusión mutua con otras partes. 
1.7.2 Condición de sincronización 
Para ilustrar el problema de la condición de sincronización supongamos ahora un 
sistema en el que existen tres procesos (Figura 15) cuyo comportamiento es el 
siguiente: 
 lector, que va almacenando en un buffer las imágenes capturadas desde 
una cámara 
 gestor, que va recogiendo las imágenes desde el buffer, las trata y las va 
colocando en una cola de impresión 
 impresor, que va imprimiendo las imágenes colocadas en la cola de 
impresión 
 
 
 
 
LECTOR 
 
 
GESTOR
 
 
IMPRESOR 
buffer cola deimpresión
cámara impresora 
 
Figura 15 Sistema compuesto por los procesos lector, gestor e impresor. 
 
Supongamos que los tres procesos se ejecutan de manera concurrente en un 
bucle infinito tal y como muestra el siguiente pseudocódigo: 
 
process lector; 
begin 
 repeat 
 captura imagen; 
 almacena en buffer; 
 forever 
end; 
 
process gestor; 
begin 
 repeat 
 coge imagen de buffer; 
 trata imagen; 
 almacena imagen en cola; 
 forever 
end; 
process impresor; 
begin 
 repeat 
 coge imagen de cola; 
 imprime imagen; 
 forever 
end;
 
M.E Carmen Cerón G Programación Concurrente BUAP 17
 
El lector debería apreciar que la solución al problema está incompleta. 
Debería tratar de responder a las siguientes preguntas: 
 ¿Qué ocurre cuando el proceso lector o el proceso gestor tratan de poner 
una imagen y el buffer o la cola están llenos? 
 ¿Qué ocurre cuando el proceso gestor o el proceso impresor tratan de 
coger una imagen y el buffer o la cola están vacíos? 
 
Hay situaciones en las que un recurso compartido por varios procesos, como 
puede ser el buffer o la cola de impresión en nuestro ejemplo, se encuentra en 
un estado en el que un proceso no puede hacer una determinada acción con él 
hasta que no cambie su estado. A esto se le denomina condición de 
sincronización. 
La programación concurrente ha de proporcionarnos mecanismos para 
bloquear procesos que no puedan hacer algo en un momento determinado a la 
espera de algún evento (p. ej. que el buffer deje de estar vacío), pero también 
que permita desbloquearlos cuando ese evento haya ocurrido. 
 
A la solución de estos dos problemas usando diferentes técnicas es a lo que 
dedicaremos gran parte del libro. 
1.8 Corrección de programas concurrentes 
El orden parcial e indeterminismo en la ejecución de las instrucciones hace que 
la corrección de un programa concurrente sea más difícil de conseguir que la 
de un programa secuencial. Para que un programa concurrente sea correcto, 
además de cumplir las especificaciones funcionales que deba cumplir, debe 
satisfacer una serie de propiedades inherentes a la concurrencia. Podemos 
agrupar esas propiedades en: 
 Propiedades de seguridad: son aquellas que aseguran que nada 
malo va a pasar durante la ejecución del programa. 
 Propiedades de viveza: son aquellas que aseguran que algo 
bueno pasará eventualmente durante la ejecución del programa. 
 
Para entender en qué consisten estas propiedades, consideremos el famoso 
juego del pañuelo en el que hay dos equipos, A y B, y un juez con un pañuelo 
(Figura 16). Cada jugador de un equipo tiene un número del 1 al 3. No puede 
haber dos jugadores en el mismo equipo con el mismo número. El juez dice un 
número y entonces los dos rivales con el mismo número salen corriendo a 
coger el pañuelo. El jugador que lo coja ha de volver corriendo a su sitio sin 
que su rival logre tocarle la espalda. 
En este escenario explicaremos las distintas propiedades de vivacidad y 
seguridad. 
 
 
M.E Carmen Cerón G Programación Concurrente BUAP 18
 
el 2
 
Figura 16 Juego del pañuelo. 
Propiedades de seguridad 
 Exclusión mutua. Hay recursos en el sistema que deben ser accedidos en 
exclusión mutua tal y como hemos visto anteriormente. Cuando esto ocurre, 
hay que garantizar que si un proceso adquiere el recurso, otros procesos 
deberán esperar a que sea liberado. De lo contrario, el resultado puede ser 
imprevisto. En nuestro ejemplo, el pañuelo ha de adquirirse en exclusión 
mutua, o lo coge un jugador o lo coge otro. Si lo cogen los dos a la vez 
puede llegar a romperse, llevando a un malfuncionamiento del sistema. 
 Condición de sincronización. Hay situaciones en las que un proceso debe 
esperar por la ocurrencia de un evento para poder seguir ejecutándose. 
Cuando esto ocurre, hay que garantizar que el proceso no prosigue hasta 
que no se produce el evento. De lo contrario, el resultado puede ser 
imprevisto. En nuestro ejemplo, un jugador ha de esperar a que digan su 
número para poder salir corriendo. Si sale corriendo antes llevaría a un 
malfuncionamiento del sistema. 
 Interbloqueo. Se produce una situación de interbloqueo cuando todos los 
procesos están esperando porque ocurra un evento que nunca se 
producirá. Hay que garantizar que no se producen este tipo de situaciones. 
En nuestro ejemplo se produciría si un jugador se guarda el pañuelo y se va 
para su casa. El juez esperaría porque le devolvieran el pañuelo y los 
jugadores esperarían porque el juez dijese su número, pero ninguno de 
estos eventos va a ocurrir nunca. Se suele conocer también con el nombre 
de deadlock o abrazo mortal. 
Problemas de vivacidad 
 Interbloqueo activo: El anterior interbloqueo también suele conocerse 
como pasivo. Se produce una situación de interbloqueo activo cuando un 
sistema ejecuta una serie de instrucciones sin hacer ningún progreso. Hay 
que garantizar que no ocurra este tipo de situaciones. En nuestro ejemplo 
se produciría si dos jugadores, al intentar coger el pañuelo, amagan una y 
otra vez, pero no se deciden a cogerlo. Mientras que la detección de un 
intebloqueo pasivo es más o menos simple, la detección de un interbloqueo 
activo es muy complicada. Se suele conocer también con el nombre de 
 
M.E Carmen Cerón G Programación Concurrente BUAP 19
livelock. A partir de ahora cada vez que hablemos de interbloqueo nos 
referiremos al interbloqueo pasivo. 
 Inanición: Se produce una situación de este tipo cuando el sistema en su 
conjunto hace progresos, pero existe un grupo de procesos que nunca 
progresan pues no se les otorga tiempo de procesador para avanzar. En 
nuestro ejemplo podría darse si el juez nunca dice el número de un jugador 
en concreto. Hay que garantizar que haya una cierta equidad en el trato a 
los procesos a no ser que las especificaciones del sistema digan lo 
contrario. Se trata de un problema también difícil de detectar. Su suele 
conocer también con el nombre de starvation. 
Resumen 
En el presente capítulo se han presentado los conceptos fundamentales de la 
programación concurrente. Se ha definido el concepto de proceso, de 
concurrencia y de programación concurrente. Se han visto las distintas 
plataformas hardware donde poder ejecutar programas concurrentes: 
monoprocesador y multiprocesador y, en función de ello, se ha visto la 
diferencia por un lado entre multiprogramación, multiproceso y procesamiento 
distribuido y, por otro lado, entre programas concurrentes, paralelos y 
distribuidos. El hecho de que dos procesos sean concurrentes no implica 
necesariamente que se ejecuten exactamente al mismo tiempo. Eso dependerá 
del hardware subyacente. En cualquier caso, e independientemente del 
hardware, los beneficios de la programación concurrente pueden resumirse en: 
mayor velocidad de ejecución, mejor aprovechamiento de la CPU y soluciones 
óptimas a problemas de naturaleza eminentemente concurrente. 
También se ha visto en este capítulo cómo determinar cuándo un conjunto 
de instrucciones puede ejecutarse de manera concurrente mediante las 
condiciones de Bernstein. Una vez determinado qué se puede ejecutar 
concurrentemente, hemos visto cómo especificarlo de dos formas distintas: 
mediante el par cobegin/coend y mediante grafos de precedencia. 
Los programas concurrentes se caracterizan por un orden parcial en la 
ejecución de sus instrucciones frente al orden total presente en los programas 
secuenciales. Este orden parcial nos lleva a un indeterminismo en el resultado 
arrojado por la ejecución de los programas concurrentes. Este indeterminismo 
hace que la depuración y corrección de programas concurrentes no sea una 
tarea precisamente trivial. 
Dos son los grandes problemas a resolver en problemas de naturaleza 
concurrente: el problema de la exclusión mutua y el problema de la condición 
de sincronización. Un programa concurrente será correcto si, además de 
contemplar sus especificaciones funcionales donde irán implícitas condiciones 
de exclusión mutua y desincronización, es capaz de evitar que se produzcan 
situaciones de interbloqueo y de inanición de procesos. 
Ejercicios resueltos 
 
 
M.E Carmen Cerón G Programación Concurrente BUAP 20
1. Construir un programa concurrente que se corresponda con el grafo de 
precedencia de la siguiente figura utilizando el par cobegin/coend 
 
 
S1
S3S2
S4
S5 S6
S7 
 
 
Solución: 
S1; 
cobegin 
 S3; 
 begin 
 S2; 
 S4; 
 cobegin 
 S5; 
 S6; 
 coend 
 end; 
coend; 
S7; 
 
 
2. Dado el siguiente trozo de código obtener su grafo de precedencia 
correspondiente. 
 
s0; 
cobegin 
 s1; 
 begin 
 s2; 
 cobegin 
 s3;s4 
 coend; 
 s5 
 end; 
 s6 
coend; 
s7 
 
 
 
M.E Carmen Cerón G Programación Concurrente BUAP 21
Solución: 
 S0 
S2 
S3 S4 
S5 
S7 
S6 S1 
 
 
3. Construir un programa concurrente que explote al máximo la concurrencia 
para copiar un fichero f en un fichero g utilizando el par cobegin/coend. 
 
Solución: 
var f, g: file of T; 
 r s: T; 
count: integer; 
begin 
 abrirLectura (f); 
 abrirEscritura (g); 
 leer (f,s); 
 while not finFichero (f) do begin 
 s:=r; 
 cobegin 
 escribir (g,s); 
 leer (f,r); 
 coend 
 escribir (g,r); 
end; 
 
 
Ejercicios propuestos 
Cuestiones breves 
1. ¿Cuál es la ventaja de la concurrencia en los sistemas monoprocesador? 
2. ¿Cuáles son las diferencias entre programación concurrente, paralela y 
distribuida? 
3. ¿Cuáles son las diferencias entre multiprogramación, multiproceso y 
procesamiento distribuido? 
4. ¿Cuáles son los dos problemas principales inherentes a la programación 
concurrente? 
5. ¿Qué es una sección crítica? 
6. ¿Cuáles son las características de un programa concurrente? 
7. ¿Qué se entiende por un programa concurrente correcto? 
 
M.E Carmen Cerón G Programación Concurrente BUAP 22
 
Problemas 
1. Usando las condiciones de Bernstein, construir el grafo de precedencia del 
siguiente trozo de código y el programa concurrente correspondiente usando 
el par cobegin/coend. 
 
S1: cuad := x*x; 
S2: m1 := a*cuad; 
S3: m2 := b*x; 
S4: z := m1 + m2; 
S5: y := z + c; 
 
2. Construir dos programas concurrentes que se correspondan con los de la 
siguiente figura utilizando el par cobegin/coend. 
 
 
S1 
S5 S2 
S3 S4
S6 
 
 
 
S1
S2 S3 
S4
S5 S6
S7