Download programacion-concurrentetodo

PROGRAMACION CONCURRENTE
• La programació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 UCP (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 los nodos los procesos
coordinados de recursos que se comparten por tareas son
las claves de esta disciplina.
Multitarea, Multiprogramacion,
multiprocesos
La programación concurrente tiene capacidad para realizar
varias tareas al mismo tiempo o muchas tareas en una sola PC
con un procesador o varios.
Multitareas
• Es la capacidad de un sistema operativo para ejecutar varios
procesos al mismo tiempo corriendo sobre un procesador.
• Con los sistemas operativos DOS esto era incapaz de
realizarse.
• Existen varios tipos de multitareas y son :
* Multitarea Nula
* Multitarea Cooperativa
* Multitarea Preferente
* Multitarea Real
Multitarea Nula
ES aquel sistema operativo
que carece de multitarea.
Aún así puede simularla
implementándola en un
espacio
de
usuario
Justamente la familia DOS
son ejemplos de sistemas
operativos de multitarea
nula.
Multitarea Cooperativa
•
Tipo de multitarea en donde los
procesos de usuario son quienes
ceden la CPU al sistema operativo a
intervalos regulares.
Es sumamente problemático porque
si por algún motivo el proceso de
usuario es interrumpido, no cede la
CPU al sistema operativo que lo
ejecuta y, por lo tanto, quedará
trabado
(bloqueado).
Los sistemas operativos Windows
antes
de
la
versión
1995
implementaban
este
tipo
de
multitarea.
Multitarea Preferente
Multitarea en donde el SO se encarga de administrar uno o más
procesadores, repartiendo el tiempo de uso del mismo entre los distintos
procesos
que
esperan
utilizarlo
(tareas
en
ejecución).
En el caso de un solo procesador, cada proceso o tarea lo utiliza en
períodos cortísimos de tiempo, lo que, en la práctica, da la sensación de
que
estuviesen
ejecutándose
al
mismo
tiempo.
Los sistemas operativos que utilizan este tipo de multitareas son los UNIX
y
sus
clones
(Linux,
etc),
Windows
NT,
etc.
Multitarea Real
Multitarea en donde el SO ejecuta los procesos realmente al mismo
tiempo haciendo uso de múltiples procesadores (más de dos).
La ejecución realmente se realiza en distintos procesadores para cada
proceso o tarea. Obviamente en el caso de que los procesos o tareas sean
más que la cantidad de procesadores, éstos comienzan a ejecutarse en
procesadores "en uso" en la forma de multitareas preferente
Todos los sistemas operativos modernos soportan esta capacidad.
Multitarea Real
Multiprogramacion
• MULTIPROGRAMACION Es la técnica que permite que dos o mas
programas ocupen la misma unidad de memoria principal y que sean
ejecutados al mismo tiempo.
• La multiprogramación se refiere a dos o mas programas corriendo o
procesándose al mismo tiempo; La multiprogramación se controla a través
del sistema operativo, el cual observa los programas y los vigila hasta que
estén concluidos.
• El numero de programas que pueden multiprogramarse en forma efectiva,
depende de una combinación de la cantidad de memoria, de la velocidad
de la CPU y del numero y velocidad de los recursos periféricos que tenga
conectados, así como de la eficiencia del SISTEMA OPERATIVO.
Principios de Concurrencia
• En un sistema multiprogramado con un único procesador, los procesos se
intercalan en el tiempo aparentando una ejecución simultánea. Aunque
no se logra un procesamiento paralelo y produce una sobrecarga en los
intercambios de procesos, la ejecución intercalada produce beneficios en
la eficiencia del procesamiento y en la estructuración de los programas.
Principios de Concurrencia
• La concurrencia es el punto clave en los conceptos de multitarea,
multiprogramación y multiproceso, la concurrencia comprende un gran
numero de cuestiones de diseño incluyendo la comunicación entre
procesos, la compartición y competencia por los recursos, la
sincronización de la ejecución de varios procesos y la asignación del
procesador a los procesos, la concurrencia puede presentarse en tres
contextos diferentes:
• Varias aplicaciones:
• Aplicaciones estructuradas:
• Estructura del sistema operativo:
Varias aplicaciones:
En este caso el tiempo de procesador de una máquina es compartido
dinámicamente entre varios trabajos o aplicaciones activas.
Aplicaciones estructuradas:
Como consecuencia del diseño modular de una aplicación y la división de la misma
en tareas explícitas estas pueden ser ejecutadas de forma concurrente.
En programación, un lenguaje estructurado es aquel que soporta la división en
bloques (procedimientos y funciones) que pueden o no comunicarse entre sí.
Por ejemplo, los archivos batch (.bat) es contrario a inestructurado, de poco uso,
que no tiene ninguna estructura, es simplemente un “bloque”,
Estructura del sistema operativo:
Como resultado de las aplicaciones estructurada que se aplica en el diseño
del propio SO, de forma que este se implemente como un conjunto de
procesos.
LABORES DEL SISTEMA OPERATIVO
Son Elementos de gestión y diseño que surgen por causa de la
concurrencia:
1) El sistema operativo debe seguir a los distintos procesos activos
2) El sistema operativo debe asignar y retirar los distintos recursos a cada
proceso activo, entre estos se incluyen:
_Tiempo de procesador
_Memoria
_Archivos
_Dispositivos de E/S
3) El sistema operativo debe proteger los datos y los recursos físicos de
cada proceso contra injerencias no intencionadas de otros procesos.
4) Los resultados de un proceso deben ser independientes de la velocidad
a la que se realiza la ejecución de otros procesos concurrentes.
Puede verse la concurrencia de procesos como una ejecución
simultánea de varios procesos. Si tenemos un multiprocesador
la concurrencia parece clara, en un momento dado cada
procesador ejecuta un proceso.
•Se puede ampliar el concepto de concurrencia si entendemos
por procesado concurrente del sistema en conjunto,
•varios procesos se vean en un estado intermedio entre su
estado inicial y final. Esta última definición incluye los sistemas
multiprogramados de un único procesador que estudiamos en
los temas anteriores.
• Cooperación entre Procesos
La velocidad de un proceso depende de la frecuencia de la
interrupción asociada a cada uno de ellos que un proceso
se ejecuta asíncronamente con respecto a otro, es decir, sus
ejecuciones son independientes. Sin embargo, hay ciertos
instantes en lo que los procesos deben sincronizar sus
actividades. Son estos puntos a partir de los cuales un proceso
no puede progresar hasta que otro haya completado algún
tipo de actividad
Posibilidad de interacción de procesos
•
Las posibilidadades de interaccion de los procesos pueden clasificarse
en funcion del nivel de conocimiento que cada proceso requieren la
existencia de los demas.
1.
Un proceso no tiene en absoluto conocimiento de la existencia de los
demas
1.
Que los procesos tengan un conocimiento indirecto de los otros
procesos.
1.
Tiene lugar cuando los procesos tienen conocimiento directo unos de
otros por haber sido diseñados para trabajar conjuntamente el alguna
actividad
Comunicación y sincronización de proceso
1.
Necesidad de exclusión mutua. Es decir, los procesos deberán
acceder de forma exclusiva a ciertos recursos o zonas de
memoria considerados como críticos.
2.
Interbloqueos: tienen lugar cuando ninguno de los procesos en
competencia puede
continuar su ejecucion normal por carecer de alguno de los
recursos que necesita.
3.
3. ejecucion incompleto: este problema tiene lugar cuando la
ejecucion de un proceso queda siempre pospuesta a favor de
algun otro de los procesos en competencia.
Necesidad de sincronizacion de los procesos: region
crıtica y
exclusion mutua
• La sincronización entre procesos puede definirse como la
necesidad que tienen algunos procesos de bloquearse en
determinadas circunstancias y ser despertados cuando
ocurren ciertos eventos. Un caso típico que muestra la
necesidad de sincronización entre procesos es cuando un
proceso inicia una lectura y va a utilizar en la siguiente
instrucción la información leída. En este caso el proceso
debe esperar a que se termine la operación de
Entrada/Salida para continuar.
Gestion de procesos
ejecucion
LA EXCLUSION MUTUA
La exclusión mutua la podríamos definir como una
operación de control que permite la coordinación de
procesos concurrentes (Comunicación requerida entre
dos o mas procesos), y que tiene la capacidad de
prohibir a los demás procesos realizar una acción
cuando un proceso haya obtenido el permiso.
SOLUCIONES SOFTWARE PARA LA EXCLUSION MUTUA
Soluciones por Software. Una manera es dejar la responsabilidad
a los procesos que deseen ejecutar concurrentemente, de esta
manera los procesos deben coordinarse unos con otros para
cumplir
la exclusión mutua sin ayuda alguna, aunque estas soluciones son
propensas a errores y a una fuerte carga de proceso (Algunos
ejemplos
de estas son: Algoritmo de Dekker y Algoritmo de Peterson).
 Algoritmo de Dekker
 Algoritmo de Peterson
 Semáforos
 Monitores
 Paso de Mensajes
 Soluciones Hardware para la exclusión mutua
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 Diikstra.
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 Dekker
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 .En el algoritmo para N procesos las variables c[i] además
de valer "verdadero" y "falso", pueden valer "en sección critica" y turno
desde 1 hasta N.
El procedimiento es una generalización de este .c[i], que es un array y
turno, que solo puede valer 1o 2 .
.Este algoritmo garantiza la exclusión mutua debido al uso de una
variable compartida , turno, que se chequea cada vez.
Inicialmente, c[0]=c[1]= falso, y el valor de turno no tiene relevancia
(pero de be ser 0 o 1). Para entrar en la sección crítica, el proceso Pi
primero asigna el valor verdadero a c[i] y luego afirma que es el turno
del otro proceso para entrar si así lo desea (turno = j). Si ambos
procesos tratan de entrar a la vez, se asignará turno como i y j
aproximadamente al mismo tiempo. Sólo una de estas asignaciones
durará; la otra ocurrirá, pero será reemplazada de inmediato. El valor
eventual de turno decide a cuál de los dos procesos se le permitirá
entrar primero en su sección crítica.