Home
About

Process

Cours/Système et réseau/Système d'exploitation/Process

Un process est l'unité de base d'un programme. Un process contient des données et des instructions pour être exécuté, le tout étant stocké en mémoire.

Exécution d'un process

Nous n'allons pas rentrer dans les détails sur ce qu'est une instruction. On y reviendra lorsque l'on parlera précisément des cores.

On va uniquement considérer ici qu'à chaque instruction est associé un byte et que le code d'un process, c'est à dire la suite d'instructions que devra effectuer le processeur, est un tableau M de byte.

L'exécution du process est alors déterminée par un entier IP (instruction pointer)tel que :

  1. IP vaut initialement 1
  2. le processeur :
    1. lit l'instruction I de numéro M[IP]
    2. incrémente IP
    3. exécute l'instruction I
  3. si I est :
    • l'instruction de fin on stope l'exécution du process
    • une instruction de saut on affecte à IP la valeur du saut
  4. retour en 2.

La variable IP est écrite directement sur le processeur. Sa taille est fixe (8B=64b) et sert uniquement à déterminer l'adresse de la prochaine instruction à effectuer.

Le processeur possède un certain nombre de ce type de variables, appelées registres. Ce sont des mémoire très rapides d'accès et qui permettent au processeur de fonctionner. Certains registres sont spécialisés et stockes des endroits d'intérêt dans la mémoire. Par exemple IP, mais également SP, ou encore l'adresse des syscall que l'on verra plus tard.

D'autres registres sont génériques et font office de variables locales lorsque l'on code en langage processeur et servent d'endroit où stocker les paramètres d'instructions.

Organisation en mémoire

L'usage veut que l'on représente la mémoire comme une suite de byte allant de bas (adresse 0) en haut (adresse max). De plus, l'adresse est souvent donnée en hexadécimal car sa base est un multiple de 2 assez grand pour être compact et pas trop grand pour ne pas avoir trop de chiffre : 0xFF=255 et rempli un byte.

https://en.wikipedia.org/wiki/X86-64#Virtual_address_space_details

Instructions simples

Si la seule instruction est d'afficher un retour à la ligne à l'écran, le code serait quelque chose du genre :

0x6   : .
0x5   : .
0x4   : .
0x3   : .
0x2   : .
0x2   : exit
0x1   : print
0x0 :

Un process ne peut jamais commencer à 0 car une adresse de 0 signifie pas d'adresse (c'est le None de python, ou le null du C).

Instructions avec paramètre

Si l'on veut afficher "Hello World" à l'écran, il faut pouvoir stocker la chaîne de caractère "Hello World" dans la mémoire et demander à notre programme de l'afficher. Il ne peut en effet pas y avoir d'instruction différente pour chaque chaîne de caractère à afficher.

0x10  : .
0x0F  : .
0x0E  : 0
0x0D  : 'd'
0x0C  : 'l'
0x0B  : 'r'
0x0A  : 'o'
0x09  : 'W'
0x08  : ' '
0x07  : 'o'
0x06  : 'l'
0x05  : 'l'
0x04  : 'e'
0x03  : 'H'
0x02  : exit
0x01  : print chaîne 3
0x00  :

L'instruction print est maintenant différente :

La chaîne de caractère est nécessairement séparée du code pour éviter qu'il puisse être exécuté (c'est à dire convertir la chaîne de caractères en instructions).

Le process doit donc avoir au moins 2 parties distinctes :

données
code

Chaque constante est adressée par son indice. Il faut donc que le code connaissent exactement la position de la constante en mémoire. Ceci n'est pas toujours possible car peut-être que le code n'est pas exécuté à partir de 0, ce qui casserait tout :

0x14     : .
0x13     : .
0x12     : .
0x11     : .
0x05-10  : 'Hello World\0'
0x04     : exit
0x03     : print chaîne 3
0x02     : .
0x01     : .
0x00     : .

En revanche, le code connaît la position relative de la constante par rapport à son exécution, ici 3 + 2. Comme le pointeur IP pointe sur la prochaine instruction, le code suivant fonctionne donc toujours, le paramètre se trouve 2 cases plus loin que l'instruction courante donc 1 de plus que la prochaine instruction :

