processus : performances

Terminologie des mesures

Nous avons besoin de 3 paramètres pour mesurer les performances au niveau de l'exécution de processus : total service time, turnaround time, total wait time.

Total service time (Ts) : C'est le temps nécessaire au processus pour exécuter la tàche qu'il doit accomplir, donc le temps nécessaire avant de quitter le short term scheduler.

Turnaround time (Tq) : C'est le temps que le processus a réellement passé dans le scheduler. Les moments où le processus est en attente d'I/O ne sont t pas comptabilisés, car pendant ce temps il n'est pas dans le short term scheduler.

Total wait time (Tw) : C'est le temps perdu par le processus en attente de pouvoir utiliser les ressources du processeur. Nous pouvons aussi rencontrer l'abréviation suivante : Tm pour missed time (temps perdu).

Tw = Tq - Ts

Penalty ratio (P) : C'est le pourcentage de pénalité que supporte le processus. Le but est de trouver une rentabilité maximum du processeur et de la mémoire pour le traitement des processus.

P = Tq / Ts

Exemple

Pour illustrer les différentes méthodes employées, nous allons nous baser sur un exemple de 5 processus qui se présentent au CPU toutes les 2 unités de temps, et dont les Ts varient.

Politiques de gestion

Nous pouvons définir les politiques de gestion selon les critères suivants :

