Questões de Algoritmos Concorrentes
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.
