LinuxSchedulers.tex

\documentclass{article} 

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}

\begin{document}
\noindent Philippe Gingras
\newline
Jean-Gabriel Gill-Couture
\newpage
\section{Introduction}
Dans presque tous les systèmes d'exploitations actuels, il est possible d'executer plusieurs tâches simultanément; ou en alternant entre elles si rapidement qu'un humain a l'impression de simultanéité. Ce principe apporte un problème important : celui d'ordonner l'exécution de ces multiples tâches. Effectivement, comme dans la vie d'un humain, le processeur a certaines tâches plus longues et d'autres plus courtes à exécuter. Les tâches les plus longues ne doivent pas trop faire attendre les plus courtes mais doivent tout de même être accomplie à un certain moment. C'est la façon de gérer ces priorités qu'on appelle l'ordonnancement.
\newline
\newline

Les ordonnanceurs étant une partie importante d'un système d'exploitation, il en existe une grande variété selon les applications et le type de microprocesseur. Cet article visera à expliciter les principales différences entre ces ordonnaceurs et leurs applications spécifiques.


\section{Ordonnancement}

\subsection{Traitement par lots}
\subsubsection{Premier arrivé, premier servi (FCFS)}
Cet algorithme d'ordonancement est un des plus simple qui existe autant pour ce qui est de le comprendre que de le programmer. Essentiellement, cet algorithme garde une file dans laquelle les processus sont rangés en attendant d'être exécutés dans leur ordre d'arrivé. Il n'y a aucun autre facteur qui est pris en compte pour donner la priorité aux processus. Le plus grand avantage du FCFS est le fait que l'algorithme garanti qu'il n'y aura jamais de famine. En contrepartie, le temps d'attente des processus est loin d'être optimal, car des processus qui prennent beaucoup de temps à exécuter vont être exécuter en entier même s'il y a plusieurs processus très cours qui se trouvent derière dans la file. 
\newline
\newline
Par exemple, si on a 3 processus qui entrent dans la file un après l'autre:  $F_1$ = 18 sec, $F_2$ = 6 sec et $F_3$ = 3 sec. Le temps d'attente moyen sera de (0 + 18 + 24) / 3 = 14 sec. Ce temps d'attente est loin d'être le meilleur et exécuter les processus dans un ordre différent le réduirait drastiquement. Dans ce cas-ci, l'ordre optimal serait $F_3$, $F_2$, $F_1$ ce qui ferait un temps d'attente moyen de (0 + 3 + 9) / 3 = 4 sec.

\subsubsection{Plus court en premier}

Cet algorithme va toujours exécuter la tâche la plus courte en premier comme son nom l'indique. Cela permet de règler le problème de temps d'attente du FCFS, mais vient avec le désavantage majeur qu'il peut causer de la famine s'il y a un processus qui prend beaucoup de temps à exécuter et un flot de processus plus courts qui vont toujours avoir la priorité sur ce processus dont le temps d'attente va continuer à croître.
\newline
\newline
Il existe aussi une autre variante de cet algorithme qui applique le même principe, mais avec le temps restant le plus court. La différence majeur est qu'avec le plus court en premier un processus sera exécuté en entier même s'il est plus long qu'un nouveau processus qui arrive. Cet variante de l'algoritme fait en sorte que si le temps restant du processus en cours est plus long que la nouvelle job qui arrive il sera interrompu et la priorité sera donnée au nouveau processus.
\subsection{Interactifs}

\subsubsection{tourniquet (round robin)} 

L'ordonnancement de type tourniquet est un type qui est en général plus efficace et donc plus utilisé que les algorithmes décrits précédemment. Le principe de cet algorithme est que chaque processus se voit attribuer une période de temps qu'on peut appeler quantum pendant lequel il peut s'exécuter. Donc, chaque processus s'exécute pour le temps d'un quantum à tour de rôle. Évidemment, si la job se termine avant la fin du quantum on passe directement au prochain processus. L'avantage de ce type d'ordonnancement est le fait que nous pouvons être certain qu'il n'y aura pas de famine et, en plus, cela ne vient pas avec le désavantage du FCFS où un processus long s'exécutera en entier faisant attendre les autres processus pendant longtemps. Par contre, l'ordonnancement de type tourniquet n'est pas parfait et pose le problème d'un choix approprié pour la longueur d'un quantum. Idéalement, on voudrait pouvoir choisir un quantum très cours pour pouvoir éviter de faire attendre les processus trop longtemps s'ils sont nombreux à arriver en même temps. Par contre, un choix de quantum trop cours vient avec le problème majeur que le temps de changement de processus n'est pas nul et doit être pris en compte pour ne utiliser un pourcentage trop élevé des ressources sur cette tâche qui n'accompli rien.
\newline
\newline
En réalité, la longueur choisi pour un quantum varie entre 20-50 ms. Par exemple, si 40 requêtes arrivent dans un interval de temps court et que la durée du quantum est de 30ms nous pouvons être certain que la dernière requête se fera attribuer du temps d'exécution au maximum 1.2 secondes après son arrivée ce qui est très raisonnable. Par ailleurs, si le changement de processus prend environ 1ms, il y a une perte de performance de seulement 3.33\% (1ms/30ms) ce qui, sans être négligable, n'est pas trop élevé.

