Caracteristicas Programacion Concurrente y Paralela

En diversos procesos computacionales es necesario aplicar diversos paradigmas de programación para enfocar el problema, es así que en algunas aplicaciones se necesita aplicar concurrencia y paralelismos para aumentar la eficiencia y potencial de los programas.

INTRODUCCIÓN

Actualmente observamos que el paradigma orientado a objetos, solo podemos ejecutar un equipo a la vez como máximo en cambio con la introducción de las hebras concurrentes(programación concurrente) o procesos es posible que cada objeto se ejecute simultáneamente, esperando mensajes y respondiendo adecuadamente. Como siempre la principal razón para la investigación de la programación concurrente es que nos ofrece una manera diferente de conceptualizar la solución de un problema, una segunda razón es la de aprovechar el paralelismo del hardware subyacente para lograr una aceleración significativa.

CONCEPTOS:

Ø PROGRAMA SECUENCIAL: Es aquel que especifica la ejecución de una secuencia de
instrucciones que comprenden el programa.

Ø PROCESO: Es un programa en ejecución, tiene su propio estado independiente del estado de
cualquier otro programa incluidos los del sistema operativo. Va acompañado de recursos como
archivos, memoria, etc.

Ø PROGRAMA CONCURRENTE: Es un programa diseñado para tener 2 o mas contextos de
ejecución decimos que este tipo de programa es multihenbrado, porque tiene mas de un contexto
de ejecución.

Ø PROGRAMA PARALELO: Es un programa concurrente en el que hay mas de un contexto de
ejecución o hebra activo simultáneamente; desde un punto de vista semántica no hay diferencia
entre un programa paralelo y concurrente.

Ø PROGRAMA DISTRIBUIDO: Es un sistema diseñado para ejecutarse simultáneamente en una red
de procesadores autónomos, que no comparten la memoria principal, con cada programa en su
procesador aparte.

FUNDAMENTOS DE LA PROGRAMACIÓN CONCURRENTE

Concurrencia: Es un termino genérico utilizado para indicar un programa único en el que
puede haber mas de un contexto de ejecución activo simultáneamente.

Estados de una hebra (PROCESO):

1. Creada: La hebra se ha creado pero aun no esta lista para ejecutarse.
2. Ejecutable o lista: La hebra esta lista para ejecutarse pero espera a conseguir un procesador
en que ejecutarse.
3. En ejecución: La hebra se esta ejecutando en un procesador.
4. Bloqueado o en espera: La hebra esta esperando tener acceso a una sección critica o ha
dejado el procesador voluntariamente.
5. Finalizada: La hebra se ha parado y no se volverá a ejecutar.

V. CARACTERISTICAS DE LOS PROCESOS CONCURRENTES

Interacción entre procesos: Los programas concurrentes implican interacción, entre los distintos
procesos que los componen:

Ø Los procesos que compartan recursos y compiten por el acceso a los mismos.
Ø Los procesos que se comunican entre sí para intercambiar datos.

En ambas situaciones se necesitan que los procesos sincronicen su ejecución, para evitar conflictos o
establecer contacto para el intercambio de datos .Esto se logra mediante variables compartidas o bien
mediante el paso de mensajes.

Indeterminismo: las acciones que se especifican en un programa secuencial, tienen un orden total,
pero en un programa concurrente el orden es parcial, ya que existe una incertidumbre sobre el orden
exacto de concurrencia de ciertos sucesos. De esta forma si se ejecuta un programa concurrente
varias veces, puede producir resultados diferentes partiendo de los mismos datos.

Gestión de recursos: los recursos compartidos necesitan una gestión especial. Un proceso que desea
utilizar un recurso compartido debe solicitar dicho recurso, esperar a adquirirlo, utilizarlo y después
liberarlo. Si el proceso solicita el recurso, pero no puede adquirirlo, en ese momento, es suspendido
hasta que el recurso esta disponible.
La gestión de recursos compartidos es problemática y se debe realizar de tal forma que se eviten
situaciones de retrazo indefinido o de bloqueo indefinido.

