Protocolo de controle de concorrência baseado em timestamp - #profMBA

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:

• read_TS(X) - rótulo de tempo de leitura;
• write_TS(X) - rótulo de tempo de gravação;

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.