1. Description

Processus (informatique)

Un processus (en anglais, process), en informatique, est un programme en cours d’exécution par un ordinateur. De façon plus précise, il peut être défini comme :

  • Un ensemble d’instructions à exécuter, pouvant être dans la mémoire morte, mais le plus souvent chargé depuis la mémoire de masse vers la mémoire vive ;

  • un espace d’adressage en mémoire vive pour stocker la pile, les données de travail, etc. ;

  • des ressources permettant des entrées-sorties de données, comme des ports réseau.

L’exécution d’un processus dure un certain temps, avec un début et (parfois) une fin. Un processus peut être démarré par un utilisateur par l’intermédiaire d’un périphérique ou bien par un autre processus : les « applications » utilisateur sont des ensembles de processus.

— Wikipédia

Les processus sont gérés par le système d’exploitation.

Rappel :

Le système d’exploitation a pour rôle de masquer la complexité matérielle de la machine en offrant à l’utilisateur une interface entre les applications et les périphériques :

abstraction peripheriques
Figure 1. OS : abstraction des périphériques

Dans les systèmes d’exploitation multi-tâches, l’ordonnanceur (scheduler) est chargé choisir le processus à exécuter. Celui-ci est élu et dispose alors de toutes les ressources matérielles disponible sur la machine (processeur, RAM et périphériques).

gestion processus
Figure 2. Gestion des processus

Les autres processus sont soit terminés, soit :

  • en attente d’exécution : prêts

  • mis en sommeil car ils attendent une ressources indisponible : bloqués

Les processus prêts sont mis dans une file en attente d’être exécuter.

etats processus
Figure 3. Etats des processus

Le processeur paratage son temps entre les différents processus à exécuter

Il existe plusieurs modes d’ordonnancement :

  • Temps partagé (time sharing system) : comportement par défaut sur les O.S. comme Linux

  • Temps réel (realtime scheduling) : suivant des algorithmes comme Round Robin ou FIFO basés sur des priorités entre tâches ou Earliest Deadline First utilisant des temps d’expiration des tâches.

taches priorites
Figure 4. Gestion des priorités entre taches

2. Gestion des processus sous Linux

Linux est un système d’exploitation multi-tâches et multi-utilisateurs.

De ce fait, il est capable de gérer simultanément un ensemble de programmes lancés par un ou plusieurs utilisateurs.

Un processus ou tâche est une instance d’un programme en cours d’exécution. Ainsi, le fait de lancer 3 fois un même programme provoquera la création de 3 processus distincts.

Un processus est identifié par le système à l’aide d’un numéro appelé PID (Process IDentifier).

Il est souvent utile de connaître, contrôler voire de tuer les processus qui tournent sur une machine.

C’est ce qui va être abordé maintenant.

2.1. Visualiser les processus.

Les 3 commandes les plus utilisées pour visualiser les processus sont :

  • ps : permet d’afficher des informations à un instant donné sur les processus présents en mémoire. Une large gamme d’options est disponible. Celles-ci permettent d’obtenir à peu près toutes les informations sur les processus.

  • top : ajoute un côté dynamique à l’affichage des processus dans le sens où il met à jour automatiquement les informations affichées à l’écran. Le délai de rafraichissement des informations par défaut est de 3 secondes mais ce délai est configurable. L’appui sur la barre d’espace provoque une mise à jour immédiate des informations.

  • pstree : affiche les processus sous la forme d’une arborescence qui met en évidence la parenté entre ceux-ci.

2.1.1. Travail à faire : Affichage des processus en cours d’exécution

  • Lancer 2 interpréteurs de commandes puis exécuter dans l’un d’eux la commande top.
    Exécuter dans l’autre, les commandes :

    • ps

    • ps -a

  • Interpréter les résultats des 2 commandes.

  • Qu’indique selon vous la colonne TTY ?

  • Parcourir la page de manuel de ps et donner la signification des options :

    • -f

    • -e ou -A

    • -l

  • Exécuter ces commandes pour observer leurs résultats.

  • Quelle est la signification de la colonne PPID lorsque les options -f ou -l sont spécifiées ?

  • Qu’indique la colonne S affichée lorsque l’option -l est utilisée ?

  • Afficher l’arborescence de processus avec pstree.

  • Quel est le nom du processus situé à la racine de cette arborescence ? (Celui-ci est le 1ier processus lancé suite de l’initialisation de l’OS).

  • Déterminer son PID.

  • Dans le terminal où s’exécute top taper h pour obtenir de l’aide et trouver comment trier les processus par PID, utilisation du CPU, occupation mémoire.

Correction

  • ps : affiche les processus utilisateur en cours dans le terminal courant

  • pa -a : affiche nes processus utilisateur en cours dans tous les terminaux

  • La colonne TTY identifie le terminal dans lequel est exécuter le processus

  • -f : Do full-format listing

  • -e : Select all processes. Identical to -A

  • -l : Long format

  • La colonne PPID indique qui est le père d’un processus en l’idendifiant par son PID

  • La colonne S indique dans quel état se trouve un processus

  • Le processus à la racine de l’arborescence a pour PID 1. Son nom dépend de l’OS et de sa version. Sur un système Linux standard, il s’agit du processus init

  • Durant l’exécution de la commande top :

    • N : Tri par PID (état normal)

    • P : Tri par utilisation du CPU

    • M : Tri par utilisation de la mémoire

