MÓDULO 3. CONCURRENCIA Y SINCRONIZACIÓN
  • Procesos.

  • Sincronización.

  • Conceptos de concurrencia y algoritmos.

  • Comunicaciones entre procesos (IPC) y concurrencia entre procesos.

  • Control de concurrencia.

  • Deadlock.

  • Estudio de casos.


PROCESOS
Un proceso es una unidad de actividad que se caracteriza por la ejecución de una secuencia de instrucciones, un estado actual y un conjunto de recursos del sistema asociados, los mismos son gestionados por el sistema operativo.Esta definición varía ligeramente en el caso de sistemas operativos multihilo, donde un proceso consta de uno o más hilos, la memoria de trabajo (compartida por todos los hilos) y la información de planificación. Cada hilo consta de instrucciones y un estado de ejecución.

Los procesos son creados y destruidos por el sistema operativo, así como también este se encarga de la comunicación entre procesos. El mecanismo por el cual un proceso crea otro proceso se denomina bifurcación (fork). Los nuevos procesos pueden ser independientes y no compartir el espacio de memoria con el proceso que los ha creado o ser creados en el mismo espacio de memoria.

En los sistemas operativos multihilo es posible crear tanto hilos como procesos. La diferencia radica en que un proceso solamente puede crear hilos para sí mismo y en que dichos hilos comparten toda la memoria reservada para el proceso.





Modelo de dos estados.

El modelo de estados más simple es el de dos estados. En este modelo, un proceso puede estar ejecutándose o no. Cuando se crea un nuevo proceso, se pone en estado de No ejecución. En algún momento el proceso que se está ejecutando pasará al estado No ejecución y otro proceso se elegirá de la lista de procesos listos para ejecutar para ponerlo en estado Ejecución. De esta explicación se desprende que es necesario que el sistema operativo pueda seguirle la pista a los procesos, conociendo su estado y el lugar que ocupa en memoria. Además los procesos que no se están ejecutando deben guardarse en algún tipo de cola mientras esperan su turno para ejecutar.
2estados.jpg


Modelo de cinco estados

El modelo anterior de dos estados funcionaría bien con una cola FIFO y planificación por turno rotatorio para los procesos que no están en ejecución, si los procesos estuvieran siempre listos para ejecutar. En la realidad, los procesos utilizan datos para operar con ellos, y puede suceder que no se encuentren listos, o que se deba esperar algún suceso antes de continuar, como una operación de Entrada/Salida. Es por esto que se necesita un estado donde los procesos permanezcan bloqueados esperando hasta que puedan proseguir. Se divide entonces al estado No ejecución en dos estados: Listo y Bloqueado. Se agregan además un estado Nuevoy otro Terminado.
Los cinco estados de este diagrama son los siguientes:

5estados.jpg


Ejecución: el proceso está actualmente en ejecución.

Listo: el proceso está listo para ser ejecutado, sólo está esperando que el planificador así lo disponga.

Bloqueado: el proceso no puede ejecutar hasta que no se produzca cierto suceso, como una operación de Entrada/Salida.

Nuevo: El proceso recién fue creado y todavía no fue admitido por el sistema operativo. En general los procesos que se encuentran en este estado todavía no fueron cargados en la memoria principal.

Terminado: El proceso fue expulsado del grupo de procesos ejecutables, ya sea porque terminó o por algún fallo, como un error de protección,aritmético, entre otros.

Los estados Nuevo y Terminado son útiles para la gestión de procesos. En este modelo los estados Bloqueado y Listo tienen ambos una cola de espera. Cuando un nuevo proceso es admitido por el sistema operativo, se sitúa en la cola de listos. A falta de un esquema de prioridades ésta puede ser una cola FIFO. Los procesos suspendidos son mantenidos en una cola de bloqueados. Cuando se da un suceso se pasan a la cola de listos los procesos que esperaban por ese suceso.

Si existe un esquema con diferentes niveles de prioridad de procesos es conveniente mantener varias colas de procesos listos, una para cada nivel de prioridad, lo que ayuda a determinar cuál es el proceso que más conviene ejecutar a continuación.

Procesos suspendidos
Una de las razones para implementar el estado Bloqueado era poder hacer que los procesos se puedan mantener esperando algún suceso, por ejemplo una Entrada/Salida. Sin embargo, al ser mucho más lentas estas operaciones, puede suceder en nuestro modelo de cinco estados todos los procesos en memoria estén esperando en el estado Bloqueado y que no haya más memoria disponible para nuevos procesos. Podría conseguirse más memoria, aunque es probable que esto sólo permita procesos más grandes y no necesariamente nuevos procesos. Además hay un costo asociado a la memoria y de cualquier forma es probable que se llegaría al mismo estado con el tiempo.

