Exercice Corrigé Ordonnancement Des Processus – Partie 5

Les quatre diagrammes de Gantt sont:

Temps de rotation = Temps fin d’exécution – Temps d’arrivée

+-----------+--------+--------+---------+--------------+
| Processus |  FCFS  |   RR   |   SJF   | Par priorité |
+-----------+--------+--------+---------+--------------+
| P1        | 10     | 19     | 19      | 16           |
+-----------+--------+--------+---------+--------------+
| P2        | 11     | 2      | 1       | 1            |
+-----------+--------+--------+---------+--------------+
| P3        | 13     | 7      | 4       | 18           |
+-----------+--------+--------+---------+--------------+
| P4        | 14     | 4      | 2       | 19           |
+-----------+--------+--------+---------+--------------+
| P5        | 19     | 14     | 9       |  6           |
+-----------+--------+--------+---------+--------------+

Temps d’attente = Temps de rotation – Temps de rafale

+-----------+--------+--------+---------+--------------+
| Processus |  FCFS  |   RR   |   SJF   | Par priorité |
+-----------+--------+--------+---------+--------------+
| P1        | 0      | 9      | 9       | 6            |
+-----------+--------+--------+---------+--------------+
| P2        | 10     | 1      | 0       | 0            |
+-----------+--------+--------+---------+--------------+
| P3        | 11     | 5      | 2       | 16           |
+-----------+--------+--------+---------+--------------+
| P4        | 13     | 3      | 1       | 18           |
+-----------+--------+--------+---------+--------------+
| P5        | 14     | 9      | 4       |  1           |
+-----------+--------+--------+---------+--------------+

On sait que:

Temps de rotation = Temps fin d’exécution – Temps d’arrivée

Temps moyen de rotation = (Temps de rotation total) / (Nombre total de processus)

Temps moyen de rotation = 10.53 unités

On sait que:

Temps de rotation = Temps fin d’exécution – Temps d’arrivée

Temps moyen de rotation = (Temps de rotation total) / (Nombre total de processus)

Temps moyen de rotation = 9.53 unités

Temps moyen de rotation = 6.86 unités

A. Quand β > α > 0

Dans ce cas, la priorité d’un processus en cours d’exécution augmente plus rapidement (β) que celle d’un processus en attente (α). Étant donné que les processus en cours d’exécution gagnent de la priorité plus rapidement, ils tendent à préempter les processus en attente qui n’ont pas été exécutés. Par conséquent, cette configuration favorise les processus qui utilisent activement le CPU, leur permettant de continuer à s’exécuter sans être interrompus tant qu’ils sont en cours d’exécution. Cela conduit à un comportement similaire à l’Ordonnancement Premier Arrivé, Premier Servi (First-Come, First-Served – FCFS), car une fois qu’un processus commence à s’exécuter, il est moins susceptible d’être préempté par d’autres en attente dans la file d’attente.

B. Quand α < β < 0

Dans ce scénario, les deux taux sont négatifs, ce qui signifie qu’au fil du temps, les priorités des processus en attente et en cours d’exécution diminuent. Cependant, comme β (le taux pour les processus en cours d’exécution) est moins négatif que α (le taux pour les processus en attente), les processus en cours d’exécution perdent de la priorité plus lentement que ceux en attente. En conséquence, les processus en cours d’exécution sont susceptibles de conserver leur priorité plus élevée pendant un certain temps, tandis que les processus en attente diminueront leur priorité plus rapidement. Ce comportement ressemble à un ordonnancement Dernier Entré, Premier Sorti (Last-In, First-Out – LIFO), car les processus les plus récents en attente seront priorisés par rapport aux processus plus anciens, ce qui conduit à une situation où les processus ajoutés le plus récemment sont plus susceptibles d’être programmés ensuite.

Résumé

• A. β > α > 0 → FCFS
• B. α < β < 0 → LIFO

L’algorithme d’ordonnancement qui favorise les processus ayant utilisé le moins de temps processeur récemment va privilégier les programmes liés aux E/S pour plusieurs raisons, tout en évitant de rendre les programmes liés aux CPU définitivement affamés.

Favoriser les programmes liés aux E/S

• Courtes périodes d’utilisation du CPU: Les programmes liés aux E/S nécessitent généralement moins de temps CPU et passent plus de temps en attente d’opérations d’entrée/sortie. Ils ont donc des périodes d’utilisation du CPU relativement courtes, ce qui les rend plus susceptibles d’avoir moins de temps CPU accumulé.
• Utilisation récente du CPU: L’algorithme favorise les processus ayant utilisé le moins de temps CPU récemment. Comme les programmes liés aux E/S utilisent le CPU pendant des périodes plus courtes, ils auront souvent une priorité plus élevée dans la file d’attente des processus.