2.2. Agir sur un processus avec les signaux

Les signaux sont un moyen de communication avec les processus. Linux prend en charge 63 signaux mais seuls un nombre restreint d’entre eux sont utilisés au quotidien.

La façon la plus commune d’envoyer les signaux à un processus est d’utiliser la commande kill. Celle-ci prend en option le numéro du signal à envoyer et le PID du processus destinataire en argument.

La commande kill sera notamment utilisée pour tuer un processus qui ne répond plus mais ce n’est pas sa seule utilisation.

Se souvenir que la commande kill permet d’envoyer toutes sortes de signaux et non simplement le signal nommé SIGKILL qui requiert l’arrêt brutal d’un processus.

Quelques combinaisons de touches permettent également d’envoyer des signaux au processus en cours :

  • Ctrl+C : envoie le signal SIGINT qui provoque généralement l’arrêt du processus

  • Ctrl+Z : envoie le signal SIGTSTP qui demande la suspension du processus

Une autre façon d’envoyer un signal est d’utiliser la commande killall qui prend en argument, non pas le PID du processus, mais son nom. Ceci permet notamment de quitter toutes les instances d’un programme sans avoir à connaitre leur PID ou à leur envoyer individuellement le signal SIGINT.

2.2.1. A faire : Utilisation des signaux

  • Lancer 2 instances de la commande top dans 2 terminaux

  • Consulter la page de manuel de signal (catégorie 7) et relever les n° des signaux : SIGINT, SIGQUIT, SIGKILL, SIGTERM

  • Quitter une des instances de top en lui envoyant le signal SIGTERM depuis un 3ième terminal

  • Relancer une instance de top dans son terminal d’origine

  • Quitter de nouveau l’instance de top en lui envoyant cette fois-ci le n° de signal correspondant à SIGKILL

  • Relancer l’instance de top dans son terminal d’origine

  • Taper Ctrl+C et constater que le programme se termine

  • Relancer l’instance de top dans son terminal d’origine

  • Taper Ctrl+Z

  • Dans le 3ième terminal, taper la commande ps -al.

  • Combien d’instances de top résident encore en mémoire ?

  • Tuer le processus pour lequel la commande précédente indique T dans la colonne S

  • Relancer la commande top dans son terminal d’origine

  • Taper la commande killall top.

  • Quelle action est provoquée par cette dernière commande ?

Correction

  • SIGINT : 2

  • SIGQUIT : 3

  • SIGKILL : 9

  • SIGTERM : 15

  • killall top : termine toutes les instances de top quelquesoit le terminal dans lequel elle est exécutée.

3. Ordonnancement des processus

3.1. Motivation

Dans un système multi-tâches, plusieurs processus/threads (processus élementaires) sont en concurrence pour l’obtention de temps processeur.

S’il n’y a qu’un seul processeur, un choix doit être fait quant au prochain processus à exécuter.

motivations
Figure 5. Un seul processeur, plusieurs tâches à exécuter

3.2. Définition

La partie du système d’exploitation qui effectue ce choix se nomme l’ordonnanceur (scheduler) et l’algorithme qu’il emploie s’appel algorithme d’ordonnancement (scheduling algorithm) :

  • Sélectionne le bon processus à exécuter

  • fait un usage efficace du processeur, car le passage d’un processus à l’autre est coûteux en termes de temps de traitement

Les objectifs d’un algorithme d’ordonnancement sont entre autres :

  • S’assurer que chaque processus en attente d’exécution reçoive sa part de temps processeur.

  • Minimiser le temps de réponse.

  • Utiliser le processeur à 100%.

  • Prendre en compte des priorités.

  • Être prédictible.

3.3. Quand ordonnancer

  • Lorsqu’un nouveau processus est créé : il faut se décider s’il faut exécuter d’abord le processus parent ou le processus enfant.

  • Lorsqu’un processus se termine : un autre processus doit être choisi parmi les processus prêts

  • Lorsqu’un processus se bloque : un autre processus doit être sélectionner pour être exécuter

  • Lorsqu’une interruption d’entrée/sortie se produit : il faut prendre une décision d’ordonnancement parmi les processus qui étaient bloqué en attente d’entrée/sortie

etats processus2
Figure 6. Etats des processus et ordonnancement

  • Une interruption est un arrêt temporaire de l’exécution

  • Les interruptions peuvent être matérielles ou logicielles

    • Une interruption logigielle peut avoir lieu lorsque le processeur détecte une erreur à l’exécution (division par zéro, …​)

    • Les interruptions matérielles sont générées par les périphériques (clavier, disques, USB, horloge, …​) pour signaler au processeur des évènements. Le CPU arrête momentanément l’exécution d’un processus pour exécuter la requête d’un périphérique.

  • On utilise les interruptions d’horloge pour commuter les tâches dans les systèmes multitâches.

  • Généralement, une interruption périodique est déclenchée par une horloge et l’ordonnanceur est alors mis en action.

Les algorithmes d’ordonnancement sont classifiés selon qu’ils réagissent ou non aux interruptions de l’horloge :

  • Ordonnancement préemptif : réagit aux interruptions de l’horloge

  • Ordonnancement non préemptif : ne réagit pas aux interruptions de l’horloge

3.4. Algorithmes d’ordonnancement non-préemptifs

3.4.1. Définition