Otra solución es el intercambio. El intercambio se lleva a cabo moviendo una parte de un proceso o un proceso completo desde la memoria principal al disco, quedando en el estado Suspendido. Después del intercambio, se puede aceptar un nuevo proceso o traer a memoria un proceso suspendido anteriormente.

El problema que se presenta ahora es que puede ser que si se decide traer a memoria un proceso que está en el estado Suspendido, el mismo todavía se encuentre bloqueado. Sólo convendría traerlo cuando ya está listo para ejecutar, esto implica que ya aconteció el suceso que estaba esperando cuando se bloqueó. Para tener esta diferenciación entre procesos suspendidos, ya sean listos como bloqueados, se utilizan cuatro estados: Listo, Bloqueado,Bloqueado y suspendido y Listo y suspendido.






Procesos en espera
Dos o más procesos pueden cooperar mediante señales de forma que uno obliga a detenerse a los otros hasta que reciban una señal para continuar.

Se usa una variable llamada semáforo para intercambiar señales.

Si un proceso esta esperando una señal, se suspende (WAIT) hasta que la señal se envíe (SIGNAL).

Se mantiene una cola de procesos en ESPERA en el semáforo

La forma de elegir los procesos de la cola en ESPERA es mediante una política FIFO.

La sincronización explícita entre procesos es un caso particular del estado "bloqueado". En este caso, el suceso que permite desbloquear un proceso no es una operación de entrada/salida, sino una señal generada a propósito por el programador desde otro proceso.

DEADLOCK
En sistemas operativos, el bloqueo mutuo (también conocido como interbloqueo, traba mortal, deadlock, abrazo mortal) es el bloqueo permanente de un conjunto de procesos o hilos de ejecución en un sistema concurrente que compiten por recursos del sistema o bien se comunican entre ellos. A diferencia de otros problemas de concurrencia de procesos, no existe una solución general para los interbloqueos.
Todos los interbloqueos surgen de necesidades que no pueden ser satisfechas, por parte de dos o más procesos. En la vida real, un ejemplo puede ser el de dos niños que intentan jugar al arco y flecha, uno toma el arco, el otro la flecha. Ninguno puede jugar hasta que alguno libere lo que tomó.

En el siguiente ejemplo, dos procesos compiten por dos recursos que necesitan para funcionar, que sólo pueden ser utilizados por un proceso a la vez. El primer proceso obtiene el permiso de utilizar uno de los recursos (adquiere el lock sobre ese recurso). El segundo proceso toma el lock del otro recurso, y luego intenta utilizar el recurso ya utilizado por el primer proceso, por lo tanto queda en espera. Cuando el primer proceso a su vez intenta utilizar el otro recurso, se produce un interbloqueo, donde los dos procesos esperan la liberación del recurso que utiliza el otro proceso.

Condiciones necesarias

Estas condiciones deben cumplirse simultáneamente y no son totalmente independientes entre ellas.
Sean los procesos P0, P1, ..., Pn y los recursos R0, R1, ..., Rm:
- Condición de exclusión mutua: Existencia al menos de un recurso compartido por los procesos, al cual sólo puede acceder uno simultáneamente.
- Condición de posesión y espera: Al menos un proceso Pi ha adquirido un recurso Ri, y lo mantiene mientras espera al menos un recurso Rj que ya ha sido asignado a otro proceso.
- Condición de no expropiación: Los recursos no pueden ser apropiados por los procesos, es decir, los recursos sólo podrán ser liberados voluntariamente por sus propietarios.
- Condición de espera circular: Dado el conjunto de procesos P0...Pn, P0 está esperando un recurso adquirido por P1, que está esperando un recurso adquirido por P2,... ,que está esperando un recurso adquirido por Pn, que está esperando un recurso adquirido por P0. Esta condición implica la condición de retención y espera.
Evitando bloqueos mutuos

