8.2    Programación paralela.

Los sistemas de computación capaces de ejecutar varios programas concurrentemente son hoy bastante comunes.

Un sistema multiprocesador tiene varias CPU compartiendo una memoria común. Un sistema de computación distribuido, o paralelo, tiene varios computadoras (posiblemente cientos) cada uno con su propia memoria y CPU, conectados vía enlaces de comunicación en una red en la cual cada una puede comunicarse con los otros. En tales sistemas, muchas tareas pueden ejecutarse concurrentemente.

Sistemas operativos que soportan multiprogramación y time-sharing, suministran cierta clase de ejecución concurrente para programas usuario separados. Nuestro interés aquí, sin embargo, se refiere a la ejecución de tareas concurrentes dentro de un sólo programa.

El problema mayor es la falta de construcciones de LP's para tales sistemas. Mayoritariamente se usan lenguajes estándar como C, al que se agregan llamadas al sistema operativo para facilitar la realización de tareas paralelas.

Principios de LP's paralelos.

Las construcciones de programación paralela agregan complejidad al diseño de lenguajes, ya que varios procesadores pueden estar accesando los mismos datos simultáneamente.

Para considerar paralelismo en LP's, se deben considerar los siguientes 4 conceptos:

  1. Definición de variables

Las variables pueden ser mutables o definicionales. Las variables mutables son aquellas declaradas en la mayoría de los lenguajes secuenciales; los valores asignados a esas variables pueden ser cambiados durante la ejecución.Además

A una variable definicional se le puede asignar un valor sólo una vez. La virtud de esta variable, es que no genera problemas de sincronización.

  1. Composición paralela

Además de las sentencias habituales de los lenguajes secuenciales, necesitamos agregar sentencias paralelas, que provocan encadenamientos de control para comenzar la ejecución. Sentencias and y la función fork llamada desde C son ejemplos de este tipo de estructuras.

  1. Estructura de programa

Los programas paralelos generalmente tienen uno de los dos siguientes modos de ejecución:

  1. Transformacional:

El objetivo es transformar la entrada en la salida apropiada. El paralelismo se aplica para acelerar el proceso, tal como multiplicar matrices rápidamente multiplicando varias secciones en paralelo.

  1. Reactivo:

El programa reacciona a estímulos externos llamados eventos. Los sistemas de tiempo real, por ejemplo, son reactivos. Por ejemplo, un sistema de reserva de pasajes.

Estos sistemas se caracterizan por tener un comportamiento no determinístico, ya que no se sabe de manera explícita cuando ocurrirá un evento.

  1. Comunicación

Los programas paralelos deben comunicarse entre ellos. Tal comunicación se da típicamente a través de una memoria compartida en que los objetos son accesados por los programas paralelos, o a través de mensajes donde cada programa paralelo tiene su propia copia de los datos.

Ejecución concurrente.

El principal mecanismo para incorporar ejecución paralela en un LP, es crear una construcción que permita esa ejecución paralela.

El comando and realiza esta tarea:

sentencia1 and sentencia2 and ... and sentencian

cuya semántica dice que cada una de las sentencias sentenciai se ejecuta en paralelo. La instrucción siguiente no se ejecuta, sino hasta que todas las sentencias paralelas terminan su ejecución.

Aunque conceptualmente es muy simple, suministra todo el poder necesario para la ejecución paralela.

Por ejemplo, si un sistema operativo debe ejecutar una tarea de lectura desde un terminal, una tarea para escribir en una pantalla y un proceso para ejecutar un programa usuario podríamos especificarlo como:

call ReadProcess and
call WriteProcess and
call ExecuteUserProgram;

El secuenciamiento de la ejecución paralela es sólo una parte del problema. La manipulación correcta de los datos es otro aspecto importante. Consideremos:

x := 1;
x := 2 and y := x + x; (*)
print (y);

ya que las dos sentencias de  (*) pueden ejecutarse en paralelo, no podemos predecir cual termina primero.Aquí y puede imprimirse con el valor 2, con el valor 4, o incluso con el valor 3. Por lo tanto, necesitamos coordinar el acceso a los datos en los programas concurrentes. Para ello se introduce el concepto de semáforo:

Semáforos.

Un semáforo es un objeto (dato) usado para sincronización entre tareas.

Un semáforo consta de dos partes:

  1. Un contador entero, cuyo valor es siempre positivo o cero, que se usa para contar el número de señales enviadas pero todavía no recibidas, y
  2. Una fila de tareas que están a la espera de señales a ser enviadas.

En un semáforo binario, el contador puede tomar sólo los valores 0 o 1. En un semáforo general, el contador puede tomar cualquier valor entero no negativo.

Para un semáforo, se definen dos operaciones primitivas (sobre el objeto P) :

Signal(P). Cuando se ejecuta, en una cierta tarea A, esta operación chequea el valor del contador en P; si es cero, entonces la primera tarea en la fila de tareas es removida de la fila y se reinicia su ejecución; si no es cero, o si la fila está vacía, entonces el contador es incrementado en 1 (indicando una señal que ha sido enviada pero no recibida todavía). En cualquier caso, la ejecución de la tarea A continúa después que la operación signal se ha completado.

Wait(P). Cuando es ejecutado por una tarea B, esta operación chequea el valor del contador en P; si no es cero, entonces el valor del contador es decrementado en 1 (lo que indica que B ha recibido una señal) y la tarea B continúa la ejecución; si es 0, entonces la tarea B es insertada al final de la fila de tareas para P y la ejecución de B es suspendida (indicando que B está esperando por una señal a ser enviada).

Como ejemplo, consideremos dos tareas que cooperan para (1) introducir un lote de datos (tarea A) y (2) procesar un lote de datos (tarea B).

Para sincronizar sus actividades, se pueden usar dos semáforos binarios. El semáforo StartB es usado por la tarea A para señalizar que el ingreso del lote de datos se ha completado. El semáforo StartA es usado por la tarea B para señalizar que el procesamiento del lote de datos se ha completado.

Task A;
begin
- ingrese primer conjunto de datos
  loop;
    signal(startB);
    - llama a task B
    - ingresa próximo conjunto de datos
    wait(startA);
    - espera hasta que B termine de procesar los datos
  end loop;
end A;          
Task B;
begin
  loop;
    wait(startB);
    - espera que A lea los datos
    -procesa los datos
    signal(startA);
    - indica a tarea A que continúe
  end loop;
end B;