# TD 1 -- Théorie et théorie et pratique de la concurrence

###### tags `TD` `M1 S1` `Concurrence`
[Sommaire](/IAsAMpizSpawifCj1gZ__g)
> [time= 15 sept 2020]

[TOC]

## Exercice 1
### Enoncé

### Réponse
#### 1)

digraph G {
    
# 1er link
    { 
    rank = same; 
    "(p1, q1, A=1, B=10)"
    }
     
     "(p1, q1, A=1, B=10)" -> "(p3, q1, A=1, B=10)" [label=1] 
     "(p1, q1, A=1, B=10)" -> "(p1, q2, A=2, B=10)"[label=2]

# 2nd link
     { 
     rank = same; 
     "(p3, q1, A=1, B=10)",
     "(p1, q2, A=2, B=10)"
     }
     
     "(p3, q1, A=1, B=10)" -> "(p3, q1, A=1, B=10)" [label=1, style=dotted]
     "(p3, q1, A=1, B=10)" ->"(p3, q2, A=2, B=10)"[label=2]
     
     "(p1, q2, A=2, B=10)" -> "(p2, q2, A=2, B=10)"[label=1]
     "(p1, q2, A=2, B=10)" ->"(p1, q3, A=2, B=11)"[label=2]
     
# 3 eme link
     { 
     rank = same; 
     "(p3, q2, A=2, B=10)", 
     "(p2, q2, A=2, B=10)", 
     "(p1, q3, A=2, B=11)"
     }
         
     "(p3, q2, A=2, B=10)" -> "(p3, q2, A=2, B=10)"[label=1, style=dotted]
     "(p3, q2, A=2, B=10)" -> "(p3, q3, A=2, B=11)"[label=2]
     
     "(p2, q2, A=2, B=10)" -> "(p3, q2, A=2, B=20)"[label=1]
     "(p2, q2, A=2, B=10)" -> "(p2, q3, A=2, B=11)"[label=2]
     
     "(p1, q3, A=2, B=11)" -> "(p2, q3, A=2, B=11)"[label=1]
     "(p1, q3, A=2, B=11)" -> "(p1, q3, A=2, B=11)"[label=2, style=dotted]
     
     # 4 eme link
     { 
     rank = same; 
     "(p3, q3, A=2, B=11)", 
     "(p3, q2, A=2, B=20)", 
     "(p2, q3, A=2, B=11)"
     }
     
     "(p3, q3, A=2, B=11)" -> "(p4, q3, A=2, B=11)"[label=1]
     "(p3, q3, A=2, B=11)" -> "(p3, q3, A=2, B=11)"[label=2, style=dotted]
     
     "(p3, q2, A=2, B=20)" -> "(p4, q2, A=2, B=20)"[label=1]
     "(p3, q2, A=2, B=20)" -> "(p3, q3, A=2, B=21)"[label=2]
     
     "(p2, q3, A=2, B=11)" -> "(p3, q3, A=2, B=22)"[label=1]
     "(p2, q3, A=2, B=11)" -> "(p2, q3, A=2, B=11)"[label=2, style=dotted]
     
     # 5 eme link
     {
     rank=same;
     "(p4, q3, A=2, B=11)",
     "(p4, q2, A=2, B=20)",
     "(p3, q3, A=2, B=21)",
     "(p3, q3, A=2, B=22)"
     }
     
     "(p4, q3, A=2, B=11)" -> "(p5, q3, A=1, B=11)"[label=1]
     "(p4, q3, A=2, B=11)" -> "(p4, q3, A=2, B=11)"[label=2, style=dotted]
     
     "(p4, q2, A=2, B=20)" -> "(p5, q2, A=1, B=20)"[label=1]
     "(p4, q2, A=2, B=20)" -> "(p4, q3, A=2, B=21)"[label=2]
     
     "(p3, q3, A=2, B=21)" -> "(p3, q3, A=2, B=21)"[label="1-2", style=dotted]
     
     "(p3, q3, A=2, B=22)" -> "(p3, q3, A=2, B=22)"[label="1-2", style=dotted]
     
     {
     rank=same;
     "(p5, q3, A=1, B=11)",
     "(p5, q2, A=1, B=20)",
     "(p4, q3, A=2, B=21)"
     }
     "(p5, q3, A=1, B=11)" -> "(p5, q4, A=1, B=11)"[label=2]
     
     "(p5, q2, A=1, B=20)" -> "(p5, q3, A=1, B=21)"[label=2]
     
     "(p4, q3, A=2, B=21)" -> "(p5, q3, A=1, B=21)"[label=1]
     "(p4, q3, A=2, B=21)" -> "(p4, q3, A=2, B=21)"[label=2, style=dotted]
     
     {
     rank=same;
     "(p5, q4, A=1, B=11)"
     "(p5, q3, A=1, B=21)"
     }
     
     "(p5, q4, A=1, B=11)" -> "(p5, q5, A=1, B=16)"[label=2]
     
     "(p5, q3, A=1, B=21)" -> "(p5, q4, A=1, B=21)"[label=2]
     
     {
     rank=same;
     "(p5, q4, A=1, B=21)"
     }
     "(p5, q4, A=1, B=21)" -> "(p5, q5, A=1, B=26)"[label=2]
     
     }

#### 2)
Non pas toute les exécution se termine avec (p5, q5, _, _) on a 2 dead lock.

## Exercice 2:
### Enoncé

### Réponse

$n \in[2, n]$

$$
\begin{array}{|lcr||lcr|}
\hline
\text{t} & \text{P1} & \text{N} &
\text{t} & \text{P2} & \text{N} \\
\hline
1 & tmp = N + 1 & 1 & 2 & tmp = N + 1 & 1 \\
10 & N = tmp & 2 & 3 & N = tmp & 1 \\
12 & tmp = N + 1 & 3 & 4 & tmp = N + 1 & 2 \\
13 & N = tmp & 3 & 5 & N = tmp & 2 \\
14 & tmp = N + 1 & 4 & 6 & tmp = N + 1 & 3 \\
15 & N = tmp & 4 & 7 & N = tmp & 3 \\
16 & tmp = N + 1 & 5 & 8 & tmp = N + 1 & 4 \\
17 & N = tmp & 5 & 9 & N = tmp & 4 \\
18 & tmp = N + 1 & 6 & 11 & tmp = N + 1 & 2 \\
19 & N = tmp & 6 & 20 & N = tmp & 2 \\
\hline
\end{array}
$$

## Exercice 3:
{%hackmd B0rpdjqcRfel-RZiyDj0PA %}