Processus

Toute machine est dotée d'un système d'exploitation qui a pour fonction de charger les programmes depuis la mémoire de masse et de lancer leur exécution en leur créant des processus.

1. Généralités

Définition

Un processus est l'instance en cours d'exécution d'un programme, gérée par le système d'exploitation.

Un processus informatique est défini par :

Un ensemble d'instructions à exécuter (un programme) ;
Un espace mémoire pour les données de travail ;
Eventuellement, des ressources, comme des descripteurs de fichiers, des ports réseau, etc.

Tous les systèmes d'exploitation modernes (Linux, Windows, MacOS, Android, iOS...) sont capables de gérer l'exécution de plusieurs processus d'une manière qui paraît simultanée.

En réalité, un coeur de processeur ne gère qu'un processus à la fois.

Vu que ça va très vite, on a l'impression que tout s'exécute en même temps (mouvement de la souris, affichage d'une image, word, excel), mais en réalité, le processeur ne s'occupe que d'un processus à la fois. Le fait qu'il va très vite donne cette impression de simultanéité.

Les systèmes d'exploitation attribuent ainsi des "états" aux processus afin de les hiérarchiser.

Les états

---
title: Diagramme d'état d'un processus à connaître
---
stateDiagram-v2
    [*] --> Prêt : Création
    Prêt --> Elu : Election
    Elu --> Bloqué : Blocage
    Elu --> [*] : Fin
    Bloqué-->Prêt : Déblocage

Il est fondamental de bien comprendre que le "chef d'orchestre" qui attribue aux processus leur état "élu", "bloqué" ou "prêt" est le système d'exploitation (OS - Operating System). On dit que le système d'exploitation gère l'ordonnancement des processus (un processus sera prioritaire sur un autre...). Lorsqu'il est créé, le processus passe à l'état prêt. Il intègre une "file d'attente", ça n'est pas forcément son tour directement.

Lorsque c'est à son tour, il passe à l'état élu, ça veut dire que le processeur s'occupe vraiment de faire tourner le programme.

Un processus qui se trouve dans l'état élu peut demander à accéder à une ressource pas forcément disponible instantanément (typiquement lire une donnée sur le disque dur). Le processus ne peut pas poursuivre son exécution tant qu'il n'a pas obtenu cette ressource. En attendant de recevoir cette ressource, il passe de l'état "élu" à l'état "bloqué".

Lorsque la ressource se libère, il repasse en état prêt.

Les règles de gestion de la file d'attente diffèrent selon le mode d'ordonnancement du système d'exploitation.

2. Ordonnancement des processus

Dans un système multi-utilisateurs à temps partagé, plusieurs processus peuvent être présents en mémoire centrale en attente d'exécution. Si plusieurs processus sont prêts, le système d'exploitation doit gérer l'allocation du processeur aux différents processus à exécuter. C'est l'ordonnanceur qui s'acquitte de cette tâche.

Le système d'exploitation d'un ordinateur peut être vu comme un ensemble de processus dont l'exécution est gérée par un processus particulier : l'ordonnanceur (scheduler en anglais).

L'ordonnanceur doit décider quel processus exécuter et pendant combien de temps. Ces deux choix sont souvent contradictoires : aucun algorithme ne peut optimiser simultanément le temps de réponse, l'équité entre processus et l'utilisation du processeur.

Ordonnancement non préemptif

Ordonnanceurs non préemptifs : First-Come First-Served (FCFS) et Short Job First (SJF)

Dans un système à ordonnancement non préemptif ou sans réquisition, le système d'exploitation choisit le prochain processus à exécuter, en général, le Premier Arrivé est le Premier Servi PAPS (ou First-Come First-Served FCFS) ou le plus court d'abord (Short Job First SJF).

Il lui alloue le processeur jusqu'à ce qu'il se termine ou qu'il se bloque (en attente d'un événement). Il n'y a pas de réquisition.

Si l'ordonnanceur fonctionne selon la stratégie SJF, il choisit, parmis le lot de processus à exécuter, le plus court (plus petit temps d'exécution). Cette stratégie est bien adaptée au traitement par lots de processus dont les temps maximaux d'exécution sont connus ou fixés par les utilisateurs car elle offre un meilleur temps moyen de séjour.

Temps de séjour

Le temps de séjour d'un processus (temps de rotation ou de virement) est l'intervalle de temps entre la soumission du processus et son achèvement.

Structures abstraites

D'après vos connaissances acquises, quelles structures de données vous semblent les plus adaptées pour programmer FCFS, puis pour SJF?

Exemple Ordonnancement FCFS

On doit trouver l'ordonnancement des processus sachant leur temps d'arrivage et la durée d'exécution prévue:

Processus	Temps d'exécution	Temps d'arrivage
A	3	0
B	6	1
C	4	4
D	2	6
E	1	7

