processus

Un processus est un programme en cours d’exécution.

Un processus possède :

• Un programme
• Des données
• Un état courant

Un processeur :

• Peut être partagé entre plusieurs processus

Système d’exploitation

Un système d'exploitation est un logiciel qui sert d'interface entre les programmes exécutés par l'utilisateur et les ressources matérielles d'un ordinateur.

Le système d’exploitation :

• Se sert d’un algorithme d’ordonnancement pour déterminer l’ordre d’exécution des processus sur le(s) processeur(s)

Le système d'exploitation alloue à chaque processus une durée d’exécution sur le processeur.

1) Etats d’un processus

• En architecture monoprocesseur, à un instant donné, un seul processus peut être en exécution, on dit que le processus est dans l’état élu.
• Un processus P1 qui se trouve à l’état élu peut demander à accéder à une ressource qui n’est pas encore disponible, par exemple pour lire un fichier sur le disque dur. En attendant, le processus P1 passe à l’état bloqué.
• Un autre processus P2 prend sa place et passe à l'état élu. Lorsque le processus P1 a obtenu accès à sa ressource (ici un fichier sur le disque dur) il passe à l’état prêt.

C’est donc le système d’exploitation qui joue le rôle de chef d’orchestre et essaye d’optimiser l’accès au microprocesseur par les processus.

D’où viennent les processus ? Les processus parents créent des processus enfants.

2) Hiérarchie des processus sous Unix

Au lancement du système d’exploitation il existe un seul processus qui est l’ancêtre de tous les autres processus (c’est le processus 0 : l’ordonnanceur). Ce premier processus est créé au niveau du noyau au moment du lancement du système d’exploitation, ensuite le processus crée un nouveau processus ; le processus init (processus 1). La commande fork permet de créer un processus enfant à partir du processus parent.

Le processus init va lui-même créé l’ensemble des processus nécessaires au lancement du système d’exploitation, notamment inetd qui permet de gérer les connexions à des services réseaux, crond qui permet de planifier (à une date et heure précise) l’exécution d’un programme, getty qui gère l’exécution de terminaux, notamment pour que l’utilisateur puisse se connecter à son poste au démarrage.

Au final on obtient une hiérarchie des processus :

On se retrouve avec une grande quantité de processus et des processeurs dont il faut optimiser le temps d’exécution.

3) Ordonnancement

3.1) Types d’ordonnancements

Il y a deux types d’ordonnancements :

• préemptif

Sélectionne un processus et le laisse s’exécuter pendant un quantum de temps (durée d’exécution sur le processeur) et l'interrompt ensuite.

• non préemptif

Sélectionne un processus et le laisse s’exécuter jusqu’à ce qu’il se bloque ou se termine.

3.2) Algorithmes d’ordonnancements non préemptifs

Nous allons étudier différents algorithmes. Voyons d’abord deux algorithmes non préemptifs.

Pour décrire chacun de ces algorithmes nous allons utiliser les processus suivants :

Source du diagramme : https://www.zonensi.fr/NSI/Terminale/C06/Ordonnancement/

Temps de séjour

Le temps de séjour d'un processus est l'intervalle de temps entre la soumission du processus et son achèvement :
Temps de séjour = instant de terminaison - instant d’arrivée.

Temps d’attente

Temps d’attente = temps de séjour - temps d’exécution

3.2.1) 1er arrivé, 1er servi (First-Come First-Served : FCFS, aussi appelé FIFO)

Il existe une version préemptive de cet algorithme, nous étudierons uniquement la version non préemptive.

Dans cet algorithme, le premier processus arrivé est le premier à s’exécuter. Le processus suivant doit attendre que le processus précédent ait terminé son exécution.

Le premier processus arrivé monopolise le processeur aussi longtemps

Temps de séjour de P1 : 5 - 0 = 5
Temps de séjour de P2 : 8 - 1 = 7
Temps de séjour de P3 : 10 - 3 = 7
Temps de séjour de P4 : 14 - 5 = 9

Temps moyen de séjour : (5 + 7 + 7 + 4) / 4 = 28 / 4 = 7

Temps d’attente de P1 : 5 - 5 = 0
Temps d’attente de P2 : 7 - 3 = 4
Temps d’attente de P3 : 7 - 2 = 5
Temps d’attente de P4 : 9 - 4 = 5

Temps d’attente moyen : (0 + 4 + 5 + 5) / 4 = 14 / 4 = 3,5

3.2.2) Le job le plus court en premier (shortest job first)

Il existe également une version préemptive de cet algorithme, que nous étudierons ensuite.

Dans cet algorithme les processus ayant les temps d'exécution estimés les plus courts sont exécutés en premier.