Los bloqueos mutuos pueden ser evitados si se sabe cierta información sobre los procesos antes de la asignación de recursos. Para cada petición de recursos, el sistema controla si satisfaciendo el pedido entra en un estado inseguro, donde puede producirse un bloqueo mutuo. De esta forma, el sistema satisface los pedidos de recursos solamente si se asegura que quedará en un estado seguro. Para que el sistema sea capaz de decidir si el siguiente estado será seguro o inseguro, debe saber por adelantado y en cualquier momento el número y tipo de todos los recursos en existencia, disponibles y requeridos. Existen varios algoritmos para evitar bloqueos mutuos:
Algoritmo del banquero, introducido por Dijkstra.
Algoritmo de grafo de asignación de recursos.
Algoritmo de Seguridad.
Algoritmo de solicitud de recursos.
Prevención

Los bloqueos mutuos pueden prevenirse asegurando que no suceda alguna de las condiciones necesarias vistas anteriormente.
- Eliminando la exclusión mutua: ningún proceso puede tener acceso exclusivo a un recurso. Esto es imposible para procesos que no pueden ser encolados (puestos en un spool), e incluso con colas también pueden ocurrir interbloqueos.
- La condición de posesión y espera puede ser eliminada haciendo que los procesos pidan todos los recursos que van a necesitar antes de empezar. Este conocimiento por adelantado muchas veces es imposible nuevamente. Otra forma es requerir a los procesos liberar todos sus recursos antes de pedir todos los recursos que necesitan. Esto también es poco práctico en general.
- La condición de no expropiación puede ser también imposible de eliminar dado que un proceso debe poder tener un recurso por un cierto tiempo o el procesamiento puede quedar inconsistente.
- La condición de espera circular es la más fácil de atacar. Se le permite a un proceso poseer sólo un recurso en un determinado momento, o una jerarquía puede ser impuesta de modo tal que los ciclos de espera no sean posibles.





SINCRONIZACIÓN

La sincronizacion en sistemas distribuidos es mas compleja que en los centralizados, esto se debe a que los primeros utilizan algoritmos distribuidos. Dado a que en un sistema distribuido la informacion relativa al mismo no se haya reunida en un único lugar, no se puede contar con un determinado proceso que se encargue de examinar el sistema y a partir de ello tome una decisión, como si sucede en los sistemas centralizados.
Los algoritmos distribuidos deben cumplir con las siguientes caracteristicas:

  • La informacion relevante se distribuye entre varias maquinas
  • Los procesos toman las decisiones sólo en base a la informacion disponible en forma local
  • Debe evitarse un punto de fallo en el sistema
  • No existe un reloj común o alguna fuente precisa del tiempo global


Cronómetros

El cronometro de computadora es un cristal de cuarzo trabajado con precisión. El mismo se mantiene sujeto a tensión y oscila con una frecuencia definida que va a depender del tipo de cristal, la forma en que se corte y la magnitud de la tensión.
Cada cristal lleva asociado dos registros, un contador y un registro mantenedor. Cada oscilación reduce el contador en uno, cuando el contador alcanza el valor cero se genera una interrupción y el contador se vuelve a cargar mediante el registro mantenedor. Cada una de estas interrupciones se llama marca o "tick" de reloj.
Cuando se arranca un sistema por primera vez, en general se pide al operador que ingrese la fecha y la hora. Las mismas se convierten al número de marcas después de cierta fecha conocida y se guardan en memoria. En cada tick de reloj, el procedimiento de servicio de interrupciones añade un uno al tiempo guardado en memoria. De esta forma el reloj ( de software) se mantiene actualizado.
En el caso de una computadora y un reloj, no importa si éste se desfasa un poco, ya que todos los procesos de la máquina utilizan el mismo reloj, de manera que la consistencia se preserva.Sin embargo, cuando se comienza a trabajar con sistemas distribuidos, donde estamos en presencia de mas de un computador, la situación es diferente. Cada computador tiene su propio cronometro, si bien la frecuencia de oscilación de un cristal es muy estable, es imposible que los diversos cristales de los distintos computadores oscilen a la misma frecuencia. De manera que, al haber diferencia en la oscilacion de los diferentes cristales se genera perdida de sincronia entre los distintos cronometros y esto a su vez traerá como consecuencia que al leerlos tengan valores distintos.Esta diferencia establecida entre los relojes es conocida como distorsión de reloj, si esto sucede, se pueden producir fallas en los programas que esperan que el tiempo asociado a un archivo, proceso o mensaje sea correcto e independiente del sitio en donde haya sido generado.
Para dar solución a esta cuestión, en 1978 Lamport demostró que la sincronización de relojes es posible presentando un algoritmo para ello.