\subsubsection{ordonnancement par priorités}

Cet algorithme s'utilise en donnant un niveau de priorité à chaque processus et en exécutant le processus qui a le plus haut niveau de priorité en premier. Sans aucun ajustement cet méthode causerait un problème de famine et seul les processus à priorité élevé se verraient attribuer du temps. Pour cette raison, le niveau de priorité d'un processus diminue avec le temps permettant de laisser la place aux processus qui sont moins prioritaires
\newline
\newline

Sous Linux, il existe la commande \emph{nice} qui permet de modifier la priorité d'un processus. Selon l'ordonnanceur utilisé, cette priorité a un effet différent sur la façon dont sera traitée la tâche. Dans certains cas comme celui du \emph{Completely Fair Scheduler} l'augmentation de la priorité d'un processus lui accordera une plus longue période d'exécution. Cette façon de faire simplifie le procédé d'ordonnancement en évitant de maintenir et modifier constamment un "indice de priorité" comme certains autre ordonnanceurs font.


\subsection{Temps réel}

L'ordonnancement en temps réel des processus est un principe très pratique dans les cas où une faible \emph{latence} est nécessaire. Le domaine de l'enregistrement audio est particulièrement demandant à ce niveau et la latence est souvent un critère important pour l'utilisation d'un système dans un studio professionnel.
\newline
\newline
Dans le cas de l'enregistrement audio, le principe de faible latence permet concrètement de diminuer le temps entre la capture du son par le micro et la sortie du son dans les enceintes, ce qui est critique lorsqu'on enregistre plusieurs musiciens au même moment séparés dans différents locaux. Effectivement des temps de latence de plus de 20 millisecondes (1 / 50 seconde) est audible par l'humain et peut devient très gênant dans un contexte comme celui là. Un noyau configuré en temps réel permet facilement de diminuer la latence jusqu'à aussi peu que 5 millisecondes, ce qui est parfaitement acceptable dans ce domaine tandis qu'on noyau n'ayant pas cette fonctionnalité activée ne pourra pas aller en dessous des 40 ou 50 millisecondes dans la majorité des cas. 
\newline
\newline
Au niveau de l'ordonnanceur, une façon de faire du \emph{realtime scheduling} est d'interdire l'interruption d'un processus possédant la priorité temps réel. Cette priorité est nommée \emph{SCHED\_FIFO} dans les ordonnanceurs Linux. Une tâche possédant la priorité SCHED\_FIFO devient donc non préemptive. Il existe cette autre façon de faire qui est de permettre la préemptivité de ce processus de manière limitée, c'est à dire que le processus peut être interrompu mais seulement après un temps donné (quantum).
\newline
\newline
L'ordonnancement en temps réel présente certains avantages comme la faible latence mais également un inconvénient majeur : une utilisation accrue du processeur. Sur un ordinateur de puissance moyenne (Core 2 Duo 2.66Ghz en date de 2014) la diminution de la latence du serveur de son JACK jusqu'à 5 millisecondes entraînait une utilisation du 5processus de 50 à 80  \% ce qui est évidemment inacceptable.
\newpage

\section{Conclusion}

L'ordonnancement est un problème auquel un grand nombre de solution ont été trouvés, mais chacune de ses solutions comporte ses lacunes. Il s'agit d'un problème qui est NP-complet ce qui fait que la recherche pour l'algorithme parfait est très difficile.

\begin{thebibliography}{9}
\bibitem{systeme}
Tanenbaum, Andrew. 2008. Systèmes d'exploitation. 3ème édition. France: Pearson Education France, 1052p.
\end{thebibliography}


\end{document}