Système d'exploitation

TBD suite des principes systèmes où on rentre plus dans les détails.

Mémoire

Process

Un process est l'unité de base d'un programme. Un process est un ensemble d'instruction exécutées par le système d'exploitation. Tout process est la propriété le l'utilisateur du système qui l'a exécuté.

Noyau

Le noyau est partie intégrante de tout process. Il est toujours là et s'exécute de temps en temps pour effectuer ses tâches.

Multi Process

Les systèmes d'exploitation permettent tous d'exécuter plusieurs threads de façon concurrente :

• plusieurs thread d'un même process : ils partagent la même organisation en mémoire
• plusieurs thread de process différents : chaque process à sa propre organisation en mémoire

Ceci peut se passer même si l'ordinateur ne possède qu'un seul core. La quasi totalité des ordinateurs actuellement sont multi-core, ce qui permet même d'exécuter des threads de façon parallèle.

Chaque thread sur une machine peut–être dans 3 états distincts :

• bloqué : en attente d'une instruction d'entrée/sortie par exemple
• actif : en cours d'exécution
• prêt : prêt à être exécuté

Le principe du multi-processing est est simple. Prenons l'exemple de 2 threads (A et B) à exécuter sur un unique core. Lorsque le noyau lance l'exécution du premier thread, il va demander au processeur de se faire réveiller au bout de 10ms par une interruption. Le thread A s'exécute donc pendant 10ms avant qu'une interruption ne rappelle le noyau qui va pouvoir stopper le thread A (qu'il va placer en mode activable) et réactiver le thread B (il passe de activable à activé). Une fois ceci fait, le noyau se rendort pour 10ms (via une interruption) et le cycle continue.

Si l'ordinateur possède plusieurs core, le noyau choisi sur quel lancer le thread mais le principe est le même : il se réveille à intervalles déterminés pour gérer l'activation et la désactivation des threads.

Cette activation/ désactivation s'appelle le context switching et n'est pas immédiate, il faut en effet s'assurer que le thread B n'endommage pas l'exécution du thread A.

Context switching

L'exécution d'un thread dépend :

• de la mémoire du process dont le thread fait partie
• de sa pile (chaque thread a une pile qui lu est propre)
• des registres du processeur (IP, SP, et tous les autres)

Si l'on exécuter un thread B sur un core qui exécute déjà un thread A il faut :

• sauver les registres du core (ils dépendent du thread A) et les remplacer par ceux sauvé du thread B
• sauver la mémoire (c'est celle associée au thread A) et la remplacer par celle sauvée du thread B :
  • toute la mémoire si les deux threads sont dans 2 process différents
  • uniquement la pile si les deux threads pont partie du même process

S'il est facile de sauver/restaurer tout les registres d'un core (il n'y en a pas beaucoup et sont de petite taille) il n'est pas possible de sauver toute la mémoire.

Même si on ne considère que la mémoire effectivement utilisée par le process (les segments de code, données, pile, tas et bibliothèques partagées) il y en a beaucoup trop pour que le transfert vert le disque dur ne soit pas prohibitif niveau temps. En revanche, ces segments sont loin de remplir toute la mémoire : il y a (normalement) la place de contenir les segments utilisées pour deux threads

L'idée est donc de trouver un moyen efficace en temps pour :

• stocker les segments des deux threads en mémoire
• conserver l'illusion pour chaque thread qu'il est seul en mémoire

Pour cela, on commence par découper toute la mémoire en pages (habituellement de 4KiB) et d'avoir une correspondance entre une mémoire logique, celle que voit le thread et la mémoire physique, en RAM.

On (le noyau) conserve pour chaque thread la correspondance des adresses physiques pour chaque page utilisée par ses segments :

mémoire physique  process A    process B    segments
      a              a           a           noyau
      b              f           b           pile
      c                          e
      d
      e
      f              c           c           bibliothèques partagées
      g
      h              d           k           tas
      j
      j              h           g           data
      l              i           j           code
      0

On voit que le process A et B partagent certaines pages (le code du noyau et les bibliothèques partagées), et qu'il reste de la place pour au moins un troisième process en mémoire.

Avec cette astuce de mémoire logique (vous verrez aussi parfois le terme de virtuelle) et physique, changer de contexte d'exécution pour arrêter un thread et en activer un autre est très rapide ! Encore pus rapide si les deux threads font partie du même process.

Ordonnancement

Si on doit exécuter $n$ thread sur $p < n$ cores il faut :

• choisir sur quel core exécuter chaque thread
• choisir quel thread exécuter
• choisir le temps pendant lequel exécuter chaque thread

Comme chaque thread possède le code du noyau et que chaque core possède un thread : le noyau est présent sur chaque core. Il est ainsi possible pour le noyau :

• d'avoir une liste globale de tous les process du système
• de répartir l'exécution de ces thread sur chaque core.

Le noyau peut donc choisir :

1. quel thread exécuter sur chaque core
2. quel thread activer par core à un moment donné
3. combien de temps laisser activé un thread avant d'en activer un autre

Exemple

TBD : à expliciter.

Core et thread

Le noyau possède pour chaque core une liste de threads qu'ils gère et il peut décider de déplacer un thread d'un core à un autre pour garantir une charge de travail équilibrée entre les différents core. Pour cela, le noyau possède un thread par core dont le but est de migrer si nécessaire un thread d'un core à un autre.

Choisir quel thread exécuter sur quel core pour minimiser le temps total d'exécution est un problème difficile, le noyau a donc des heuristiques de choix simples pour pouvoir décider souvent plutôt qu'optimalement.

Activation et désactivation d'un thread

Plusieurs possibilités existent, chacune avec leurs avantages et inconvénient :

• chacun son tour. Principe du tourniquet (round-robin)
• par priorité :
  • celui qui a été le moins de temps exécuté : utilisé par la méthode actuelle, Completely fair scheduler
  • le premier à finir (utilisé par la nouvelle méthode, EEVDF)
  • ...

Les algorithmes basé sur la priorité doivent pouvoir rapidement :

• choisir le thread le plus prioritaire
• modifier la priorité d'un thread une fois qu'il est activé

Pour cela, on utilise une file de priorité implémentée sous la forme d'un arbre de recherche rouge-noir ce qui permet de garantir des opérations en $\mathcal{O}(\log(N))$.

Temps d'activation

L'algorithme utilisé actuellement (CFS) procède ainsi. Dans un temps donné T, s'il y a $N$ thread à exécuter, on allouera $T/N$ temps à tout le monde.

On s'assure en plus que ce temps est supérieur au temps nécessaire pour le context switching, ce qui assure que tout thread pourra au moins être exécuté 1 cycle.

Création de process/thread

L'ensemble des process est organisé en arbre, à partir du premier process lancé par le noyau.

Un process est composé :

• d'un identifiant (un identifiant noté pid)
• de l'identifiant de son parent (noté ppid)
• de sa table d'allocation mémoire
• d'un ensemble de threads (il y en a au moins 1). Chaque thread étant déterminé par son contexte d'exécution composé de :
  • sa pile
  • les registres du core sur lequel il est exécuté

Création de thread

Il suffit d'allouer une page pour sa pile et créer un contexte d'exécution en associant une valeur au pointeur de pile et au pointeur d'instruction (la première instruction du thread, une fonction du code).

Création de process

La création d'un nouveau process se fait par duplication d'un autre process. C'est un appel système.

Le nouveau process possède :

• un identifiant qui lui est propres
• l'identifiant de son parent est l'identifiant du process à l'initiative de la duplication
• sa table d'allocation mémoire est une copie de la table d'allocation de son parent
• d'un nouveau thread dont le pointeur d'instruction est le même que celui du thread à l'origine de la commande ayant initié la duplication

Ce qui différencie le nouveau process de l'ancien est que le retour du syscall de duplication vaut :

• 0 pour le thread de l'enfant
• le pid (strictement position) du process du thread parent
• -1 si une erreur est survenue

Pour que la duplication des pages mémoires ne soit pas longue, on utilise la technique du copy on write : on garde la même page pour les deux process, on ne duplique la page mémoire que si un des deux process veut modifier la page.

Les process sont ainsi organisé en arbre. Chaque process ayant un parent, à part le premier process exécuté par le noyau dont le but est de créer tous les démons et de finir par le process de login.

Lorsqu'un process se termine (ou est tué par un signal) il commence par terminer ses enfants (en leur envoyant un signal de fin).

Système de fichiers

La mémoire permet de stocker et gérer l'information nécessaire pour l'exécution de process. Il est cependant nécessaire d'avoir un espace de stockage permanent pour stocker les programmes ou les données lorsque l'ordinateur est éteint.

On stocke ces informations sous la forme de fichiers organisés en arborescence.

Démarrage de l'ordinateur

Les différentes étapes du chargement d'un système d'exploitation

1. boot de l'ordinateur
2. exécution d'un chargeur d'amorçage (bootloader)
3. charge le noyau
   1. vérification du matériel
   2. vérification des sous-systèmes : réseau, ...
4. passage en user mode puis charge les démons et les interfaces
5. login

Bibliographie

• deux playlist YouTube :
  • https://www.youtube.com/watch?v=7cQ1PNVYgxw&list=PL2Yggtk_pK6-R9ehjj0AoTnWrNOLChuld
  • https://www.youtube.com/watch?v=TavEuAJ4z9A&list=PLhy9gU5W1fvUND_5mdpbNVHC1WCIaABbP
• du transistor au processeur : https://www.amazon.fr/Code-Language-Computer-Hardware-Software/dp/0137909101
• architecture matérielle : https://www.amazon.fr/Write-Great-Code-2nd-Understanding/dp/171850036X/