ALGORITMO DE LAMPORT
Lamport señaló que la sincronización de relojes no tiene que ser absoluta. Si hay dos procesos que no interactúan entre si, no es necesario que sus relojes estén sincronizados, ya que la carencia de sincronizacion no seria visible y por ende, no puede generar problemas.Ademas señaló que no es importante que todos los procesos concuerden en la hora, sino que concuerden en el orden en el que suceden los eventos.
En cierta clase de algoritmos, lo que importa es la consistencia interna de los relojes y no su cercanía al tiempo real. Para este tipo de algoritmos hablamos de relojes, como relojes lógicos. Por otra parte, cuando los relojes deben valer lo mismo, y no desviarse del tiempo real por mucho, se llaman relojes ciertos.
Para la sincronización de relojes lógicos Lamport definió la relación "happens-before". La misma consiste en que si se tiene un evento A y un evento B, perteneciendo ambos al mismo proceso, la expresión A->B se lee “A happens-before B” y significa que todos los procesos acuerdan que primero ocurre el evento A, y luego, ocurre el evento B.
Otra situación en donde puede verse la relación "happen-before" es si A es el evento de un mensaje enviado por un proceso, y B es el evento de un mensaje recibido por otro proceso, entonces A ->B también es verdadero, ya que un mensaje no puede ser recibido antes de ser enviado ni ambos eventos pueden suceder al mismo tiempo, dado a que el envio toma un tiempo finito en concretarse.

Happens-before es una relación transitiva, por lo cual si dos eventos, X e Y, ocurren en diferentes procesos, y no intercambian mensajes (ni aún con un tercero), entonces X->Y es falsa y los eventos son concurrentes, con lo cual no es necesario decir nada acerca del momento en que los eventos suceden.
Para todo evento a, se asigna un valor de tiempo C(A) en el que todos los procesos están de acuerdo. De manera que cuando existe una relacion happen before A->B, todos los procesos van a concordar en la relacion C(A)<C(B). Con lo cual significa que el evento A sucede antes que el evento B. Análogamente sucede si A es un evento emisor y B es un evento receptor.

Concurrencia


Conceptos de concurrencia
{
Dos o más procesos decimos que son concurrentes, paralelos, o que se ejecutan concurrentemente, cuando son procesados al mismo tiempo, es decir, que para ejecutar uno de ellos, no hace falta que se haya ejecutado otro.
En sistemas multiprocesador, esta ejecución simultánea podría conseguirse completamente, puesto que podremos asignarle, por ejemplo, un proceso A al procesador A y un proceso B al procesador B y cada procesador realizaran la ejecución de su proceso.
Cuando tenemos un solo procesador se producirá un intercalado de las instrucciones de ambos procesos, de tal forma que tendremos la sensación de que hay un paralelismo en el sistema (concurrencia, ejecución simultánea de más de un proceso).
Ahora bien, está claro que en esto tenemos que tener en cuenta que mientras un proceso está escribiendo un valor en una variable determinada, puede darse el caso que otro proceso que es concurrente al primero vaya a leer o escribir en esa misma variable, entonces habrá que estudiar el caso en el que un proceso haga una operación sobre una variable (o recurso en general) y otro proceso concurrente a él realice otra operación de tal forma que no se realice correctamente. Para estudiar esto, y determinar el tipo de operaciones que se pueden realizar sobre recursos compartidos utilizaremos las condiciones de Bernstein.
2. Condiciones de Bernstein.
Condiciones que nos determinan si dos procesos se pueden ejecutar de forma paralela.

R(S1) es el conjunto de variables cuyo valor es accedido durante la ejecución de la instrucción.

W(S1) es el conjunto de variables cuyo valor cambia durante la ejecución de la instrucción.
Condiciones de Bernstein: Dos procesos se pueden ejecutar de forma concurrente si se verifican las siguientes condiciones:

R(S2) Intersección W(S1) = {conjunto vacío}

R(S1) Intersección W(S2) = {conjunto vacío}

W(S1) Intersección W(S2) = {conjunto vacío}

} (Damian Andres Lopez 22/05/2011)
Control de concurrencia


En general, un servidor ejecuta operaciones en beneficio de varios clientes cuyas operaciones pueden estar entrelazadas. Las transacciones atómicas permiten a los clientes especificar secuencias atómicas de operaciones. Estas secuencias de operaciones deben ser planificadas en el servidor de tal forma que su efecto sobre los datos compartidos sea serialmente equivalente. Estos métodos de planificación son conocidos como métodos o algoritmos de control de concurrencia. Esta sección vamos a examinar tres de ellos.


1 Bloqueo


