Ordonnancement Introduction Un ordonnanceur ( scheduler) comporte deux parties : ordonnanceur de haut niveau (Long Term Scheduling): politique de décision, affectation de priorité ordonnanceur de bas niveau ou distributeur ( Short Term Scheduling ou dispatcher) : affectation d’un processeur à un processus Pour l’ordonnanceur détailler : Mode de décision or 1 1 Sni* to View cepts sont ? Il s’agit de spécifier des instants où les priorités des processus sont évaluées et comparées et ou des processus sont sélectionnés pour exécution.
Entre deux instants consécutifs, ‘allocation de processeurs aux processus ne change pas. – mode non pré-emptif : un processus en exécution continue jusqu’à ce qu’il se termine ou se bloque (non adéquat pour les systèmes temps réel et temps partagé) mode pré-emptif : un processus en exécution peut être interrompu par diverses causes : un nouveau processus arrive, un processus existant est réveillé, un temps q s’est écoulé, la priorité d’un processus prêt est devenue plus grande que celle du 1 si p peut être pré-empté par un autre processus et O dans le cas contraire ( vp représente une priorité d’exécution).
Fonction de priorité A tout moment une priorité est affectée à un processus du fait du résultat de l’application d’une
Solution de l’exercice 3 On reprendra les politiques de l’exemple précédent et les résultats chronologiques et synthétiques sont consignés dans le tableau ci-dessous . Pl P2 P3 P4 total moyenne FIFO 3 Les deux politiques les plus intéressantes sont ici SJF et SRT. 7 6 31 LIFO 20 7 2 105 PAGF30F11 4,5 3,67 6,16 PAGFd0F11 On considère les politiques d’ordonnancement suivantes : FIFO, LIFO, SIF, SRT, HRN, RR . pour les politiques pré-emptives, le quantum est égal à 1 unité de temps. Comparer ces diverses politiques.
Exercice 3 On considère l’ensemble suivant de processus rocessus date d’arrivée temps de sen,’ice 4 s 1 d’autant plus grande que le temps total de service est court : – un processus « court » devrait être terminé rapidement – traiter d’abord les travaux courts réduit le temps total d’exécution de tous les processus Les priorités externes sont utilisées pour différencier les classes d’utilisateurs et de exemple : processus temps réel : hautes priorités processus interactifs : moyennes priorités processus batch . asses priorités L’adaptation temporelle prend en compte le fait que l’urgence ? terminer une tâche peut varier dans le temps. xemple : accroître la priorité au fur et à mesure que le temps du processus dans le système augmente ( probleme des prédictions météo : elles ne peuvent arriver après la date correspondante). Règle d’arbitrage Cette règle est faite pour les conflits entre processus de même priorité.
Plusieurs possibilités choix au hasard, choix suivant la position dans la Principaux algorithmes Examinons maintenant quelques algorithmes d’ordonnancement FIFO ( First Int First out) L’ordre est celui de l’arrivée des processus dans la file des processus prêts. La fonction de priorité est P(r) r où r est le temps réel passé dans le système. Le mode de décision est non pré-empt PAGF 6 1 moment. LIFO ( Last ln/ First Out) L’ordre est Pinverse du précédent : le dernier arrivé est le premier serai.
La fonction de priorité est P(r) – r où r représente toujours le temps réel passé dans le système. l_e mode de décision et la règle d’arbitrage sont comme dans FIFO. SIF ( ShortestJob First) On suppose que le temps total de service t est connu à l’avance ( bien adapté aux processus batch où l’utilisateur peut indiquer un temps max). La fonction de priorité – -t. Le mode de décision est non est P(t) – pré-emptif. La règle d’arbitrage est la chronologie ou le choix au hasard. La difficulté est évidemment l’estimation du temps de service.
Ceci peut s’opérer, par exemple, de la manière suivante, pour un processus interactif qui s’exécute comme une série de « bursts » de durée d’exécution réelle Ti. Au n+l ème burst, on peut estimer le temps de service par la moyenne : Cette relation peut être ré-écrite sous la forme En fait, dans la pratique, on généralise cette relation en employant des facteurs de pondération a (compris entre O et 1) et 1-a: n+l = a Tn + (1-osn Cette méthode s’appelle la pondération exponentielle.
SRT ( Shortest Remaining Time) Version pré-emptive du SIF. Si a est le temps CPLJ consommé et t le temps total estimé de service, la fonction de priorité est P(a,t) = a-t_ La l’arrivée du nouveau proc 11 ré-emption a lieu ? Ile des pré-emption a lieu à l’arrivée du nouveau processus dans la file des prêts. HRN (Highest Ratio Next) Cet algorithme permet de prendre en compte l’attente d’un processus en basant la priorité sur le rapport : (w+t)/t où w est le temps passé à attendre et t le temps total estimé de service. processus qui n’attend pas possède un rapport de 1 (cas notamment d’un processus qui vient d’entrer dans le système) , un processus qui attend longtemps possède un rapport R bien plus grand que RR ( Round Robin) Un quantum de temps Q est imposé. Lorsqu’un processus actif a consommé son quantum Q, il doit quitter le processeur et est placé en queue d’une file. La règle d’arbitrage est donc cyclique. Tous les processus ont par contre la même prlorité.
Notons que le quantum Q peut être constant dans le temps ou varier avec la charge du système : soit T le temps nécessaire à un cycle de tous es processus ; on peut poser : Q = T/n où n est le nombre de processus actifs pendant T unités de temps. Très utilisé dans les systèmes en temps partagé. MLF ( Multil_evel Feed-back) Il est défini n niveaux de priorité. pour chaque niveau i est défini un temps Ti qui est le temps maximum d’utilisation du processeur au niveau i.
S’il y a dépassement, la priorité du processus est décrémentée de 1 et celui-ci passe donc au niveau de riorité immédiatement inférieur. Le temps Ti de c peut être PAGF 11 niveau de priorité immédiatement inférieur. Le temps Ti de haque niveau peut être défini par : Ti = 2n-iTn Tn est le temps maximum d’utilisation du processeur au niveau n ; Tk = 2n-k. Tn est le temps maximum d’utilisation du processeur au niveau k. La règle d’arbitrage peut être chronologique ( type FIFO) ou cyclique ( type RR).
Le temps total consommé CPIJ pour un processus au niveau k (O k n) est a tel que : En utilisant la relation on obtient Cette relation permet de déterminer la priorité du processus, sachant qu’il a atteint un temps de service a P(a) = k et, en posant i = n-k, P(a) = n- i où i est déterminé par : On constate que i a < Tn alors i Oet P(a) n, plus haute priorité si a > Tn. ( 2n – 1), alors 1 ce qui est interprété comme une erreur. PDS ( policy-Driven Scheduling) Cette méthode est adaptative en ce sens que l’affectation des priorités dépend de la charge du système.
Elle est basée sur l’utilisation d’une fonction f(r), appelée fonction politique, qui prescrit la corrélation entre le temps réel passé us dans le système et le montant de service s(r) reçu par un processus est de la forme : tj(r) est la durée d’utilisation de la ressource j à l’instant r ; wjest le poids associé à la ressource j et n est e nombre de ressources distinctes gérées par le scheduler.. Pour simplifier ici la méthode PDS, on ne prendra en considération qu’une seule ressource, le processeur; donc s(r) = a.
Dans un diagramme ( a, r un point de coordonnées ( ai , ri ) exprime la relation entre le temps passé dans le système et le temps « utile » d’utilisation du processeur. Un point ( ai = f(ri), fi = f-l(ai )) exprime ce qui est souhaité. Pour un temps de service ai on peut donc mesurer la différence ri – f-l(ai ) entre ce qui est réel et ce qui est souhaité. On pourra alors prendre comme priorité P(ai , ri ) cette différence P(ai , ri La prlorité s’accroit lorsque le temps passe et que le processus ne reçoit pas les services souhaités.
En fait, lorsque p est positive, cela signifie que le service accordé n’est pas à la hauteur des espérances, tandis que si P est négatif, cela signifie que l’on prend « de l’avance » et, dans ce cas, on pourrait stopper le processus pour laisser la place à des processus moins favorisés. Parmi les exemples précédents, représentatifs des algorithmes d’ordonnancement des divers systèmes d’exploitation, il paraît inévitable de rechercher lequel est le meilleur. La réponse à cette question