Prévention de la starvation des programmes liés aux CPU

• Changement de contexte fréquent: Les programmes liés aux E/S libèrent régulièrement le CPU pour effectuer leurs opérations d’E/S. Cela crée des occasions pour le planificateur d’allouer du temps CPU aux processus liés aux CPU.
• Mécanismes d’équité: La plupart des algorithmes d’ordonnancement modernes intègrent des mécanismes pour garantir que tous les processus, y compris ceux liés aux CPU, reçoivent du temps CPU. Même s’ils consomment plus de temps CPU, ils ne seront pas définitivement affamés, car les programmes liés aux E/S cèdent souvent le CPU.

Conclusion

En résumé, cet algorithme d’ordonnancement favorise les programmes liés aux E/S en raison de leur utilisation courte du CPU tout en s’assurant que les programmes liés aux CPU continuent de recevoir du temps CPU périodiquement, évitant ainsi la starvation.

Voici une explication des différences dans le degré de discrimination des algorithmes d’ordonnancement en faveur des processus courts:

A. FCFS (First-Come, First-Served)

• Discrimination: FCFS désavantage les jobs courts.
• Raison: Les jobs courts qui arrivent après des jobs longs doivent attendre que ces derniers soient terminés, ce qui entraîne des temps d’attente plus longs pour les jobs courts.

B. RR (Round Robin)

• Discrimination: RR traite tous les jobs de manière égale.
• Raison: Chaque travail reçoit des tranches de temps CPU égales. Cependant, les jobs courts peuvent quitter le système plus rapidement, car ils sont susceptibles de terminer leur exécution pendant leur première ou deuxième tranche de temps, surtout s’ils arrivent tôt dans le cycle.

C. Multilevel Feedback Queues

• Discrimination: Les files d’attente à rétroaction multiple favorisent également les jobs courts.
• Raison: Cet algorithme fonctionne de manière similaire à RR, mais il utilise plusieurs niveaux de priorité. Les jobs qui utilisent moins de temps CPU peuvent être déplacés vers des niveaux de priorité plus élevés, leur permettant d’obtenir plus de temps CPU et de terminer plus rapidement.

Résumé:

• FCFS: Désavantage les jobs courts.
• RR: Traite tous les jobs également, mais permet aux jobs courts de partir plus rapidement.
• Multilevel Feedback Queues: Favorise activement les jobs courts en leur donnant une meilleure priorité.

A. Est-il possible que le thread T2 s’exécute pendant le quantum de temps de T1 ? Expliquez.

Oui, si le thread T1 se bloque pour une raison quelconque (comme une opération d’E/S), la JVM programmera un autre thread. Dans ce cas, ce serait le thread T2.

B. Que se passe-t-il si le thread actuellement en cours d’exécution a sa méthode stop() invoquée pendant son quantum de temps ?

Le reste de son quantum de temps sera partagé par tous les autres threads dans la file d’attente en utilisant l’algorithme d’ordonnancement par défaut de la JVM.

C. Que se passe-t-il si le planificateur sélectionne un thread à exécuter qui a eu sa méthode suspend() invoquée ?

Le reste de son quantum de temps sera également partagé par tous les autres threads dans la file d’attente en utilisant l’algorithme d’ordonnancement par défaut de la JVM.

Réponse:
A. Les priorités assignées aux processus sont respectivement 80, 69 et 65.
B. Le planificateur abaisse la priorité relative des processus liés aux CPU.

Explication:
 
Calcul des Priorités:

 
Interprétation des Résultats:

Les valeurs des priorités calculées (80, 69, 65) signifient que P1 a la priorité la plus faible (80) et P3 la plus élevée (65).

Dans le contexte du planificateur UNIX, un numéro de priorité plus élevé indique une priorité plus faible. Ainsi, P1, qui est probablement un processus liés aux CPU avec une utilisation élevée, a une priorité plus basse.

Conclusion:

Le planificateur UNIX traditionnel abaisse donc la priorité relative des processus liés aux CPU, car une utilisation intensive du CPU (comme pour P1) conduit à une augmentation du numéro de priorité (donc une diminution de la priorité). Cela encourage le système à donner plus de temps à des processus moins gourmands en CPU.