0x14     : .
0x13     : .
0x12     : .
0x11     : .
0x05-10  : 'Hello World\0'
0x04     : exit
0x03     : print chaîne IP+1
0x02     : .
0x01     : .
0x00     : .

Les adresses de départ exactes sont modifiées aléatoirement par le système d'exploitation pour des raisons de sécurités.

Vous pourrez m'objecter, qu'il n'est pas possible d'avoir une commande différente pour chaque saut de paramètre. Cela ferait trop de commande.

Effectivement, ce n'est pas comme ça que c'est géré. On utilise des commandes de taille variables où :

Comme le processeur les connaît, il incrémentera automatiquement le compteur d'instruction de la taille de l'instruction plus le nombre de ses paramètres. Notre code devient :

0x15     : .
0x14     : .
0x13     : .
0x12     : .
0x11     : 'Hello World\0'
0x05-10  : exit
0x04     : 1
0x03     : print chaîne avec un paramètre
0x02     : .
0x01     : .
0x00     : .

Notez que le paramètre doit être de taille fixe (ici 1 byte) pour que tout fonctionne. Il n'est pas possible pour cette commande de faire des sauts de plus de 255 byte (il faudrait une autre commande qui prend un word à la place d'un byte comme paramètre)

Pour des raisons de lisibilité, nous n'allons pas recopier directement le code dans ce qui suit. On va utiliser des règles qui vont faciliter la lecture des programme et qui sont immédiatement transposable :

section .data

  hello DB "Hello World", 0
data_F:                            ; facultatif

section .text

main:                              ; label d'adresse
    print chaîne hello

Le code précédent devient alors plus lisible sans perdre de sa généralité :

Ceci donne en mémoire :

data_F :
       : 0
       : 'd'
       : 'l'
       : 'r'
       : 'o'
       : 'W'
       : ' '
       : 'o'
       : 'l'
       : 'l'
       : 'e'
hello  : 'H'
         exit
main   : print chaîne hello
       :
...
0x0    :

Du fichier au programme

A priori tout programme peut fonctionner uniquement avec des instructions et des valeurs initiales, le étant déterminé pendant l'exécution.

Le fichier stockant le programme est donc uniquement composé des constantes et des instructions. S'il suit exactement ce principe :

code
données

et que les appels aux constantes sont des déplacements relatifs, le code exécuté peut être stocké directement dans un fichier pour être réutilisé plus tard sans aucun changement.

Le code en mémoire et le code fichier est identique identique

Instructions avec variables

Regardons le code python suivant :

for i in range(10):
  print(i)

Écrivez le code comme précédemment. En ajoutant des instructions

Rappelez-vous que le code :

  • ne peut pas posséder de constantes.
  • les paramètres sont placés après l'appel à l'instruction

solution

 
section .data

i B 0

section .text

main:
    place 0 dans i
boucle:
    print byte [i]
    incrémente [i]
    si [i] < 10 saute en boucle

On utilise [i] plutôt que i pour indiquer que l'on considère la valeur M[i] si M est le tableau en mémoire et pas l'adresse i.

Outre le fait d'inventer des commandes plausibles (print byte, incrémente et l'instruction de saut), on a utilisé une case consacrée à nos données pour stocker une variable (la variable i du code python)

On remarque que la position de la variable dans la pile ne bouge pas

Ce nest pas très optimisé puisqu'on devra sauvegarder cette variable dans le fichier du code et alourdira inutilement notre fichier. de plus, i est une variable, elle ne devrait pas être présente dans le code "en dur" mais créée à la volé par le programme.

On pourrait utiliser un segment spécifique pour les données non initialisées, de nom de section bss, mais son usage est très particulier et réservées aux variables globales.

Utilisation d'une pile

La gestion des variable est faite par une pile

Commençons par voir comment tout ceci est fait avant de voir comment l'implémenter en mémoire.

Une pile est une structure de donnée qui comprend deux fonctions :

  • empilage(d) : ajoute l'élément d à la pile et rend son indice de stockage
  • dépilage() : supprime un élément à la pile
  • accès(i) : accède au i+1 ème élément de la pile en lecture ou en écriture

