Página dos laboratórios:
https://tecnico-distsys.github.io/
Esclarecimento sobre a concretização da máquina de estados no servidor
A noção de máquina de estados pressupõe que os pedidos são processados em série, uma de cada vez. Para além disso, todas as réplicas devem processar os pedidos pela mesma ordem, pelo que a ordem de processamento dos pedidos deve ser a indicada pelo algoritmo de ordem total simplificado (baseado num gerador centralizado de números de sequência).
Para conseguir este objectivo, necessitam de criar um mecanismo de sincronização em que cada fio-de-execução do servidor, quando executa um "put" ou um "take", executa essa operação em exclusão mútua e só o faz na ordem certa. O estudo destes mecanismos de sincronização não faz parte da matéria de "Sistemas Distribuídos", uma vez que esta matéria foi leccionada em Sistemas Operativos". Apesar disto, e porque o algoritmo de sincronização não é trivial, sugerimos o seguinte:
- O servidor deve manter um contador que indica qual o próximo pedido a executar. O fio de execução associado a um determinado pedido só deve fazer progresso quando o número do próximo pedido a executar for o seu.
- Se um fio de execução conseguir obter acesso à exclusão mútua mas não for o próximo pedido a executar, deve bloquear-se numa condição.
- Depois de conseguir acesso à exclusão mútua na ordem certa, o fio de execução que executa um pedido deve incrementar o número do próximo pedido a executar, de forma a que o pedido seguinte possa vir a ser executado.
- No final da execução de um pedido, se for possível executar um novo pedido, é necessário sinalizar a condição onde estao bloqueados os pedidos à espera da sua vez.
- A execução do "take" tem a particularidade de o pedido poder ter de se bloquear se não existir tuplo pretendido. Neste caso, será necessário incrementar na mesma o número do próximo pedido a executar, para que os pedidos seguintes se executem, em particular para que seja possível executar posteriormente um "put" que vai desbloquear o "take".
- Os "take" bloqueados à espera de tuplo devem ficar registados numa fila ordenada pela ordem total, de forma a se poder libertar o "take" que chegou primeiro. Sugere-se também que cada "take" espere pelo "put" correspondente numa condição individual, de forma a ser possível libertar apenas o "take" mais antigo quando finalmente chegar o tuplo pretendido.
- Existem duas maneiras possíveis de um "put" passar o tuplo que inseriu a um "take" que estava bloqueado:
a) O fio de execução que faz "put" coloca o tuplo directamente numa estutura de dados do fio de execução que faz o "take", sem sequer passar pelo estado partilhado. Desta forma, depois de acordar, o "take" nem precisa de aceder ao espaço de tuplos.
b) O fio de execução que faz "put" coloca o tuplo no espaço de tuplos, acorda o "take" mais antigo, e esse fio de execução retira o tuplo do espaços de tuplos.
No caso b), o "put" deve desbloquear apenas o fio de execução correspondente ao "take" que estava bloqueado, e não deve incrementar o contador que indica qual o próximo pedido a executar. Isto garante que apenas o "take" que estava pendente se irá executar e que este não será "ultrapassado" por um take novo. Deve ser o "take" que, depois de retirar o seu tuplo, incrementa o contador que indica qual o próximo pedido a executar e liberta o próximo comando da máquina de estado.