capÍtulo 1. conceptos fundamentalesmceron.cs.buap.mx/cap1_dis.pdf · “acaecimiento o concurso de...

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”.


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.


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.


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ón concurrente 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


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.


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.


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.

procesoA

procesoB

procesoC

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 tener la 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:


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

procesoC

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


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


[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:


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 -- -- -- NoS4 -- -- -- --

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.


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.


hilo de ejecución

programa

i1 i2

i3 i4

i5 i6

i7

Figura 9 Orden total.

i1 i2

i3 i4

i5 i6

i7

i1i2

i3i4

i5i6

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;


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


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 1P1 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).


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 de impresió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;


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.


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


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 de sincronización, es capaz de evitar que se produzcan situaciones de interbloqueo y de inanición de procesos.

Ejercicios resueltos


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


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?


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

capÍtulo 1. conceptos fundamentalesmceron.cs.buap.mx/cap1_dis.pdf · “acaecimiento o concurso de...

Documents