Exemple :

empile(1)
empile(2)
print(accès(0))  # rendra 2
print(accès(1))  # rendra 1
dépile()
print(accès(0))  # rendra 1

Cette structure permet deux choses fondamentale :

C'est exactement ce qu'il faut pour gérer des variables.

De plus, une pile se gère comme un tableau ! Soit SP un indice de la mémoire qui contient le dernier élément de la pile.

Après les deux premières lignes du programme précédent on a :

SP+1 :         1
SP   :         2
SP-1 :

De là le code complet est :

section .text

main:
    empile 0
    empile 2
    print byte [SP]
    print byte [SP+1]
    dépile
    print byte [SP]

Pour continuer nos sucres syntaxiques on utilise :

Ce concept est fondamental. Si vous avez compris, félicitations vous avez compris les pointeurs :

Il est tout à fait possible de n'utiliser que ces deux registres pour exécuter un ordinateur comme on le fait ici.

On peut calculer en calculant la notation polonaise inverse, utiliser le langage Forth ou encore lorsque vous exécutez des programmes python

Ce n'est cependant pas ce qui est fait usuellement car les registres sont d'accès bien plus rapide que la mémoire. Les processeurs possèdent tous un petit nombre de registres de taille fixe (on utilise majoritairement ceux de 64b mais il en existe de 8b à 128b, voir plus) utilisées pour les passages de paramètres et les retours de ses instructions.

Process en mémoire avec pile

pile
...
...
données
code

La pile se remplit en diminuant de valeur. Elle commence à la plus haute adresse possible et ne peut aller plus bas que le dernier élément des données.

