À quoi sert le cours de systèmes d’exploitation ?

Un jour, un étudiant m’a posé la question en cours: “À quoi sert le cours de systèmes d’exploitation ?”. Excellente question ! À mon humble avis, c’est un sujet intéressant en soi. Mais ce n’est pas la réponse que mes étudiants mathématiciens veulent entendre.

L’algorithme joue un rôle crucial dans la performance d’un programme, mais ce n’est pas le seul facteur. Les interactions du programme avec le matériel peuvent changer son temps d’exécution de plusieurs ordres de grandeurs, jusqu’à ralentir votre programme d’un facteur 1000 ou 10000. Toutes les interactions avec le matériel passent par le système d’exploitation, y compris les caches du processeur, pour des problèmes de couleurs dans les caches multi-voies. Il faut donc les comprendre pour éviter de “programmer contre son camp”, et être capable de comprendre ce qui se passe.

Calculabilité et ordinateur

Au 19ième siècle, les mathématiciens ont inventé la notion de calculabilité: ce que l’on peut calculer. Cette notion est insuffisante en Informatique. En Informatique, le but est de vraiment calculer avec une machine physique stupide ayant une taille mémoire limitée et une vitesse de calcul limitée.

Algorithmique et programmation

Pour le même algorithme, il y a de nombreuse façons différentes de l’implanter. Pour le tri par insertion (ce n’est pas l’algorithme le plus compliqué), il existe au moins 4 familles d’implantation dans le rosetta code (avec un tableau statique en décalant en partant de la fin, avec un tableau dynamique en l’agrandissant, avec des listes, avec une recherche dichotomique combiné des opérateurs de slices sur les tableaux) et je n’ai pas compté PROLOG.

Dans le même ordre d’idées, les programmes ne sont plus écrits en assembleurs et les programmeurs ne manipulent pas uniquement des 0 et des 1 en RAM. Ils utilisent des “objets” de haut-niveau fournis par le système. Trois “objets” au moins: les processus, la mémoire virtuelle, les fichiers.

C’est le système d’exploitation qui coordonne l’exécution des programmes sur la machine. L’utilisateur va demander au système d’exploitation de lancer son programme. Le système va charger ce programme en mémoire pour pouvoir l’exécuter sur le processeur. Le programme va utiliser de la mémoire, qu’il va demander et rendre dynamiquement en fonction de ses besoins au cours de son exécution. Le programme va lire des données (des fichiers) indiquant au système ce dont il a besoin. De même il va écrire ses données en passant par le système. Il va aussi se coordonner avec les autres programmes en exécution. Cette coordination passe aussi par le système: terminaison, échange de message, flux de données.

Il y a de nombreuses façons différentes d’implanter cette discussion avec le système d’un même algorithme. Et donc le système d’exploitation a un impact majeur (pour dire un chiffre, un facteur entre 1 à 10000 (si si)) sur le temps d’exécution.

Le cours de système sert comprendre, expliquer et optimiser, le temps d’exécution d’un programme. C’est un complément direct du cours d’algorithmique lorsque l’on programme.

Quelques exemples simples d’impacts forts sur les performances:

Prenons un même algorithme implanté avec le même langage dans deux programmes par deux personnes différentes (vous et votre stagiaire). L’un s’exécute en 3ms, l’autre en 30 secondes. Pourquoi ?

Les sections suivantes donnent des exemples.

Allocation mémoire

1. Le programme qui dure 3ms alloue une grande quantité de mémoire, mais en plusieurs fois, uniquement par petit morceau, en prenant soin de libérer ce qui est inutile
2. Au contraire, le programme qui dure 3ms alloue en une seule fois toute sa mémoire, tandis que l’autre passe son temps à allouer, et libérer, de la mémoire
3. Le programme qui dure 3ms alloue un énorme bloc de mémoire que le système lui garantie être initialisé à 0, l’autre écrit 0 partout dans le bloc pour l’initialiser.

Lecture de fichiers

1. Le programme qui dure 3ms lit une seule fois son fichier de données, tandis que l’autre passe son temps à ouvrir, relire et fermer ce même fichier.
2. Le programme qui dure 3ms lit uniquement la portion pertinente d’un gros fichier, tandis que l’autre le parcourt en entier pour trouver cette partie pertinente.

