NSY 103 - Notes de cours - Examen corrige
Les formateurs seront invités à déposer/proposer un sujet d'examen. ...... Les
signaux de commandes sont distribués grâce à un élément appelé séquenceur.
...... processus et les systèmes de pneumatiques (transfert de flux de données).
part of the document
Méthodes de programmation systèmes
UE n° NSY103
Notes de cours
Code de lUE :
NSY103
Titre de la formation :
Méthodes de programmation systèmes
Ouvert :
Ouvert
Type de diplôme :
Unité de valeur CNAM.
Nombre d'heures :
55h (~18 + 1 cours de 3 heures)
Durée de la formation :
Un semestre - Période : deuxième semestre
Jours de cours
Lundi & Mercredi
Heures de cours
18h00-21h00
Lieu de la formation :
CUCES UNIVERSITES
Salle :
S05 LE LUNDI ET S18 LE MERCREDI (à confirmer)
URL :
http://cours.desvigne.org/
Animateur
Emmanuel DESVIGNE
Document sous licence libre FDL - © Emmanuel DESVIGNE, version 1.0b, avril 2008
Avant propos
Ce document contient les notes de cours de lUE du CNAM « NSY103 : méthodes de programmation systèmes ».
Il a été élaboré à partir des connaissances acquises lors de ma formation initiale (DESS ingénierie des réseaux et systèmes, obtenu à Nancy en 1995), de diverses expériences professionnelles (je travaille actuellement comme responsable informatique à la maternité régionale de Nancy), à laide de la mine dor que représente Internet, et à laide de ces quelques livres :
Joëlle Delacroix Linux : programmation système et réseau, Dunod 2003 ;
Andrew Tanenbaum Systèmes dexploitation, Pearsoneducation 2003 ;
Jean-Marie Rifflet La programmation sous Unix - 3ème édition, Ediscience 1993 ;
Jean-Marie Rifflet La communication sous Unix - 2ème édition, Ediscience 1994.
Dans ces conditions, difficile de revendiquer la paternité du présent melting pot. Aussi, ce document est mis sous licence libre GNU-FDL. Vous pouvez le copier, limprimer, le diffuser, voire lapprendre librement.
Le programme officiel invite le formateur à ne voir que les systèmes Linux et Linux temps réel. Ces systèmes dexploitation proposent effectivement tous les mécanismes décrits dans ce document. Ils sont stables, efficaces... Néanmoins, même sils ont une certaine préférence des personnes ayant rédigé le programme du CNAM pour des raisons éducatives (et du rédacteur du présent document, avouons-le), il est difficile de faire limpasse des autres systèmes dexploitation que le marché propose, comme les Unix, XXX-BSD, Mac OS (qui sen inspire), et MS-Windows. Cest pourquoi, parfois, les philosophies de ces derniers OS seront indiquées, afin dillustrer quil peut y avoir dautres solutions/implémentations, et pour que le candidat acquière une culture générale des systèmes dexploitation.
Ces systèmes dexploitations sont eux-mêmes très largement écrit en C (et parfois en C++). De plus, les travaux dirigés, travaux pratiques, projets devront être rédigés dans ces langages. Aussi, le premier cours sera en grande partie réservé à une mise à niveau sur ces langages, afin de donner les pointeurs pour que tous les candidats possèdent des bases identiques. Si le volume (en nombre de pages) de cette révision est importante, sagissant dun pré-requis, le formateur ne doit pas y passer plus dune séance. Cette mise à niveau pourra demander une quantité plus ou moins importante de travail personnel de la part des candidats.
Table des matières
TOC \o "1-3" \h \z HYPERLINK \l "_Toc196727541" 1 Avant propos PAGEREF _Toc196727541 \h 2
HYPERLINK \l "_Toc196727542" 2 Table des matières PAGEREF _Toc196727542 \h 3
HYPERLINK \l "_Toc196727543" 3 Programme officiel PAGEREF _Toc196727543 \h 9
HYPERLINK \l "_Toc196727544" 3.1 Public concerné et conditions daccès PAGEREF _Toc196727544 \h 9
HYPERLINK \l "_Toc196727545" 3.2 Finalités de lunité denseignement PAGEREF _Toc196727545 \h 9
HYPERLINK \l "_Toc196727546" 3.2.1 Objectifs pédagogiques PAGEREF _Toc196727546 \h 9
HYPERLINK \l "_Toc196727547" 3.2.2 Capacité et compétences acquises PAGEREF _Toc196727547 \h 9
HYPERLINK \l "_Toc196727548" 3.3 Organisation PAGEREF _Toc196727548 \h 9
HYPERLINK \l "_Toc196727549" 3.3.1 Description des heures denseignements PAGEREF _Toc196727549 \h 9
HYPERLINK \l "_Toc196727550" 3.3.2 Modalités de validation PAGEREF _Toc196727550 \h 9
HYPERLINK \l "_Toc196727551" 3.4 Contenu de la formation PAGEREF _Toc196727551 \h 9
HYPERLINK \l "_Toc196727552" 3.5 Bibliographie PAGEREF _Toc196727552 \h 10
HYPERLINK \l "_Toc196727553" 3.6 Contacts PAGEREF _Toc196727553 \h 11
HYPERLINK \l "_Toc196727554" 3.6.1 Coordonnées du secrétariat du responsable national : PAGEREF _Toc196727554 \h 11
HYPERLINK \l "_Toc196727555" 3.6.2 Coordonnées du responsable de cette formation à NANCY : PAGEREF _Toc196727555 \h 11
HYPERLINK \l "_Toc196727556" 3.7 Nouveautés à partir de la session 2006-2007 PAGEREF _Toc196727556 \h 11
HYPERLINK \l "_Toc196727557" 3.7.1 Origine de la réforme PAGEREF _Toc196727557 \h 11
HYPERLINK \l "_Toc196727558" 3.7.2 Résumé du principe de la réforme PAGEREF _Toc196727558 \h 11
HYPERLINK \l "_Toc196727559" 3.7.3 Plan imposé par cette réforme pour le cours NSY103 PAGEREF _Toc196727559 \h 12
HYPERLINK \l "_Toc196727560" 4 Mise à niveau en C/C++ PAGEREF _Toc196727560 \h 13
HYPERLINK \l "_Toc196727561" 4.1 Bref historique du C PAGEREF _Toc196727561 \h 13
HYPERLINK \l "_Toc196727562" 4.2 La compilation PAGEREF _Toc196727562 \h 13
HYPERLINK \l "_Toc196727563" 4.3 Les composants élémentaires du C PAGEREF _Toc196727563 \h 15
HYPERLINK \l "_Toc196727564" 4.3.1 Les identificateurs PAGEREF _Toc196727564 \h 15
HYPERLINK \l "_Toc196727565" 4.3.2 Les mots-clefs PAGEREF _Toc196727565 \h 15
HYPERLINK \l "_Toc196727566" 4.3.3 Les commentaires PAGEREF _Toc196727566 \h 16
HYPERLINK \l "_Toc196727567" 4.4 Structure d'un programme C PAGEREF _Toc196727567 \h 16
HYPERLINK \l "_Toc196727568" 4.5 Les types PAGEREF _Toc196727568 \h 18
HYPERLINK \l "_Toc196727569" 4.5.1 Les types prédéfinis PAGEREF _Toc196727569 \h 18
HYPERLINK \l "_Toc196727570" 4.5.2 Les types composés PAGEREF _Toc196727570 \h 19
HYPERLINK \l "_Toc196727571" 4.6 Les constantes PAGEREF _Toc196727571 \h 21
HYPERLINK \l "_Toc196727572" 4.6.1 Les constantes entières PAGEREF _Toc196727572 \h 21
HYPERLINK \l "_Toc196727573" 4.6.2 Les constantes réelles PAGEREF _Toc196727573 \h 22
HYPERLINK \l "_Toc196727574" 4.6.3 Les constantes caractères PAGEREF _Toc196727574 \h 22
HYPERLINK \l "_Toc196727575" 4.7 Les opérateurs PAGEREF _Toc196727575 \h 23
HYPERLINK \l "_Toc196727576" 4.7.1 L'affectation PAGEREF _Toc196727576 \h 23
HYPERLINK \l "_Toc196727577" 4.7.2 Les opérateurs arithmétiques PAGEREF _Toc196727577 \h 23
HYPERLINK \l "_Toc196727578" 4.7.3 Les opérateurs relationnels PAGEREF _Toc196727578 \h 24
HYPERLINK \l "_Toc196727579" 4.7.4 Les opérateurs logiques booléens PAGEREF _Toc196727579 \h 24
HYPERLINK \l "_Toc196727580" 4.7.5 Les opérateurs logiques bit à bit PAGEREF _Toc196727580 \h 25
HYPERLINK \l "_Toc196727581" 4.7.6 Les opérateurs d'affectation composée PAGEREF _Toc196727581 \h 25
HYPERLINK \l "_Toc196727582" 4.7.7 Les opérateurs d'incrémentation et de décrémentation PAGEREF _Toc196727582 \h 25
HYPERLINK \l "_Toc196727583" 4.7.8 L'opérateur virgule PAGEREF _Toc196727583 \h 26
HYPERLINK \l "_Toc196727584" 4.7.9 L'opérateur conditionnel ternaire PAGEREF _Toc196727584 \h 26
HYPERLINK \l "_Toc196727585" 4.7.10 L'opérateur de conversion de type PAGEREF _Toc196727585 \h 26
HYPERLINK \l "_Toc196727586" 4.7.11 L'opérateur adresse / pointeur / indirection PAGEREF _Toc196727586 \h 26
HYPERLINK \l "_Toc196727587" 4.7.12 Règles de priorité des opérateurs PAGEREF _Toc196727587 \h 28
HYPERLINK \l "_Toc196727588" 4.7.13 Les constantes chaînes de caractères PAGEREF _Toc196727588 \h 29
HYPERLINK \l "_Toc196727589" 4.8 Les instructions de branchement conditionnel PAGEREF _Toc196727589 \h 29
HYPERLINK \l "_Toc196727590" 4.8.1 Branchement conditionnel if... else PAGEREF _Toc196727590 \h 30
HYPERLINK \l "_Toc196727591" 4.8.2 Branchement multiple switch PAGEREF _Toc196727591 \h 30
HYPERLINK \l "_Toc196727592" 4.9 Les boucles PAGEREF _Toc196727592 \h 31
HYPERLINK \l "_Toc196727593" 4.9.1 Boucle while PAGEREF _Toc196727593 \h 31
HYPERLINK \l "_Toc196727594" 4.9.2 Boucle do... while PAGEREF _Toc196727594 \h 31
HYPERLINK \l "_Toc196727595" 4.9.3 Boucle for PAGEREF _Toc196727595 \h 32
HYPERLINK \l "_Toc196727596" 4.10 Les instructions de branchement non conditionnel PAGEREF _Toc196727596 \h 32
HYPERLINK \l "_Toc196727597" 4.10.1 Branchement non conditionnel break PAGEREF _Toc196727597 \h 32
HYPERLINK \l "_Toc196727598" 4.10.2 Branchement non conditionnel continue PAGEREF _Toc196727598 \h 32
HYPERLINK \l "_Toc196727599" 4.10.3 Branchement non conditionnel goto PAGEREF _Toc196727599 \h 33
HYPERLINK \l "_Toc196727600" 4.11 Les fonctions PAGEREF _Toc196727600 \h 33
HYPERLINK \l "_Toc196727601" 4.11.1 Définition dune fonction PAGEREF _Toc196727601 \h 33
HYPERLINK \l "_Toc196727602" 4.11.2 Appel d'une fonction PAGEREF _Toc196727602 \h 34
HYPERLINK \l "_Toc196727603" 4.11.3 Déclaration d'une fonction PAGEREF _Toc196727603 \h 34
HYPERLINK \l "_Toc196727604" 4.11.4 Cas particulier de la fonction main() PAGEREF _Toc196727604 \h 35
HYPERLINK \l "_Toc196727605" 4.11.5 Pointeur sur une fonction PAGEREF _Toc196727605 \h 35
HYPERLINK \l "_Toc196727606" 4.11.6 Fonctions avec un nombre variable de paramètres PAGEREF _Toc196727606 \h 36
HYPERLINK \l "_Toc196727607" 4.12 Durée de vie des variables PAGEREF _Toc196727607 \h 37
HYPERLINK \l "_Toc196727608" 4.12.1 Variables globales PAGEREF _Toc196727608 \h 38
HYPERLINK \l "_Toc196727609" 4.12.2 Variables locales PAGEREF _Toc196727609 \h 38
HYPERLINK \l "_Toc196727610" 4.12.3 Transmission des paramètres d'une fonction PAGEREF _Toc196727610 \h 39
HYPERLINK \l "_Toc196727611" 4.12.4 Les qualificateurs de type const et volatile PAGEREF _Toc196727611 \h 39
HYPERLINK \l "_Toc196727612" 4.13 Les directives au préprocesseur PAGEREF _Toc196727612 \h 40
HYPERLINK \l "_Toc196727613" 4.13.1 La directive #include PAGEREF _Toc196727613 \h 40
HYPERLINK \l "_Toc196727614" 4.13.2 La directive #define PAGEREF _Toc196727614 \h 40
HYPERLINK \l "_Toc196727615" 4.13.3 La compilation conditionnelle PAGEREF _Toc196727615 \h 42
HYPERLINK \l "_Toc196727616" 4.14 Les bibliothèques standards PAGEREF _Toc196727616 \h 43
HYPERLINK \l "_Toc196727617" 4.15 Les conventions d'écriture d'un programme C PAGEREF _Toc196727617 \h 44
HYPERLINK \l "_Toc196727618" 4.16 Le C++ PAGEREF _Toc196727618 \h 44
HYPERLINK \l "_Toc196727619" 4.16.1 Généralités PAGEREF _Toc196727619 \h 44
HYPERLINK \l "_Toc196727620" 4.16.2 Différences entre C et C++ PAGEREF _Toc196727620 \h 45
HYPERLINK \l "_Toc196727621" 4.17 Travaux dirigés PAGEREF _Toc196727621 \h 50
HYPERLINK \l "_Toc196727622" 5 Introduction : architecture des ordinateurs PAGEREF _Toc196727622 \h 54
HYPERLINK \l "_Toc196727623" 5.1 Schéma de base PAGEREF _Toc196727623 \h 54
HYPERLINK \l "_Toc196727624" 5.2 Le microprocesseur (CPU) PAGEREF _Toc196727624 \h 54
HYPERLINK \l "_Toc196727625" 5.2.1 Présentation PAGEREF _Toc196727625 \h 54
HYPERLINK \l "_Toc196727626" 5.2.2 Fonctionnement PAGEREF _Toc196727626 \h 54
HYPERLINK \l "_Toc196727627" 5.2.3 Mémoire cache PAGEREF _Toc196727627 \h 55
HYPERLINK \l "_Toc196727628" 5.2.4 Signaux de commande PAGEREF _Toc196727628 \h 56
HYPERLINK \l "_Toc196727629" 5.2.5 Unités fonctionnelles PAGEREF _Toc196727629 \h 56
HYPERLINK \l "_Toc196727630" 5.2.6 Familles PAGEREF _Toc196727630 \h 57
HYPERLINK \l "_Toc196727631" 5.2.7 Jeu d'instruction, architecture de CPU PAGEREF _Toc196727631 \h 57
HYPERLINK \l "_Toc196727632" 5.2.8 Améliorations technologiques PAGEREF _Toc196727632 \h 58
HYPERLINK \l "_Toc196727633" 5.3 Le bus PAGEREF _Toc196727633 \h 59
HYPERLINK \l "_Toc196727634" 5.3.1 Description PAGEREF _Toc196727634 \h 59
HYPERLINK \l "_Toc196727635" 5.3.2 Matériel PAGEREF _Toc196727635 \h 60
HYPERLINK \l "_Toc196727636" 5.3.3 Dans un ordinateur PAGEREF _Toc196727636 \h 61
HYPERLINK \l "_Toc196727637" 5.4 Le chipset PAGEREF _Toc196727637 \h 61
HYPERLINK \l "_Toc196727638" 5.5 La mémoire PAGEREF _Toc196727638 \h 62
HYPERLINK \l "_Toc196727639" 5.5.1 Caractéristiques techniques PAGEREF _Toc196727639 \h 62
HYPERLINK \l "_Toc196727640" 5.5.2 Temps d'accès et capacité des différents types de mémoire PAGEREF _Toc196727640 \h 63
HYPERLINK \l "_Toc196727641" 5.6 Communication périphériques/CPU PAGEREF _Toc196727641 \h 63
HYPERLINK \l "_Toc196727642" 5.6.1 Les interruptions matérielles (et IRQ) PAGEREF _Toc196727642 \h 63
HYPERLINK \l "_Toc196727643" 5.6.2 Les adresses de base PAGEREF _Toc196727643 \h 64
HYPERLINK \l "_Toc196727644" 5.6.3 Utilisation dun canal DMA PAGEREF _Toc196727644 \h 64
HYPERLINK \l "_Toc196727645" 6 Le système dexploitation PAGEREF _Toc196727645 \h 65
HYPERLINK \l "_Toc196727646" 6.1 Définition PAGEREF _Toc196727646 \h 65
HYPERLINK \l "_Toc196727647" 6.2 Structure générale PAGEREF _Toc196727647 \h 65
HYPERLINK \l "_Toc196727648" 6.3 Les différents types de systèmes dexploitation PAGEREF _Toc196727648 \h 67
HYPERLINK \l "_Toc196727649" 6.3.1 Les systèmes à traitements par lots PAGEREF _Toc196727649 \h 67
HYPERLINK \l "_Toc196727650" 6.3.2 Les systèmes interactifs PAGEREF _Toc196727650 \h 67
HYPERLINK \l "_Toc196727651" 6.3.3 Les systèmes « temps-réel » PAGEREF _Toc196727651 \h 68
HYPERLINK \l "_Toc196727652" 6.4 Le noyau PAGEREF _Toc196727652 \h 68
HYPERLINK \l "_Toc196727653" 6.4.1 Définition PAGEREF _Toc196727653 \h 68
HYPERLINK \l "_Toc196727654" 6.4.2 Les différents types de noyaux PAGEREF _Toc196727654 \h 69
HYPERLINK \l "_Toc196727655" 6.4.3 Avantages et inconvénients des différents types de noyau PAGEREF _Toc196727655 \h 70
HYPERLINK \l "_Toc196727656" 6.5 Linux PAGEREF _Toc196727656 \h 71
HYPERLINK \l "_Toc196727657" 6.5.1 Structure de lOS Linux PAGEREF _Toc196727657 \h 71
HYPERLINK \l "_Toc196727658" 6.5.2 Quelques notions fondamentales PAGEREF _Toc196727658 \h 72
HYPERLINK \l "_Toc196727659" 6.5.3 La commutation de contexte PAGEREF _Toc196727659 \h 72
HYPERLINK \l "_Toc196727660" 6.5.4 Principe de gestion des interruptions matérielles et logicielles PAGEREF _Toc196727660 \h 74
HYPERLINK \l "_Toc196727661" 6.5.5 Prise en compte dune interruption matérielle PAGEREF _Toc196727661 \h 75
HYPERLINK \l "_Toc196727662" 6.5.6 Gestion des exceptions (trappes) PAGEREF _Toc196727662 \h 76
HYPERLINK \l "_Toc196727663" 6.5.7 Exécution dune fonction du système PAGEREF _Toc196727663 \h 77
HYPERLINK \l "_Toc196727664" 6.5.8 Imbrication de la prise en compte des interruptions PAGEREF _Toc196727664 \h 78
HYPERLINK \l "_Toc196727665" 7 Le « multitâche » en pratique PAGEREF _Toc196727665 \h 79
HYPERLINK \l "_Toc196727666" 7.1 Les processus PAGEREF _Toc196727666 \h 79
HYPERLINK \l "_Toc196727667" 7.2 Création dun processus sous Linux PAGEREF _Toc196727667 \h 81
HYPERLINK \l "_Toc196727668" 7.2.1 La fonction fork() PAGEREF _Toc196727668 \h 81
HYPERLINK \l "_Toc196727669" 7.2.2 Les fonctions de gestion des identifiants de processus PAGEREF _Toc196727669 \h 82
HYPERLINK \l "_Toc196727670" 7.2.3 Optimisation de fork() : le « copy on write » PAGEREF _Toc196727670 \h 82
HYPERLINK \l "_Toc196727671" 7.2.4 Les processus zombies (et comment les éviter) PAGEREF _Toc196727671 \h 83
HYPERLINK \l "_Toc196727672" 7.2.5 Les fonctions de recouvrement PAGEREF _Toc196727672 \h 87
HYPERLINK \l "_Toc196727673" 7.3 Les threads (ou processus légers) PAGEREF _Toc196727673 \h 90
HYPERLINK \l "_Toc196727674" 7.3.1 Principe des threads PAGEREF _Toc196727674 \h 90
HYPERLINK \l "_Toc196727675" 7.3.2 Implémentation des threads au niveau utilisateur PAGEREF _Toc196727675 \h 91
HYPERLINK \l "_Toc196727676" 7.3.3 Implémentation des threads au niveau noyau PAGEREF _Toc196727676 \h 92
HYPERLINK \l "_Toc196727677" 7.3.4 Fonctions système liées aux threads PAGEREF _Toc196727677 \h 92
HYPERLINK \l "_Toc196727678" 7.4 Lordonnancement (le « scheduler ») PAGEREF _Toc196727678 \h 95
HYPERLINK \l "_Toc196727679" 7.4.1 Rappels sur la commutation de contexte PAGEREF _Toc196727679 \h 95
HYPERLINK \l "_Toc196727680" 7.4.2 La politique du « premier arrivé, premier servi » PAGEREF _Toc196727680 \h 96
HYPERLINK \l "_Toc196727681" 7.4.3 La politique par priorité PAGEREF _Toc196727681 \h 96
HYPERLINK \l "_Toc196727682" 7.4.4 La politique du tourniquet (round robin) PAGEREF _Toc196727682 \h 97
HYPERLINK \l "_Toc196727683" 7.4.5 Les politiques dordonnancement sous Linux PAGEREF _Toc196727683 \h 97
HYPERLINK \l "_Toc196727684" 8 Le démarrage dun système Linux PAGEREF _Toc196727684 \h 100
HYPERLINK \l "_Toc196727685" 8.1 Le chargeur de noyau PAGEREF _Toc196727685 \h 100
HYPERLINK \l "_Toc196727686" 8.2 Le processus « init » PAGEREF _Toc196727686 \h 100
HYPERLINK \l "_Toc196727687" 8.3 Les niveaux d'exécution PAGEREF _Toc196727687 \h 102
HYPERLINK \l "_Toc196727688" 8.4 Larborescence des processus PAGEREF _Toc196727688 \h 104
HYPERLINK \l "_Toc196727689" 9 Les signaux PAGEREF _Toc196727689 \h 106
HYPERLINK \l "_Toc196727690" 9.1 Présentation PAGEREF _Toc196727690 \h 106
HYPERLINK \l "_Toc196727691" 9.2 Les signaux classiques PAGEREF _Toc196727691 \h 106
HYPERLINK \l "_Toc196727692" 9.2.1 Lenvoi dun signal PAGEREF _Toc196727692 \h 107
HYPERLINK \l "_Toc196727693" 9.2.2 La prise en compte dun signal PAGEREF _Toc196727693 \h 108
HYPERLINK \l "_Toc196727694" 9.2.3 Signaux et appels système PAGEREF _Toc196727694 \h 109
HYPERLINK \l "_Toc196727695" 9.3 Les routines systèmes liées aux signaux PAGEREF _Toc196727695 \h 110
HYPERLINK \l "_Toc196727696" 9.3.1 Envoyer un signal à un processus PAGEREF _Toc196727696 \h 110
HYPERLINK \l "_Toc196727697" 9.3.2 Bloquer les signaux PAGEREF _Toc196727697 \h 111
HYPERLINK \l "_Toc196727698" 9.3.3 Attacher un handler à un signal PAGEREF _Toc196727698 \h 114
HYPERLINK \l "_Toc196727699" 9.3.4 Traiter les appels systèmes interrompus PAGEREF _Toc196727699 \h 118
HYPERLINK \l "_Toc196727700" 9.3.5 Attendre un signal PAGEREF _Toc196727700 \h 118
HYPERLINK \l "_Toc196727701" 9.3.6 Armer une temporisation PAGEREF _Toc196727701 \h 118
HYPERLINK \l "_Toc196727702" 9.4 Les signaux temps réel PAGEREF _Toc196727702 \h 119
HYPERLINK \l "_Toc196727703" 9.4.1 Présentation PAGEREF _Toc196727703 \h 119
HYPERLINK \l "_Toc196727704" 9.4.2 Envoyer un signal temps réel PAGEREF _Toc196727704 \h 120
HYPERLINK \l "_Toc196727705" 9.4.3 Attacher un handler à un signal temps réel PAGEREF _Toc196727705 \h 121
HYPERLINK \l "_Toc196727706" 9.4.4 Exécution du gestionnaire de signal PAGEREF _Toc196727706 \h 122
HYPERLINK \l "_Toc196727707" 9.4.5 Complément sur les signaux temps-réels PAGEREF _Toc196727707 \h 123
HYPERLINK \l "_Toc196727708" 10 Communication centralisée inter-processus PAGEREF _Toc196727708 \h 125
HYPERLINK \l "_Toc196727709" 10.1 Les tubes (pipes) PAGEREF _Toc196727709 \h 125
HYPERLINK \l "_Toc196727710" 10.1.1 Les tubes anonymes PAGEREF _Toc196727710 \h 125
HYPERLINK \l "_Toc196727711" 10.1.2 Les tubes nommés PAGEREF _Toc196727711 \h 131
HYPERLINK \l "_Toc196727712" 10.2 Caractéristiques communes aux IPCs PAGEREF _Toc196727712 \h 138
HYPERLINK \l "_Toc196727713" 10.3 Les files de messages (messages queues/MSQ) PAGEREF _Toc196727713 \h 139
HYPERLINK \l "_Toc196727714" 10.4 Les régions de mémoire partagée PAGEREF _Toc196727714 \h 146
HYPERLINK \l "_Toc196727715" 11 La communication répartie PAGEREF _Toc196727715 \h 155
HYPERLINK \l "_Toc196727716" 11.1 Le modèle client-serveur PAGEREF _Toc196727716 \h 155
HYPERLINK \l "_Toc196727717" 11.2 Quelques rappels réseau PAGEREF _Toc196727717 \h 156
HYPERLINK \l "_Toc196727718" 11.3 Les fonctions et structures propres à TCP/IP PAGEREF _Toc196727718 \h 158
HYPERLINK \l "_Toc196727719" 11.3.1 La normalisation des entiers (endianness) PAGEREF _Toc196727719 \h 158
HYPERLINK \l "_Toc196727720" 11.3.2 La résolution de nom PAGEREF _Toc196727720 \h 159
HYPERLINK \l "_Toc196727721" 11.3.3 La résolution de service PAGEREF _Toc196727721 \h 161
HYPERLINK \l "_Toc196727722" 11.4 La communication par datagrammes PAGEREF _Toc196727722 \h 162
HYPERLINK \l "_Toc196727723" 11.5 La communication en mode connecté PAGEREF _Toc196727723 \h 162
HYPERLINK \l "_Toc196727724" 11.6 Manuel de lAPI des socket PAGEREF _Toc196727724 \h 163
HYPERLINK \l "_Toc196727725" 12 Les problématiques de synchronisation PAGEREF _Toc196727725 \h 177
HYPERLINK \l "_Toc196727726" 12.1 Problématique PAGEREF _Toc196727726 \h 177
HYPERLINK \l "_Toc196727727" 12.2 Lexclusion mutuelle PAGEREF _Toc196727727 \h 177
HYPERLINK \l "_Toc196727728" 12.2.1 Exemple de problématique PAGEREF _Toc196727728 \h 177
HYPERLINK \l "_Toc196727729" 12.2.2 Recherche de solutions à lexclusion mutuelle PAGEREF _Toc196727729 \h 178
HYPERLINK \l "_Toc196727730" 12.3 Lallocation de ressources les sémaphores PAGEREF _Toc196727730 \h 180
HYPERLINK \l "_Toc196727731" 12.3.1 Principe PAGEREF _Toc196727731 \h 180
HYPERLINK \l "_Toc196727732" 12.3.2 Le danger des sémaphores : linterblocage PAGEREF _Toc196727732 \h 182
HYPERLINK \l "_Toc196727733" 12.3.3 Les sémaphores sous Linux PAGEREF _Toc196727733 \h 183
HYPERLINK \l "_Toc196727734" 12.4 Les lecteurs-rédacteurs PAGEREF _Toc196727734 \h 187
HYPERLINK \l "_Toc196727735" 12.4.1 Principe PAGEREF _Toc196727735 \h 187
HYPERLINK \l "_Toc196727736" 12.4.2 Les verrous de fichiers sous Linux PAGEREF _Toc196727736 \h 189
HYPERLINK \l "_Toc196727737" 12.5 Le schéma producteur-consommateur PAGEREF _Toc196727737 \h 190
HYPERLINK \l "_Toc196727738" 12.5.1 Principe et résolution pour 1 producteur et 1 consommateur PAGEREF _Toc196727738 \h 190
HYPERLINK \l "_Toc196727739" 12.5.2 Extension du problème à X producteurs et Y consommateurs PAGEREF _Toc196727739 \h 191
HYPERLINK \l "_Toc196727740" 12.6 Lexclusion mutuelle chez les thread PAGEREF _Toc196727740 \h 192
HYPERLINK \l "_Toc196727741" 12.6.1 Les mutex PAGEREF _Toc196727741 \h 192
HYPERLINK \l "_Toc196727742" 12.6.2 Les variables conditions PAGEREF _Toc196727742 \h 193
HYPERLINK \l "_Toc196727743" 12.7 Autres problématiques dinterblocages PAGEREF _Toc196727743 \h 194
HYPERLINK \l "_Toc196727744" 12.7.1 Le dîner des philosophes PAGEREF _Toc196727744 \h 194
HYPERLINK \l "_Toc196727745" 12.7.2 L'algorithme du banquier PAGEREF _Toc196727745 \h 194
HYPERLINK \l "_Toc196727746" 13 La gestion de la mémoire PAGEREF _Toc196727746 \h 196
HYPERLINK \l "_Toc196727747" 13.1 Rappels PAGEREF _Toc196727747 \h 196
HYPERLINK \l "_Toc196727748" 13.2 Espace dadressage PAGEREF _Toc196727748 \h 196
HYPERLINK \l "_Toc196727749" 13.3 La segmentation PAGEREF _Toc196727749 \h 197
HYPERLINK \l "_Toc196727750" 13.4 La pagination PAGEREF _Toc196727750 \h 198
HYPERLINK \l "_Toc196727751" 13.5 Protection des accès mémoire entre processus PAGEREF _Toc196727751 \h 200
HYPERLINK \l "_Toc196727752" 13.6 La pagination multiniveaux PAGEREF _Toc196727752 \h 201
HYPERLINK \l "_Toc196727753" 13.7 Mémoire virtuelle swap PAGEREF _Toc196727753 \h 202
HYPERLINK \l "_Toc196727754" 13.7.1 Principe PAGEREF _Toc196727754 \h 202
HYPERLINK \l "_Toc196727755" 13.7.2 Lalgorithme optimal PAGEREF _Toc196727755 \h 203
HYPERLINK \l "_Toc196727756" 13.7.3 Lalgorithme FIFO PAGEREF _Toc196727756 \h 203
HYPERLINK \l "_Toc196727757" 13.7.4 Lalgorithme LRU PAGEREF _Toc196727757 \h 203
HYPERLINK \l "_Toc196727758" 13.7.5 Lalgorithme de la seconde chance PAGEREF _Toc196727758 \h 204
HYPERLINK \l "_Toc196727759" 13.7.6 Lalgorithme LFU PAGEREF _Toc196727759 \h 204
HYPERLINK \l "_Toc196727760" 13.7.7 Anomalie de Belady PAGEREF _Toc196727760 \h 204
HYPERLINK \l "_Toc196727761" 13.8 Application : la gestion de mémoire sous Linux PAGEREF _Toc196727761 \h 205
HYPERLINK \l "_Toc196727762" 13.8.1 Les régions PAGEREF _Toc196727762 \h 205
HYPERLINK \l "_Toc196727763" 13.8.2 La gestion de la pagination PAGEREF _Toc196727763 \h 205
HYPERLINK \l "_Toc196727764" 13.8.3 La gestion de lespace dadressage PAGEREF _Toc196727764 \h 206
HYPERLINK \l "_Toc196727765" 13.9 Les algorithmes dallocation mémoire PAGEREF _Toc196727765 \h 209
HYPERLINK \l "_Toc196727766" 13.9.1 Principes généraux PAGEREF _Toc196727766 \h 209
HYPERLINK \l "_Toc196727767" 13.9.2 Implémentation sous Linux PAGEREF _Toc196727767 \h 209
HYPERLINK \l "_Toc196727768" 14 Systèmes de fichiers et implémentation PAGEREF _Toc196727768 \h 211
HYPERLINK \l "_Toc196727769" 14.1 Introduction PAGEREF _Toc196727769 \h 211
HYPERLINK \l "_Toc196727770" 14.2 Le fichier logique PAGEREF _Toc196727770 \h 213
HYPERLINK \l "_Toc196727771" 14.3 Généralités sur la résolution de nom PAGEREF _Toc196727771 \h 213
HYPERLINK \l "_Toc196727772" 14.4 Le fichier physique PAGEREF _Toc196727772 \h 214
HYPERLINK \l "_Toc196727773" 14.4.1 Le disque dur PAGEREF _Toc196727773 \h 214
HYPERLINK \l "_Toc196727774" 14.4.2 Les méthodes dallocation des mémoires secondaires PAGEREF _Toc196727774 \h 215
HYPERLINK \l "_Toc196727775" 14.4.3 La gestion de lespace libre PAGEREF _Toc196727775 \h 216
HYPERLINK \l "_Toc196727776" 14.4.4 Les partitions PAGEREF _Toc196727776 \h 217
HYPERLINK \l "_Toc196727777" 14.4.5 Le montage dune partition PAGEREF _Toc196727777 \h 217
HYPERLINK \l "_Toc196727778" 14.5 Exemple de système de gestion de fichier : ext2 PAGEREF _Toc196727778 \h 218
HYPERLINK \l "_Toc196727779" 14.5.1 La structure di-node PAGEREF _Toc196727779 \h 218
HYPERLINK \l "_Toc196727780" 14.5.2 Les droits classiques sur les fichiers sous Unix/Linux PAGEREF _Toc196727780 \h 219
HYPERLINK \l "_Toc196727781" 14.5.3 Liens physiques et liens symboliques PAGEREF _Toc196727781 \h 220
HYPERLINK \l "_Toc196727782" 14.5.4 Lallocation des blocs de données PAGEREF _Toc196727782 \h 220
HYPERLINK \l "_Toc196727783" 14.5.5 Structure des partitions PAGEREF _Toc196727783 \h 221
HYPERLINK \l "_Toc196727784" 14.6 Le système de gestion de fichiers virtuel VFS PAGEREF _Toc196727784 \h 223
HYPERLINK \l "_Toc196727785" 14.6.1 Introduction PAGEREF _Toc196727785 \h 223
HYPERLINK \l "_Toc196727786" 14.6.2 Structures et fonctionnement de VFS PAGEREF _Toc196727786 \h 223
HYPERLINK \l "_Toc196727787" 14.6.3 Accès à VFS par un processus PAGEREF _Toc196727787 \h 224
HYPERLINK \l "_Toc196727788" 14.6.4 Le fonctionnement du cache des dentry (dcache) PAGEREF _Toc196727788 \h 225
HYPERLINK \l "_Toc196727789" 14.6.5 Le cache des blocs disque (buffer cache) PAGEREF _Toc196727789 \h 226
HYPERLINK \l "_Toc196727790" 14.7 Les opérations sur les fichiers PAGEREF _Toc196727790 \h 227
HYPERLINK \l "_Toc196727791" 14.7.1 Louverture dun fichier PAGEREF _Toc196727791 \h 227
HYPERLINK \l "_Toc196727792" 14.7.2 La fermeture dun fichier PAGEREF _Toc196727792 \h 232
HYPERLINK \l "_Toc196727793" 14.7.3 La lecture et lécriture dans un fichier PAGEREF _Toc196727793 \h 233
HYPERLINK \l "_Toc196727794" 14.7.4 Se positionner dans un fichier PAGEREF _Toc196727794 \h 235
HYPERLINK \l "_Toc196727795" 14.7.5 Manipuler les attributs des fichiers PAGEREF _Toc196727795 \h 236
HYPERLINK \l "_Toc196727796" 14.7.6 Réaliser des opérations sur des fichiers PAGEREF _Toc196727796 \h 239
HYPERLINK \l "_Toc196727797" 14.7.7 Création/suppression de liens PAGEREF _Toc196727797 \h 239
HYPERLINK \l "_Toc196727798" 14.7.8 Modification et tests des droits dun fichier PAGEREF _Toc196727798 \h 240
HYPERLINK \l "_Toc196727799" 14.7.9 Modification du propriétaire dun fichier PAGEREF _Toc196727799 \h 243
HYPERLINK \l "_Toc196727800" 14.8 Les opérations sur les répertoires PAGEREF _Toc196727800 \h 243
HYPERLINK \l "_Toc196727801" 14.8.1 Changer de répertoire courant PAGEREF _Toc196727801 \h 243
HYPERLINK \l "_Toc196727802" 14.8.2 Changer de répertoire racine PAGEREF _Toc196727802 \h 244
HYPERLINK \l "_Toc196727803" 14.8.3 Création dun répertoire PAGEREF _Toc196727803 \h 245
HYPERLINK \l "_Toc196727804" 14.8.4 Destruction dun répertoire PAGEREF _Toc196727804 \h 245
HYPERLINK \l "_Toc196727805" 14.8.5 Exploration dun répertoire PAGEREF _Toc196727805 \h 245
HYPERLINK \l "_Toc196727806" 14.9 Les opérations diverses PAGEREF _Toc196727806 \h 247
HYPERLINK \l "_Toc196727807" 14.9.1 Les opération sur les liens symboliques PAGEREF _Toc196727807 \h 247
HYPERLINK \l "_Toc196727808" 14.9.2 Les opérations sur les partitions PAGEREF _Toc196727808 \h 248
HYPERLINK \l "_Toc196727809" 14.10 Le système de fichier /proc PAGEREF _Toc196727809 \h 252
HYPERLINK \l "_Toc196727810" 15 Les entrées-sorties PAGEREF _Toc196727810 \h 253
HYPERLINK \l "_Toc196727811" 15.1 Principes PAGEREF _Toc196727811 \h 253
HYPERLINK \l "_Toc196727812" 15.1.1 Le contrôleur dentrées-sorties PAGEREF _Toc196727812 \h 253
HYPERLINK \l "_Toc196727813" 15.1.2 Le pilote PAGEREF _Toc196727813 \h 253
HYPERLINK \l "_Toc196727814" 15.1.3 Ordonnancement des requêtes des pilotes PAGEREF _Toc196727814 \h 254
HYPERLINK \l "_Toc196727815" 15.2 Les entrées-sorties sous Linux PAGEREF _Toc196727815 \h 256
HYPERLINK \l "_Toc196727816" 15.2.1 Fichiers spéciaux PAGEREF _Toc196727816 \h 256
HYPERLINK \l "_Toc196727817" 15.2.2 Opérations de contrôle sur un périphérique PAGEREF _Toc196727817 \h 259
HYPERLINK \l "_Toc196727818" 15.2.3 Multiplexage des entrées-sorties PAGEREF _Toc196727818 \h 259
Programme officiel
Public concerné et conditions daccès
Avoir des bases sur le fonctionnement des systèmes d'exploitation (cette UE intervient dans des diplômes et certifications de niveau supérieur à Bac + 2).
Finalités de lunité denseignement
Objectifs pédagogiques
Approches qualitative et quantitative des systèmes d'exploitation et de communication. Conception et fonctionnement des systèmes d'exploitation centralisés et répartis, spécificités des systèmes temps réels. Introduction à la programmation système.
Exemples dans les systèmes UNIX, LINUX et LINUX-RT
Capacité et compétences acquises
Savoir développer une application multi-processus utilisant des outils de communication et de synchronisation en C sous Linux/Unix.
Appréhender les mécanismes fondamentaux des systèmes d'exploitationComprendre la problématique des systèmes temps réels et les particularités de ces systèmes
Organisation
Description des heures denseignements
Cours : 60 heures (Nancy : 51 heures).
Modalités de validation
Examen final (pour Nancy : projet = ¼, examen final = ¾, Cf. réforme 2006-2007).
Contenu de la formation
Introduction générale
Structure des systèmes informatiques.
Structure des systèmes d'exploitation.
Spécificités des systèmes temps réel
Gestion de processus
Processus : concepts, opérations sur les processus. Processus coopératifs, threads, communications inter-processus (tubes, files de messages, segments de mémoire partagée).
Ordonnancement de l'unité centrale
Concepts et critères d'ordonnancement.
Ordonnancement temps réel
Synchronisation de processus
Section critique, sémaphores, problèmes classiques.
Interblocage, inversion de priorités
Prévention, détection, correction, héritage de priorités...
Gestion de la mémoire
pagination, segmentation. Mémoire virtuelle.
Systèmes de fichiers
Interfaces des systèmes de fichiers et implémentation.
Systèmes distribués
Structure des réseaux et structure des systèmes répartis. Programmation socket
Exemple d'un système : LINUX, LINUX-RT
Bibliographie
AuteurTitreJoëlle Delacroix*Linux : programmation système et réseau, Dunod 2003Nils SchaeferProgrammation système sous Unix, sN InformatiqueAndrew TanenbaumSystèmes dexploitation, Pearsoneducation 2003Jean-Marie RiffletLa programmation sous Unix - 3ème édition, Ediscience 1993Jean-Marie RiffletLa communication sous Unix - 2ème édition, Ediscience 1994(*) : le livre de Joëlle Delacroix est le seul livre de la bibliographie officielle du CNAM.
Contacts
Coordonnées du secrétariat du responsable national :
Accès 37 0 36Case courrier : 432
Service d'Informatique cycle A - 2 rue Conté - Paris 3e
Tél : 01 40 27 27 02 - Fax : 01 58 80 84 93
Contact : Virginie Moreau et Françoise CarrasseCourriel : HYPERLINK "mailto:sec-cycleA.informatique@cnam.fr" sec-cycleA.informatique@cnam.fr
Coordonnées du responsable de cette formation à NANCY :
M. Emmanuel DESVIGNE
Tel : 06 33 65 13 35
Courriel : HYPERLINK "mailto:emmanuel@desvigne.org" emmanuel@desvigne.org
URL des cours : HYPERLINK "http://cours.desvigne.org/" http://cours.desvigne.org/
Nouveautés à partir de la session 2006-2007
Origine de la réforme
Suite à des discussions avec la CTI (commission des titres de l'ingénieur) et ses équivalents pour la Licence et les titres RNCP, le CNAM doit garantir que les programmes enseignés de partout en France sont identiques. Pour cela, il a été crée un "référentiel de cours" plus efficace que les simples descriptions d'UE en une page auxquelles nous étions habitués.
Un site "http://ne.pleiad.net" regroupe ces infos (à destination des formateurs) pour les 4 cours expérimentés cette année : RSX101, RSX102, NSY103, et NFP107.
Résumé du principe de la réforme
Les formateurs seront invités à déposer/proposer un sujet d'examen. Le coordinateur du cours pour le Nord-Est gèrera une "discussion" visant à faire émerger UN seul sujet pour tout le Nord-Est. Ce sujet est ensuite transmis au Professeur responsable du cours au niveau national (à Paris) qui donne son accord ou refuse le sujet en suggérant des modifications.
Il est demandé aux enseignants de suivre le plan du cours et de participer à la discussion avec les autres enseignants du Nord-Est faisant le même cours que vous au même semestre.
Pour vos cours, le référentiel est maintenant en place. Il va donc être plus facile de travailler dès le début en harmonie avec la réforme. Logiquement ce plan de cours doit être proche des vôtres. Il ne devrait varier que dans la chronologie et l'enveloppe horaire consacrée à chaque partie (représentative des questions qui seront posées et des points associés).
En résumé : le programme est imposé, mais le sujet doit faire l'objet d'une discussion commune.
Plan imposé par cette réforme pour le cours NSY103
Introduction
THEME 1 : Rappels d'architecture machine (interruptions, fonctionnement de caches)
Structure des systèmes d'exploitation. Notions de bases (commutation de contexte, trappes,
appels système)
Gestion de processus
THEME 2 : Processus : concepts, opérations sur les processus.
THEME 3 : Processus Linux : création dun processus, recouvrement de code, fin de
processus, états et structure dun processus Linux. (fork, exec, wait, exit.)
THEME 4 : Concepts et critères d'ordonnancement de lunité centrale. Algorithmes usuels.
Notion de préemption. Ordonnancement sous Linux. Fonctionnement des signaux.
Communication entre processus
THEME 5 : Communication centralisée : outils Linux (tubes anonymes, files de messages)
THEME 6 : Communication répartie : les sockets
THEME 7 : Les schémas de synchronisation : exclusion mutuelle,
producteurs/consommateurs, sémaphores.
Gestion de la mémoire
THEME 7 : Pagination. Mémoire virtuelle. Segments de mémoire partagé sous Linux.
Systèmes de fichiers
THEME 8 : Interfaces des systèmes de fichiers et implémentation. Allocation du support de
masse. Notions de répertoires, de partition. Gestion des accès disque (politique
dordonnancement du bras)
THEME 9 : Systèmes de gestion de fichiers sous Linux (inode, structure dun fichier Linux,
structure dune partition Linux, commandes Linux liées à la gestion de fichiers)
THEME 10 : Révision
Bibliographie
Joëlle Delacroix Linux : programmation système et réseau, Dunod 2003
Référentiel dévaluation : Lévaluation de première et deuxième session est axée autour :
1/ dun projet de mise en uvre des outils de communication est donné à réaliser aux
auditeurs. Ce projet conduit à la spécification et programmation dune application
multiprocessus simple communicant via les outils étudiés (tubes, MSQ, sockets, etc
).
Ce projet est obligatoire ; il compte pour un quart de la note finale de première et deuxième
session.
2/ dun examen écrit comptant pour ¾ de la note finale.Mise à niveau en C/C++
La majorité des systèmes dexploitation modernes sont écrits dans le langage C et/ou en C++. Les travaux pratiques/travaux dirigés de ce cours demanderont à connaître ces langages. Il serait irraisonnable despérer obtenir ce module NSY103 en faisant limpasse de la maîtrise du C (et davoir quelques notions de C++).
Aussi, ce chapitre doit permettre à chacun de voir ou de revoir les principes et la syntaxe de ces langages.
Bref historique du C
Le C est un langage procédural conçu en 1972 par Dennis Richie et Ken Thompson, chercheurs aux Bell Labs, afin de développer un système d'exploitation : UNIX sur un DEC PDP-11.
En 1978, Brian Kernighan et Dennis Richie publient la définition classique du C dans le livre « The C Programming language ». Le C devenant de plus en plus populaire dans les années 80, plusieurs groupes mirent sur le marché des compilateurs comportant des extensions particulières.
En 1983, l'ANSI (American National Standards Institute) décida de normaliser le langage ; ce travail s'acheva en 1989 par la définition de la norme ANSI C. Celle-ci fut reprise telle quelle par l'ISO (International Standards Organization) en 1990.
La compilation
Le C est un langage compilé : le code (compréhensible par un être humain) doit être passé dans une moulinette (le compilateur) qui transformera ce code source en code exécutable directement par le microprocesseur (nous y reviendrons, cest justement un point important de ce cour). Classiquement, la compilation se décompose en fait en 4 phases successives :
Le traitement par le préprocesseur (preprocessing) : le fichier source est analysé par le « préprocesseur » qui effectue des transformations purement textuelles (remplacement de chaînes de caractères, inclusion d'autres fichiers sources ...). Le résultat de ce prétraitement est toujours du C ;
La compilation : la compilation traduit le texte généré par le préprocesseur en assembleur, c'est-à-dire en une suite d'instructions du microprocesseur qui utilisent des « mnémoniques » rendant la lecture possible par un être humain ;
L'assemblage : cette opération transforme le code assembleur en un fichier binaire, c'est-à-dire en instructions directement compréhensibles par le processeur. Généralement, la compilation et l'assemblage se font dans la foulée, sauf si l'on spécifie explicitement que l'on veut le code assembleur. Le fichier produit par l'assemblage est appelé « fichier objet » ;
L'édition de liens : un programme est souvent séparé en plusieurs fichiers source, pour des raisons de clarté mais aussi parce qu'il fait généralement appel à des librairies de fonctions standard déjà écrites. Une fois chaque code source assemblé, il faut donc lier entre eux les différents fichiers objets. L'édition de liens produit alors un fichier dit exécutable.
Par convention, les différents types de fichiers utilisés lors de la compilation sont distingués par leur suffixe. Les fichiers source sont suffixés par .c, les fichiers prétraités par le préprocesseur par .i, les fichiers assembleur par .s, et les fichiers objet par .o. Les fichiers objets correspondant aux bibliothèques pré-compilées ont pour suffixe « .a ». Enfin, sous Unix/Linux, les exécutables produits nont pas de suffixe (« .com » ou « .exe » sous Windows).
Remarque importante (sous réserve de se faire taper sur les doigts par les puristes) : afin de ne pas réinventer la roue à chaque projet, certaines fonctions et routines sont compilées en fichiers objets (extension « .o »), puis classées dans des fichiers darchives (extension « .a ») appelés « bibliothèques » en français (libraries en anglais). Il est interdit de traduire le mot anglais « library » en « librairie », mais bien en « bibliothèque ».
A noter quil existe une version moderne des bibliothèques : classiquement, lors de lédition de liens, toutes les fonctions et routines utilisées par un programme étaient ajoutées à lintérieur même de du fichier exécutable. Ainsi, si 10 programmes qui utilisent la même bibliothèque étaient exécutés en parallèle, chaque programme chargé en mémoire contient le même bout de code (ce qui prend inutilement de la place). Aujourdhui, les fonctions qui sont mutualisées sont rangées dans des « bibliothèque dynamiques partagées ». On parlera de « shared library » sous Unix/Linux (suffixe « .so ») ou de « dynamically linked library » (suffixe « .dll ») sous Windows.
Classiquement, le compilateur C sous UNIX s'appelle cc. Il existe des alternatives, comme le compilateur du projet GNU : gcc. Ce compilateur peut-être obtenu gratuitement avec sa documentation et ses sources. Par défaut, gcc active toutes les étapes de la compilation. On le lance par la commande
gcc [options] fichier.c [-llibrairies]
Par défaut, le fichier exécutable s'appelle a.out. Le nom de l'exécutable peut être modifié à l'aide de l'option -o.
De façon classique (sans lutilisation de bibliothèque dynamique partagée), les éventuelles bibliothèques sont déclarées par loption -lbibliothèque. Dans ce cas, le système recherche le fichier bibliothèque.a dans le répertoire contenant les bibliothèques pré-compilées (généralement /usr/lib/ sous Unix/Linux). Par exemple, pour lier le programme avec la librairie mathématique, on spécifie -lm. Le fichier objet correspondant est libm.a. Lorsque les librairies pré-compilées ne se trouvent pas dans le répertoire usuel, on spécifie leur chemin d'accès par l'option -L.
Les options les plus importantes du compilateur gcc sont les suivantes :
-c : supprime l'édition de liens ; produit un fichier objet ;
-E : n'active que le préprocesseur (le résultat est envoyé sur la sortie standard) ;
-g : produit des informations symboliques nécessaires au débogueur ;
-Inom-de-répertoire : spécifie le répertoire dans lequel doivent être recherchés les fichiers en-têtes à inclure (en plus du répertoire courant) ;
-Lnom-de-répertoire : spécifie le répertoire dans lequel doivent être recherchées les librairies précompilées (en plus du répertoire usuel) ;
-o nom-de-fichier : spécifie le nom du fichier produit. Par défaut, le fichier exécutable fichier produit s'appelle « a.out ».
-O, -O1, -O2, -O3 : options d'optimisations. Sans ces options, le but du compilateur est de minimiser le coût de la compilation. En rajoutant l'une de ces options, le compilateur tente de réduire la taille du code exécutable et le temps d'exécution. Les options correspondent à différents niveaux d'optimisation : -O1 (similaire à -O) correspond à une faible optimisation, -O3 à l'optimisation maximale ;
-S : n'active que le préprocesseur et le compilateur ; produit un fichier assembleur ;
-v : imprime la liste des commandes exécutées par les différentes étapes de la compilation ;
-W : imprime des messages d'avertissement (warning) supplémentaires ;
-Wall : imprime tous les messages d'avertissement.
Les composants élémentaires du C
Un programme en langage C est constitué des six groupes de composants élémentaires suivants :
les identificateurs,
les mots-clefs,
les constantes,
les chaînes de caractères,
les opérateurs,
les signes de ponctuation.
On peut ajouter à ces six groupes les commentaires, qui sont enlevés par le préprocesseur.
Les identificateurs
Le rôle d'un identificateur est de donner un nom à une entité du programme. Plus précisément, un identificateur peut désigner :
un nom de variable ou de fonction,
un type défini par typedef, struct, union ou enum,
une étiquette (ou label).
Un identificateur est une suite de caractères parmi :
les lettres (minuscules ou majuscules, mais non accentuées),
les chiffres (sauf pour le premier caractère),
le « blanc souligné » ou « underscore » : « _ ».
! Le langage C est « case sensitive » (tient compte des majuscules/minuscules).
Exemples : var1, type_2 ou _deb sont des identificateurs valides.
Remarque : Il est déconseillé d'utiliser le underscore « _ » comme premier caractère d'un identificateur. En effet, par convention, il est souvent employé pour définir les variables globales de l'environnement C (prédéfinies par le compilateur).
Si la norme nimpose rien, pour éviter des surprises avec certains compilateurs, il est conseillé déviter de créer des identificateurs de plus de 31 caractères.
Les mots-clefs
Un certain nombre de mots, appelés mots-clefs, sont réservés pour le langage lui-même et ne peuvent pas être utilisés comme identificateurs. L'ANSI C compte 32 mots clefs :
autobreakcasecharconstcontinuedefaultdodoubleelseenumexternfloatforgotoifintlongregisterreturnshortsignedsizeofstaticstructswitchtypedefunionunsignedvoidvolatilewhileque l'on peut ranger en catégories :
les spécificateurs de stockage : auto, register, static, extern, typedef ;
les spécificateurs de type : char, double, enum, float, int, long, short, signed, struct, union, unsigned, void ;
les qualificateurs de type : const, volatile ;
les instructions de contrôle : break, case, continue, default, do, else, for, goto, if, switch, while ;
divers : return, sizeof.
Les commentaires
Un commentaire débute par /* et se termine par */. Par exemple :
/* Ceci est un commentaire */
On ne peut pas imbriquer des commentaires. Les compilateurs acceptent de plus en plus souvent les commentaires à la façon C++ : le commentaire commence par un double « / », et se continue jusquà la fin de la ligne. Exemple :
Ceci nest pas un commentaire ; // Ceci est un commentaire
Structure d'un programme C
Une expression est une suite de composants élémentaires syntaxiquement correcte, par exemple :
x = y + 4
ou bien
(i >= 0) && (i < 10) || (p[i] != 0)
Une instruction est une expression suivie d'un point-virgule. Le point-virgule est donc le « séparateur dinstruction » ; il signifie en quelque sorte « évaluer cette expression ».
Plusieurs instructions peuvent être rassemblées par des accolades { et } pour former une instruction composée ou bloc qui est syntaxiquement équivalent à une instruction (le « { » signifie « début de bloc », ou « begin » dans dautres langages comme le Pascal), et « } » signifie « fin de bloc » - le « end » - dans certains langages). Par exemple :
if (x != 0)
{
z = y / x;
t = y % x;
}
Une instruction composée d'un spécificateur de type et dun identificateur ou d'une liste d'identificateurs séparés par une virgule est une déclaration. Par exemple :
int a;
int b = 1, c;
double x = 2.38e4;
La déclaration dun tableau se fait avec les accolades. Exemple :
int b[10] ;
/* déclare un tableau b de 10 entiers. Le premier élément du tableau sera b[0], et le 10ième et dernier sera b[9] */
Remarque : en C, nous ne pouvons définir que des tableaux de taille connue lors de la compilation. Par exemple, le code suivant est interdit :
int a=f() ; /* la variable a est initialisée avec le résultat de lappel à la fonction f() */
int b[a] ; /* à la compilation, la valeur de « a » est inconnue ; cette ligne engendrera une erreur de la part du compilateur */
/* Par contre, la ligne suivante est correcte : */
int c[4*4+1] ;
Important : en C, toute variable doit faire l'objet d'une déclaration avant d'être utilisée.
Typiquement, un programme C se présente de la façon suivante :
[directives au préprocesseur]
[déclarations de variables externes]
[fonctions secondaires]
main()
{
déclarations de variables internes
instructions
}
Les fonctions secondaires peuvent être placées indifféremment avant ou après la fonction principale main(). Si elle nest pas définie, il est fortement conseillé quune fonction soit déclarée au moment où elle est utilisée. Une fonction secondaire peut sécrire de la manière suivante :
type nom_de_ma_fonction (arguments)
{
déclarations de variables internes
instructions
}
Ainsi, le code suivant est correct :
void i()
{
printf("bonjour.\n") ;
}
main ()
{
i() ; /* ceci est un appel à la fonction i() */
}
Par contre, le code suivant nest pas propre :
main ()
{
i() ; /* ceci nest pas propre : on appelle la fonction i(), alors quà ce stade, on ne sait pas quels sont les arguments acceptés, ni le type retourné. Ces informations ne seront connues quaprès... */
}
void i()
{
printf("bonjour.\n") ;
}
Pour faire propre, il faut déclarer la fonction i() avant quelle soit utilisée. Exemple :
/* déclaration de la fonction i() : */
void i(); /* ceci indique au compilateur les arguments et le type retourné par la fonction i(), sans préciser son contenu */
main ()
{
i() ; /* ici, i() est connue */
}
void i()
{
printf("bonjour.\n") ;
}
La déclaration des arguments dune fonction obéit à une syntaxe voisine de celle des déclarations de variables : on met en argument de la fonction une suite d'expressions type objet séparées par des virgules. Par exemple :
int somme(int a, int b)
{
int resultat;
resultat = a * b;
return(resultat);
}
Remarque : la déclaration ci-dessus est moderne. Historiquement, Richie et Thompson utilisaient une autre syntaxe, toujours reconnue par les compilateurs, mais moins propre :
int somme(a, b)
int a;
int b;
{
int resultat;
resultat = a * b;
return(resultat);
}
Les types
Les types prédéfinis
Le C est un langage « typé » : toute variable, constante ou fonction est d'un type précis. Le type d'un objet définit la façon dont il est représenté en mémoire.
Les types de base en C concernent les caractères, les entiers et les flottants (nombres réels). Ils sont désignés par les mots-clefs suivants :
char (un octet : représente un caractère suivant son code ASCII),
int (un entier ; sa taille dépend de la machine sur laquelle le code est compilé : 16 bits, 32 bits, 64 bits
),
float (nombre en virgule flottante représenté sur 32 bits suivant le codage de lIEEE),
double (nombre en virgule flottante représenté sur 64 bits suivant le codage de lIEEE),
short (demi entier ; « short » employé seul est équivalent à « short int »),
long (double le nombre de bit du type int ou double qui suit ; employé seul, il signifie « long int »),
unsigned (par défaut, un type entier ou flottant est signé, sauf sil est précédé du mot clé unsigned),
signed (précise - bien que ce soit le cas par défaut que le type qui suit est signé),
void (type vide) : il sagit dun type très particulier, qui signifie « pas de type ». Cest principalement utilisé pour indiquer quune fonction ne retourne aucune valeur (cest ainsi quen C, nous définissons une procédure : la notion de procédure nexistant pas, nous définissons une fonction qui retourne du vide).
Exemple de procédure en C :
void f(int a, int b)
{
int i = a + b ;
g(i);
/* ici, il ny a aucune instruction return(valeur) */
}
Pour savoir le nombre doctet utilisé en mémoire pour stocker un type, il faut utiliser le mot clé prédéfini « sizeof() ». Exemple : sizeof(int).
Remarque : en C, le type booléen nexiste pas. On utilise intrinsèquement le type int.
Les types composés
Voici les différents types composés en C :
Nous avons précédemment vu les tableaux. Exemple : float b[5] ;Nous pouvons composer les symboles [] afin de définir des tableaux de tableau, des tableaux de tableaux de tableau, etc. Par exemple, pour définir une matrice n de 10x10 nombres à virgule flottante, nous pouvons utiliser :
double n[10][10] ;
Dans cet exemple, n[4] est un tableau de 10 double.
Une structure est une suite finie d'objets de types différents. Contrairement aux tableaux, les différents éléments d'une structure n'occupent pas nécessairement des zones contiguës en mémoire. Chaque élément de la structure, appelé membre ou champ, est désigné par un identificateur.On distingue la déclaration d'un modèle de structure de celle d'un objet de type structure correspondant à un modèle donné. La déclaration d'un modèle de structure dont l'identificateur est modele_de_struct suit la syntaxe suivante :
struct modele_de_struct{
type1 membre1; type2 membre2; ... typeN membreN; };
/* une variable de type modele_de_struct se déclare ainsi : */
struct modele_de_struct var1 ;
/* on accède aux champs de var1 ainsi : */
var1.membre1=blablabla ;
var1.membre2=blablabla ;
Une union désigne un ensemble de variables de types différents susceptibles d'occuper alternativement une même zone mémoire. Une union permet donc de définir un objet comme pouvant être d'un type au choix parmi un ensemble fini de types. Si les membres d'une union sont de longueurs différentes, la place réservée en mémoire pour la représenter correspond à la taille du membre le plus grand.Les déclarations et les opérations sur les objets de type union sont les mêmes que celles sur les objets de type struct. Dans l'exemple suivant, la variable hier de type union jour peut être soit un entier, soit un caractère :
union jour
{
char lettre;
int numero;
};
union jour hier;
...
jour.numero=4 ;
/* à ce stade, il serait incohérent (sauf cas particulier) de vouloir utiliser jour.lettre */
Les champs de bits (bitfields) permettent, en C, de spécifier la longueur des champs d'une structure au bit près si ce champ est de type entier (int ou unsigned int). Cela se fait en précisant le nombre de bits du champ avant le ; qui suit sa déclaration. Par exemple, la structure suivante
struct registre
{
unsigned int actif : 1;
unsigned int valeur : 31;
};
possède deux membres : actif qui est codé sur un seul bit, et valeur qui est codé sur 31 bits. Tout objet de type struct registre est donc codé sur 32 bits. Toutefois, l'ordre dans lequel les champs sont placés à l'intérieur de ce mot de 32 bits dépend de l'implémentation. Le champ actif de la structure ne peut prendre que les valeurs 0 et 1. Aussi, si r est un objet de type struct registre, l'opération « r.actif += 2; » ne modifie pas la valeur du champ. Remarques : la taille totale d'un champ de bits doit être inférieure au nombre de bits d'un entier. De plus, un champ de bits n'a pas d'adresse ; on ne peut donc pas lui appliquer l'opérateur « & » ;
Les énumérations permettent de définir un type par la liste des valeurs qu'il peut prendre. Un objet de type énumération est défini par le mot-clef enum et un identificateur de modèle, suivis de la liste des valeurs que peut prendre cet objet. Exemple :
enum modele { constante1, constante2, ...,constanteN };
En réalité, les objets de type enum sont représentés comme des int. Les valeurs possibles constante1, constante2,... ,constanteN sont codées par des entiers de 0 à N-1. De plus, on peut modifier le codage par défaut des valeurs de la liste lors de la déclaration du type énuméré, par exemple : enum booleen { faux = 0, vrai = 23 };
Enfin, pour alléger l'écriture des programmes, il est possible de définir des types composés avec typedef. La syntaxe est : typedef type synonyme ;
Par exemple :
struct complexe_struct
{
double reelle;
double imaginaire;
};
typedef struct complexe_struct complexe;
main()
{
complexe z;
z.reelle=z.imaginaire=0 ;
...
}
Les constantes
Une constante est une valeur qui apparaît littéralement dans le code source d'un programme. Le type de la constante étant déterminé par la façon dont la constante est écrite. Les constantes peuvent être de 4 types : entier, flottant (nombre réel), caractère, ou énumération. Ces constantes vont être utilisées, par exemple, pour initialiser une variable.
Les constantes entières
Une constante entière peut être représentée de 3 manières différentes suivant la base dans laquelle elle est écrite :
décimale : par exemple, -10, 0 et 2437348 sont des constantes entières décimales ;
octale : la représentation octale d'un entier correspond à sa décomposition en base 8. Les constantes octales doivent commencer par un zéro. Par exemple, les représentations octales des entiers 0 et 255 sont respectivement 00 et 0377 ;
hexadécimale : la représentation hexadécimale d'un entier correspond à sa décomposition en base 16. Les lettres de a à f sont utilisées pour représenter les nombres de 10 à 15. Les constantes hexadécimales doivent commencer par 0x ou 0X. Par exemple, les représentations hexadécimales de 14 et 255 sont respectivement 0xe et 0xff.
Par défaut, une constante décimale est représentée avec le format interne le plus court permettant de la représenter parmi les formats des types int, long int et unsigned long int tandis qu'une constante octale ou hexadécimale est représentée avec le format interne le plus court permettant encore de la représenter parmi les formats des types int, unsigned int, long int et unsigned long int.
On peut cependant spécifier explicitement le format d'une constante entière en la suffixant par u ou U pour indiquer qu'elle est non signée, ou en la suffixant par l ou L pour indiquer qu'elle est de type long. Par exemple :
ConstanteType123456int02311int /* octal */0x04d2int /* hexadécimal */123456789Llong1234Uunsigned int123456789ULunsigned long intLes constantes réelles
Les constantes réelles sont représentées par la notation classique par mantisse et exposant. L'exposant est introduit par la lettre e ou E ; il s'agit d'un nombre décimal éventuellement signé.
Par défaut, une constante réelle est représentée avec le format du type double. On peut cependant influer sur la représentation interne de la constante en lui ajoutant un des suffixes f (indifféremment F) pour forcer le type float, ou l (indifféremment L) pour forcer le type long double. Par exemple :
ConstanteType12.34double12.3e-4double12.34Ffloat12.34Llong doubleLes constantes caractères
Pour désigner un caractère imprimable, il suffit de le mettre entre apostrophes (par ex. 'A' ou '$').
Les seuls caractères imprimables qu'on ne peut pas représenter de cette façon sont l'antislash (« \ ») et l'apostrophe (« ' »), qui sont respectivement désignés par « \\ » et « \' ». Le point d'interrogation et les guillemets peuvent aussi être désignés par les notations « \? » et « \" ». Les caractères non imprimables peuvent être désignés par '\code-octal' où code-octal est le code en octal du caractère. On peut aussi écrire '\xcode-hexa' où code-hexa est le code en hexadécimal du caractère. Par exemple, '\33' et '\x1b' désignent le caractère escape. Toutefois, les caractères non-imprimables les plus fréquents disposent aussi d'une notation plus simple :
CaractèreValeur'\n'nouvelle ligne'\r'retour chariot'\t'tabulation horizontale'\f'saut de page'\v'tabulation verticale'\a'signal d'alerte'\b'retour arrièreLes opérateurs
L'affectation
En C, l'affectation est un opérateur à part entière. Elle est symbolisée par le signe « = ». Sa syntaxe est la suivante : variable = expression
Le terme de gauche de l'affectation peut être une variable simple, un élément de tableau mais pas une constante. Cette expression a pour effet d'évaluer expression et d'affecter la valeur obtenue à variable. Remarque importante : cette expression « variable = expression » possède elle même une valeur, qui est celle de expression. Ainsi, l'expression « i = 5 » vaut 5. Cette subtilité permet des écritures du style :
i = j = 20 + 4 ;
Dans ce cas, lexpression de droite est évaluée (20 + 4 vaut 24), et le résultat est affecté à la variable j. Puis, le résultat de « j = 20 + 4 », cest à dire 24, est affecté à la variable i.
L'affectation effectue une conversion de type implicite : la valeur de l'expression (terme de droite) est convertie dans le type du terme de gauche. Par exemple, le programme suivant :
main()
{
int i;
int j = 2;
float x = 2.5;
i = j + x; /* i vaut 2 + 2 = 4 */
x = x + i; /* x vaut 2.5 + 4 */
/* à ce stade, x vaut 6.5 */
}
Les opérateurs arithmétiques
Les opérateurs arithmétiques classiques sont l'opérateur unaire moins « - » (changement de signe) ainsi que les opérateurs binaires :
+addition-soustraction*multiplication/division%reste de la division (modulo)Ces opérateurs agissent de la façon attendue sur les entiers comme sur les flottants. Leurs seules spécificités sont les suivantes :
Contrairement à d'autres langages, le C ne dispose que de la notation / pour désigner à la fois la division entière et la division entre flottants. Si les deux opérandes sont de type entier, l'opérateur / produira une division entière (quotient de la division). Par contre, il délivrera une valeur flottante dès que l'un des opérandes est un flottant. Par exemple :
float x;
x = 3 / 2; /* ici, x vaut 1 */
x = 3 / 2.0; /* ici, x vaut 1.5 */
L'opérateur % ne s'applique qu'à des opérandes de type entier. Si l'un des deux opérandes est négatif, le signe du reste dépend de l'implémentation, mais il est en général le même que celui du dividende.
Notons enfin qu'il n'y a pas en C d'opérateur effectuant l'élévation à la puissance. Il faut utiliser des fonctions prédéfinies dans certaines bibliothèques pour réaliser cette opération.
Les opérateurs relationnels
Leur syntaxe est expression1 op expression2 avec op parmi :
>strictement supérieur>=supérieur ou égal » est une abréviation qui permet daccéder aux champs dune variable composée (i.e. de type struct ou union) à travers son pointeur. Exemple :
typedef struct { double im ; double re ; } complexe ;
complexe z ;
complexe *ptrz = &z ; /* définition de ptrz comme pointeur vers un complexe, et on linitialise en le faisant pointer vers la variable z */
ptrz->im = ptrz->re = 1.0 ;
/* la ligne précédente équivaut à écrire : (*ptrz).im = (*ptrz).re = 1.0 ; */
Attention !!! Larithmétique des pointeurs est particulière. En effet, si p est un pointeur qui pointe vers une variable de type t, « p++ » revient en réalité à ajouter à p le nombre doctets pris en mémoire par un objet de type t (i.e. sizeof(t) ). Exemple :
double t[2] ;
double *p = &t[0] ; /* p est défini comme pointeur sur un double, et est initialisé pour pointer sur t */
*p=1.0 ; /* équivaut à t[0]=1.0 */
p++ ; /* p ne pointe pas vers loctet suivant en mémoire, mais vers lobjet de type double suivant */
p=4.0 ; /* équivaut à t[1]=4.0 */
Règles de priorité des opérateurs
Le tableau suivant classe les opérateurs par ordres de priorité décroissants. Les opérateurs placés sur une même ligne ont même priorité. Si dans une expression figurent plusieurs opérateurs de même priorité, l'ordre d'évaluation est définie par la flèche de la seconde colonne du tableau. On préférera toutefois mettre des parenthèses en cas de doute... :
() [] -> .(! ~ ++ -- -(unaire) (type) *(indirection) &(adresse) sizeof()(* / %(+ -(binaire)(>(< >=(== !=(&(et bit-à-bit)(^(|(ou bit-à-bit)(&&(||(? :(= += -= *= /= %= &= ^= |= =(,(Les constantes chaînes de caractères
Une constante chaîne de caractères est une suite de caractères entourés par des guillemets « " ». Par exemple :
"Ceci est une chaîne de caractères"
Une chaîne de caractères peut contenir des caractères non imprimables, désignés par les représentations vues précédemment. Par exemple :
"ligne 1 \n ligne 2"
A l'intérieur d'une chaîne de caractères, le caractère « " » doit être désigné par \". Enfin, le caractère \ suivi d'un passage à la ligne est ignoré. Cela permet de faire tenir de longues chaînes de caractères sur plusieurs lignes. Par exemple :
"ceci est une longue longue longue longue longue longue \
longue longue chaîne de caractères"
Attention !!! Encore un piège du C : en C, le type « chaîne de caractères » nexiste pas. Le C utilise des tableaux de caractères pour stocker une chaîne. En mémoire, le caractère nul « \0 » permet de terminer une chaîne de caractères. Par exemple, la chaîne "ABC" prendra 4 octets en mémoire : le 65 (code ASCII du 'A'), 66 (code ASCII du 'B'), 67 (code ASCII du 'C'), puis '\0'. Lorsque nous affectons une chaîne de caractères à une constante, il est inutile de compter combien il y a de caractères dedans :
char str[] = "ABC" ;
Avec ce que nous avons vu dans le chapitre sur les pointeurs, nous savons maintenant que nous pouvons écrire aussi :
char *str = "ABC" ;
Les instructions de branchement conditionnel
On appelle instruction de contrôle toute instruction qui permet de contrôler le fonctionnement d'un programme. Parmi les instructions de contrôle, on distingue les instructions de branchement et les boucles. Les instructions de branchement permettent de déterminer quelles instructions seront exécutées et dans quel ordre.
Branchement conditionnel if... else
La forme la plus générale est celle-ci :
if (expression)
instruction_executée_si_expression_est_vraie
else
instruction_executée_si_expression_est_fausse
La clause « else instruction_executée_si_expression_est_fausse » est optionnelle.
Le code suivant :
if (expression1)
instruction1
else if (expression2)
instruction2
else
instruction3
est équivalent à :
if (expression1)
instruction1
else
{
if (expression2)
instruction2
else
instruction3
}
Autrement dit, instruction3 fait référence au dernier else, cest à dire au deuxième if.
Branchement multiple switch
Sa forme la plus générale est celle-ci :
switch (expression)
{
case constante1 :
liste d'instructions 1
break;
case constante2 :
liste d'instructions 2
break;
...
case constanteN :
liste d'instructions N
break;
default:
liste d'instructions si aucun cas rencontré
break; /* ce dernier break est optionnel */
}
Si la valeur de expression est égale à l'une des constantes, la liste d'instructions correspondant est exécutée. Sinon la liste d'instructions « si aucun cas rencontré » correspondant à « default » est exécutée. L'instruction « default » est facultative.
Remarque importante : si on omet un « break », les instructions correspondant aux cas suivants seront aussi exécutées. Exemple :
switch (i)
{
case 0 :
liste d'instructions exécutées si i == 0 ;
break;
case 1 :
liste d'instructions exécutées si i == 1 ;
case 2 :
liste d'instructions exécutées si i==1 ou i==2 ;
break ;
default:
liste d'instructions si i différent de 0,1 et 2 ;
}
Les boucles
Les boucles permettent de répéter une série d'instructions tant qu'une certaine condition n'est pas vérifiée.
Boucle while
La syntaxe de while est la suivante :
while (expression)
instruction
Lexpression expression est tout dabord évaluée une première fois. Si elle est vraie, instruction est effectuée. Puis, expression est de nouveau évaluée, etc. Exemple :
i = 1;
while (i < 10)
{
g(i);
i++;
}
Boucle do... while
Il peut arriver que l'on ne veuille effectuer le test de continuation qu'après avoir exécuté l'instruction. Dans ce cas, on utilise la boucle do... while. Sa syntaxe est :
do
instruction
while (expression);
Ici, instruction sera toujours exécutée au moins une fois. La boucle continuera tant que expression est non nulle. Exemple :
int a=0;
do
{
a=f(); /* sera toujours effectué */
} while (a > 0) && (a y ? x : y) ».
Attention, ici aussi, pour éviter les effets de bors, comme a et b peuvent être nimporte quelle expression complexe, il vaut mieux parenthéser. La bonne définition de la macro, qui évite tout effet de bord, est :
#define MAX(a,b) ((a) > (b) ? (a) : (b))
Une macro a donc une syntaxe similaire à celle d'une fonction, mais son emploi permet en général d'obtenir de meilleures performances en temps d'exécution (mais pas en place prise par le code en mémoire).
La distinction entre une définition de constante symbolique et celle d'une macro avec paramètres se fait sur le caractère qui suit immédiatement le nom de la macro : si ce caractère est une parenthèse ouvrante, c'est une macro avec paramètres, sinon c'est une constante symbolique. Il ne faut donc jamais mettre d'espace entre le nom de la macro et la parenthèse ouvrante. Ainsi, si l'on écrit par erreur :
#define CARRE (a) a * a
la chaîne de caractères « CARRE(2) » sera remplacée par
(a) a * a (2)
Ici aussi, pour éviter tout effet de bord avec la priorité des opérateurs, la bonne syntaxe serait :
#define CARRE(a) ( (a) * (a) )
En effet, en C, il nest jamais gênant de surparenthèser. Le code suivant fonctionnera :
int i=((2)*(3)(*(p))); /* notez que p est un pointeur */
La compilation conditionnelle
La compilation conditionnelle a pour but d'incorporer ou d'exclure des parties du code source dans le texte qui sera généré par le préprocesseur. Elle permet d'adapter le programme au matériel ou à l'environnement sur lequel il s'exécute, ou d'introduire dans le programme des instructions de débogage.
Les directives de compilation conditionnelle se répartissent en deux catégories, suivant le type de condition invoquée :
la valeur d'une expression
l'existence ou l'inexistence de symboles.
Exemples :
#if condition1
partie-du-programme-1
#elif condition2
partie-du-programme-2
...
#elif conditionN
partie-du-programmeN
#else
partie-du-programme-defaut
#endif
Le nombre de #elif est quelconque et le #else est facultatif. Chaque conditionX doit être une expression constante.
Une seule « partie-du-programme » sera compilée : celle qui correspond à la première conditionX non nulle, ou bien la partie-du-programme-defaut si toutes les conditions sont nulles.
Par exemple, on peut écrire :
#define PROCESSEUR ALPHA
...
#if PROCESSEUR == ALPHA
taille_long = 64;
#elif PROCESSEUR == PC
taille_long = 32;
#endif
Lautre directive de compilation conditionnelle est un test lié à l'existence d'un symbole. Sa syntaxe est :
#ifdef symbole
partie-du-programme-1
#else
partie-du-programme-2
#endif
Si symbole est défini au moment où l'on rencontre la directive #ifdef, alors partie-duprogramme-1 sera compilée et partie-du-programme-2 sera ignorée. Dans le cas contraire, c'est partie-du-programme-2 qui sera compilée. La directive #else est évidemment facultative.
Da façon similaire, on peut tester la non-existence d'un symbole par : #ifndef symbole
Ce type de directive est utile pour rajouter des instructions destinées au débogage du programme :
#define DEBUG
...
#ifdef DEBUG
code qui affiche le contenu de certaines variables, etc.
#endif /* DEBUG */
Il suffit alors de mettre en commentaire la directive « #define DEBUG » pour que les instructions liées au débogage ne soient pas compilées. Cette dernière directive peut être remplacée par l'option de compilation -Dsymbole, qui permet de définir un symbole lorsquon lance la compilation. Ainsi, « gcc -DDEBUG fichier.c » équivaut à un « gcc fichier.c » avec un fichier « fichier.c » dont la première ligne serait : « #define DEBUG ».
Remarque : ces directives conditionnelles sont très utilisées pour éviter dimporter un fichier plusieurs fois avec la directive « #include ». Exemple dun fichier « test.h » :
#ifndef TEST_H
#define TEST_H
blablabla...
#endif
Ainsi, si dans le blablabla ci-dessus, il venait à y avoir un « #include "fichier2.h" », et que fichier2.h venait à faire un « #include "test.h" », le compilateur ne tournerait pas en boucle.
Les bibliothèques standards
Contrairement à dautres langages, il nexiste pas en C de fonctions prédéfinies pour écrire à lécran, ouvrir/lire/écrire/fermer un fichier, comparer deux chaînes de caractères, trier un tableau dentier, etc.
Par contre, tout compilateur propose des « bibliothèques de fonctions », rangées dans des archives ou bibliothèques dynamiques. Or, si certaines de ces fonctions sont propres à chaque compilateur et/ou à chaque environnement, certaines fonctions sont obligatoires, et inscrites dans la norme ANSI, dans une bibliothèque qui est toujours utilisée lors de la phase dédition de liens durant la compilation, sans que lutilisateur nait besoin de la spécifier explicitement : la bibliothèque libc. Dautres fonctions sont disponibles si votre environnement répond à dautres normes, comme par exemple la norme POSIX. Certaines fonctions de la norme POSIX sont déjà présentes dans la bibliothèque libc. Dautres ont besoin que lutilisateur précise lutilisation de bibliothèques externes particulières lors de la phase dédition de lien, avec loption « -lnom_de_la_bibliothèque » du compilateur.
Exemple : pour afficher une chaîne de caractères "bonjour\n" à lécran, nous pouvons utiliser la fonction standard AINSI « puts() » existant dans la bibliothèque libc.
Or, le compilateur risque de nous afficher une alerte si nous écrivons le code suivant :
char s[]="ceci est un test\n" ;
main()
{
put(s) ;
}
En effet, la fonction puts() est définie nulle part. Par contre, en lisant la documentation de cette fonction puts() (man puts sous Unix/Linux par exemple), nous apprenons que le prototype de la fonction puts() est définie dans le fichier stdio.h. Il suffit donc de commencer notre programme par : #include
Ainsi, nous pourrons utiliser puts() (et beaucoup dautre fonctions, constantes, macos) dont les déclarations se trouvent dans le fichier /usr/include/stdio.h.
Pour les fonctions qui ne font par partie de la bibliothèque standard libc, il faudra certainement fournir loption « -lnom_dune_bibliothèque_externe » au compilateur pour que ce dernier sache où aller chercher les fonctions dont le programme a besoin.
Exemple : il existe une fonction mathématique « double pow(double x, double y); » qui retourne le nombre flottant x à la puissance y. Le manuel de cette fonction nous apprend :
que la définition de cette fonction se trouve dans le fichier math.h. Avant dutiliser cette fonction dans notre programme, il faudra bien penser à faire un : #include
de plus, il faut penser à indiquer au compilateur daller chercher cette fonction dans la bibliothèque des fonctions mathématiques « m », en donnant loption de compilation « -lm ». Exemple : cc test.c o test lm
Sans cette dernière option, nous aurions certainement une erreur comme celle-ci à la compilation :
In function `main':
: undefined reference to `pow'
collect2: ld returned 1 exit status
Les conventions d'écriture d'un programme C
Il existe très peu de contraintes dans l'écriture d'un programme C. Par exemple, en dehors dune composante élémentaire, il est toujours possible dajouter des espaces, des tabulations, des retours à la ligne...
Toutefois ne prendre aucune précaution aboutirait à des programmes illisibles. Aussi existe-t-il un certain nombre de conventions.
on n'écrit qu'une seule instruction par ligne : le point virgule d'une instruction ou d'une déclaration est toujours le dernier caractère de la ligne ;
les instructions sont disposées de telle façon que la structure modulaire du programme soit mise en évidence. En particulier, une accolade ouvrante marquant le début d'un bloc doit être seule sur sa ligne ou placée à la fin d'une ligne. Une accolade fermante est toujours seule sur sa ligne ;
on laisse un blanc :
entre les mots-clefs if, while, do, switch et la parenthèse ouvrante qui suit,
après une virgule,
de part et d'autre d'un opérateur binaire (pas toujours suivi) ;
on ne met pas de blanc entre un opérateur unaire et son opérande, ni entre les deux caractères d'un opérateur d'affectation composée.
les instructions doivent être indentées afin que toutes les instructions d'un même bloc soient alignées.
Le C++
Généralités
Le langage C++ a été conçu par Bjarne Stroustrup, afin dajouter (entre autre) au C la notion de « programmation objet ».
La Programmation Orientée Objet (POO), parfois appelée Programmation Par Objets (PPO). Cette technique permet d'introduire le concept d'« objet », qui consiste en un ensemble de données et de procédures qui agissent sur ces données.
Lorsque l'objet est parfaitement bien écrit, il introduit la notion fondamentale d'« encapsulation des données ». Ceci signifie qu'il n'est plus possible pour l'utilisateur de l'objet, d'accéder directement aux données : il doit passer par des « méthodes » spécifiques écrites par le concepteur de l'objet, et qui servent d'interface entre l'objet et ses utilisateurs. L'intérêt de cette technique est évident. L'utilisateur ne peut pas intervenir directement sur l'objet, ce qui diminue les risques d'erreur, ce dernier devenant une boîte noire.
Une autre notion importante en P.O.O. est l'héritage. Elle permet la définition d'une nouvelle « classedobjet » à partir d'une « classe dobjet » existante. Il est alors possible de lui adjoindre de nouvelles données, de nouvelles fonctions membres (procédures) pour la spécialiser.
Différences entre C et C++
Nous allons parler ici d'un certain nombre de différences existant entre le C et le C++. Nous pourrions d'ailleurs plutôt utiliser le terme d'incompatibilités.
Les fonctions : la définition historique des fonctions nest plus acceptée en C++. La syntaxe :
int calcule_somme(a, b)
int a;
int b;
{
return(a+b) ;
}
sera refusée par le compilateur. En C++, seule la syntaxe suivante reste valide :
int calcule_somme(int a, int b)
{
return(a+b) ;
}
Const : le C++ a quelque peu modifié l'utilisation "C" de ce qualificatif const. Pour rappel, « const » est utilisé pour définir une constante. C'est une bonne alternative à un #define. La portée en C++ est désormais plus locale. En C, un const permettait pour une variable globale d'être visible partout. C++ limite quant à lui la portée d'une telle variable, au fichier source contenant la déclaration ;
Compatibilité de pointeurs : en C ANSI, un pointeur de type « void * » est compatible avec tout autre type de pointeurs, et inversement. Le code suivant est légal en C :
void *p_generique; /* Pointeur générique */
int *p_entier; /* Pointeur sur un entier */
[...]
p_entier = p_generique;
[...]
p_generique = p_entier;
Ces affectations font intervenir des conversions implicites. En C++, seule la conversion int*->void* est implicite. L'autre reste possible, mais nécessite un "cast" :
void *p_generique; /* Pointeur générique */
int *p_entier; /* Pointeur sur un entier */
[...]
p_entier = (int *) p_generique; /* cast obligatoire */
[...]
p_generique = p_entier; /* reste OK */
Nouvelle forme de commentaire : en C++, tout ce qui suit un double slash (« // ») jusquà la fin de la ligne est considéré comme un commentaire ;
Déclaration des variables : en C, les déclarations de variables devaient impérativement être en début de bloc. C++ lève cette obligation. Exemple :
int f(int a, int b)
{
int i ;
i = a + b ;
b++;
int j ; // interdit en C, légal en C++
j = a + b + i ;
return(j) ;
}
Valeur par défaut dun paramètre : il est dorénavant possible de donner une valeur par défaut à un paramètre. Exemple :
// Si aucun paramètre transmis, choisi 1 par défaut.
int double(int a=1)
{
return(2 * a) ;
}
[...]
int i = double(2) ; // i vaut 4 ;
int j = double() ; // j vaut double(1), i.e. : 2
Passage de paramètres par référence : nous avons vu quen C, il était impossible de passer des variables par référence. Si nous voulions quune variable passée en paramètre soit « modifiable », il fallait passer en paramètre non pas la variable elle-même, mais un pointeur sur cette variable. Une nouvelle syntaxe apparaît en C++ pour permettre de passer une variable en paramètre afin quelle puisse être modifiée par la fonction appelée : dans les paramètres, le nom de la variable doit être précédé par le symbole « & ». Exemple :
void double_parametre(int &a)
{
a *= 2 ; /* on modifie le contenu de la variable de la fonction appelante */
}
[...]
int i = 4;
double_parametre(i);
// à ce stade, i vaut 8
Important !!! Evidement, le paramètre passé à une fonction prototypée pour accepter un paramètre par référence doit être une « lvalue » (variable modifiable). En effet, dans lexemple ci-dessus, le code « double_parametre(4); » naurait aucun sens.
Opérateurs new et delete : classiquement, pour allouer de la mémoire afin de stocker des valeurs dun type quelconque, il fallait utiliser les fonctions de la bibliothèque standard malloc() et free(). Le C++ propose un nouveau jeu d'opérateurs d'allocation/désallocation de mémoire : new et delete. Ils ont été créés principalement pour la gestion dynamique des objets, mais on peut les utiliser également pour des variables simples. Exemple :
int *p ; // à ce stade, p pointe on ne sait où...
p = new int ; /* dorénavant, p pointe vers un espace mémoire réservé pour stocker une valeur de type int */
*p = 4 ;
[...]
delete p ; // libère la mémoire réservée par p
Les flux : C++ introduit la notion de « flux » pour gérer les entrées/sorties. Deux opérateurs binaires sont introduits pour gérer les flux : « >> » permet de récupérer de linformation en provenance dun flux, et « suivant = p;
temp_p->valeur_stockee = nouvelle_val;
return(temp_p);
}
int depile(pile **p)
{
pile *temp_p;
int val_ret;
if ( (*p) == PILE_VIDE )
return(0);
temp_p = *p;
val_ret = temp_p->valeur_stockee;
(*p) = (*p)->suivant;
free(temp_p);
return(val_ret);
}
int est_vide(pile *p)
{
return(p == PILE_VIDE);
}
Fichier « main.c » :
#include
#include "pile.h"
int main()
{
pile *p;
p = cree_pile();
printf("Est-ce qu'une pile nouvellement crée est vide : ");
if (est_vide(p))
printf("oui\n");
else
printf("non\n");
printf("J'empile 2\n");
p = empile(p, 2);
printf("J'empile -1\n");
p = empile(p, -1);
printf("J'empile 0\n");
p = empile(p, 0);
printf("Valeur dépilée : %d\n", depile(&p));
printf("Est-ce que la pile est maintenant vide : ");
if (est_vide(p))
printf("oui\n");
else
printf("non\n");
printf("Valeur dépilée : %d\n", depile(&p));
printf("Est-ce que la pile est maintenant vide : ");
if (est_vide(p))
printf("oui\n");
else
printf("non\n");
printf("Valeur dépilée : %d\n", depile(&p));
printf("Est-ce que la pile est maintenant vide : ");
if (est_vide(p))
printf("oui\n");
else
printf("non\n");
detruit_pile(p);
return(0);
}
Compilation et utilisation sous Linux :
$> cc -Wall -O2 pile.c main.c -o test
$> ./test
Est-ce qu'une pile nouvellement crée est vide : oui
J'empile 2
J'empile -1
J'empile 0
Valeur dépilée : 0
Est-ce que la pile est maintenant vide : non
Valeur dépilée : -1
Est-ce que la pile est maintenant vide : non
Valeur dépilée : 2
Est-ce que la pile est maintenant vide : oui
$>
Introduction : architecture des ordinateurs
Schéma de base
Dans sa version moderne, un ordinateur est constitué des éléments suivants :
un ou plusieurs microprocesseurs (CPU) ;
de la mémoire vive (RAM),
des périphériques, qui dialoguent avec le CPU et la RAM via des « contrôleurs de périphérique ».
Le dialogue entre ces différents éléments se fait via des « bus » (bus = canal de communication entre plusieurs composants). Comme il existe plusieurs type de bus (PCI, ISA, USB, etc.), linterconnexion entre bus se fait à travers des « ponts ». Aujourdhui, ces ponts sont implémentés dans un « chipset ».
Le microprocesseur (CPU)
Présentation
Le processeur (CPU, pour Central Processing Unit, soit Unité Centrale de Traitement) est le cerveau de l'ordinateur. Il permet de manipuler des informations numériques, c'est-à-dire des informations codées sous forme binaire, et d'exécuter les instructions stockées en mémoire.
Le premier microprocesseur (Intel 4004) a été inventé en 1971. Il s'agissait d'une unité de calcul de 4 bits, cadencé à 108 kHz. Depuis, la puissance des microprocesseurs augmente exponentiellement (Cf. loi empirique de Moore : « la complexité des semi-conducteurs proposés en entrée de gamme double tous les dix-huit mois à coût constant depuis 1959, date de leur invention ».
Fonctionnement
Le CPU est un circuit électronique cadencé au rythme d'une « horloge interne », grâce à un cristal de quartz qui, soumis à un courant électrique, envoie des impulsions, appelées « top ». La fréquence d'horloge (appelée également cycle), correspondant au nombre d'impulsions par seconde, s'exprime en Hertz (Hz). Ainsi, un ordinateur à 200 MHz possède une horloge envoyant 200 000 000 de battements par seconde. La fréquence d'horloge est généralement un multiple de la fréquence du système (FSB, Front-Side Bus), c'est-à-dire un multiple de la fréquence de la carte mère
A chaque top d'horloge le processeur exécute une action, correspondant à une instruction ou une partie d'instruction. L'indicateur appelé CPI (Cycles Par Instruction) permet de représenter le nombre moyen de cycles dhorloge nécessaire à lexécution dune instruction sur un microprocesseur. La puissance du processeur peut ainsi être caractérisée par le nombre d'instructions qu'il est capable de traiter par seconde. L'unité utilisée est le MIPS (Millions d'Instructions Par Seconde) correspondant à la fréquence du processeur que divise le CPI.
Définition : une instruction est l'opération élémentaire que le processeur peut accomplir. Les instructions sont stockées dans la mémoire principale (RAM), en vue d'être traitée par le processeur. Une instruction est composée de deux champs :
le code opération, représentant l'action que le processeur doit accomplir ;
le code opérande, définissant les paramètres de l'action. Le code opérande dépend de l'opération. Il peut s'agir d'une donnée ou bien d'une adresse mémoire.
Le nombre d'octets d'une instruction est variable selon le type de donnée et selon de type de CPU (l'ordre de grandeur est de 1 à 4 octets).
Les instructions peuvent être classées en catégories dont les principales sont :
Accès à la mémoire : des accès à la mémoire ou transferts de données entre registres.
Opérations arithmétiques : opérations telles que les additions, soustractions, divisions ou multiplication.
Opérations logiques : opérations ET, OU, NON, NON exclusif, etc.
Contrôle : contrôles de séquence, branchements conditionnels, etc.
Définition : lorsque le processeur exécute des instructions, les données sont temporairement stockées dans de petites mémoires rapides de 8, 16, 32 ou 64 bits, située à lintérieur du microprocesseur, que l'on appelle registres. Suivant le type de processeur le nombre global de registres peut varier d'une dizaine à plusieurs centaines.
Les principaux registres sont :
le registre accumulateur (ACC), stockant les résultats des opérations arithmétiques et logiques ;
le registre d'état (PSW, Processor Status Word), permettant de stocker des indicateurs sur l'état du système (retenue, dépassement, etc.) ;
le registre instruction (RI), contenant l'instruction en cours de traitement ;
le compteur ordinal (CO ou PC pour Program Counter), contenant l'adresse de la prochaine instruction à traiter ;
le registre tampon, stockant temporairement une donnée provenant de la mémoire.
Mémoire cache
Définition : la mémoire cache (également appelée antémémoire ou mémoire tampon) est une mémoire rapide permettant de réduire les délais d'attente des informations stockées en mémoire vive.
En effet, depuis quelques années, la mémoire centrale de l'ordinateur possède une vitesse bien moins importante que le processeur. Il existe néanmoins des mémoires beaucoup plus rapides, mais dont le coût est très élevé. La solution consiste donc à inclure ce type de mémoire rapide à proximité du processeur et d'y stocker temporairement les principales données devant être traitées par le processeur. Les ordinateurs récents possèdent plusieurs niveaux de mémoire cache :
La mémoire cache de premier niveau (appelée Cache L1, pour Level 1 Cache) est directement intégrée dans le processeur. Dans certains modèles de microprocesseurs (ça na pas toujours été le cas), elle se subdivise en 2 parties :
le cache d'instructions, qui contient les instructions issues de la mémoire vive décodées lors de passage dans les « pipelines » (Cf. ci-dessous) ;
la seconde est le cache de données, qui contient des données issues de la mémoire vive et les données récemment utilisées lors des opérations du processeur.
Les caches du premier niveau sont très rapides d'accès : leur délai d'accès tend à s'approcher de celui des registres internes aux processeurs ;
La mémoire cache de second niveau (appelée Cache L2, pour Level 2 Cache) est située au niveau du boîtier contenant le processeur (dans la puce). Le cache de second niveau vient s'intercaler entre le processeur avec son cache interne et la mémoire vive. Il est plus rapide d'accès que cette dernière mais moins rapide que le cache de premier niveau ;
La mémoire cache de troisième niveau (appelée Cache L3, pour Level 3 Cache) est située au niveau de la carte mère.
Tous ces niveaux de cache permettent de réduire les temps de latence des différentes mémoires lors du traitement et du transfert des informations. Pendant que le processeur travaille, le contrôleur de cache de premier niveau peut s'interfacer avec celui de second niveau pour faire des transferts d'informations sans bloquer le processeur. De même, le cache de second niveau est interfacé avec celui de la mémoire vive (cache de troisième niveau), pour permettre des transferts sans bloquer le fonctionnement normal du processeur.
Signaux de commande
Les signaux de commande sont des signaux électriques permettant d'orchestrer les différentes unités du processeur participant à l'exécution d'une instruction. Les signaux de commandes sont distribués grâce à un élément appelé séquenceur. Le signal Read/Write (en français lecture/écriture), permet par exemple de signaler à la mémoire que le processeur désire lire ou écrire une information.
Unités fonctionnelles
En pratique, le microprocesseur est constitué d'un ensemble d'unités fonctionnelles reliées entre elles. L'architecture d'un microprocesseur est très variable d'une architecture à une autre. Cependant, les principaux éléments d'un microprocesseur sont les suivants :
Une unité d'instruction (ou unité de commande, en anglais control unit) qui lit les données entrant dans le CPU, les décode, puis les envoie à l'unité d'exécution ;
L'unité d'instruction est notamment constituée des éléments suivants :
le séquenceur (ou bloc logique de commande) chargé de synchroniser l'exécution des instructions au rythme d'une horloge. Il est ainsi chargé de l'envoi des signaux de commande ;
le compteur ordinal contenant l'adresse de l'instruction en cours ;
le registre d'instruction contenant l'instruction suivante.
Une unité d'exécution (ou unité de traitement), qui accomplit les tâches que lui a données l'unité d'instruction. L'unité d'exécution est notamment composée des éléments suivants :
L'unité arithmétique et logique (notée UAL ou en anglais ALU pour Arithmetical and Logical Unit). L'UAL assure les fonctions basiques de calcul arithmétique et les opérations logiques (ET, OU, Ou exclusif, etc.),
L'unité de virgule flottante (notée FPU, pour Floating Point Unit), qui accomplit les calculs complexes non entiers que ne peut réaliser l'unité arithmétique et logique,
Le registre d'état,
Le registre accumulateur.
Une unité de gestion des bus (ou unité d'entrées-sorties), qui gère les flux d'informations entrant et sortant, en interface avec la mémoire vive du système ;
Le schéma ci-dessous donne un schéma simplifié des éléments constituant le CPU :
EMBED PowerPoint.Slide.8
Familles
Chaque type de CPU possède son propre jeu d'instructions (ensemble dinstructions reconnues par le CPU). On distingue ainsi les familles de processeurs suivants, possédant chacun un jeu d'instruction qui leur est propre :
80x86 : (« x » représente la famille). Exemple : 386, 486, 586, 686, Pentium, ...,
ARM,
IA-64,
MIPS,
Motorola 6800,
PowerPC,
SPARC,
...
Cela explique qu'un programme exécutable compilé et assemblé pour un type de processeur ne puisse fonctionner directement sur un système possédant un autre type de processeur.
Jeu d'instruction, architecture de CPU
On appelle jeu dinstructions lensemble des opérations élémentaires qu'un processeur peut accomplir. Le jeu d'instruction d'un processeur détermine ainsi son architecture, sachant qu'une même architecture peut aboutir à des implémentations différentes selon les constructeurs.
Le processeur travaille effectivement grâce à un nombre limité de fonctions, directement câblées sur les circuits électroniques. La plupart des opérations peuvent être réalisées à l'aide de fonctions basiques. Certaines architectures incluent néanmoins des fonctions évoluées courante dans le processeur.
Les deux grandes architectures de CPU sont :
Larchitecture CISC (Complex Instruction Set Computer, soit « ordinateur à jeu d'instruction complexe ») consiste à câbler dans le processeur des instructions complexes, difficiles à créer à partir des instructions de base. L'architecture CISC est utilisée en particulier par les processeurs de type 80x86. Ce type d'architecture possède un coût élevé dû aux fonctions évoluées imprimées sur le silicium. D'autre part, les instructions sont de longueurs variables et peuvent parfois nécessiter plus d'un cycle d'horloge. Or, un processeur basé sur l'architecture CISC ne peut traiter qu'une instruction à la fois, d'où un temps d'exécution conséquent ;
Larchitecture RISC (Reduced Instruction Set Computer, soit « ordinateur à jeu d'instructions réduit ») n'a pas de fonctions évoluées câblées. Les programmes doivent ainsi être traduits en instructions simples, ce qui entraîne un développement plus difficile et/ou un compilateur plus puissant. Une telle architecture possède un coût de fabrication réduit par rapport aux processeurs CISC. De plus, les instructions, simples par nature, sont exécutées en un seul cycle d'horloge, ce qui rend l'exécution des programmes plus rapide qu'avec des processeurs basés sur une architecture CISC. Enfin, de tels processeurs sont capables de traiter plusieurs instructions simultanément en les traitant en parallèle.
Améliorations technologiques
Ces dernières années, les constructeurs de microprocesseurs (appelés fondeurs), ont mis au point un certain nombre d'améliorations permettant d'optimiser le fonctionnement du processeur :
Le parallélisme : consiste à exécuter simultanément, sur des processeurs différents, des instructions relatives à un même programme. Cela se traduit par le découpage d'un programme en plusieurs processus traités en parallèle afin de gagner en temps d'exécution.
Le pipeline : technologie visant à permettre une plus grande vitesse d'exécution des instructions en parallélisant des étapes.
Pour comprendre le mécanisme du pipeline, il est nécessaire au préalable de comprendre les phases d'exécution d'une instruction. Les phases d'exécution d'une instruction pour un processeur contenant un pipeline « classique » à 5 étages sont les suivantes :
LI : (Lecture de l'Instruction (en anglais FETCH instruction) depuis le cache ;
DI : Décodage de l'Instruction (DECODe instruction) et recherche des opérandes (Registre ou valeurs immédiate);
EX : Exécution de l'Instruction (EXECute instruction) (si ADD, on fait la somme, si SUB, on fait la soustraction, etc.);
MEM : Accès mémoire (MEMory access), écriture dans la mémoire si nécéssaire ou chargement depuis la mémoire ;
ER : Ecriture (Write instruction) de la valeur calculée dans les registres.
Classiquement, les instructions sont organisées en file d'attente dans la mémoire, et sont chargées les unes après les autres.
Dans un pipeline, le traitement des instructions nécessite au maximum les cinq étapes précédentes. Dans la mesure où l'ordre de ces étapes est invariable (LI, DI, EX, MEM et ER), il est possible de créer dans le processeur un certain nombre de circuits spécialisés pour chacune de ces phases.
L'objectif du pipeline est d'être capable de réaliser chaque étape en parallèle avec les étapes amont et aval, c'est-à-dire de pouvoir lire une instruction (LI) lorsque la précédente est en cours de décodage (DI), que celle d'avant est en cours d'exécution (EX), que celle située encore précédemment accède à la mémoire (MEM) et enfin que la première de la série est déjà en cours d'écriture dans les registres (ER).
EMBED PowerPoint.Slide.8
Il faut compter en général 1 à 2 cycles d'horloge (rarement plus) pour chaque phase du pipeline, soit 10 cycles d'horloge maximum par instruction. Pour deux instructions, 12 cycles d'horloge maximum seront nécessaires (10+2=12 au lieu de 10*2=20), car la précédente instruction était déjà dans le pipeline. Les deux instructions sont donc en traitement dans le processeur, avec un décalage d'un ou deux cycles d'horloge). Pour 3 instructions, 14 cycles d'horloge seront ainsi nécessaires, etc.
Technologie superscalaire (en anglais superscaling) consiste à disposer plusieurs unités de traitement en parallèle afin de pouvoir traiter plusieurs instructions par cycle ;
La technologie HyperThreading (traduisez HyperFlots ou HyperFlux) consiste à définir deux processeurs logiques au sein d'un processeur physique. Ainsi, le système dexploitation reconnaît deux processeurs physiques et se comporte en système multitâche en envoyant deux threads simultanés (nous reparlerons longuement de ce quest un thread dans les prochains chapitres). On parle alors de SMT (Simultaneous Multi Threading). Cette « supercherie » permet d'utiliser au mieux les ressources du processeur en garantissant que des données lui sont envoyées en masse.
Le bus
Description
Un bus informatique désigne l'ensemble des « lignes de communication » connectant les différents composants d'un ordinateur.
le bus système (aussi appelé bus interne) : il relie le micro-processeur à la mémoire vive ;
le bus dextension (aussi appelé bus dentrées/sorties) : il relie le micro-processeur aux connecteurs dentrées/sorties et aux connecteurs dextension.
Un bus qui n'interconnecte que deux dispositifs est appelé un « port ».
Un bus est souvent caractérisé par une fréquence et le nombre de bits d'informations qu'il peut transmettre simultanément (via des « lignes »). Lorsqu'un bus peut transmettre plus d'un bit d'information simultanément, on parlera d'un bus parallèle, sinon, d'un bus série.
Remarque : la fréquence donnée est tantôt la fréquence du signal électrique sur le bus, tantôt la cadence de transmission des informations, qui peut être un multiple de la fréquence du signal (vitesse de transmission = fréquence dhorloge * nombre de lignes).
Exercice : quelle est la vitesse de transmission (en méga octets par seconde Mo/s ) dun bus de 32 bits ayant une fréquence de 66 MHz ?
A ne pas savoir par cur, voici quelques exemples de vitesse de bus :
NormeLargeur du bus (bits)Vitesse du bus (MHz)Bande passante (Mo/sec)ISA 8-bit88.37.9ISA 16-bit168.315.9EISA328.331.8VLB3233127.2PCI 32-bit3233127.2PCI 64-bit 2.16466508.6AGP3266254.3AGP(x2 Mode)3266x2528AGP(x4 Mode)3266x41056AGP(x8 Mode)3266x82112ATA33163333ATA1001650100ATA1331666133Serial ATA (S-ATA)1180Serial ATA II (S-ATA2)2380USB11.5USB 2.0160Firewire1100Firewire 21200SCSI-184.775SCSI-2 Fast81010SCSI-2 Wide161020SCSI-2 - Fast Wide 32 bits321040SCSI-3 Ultra82020SCSI-3 - Ultra Wide162040SCSI-3 - Ultra 284040SCSI-3 - Ultra 2 Wide164080SCSI-3 - Ultra 160 (Ultra 3)1680160SCSI-3 - Ultra 320 (Ultra 4)1680 DDR320SCSI-3 - Ultra 640 (Ultra 5)1680 QDR640Matériel
D'un point de vue physique, un bus est un ensemble de conducteurs électriques parallèles. À chaque cycle de temps, chaque conducteur transmet un bit.
En général, lélément qui écrit sur le bus positionne une tension de 0 volt pour indiquer un « zéro binaire », et une tension choisie conventionnellement par le constructeur pour indiquer le « un binaire ». Les éléments qui « écoutent » sur le bus mettent leur ligne en position « impédance infinie » pour ne pas entraver ce signal.
Pour les bus parallèles (exemple : ceux entre le CPU, la mémoire, les éléments dentrée/sortie) on en général une taille de 8 bits, 16 bits, 32 bits, 64 bits ou plus.
Certains conducteurs supplémentaires sont affectés à la transmission des signaux de contrôles de l'état du bus (horloge, demande dutilisation du bus, etc).
Dans un ordinateur
Dans un ordinateur, la lecture et lécriture entre le CPU et la mémoire vive (ou entre un périphérique et la mémoire vive, ou entre le CPU et un périphérique) se fait sur trois bus distincts :
un bus de données,
un bus d'adresse,
un bus de contrôle.
Le bus d'adresse est utilisé pour sélectionner la ou les cellules mémoires qui doivent être lues ou écrites. Le bus de données transmet le contenu de la mémoire elle-même (ou la donnée à inscrire en mémoire). Le bus de contrôle permet de gérer la communication sur le bus (demande dutilisation du bus, horloge, etc).
Le chipset
On appelle chipset (en français « jeu de composants ») l'élément chargé d'aiguiller les informations entre les différents bus de l'ordinateur, afin de permettre à tous les éléments constitutifs de l'ordinateur de communiquer entre eux. Le chipset était originalement composé d'un grand nombre de composants électroniques, ce qui explique son nom. Aujourdhui, dans un PC, il est généralement composé de deux éléments :
le NorthBridge (Pont Nord ou Northern Bridge, appelé également contrôleur mémoire) est chargé de contrôler les échanges entre le processeur et la mémoire vive. C'est la raison pour laquelle il est situé géographiquement proche du processeur. Il est parfois appelé GMCH, pour Graphic and Memory Controller Hub ;
le SouthBridge (Pont Sud ou Southern Bridge, appelé également contrôleur d'entrée-sortie ou contrôleur d'extension) gère les communications avec les périphériques d'entrée-sortie. Le pont sud est également appelé ICH (I/O Controller Hub).
On parle généralement de bridge (en français pont) pour désigner un élément d'interconnexion entre deux bus.
EMBED PowerPoint.Slide.8
La mémoire
On appelle « mémoire » tout composant électronique capable de stocker temporairement des données. On distingue ainsi deux grandes catégories de mémoires :
la mémoire centrale (appelée également mémoire interne) permettant de mémoriser temporairement les données lors de l'exécution des programmes. La mémoire centrale est réalisée à l'aide de micro-conducteurs, c'est-à-dire des circuits électroniques spécialisés rapides. La mémoire centrale correspond à ce que l'on appelle la mémoire vive ;
la mémoire de masse (appelée également mémoire physique ou mémoire externe) permettant de stocker des informations à long terme, y compris lors de l'arrêt de l'ordinateur. La mémoire de masse correspond aux dispositifs de stockage magnétiques, tels que le disque dur, aux dispositifs de stockage optique, correspondant par exemple aux CD-ROM ou aux DVD-ROM, ainsi qu'aux mémoires mortes.
Caractéristiques techniques
Les principales caractéristiques d'une mémoire sont les suivantes :
la capacité, représentant le volume global d'informations (en bits) que la mémoire peut stocker ;
le temps d'accès, correspondant à l'intervalle de temps entre la demande de lecture/écriture et la disponibilité de la donnée ;
le temps de cycle, représentant l'intervalle de temps minimum entre deux accès successifs ;
le débit, définissant le volume d'information échangé par unité de temps, exprimé en bits par seconde ;
la non volatilité, caractérisant l'aptitude d'une mémoire à conserver les données lorsqu'elle n'est plus alimentée électriquement.
Ainsi, la mémoire idéale possède une grande capacité avec des temps d'accès et temps de cycle très restreints, un débit élevé et est non volatile.
EMBED PowerPoint.Slide.8
Néanmoins les mémoires rapides sont également les plus onéreuses. C'est la raison pour laquelle des mémoire utilisant différentes technologiques sont utilisées dans un ordinateur, interfacées les unes avec les autres et organisées de façon hiérarchique.
Temps d'accès et capacité des différents types de mémoire
Les mémoires les plus rapides (aussi les plus coûteuses) sont situées en faible quantité à proximité du processeur et les mémoires de masse, moins rapides (et moins coûteuses), servent à stocker les informations de manière permanente.
Parmi les types de mémoires, nous pouvons noter :
La mémoire vive : généralement appelée RAM (Random Access Memory, traduisez mémoire à accès direct), cest la mémoire principale du système, c'est-à-dire qu'il s'agit d'un espace permettant de stocker de manière temporaire des données lors de l'exécution d'un programme ;
Mémoire morte : la mémoire morte, appelée ROM pour Read Only Memory (traduisez mémoire en lecture seule) est un type de mémoire permettant de conserver les informations qui y sont contenues même lorsque la mémoire n'est plus alimentée électriquement. A la base ce type de mémoire ne peut être accédée qu'en lecture. Toutefois il est désormais possible d'enregistrer des informations dans certaines mémoires de type ROM.
Mémoire flash : la mémoire flash est un compromis entre les mémoires de type RAM et les mémoires mortes. En effet, la mémoire Flash possède la non-volatilité des mémoires mortes tout en pouvant facilement être accessible en lecture ou en écriture. En contrepartie les temps d'accès des mémoires flash sont plus importants que ceux de la mémoire vive.
Communication périphériques/CPU
Les interruptions matérielles (et IRQ)
Puisque le CPU ne peut pas traiter plusieurs informations simultanément (il traite une information à la fois, le multitâche consiste à alterner des morceaux d'instructions de plusieurs tâches différentes de façon très rapide, afin que lutilisateur ait une impression de simultanéité), un programme en cours d'exécution peut, grâce à une interruption, être momentanément suspendu, le temps que s'exécute une routine d'interruption. Le programme interrompu peut ensuite reprendre son exécution.
Une interruption devient une interruption matérielle lorsqu'elle est demandée par un composant matériel de l'ordinateur.
Ainsi, lorsque lorsquun périphérique a besoin d'une ressource, il envoie parfois au CPU une demande d'interruption pour que ce dernier lui prête son attention.
En pratique, dans un PC classique, les périphériques ont un numéro d'interruption, que l'on appelle IRQ (Interruption request, ce qui signifie «requête d'interruption»). Physiquement, chaque IRQ correspond à un signal sur une ligne. Par exemple, historiquement, sur un bus ISA, il y a une ligne qui signifie « demande dinterruption ». Et sur le bus de données, le ou les lignes à « 1 » sur le canal de données indiquai(en)t le numéro dIRQ (de 0 à 7). Comme plusieurs demandes dinterruptions peuvent être faites simultanément, un « contrôleur dinterruption » permet de prendre en compte lIRQ ayant la plus haute priorité. Avec larrivée des bus 16 bits est apparu un second contrôleur d'interruptions. La liaison entre les deux groupes d'interruptions se fait par l'intermédiaire de l'IRQ 2 reliée à l'IRQ 9 (et est appelée «cascade»). La cascade vient donc en quelque sorte "insérer" les IRQ 8 à 15 sauf le 9 entre les IRQ 1 et 3 :
89101112131415|01234567Principe de cascade dIRQ
Sur un PC, pour un contrôleur dinterruption donné, les IRQ ayant un le numéro le plus petit est prioritaire. Avec le principe de cascade, les priorités des IRQ sont classées ainsi :
0 > 1 > 8 > 9 > 10 > 11 > 12 > 13 > 14 > 15 > 3 > 4 > 5 > 6 > 7
Les adresses de base
Les périphériques ont besoin d'échanger des informations avec le CPU. Des plages dadresses mémoire leur sont assignées pour l'envoi et la réception de données. Ces adresses sont appelées « adresses de base » (les termes suivants sont également parfois utilisés : « ports d'entrée/sortie », « ports d'E/S », « adresse d'E/S », « ports de base », ou en anglais « I/O address » ou «Input/Output Address »).
C'est par l'intermédiaire de cette adresse de base que le périphérique peut communiquer avec le système d'exploitation. Il nexiste qu'une adresse de base unique par périphérique.
Utilisation dun canal DMA
Des périphériques ont régulièrement besoin daccéder à une zone mémoire afin de s'en servir comme zone de tampon (en anglais buffer), c'est-à-dire une zone de stockage temporaire permettant d'enregistrer rapidement des données en entrée ou en sortie.
Un canal d'accès direct à la mémoire, appelé DMA (Direct Memory Access soit « Accès direct à la mémoire »), a ainsi été défini pour y remédier.
Le canal DMA désigne un accès à un emplacement de la mémoire vive (RAM) de lordinateur, repéré par une « adresse de début » (ou «RAM Start Address» en anglais) et une « adresse de fin ». Cette méthode permet à un périphérique d'emprunter des canaux spéciaux qui lui donnent un accès direct à la mémoire, sans faire intervenir le microprocesseur, afin de le décharger de ce dernier.
Un ordinateur de type PC possède 8 canaux DMA. Les quatre premiers canaux DMA ont une largeur de bande de 8 bits tandis que les DMA 4 à 7 ont une largeur de bande de 16 bits.
Le système dexploitation
Définition
Le système d'exploitation (SE, en anglais « Operating System » ou OS) est un ensemble de programmes responsables de la liaison entre les ressources matérielles d'un ordinateur et les applications de l'utilisateur (traitement de texte, jeu vidéo...).
Il assure le démarrage de l'ordinateur, et fournit aux programmes applicatifs des points d'entrée génériques pour les périphériques.
Il a des objectifs principaux :
la prise en charge, la gestion, et le partage des ressources dun ordinateur,
la construction au dessus de ces ressources dune « interface standardisée » (au niveau des programmeurs, on parlera plus tard dAPI : « Application Programming Interface », ou « Interface de programmation » en français) plus conviviale et plus facile demploi pour y accéder.
Le partage des ressources va principalement concerner :
le partage du CPU,
le partage de la mémoire centrale,
le partage des périphériques dentrée-sortie (clavier, écran, imprimante, webcam...).
Les questions auxquelles le système dexploitation doit répondre sont :
Dans le cadre du partage du processeur : parmi tous les programmes chargés en mémoire centrale, lequel doit sexécuter ?
Dans le cadre du partage de la mémoire centrale : comment allouer la mémoire centrale aux différents programmes? Comment disposer dune quantité suffisante de mémoire pour y placer tous les programmes nécessaires à un bon taux dutilisation du processeur ? Comment assurer la protection entre ces différents programmes utilisateurs (protection = veiller à ce quun programme donné naccède pas à une plage mémoire allouée à un autre programme) ?
Dans le cadre du partage des périphériques: dans quel ordre traiter les requêtes dentrées-sorties pour optimiser les transferts?
Structure générale
Le système dexploitation réalise donc une couche logicielle placée entre la machine matérielle et les applications. Le système dexploitation peut être découpé en plusieurs grandes fonctionnalités. Dans une première approche, ces fonctionnalités qui seront étudiées plus en détail dans ce cour sont :
la fonctionnalité de gestion du processeur : le système doit gérer lallocation du processeur aux différents programmes pouvant sexécuter. Cette allocation se fait par le biais dun algorithme dordonnancement qui planifie lexécution des programmes. Dans ce cadre, une exécution de programme est appelée processus ;
la fonctionnalité de gestion des objets externes : comme la mémoire centrale est une mémoire volatile, toutes les données devant être conservées au-delà de larrêt de la machine doivent être stockées sur une mémoire de masse non volatile (disque dur, Clé USB, CD-Rom...). La gestion de lallocation des mémoires de masse ainsi que laccès aux données qui y sont stockées sappuient sur la notion de fichiers et de système de gestion de fichiers ;
la fonctionnalité de gestion des entrées-sorties : le système doit gérer laccès aux périphériques. Il doit faire la liaison entre les appels de haut niveau des programmes utilisateurs (exemple : fgetc()) et les opérations de bas niveau de lunité déchange responsable du périphérique (unité déchange clavier) : cest le pilote dentrées-sorties (driver) qui assure ce travail ;
la fonctionnalité de gestion de la mémoire : le système doit gérer lallocation de la mémoire centrale entre les différents programmes pouvant sexécuter, cest-à-dire quil doit trouver une place libre suffisante en mémoire centrale pour que le chargeur puisse y placer un programme à exécuter, en sappuyant sur les mécanismes matériels sous-jacents de segmentation et de pagination. Comme la mémoire physique est souvent trop petite pour contenir la totalité des programmes, la gestion de la mémoire se fait selon le principe de la mémoire virtuelle : à un instant donné, seules sont chargées en mémoire centrale les parties de code et données utiles à lexécution, les autres étant temporairement stockées sur disque ;
la fonctionnalité de gestion de la concurrence : comme plusieurs programmes coexistent en mémoire centrale, ceux-ci peuvent vouloir communiquer pour échanger des données. Par ailleurs, il faut synchroniser laccès aux données partagées afin de maintenir leur cohérence. Le système dexploitation offre des outils de communication et de synchronisation entre processus ;
la fonctionnalité de gestion de la protection : le système doit fournir des mécanismes garantissant que ses propres ressources (processeur, mémoire, fichiers) ne peuvent être utilisées que par les programmes auxquels les droits nécessaires ont été accordés. Ii faut notamment protéger le système et la machine des programmes utilisateurs (mode « exécution utilisateur » et mode « superviseur ») ;
la fonctionnalité daccès au réseau : des exécutions de programmes placées sur des machines physiques distinctes doivent pouvoir échanger des données. Le système dexploitation fournit des outils permettant aux applications distantes de dialoguer au travers une couche de protocoles réseau telle que TCP/IP.
Les fonctionnalités du système dexploitation utilisent les mécanismes offerts par le matériel de la machine physique pour réaliser leurs opérations. Notamment, le système dexploitation sinterface avec la couche matérielle, par le biais du mécanisme des interruptions (Cf. chapitre précédent), qui lui permet de prendre connaissance des événements survenant au niveau matériel.
Par ailleurs, le système dexploitation sinterface avec les applications du niveau utilisateur par le biais des fonctions prédéfinies que chacune de ses fonctionnalités offre. Ces fonctions que lon qualifie de routines systèmes constituent les points dentrées des fonctionnalités du système dexploitation. Il est possible de les appeler depuis les applications de niveau utilisateur. Ces appels peuvent se faire à deux niveaux :
dans le code dun programme utilisateur à laide dun appel système, qui nest autre quune forme dappel de procédure amenant à lexécution dune routine système ;
depuis le « prompt » de linterpréteur de commandes, à laide dune commande. Linterpréteur de commandes est un outil de niveau utilisateur qui accepte les commandes de lutilisateur, les analyse et lance lexécution de la routine système associée ;
plus récemment, dans les systèmes dexploitations graphique, en utilisant les mécanismes dicônes (double clic, menu contextuel, clisser/déposer, etc.).
Les différents types de systèmes dexploitation
Les systèmes dexploitation « ayant à gérer plusieurs tâches » peuvent être classés selon différents types :
les systèmes à traitements par lots ;
les systèmes multi-utilisateurs interactifs ;
les systèmes temps-reels.
Les systèmes à traitements par lots
Les systèmes à traitement par lots (ou systèmes batch) constituent en quelque sorte les ancêtres de tous les systèmes dexploitation. Ils sont nés de lintroduction sur les toutes premières machines de deux programmes permettant une exploitation plus rapide et plus rentable du processeur, en vue dautomatiser les tâches de préparation des travaux à exécuter. Ces deux programmes sont :
le chargeur dont le rôle a été initialement de charger automatiquement les programmes dans la mémoire centrale de la machine depuis les cartes perforées ou le dérouleur de bandes ;
le moniteur denchaînement de traitements, dont le rôle a été de permettre lenchaînement automatique des travaux soumis en lieu et place de lopérateur de la machine.
Le principe du traitement par lots sappuie sur la composition de lots de travaux ayant des caractéristiques ou des besoins communs, la formation de ces lots visant à réduire les temps dattente du processeur en faisant exécuter les uns à la suite des autres ou ensemble, des travaux nécessitant les mêmes ressources.
La caractéristique principale dun système de traitement par lots est quil ny a pas dinteraction possible entre lutilisateur et la machine durant lexécution du programme soumis. Le programme est soumis avec ses données dentrées et lutilisateur récupère les résultats de lexécution ultérieurement, soit dans un fichier, soit sous forme dune impression. Cest le mode de fonctionnement typique des anciens MainFrame.
Les systèmes interactifs
La particularité dun système dexploitation interactif est que lutilisateur de la machine peut interagir avec lexécution de son programme. Typiquement, lutilisateur lance lexécution de son programme et attend, derrière le clavier et lécran, le résultat de celle-ci. Sil saperçoit que lexécution nest pas conforme à son espérance, il peut immédiatement agir pour arrêter celle-ci, et analyser les raisons de léchec.
Puisque lutilisateur attend derrière son clavier et son écran et que, par nature, lutilisateur de la machine est un être impatient, le but principal poursuivi par les systèmes interactifs va être doffrir pour chaque exécution le plus petit temps de réponse possible. Pour parvenir à ce but, la plupart des systèmes interactifs travaillent en temps partagé (impression de multitâche donné en exécutant rapidement de courts fragments de plusieurs programmes les uns à la suite des autres).
En effet, un système en temps partagé permet aux différents utilisateurs de partager lordinateur simultanément, tout en ayant par ailleurs la sensation dêtre seul à utiliser la machine. Ce principe repose notamment sur un partage de lutilisation du processeur par les différents programmes des différents utilisateurs. Chaque programme occupe à tour de rôle le processeur pour un court laps de temps (le quantum) et les exécutions se succèdent suffisamment rapidement sur le processeur pour que lutilisateur ait limpression que son travail dispose seul du processeur.
Les systèmes « temps-réel »
Les systèmes temps réel sont des systèmes liés au contrôle de procédé pour lesquels la caractéristique primordiale est que les exécutions de programmes sont soumises à des contraintes temporelles, cest-à-dire quune exécution de programme est notamment qualifiée par une date butoir de fin dexécution, appelée « échéance », au-delà de laquelle les résultats de lexécution ne sont plus valides.
Exemple : programme de contrôle dun automate dune chaîne de production, pilotage dun missile, etc.
Pour garantir le respect de limites ou contraintes temporelles, il est nécessaire que :
les différents services et algorithmes utilisés s'exécutent en temps borné. Un système d'exploitation temps réel doit ainsi être conçu de manière à ce que les services qu'il propose (accès hardware, etc.) répondent en un temps borné ;
les différents enchaînements possibles des traitements garantissent que chacun de ceux-ci ne dépassent pas leurs limites temporelles. Ceci est vérifié à l'aide dun test appelé « test d'acceptabilité ».
On distingue deux types de systèmes « temps réel » :
le temps réel strict (ou dur, de l'anglais hard real-time) : il ne tolère aucun dépassement de ces contraintes, ce qui est souvent le cas lorsque de tels dépassements peuvent conduire à des situations critiques, voire catastrophiques : pilote automatique d'avion, système de surveillance de centrale nucléaire, etc. ;
le temps réel souple (ou mou, de langlais soft real-time) : à l'inverse, le temps réel souple s'accommode de dépassements des contraintes temporelles dans certaines limites au-delà desquelles le système devient inutilisable : visioconférence, jeux en réseau, etc.
On peut ainsi considérer qu'un système temps réel strict doit respecter des limites temporelles données même dans la pire des situations d'exécution possibles. En revanche un système temps réel souple doit respecter ses limites pour une moyenne de ses exécutions. On tolère un dépassement exceptionnel, qui sera peut-être rattrapé à l'exécution suivante.
Le noyau
Définition
Un noyau (kernel en anglais), est la partie fondamentale de certains systèmes d'exploitation. Elle gère les ressources de l'ordinateur et permet aux différents composants - matériels et logiciels - de communiquer entre eux.
En tant que partie du système d'exploitation, le noyau fournit des mécanismes d'abstraction du matériel, notamment de la mémoire, du (ou des) processeur(s), et des échanges d'informations entre logiciels et périphériques matériels. Le noyau autorise aussi diverses abstractions logicielles et facilite la communication entre les processus.
Le noyau d'un système d'exploitation est lui-même un logiciel, mais ne peut cependant utiliser tous les mécanismes d'abstraction qu'il fournit aux autres logiciels. Son rôle central impose par ailleurs des performances élevées.
La majorité des systèmes d'exploitation sont construits autour de la notion de noyau. L'existence d'un noyau, c'est-à-dire d'un programme unique responsable de la communication entre le matériel et le logiciel, résulte de compromis complexes portant sur des questions de performance, de sécurité et d'architecture des processeurs.
L'existence d'un noyau présuppose une partition virtuelle de la mémoire vive physique en deux régions disjointes, l'une étant réservée au noyau (l'espace noyau) et l'autre aux applications (l'espace utilisateur). Cette division fondamentale de l'espace mémoire en un espace noyau et un espace utilisateur contribue beaucoup à donner la forme et le contenu actuels des systèmes généralistes (Linux, Windows, Mac OS X, etc.). Le noyau a de grands pouvoirs sur l'utilisation des ressources matérielles, en particulier de la mémoire. Elle structure également le travail des développeurs : le développement de code dans l'espace noyau est à priori plus délicat que dans l'espace utilisateur car la mémoire n'est pas protégée.
Diverses abstractions de la notion d'application sont fournies par le noyau aux développeurs. La plus courante est celle de processus (ou tâche). Le noyau du système d'exploitation n'est en lui même pas une tâche, mais un ensemble de routines pouvant être appelées par les différents processus pour effectuer des opérations requérant un certain niveau de privilèges. Les flots d'exécution dans le noyau sont des continuations des flots d'exécution des processus utilisateurs bloqués lorsqu'ils effectuent des appels systèmes. En général, un processus bloqué ne consomme pas de temps processeur, il est réveillé par le processus système lorsque celui-ci se termine.
Lorsque plusieurs tâches doivent être exécutées de manière parallèle, un noyau multitâche s'appuie sur les notions de :
commutation de contexte ;
ordonnancement ;
temps partagé.
Les différents types de noyaux
Il existe toutes sortes de noyaux, plus ou moins spécialisés. Des noyaux spécifiques à une architecture, souvent monotâches, d'autres généralistes et souvent multitâches et multiutilisateurs. L'ensemble de ces noyaux peut être divisé en deux approches opposées d'architectures logicielles : les noyaux monolithiques (modulaires ou pas) et les micro-noyaux.
Définitions :
« Noyaux monolithiques non modulaires » : certains OS, comme d'anciennes versions de Linux, certains BSD ou certains vieux Unix ont un noyau monolithique. Cest-à-dire que l'ensemble des fonctions du système et des pilotes sont regroupés dans un seul bloc de code et un seul bloc binaire généré à la compilation. De par la simplicité de leur concept mais également de leur excellente vitesse d'exécution, les noyaux monolithiques ont été les premiers à être développés et mis en uvre. Cependant, au fur et à mesure de leurs développements, les codes des noyaux monolithiques ont augmenté en taille et il s'est avéré difficile de les maintenir. Le support par les architectures monolithiques des chargements à chaud ou dynamiques implique une augmentation du nombre de pilotes matériel compilés dans le noyau, et par suite, une augmentation de la taille de l'empreinte mémoire des noyaux. Celle-ci devint rapidement inacceptable. De plus, les multiples dépendances créées entre les différentes fonctions du noyau empêchaient la relecture et la compréhension du code ;
« Noyaux monolithiques modulaires » : pour répondre aux problèmes des noyaux monolithiques, ces derniers sont devenus modulaires. Dans ce type de noyau, seules les parties fondamentales du système sont regroupées dans un bloc de code unique (monolithique). Les autres fonctions, comme les pilotes matériel, sont regroupées en différents modules qui peuvent être séparés tant du point de vue du code que du point de vue binaire. La très grande majorité des systèmes actuels utilise cette technologie : Linux, la plupart des BSD ou Solaris. Par exemple avec le noyau Linux, certaines parties peuvent être non compilées ou compilées en tant que modules chargeables directement dans le noyau. La modularité du noyau permet le chargement à la demande de fonctionnalités et augmente les possibilités de configuration. Ainsi les systèmes de fichiers peuvent être chargés de manière indépendante, un pilote de périphérique changé, etc. Les distributions Linux, par exemple, tirent profit des modules chargeables lors de l'installation. L'ensemble des pilotes matériel sont compilés en tant que modules. Le noyau peut alors supporter l'immense variété de matériel trouvé dans les compatibles PC. Après l'installation, lors du démarrage du système, seuls les pilotes correspondant au matériel effectivement présent dans la machine sont chargés en mémoire vive. La mémoire est économisée.
Les noyaux monolithiques modulaires conservent les principaux atouts des noyaux monolithiques purs dont ils sont issus. Ainsi, la facilité de conception et de développement est globalement maintenue et la vitesse d'exécution reste excellente. L'utilisation de modules implique le découpage du code source du noyau en blocs indépendants. Ces blocs améliorent l'organisation et la clarté du code source et en facilitent également la maintenance.
Les noyaux monolithiques modulaires conservent également un important défaut des noyaux monolithiques purs : une erreur dans un module met en danger la stabilité de tout le système. Les tests et certification de ces composants doivent être plus poussés.
« Micro-noyaux » : les systèmes à micro-noyaux cherchent à minimiser les fonctionnalités dépendantes du noyau en plaçant la plus grande partie des services du système d'exploitation à lextérieur de ce noyau, c'est-à-dire dans l'espace utilisateur. Ces fonctionnalités sont alors fournies par de petits serveurs indépendants possédant souvent leur propre espace d'adressage. Un petit nombre de fonctions fondamentales sont conservées dans un noyau minimaliste appelé « micro-noyau ». L'ensemble des fonctionnalités habituellement proposées par les noyaux monolithiques est alors assuré par les services déplacés en espace utilisateur et par ce micro-noyau. Cet ensemble logiciel est appelé « micro-noyau enrichi ».
Ce principe a de grands avantages théoriques : en éloignant les services « à risque » des parties critiques du système dexploitation regroupées dans le noyau, il permet de gagner en robustesse et en fiabilité, tout en facilitant la maintenance et lévolutivité. En revanche, les mécanismes de communication (IPC) qui deviennent fondamentaux pour assurer le passage de messages entre les serveurs, sont très lourds et peuvent limiter les performances.
Avantages et inconvénients des différents types de noyau
Les avantages théoriques des systèmes à micro-noyaux sont la conséquence de l'utilisation du mode protégé par les services qui accompagnent le micro-noyau. En effet, en plaçant les services non critiques dans l'espace utilisateur, ceux-ci bénéficient de la protection de la mémoire. La stabilité de l'ensemble en est améliorée : une erreur d'un service en mode protégé a peu de conséquences sur la stabilité de l'ensemble de la machine.
De plus, en réduisant les possibilités pour les services de pouvoir intervenir directement sur le matériel, la sécurité du système est renforcée. Le système gagne également en possibilités de configuration. Ainsi, seuls les services utiles doivent être réellement lancés au démarrage. Les interdépendances entre les différents serveurs sont faibles. L'ajout ou le retrait d'un service ne perturbe pas l'ensemble du système. La complexité de l'ensemble est réduite.
Le développement d'un système à micro-noyau se trouve également simplifié en tirant parti à la fois de la protection de la mémoire et de la faible interdépendance entre les services. Les erreurs provoquées par les applications en mode utilisateur sont traitées plus simplement que dans le mode noyau et ne mettent pas en péril la stabilité globale du système. L'intervention sur une fonctionnalité défectueuse consiste à arrêter l'ancien service puis à lancer le nouveau, sans devoir redémarrer toute la machine.
Les micro-noyaux ont un autre avantage : ils sont beaucoup plus compacts que les noyaux monolithiques. Six millions de lignes de code pour le noyau Linux 2.6.0 contre en général moins de 50 000 lignes pour les micro-noyaux. La maintenance du code exécuté en mode noyau est donc simplifiée. Le nombre réduit de lignes de code peut augmenter la portabilité du système.
L'utilisation de nombreux services dans l'espace utilisateur engendre les deux problèmes suivants :
la plupart des services sont à l'extérieur du noyau et génèrent un très grand nombre d'appels système ;
les interfaces de communication entre les services (IPC) sont complexes et trop lourdes en temps de traitement.
Pour ces raisons de performance, les systèmes généralistes basés sur une technologie à micro-noyau, tels que Windows et Mac OS X, n'ont pas un « vrai » micro-noyau enrichi. Ils utilisent un micro-noyau hybride : certaines fonctionnalités qui devraient exister sous forme de mini-serveurs se retrouvent intégrées dans leur micro-noyau, utilisant le même espace d'adressage. Pour Mac OS X, cela forme XNU : le noyau monolithique BSD fonctionne en tant que « service » de Mach et ce dernier inclut du code BSD dans son propre espace d'adressage afin de réduire les latences.
Ainsi, les deux approches d'architectures de noyaux, les micro-noyaux et les noyaux monolithiques, considérés comme diamétralement différentes en terme de conception, se rejoignent quasiment en pratique par les micro-noyaux hybrides et les noyaux monolithiques modulaires.
Linux
Le système dexploitation Linux est un système multiprogrammé, compatible avec la norme pour les systèmes dexploitation IEEE-POSIX 1003.1, appartenant à la grande famille des systèmes de type Unix. Cest un système de type interactif qui présente également des aspects compatibles avec la problématique du temps réel faiblement contraint.
Le système Linux est né en 1991 du travail de développement de Linus Torvalds. Initialement créé pour sexécuter sur des plates-formes matérielles de type IBM/PC/Intel 386, le système est à présent disponible sur des architectures matérielles très diverses telles que SPARC, Alpha, IBMSystem/390, Motorola, etc.
Une des caractéristiques principales de Linux est le libre accès à son code source, celui-ci ayant été déposé sous Licence Publique GNU (GPL). Le code source peut ainsi être téléchargé (http://kernel.org/), étudié et modifié par toute personne désireuse de le faire.
Structure de lOS Linux
Le système Linux est structure comme un noyau monolithique modulaire qui peut être découpé en quatre grandes fonctions :
une fonctionnalité de gestion des processus qui administre les exécutions de programmes, le processus étant limage dynamique de lexécution dun programme ;
une fonctionnalité de gestion de la mémoire ;
une fonctionnalité de gestion des fichiers de haut niveau : le VFS (Virtual File System), qui sinterface avec des gestionnaires de fichiers plus spécifiques de type Unix, DOS, etc., lesquels sinterfacent eux-mêmes avec les contrôleurs de disques, disquettes, CD-Rom, clés USB, etc.;
une fonctionnalité de gestion du réseau qui sinterface avec le gestionnaire de protocole puis le contrôleur de la carte réseau.
Larchitecture du système Linux peut être ajustée autour du noyau grâce au concept de « modules chargeables » (Cf. précédent chapitre).
Lors du paramétrage de la compilation du noyau, il est possible de définir pour chaque module sil doit être liée de façon statique au noyau (il fait alors partie du noyau monolithique), où sil doit être lié de façon dynamique (lors de linsertion dun périphérique « plug & play » par exemple).
Deux commandes permettent alors au super utilisateur (root) de gérer le lactivation dynamique dun module :
insmod nom_module (pour charger un module) ;
rmmod nom_module (pour décharger un module).
Quelques notions fondamentales
Comme nous lavons déjà évoqué précédemment, le système dexploitation sinterface avec les applications du niveau utilisateur par le biais des fonctions prédéfinies qualifiées de routines systèmes, qui constituent les points dentrées des fonctionnalités du système.
A ce titre, le noyau Linux ne doit pas être appréhendé comme étant un processus, mais un gestionnaire de processus, qui offre des services à ceux-ci.
Lexécution des routines systèmes seffectue sous un mode privilégié, appelé « mode superviseur », ou « mode maître », ou « mode noyau » (« kernel mode »). Lorsquun programme est exécuté en mode, aucune restriction ne sapplique à lui. Il peut accéder à toute la mémoire, dialoguer directement avec les périphériques, etc.
Un processus utilisateur sexécute par défaut selon un mode qualifié de « mode esclave » ou « mode utilisateur » (« User Mode »): ce mode dexécution est un mode pour lequel les actions pouvant être entreprises par le programme sont volontairement restreintes afin de protéger la machine des actions parfois malencontreuses du programmeur. Notamment, le jeu dinstructions utilisables par le programme en mode utilisateur est réduit, et spécialement les instructions permettant la manipulation des interruptions est interdite.
Remarque : sur les microprocesseurs de la famille Intel 80386 (et tous les successeurs et leurs clones), les niveaux de privilège sont implémentés en attribuant une valeur de 0 à 3 aux objets reconnus par le microprocesseur (segments, tables, etc.), le niveau 0 correspondant au niveau le plus privilégié et le niveau 3 au niveau le moins privilégié. Ces niveaux de privilège affectés aux objets définissent des règles daccès aux objets ainsi quun ensemble dinstructions privilégiées ne pouvant être exécuté que lorsque le niveau courant du processeur est égal à 0. Le système Linux nutilise que deux de ces niveaux : le niveau 0 correspond au niveau superviseur tandis que le niveau 3 correspond au niveau utilisateur. Les niveaux 1 et 2 ne sont pas pris en compte.
La commutation de contexte
Lorsquun processus utilisateur demande lexécution dune routine du système dexploitation par le biais dun appel système, ce processus quitte son mode courant dexécution (le mode esclave) pour passer en mode dexécution du système, soit le mode superviseur. Ce passage du mode utilisateur au mode superviseur constitue une commutation de contexte : elle saccompagne dune opération de sauvegarde du contexte utilisateur, cest-à-dire principalement de la valeur des registres du processeur (compteur ordinal, registre détat), sur la pile noyau. Un contexte noyau est chargé constitué dune valeur de compteur ordinal correspondant à ladresse de la fonction à exécuter dans le noyau, et dun registre détat en mode superviseur. Lorsque lexécution de la fonction système (on parle aussi de primitive) est achevée, le processus repasse du mode superviseur au mode utilisateur. Il y a de nouveau une opération de commutation de contexte avec restauration du contexte utilisateur sauvegardé lors de lappel système, ce qui permet de reprendre lexécution du programme utilisateur juste après lappel.
Trois causes majeures provoquent le passage du mode utilisateur au mode superviseur :
le fait que le processus utilisateur appelle une fonction du système. Cest une demande explicite de passage en mode superviseur.
Voici le mécanisme dappel dune fonction système sur un PC i386 : dans le registre %EAX, mettre le numéro de la fonction à appeler (en effet, chaque fonction système Linux possède un identifiant numérique unique), et mettre les arguments à transmettre dans les registres %EBX, %ECX, %EDX, %ESI et %ED. Appeler ensuite linterruption 0x80. Exemple de fonctions systèmes :
%EAXNomCode source%ebx%ecx%edx%esi%edi1 sys_exit Kernel/exit.c int 2 sys_fork arch/i386/kernel/process.c strucl pt_regs 3 sys_read fs/read_write.c unsigned int char * size_t 4 sys_write fs/read_write.c unsigned int char * size_t 5 sys_open fs/open.c const char * int int 6 sys_close fs/open.c unsigned int Nous reviendrons sur ce point dans un chapitre spécifique.
EMBED PowerPoint.Slide.8
lexécution par le processus utilisateur dune opération illicite (division par zéro, instruction machine interdite, violation mémoire...) : cest la trappe ou lexception. Lexécution du processus utilisateur est alors arrêtée ;
la prise en compte dune interruption par le matériel (IRQ). Le processus utilisateur est alors stoppé et lexécution de la routine dinterruption associée à linterruption survenue est exécutée en mode superviseur. Linterruption en question peut provenir de lhorloge du système. Cest par ce mécanisme que se gère le « temps de calcul » dun processus.
Par ailleurs, il faut noter que le noyau Linux est un noyau réentrant : le traitement dune interruption en mode noyau peut être interrompu au profit du traitement dune autre interruption survenue entre-temps. De ce fait, les exécutions au sein du noyau peuvent être imbriquées les unes par rapport aux autres. Aussi, le noyau maintient-il une valeur de niveau dimbrication, qui indique la profondeur dimbrication courante dans les chemins de contrôle du noyau.
Principe de gestion des interruptions matérielles et logicielles
Dans le système Linux, chaque interruption, quelle soit matérielle ou logicielle, est identifiée par un entier de 8 bits appelé « vecteur dinterruption », dont la valeur varie de 0 à 255 :
les valeurs de 0 à 31 correspondent aux interruptions « non masquables » (nous reviendrons sur ce terme) et aux exceptions. Correspond aux différentes interruptions gérées nativement par le CPU ;
les valeurs de 32 à 47 sont affectées aux interruptions « masquables » levées par les périphériques (IRQ) ;
les valeurs de 48 à 255 peuvent être utilisées pour identifier dautres types de trappes que celles admises par le processeur (qui correspondent aux valeurs de 0 à 31). Comme nous lavons déjà vu, lentrée 128 (0x80 en hexadécimal) est réservée aux appels système.
Ce numéro permet dadresser une table comportant 256 entrées, appelée « table des vecteurs dinterruptions » (idt_table), placée en mémoire centrale lors du démarrage de lOS.
Ainsi, lunité de contrôle du processeur, avant de commencer Iexécution nouvelle instruction machine, vérifie si une interruption ne lui a pas été délivrée. Si tel est le cas, les étapes suivantes sont mises en uvre :
linterruption i a été délivrée au processeur. Lunité de contrôle accède à lentrée n° i de la table des vecteurs dinterruptions, dont ladresse est conservée dans un registre du processeur, et récupère ladresse en mémoire centrale du gestionnaire de linterruption levée ;
lunité de contrôle vérifie que linterruption a été émise par une source autorisée ;
lunité de contrôle effectue un changement de niveau dexécution (passage en mode superviseur) si cela est nécessaire et commute de pile dexécution. En effet, comme nous lavons déjà vu, les exécutions des gestionnaires dinterruptions pouvant être imbriquées, la prise en compte dune interruption par lunité de contrôle peut être faite alors que le mode dexécution du processeur est déjà le mode superviseur (niveau dimbrication > 1) ;
lunité de contrôle sauvegarde dans la pile noyau le contenu du registre détat et du compteur ordinal;
lunité de contrôle charge le compteur ordinal avec ladresse du gestionnaire dinterruption.
Le gestionnaire dinterruption sexécute. Cette exécution achevée, Iunité de contrôle restaure le contexte sauvegardé au moment de la prise en compte de linterruption, cest-à-dire :
Iunité de contrôle restaure les registres détat et le compteur ordinal à partir des valeurs sauvegardées dans la pile noyau ;
lunité de contrôle commute de pile dexécution pour revenir à la pile utilisateur si le niveau dimbrication des exécutions du noyau est égal à 1.
Nous allons à présent examiner un peu plus en détail le fonctionnement des différents gestionnaires, pour les interruptions matérielles, pour les exceptions, et enfin, pour les appels systèmes.
Prise en compte dune interruption matérielle
Rappelons quune interruption matérielle est un signal permettant à un dispositif externe au CPU (un périphérique dentrées/sorties par exemple) dinterrompre le travail courant du processeur afin quil aille réaliser un traitement particulier lié à la cause de linterruption, appelé routine dinterruption (Cf. paragraphe sur les IRQ).
Comme il nexiste que 15 niveaux dinterruptions, il peut arriver que plusieurs périphériques différents soient attaches à la même interruption (partage de numéro dIRQ). Dans ce cas, le contrôleur dinterruptions scrute chaque périphérique de la ligne dinterruption levée pour connaître le périphérique initiateur du signal.
Voici le déroulement des opérations lorsquune interruption matérielle est levée :
le contrôleur dinterruption émet un signal sur la broche INT du CPU ;
le processeur acquitte ce signal en envoyant un signal INTA ;
le contrôleur place le numéro de linterruption levée sur le bus de données ;
le processeur (unité de contrôle) utilise ce numéro pour indexer la table des vecteurs dinterruptions et lancer lexécution du gestionnaire de linterruption matérielle selon la logique décrite précédemment.
EMBED PowerPoint.Slide.8
Une interruption survenant à nimporte quel moment, il peut être souhaitable dinterdire sa prise en compte par le processeur, notamment lorsque celui-ci train dexécuter du code noyau critique. Pour cela, les interruptions peuvent être masquées grâce à une instruction machine spécifique (instruction « cli »). Dans ce cas, les interruptions sont ignorées par le processeur jusquà ce que celui-ci démasque les interruptions par le biais dune seconde instruction machine (instruction « sti »).
Lorsquune IRQ i est levée au niveau matériel, cest la fonction IRQn_interrupt() qui est appelée, avec n le point dentrée dans la table des vecteurs dinterruptions (n = i + 32, vu que les linterruption matérielle sont numérotées à partir de 32 dans la table des vecteurs dinterruption).
Cette fonction commence par effectuer une sauvegarde complémentaire des registres généraux sur la pile noyau. A lissue de cette sauvegarde, le gestionnaire de linterruption invoque le traitement même de tinterruption (fonction do_IRQ( )). Comme linterruption, si elle est partagée, peut avoir été émise par plusieurs périphériques différents, la routine dinterruption (appelée parfois « traitant dinterruption ») do_IRQ() contient plusieurs routines de services (appelées ISR : interrupt service routines), spécifiques à chacun des périphériques concernés. Ces routines sont exécutées les unes à la suite des autres de façon à déterminer quel est le périphérique initiateur de linterruption. LISR concernée est alors totalement exécutée.
Les actions exécutées par une routine de service sont réparties selon 3 catégories:
les actions critiques qui doivent être exécutées immédiatement, interruptions masquées;
les actions non critiques qui peuvent être exécutées rapidement, interruptions démasquées;
les actions pouvant être reportées. Ce sont des actions dont la durée dexécution est longue et dont la réalisation nest pas critique pour le fonctionnement du noyau. Pour cette raison, le système Linux choisit de reporter leur exécution en dehors de la routine de service, dans des fonctions appelées les « parties basses » (bottom halves) qui seront exécutées plus tard, juste avant de revenir en mode utilisateur. LISR se contente dactiver ces parties basses pour demander leur exécution ultérieure (fonction mark_bh()).
Une fois les routines de services exécutées, le contexte sauvegardé au moment de la prise en compte de linterruption est restitué, dune part par le gestionnaire de linterruption matérielle (restitution des registres généraux sauvegardés lors de son appel), dautre part par lunité de contrôle du processeur (restitution du registre détat et du compteur ordinal). Si le niveau dimbrication du noyau est égal à 1, alors le mode dexécution bascule au niveau utilisateur et le programme utilisateur reprend son exécution. Avant ce retour en mode utilisateur, les parties basses activées par les routines de services sont exécutées.
Gestion des exceptions (trappes)
Loccurrence dune trappe est levée lorsque le CPU rencontre une situation anormale en cours dexécution, comme, par exemple, une division par 0 (trappe 0 sous Linux), un débordement (trappe 4 sous Linux), lutilisation dune instruction interdite (trappe 6 sous Linux) ou encore, un accès mémoire interdit (trappe 10 sous Linux).
Le traitement dune trappe est très comparable à celui des interruptions, évoqué au paragraphe précédent. La différence essentielle réside dans le fait que loccurrence dune trappe est synchrone avec lexécution du programme.
Aussi, de la même manière que pour les interruptions, une trappe est caractérisée par un numéro et un gestionnaire de trappe lui est associé, dont ladresse en mémoire est rangée dans la table des vecteurs dinterruptions.
Le traitement associé à la trappe consiste à envoyer un signal au processus fautif (fonction do_handler_name() où « handler_name » est le nom de lexception). La prise en compte de ce signal provoque par défaut larrêt du programme en cours dexécution, mais le processus a la possibilité de spécifier un traitement particulier qui remplace alors le traitement par défaut (nous verrons ce point ultérieurement lorsque nous parlerons des signaux). Dans le cas par défaut, une image mémoire de lexécution arrêtée est créée afin de pouvoir être utilisée par le programmeur, pour comprendre le problème survenu (cette image mémoire du programme fautif est stocké dans un fichier coredump).
Une trappe particulière est celle liée à la gestion des défauts de pages en mémoire centrale (trappe 14 sous Linux). Son occurrence nentraîne pas la terminaison du processus associé, mais permet le chargement à la demande des pages constituant lespace dadressage du processus (nous y reviendrons dans le chapitre traitant de la mémoire).
Exécution dune fonction du système
Lappel à une fonction du système peut être réalisé soit depuis un programme utilisateur par le biais dun appel de procédure qualifié dans ce cas dappel système, soit par le biais dune commande (lancée depuis le prompt shell). La commande est prise en compte par un programme particulier, linterpréteur de commandes, qui à son tour invoque la fonction système correspondante.
Linvocation dune fonction système se traduit par la levée dune interruption logicielle particulière, entraînant un changement de mode dexécution et le branchement à ladresse de la fonction.
Plus précisément, lensemble des appels système disponibles est regroupé dans une ou plusieurs bibliothèques, avec lesquelles léditeur de liens fait la liaison. Chaque fonction de la bibliothèque encore appelée routine denveloppe comprend une instruction permettant le changement de mode dexécution, ainsi que des instructions assurant le passage des paramètres depuis le mode utilisateur vers le mode superviseur. Souvent, des registres généraux prédéfinis du processeur servent à ce transfert de paramètres. Enfin, la fonction lève une trappe en passant au système un numéro spécifique à la routine appelée.
Comme nous lavons déjà vu, chaque fonction système est identifiée par un numéro.
Le système cherche dans une table ladresse de la routine identifiée par le numéro de la fonction, et se branche sur son code. A la fin de lexécution de la routine, la fonction de la bibliothèque retourne les résultats de lexécution via les registres réservés à cet effet, puis restaure le contexte du programme utilisateur.
Sous le système Linux, la trappe levée par la routine denveloppe pour lexécution dune fonction du système porte le numéro 128 (0x80 en hexadécimal). Les paramètres, dont le nombre ne doit pas être supérieur à 5, sont passés via les registres %CBX, %CCX, %CDX, %ESI, et %CDI du processeur x86. Le numéro de la routine système concernée est passé via le registre %EAX (laccumulateur). Ce numéro sert dindex pour le gestionnaire des appels système dans une table des appels système, la table sys_call_table, comportant 256 entrées. Chaque entrée de la table contient ladresse de la routine système correspondant à Iappel système demandé. Le gestionnaire dappel système renvoie via le registre %EAX un code retour qui coïncide à une situation derreur si sa valeur est comprise entre -1 et -125. Dans ce cas, cette valeur est placée dans une variable globale errno et le registre %EAX est rempli avec la valeur -1, ce qui indique pour le processus utilisateur une situation déchec dans la réalisation de lappel système. La cause de lerreur peut être alors consultée dans la variable errno à laide dun ensemble de fonctions et variables prédéfinies (Cf. man) :
#include
#include
#include
void perror(const char *s);
char *strerror(int errnum);
La fonction perror() affiche un message constitué de deux parties, dune part, la chaîne spécifiée par le paramètre s, dautre part, le message derreur correspondant à la valeur de la variable errno.
La fonction strerror() retourne le message derreur correspondant à la valeur de lerreur spécifiée par largument errnum.
Lensemble des valeurs admises pour la variable errno est spécifié dans le fichier « errno.h ».
Imbrication de la prise en compte des interruptions
Comme déjà évoqué, le noyau Linux est un noyau réentrant, cest à dire quà un instant t donné, plusieurs exécutions en mode noyau peuvent exister, une seule étant active. En effet, le noyau autorise un gestionnaire dinterruption à interrompre lexécution dun autre gestionnaire dinterruption. Lexécution du gestionnaire est suspendue, son contexte sauvegardé sur la pile noyau, et lexécution est reprise lorsque lexécution du gestionnaire survenue entre-temps est achevée. De ce fait, les exécutions au sein du noyau peuvent être arbitrairement imbriquées.
Le noyau maintient une valeur de niveau dimbrication, qui indique la profondeur dimbrication courante dans les exécutions du noyau. Le retour en mode utilisateur nest effectué que lorsque ce niveau dimbrication est à 1. Il est précédé de lexécution des parties basses activées par lensemble des routines de services exécutées. Plus précisément :
un gestionnaire dinterruption peut interrompre un gestionnaire de trappe ou un autre gestionnaire dinterruption ;
par contre, un gestionnaire de trappe ne peut jamais interrompre un gestionnaire dinterruption.
Le « multitâche » en pratique
Les processus
Nous avons survolé dans les précédents chapitres les mécanismes dinterruption et de commutation de contexte, qui sont les outils qui permettent la mise en place de « multitâche » (temps partagé, ou pseudo-parallélisme) sur un système mono-processeur.
La notion de « tâche » étant restée floue, nous allons essayer de la préciser. Historiquement, sous Unix (puis sous Linux), une tâche sest appelée « processus ».
Définition : un processus est en quelque un programme (du code) qui sexécute en mémoire. Il est protégé par un certains nombre de mécanismes système (que nous verrons dans ce cours), afin quaucun autre processus ne puisse venir directement le perturber (par exemple, un processus ne peut accéder aux données, au code, à la pile à lexécution, etc. dautres processus).
Voici, sous Linux, les éléments qui sont propre à chaque processus :
Gestion des tâchesGestion de la mémoireGestion de fichiersEtat des registres du CPUPointeur vers un segment texte (constantes, données dinitialisation des variables, etc.)Répertoire racine (root)Compteur ordinalPointeur vers un segment de données (où sont stockées les variables) Répertoire de travail (current directory)Etat du processusPointeur vers un segment de la pileDescripteurs de fichiers ouvertsPointeur de la pileID utilisateurEtat du processusID groupePrioritéParamètres dordonnancementIdentifiant du processus (PID)PID du processus parentGroupe du processusEtat des signauxHeure de lancement du processusTemps de CPU utiliséTemps de traitement du filsHeure de la prochaine alerteLes plus curieux (et les plus courageux, la lecture nétant pas aisée de prime abord) pourront regarder le type « struct task_struct » défini sous Linux dans le fichier « /usr/include/linux/sched.h » pour stocker ces données.
Ce quil faut retenir de ce tableau : un processus nest pas simplement du code et un lieu de stockage des données, mais il contient aussi un grand nombre dinformations utiles au système dexploitation et à lui-même pour gérer la sécurité, la quantité de mémoire allouée, les entrées/sorties, etc.
Dans un environnement multitâche, un processus est caractérisé par son état. En effet, il peut-être :
en cours déxécution (état « élu »),
en attende de temps CPU pour être exécuté à nouveau (état « prêt »),
enfin, le processus peut être en attente dune ressource - mémoire, fichier, etc. (état « bloqué ».
Le diagramme des états dun processus peut se matérialiser par le diagramme détats suivant :
EMBED PowerPoint.Slide.8
Lors du démarrage, un mécanisme lit le contenu du fichier exécutable. Il regarde les deux premiers octets du fichier (qui forment un nombre appelé « Magic Number »). Sil détecte quil ne sagit pas dun script (script shell, perl, etc.) mais dun fichier exécutable en binaire, il place le contenu du code et des données dinitialisation en mémoire, alloue de la mémoire pour les données, la pile, etc. Ce mécanisme sappelle le « chargeur ».
Tout système dexploitation multitâche définit une structure pour gérer les processus : il sagit du PCB (Process Control Block, i.e. bloc de contrôle de processus). Le PCB contient un identificateur unique pour chaque processus (PID pour Process ID), létat courant du processus (élu, prêt, bloqué), les informations liées à lordonnancement du processus, etc. Le PCB sous Linux correspond à la structure « struct task_struct » déjà évoquée ci-dessus. Lensemble de tous les blocs de contrôle sont stockés dans une table des processus, nommée PT (process table) dans la littérature anglaise.
Dans le noyau Linux, cette table était définie dans le fichier « kernel/sched.c »), et sappelle « task[NRTASK] ». Chaque élément de ce tableau est un pointeur qui pointe vers un BCB de type « struct task_struct ».
Chaque processus, identifié par son PID, appartient à un groupe de processus. Un groupe de processus est identifié par un identifiant : le GID (Group ID). En pratique, deux processus sont dans le même groupe de processus sils ont été lancés par le même processus parent. Le numéro du processus parent est noté PPID (Parent PID).
Création dun processus sous Linux
La fonction fork()
La création dun processus sous Linux est faite avec la fonction « fork() » :
#include
pid_t fork(void);
Lappel de la fonction système « fork() » crée un nouveau processus, qui sera lexacte copie du processus appelant. Le processus appelant est appelé le processus parent. Le processus nouvellement créé est appelé le processus fils. La fonction fork() retourne au père le numéro de PID du fils qui vient dêtre créé, et retourne la valeur 0 au fils.
Ce mécanisme peut se schématiser le la façon suivante :
EMBED PowerPoint.Slide.8
Lors de lexécution de la fonction fork(), si les ressources noyaux sont disponibles, le système effectue les opérations suivantes :
le système alloue un bloc de contrôle (PCB) et une pile noyau pour le nouveau processus, et trouve une entrée libre dans la table des processus pour ce nouveau bloc de contrôle ;
le système copie les informations contenues dans le bloc de contrôle du père dans celui du fils sauf les informations concernant le PID, le PPID et les chaînages vers les fils et les frères ;
le système alloue un PID unique au nouveau processus ;
le système associe au processus fils le contexte mémoire du processus parent (cest-à-dire le code, les données, et la pile) ;
létat du nouveau processus est mis à la valeur « TASK_RUNNING » ;
le système retourne au processus père le PID du nouveau processus ainsi créé, et au nouveau processus (le fils), la valeur 0.
Ainsi, lors de cette création, le processus fils hérite de tous les attributs de son père sauf :
son propre identificateur,
et tout les compteurs de temps dexécution (qui sont remis à 0).
Sil ny a plus assez de ressource pour créer un nouveau processus, la fonction fork() retourne une valeur négative. La variable globale errno donne la raison de cette erreur (errno vaut EAGAIN sil ny a plus assez de place dans la table des processus, et ENOMEM sil ny a plus assez de mémoire).
Les fonctions de gestion des identifiants de processus
Le système propose un certain nombre de fonctions pour gérer les numéros de processus :
#include
#include
pid_t getpid(void); /* retourne le PID du processus courant */
pid_t getppid(void);/* retourne le PID du processus parent */
uid_t getuid(void); /* retourne lUID du processus */
gid_t getgid(void); /* retourne le GID du processus */
A noter que lUID, ainsi que le GID sont égaux pour le père et pour le fils juste après lappel à la fonction fork().
Optimisation de fork() : le « copy on write »
Comme nous venons de le voir, lappel à la fonction fork() doit normalement engendrer :
la duplication du code,
la duplication de la pile à lexécution,
la duplication du « tas » (heap), cest à dire des la zone mémoire composée du :
le segment texte (constantes, données dinitialisation des variables, etc.)
segment de données (où sont stockées les variables), etc.
Sil devait être exécuté entièrement, lensemble de ce travail serait très coûteux en terme de CPU (recopie de mémoire). Or, en pratique, il est assez fréquent que le processus père et le processus fils accèdent aux données en lecture seule, et que celles-ci ne sont pas modifiées avant le fin du processus fils. Dans ce cas, la recopie aura été totalement inutile : le père et le fils auraient pu partager les mêmes données.
Aussi, en pratique, seule la pile à lexécution est dupliquée lors dun fork(). Le code et les autres segments de données ne sont pas dupliqués. Par un mécanisme de « virtualisation » de la mémoire physique (qui sera étudiée dans un prochain chapitre), la mémoire physique allouée au fils est exactement la même que celle allouée au père. Et cest uniquement lors de la première modification (écriture) dune valeur dans une zone mémoire que celle-ci est dupliquée (allocation mémoire puis recopie des données). Ce mécanisme sappelle « copy on write » (recopie uniquement lors dune écriture) :
EMBED PowerPoint.Slide.8 => EMBED PowerPoint.Slide.8
=> EMBED PowerPoint.Slide.8
Les processus zombies (et comment les éviter)
Il existe une erreur classique dans le développement de programme Unix/Linux gérant plusieurs processus : un processus père qui crée des fils, et qui ne s'occupe pas ensuite d'acquérir leur code de fin (cest à dire la valeur retournée par la fonction exit(), ou retournée par le return() de la fonction main()).
Ces processus fils restent dans un état « fin dexécution du programme », jusquà ce que le père sinquiète du code retour du processus fils. On parle alors de processus « zombie ».
A noter que les processus zombies ne peuvent pas être supprimés par les méthodes classiques (y compris pour les utilisateurs privilégiés). Les ressources (mémoire, fichiers, etc.) son libérées, mais le processus prend encore une place dans la table des processus. Comme cette dernière nest pas extensible, le système se retrouve alors encombré de processus inactifs (ils ont comme état la valeur « TASK_ZOMBIE »).
Normalement, les processus zombies sont « purgés » à la mort du processus père. Si cette purge se passe mal, seul un redémarrage système sera efficace.
Plusieurs méthodes permettent de les éviter (on parle de synchronisation père/fils) :
Utilisation des fonctions wait() et waitpid() :
#include
#include
pid_t wait(int *status);
pid_t waitpid(pid_t pid, int *status, int options);
extrait de « man wait » ou de « man waitpid » : 0 : attendre la fin du processus numéro pid.
La valeur de l'argument option options est un OU binaire entre les constantes suivantes :
WNOHANG : ne pas bloquer si aucun fils ne s'est terminé.
WUNTRACED : recevoir l'information concernant également les fils bloqués si on ne l'a pas encore reçue.
Si status est non NULL, wait() et waitpid() y stockent l'information sur la terminaison du fils.
Cette information peut être analysée avec les macros suivantes, qui réclament en argument le buffer status (un int, et non pas un pointeur sur ce buffer) :
WIFEXITED(status) : non nul si le fils s'est terminé normalement
WEXITSTATUS(status) : donne le code de retour tel qu'il a été mentionné dans l'appel exit() ou dans le return de la routine main. Cette macro ne peut être évaluée que si WIFEXITED est non nul.
WIFSIGNALED(status) : indique que le fils s'est terminé à cause d'un signal non intercepté.
WTERMSIG(status) : donne le nombre de signaux qui ont causé la fin du fils. Cette macro ne peut être évaluée que si WIFSIGNALED est non nul.
WIFSTOPPED(status) : indique que le fils est actuellement arrêté. Cette macro n'a de sens que si l'on a effectué l'appel avec l'option WUNTRACED.
WSTOPSIG(status) : donne le nombre de signaux qui ont causé l'arrêt du fils. Cette macro ne peut être évaluée que si WIFSTOPPED est non nul.
Valeur Renvoyée : en cas de réussite, le PID du fils qui s'est terminé est renvoyé, en cas d'echec -1 est renvoyé et errno contient le code d'erreur :
ECHILD : Le processus indiqué par pid n'existe pas, ou n'est pas un fils du processus appelant (Ceci peut arriver pour son propre fils si l'action de SIGCHLD est placé sur SIG_IGN, voir également le passage de la section NOTES concernant les threads).
EINVAL : L'argument options est invalide.
ERESTARTSYS : WNOHANG n'est pas indiqué, et un signal à intercepter ou SIGCHLD a été reçu. Cette erreur est renvoyée par l'appel système. La routine de bibliothèque d'interface n'est pas autorisée à renvoyer ERESTARTSYS, mais renverra EINTR.
>>
Le problème de la fonction wait(), et de la fonction waitpid() dans son fonctionnement par défaut est quelles sont bloquantes (suite à leur appel, le programme sarrête jusquà ce quun fils se termine). Une première solution à utiliser waitpid() en mettant le paramètre « option » à « WNOHANG ». Mais comme nous ne savons pas à quel moment un fils se termine, il faut lancer régulièrement cette fonction waitpid(). On dit alors que nous faisons du « polling ». Ce mode de fonctionnement, qui consomme du CPU et des appels systèmes nest pas optimum. Une solution bien plus esthétique consiste à nappeler waitpid()que lorsque nous sommes sûr quun processus fils est terminé. Nous y reviendrons très largement dans le chapitre prévu à cet effet, mais vous pouvez noter dès à présent que le père reçoit un « signal » du système dexploitation lorsquun de ses fils se termine. Ce signal peut être « intercepté » à laide de la fonction signal(). Voici un extrait de la documentation de cette fonction :
#include
void (*signal(int signum, void (*handler)(int)))(int);
L'appel-système signal() installe un nouveau gestionnaire pour le signal numéro signum. Le gestionnaire de signal est handler (NDLR : cest à dire le pointeur vers une fonction) qui peut être soit une fonction spécifique de l'utilisateur, soit l'une des constantes SIG_IGN ou SIG_DFL.
Lors de l'arrivée d'un signal correspondant au numéro signum, les évènements suivants se produisent :
- si le gestionnaire correspondant est configuré avec SIG_IGN, le signal est ignoré.
- si le gestionnaire vaut SIG_DFL, l'action par défaut pour le signal est entreprise, comme décrit dans le manuel signal(7).
- finalement, si le gestionnaire est dirigé vers une fonction handler(), alors tout d'abord, le gestionnaire est re-configuré à SIG_DFL, ou le signal est bloqué, puis handler() est appelé avec l'argument signum.
Utiliser une fonction comme gestionnaire de signal est appelé "intercepter - ou capturer - le signal". Les signaux SIGKILL et SIGSTOP ne peuvent ni être ignoré, ni être interceptés.
Valeur Renvoyée : signal() renvoie la valeur précédente du gestionnaire de signaux, ou SIG_ERR en cas d'erreur.
>>
En pratique, lorsquun fils se termine, le père reçoit un signal de type « SIGCHLD ». Lidée consiste à intercepter ce signal « SIGCHLD » lorsque le fils se termine, et seulement à ce moment là, lancer une des fonctions bloquante waitpid() en mode non bloquant. Voici un squelette dun tel programme :
#include
#include #include
[...]
void fin_d_un_enfant(int num_signal){ /* On ne lutilise pas, mais notez quà ce */
/* stade, le paramètre num_signal vaut */
/* obligatoirement la valeur SIGCHLD (vu que */
/* cette fonction ne sert quà intercepter */
/* le signal SIGCHLD). */
/* Nettoyage des processus fils */
/* Comme plusieurs fils peuvent se terminer au */
/* même instant, nous ne savons pas si la */
/* fonction est appelée suite à la fin dun ou de */
/* plusieurs fils. Il faut lancer waitpid() */
/* plusieurs fois (à laide dune boucle while), */
/* tant quil reste des zombies à faire */
/* disparaître : */ while(waitpid(-1, NULL, WNOHANG) > 0);
/* on repositionne la présente fonction */
/* comme vecteur dinterception (handler) */
/* pour le prochain fils qui viendra à se */
/* terminer */
signal(SIGCHLD, fin_d_un_enfant);}
[...]
int main(int argc, char *argv[]){ ... signal(SIGCHLD, fin_d_un_enfant); ... if (fork() == 0)
{
/* Code du fils... */
/* Pour le fils, on na pas à intercepter */
/* le signe SIGCHLD => on positionne le */
/* handler par défaut. */
signal(SIGCHLD, SIG_DFL);
[...] /* suite du code du fils */
}
else {
/* Le code du père... */
[...]
}}
Les fonctions de recouvrement
Lorsque nous appelons la fonction fork(), le code du processus fils est exactement le même que celui du processus parent. Or, nous pouvons être amenés à avoir à exécuter un autre programme dans le processus fils.
Un ensemble de fonctions, dites « fonctions de recouvrement » (ou primitives de recouvrement), permettent de charger un autre programme à la place de celui en cours. Voici la liste de ces fonctions sous Linux :
execl(),
execlp(),
execle(),
execv(),
execvp(),
execve().
Le manuel Linux nous permet de comprendre le fonctionnement de ces fonctions :
>
Extrais du manuel de execve() :
>
La primitive pthread_exit(void *ret) met fin au thread qui lexécute. Elle retourne le paramètre ret qui peut être récupéré par un autre thread effectuant pour sa part un appel à la primitive « pthread_join(pthread_t thread, void **retour) » où thread correspond à lidentifiant du thread attendu, et retour correspond à la valeur ret retournée lors de la terminaison. Lexécution du processus qui effectue un appel à la fonction « int pthread_join(pthread_t thread, void **ret) » est suspendue jusquà ce que le thread attendu se soit achevé. Le paramètre *ret contient la valeur passée par le thread au moment de lexécution de la primitive pthread_exit(). Voici les extraits des pages du manuel de pthread_exit() et de pthread_join() :
>
Chaque thread est dote des attributs suivants:
ladresse de départ et la taille de la pile qui lui est associée ;
la politique dordonnancement qui lui est associée (Cf. prochain chapitre) ;
la priorité qui lui est associée ;
son attachement ou son détachement. Un thread détaché se termine immédiatement sans pouvoir être pris en compte par un pthread_join().
Lors de la création dun nouveau thread par un appel à la primitive pthread_create(), les attributs de ce thread sont fixés par lintermédiaire de largument pthread_attr_t *attr. Si les attributs par défaut sont suffisants, ce paramètre est mis à NULL. Sinon, il faut au préalable initialiser une structure de type pthread_attr_t, en invoquant la primitive pthread_attr_init(), puis modifier chacun des attributs en utilisant les fonctions pthread_attrgetXXX() et pthread_attr_setXXX() qui permettent respectivement de consulter et modifier lattribut XXX.
A noter que limplémentation des threads sous Linux est réalisée au niveau du noyau, en sappuyant sur la routine système « clone() ».
Lordonnancement (le « scheduler »)
Rappels sur la commutation de contexte
Un système dexploitation multitâche est capable de choisir un programme à exécuter parmi tous ceux éligibles (qui ont besoin de CPU). Cest le travail de lordonnanceur (scheduler en anglais). Lorsque cet ordonnanceur a choisi quel programme il va exécuter, il programme lhorloge afin que cette dernière lève une interruption matérielle au bout dun temps donné. Puis, il lance lexécution du programme de lutilisateur (cest la réquisition du CPU par le processus utilisateur).
Si, durant son exécution, le programme utilisateur na pas eu besoin de faire appel à une fonction système, linterruption matérielle est levée par lhorloge. Le processus a épuisé son temps de CPU, et passe alors dans un état « prêt ». Regardons plus en détail ce quil se passe lorsque linterruption est levée (on dit quil y a préemption) :
toutes les interruptions matérielles commencent par sauvegarder les registres dans une entrée de la table des processus du processus en cours ;
ensuite, linformation placée sur la pile par linterruption est supprimée, et le pointeur de pile est défini de manière à pointer vers une pile temporaire utilisée par le gestionnaire de processus. Des actions telles que la sauvegarde des registres et le positionnement du pointeur de pile ne peuvent pas être exprimées dans des langages de haut niveau comme le C. Elles sont donc accomplies par une petite routine en langage assembleur (propre à chaque CPU). Le plus souvent, la même routine sert à toutes les interruptions dans la mesure où la sauvegarde des registres est toujours une tâche identique, quelle que soit la cause de linterruption ;
lorsque la routine a terminé de sexécuter, elle appelle une procédure C pour prendre en charge le reste des tâches à accomplir pour ce type spécifique dinterruption ;
lorsque lordonnanceur a terminé son travail - au cours duquel il pourra très bien avoir fait passer certains processus en état prêt -, il est appelé pour exécuter le prochain processus. Ensuite, le contrôle retombe entre les mains du code assembleur, qui charge les registres et les « mappages » mémoire (Cf. prochains chapitres) pour le processus désormais actif et commence son exécution.
Voici le résumé des tâches que le système dexploitation accomplit à son niveau le plus bas lorsquune interruption a lieu :
Le matériel place dans la pile le compteur ordinal, etc. ;
Le matériel charge un nouveau compteur ordinal à partir du vecteur dinterruptions ;
La procédure en langage assembleur sauvegarde les registres ;
La procédure en langage assembleur définit une nouvelle pile ;
Le service dinterruption en C sexécute (généralement pour lire des entrées et les placer dans le tampon) ;
Lordonnanceur décide du prochain processus à exécuter ;
La procédure C retourne au code assembleur ;
La procédure en langage assembleur démarre le nouveau processus actif.
Nous allons voir comment cet ordonnanceur fonctionne, cest à dire quelles sont les différentes politiques possibles pour choisir un processus parmi tous ceux qui sont éligibles.
La politique du « premier arrivé, premier servi »
Cest lordonnanceur le plus simple à programmer. Il consiste à mettre en place une simple file dattente, et à lancer les processus les uns à la suite des autres, dans leur ordre darrivée. Il ny a pas de préemption : chaque processus sexécute jusquà ce quil soit terminé, ou jusquà ce quil fasse appel à une primitive système.
Le grand inconvénient de cette solution est que les processus qui ont les plus petits temps dexécution (beaucoup dappel système par exemple) sont pénalisés par les processus qui consomment simplement du CPU (longs calculs par exemple).
La politique par priorité
Cette fois ci, chaque processus possède une priorité (priorité constante définie au départ). Avec cette politique, le programme qui va faire la réquisition du CPU est choisi comme étant le programme dans létat « prêt » qui aura la plus grande priorité. Si plusieurs programmes éligibles on la même priorité, une file dattente est gérée.
Il existe une variante où une préemption est faite à un processus sitôt quun processus plus prioritaire passe à létat « prêt ».
Le gros inconvénient de cette méthode est quelle engendre des « famines » chez les processus ayant la priorité la plus faible : les processus ayant la priorité la plus élevée consomment du CPU, au détriment des processus les moins prioritaires, qui peuvent se trouver dans une situation où ils ne sont plus jamais lancés.
Une des solutions à ce problème de famine (variantes) est de faire baisser dynamiquement la priorité des processus quand ils viennent davoir du CPU.
La politique du tourniquet (round robin)
Cest la solution la plus souvent mise en place dans les système en « temps partagé ». Ici, le temps est découpé tranches (on parle de « quantum de temps », de lordre de 10 à 100 ms. selon les systèmes).
Lorsquun processus est élu, il sexécute durant un quantum de temps, avant dêtre préempté (sauf sil a lancé une fonction système entre temps).
Une file des processus permet de lancer les processus les uns à la suite des autres (comme dans la politique du « premier arrivé, premier servi »), mais cette fois-ci, pour un temps donné.
La recherche de la valeur du quantum de temps optimum est très importante : sil est trop grand, limpression de temps partagé disparaît. Sil est trop petit, il y aura beaucoup de commutation de contexte, ce qui réduit les performances.
Les politiques dordonnancement sous Linux
Trois politiques dordonnancement différentes sont mises en uvre sous Linux :
les deux premières, appelées « SCHED_FIFO » et « SCHED_RR » sont des algorithmes dit « temps-réels ». Les processus identifiés comme régis par ces deux politiques temps-réel sont toujours prioritaires ;
la troisième, appelée « SCHED_OTHER » est utilisée par les processus « classiques ».
La politique dordonnancement est indiquée dans le champs « policy » du bloc de contrôle de processus (PCB, de type « struct task_struct » sous Linux comme déjà évoqué).
Lordonnancement réalisé par le noyau est découpé en périodes. Au début de chaque période, le système calcule les quantums de temps attribués à chaque processus, cest-à-dire, le nombre de « ticks » dhorloge durant lequel le processus peut sexécuter. Une période prend fin lorsque lensemble des processus initialisés sur cette période a achevé son quantum. Le lecteur aura noté quavec cette méthode, tous les processus naura pas nauront pas nécessairement le même temps de CPU. Les algorithmes mis en place peuvent se résumer ainsi :
Ordonnancement des processus temps-réel : les processus temps réel sont qualifiés par une priorité fixe dont la valeur évolue entre 1 et 99 (paramètre rt_priority du bloc de contrôle du processus), et sont ordonnancés soit selon la politique « SCHED_FIFO », soit selon la politique « SCHED_RR » :
La politique « SCHED_FIFO » est une politique préemptive qui offre un service de type « premier arrivé, premier servi » entre processus de même priorité. A un instant t, le processus « SCHED_FIFO » de plus haute priorité le plus âgé est élu. Ce processus poursuit son exécution, soit jusquà ce quil se termine, soit jusquà ce quil soit préempté par un processus temps-réel plus prioritaire devenu prêt. Dans ce dernier cas, le processus préempté réintègre la tête de file correspondant à son niveau de priorité ;
La politique « SCHED_RR » est une politique du tourniquet à quantum de temps entre processus de même priorité. Dans ce cas, le processus élu est encore le processus « SCHED_RR » de plus forte priorité. Mais ce processus ne peut poursuivre son exécution au-delà du quantum de temps qui lui a été attribué. Le quantum de temps (paramètre counter du bloc de contrôle du processus) correspond à un certain nombre de « ticks » horloge. Une fois ce quantum expiré, le processus élu est préempté et il réintègre la queue de la file correspondant à son niveau de priorité. Le processeur est alors alloué à un autre processus temps-reèl, qui est le processus temps réel le plus prioritaire ;
Ordonnancement des processus classiques : Les processus classiques sont qualifiés par une priorité dynamique qui varie en fonction de lutilisation faite par le processus des ressources de la machine et notamment du processeur. Cette priorité dynamique représente le quantum alloué au processus, cest-à-dire le nombre de « ticks » horloge dont il peut disposer pour sexécuter. Ainsi, un processus élu voit sa priorité initiale décroître en fonction du temps processeur dont il a disposé. Ainsi, il devient moins prioritaire que les processus qui ne se sont pas encore exécutés. Ce principe, appelé extinction de priorité, évite les problèmes de famine des processus de petite priorité.
La politique « SCHED_OTHER » décrite ici correspond à la politique dordonnancement des systèmes Unix classiques. Plus précisément, la priorité dynamique dun processus est égale à la somme entre un quantum de base (paramètre « priority » du bloc de contrôle du processus) et un nombre de « ticks » horloge restants au processus sur la période dordonnancement courante (paramètre « counter » du bloc de contrôle du processus). Un processus fils hérite à sa création du quantum de base de son père et de la moitié du nombre de ticks horloge restant de son père.
Le processus possède ainsi une priorité égale à la somme entre les champs « priority » et « counter » de son bloc de contrôle, et sexécute au plus durant un quantum de temps égal à la valeur de son champ « counter ».
La fonction dordonnancement Linux (schedule()) gère deux types de files :
La file des processus actifs (runqueue), qui relie entre eux les blocs de contrôle des processus à létat « prêts » (état « TASK_RUNNING ») ;
Les files des processus en attente (wait queues), qui relient les PCB des processus bloqués (états « TASK_INTERRUPTIBLE » et « TASK_UNINTERRUPTIBLE ») dans lattente dun même événement. Il y a autant de « wait queues » (files dattentes) quil y a dévénements sur lesquels un processus peut être en attente (ouverture dun fichier, attente de lecture dans une pile de protocole réseau, etc.).
Létat dun processus sous Linux est positionné dans le champ « state » du PCB, et peut prendre les valeurs suivantes (nous reviendrons sur certaines de ces valeurs dans les prochains chapitres, comme lorsque nous traiterons les signaux) :
#define TASK_RUNNING 0
#define TASK_INTERRUPTIBLE 1
#define TASK_UNINTERRUPTIBLE 2
#define TASK_ZOMBIE 4
#define TASK_STOPPED 8
#define TASK_EXCLUSIVE 32
Les plus curieux qui sintéressent au fonctionnement de cette fonction schedule() pourront regarder comment fonctionnent deux fonctions quelle appelle :
la fonction goodness(), qui effectue le choix du prochain processus à exécuter,
la fonction switch_to(), qui est la macro qui réalise la commutation de contexte. Cette fonction sauvegarde le contexte du processus courant, commute lexécution du noyau sur la pile noyau du processus à élire, puis restaure le contexte du processus à élire.
Le bilan : le principal inconvénient de lordonnanceur Linux vient de la prise en compte des processus temps-réel. Un programme temps réel mal intentionné peut facilement monopoliser les ressources de la machine et provoquer une famine.
En revanche, si on écarte le cas des processus temps-réel, le risque de famine est inexistant : chaque processus se voit élu dans des délais acceptables grâce au principe de vieillissement. Et comme l'ordonnancement se fait aussi au changement d'état du processus courant, on tire partie des blocages d'un processus pour éviter les temps morts. Le processeur est utilisé de manière optimale.
Le démarrage dun système Linux
Le chargeur de noyau
A lallumage dun ordinateur de type PC, le tout premier programme à être lancé est en réalité le BIOS (Basic Input Output System). Il sagit de code contenant un certain nombre de routines, contenues dans une mémoire morte (ROM) ou de la mémoire « flash », située sur la carte mère. Ces routines servent à faire des opérations basiques liées aux entrées/sorties.
Celui-ci va chercher au début du 1er disque dur afin d'y trouver un chargeur (en réalité, aujourdhui, le BIOS sait aussi aller chercher ce chargeur sur un CD-Rom, une clé USB, voire sur le réseau). Ce chargeur est un petit programme dont le but sera de lancer le système d'exploitation complet. Les chargeurs récents (GRUB, Lilo, etc.) sont capables de laisser à l'utilisateur le choix du système à lancer (on parlera de multiboot). Plusieurs OS peuvent alors cohabiter sur une même machine.
Ce chargeur va ensuite charger le MBR (master boot record), situé dans les premiers secteurs du disque considéré. Ce MBR contient la « table des partitions » (nous verrons lutilité de cette table dans le chapitre sur la gestion de fichiers), ainsi quun second chargeur, dont le rôle sera de charger en mémoire et démarrer le noyau du système dexploitation. A noter que des options peuvent être passées en paramètre au noyau, comme par exemple (liste non exhaustive, loin sen faut) :
vga=XXX : sert à changer la résolution d'écran utilisée pendant le démarrage. Utile si celle par défaut n'est pas reconnue par la carte graphique.
no-scroll : permet de désactiver le défilement du texte sur l'écran. A utiliser notamment avec des terminaux braille pour lesquels le défilement peut poser problème.
noapic : désactive le mécanisme de partage dIRQ par plusieurs périphériques (qui pose parfois des problèmes avec certains dentre eux) ;
mem=XXX : permet d'indiquer la valeur de mémoire vive présente sur la machine pour le cas ou l'auto-detection échouerait. On peut utiliser des lettres pour cette taille. Par exemple 512M désignera 512 Méga-octets de mémoire ;
init=XXX : permet d'indiquer de manière explicite quel programme doit être lancé après l'initialisation du noyau (Cf. détails ci-dessous).
Le processus « init »
Une fois que le noyau a fini tout son travail d'initialisation, il lance un programme qui va devenir le père de tous les autres processus, et portera le PID (identifiant de processus) 1.
Ce programme s'appelle généralement « init ». Le noyau va en fait essayer de lancer successivement (via la fonction start_kernel()) les programmes suivants :
/sbin/init
/etc/init
/bin/init
/bin/sh
Dès qu'un de ceux-là est lancé avec succès, les autres ne sont même pas testés. Ainsi, on constate que le programme init est cherché dans différents répertoires (/sbin, /etc et finalement /bin) . S'il ne se trouve dans aucun de ceux-là, le noyau tente de lancer un shell (interpréteur de commandes), afin que l'utilisateur ait accès au système. Si cela échoue également, le noyau affiche un message d'erreur et s'arrête.
Le processus lance toujours quatre threads (kupdate et bdflush qui gèrent le cache disque, et kswap et kpiod qui gèrent la mémoire virtuelle). Puis, init va charger tous les autres processus. Le comportement d'init se configure à l'aide du fichier « /etc/inittab ». En voici un exemple d'extrait :
id:5:initdefault:
si::sysinit:/etc/rc.sysinit
l0:0:wait:/etc/rc.d/rc 0
l1:1:wait:/etc/rc.d/rc 1
l2:2:wait:/etc/rc.d/rc 2
l3:3:wait:/etc/rc.d/rc 3
l4:4:wait:/etc/rc.d/rc 4
l5:5:wait:/etc/rc.d/rc 5
l6:6:wait:/etc/rc.d/rc 6
ca::ctrlaltdel:/sbin/shutdown -t3 -r now
Chaque ligne est construite de la même manière avec les champs suivants :
Identifiant:Niveau dexécution:Action:Programme
Identifiant : une chaîne de caractères choisie par l'utilisateur (sauf dans certains cas particuliers) et permettant d'identifier la ligne.
Niveaux d'exécution : les niveaux d'exécution (détaillés dans le chapitre suivant) pour lesquels cette ligne doit être prise en compte.
Action : contient une des actions prédéfinies indiquant ce qui doit être fait. Le tableau suivant les liste.
Programme : le programme qui doit être exécuté lorsque l'on rentre dans les niveaux indiqués.
Selon l'action choisie, le comportement sera différent et certains champs peuvent être ignorés. Voici la description des actions le plus souvent utilisées :
initdefault : permet d'indiquer le niveau d'exécution à utiliser par défaut. Le champ « Niveaux d'exécution » contiendra alors une seule valeur qui sera ce niveau par défaut. Dans une telle ligne, le champ « Programme » est ignoré ;
sysinit : le champs « Programme » contient le chemin vers un exécutable qui sera lancé en tout premier par « init » (donc juste après que le noyau ait terminé ses initialisations). Dans une telle ligne, le champ « Niveaux dexécution » est ignoré ;
wait : lorsque le système passera dans le niveau d'exécution spécifié, « init » exécutera la commande indiquée puis attendra qu'elle se termine ;
respawn : semblable à « wait », si ce n'est qu'à chaque fois que le programme se termine, « init » le relancera ;
ctrlaltdel : permet d'indiquer une commande devant être exécutée lorsque l'utilisateur presse la combinaison de touches Ctrl-Alt-Suppr. Dans une telle ligne, le champ « Niveaux dexécution » est ignoré.
Les niveaux d'exécution
Sur les systèmes GNU/Linux, il existe plusieurs niveaux d'exécution possibles (appelés aussi modes d'exécution). Il s'agit en fait de modes de démarrage différents, qui diffèrent les uns des autres par les services qui y sont lancés.
La convention choisie est celle appelée « System V init » qui définit la manière dont doivent être gérés les différents niveaux. Dans le fichier « /etc/inittab » donné en exemple dans le chapitre précédent, on peut voir que c'est le programme « /etc/rc.d/rc » qui gère cela. Il est lancé avec en paramètre le numéro de niveau lorsque l'on a besoin de basculer dans un certain niveau d'exécution.
On trouve en général 7 niveaux d'exécution numérotés de 0 à 6. Leur utilisation est libre, mais traditionnellement, ils prennent la signification suivante :
0 (arrêt) : passer dans ce niveau provoque un arrêt de la machine ;
1 (maintenance, ou sigle user) : on a directement accès à un shell, mais quasiment aucun service n'est lancé. Utile pour le dépannage en cas de problème important ;
2 (multi-utilisateurs simple) : plusieurs utilisateurs peuvent se connecter en mode texte. Mais les services sont limités (souvent pas de réseau par exemple) ;
3 (multi-utilisateurs complet) : tous les services nécessaires sont démarrés et plusieurs utilisateurs peuvent se connecter en mode texte ;
4 (mode utilisateur) : généralement non employé, il peut être librement utilisé ;
5 (mode graphique) : identique au mode 3, mais les utilisateurs peuvent se connecter en mode graphique (X11) et disposer d'un gestionnaire de fenêtre (Gnome, KDE, etc.) ;
6 (redémarrage) : passer dans ce niveau entraîne un redémarrage de la machine.
Après le démarrage, le système se trouve dans le mode indiqué par « initdefault » dans « /etc/inittab ». Pour pouvoir changer, il existe un outil appelé « telinit ». Il suffit de le lancer en lui passant en paramètre le numéro du niveau souhait. Par exemple, pour redémarrer la machine, il suffit de lancer la commande suivante en étant identifié comme étant lutilisateur root :
# telinit 6
Bien qu'il y ait des conventions pour ce qui doit être fait dans chaque mode, cela peut être entièrement changé.
Pour comprendre comment influer sur ce comportement, il faut d'abord savoir ce que fait le programme « /etc/rc.d/rc » (ou un autre selon les systèmes et le contenu du fichier « inittab »).
Ce programme (souvent, un scipt shell, ou perl) gère les niveaux d'exécution en allant consulter le contenu du répertoire « /etc/rc.d/rcX.d » (ou « /etc/rcX.d » dans certain systèmes comme la distribution Debian), avec X correspondant au numéro du niveau devant être changé.
Ce script va rechercher d'abord tous les exécutables s'y trouvant et dont le nom commence par la lettre « K » (pour Kill) suivie par deux chiffres. Il lance ces programmes en leur passant en paramètre « stop ». Cela correspond aux services qui doivent être arrêté dans ce mode dexécution là. Ils sont lancés dans l'ordre croissant du nombre indiqué après le K, ce qui permet de les ordonner (démarrer tel service avant tel autre).
C'est ensuite au tour des programmes dont le nom commence par la lettre « S » (pour Start) puis également un nombre sur deux chiffres. Ils sont lancés de la même manière que les précédents si ce n'est que c'est le paramètre « start » qui est passé.
Pour illustrer ceci, voici un contenu possible d'un de ces répertoires :
# ls /etc/rc.d/rc3.d
K15httpd
K20samba
K45named
S10network
S55sshd
S99local
Dans cet exemple (qui est totalement farfelu), lorsque le système passe dans le niveau 3 (soit au démarrage si c'est celui par défaut, soit ensuite, si c'est l'utilisateur qui le demande), on arrêtera les services httpd (serveur web), samba (serveur de fichiers suivant le protocole CIF, c'est-à-dire « à la sauce Windows ») et named (serveur de noms). Ensuite seront démarrés les services network (pour la prise en charge du réseau), sshd (serveur de connexion distante sécurisée par le protocole SSL) et local (qui contient traditionnellement par convention des programmes devant être exécuté en fin de démarrage).
Comme des programmes peuvent exister dans plusieurs niveaux différents, on ne trouvera en réalité dans les répertoires « /etc[/rc.d]/rcX.d » que des liens symboliques pointant vers des fichiers situés dans le répertoire « /etc/rc.d/init.d » (ou « /etc/ init.d » sur certains systèmes). Ces fichiers sont en réalité pour la plupart des scripts shell, et le même sera lancé pour le démarrage ou l'arrêt. C'est donc de la responsabilité du script de voir s'il a été appelé avec le paramètre « start » ou le paramètre « stop », afin de savoir quelles actions entreprendre.
Sachant cela, ajouter ou supprimer des services dans un niveau donné revient uniquement à créer ou supprimer des liens symboliques. En reprenant l'exemple précédent, voici un exemple (tout aussi farfelu) de ce qui pourrait être fait :
# cd /etc/rc.d/rc3.d
# rm S55sshd
# ln -s /etc/rc.d/init.d/ftpd S40ftpd
Ces actions vont faire en sorte que dans le niveau 3, le serveur ssh ne sera plus exécuté. En revanche, un serveur ftp sera lancé. Tout cela suppose qu'un script « ftpd » soit présent dans le répertoire « /etc/rc.d/init.d/ », et qu'il fournisse le service attendu (lancer un serveur FTP). Les distributions GNU/Linux incluent ce genre de script lorsqu'un service est installé. L'utilisateur n'a donc ensuite qu'à modifier les liens symboliques.
Le squelette dun tel script situé dans le répertoire « /etc/rc.d/init.d/ » ressemble souvent à :
# Exemple de squelette de fichier /etc/init.d/xxx sur Debian :
# L'instruction 'set -e' au début du script
# pour qu'il s'interrompe dès qu'une commande
# retourne une valeur de retour non nulle (erreur).
set e
# On positionne les variables denvironnement en
# fonction du système dexploitation :
PATH=/sbin:/bin:/usr/sbin:/usr/bin
DESC="description_de_ce_que_fait_le_demon"
NAME=nom_du_demon
DAEMON=/usr/sbin/$NAME
PIDFILE=/var/run/$NAME.pid
SCRIPTNAME=/etc/init.d/$NAME
# Fonction qui démarre le service :
d_start() {
start-stop-daemon --start --quiet \
--pidfile $PIDFILE --exec $DAEMON
}
# Fonction qui arête le service :
d_stop() {
start-stop-daemon --stop --quiet \
--pidfile $PIDFILE --name $NAME
}
# Fonction qui force le service à relire sa configuration :
d_reload() {
start-stop-daemon --stop --quiet \
--pidfile $PIDFILE --name $NAME --signal 1
}
# Reste à regarder quelle est la chaîne passée en paramètre,
# et à appeler la bonne fonction :
case "$1" in
start)
echo -n "Starting $DESC: $NAME"
d_start
echo "."
;;
stop)
echo -n "Stopping $DESC: $NAME"
d_stop
echo "."
;;
reload)
echo -n "Reloading $DESC configuration..."
d_reload
echo "done."
;;
restart|force-reload)
echo -n "Restarting $DESC: $NAME"
d_stop
sleep 1
d_start
echo "."
;;
*)
echo "Usage: $SCRIPTNAME {start|stop |restart|force-reload|reload}" >&2
exit 1
;;
esac
exit 0
Larborescence des processus
Vous laurez compris, le mécanisme de multitâche sous Linux repose sur le dédoublement des processus à laide de la fonction fork(), puis le recouvrement du processus fils à laide des fonctions de recouvrement execXX(), et enfin, lutilisation de threads gérés au niveau du noyau.
La commande pstree permet de rendre compte de larborescence des processus lancés. Exemple sur une station Debian :
# pstree -A -c n
init-+-ksoftirqd/0
|-events/0
|-khelper
|-kthread-+-kblockd/0
| |-pdflush
| |-pdflush
| |-aio/0
| |-kseriod
| `-khubd
|-xbox_extsmi
|-kswapd0
|-kjournald
|-portmap
|-apache2-+-apache2
| |-apache2
| |-apache2
| `-apache2
|-named
|-freepopsd
|-spamd-+-spamd
| `-spamd
|-cron
|-klogd
|-lpd
|-master-+-qmgr
| `-pickup
|-nmbd
|-smbd---smbd
|-sshd---sshd---bash---pstree
|-syslogd
|-xinetd
|-rpc.statd
|-ntpd
|-rpc.nfsd
|-rpc.mountd
|-miniserv.pl
|-smartd
|-winbindd---winbindd
|-getty
|-getty
`-dhcpd3
De plus, la commande ps (Cf. man ps) permet dobtenir un résultat moins visuel mais plus complet sur le chaînage de lancement des processus.
Les signaux
Présentation
Comme nous lavons déjà vu précédemment, un signal est en quelque sorte un message envoyé par le noyau à un processus (suite à un événement, ou à la demande dun autre processus). Un signal ne contient pas dinformation en soit, excepté le nom du signal.
Larrivée dun signal oblige un processus à exécuter une fonction particulière liée au signal, appelée « handler de signal » ou « gestionnaire de signal ». On dit que le processus est « dérouté » ou « détourné ».
Les signaux sont parfois appelés « interruptions logicielles ». En effet, un parallèle peut-être fait entre le déroutement dun processus suite à la réception dun signal et le traitement des interruptions matérielles (même si en pratique, ces deux types dinterruptions sont différents).
Par contre, cest grâce à cette notion de signal que les trappes (ou exceptions, cest à dire gestion des évènements non désirés comme par exemple : « division par 0 », « accès par un processus dune zone mémoire où il na pas le droit daccéder », etc.) sont traitées.
Nous verrons que le noyau Linux propose un mécanisme classique denvoi et de gestion des signaux (semblable aux autres noyaux Unix), mais il fournit aussi un mécanisme de signaux « temps réels ».
Les signaux classiques
Depuis le noyau Linux version 2.2, ce système dexploitation permet de gérer 64 signaux (le signal 0, qui ne porte pas de nom, 31 signaux classiques qui ont une signification particulière et un nom particulier , et 31 signaux temps réel).
Voici la liste des 31 signaux classiques sous Linux (listing extrait du fichier « /usr/include/bits/signum.h » dune distribution Debian 3.1 :
#define SIGHUP 1 /* Hangup (POSIX). */
#define SIGINT 2 /* Interrupt (ANSI). */
#define SIGQUIT 3 /* Quit (POSIX). */
#define SIGILL 4 /* Illegal instruction (ANSI). */
#define SIGTRAP 5 /* Trace trap (POSIX). */
#define SIGABRT 6 /* Abort (ANSI). */
#define SIGIOT 6 /* IOT trap (4.2 BSD). */
#define SIGBUS 7 /* BUS error (4.2 BSD). */
#define SIGFPE 8 /* Floating-point exception (ANSI). */
#define SIGKILL 9 /* Kill, unblockable (POSIX). */
#define SIGUSR1 10 /* User-defined signal 1 (POSIX). */
#define SIGSEGV 11 /* Segmentation violation (ANSI). */
#define SIGUSR2 12 /* User-defined signal 2 (POSIX). */
#define SIGPIPE 13 /* Broken pipe (POSIX). */
#define SIGALRM 14 /* Alarm clock (POSIX). */
#define SIGTERM 15 /* Termination (ANSI). */
#define SIGSTKFLT 16 /* Stack fault. */
#define SIGCLD SIGCHLD /* Same as SIGCHLD (System V). */
#define SIGCHLD 17 /* Child status has changed (POSIX). */
#define SIGCONT 18 /* Continue (POSIX). */
#define SIGSTOP 19 /* Stop, unblockable (POSIX). */
#define SIGTSTP 20 /* Keyboard stop (POSIX). */
#define SIGTTIN 21 /* Background read from tty (POSIX). */
#define SIGTTOU 22 /* Background write to tty (POSIX). */
#define SIGURG 23 /* Urgent condition on socket (4.2 BSD). */
#define SIGXCPU 24 /* CPU limit exceeded (4.2 BSD). */
#define SIGXFSZ 25 /* File size limit exceeded (4.2 BSD). */
#define SIGVTALRM 26 /* Virtual alarm clock (4.2 BSD). */
#define SIGPROF 27 /* Profiling alarm clock (4.2 BSD). */
#define SIGWINCH 28 /* Window size change (4.3 BSD, Sun). */
#define SIGPOLL SIGIO /* Pollable event occurred (System V). */
#define SIGIO 29 /* I/O now possible (4.2 BSD). */
#define SIGPWR 30 /* Power failure restart (System V). */
#define SIGSYS 31 /* Bad system call. */
A noter que toutes les valeurs des signaux ne sont pas nécessairement les mêmes suivant les différents Unix, voire entre deux versions majeures de noyaux Linux. Aussi, il conviendra de toujours utiliser dans vos programmes le nom du signal (ex : SIGURG ou SIGKILL) plutôt que leur valeur numérique (23 ou 9).
Si la plupart des signaux on une signification imposée par le système, il existe deux signaux (SIGUSR1 et SIGUSR2) qui peuvent être utilisés par le programmeur à sa guise (il peut leurs assigner par convention la sémantique quil désire).
Pour traiter les signaux, le descripteur de processus (PCB) contient les champs suivants :
le champ signal est de type sigset_t qui stocke les signaux envoyés au processus. Cette structure est constituée de deux entiers non signés de 32 bits chacun (soit 64 bits au total), chaque bit représentant un signal. Une valeur à 0 indique que le signal correspondant na pas été reçu tandis quune valeur à 1 indique que le signal a été reçu ;
le champ blocked est de type sigset_t (64 bits) et stocke les signaux bloqués (cest-à-dire les signaux dont Ia prise en compte est retardée) ;
le champ sigpending est un drapeau (flag) indiquant sil existe au moins un signal non bloqué en attente ;
le champ gsig est un pointeur vers une structure de type signal_struct, qui contient notamment, pour chaque signal, la définition de laction qui lui est associée.
En pratique, la gestion des signaux se retrouve à plusieurs niveaux dans le système dexploitation :
envoi dun signal par un processus (par le noyau ou par le processus dun utilisateur, ou suite à une exception),
prise en compte du signal et exécution du code qui lui est associé ;
enfin, il existe une interaction entre certains appels systèmes et les signaux.
Nous allons détailler chacun de ces mécanismes.
Lenvoi dun signal
Lenvoi dun signal peut être effectué :
par un processus à destination dun autre processus, à laide de la fonction système « kill() » (Cf. prochains chapitres). Il existe une commande « kill » qui peut être lancée depuis un shell, et qui appelle la fonction système « kill() ». Exemple dutilisation : # kill -SIGTERM num_de_pid
ou alors, lexécution du processus a levé une trappe, et le gestionnaire dexception associé positionne un signal pour signaler Ierreur détectée. Par exemple, suite à une division par zéro, le gestionnaire dexception divide_error() positionne le signal SIGFPE.
Lors de lenvoi dun signal, le noyau exécute la routine du noyau seng_sig_info() qui positionne tout simplement à 1 le bit correspondant au signal reçu dans le champ signal du PCB du processus destinataire. La fonction se termine immédiatement dans les deux cas suivant :
le numéro du signal émis est 0. Ce numéro nétant pas un numéro de signal valable, le noyau retourne immédiatement une valeur derreur ;
ou lorsque le processus destinataire est dans létat « zombie ».
Le signal ainsi délivré (mise à 1 du bit dans le champ signal) mais pas encore pris en compte par le processus destinataire (le handler de signal na pas encore été lancé) est qualifié de signal pendant.
A noter que ce mécanisme de mémorisation de la réception du signal permet effectivement de mémoriser quun signal a été reçu, mais ne permet pas de mémoriser combien de signaux dun même type ont été reçus. Par exemple, si deux processus fils se terminent de façon rapprochée dans le temps, le premier enverra un signal SIGCHLD au père. Il est tout à fait possible que la mort du second fils engendre le même signal SIGCHLD au père, alors que le premier signal SIGCHLD était encore pendant (i.e. non pris en compte par le père). Ainsi, la réception dun signal SIGCHLD par le père lui indique « quau moins » un fils sest terminé, sans que le système ne puisse lui indiquer combien.
La prise en compte dun signal
La prise en compte dun signal par un processus seffectue lorsque celui-ci sapprête à quitter le mode noyau pour repasser en mode utilisateur (cest à dire lors du retour dun appel à une fonction système, ou lorsque le scheduler élit ce processus et souhaite le faire démarrer). On dit alors que le signal (qui était pendant) est délivré au processus.
Cette prise en compte est réalisée par la routine du noyau do_signal() qui traite chacun des signaux pendants du processus. Trois types dactions peuvent être réalisés:
ignorer le signal ;
exécuter laction par défaut ;
exécuter une fonction spécifique installée consciemment par le programmeur.
Ces actions sont stockées pour chaque signal dans le champ gsig.sa_handler du bloc de contrôle du processus (PCB). Ce champ prend la valeur SIG_IGN dans le cas où le signal doit être ignoré, la valeur SIG_DFL sil faut exécuter le handler de signal par défaut, et enfin contient ladresse de la fonction spécifique à exécuter dans le troisième cas.
Lorsque le signal est ignoré, aucune action nest exécutée. Il existe une exception à cette règle : le signal SIGCHLD. En effet, si le processus a programmé le signal SIGCHLD afin que ce dernier soit ignoré, le noyau force le processus à lire le code retour des zombies, afin que ces derniers libèrent leurs ressources (principalement des entrées dans les tables des PCB) et soient effacés définitivement.
Les actions par défaut qui peuvent être exécutées suites à un envoi de signal sont au nombre de cinq :
fin du processus,
fin du processus et création (si lutilisateur la décidé) dun fichier core dans le répertoire courant, qui est un fichier contenant limage mémoire du processus, et qui peut être analysé par un débogueur,
le signal est ignoré,
le processus est stoppé (il passe dans létat TASK_STOPPED),
le processus reprend son exécution (létat est positionné à TASK_RUNNING).
Voici un tableau qui indique les actions par défaut liées aux différents signaux :
Actions par défautNom du signalFin du processSIGHUP, SIGINT, SIGBUS, SIGKILL, SIGUSR1, SIGUSR2, SIGPIPE, SIGALRM, SIGTERM, SIGSTKFLT, SIGXCOU, SIGXFSZ, SIGVTALRM, SIGPROF, SIGIO, SIGPOLL, SIGPWR, SIGUNUSEDFin du process et création coreSIGQUIT, SIGILL, SIGTRAP, SIGABRT, SIGIOT, SIGFPE, SIGSEGVSignal ignoréSIGCHLD, SIGURG, SIGWINCHProcessus stoppéSIGSTOP, SIGTSTP, SIGTTIN, SIGTTOUProcessus redémarréSIGCONTTout processus peut installer un traitement spécifique pour chacun des signaux, hormis pour le signal SIGKILL. Ce traitement spécifique remplace alors le traitement par défaut défini par le noyau. Ce traitement spécifique peut être de deux natures différentes :
demande à ignorer Ie signal (prend alors la valeur SIG_IGN),
définit une action particulière programmée dans une fonction C attachée au code de lutilisateur (prend alors la valeur du handler ou gestionnaire du signal).
A noter que lorsquun signal pendant est délivré au processus, si ce signal est détourné par une fonction programmée par lutilisateur, le noyau :
revient en mode « utilisateur »,
lance lexécution du handler,
et à la fin de lexécution de ce handler, le noyau sarrange pour que le processus reprenne son exécution normale (cest la fonction restore_sigcontext() qui effectue ce travail).
Voici en pratique ce qui se passe. Lorsque le noyau est prêt pour redonner la main à un processus en mode utilisateur (soit après un appel système, soit après que le scheduler ait élu ce processus), le noyau appelle tout dabord la fonction do_signal(). Cette fonction vérifie quil nexiste pas de signal pendant. Si cest le cas, le noyau appel le handler correspondant (avec le privilège utilisateur). Lorsque cette fonction se termine, si aucun autre signal nest pendant, le noyau retourne à lexécution du programme à laide de la fonction restore_sigcontext().
Signaux et appels système
Lorsquun processus exécute un appel système qui se révèle bloquant (exemple : appel de la fonction open() pour ouvrir un fichier qui nest pas encore ouvert par un autre processus ; il va falloir aller lire et interpréter des blocs sur le disque dur ; pendant ce temps, le processus est « bloqué »), le processus est placé par le noyau dans létat TASK_INTERRUPTIBLE ou dans létat TASK_UNINTERRUPTIBLE :
sil est dans létat TASK_INTERRUPTIBLE, le processus peut être réveillé par le système lorsquil reçoit un signal ;
inversement, le système place le processus dans létat TASK_UNINTERRUPTIBLE si le processus ne doit pas être réveillé par un signal.
Lorsquun processus placé dans létat « TASK_INTERRUPTIBLE » suite à un appel système blocant est réveillé par le noyau (lorsquil reçoit un signal), une fois le handler correspondant terminé, le système positionne ce processus dans létat « TASK_RUNNING », et il positionne la variable errno à EINTR. Nous verrons dans les prochains chapitres comment faire pour que le processus ne reprenne pas son exécution normale, et attende bien la fin de son appel système.
Remarque importante : un processus fils nhérite pas des signaux pendants de son père. De plus, en cas de recouvrement du code hérité du père, les gestionnaires par défaut sont réinstallés pour tous les signaux du fils.
Les routines systèmes liées aux signaux
Envoyer un signal à un processus
Comme nous lavons déjà vu, lenvoi dun signal se fait à laide de la fonction kill(). Un « man 2 kill » nous donne :
>
Bloquer les signaux
Pour bloquer les signaux, nous devons manipuler des objets de type « sigset_t », qui représente un « ensemble de signaux ».
Pour manipuler les variables de type sigset_t, nous avons à notre disposition les fonctions suivantes (Cf. « man 3 sigsetops ») :
>
La primitive « sigsuspend(const sigset_t *ens); » permet de façon atomique de modifier le masque des signaux et de se bloquer en attente. Une fois un signal non bloqué délivré, la primitive se termine en restaurant le masque antérieur :
>
Enfin, la primitive « int sigpending(sigset_t *ens); » permet de connaître lensemble des signaux pendants dun processus.
>
Exemple classique de lutilisation de ces fonctions : empêcher le CTRL+C (break) pendant lexécution dune phase sensible de code :
>
Attacher un handler à un signal
Deux primitives permettent dattacher un gestionnaire de traitement dun signal à un signal. Ils sagit des fonctions signal() et sigaction(). La première est plus simple dutilisation, mais risque de poser des soucis de compatibilité avec dautres Unix. La seconde est plus complexe dappréhension, mais plus universelle. Voici leurs documentations :
>
Traiter les appels systèmes interrompus
Lorsquun processus placé dans létat « TASK_INTERRUPTIBLE » suite à un appel système blocant est réveillé par le noyau lorsquil reçoit un signal, le handler correspondant sexécute. Celui-ci terminé, le système positionne ce processus dans létat « TASK_RUNNING », et il positionne la variable errno à EINTR. Or, il ne faut pas reprendre lexécution dun processus qui est bloqué après un appel système. Deux solutions permettent de résoudre ce problème :
relancer « manuellement » lexécution de lappel système lorsque celui-ci échoue avec un code derreur errno valant EINTR. Par exemple :
do
{
nb_lus=read(desc_fic, buffer, nb_a_lire);
} while ((nb_lus == -1)&&(errno == EINTR));
autre solution, plus hestétique : utiliser la fonction « int siginterrupt(int signum, int interrupt); ». Cette fonction est appelée après linstallation du gestionnaire de signal associé au signal signum. Si le paramètre « interrupt » est nul, lappel système interrompu par le signal « signum » sera relancé automatiquement. Sinon, si « interrupt » est non nul, le système reprend son fonctionnement par défaut (lappel système retourne une erreur, et errno prend la valeur EINTR).
Attendre un signal
Lappel à la fonction « pause() » bloque un processus dans lattente de la délivrance dun signal :
>
Armer une temporisation
La primitive « alarm() » permet darmer une temporisation. A la fin de cette temporisation, le signal SIGALRM est délivré au processus.
>
Complément sur les signaux temps-réels
Pour compléter ce qui a été écrit précédemment concernant les signaux temps réels, voici un extrait de la documentation ad-hoc de Linux. Il est conseillé de lire attentivement les phrases en gras si vous souhaitez utiliser les signaux temps-réel :
>
La lecture et lécrite dans un tube se fait à laide des fonctions read() et write() :
>
Exemple dutilisation dun tube anonyme :
0)
write(STDOUT_FILENO, &buf, 1);
write(STDOUT_FILENO, "\n", 1);
close(pfd[0]);
exit(0);
}
else
{ /* Le père écrit argv[1] dans le tube */
/* Fermeture du descripteur en lecture inutilisé */
close(pfd[0]);
write(pfd[1], argv[1], strlen(argv[1]));
close(pfd[1]); /* Le lecteur verra EOF */
wait(NULL); /* Attente du fils */
exit(EXIT_SUCCESS);
}
return(0);
}
>>
Les pipes anonymes sont utilisé au niveau de linterpréteur de commandes (le shell) avec la syntaxe « | » (barre verticale, appelée « pipe », faite avec AltGr+6 sur un clavier AZERTY).
Pour comprendre le mécanisme du pipe du shell Unix/Linux, il faut savoir que chaque programme lancé depuis le shell possède trois descripteurs ouverts par défaut :
stdin : cest le descripteur de fichier dentrée standard. Sauf action explicite, il sagit du clavier. Dans ce cas, une fin de fichier peut être envoyée à laide de la combinaison de touches CTRL+Z (code ASCII 26) ;
stdout : cest le descripteur de fichier de sortie standard. Sauf action explicite, écrire sur ce descripteur envoie le texte à lécran. Par exemple, cest sur ce descripteur que sont envoyées les chaînes de caractères passées à la fonction printf() ;
stderr : cest le descripteur de fichier où sont envoyés les messages derreur (par exemple, ceux affichés par perror()).
Par convention, stdin est le premier fichier ouvert. Il a donc comme numéro de descripteur 0. Ensuite, stdout vaut 1, et stderr vaut 2. A noter que pour éviter tout problème si un jour cette convention venait à changer, et pour écrire du code portable, mieux vaut plutôt utiliser les constantes STDIN_FILENO, STDOUT_FILENO, et STDERR_FILENO.
Sous shell, rediriger stdin se fait avec le symbole « ». Rediriger stderr se fait avec la suite de caractères « 2>&1 » (sans espace, sinon, le symbole « & » sera interprété autrement par le shell).
Exemple : la commande shell « wc l » (sans autre paramètre) compte le nombre de lignes dans stdin. La commande « ls » liste les fichiers présents dans le répertoire courant. Ainsi, la commande :
ls | wc -l
va rediriger stdout de ls pour et fournir ce flux en entrée à stdin de wc. Le résultat indiquera le nombre de fichiers contenus dans le répertoire courant.
Si nous voulions simuler ce même mécanisme dans un de nos programmes, il est nécessaire dutiliser la fonction dup(), qui duplique un descripteur :
>
Ce qui est important, cest que dup() utilise le plus petit numéro disponible. Ainsi, si nous fermons le fichier dentrée standard stdin (avec un « close(STDIN_FILENO) »), puis un « dup(descripteur_de_pipe_en_lecture) », le numéro de descripteur retrourné par dup() a toutes les chances dêtre 0 (le numéro de descripteur de stdin).
Un bon exercice : selon ce principe, écrire un programme C qui ouvre un pipe anonyme, puis lance un fils avec fork(). Le père ferme stdout, puis lui ré-attribue grâce à la fonction dump() le descripteur en écriture du pipe, et lance (avec la fonction execlp()) une commande « ls ». De son coté, le fils ferme stdin, puis attribue (à laide de dump()) le descripteur en écriture du pipe à stdin, avant de lancer la commande « wc l » avec la fonction execlp().
Les tubes nommés
Tout comme les tubes anonymes, les tubes nommés sont mono directionnels, et également gérés par le système de gestion de fichiers. Mais cette fois ci, il y a correspondance entre le tube et un vrai fichier (identifié avec son nom). De ce fait, ils sont accessibles par nimporte quel processus connaissant ce nom et disposant des droits daccès ad hoc. Le tube nommé permet donc à des processus sans liens de parenté de communiquer selon un mode déchange par flux.
Les fichiers de type « tubes nommés » ne sont pas des fichiers classiques de type « conteneurs » où seraient stockés des octets. En faisant un « ls l » sous shell, les tubes nommés sont caractérisés par le type « p ». Ce sont des fichiers constitués dun seul « i-noeud » (i-node en anglais : il sagit de la structure physique qui permet de construire des fichiers ; nous verrons tout ça dans un prochain chapitre sur les fichiers), auquel nest associé aucun bloc de données. Tout comme pour les tubes anonymes, les données contenues dans les tubes sont placées dans un tampon, constitué par une seule case de la mémoire centrale.
La création dun tube nommé se fait à laide de la commande shell :
mkfifo nom_pipe
Cette commande fait appel à la fonction système (que vous pouvez vous aussi utiliser dans vos programmes) : mkfifo() :
>
Ensuite, lutilisation dun tube nommé ressemble à lutilisation dun fichier. Louverture se fait à laide de la primitive « open() » :
>
La lecture, lécriture, et la fermeture se font avec les même fonction que celles utilisées pour les tubes anonymes (et les fichiers), cest à dire avec read(), write(), et close().
Caractéristiques communes aux IPCs
Comme nous lavons déjà vu, les IPC Système V (Inter Process Communication) forment un groupe de trois outils de communication :
les files de messages ou MSQ (messages queues) ;
les regions de mémoire partagée (shared memory) ;
les sémaphores.
Ces trois outils sont gérés dans des tables du système, une par outils. Un outil IPC est identifié de manière unique par un identifiant externe appelé la clé (qui a le même rôle que le chemin daccès dun fichier) et par un identifiant interne (qui joue le rôle de descripteur, comme pour les descripteurs de fichiers). Un outil IPC est accessible à tout processus connaissant lidentifiant interne de cet outil. La connaissance de cet identifiant sobtient par héritage, ou par une demande explicite au système au cours de laquelle le processus fournit lidentifiant externe de loutil IPC.
La clé est une valeur numérique de type key_t. Les processus désirant utiliser un même outil IPC pour communiquer doivent se mettre daccord sur la valeur de Ia clé référençant loutil. Ceci peut être fait de deux manières:
la valeur de la clé est figée dans le code de chacun des processus,
ou la valeur de la clé est calculée par le système à partir dune référence commune à tous les processus. Cette référence est composée de deux parties : un nom de fichier et un entier.
Le calcul de la clé est effectué par la fonction système « ftok() » :
>
A noter que les IPC sont créés à laide de primitives ayant la forme xxxget(). Le dernier argument des ces fonctions (le flag) permet de spécifier les droits (en lecture/écriture, pour lutilisateur qui la créé, et pour les autres). Pour ce, il suffit dutiliser les constantes définies dans « #include » (Cf. man 2 stat). Par exemple, S_IRUSR et S_IWUSR spécifient des permissions de lecture et écriture pour le propriétaire de lIPC, tout comme S_IROTH et S_IWOTH spécifient des permissions de lecture et écriture pour les autres utilisateurs. En labsence de ces flags, seul lutilisateur root pourrait utiliser les IPC. Autrement, si vous programmez à laide des IPCs, et si votre code ne fonctionne que sous root (et pas en étant connecté comme utilisateur quelconque), cest que vous avez oublié ces options.
Sous shell, la commande ipcs permet de lister tous les IPC existants à un moment donné dans le système. Pour chaque IPC, cette commande fournit :
le type (q pour message queue, s pour sémaphore, et m pour mémoire partagée) ;
lidentification interne,
la valeur de la clé,
les droits daccès,
le propriétaire et le groupe propriétaire.
Exemple :
# ipcs
IPC status from /dev/mem as of sam 14 avr 19:53:17 DFT 2007
T ID KEY MODE OWNER GROUP
Message Queues:
q 1310720 0x4107001c -Rrw-rw---- root printq
q 3276801 00000000 --rw-rw-rw- root system
q 3276802 00000000 -Rrw-rw-rw- root system
Shared Memory:
m 0 0x58052224 --rw-rw-rw- root system
m 1 0x47041246 --rw-r--r-- imnadm imnadm
m 2 0x58041246 --rw-r--r-- imnadm imnadm
m 3145739 00000000 --rw-rw-rw- root system
m 3276812 0x610b0002 --rw-rw-rw- root system
m 13 0x0d052cf4 --rw-rw-rw- root system
Semaphores:
s 262144 0x58052224 --ra-ra-ra- root system
s 1 0x44052224 --ra-ra-ra- root system
s 131074 00000000 --ra-ra-ra- imnadm imnadm
Les files de messages (messages queues/MSQ)
Le principe repose sur le concept de communication (qui peut être bi-directionnel) par « boîte aux lettres ». Le noyau Linux permet de créer/gérer MSGMNI (128 par défaut) boîtes aux lettres de messages. La création ou laccès à une file de messages existant se font à laide de la fonction « msgget() » :
>
La création dune file se fait en positionnant msgflg à IPC_CREAT et IPC_EXCL. La clé est calculée au préalable avec ftok(). Laccès à une file existante se fait en mettant le paramètre msgflg à 0.
Si clé vaut « IPC_PRIVATE », la file ne sera accessible que du processus lui-même, et à ses descendants.
Ensuite, msgsnd() et msgrcv() permettent denvoyer et de recevoir des messages :
0 ) */
char mtext[1]; /* contenu du message */
};
Le champ mtext est un tableau ou autre structure de
taille msgsz, valeur entière positive ou nulle. Les
message de taille nulle (sans champ mtext) sont autorisés.
Le membre mtype doit avoir une valeur strictement
positive qui puisse être utilisée par le processus lecteur
pour la sélection de messages (voir la description
de msgrcv ci-dessous).
Lappel système msgsnd() insère une copie du message pointé
par largument msgp dans la file dont lidentifiant est
indiqué par la valeur de largument msqid.
Sil y a assez de place dans la file, msgsnd() réussit
immédiatement (la capacité de la file est définie par le
champ msg_bytes de la structure associée à la file de
messages). Durant la création de la file, ce champ est
initialisé à MSGMNB octets, mais cette limite peut être
modifiée avec msgctl().) Sil ny a pas assez de place,
alors le comportement par défaut de msgsnd() est de bloquer
jusquà obtenir suffisamment despace. En indiquant
IPC_NOWAIT dans largument msgflg, le message ne sera pas
envoyé et lappel système échouera en retournant EAGAIN
dans errno.
Un appel à msgsnd() bloqué peut aussi échouer si la file
est supprimée (auquel cas lappel système échouera avec
errno valant EIDRM), ou si un signal a été intercepté
(auquel cas lappel système échouera avec errno valant
EINTR). (msgsnd et msgrcv ne sont jamais relancés
automatiquement après interruption par un gestionnaire de
signal, quelle que soit la configuration de SA_RESTART lors
de linstallation du gestionnaire.)
Si lappel système réussit, la structure décrivant la file
de messages est mise à jour comme suit :
msg_lspid contient le PID du processus appelant.
msg_qnum est incrémenté de 1.
msg_stime est rempli avec lheure actuelle.
Lappel système msgrcv() supprime un message depuis la
file indiquée par msqid et le place dans le tampon pointé
par msgp.
Largument msgsz indique la taille maximale en octets du
membre mtext de la structure pointée par largument msgp. Si
le contenu du message est plus long que msgsz octets, le
comportement dépend de la présence ou non de MSG_NOERROR
dans msgflg. Si MSG_NOERROR est spécifié, alors le message
sera tronqué (et la partie tronquée sera perdue) ; si
MSG_NOERROR nest pas spécifié, le message ne sera pas
extrait de la file, et lappel système échouera en
renvoyant -1 et en indiquant E2BIG dans errno.
Largument msgtyp indique le type de message désiré :
- Si msgtyp vaut 0, le premier message est lu.
- Si msgtyp est supérieur à 0, alors le premier
- message de type msgtyp est extrait de la file.
- Si msgflg contient MSG_EXCEPT, linverse est
effectué, le premier message de type différent de
msgtyp est extrait de la file.
- Si msgtyp est inférieur à 0, le premier message de
la file avec un type inférieur ou égal à la valeur
absolue de msgtyp est extrait.
Largument msgflg est composé dun OU binaire « | » avec
les options suivantes :
IPC_NOWAIT :
Retourne immédiatement si aucun message du type
désiré nest présent dans la file. Lappel système
échoue et errno est fixé à ENOMSG.
MSG_EXCEPT :
Utilisé avec msgtyp supérieur à 0 pour lire les
messages de type différent de msgtyp.
MSG_NOERROR :
Tronque silencieusement les messages trop longs.
Si aucun message du type requis nest disponible et si
on na pas demandé IPC_NOWAIT dans msgflg, le processus
appelant est bloqué jusquà loccurrence dun des
événements suivants :
- Un message du type désiré arrive dans la file.
- La file de messages est supprimée. Lappel
système échoue et errno contient EIDRM.
- Le processus appelant reçoit un signal à
intercepter. Lappel système échoue et errno
contient EINTR.
Si lappel système réussit, la structure décrivant la file
de messages est mise à jour comme suit :
- msg_lrpid est rempli avec le PID du processus
appelant.
- msg_qnum est décrémenté de 1.
- msg_rtime est rempli avec lheure actuelle.
VALEUR RENVOYÉE
En cas déchec les deux appels système renvoient -1 et
errno contient le code derreur. Sinon msgsnd()
renvoie 0 et msgrcv() renvoie le nombre doctets copiés
dans la table mtext.
ERREURS
En cas déchec de msgsnd(), errno aura lune des valeurs
suivantes :
EACCES : Le processus appelant na pas de permissions
décriture dans la file et na pas la capacité
CAP_IPC_OWNER.
EAGAIN : Le message na pas pu être envoyé à cause
de la limite msg_qbytes pour la file et de la
requête IPC_NOWAIT dans msgflg.
EFAULT : msgp pointe en dehors de lespace dadressage
accessible.
EIDRM : La file de messages a été supprimée.
EINTR : Un signal est arrivé avant davoir pu écrire
quoi que ce soit.
EINVAL : msqid est invalide, ou bien mtype nest pas
positif, ou bien msgsz est invalide (négatif ou
supérieur à la valeur MSGMAX du système).
ENOMEM : Le système na pas assez de mémoire pour copier
le message pointé par msgp.
En cas déchec de msgrcv(), errno prend lune des valeurs
suivantes :
E2BIG : Le message est plus long que msgsz, et
MSG_NOERROR na pas été indiqué dans msgflg.
EACCES : Le processus appelant na pas de permission de
lecture dans la file et na pas la capacité
CAP_IPC_OWNER.
EAGAIN : Aucun message nest disponible dans la file, et
IPC_NOWAIT est spécifié dans msgflg.
EFAULT : msgp pointe en dehors de lespace dadressage
accessible.
EIDRM : La file de messages a été supprimée alors que le
processus attendait un message.
EINTR : Un signal est arrivé avant davoir pu lire quoi
que ce soit.
EINVAL : msgqid ou msgsz invalides.
ENOMSG : IPC_NOWAIT a été requis et aucun message du
type réclamé nexiste dans la file.
NOTES
Largument msgp est déclaré comme un struct msgbuf *
avec les bibliothèques libc4, libc5, glibc 2.0, glibc 2.1.
Il est déclaré comme un void * avec la bibliothèque glibc
2.2, suivant ainsi les spécifications SUSv2 et SUSv3.
Les limites système concernant les files de messages et
affectant msgsnd() sont :
MSGMAX : Taille maximale dun message : 8192 octets
(sous Linux, cette limite peut être lue et
modifiée grâce au fichier
/proc/sys/kernel/msgmax).
MSGMNB : Taille maximale dune file de messages : 16384
octets (sous Linux, elle peut être lue et
modifiée grâce au fichier
/proc/sys/kernel/msgmnb). Le superutilisateur
peut augmenter la taille dune file de messages
au-delà de MSGMNB en utilisant lappel système
msgctl(2).
Limplémentation des files de messages sous Linux na
pas de limite intrinsèque pour le nombre maximal dentêtes
de messages (MSGTQL) et la taille maximale de
lensemble de tous les messages sur le système (MSGPOOL).
>>
A noter quun appel à msgrcv() est bloquant, sauf si msgflg a possède la valeur « IPC_NOWAIT ».
Une file de message est détruite avec un appel « msgctl(int msqid, IPC_RMID, NULL) » (Cf. « man 2 msgctl » pour plus dinformations sur cette fonction).
Sous shell, la suppression dune file de message peut se faire à laide de la commande « ipcrm » :
# ipcrm q identifiant
ou # ipcrm Q cle
Exemple dutilisation des files de messages : un processus A crée une MSQ de clé 12300, puis écrit le message « ceci est un message » à destination du processus B. Le processus B lit le message et l'affiche, puis détruit la MSQ. Correction (simplissime) :
>
Les régions de mémoire partagée
Nous savons que la mémoire allouée à chaque processus est protégée, afin quun autre processus utilisateur ne puisse venir y lire ou écrire des données. Néanmoins, il peut arriver que des processus aient besoin de partager une zone mémoire. Cest le rôle des régions de mémoire partagées, ou shared memory.
Evidemment, il ne faut pas que les processus qui partagent une zone mémoire lutilisent de façon anarchique. Il faut que les processus mettent une sorte de verrou sur la zone quand ils lutilisent, puis déverrouillent la zone une fois le travail terminé, laissant ainsi à un autre processus la possibilité de lutiliser à son tour. Cest le principe des sémaphores que nous verrons dans un prochain chapitre.
A noter que comme les files de messages, les régions de mémoire partagée est un mécanisme dIPC. Aussi, il est chacun de ces objets est identifié par une clé, et il faut utiliser ftok() pour créer/gérer ces clés (ou le programmeur choisi une valeur de clé de façon conventionnelle).
La création dune région de mémoire partagée se fait à laide de la fonction shmget(), dont le principe sapparente à celui de msgget() :
SHMMAX, ou bien un segment
associé à key existe, mais sa taille est
inférieure à size.
ENFILE : La limite du nombre total de fichiers
ouverts sur le système a été atteinte.
ENOENT : Aucun segment nest associé à key, et IPC_CREAT
nétait pas indiqué.
ENOMEM : Pas assez de mémoire pour allouer le segment.
ENOSPC : Tous les identifiants de mémoire partagée
sont utilisés (SHMMNI), ou lallocation dun
segment partagé de taille size dépasserait
les limites de mémoire partagée du système
(SHMALL).
EPERM : Lattribut SHM_HUGETLB est indiqué, mais
lappelant nest pas privilégié (ne possède pas
la capacité CAP_IPC_LOCK).
NOTES
IPC_PRIVATE nest pas une option mais une valeur de
type key_t. Si cette valeur spéciale est utilisée comme clé,
lappel système ignore tout sauf les 9 bits de poids
faibles de shmflg et tente de créer un nouveau segment.
Les limites suivantes influent sur lappel système shmget :
SHMALL : Nombre maximal de pages de mémoire partagée sur
le système (sous Linux, cette limite peut être
lue et modifiée grâce au fichier
/proc/sys/kernel/shmall).
SHMMAX : Taille maximale dun segment partagé (sous Linux,
cette limite peut être lue et modifiée
grâce au fichier /proc/sys/kernel/shmmax).
SHMMIN : Taille minimale dun segment partagé : dépend de
limplémentation (actuellement 1 octet, bien
que PAGE_SIZE soit la valeur effectivement
utilisée).
SHMMNI : Nombre maximal de segments de mémoire
partagée sur le système (actuellement 4096,
mais 128 avant Linux 2.3.99 ; sous Linux, cette
limite peut être lue et modifiée grâce au
fichier /proc/sys/kernel/shmmni).
Il ny a pas de limite pour le nombre de segments partagés
par processus (SHMSEG).
>>
Une fois la mémoire partagée allouée, il faut pouvoir récupérer un pointeur qui pointe vers la zone allouée par la fonction shmget(). On dit que nous allons attacher un pointeur à de la mémoire partagée. Cette opération seffectue à laide de la fonction shmat(). Inversement, la routine shmdt() détache un pointeur à une région de mémoire partagée :
>
Une région de mémoire partagée peut être détruite à laide dun appel :
shmctl(int shmid, IPC_RMID, NULL);
Cf. « man shmctl » pour plus de détails. Autrement, sous shell, la suppression dune région de mémoire partagée peut se faire à laide de « ipcrm » (même principe que pour détruire une file de messages) :
# ipcrm q identifiant
ou # ipcrm Q cle
Exemple dutilisation de shared memory : le programme A, crée une mémoire partagée, va aller inscrire une structure dans cette mémoire. Un des champs de cette structure est mis à jour en permanence. Le programme B attache la mémoire partagée créée par A, son propre processus, puis va lire les données contenues dans la structure crée par A. Correction (vraiment pas belle) :
c;
var2 = ((structure_partagee_B *) ptr_mem_partagee_B)->d;
printf("data.a : %d\n", var1);
printf("data.b : %lf\n", var2);
}
/* On détruit le segment (le segment n'est pas détruit tant */
/* qu'au moins un processus est lié au segment) */
shmdt (ptr_mem_partagee_B);
return(0);
}
>>
La communication répartie
Le modèle client-serveur
Tous les mécanismes que nous avons vu jusquà présent concernent des opérations au sein dune même machine. Or, il peut arriver que des processus distants, situés sur des machines différentes, aient besoin de communiquer via le réseau.
Une façon classique de traiter ce problème est dutiliser le modèle client-serveur. Un ordinateur (le client) établit le dialogue en envoyant une requête via le réseau à une autre machine (le serveur), qui lui répond :
EMBED PowerPoint.Slide.8
Nous pouvons caractériser les modèles clients-serveurs suivant 3 critères :
la manière dont le serveur traite les requête en provenance du client. Il existe les serveurs :
itératifs : les requêtes sont traitées les unes à la suite des autres (une seule à la fois),
parallèles : le processus qui reçoit les requête fait un fork(), et la requête est traitée par le fils. Plus souple, ayant des meilleurs temps de réponse, ce modèle parallèle peut charger une machine, si de nombreuses machines envoient des requêtes en même temps. Une limite du nombre de fils évite de voir le serveur sécrouler en cas de surcharge ;
le niveau de fiabilité des serveurs. On distingue les serveurs :
sans état : en cas de crash dun processus serveur qui traîte une requête, il est impossible de savoir ce qui a déjà été traité, et ce quil restait à faire,
à état : chaque étape intermétdiaire du traitement de la requête est historisée par le serveur sur le disque dur. Ainsi, en cas de panne, il est possible dannuler ce qui avait déjà été fait et qui restait innachevé, ou de terminer le traitement ;
enfin, la communication client/serveur peut se faire :
par envoi de courts messages (on parle de communication par paquets ou par datagrammes),
ou en établissant une connexion (les informations sont envoyées sous forme de « flux de données » ou « flot de données »).
Il est tout à fait possible de cascader des le modèle de client/serveur. Par exemple, un client qui envoie une requête à un serveur dapplication, qui envoie lui-même une requête à un gestionnaire de base de données (SGBD). Dans ce dernier cas, on parle darchitecture 3-tiers :
EMBED PowerPoint.Slide.8
Le modèle 3-tiers peut ête étendu en répartissant la couche applicative sur plusieurs machines. On parle darchitecture N-tiers (ou multi-tiers) :
EMBED PowerPoint.Slide.8
Lutilisation de plusieurs serveurs applicatifs peut avoir deux raisons :
effectuer des calculs en parallèles (utilisation dalgorithmes de calculs répartis),
et/ou répartir la charge sur plusieurs serveurs. Dans ce cas, une machine reçoit les requêtes des clients (le « frontend »), et les distribuent tour à tour à plusieurs serveurs, tous capables de traiter la requête.
Quelques rappels réseau
Les théoriciens décomposent un protocole de communication en « couches ». Le modèle OSI (de lISO) contient 7 couches :
EMBED PowerPoint.Slide.8
Classiquement, la communication Unix/Linux se fait avec le protocole TCP/IP. Nous nous intéresserons principalement aux protocoles de niveau 4/transport « TCP » (communication par connexion) et « UDP » (communication par paquets). Ces deux protocoles sappuient sur le protocole de communication « IP » (niveau 3/réseau), qui sappuie lui-même sur des protocoles de niveau 2 de type Ethernet, ou Wifi... (802.x).
A noter que toute machine dun réseau IP est identifiée au niveau 3 par une adresse IP. Dans le protocole IP version 4, une adresse IP est constituée de 4 octets.
De plus, les machines possèdent un nom de dommaine sous la forme :
nom_noeud. nom_ss-domaine[...].nom_domaine_racine
Le service réseau qui assure la traduction « nom » « adresse IP » est le DNS (Domain Name Service).
Enfin, chaque service (mail, DNS, pop, http, etc) est identifié par un numéro, appelé « numéro de port » :
EMBED PowerPoint.Slide.8
Par convention, les numéros de ports sont assignés dans les plages suivantes :
Port n° 0 : non utilisable pour une application. C'est un « jocker » qui indique au système que c'est à lui de compléter le numéro (Cf. N°49152 à 65535) ;
Ports 1 à 1023 : ports réservés au superutilisateur (root/Administrateur). On y trouve les serveurs « classiques » (DNS, FTP, SMTP, Telnet, SSH...). Il existait anciennement un découpage 1-255, 256-511, et 512-1023 qui nest plus utilisé ;
Ports 1024 à 49151 : services enregistrés par l'IANA (Internet Assigned Numbers Authority), accessibles aux utilisateurs ordinaires ;
Ports 49152 à 65535 : zone d'attribution automatique des ports, pour la partie cliente.
Sous Unix/Linux, lAPI qui permet détablir une communication entre un client et un serveur sappuie sur la notion de « socket » (une socket sapparente à une fiche). Il existe deux types de sockets :
les sockets en mode datagrammes, qui sappuient sur le protocole UDP,
et les sockets en mode connecté, qui sappuient sur le protocole TCP.
Les fonctions et structures propres à TCP/IP
La normalisation des entiers (endianness)
Certains microprocesseur (motorola 68000, sparc...) stockent les mots de plusieurs octets en mettant par convention locter de poid fort en premier (Exemple : le mot de 32 bits 0xa0b1c2d3 verra loctet 0xa0 stocké en premier, 0xb1 en second, 0xc2 en 3ème, puis 0xd3 en dernier. On dit que ces microprocesseurs sont gros-boutistes, ou fonctionne en mode big-endian.
Inversement, par convention, dautre CPU (Pentium par exemple) stockent les octes de poids faibles en premier. On parle de microprocesseurs petits-boutistes, ou quils fonctionnent en little-endian.
Or, sans y faire attention, si un ordinateur gros-boutiste envoie un mot de 4 octets à un ordinateur petit-boutiste, les octets des mots se trouvent inversés, ce qui serait catastrophique.
Aussi, une convention a été choisie pour représenter les mot sur les réseaux IP (en fait, il sagit de la convention « octets de poids fort en premier »). Il existe 4 fonctions (htonl(), htons(), ntohl(), ntohs()) qui permettent de normaliser les entiers (adresses IP, numéros de port, etc.), afin de les convertir dans la convention dInternet. Si la machine locale a un CPU qui a la même convention que celle dInternet, ces 4 fonctions ne font rien. Sinon, elles inversent les octets de poid faibles avec les octets de poids fort.
>
La résolution de nom
Les fonctions qui font appel au DNS utilisent la structure hostent qui est définie par un « #include » :
struct hostent
{
char *h_name; /* nom officiel de lhôte */
char **h_aliases; /* liste dalias */
int h_addrtype; /* type dadresse (tjs AF_INET */
/* pour IP v4 ou AF_INET6 pour */
/* IP v6) */
int h_length; /* longueur de ladresse */
char **h_addr_list; /* list daddresses */
};
Les tableaux h_aliases et h_addr_list ont comme dernier élément la valeur NULL.
La traduction IP vers nom se fait à laide de la fonction gethostbyaddr(), et la traduction nom vers adresse IP se fait avec la fonction gethostbyname() :
>
Pour IP version 4, les adresses sont stockées dans des structures de type struct sockaddr_in, qui est constituée des champs suivants :
struct sockaddr_in
{
short sin_family; /* AF_INET */
u_short sin_port; /* Num. de port en endian Internet */
struct in_addr sin_addr; /* Adresse IP (en endian Internet) */
char sin_zéro [8]; /* Bourrage */
};
struct in_addr
{
u_long s_addr;
};
La résolution de service
Comme nous lavons vu, chaque service est identifié par un numéro de port, choisi par convention. Sous Unix/Linux, les numéros de ports standards sont listés dans le fichier « /etc/services ».
Pour connaître le numéro de port associé à un service (et réciproquement), il existe deux fonctions : getservbyname() et getservbyport() :
>
La communication par datagrammes
Coté serveur, la création dun socket() est réalisée à laide de la fonction socket(). Puis, le socket est attaché à une adresse à laide de la fonction bind(). Léchange de datagrammes se fait à laide des fonctions sendto() et recvfrom(), qui permettent de spécifier le numéro de port sur lequel lécoute est faite (avec le protocole UDP). Enfin, le socket est détruit à laide de la fonction close().
Coté client, comme pour le serveur, la création dun socket() est réalisée à laide de la fonction socket().Léchange de datagrammes se fait à laide des fonctions sendto() et recvfrom(). Enfin, le socket est détruit à laide de la fonction close().
Un échange client-serveur pour se schématiser ainsi :
EMBED PowerPoint.Slide.8
A noter quun socket est identifier par un descripteur, comme les pipes et des fichiers.
La communication en mode connecté
Coté serveur, le socket est créé par la fonction socket(). La fonction bind() associe le socket à une adresse. La fonction listen() met le processus en attente (création de la file dattente des requêtes reçues). La fonction accept() permet daccepter létablissement dune connexion. Comme pour les fichiers, les fonctions read() et write() permettent denvoyer ou de recevoir des flux de données dans la connexion. Lappel de close() ferme proprement le socket.
Coté client, le socket est créé par la fonction socket().La fonction connect() permet détablir une connexion avec le serveur. Les fonctions read() et write() permettent denvoyer ou de recevoir des flux de données dans la connexion, et close() ferme proprement le socket.
EMBED PowerPoint.Slide.8
Manuel de lAPI des socket
>
Les problématiques de synchronisation
Problématique
Les systèmes multiprogrammés et temps-partagé autorisent la présence de plusieurs processus en même temps dans le système. Il en résulte une nouvelle situation qui nexistait pas auparavant dans les systèmes monoprogrammés. En effet, il peut arriver que plusieurs programmes aient besoin des mêmes ressources :
mémoire centrale,
CPU,
périphériques,
etc.
De même, certains de ces processus coopèrent ensembles pour satisfaire les besoins dune seule application. Cette coopération passe très souvent par lutilisation et le partage de données communes (Cf. exemple avec les régions de mémoire partagée shared memory vu dans le chapitre précédent).
Le partage de ressources et lutilisation de données communes posent de sérieux problèmes. Le système dexploitation doit proposer des techniques et des outils permettant de contrôler laccès et lutilisation de ces ressources. Ces outils et techniques doivent garantir labsence de blocage et un partage équitable.
Les systèmes dexploitation attribuent deux propriétés aux ressources :
leur état (libre ou occupé),
leur nombre de points daccès (nombre de processus qui peuvent y accéder en même temps).
Une ressource est dite critique quand elle ne peut être utilisée que par un seul processus à la fois.
Dès lors, dans les systèmes multiprogrammés ou temps-partagé, lutilisation dune ressource par un processus se fait en trois étapes :
l'allocation de la ressource par le processus,
utilisation de la ressource,
la libération de la ressource, la rendant disponible pour les autres programmes.
Pour garantir une bonne utilisation des ressources, plusieurs schémas de synchronisation classiques sont proposés, schémas que nous allons détailler dans les prochains chapitres :
lexclusion mutuelle,
lallocation de ressources,
les lecteurs-rédacteurs,
les producteurs-consommateurs.
Lexclusion mutuelle
Exemple de problématique
Pour comprendre lexclusion mutuelle, la littérature utilise souvent un problème tout simple : un programme de vente de billets à un spectacle. Au départ, il y a N billets de disponibles. Lobjectif est de programmer une fonction de réservation qui réserve une place de spectacle, et qui retourne la valeur 1 si la réservation sest déroulée normalement, et 0 sil ny a plus de place disponible. En C, le programme pourrait sécrire :
int nb_place=N;
/* bla bla bla... */
int reservation(void)
{
int ret=0;
if (nb_place > 0) /* !!! */
{
/* Il reste au moins une place libre, */
/* aussi, on réserve une place */
nb_place-- ;
ret = 1;
}
return(ret);
}
Dans un système monotâche, ce programme fonctionnerait parfaitement. Mais, dans un système multiprogrammé, voici ce quil peut se produire :
le programme se déroule normalement, jusquà ce quil ne reste plus quune seule place ;
un client C1 souhaite réserver. Il appelle la fonction reservation(). Le registre de compteur ordinal se branche donc à ladresse de cette fonction reservation(). Il effectue le test « if (nb_place > 0) ». Evidemment, comme il reste une place, le résultat de ce test est « VRAI » ;
puis, parce que le processus du client C1 a consommé tout son temps CPU dans le cycle dordonnancement, il y a préemption ;
le scheduler élit un processus client C2 qui, lui aussi, a besoin de réserver une place de spectacle. Il effectue lui aussi un appel à la fonction reservation(). Comme il reste encore une place, cette fonction lui reservera cette dernière place, et retournera la valeur 1 ;
au tour suivant, le scheduler redonnera la main au processus C1 qui, rappelons nous, en était au point « /* !!! */ » dans le code ci-dessus. Le résultat du test avait été vrai, aussi, il continue dexécuter le code correspondant à « then ». La variable nb_place est décrémentée (elle vaut alors la valeur -1 !!!), et la fonction retourne aussi la valeur 1. C1 et C2 ont réservé en même temps la dernière place, ce qui nest pas acceptable.
Evidemment, nous pourrions penser que cette situation de préemption au point « /* !!! */ » couplé au fait quun autre processus ait besoin aussi de réserver une place dans le même tour délection de lordonnanceur est exceptionnelle. Pas si sûr. Pensez au programme de réservation de la billèterie du dernier concert de U2 (100'000 billets vendus en 15 minutes)... De plus, même exceptionnelle, la situation peut néanmoins engendrer des conséquences catastrophiques (avions qui sécrasent, équipement radiologique qui irradie le patient, etc.).
Recherche de solutions à lexclusion mutuelle
En fait, dans lexemple précédent, nous avons identifié le fait que la variable nb_place ne devait être manipulée que par un et un seul processus à la fois. Il sagit dune ressource critique.
Dans le programme ci-dessus, lensemble de toutes les instructions qui se suivent, et qui ont besoin daccéder à cette ressource critique sappelle une section critique. Dans lexemple, il sagit du code :
int reservation(void)
{
int ret=0;
/* début de section critique */
if (nb_place > 0)
{
nb_place--;
ret = 1;
}
/* fin de la section critique */
return(ret);
}
Demander à un système dexploitation de gérer une section critique doit lobliger à assurer 3 propriétés :
assurer lexclusion mutuelle (lorsquun processus utilise une ressource critique, un autre processus ne peut lutiliser),
assurer une attente bornée aux autres processus qui souhaitent utiliser une ressource critique déjà assignée (chaque processus doit pouvoir accéder à la ressource en un temps maximum),
assurer la propriété de bon déroulement : lorsquun processus libère une ressource et que plusieurs autres processus sont en attente de cette ressource, lélection du processus comme étant celui qui sapproprie la ressource se fait en ne considérant comme critère que la liste des candidats potentiels. Aucun événement extérieur ne peut influer ou bloquer ce choix.
Comme nous lavons vu en introduction, laccès à une ressource critique doit se faire en en verrouillant sont accès (en se lallouant) avec un mécanisme appelé « prélude », et doit le libérer avec un mécanisme appelé « postlude ».
La première solution consisterait à interdir toute interruption durant la section critique :
int reservation(void)
{
int ret=0;
disable_interrupt; /* masque les interruptions */
if (nb_place > 0)
{
nb_place--;
ret = 1;
}
enable_interrupt; /* réactive les interruptions */
return(ret);
}
Linconvénient de cette solution est que tous les processus sont bloqués, même ceux qui nont pas besoin de cette ressource. Cette solution est réservée uniquement aux parties de code sensibles du noyau (comme par exemple, la manipulation des files dattente de lordonnanceur, ou la protection des buffeur de cache).
Une autre solution (appelée « Test & Set »), qui vaut une note éliminatoire à lexamen, consiste à obliger le processus souhaitant mettre un verrou à une ressource critique à faire du « polling » en attendant que la ressource se libère.
Pour ce, il faut créer une fonction « Test_and_Set() » de la façon suivante :
int Test_and_Set(int *verrou)
{
disable_interrupt;
int ret = *verrou;
*verrou = 1;
return(ret);
enable_interrupt;
}
Pour chaque ressource, il faut définir une variable globale « int cadena = 0; ». Le prélude devient alors :
while (Test_and_Set(&cadena));
A la fin de la section critique, le postlude devient :
cadena = 0;
Le premier processus recevra de la fonction « Test_and_Set() » une valeur 0. Tous les autres recevront une valeur 1, tant que le processus ayant verrouillé la ressource ne positionnera pas la variable faisant office de verrou à 0. Cette solution est inacceptable : si plusieurs processus sont en attente dune ressource verrouillée, la boucle de polling occupe le CPU, ce qui fait sécrouler les performances de la machine.
Dautres algorithmes nutilisant pas de propriétés matérielles du CPU permettent de résoudre ce problème pour N processus. Néanmoins, ici aussi, les processus exclus doivent faire du polling avant dentrer en section critique (Cf. algorithme de Peterson).
Lallocation de ressources les sémaphores
Principe
Comme nous lavons vu, tout le problème vient du fait que si létat de réservation dune ressource critique est stockée dans une variable, il peut y avoir une interruption (donc préemption) entre le moment où on effectue le test « la variable indique-t-elle que la ressource est disponible » et le moment ou on « assigne à la variable une valeur indiquant que la ressource est assignée en exclusivité à un processus ».
Or, les CPU modernes permettent de réaliser ces deux opérations de façon unitaire, sans quune interruption puisse perturber le résultat. Ainsi, les systèmes dexploitation modernes utilisent cette opération pour proposer un mécanisme dexclusion mutuelle : le sémaphore. En voici le principe.
Les trois opérations liées aux sémaphores sont « Init », « P » et « V » (P et V signifient en néerlandais Proberen tester et Verhogen incrémenter , ce qui se traduirait en français par « Puis-je ? » et « Vas-y ! »). La valeur d'un sémaphore est le nombre d'unités de ressource (exemple : imprimantes...) libres. S'il n'y a qu'une ressource, un sémaphore devient à système numérique binaire avec les valeurs 0 ou 1. Explication de ces trois fonctions :
l'opération P est en attente jusqu'à ce qu'une ressource soit disponible, ressource qui sera immédiatement allouée au processus courant ;
V est l'opération inverse. Elle rend simplement une ressource disponible à nouveau après que le processus a terminé de l'utiliser ;
Init est seulement utilisé une (et une seule fois) pour initialiser le sémaphore.
Les opérations P et V sont indivisibles ; les différentes opérations ne peuvent pas être exécutées plusieurs fois de manière concurrente.
Dans la littérature anglaise, les opérations V et P sont quelques fois appelées respectivement up et down. En conception logicielle, elles sont parfois appelées release et take.
Un sémaphore a généralement une file de processus associée (file de type FIFO). Si un processus exécute l'opération P sur un sémaphore qui a la valeur zéro, le processus est ajouté à la file dattente du sémaphore (le processus ne consomme pas de CPU, et la désactivation de lattente est faite communément par lordonnanceur : quand un autre processus incrémente le sémaphore en exécutant l'opération V, et qu'il y a des processus dans la file, l'un d'eux est retiré de la file et reprend la suite de son exécution).
Voici les algorithmes (ça nest pas du C propre) de ces 3 opérations :
Opération Init(sem, val) :
void Init(semaphore sem, int val)
{
disable_interrupt;
sem.K = val;
sem.L = NULL;
enable_interrupt;
}
Opération P(sem) :
void P(semaphore sem)
{
disable_interrupt;
sem.K--;
if (sem.K < 0)
{
sem.L.suivant = processus_courant;
processus_courant.state = bloque;
reordonnancement = vrai;
}
enable_interrupt;
}
Opération V(sem) :
void V(semaphore sem)
{
disable_interrupt;
sem.K++;
if (sem.K 0)
{
/* Il reste au moins une place libre, */
/* aussi, on réserve une place */
nb_place-- ;
ret = 1;
}
V(sem_places); /* postlude, fin de section critique */
return(ret);
}
Le danger des sémaphores : linterblocage
Supposons un processus A dont le code est le suivant :
...
P(Sem1); /* !!! */
P(Sem2);
/* section critique utilisant les ressources */
/* verrouillées par les sémaphores Sem1 et Sem2 */
Blablabla...
V(Sem2);
V(Sem1);
Et un processus B dont le code est :
...
P(Sem2);
P(Sem1);
/* section critique utilisant les ressources */
/* verrouillées par les sémaphores Sem1 et Sem2 */
Blablabla...
V(Sem1);
V(Sem2);
Supposons que Sem1 et Sem2 soient des sémaphores initialisés à la valeur 1, et que ce soit le processus A qui ait le CPU, et que son exécution se termine juste après lappel « P(Sem1); » et juste avant « P(Sem2); » (i.e. quil y a préemption au point « /* !!! */ »).
Le processus B est alors exécuté. Il fait un « P(Sem2); » qui lui assure lexclusivité sur la ressource 2. Puis, il fait un « P(Sem1); » qui est bloquant (le processus A a déjà verrouillé la ressource).
Lordonnanceur élit le processus A, qui fait un « P(Sem2); » bloquant (en effet, la ressource 2 est verrouillée par le processus B). Pour résumer, nous nous retrouvons avec la situation suivante :
le processus A sest assuré lexclusivité de la ressource n°1, et est bloqué en attente de la ressource n°2,
et le processus B sest assuré lexclusivité de la ressource n°2, et est bloqué en attente de la ressource n°1.
Il sagit dun cas dinterblocage (on parle aussi détreinte fatale ou détreinte mortelle), où aucun des processus nobtiendra jamais ce quil désire.
Une solution simple dans le cas présent consiste programmer les processus pour quils fassent les réservations toujours dans le même ordre (cest ce qui est fait au sein du noyau Linux).
De façon générale, il y a interblocage quand :
il existe une exclusion mutuelle (au moins une ressource doit être dans un mode non partageable),
occupation et attente : au moins un processus sest accaparé une ressource, et attend une autre ressource,
il ny a pas de réquisition : les ressources sont libérées uniquement par la bonne volonté des processus,
il existe un cycle dans le graphe dattente entre au moins deux processus.
Un graphe dattente est un graphe où sont représentés les processus et les ressources comme étant des nuds. Des flèches symbolisent les situations « bloque » et « attend ».
Les sémaphores sous Linux
Comme nous lavons vu dans les chapitres précédents, les sémaphores sont implémentés sous Linux sous la forme dIPC.
De plus, les IPC de sémaphores introduisent une nouvelle notion en plus des fonctions P() et V() : il sagit de la fonction ATT(), qui bloque un processus dans lattente que le sémaphore soit nul (mais sans décrémenter la valeur du sémaphore).
La création dun ensemble de sémaphore se fait à laide de la fonction semget() :
>
Linitialisation dun sémaphore sem à une valeur v0 se fait via la fonction semctl() :
semctl(sem, 0, SETVAL, v0);
La destruction dun semaphore sem se fait par lappel de cette même fonction semctl() :
semctl(sem, 0, IPC_RMID, 0);
Lire le manuel de cette function pour plus de details. Enfin, les fonctions P(), V(), et ATT() dun sémaphore se font à laide de la fonction semop() :
>
Les lecteurs-rédacteurs
Principe
La problématique des lecteurs-rédacteurs est relativement simple. Deux classes de processus sont en compétition pour accéder à une ressource (par exemple, un fichier, ou une région de mémoire partagée) :
les lecteurs, qui ne peuvent être concurrents qu'entre eux (plusieurs processus peuvent accéder à la ressource en lecture, avec lassurance que le résultat obtenu sera toujours le même),
et les rédacteurs, qui sont exclusifs vis-à-vis de tous (un rédacteur ne peut écrire que lorsquaucun lecteur ou rédacteur accède à la ressource).
Une solution de ce problème peut se faire à laide :
dune variable globale (qui est une ressource critique) nb_lect qui indique combien de lecteurs accèdent à la ressource (la variable est initialisée à 0),
dun sémaphore sem_nb_lect, qui assure lallocation de la variable nb_lect,
et dun sémaphore sem_exclu, qui assure lexclusivité à la ressource (soit au groupe de lecteur(s), soit à un rédacteur).
Le code du rédacteur devient :
int nb_lect = 0 ;
Init(sem_nb_lect, 1);
Init(sem_exclu, 1);
...
bla bla bla...
...
void Redacteur(void)
{
P(sem_exclu);
Section critique, je mets ici le code décriture...
V(sem_exclu);
}
Le code du lecteur est :
void Lecteur(void)
{
/* je me garantis lexclu de la variable nb_lect : */
P(sem_nb_lect);
nb_lect++;
if (nb_lect == 1) /* je suis le premier lecteur */
{
/* je donne lexclusion au groupe des lecteurs */
P(sem_exclu);
}
/* je nai plus besoin daccéder à nb_lect : */
V(sem_nb_lect);
Bla bla bla (code daccès en lecture seule)
/* je me garantis lexclu de la variable nb_lect : */
P(sem_nb_lect);
nb_lect--;
if (nb_lect == 0) /* je suis le dernier lecteur */
{
/* je libère lexclusion au groupe des lecteurs */
V(sem_exclu);
}
/* je nai plus besoin daccéder à nb_lect : */
V(sem_nb_lect);
}
Remarque : avec cette solution, le rédacteur peut crier famine, sil y a toujours au moins un lecteur. Exercice : chercher une solution qui assure la priorité dutilisation aux rédacteurs (et tant pis si les lecteurs crient famine).
Les verrous de fichiers sous Linux
Le système dexploitation Linux/Unix propose deux solutions simples de verrous sur les fichiers :
les verrous partagés (qui peuvent être utilisés pour accéder à un fichier en lecture seule, évitant ainsi quun rédacteur vienne y écrire pendant un lecteur),
et les verrous exclusifs (utilisés par les rédacteurs, pour éviter quun lecteur ou quun autre rédacteur y accède pendant son écriture).
Positionner un verrou sur un fichier se fait avec la fonction flock() :
>
Le schéma producteur-consommateur
Principe et résolution pour 1 producteur et 1 consommateur
Un processus, désigné comme le producteur, est chargé d'emmagasiner des données dans une file d'attente de type FIFO circulaire. Un second processus, le consommateur, est chargé de les déstocker. Evidemment, les vitesses de remplissage et de déremplissage sont aléatoires, et nont rien en commun. Problème : comment faire pour que chaque intervention exclue les autres ?
Rappel sur les files dattente circulaires : la file est réalisée à laide dun tableau de N cases (numérotées de 0 à N-1). Il existe deux pointeurs : le début de la file, et la fin de la file, tous deux initialisés à 0. Lorsque le producteur remplit la file, sil reste de la place, il place la donnée dans la case pointée par la fin de file. Puis il ajoute 1 à ce pointeur. Sil vaut N, le pointeur passe à 0. Lorsque le consommateur accède à la file pour y lire des données, sil y a des données à lire, il lit le contenu de la case pointée par le début de file. Il ajoute 1 à ce pointeur. Sil vaut N, le pointeur passe à 0.
Pour résoudre ce problème, il suffit de le voir de la façon suivante : il existe des cases vides et des cases pleines. Le producteur produit des cases pleines et consomme des cases vides, alors que le consommateur produit des cases vides et consomme des cases pleines. Il existe deux types de ressources : les cases vides, et les cases pleines.
Il suffit alors dutiliser deux sémaphores : un sémaphore des cases pleines, initialisé à 0, et le sémaphore des cases vides, initialisé à N :
Init(sem_pleines, 0);
Init(sem_vides, N);
int Ptr_debut=0;
int Ptr_fin=0;
int Cases[N];
Le code du producteur devient :
void Producteur(int message_a_enfiler)
{
/* on attend une case libre */
P(sem_vides);
Cases[Ptr_fin] = message_a_enfiler;
Ptr_fin = (Ptr_fin + 1) % N;
/* on produit une case pleine */
V(sem_pleines);
}
Le code du consommateur est :
int Consommateur(void)
{
int message_lu;
/* on attend une case pleine */
P(sem_pleines);
message_lu = Cases[Ptr_debut];
Ptr_debut = (Ptr_debut + 1) % N;
/* on produit une case vide */
V(sem_vides);
return(message_lu);
}
Extension du problème à X producteurs et Y consommateurs
Dans ce problème, plusieurs processus peuvent écrire à nimporte quel moment, et plusieurs consommateurs peuvent écrire à nimporte quel moment.
Dans ce cas, il faut sassurer que les modifications des variables Ptr_debut et Ptr_fin ne se fassent pas en même temps par deux processus. Pour ce, il suffit de protéger chacun par son sémaphore :
Init(sem_Ptr_debut, 1);
Init(sem_Ptr_fin, 1);
Le code devient :
void Producteur(int message_a_enfiler)
{
/* on attend une case libre */
P(sem_vides);
/* On sassure lexclusivité de Ptr_fin */
P(sem_Ptr_fin);
Cases[Ptr_fin] = message_a_enfiler;
Ptr_fin = (Ptr_fin + 1) % N;
/* On na plus besoin dutiliser Ptr_fin */
V(sem_Ptr_fin);
/* on produit une case pleine */
V(sem_pleines);
}
int Consommateur(void)
{
int message_lu;
/* on attend une case pleine */
P(sem_pleines);
/* On sassure lexclusivité de Ptr_debut */
P(sem_ Ptr_debut);
message_lu = Cases[Ptr_debut];
Ptr_debut = (Ptr_debut + 1) % N;
/* On na plus besoin dutiliser Ptr_debut */
V(sem_ Ptr_debut);
/* on produit une case vide */
V(sem_vides);
return(message_lu);
}
A noter que les messages queues et les pipes (vus au chapitre précédent) sont aussi deux autres solutions au problème du producteur/consommateur.
Lexclusion mutuelle chez les thread
Comme nous lavons vu, les threads partagent le même espace mémoire. Il est donc nécessaire de protéger laccès aux variables globales.
Sans entrer dans les détails, voici les solutions mises à disposition des programmeurs pour gérer les problématiques dexclusion mutuelle entre threads.
Les mutex
Lexpression mutex provient de « Mutual exclusive object ». Le mutex est représenté dans les programmes par une variable de type pthread_mutex_t.
Pour créer un mutex, il suffit de créer une variable de type pthread_mutex_t, et de linitialiser avec la constante PTHREAD_MUTEX_INITIALIZER :
pthread_mutex_t mon_mutex = PTHREAD_MUTEX_INITIALIZER;
La destruction dun mutex se fait à laide de lappel à la function :
int pthread_mutex_destroy(pthread_mutex_t *pMutex);
Une fois créés, tous les thread aillant accès par adresse à un mutex peuvent le verrouiller lorsquils ont besoin dun accès exclusif aux données protégées. A nimporte quel instant, un unique thread est autorisé a verrouiller le même mutex. Il existe deux façons de verrouiller un mutex, via deux fonctions :
int pthread_mutex_lock(pthread_mutex_t *pMutex);
int pthread_mutex_trylock(pthread_mutex_t *pMutex);
Ces deux fonctions ont un comportement différent. Quand un thread appel la fonction pthread_mutex_lock(), la fonction retourne si :
une erreur sest produite,
le mutex est correctement verrouillé.
Le thread en question est alors le seul qui a verrouillé le mutex. Si le mutex est déjà verrouille par un autre thread, la fonction ne retourne pas tant que le verrouillage nest pas obtenu. En cas de succès, 0 est retourné, une valeur non nulle sinon.
La fonction pthread_mutex_trylock() retourne toujours même si le mutex est déjà verrouillé par un autre thread. Comme la première fonction, il retourne 0 en cas de succès. Ceci signifie que le mutex a pu être verrouille par cet appel. Si un autre thread as déjà verrouillé le mutex, EBUSY est retourné.
Dès que le thread a fini de travailler avec les données protégées, le mutex doit être déverrouillé pour laisser la place a dautres thread. Ceci est simplement réalisé en appelant la fonction suivante :
int pthread_mutex_unlock(pthread_mutex_t *pMutex);
Les variables conditions
Les variables conditions sont des éléments de type pthread_cond_t permettant à un processus de se mettre en attente dun événement provenant dun autre thread, comme, par exemple, la libération dun mutex.
Deux opérations sont associées aux variables conditions :
lattente dune condition,
laction de signaler quune condition est remplie.
Une variable condition est toujours associée à un mutex qui la protège des accès concurrents. Son utilisation suit le protocole suivant :
Thread en attente de condition :Thread signalant la condition : initialisation de la condition et du mutex associétravailler jusquà réaliser la condition attendueblocage du mutex et mise en attente sur la conditionblocage du mutex et signalisation que la condition est remplielibération du mutexlibération du mutexIl faut noter que la primitive effectuant la mise en attente libère atomiquement le mutex associé a Ia condition, ce qui permet au thread signalant la condition de lacquérir à son tour (étape 2). Le verrou est de nouveau acquis par le thread en attente, une fois la condition attendue signalée. Plus précisément, létape 2, pour le processus attendant la condition, peut être précisée comme suit :
blocage du mutex ;
mise en attente sur la condition et déblocage du mutex ;
condition signalée, réveille du thread et blocage du mutex, une fois celui-ci libéré par le thread signalant la condition (étape 3).
En pratique, linitialisation dune variable condition seffectue a laide de la constante PTHREAD_COND_INITIALIZER :
pthread_cond_t condition = PTHREAD_COND_INITIALIZER;
La mise en attente sur une condition se fait avec la primitive pthread_cond_wait(). Le prototype de cette primitive est :
pthread_cond_wait(pthread_cond_t *condition, \
pthread_mutex_t *mutex);
La primitive pthread_cond_signal() permet à un thread de signaler une condition remplie. Le prototype de cette primitive est :
pthread_cond_signal(pthread_cond_t *condition);
Enfin, la destruction dune variable condition se fait à laide de la function :
int pthread_cond_destroy(pthread_cond_t *condition);
Autres problématiques dinterblocages
Les schémas que nous venons de voir permettent de résoudre des problèmes rencontrés classiquement lors de la programmation de systèmes dexploitation ou de programme multi-processus. Nous allons voir quelques exemples de tels problèmes. Leurs résolutions pourront être faite dans le cadre de TD ou de TP.
Le dîner des philosophes
Le problème des philosophes et des spaghettis est un problème classique en informatique système. Il concerne l'ordonnancement des processus et l'allocation des ressources à ces derniers. Ce problème a été énoncé par Edsger Dijkstra.
La situation est la suivante :
cinq philosophes (initialement mais il peut y en avoir beaucoup plus) se trouvent autour d'une table ;
chacun des philosophes a devant lui un plat de spaghetti ;
à gauche de chaque assiette se trouve une fourchette.
Un philosophe n'a que trois états possibles :
penser pendant un temps indéterminé ;
être affamé (pendant un temps déterminé et fini sinon il y a famine) ;
manger pendant un temps déterminé et fini.
Des contraintes extérieures s'imposent à cette situation :
quand un philosophe a faim, il va se mettre dans l'état « affamé » (hungry) et attendre que les fourchettes soient libres ;
pour manger, un philosophe a besoin de deux fourchettes : celle qui se trouve à gauche de sa propre assiette, et celle qui se trouve à gauche de celle de son voisin de droite (c'est-à-dire les deux fourchettes qui entourent sa propre assiette) ;
si un philosophe n'arrive pas à s'emparer d'une fourchette, il reste affamé pendant un temps déterminé, en attendant de renouveler sa tentative.
Le problème consiste à trouver un ordonnancement des philosophes tel qu'ils puissent tous manger, chacun à leur tour.
Remarques :
Les philosophes, s'ils agissent tous de façons naïves et identiques, risquent fort de se retrouver en situation d'interblocage. En effet, il suffit que chacun saisisse sa fourchette de gauche et, qu'ensuite, chacun attende que sa fourchette de droite se libère pour qu'aucun d'entre eux ne puisse manger, et ce pour l'éternité.
On considère qu'un philosophe qui meurt (crash du processus) reste dans une phase « penser » infiniment. Il en résulte donc un problème : quid d'un philosophe qui meurt avec ses fourchettes en main ?
L'algorithme du banquier
L'algorithme du banquier est un algorithme qui a été mis au point par Edsger Dijkstra en 1965 pour éviter les problèmes interblocages et gérer l'allocation des ressources.
Cet algorithme est nommé ainsi car il reproduit le modèle du prêt à des clients par un banquier.
Dans lexemple qui suit, 5 processus sont actifs (A, B, C, D, E) et il existe 4 catégories de périphériques, les ressources P1 à P4. Considérons les deux tableaux suivants qui résument l'état d'un ordinateur à l'instant t :
1) liste des ressources actuellement attribuées à différents processus :
Ressource P1Ressource P2Ressource P3Ressource P4Processus A3011Processus B0100Processus C1110Processus D1101Processus E0000Total53222) liste des ressources demandées par chaque processus pour achever lexécution :
Ressource P1Ressource P2Ressource P3Ressource P4Processus A1100Processus B0112Processus C3100Processus D0010Processus E21103) liste des ressources disponibles au total :
Ressource P1Ressource P2Ressource P3Ressource P4Dispo. au total6342Les tableaux 1 et 3 permettent de calculer les ressources disponibles à linstant T :
Ressource P1Ressource P2Ressource P3Ressource P4Reste dispo.1020Définition : un état est dit sûr s'il existe une suite d'états ultérieurs qui permette à tous les processus d'obtenir toutes leurs ressources et de se terminer.
Problème : trouver la suite détats qui permettent à chaque processus de se terminer.
L'algorithme suivant détermine si un état est sûr :
Trouver dans le tableau 2 une ligne L dont les ressources demandées sont toutes inférieures à celles de dispo (Li
Les algorithmes dallocation mémoire
Principes généraux
Avant tout, il faut distinguer deux types dallocation :
lallocation statique (celle qui est faite au lancement dun processus, pour réserver de la place pour le code, pour la pile, les variables de taille fixe, etc). L'avantage de l'allocation statique se situe essentiellement au niveau des performances, puisqu'on évite les coûts de l'allocation dynamique à l'exécution : la mémoire statique est immédiatement utilisable ;
lallocation dynamique (qui est faite pour gérer des objets de tailles variables). Beaucoup plus souple, cette méthode oblige à allouer avant dutiliser (puis libérer une fois devenu inutile) lespace nécessaire pour stocker chaque objet.
Un algorithme simple de gestion de la mémoire consiste à regarder la mémoire libre dans son ensemble, et de lallouer au fur et à mesure. Ainsi, lorsquun processus demande N octets, le noyau cherche la première zone despace continu ayant N octets de mémoire contiguë, et lalloue. Cet algorithme, nommé « allocation first fit ».
Le problème avec cet algorithme simpliste, est quà force dallocation/désallocation, la mémoire se fragmente. Une optimisation de cet algorithme consiste à chercher le plus petit espace contiguë de mémoire libre contenant N octets (algorithme « allocation best fit »). Le système recherche le plus petit espace libre de M octets, avec M>N. Linconvénient de cet algorithme est quil génère beaucoup de petits espaces libres de « M-N » octets, qui sont inutilisés car trop petits.
Dans tous les cas, pour parcourir la mémoire, le noyau construit des listes chaînées (voire doublement chaînées) entre elles.
Implémentation sous Linux
Le noyau gère lensemble des cases libres de la mémoire centrale par lintermédiaire dune table nommée « free_area » comportant 10 entrées. Chacune des entrées comprend deux éléments :
une liste doublement chaînée de blocs de pages libres, lentrée n°i gérant des blocs de 2i pages ;
un tableau binaire nommé « bitmap », qui reflète lallocation des pages allouées. Pour une entrée i du tableau free_area (0 < i < 9), chaque nème bit du tableau reflète létat dun ensemble de deux groupes de 2i blocs de pages. Si le bit est à 0, alors les deux groupes de blocs de pages correspondant sont soit tous les deux totalement occupés, soit contiennent tous les deux au moins une page libre. Si le bit vaut 1, alors au moins lun des deux blocs est totalement occupé (et lautre contient au moins une page libre).
Le noyau gère ainsi 10 listes de blocs de pages dont la taille en page est égal à 20 (1 page), 21 (2 pages), 22 (4 pages), .. . 29 (512 pages). II effectue des demandes dallocation pour des blocs de pages contiguës de taille supérieure à 1, notamment pour satisfaire les requêtes mémoires de composants ne connaissant pas la pagination, comme cest le cas par exemple pour certains pilotes dentrées-sorties.
Lorsque le noyau traite une demande dallocation pour un nombre de i pages consécutives, il prend dans la liste log2(i) de la table free_area le premier bloc libre. Si aucun bloc na été trouvé dans cette liste, le noyau explore les listes de taille supérieure j (j>i). Dans ce dernier cas, i cases sont allouées dans le bloc de j cases et les j-i cases restantes sont replacées dans les listes de taille inférieure.
EMBED PowerPoint.Slide.8
Lorsque le noyau libère un bloc de i pages libres, il replace ce bloc dans une des listes de la table free_area, en tentant de fusionner ce bloc avec ses voisins si ceux-ci sont de même taille et si ils sont libres également. Ainsi, un bloc de 2 pages libres ayant un voisin comportant également 2 pages libres, forme un groupe de 4 pages libres. Ce groupe de 4 pages libres est inséré dans la liste de la troisième entrée de la table free_area, à moins quil ne comporte lui aussi un voisin de 4 pages libres, auquel cas il est fusionné avec lui pour former un bloc de 8 pages libres... et ainsi de suite jusquà former des groupes de 512 pages libres.
Systèmes de fichiers et implémentation
Introduction
La mémoire vive souffre de deux handicaps :
elle est (relativement) coûteuse,
elle perd ses données dès quelle nest plus alimentée en électricité.
Les disques durs (et autres périphériques de masse) ne souffrent pas de ces lacunes, mais ils ont des temps daccès qui les rendent inutilisable comme mémoire pour stoker des programmes exécutés par le CPU, ou pour stocker les variables de ces programmes.
Le compromis utilisé dans tous les systèmes dexploitation consiste à utiliser la mémoire vive pour lexécution des programmes (codes et données). Les exécutables (ceux qui sont chargés en RAM), les bibliothèques dynamiques, les données sources, et les résultats des traitements sont stockés sur les périphériques de masse.
Chaque programme (exécutable), chaque ensemble de données, chaque document, etc. est souvent stocké dans un « container » appelé fichier. Classiquement, les fichiers sont identifiés par un nom.
Sous Linux, il existe différents types de fichiers (nous rentrerons dans le détail par la suite) :
les containers de données, documents, programmes, bibliothèques, etc.
les fichiers « périphériques » (souvent sous /dev),
les fichiers de communication entre les processus (pipes),
les fichiers dinterface entre lutilisateur et le noyau (sous /proc),
les liens symboliques.
Souvent, lutilisateur a une vue logique du fichier : il le voit comme un container contenant ses données sous forme continue. En pratique, physiquement, les données sont découpées, et stockées sur le périphérique de masse, suivant un mécanisme qui permet de les retrouver, les modifier, et les effacer si nécessaire.
Parce que la gestion des fichiers deviendrait vite très difficile, tous les fichiers ne sont pas stockés « en vrac », mais sont classiquement rangés dans des « répertoires » ou « dossiers » (directory en Anglais). Dans les systèmes dexploitation modernes, ces répertoires peuvent contenir des sous répertoires, qui eux même peuvent contenir des sous-répertoires, et ainsi de suite. Lensemble de tous les répertoires, sous-répertoires, et fichiers forment une arborescence, comme par exemple (vue simplifiée) :
/ le répertoire racine
/bin : les fichiers exécutables (en binaire) pour linitialisation du système, et les commandes "essentielles ;
/boot : le noyau vmlinuz et les fichiers de démarrage (grub ou lilo
) ;
/dev : répertoire de fichiers spéciaux, qui servent de canaux de communication avec les périphériques (disques, adaptateur réseau, etc...) ;
/etc : les fichiers de configuration du système et les principaux scripts de paramétrage ;
/etc/rc.d : scripts de démarrage du système
/etc/X11 : scripts de configuration du serveur X
/etc/sysconfig : configuration des périphériques
/etc/skel : fichiers recopiés dans le répertoire personnel d'un nouvel utilisateur lorsque son compte est créé ;
/home : la répertoire contenant les répertoires personnels des utilisateurs ;
/lib : les bibliothèques et les modules du noyau
/mnt : la répertoire où sont classiquement « montés » les systèmes de fichiers des périphériques amovibles (CD-Rom, disquette, clé USB, système de fichier réseau, etc.). Nous reviendrons sur cette notion de « montage » ;
/opt : lieu d'installation d'applications supplémentaires ;
/root : répertoire personnel du super-utilisateur « root » ;
/sbin : les fichiers exécutables pour l'administration du système ;
/tmp : stockage des fichiers temporaires ;
/usr : programmes accessibles à tout utilisateur. Sa structure reproduit celle de la racine / ;
/var : données variables liées à la machine (fichiers d'impression, logs, traces de connexions http, etc.) ;
/proc : pseudo-répertoire contient une « image » du système ( par exemple, /proc/kcore est une image virtuelle de la RAM).
Le sous-ensemble du système dexploitation qui assure la gestion cette arborescence, les fichiers quils contiennent, etc. sappelle le système de gestion de fichiers (SGF), ou tout simplement système de fichiers (SF), file system (FS) en Anglais. Voici une liste non exhaustive de systèmes de gestion de fichiers célèbres :
ext2, ext3 : Extented FS version 2 et 3 (Linux, BSD) ;
FAT : File Allocation Table (DOS/Windows, Linux, BSD, OS/2, Mac OS X). Se décompose en plusieurs catégories :
FAT12,
FAT16,
FAT32,
VFAT ;
FFS : Fast File System (BSD, Linux expérimental) ;
HFS et HFS+ : Hierarchical File System (Mac OS, Mac OS X, Linux) ;
HPFS : High Performance FileSystem (OS/2, Linux) ;
minix fs (minix, Linux) ;
NTFS : New Technology FileSystem (Windows NT/2000/XP, Linux écriture expérimentale , Mac OS X en lecture seule) ;
ReiserFS (Linux, BSD en lecture seule) ;
CFS : Cryptographic File System - FS chiffré (BSD, Linux) ;
cramfs : FS compressé (Linux en lecture seule) ;
EFS : Encrypting File System : FS chiffré au-dessus de NTFS (Windows) ;
ISO 9660 : en lecture seule sur tous les systèmes lisant les CDROM/DVDROM ;
QNX4fs : FS utilisé pour le temps réel (QNX, Linux en lecture seule) ;
UDF : format de disque universel (système de fichiers des DVD-ROM et des disques optiques réinscriptibles tels les CD-RW, DVD±RW, etc.).
Certains file systems permettent daccéder à des périphériques via un réseau :
AFS : Andrew File System : (Aix, Linux expérimental) ;
Coda : Systèmes de fichiers informatique (Linux) ;
NFS : tous les Unix, Linux, Mac OS X (Windows pour la 4) ;
NCP : NetWare Core Protocol (Novell NetWare, Linux en client seul) ;
SMB : Server message block (Windows, Linux, BSD et Mac OS X via Samba) ;
CIFS : Evolution de SMB, supporté par Samba ainsi que par Windows 2000 et XP.
Le fichier logique
Comme nous lavons vu, lutilisateur (le programmeur) voit un fichier de données comme un container qui stocke celles ci de façon linéaire. Les opérations classiques réalisées sur un fichier sont :
ouvrir le fichier (soit en lecture seule, soit en écriture, ou en lecture+écriture),
lire dans le fichier à partir dune « tête de lecture virtuelle »,
écrire dans le fichier à partir dune « tête de lecture virtuelle »,
dans certains cas, déplacer cette « tête de lecture virtuelle » dans le fichier,
puis enfin, fermer le fichier.
Il est aussi possible de :
renommer un fichier,
le déplacer (le changer de répertoire),
et dans certains systèmes, de créer un lien (physique ou logique) vers un fichier (nous verrons cette notion plus tard).
A noter que les « supports de masse » peuvent permettre des accès selon différents modes :
les bandes magnétiques, lecteurs DAT ou streamer permettent des accès séquentiels (la lecture se fait « en continu »),
les disques durs, CD-Rom, clés USB, etc. permettent des accès directs aux données (il est possible de déplacer la « tête de lecture virtuelle » à nimporte quel endroit du fichier),
enfin, pour faciliter les recherches, il est possible dutiliser une notion de clé, clé qui permet de déterminer la position dune donnée sur un disque. On parlera alors daccès indexé (ou accès aléatoire).
Généralités sur la résolution de nom
Comme nous lavons vu, un fichier est identifié par un « nom ». Suivant les systèmes dexploitation, les noms peuvent avoir des formes très différentes. Nous pouvons toutefois reconnaître certaines propriétés constantes :
pour chaque disque, ou pour chaque partition (nous reviendrons sur ce concept de partition, mais retenez quil sagit souvent de découper un disque physique en plusieurs disques virtuels, appelés alors « partition »), il existe un dossier qui contient tous les fichiers et sous-dossiers, appelé parfois « répertoire racine » ou tout simplement « racine » ;
le « nom de fichier » contient le nom lui-même, mais peu aussi être préfixé de la suite de répertoire et sous-répertoires dans lequel il se trouve (on parle alors de « chemin » ;
chaque programme qui sexécute possède dans la plupart des OS un « répertoire courant », appelé aussi « répertoire de travail ». Très souvent, un processus hérite du répertoire courant de son père. Mais il arrive aussi (cest souvent le cas par défaut dans les OS graphiques) que le répertoire courant soit le répertoire qui contient lexécutable, ou soit une des propriétés de licône qui le représente. Des primitives permettent à un programme de changer son répertoire courant ;
aussi, le « chemin » qui référence un fichier peut être relatif à ce répertoire courant (on parle alors de chemin relatif), ou peut contenir toutes les informations qui permettent de le localiser (ordinateur, disque, partition, suite de répertoires/sous-répertoires, etc.). On parle alors de chemin absolu ;
il existe un caractère séparateur permettant de différencier les différents répertoires/sous-répertoires dans un chemin (par exemple, il sagit du slash « / » sous Unix/Linux, et de lanti-slash « \ » sous Windows ;
il existe un ou plusieurs caractère(s) qui traduisent le répertoire courant (il sagit du point « . » pour Unix/Linux et Windows), et un ou plusieurs caractère(s) qui traduisent le répertoire parent (il sagit de deux points à la suite « .. » pour Unix/Linux et Windows). A noter que le répertoire parent de la racine est la racine elle-même.
Lensemble théorique de tous les noms possibles sappelle lespace de nom. Dans les systèmes dexploitations modernes, cet espace de nom peut contenir différents sous-ensembles, chacun étant géré par un file system différent. Certains de ces systèmes de gestions de fichiers permettent daccéder à des périphériques locaux (par exemple, FAT16 pour un lecteur de disquette, ext3 pour un disque dur, NTFS pour un disque dur externe USB, etc.), et dautres, à des périphériques accessibles via le réseau (par exemple, NFS pour accéder à un partage Unix, SMB/CIF pour accéder à un partage Windows/Samba, etc.).
A noter que chaque gestionnaire de gestion de fichiers possède ses propres propriétés en terme de :
profondeur maximum dimbrication des répertoires/sous-répertoires,
nombre maximum de lettres dans un nom de répertoire ou de fichier,
nombre maximum de lettres au total dans le nom,
de différentiation majuscules/minuscules ( FS case sensitive ou pas),
la prise en charge (ou pas) des « localisations » (caractères accentués, support de plusieurs pages de codes, etc.),
niveau de sécurité (gestion ou pas de notion dutilisateur propriétaire, de groupes, daccess list ACLs , etc),
propriétés (gestions de notions de fichiers cachés, de fichiers exécutables, de droits en terme de lecture/écriture, date de création, date de dernier accès, date de dernière modification, etc.) ;
de chiffrement (certain FS permettent de crypter les données contenues),
de compression (certains FS permettent de compresser des données pour gagner de la place),
de journalisation (chaque opération décriture est journalisée dans un fichier spécial ; ainsi, en cas darrêt violent du système, il est possible de réparer rapidement la structure du file system à laide de ce journal, sans avoir à parcourir tout le disque) ;
etc.
A noter quun informaticien, Tim Berners-Lee, a proposé dans le RFC 1630, mis à jour par le RFC 2396, puis par le 3986, une norme standard de nomenclature : lURI (Uniform Resource Identifier). Il est probable que les futures versions des OS sauront lire directement les URIs.
Le fichier physique
Le disque dur
Chaque disque dur est constitué :
dun ensemble de plateaux (souvent, jusquà 20), ce qui forme une pile de disques ;
chaque plateau possède 2 faces ;
chaque face est découpée en « pistes » (cercles concentriques). Suivant les modèles, chaque plateau peut être découpé de 10 à plus de 1000 pistes. A noter que chaque ensemble de pistes situées les unes au dessus des autres sur les différents plateaux sappellent des cylindres ;
enfin, chaque piste est découpée en secteurs (souvent, de 4 à 32 secteurs par piste). Selon les modèles, toutes les pistes peuvent contenir le même nombre de secteurs, ou avoir un nombre de secteurs plus petit pour les pistes proches de laxe, et plus grand pour les pistes qui en sont éloignées. Quoi quil en soit, chaque secteur contient en général de 32 à 4096 octets (couramment : 512 octets).
Lopération qui consiste à créer une telle structure logique à partir du disque physique sappelle le formatage.
Les têtes de lecture/écriture sont fixées à un bras, faisant ressembler lensemble à un peigne. Un disque peut donc lire en parallèle tous les secteurs situés les uns au dessus des autres.
EMBED PowerPoint.Slide.8
Pour optimiser les accès aux secteurs, ceux-ce sont regroupés en « blocs ». Le bloc constitue la plus petite unité déchange entre le disque et la mémoire centrale. Vous laurez compris, la taille dun bloc dépend fortement de la structure physique du disque.
Les méthodes dallocation des mémoires secondaires
Physiquement, les fichiers logiques sont découpés en morceaux, eux même stockés dans des blocs. Or les fichiers se constituent, grandissent, rapetissent, seffacent, dautres sont créés... lespace disque libre subit le même phénomène que la mémoire centrale : il se fragmente.
Tout lart des gestionnaires de fichiers consiste à :
proposer une structure permettant de stocker sur le disque lespace de noms (comment lutilisateur aura découpé lespace de nom en répertoire, sous-répertoire, etc.),
allouer les blocs libres aux fichiers qui se constituent et grandissent afin déviter la fragmentation.
On retrouve principalement quatre méthodes dallocation des blocs :
la méthode lallocation contiguë : cette méthode suppose que le fichier sera stocké sur des blocs qui se suivent physiquement. Cette méthode est simple et efficace, mais peu utilisée : elle impose au programmeur de connaître à lavance la taille finale du fichier. Comme pour la mémoire centrale, il existe deux algorithmes permettant lallocation contiguë :
lallocation « first fit » : la première zone de blocs contiguë de taille supérieure ou égale à celle du fichier est allouée,
lallocation « best fit » : le système recherche lespace libre de a taille la plus petite possible pouvant contenir le fichier ;
la méthode dallocation par zones : il sagit dune extension de la méthode précédente. Ici, un fichier peut-être constitué de zones. Chaque zone est constituée de blocs contiguës, mais les zones ne sont pas nécessairement contiguës. Le début du fichier est stocké dans une « zone primaire », le reste étant stocké dans des « zones secondaires », qui sont allouées au fur et à mesure que le fichier grandit. Souvent, le nombre de zones secondaires est limité (limitant ainsi la possibilité dextension dun fichier). Les temps daccès peuvent être moins bons (si les zones ne sont pas physiquement contiguës, le contrôleur de disque devra déplacer le bras pour changer les têtes de place), mais cette méthode permet à un fichier de grandir ;
la méthode dallocation par blocs chaînés : dans cette méthode, le fichier est disposés dans une suite de blocs chaînés entre eux, qui peuvent être disposés physiquement nimporte où sur le disque. Pour étendre un fichier, il suffit de prendre un bloc libre, et de créer un lien entre le dernier bloc alloué précédemment et ce nouveau. Cette méthode possède deux inconvénients majeurs : la seule méthode de lecture est la lecture par accès séquentiel ; de plus, elle occupe de la place sur le disque pour stocker le chaînage ;
la méthode dallocation indexée : dans cette méthode, toutes les adresses des blocs physiques constituant un fichier sont rangés dans une table appelée index, elle même contenue dans un bloc du disque. A la création dun fichier, un index est créé, avec toutes ses entrées initialisées à 0. Ces entrées sont ensuite mises à jour au fur et à mesure que le fichier grandit. Ce regroupement de toutes les adresses des blocs dun fichier dans une même table permet un accès direct. De plus, les blocs alloués au fichier ne contiennent que des données du fichier (et plus de liens vers dautres blocs). Apparaissent néanmoins deux problèmes :
si la taille du fichier est petite, et que la taille dun blocs est grand, nous perdons beaucoup de place ;
inversement, si le fichier est grand, un seul bloc peut ne pas suffire à stocker tous les blocs composant un fichier. Dans ce cas, la solution est de réaliser un index multiniveaux : le premier bloc dindex ne contient pas une liste du blocs contenant les données du fichier, mais une liste de blocs dindex. Ainsi, la taille maximale potentielle dun fichier est agrandie exponentiellement. Par contre, il faudra lire deux blocs (et non plus un seul) avant de pouvoir accéder aux données dun fichier. Evidemment, plus le nombre de niveaux est important, plus le temps passé à suivre les indexes est important, réduisant ainsi les performances.
La gestion de lespace libre
Le système conserve une liste despace libre, qui mémorise tous les blocs libres du disque. Lors de la création ou de lagrandissement dun fichier, le système cherche dans cet espace des blocs pour les alloués au fichier. Ces derniers sont alors ôtés de la liste. Lors de la destruction dun fichier, les blocs le constituant sont alors remis dans cette liste des blocs libres.
Parmi les méthodes utilisées pour recenser lespace libre, deux sont principalement utilisées :
la gestion de lespace libre par vecteur de bits : dans cette méthode, un tableau binaire (ne contenant que des 0 et des 1) indique la disponibilité dun blocs. Si le ième bit du tableau est à 0, le blocs numéro i est libre. Sinon, il est occupé. La longueur de ce vecteur binaire est donc égal au nombre de blocs dans le disque ;
la gestion de lespace libre par liste chaînée : ici, les blocs libres sont chaînés entre eux. Linconvénient ce cette méthode est que si nous avons besoin dallouer N blocs consécutifs, nous seront peut-être obligé de parcourir une longue liste de blocs. Une variante de cette méthode consiste à regrouper les blocs libres dans une zone, et dindiquer dans chaque premier bloc dune zone libre le nombre de blocs contigus, puis le lien vers le premiers blocs de la zone suivante (constituée elle aussi de blocs contigus).
Les partitions
Comme nous lavons déjà vu, le nombre de fichiers pouvant être stockés dans un disque peut être très important. Pour éviter que tous les fichiers soient stockés uniformément dans le même disque physique, ce dernier peut être découpé en un ou plusieurs disques logiques : on parle alors de partitions, ou de volumes.
Chaque partition peut être repérée par un nom, appelé label.
En ce qui concerne les PC, les informations liées aux partitions sont stockés dans une table, appelée table des partitions. Cette table des partitions était stockée dans le premier bloc du disque (appelé MBR, pour master boot record). Comme ce bloc est de taille réduite, le système ne pouvais gérer historiquement que quatre partitions. Or, ce chiffre sétant par la suite révélé insuffisant, une astuce a consisté à typer les partitions. Le système doit posséder au minimum une partition primaire (qui sont les seules à pouvoir contenir un secteur damorçage, qui contient le chargeur du noyau), et au maximum une partition secondaire (ou partition étendue), qui doit toujours être la dernière. Celle-ci peut alors contenir autant de lecteurs logiques que souhaités, qui sont autant de partitions (mais qui ne peuvent être amorçables).
Le montage dune partition
Sous Windows, chaque disque, ou chaque partition est identifié avec une lettre de lecteur (« A: » et « B: » sont généralement réservés pour les lecteurs de disquettes, « C: » pour la partition amorçables, etc.
Sous Unix/Linux, une partition doit être montée sous un répertoire. Ainsi, il est nécessaire davoir au minimum une partition : la partition sous laquelle sera montée la racine de lespace de noms (on parle aussi de partition root dans la littérature anglaise).
La création dun lien « répertoire ( partition » sappelle le montage. Cette opération se fait automatiquement à linitialisation du système (la partition « root » à monter au démarrage est un paramètre du noyau, souvent fourni par le « boot loader » (fréquemment lilo ou grub pour Linux) ; puis, les scripts dinitialisation regardent alors les différents montages quils doivent réaliser dans le fichier de configuration « /etc/fstab »). Cette opération de montage/démontage peut ensuite être effectuée à tout moment par le super utilisateur, à laide des commandes « mount » et « umount » (qui, elles-même, font appel à des primitives système « mount() » et « umount() »).
A noter que les différentes partitions peuvent toutes être gérées par un « file system » différent. Par exemple, la racine peut être une partition de type ext3. Le dossier « /home » peut se voir monter une partition de type « reiserfs », le répertoire « /mnt/floppy » se voit monter une partition de type « vfat », alors que le répertoire « /mnt/cdrom » se voit monter une partition de type « iso9660 ».
Exemple de système de gestion de fichier : ext2
Historiquement, Linux était un projet dont le but avoué était de pouvoir lire des partitions de type minix (gestionnaire de partition très limité : adressage des blocs sur 16 bits ce qui limite la taille des fichiers à 64 Ko , un nombre de 16 entrées maximum dans chaque répertoire, et des noms de fichiers ne pouvant excéder 14 caractères).
Depuis, Linux a été profondément remodeler pour acquérir une couche virtualisant les file systems (Cf. prochain chapitre), ainsi que des systèmes de fichiers plus évolués et ayant moins de contraintes. Nous allons étudier dans ce chapitre lun des plus connu dentre eux : le gestionnaire de fichiers ext2.
La structure di-node
Un fichier physique Linux est identité par un nom et toutes les informations le concernant sont stockées dans un descripteur appelé i-node ou i-nud. Ensuite, le fichier na pas de structure logique et est simplement constitué comme une suite doctets.
Les blocs sont alloués au fichier selon une organisation indexée. Chaque bloc est identité par un numéro logique qui correspond à son index dans la partition du disque et est codé sur 4 octets. La taille dun bloc devant être une puissance de 2, multiples de la taille dun secteur (généralement 512 octets), elle varie selon les systèmes entre 512, 1'024, 2'048 ou 4'096 octets.
Linode du fichier est une structure stockée sur le disque, allouée à la création du fichier, et est repérée par un numéro. Un i-node contient les informations suivantes:
le nom du fichier ;
le type du fichier et les droits daccès associés ;
les identificateurs du propriétaire du fichier ainsi que du groupe ;
diverses heures telles que lheure de dernier accès au fichier, lheure de dernière modification du contenu du fichier, lheure de dernière modification de linode, lheure de suppression du fichier ;
le nombre de liens vers dautres fichiers ;
Ia taille du fichier (en octets) ;
le nombre de blocs de données alloués au fichier ;
deux listes de contrôle daccès respectivement pour le fichier et pour le répertoire ;
une table dadresses des blocs de données.
Les types de fichier sous linux sont :
les fichiers réguliers (ou normaux) : « regular files » sont les fichiers les plus courants. Ils sont destinés à stocker les données des utilisateurs quel que soit le type de ces données. Ces fichiers sont sans organisation et ne constituent quune suite doctets, caractérisée par sa longueur ;
les répertoires ;
les liens symboliques. Il sagit de pointeurs (alias) vers un autre fichier. Toute action effectuée sur le contenu dun lien équivaut a une action sur le fichier pointé ;
les fichiers de périphériques. Se sont des fichiers liés a un pilote dentrées-sorties au sein du noyau. Une opération de lecture ou décriture réalisée sur le fichier équivaut à une action sur le périphérique. On distingue à ce niveau :
les fichiers spéciaux en mode bloc (ex : disques), pour lesquels les échanges seffectuent bloc après bloc,
et les fichiers spéciaux en mode caractère (ex : les terminaux) pour lesquels les échanges seffectuent caractère après caractère.
Ces fichiers spéciaux, ainsi que le mécanisme des entrées-sorties feront lobjet dun prochain chapitre ;
les tubes nommés (pipes) et les sockets.
A noter que les liens symboliques, les tubes nommés, les sockets et les fichiers de périphériques sont des fichiers dont la structure physique se résume a lallocation dun i-node. Aucun bloc de données ne leur est associé.
Les droits classiques sur les fichiers sous Unix/Linux
Les droits des fichiers sont appliqués à trois groupes de comptes utilisateurs :
le propriétaire du fichier,
le groupe qui contient le propriétaire du fichier,
tous les autres comptes, qui ne sont ni le propriétaire, ni un membre du groupe auquel il appartient.
Trois types de permissions peuvent être donnés à des fichiers :
la permission en lecture,
la permission en écriture,
la permission en exécution.
En interne, une constante en octale est liée à chacun de ces droits :
4 pour la permission en lecture,
2 pour la permission en écriture,
1 pour la permission en exécution.
Par exemple, un droit en lecture+exécution vaudra 4+1 = 5. Traditionnellement, les droits sont représentés en octal sous la forme : 0XYZ, avec X le droit pour le propriétaire, Y le droit pour le groupe auquel il appartient, et Z le droit pour les autres utilisateurs. Par exemple, un droit de « 0750 » signifie que le propriétaire peut tout faire (lire, écrire, et exécuter), le groupe auquel il appartient peut lexécuter et le lire, alors que les autres utilisateurs ne peuvent accéder au fichier. Pour un répertoire, le droit « x » signifie « peut accéder au contenu du répertoire ».
Enfin, 3 autres bits ont une signification particulière :
le bit « setuid » : un exécutable pour lequel ce bit est positionné sexécute avec lidentité du propriétaire du fichier et non avec celle de lutilisateur qui a demandé lexécution ;
le bit « setgid » : un exécutable pour lequel ce bit est positionne sexécute avec lidentité du groupe du propriétaire du fichier, et non avec celle de lutilisateur qui en a demandé lexécution ;
enfin, le bit « sticky » : les fichiers appartenant a un répertoire pour lequel ce bit est positionné ne peuvent être supprimés que par leurs propriétaires.
La commande shell « ls -al » permet de lister tous ces attributs pour les fichiers dun répertoire :
le premier champ code le type du fichier et les droits associes au fichier. Le type (1 caractère) est codé par une lettre qui prend la valeur suivante :
d pour un répertoire (directory),
p pour un tube (pipe),
l pour un lien symbolique,
b pour un périphérique « bloc »,
c pour un périphérique « caractère »,
- pour un fichier ordinaire ;
Les droits daccès sont codés par groupe de trois caractères, correspondant a chacune des permissions possibles pour chacune des trois entités citées au paragraphe précédent. Ainsi « rwxr--r-x » indique que lutilisateur peut lire, écrire, et exécuter le fichier (premier groupe « rwx »), le groupe peut seulement lire le fichier (deuxième groupe « r-- »), tandis que les autres peuvent lire et exécuter le fichier (troisième groupe « r-x ») ;
le deuxième champ indique le nombre de liens pour le fichier ;
le troisième champ indique le nom de lutilisateur propriétaire du fichier ;
le quatrième champ indique le nom du groupe ;
le cinquième champ indique le nombre doctets composant le fichier ;
le sixième champ indique la date de dernière modification du fichier ;
le dernier champ indique le nom du fichier.
La commande shell « chmod droit fichier » permet de changer les droits du fichier « fichier », afin de les positionner à « droit ». Cf. « man chmod » pour plus de détails.
Liens physiques et liens symboliques
Le système de gestion de fichiers ext2 manipule deux types de liens : les liens physiques, et les liens symboliques.
Le lien physique correspond à lassociation dun nom a un fichier (et donc, a un i-node). Un même fichier peut recevoir plusieurs noms différents, dans un même répertoire, ou dans des répertoires différents dune même partition. Créer un lien physique sur un fichier équivaut a créer une nouvelle entrée dans un répertoire pour mémoriser lassociation « nom de fichier i-node ». Un lien physique ne peut pas être créé sur un répertoire.
Le lien symbolique correspond à la création dun fichier de type particulier (de type « l »), qui contient comme donnée un pointeur vers un autre fichier (+/- le raccourcis sous Windows).
La commande « ln nomfichier1 nomfichier2 » crée un lien physique sur le fichier nomfichier1, en lui attribuant un nouveau nom nomfichier2.
La commande « ln -s nomfichier1 nomfichier2 » crée un lien symbolique sur le fichier nomfichier1, en créant le fichier nomfichier2 qui contient comme donnée le chemin daccès au fichier nomfichier1.
Lallocation des blocs de données
Li-node du fichier contient un tableau de EXT2_NBLOCKS entrées, contenant chacune un numéro de bloc logique. Par défaut la valeur de EXT2_NBLOCKS est égale à 15.
Lorganisation de cette table suit lorganisation indexée sinspirant de celle que nous avons vus précédemment, à une différence près, qui réalise une optimisation.
Ainsi :
les 12 premières entrées du tableau contiennent un numéro de bloc logique correspondant directement à un bloc de données du fichier ;
la treizième entrée sert de premier niveau dindex. Elle contient un numéro de bloc logique contenant lui-même des numéros de blocs logiques qui correspondent à des blocs de données ;
la quatorzième entrée sert de deuxième niveau dindex. Elle contient un numéro de bloc logique contenant lui-même des numéros de blocs logiques qui contiennent à leur tour les numéros de blocs logiques correspondant a des blocs de données ;
enfin, la quinzième entrée introduit un niveau dindirection supplémentaire.
EMBED PowerPoint.Slide.8
Adressage des blocs constituant un fichier ext2
Lors de la création dun fichier, aucun bloc de données ne lui est alloué. Les blocs sont attribués au fichier au fur et à mesure de son extension, en commençant par allouer les 12 premières entrées de la table, puis en emplissant ensuite le premier niveau dindirection, puis le second et enfin le troisième si besoin est.
Pour des raisons defficacité, et de façon à réduire la fragmentation du fichier, le système pré-alloue des blocs de données. Plus précisément, lorsque le système alloue un nouveau bloc pour le fichier, il pré-alloue en même temps jusquà 8 blocs adjacents. Ces blocs pré-alloués sont libérés lorsque le fichier est fermé, sils nont pas été utilisés.
Structure des partitions
Une partition Linux/ext2 est composée dun bloc damorçage, utilisé lors du démarrage du système, puis dun ensemble de groupe de blocs, chaque groupe contenant des blocs de données et des i-nodes enregistrés dans les pistes adjacentes. En effet, chaque groupe de blocs contient les informations suivantes :
une copie du super bloc (Cf. ci-dessous) du système de gestion de fichier,
une copie des descripteurs de groupe de blocs (Cf. ci-dessous),
un vecteur de bits pour gérer les blocs libres du groupe,
un groupe di-nodes, souvent appelé « table des i-nodes ». Le numéro de li-node est égal à son rang dans cette table,
un vecteur de bits pour gérer les i-nodes libres,
des blocs de données.
EMBED PowerPoint.Slide.8
Le super bloc contient des informations générales sur la partition, tel que :
le nom de la partition ;
des statistiques comme Iheure de la dernière opération de montage, et le nombre dopérations de montage réalisées sur la partition ;
la taille de la partition (en bloc) ;
le nombre total di-nodes dans la partition ;
Ia taille dun bloc dans la partition ;
le nombre de blocs libres et di-nodes libres dans la partition ;
le nombre de blocs et di-nodes par groupe ;
lheure du dernier contrôle de cohérence et lintervalle de temps entre chaque contrôle de cohérence.
Ce super-bloc est dupliqué dans tous les groupes de blocs. Le système utilise couramment la copie placée dans le groupe de blocs 0. La mise à jour des copies placées dans les autres groupes de blocs a lieu lors des contrôles de cohérence du système de gestion de fichiers (commande « /sbin/e2fsck »). Si une corruption est constatée sur le super-bloc du groupe 0, alors les copies redondantes sont utilisées pour ramener la partition à un état cohérent.
Chaque groupe de blocs est associé à un descripteur de groupe de blocs qui contient les informations suivantes :
les numéros des blocs contenant les vecteurs de bits gérant la liste des blocs libres et la liste des i-nodes libres ;
le nombre de blocs libres et le nombre di-nodes libres dans le groupe ;
le nombre de répertoires dans le groupe ;
le numéro du premier bloc contenant les i-nodes libres.
Dune façon similaire au super-bloc, les descripteurs des groupes de blocs sont dupliqués dans tous les groupes de blocs. Les mises à jour sont effectuées lors des contrôles de cohérences de la partition.
Afin de réduire la fragmentation, le système Linux tente dallouer un nouveau bloc à un fichier dans le groupe de blocs contenant le dernier bloc alloué pour ce même fichier. Sinon, il cherche un bloc libre dans le groupe de blocs contenant linode du fichier.
La liste des blocs libres et la liste des i-nodes libres sont gérées par lintermédiaire de deux vecteurs de bits. Un bit égal à 0 signifie que le bloc de donnée ou li-node correspondant est libre, et la valeur 1 signifie au contraire que le bloc de donnée ou li-node correspondant est occupé. Chacun des vecteurs de bits est entièrement compris dans un seul bloc du disque.
Le système de gestion de fichiers virtuel VFS
Introduction
Comme nous lavons déjà vu, Linux est capable davoir, dans son arborescence globale (dans son espace de noms) plusieurs file systems. Comme il est inconcevable que lutilisateur (le programmeur) ait à utiliser plusieurs primitives selon le file system qui gère le fichier auquel il accède, Linux utilise une couche virtuelle entre le file système réel et lutilisateur. Cette couche virtuelle se présente comme un système de gestion de fichiers virtuel, appelé VFS (Virtual File System).
Lutilisateur appelle les primitives de VFS sur un fichier. Selon le file system qui gère le fichier en question, le système traduira ces appels aux routines de VFS en leur équivalent pour le file system réel en effectuant les opérations suivantes :
vérification des paramètres ;
conversion du nom de fichier en numéro de périphérique et numéro di-node ;
vérification des permissions ;
appel a la fonction spécifique au système de gestion de fichiers concerné.
En plus de cette normalisation des appels aux primitives de gestion de fichier, VFS gère deux systèmes de cache :
un cache de noms qui conserve les conversions les plus récentes des nom de fichiers en numéro de périphérique et numéro di-node ;
un cache de tampons disque appelé buffer cache, qui contient un ensemble de blocs de données lus depuis le disque.
Structures et fonctionnement de VFS
Les structures du VFS créent un modèle de fichier, pour tout système de gestion de fichiers, qui est très proche du modèle de fichier natif de Linux ext2. Ce choix permet au système de travailler sur son propre système de gestion de fichiers avec un minimum de surcharge.
La structure du VFS est organisée autour dobjets auxquels sont associés des traitements. Les objets sont :
lobjet « système de gestion de fichiers » (super-bloc), représenté par une structure « super-bloc » (struct super_block, définie dans ), qui contient des informations sur les caractéristiques du système de gestion de fichiers, telles que :
la taille des blocs,
les droits daccès,
la date de dernière modification,
le point de montage sur larborescence de fichiers.
Cette structure offre un ensemble dopérations permettant de manipuler le système de gestion de fichiers associé (champ struct super_operations *s_ops), notamment lire ou écrire un i-node, écrire le super-bloc, et obtenir des informations sur le système de gestion de fichiers. Lensemble des structures super_block est regroupé dans une liste doublement chaînée ;
lobjet « i-node » : décrit par un i-node (structure struct inode définie dans ). Cette structure contient des informations sur le fichier associé à li-node de même nature que celles trouvées dans un i-node de type ext2. Elle contient par ailleurs des informations spécifiques liées au type de système de gestion de fichiers, ainsi que des méthodes permettant de manipuler la structure (struct inode_operations *i_op). Lensemble des i-nodes est géré de deux façons différentes :
une liste circulaire doublement chaînée regroupe lensemble des i-nodes ;
et pour la recherche rapide dun i-node particulier, laccès seffectue par le biais dune table de hachage, avec pour clé de recherche, lidentifiant du super-bloc et le numéro de linode dans ce super-bloc.
lobjet « fichier » (file) : chaque fichier ouvert est décrit par une structure struct file (définie dans ). Cette structure contient un ensemble dinformations utiles pour la réalisation des opérations de lecture et décriture sur le fichier, telles que le type daccès autorisé, la position courante dans le fichier, le nombre de processus ayant ouvert le fichier, etc. Comme pour les structures précédentes, la structure struct file inclut un ensemble de méthodes (struct file_operations *f_op) permettant de manipuler la structure, qui sont les opérations pour la lecture, lécriture, louverture, ou la fermeture dun fichier, etc. ;
lobjet « nom de fichier » (dentry) : les objets nom de fichier (ou dentry) sont créés pour mémoriser les entrées de répertoire lues lors de la recherche dun fichier. Ainsi la recherche du fichier « /home/manu/test.c » aboutit à la création de trois objets dentry (un pour home, le suivant pour manu, le denier pour test.c), chaque objet dentry effectuant le lien entre le nom et le numéro dinode associé. Ces objets sont par ailleurs gérés par le cache des noms.
Accès à VFS par un processus
Chaque processus accède à un fichier ouvert en utilisant un « descripteur de fichier ». Ce descripteur de fichier est en fait un numéro dindex dans la table des fichiers ouverts.
En pratique, chaque entrée de cette table des fichiers ouverts, appelé fd (descripteur de fichier), pointe vers un objet de type fichier. Lui-même pointe à son tour vers un objet de type dentry, afin deffectuer la liaison entre le nom du fichier et son i-node. Cet i-node pointe à son tour ver lobjet « super-blocs » décrivant le système de gestion de fichiers auquel appartient le fichier.
Par ailleurs, le champ fs du bloc de contrôle du processus (PCB) pointe sur un objet fichier, qui correspond au répertoire courant du processus.
A noter que quà la création de chaque processus, le fils hérite des fichiers ouverts du père (la table des fichiers ouverts est dupliquées). De plus, 3 fichiers sont toujours déjà ouverts :
lentrée numéro 0 dans la table des descripteurs de fichiers correspond à lentrée standard, appelée stdin, correspondant par défaut au clavier ;
lentrée numéro 1 dans la table des descripteurs de fichiers correspond à la sortie standard, appelée stdout, correspondant par défaut à lécran ;
enfin, lentrée numéro 2 dans la table des descripteurs de fichiers correspond à la sortie des messages derreur, appelée stderr, correspondant par défaut à lécran.
EMBED PowerPoint.Slide.8
Un champ « f_count » permet de savoir par combien de processus un fichier est ouvert (appelé « nombre de référence »). Le fichier est libéré (et la structure est effacée) lorsque que ce compteur est à zéro. De plus, le champ « f_pos » indique la position courante de la tête de lecture virtuelle dans le fichier (appelé « pointeur du fichier »).
Comme exercice, regardons les actions effectuées par le VFS lors de louverture dun fichier (appel à la primitive desc = open(nom_fichier, mode_ouventure)) :
la routine denveloppe correspondant a la fonction open() lève une trappe, bascule le processus appelant en mode superviseur, puis appelle la routine système sys_open() après avoir passé les paramètres dexécution (nom du fichier et mode douverture) ;
une nouvelle entrée est allouée dans la table des fichiers ouverts et un nouvel objet fichier pointé par cette entrée est créé ;
le nom de fichier est converti en numéro de périphérique et i-node, et lobjet dentry correspondant est associé au fichier ;
li-node associée au fichier est obtenue (méthode look_up de lobjet i-node représentant le répertoire contenant le fichier) ;
les opérations concernant le fichier (champ *f_ops de lobjet fichier) sont initialisées depuis le champ default_file_ops de la structure i_op de li-node correspondant au fichier ;
la méthode open de lobjet fichier est appelée pour réaliser louverture physique du fichier en fonction du type du système de gestion de fichiers ;
lindex de lentrée de la table des fichiers ouverts pointant sur lobjet fichier est retourné a lutilisateur. Elle constitue le descripteur desc du fichier.
Le fonctionnement du cache des dentry (dcache)
Lorsque le VFS doit lire un fichier depuis le support de masse, il doit au préalable convertir le nom logique du fichier vers son équivalent physique, à savoir le numéro du périphérique contenant le fichier, et le numéro de linode descriptive du fichier. Prenons par exemple la recherche du fichier dont le chemin est « manu/tp/test.c » pour le compte de lutilisateur manu. Le traitement de ce chemin daccès suit les étapes suivantes :
le chemin ne commençant pas par « / », la recherche seffectue depuis Ie répertoire courant du processus, dont li-node est repérée depuis le bloc de contrôle du processus. Si le chemin du fichier avait commencé par « / », Ie chemin absolu aurait été analysé à partir de li-node de la racine du système de gestion de fichiers, qui est également conservée en mémoire. En utilisant li-node décrivant le répertoire courant, le VFS recherche dans les blocs de données de ce fichier répertoire lentrée concernant « manu ». Lentrée trouvée, le VFS connaît le numéro di-node associé à « manu ». Un objet dentry est créé pour ce couple ;
linode décrivant le répertoire « manu » est lue depuis le disque, et lentrée concernant « tp » est recherchée dans les blocs de données de ce fichier répertoire. Lentrée trouvée, le VFS connaît Ie numéro di-node associé à « tp ». Un objet dentry est créé pour ce couple ;
linode décrivant le répertoire « tp » est lue depuis le disque et lentrée concernant « test.c » est recherchée dans les blocs de données de ce fichier répertoire. Lentrée trouvée, le VFS connaît le numéro di-node associé a « test.c ». Un objet dentry est créé pour ce couple.
Cet exemple montre que la recherche dun i-node associée à un fichier est un traitement long et coûteux. Aussi, le VFS maintient-il un cache de tous les objets dentry créés au cours de cette recherche. Ainsi, lorsque le VFS cherche le numéro di-node associé à un nom de répertoire, il regarde tout dabord dans le cache si un objet dentry concernant ce nom existe. Si oui, il récupère le numéro di-node associé sans lecture disque. Sinon, il lit les blocs de données associés au répertoire depuis le disque jusquà trouver lentrée recherchée.
Le cache des blocs disque (buffer cache)
Le VFS maintient également un cache contenant les blocs disque les plus récemment accédés. Lors de la lecture dun bloc, celui-ci est place dans une zone mémoire appelée tampon (buffer). Ainsi, lorsque le VFS cherche a accéder a un bloc du disque, il consulte dabord lensemble des tampons présents dans le cache. Si le tampon correspondant est présent, alors lopération de lecture ou décriture est réalisée dans le cache. Sinon, le bloc est lu depuis le disque et place dans un tampon libre sil en existe un. Sinon, le VFS récupère le tampon le moins récemment utilisé pour y placer le nouveau bloc dont il a besoin.
Remarque : dans le cas dune écriture, le bloc est modifié en mémoire centrale sans être recopié immédiatement sur le disque. Lécriture du bloc modifié sur le disque nest effectuée que lorsque Ie tampon contenant ce bloc est libéré pour y placer un nouveau bloc. Il sensuit quun arrêt intempestif du système peut entraîner une perte de données pour tous les tampons dont le contenu modifié na pas été recopié sur le disque.
Cest pourquoi il existe deux threads noyau, bdflush et kupdate, responsables de la gestion des tampons dans le buffer cache et de leur écriture sur le disque si leur contenu a été modifié :
bdflush est réveillé lorsque trop de tampons modifiés existent dans le cache, ou lorsque la taille du cache devint insuffisante par rapport au nombre de tampons requis ;
kupdate effectue une sauvegarde régulière des tampons modifiés.
Par ailleurs, une application utilisateur dispose de trois primitives pour forcer la sauvegarde des tampons modifiés la concernant :
sync() sauvegarde tous les tampons modifiés sur le disque ;
fsync() permet à un processus de sauvegarder sur le disque tous les blocs appartenant à un fichier quil est ouvert ;
fdatasync() réalise la même opération que fsync(), sans sauvegarder li-node du fichier.
Les opérations sur les fichiers
Louverture dun fichier
Louverture dun fichier se fait à laide de la primitive open() :
>
La fermeture dun fichier
La fermeture dun fichier se fait via la primitive close() :