concurrencias - serializacion

7/21/2019 concurrencias - serializacion

http://slidepdf.com/reader/full/concurrencias-serializacion 1/56

Tema 7. Control de la concurrencia 1

7. Control de la concurrencia

Objetivos

•

Conocer la problemática asociada a la concurrenciade transacciones en los sistemas de bases de datos• Entender el signifcado de la serializabilidad y su

aplicación al control de la concurrencia•

Comprender algunas técnicas para el control de laconcurrencia empleadas por los sistemas gestoresde bases de datos





Contenidos

1. Introducción y problemas de la concurrencia2. erializabilidad!. Técnicas de control de la concurrencia". #ranularidad de datos



Tema 7. Control de la concurrencia !

Bibliografía

[CB 2005] Connolly $ T.%Begg C.&Siste as de bases dedatos . "' Edición. (earson Educación. )ddison *esley.+Cap. 2,-

[!" 2002] !l asri $ .% "avat#e $ ./.& $unda entos deSiste as de Bases de %atos . !' Edición. )ddison0*esley. +Cap. 1 y 2,-

E3 1 74 Elmasri$ .% 3a5at6e$ ./.& Siste as de bases dedatos. Conce&tos funda entales . 2' Edición.)ddison0*esley Iberoamericana. +Cap. 17 y 1 -




Tema 7. Control de la concurrencia "

• 8os sistemas de bases de datos$ seg9n el n9mero deusuarios :ue pueden utilizarlos de ;ormaconcurrente$ se clasifcan en sistemas onousuario y ultiusuario

• <arios usuarios pueden usar un mismo e:uipo a la5ez gracias a la ulti&rogra aci'n & el computadorpuede procesar al mismo tiempo 5ariastransacciones – i el e:uipo tiene varias C() $ es posible el procesamiento

simultáneo +paralelo- de transacciones – i sólo 6ay una C() $ el SO de ulti&rogra aci'n reparte

el tiempo de C(= entre las transacciones&ejecuci'n concurrente intercalada

modelo :ue supondremos

7.* +ntroducci'n,



Tema 7. Control de la concurrencia >

• -arias transacciones introducidas por usuarios$:ue se e?ecutan de manera concurrente $ puedenleer odi/car los is os elementos almacenadosen la base de datos

• azones para permitir la concurrencia& – )umentar la producti5idad& n9mero de transacciones

e?ecutadas por minuto. – )umentar la utilización de la C(= +menos tiempo ociosa- y

Control del disco. – educir el tiempo medio de respuesta de transacciones +las

@pe:ueAasB no esperan a las @grandesB-.

7.* +ntroducci'n,



Tema 7. Control de la concurrencia

• ... por:ue pueden surgir &roble as si lastransacciones concurrentes se ejecutan deanera no controlada

• E?emplo sencillo&

sistema de bases de datos que permite hacer y anular reservas de plazasen vuelos de diferentes compañías aéreas. – e almacena un registro &or cada vuelo $ :ue incluye$

entre otras cosas$ el n9mero de asientos reser5ados en el5uelo

– ean dos transacciones T1 y T2 concurrentes &T1 trans/ere N reservas reali adas en un vuelo X a otrovuelo YT2 reserva M &la as en el vuelo X

7.* , y &roble as de la concurrencia1(or u3 es necesario el control de la

concurrencia4


http://slidepdf.com/reader/full/concurrencias-serializacion 7/56 Tema 7. Control de la concurrencia 7

7.* , y &roble as de la concurrencia(roble as &otenciales &rovocados &or la

concurrenciaransacci'n *leerDelemento+ -%&F 03%escribirDelemento+ -%leerDelemento+G-%

G&FGH3%escribirDelemento+G-%

ransacci'n 2leerDelemento+ -%&F H %escribirDelemento+ -%

• )un:ue las transacciones pueden ser per;ectamentecorrectas en sJ mismas$ la e?ecución concurrente de

T1 y T2 puede producir un resultado incorrecto6debido a la intercalaci'n de sus o&eraciones $poniendo en cuestión la integridad y la co6erenciade la base de datos


http://slidepdf.com/reader/full/concurrencias-serializacion 8/56 Tema 7. Control de la concurrencia

• 8a actuali aci'n &erdida – T1 y T2 :ue acceden a los mismos datos$ tienen suso&eraciones intercaladas de modo :ue 6acen incorrectoel 5alor de alg9n dato

7.* , y &roble as de la concurrencia(roblemas potenciales pro5ocados por la concurrencia

*leerDelemento+ -%&F 03%

escribirDelemento+-%

leerDelemento+G-%


2

leerDelemento+ -%&F H %


El elemento X tiene un valorincorrecto porquesu

actualización por T1 se

‘perdió’ se sobreescribi!"


http://slidepdf.com/reader/full/concurrencias-serializacion 9/56 Tema 7. Control de la concurrencia

• 8a actuali aci'n te &oral +o lectura sucia- – T1 actualiza un elemento X de la /K y luego ;alla$ pero antes

de :ue se restaure el 5alor original de X$T2 tiene acceso alL5alor temporalM de X


*leerDelemento+ -%&F 03%escribirDelemento+-%

leerDelemento+G-%,

2


escribirDelemento+-%T1 falla y debe devolver a X suanti#uo valor$ pero mientras% T2

ha leído el valor &temporal'incorrecto de X dato sucio "


http://slidepdf.com/reader/full/concurrencias-serializacion 10/56 Tema 7. Control de la concurrencia 1,

• El resu en incorrecto – Ntra transacción T( calcula una ;unción agregada deresumen sobre 5arios registros + suma las plazas reservadas para todoslos vuelos-$ mientras otras transacciones$ como T1$ actualizandic6os registros& puede :ue T( considere unos registrosantes de ser actualizados y otros después


*

leerDelemento+ -%&F 03%escribirDelemento+-%

leerDelemento+G-% G&FGH3%escribirDelemento+G-%

suma&F,%leerDelemento+)-%suma&FsumaH)%OOO

leerDelemento+ -%suma&FsumaH %leerDelemento+G-%suma&F sumaHG%O

T3 lee X después derestar N, pero lee Y

antes de sumar N % asíque el resultado es un

resumen incorrectodiscrepancia de )"



• 8a lectura no re&etible – T* lee un elemento X dos 5eces y otra transacción$ como T1$modifca dic6o X entre las dos lecturas& T* recibe di;erentes5alores para el mismo elemento


*

leerDelemento+ -%&F 03%


leerDelemento+G-%

G&FGH3%escribirDelemento+G

8

leerDelemento+-%

OleerDelemento+-%O

T* lee Xantes derestar )

T* lee Xdespués de restar )


