Concurrencia
Es la existencia de varias actividades ejecutándose simultáneamente, y necesitan
sincronizarse para actuar conjuntamente. Se trata, en este caso, de un concepto lógico, ya
que sólo hace referencia a las actividades, sin importar el número de procesadores
presentes.
Para que dos actividades, sean concurrentes, es necesario que tengan relación
entre sí, como puede ser la cooperación en un trabajo determinado o el uso de información
compartida.
Si un sistema es multiprocesador, también pueden presentarse situaciones de
concurrencia siempre y cuando las actividades necesiten actuar entre sí, bien por utilizar
información común, o por cualquier otra causa.
Los procesos del sistema pueden ejecutarse concurrentemente, puede haber
múltiples tareas en el CPU con varios procesos. Existen varias razones para permitir la
ejecución concurrente:
Compartir recursos físicos: Ya que los recursos del hardware de la computadora
son limitados, nos podemos ver obligados a compartirlos en un entorno multiusuario.
Compartir recursos lógicos: Puesto que varios usuarios pueden interesarse en el
mismo elemento de información (por ejemplo un archivo compartido), debemos
proporcionar un entorno que permita el acceso concurrente a estos tipos de recursos.
Acelerar los cálculos: Si queremos que una tarea se ejecute con mayor rapidez,
debemos dividirla en subtareas, cada una de las cuales se ejecutara, en paralelo con
las demás.
Modularidad: Podremos construir el sistema en forma modular, dividiendo las
funciones del sistema en procesos separados.
Comodidad: Un usuario puede tener que ejecutar varias tareas a la vez, por ejemplo
puede editar, imprimir y compilar en paralelo.
La ejecución concurrente que requiere la cooperación entre procesos necesita un
mecanismo para la sincronización y comunicación de procesos, exclusión mutua y
sincronización.
PROBLEMAS DE CONCURRENCIA
En los sistemas de tiempo compartido (aquellos con varios usuarios, procesos, tareas,
trabajos que reparten el uso de CPU entre estos) se presentan muchos problemas debido
a que los procesos compiten por los recursos del sistema. Imagine que un proceso está
escribiendo en la unidad de cinta y se le termina su turno de ejecución e inmediatamente
después el proceso elegido para ejecutarse comienza a escribir sobre la misma cinta. El
resultado es una cinta cuyo contenido es un desastre de datos mezclados. Así como la cinta,
existen una multitud de recursos cuyo acceso debe der controlado para evitar los problemas
de la concurrencia.
El sistema operativo debe ofrecer mecanismos para sincronizar la ejecución de procesos:
semáforos, envío de mensajes, 'pipes', etc. Los semáforos son rutinas de software (que en
su nivel más interno se auxilian del hardware) para lograr exclusión mutua en el uso de
recursos. Para entender este y otros mecanismos es importante entender los problemas
generales de concurrencia, los cuales se describen enseguida.
Condiciones de Carrera o Competencia: La condición de carrera (race condition)
ocurre cuando dos o más procesos accesan un recurso compartido sin control, de
manera que el resultado combinado de este acceso depende del orden de llegada.
Suponga, por ejemplo, que dos clientes de un banco realizan cada uno una operación
en cajeros diferentes al mismo tiempo.
El usuario A quiere hacer un depósito. El B un retiro. El usuario A comienza la transacción
y lee su saldo que es 1000. En ese momento pierde su turno de ejecución (y su saldo queda
como 1000) y el usuario B inicia el retiro: lee el saldo que es 1000, retira 200 y almacena el
nuevo saldo que es 800 y termina. El turno de ejecución regresa al usuario A el cual hace
su depósito de 100, quedando saldo = saldo + 100 = 1000 + 100 = 1100. Como se ve, el
retiro se perdió y eso le encanta al usuario A y B, pero al banquero no le convino esta
transacción. El error pudo ser al revés, quedando el saldo final en 800.
Postergación o Aplazamiento Indefinido(a): Esto se mencionó en el apartado
anterior y consiste en el hecho de que uno o varios procesos nunca reciban el
suficiente tiempo de ejecución para terminar su tarea. Por ejemplo, que un proceso
ocupe un recurso y lo marque como 'ocupado' y que termine sin marcarlo como
'desocupado'. Si algún otro proceso pide ese recurso, lo verá 'ocupado' y esperará
indefinidamente a que se 'desocupe'.
Condición de Espera Circular: Esto ocurre cuando dos o más procesos forman una
cadena de espera que los involucra a todos. Por ejemplo, suponga que el proceso A
tiene asignado el recurso 'cinta' y el proceso B tiene asignado el recurso 'disco'. En
ese momento al proceso A se le ocurre pedir el recurso 'disco' y al proceso B el
recurso 'cinta'. Ahi se forma una espera circular entre esos dos procesos que se
puede evitar quitándole a la fuerza un recurso a cualquiera de los dos procesos.
Condición de No Apropiación: Esta condición no resulta precisamente de la
concurrencia, pero juega un papel importante en este ambiente. Esta condición
especifica que si un proceso tiene asignado un recurso, dicho recurso no puede
arrebatársele por ningún motivo, y estará disponible hasta que el proceso lo 'suelte'
por su voluntad.
Condición de Espera Ocupada: Esta condición consiste en que un proceso pide un
recurso que ya está asignado a otro proceso y la condición de no apropiación se debe
cumplir. Entonces el proceso estará gastando el resto de su time slice checando si el
recurso fue liberado. Es decir, desperdicia su tiempo de ejecución en esperar. La
solución más común a este problema consiste en que el sistema operativo se dé
cuenta de esta situación y mande a una cola de espera al proceso, otorgándole
inmediatamente el turno de ejecución a otro proceso.
Condición de Exclusión Mutua: Cuando un proceso usa un recurso del sistema
realiza una serie de operaciones sobre el recurso y después lo deja de usar. A la
sección de código que usa ese recurso se le llama 'región crítica'. La condición de
exclusión mutua establece que solamente se permite a un proceso estar dentro de la
misma región crítica. Esto es, que en cualquier momento solamente un proceso
puede usar un recurso a la vez. Para lograr la exclusión mutua se ideo también el
concepto de 'región crítica'. Para logar la exclusión mutua generalmente se usan
algunas técnicas para lograr entrar a la región crítica: semáforos, monitores, el
algoritmo de Dekker y Peterson, los 'candados'. Para ver una descripción de estos
algoritmos consulte
Condición de Ocupar y Esperar un Recurso: Consiste en que un proceso pide un
recurso y se le asigna. Antes de soltarlo, pide otro recurso que otro proceso ya tiene
asignado.
Los problemas descritos son todos importantes para el sistema operativo, ya que debe ser
capaz de prevenir o corregirlos. Tal vez el problema más serio que se puede presentar en
un ambiente de concurrencia es el 'abrazo mortal', también llamado 'trabazón' y en inglés
deadlock. El deadlock es una condición que ningún sistema o conjunto de procesos quisiera
exhibir, ya que consiste en que se presentan al mismo tiempo cuatro condiciones
necesarias: La condición de no apropiación, la condición de espera circular, la condición de
exclusión mutua y la condición de ocupar y esperar un recurso. Ante esto, si el deadlock
involucra a todos los procesos del sistema, el sistema ya no podrá hacer algo productivo. Si
el deadlock involucra algunos procesos, éstos quedarán congelados para siempre.
Exclusión mutua de secciones criticas
Forma de asegurar que si un proceso está usando una variable o archivo compartido, los
otros procesos quedarán excluidos de hacer lo mismo.
Los procesos pueden tener en su código secciones en que realizan cálculos internos y
operaciones que no dan lugar a condiciones de competencia. Sin embargo existen
secciones de programa en que el proceso está accediendo a recursos compartidos que
pueden dar pié a condiciones de competencia.
La parte del programa en que se accede a un recurso compartido se denomina sección o
región crítica (requisito necesario, pero no suficiente). Los requisitos para que procesos
paralelos cooperen de manera correcta usando datos compartidos son los siguientes:
Dos procesos nunca pueden estar simultáneamente dentro de sus regiones críticas.
No se puede suponer nada acerca de las velocidades de ejecución de los procesos
o el número de las CPU.
Ningún proceso que se ejecute fuera de su región crítica puede bloquear a otros
procesos.
Ningún proceso deberá tener una espera indefinida para entrar en su región crítica.
La exclusión mutua debe ponerse en práctica sólo cuando los procesos obtienen acceso a
datos compartidos modificables; cuando los procesos realizan operaciones que no entran
en conflicto con otras, deben permitirse que procedan concurrentemente. Cuando un
proceso obtiene acceso a datos compartidos modificables, se dice que se encuentra en
una sección crítica. Es evidente que, para evitar la clase de problemas observados en la
sección anterior, debe asegurarse que cuando un proceso se encuentre en una sección
crítica, los demás procesos (o al menos los que tengan acceso a los datos compartidos) no
pueden entrar a sus propias secciones críticas.
Mientras un proceso se encuentra en su sección crítica, otros procesos pueden, claro está,
seguir ejecutándose fuera de sus secciones críticas. Cuando un proceso abandona su
región crítica, otro proceso que espera entrar en su propia sección crítica (si existe algún
proceso en espera). Lograr que se cumpla la exclusión mutua es uno de los problemas
fundamentales de la programación concurrente. Se han propuesto muchas soluciones,
algunas de software y otras de hardware, algunas sencillas y otras complejas, y algunas
que requieren la cooperación voluntaria de los procesos y otras que exigen un escrito ajuste
a rígidos protocolos.
Encontrarse dentro de una región crítica es un estado especial concedido a un proceso. El
proceso tiene acceso exclusivo a los datos compartidos y los demás procesos que requieran
acceso a los datos en ese momento deben esperar. Así pues, las secciones críticas deben
ejecutarse tan rápido como sea posible; un proceso no se debe bloquear dentro de su propia
sección crítica y las secciones críticas deben codificarse con mucho cuidado (para evitar,
por ejemplo, la posibilidad de ciclos infinitos).
Si un proceso de una sección crítica termina, ya sea voluntaria o involuntariamente, el
sistema operativo, al realizar su mantenimiento de terminaciones, debe liberar la exclusión
mutua de manera que otros procesos puedan entrar en sus regiones críticas.
En el momento de un cambio de proceso del uno al otro se pueden producir las siguientes
situaciones:
Sin sincronización entre procesos: Puede darse el caso de que ESCRIBIR esté
actualizando un registro y se quede a medías, sorprendiéndole el cambio de proceso,
por tanto, terminará de escribirlo cuando vuelva a hacer uso del procesador. Con el cambio le tocará el turno al proceso LEER, que accederá a dicho registro pudiendo
leerlo completamente. Es evidente que los datos leídos serán inconsistentes.
Con sincronización entre procesos: Supongamos algún mecanismo que prohíba
la lectura (bloqueo de registros) a cualquier proceso, mientras el proceso ESCRIBIR
esté realizando alguna operación. En este caso, LEER, al hacer uso del procesador
que se encuentra bloqueado, quedaría en espera de que el registro quede totalmente
escrito y se proceda a su desbloqueo, LEER pasaría a estado bloqueado, ESCRIBIR
terminaría su trabajo sobre el registro y en el siguiente cambio LEER procedería a
hacer el suyo.
Esta sincronización por la cual una actividad impide que otras puedan tener acceso
a un dato mientras se encuentra realizando una operación sobre el mismo es lo que se
conoce como exclusión mutua.
La zona de código de un proceso que no puede ser interrumpida por otro, por los
motivos expuestos anteriormente se le llama Región Crítica.
Regiones críticas
Es el conjunto de actividades elementales cuya ejecución exige el monopolio de recursos.
Por ejemplo, para indicar que alguna acción se realizará con acceso exclusivo a ciertos
datos compartidos.
Región datos - compartidos do acción
¿Como evitar la región critica?. La clave para prevenir el problema aquí y en
muchas otras situaciones en que interviene la memoria compartida, archivos compartidos y
todo lo que se comparte, consiste en determinar alguna manera de prohibir que un proceso
lea y escriba los datos compartidos al mismo tiempo.
De otra manera lo que se necesita es la sincronización. Una manera de asegurar de que si
un proceso ésta utilizando una variable o archivo compartido, es que los otros procesos no
pueden hacer lo mismo.
Para tener una solución adecuada a la región crítica se necesita que se cumplan cuatro
condiciones.
1. Nunca dos procesos pueden encontrarse simultáneamente dentro de sus regiones
críticas.
2. No se hacen suposiciones acerca de las velocidades relativas de los procesos o
del Número de CPU.
3. Ningún proceso suspendido fuera de la región crítica debe bloquear a otros procesos.
4. Nunca un proceso debe querer entrar en forma arbitraria en su región crítica.
Representación de regiones criticas
Cuando se diseña un proceso que debe contener una o varias regiones críticas se
deben de tomar en cuenta las siguientes consideraciones:
La región crítica debe ser ejecutada lo más rápido posible.
Un programa no debe ínter bloquearse en una región crítica.
Las regiones críticas deben ser programadas con mucho cuidado (no se
permiten Ciclos indefinidos).
Mientras un proceso está en su región crítica otros procesos pueden continuar
Ejecutándose fuera de las regiones críticas.
Cuando se tienen procesos que comparten datos, si un proceso deja la región
Crítica otro de los procesos que espera a entrar en su región crítica puede proceder.
Cuando el proceso termina, voluntaria o involuntariamente, el sistema operativo debe de
realizar la limpieza propia de fin de proceso y liberar la exclusión mutua de otros procesos
El problema de la Sección Crítica
En procesos compitiendo para utilizar algún dato compartido.
Cada proceso tiene un segmento de código, llamado sección crítica, en el que se
accede al dato compartido.
Problema – asegurarse de que cuando un proceso esta ejecutándose en su sección
crítica, a ningún otro proceso se le permite ejecutar la suya.
Estructura del proceso Pi
repeat
entry section
sección crítica
exit section
sección restante
until false;
Solución al problema de la Sección Crítica
Una solución al problema de la sección crítica debe satisfacer los siguientes tres
requerimientos:
1. Exclusión Mútua. Si un proceso Pi esta ejecutándose en su sección crítica,
entonces ninguno de los otros procesos puede estar en su sección crítica.
2. Progreso. Si ningún proceso esta ejecutándose en su sección crítica y existen
procesos que quieren entrar en su sección crítica, entonces la selección del
próximo proceso que entrará a la sección crítica no puede ser pospuesta
indefinidamente.
3. Espera limitada. Debe existir un límite del número de veces que se les
permite a otros procesos entrar en sus secciones críticas en el intervalo entre
que un proceso ha hecho un requerimiento para entrar en su sección crítica y
que se le concede el permiso.
Se supone que cada proceso se ejecuta a velocidad distinta de cero.
Ninguna suposición respecto a la velocidad relativa de los n procesos.
No hay comentarios.:
Publicar un comentario