Sélectionne un processus, puis le laisse s’exécuter jusqu’à ce qu’il se bloque, ou qu’il libère volontairement le processeur :

  • Même s’il s’exécute pendant des heures, il ne sera pas suspendu de force

  • Aucune décision d’ordonnancement n’intervient pendant les interruptions d’horloge

3.4.2. Premier arrivé, premier servi

Implémenter via une file d’attente FIFO

Exemple :

Considérons les processus P1, P2, P3 qui arrivent successivement au temps 0 avec les temps d’exécutions suivants :

  • P1 : 24ms

  • P2 : 3ms

  • P3 : 3ms

paps1
Figure 7. Frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type "premier arrivé-premier servi"

Temps d’attente :

  • P1 : 0

  • P2 : 24ms

  • P3 : 24+3 = 27ms

Temps d’attente moyen des processus avant de pouvoir être exécuté : \( (0+24+27)/3 = 17ms \)

3.4.3. A faire : Ordonnancement "premier arrivé-premier servi"

Soit les processus P1, P2, P3 qui arrivent successivement au temps 0 avec les temps d’exécutions suivants :

  • P1 : 3ms

  • P2 : 3ms

  • P3 : 24ms

Quel est le temps d’attente moyen avant l’exécution des processus ?

  • \((3+3+24)/3=10ms\)
  • \((0+3+6)/3=3ms\)
  • \((3+6+33)/3=14ms\)
  • \((0+3+27)/3=10ms\)

Soit les processus P1, P2, P3 qui arrivent successivement au temps 0 avec les temps d’exécutions suivants :

  • P1 : 3ms

  • P2 : 24ms

  • P3 : 3ms

Quel est le temps d’attente moyen avant l’exécution des processus ?

  • \((3+3+24)/3=10ms\)
  • \((0+3+6)/3=3ms\)
  • \((3+6+33)/3=14ms\)
  • \((0+3+27)/3=10ms\)

3.4.4. Shortest job first

L’ordonnanceur choisi, parmi le lot de processus à exécuter, le plus court (plus petit temps d’exécution).

Cette stratégie offre le temps moyen d’attente minimale.

Exemple :

Considérons les processus P1, P2, P3 et P4 qui arrivent simultanément au temps 0 avec les temps d’exécutions suivants :

  • P1 : 6ms

  • P2 : 8ms

  • P3 : 7ms

  • P4 : 3ms

sjf1
Figure 8. Frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type "SJF"

Temps d’attente :

  • P4 : 0

  • P1 : 3ms

  • P3 : 6+3 = 9ms

  • P2 : 7+6+3 = 16ms

Temps d’attente moyen des processus avant de pouvoir être exécuté : \( (0+3+9+16)/4 = 7ms \)

3.4.5. A faire : Ordonnancement "Shortest Job First"

Soit les processus P1, P2, P3 et P4 qui arrivent simultanément au temps 0 avec les temps d’exécutions suivants :

  • P1 : 4ms

  • P2 : 6ms

  • P3 : 2ms

  • P4 : 5ms

Dans quel ordre les processus seront-ils exécutés ?

  • P3 - P1 - P4 - P2
  • P1 - P3 - P4 - P2
  • P4 - P2 - P3 - P1
  • P3 - P2 - P1 - P4

Quel est le temps d’attente moyen avant l’exécution des processus ?

  • \((2+4+5+6)/4=4,25ms\)
  • \((0+3+4+5)/4=3ms\)
  • \((0+2+6+11)/4=4,75ms\)
  • \((2+6+11+17)/4=9ms\)

3.4.6. A faire : Ordonnancements non préemptifs

Soit les cinq processus A, B, C, D et E, dont les temps d’exécution et leurs temps d’arrivée respectifs sont les suivants: :

Processus Temps exécution (ms) Temps arrivée (ms)

A

3

0

B

6

1

C

4

4

D

2

6

E

1

7

Dans quel ordre les processus seront-ils exécutés par un ordonnanceur "Premier arrivé-Premier servi" ?

  • A - B - C - D - E
  • E - D - A - C - B
  • E - D - C - B - A
  • A - B - E - D - C

Le temps de séjour du procesus dans l’ordonnanceur est définit par : \( t_{séjour} = t_{fin} - t_{arrivée} \)

  • le processus A arrive à \(t_a=0\) et se termine après son exécution de \(3ms\) à \(t_f=3ms\) : \(t_s = 3ms\)

  • le processus B arrive à \(t_a=1\) et se termine après son exécution de \(6ms\) à \(t_f=9ms\) : \(t_s = 8ms\)

Quel est le temps de séjour moyen des processus ?

  • \((0+1+4+6+7)/5=3,6ms\)
  • \((3+9+13+15+16)/5=5,6ms\)
  • \((3+8+9+9+9)/5=7,6ms\)
  • \((3+8+9+13+15)/5=9,6ms\)

Le temps d’attente du procesus avant de pouvoir être exécuté est définit par : \( t_{attente} = t_{séjour} - t_{exécution} \)

  • le processus A séjourne pendant \(t_s=3ms\) et est exécuté pendant \(t_e=3ms\) : \(t_a = 0ms\)

  • le processus B séjourne pendant \(t_s=8ms\) et est exécuté pendant \(t_e=6ms\) : \(t_a = 2ms\)