http://slidepdf.com/reader/full/concurrencias-serializacion 13/56 Tema 7. Control de la concurrencia 1!

• (ero el ob?eti5o de un #/K multiusuario también esmaPimizar el grado de concurrencia del sistema

• i se &er ite la intercalaci'n de operaciones$ePisten muc6os órdenes posibles de e?ecución de lastransacciones

7.2 Seriali abilidadoti5ación

¿Existe algún modo de identificar las ejecuciones que está garantizado queprotegen la consistencia de la base de datos?

eoría de la Seriali abilidad

Planificación "# actualización perdida$

*leerDelemento+ -%&F 03%

escribirDelemento+-%leerDelemento+G-%


2


escribirDelemento+ -

%

Planificación %#correcta$

*leerDelemento+ -%&F 03%escribirDelemento+-%

leerDelemento+G-% G&FGH3%escribirDelemento+G-%

2

leerDelemento+ -%&F H %escribirDelemento+ -%


http://slidepdf.com/reader/full/concurrencias-serializacion 14/56 Tema 7. Control de la concurrencia 1"

• Cada transacción comprende una secuencia deoperaciones :ue incluyen acciones de lectura yescritura en la /K$ :ue fnaliza con una confrmación+commit - o anulación +rollback -

• =na &lani/caci'n P de n transaccionesconcurrentes T1% T2 ... Tn es una secuencia de laso&eraciones realizadas por dic6as transacciones$

su?eta a la restricción de :ue&ara cada transacción Ti :ue participa en +$sus o&eraciones aparecen en P en el is o orden en el ue ocurren en Ti

7.2 Seriali abilidad(lani/caci'n de transacciones


http://slidepdf.com/reader/full/concurrencias-serializacion 15/56 Tema 7. Control de la concurrencia 1>

• (ara el control de la concurrencia +y recuperación de;allos- interesa prestar mayor atención a estaso&eraciones &

• E?emplos de planifcaciones de transacciones – El subJndice de cada operación indica la transacción :ue la

realiza+, - l1 X" $ e1 X" $ l1 " $ e1 " $ c1 $ l2 X" $ e2 X" $ c2 $

+/ - l2 X" $ e2 X" $ c2 $ l1 X" $ e1 X" $ l1 " $ e1 " $ c1 $

+0- l

1X" $ l

2X" $ e

1X" $ l

1" $ e

2X" $ c

2$ e

1" $ c

1$

+ - l X e X l X e X c l e c

7.2 Seriali abilidad(lanifcación de transacciones

o&eraci'n abreviatura

leer elemento l

escribir elemento ecommit c

rollbac3 r



• =na &lani/caci'n serie P es a:uella en la :ue laso&eraciones de cada transacci'n se ejecutanconsecutiva ente sin :ue se intercalenoperaciones de otras transacciones+

,- l

1X" $ e

1X" $ l

1" $ e

1" $ c

1$ l

2X" $ e

2X" $ c

2$

+/ - l2 X" $ e2 X" $ c2 $ l1 X" $ e1 X" $ l1 " $ e1 " $ c1 $• Toda planifcación serie es correcta /K

consistente•

(ero no se garantiza :ue los resultados de todas lase?ecuciones en serie de las mismas transaccionessean idénticos – E?emplo& c4lculo del interés de una cuenta bancaria antes o después de realizar

un in#reso considerable

en eneral$ son inace tables en la ráctica

7.2 Seriali abilidad(lani/caci'n serie



• =na &lani/caci'n no serie P es a:uella en la :uelas o&eraciones de un conjunto detransacciones concurrentes se ejecutanintercaladas

+0- l1 X" $ l2 X" $ e1 X" $ l1 " $ e2 X" $ c2 $ e1 " $ c1 $+ - l1 X" $ e1 X" $ l2 X" $ e2 X" $ c2 $ l1 " $ e1 " $ c1 $

• Qemos de determinar u3 &lani/caciones noserie &er iten llevar la B% a un estado al ue&ueda llegarse ediante una ejecuci'n enserie

7.2 Seriali abilidad(lani/caci'n no serie

Este es el ob5etivo de la&erializa'ilidad

()



• =na &lani/caci'n P +no serie- es seriali able si ese uivalente a alguna &lani/caci'n serie de lasis as n transacciones – =na planifcación :ue no es e:ui5alente a ninguna

e?ecución en serie$ es una planifcación no seriali able• Toda planifcación serializable es correcta – (roduce los mismos resultados :ue alguna e?ecución en

serie•

Kos maneras de defnir la e:ui5alencia entreplanifcaciones& – ! uivalencia &or con:ictos – ! uivalencia de vistas

7.2 Seriali abilidad(lani/caci'n seriali able



Tema 7. Control de la concurrencia 2,

• En una planifcación$ 2 o&eraciones están encon:icto si – pertenecen a diferentes transacciones $ – tienen acceso al is o ele ento X$ –

y al menos una de ellas es escri'ir*elemento X"Nperaciones en conRicto en las planifcaciones +0 y + -

P" # l1+X - l2+X - e1+X - l1+Y - e2+X - c2 - e1+Y - c1-

P%# l1+X - e1+X - l2+X - e2+X - c2 - l1+Y - e1+Y - c1 -

• Kos &lanes son e uivalentes &or con:ictos si el

orden de cuales uiera dos o&eraciones encon:icto es el is o en a bos lanes

7.2 Seriali abilidadE:ui5alencia por conRictos




• Construcción del grafo de &recedencia +o deserialización- – Es un gra;o dirigido = > )% , " – N es un con?unto de nodos y es un con?unto de aristas

dirigidas – )lgoritmo&Crear un nodo &or cada transacci'n Ti en (

Crear una arista T . T/ si T3 lee el 5alor de un elementodes&u3s de :ue T 5 lo 6aya escritoCrear una arista T . T/ si T3 escribe el 5alor de unelemento des&u3s de :ue T 5 lo 6aya leídoCrear una arista T . T/ si T3 escribe el 5alor de unelemento des&u3s de :ue T 5 lo 6aya escrito

Ti

7.2 Seriali abilidad%etecci'n de la seriali abilidad &or con:ictos

T . T/



Tema 7. Control de la concurrencia 2!

• =na arista T 5 → T3 indica :ue T 5 debe aparecer antes :ue T3 en una &lani/caci'n serie e uivalente a ( %pues dos operaciones en conRicto aparecen en dic6oorden en (

• i el gra;o contiene un ciclo $P no es seriali able por conRictos – =n ciclo es una secuencia de aristas 0> T . → T3"% T3 → Tp"%... Ti

→ T .""

• i no 6ay ciclos en el gra;o$ ( es seriali able Es posible obtener una planifcación serie ?e:ui5alente a +$ mediante una ordenación topológica de los nodos

7.2 Seriali abilidadKetección de la serializabilidad por conRictos +y 2-

T1 T2P

T1 T2P!

T1 T2

P"

T1 T2P%



Tema 7. Control de la concurrencia 2"

Planificación 0

7.2 Seriali abilidad!je &lo de &lani/caci'n no seriali able

ransacci'n *leerDelemento+ -%escribirDelemento+ -%leerDelemento+G-%escribirDelemento+G-%

ransacci'n 2leerDelemento+S-%leerDelemento+G-%escribirDelemento+G-%leerDelemento+ -%escribirDelemento+ -%

ransacci'n leerDelemento+G-%leerDelemento+S-%escribirDelemento+G-%escribirDelemento+S-%

*

leerDelemento+ -%escribirDelemento+-%

leerDelemento+G-%

escribirDelemento+G-%

2leerDelemento+S-%leerDelemento+G-%escribirDelemento+G-%

leerDelemento+ -%

escribirDelemento+ -

leerDelemento+G-%leerDelemento+S-%

escribirDelemento+G-%escribirDelemento+S-%

T1 T2

Y

X

T3

Y,Y

Qay dos ciclos& T1 T 2 T 1 y

T1 T 2 T ! T 1



Tema 7. Control de la concurrencia 2>

Planificación

7.2 Seriali abilidad!je &lo de &lani/caci'n seriali able

ransacci'n *leerDelemento+ -%escribirDelemento+ -%leerDelemento+G-%escribirDelemento+G-%

ransacci'n 2leerDelemento+S-%leerDelemento+G-%escribirDelemento+G-%leerDelemento+ -%escribirDelemento+ -%

ransacci'n leerDelemento+G-%leerDelemento+S-%escribirDelemento+G-%escribirDelemento+S-%

*

leerDelemento+ -%escribirDelemento+-%

leerDelemento+G-%escribirDelemento+G-%

2

leerDelemento+S-%

leerDelemento+G-%escribirDelemento+G-%

leerDelemento+ -%escribirDelemento+ -

leerDelemento+G-%leerDelemento+S-%

escribirDelemento+G-%escribirDelemento+S-%

T1 T2X,Y

T3

Y,Y

8a &lani/caci'nserie

e uivalente esT3 T1 T2




Es el ?@ el que distribuye los recursos

para los procesos% y determina laintercalaci!n de las operaciones de las

transacciones concurrentese5ecutadas como procesos del ?@"

Planificación P+ordenamiento delas operaciones

• "ar4a del sistema• Momento de

introducci!n de las transacciones

• Prioridades de los procesos

555

Planificador deTareas del &)

7.2 Seriali abilidad<&licaciones de la seriali abilidad

Es necesario encontrar t3cnicas ue garanticen la

seriali abilidad $ sin tener :ue 5erifcar a posteriori

;;enfoque muypoco pr4ctico<<

(arece$ pues$ :ue 6abrJa:ue comprobar si + esserializable una veejecutadas lastransacciones incluidas en

+...0.ecución deTransacciones

N)&6

)(

"ancelar elefecto de +

reintentar

7P serializa'le8




• étodos basados en la teoría de la

seriali abilidad $ :ue defnen un con?unto de reglas +o protocolo- tal :ue... – si todas las transacciones las cumplen$ o – el subsistema de control de concurrencia del

#/K las impone +automáticamente-

... se asegura la seriali abilidad de toda&lani/caci'n de transacciones

•

Clasifcación – étodos de blo ueo – étodos de arca de tie &o – Técnicas de ultiversi'n – étodos o&ti istas

7. 3cnicas de control de concurrencia




• =so de blo ueos para controlar el accesoconcurrente a los elementos de datos almacenadosen la base de datos

• eglas básicas del blo:ueo& – Blo ueo co &artido & si una transacción tiene un blo:ueo

compartido sobre un elemento de datos$ &uede leer elele ento6 &ero no actuali arlo +escribir-

<arias transacciones pueden mantener a la 5ez blo:ueoscompartidos sobre el mismo elemento

– Blo ueo e=clusivo & si una transacción tiene un blo:ueoePclusi5o sobre un elemento de datos$ &uede leer yactuali ar +escribir- el ele ento

=n blo:ueo ePclusi5o proporciona acceso ePclusi5o alelemento

7. 3cnicas de control de concurrencia93todos de blo ueo



Tema 7. Control de la concurrencia !,

• Cuando una transacción T solicita un blo ueo O – Si el ele ento no #a sido ya blo ueado por otra

transacción$ se le concede el blo:ueo – Si el elemento sJ est? blo ueado $ el #/K determina si la

solicitud es co &atible con el blo:ueo ePistente&i se pide un blo ueo co &artido sobre un elemento:ue ya tiene un blo ueo co &artido $ el blo:ueo seráconcedido a TEn otro caso $T debe es&erar 6asta :ue se libere elblo:ueo ePistente

• =na transacción :ue obtiene un blo:ueo lo mantiene#asta ue lo libera e=&lícita ente o ter ina +commit o rollbac3- – ólo cuando se libera un blo:ueo ePclusi5o los e;ectos de la

escritura serán 5isibles para las demás transacciones

7. 3cnicas de control de concurrenciaétodos de blo:ueo



Tema 7. Control de la concurrencia !1

• )lgunos sistemas permiten la ejora +o promoción-y la reducci'n +o degradación- de blo:ueos – )umenta el ni5el de concurrencia del sistema

• i T emitió bloquear lectura X"$ más tarde puede

ejorarlo a blo ueo e=clusivo emitiendobloquear escritura X" – i T es la ;nica :ue tiene un blo:ueo compartido sobre X$ se

le concede la solicitud – En otro caso$ T debe esperar

• i T emitió bloquear escritura X"$ más tarde puedereducirlo a un blo ueo co &artido emitiendobloquear lectura X" – )sJ permite :ue otras transacciones lean X





• El uso de blo:ueos para la programación detransacciones no garanti a la seriali abilidad delas planifcaciones


Planificación 9

8blo:uearDlectura+G-%leerDelemento+G-%desblo:uear+G-%

blo:uearDescritura+ -%leerDelemento+ -%&F HG%escribirDelemento+ -%desblo:uear+ -%

5

blo:uearDlectura+ -%leerDelemento+ -%desblo:uear+ -%blo:uearDescritura+G-% leerDelemento+G-%

G&F HG%

escribirDelemento+G-%desblo:uear+G-%

ransacci'n 8blo:uearDlectura+G-%leerDelemento+G-%desblo:uear+G-%blo:uearDescritura+ -%leerDelemento+ -%&F HG%escribirDelemento+ -%desblo:uear+ -%

ransacci'n 5blo:uearDlectura+ -%leerDelemento+ -%desblo:uear+ -%blo:uearDescritura+G-% leerDelemento+G-%

G&F HG%escribirDelemento+G-%desblo:uear+G-%

<alores iniciales& X>2A% >(Aesultados de las &lani/cacionesserie &T*BT6- X>6A% >9AT6BT*- X>8A% >6A

esultado de la planifcación

#&X>6A% >6A )o serializable<"



Tema 7. Control de la concurrencia !!

Es necesario seguir un &rotocolo adicional :ueindi:ue d'nde colocar las o&eraciones deblo ueo y desblo ueo dentro de las transacciones

• El más conocido es el Blo ueo en %os $ases +/2V-• =na transacción T sigue el protocolo de blo:ueo en

dos ;ases si todas las o&eraciones de blo ueo&receden a la &ri era o&eraci'n dedesblo ueoKe este modo$ podemos 5er T di5idida en dos ;ases & –

$ase de e=&ansi'n +o crecimiento-T puede ad uirir blo ueos Tno puede liberar ning9n blo:ueo

– $ase de contracci'nT puede liberar blo ueos ePistentes

T no puede ad uirir ning9n blo:ueo

7. 3cnicas de control de concurrenciaétodos de blo:ueo& Blo ueo en dos fases



Tema 7. Control de la concurrencia !"

• i el sistema permite me?orar y reducir blo:ueosO – 8a ejora sólo puede tener lugar en la fase de e=&ansi'n – 8a reducci'n sólo puede realizarse en la fase de

contracci'nEn el código de T$ un bloquear lectura X" puede aparecer en la;ase de contracción de T sólo si reduce un bloqueo eCclusivoauno compartido

7. 3cnicas de control de concurrencia/lo:ueo en dos ;ases

ransacci'n 8@blo:uearDlectura+G-%leerDelemento+G-%blo:uearDescritura+ -%desblo:uear+G-%leerDelemento+ -%&F HG%escribirDelemento+ -%desblo:uear+ -%

ransacci'n 5@blo:uearDlectura+ -%leerDelemento+ -%blo:uearDescritura+G-%desblo:uear+ -%leerDelemento+G-%

G&F HG%escribirDelemento+G-%desblo:uear+G-%



Tema 7. Control de la concurrencia !>

• Si toda transacci'n de una planifcación sigue el&rotocolo de blo ueo en dos fases $ entonces la&lani/caci'n es seriali able

• <enta?a –

Ga no es necesario co &robar la seriali abilidad de lasplanifcaciones• Incon5enientes

– El /2V puede li itar el grado de concurrencia en un plan – Emplear blo:ueos puede pro5ocar &roble as de ...

+nterblo ueo +blo:ueo mortal o abrazo mortal-Blo ueo inde/nido +o espera indefnida-

7. 3cnicas de control de concurrencia/lo:ueo en dos ;ases




•T debe blo uear todos los ele entos a los :uetendrá acceso +lectura o escritura- antes de co en ar a e?ecutarse

– Si no es &osible blo uear alg;n ele ento $T noblo uear? ninguno y es&erar? para reintentarlo mástarde

– (rotocolo libre de interblo:ueo

7. 3cnicas de control de concurrencia/lo:ueo en dos ;ases conservador o est?tico

/lo:ueo en dos ;ases estrictoel más utilizado• T no libera ning;n 'lo:ueo e;clusi<o #asta ter inar

+con 0@DD T o F@GG/,0H- – "inguna transacci'n lee o escribe un ele ento

odi/cado &or T$salvo si T se #aco &letado &lani/caci'n estricta

– (uede su;rir interblo:ueo +sal5o si se combina con /2Vconser5ador-/lo:ueo en dos ;ases riguroso

más restricti5o :ue el /2V estricto• T no libera ning;n 'lo:ueo compartido ni e;clusi<o #asta

ter inar +con 0@DD T o F@GG/,0H- &lani/caci'n estricta




• Situaci'n en la ue cada una de dos +o más-transacciones est? es&erando a ue se libereun blo ueo establecido &or la otra transacci'n

7. 3cnicas de control de concurrencia!l &roble a del interblo ueo

Ablo:uearDescritura+ -

%leerDelemento+ -%&F 01,%escribirDelemento+ -%blo:uearDescritura+G-%[, en es&era ,]

7

blo:uearDescritura+G-%leerDelemento+G-%

G&FGH1,,%escribirDelemento+G-%blo:uearDescritura+G-%[, en es&era ,]• El #/K 6a de reconocer un interblo:ueo y romperlo&

– <bortar una o más transaccionese des6acen sus escrituras y se liberan sus blo:ueos)sJ$ el resto de transacciones podrá continuar sue?ecución

– >einiciar automáticamente las transacciones




• Qay ! técnicas generales para gestionar losinterblo:ueos – e &ori aciones de blo:ueos – (revenci'n de interblo:ueos – %etecci'n de interblo:ueos

• Con5iene detectar interblo:ueos cuando se sabe :ue6ay &oca interferencia entre transacciones$ esdecir si... – 8as transacciones son cortas y blo uean &ocos

ele entos $ o – 8a carga de transacciones es &e ue a

• En otro caso$ con5iene usar temporizaciones otécnicas de pre5ención

Es más di;Jcil pre5enir :ue utilizar temporizaciones oue detectarlos rom erlos or lo ue en la

7. 3cnicas de control de concurrencia!l &roble a del interblo ueo




• =na transacción :ue solicita un blo:ueo s'loes&erar? durante un perJodo de tie &o&rede/nido por el sistema

• Si no se concede el blo ueo durante ese tiempo$

se producirá un @fn de temporizaciónB& el #/Kasu ir? :ue la transacción est? interblo ueada +aun:ue puede :ue no-$ la abortar? y la reiniciar? automáticamente

Es una solución muy sencilla y práctica(ero puede 6acer :ue sean abortadas y reiniciadastransacciones :ue en realidad no están en uninterblo:ueo

7. 3cnicas de control de concurrenciae &ori aciones de blo ueos



Tema 7. Control de la concurrencia ",

• Nrdenar las transacciones usando arcaste &orales de transacción MT+T #Identifcador ;nico para T8as DT se ordenan seg;n se inician las transacciones8a T más antigua tiene la DT T" menor

?ea T 5que intenta bloquear el elemento de datos X %pero X ya est4 bloqueado por T3 con un candado en conflicto

I <lgorit o !s&erar 9orirsi DT T 5" J DT T3" entonces T 5 puede es&erarsi no$ se aborta T 5 +T 5 muere- y

se reinicia después con la is a marca de tiempo=na T 5 más antigua espera a :ue termine otra T3 más reciente=na T 5 más reciente :ue solicita un elemento blo:ueado por una T3

más antigua$ es abortada +muere- y reiniciada

7. 3cnicas de control de concurrencia(revenci'n de interblo ueos

d l d



Tema 7. Control de la concurrencia "1

• <lgorit o Derir !s&erarsi DT T 5" J DT T3" entonces se aborta T3 +T 5 6iere a T3- y se reinicia después con la is a DT

si no$ T 5 puede es&erar=na T 5 más reciente espera a :ue termine una T3 más antigua

=na T 5 más antigua :ue solicita un elemento blo:ueado por una T3 más reciente$ 6ace :ue la más reciente sea abortada +es 6erida- yreiniciada

• Incon5enientes – )mbos algoritmos 6acen :ue sean abortadas y reiniciadas

transacciones :ue &odrían &rovocar un blo ueo ortal $aun ue tal cosa nunca ocurriera W

– En el algoritmo EsperarKDorir$ una T 5 podrJa abortar yreiniciarse varias veces seguidas si T3 más antigua sigueblo:ueando el X :ue T 5 solicita

7. 3cnicas de control de concurrencia(re5ención de interblo:ueos

3 i d l d i




• -eri/caci'n &eri'dica del estado del siste aXestá en un blo:ueo mortalY• Creación de un grafo de es&era :ue muestra las

dependencias entre transacciones – Crear un nodo por cada transacción en e?ecución$

eti:uetado con el identifcador de la transacción$ T

– i T 5 espera para blo:uear el elemento X$ ya blo:ueado porT3$ crear una arista dirigida desde T 5 a T3

– Cuando T3 libera el candado sobre X$borrar la aristacorrespondiente

• i ePiste un ciclo en el gra;o de espera$ entonces se6a detectado un interblo ueo entre las

transacciones

7. 3cnicas de control de concurrencia%etecci'n de interblo ueos

T . T/

XT . T/

7 3 i d l d i



Tema 7. Control de la concurrencia "!

• (ero... X cu?ndo 6ay :ue veri/car el estado delsistema +e?ecutar el algoritmo :ue genera el gra;o deespera-Y – ) intervalos unifor es de tiempo$ o –

) intervalos de tiempo desiguales &Iniciar algoritmo de detección con un tamaAo deinter5alo inicialCada 5ez :ue no se detecta interblo:ueo$ incrementar elinter5alo

– (or e?emplo$ al doble del anteriorCada 5ez :ue se detecta interblo:ueo$ reducir elinter5alo

– (or e?emplo a la mitadEPistirán lJmites superior e in;erior del tamaAo delinter5alo

7. 3cnicas de control de concurrenciaKetección de interblo:ueos

7 3 i d l d i



Tema 7. Control de la concurrencia ""

• Si el sistema está en un estado de interblo ueo $elSEB% necesita abortar algunas transacciones ...• XCu?les Y Selecci'n de vícti as

– Es me?or abortar transacciones :ue lle5en &oco tie &o en

ejecuci'n – Es me?or abortar una transacción :ue 6aya 6ec6o &ocosca bios en la base de datos

– Es me?or abortar una transacción :ue todavía debe #aceruc#os ca bios en la base de datos

(uede :ue el #/K no conozca esta in;ormacióne trata de abortar las transacciones :ue suponganel mJnimo coste

• Es necesario e5itar la inanici'n

7. 3cnicas de control de concurrenciaKetección de interblo:ueos

7 3 i d l d i



Tema 7. Control de la concurrencia ">

• =na transacción su;re inanici'n cuando esseleccionada para ser abortada + vícti a -sucesi5amente& nunca ter ina su ejecuci'n – Es similar al blo:ueo indefnido

• 8a solución es asignar &rioridades más altas a lastransacciones abortadas 5arias 5eces$ para no sersiempre las 5Jctimas

7. 3cnicas de control de concurrenciaKetección de interblo:ueos& el &roble a de lainanici'n

7 3 i d l d i




• El protocolo de control de concurrencia nuncaselecciona a una transacci'n ue est?es&erando &ara establecer un blo ueo $ mientrasotras transacciones contin9an e?ecutándose connormalidad – Ncurre si el es:uema de espera da más prioridad a unas

transacciones :ue a otras es:uema de espera injusto• Kos algoritmos de pre5ención de blo:ueo indefnido

– Consiguen un es:uema de espera justo!l &ri ero ue llega6 es el &ri ero en seratendido

8as transacciones puede blo:uear el elemento X en elorden en :ue solicitaron su blo:ueo

<u ento de &rioridad en la es&eraCuanto más espera T$ mayor es su prioridadCuando T tiene la prioridad más alta de todas$ obtiene el

7. 3cnicas de control de concurrencia!l &roble a del blo ueo inde/nido

7 8 E l id d d d t




• Toda técnica de control de concurrencia supone :uela base de datos está constituida por un con?unto de elementos de datos con nombre

• 3ormalmente$ un ele ento de datos será uno de

estos& – un 5alor de ca &o de un registro de la /K – un registro de la /K – una &?gina +uno o 5arios blo:ues de disco- – un /c#ero – la B% completa

• Eranularidad F tamaAo del elemento dein;ormación – #ranularidad /na elementos de tamaAo pe:ueAo

– #ranularidad gruesa elementos grandes

7.8 Eranularidad de datos!le entos de bases de datos y granularidad

7 8 E l id d d d t




• En el contePto de los métodos de blo:ueo$ elta a o del ele ento de datos afecta al gradode concurrencia &

tamaAo+elemento- #rado de concurrencia G también...

n9mero de ele entos en la /K carga de trabajo para la gesti'n de blo ueos $ y es&acio ocupado por la infor aci'n de blo ueo

• (ero... XCuál es el ta a o adecuado para los

elementosY(ues de&ende de la naturale a de las transacciones & – i una T representati5a accede a &ocos registros

elegir granularidad de registro – i T accede a uc#os registros de un is o /c#ero

elegir granularidad de &?gina o de /c#ero

7.8 Eranularidad de datos!lecci'n del ta a o adecuado del ele ento dedatos

< l i'




"+-!F %! <BS ><CC+G"FGE+CO O CO"C!( )<F &• Kefnición del nivel de

aisla iento de cadatransacción +por parte del

usuario o$ por omisión$ elpropio #/K-• Control ePplJcito de

blo ueos +operación G@0H-por parte del usuario $ si se

permiten ni5eles deaislamiento in;eriores a?EF ,G L,/GE

"+-!F %! <BS ><CC+G"$HS+CO O +" !>"O &• El #/K implementa los

ni5eles de aislamientodefnidos por el usuario para

las transacciones siguiendouna o 5arias t3cnicas o &rotocolos

• (or e?emplo el #/K Nracleusa dos& –

/lo:ueos – ulti5ersiónEstos conceptos se tratan enel ane=o de este tema

Estos conceptos se 6anestudiado en la teoría de

este tema

<claraci'n ...

< & t d i



Tema 7. Control de la concurrencia >,

<s&ectos de concurrencia enSIF J2 y Oracle

• Z80 2 – 3i5eles de aislamiento de transacción

• Nracle – 3i5eles de aislamiento de transacción –

Técnica multi5ersión – /lo:ueos +candados-



Tema 7. Control de la concurrencia >1

SIF J2• Kefnición de caracterJsticas de la transacción :ue

se inicia – &0T T= N& "T6)N modoacceso aislamiento

• odos de acceso – =0 % )N>Y

(ro6Jbe actualizaciones – =0 % ?=6T0 +por de;ecto-

• 3i5el de aislamiento – #rado de inter;erencia :ue una transacción tolera

cuando se e?ecuta concurrentemente con otras – =0 % @N")MM6T0% – =0 % ")MM6T0% – =0P0 T!>0 =0 % – &0=6 >6 !>0 +por de;ecto-



Tema 7. Control de la concurrencia >2

Z80 2

• i alguna transacción se e?ecuta en alg9n ni5elmenor al ?EF ,G L,/GE $ la seriabilidad puede serincumplida&

)ivel de aislamientoGecturasucia

Gectura norepetible

Gecturafantasma

FE, M)0@DD TE ?í ?í ?í

FE, 0@DD TE )o ?í ?í

FE+E,T,/GE FE, )o )o ?í

?EF ,G L,/GE )o )o )o

Si el sistema soporta niveles distintos a ?EF ,G L,/GE ,debería proporcionar facilidades de control explícitode la concurrencia (sentencias G@0H y M)G@0H…)



Tema 7. Control de la concurrencia >!

Oracle• CaracterJsticas de la transacción

– &0T T= N& "T6)N A=0 % )N>Y B =0 % ?=6T0C aislamiento

• 3i5el de aislamiento &0=6 >6 !>0 – i T2 serializable intenta e?ecutar una sentencia LMD :ue

actualiza un dato :ue puede 6aber sido modifcado por T1 noconfrmada en el momento de comenzar T2$ entonces dic6asentencia LMD ;alla

– =na T serializable sólo 5e los cambios confrmados en el instanteen :ue se inicia$ más los cambios realizados por la propiatransacción mediante )?EFT $M+ ,TE $ EGETE

• 3i5el de aislamiento =0 % ")MM6T0% +de;ecto- – i T2 read commited intenta e?ecutar una sentencia LMD :ue

necesita flas blo:ueadas por T1$ entonces espera 6asta :ue seliberen los blo:ueos de las flas

– Cada consulta e?ecutada por una transacción sólo 5e los datos

confrmados antes de comenzar la consulta +no la transacción-



Tema 7. Control de la concurrencia >"

Nracle•

Consistencia de lectura – #arantiza :ue el conjunto de datos visto &or unasentencia es consistente con res&ecto del instanteen el ue co en ' $ y :ue no ca bia durante laejecuci'n de la sentencia

– )segura :ue los lectores no es&eran a escritores ni

a otros lectores de los mismos datos – )segura :ue los escritores no es&eran a los lectores de los mismos datos

– )segura :ue los escritores s'lo es&eran a otrosescritores si intentan odi/car las is as /las entransacciones concurrentes



Tema 7. Control de la concurrencia >>

Nracle•

Implementación de consistencia de lectura – e aseme?a a :ue cada usuario traba?a con una copiapri5ada de la /K + ultiversi'n -

– Cuando ocurre una actualización$ los valores originales de los datos a;ectados$ se co&ian en otra ona deldisco +segmentos de rollback -

– ientras la transacción T :ue actualiza no se confrma$cual uier usuario ue consulte los datos modifcadosve los valores originales

– 8os ca bios 6ec6os por T sólo :uedan &er anentes cuando es con/r ada

– Fas sentencias +de otras transacciones- ue co ien an des&u3s de :ue T se confrme ya ven losca bios 6ec6os por T"unca ocurren lecturas sucias



Nracle

• /lo:ueos – Eesti'n <uto ?tica de los blo:ueos

/lo:ueos e=clusivos y co &artidos – (ermiten a otras transacciones leer los datos

blo:ueados$ pero no modifcarlos/lo:ueos de tabla o de /la +una o más-8os blo:ueos sólo se liberan la /nali ar latransacci'n +0@DD T o F@GG/,0H-

– Eesti'n 9anuale superpone al blo:ueo automáticoentencia >)"( T !>0 +no ePiste @N>)"( -

concurrencias - serializacion

Documents