Gestion du processeur central

IV. Gestion du processeur central

Dans un système multitâche, la ressource la plus importante d’une machine est le processeur. Cette ressource est allouée à un et un processus sélectionné parmi un ensemble des processus éligibles. Par conséquent, il convient à bien gérer ce dernier afin de le rendre plus productif. En effet, un système d’exploitation dispose d’un module qui s’occupe de l’allocation du processeur en l’occurrence le Dispatcheur. Ce module est exécuté chaque fois qu’un processus se termine ou se bloque dans le but de réquisitionner le processeur pour un autre processus. En plus de ce Dispatcheur, un système d’exploitation dispose d’un autre module permettant ainsi la mise en ordre des processus qui demandent le processeur.

IV.1. Définition

L'ordonnanceur (scheduler) est un programme du système d’exploitation qui s’occupe de choisir, selon une politique de scheduling donnée, un processus parmi les processus prêts pour lui affecter le processeur.

IV.2. Objectifs de scheduling.

L'ordonnancement est la partie du système d'exploitation qui détermine dans quel ordre les processus prêts à s'exécuter (présents dans la file des prêts) seront élus. Ses objectifs sont :

1.      faible temps de réponse des processus,

2.      bon fonctionnement des processus en tâches de fond,

3.      éviter absolument la famine.

IV.3. Critères de scheduling.

1.      Utilisation de la CPU – utiliser la CPU le maximum possible

2.      Débit (Throughput) – # de processus qui terminent leur exécution par unité de temps

3.      Temps de rotation (Turnaround time) – le temps depuis le lancement du processus jusqu’à sa terminaison (les attentes incluses)

4.      Temps d’attente – temps d’un processus dans la file d’attente des processus prêts

5.      Temps de réponse – temps mis entre une requête émise et la première réponse, pas la sortie (pour les environnements à temps partagé)

IV.4. Niveaux de scheduling

Il existe trois niveaux de Scheduling :

1. Le scheduling de haut niveau (Long-Term scheduling) qui décide du degré de la multiprogrammation (nombre maximal de processus dans le système).

2.      Le  scheduling de niveau intermédiaire (Medium-Term scheduling) gère le déplacement des processus d’une file d’attente à une autre. Dans la majorité des systèmes actuels, les niveaux intermédiaires et haut sont combinés -> haut niveau.

3.   Le scheduling de bas niveau (Short-Term scheduling) (dispatcher ou répartiteur) est sollicité plusieurs fois par seconde et doit constamment résider en mémoire. Il permet de déterminer le processus prêt à utiliser le processeur central.

IV.5. Politiques de scheduling.

Les algorithmes d’ordonnancement se distinguent les uns des autres du fait que certains
autorisent la réquisition de l’unité centrale alors que d’autres l’interdisent. La réquisition est
la possibilité de retirer à n’importe quel instant le processeur à un processus même si ce
dernier est en cours d’exécution.

Nous distinguons plusieurs algorithmes d’ordonnancement, les plus répandus sont :

IV.5.1. First in first out FIFO (first come first served FCFS)

Dans cet algorithme ; connu sous le nom FIFO (First In, First Out) ; les processus sont rangés dans la file d’attente des processus prêts selon leur ordre d’arriver. Les règles régissant cet ordonnancement sont :

1.      Quand un processus est prêt à s’exécuter, il est mis en queue de la file d’attente des processus prêts.

2.      Quand le processeur devient libre, il est alloué au processus se trouvant en tête de file d’attente des processus prêts.

3.      Le processus élu relâche le processeur s’il se termine ou s’il demande une entrée sortie.

Cet algorithme est sans réquisition et non adapté à un système temps partagé car dans un système pareil, chaque utilisateur obtient le processeur à des intervalles réguliers.

IV.5.2. Short job first SJF

SJF choisit de façon prioritaire les processus ayant le plus court temps d’exécution sans réellement tenir compte de leur date d’arrivée. Dans cet algorithme les différents processus sont rangés dans la file d'attente des processus prêts selon un ordre croissant de leur temps d'exécution (cycle de calcul). Les règles régissant cet ordonnancement sont :

1.      Quand un processus est prêt à s’exécuter, il est inséré dans la file d’attente des processus prêts à sa position approprie.

2.      Quand le processeur devient libre, il est assigné au processus se trouvant en tête de la file d’attente des processus prêts (ce processus possède le plus petit cycle processeur). Si deux processus ont la même longueur de cycle, on applique dans ce cas l’algorithme FCFS.

3.      Si le système ne met pas en œuvre la réquisition, le processus élu relâche le processeur s’il se termine ou s’il demande une entrée sortie. Dans le cas contraire, le processus élu perd le processeur également. Quand un processus ayant un cycle d’exécution inférieur au temps processeur restant du processus élu, vient d’entrer dans la file d’attente des prêts. Le processus élu dans ce cas sera mis dans la file d’attente des éligibles, et le processeur est alloué au processus qui vient d’entrer.

Cet algorithme peut être avec ou sans réquisition et son implémentation est difficile, car il n’existe aucune manière pour connaître le cycle suivant du processeur.

IV.5.3. Avec priorité

Dans cet algorithme, les processus sont rangés dans la file d’attente des processus prêt par ordre décroissant de priorité. L’ordonnancement dans ce cas est régit par les règles suivantes :