Écriture de données et synchronisation

1. Le programme qui dure 3ms n’affiche rien, tandis que l’autre fait beaucoup de printf dans son terminal. Le terminal est géré par un autre programme. La communication entre les deux programmes est grossièrement synchrone. Il faut attendre que le terminal ait fini d’afficher les printf précédents avant de pouvoir y écrire les suivants (à quelques centaines de lignes près).

Communication et synchronisation

1. Le programme qui dure 3ms communique directement les données qu’il produit à un autre programme en exécution qui va les consommer, tandis que l’autre écrit une grande quantité de données dans un fichier qui seront lu plus tard par le consommateur.
2. Au contraire, le programme qui dure 3ms écrit ses résultats dans un fichier car le processus consommateur n’est pas prêt à les recevoir avant 30 secondes.

Tailles et effet de seuil

Les exemples précédents utilisent volontairement des mots flous comme: gros, grand, beaucoup, trop, longtemps, etc. Ces notions fonctionnent souvent avec des seuils quasiment binaires qui dépendent de la machine physique (taille des caches) et des réglages du système (taille des tampons).

Quelques exemples d’impacts complexes (Il y a des mots compliqués, voir jargonneux, dans cette partie :-) )

Prenons un programme dont le temps d’exécution est instable. Il varie significativement suivant les exécutions. Pourquoi ?

D’autres programmes sont en train de s’exécuter

D’autres programmes sont peut être eux-aussi en train de s’exécuter. Ils utilisent aussi la machine, ses processeurs, sa mémoire, ses caches, son réseau, son système de fichiers. Ils peuvent donc retarder l’exécution si ils utilisent les mêmes ressources que votre programme, ou si ces ressources sont en conflits.

La machine swappe à cause d’un autre programme

Deux programmes veulent plus que la moitié de la mémoire de la machine. Le système passe son temps à copier des portions de sa mémoire sur le disque (lent).

Programme multi-threadé

Le système choisit l’ordonnancement des threads. Si votre programme y est particulièrement sensible, cela peut suffire.

Utilisation d’un Ramasse-miette

Le Garbage-Collector peut se déclencher pour des raisons externes à votre programme, ou asynchrone par rapport à son exécution. Suivant le moment où son travail va s’effectuer, il peut prendre plus ou moins de temps.

Lien direct entre le placement de l’allocation mémoire et l’architecture

Arguments donnés comme des variables d’environnement

La taille des variables d’environnement (comme PATH) modifie l’alignement des variables globales du programme, donc l’usage plus ou moins efficace des caches.

Allocation mémoire de tailles différente dans des ordres différents

Votre programme alloue des blocs de mémoire de tailles différentes dans un ordre aléatoire à chaque exécution: problème d’alignement, de partage de cache, de couleurs de page pour les caches multi-voies (les plus communs).

Deux threads, chacun avec sa variable globale

Votre programme utilise deux threads et ces deux threads manipulent chacun abondamment deux variables globales indépendantes, sans lock. Mais ces deux variables sont placées sur la même ligne de cache provoquant de nombreuses invalidations forçant une lecture en RAM.

Les systèmes d’exploitation et les bugs

Il est plus facile d’aller sur la lune que d’écrire un programme de taille moyenne sans bug. On sait aller sur la lune depuis 50 ans. Pour les bugs, vous pouvez lire https://en.wikipedia.org/wiki/List_of_software_bugs pour vous persuader.

Les programmes sont exécutés dans un environnement particulier avec des entrées/sorties particulières. De nombreux bugs ne viennent pas de l’algorithme mais des interactions entre le programme et le reste du monde. Ces interactions passent presque toutes par le système d’exploitation. Comprendre ces bugs nécéssitent de comprendre ce que fait le système d’exploitation. Trouver le bug consiste aussi à modifier ce que fait le système pour pouvoir éliminer certaines pistes.

En résumé

Le cours de système d’exploitation est un complément indispensable au cours d’algorithmique pour être capable de comprendre et d’analyser la performance de l’implantation d’un algorithme.

Deux autres cours interviennent dans ce même registre de manière complémentaire: le cours d’"Architecture des ordinateurs", notamment pour les problèmes de caches, et le cours de “Réseaux”, pour les programmes distribués.