Exercícios do livro Principles of Concurrent and Distributed Programming. M. Ben-Ari.

Capítulo 6.

1. Consider the following algorithm:

Algorithm 6.15: Semaphore Algorithm A
Semaphore S←1, T ← 0
p q
p1: wait(S)
p2: write(“p”)
p3: signal(T)
q1: wait(T)
q2: write(“q”)
q3: signal(S)

(a) What are the possible outputs of this algorithm?

Resposta:
p passa no wait(S) diretamente pois S é 1. Escreve p. Libera T.

Enquanto isso q esperava por T. Depois que p libera T, q escreve q e libera S.

A saída é pq.

(b) What are the possible outputs if we erase the statement wait(S)?

Resposta:

A saída seria a mesma, pq.

q continuaria a esperar T. p executaria p2 de imediato sem passar pelo wait(S) que ele conseguiria passar sempre, já que S é inicializado com 1 inicialmente.

(c) What are possible outputs if we erase the statement wait(T)?

Resposta:

Como q não tem mais que esperar por q, então podemos ter duas saídas possíveis:

  • pq
  • qp

A primeira ocorre quando o processo p chega a p2 antes que q chegue a q2. A segunda quando o contrário ocorre, q chega a q2 antes que p chegue a p2.

2. What are the possible outputs of the following algoritm?

Algorithm 6.1: Semaphore algorithm B
Semaphore S←1
boolean B ← false
p q r
p1: write(“p”)
p2: signal(S1)
p3: signal(S2)
q1: wait(S1)
q2: write(“q”)
q3:
r1: wait(S2)
r2: write(“r”)
r3:

Resposta:

  • pqr
  • prq

“p” sempre será impresso primeiro já que q e r aguardam S1 e S2 respectivamente. Após isso, o semáforo S1 e liberado e logo em seguida o S2. Se q passar pelo wait(S1) antes que r passe pelo wait(S2) a saída será pqr. Caso contrário, a saída será prq.

3. What are the possible outputs of the following algorithm?

Algorithm 6.17: Semaphore wit a loop
Semaphore S←1
boolean B ← false
p q
p1: wait(S)
p2: B ← true
p3: signal(S)
q1: wait(S)
q2: while not B
q3: write(‘*’)
q4: signal(S)

Resposta:

  • (nada)
  • ******….

Se p passa pelo seu wait(S) e atribui true para B, então q ficara preso no laço de q2.

Se q consegue chegar até q3, ele ficará imprimindo ‘*’ eternamente. O valor de B ficará inalterado já que p não sairá de p1 até que S seja liberado, o que não irá acontecer pois q está num laço onde a condição de saída será sempre falsa.

4. Show that if the initial value of S.V in algorithm 6.3 is k, at most k processes can be in the critical section at any time.

Resposta:

O funcionamento do semáforo deixa que pelo menos S.V processos passem por wait(S) sem que S seja bloqueado. Se S.V é k, então o wait irá decrementar S.V quando S.V for positivo, quando não, ele irá acionar o processo a S.L e depois bloquear p.

6. Modify Algorithm 6.5 to use a single general semaphore.

Resposta:

O que realmente importa aqui é que sort1 e sort2 sejam executados antes do merge. Então podemos usar um semáforo com duas ‘vagas’.

Algorithm 6.5 (modificado) : Mergesort
integer array A
Semaphore S ← (2, ∅)
sort1 sort2 merge
p1: soft 1st half of A
p2: signal(S)
q1: sort 2nd half of A
q2: signal(S)
r1: wait(S)
r2: merge halfes of A

Capítulo 7.