Cours du 07/12/2023
J’ai séché le TD sorry not sorry 🤓
C’est un peu un détail du cours 8.

Ensemble en concurrence

Opération atomique sur les assignations et le programme ne meurt pas en zone critique.

Tentative 1

flag : array[0, 1] of bool # le prof parle d'array mais + voir ça comme un dict
                           # où {0: false, 1: false} et les clés sont les 2 threads

Procédure lock
begin
  i := ThreadID.get()
  flag[i] := true
  j := 1 - i
  while (flag[j]) # attends
  endwhile
end

Procédure unlock
begin
  i := ThreadID.get()
  flag[i] := false
end

Procédure main
begin
  x.lock()
  # zone critique
  x.unlock()
rend

Exclusion mutuelle

Ok

Blocage

Oui, les opérations dans lock ont beau être atomique, lock en tant que telle ne l’est pas, alors si deux fonctions appellent lock en même temps, ils vont se bloquer.

Tentative 2

victim : int

Procédure lock
begin
  i := TheadID.get()
  victim := i
  while (victim = i) # tant que je suis la victime, j'attend
  endwhile
end

Procédure unlock
begin
end

Procédure main
begin
  x.lock()
  # zone critique
  x.unlock()
end

Blocage

Blocage tout seul, en plus on ne peut pas prendre 2x la ressource à la suite, car on est dépendant d’un autre processus pour être libéré.

Synthèse

• On veut déclarer que l’on a envie d’entrer
• On veut donner une priorité, un tour de rôle

flag : array [0, 1] of bool # le prof parle d'array mais + voir ça comme un dict
                            # où {0: false, 1: false} et les clés sont les 2 threads
victim : int

Procédure lock()
begin
  i := ThreadID.get()
  j := 1 - i
  flag[i] := true
  victim := i
  while (flag[j] && victim = i) # je suis intéressé + la victime
  endwhile
end

Procédure unlock()
begin
  i := ThreadID.get()
  flag[i] := false
end

Procédure main()
begin
  x.lock()
  # zone critique
  x.unlock()
end

Exclusion mutuelle

Oui

Blocage

Non

Famine

Non, liste FIFO 😎

Avec n threads

n thread 0..(n-1)
level  : array [0..n-1] of int{0} # tous initialisés à 0
victim : array [0..n-1] of int    # identité des threads

Procédure lock
begin
  curr := ThreadID.get() # thread courant
  for(i = 1 ; i < n ; i++)
    level[curr] := i
    victim[i] := curr
    # logique de comment passer d'un niveau à l'autre
    while (∃k != curr (level[k] >= i && victim[i] = curr)) # il existe quelqu'un différent de moi
                                                           # qui est devant moi
                                                           # ET je suis la victime
    endwhile
  endfor
end

Procédure unlock
begin
  curr := ThreadID.get()
  level[curr] := 0
end

Exclusion mutuelle

Oui, car les threads ferment la porte à ceux qui sont derrière lui dans l’array.

Blocage

Oui, c’est une généralisation de la seconde tentative \RA merci la victim

Famine

Non, liste FIFO (≧◡≦)

\RA cf. Cours 5