Au début ici on exécute le processus P1 (c’est le seul qui est dans la file au début). Ensuite on a le choix entre P2, P3 et P4. On exécute celui ayant la durée d’exécution estimée la plus courte (ici P3).

Temps de séjour de P1 : 5 - 0 = 5
Temps de séjour de P3 : 7 - 3 = 4
Temps de séjour de P2 : 10 - 1 = 9
Temps de séjour de P4 : 14 - 5 = 9

Temps moyen de séjour : (5 + 4 + 9 + 9) / 4 = 27 / 4 = 6,75

Temps d’attente de P1 : 5 - 5 = 0
Temps d’attente de P3 : 4 - 2 = 2
Temps d’attente de P2 : 9 - 3 = 6
Temps d’attente de P4 : 9 - 4 = 5

Temps d’attente moyen : (0 + 2 + 6 + 5) / 4 = 13 / 4 = 3,25

Nous allons maintenant étudier deux algorithmes préemptifs.

3.3) Algorithmes d’ordonnancements préemptifs

3.3.1) Plus petit temps de séjour (Shortest Remaining Time)

C’est la version préemptive de l’algorithme du job le plus court en premier.

L’ordonnanceur compare la durée estimée pour un processus arrivant dans la file avec la valeur du processus actuellement en cours d’exécution. Si le temps du processus est plus court, il entre en exécution.

Au début seul le processus P1 est dans la file, P1 est exécuté. Au bout de 1 tick le processus P2 est estimé plus court, le processus P1 est interrompu et c’est alors le processus P2 qui est exécuté, et ainsi de suite.

A la fin P1 et P4 ont la même durée d’exécution restante estimée, mais P1 a déjà été exécuté, on choisit P1 avant P4.

Temps de séjour de P1 : 10 - 0 = 10
Temps de séjour de P2 : 4 - 1 = 3
Temps de séjour de P3 : 6 - 3 = 3
Temps de séjour de P4 : 14 - 5 = 9

Temps moyen de séjour : (10 + 3 + 3 + 9) / 4 = 25 / 4 = 6,25

Temps d’attente de P1 : 10 - 5 = 5
Temps d’attente de P2 : 3 - 3 = 0
Temps d’attente de P3 : 3 - 2 = 1
Temps d’attente de P4 : 9 - 4 = 5

Temps d’attente moyen : (5+ 0 + 1 + 5) / 4 = 11 / 4 = 2,75

3.3.2) Le tourniquet (Round-robin)

Cet algorithme est très utilisé en pratique.

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.

Exemple avec un quantum de temps de 3 cycles :

Le Processus P1 est le seul disponible, il commence son exécution. Au bout de 3 cycles il est interrompu et mis en queue de file. On passe au processus P2, son exécution se termine au bout de 3 cycles. Le processus P3 est le suivant dans la file et se termine au bout de 2 cycles, on passe au processus P4 pour lequel il reste 1 cycle à la fin. On revient au processus P1 qui se termine au bout de deux cycles, et enfin on termine le processus P4 au bout d’un cycle.

Temps de séjour de P1 : 13 - 0 = 13
Temps de séjour de P2 : 6 - 1 = 5
Temps de séjour de P3 : 8 - 3 = 5
Temps de séjour de P4 : 14 - 5 = 9

Temps moyen de séjour : (13 + 5 + 5 + 9) / 4 = 32 / 4 = 8

Temps d’attente de P1 : 13 - 5 = 8
Temps d’attente de P2 : 5 - 3 = 2
Temps d’attente de P3 : 5 - 2 = 3
Temps d’attente de P4 : 9 - 4 = 5

Temps d’attente moyen : (8+ 2 + 3 + 5) / 4 = 18 / 4 = 4,5

On remarquera que dans cet algorithme il est crucial de choisir un quantum de temps optimal.

4) Interblocage (deadlock)

Deux processus P1 et P2 peuvent avoir besoin de deux mêmes ressources, par exemple de deux fichiers sur le disque dur.

• On sépare les processus et les ressources : ce sont les nœuds du graphe.
• Lorsqu’un processus attend une ressource, un arc est tracé partant de ce processus vers la ressource,
• Lorsqu’un processus acquiert une ressource, un arc est tracé partant de la ressource vers le processus. On efface l’arc dans l’autre sens s’il existe.

Les deux processus s’attendent mutuellement.

L’interblocage se produit lorsqu’il existe un cycle dans le graphe.

Ici le processus P2 est en train d’utiliser la ressource R1 mais à besoin de la ressource R2 pour continuer son exécution. Le processus P1 est en train d’utiliser la ressource R2 mais à besoin de la ressource R1 pour continuer son exécution.