Un ejemplo simple de mecanismo de serialización es el uso de bloqueos exclusivos. En este método, el servidor intenta bloquear cualquier dato que utiliza la transacción en curso. Si el clienteY pide el acceso a un dato que ya ha sido bloqueado por otra transacción de un cliente X, la petición es suspendida y el cliente Y debe esperar hasta que el dato sea desbloqueado. La figura 3.10 ilustra el uso de los bloqueos exclusivos.


Transacción T:

Transacción U:

Retirada(A, 4);

Retirada(C, 3);

Depósito(B, 4);

Depósito(B, 3);

Operaciones
Bloqueos
Operaciones
Bloqueos
AbrirTransacción



balance := A.Read()
bloquea A


A.Escribe(balance-4)





AbrirTransacción



balance := C.Read()
bloquea C


C.Escribe(balance-3)

balance := B.Read()
bloquea B




balance := B.Read()
espera por B
B.Escribe(balance+4)



CierraTransacción
Desbloquea A,B





bloquea B


B.Escribe(balance + 3)



CierraTransacción
desbloquea B, C
Fig. 3.10 Dos transacciones concurrentes con bloqueos exclusivos


Ambas transacciones comparten la cuenta bancaria B y el problema es maximizar todo lo posible la concurrencia de estas transacciones mediante una planificación serialmente equivalente. La planicación de la figura ha sido realizada mediante el algoritmo de bloqueo en dos fases, que consiste en que a una transacción no se le permite bloquear un nuevo dato si es que ya ha ha cedido un bloqueo. Esta política conduce a que cada transacción tiene una primera fase denominada fase de crecimiento en la que adquiere todos los bloqueos sobre los datos que accede y una segunda fase en la que libera los bloqueos, denominada fase de reducción en que libera los datos que deja de utilizar. Así, en la figura 3.10 vemos cómo la transacción T bloquea la cuenta A y accede a ella, después U bloquea la cuenta C y accede a ella y T bloquea B y accede a ella. Como T no va a utilizar más datos, la fase de crecimiento de T ha terminado. En ese instante, U se dispone a acceder a la cuenta B y trata de bloquearla pero se encuentra con que U ya la ha bloqueado, de modo que le toca esperar hasta que T la libere cuando haya terminado con ella. Es entonces cuando la bloquea para sí y termina su fase de crecimiento. Como vemos, el algoritmo de bloqueo en dos fases garantiza la serialidad de una planificación y proporciona cierto grado de concurrencia. Por esta razón, es ampliamente utilizado.


En algunos sistemas, la fase de reducción no empieza hasta que la transacción no ha acabado, bien por que se ha comprometido o bien por que ha sido abortada. A esta variante se la denomina bloqueo en dos fases estricto. La figura anterior lo utiliza. La ventaja es que toda transación siempre lee un valor escrito por una transacción comprometida. En el algoritmo no estricto, sería posible que en la fase de reducción de una transacción T liberásemos el bloqueo de un dato, y antes de concluir la fase de reducción, otra transacción U accediese a ese dato. La fase de reducción de T continúa, pero antes de concluir recibe una operación de aborto por parte del cliente. La transacción entera debe ser desecha rebobinando el log. El problema es que ahora U tiene un dato erróneo -denominado lectura sucia-, por lo que el servidor debe tomar la decisión de abortar U. Este aborto puede provocar nuevos abortos, etc. En suma se evitan los denominados abortos en cascada.



2 Control de concurrencia optimista

{
Una manera de lidiar con el problema es asumir que este tipo de interferencia de hilos es poco probable que ocurra, y simplemente verificar el problema y devolver un error si esto es así. Esto es comúnmente un modo válido de lidiar con el problema en situaciones complejas donde la “sobrecarga” de estructuras de datos por varios hilos no es demasiado elevada.
} (Damian Andres Lopez 22/05/2011)
Kung y Robinson (1981) identificaron un número de desventajas del mecanismo de bloqueo y propusieron una aproximación alternativa optimista a la serialización de transacciones que evitan sus defectos. Entre los defectos del bloqueo identificaron los siguientes:


El mantenimiento de los bloqueos representa una sobrecarga para un servidor transaccional. Incluso las transacciones que sólo leen datos, como las búsquedas, que no tienen posibilidad de afectar a la integridad de los datos, necesitan bloqueo de tipo lectura a fin de garantizar que el dato que se está leyendo no es modificado por otras transacciones al mismo tiempo.