Comunicación: la comunicación entre procesos puede ser sincrona, cuando los procesos necesitan
sincronizarse para intercambiar los datos, o asíncrona cuando un proceso que suministra los datos no
necesita esperar a que el proceso receptor lo recoja, ya que los deja en un buffer de comunicación
temporal.

Violación de la exclusión mutua: en ocasiones ciertas acciones que se realizan en un programa
concurrente, no proporcionan los resultados deseados .Esto se debe a que existe una parte del
programa donde se realizan dichas acciones que constituye una región critica, es decir, es una parte
de un programa en la que se debe garantizar que si un proceso accede a la misma, ningún otro podrá
acceder.

PROGRAMACIÓN PARALELA

La programación paralela es una técnica de programación basada en la ejecución simultánea, bien
sea en un mismo ordenador (con uno o varios procesadores) o en un cluster de ordenadores, en cuyo
caso se denomina computación distribuida. Al contrario que en la programación concurrente, esta
técnica enfatiza la verdadera simultaneidad en el tiempo de la ejecución de las tareas.

Los sistemas multiprocesador o multicomputador consiguen un aumento del rendimiento si se
utilizan estas técnicas. En los sistemas monoprocesador el beneficio en rendimiento no es tan
evidente, ya que la CPU es compartida por múltiples procesos en el tiempo, lo que se denomina
multiplexación.

El mayor problema de la computación paralela radica en la complejidad de sincronizar unas tareas
con otras, ya sea mediante secciones críticas, semáforos o paso de mensajes, para garantizar la
exclusión mutua en las zonas del código en las que sea necesario.

Es el uso de varios procesadores trabajando juntos para resolver una tarea común, cada procesador
trabaja una porción del problema pudiendo los procesos intercambiar datos a través de la memoria o
por una red de interconexión.

Un programa paralelo es un programa concurrente en el que hay más de un contexto de ejecución, o
hebra, activo simultáneamente. Cabe recalcar que desde un punto de vista semántica no hay
diferencia entre un programa concurrente y uno paralelo

Necesidad de la programación paralela
Ø Resolver problemas que no caben en una CPU.
Ø Resolver problemas que no se resuelven en un tiempo razonable.
Ø Se puede ejecutar :
o Problemas mayores.
o Problemas mas rápidamente.

Aspectos en la programación paralela
Ø Diseño de computadores paralelos teniendo en cuenta la escalabilidad y comunicaciones.
Ø Diseño de algoritmos eficientes, no hay ganancia si los algoritmos no se diseñan
adecuadamente.
Ø Métodos para evaluar los algoritmos paralelos: ¿Cuán rápido se puede resolver un problema
usando una máquina paralela?,¿Con que eficiencia se usan esos procesadores?.
Ø En lenguajes para computadores paralelos deben ser flexibles para permitir una
implementación eficiente y fácil de programar.
Ø Los programas paralelos deben ser portables y los compiladores paralelizantes.

Modelos de computadoras
Ø Modelo SISD
1. Simple instrucción, simple Data.
2. Consiste en un procesador que recibe un cierto flujo de instrucciones y de datos.
3. Un algoritmo para esta clase dice ser secuencial o serial.
Ø Modelo MISD
4. Multiple Instruction, simpledata.
5. Existencia de N procesadores con un simple flujo de datos ejecutando instrucciones
diferentes en cada procesador.
Ø Modelo SIMD
6. Simple Instruction, múltiple Data.
7. Existen JN procesadores ejecutando la misma instrucción sobre los mismos o
diferentes datos.
8. Existencia de datos compartidos.
Ø Modelo MIMD
9. Multiple Instruction, multiple data.
10. Existen N procesadores ejecutando instrucciones diferentes sobre los mismos o
diferentes datos.
11. Existencia de datos compartidos.
Métodos para conectar los procesadores en paralelo
Ø Malla.
Ø Árbol Binario.
Ø Hiperarbol.
Ø Piramidal.
Ø Mariposa.
Ø HiperCubo.
Ø Hiper Cubo Cíclico.
Ø Transpaso-Intercambio.