Quel est le temps d’attente moyen des processus ?

  • \((0+1+4+6+7)/5=3,6ms\)
  • \((3+9+13+15+16)/5=5,6ms\)
  • \((3+8+9+9+9)/5=7,6ms\)
  • \((0+2+5+7+8)/5=4,4ms\)
Correction
paps2
Figure 9. Frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type "PAPS"

Quel est le temps moyen d’excution des processus ?

  • \((0+1+4+6+7)/5=3,6ms\)
  • \((3+9+13+15+16)/5=5,6ms\)
  • \((3+6+4+2+1)/5=3,2ms\)
  • \((3+8+9+9+9)/5=7,6ms\)
Correction

Il y a \(5\) processus et la durée totale d’exécution est de \(16ms\) : \(temps \quad moyen \quad d’execution = 16/5 = 3,2ms\)

Soit les cinq processus A, B, C, D et E, dont les temps d’exécution et leurs temps d’arrivée respectifs sont les suivants: :

Processus Temps exécution (ms) Temps arrivée (ms)

A

3

0

B

6

1

C

4

4

D

2

6

E

1

7

Dans quel ordre les processus seront-ils exécutés par un ordonnanceur "Shortest Job First" ?

  • A - B - C - D - E
  • E - D - A - C - B
  • E - D - C - B - A
  • A - B - E - D - C

Quel est le temps de séjour moyen des processus ?

  • \((0+1+4+6+7)/5=3,6ms\)
  • \((3+9+13+15+16)/5=5,6ms\)
  • \((3+8+9+9+9)/5=7,6ms\)
  • \((3+8+3+6+12)/5=6,4ms\)

Quel est le temps d’attente moyen des processus ?

  • \((0+1+4+6+7)/5=3,6ms\)
  • \((0+2+2+4+8)/5=3,2ms\)
  • \((3+8+9+9+9)/5=7,6ms\)
  • \((0+2+5+7+8)/5=4,4ms\)
Correction
sjf2
Figure 10. Frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type "SJF"

Durant l’exécution du processus B, les processus C, D et E arrivent dans la file d’attente. Ils sont exécutés du plus cours au plus long.

Quel est le temps moyen d’excution des processus ?

  • \((0+1+4+6+7)/5=3,6ms\)
  • \((3+9+13+15+16)/5=5,6ms\)
  • \((3+6+4+2+1)/5=3,2ms\)
  • \((3+8+9+9+9)/5=7,6ms\)
Correction

Il y a \(5\) processus et la durée totale d’exécution est de \(16ms\) : \(temps \quad moyen \quad d’execution = 16/5 = 3,2ms\)

3.5. Algorithmes d’ordonnancement préemptifs

3.5.1. Définition

Un ordonnanceur préemptif s’assure qu’aucun processus ne s’exécute pendant trop de temps.

Une horloge électronique génère périodiquement une interruption.

A chaque interruption d’horloge, l’ordonnanceur reprend la main et décide si le processus courant doit :

  • poursuivre son exécution

  • être suspendu pour laisser place à un autre

Si le processus courant doit suspendre son exécution au profit d’un autre, le système d’exploitation doit d’abord sauvegarder le contexte du processus avant de charger le contexte du processus à lancer.

On appelle cette action 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 contexte est sauvegardé dans la RAM si elle est suffisante, sinon, il est sauvegardé dans une mémoire secondaire (Swapping).

Swapping
Figure 11. Swapping

Généralement, on néglige dans les calculs ce temps de commutation mais cette approximation n’est valable que si le système dispose de suffisamment de ressources (RAM en particulier) et n’a pas recours au swapping.

  • Le temps d’allocation du processeur au processus est appelé quantum.

La commutation entre processus doit être rapide, c’est-à-dire, exiger un temps nettement inférieur au quantum.

3.5.2. Shortest Remaining Time

Ordonnancement du plus petit temps de séjour : c’est la version préemptive de l’algorithme Shortest Job First

Avec l’ordonnancement SRT, si un processus dont le temps d’exécution est plus court que le reste du temps d’exécution du processus en cours de traitement est disponible, alors il prendra sa place.

Exemple :

Considérons les processus P1, P2, P3 et P4 dont les temps d’arrivées et les temps d’exécutions sont les suivants :

Processus Temps exécution (ms) Temps arrivée (ms)

P1

8

0

P2

4

1

P3

9

2

P4

5

3

  • P1 commence à \(t=0\), il est le seul processus dans la file d’attente

  • P2 arrive à \(t=1ms\) :

    • Le temps restant à P1 est de \(7ms\) ce qui est plus long que le temps demandé par P2 (\(4ms\))

  • P2 est exécuté et P1 retourne dans le file d’attente

  • …​

srf1
Figure 12. Frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type SRT

Temps d’attente :

  • P1 : commence à \(0\) puis est interrompu à \(1ms\) et reprend à \(10ms\) : \(10-1=9ms\)

  • P2 : démarre dès son arrivée et est intégralement exécuté: \(0ms\)

  • P3 : commence à \(17ms\) et est entré dans la file à \(2ms\) : \(17-2=15ms\)

  • P4 : commence à \(5ms\) et est entré dans la file à \(3ms\) : \(5-3=2ms\)

Temps d’attente moyen des processus avant de pouvoir être exécuté : \( (9+0+15+2)/4 = 6,5ms \)