El uso de los bloqueos, incluso el bloqueo en dos fases, puede conducir a interbloqueos. Si dos procesos tratan cada uno de adquirir el mismo par de bloqueos pero en orden opuesto, resulta el bloqueo. Los interbloqueos se pueden prevenir utilizando técnicas como numerar los datos en un orden canónico e imponiendo a la transacción un acceso a los mismos en orden creciente. Frente a la evitación del interbloqueo está el permitir que se produzcan y, cuando esto ocurre, detectarlo. Por ejemplo, se puede imponer a la transacción que no mantenga un bloqueo sobre un dato un tiempo mayor de T segundos. Cuando esto ocurre, salta un temporizador asociado al dato, lo que indica que con alta probabilidad se ha producido un interbloqueo.


Para evitar abortos en cascada, los bloqueos no pueden se cedidos hasta el final de la transacción, lo que reduce sustancialmente el grado de concurrencia.


La alternativa de Kung y Robinson es optimista porque está basada en la observación de que, en la mayoría de las veces la verosimilitud de que dos transacciones accedan al mismo dato es baja. A las transacciones se les permite continuar como si no hubiese posibilidad de conflicto hasta que el cliente emite la primitivaCerrarTransacción. Es ahora, antes de comprometer la transacción cuando se evalúa la posibilidad de conflicto con otras transacciones. Si se detecta, la transacción no se compromete, sino que simplemente se aborta para que el cliente la reinicie, esta vez quizá con mejor suerte. Cada transacción sigue tres fases, la fase de lectura, la fase de validación y la fase de escritura.


1. Fase de lectura. El servicio de la transacción construye una copia de los datos que la transacción utiliza. A esta copia se la denomina también versión tentativa. La transacción trabaja sobre la copia y no sobre los ficheros reales. Las operaciones de lectura son realizadas inmediatamente, bien desde la copia o, si aún no se ha creado la copia de un dato, desde la versión real más recientemente comprometida. Las operaciones de escritura registran los valores de los datos en la copia. Cuando varias transacciones acceden al mismo dato, varias copias de ese dato coexisten, una por transacción.


2. Fase de validación. Cuando se recibe la operación CierraTransacción la transacción se valida. A grandes rasgos, si los datos que utiliza la transacción en curso han sido utilizados por otras transacciones desde que comenzó la transacción en curso, la validación falla. Si la validación tiene éxito, la transacción se compromete. En caso contrario, debe utilizarse alguna forma de resolución de conflicto y bien abortar la transacción actual o aquellas implicadas en el conflicto.


3. Fase de escritura. Si la transacción es validada, todos los cambios registrados en la versión tentativa se hacen permanentes. Las transacciones de sólo lectura pueden comprometerse inmediatamente, mientras que las de escritura tienen que esperar a ser grabadas en disco.

2 Control de concurrencia pesimista.
Podemos tomar un enfoque bastante diferente del problema, considerando que la lista tiende a ser modificada y, por esto, requiere su propio bloqueo. Todas las operaciones que lean o escriban en la lista, incluyendo búsquedas, deberán bloquear primero la lista. Esto provee una solución alternativa al problema de bloquear limpiamente a varios objetos en la lista. Revisemos las operaciones que deseamos realizar nuevamente, con el ojo puesto en este diseño alternativo del bloqueo.
Un hilo puede querer leer y modificar los contenidos de un objeto de la lista, pero sin modificar el objeto existente ni su posición en la lista. Esta operación toma mucho tiempo, y no queremos obstaculizar a otros hilos que quieran operar con otros objetos, de modo que el hilo que modifique el objeto debe realizar las siguientes operaciones:
  • Bloquear la lista.
  • Buscar el objeto en la lista.
  • Bloquear el objeto.
  • Desbloquear la lista.
  • Realizar las operaciones en el objeto.
  • Desbloquear el objeto.

4 Etiquetado temporal


Una aproximación completamente diferente al control de concurrencia es asignar una etiqueta temporal a la transacción en el cliente cuando este invocaAbrirTransacción. Usando el algoritmo de Lamport, podemos asegurar que las etiquetas temporales son únicas.


El algoritmo de control de concurrencia basado en etiquetas temporales utiliza también el concepto de copias o versiones tentativas de los datos. Así, cada transacción dispone de una copia para cada dato al que accede. Las operaciones de escritura se graban en versiones tentativas hasta que el cliente emita la primitivaCerrarTransacción en que la transacción se compromete y la versión tentativa del dato se transforma en definitiva. Tanto el dato como cada una de sus copias tienen asociados una etiqueta temporal de escritura. El dato tiene un conjunto de etiquetas de lectura que son resumidas por la etiqueta más reciente. Cuando una transacción se compromete, la copia de cada dato accedido por la transacción se convierte en el dato y la etiqueta temporal de cada copia se convierte en la etiqueta temporal del dato correspondiente.