Le code (section text) commence à la plus petite valeur strictement positive possible (c'est plus que 1 à cause de la pagination. Pour une pagination de 4KiB, la première adresse possible est 0x1000).

La pile est nécessaire à l'exécution du programme mais pas pour sa conception. Le fichier contenant le programme ne contient pas la pile.

Gestion des variables avec la pile

Reprenons notre petite boucle python :

for i in range(10):
  print(i)

Et utilisons la pile pour gérer i :

section .text

main:
    empile 0
boucle:
    print byte [SP]
    incrémente [SP]
    si [SP] < 10 saute en boucle
    dépile

Où incrémente [SP] signifie M[SP] += 1

Une variable est définie par sa visibilité dans le programme déterminé par le bloc dans le quel elle apparaît. Par exemple en python :

def f(a, b):
  code de f

while condition:
  code
  if condition 2:
    code du if
    appel de f

for range:
  code du for
  appel de f

Contient 4 blocs :

Gérer les variables se fait alors comme suit :

Ceci permet de ne jamais stocker des variables inutiles et de toujours pouvoir accéder aux variables d'un bloc.

Écrivez le code suivant avec la pile et en utilisant les règles de création et de suppression des variables :

for i in range(10):
  for j in range(20):
    print(i+j)

solution

On crée une variable pour chaque bloc :

section .text

main:
    empile 0
boucle:
    empile 0
boucle2:
    print byte [SP+1] + [SP]
    incrémente [SP]
    si [SP] < 20 saute en boucle2
    dépile
    incrémente [SP]
    si [SP] < 10 saute en boucle
    dépile

On aurait aussi pu créer les deux variables en une fois :

section .text

main:
    empile 0
    empile 0
boucle:
    print byte [SP+1] + [SP]
    incrémente [SP]
    si [SP] < 20 saute en boucle
    place dans [SP] la valeur 0
    incrémente [SP+1]
    si [SP+1] < 10 saute en boucle
    dépile

Cette dernière implémentation combine les deux boucle for en une seule boucle

Appels de fonctions

La pile, si pratique pour gérer toutes nos variables est également d'une efficacité redoutable pour gérer les appels de fonctions.

Prenons le code python :

def ma_fct(x);
  for i in range(20):
    print(x+i)

for i in range(10):
  ma_boucle(i)

Et écrivons ce programme avec la pile :

section .text

main:
    empile 0
boucle:
    empile [SP]                           ; paramètre
    empile retour                         ; retour de la fonction
    saut ma_fct
retour:
    dépile                                ; supprime le retour
    dépile                                ; supprime le paramètre
    incrémente [SP]
    si [SP] < 10 saute en boucle
    dépile
    saute en fin
ma_fct:
    empile 0                              ; variable de la fonction
fct_boucle:
    print byte [SP+2] + [SP]              ; SP+2 contient l'argument
    incrémente [SP]
    si [SP] < 20 saute en fct_boucle
    dépile
    saute en [SP]
fin:

La pile nous a permis de stocker les paramètres et le saut de retour de la fonction. En appliquant le même principe pour toutes les fonctions :

On a crée un moyen simple et efficace de gérer des fonctions (c'est même récursif !) C'est ce qu'o appelle une ABI.

Les processeurs possèdent souvent deux instructions pour gérer l'appel (mais pas les paramètres) des fonctions :

Les appelles et retour de fonctions ont souvent leurs propres instructions qui gèrent le saut, l'empilage et le dépilage de la valeur de retour.

Limitation de la pile

La pile est un moyen efficace de gérer les variables et les appels de fonctions. Elle possède cependant un inconvénient :

On ne peut mettre que des choses pas trop grosse, la taille globale de la pile est relativement petite (10MiB), et dont on connaît la taille. De plus une fois que la donnée est dans la pile on ne peut plus modifier sa taille.

Taille inconnue

Si l'on demande à un utilisateur de taper un texte, ou si l'on veut récupérer le contenu d'une page web on ne peut être sur de la taille nécessaire pour contenir le résultat : cela va dépendre du moment où l'on exécute le code.

On ne peut donc pas dans ce cas là réserver une plage de byte dans la pile pour stocker cette variable, elle peut, selon la page chargée ou le texte tapée être aussi grande que l'on veut.

Taille changeante

x = 0
for i in range(100):
  x += i
  print(x)

Écrivez le code associé au programme ci-dessus en supposant que x est un byte

solution

 
section .text

main:
    empile 0
    empile 0
boucle:
    place dans SP+1 la valeur [SP] + [SP+1]
    print byte [SP+1]
    incrémente [SP]
    si [SP] < 100 saute en boucle
    dépile
    dépile

A un moment donné la valeur de $x$ stockée dans la pile à l'adresse A de la mémoire va déborder en A+1.

Tas

Pour palier les limitations de la pile il faut ajouter la possibilité de réserver de la mémoire pour y stocker des choses. Il faut bien sûr prendre de la mémoire qui ne sert pas au process : entre la fin des données et le début de la pile.

Cette mémoire utilisée par le processus qui n'est ni des données, ni du code ni la pile est appelée tas. On a alors un schéma de ce type en mémoire :

pile
...
...
tas
données
code

Au départ, le tas est vide, mais le programme peut le remplir. Prenons le squelette de code ci-après :

section .data

    ...      ; ici toutes les déclarations de données

début_tas:

section .text

main:

    ...   ; ici le code

fin_code:

main:

Le tas peut théoriquement aller jusqu'au début de la pile. En pratique ce n'est pas le cas, c'est le système d'exploitation qui contrôle sa taille (via l'appel système brk). Ceci permet de contrôler la mémoire que prend un process lorsqu'il y a plusieurs process sur un système (tout le temps en fait).

Utilisation du tas

Les données stockées dans le tas sont déterminées par leur adresse. En connaissant leur type on peut les manipuler comme les autres variable, à une indirection prêt. Allons-y :

Comme toutes les variables sont stockées dans la pile, la variable qui représente une donnée du tas sera son adresse. De là :

  1. soit x l'adresse d'un byte stockée sur le tas.
  2. on l'empile : [SP] (la valeur M[SP]) vaut x
  3. la valeur du byte stocké dans le tas vaut : [[SP]] (M[x] = M[M[SP]]).

À vous :

Utilisez le tas pour stocker la variable $i$ du code python suivant :

for i in range(10):
  print(i)

solution

 
section .data

    ...      ; ici toutes les déclarations de données

début_tas:

section .text

main:
    empile début_tas
    affecte 0 à l'adresse [SP]
    print byte [[SP]]
    si [[SP]] < 10 saute en main
    dépile
fin_code:

main:

Limitation du tas

Le tas est un endroit de stockage vierge et libre. Il faut se souvenir de qui à stocké quoi dedans sous peine de faire n'importe quoi.

Bibliothèques partagées

https://en.wikipedia.org/wiki/Shared_library

Il manque encore une chose à notre process. La fonction print et ses avatars print chaîne et print byte sont complexes. Elles ne peuvent être des opération du processeur qui ne fait que des choses basique comme additionner des trucs, sauter à des endroit ou mettre des choses à des adresses précises.

Cette fonction a été écrite par quelqu'un d'autre qui la met à notre disposition. Elle est de plus tellement pratique que quasi tous les processus vont l'utiliser. Une telle bibliothèque existe, c'est la libc (quasi tous les processus d'une machine Linux vont utiliser des fonctions de cette bibliothèque).

On appelle ces bibliothèques des bibliothèques partagées. Ce sont les .dll de windows, les .so de Linux et les .dylib de Macos.

Il n'est pas nécessaire de stocker le code de ces bibliothèques dans notre fichier de code, plein de place serait gaspillée puisque cette bibliothèque se retrouverait dans tous les fichiers, il suffit que l'ordinateur en possède une copie.

Bibliothèque partagée en mémoire

La bibliothèque est un ensemble de fonctions. Elles sont placées entre le tas et la pile :

pile
...
fonctions partagées
...
tas
données
code

Bibliothèque partagée dans le fichier du programme

Il faut ajouter au début du fichier des informations sur :

Lorsque l'OS chargera le fichier, il analysera cette partie puis :

Forme finale d'un process

En mémoire, l'OS ajoute devant chaque groupe d'adresse (une page) ce que le process à le droit de faire :

On a alors quelque chose du genre :

pile                   ; droit de lecture et d'écriture
...
fonctions partagées    ; droit de lecture
...
tas                    ; droit de lecture et d'écriture
données                ; droit de lecture et d'écriture
code                   ; droit d'exécution et de lecture

Sur le disque dur

Le fichier contient l'ensemble des sections text et data plus des données de relocalisation pour les bibliothèques partagées.

Le format de fichier Linux pour les ficher est le format elf : executable and linkable format

Format elf :

relocation des la bibliothèque partagée

pile et tas quand les utiliser

Variables et données d'un process

Cette partie est à retenir, elle est cruciale pour comprendre comment sont organisées les programmes en C.

Constantes et données globales

sans la section data. Stockées dans le fichier du programme. Il faut donc qu'elles soient de taille connues : le programme stockant directement la constante ou laisse assez de place pour stocker les données globales.

Variables

Les variables sont utilisées dans des blocs de codes. Elles sont :

  1. de taille fixe et connue
  2. stockées dans la pile

Une variable est soit :

La taille des variable doit être connue à l'écriture du code. De plus la pile étant souvent de taille réduite (10MiB) par rapport la totalité de la mémoire disponible (plusieurs GiB), on réservera cette approche (variable = tableau) pour les petit tableaux.

Mémoire

Lorsque les tableaux que l'on veut créer ne sont pas de taille fixe, ou trop grand pour être considéré comme une variable, on procède avec une indirection :

La taille de la variable est fixe : 8B tout en conservant une taille variable de la donnée.

Thread

Un process continent :

Chaque thread possède un pointeur IP et une pile qui lui est propre (ainsi que son BP associé), cela s'appelle un contexte d'exécution le reste est partagé avec les autres threads du process. Plusieurs threads ne peuvent pas écrire dans la pile de l'autres mais peuvent se partager les variables du tas et de la section donnée.

Le process est une organisation d'un programme, le thread son exécution.

L'intérêt est que l'OS peut exécuter plusieurs thread d'un process de façon concurrente pour aider à l'exécution du process.

Par exemple pour un jeu :

Ou plus prosaïquement pour multiplier deux matrice, plusieurs thread peuvent chacun calculer un élément du produit sans se gêner.