edrdo/progcon_ex6

Ficha de Exercícios 6

Programação Concorrente (CC3037), DCC/FCUP

Eduardo R. B. Marques, DCC/FCUP

Objectivos: Exercícios sobre "Software Transactional Memory" (STM).

→ Documentação ScalaSTM

→ Use scripts compile.sh e run.sh para compilar ou executar código.

1

Considere a seguinte história de transações numeradas de $(1)$ a $(5)$, executadas por 3 threads - $t_1$, $t_2$, e $t_3$ - e envolvendo dois registos $a$ e $b$. Observe que as transações $(2)$ e $(4)$ envolvem mais do que uma operação sobre $a$ e $b$. Assuma que os registos $a$ e $b$ têm valor inicial $0$.

1. Considerando execuções serializáveis das transações, faça uma análise da possível evolução de visões consistentes (i.e. observáveis numa execução correcta) de $[a,b]$ e também dos possíveis valores lidos $x$ e $y$ nas transações (4) e (5).

2. Assumindo que as leituras e escritas executam fora do contexto de uma transação na história apresentada (mas que são atómicas individualmente), dê exemplo de uma história linear expressa em termos de uma ordem de operações que corresponda a uma execução linearizável e que seja diferente no seu efeito de todas as execuções serializáveis da alínea anterior.

2

O tipo TArray.View representa um array transacional com operações de leitura e escrita atómica. O seu funcionamento é bastante simples:

• Uma instância a de TArray.View de tamanho n é criada com a = STM.newTArray(n);
• a.length() devolve o tamanho imutável de a, isto é, o tamanho n especificado aquando da criação do array;
• a.apply(pos) lê atomicamente a posição pos de a;
• a.update(pos,x) escreve atomicamente x na posição pos de a.

Considere o esqueleto dado para uma fila de capacidade limitada bloqueante em CABlockingQueue, implementada usando o esquema usual de "array circular". Complete a implementação tendo em conta que as operações add() e remove() deverão bloquear respectivamente quando a fila estiver cheia e vazia.

Pode executar ./run.sh pc.stm.TestEx2 para testar a sua implementação, adaptando o código do método main se achar necessário.

3

Em LLBlockingDeque é dada o esqueleto da implementação de uma "double-ended queue (deque)" usando listas duplamente ligadas, disponibilizando os tradicionais métodos addFirst() / addLast() e removeFirst() / removeLast.

Defina o código de addFirst() e removeLast() em falta. Á semelhança de removeLast() o método removeFirst() deverá ser bloqueante quando uma "deque" estiver vazia.

Pode executar ./run.sh pc.stm.TestEx3 para testar a sua implementação, alterando no código do método main a chamada a test1() para test2(). Nos dois "testes" as remoções pela thread t3 deverão retornar elementos na ordem 0, ..., 99.