En control de concurrencia por etiquetado temporal, el servidor comprueba que cada operación de lectura o escritura sobre un dato es conforme con las reglas de conflicto. Una operación de la transacción en curso Tj puede entrar en conflicto con operaciones previas hechas por otras transacciones Ti bien comprometidas, bien aún no comprometidas. Las reglas de conflicto son las siguientes.


Regla
Tj

1.
Escritura
Tj no debe escribir un dato que ha sido leído por alguna Ti más reciente (Ti > Tj)
2.
Escritura
Tj no debe escribir un dato que ha sido escrito por alguna Ti más reciente
3.
Lectura
Tj no debe leer un dato que ha sido escrito por una Ti más reciente


Regla de escritura. Combinando las reglas 1 y 2 tenemos la siguiente regla para decidir si aceptar una operación de escritura de la transacción Tj sobre el dato D.


IF Tj  máxima etiqueta de lectura en D AND

Tj > etiqueta de escritura del dato comprometido D

THEN realiza la operación de escritura en la copia de D con etiqueta de escritura Tj

ELSE Aborta la transacción Tj (* Es demasiado tarde *)

END


Que significa que: Si Tj es más moderna que la transacción que creó el dato y es más moderna que la transacción que leyó el dato por última vez, entonces escribe en la copia. En caso contrario aborta la transacción.


Regla de lectura. Usando la regla 3 tenemos el siguiente procedimiento para decidir si aceptar inmediatamente, esperar o rechazar una operación de lectura de la transacción Tj sobre el dato D.


IF Tj > etiqueta de escritura del dato comprometido D

THEN

Sea Ds la copia hecha por la transacción más reciente más antigua o igual que Tj

IF Ds no existe

THEN Lee de D

ELSE Esperar hasta que la transacción que copió Ds se comprometa o aborte

END

ELSE Aborta Tj

END


Nótese que:

Si Tj ya ha escrito en la copia su versión del dato, este será el usado.

Una operación de lectura que llega demasiado pronto -transacciones más antiguas que también usan D aún no se han comprometido- espera a que la transacción anterior se comprometa. Si la transacción anterior se llega a compometer, entoces Tj leerá de su versión comprometida. Si aborta, Tj repetirá la operación de lectura (y seleccionará la versión previa). Esta regla evita las lecturas sucias.

Una lectura que llega demasiado tarde, es decir, otra transacción más reciente ya ha escrito el dato y se ha comprometido, es abortada.


Conviene repasar el mecanismo de escritura con un ejemplo. Supongamos que tenemos tres transacciones P, Q y R de etiquetas temporales EP, EQ y ER respectivamente. P ejecutó hace mucho tiempo y utilizó todos los ficheros que van a utilizar Q y R. Todas las etiquetas temporales de estos ficheros valen EP. Q y R comienzan concurrentemente, siendo R más moderna que Q, por lo que la etiqueta temporal EQ < ER. Consideremos una operación de Q en la que accede a un fichero para escribir. Las etiquetas de lectura y escritura de este fichero son RF y WF respectivamente, P se comprometió hace tiempo y tenemos que RF = EP y WF = EP. Se cumple la condición del IF de escritura y se actualiza la copia de F con la escritura hecha por Q. Ahora la etiqueta de la copia de F de la transacción Q, WFQ, es EQ (WFQ = EQ), pero la etiqueta del dato sigue siendo la anterior EP (WF = EP).


Supongamos ahora que, después de que Q escribe sobre F, pero antes de que Q se comprometa, R realiza una operación de escritura sobre el fichero F. Como el dato F no se ha tocado, las condiciones son las mismas que antes: en el IF de escritura se compara la etiqueta de la transacción y la de la versión comprometida del dato, de modo que se actualiza la copia de F de R. Tenemos ahora dos copias de F, con etiquetas (WFQ = EQ) y (WFR = ER), mientras la etiqueta de escritura del dato F es (WF = EP). Como vemos, ambas transacciones operan concurentemente, despreocupadas, cada una escribiendo sobre su propia copia.