Remarque : Avec l’algorithme d’ordonnancement Shortest Job First (non-préemptif) ce temps aurait été de \(7,5ms\).

Rapel :

  • Le temps de séjour du procesus dans l’ordonnanceur est définit par : \( t_{séjour} = t_{fin} - t_{arrivée} \)

  • Le temps d’attente du procesus avant de pouvoir être exécuté est définit par : \( t_{attente} = t_{séjour} - t_{exécution} \)

Processus Temps exécution (ms) Temps arrivée (ms) Temps séjour Temps attente

P1

8

0

17-0 = 17

17-8 = 9

P2

4

1

5-1 = 4

4-4 = 0

P3

9

2

26-2 = 24

24-9 = 15

P4

5

3

10-3 = 7

7-5 = 2

3.5.3. A faire : Ordonnancement "Shortest Remaining First"

P1, P2, P3 et P4 dont les temps d’arrivées et les temps d’exécutions sont les suivants :

Processus Temps exécution (ms) Temps arrivée (ms)

P1

7

0

P2

2

1

P3

5

2

P4

1

3

Dans quel ordre les processus seront-ils exécutés ?

  • P1 - P2 - P3 - P4
  • P1 - P2 - P4 - P1 - P2 - P3
  • P1 - P2 - P3 - P1 - P4 - P2
  • P1 - P2 - P4 - P3 - P1

Quel est le temps d’attente moyen avant l’exécution des processus ?

  • \((0+2+4+6)/4=3ms\)
  • \((9+8+5+2)/4=6ms\)
  • \((8+0+2+0)/4=2,5ms\)
  • \((0+2+6+8)/4=4ms\)
Correction
srf3
Figure 13. Frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type "SRF"

3.5.4. Round Robin

Ordonnancement circulaire : appelé également algorithme du tourniquet ou Round Robin est un algorithme ancien, simple, fiable et très utilisé.

L’algorithme RR 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.

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.

    • Pour éviter la famine, un nouveau processus est insérer en fin de file, pour ne pas doubler les processus existants

rr1
Figure 14. Principe de l’algorithme Round Robin

Exemple :

Soit un ordonnancement de type RR dont le quantum est de \(4ms\). Considérons les processus P1, P2, P3 arrivés successivement et dont les temps d’exécutions sont les suivants :

Processus Temps exécution (ms)

P1

24

P2

3

P3

3

  • P1 est en tête de la file d’attente. Il a le processeur pour \(4ms\) puis est remis dans la file d’attente.

  • P2 est le suivant dans la file, il prend sa place et occupe le processeur pendant \(3ms\) (sa durée d’exécution est plus courte que le quantum).

  • P3 est le suivant dans la file, il prend sa place et occupe le processeur pendant \(3ms\) (sa durée d’exécution est plus courte que le quantum).

  • P1 est le suivant dans la file, il prend sa place et s’execute tant qu’il n’y a pas de nouveaux processus.

rr2
Figure 15. Frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type RR

Temps d’attente :

  • P1 : commence à \(0\) puis est interrompu à \(4ms\) et reprend à \(10ms\) : \(10-4=6ms\)

  • P2 : démarre dès son arrivée et est intégralement exécuté: \(0ms\)

  • P3 : démarre dès son arrivée et est intégralement exécuté: \(0ms\)

Temps d’attente moyen des processus avant de pouvoir être exécuté : \( (6+0+0)/3 = 2ms \)

3.5.5. A faire : Ordonnancement "Round Robin"

A et B sont deux processus dont les temps d’arrivées et les temps d’exécutions sont les suivants :

Processus Temps exécution (ms) Temps arrivée (ms)

A

15

0

B

4

2

Dans quel ordre les processus seront-ils exécutés si l’ordonnancement RR se fait avec un quantum de \(3ms\) et le temps de commutation est supposé nul ?

  • A - B
  • A - B - A - A - A - A
  • A - B - A - B - A - A - A
  • A - A - B - B - A - A - A

Quel est le temps d’attente moyen avant l’exécution des processus ?

  • \((0+4)/2=2ms\)
  • \((15+4)/2=9,5ms\)
  • \((4+2)/2=3ms\)
  • \((4+4)/2=4ms\)

Combien de changement de contexte observe-t-on ?

  • \(1\)
  • \(2\)
  • \(4\)
  • \(5\)

Quel est le temps de séjour du processus A ?

  • \(15ms\)
  • \(0ms\)
  • \(19ms\)
  • \(3ms\)

Quel est le temps de séjour du processus B ?

  • \(4ms\)
  • \(2ms\)
  • \(3ms\)
  • \(8ms\)
Correction
rr3

3.5.6. A faire : Ordonnancements préemptifs

Soit les cinq processus A, B, C, D et E, dont les temps d’exécution et leurs temps d’arrivée respectifs sont les suivants: :

Processus Temps exécution (ms) Temps arrivée (ms)

A

3

0

B

6

2

C

4

4

D

5

6

E

2

8

  • Dessiner la frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type "SRF"

  • Calculer les temps d’attente de chaque processus et le temps moyen d’attente de tous les processus

  • Calculer les temps de séjour de chaque processus et le temps moyen de séjours de tous les processus

Correction
srf2
Figure 16. Frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type "SRF"
Processus Temps exécution (ms) Temps arrivée (ms) Séjour (ms) Attente (ms)

A

