Scribd
Cargar
274 vistas12 páginas

Algoritmos de Programación Concurrente

Este documento proporciona una introducción a la programación concurrente. Explica que los programas concurrentes permiten la ejecución en paralelo de declaraciones e instrucciones a través de procesos múltiples, a diferencia de la ejecución secuencial en programas ordinarios. También destaca la importancia de la sincronización entre procesos para evitar conflictos al acceder recursos compartidos, y presenta algoritmos como Bully y Ring para la elección de un coordinador entre procesos. Finalmente, introduce conceptos como los algoritmos de consenso para log

Cargado por

Jesseliz Choque
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPT, PDF, TXT o lee en línea desde Scribd
274 vistas12 páginas

Algoritmos de Programación Concurrente

Este documento proporciona una introducción a la programación concurrente. Explica que los programas concurrentes permiten la ejecución en paralelo de declaraciones e instrucciones a través de procesos múltiples, a diferencia de la ejecución secuencial en programas ordinarios. También destaca la importancia de la sincronización entre procesos para evitar conflictos al acceder recursos compartidos, y presenta algoritmos como Bully y Ring para la elección de un coordinador entre procesos. Finalmente, introduce conceptos como los algoritmos de consenso para log

Cargado por

Jesseliz Choque
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPT, PDF, TXT o lee en línea desde Scribd

QU ES PROGRAMACIN

CONCURRENTE?
Programa ordinario

Ejecucin Secuencial

Declaraciones
.
.
.
Instrucciones

Programa Concurrente

Declaraciones Declaraciones
.
.
.

.
.
.

Instrucciones

Instrucciones

Declaraciones

...

.
.
.
Instrucciones

Ejecucin en Paralelismo Abstracto

SINCRONISMO

Es importante que:
Varios

procesos no accesen a un recurso compartido


al mismo tiempo
Aceso exclusivo temporal

Algunos procesos pueden necesitar ponerse


deacuerdo en el orden de ejecucin de ciertos
eventos

ALGORITMOS DE ELECCIN
Se

requiere de un processo que actue como:

Coordinador
Iniciador
Ejecute

El

algun rol especial

objetivo de la eleccin es que cuando la


misma concluya, todos los procesos debe estar
de acuerdo en quien debe ser el coordinador
Bully Algorithm Algoritmo Abusn
Ring Algorithm Algoritmo basado en anillo

BULLY ALGORITHM
Garcia-Molina 1982
Sistema Sncrono

T = 2*Ttrans + TProcesa

Permite la caida de
procesos durante eleccin
Construccin de detector
de fallas

Coordinador
Ok
Ok in
cc
e
l
E

ci

ID de los mayores

ec

Ele
Ok
cci

El

Conocimiento de los otros


procesos

Eleccin

Timouts para fallas

X
7

RING ALGORITHM

Se elige el proceso
con identificador mas
grande

[5,3,4,1,2,
[5,3,4,1] 6,0]

[5,3,4,1,2,
6,0]
[5,3]

[5,3,4,1,2,
6,0
[5,3,4,1,2

3
]

6
,1
,2
,6

No hay fallas
Sistema asncrono

[5,3,4,1,2,
6,0]
[5,3,4]

[5]
[5,3,4,1,2,6
,0]
5
[5,3,4,1,2,6,0]
[5,3,4,1,2,
6,0]

[5
,3
,4

Chang y Roberts
1979
pi tiene un canal de
comunicacin con el
siguiente proceso del
anillo, p(i+1) mod N
Supuestos

X6
7

[5,3,4,1,2, 6,0]
0

ALGORITMOS DE CONSENSO
Consenso frente a cadas o fallas bizantinas
Cuando existe replicacin se debe llegar a un consenso
para saber que informacin se envia
Problemas:

Sensores replicados no necesariamente dan el mismo valor


Sensor malogrado o procesador que falla

Cada proceso elige un valor inicial y


Se requiere que todos los procesos decidan por uno de esos
valores

Como lograr consenso


Fallas

Por cadas: proceso no envia mensajes


Bizantinas: proceso envia mensajes arbitrarios

Algoritmo de una ronda


Algoritmo de los generales bizantinos
Algoritmo del rey (King Algorithm)

ALGORITMO DE UNA RONDA


Si unos cuantos caen no se
llega a consenso
Cada uno hace su tabla de
valores escojidos por los
otros

1
A

2
-AB
B

A B

A
B

3
AAB
A

ALGORITMO DE LOS
GENERALES BIZANTINOS
Se ejecutan mas rondas
Primera ronda: igual a
anterior
Segunda Ronda: enviar a
cada proceso la eleccin de
los otros

3:B

2:A
A

A B

B
[Link]
AAB

AAB

ALGORITMO DEL REY

A:1
A:1
B:1
B:0

Requiere menos mensajes que el


algoritmo de los generales
bizantinos
En cada ronda un proceso recibe
el titulo de rey y su voto vale
mas
Algoritmo
Cada general almacena el voto
de la mayoria en la primera
ronda
Segunda ronda:

Cuando el nodo recibe el plan del


rey

Si mi mayoria es amplia: >(n/2)+1


considerar mi voto mayoria
Caso contrario considerar voto del
rey

Tercera ronda:

Repetir segunda ronda con otro


rey

1
A

B
2

B
A

A:1
A:1
B:0
B:1 B

A:1
B:0
B:1

B
4

A:1
B:1
B:0

A:1
B:0
B:1

BIBLIOGRAFIA UTILIZADA

Distributed Systems: Principles and Paradigms


(Prentice Hall)
Andrew

S. Tanembaum
Maarten Van Sten

Principles of Concurrent and Distributed


Programming (Adison Wesley)
M.

Ben-Ari

TRABAJO EN GRUPO (GRUPOS DE 4)

Realizar un trabajo sobre programacin con


hebras en:
Java
C++

con POSIX Threads sobre Linux


Las librerias process.h y windows.h para C/C++ en
Windows
La MFC de Microsoft Visual Studio

Presentar un informe
Realizar una presentacin con Slides, la cual ser
expuesta por un miembro del grupo elegido al
azar.

TAREA ADICIONAL
ALGORITMO DE ROUND ROBIN
ALGORITMO DE FIFO
ALGORITMO SCHEDULING
FIFO
RONROBIN
BULLY

También podría gustarte