Voici ce que ça donnerait si ils pouvaient être élus en même temps au niveau de l'exécution. !!!MAIS CA N'EST PAS LE CAS!!!!

gantt
    dateFormat mm
    axisFormat %M
    A : 00, 3m
    B : 01, 6m
    C : 04, 4m
    D : 06, 2m
    E : 07, 1m

Au temps 0, seulement le processus A est dans le système et il s'exécute. Au temps 1 le processus B arrive mais il doit attendre qu'A termine car il a encore 2 unités de temps. Ensuite B s'exécute pendant 6 unités de temps. Au temps 4, 6, et 7 les processus C, D et E arrivent mais B n'a pas fini. Une fois que B a terminé, C, D et E entrent au système dans l'ordre (tout ça en supposant qu'il n'y a pas de blocage)

Voici donc le schéma d'exécution:

gantt
    dateFormat mm
    axisFormat %M
    Arrivage de A :milestone, 00, 0d
    A : a1, 00, 3m
    Arrivage de B :milestone, 01, 0d
    B : b1, after a1, 6m
    Arrivage de C :milestone, 04, 0d
    C : c1, after b1, 4m
    Arrivage de D :milestone, 06, 0d
    D : d1, after c1, 2m
    Arrivage de E :milestone, 07, 0d
    E : e1, after d1, 1m

Processus	Temps d'exécution	Temps d'arrivage	Temps de terminaison
A	3	0	3
B	6	1	9
C	4	4	13
D	2	6	15
E	1	7	16

Le temps de séjour pour chaque processus est obtenu soustrayant le temps d'entrée du processus du temps de terminaison. Ainsi : Le temps d'attente est calculé soustrayant le temps d'exécution du temps de séjour :

Processus	Temps de sejour	Temps d'attente
A	\(3-0 = 3\)	\(3-3 = 0\)
B	\(9-1 = 8\)	\(8-6 = 2\)
C	\(13-4 = 9\)	\(9-4 = 5\)
D	\(15-6 = 9\)	\(9-2 = 7\)
E	\(16-7 = 9\)	\(9-1 = 8\)

Tout simplement, on peut déduire ces informations du dessin si on l'a fait au lieu d'apprendre des formules.

On calcule tout bêtement les moyennes de ces colonnes si on nous demande des temps moyens.

Exemple Ordonnancement SJF

On doit trouver l'ordonnancement des processus sachant leur temps d'arrivage et la durée d'exécution prévue:

Processus	Temps d'exécution	Temps d'arrivage
A	3	0
B	6	1
C	4	4
D	2	6
E	1	7

Ici, l'ordre de priorité sera donc A,B,E,D,C car E, D et C arrivent pendant l'exécution de B. A la fin de B, le plus court est choisi, donc c'est E, puis D, puis C.

gantt
    dateFormat mm
    axisFormat %M
    Arrivage de A :milestone, 00, 0d
    A : a1, 00, 3m
    Arrivage de B :milestone, 01, 0d
    B : b1, after a1, 6m
    Arrivage de C :milestone, 04, 0d
    C : c1, after d1, 4m
    Arrivage de D :milestone, 06, 0d
    D : d1, after e1, 2m
    Arrivage de E :milestone, 07, 0d
    E : e1, after b1, 1m

Je vous laisse créer le tableau comportant les temps d'attente et de terminaison.

Ordonnancement préemptif

Dans un schéma d'ordonnanceur préemptif, ou avec réquisition, pour s'assurer qu'aucun processus ne s'exécute pendant trop de temps, les ordinateurs ont une horloge électronique qui génère périodiquement une interruption. A chaque interruption d'horloge, le système d'exploitation reprend la main et décide si le processus courant doit poursuivre son exécution ou s'il doit être suspendu pour laisser place à un autre. S'il décide de suspendre son exécution au profit d'un autre, il doit d'abord sauvegarder l'état des registres du processeur avant de charger dans les registres les données du processus à lancer. C'est qu'on appelle la commutation de contexte ou le changement de contexte. Cette sauvegarde est nécessaire pour pouvoir poursuivre ultérieurement l'exécution du processus suspendu. Le temps d'allocation du processeur à un processus est appelé quantum. Le processeur passe d'un processus à l'autre à chaque expiration du quantum, donnant l'impression de parallélisme (pseudo-parallélisme).

Pour aller plus loin : Shortest Remaining Time (SRT)

Version préemptive de SJF : quand un processus arrive, s'il a un temps d'exécution restant inférieur à celui du processus en cours, il prend immédiatement la main.

Ordonnancement circulaire

L'algorithme du tourniquet, circulaire ou round robin est un algorithme ancien, simple, fiable et très utilisé. Il mémorise dans une file du type FIFO (First In First Out) la liste des processus prêts, c'est-à-dire en attente d'exécution.