3

0

3

0

B

6

2

13

7

C

4

4

4

0

D

5

6

14

9

E

2

8

2

0

  • temps de séjour moyen : \((3+13+4+14+2)/5=7,2ms\)

  • temps moyen d’attente : \((0+7+0+9+0)/5=3,2ms\)

  • Dessiner la frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type "RR" avec un quatum de \(1ms\)

  • Calculer les temps d’attente de chaque processus et le temps moyen d’attente de tous les processus

  • Calculer les temps de séjour de chaque processus et le temps moyen de séjours de tous les processus

  • Combien de changement de contextes cet ordonnancement fait-il intervenir ?

Correction
rr4
Figure 17. Frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type "RR" (quatum = 1ms)
Processus Temps exécution (ms) Temps arrivée (ms) Séjour (ms) Attente (ms)

A

3

0

4

1

B

6

2

16

10

C

4

4

13

9

D

5

6

15

10

E

2

8

8

6

  • temps de séjour moyen : \((4+16+13+15+8)/5=11,2ms\)

  • temps moyen d’attente : \((1+10+9+10+6)/5=7,2ms\)

  • \(18\) changement de contextes

  • Dessiner la frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type "RR" avec un quatum de \(3ms\)

  • Calculer les temps d’attente de chaque processus et le temps moyen d’attente de tous les processus

  • Calculer les temps de séjour de chaque processus et le temps moyen de séjours de tous les processus

  • Combien de changement de contextes cet ordonnancement fait-il intervenir ?

Correction
rr5
Figure 18. Frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement de type "RR" (quatum = 3ms)
Processus Temps exécution (ms) Temps arrivée (ms) Séjour (ms) Attente (ms)

A

3

0

3

0

B

6

2

10

4

C

4

4

14

10

D

5

6

14

9

E

2

8

9

7

  • temps de séjour moyen : \((3+10+14+14+9)/5=10ms\)

  • temps moyen d’attente : \((0+4+10+9+7)/5=6ms\)

  • \(8\) changement de contextes

3.6. Algorithmes d’ordonnandement avec priorité

3.6.1. Principe

Certains processus sont plus importants ou urgents que d’autres. Les ordonnanceurs à priorité attribuent à chaque processus une priorité. Le choix du processus à élire dépend des priorités des processus prêts.

Dans le cas général, les processus de même priorité sont regroupés dans une file du type FIFO. Il y a autant de files qu’il y a de niveaux de priorité.

L’ordonnanceur choisit le processus le plus prioritaire qui se trouve en tête de file.

En général, les processus de même priorité sont ordonnancés selon l’algorithme du tourniquet (Round Robin).

taches priorites
Figure 19. Gestion des priorités entre taches

Exemple simple avec une seule file d’ordonnacement par priorités :

Considérons les processus P1, P2, P3 dont les temps d’arrivées, les temps d’exécutions et les priorités sont les suivants :

Processus Temps exécution (ms) Temps arrivée (ms) Priorité

P1

4

0

0

P2

3

2

1

P3

3

3

2

On suppose qu’à chaque quatum, c’est le processus qui a la priorité la puls importante qui est exécuté, ce qui peut provoquer la suspension d’un autre processus, lequel reprendra lorsqu’il sera le plus prioritaire.

Si le quantum est de \(1ms\) :

  • P1 commence à \(t=0\), il est le seul processus dans la file d’attente

  • P2 arrive à \(t=2ms\) :

    • La priorité de P2 est plus importante que celle de P1

    • P2 est exécuté et P1 retourne dans le file d’attente

  • P3 arrive à \(t=3ms\) :

    • La priorité de P3 est plus importante que celle de P2

    • P3 est exécuté et P2 retourne dans le file d’attente

  • Lorsque P3 est fini, il y a P1 et P2 dans la file d’attente

    • P2 est plus prioritaire que P1, il s’exécute en premier

priorites1
Figure 20. Frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement par priorités

Temps d’attente :

  • P1 : commence à \(0\) puis est interrompu à \(2ms\) et reprend à \(8ms\) : \(8-2=6ms\)

  • P2 : démarre dès son arrivée et est interrompu pendant \(3ms\) avant de reprendre : \(3ms\)

  • P3 : démarre dès son arrivée et n’est jamais interrompu : \(0ms\)

Temps d’attente moyen des processus avant de pouvoir être exécuté : \( (6+3+0)/3 = 3ms \)

3.6.2. A faire : Ordonnancements par priorités

Soit les cinq processus A, B, C, D, dont les temps d’exécution,les temps d’arrivée et les priorités respectifs sont les suivants: :

Processus Temps exécution (ms) Temps arrivée (ms) Priorité

A

5

0

4

B

4

2

2

C

2

2

6

D

4

4

2

  • Dessiner la frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement par priorités avec préemption :

    • Le processus le plus prioritaire de la file s’exécute

    • Lorsqu’un nouveau processus entre dans la file, on réévalue les priorités

    • En cas d’égalité de priorités, c’est le processus le plus court qui s’exécute

    • En cas d’égalité de durée, c’est le processus le plus ancien dans la file qui s’exécute

  • Calculer les temps d’attente de chaque processus et le temps moyen d’attente de tous les processus

  • Calculer les temps de séjour de chaque processus et le temps moyen de séjours de tous les processus

