Ordre d’opération de programmation concurrente

J’étudie une classe de système d’exploitation et j’essaie de comprendre comment fonctionne la programmation simultanée.

La seule chose que je ne peux vraiment pas comprendre est de comprendre “l’ordre” de l’exécution de l’opération / instruction de deux ou plusieurs processus:

Par exemple, compte tenu de ce code pour deux processus tentant d’accéder à une section critique

entrer la description de l'image ici

de Parbegin , quel est l’ordre d’exécution de ce code? Ils fonctionnent de manière 1: 1 (comme une ligne de code est exécutée en alternance par Process1 et Process2 comme 1,1, 2,2, 3,3 … n, n avec la condition visiblement entrée / sortie) ou il y a un ordre particulier qui me manque?

Pour ce que j’ai compris, l’exécution est quelque chose comme ça:

  var and turn inizialized turn is equal to 1 then P1 enter in the CS turn is equal to 1 then P2 enter the while P2 is now in busy-wait P1 is doing the critical section P1 exit from the critical section and set turn=2 P2 exit from the while and enter CS P1 doing remainder P2 exit CS and set turn=1 P1 can enter the cycle 

etc. Est-ce que je fais quelque chose de mal?

Une caractéristique importante de la simultanéité, et la source de nombreuses difficultés, est que l’ordre des opérations entre les processus n’est pas connu . L’ordre des opérations est non déterministe .

En première approximation, vous pouvez considérer l’ordre des opérations comme aléatoire. Autrement dit, considérez que le processeur (plus précisément le planificateur ) exécute le programme multiprocess comme suit:

  • Choisissez au hasard un des processus.
  • Exécutez une instruction de ce processus.
  • Répéter.

Le processeur peut exécuter une instruction de chaque processus à son tour. Ou il peut exécuter 2½ boucles du processus 1, puis 3 instructions du processus 2, puis reprendre le processus 1 pendant un moment, un peu plus du processus 2, etc. Ou il peut exécuter 3 instructions du processus 1, puis 1 du processus 2, puis 4 du processus 1, puis 1 du processus 2, puis 5 du processus 1, etc. Ou il peut continuer à exécuter le processus 1 pour toujours.

Le but de l’étude de la simultanéité est de déterminer les propriétés des programmes qui sont vraies, quelle que soit la séquence de sélection aléatoire, ou du moins pour une classe de choix aléatoires qui ne sont pas “trop ​​extrêmes”. Le type le plus courant de classe “pas trop extrême” est les hypothèses d’ équité , ce qui signifie en gros que chaque instruction qui n’est pas bloquée (une instruction bloquée ressemble à une instruction d’entrée en attente d’un événement d’entrée) sera finalement exécutée. Cela exclut “l’exécution du processus 1 pour toujours”, mais aucun des autres exemples ci-dessus.

En ce qui concerne l’algorithme que vous citez en particulier, son objective est qu’un seul des processus puisse être entre le début et la fin de la section critique. (Notez que bien que la section critique soit écrite sur une seule ligne, elle se compose généralement de plusieurs instructions). Cette propriété est souhaitée, quelle que soit la manière dont les instructions des deux processus sont entrelacées.

Il y a plusieurs simplifications dans ma réponse. En particulier, le caractère aléatoire et le non-déterminisme sont en réalité des concepts différents . Avec un ordonnanceur aléatoire, vous pouvez ou non avoir de la chance, et sinon vous pouvez réessayer, alors qu’un ordonnanceur non déterministe peut vous aider. Un ordonnanceur aléatoire est en fait assez équitable, alors qu’un ordonnanceur du monde réel peut ne pas être juste du tout. La chose importante à internaliser à propos de la concurrence est que vous ne pouvez pas prédire le comportement du programme à l’avance: il existe de nombreux comportements possibles.