alt text

Choix du processus à exécuter:

Il alloue le processeur au processus en tête de file, pendant un quantum de temps. Si le processus se bloque ou se termine avant la fin de son quantum, le processeur est immédiatement alloué à un autre processus (celui en tête de file). Si le processus ne se termine pas au bout de son quantum, son exécution est suspendue. Le processeur est alloué à un autre processus (celui en tête de file). Le processus suspendu est inséré en queue de file. Les processus qui arrivent ou qui passent de l'état bloqué à l'état prêt sont insérés en queue de file.

Choix de la valeur du quantum:

Un quantum trop petit provoque trop de commutations et abaisse l'efficacité du processeur. Un quantum trop grand augmente le temps de réponse des processus courts.

Exemple

Soient deux processus A et B prêts tels que A est arrivé en premier suivi de B, 2 unités de temps après. Les temps de UCT nécessaires pour l'exécution des processus A et B sont respectivement 15 et 4 unités de temps. Le temps de commutation est supposé nul. Calculer le temps de séjour de chaque processus A et B, le temps moyen de séjour, le temps d'attente, le temps moyen d'attente, et le nombre de changements de contexte pour :

SRT
Round robin (quantum = 10 unités de temps)
Round robin (quantum = 3 unités de temps)

Il faut faire des dessins

Exemple SRT

Schéma d'exécution:

Quand B arrive, il reste 13 unités de temps à A. B prend donc la main avec ses 4 unités de temps, puis A reprend son exécution et se termine.

gantt
    dateFormat mm
    axisFormat %M
    Arrivage de A :milestone, 00, 0d
    A : a1, 00, 2m
    Arrivage de B :milestone, 02, 0d
    B : b1, after a1, 4m
    A : a2, after b1, 13m

Complétez:

Processus	Temps de sejour	Temps d'attente
A
B

Temps moyen de séjour:
Temps moyen d'attente:

Exemple Round Robin (q=10)

A prend direct 10 unités (le max) puis repart dans sa file.
B prend ses 4 unités et se termine.
A est défilé, prend ses 5 unités restantes et se termine.

gantt
    dateFormat mm
    axisFormat %M
    Arrivage de A :milestone, 00, 0d
    A : a1, 00, 10m
    Arrivage de B :milestone, 02, 0d
    B : b1, after a1, 4m
    Terminaison B :milestone, after b1, 0d
    A : a2, after b1, 5m
    Terminaison A :milestone, after a2, 0d

Complétez:

Processus	Temps de sejour	Temps d'attente
A
B

Temps moyen de séjour:
Temps moyen d'attente:

Exemple Round Robin (q=3)

Commentez le schéma d'exécution suivant:

gantt
    dateFormat mm
    axisFormat %M
    Arrivage de A :milestone, 00, 0d
    A : a1, 00, 3m
    Arrivage de B :milestone, 02, 0d
    B : b1, after a1, 3m
    A : a2, after b1, 3m
    B : b2, after a2, 1m
    Terminaison B :milestone, after b2, 0d
    A : a3, after b2, 9m
    Terminaison A :milestone, after a3, 0d

Complétez:

Processus	Temps de sejour	Temps d'attente
A
B

Temps moyen de séjour:
Temps moyen d'attente:

Bidouiller du processus > Les trucs qui servent tout le temps

Un processus peut créer un ou plusieurs processus à l'aide d'une commande système ("fork" sous les systèmes de type Unix).

Imaginons un processus A qui crée un processus B. On dira que A est le père de B et que B est le fils de A. B peut, à son tour créé un processus C (B sera le père de C et C le fils de B). On peut modéliser ces relations père/fils par une structure arborescente

Si un processus est créé à partir d'un autre processus, comment est créé le tout premier processus ?

Sous un système d'exploitation comme Linux, au moment du démarrage de l'ordinateur un tout premier processus (appelé processus 0 ou encore Swapper) est créé à partir de "rien" (il n'est le fils d'aucun processus). Ensuite, ce processus 0 crée un processus souvent appelé "init" ("init" est donc le fils du processus 0).

La base 1

Pour installer les utilitaires de gestion des processus, entrez la commande suivante dans le shell de MSYS2 (Notez que sous linux, ces utilitaires sont intallés par défaut)

pacman -S procps-ng psmisc

Lancez le programme perl qui vous a été donné:

./process_create.pl

Ce programme permet de créer une arborescence de processus (qui ne font pas grand chose à part être là).

Le prompt ne revient pas. En effet, le processus que vous avez lancé est en "avant plan" (foreground).

On va le mettre en "arrière plan" (background). Pour commencer, appuyez sur Ctrl+Z

Cette commande permet d'envoyer un signal de suspension spécial SIGTSTP (Signal Terminal STOP) au processus en avant plan dans un terminal.

