2.4 Concurrencia y secuenciabilidad.
2.4 Concurrencia y secuenciabilidad.
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.
Idear soluciones que garanticen la exclusión mutua es uno de los problemas fundamentales de la programación concurrente. Muchas son las alternativas y tipos de mecanismos que se pueden adoptar. A lo largo de este tema veremos diferentes soluciones software y alguna hardware ; unas serán sencillas y otras complejas, algunas requieren la cooperación voluntaria de los procesos y otras que exigen un estricto ajuste a rígidos protocolos. La selección de las operaciones primitivas adecuadas para garantizar la exclusión mutua de las secciones críticas es una decisión primordial en el diseño de un sistema operativo. Al menos, una solución apropiada debería cumplir las cuatro condiciones siguientes:
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.
Los procesos son concurrentes si existen simultáneamente. Los procesos
concurrentes pueden funcionar en forma totalmente independiente unos de otros,
o pueden ser asíncronos, lo cual significa que en ocasiones requiere cierta
sincronización y cooperación.
En un sistema monoprocesador, la
existencia de multiprogramación es condición necesaria, pero no suficiente para
que exista concurrencia, ya que los procesos pueden ejecutarse
independientemente. Por ejemplo, un editor y un compilador pueden estar
ejecutándose simultáneamente en una computadora sin que exista concurrencia
entre ellos. Por otro lado si un programa se está ejecutando y se encuentra
grabando datos en un archivo, y otro programa también en ejecución está
leyendo datos de ese mismo archivo, sí existe concurrencia entre ellos, pues el
funcionamiento de uno interfiere en el funcionamiento de otro.
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.
Concurrencia y secuenciabilidad
Puede verse la concurrencia
de procesos como la ejecución simultánea de varios procesos. Si
tenemos unmultiprocesador o un sistema distribuido(tema
1) 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 (o procesado paralelo) la circunstancia en la que de tomar
una instantánea del sistema en conjunto, varios procesos se
vean en un estado intermedio entre su estado inicial y final.
Los distintos procesos dentro de un
ordenador no actúan de forma aislada. Por un lado, algunos procesos cooperan
para lograr un objetivo común. Por otro lado, los procesos compiten por el uso
de unos recursos limitados, como el procesador, la memoria o los ficheros.
Estas dos actividades de cooperación y competición llevan asociada la necesidad
de algún tipo de comunicación entre los procesos.
Para aclarar un poco todo esto,
supongamos que en un entorno UNIX se ejecuta la orden
·
cat tema1 tema2 tema3 | wc -l
Esta orden va a provocar que el
intérprete de órdenes cree dos procesos concurrentes, el primero ejecutará el
programa cat, que concatenará el contenido de los ficheros de texto tema1, tema2 y tema3.
El segundo ejecutará el programa wc, que contará el número de
líneas de la salida producida por cat. Estos dos procesos cooperan,
y será preciso algún tipo de sincronización entre ellos, concretamente hasta
que cat no produzca alguna salida wc debería
bloquearse.
Competencia entre los procesos
·
La naturaleza física del recurso hace que sea imposible
compartirlo. Un ejemplo lo constituye una impresora, si una impresora fuera
utilizada por varios procesos simultáneamente sus salidas se entremezclarían en
el papel.
· El recurso es tal que si es usado por varios procesos de forma
concurrente la acción de uno de ellos puede interferir con la de otro. Un
ejemplo común lo constituye un fichero que contiene unos datos accesibles desde
más de un proceso, y modificables al menos por uno de ellos.
Dentro de la categoría de recursos no
compartibles se incluirán la mayoría de los periféricos (los
discos no), los ficheros de escritura y las zonas de memoria sujetas a
modificación. Los recursos compartibles incluirán la CPU (en los temas previos
vimos cómo compartir la CPU entre los procesos introduciendo el concepto de PCB),
los ficheros de lectura, y las zonas de memoria que contengan rutinas puras o
bien datos que no están sujetos a modificación.
Ejemplos
El hecho de reservar un asiento en
una avión mediante un sistema basado en aplicaciones web, cuando decenas de
personas en el mundo pueden reservarlo también, nos da una idea de lo
importante y crucial que es el control de concurrencia en un sistema de base de
datos a mediana o gran escala.
Otro ejemplo en el que podemos
observar la incidencia del control de concurrencia en el siguiente: en una Base
de Datos bancaria podría ocurrir que se paguen dos cheques en forma simultánea
sobre una cuenta que no tiene saldo suficiente para cubrirlos en su totalidad,
esto es posible evitarlo si se tiene un control de concurrencia.
Sincronizacion
Cinco filósofos se sientan alrededor
de una mesa y pasan su vida cenando y pensando. Cada filósofo tiene un plato de
fideos y un tenedor a la izquierda de su plato. Para comer los fideos son
necesarios dos tenedores y cada filósofo sólo puede tomar los que están a su
izquierda y derecha. Si cualquier filósofo coge un tenedor y el otro está
ocupado, se quedará esperando, con el tenedor en la mano, hasta que pueda coger
el otro tenedor, para luego empezar a comer.
Si dos filósofos adyacentes intentan
tomar el mismo tenedor a una vez, se produce una condición de carrera: ambos
compiten por tomar el mismo tenedor, y uno de ellos se queda sin comer.
Si todos los filósofos cogen el
tenedor que está a su derecha al mismo tiempo, entonces todos se quedarán
esperando eternamente, porque alguien debe liberar el tenedor que les falta.
Nadie lo hará porque todos se encuentran en la misma situación (esperando que
alguno deje sus tenedores). Entonces los filósofos se morirán de hambre. Este
bloqueo mutuo se denomina interbloqueo o deadlock.
El problema consiste en encontrar un algoritmo que permita que los
filósofos nunca se mueran de hambre.
Requisitos para la Exclusión Mutua
Los recursos no compartibles, ya sean periféricos, ficheros, o datos en
memoria, pueden protegerse del acceso simultáneo por parte de varios procesos
evitando que éstos ejecuten de forma concurrente sus fragmentos de código a
través de los cuales llevan a cabo este acceso. Estos trozos de código reciben
el nombre de secciones o regiones críticas, pudiéndose asimilar el
concepto de exclusión mutua en el uso de estos recursos a la idea de exclusión
mutua en la ejecución de las secciones críticas. Así, por ejemplo, puede
implementarse la exclusión mutua de varios procesos en el acceso a una tabla de
datos mediante el recurso de que todas las rutinas que lean o actualicen la
tabla se escriban como secciones críticas, de forma que sólo pueda ejecutarse
una de ellas a la vez.
Idear soluciones que garanticen la exclusión mutua es uno de los problemas fundamentales de la programación concurrente. Muchas son las alternativas y tipos de mecanismos que se pueden adoptar. A lo largo de este tema veremos diferentes soluciones software y alguna hardware ; unas serán sencillas y otras complejas, algunas requieren la cooperación voluntaria de los procesos y otras que exigen un estricto ajuste a rígidos protocolos. La selección de las operaciones primitivas adecuadas para garantizar la exclusión mutua de las secciones críticas es una decisión primordial en el diseño de un sistema operativo. Al menos, una solución apropiada debería cumplir las cuatro condiciones siguientes:
1. Sólo un proceso, de todos los que poseen secciones críticas por el mismo
recurso compartido, debe tener permiso para entrar en ella en un momento dado.
2. Un proceso que se interrumpe en una sección no crítica debe hacerlo sin
interferir con los otros procesos.
3. Un proceso no debe poder solicitar acceso a una sección crítica para
después ser demorado indefinidamente, no puede permitirse el interbloqueo o la
inanición.
4. Si ningún proceso está en su sección crítica, cualquier proceso que
solicite entrar en la suya debe poder hacerlo sin demora.
5. No se debe suponer sobre la velocidad relativa de los procesos o el
número de procesadores.
6. Un proceso permanece en su sección crítica por un tiempo finito.
BENEFICIOS DE LA CONCURRENCIA
·
Trata de evitar los tiempos muertos de la UCP
·
Comparte y optimiza el uso de recursos
·
Permite la modularidad en las diferentes etapas del proceso
·
Acelera los cálculos
·
Da mayor comodidad
DESVENTAJAS DE LA CONCURRENCIA
·
Inanición e interrupción de procesos
·
Ocurrencia de bloqueos
·
Que dos o más procesos requieran el mismo recurso (no apropiativo).
Comentarios
Publicar un comentario