Sur les interruptions du système

Un OS moderne fait typiquement plusieurs choses en même temps : processus qui calculent, entrées-sorties sur le disque, le réseau, interaction avec l’utilisateur, … Le noyau doit être en mesure de traiter des interruptions, c’est-à-dire des événements qui provoquent un arrêt du flot d’exécution actuel pour entrer dans une routine système. Les interruptions peuvent avoir plusieurs sources, en particulier certaines sont prévisibles et dépendent uniquement du programme en cours, et d’autres dépendent d’interactions avec le matériel et peuvent survenir n’importe quand.

Le traîtement des interruptions pose évidemment des problèmes de synchronisation : comment s’assurer que l’interruption peut être traîtée ici et maintenant sans déranger le processus en cours, comment communiquer avec les autres tâches du système dans un contexte d’exception où certaines opérations sont interdites, etc.

Les routines appellées lorsqu’une interruption survient sont décrites dans l’IDT (Interrupt Descriptor Table) qui est mis en place très rapidement lors de l’initialisation du noyau.

Lorsqu’une interruption survient alors que le processeur est en mode noyau, l’interruption est exécutée sur la pile courante, c’est-à-dire que la tâche actuelle est interrompue jusqu’à ce que la routine d’interruption rende la main à la tache précédemment en cours. Lorsqu’une interruption survient en mode utilisateur, dans la plupart des OS le processeur passe en mode noyau et met ESP à une valeur prédéfinie. En général l’OS utilise une pile en mode noyau pour chaque thread du système, mais d’autres schémas sont possibles, en particulier on peut n’avoir qu’une pile noyau par CPU.

Différents types d’interruptions

Les interruptions matérielles

Les interruptions matérielles, ou IRQ (Interrupt Requests) sont des interruptions causées par le matériel et transitant par un composant de la carte mère appellé PIC (Programmable Interrupt Controller), ou APIC (Advanced PIC) sur les systèmes plus récents. Le PIC a le pouvoir d’interrompre le processeur dans le cas d’une interruption matérielle, mais le processeur peut néanmoins bloquer les interruptions matérielles en désactivant un flag, le flag IF. Ceci se fait avec les deux instructions assembleur cli (Clear IF, désactive les interruptions) et sti (Set IF, active les interruptions). De plus, une entrée IDT spécifie si le flag IF doit être désactivé au moment où l’on recoit une interruption, ce qui fait que le traitement de cette interruption ne pourra pas être lui-même interrompu par une nouvelle interruption.

Les exceptions du processeur

Le processeur déclenche une interruption lorsque des circonstances l’empêchent de continuer normalement. En particulier des opérations invalides, une division par zéro ou encore un accès à une zone mémoire invalide déclenchent une exception.

L’exception de défaut de page (page fault) est particulièrement utile car elle permet de rajouter de la mémoire “à la demande” aux processus utilisateur. Les autres exceptions ont habituellement pour conséquence la terminaison de la tâche en cours.

Les appels système

Dans la plupart des OS les appels systèmes sont implémentés via l’instruction int qui déclenche une interruption du processeur. L’interruption ne pouvant être traîtée qu’en mode noyau, le processeur passe en mode noyau et exécute un handler correspondant, qui traîte l’interruption comme un appel système. Les paramètres de l’appel sont typiquement passés par les registres généraux (Linux) ou par la pile (BSD).

Problèmes de synchronisation

Verrous et threads

Les IRQ sont les interruptions qui posent le plus problème : celles-ci doivent être traîtées rapidement car il faut communiquer avec le matériel qui attent de nous dire quelque chose de précis. Néanmoins celles-ci doivent également être capable de discuter avec les autres parties du système, et en particulier d’utiliser des structures à accès non atomique et nécessitant donc l’acquisition d’un verrou (mutex). L’implémentation de base de l’opération de vérouillage d’une mutex consiste à, en une opération atomique, récupérer l’état précédent de la mutex et définir son état courant à “vérouillé”. Si son état précédent était déjà “vérouillé”, alors on n’a pas pu obtenir le verrou et on fait une pause pour laisser s’exécuter d’autres threads. En particulier on espère que le thread qui a le verrou va pouvoir terminer ses opérations sur les données et libérer le verrou, ce qui permettera de l’utiliser dans le traîtement de l’IRQ.

Néanmoins il y a un problème à cela : en effet, si l’IRQ a eu lieu dans le thread qui possédait le verrou, alors on ne peut pas retourner dans la partie qui utilise la ressource sans terminer la routine de traîtement d’IRQ. L’utilisation de cette stratégie simple risque donc de nous laisser avec un deadlock.

Notion de lower half et higher half

On peut donc diviser le code du noyau en deux catégories :

• Le code dit lower half qui s’exécute lors d’une IRQ. Ce code s’exécute généralement en mode non-interruptible (c’est-à-dire avec IF désactivé), et ne peut pas réaliser de changement de contexte (task switching) pour attendre qu’un verrou se libère. Ce code doit effectuer une partie de la communication avec le matériel car celui-ci requiert une réponse rapide, mais il doit très rapidement rendre la main afin de ne pas bloquer l’exécution du système.
• Le code dit higher half qui s’exécute en temps normal, le plus souvent en mode interruptible. Dans ce code des changements de contexte sont possibles, et le verrouillage des ressources peut se faire de façon classique avec des verrous. En particulier selon les implémentations, l’allocation dynamique de mémoire (kmalloc/kfree) peut nécessiter l’acquisition d’un verrou, ce qui la rend utilisable uniquement en higher half.

Solutions de communication appropriées

Pour communiquer entre lower half et higher half, plusieurs solutions sont possibles :

• Le waiter thread : un thread attend une IRQ, il se met en pause. La routine de gestion de l’IRQ ne fait qu’une chose : relancer l’exécution du thread qui attendait l’IRQ. Toute la communication avec le matériel se fait donc dans le code de ce thread, qui est du code higher half et peut faire ce qu’il veut.
• Les structures de données atomiques : on peut imaginer un FIFO par exemple dans lequel les parties lower half et higher half peuvent lire et écrire de façon atomique. Pour la partie lower half (qui fait généralement l’écriture), elle tourne en mode non-interruptible donc n’a pas de précaution particulière à prendre. La partie higher half peut par contre envisager de passer temporairement en mode non-interruptible afin de lire dans le buffer.
• Les structures de données sans verrou : on peut imaginer une FIFO de type buffer circulaire telle qu’une lecture et une écriture puissent avoir lieu en même temps, dans ce cas il n’y a pas de précaution particulière à prendre.
• Une combinaison des waiter thread et des queues à accès atomique.

Conclusion

La divison lower half / higher half est une solution facilement accessible aux problèmes de synchronisation dus aux IRQ, et c’est celle utilisée notamment dans 4.4BSD. D’autres solutions existent, qui consistent essentiellement à exécuter des portions plus importantes de code en mode non-interruptible. L’extrême étant le micronoyau où tout le code noyau s’exécute en mode non-interruptible (il est de toute façon extrêmement concis), et ce sont des processus utilisateur qui gérent chacun des IRQ (qu’ils reçoivent un peu comme un processus Unix reçoit un signal).