Correction
priorites2
Figure 21. Frise temporelle ou diagramme de Gantt de l’exécution des processus avec un ordonnancement par priorités
Processus Temps exécution (ms) Temps arrivée (ms) Séjour (ms) Attente (ms)

A

5

0

7

2

B

4

2

9

5

C

2

2

2

0

D

4

4

11

7

  • temps de séjour moyen : \((7+9+2+11)/4=7,25ms\)

  • temps moyen d’attente : \((2+5+0+7)/4=3,5ms\)

4. Interblocage

4.1. Introduction

Linterblocage de processus est du à l’existence d’un groupe de processus bloqués en attente de ressources, chacune d’elles étant allouée à l’un des processus du groupe

4.2. Définition

Pour s’exécuter, un processus a besoin d’un certain nombre d’éléments matériels comme de la mémoire, un processeur, des périphériques (clavier et écran par exemple) et des éléments logiciels, fichiers, tables, etc.

Tous ces éléments matériels et logiciels sont appelés des ressources.

On distingue des ressources à accès :

  • partagé : fichier en lecture seule, une base de données en consultation, …​

  • exclusif : une imprimante, un scanner, un lecteur de bande magnétique, …​

Pour utiliser une ressource, un processus doit :

  • demander son allocation, explicitement ou implicitement

  • l’utiliser

  • la libérer

4.3. Accès concurents aux ressources

Mise en évidence :

Deux agences d’une banque veulent mettre à jour le même compte bancaire. Pour cela, l’agence de Nancy effectue :

1. courant = get_account(1867A)
2. nouveau = courant + 1000
3. update_account(1867A, nouveau)

et l’agence de Karlsruhe :

A. aktuelles = get_account(1867A)
B. neue = aktuelles -1000
C. update_account(1867A, neue)

En supposant que l’agence de Nancy commence en premier, quel sera le montant à l’issue des transactions ?

Solutions :

Ça n’a aucun rapport réel avec qui commence la transaction, puisqu’elles ne sont pas atomiques (la partie « En supposant …​ en premier » de la question est volontairement piégeuse).

Des variables locales + exécutions parallèles entremêlées peuvent conduire à des résultats différents, par exemple :

  • 1 → 2 → 3 → A → B → C

    • compte inchangé

  • 1 → A → 2 → B → 3 → C

    • compte – 1000

  • 1 → A → B → 2 → C → 3

    • compte + 1000

On a une condition de compétition (race condition) : * Comment garantir le même montant ? en forçant l’ordre d’exécution * Comment forcer l’ordre d’exécution ? en rendant les opérations atomiques (ce qui garanti son exécution complète indépendamment des autres processus et de la stratégie d’ordonnancement)

Cette opération est une section critique. Elle doit s’exécuter en exclusion mutuelle.

Pour garantir l’exclusion mutuelle, on introduit deux nouvelles fonctions :

  • bloque(num_compte) : réserve le compte passé en argument. Si ce dernier est déjà réservé, elle bloque le programme appelant

  • debloque(num_compte) : libère le compte passé en argument s’il est bloqué

La fonction tranfert() protégée d’un montant depuis un compte vers un autre compte pourrait s’écrire :

1 function transfert(from, to, montant):
2    bloque(from)
3    bloque(to)
4
5    cour = get_account(from)
6    cour = cour -montant
7    set_account(from, cour)
8
9    cour = get_account(to)
10   cour = cour + montant
11   set_account(to, cour)
12
13   debloque(to)
14   debloque(from)