CONCLUSIONES:

Ø Un programa paralelo es un programa concurrente en el que hay más de un contexto de
ejecución, o hebra, activo simultáneamente.
Ø Las aplicaciones de la concurrencia se centra principalmente en los sistemas operativos.
Ø Se ha propuesto varias primitivas de la comunicación entre procesos(Semáforos, monitores, etc)
pero todas son equivalentes en el sentido de que cada una se puede utilizar para implementar a
las demás.
Ø La programación paralela ayuda a disminuir la complejidad computacional de los algoritmos.
Ø La programación paralela nos ayuda a resolver problemas más complejos.

Monitores

Programas

DESCARGAR EL ARCHIVO Y ABRIRLO CON C# EJECUTARLO 


Programa contador de números pares eh impares y al final hilos
http://www.mediafire.com/download.php?eqbc0526a56gjgy

Programa ejemplo hilos
http://www.mediafire.com/download.php?eqbc0526a56gjgy

Programa procesos
http://www.mediafire.com/download.php?v3ym9zq7vcmkuwk

Programa caballo de carrera
http://www.mediafire.com/download.php?og7oiiuvyno7e21

Exclusión mutua

Los algoritmos de exclusión mutua (comúnmente abreviada como mutex por mutual exclusion) se usan en programación concurrente para evitar el uso simultáneo de recursos comunes, como variables globales, por fragmentos de código conocidos como secciones críticas.

Algunos ejemplos de algoritmos clásicos de exclusión mutua son:

Algoritmo de Dekker

El algoritmo de Dekker es un algoritmo de programación concurrente para exclusión mutua, que permite a dos procesos o hilos de ejecución compartir un recurso sin conflictos. Fue uno de los primeros algoritmos de exclusión mutua inventados, implementado por Edsger Dijkstra.

Si ambos procesos intentan acceder a la sección crítica simultáneamente, el algoritmo elige un proceso según una variable de turno. Si el otro proceso está ejecutando en su sección crítica, deberá esperar su finalización.

Existen cinco versiones del algoritmo Dekker, teniendo ciertos fallos los primeros cuatro. La versión 5 es la que trabaja más eficientemente, siendo una combinación de la 1 y la 4.
Versión 1: Alternancia estricta. Garantiza la exclusión mutua, pero su desventaja es que acopla los procesos fuertemente, esto significa que los procesos lentos atrasan a los procesos rápidos.
Versión 2: Problema interbloqueo. No existe la alternancia, aunque ambos procesos caen a un mismo estado y nunca salen de ahí.
Versión 3: Colisión región crítica no garantiza la exclusión mutua. Este algoritmo no evita que dos procesos puedan acceder al mismo tiempo a la región crítica.
Versión 4: Postergación indefinida. Aunque los procesos no están en interbloqueo, un proceso o varios se quedan esperando a que suceda un evento que tal vez nunca suceda.



shared int cierto = 1;

''/* Definición de variables compartidas */ ''
shared int bandera[2] = {0,0};
shared int turno = 0;

while (cierto)
{
bandera[proc_id] = cierto;
while (bandera[1-proc_id] == cierto)
{
if (turno == 1-proc_id)
{
bandera[proc_id] = 0;
while (turno == (1-proc_id)) /* espera a que sea su turno de intentar */;
bandera[proc_id] = 1;
}
}
/* ''Sección crítica'' */
turno = 1-proc_id; /* es el turno del otro proceso */
bandera[proc_id] = 0;
/* ''Sección no crítica'' */
}

///////////////////////////////////////////////////////////////////////////

