Apoyo del tema en html
http://www.depi.itchihuahua.edu.mx/apacheco/lengs/paralelo/index.html
viernes, 22 de mayo de 2009
Introduccion
La computación concurrente es la simultaneidad en la ejecución de múltiples tareas interactivas. Estas tareas pueden ser un conjunto de procesos o hilos de ejecución creados por un único programa. Las tareas se pueden ejecutar en un sola unidad central de proceso (multiprogramación), en varios procesadores o en una red de computadores distribuidos. La programación concurrente está relacionada con la programación paralela, pero enfatiza más la interacción entre tareas. Así, la correcta secuencia de interacciones o comunicaciones entre los procesos y el acceso coordinado de recursos que se comparten por todos los procesos o tareas son las claves de esta disciplina.
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 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 critica.• 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.
Algoritmo 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 que funcione para N procesos.
jueves, 21 de mayo de 2009
miércoles, 20 de mayo de 2009
Semaforo
Un semáforo binario es un indicador (S) de condición que registra si un recurso está disponible o no. Un semáforo binario sólo puede tomar dos valores: 0 y 1. Si, para un semáforo binario, S = 1 entonces el recurso está disponible y la tarea lo puede utilizar; si S = 0 el recurso no está disponible y el proceso debe esperar.Los semáforos se implementan con una cola de tareas o de condición a la cual se añaden los procesos que están en espera del recurso.
En algunos textos, se utilizan las notaciones P y V para las operaciones de espera y señal respectivamente, ya que ésta fue la notación empleada originalmente por Dijkstra (el creador de la solución) para referirse a las operaciones.
En algunos textos, se utilizan las notaciones P y V para las operaciones de espera y señal respectivamente, ya que ésta fue la notación empleada originalmente por Dijkstra (el creador de la solución) para referirse a las operaciones.
Uso del semaforo
Los semáforos se emplean para permitir el acceso a diferentes partes de programas (llamados secciones críticas) donde se manipulan variables o recursos que deben ser accedidos de forma especial. Según el valor con que son inicializados se permiten a más o menos procesos utilizar el recurso de forma simultánea.
Un tipo simple de semáforo es el binario, que puede tomar solamente los valores 0 y 1. Se inicializan en 1 y son usados cuando sólo un proceso puede acceder a un recurso a la vez.
Cuando el recurso está disponible, un proceso accede y decrementa el valor del semáforo con la operación P. El valor queda entonces en 0, lo que hace que si otro proceso intenta decrementarlo tenga que esperar. Cuando el proceso que decrementó el semáforo realiza una operación V, algún proceso que estaba esperando puede despertar y seguir ejecutando.
Para hacer que dos procesos se ejecuten en una secuencia predeterminada puede usarse un semáforo inicializado en 0. El proceso que debe ejecutar primero en la secuencia realiza la operación V sobre el semáforo antes del código que debe ser ejecutado después del otro proceso. Éste ejecuta la operación P. Si el segundo proceso en la secuencia es programado para ejecutar antes que el otro, al hacer P dormirá hasta que el primer proceso de la secuencia pase por su operación V. Este modo de uso se denomina señalación (signaling), y se usa para que un proceso o hilo de ejecución le haga saber a otro que algo ha sucedido
Un tipo simple de semáforo es el binario, que puede tomar solamente los valores 0 y 1. Se inicializan en 1 y son usados cuando sólo un proceso puede acceder a un recurso a la vez.
Cuando el recurso está disponible, un proceso accede y decrementa el valor del semáforo con la operación P. El valor queda entonces en 0, lo que hace que si otro proceso intenta decrementarlo tenga que esperar. Cuando el proceso que decrementó el semáforo realiza una operación V, algún proceso que estaba esperando puede despertar y seguir ejecutando.
Para hacer que dos procesos se ejecuten en una secuencia predeterminada puede usarse un semáforo inicializado en 0. El proceso que debe ejecutar primero en la secuencia realiza la operación V sobre el semáforo antes del código que debe ser ejecutado después del otro proceso. Éste ejecuta la operación P. Si el segundo proceso en la secuencia es programado para ejecutar antes que el otro, al hacer P dormirá hasta que el primer proceso de la secuencia pase por su operación V. Este modo de uso se denomina señalación (signaling), y se usa para que un proceso o hilo de ejecución le haga saber a otro que algo ha sucedido
Problema del barbero durmiente
Problema del barbero durmiente
En ciencias de la computación, el problema del barbero durmiente es un problema de sincronización. El problema consiste en una barbería en la que trabaja un barbero que tiene un único sillón de barbero y varias sillas para esperar. Cuando no hay clientes, el barbero se sienta en una silla y se duerme. Cuando llega un nuevo cliente, éste o bien despierta al barbero o si el barbero está afeitando a otro cliente se sienta en una silla (o se va si todas las sillas están ocupadas por clientes esperando). El problema consiste en realizar la actividad del barbero sin que ocurran condiciones de carrera. La solución implica el uso de semáforos
Un semáforo es una variable protegida (o tipo abstracto de datos) que constituye el método clásico para restringir o permitir el acceso a recursos compartidos (por ejemplo, un recurso de almacenamiento) en un entorno de multiprocesamiento. Fueron inventados por Edsger Dijkstra y se usaron por primera vez en el sistema operativo THEOS.
En electrónica y en programación concurrente, se conoce como condición de carrera al error que se produce en programas o circuitos lógicos que no se han construido adecuadamente para su ejecución simultánea con otros procesos.
Como se usa
El próximo codigo garantiza la sincronización entre el barbero y el cliente, pero puede llevar a que el cliente se quede sin silla. P() y V() son funciones provistas por el semáforo.
Se necesita:
+ semaforo Cliente = 0
+ semaforo Barbero = 0
+ semaforo SillasAccesibles = 1 //MUTEX = objetos de exclusión mutua
+ int SillasLibres = N //nro total de sillas
Función barbero (Proceso/hilo-thread):
while(true) { //ciclo infinito
P(Cliente) //si no tiene cliente se duerme
P(SillasAccesibles) //ya está despierto y quiere modificar el nro de sillas
SillasLibres++ //queda disponible una silla
V(Barbero) // el Barbero está listo para cortar
V(SillasAccesibles) //no se necesitan bloquear las sillas
//el barbero corta el pelo, zona de código no crítico
}
Función cliente (Proceso/hilo-thread):
P(SillasAccesibles) //trata de acceder a una silla
if ( SillasLibres > 0 ) { //si hay sillas libres
SillasLibres -- //se sienta en una
V(Cliente) //avisa al barbero, el cual está esperando, que haya un cliente
V(SillasAccesibles) // no se necesitan bloquear las sillas
P(Barbero) // ahora le toca al cliente, pero espera si el barbero está ocupado
//se le está cortando el pelo al cliente
} else { // no hay sillas libres
V(SillasAccesibles) //libero el bloqueo de las sillas
//se va de la barbería
}
En ciencias de la computación, el problema del barbero durmiente es un problema de sincronización. El problema consiste en una barbería en la que trabaja un barbero que tiene un único sillón de barbero y varias sillas para esperar. Cuando no hay clientes, el barbero se sienta en una silla y se duerme. Cuando llega un nuevo cliente, éste o bien despierta al barbero o si el barbero está afeitando a otro cliente se sienta en una silla (o se va si todas las sillas están ocupadas por clientes esperando). El problema consiste en realizar la actividad del barbero sin que ocurran condiciones de carrera. La solución implica el uso de semáforos
Un semáforo es una variable protegida (o tipo abstracto de datos) que constituye el método clásico para restringir o permitir el acceso a recursos compartidos (por ejemplo, un recurso de almacenamiento) en un entorno de multiprocesamiento. Fueron inventados por Edsger Dijkstra y se usaron por primera vez en el sistema operativo THEOS.
En electrónica y en programación concurrente, se conoce como condición de carrera al error que se produce en programas o circuitos lógicos que no se han construido adecuadamente para su ejecución simultánea con otros procesos.
Como se usa
El próximo codigo garantiza la sincronización entre el barbero y el cliente, pero puede llevar a que el cliente se quede sin silla. P() y V() son funciones provistas por el semáforo.
Se necesita:
+ semaforo Cliente = 0
+ semaforo Barbero = 0
+ semaforo SillasAccesibles = 1 //MUTEX = objetos de exclusión mutua
+ int SillasLibres = N //nro total de sillas
Función barbero (Proceso/hilo-thread):
while(true) { //ciclo infinito
P(Cliente) //si no tiene cliente se duerme
P(SillasAccesibles) //ya está despierto y quiere modificar el nro de sillas
SillasLibres++ //queda disponible una silla
V(Barbero) // el Barbero está listo para cortar
V(SillasAccesibles) //no se necesitan bloquear las sillas
//el barbero corta el pelo, zona de código no crítico
}
Función cliente (Proceso/hilo-thread):
P(SillasAccesibles) //trata de acceder a una silla
if ( SillasLibres > 0 ) { //si hay sillas libres
SillasLibres -- //se sienta en una
V(Cliente) //avisa al barbero, el cual está esperando, que haya un cliente
V(SillasAccesibles) // no se necesitan bloquear las sillas
P(Barbero) // ahora le toca al cliente, pero espera si el barbero está ocupado
//se le está cortando el pelo al cliente
} else { // no hay sillas libres
V(SillasAccesibles) //libero el bloqueo de las sillas
//se va de la barbería
}
Ejemplo concurrencia
Este es un ejemplo de declaración de procesos en el lenguaje Pascal-FC.
La concurrencia puede ser pesada (procesos) o ligera (hilos). En el primer caso, un proceso es una entidad que, en los sistemas multitarea, conforma una ejecución concreta de programa, mientras que en el segundo, un hilo es una secuencia de control dentro de un proceso ejecutando sus instrucciones independientemente.
Como podremos comprobar, en los ejemplos se omite cualquier referencia a dicho lenguaje y se abordan los ejemplos directamente. La idea no es aprender Pascal-FC, sino aprender más sobre la programación concurrente.
El ejemplo es un "Hola Mundo" un tanto especial:
program declaraprocesos;
(* las siguientes instrucciones declaran los procesos, que en Pascal-FC van en la zona de declaración de tipos *)
process Hola;
var i: integer;
begin
for i:= 1 to 10 do
writeln('Hola')
end;
process Mundo;
var i: integer;
begin
for i:= 1 to 10 do
writeln('Mundo')
end;
(* Inicio del programa *)
begin
writeln('esto es en secuencial');
(* dentro de cobegin ... coend tenemos aquellos procesos que se ejecutan de forma concurrente *)
cobegin
Hola;
Mundo;
coend;
writeln('también en secuencial');
end.
Como vemos, tanto el "Hola" como el "Mundo" se imprimirán concurrentemente en pantalla, ya que están en procesos independientes. Un posible resultado es algo así:
esto es en secuencial
Hola
Mundo
Hola
Hola
Mundo
Mundo
Hola
Mundo
Mundo
Mundo
Hola
Mundo
Mundo
Hola
Hola
Hola
Hola
Hola
Mundo
Mundo
también en secuencial
Digo posible resultado ya que, si vuelvo a ejecutar el mismo código puedo obtener un resultado diferente, como por ejemplo
esto es en secuencial
Hola
Mundo
Mundo
Mundo
Hola
Mundo
Mundo
Mundo
Mundo
Hola
Hola
Mundo
Mundo
Mundo
Hola
Hola
Hola
Hola
Hola
Hola
también en secuencial
Podría ejecutar más veces el mismo código sin tener porqué dar el mismo resultado. A esta propiedad se le denomina comportamiento indeterminista de los programas concurrentes, y consiste en que un mismo programa puede dar resultados diferentes cuando se ejecuta repetidamente sobre los mismos datos de entrada.
La concurrencia puede ser pesada (procesos) o ligera (hilos). En el primer caso, un proceso es una entidad que, en los sistemas multitarea, conforma una ejecución concreta de programa, mientras que en el segundo, un hilo es una secuencia de control dentro de un proceso ejecutando sus instrucciones independientemente.
Como podremos comprobar, en los ejemplos se omite cualquier referencia a dicho lenguaje y se abordan los ejemplos directamente. La idea no es aprender Pascal-FC, sino aprender más sobre la programación concurrente.
El ejemplo es un "Hola Mundo" un tanto especial:
program declaraprocesos;
(* las siguientes instrucciones declaran los procesos, que en Pascal-FC van en la zona de declaración de tipos *)
process Hola;
var i: integer;
begin
for i:= 1 to 10 do
writeln('Hola')
end;
process Mundo;
var i: integer;
begin
for i:= 1 to 10 do
writeln('Mundo')
end;
(* Inicio del programa *)
begin
writeln('esto es en secuencial');
(* dentro de cobegin ... coend tenemos aquellos procesos que se ejecutan de forma concurrente *)
cobegin
Hola;
Mundo;
coend;
writeln('también en secuencial');
end.
Como vemos, tanto el "Hola" como el "Mundo" se imprimirán concurrentemente en pantalla, ya que están en procesos independientes. Un posible resultado es algo así:
esto es en secuencial
Hola
Mundo
Hola
Hola
Mundo
Mundo
Hola
Mundo
Mundo
Mundo
Hola
Mundo
Mundo
Hola
Hola
Hola
Hola
Hola
Mundo
Mundo
también en secuencial
Digo posible resultado ya que, si vuelvo a ejecutar el mismo código puedo obtener un resultado diferente, como por ejemplo
esto es en secuencial
Hola
Mundo
Mundo
Mundo
Hola
Mundo
Mundo
Mundo
Mundo
Hola
Hola
Mundo
Mundo
Mundo
Hola
Hola
Hola
Hola
Hola
Hola
también en secuencial
Podría ejecutar más veces el mismo código sin tener porqué dar el mismo resultado. A esta propiedad se le denomina comportamiento indeterminista de los programas concurrentes, y consiste en que un mismo programa puede dar resultados diferentes cuando se ejecuta repetidamente sobre los mismos datos de entrada.
Suscribirse a:
Entradas (Atom)