Exécutez maintenant la commande ps. Elle permet de lister les processus (sous MSYS2, on ne voit pas tout, mais c'est justement bien suffisant).

$ ps
      PID    PPID    PGID     WINPID   TTY         UID    STIME COMMAND
     7359     628    7359      24820  cons0     197612 17:12:20 /usr/bin/ps
      628       1     628      99764  cons0     197612 17:06:56 /usr/bin/bash
S    7328     628    7328      71104  cons0     197612 17:11:38 /usr/bin/perl
...
...

Ici, un processus associé à l'exécution de notre programme perl est en troisième ligne. Il est suspendu, mais il existe toujours.

Commande ps

Chaque ligne représente un processus.
PID signifie Processus ID. C'est l'identifiant unique donné au processus par le système d'exploitation.
PPID signifie Parent Processus ID. C'est l'identifiant du processus qui a créé ce processus.
COMMAND représente le programme que fait tourner le processus
Le reste on s'en fiche

Vu qu'il y a des parents et des enfants on se doute bien maintenant que ça fait un arbre de processus. On voit d'ailleurs que c'est le bash qui a créé les 2 autres processus. Si vous ne voyez pas, demandez.

Vous pouvez maintenant demander sa mise en arrière plan avec la commande bg.

Si vous réexécutez la commande ps, le S aura disparu.

Remettez le processus en avant plan avec la commande fg

On va maintenant killer le processus. Entrez la combinaison de touches Ctrl+C. Cette combinaison envoie un signal SIGINT (interruption) au processus en avant plan, qui met fin à son exécution.

refaites un ps, le processus perl a disparu.

Vous avez la base de la gestion des process dans un terminal. (Et oui, on peut causer avec les processus par le biais de signaux, on ne les abordera pas, mais il vous faut le guide de survie minimum)

On y retourne (la base 2)

Pour lancer directement le programme en arrière plan, lancez la commande

./process_create.pl &

Les processus créés ne vivront qu'une minute. Relancez la commande si les processus disparaissent.

Comme vous l'avez deviné, mettre un & à la fin d'une commande permet de lancer le processus associé en arrière plan.

Vu que le process écrit sur la sortie standard, il faut appuyer sur entrée pour avoir le retour du prompt.

vous pouvez observer les processus créés grâce à la commande top. Elle dispose d'une multitude de paramètres et d'interactions possibles. Pour quitter la commande top, appuyez sur la touche q

Vous pouvez demander l'affichage de l'arborescence des processus avec la commande pstree -p

Exercices à réaliser après avoir travaillé et compris le cours.

Q1. Qu'est-ce qu'un processus informatique ?
Q2. Quels sont les états dans lequel un processus peut se trouver ?
Q3. Quel dispositif attribue à un processus un état ?
Q4. Dans quel état se trouve un processus en cours d'exécution par le microprocesseur ?
Q5. Par quoi est identifié un processus ?
Q6. Qu'est-ce que l'ordonnancement des processus ?
Q7. Nommez les 2 grandes famille d'ordonnanceurs et décrivez leur différence fondamentale.
Q8. Considérons cinq processus notés A, B, C, D et E dans une file d'attente. Les durées d'exécution et leurs dates d'arrivage respectifs sont donnés dans le tableau ci-dessous.

Processus	Durée d'exécution	Date d'arrivage
A	10	0
B	1	1
C	2	2
D	1	3
E	5	4

Donner le schéma d'exécution des algorithmes d'ordonnancement suivants :

First-Come First-Served (FCFS)
Short Job First (SJF)
Shortest Remaining Time (SRT)
Round Robin (RR) avec un quantum de 2

Quelle politique d'ordonnancement donne le meilleur résultat, c'est-à-dire celui correspondant à la durée minimale d'attente moyenne par processus ?

Q9. Trois processus A, B et C ont été chargés dans un système informatique comme indiqué ci-dessous :

Processus	Durée d'exécution	Date d'arrivage
A	4	0
B	2	0
C	1	3

Donner le schéma d'exécution des algorithmes d'ordonnancement suivants (il n'est pas requis de connaître ces termes. Ils vous seront rappelés. Round Robin est quand même super utilisé, c'est bien de se souvenir de son fonctionement):

First-Come First-Served (FCFS)
Short Job First (SJF)
Shortest Remaining Time (SRT)
Round Robin (RR) avec un quantum de 1

Quelle politique d'ordonnancement donne le meilleur résultat c'est-à-dire celui correspondant à la durée minimale d'attente moyenne par processus ?

Q10. Quelle commande permet de lister les processus en cours sur la machine?
Q11. Quelle commande permet de terminer un processus à partir de son PID ?
Q12. Quelle combinaison de touches permet de terminer le processus en avant plan dans un terminal ?
Q13. Réalisez le diagramme d'état d'un processus.