El algoritmo de Peterson 
también conocido como solución de Peterson, es un algoritmo de programación concurrente para exclusión mutua, que permite a dos o más procesos o hilos de ejecución compartir un recurso sin conflictos, utilizando sólo memoria compartida para la comunicación.

Peterson desarrolló el primer algoritmo (1981) para dos procesos que fue una simplificación del algoritmo de Dekker para dos procesos. Posteriormente este algoritmo fue generalizado para N procesos.

bandera[0] = 0
bandera[1] = 0
turno = 0
p0: bandera[0] = 1 p1: bandera[1] = 1
turno = 1 turno = 0
while( bandera[1] && turno == 1 ); while( bandera[0] && turno == 0 );
//no hace nada; espera. //no hace nada; espera.
// sección crítica // sección crítica

// fin de la sección crítica // fin de la sección crítica
bandera[0] = 0 bandera[1] = 0


Los procesos p0 y p1 no pueden estar en la sección crítica al mismo tiempo: si p0 está en la sección crítica, entonces bandera[0] = 1, y ocurre que bandera[1] = 0, con lo que p1 ha terminado la sección crítica, o que la variable compartida turno = 0, con lo que p1 está esperando para entrar a la sección crítica. En ambos casos, p1 no puede estar en la sección crítica...




// Variables compartidas
bandera: array[0..N-1] of -1..n-2; /* inicializada a –1 */
turno: array[0..N-2] of 0..n-1; /* inicializada a 0 */

// Protocolo para Pi ( i=0,...,N-1 )
j:0..N-2; /* variable local indicando la etapa */
for j = 0 to N-2
{
bandera[i] = j;
turno[j] = i;
while [(∃ k ≠ i : bandera[k] ≥ j) ∧ (turno[k] == i)] do;
}
<sección crítica>
bandera[i] = -1;

Programacion Concurrente y Paralela

Objetivo:
Uno de los objetivos del sistema operativo es la representación de los procesos y el soporte de los cambios de contexto entre procesos, que posibilitan la compartición del recurso CPU.


Sirven:
Los algoritmos de exclusión mutua (comúnmente abreviada como mutex por mutual exclusion) se usan en programación concurrente para evitar el uso simultáneo de recursos comunes, como variables globales, por fragmentos de código conocidos como secciones críticas.



Exclusión mutua

La mayor parte de estos recursos son las señales, contadores, colas y otros datos que se emplean en la comunicación entre el código que se ejecuta cuando se da servicio a una interrupción y el código que se ejecuta el resto del tiempo. Se trata de un problema de vital importancia porque, si no se toman las precauciones debidas, una interrupción puede ocurrir entre dos instrucciones cualesquiera del código normal y esto puede provocar graves fallos.

La técnica que se emplea por lo común para conseguir la exclusión mutua es inhabilitar las interrupciones durante el conjunto de instrucciones más pequeño que impedirá la corrupción de la estructura compartida (la sección crítica). Esto impide que el código de la interrupción se ejecute en mitad de la sección crítica.

En un sistema multiprocesador de memoria compartida, se usa la operación indivisible test-and-set sobre una bandera, para esperar hasta que el otro procesador la despeje. La operación test-and-set realiza ambas operaciones sin liberar el bus de memoria a otro procesador. Así, cuando el código deja la sección crítica, se despeja la bandera. Esto se conoce como spin lock o espera activa.

Algunos sistemas tienen instrucciones multioperación indivisibles similares a las anteriormente descritas para manipular las listas enlazadas que se utilizan para las colas de eventos y otras estructuras de datos que los sistemas operativos usan comúnmente.

La mayoría de los métodos de exclusión mutua clásicos intentan reducir la latencia y espera activa mediante las colas y cambios de contexto. Algunos investigadores afirman que las pruebas indican que estos algoritmos especiales pierden más tiempo del que ahorran.


fuente:
buentastareas.com
wikipedia