Que se passe-t-il si on effectue ces deux transfert en même temps :

  • tâche A : transfert('1246A', '6314B', 100)

  • tâche B : transfert('6314B', '1246A', 10)`

Réponse :

  • La ligne 2 de la tâche A bloque le compte '1246A'

  • La ligne 2 de la tâche B bloque le compte '6314B'

  • La ligne 3 de la tâche A demande l’accès au compte '6314B' : il ne l’obtient pas et doit attendre que la tâche B le libère

  • La ligne 3 de la tâche B demande l’accès au compte '1246A' : il ne l’obtient pas et doit attendre que la tâche A le libère

Les deux tâches attendent que l’autre avance pour pouvoir poursuivre : on est en situation d’interblocage

4.4. Conditions nécessaires pour l’interblocage

Pour qu’une situation d’interblocage ait lieu, les quatre conditions suivantes doivent être remplies (Conditions de Coffman) :

  • L’exclusion mutuelle : A un instant précis, une ressource est allouée à un seul processus.

  • La détention et l’attente : Les processus qui détiennent des ressources peuvent en demander d’autres.

  • Pas de préemption : Les ressources allouées à un processus sont libérées uniquement par ce même processus.

  • L’attente circulaire : Il existe une chaîne d’au moins deux processus de telle manière que chaque processus dans la chaîne requiert une ressource allouée au processus suivant dans la chaîne.

4.5. Modélisation : graphe d’allocation des ressources

Le graphe d’allocation des ressources est un graphe biparti composé de deux types de nœuds et d’un ensemble d’arcs :

  • Les processus sont représentés par des cercles

  • Les ressources sont représentées par des rectangles, un ou plusieurs points représentent les instances de la ressource disponibles

  • Un arc orienté d’une ressource vers un processus signifie que la ressource est allouée au processus

  • Un arc orienté d’un processus vers une ressource signifie que le processus est bloqué en attente de la ressource

Ce graphe indique pour chaque processus les ressources qu’il détient ainsi que celles qu’il demande

transfert
Figure 22. Graphe d’allocation des ressources des tranferts A et B

La présence d’un cycle dans le graphe indique une situation d’interblocage

transfert2
Figure 23. cycle = interblocage

4.5.1. A faire : Exercice 1

Soit trois processus A, B, C qui utilisent trois ressources R, S, T :

A B C

Demande R

Demande S

Demande T

Demande S

Demande T

Demande R

Libère R

Libère S

Libère T

Libère S

Libère T

Libère R

L’ordonnacement des processus est de type "premier arrivé, premier servi". Cette situation conduit-elle à un interblocage ?

  • OUI
  • NON

On utilise maintenant un ordonnancement circulaire de type tournique (Round Robin) et les actions des processus sont atomiques :

A - B - C - A - B - C - A - B - C - A - B - C

Cette situation conduit-elle à un interblocage ? Dessiner le graphe d’allocation des ressources et verifier la présence d’un cycle.

  • OUI
  • NON
Correction
Mise en évidence d’une situation d’interblocage

4.5.2. A faire : Exercice 2

Considérons un système ayant sept processus, A à G, et six ressources R à W.

A un instant donné, l’attribution des ressources est la suivante :

  • A détient R et demande S

  • B demande T

  • C demande S

  • D détient U et demande S et T

  • E détient T et demande V

  • F détient W et demande S

  • G détient V et demande U

Questions :

  • Construire le graphe d’allocation des ressources ?

  • Y a-t-il un interblocage?

  • Si oui, quels sont les processus concernés ?

Remarque :

Un graphe peut être réduit pour déterminer s’il existe ou non un interblocage.

  • Si le graphe peut être réduit pour tous les processus, il n’y a pas d’interblocage

  • Si le graphe ne peut être réduit pour tous les processus, alors les processus irréductible constituent l’ensemble des processus interbloqués

  • Pour la réduction d’un graphe d’allocation des ressources, les flèches associées à chaque processus et à chaque ressource doivent être vérifiées :

    • Si une ressource possède seulement des flèches qui sortent (il n’y a pas de requêtes), on les efface

    • Si un processus possède seulement des flèches qui pointent vers lui, on les efface.

    • Si les demandes en ressources d’un processus peuvent être servies, on réduit le graphe en enlevant les arcs de/vers ce processus ;

Correction
Construction du graphe
Mise en évidence d’un interblocage

4.5.3. A faire : Exercice 3

Un système informatique dispose de 3 types de ressources (R1, R2 et R3) et de 3 processus (P1, P2 et P3) :

  • R1 possède une seule instance

  • R2 possède deux instances

  • R3 possède une seule instance

Table 1. Ressources effectivement affectées aux processus

R1

R2

R3

P1

0

1

0

P2

1

1

0

P3

0

0

1
Table 2. Les demandes de ressources en attente

R1

R2

R3

P1

1

0

0

P2

0

0

1

P3

0

0

0

  • Dessinez le graphe d’allocation des ressources de ce système.

  • Le système est-il en situation d’interblocage ?

Correction
graphe1
Figure 24. Graphe d’allocation des ressources

Il n’y a pas de cycle dans le graphe d’allocation. Il n’y a donc pas d’interblocage.

graphe2
Figure 25. Graphe d’allocation des ressources réduit

4.5.4. A faire : Exercice 4

Un système informatique dispose de 3 types de ressources (R1, R2 et R3) et de 3 processus (P1, P2 et P3) :

  • R1 possède une seule instance

  • R2 possède deux instances

  • R3 possède une seule instance

Table 3. Ressources effectivement affectées aux processus

R1

R2

R3

P1

0

1

0

P2

1

1

0

P3

0

0

1
Table 4. Les demandes de ressources en attente

R1

R2

R3

P1

1

0

0

P2

0

0

1

P3

0

1

0

  • Dessinez le graphe d’allocation des ressources de ce système.

  • Le système est-il en situation d’interblocage ?

Correction
graphe4
Figure 26. Graphe d’allocation des ressources

Il y a deux cycles dans le graphe d’allocation. Il y a donc interblocage.

4.5.5. A faire : Exercice 5

Soit les trois processus suivants qui utilisent les trois ressources R1, R2 et R3 :

Processus P1
Debut
  Demander(R1)
  Demander(R2)
  Exécution
  Libérer(R2)
  Libérer(R1)
Fin

Processus P2
Debut
  Demander(R2)
  Demander(R3)
  Exécution
  Libérer(R3)
  Libérer(R2)
Fin

Processus P3
  Debut
  Demander(R3)
  Demander(R2)
  Exécution
  Libérer(R2)
  Libérer(R3)
Fin

L’ordonnancement des processus est de type circulaire ou tourniquet (Round Robin) et commence avec P1.

  • Tracer le graphe d’allocation des ressources

  • Montrer que cette exécution conduit à une situation d’interblocage

  • Quels processus sont à l’origine de cet interblocage ?

Correction
graphe3
Figure 27. Graphe d’allocation des ressources

Il y a un cycle dans le graphe d’allocation. Il y a donc interblocage. Les procesus P2 et P3 sont à l’origine du blocage mais P1 est également bloqué car il attend la libération de R2 par P2

5. webographie

the_end.jpg