1.      Quand un processus est admis par le système, il est inséré dans la file d’attente des
processus prêts à sa position approprie (dépend de la valeur de priorité).

2.      Quand le processeur devient libre, il est alloué au processus qui se trouve en tête de file d’attente des processus prêts (le plus prioritaire).

3.      Un processus élu relâche le processeur s’il se termine ou se bloque (E/S ou autre).

Si le système met en œuvre la réquisition, quand un processus de priorité supérieure à celle du processus élu entre dans l’état prêt ; le processus élu sera mis dans la file d’attente des éligibles à la position approprie, et le processeur est alloué au processus qui vient d’entrer.

Cet algorithme peut être avec ou sans réquisition. Un processus de priorité basse risque de ne pas être servi (problème de famine) d’où la nécessité d’ajuster périodiquement les priorités des processus prêts. L’ajustement consiste à incrémenter graduellement la priorité des processus de la file d’attente des éligibles (par exemple à chaque 15 mn on incrémente d’une unité la priorité des processus prêts).

IV.5.4. Tourniquet

Dans cet algorithme les processus sont rangés dans une file d'attente des éligibles, le processeur est alloué successivement aux différents processus pour une tranche de temps fixe Q appelé Quantum. Cet Ordonnancement est régit par les règles suivantes :

1.      Un processus qui rentre dans l’état éligible est mis en queue de la file d'attente des prêts.

2.      Si un processus élu se termine ou se bloque avant de consommer son quantum de temps, le processeur est immédiatement alloué au prochain processus se trouvant en tête de la file d'attente des prêts.

3.      Si le processus élu continue de s'exécuter au bout de son quantum, dans ce cas le processus sera interrompu et mis en queue de la file d'attente des prêts et le processeur est réquisitionné pour être réalloué au prochain processus en tête de cette même file d’attente.

Cet algorithme est avec réquisition, il est adapté aux systèmes temps partagé. La stratégie du tourniquet garantit que tout processus est servi au bout d’un temps fini. Son avantage est d’éviter la famine. On dit qu'un processus est en famine lorsqu'il est prêt à être exécuté et se voit refuser l'accès à une ressource (ici le processeur) pendant un temps indéterminé. L’efficacité de cet ordonnanceur dépend principalement de la valeur du quantum Q:

−        Le choix d'un Q assez petit augmente le nombre de commutation.

−        Le choix d'un Q assez grand augmente le temps de réponse du système

IV.6. Contrôle de processus

Un processus est une entité dynamique qui matérialise un programme en cours d'exécution avec ses propres ressources physiques (mémoire, processeur, entrée/sortie, …) et logiques (données, variables,…). Contrairement à un programme (texte exécutable) qui a une existence statique.

Le système d’exploitation manipule deux types de processus :

−        Processus système : processus lancé par le système (Init processus père des tous les processus du système)

−        Processus utilisateur : processus lancée par l’utilisateur (commande utilisateur)

Dès sa création, un processus reçoit les paramètres suivants :

−        PID : identificateur du processus (numéro unique)

−        PPID : identificateur du processus père

−        UID : identificateur de l’utilisateur qui a lancé le processus

−        GID : identificateur du groupe de l’utilisateur qui a lancé le processus

IV.6.1. Etats d'un processus

Dans les systèmes mono programmés, un programme ne quitte pas l’unité centrale avant de terminer son exécution. Pendant cette période, il dispose de toutes les ressources de la machine. Par contre, ce n’est pas le cas dans les systèmes multiprogrammés et temps-partagé, un processus peut se trouver dans l’un des états suivants :

1.      Elu : (en cours d’exécution) : si le processus est en cours d'exécution

2.      Bloqué : attente qu’un événement se produit ou bien ressource pour pouvoir continuer

3.      Prêt : si le processus dispose de toutes les ressources nécessaires à son exécution à l'exception du processeur.

Figure 17. Diagramme de transition d’un processus

IV.6.2. Bloc de contrôle de processus PCB

Lorsqu’un processus est temporairement suspendu, il faut qu’il puisse retrouver l’état où il se trouvait au moment de suspension, il faut que toutes les informations dont il a besoin soient sauvegardées pendant sa mise en attente.

Notons que le contexte d’un processus dépend du système, mais dans tous les cas c’est un bloc de contrôle de processus (BCP) qui contient toute information nécessaire à la reprise d’un processus interrompu : Etat du processus (prêt, suspendu, ..), quantité de mémoire, temps CPU (utilisé, restant), priorité, etc.

Les BCP sont rangés dans une table (table des processus) qui se trouve dans l’espace mémoire du système (figure 18).

Figure 18. Bloc de contrôle de processus (PCB)

 

IV.6.3. Création de processus

Il existe des appels système permettant de créer un processus, charger son contexte et lancer son exécution (fork, exec sous Unix). Un processus (père) peut créer d’autres processus (fils) qui hérite les descripteurs de son père. Ce dernier à son tour crée d’autres processus. Un processus a un seul père mais peut avoir plusieurs fils.

Figure 19. Création de processus.

IV.6.4. Destruction d'un processus

Les processus peuvent se terminer ou ils peuvent être éliminés par d’autres processus (la primitive kill). A la destruction d’un processus, on libère toutes les ressources qu’il avait.

Dans certains cas, la destruction d’un processus entraîne l’élimination de ces descendants; cette  pération n’affecte pas les processus qui peuvent continuer indépendamment de leur père (processus orphelins).