144 lines
5.7 KiB
TeX
144 lines
5.7 KiB
TeX
\chapter{Ordonnancement des processus}
|
|
|
|
\section{Généralités}
|
|
|
|
La durée de cycle d'un processus, c'est la durée moyenne d'un cycle de
|
|
Von-Neuman non intérompu (pour des entrées/sorties).
|
|
|
|
Globalement, pour un ordinateur grand public, la plus grande majorité
|
|
des programmes se trouvent être majoritairement tributaire des
|
|
entrées/sorties.
|
|
|
|
\subsection{Ordonnancement et réquisition}
|
|
|
|
Il existe deux familles d'ordonnanceurs : avec ou sans
|
|
réquisitions. On parle alors de système coopératifs ou préemptifs.
|
|
|
|
Pour commuter, il peut se passer deux choses :
|
|
- soit ce n'est pas un choix : le processus s'est bloqué pour une E/S
|
|
ou s'est terminé.
|
|
- un choix : par exemple lorsqu'un nouveau processus arrive ; passage
|
|
des états actifs ou bloqués à l'état prêt.
|
|
|
|
Les ordonnanceurs sans réquisition ne passe la main à d'autres
|
|
processus que dans le cas où un autre processus se bloque.
|
|
Dans un système de ce type, on demande au programmeur de placer dans
|
|
son code des yield, un appel système pour passer la main à un autre
|
|
programme.
|
|
|
|
Le problème d'un système préemptif c'est la synchronisation (il ne
|
|
faudrait pas arrêter un processus en pleine transaction réseau ou
|
|
lors d'un appel système, ...)
|
|
Pour une horloge à temps fixe est nécessaire pour ce genre de système.
|
|
|
|
\subsection{Critères d'ordonnancement}
|
|
|
|
Pour tous les systèmes, les grandes lignes sont~:
|
|
\begin{itemize}
|
|
\item \textbf{Équité~:} répartition du CPU entre processus différent
|
|
(faut-il donner autant de CPU à tous)
|
|
\item \textbf{Respect de politique~:} imposer les choix
|
|
d'ordonnacement. Regarder que tous les processus respectent bien
|
|
les règles d'ordonnancement définies.
|
|
\item \textbf{Équilibre~:} le choix de l'ordonnanceur ne doit pas
|
|
conduire à un trop grand nombre de périphériques inactifs.
|
|
\end{itemize}
|
|
|
|
Pour un système de traitement par lot, les grandes lignes sont
|
|
plutôt~:
|
|
\begin{itemize}
|
|
\item \textbf{Capacité de traitement/rendement~:} mombre de
|
|
processus exécutés par unité de temps.
|
|
\item \textbf{Temps de restitution/service~:} délai entre la
|
|
soumission d'un processus et sa terminaison (mise en mémoire,
|
|
atente en état prêt, attente E/S, exécution)
|
|
\end{itemize}
|
|
|
|
Pour des processus interactifs, les grandes lignes sont~:
|
|
\begin{itemize}
|
|
\item \textbf{Temps de réponse~:} délai entre la soumission et le
|
|
moment où l'oin commence à répondre.\\
|
|
Paradoxalement, un processus plus long à s'exécuter peut être
|
|
préféré s'il répond plus vite.
|
|
\item \textbf{Temps d'attente~:} temps passé en état prêt.\\
|
|
C'est évidemment du gachi pour l'utilisateur.
|
|
\item \textbf{Proportionnalité~:} aux attentes des utilisateurs.\\
|
|
Répondre en fonction des critères de l'utilisateur. (commande
|
|
\texttt{nice}).
|
|
\end{itemize}
|
|
|
|
Dans le cas des systèmes temps réels, les deux critères importants
|
|
sont~: le respect des dates limites (éviter la perte de données) et la
|
|
prédictibilité (pour la stabilité des applications multimédia).
|
|
|
|
\section{Algorithmes d'ordonnancement}
|
|
|
|
\subsection{Premier arrivé premier servi}
|
|
|
|
C'est le premier algorithme à avoir été implémenté, directement issue
|
|
du traitement par lot.
|
|
|
|
Il s'agit d'un algorithme sans réquistion. Il est facile à comprendre
|
|
est facile à programmer.
|
|
Il y a une file d'attente des processus « prêt ». C'est relativement
|
|
optimal et peut couteux~: des simples mises à jour de pointeurs pour
|
|
la gestion de la file.
|
|
|
|
Il est intrinsèquement équitable pour des processus équivalent.
|
|
|
|
Les problèmes de cet algo sont la grande variance dans les critères
|
|
d'ordonnancement ; mais également l'effet d'accumulation~: les petits
|
|
processus qui font de nombreux accès aux périphériques perdent
|
|
énormément de temps car les périphériques sont inactifs le temps qu'un
|
|
processus long s'exécute.
|
|
|
|
|
|
\subsection{Plus court d'abord}
|
|
|
|
Il s'agit d'un algorithme sans réquisition
|
|
|
|
C'est le meilleur algo pour avoir un temps d'attente moyen minimal.
|
|
|
|
Le problème de cet algo est que l'on est pas capable de
|
|
l'implémenter, car on est pas capable de calculer la durée du prochain
|
|
cycle :D
|
|
|
|
Cet algo n'est pas adapté pour l'ordonnancement à court terme, mais
|
|
reste valable pour les systèmes de traitement par lots.
|
|
Étant donné qu'il est optimal, on peut l'utiliser pour benchmarker les
|
|
autres types d'ordonnanceurs.
|
|
|
|
\subsection{Ordonnancement avec priorité}
|
|
|
|
|
|
\subsection{Tourniquet}
|
|
|
|
Concu spécialement pour le temps partagé.
|
|
C'est un FCFS avec réquisition sur une base de quantums (20-50ms).
|
|
Il nécesite une horloge pour permettre d'être préamptif.
|
|
|
|
Il y a quelques précautions à prendre~:
|
|
- Le quantum doit être grand par rapport au temps de commutation
|
|
- Le quantum ne doit pas être trop grand
|
|
|
|
\subsection{Files d'attentes multi-niveau}
|
|
|
|
On découpe la file d'attente des processus prêts en plusieurs files (processus système, interactifs, arrière-plan, ...)
|
|
Il est donc possible d'utiliser un algorithme d'ordonnancement différent pour chaque file. On peut également ordonnancer les files entre-elles (priorité fixes,
|
|
allocation de tranches de temps, ...)
|
|
|
|
Il est généralement utilisé conjointement avec un ordinnancement avec feedback (ou recyclage) comme algo de veillissement : il s'agit de la possibilité de
|
|
déplacer les processus d'une file d'attente à l'autre. L'implementation est légère.
|
|
|
|
\subsection{Loterie}
|
|
|
|
OVNI dans la théorie de l'ordonnancement.
|
|
|
|
Chaque processus qui arrive dans la liste se voit attribuer un numéro, puis à intervalle régulier, il va choisir un processus aléatoirement.
|
|
|
|
Il a quelques avantages :
|
|
- L'implémentation de priorité est légère : il suffit de lui donner deux tickets d'ordonnanceur ou plus !
|
|
|
|
\subsection{Ordonnancement temps-réel}
|
|
|