Processus et ordonnancement

Gestion des processus¶

Un processus est une instance d'exécution d'un programme. Un processus peut être démarré par l'utilisateur, par un périphérique, ou par un autre processus appelé parent. La commande UNIX ps présente un cliché instantanné des processus en cours d'exécution sur l'ordinateur.

Un extrait de l'affichage réalisé par la commmande est présenté ci-dessous.

On rappelle que :

UID est l'identifiant de l'utilisateur propriétaire du processus ;
PID est l'identifiant du processus
PPID est l'identifiant du processus parent
C indique l'utilisation processeur
STIME est l'heure de démarrage du processus
TIME est la durée d'utilisation du processeur par le processus
CMD est le nom de la commande utilisée pour démarrer le processus.
Donner le PID du parent du processus démarré par la commande vi.
Donner le PID d'un processus enfant du processus démarré par la commande xfce4-terminal.
Citer le PID de deux processus qui ont le même parent.
Parmi tous les processus affichés, citer le PID des deux processus ayant consommé le plus de temps du processeur.

Processus et chronogramme¶

On considère cinq processus P1, P2, P3, P4 et P5 dont les durée d'exécution et les dates d'arrivée sont donnés dans le tableau ci-dessous.

Processus	Temps d'exécution	Instant d'arrivée
`P1`	3	0
`P2`	6	1
`P3`	4	4
`P4`	2	6
`P5`	1	7

À l'instant \(t = 0\), le processus P1 est dans l'état Élu et commence à être exécuté. On prévoit qu'il nécessite 3 quantum (unités de temps d'exécution). À l'instant \(t = 1\), le processus P2 est dans l'état prêt. Le processus P1 est encore en train de s'exécuter, P2 est donc placé dans la file d'attente des processus à exécuter. On peut schématiser cette situation à l'aide d'un chronogramme.

1. Compléter le chronogramme en utilisant l'algorithme premier arrivé premier servi : le processeur exécute le processus durant toute la durée d'exécution, puis une fois que celui-ci passe dans l'état fin, il exécute le prochain processus dans la file d'attente. Les processus sont rajoutés à la file d'attente à leurs instants d'arrivée.
2. Le temps de séjour est est obtenu pour chaque processus en soustrayant le temps d'entrée du processus à son temps de terminaison.
  
  Calculer le temps de séjour pour chacun des processus, ainsi que le temps moyen de séjour pour l'ensemble des processus.
3. Le temps d'attente est obtenu en soustrayant le temps d'exécution au temps de séjour.
  
  Calculer le temps d'attente pour chacun des processus, ainsi que le temps moyen de séjour pour l'ensemble des processus.
4. Le temps de latence est le délai entre la création du processus et le début de son exécution.
  
  Calculer le temps de latence pour chacun des processus, ainsi que le temps moyen de latence pour l'ensemble des processus.
Reprendre les questions précédentes en utilisant l'algorithme du travail le plus court d'abord : le processeur exécute le processus durant toute sa durée d'exécution, puis une fois que celui-ci passe dans l'état fin, il exécute le processus dont la durée d'exécution est la plus faible. Les processus sont rajoutés à la file d'attente à leurs instants d'arrivée.
On dit qu'un ordonnancement est préemptif si le système d'exploitation peut interrompre l'exécution d'un processus avant que celui-ci ne soit terminé pour poursuivre l'exécution d'un autre processus.

Reprendre l'algorithme d'ordonnancement du travail le plus court d'abord de telle sorte que le processus en cours d'exécution est interrompu lorsqu'un nouveau processus entrant dans la file des processus possède une durée d'exécution inférieure à la durée d'exécution restante du processus courant.

Par exemple, si P1 est en train d'être exécuté, et qu'il reste 2 unités de temps avant la fin de P1 lorsque P2 entre dans la file des processus, alors P1 est interrompu et P2 passe dans l'état élu, il est exécuté par le processeur.

Algorithme du tourniquet¶

L'algorithme du tourniquet est un algorithme d'ordonnancement préemptif. Le temps d'allocation du processeur au processus est appelé quantum.

L'ordonnanceur 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.

On considère les processsus P1 et P2 suivants :

Processus Durée d'exécution Instant d'arrivée

P1 15 0

P2 4 4

Avec un quantum de 10 unités de temps et l'ordonnancement généré par l'algorithme du tourniquet est :
1. Déterminer les temps de séjour et les temps d'attente des processus P1 et P2.
2. Combien y a-t-il de changement de contexte (interruptions d'un processus par l'ordonnanceur au profit d'un autre) ?
3. Reprendre les questions précédentes si le quantum est de 3 unités de temps.
1. Déterminer l'ordonnancement généré par l'algorithme du tourniquet pour les processus P1, P2, P3 avec un quantum de 3 unités de temps et :
  
  Processus Instant d'arrivée Durée d'exécution
  
  P1 0 10
  
  P2 3 4
  
  P3 2 8
2. Reprendre les questions précédentes dans le cas où tous les processus sont démarrés à l'instant \(t = 0\) dans l'ordre P1, P2, P3.

Type BAC¶

D'après BAC 2022 (Amérique du Sud)

On s'intéresse au cadre d'un ordonnanceur préemptif avec priorité. Le tableau ci-dessous donne les demandes d'exécution de quatre processus et indique :

le temps d'exécution du processus (en unité de temps) ;
l'instant d'arrivée du processus sur le processeur (en unité de temps) ;
le numéro de priorité du processus (classé de 1 à 10, plus la priorité est grande, plus le numéro de priorité est petit).

À chaque instant, l'ordonnanceur choisit d'exécuter le processus ayant la priorité la plus importante. Ceci peut alors provoquer la suspension d'un autre processus qui reprendra lorsqu'il deviendra le processus le plus prioritaire de la file d'attente.

Processus	Temps d'exécution	Instant d'arrivée	Numéro de priorité
`P1`	3	0	4
`P2`	4	2	2
`P3`	3	3	1
`P4`	4	5	3

Compléter le diagramme ci-dessous, et indiquer dans chacune des cases le processus exécuté par le processeur entre deux unités de temps (il peut y avoir des cases vides).
Déterminer les temps de séjour, temps d'attente de chacun des processuss.
Déterminer le temps de séjour moyen, le temps d'attente moyen de l'ensemble des processus.
À quelle(s) condition(s) le temps d'attente d'un processus peut-il être nul ?