Exercícios

Nos exercícios seguintes, sempre que o algoritmo especificado não for da sua autoria, indique o autor original e a refêrencia para o local onde o encontrou. Muitos dos exercícios apresentados são retirados de [2] e têm como objectivo esclarecer a diferença de abordagem entre esta disciplina e Métodos de Programação IV.

1.

Qual o objectivo do programa da figura 1.9.

  

Figure 1.9: Exemplo de programa em SPL

out   y : int where y = 0
local x : bool where x = true

P1:: [
 l0: while x do
 l1: y := y + 1;
 l2:
]

||

P2:: [
 m0: x := false;
 m1:
]

2.

Especifique em SPL um protocolo (diferente dos apresentados neste capítulo) para resolver o problema da exclusão mútua entre dois processos.

3.

Repita a alínea anterior para o caso de N processos.

4.

Especifique um protocolo que resolva o probelma da exclusão mútua entre N processos, mas que garanta que o acesso à região crítica é feito à vez, i.é, após um processo ter executado a sua região crítica apenas poderá voltar a executá-la depois de todos os outros o terem feito.

5.

Suponha que o SPL não suportava semáforos. Implemente um mecanismo para simular o comportamento destes usando canais de comunicação (e, provavelmente, mais algum processo a executar em paralelo). Teste a sua solução reescrevendo o exemplo da figura 1.6.

6.

Um trigger de N posições (N>1) é um dispositivo, normalmente utilizado em votações electrónicas, com N sinais de entrada e apenas um sinal de saída. Logo que mais de metade dos sinais de entrada estejam activos o trigger activa o sinal de saída e termina. Os sinais de entrada podem ser activados por qualquer ordem.

(a)

Especifique em SPL um trigger de 3 posições.

(b)

Especifique um trigger de N posições.

7.

Considere que se pretende desenvolver um sistema de controlo para um cruzamento entre uma estrada e uma via férrea. Para se testar a validade de um possível controlador é necessário especificar o ambiente que o rodeia, pois não é desejável testar o controlador no sistema real. Para tal vamos representar a estrada e a via férrea como processos que simulam o seu comportamento. Assim, o esqueleto para o nosso programa será algo como o apresentado na figura 1.10. Nesse programa, quando cancela_aberta tem o valor true os carros podem passar o cruzamento e quando sinal_verde tem o valor true os comboios podem passar o cruzamento. A aproximação de um carro ao cruzamento é modelada pela atribuição à variável aprox_carro do valor true. O mesmo se passa para a variável aprox_comboio em relação a um comboio que se aproxima. Dado esse esqueleto, pretende-se que implemente o processo de um controlador que garanta que nunca existam colisões entre carros e comboios e que, sempre que um carro (ou comboio) chegue ao cruzamento, tenha alguma vez a oportunidade de o passar.

  

Figure 1.10: Esqueleto do controlador de um cruzamento

local aprox_carro, aprox_comboio : bool where 
      (aprox_carro, aprox_comboio ) = (false, false);
local cancela_aberta, sinal_verde : bool where 
      (cancela_aberta, sinal_verde) = (false, false);
% Outras declaracoes

Estrada :: [
        e0: loop forever do [
                e1: noncritical;
                e2: aprox_carro := true;
                e3: await cancela_aberta;
                e4: critical;
                e5: aprox_carro := false
        ]
]

||

Carril :: [
        c0: loop forever do [
                c1: noncritical;
                c2: aprox_comboio := true;
                c3: await sinal_verde;
                c4: critical;
                c5: aprox_comboio := false
        ]
]

||

Controlador :: [
        % Completar
]