No protocolo de
controle de concorrência baseado em timestamp é associado um rótulo
de tempo (timestamp) fixo exclusivo, ou seja, antes que uma transação
inicie, o sistema de banco de dados fornecerá um número que servirá
de identificador da ordem de execução da mesma.
Supondo que temos
duas transações A e B, a transação A se iniciou no tempo 1 e a
transação B teve início no tempo 2, logo, a transação A será
executada primeiro que a transação B, pois seu tempo de início é
mais antigo.
Para implementar
este esquema de rótulo de tempo, temos duas possibilidades:
Usar a hora do
relógio do sistema (clock) sendo esse o timestamp, então, o
horário de início da transação será igual à hora em que a
transação entra no sistema.
Usar um
contador lógico que é incrementado sempre que se usa um novo
timestamp, isto é, o timestamp da transação é igual ao valor do
contador no momento em que a transação entra no sistema. Os
rótulos de tempo da transação são numerados com 1, 2, 3 e assim
consecutivamente (o computador tem um valor máximo finito, de modo
que o sistema precisa reiniciar o contador periodicamente para zero
quando nenhuma transação estiver sendo executada por algum período
curto de tempo).
O algoritmo precisa
garantir que a ordem em que o item está sendo acessado não está
violando a ordem do rótulo de tempo, e para isso o algoritmo associa
a cada item X do banco de dados dois valores de rótulo de tempo(TS),
sendo:
Esses
timestamps são atualizados sempre que uma nova instrução
read_TS(X) ou write_TS(X) é executada. Sempre que uma transação
read e write é desfeita pelo esquema de controle de concorrência,
esta transação recebe um novo timestamp e é reiniciada. O rótulo
de tempo (TO) compara o rótulo de tempo de T com read_TS(X) e
write_TS(X) para garantir que o rótulo da transação de tempo não
seja violada, ou seja, o protocolo de ordenação de timestamp irá
garantir que qualquer operação read ou write que esteja em conflito
sejam executadas por ordem de timestamp.
Veja o algoritmo abaixo:
TS-Básico(Tx, dado, operação)
início
se operação= ‘READ’então
se TS(Tx)< R-TS(dado).TS-Write então
início abort(Tx);
restart(Tx) com novo TS;
fim
senão início executar read(dado);
se R-TS(dado).TS-Read < TS(Tx)então
R-TS(dado).TS-Read =TS(Tx);
fim
senão início/* operação= ‘WRITE’*/
se TS(Tx)< R-TS(dado).TS-Read ou
TS(Tx)< R-TS(dado).TS-Write então
início abort(Tx);
restart(Tx) com novo TS;
fim
senão início executar write(dado);
R-TS(dado).TS-Write =TS(Tx);
fim
fim
fim
Exercício
Implemente em JavaScript o protocolo de controle de concorrência baseado em Timestamp - TS-Básico.
A transação será entrada via caixa de texto e será verificado se esta de acordo ou não com o algoritmo:
r1(a);w1(a);r2(a);w2(a)c1 - Esta ok ou não.
Se não estiver ok, avisar o ponto onde esta errado.