• préemptives : utilisation d'une notion de temps attribué au travail du processus dans le cpu (quantum).
  • intrinsèques : la gestion dépend des caractéristiques propres au processeur.
  • extrinsèques : la gestion dépend de paramètres extérieurs au processus (l'utilisateur, etc.).
• coopératives
  • intrinsèques
  • extrinsèques

FCFS : First Come, First Served

En FCFS, le processus qui se présente dans le short term scheduler entre dans la file. La propriété d'une file étant FIFO (First In, First Out), le premier processus qui entre dans la file est le premier à bénéficier du processeur.

Nous constatons que ce système est très simple, mais très peu rentable. Les processus longs sont faforisés par rapport aux processus courts qui sont pénalisés (système non équitable, très grosses variations dans les pénalités).

Le type de gestion est non-préemptif, car normalement rien n'est prévu par le système d'exploitation pour déloger le processus du cpu, ou favoriser un processus dans la file.

RR : Round Robin

En Round Robin, le système d'exploitation est préemptif, basé sur un signal horloge. A chaque intervale de temps (quantum), le processus doit libérer le processeur. Si son travail n'est pas terminé, il retourne dans la file des processus en attente de temps CPU. Round Robin est souvent baptisé la méthode du tourniquet.

Le but de cette opération est de limiter les différences entre les pénalités des processus.

Compromis : dans une gestion de type Round Robin, nous sommes soumis à un compromis entre d'un côté le temps que le scheduler utilise pour la gestion des autres processus (à chaque arrêt d'un processus, il faut sauver les vecteurs d'états, etc.) et de l'autre le temps accordé aux processus gérés (quantum). Nous pouvons estimer qu'une bonne gestion est aux alentours de 30% de temps pour le scheduler.

Les deux tableaux (quantum de 1, et quantum de 4) ne prennent en compte que le temps d'occupation du processeur par les processus, mais pas le temps où le cpu est monopolisé par le scheduler.

Nous pouvons constater que dans les deux cas les pénalités sont réparties de manière plus uniforme, mais que les processus courts (par exemple, le E) restent pénalisés.

VRR : Virtual Round Robin

Nous avons vu que quand le quantum d'un processus expire, le cpu est libéré et le processus retourne dans la file des processus en attente (ready queue).
De même, quand un processus est en attente d'I/O, il libère le cpu et est placé dans la file des bloqués (il peut exister plusieurs files de bloqués, une par évènement). Quand la ressource est libre, le processus peut sortir de la file des bloqués, et rejoindre la file des processus en attente de passage dans le processeur.

La gestion Virtual Round Robin permet aux processus qui quittent la file des bloqués de ne pas passer par le file ready, mais d'entrer directement dans une autre file (auxiliary queue), prioritaire sur cette dernière.

Le scheduler vérifie d'abord dans la file auxiliaire, et donne l'accès cpu aux processus qu'elle contient. C'est seulement quand la file auxiliaire est vide que le scheduler permet aux processus de la file ready (qui proviennent de l'état new) d'utiliser le processeur.

SPN : Shortest Process Next

Round Robin permet de réduire la pénalité des processus courts, mais nécessite une préemption. SPN tend au même effet, mais sans préemption.

Le prochain processus sélectionné sera celui qui nécessite le moins de temps cpu pour son exécution (Ts). L'ordre FIFO de la file n'est donc plus respecté.

Problèmes de SPN :

• il faut à chaque fois déterminer la longueur du processus pour savoir où le positionner dans la file.
• il est possible qu'un long processus ne puisse jamais bénéficier du processeur si beaucoup de processus courts se présentent dans la file (starvation for longer processes).

Nous pouvons remarquer que le taux moyen des pénalités est assez bas, et que la répartition des pénalités est équitable. Le problème est qu'il n'est pas possible d'établir des prévisions stables (cela dépend fortement des différentes tailles de processus qui se présentent en entrée).

Méthode d'évaluation de la longueur du processus

Tout processus qui vient de l'état new vers la file ready est déclaré de longueur moyenne. Suivant le temps passé dans le processeur, une valeur lui est attribuée. Cette valeur est modifiée à chaque passage dans l'état running.

Le cœfficient α (ou smoothing factor) permet à chaque passage dans l'état running de déterminer si le processus est court ou non par rapport à la moyenne des derniers processus qui viennent d'être exécutés.

Cette information de longueur se trouve dans le PCB (Process Control Block), plus précisément dans la partie "état du processus".

PSPN : Preemptive Shortest Process Next

La technique est identique à la technique SPN, mais ici le choix du processus le plus court se fait non seulement entre les processus de la file ready, mais aussi entre ces processus et le processus actuellement dans le CPU.

Quand un processus se présente dans la file ready avec un Ts inférieur au Ts restant (à ce moment) du processus dans le processeur, le scheduler libère le cpu pour le nouveau processus le plus court.

C'est pourquoi PSPN se nomme aussi SRT, pour Shortest Remaining Time (Plus court temps restant).

Les processus longs sont encore pénalisés, mais la pénalité moyenne a encore diminué par rapport à la méthode précédente (SPN).

Problème du PSPN :

• Si un long processus arrive à une taille minime et qu'un processus de taille encore plus courte entre dans la file, le long processus doit libérer le processeur. Cette opération nécessite la sauvegarde des différents registres du cpu et des informations diverses du processus (vecteurs d'états), ce qui risque d'être plus coûteux en temps que si l'OS avait laissé le processus terminer son exéction dans le processeur.

C'est pourquoi un Ts minimum est fixé dans le système d'exploitation. Si le Ts du processus qui est dans le processeur est inférieur ou égal à cette valeur minimum, le scheduler laisse le processus terminer sa tàche.

HPRN : Highest Penalty Ratio Next

HPRN signifie que le processus qui a la plus grosse pénalité est le suivant à pouvoir bénéficier des ressources du processeur. C'est une tentative d'équilibrer les pénalités sans utiliser de préemption.

Ce type de gestion est gourmande en ressources, car elle nécessite de nombreux calculs des pénalités.

FB : Multiple-level feedback

Ce style de gestion réintroduit la notion de préemption (car on utilise le quantum) sous la technique de priorité dynamique.

Différents types de gestions vu précédemment (SPN, PSPN, HPRN) utilisent la longueur relative des processus, mais l'obtention de cette information nécessite une gestion appropriée et du temps pour l'évaluation. Dans certains cas, il n'est même pas possible de déterminer cette longueur.

Nous ne pouvons pas toujours aisément déterminer le temps restant, mais il est plus facile de déterminer le temps déjà utilisé.
Un autre moyen de favoriser les processus courts est de pénaliser les processus qui ont déjà profité du temps cpu.

Le principe est le suivant :

• Utilisation de plusieurs files à l'entrée du processeur, organisées en différents niveaux.
• A chaque expiration du quantum d'un processus, il entre dans une file de niveau inférieur.
• Le scheduler permet l'accès au cpu pour les processus de la file ready. Quand il n'existe plus de processus dans cette file, il utilise la file d'un niveau inférieur. Si un nouveau processus entre dans la file ready, il aura donc priorité sur les processus situés dans une file de niveau inférieur (qui ont donc déjà bénéficié d'un certain nombre de temps d'accès au processeur).

Un problème subsiste : si de nouveaux processus se présentent sans cesse en entrée, les processus situés dans les files de niveau inférieur n'ont que peu de chance d'accéder au processeur.

Deux techniques sont possibles pour remédier à ce problème :

• Chaque niveau double la valeur du quantum des processus de ce niveau. De cette manière, au moment où les processus contenus dans cette file auront accès au cpu, ils disposeront de plus de temps pour effectuer leur tàche.
• Si le temps passé dans un niveau est trop important, le processus remonte dans la file du niveau supérieur.

SRR : Selfish Round Robin

Système préemptif comme le Round Robin, le SRR favorise les processus qui ont déjà bénéficié d'un temps processeur et qui ont du libérer le cpu (soit parce que leur quantum est expiré, soit parce qu'ils étaient en attente d'un I/O qui est maintenant accessible).

La file ready est divisée en 2 files :

• new : pour les nouveaux processus en entrée, et ceux qui attendent leur premier accès au cpu.
• accepted : pour les processus acceptés par le système de gestion.

Les principes de fonctionnement sont les suivants :

• Un processus de la file new ne peut pas accéder au processeur, seuls le peuvent les processus de la file accepted.
• Un nouveau processus se voit attribuer une priorité 0, et entre dans la file new.
• Les priorités augmentent à chaque cycle d'une valeur définie pour la file. La valeur d'incrémentation de la file new (a) doit être supérieure à celle de la file accepted (b).
• Les valeurs a et b sont des variables paramétrables. Elles peuvent être ajustées pour adapter la méthode.
• Quand le niveau de priorité d'un nouveau processus (un processus de la file new) atteint la priorité d'un processus de la file des processus acceptés, le nouveau processus est accepté et placé en tête de la file des acceptés. Il sera donc le prochain à accéder au processeur.
  Quand la file des processus acceptés est vide, le processus de la file new qui a la priorité la plus élevée est accepté.

Fair share scheduling

Nous nous sommes penchés sur un unique set de processus, et de la sélection du prochain processus à exécuter. Nous n'avons pas pris en compte le fait que les processus de plusieurs utilisateurs cohabitent.

Un système FSS (Fair share scheduling) divise les ressources en parts équitables, soit entre les utilisateurs, soit entre les groupes.

Structure du document