Supongamos que, una vez creadas ambas copias, R se compromete. Esto significa que Q, siendo anterior a R, ha llegado al servidor demasiado tarde. Veamos lo que ocurre cuando R intenta escribir sobre F. Tenemos que ER < WF, ya que R acaba de escribir y comprometerse, luego no se cumple la segunda condición del IF de escritura y la transacción R aborta. Como vemos, este mecanismo es, en cierto sentido, optimista, En el método de Kung y Robinson, esperamos que dos transacciones no usen los mismos ficheros. Aquí no nos importa si dos transacciones usan los mismos ficheros. Sólo que la transacción más antigua llegue antes. Si R llega antes que Q, y realiza una operación de lectura, R aborta no importa si Q se compromete o no.


Repasemos también el mecanismo de lectura. Consideremos una operación de Q en la que accede a un fichero para leer. Las etiquetas de lectura y escritura de este fichero son RF y WF respectivamente, P se comprometió hace tiempo y tenemos que RF = EP y WF = EP. Se cumple la condición del IF de lectura. No hay otras transacciones en curso, por lo que no hay que esperar a otra transacción más reciente y se lee del dato F. La etiqueta de lectura del dato es ahora EQ (RF = EQ).


Supongamos ahora que, después de que Q lee de F, pero antes de que Q se comprometa, R realiza una operación de lectura sobre el fichero F. Como el dato F no se ha tocado, las condiciones son las mismas que antes: en el IF de lectura se compara la etiqueta de la transacción Q y la versión comprometida de escritura del dato F, de modo que pasamos a comprobar si una transacción más antigua que R tiene alguna copia de F. Como ni Q ni ninguna otra transacción han tratado de escribir sobre F, no existe ninguna copia, por lo que la lectura se atiende y la etiqueta de lectura del dato F se actualiza a ER (RF = ER). En el caso de que Q hubiese escrito F antes de que R leyese, esta copia sí existiría, por lo que si R lee del dato, leería una versión obsoleta. Es mejor leer de la copia, más actual, pero ¿Qué ocurre si Q aborta? Estaríamos leyendo un valor erróneo. La solución es que R debe esperar a que Q se comprometa para leer de F. Observemos que esta espera no se produce en el caso de escritura, donde cada transacción escribe su propia copia del dato. Eso sí, si R se comprometía antes que Q, Q debía abortar.-
{
Competencia entre procesos concurrentes por los recursos

Los procesos concurrentes entran en conflicto cuando compiten por el uso del mismo recurso, es
decir, quieren acceder a un recurso al mismo tiempo. Y la ejecución de un proceso puede influir en
el comportamiento de los procesos que compiten y el sistema operativo le asignará el recurso a uno de ellos y el otro tendrá que esperar. Por lo que el proceso que quede esperando, se retrasará, se bloqueara y en el peor de los casos nunca se terminará con éxito.
Exclusión Mutua:
La exclusión mutua consiste en asegurar que los recursos no compartidos sean accedidos por un único proceso a la vez.
Región Critica Las secciones críticas o regiones críticas son fragmentos de programa que acceden a recursos no compartidos. Si dos procesos no están nunca en sus secciones críticas al mismo tiempo, se evita que haya conflicto entre estos por el recurso.
- Requisitos para la exclusión mutua: El uso adecuado de la concurrencia entre procesos exige la capacidad de definir secciones críticas y hacer cumplir la exclusión mutua. Esto es fundamental para cualquier esquema de proceso concurrente. Cualquier servicio o capacidad que dé soporte para la exclusión mutua debe cumplir los requisitos siguientes:
  1. Solo un proceso, de entre todos los que poseen secciones críticas por el mismo recurso u objeto compartido, debe tener permiso para entrar en ella en un instante dado.
  2. Un proceso que se interrumpe en una sección no crítica debe hacerlo sin estorbar
a los otros procesos.
  1. 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 (cuando un proceso nunca puede acceder a un recurso por falta de prioridad) .
  2. Cuando ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en
la suya debe poder hacerlo sin tardanza.
  1. No se pueden hacer suposiciones sobre la velocidad relativa de los procesos o su número.
  2. Un proceso permanece en su sección crítica solo por un tiempo finito

Soluciones a la exclusión mutua

I. 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. Entre estas soluciones podemos encontrar:
  • Algoritmo de Dekker

  • Algoritmo de Peterson

Soluciones por Hardware: Propone el uso de instrucciones de la máquina a tal efecto, estas tienen la ventaja de reducir la sobrecarga.
Soporte al Sistema Operativo: Entre estos métodos se encuentran los semáforos, monitores, paso de mensajes, etc } (Damian Andres Lopez 22/05/2011)