Programme informatique du concours d'inspecteur PSE

Introduction

Ce livre est issu de mes fiches de préparation pour le concours d'inspecteur PSE concernant le programme informatique. Il est publié au format mdbook sous licence MIT. Si vous souhaitez participer au projet n'hésitez pas à le cloner et à envoyer des pull request. Le but étant qu'il soit le plus utile possible au plus grand nombre. J'ai séparé les différentes grandes parties du programme en six chapitres plus un chapitre supplémentaire d'introduction au shell.

Chapitres

Algorithmique et méthodes de programmation

Introduction

Ce chapitre traite de la partie algorithmique et méthodes de programmation du programme PSE.

Les trois premières parties présentent les bases de l'algorithmique avec les structures de contrôle, les tris et les structures de données. La quatrième partie traite très rapidement du sujet hautement important des algorithmes de chiffrements. La cinquième présente succinctement la POO. La sixième survole les mécanismes de la compilation et traite de la différence entre langage compilé et langage interprété. Enfin la dernière partie traite des APIs (utilisés dans les échanges de données inter-applicatifs) des spécifications SOAP, REST et de leurs évolutions récentes : GraphQL de Facebook et gRPC de Google.

Sections

Structures de contrôle

En programmation informatique, une structure de contrôle est une instruction particulière à un langage de programmation impératif pouvant dévier le flot de contrôle du programme la contenant lorsqu'elle est exécutée. Si, au plus bas niveau, l'éventail se limite généralement aux branchements et aux appels de sous-programme, les langages structurés offrent des constructions plus élaborées comme les alternatives (if, if-else, switch...), les boucles (while, do-while, for...) ou encore les appels de fonction. Outre les structures usuelles, la large palette des structures de contrôle s'étend des constructions de gestion d'exceptions (try-catch...) fréquemment trouvés dans les langages de haut niveau aux particularismes de certains langages comme les instructions différées (defer) de Go.

Sous-sections

Structures de contrôle

Structures de contrôle séquentielles

Un programme informatique impératif est une suite d'instructions. Un registre interne de processeur, le compteur ordinal (PC), est chargé de mémoriser l'adresse de la prochaine instruction à exécuter.

La plupart des instructions d'un programme sont exécutées séquentiellement : après le traitement de l'instruction courante le compteur ordinal est incrémenté, et la prochaine instruction est chargée.

La séquence est donc la structure de contrôle implicite. Elle donne l'ordre d'exécution des instructions, souvent séparées par un point-virgule ou par des retours chariots.

Un programme s'arrête généralement après l'exécution de la dernière instruction. La plupart des langages de programmation proposent également une ou plusieurs instructions pour stopper l'exécution du programme à une position arbitraire.

Selon l'environnement d'exécution sous-jacent (système d'exploitation ou microprocesseur), cet arrêt peut être définitif ou correspondre à une suspension de l'exécution du programme en attendant un évènement externe : c'est par exemple le fonctionnement habituel de la plupart des instructions d'entrée sorties qui bloquent le flot d'exécution (mécanisme d'interruption avec stockage en mémoire tampon) jusqu'à ce que le périphérique concerné ait terminé de traiter les données.

Structures de contrôle

Structures de contrôle itératives

Ces instructions permettent de réaliser une machine à états finis, cela signifie que leur seul effet de bord est de modifier un registre qui correspond à l'état courant du programme.

Dans un processeur, cet état correspond à la valeur du compteur ordinal.

Commandes à étiquettes :

Sauts inconditionnels
Sauts conditionnels
Sous programmes, commandes de sorties de boucles

Commandes de blocs :

Blocs d'instructions
Alternatives (if, then, else, switch)
Boucles (do, while, each)

Structures de contrôle

Extensions de la notion de boucles

Un compteur permet de réaliser une boucle associée à une variable entière ou un pointeur qui sera incrémenté à chaque itération. Il est souvent utilisé pour exploiter les données d'une collection indexée (boucle for).

Un itérateur (ou curseur ou énumérateur) est un objet qui permet de réaliser une boucle parcourant tous les éléments contenus dans une structure de données.

Structures de contrôle

Sous-programmes

Un sous-programme permet la réutilisation d'une partie du code et ainsi le développement des algorithmes récursifs.

Beaucoup de langages modernes ne supportent pas directement la notion de sous-programme au profit de constructions de haut niveau qui peuvent être appelées, d'un langage à l'autre procédure, fonction, méthode, ou routine. Ces constructions ajoutent la notion de passage de paramètres et surtout le cloisonnement des espaces de noms pour éviter que le sous-programme ait un effet de bord sur la routine appelante.

Il existe diverses extensions à la notion de procédure comme les coroutines (routine avec suspension), signaux, et slots (signaux implémentés pour les objets), fonctions de rappel (callback, traitement post-fonction), méthodes virtuelles (programmation par contrat, méthode implémentée dans les classes héritées) Elles permettent de modifier dynamiquement, c'est à dire à l'exécution, la structure du flot d'exécution du programme.

Structures de contrôle

Exceptions

Tout programme en exécution peut être sujet à des erreurs pour lesquelles des stratégies de détection et de réparation sont possibles. Ces erreurs ne sont pas des bugs mais des conditions exceptionnelles dans le déroulement normal d'une partie d'un programme.

Structures de contrôle

Programmation multitâche

Dans un système multitâche, plusieurs flots d'exécutions, appelés processus légers, s'exécutent simultanément.

Il est alors nécessaire d'assurer la synchronisation de ces flots d'exécution. Dans la plupart des langages, cela est réalisé via des bibliothèques externes ; certains d'entre eux intègrent néanmoins des structures de contrôle permettant d'agir sur des tâches concourantes.

Structures de contrôle

Programmation événementielle

La programmation évènementielle est une autre façon de contrôler le flot d'exécution d'un programme. Il s'agit de créer des gestionnaires qui viendront s'abonner à une boucle mère, chargée d'aiguiller les évènements qui affectent le logiciel.

Algorithmes de tri

Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle "est inférieur ou égal à". Les algorithmes de tris sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique. Ils peuvent également servir pour mettre des données sous forme canonique ou les rendre plus lisibles pour l'utilisateur.

La collection à trier est souvent donnée sous forme de tableau, afin de permettre l'accès direct aux différents éléments de la collection, ou sous forme de liste, ce qui peut se révéler être plus adapté à certains algorithmes et l'usage de la programmation fonctionnelle.

Bon nombre d'algorithmes de tri procèdent par comparaisons successives, et peuvent donc être définis indépendamment de l'ensemble auquel appartiennent les éléments de la relation d'ordre associée. Un même algorithme peut par exemple être utilisé pour trier les réels selon la relation d'ordre usuelle "est inférieur ou égal à" et des chaînes de caractères selon l'ordre lexicographique. Ces algorithmes se prêtent naturellement à une implémentation polymorphe (différents types).

Les algorithmes de tri sont souvent étudiés dans les cours d'algorithmique pour introduire des notions comme la complexité algorithmique ou la terminaison.

Sous-sections

Algorithmes de tri

Critère de classification

La classification des algorithmes de tri est très importante, car elle permet de choisir l'algorithme le plus adapté au problème traité, tout en tenant compte des contraintes imposées par celui-ci. Les principales caractéristiques qui permettent de différencier les algorithmes de tri, outre leur principe de fonctionnement, sont la complexité temporelle, la complexité spatiale et le caractère stable.

La complexité temporelle (en moyenne ou dans le pire des cas) mesure le nombre d'opérations élémentaires effectuées pour trier une collection d'éléments. C'est un critère majeur pour comparer les algorithmes de tri, puisque c'est une estimation directe du temps d'exécution de l'algorithme. Dans le cas des algorithmes de tri par comparaison, la complexité en temps est le plus souvent assimilable au nombre de comparaisons effectuées, la comparaison et l'échange éventuel de deux valeurs s'effectuant en temps constant.

La complexité spatiale (en moyenne ou dans le pire des cas) représente, quant à elle, la quantité de mémoire dont va avoir besoin l'algorithme pour s'exécuter. Celle-ci peut dépendre, comme le temps d'exécution, de la taille de l'entrée. Il est fréquent que les complexités spatiales en moyenne et dans le pire des cas soient identiques. C'est souvent le cas lorsqu'une complexité est donnée sans indication supplémentaire.

Un tri est dit en place s'il n'utilise qu'un nombre très limité de variables et qu'il modifie directement la structure qu'il est en train de trier. Ceci nécessite l'utilisation d'une structure de donnée adaptée (un tableau par exemple). Ce caractère peut être très important si on ne dispose pas de beaucoup de mémoire.

Toutefois, on ne déplace pas, en général, les données elles-mêmes, mais on modifie seulement des références (ou pointeurs) vers ces dernières.

Un tri est dit stable s'il préserve l'ordonnancement initial des éléments que l'ordre considère comme égaux (tri à bulles, tri par insertion et le tri par fusion).

Un tri interne s'effectue entièrement en mémoire centrale tandis qu'un tris externe utilise des fichiers sur une mémoire de masse pour trier des volumes trop importants pour pouvoir tenir en mémoire centrale.

Certains algorithmes permettent d'exploiter les capacités multitâches de la machine. Notons également, que certains algorithmes, notamment ceux qui fonctionnent par insertion, peuvent être lancés sans connaître l'intégralité des données à trier; on peut alors trier et produire les données à trier en parallèle.

Algorithmes de tri

Exemples d'algorithmes de tri

Algorithmes rapides T(n)=O(n.log n)

Tri fusion (merge sort) : Pour une entrée donnée, l'algorithme la divise en deux parties de tailles similaires, trie chacune d'elles en utilisant le même algorithme, puis fusionne les deux parties triées. Il se prête aussi bien à des implémentations sur listes que sur tableaux.
Tri rapide (quick sort) : Une valeur est choisie comme pivot et les éléments plus petits que le pivot sont dissociés, par échanges successifs, des éléments plus grands que le pivot ; chacun de ces deux sous-ensembles est ensuite trié de la même manière. On peut rendre la complexité quasiment indépendante des données en utilisant un pivot aléatoire ou en appliquant au tableau une permutation aléatoire avant de le trier.
Tri par tas (heap sort) : Il s'agit d'une amélioration du tri par sélection. L'idée est la même (insérer les élément un à un dans une structure déjà triée) mais l'algorithme utilise une structure de tas, souvent implémentée au moyen d'un tableau.
Tri introspectif (Introspective sort) : Il s'agit d'un hybride du tri rapide et du tri par tas. Par rapport au tri rapide, il présente l'avantage d'avoir une complexité O(n.log n) dans le pire cas.
Tri arborescent (tree sort): L'idée est d'insérer les éléments un à un dans l'arbre binaire de recherche, puis de lire l'arbre selon un parcours en profondeur. Un arbre binaire de recherche(ABR) est un arbre binaire dans lequel chaque noeud possède une clé, telle que chaque noeud du sous-arbre gauche ait une clé inférieure ou égale à celle du noeud considéré, et que chaque noeud du sous-arbre droit possède une clé supérieure ou égale à celle-ci.
Tri doux (smoothsort) : La première étape consiste à transformer le tableau en arbre binaire. Le premier élément est déjà trivialement bien ordonné, puis on ajoute un à un les éléments suivants. On réordonne chaque fois un peu les éléments si nécessaire pour qu'ils correspondent aux critères :
- Chaque noeud ne peut être supérieur à son noeud parent.
- Le premier noeud enfant ne peut être supérieur au deuxième noeud enfant.

La deuxième étape consiste à retransformer l'arbre binaire en tableau trié. Chaque élément en partant de la droite est laissé tel quel car il s'agit de la racine de l'arbre qui est déjà le plus grand élément, et l'arbre restant est réordonné si nécessaire. On fait ceci jusqu'à arriver à un tableau trié.

Algorithmes moyennement rapides

Tri de Shell (shell sort) : Ce tri repose sur le tri par insertion des sous-suites de l'entrée obtenues en prenant les éléments espacés d'un pas constant, pour une suite de pas prédéfinie. La complexité varie selon le choix de cette suite.
Tri à peigne (comb sort) : Il s'agit d'une variante plus efficace du tri à bulles, ne comparant pas uniquement des éléments consécutifs. On peut dire qu'il est au tri à bulles ce que le tri de Shell est au tri par insertion.
Tri par insertion (insertion sort): Ce tri souvent utilisé naturellement pour trier des cartes à jouer. Les valeurs sont insérées les unes après les autres dans une liste triée (initialement vide). C'est souvent le plus rapide et le plus utilisé pour trier les entrées de petite taille. Il est également efficace pour des entrées déjà presque triées.
Tri à bulles (bubble sort) : L'algorithme consiste à parcourir l'entrée du début à la fin et pour chaque couple d'éléments consécutifs, à les intervertir s'ils sont mal ordonnés. Cette opération est répétée jusqu'à ce que la structure soit triée (aucune intervention lors du dernier passage). Cet algorithme est peu efficace et rarement utilisé en pratique ; son intérêt est principalement pédagogique.
Tri cocktail (cocktail sort) : Il s'agit d'une variante du tri à bulles dans laquelle l'entrée est alternativement parcourue dans les deux sens. S'il permet de traiter de manière plus efficace quelques cas problématiques pour le tri à bulles, il reste essentiellement similaire à ce dernier et l'intérêt est encore une fois principalement pédagogique.
Tri pair-impair (odd-even sort) : Il s'agit d'une variante du tri à bulles, qui procède en comparant successivement tous les éléments d'index pairs avec les éléments d'index impairs qui les suivent, puis inversement. On va ainsi commencer en comparant le premier élément au second, le troisième au quatrième, etc., puis l'on comparera le second élément au troisième, le quatrième au cinquième. L'opération est répétée jusqu'à ce que la structure soit triée.

Algorithmes lents

Tri par selection (selection sort) : Sur un tableau de n éléments on recherche l'élément le plus petit du tableau et on l'échange avec l'élément d'indice 0. Puis on recherche le deuxième plus petit et on l'échange avec l'élément d'indice 1. L'opération est répétée jusqu'à ce que la structure soit triée.

Structures de données

Une structure de données est une manière d'organiser les données pour les traiter plus facilement. C'est une mise en oeuvre concrète d'un type abstrait.

Sous-sections

Structures de données

Pile

Une pile est une structure de données fondée sur le principe "dernier entré, premier sorti" (LIFO), ce qui veut dire qu'en général, le dernier élément ajouté à la pile, sera le premier à en sortir.

La plupart des microprocesseurs gèrent nativement une pile. Elle correspond alors à une zone de la mémoire, et le processeur retient l'adresse du dernier élément.

Voici les primitives communément utilisées pour manipuler les piles. Il n'existe pas de normalisation pour les primitives de manipulation de pile. Leurs noms sont donc indiqués de manière informelle. Seules les trois premières sont réellement indispensables, les autres pouvant s'en déduire :

Empiler (Push) : ajoute un élément sur la pile.
Dépiler (Pull) : enlève un élément de la pile et le renvoie.
"La pile est-elle vide ?" (IsNull) : renvoie vrai si la pile est vide, faux sinon.
"Nombre d'éléments de la pile" (Length): renvoie le nombre d'élément de la pile.
"Quel est l'élément de tête ?" (Peek ou Top) : renvoie l'élément de tête sans le dépiler.
"Vider la liste" (Clear) : dépiler tous les éléments.

Structures de données

File

Une file est une structure de donnée basée sur le principe de "premier entré, premier sorti" (FIFO), les premiers éléments ajoutés à la file seront les premiers à en être retirés.

Les files servent à organiser le traitement séquentiel des blocs de données d'origines diverses.

La théorie des files d'attente, élaborée pour le dimensionnement des réseaux téléphoniques, relie le nombre d'usagers, le nombre de canaux disponibles, le temps d'occupation moyen du canal, et le temps d'attente à prévoir (Loi de Poisson).

Cette structure est utilisée :

en général, pour mémoriser temporairement des transactions qui doivent attendre pour être traitées ;
les serveurs d'impression, qui traitent ainsi les requêtes dans l'ordre dans lequel elles arrivent, et les insèrent dans une file d'attente (spool) ; certains moteurs multitâches, dans les systèmes d'exploitation, qui doivent accorder du temps machine à chaque tâche, sans en privilégier aucune ;
un algorithme de parcours en largeur utilise une file pour mémoriser les noeuds visités ;
pour créer toutes sortes de mémoires tampons (buffers) ;
En gestion des stocks les algorithmes doivent respecter la gestion physique des stocks pour assurer la cohérence physique/valorisation.

Voici les primitives communément utilisées pour manipuler les files. Il n'existe pas de normalisation pour les primitives de manipulation de file. Leurs noms sont donc indiqués de manière informelle :

Enfiler (Enqueue) : ajouter un élément dans la file.
Defiler (Dequeue) : renvoie le prochain élément de la file, et le retire de la file.
"La file est-elle vide ?" (IsNull) : renvoie "vrai" si la file est vide, "faux" sinon.
"Nombre d'élément dans la file" (Length) : renvoie le nombre d'élément dans la file.

Structures de données

Liste

Une liste est une structure de données permettant de regrouper des données de manière à pouvoir y accéder librement (contrairement aux files et aux piles).

Voici les primitives communément utilisées pour manipuler des listes ; il n'existe pas de normalisation pour les primitives de manipulation de listes, leurs noms respectifs sont donc indiqués de manière informelle.

Primitives de base :

Insérer (Add) : ajoute un élément dans la liste ;
Retirer (Remove) : retire un élément de la liste ;
"La liste est-elle vide ?" (IsNull) : renvoie "vrai" si la liste est vide, "faux" sinon ;
"Nombre d'éléments dans la liste" (Length) : renvoie le nombre d'éléments dans la liste.

Primitives auxiliaires fréquemment rencontrées :

Premier (First) : retourne le premier élément dans la liste ;
Dernier (Last) : retourne le dernier élément dans la liste ;
Prochain (Next) : retourne le prochain élément dans la liste ;
Précédent (Previous) : retourne l'élément qui précède dans la liste ;
Cherche (find) : cherche si un élément précis est contenu dans la liste et retourne sa position.

Une liste est un conteneur d'éléments, où chaque élément contient la donnée, ainsi que d'autres informations permettant la récupération des données au sein de la liste. La nature (les types) de ces informations caractérise un type différent de liste.

On peut distinguer, de manière générale, deux types de liste :

les tableaux ;
les listes chaînées.

Dans un tableau, l'accès à un élément se fait à l'aide d'un index qui représente l'emplacement de l'élément dans la structure.

Les données présentes dans un tableau sont contiguës en mémoire. Cela induit une taille de tableau fixe. Cependant certains langages de haut niveau fournissent des tableaux qui modifient leur taille en fonction de leur utilisation : on parle alors de tableau à taille dynamique. Mais leur implémentation utilise le principe des listes chaînées. Les tableaux peuvent également avoir plusieurs dimensions, représentées par une séquence d'indices.

Contrairement à un tableau, la taille d'une liste chaînée n'a pas de limite autre que celle de la mémoire disponible. Cette limitation est franchie par le fait que chaque élément peut pointer, suivant le type de liste chaînée, vers un ou plusieurs éléments de la liste en utilisant une définition récursive. Ainsi, pour augmenter la taille d'une liste chaînée, il suffit de créer un nouvel élément et de faire pointer certains éléments, déjà présents au sein de la liste, vers le nouvel élément.

Il existe deux grand types de liste chainée :

les listes simplement chaînées : chaque élément dispose d'un pointeur sur l'élément suivant (ou successeur) de la liste. Le parcours se fait dans un seul sens ;
les listes doublement chaînées : chaque élément dispose de deux pointeurs, respectivement sur l'élément suivant (ou successeur) et sur l'élément précédent (ou prédécesseur). Le parcours peut alors se faire dans deux sens, mutuellement opposés : de successeur en successeur, ou de prédécesseur en prédécesseur.

A cela on peut ajouter une propriété : le cycle. Cette fois ci, la liste chaînée forme une boucle. Dès qu'on atteint la "fin" de la liste et qu'on désire continuer, on se retrouve sur le "premier" élément de la liste. Dans ce cas, la notion de début ou de fin de chaîne n'a plus de raison d'être.

Structures de données

Arbre enraciné

En théorie de graphes, un arbre enraciné ou une arborescence est un graphe acyclique orienté possédant une unique racine, et tel que tous les noeuds sauf la racine ont un unique parent.

Dans un arbre, on distingue deux catégories d'éléments :

les feuilles (ou noeuds externes), éléments ne possédant pas de fils dans l'arbre ;
les noeuds interne, éléments possédant des fils (sous-branches).

La racine de l'arbre est l'unique noeud ne possédant pas de parent. Les noeuds (les pères avec leurs fils) sont reliés entre eux par une arête. Selon le contexte, un noeud peut désigner un noeud interne ou externe (feuille) de l'arbre.

La profondeur d'un noeud est la distance, i.e. le nombre d'arêtes, de la racine au noeud. La hauteur d'une arbre est la plus grande profondeur d'une feuille de l'arbre. La taille d'un arbre est son nombre de noeuds (en comptant les feuilles ou non), la longueur de cheminement est la somme des profondeurs de chacune des feuilles.

Les arbres peuvent être étiquetés. Dans ce cas, chaque noeud possède une étiquette, qui est en quelque sorte le "contenu" du noeud. L'étiquette peut être très simple : un nombre entier, par exemple. Elle peut également être aussi complexe que l'on veut : un objet, une instance d'une structure de donnée, un pointeur, etc. Il est presque toujours obligatoire de pouvoir comparer les étiquettes selon une relation d'ordre total, afin d'implanter les algorithmes sur les arbres.

Les fichiers et dossiers dans un système de fichiers sont généralement organisés sous forme arborescente.

Les arbres sont en fait rarement utilisés en tant que tels, mais de nombreux types d'arbres avec une structure plus restrictive existent et sont couramment utilisés en algorithmique, notamment pour gérer des bases de données, ou pour l'indexation de fichiers. Ils permettent alors des recherches rapides et efficaces. Par exemple :

Les arbres binaires dont chaque noeud a au plus deux fils : ils sont en fait utilisés sous forme d'arbres binaires de recherche, de tas, ou encore d'arbres rouge-noir. Le dernier exemple est un cas particulier d'arbre équilibré, c'est à dire dont les sous-branches ont presque la même hauteur.
Les arbres n-aires qui sont une généralisation des arbres binaires : chaque noeud a au plus n fils. Les arbres 2-3-4 et les arbres B en sont des exemples d'utilisation et sont eux aussi des arbres équilibrés.

Pour construire un arbre à partir de cases ne contenant que des informations, on peut procéder de l'une des trois façons suivantes :

Créer une structure de données composée de :
- l'étiquette (la valeur contenue dans le noeud),
- un lien vers chaque noeud fils,
- un arbre particulier, l'arbre vide, qui permet de caractériser les feuilles. Une feuille a pour fils des arbres vides uniquement.
Créer une structure de données composée de :
- l'étiquette (la valeur contenue dans le noeud),
- un lien vers le "premier" noeud fils (noeud fils gauche le cas échéant),
- un autre lien vers le noeud frère (le "premier" noeud frère sur la droite le cas échéant).
Créer une structure de données composée de :
- l'étiquette (la valeur contenue dans le noeud),
- un lien vers le noeud père.

On note qu'il existe d'autres types de représentation propres à des cas particuliers d'arbres. Par exemple, le tas est représenté par un tableau d'étiquettes.

Les parcours d'arbre sont des processus de visites des sommets d'un arbre, par exemple pour trouver une valeur.

Le parcours en largeur correspond à un parcours par niveau de noeuds de l'arbre. Un niveau est un ensemble de noeuds internes ou de feuilles situés à la même profondeur - on parle aussi de noeud ou de feuille de même hauteur dans l'arbre considéré. L'ordre de parcours d'un niveau donné est habituellement conféré, de manière récursive, par l'ordre de parcours des noeuds parents - noeuds de niveau immédiatement supérieur.

Le parcours en profondeur est un parcours récursif sur un arbre. Dans le cas général, deux ordres sont possibles :

Parcours en profondeur préfixe : dans ce mode de parcours, le noeud courant est traité avant ses descendants.
Parcours en profondeur suffixe : dans ce mode de parcours, le noeud courant est traité après ses descendants.

Pour les arbres binaires, on peut également faire un parcours infixe, c'est à dire traiter le noeud courant entre les noeuds gauche et droit.

Parcours préfixe :

    visiterPréfixe(Arbre A) :
        visiter (A)
        Si nonVide (gauche(A))
            visiterPréfixe(gauche(A))
        Si nonVide (droite(A))
            visiterPréfixe(droite(A))

Parcours suffixe :

    visiterSuffixe(Arbre A) :
        Si nonVide(gauche(A))
            visiterSuffixe(gauche(A))
        Si nonVide(droite(A))
            visiterSuffixe(droite(A))
        visiter(A)

Parcours infixe :

    visiterInfixe(Arbre A) :
        Si nonVide(gauche(A))
            visiterInfixe(gauche(A))
        visiter(A)
        Si nonVide(droite(A))
            visiterInfixe(droite(A))

Structures de données

Arbre binaire de recherche

Un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clefs appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.

Un arbre binaire de recherche est un arbre binaire dans lequel chaque noeud possède une clé, telle que chaque noeud du sous-arbre gauche ait une clé inférieure ou égale à celle du noeud considéré, et que chaque noeud du sous-arbre droit possède une clé supérieure ou égale à celle-ci - selon la mise en oeuvre de l'ABR, on pourra interdire ou non des clés de valeur égale. Les noeuds que l'on ajoute deviennent des feuilles de l'arbre.

La recherche dans un arbre binaire d'un noeud ayant une clé particulière est un procédé récursif. On commence par examiner la racine. Si la clé est la clé recherchée, l'algorithme se termine et renvoie la racine. Si elle est strictement inférieure, alors elle est dans le sous-arbre gauche, sur lequel on effectue alors récursivement la recherche. De même si la clé recherchée est strictement supérieure à la clé de la racine, la recherche continue dans le sous-arbre droit. Si on atteint une feuille dont la clé n'est pas celle recherchée, on sait alors que la clé recherchée n'appartient à aucun noeud, elle ne figure donc pas dans l'arbre de recherche. On peut comparer l'exploration d'un arbre binaire de recherche avec la recherche par dichotomie qui procède à peu près de la même manière sauf qu'elle accède directement à chaque élément d'un tableau au lieu de suivre les liens. La différence entre les deux algorithmes est que, dans la recherche dichotomique, on suppose avoir un critère de découpage de l'espace en deux parties que l'on n'a pas dans la recherche dans un arbre.

Cette opération requiert un temps en O(log n) dans le cas moyen, mais O(n) dans le cas critique où l'arbre est complètement déséquilibré et ressemble à une liste chaînée. Ce problème est écarté si l'arbre est équilibré par rotation au fur et à mesure des insertions pouvant créer des listes trop longues.

L'insertion d'un noeud commence par une recherche : on cherche la clé du noeud à insérer ; lorsqu'on arrive à une feuille, on ajoute le noeud comme fils de la feuille en comparant sa clé à celle de la feuille : si elle est inférieure, le nouveau noeud sera à gauche ; sinon il sera à droite.

Sa complexité est la même que pour la recherche.

Il est aussi possible d'écrire une procédure d'ajout d'élément à la racine d'un arbre binaire. Cette opération requiert la même complexité mais est meilleure en terme d'accès aux éléments.

Pour la suppression, on commence par rechercher la clé du noeud à supprimer dans l'arbre. Plusieurs cas sont à considérer, une fois que le noeud à supprimer a été trouvé à partir de sa clé :

Suppression d'une feuille : Il suffit de l'enlever de l'arbre puisqu'elle n'a pas de fils.
Suppression de noeud avec un enfant : Il faut l'enlever de l'arbre en le remplaçant par son fils.
Suppression d'un noeud avec deux enfants : Supposons que le noeud à supprimer soit appelé N. On échange le noeud N avec son successeur le plus proche (le noeud le plus à gauche du sous-arbre droit) ou son plus proche prédécesseur (le noeud le plus à droite du sous-arbre gauche). Cela permet de garder à la fin de l'opération une structure d'arbre binaire de recherche. Puis on applique à nouveau la procédure de suppression à N, qui est maintenant une feuille ou un noeud avec un seul fils.

Ce choix d'implémentation peut contribuer à déséquilibrer l'arbre. En effet, puisque ce sont toujours des feuilles du sous-arbre gauche qui sont supprimées, une utilisation fréquente de cette fonction amènera à un arbre plus lourd à droite qu'à gauche. On peut remédier à cela en alternant successivement la suppression du minimum du fils droit avec celle maximum du fils gauche, plutôt que toujours choisir ce dernier. Il est par exemple possible d'utiliser un facteur aléatoire : le programme aura une chance sur deux de choisir le fils droit et une chance sur deux de choisir le fils gauche.

Dans tous les cas cette opération requiert de parcourir l'arbre de la racine jusqu'à une feuille : le temps d'exécution est donc proportionnel à la profondeur de l'arbre qui vaut n dans le pire des cas, d'où une complexité maximale O(n).

On peut récupérer les clés d'un arbre binaire de recherche dans l'ordre croissant en réalisant un parcours infixe. Il faut concaténer dans cet ordre la liste triée obtenue récursivement par parcours du fils gauche à la racine puis à celle obtenue récursivement par parcours du fils droit. Il est possible de le faire dans l'ordre inverse en commençant par le sous-arbre droit. Le parcours de l'arbre se fait en temps linéaire, puisqu'il doit passer par chaque noeud une seule fois.

On peut dès lors créer un algorithme de tri simple mais peu efficace, en insérant toutes les clés que l'on veut trier dans un nouvel arbre binaire de recherche puis en parcourant de manière ordonnée cet arbre comme ci-dessus.

Les arbres binaires de recherche peuvent servir d'implémentation au type abstrait de file de priorité. En effet, les opérations d'insertion d'une clé et de test au vide se font avec des complexités avantageuses (respectivement en O(log n) et en O(1)). Pour l'opération de suppression de la plus grande clé, il suffit de parcourir l'arbre depuis sa racine en choisissant le fils droit de chaque noeud, et de supprimer la feuille terminale. Cela demande un nombre d'opérations égal à la hauteur de l'arbre, donc une complexité logarithmique. L'avantage notoire de cette représentation d'une file de priorité est qu'avec un processus similaire, on dispose d'une opération de suppression de la plus petite clé en temps logarithmique également.

L'insertion et la suppression s'exécutent en O(h) où h est la hauteur de l'arbre. Cela s'avère particulièrement coûteux quand l'arbre est très déséquilibré (un arbre peigne par exemple, dont la hauteur est linéaire en le nombre de clés), et on gagne donc en efficacité à équilibrer les arbres au cours de leur utilisation. Il existe des techniques pour obtenir des arbres équilibrés, c'est à dire une hauteur logarithmique en nombre d'éléments :

les arbres rouge-noir
les B-arbres

Structures de données

Arbre B

Un arbre B est une structure de données en arbre équilibré. Les arbres B sont principalement mis en oeuvre dans les mécanismes de gestion de bases de données et de systèmes de fichiers. Ils stockent les données sous une forme triée et permettent une exécution des opérations d'insertion et de suppression en temps toujours logarithmique.

Le principe est de permettre aux noeuds parents de posséder plus de deux noeuds enfants : c'est une généralisation de l'arbre binaire de recherche. Ce principe minimise la taille de l'arbre et réduit le nombre d'opérations d'équilibrage. De plus un B-arbre grandit à partir de la racine, contrairement à un arbre binaire de recherche qui croît à partir des feuilles.

Un arbre étiqueté est un arbre tel qu'à chaque noeud on associe une étiquette ou clé (ou bien plusieurs étiquettes ou clés dans le cas des arbres B) prise(s) dans un ensemble donné. Donc formellement un arbre étiqueté est un couple formé d'un graphe orienté, acyclique et connexe et d'une fonction d'étiquetage des arbres qui attribue à chaque noeud une étiquette ou une clé. Parmi les arbres étiquetés, un arbre B possède quelques propriétés spécifiques supplémentaires.

Soit L et U deux entiers naturels non nuls tels que L≤U. En toute généralité, on définit alors un L-U arbre B de la manière suivante : chaque noeud, sauf la racine, possède un minimum de L-1 clés (appelées aussi éléments), un maximum de U-1 clés et au plus U fils. Pour chaque noeud interne -- noeud qui n'est pas une feuille --, le nombre de fils est toujours égal au nombre de clés augmenté d'une unité. Si n est le nombre de fils, alors on parle de n-noeud. Un L-U arbre B ne contient que des n-noeuds avec L≤n≤U. Souvent on choisit la configuration L=t et U=2.t : t est appelé le degré minimal de l'arbre B.

De plus, la construction des arbres B garantit qu'un arbre B est toujours équilibré. Chaque clé d'un noeud interne est en fait une borne qui distingue les sous-arbres de ce noeud.

Un arbre B est implémenté par un arbre enraciné. Un noeud x est étiqueté par :

Un entier n qui correspond au nombre de clefs contenues dans e noeud x
n clefs notées c₁,...,cₙ.
Un booléen indiquant si x est une feuille ou non.
n+1 pointeurs notés p₁,...,pₙ₊₁ associés aux fils f₁,...,fₙ₊₁ de x. Une feuille ne contient pas de pointeurs.

De plus, un arbre B vérifie ces propriétés :

Toutes les feuilles ont la même profondeur, à savoir la hauteur h de l'arbre.
Si x n'est pas une feuille :
- pour 2≤i≤n, pour toute clef k du fils fᵢ : cᵢ₋₁≤k≤cᵢ.
- pour toute clef k du fils f₁ : k≤c₁.
- pour toute clef k du fils fₙ₊₁ : cₙ≤k.
Si x n'est ni une feuille, ni la racine, n est compris entre L-1 et U-1.

La plupart du temps, la configuration est telle que U = 2L. On parle alors d'arbre B d'ordre L. Un arbre B d'ordre t est défini alors plus simplement par un arbre qui satisfait les propriétés suivantes :

Chaque noeud a au plus 2t-1 clés.
Chaque noeud qui n'est ni racine ni feuille possède au moins t-1 clés.
Si l'arbre est non vide, la racine est aussi non vide.
Un noeud qui possède k fils contient k-1 clefs.
Toutes les feuilles se situent à la même hauteur.

Comme on le verra par la suite, la hauteur d'un B-arbre est logarithmique en le nombre d'éléments. Ainsi, les opérations de recherche, insertion et suppression sont implémentables en O(log n) dans le pire des cas, où n est le nombre d'éléments.

La recherche est effectué de la même manière que dans un arbre binaire de recherche. Partant de la racine, on parcourt récursivement l'arbre ; à chaque noeud, on choisit le sous-arbre fils dont les clés sont comprises entre les même bornes que celles de la clé recherchée grâce à une recherche dichotomique.

L'insertion nécessite tout d'abord de chercher le noeud où la nouvelle clé devrait être insérée, et l'insérer. La suite se déroule récursivement, selon qu'un noeud ait ou non trop de clés : s'il possède un nombre acceptable de clés, on ne fait rien ; autrement on le transforme en deux noeuds, chacun possédant un nombre minimum de clés, puis on fait "remonter" la clé du milieu qui est alors insérée dans le noeud père. Ce dernier peut du coup se retrouver avec un nombre excessif de fils ; le procédé se poursuit ainsi jusqu'à ce qu'on atteigne la racine. Si celle-ci doit être divisée, on fait "remonter" la clé du milieu dans une nouvelle racine, laquelle génèrera comme noeuds fils les deux noeuds créés à partir de l'ancienne racine, à l'instar de l'étape précédente. Pour que l'opération soit possible, on remarque qu'il faut que U ≥ 2L ; sinon les nouveaux noeuds ne possèderont pas suffisamment de clés.

Une variante consiste à éclater préventivement chaque noeud "plein" (possédant un nombre maximal de clés) rencontré lors de la recherche du noeud où se réalisera l'insertion. De cette manière on évite une remontée dans l'arbre, puisque l'on s'assure que le père d'un noeud à scinder en deux peut accueillir une clé supplémentaire. La contrepartie en est une légère augmentation de la hauteur moyenne de l'arbre.

Pour la suppression, on doit d'abord chercher la clé à supprimer et la supprimer du noeud qui la contient.

Si le noeud est interne, on procède de manière similaire aux arbres binaires de recherche en cherchant la clé k la plus à gauche dans le sous-arbre droit de la clé à supprimer ou la plus à droite dans le sous-arbre gauche. Cette clé k appartient à une feuille. On peut la permuter avec la clé à supprimer, que l'on supprime ensuite. Comme elle appartient à une feuille, on se ramène au cas suivant.
Si le noeud est une feuille, soit il possède encore suffisamment de clés et l'algorithme se termine, soit il dispose de moins de L-1 clés et on se trouve dans l'une des deux situations suivantes :
- soit un de ses frères à droite ou à gauche possède suffisamment de clés pour pouvoir en "passer" une à la feuille en question : dans ce cas cette clé remplace la clé qui sépare les deux sous-arbres dans l'arbre père, qui va elle-même dans la feuille en question ;
- soit aucun de ses frères n'a suffisamment de clés : dans ce cas, le père fait passer une de ses clés dans un des deux (ou le seul) frère pour permettre à la feuille de fusionner avec celui-ci. Ceci peut cependant conduire le père à ne plus avoir suffisamment de clés. On réitère alors l'algorithme : si le noeud a un frère avec suffisamment de clés, la clé la plus proche va être échangée avec la clé du père, puis la clé du père et ses nouveaux descendants sont ramenés dans le noeud qui a besoin d'une clé ; sinon, on effectue une fusion à l'aide d'une clé du père et ainsi de suite. Si l'on arrive à la racine et qu'elle possède moins de L éléments, on fusionne ses deux fils pour donner une nouvelle racine.

Notamment après une suppression, l'arbre peut être rééquilibré. Cette opération consiste à répartir équitablement les valeurs dans les différents noeuds de l'arbre et à rétablir les propriétés de remplissage minimum des noeuds.

Le rééquilibrage commence au niveau des feuilles et progresse vers la racine, jusqu'à celle-ci. La redistribution consiste à transférer un élément d'un noeud voisin qui possède suffisamment de valeurs vers le noeud qui en manque. Cette redistribution est appelée rotation. Si aucun voisin ne peut fournir de valeur sans être lui même sous la limite, le noeud déficient doit être fusionné avec un voisin. Cette opération provoque la perte d'un séparateur dans le noeud parent, celui-ci peut alors être en déficit et a besoin d'être équilibré. La fusion et redistribution se propage jusqu'à la racine, seul élément où la déficience en valeurs est tolérée.

Un algorithme d'équilibrage simple consiste à :

Si le noeud voisin gauche existe et dispose de suffisamment de valeurs pour pouvoir en offrir une, réaliser une rotation gauche.
Sinon, si le noeud voisin droite existe et dispose de suffisamment d'éléments, réaliser une rotation droite.
Sinon, le noeud déficient doit être fusionné avec un de ses voisins tel que la somme du nombre de leurs clés plus 1 soit inférieure ou égale à la capacité maximale (taille_gauche+taille_droite+1≤U-1). La valeur supplémentaire correspond au séparateur présent dans le parent. Cette opération est toujours possible si U-1≥2L avec taille_gauche=L-2 et taille_droite=L-1 ou le contraire, soit un noeud immédiatement sous la limite de L-1 clés et un noeud exactement à la limite.

Copier le séparateur à la fin du noeud de gauche.
Ajouter tous les éléments du noeud de droite à la fin du noeud de gauche.
Effacer le noeud de droite et effacer le séparateur du parent puis vérifier qu'il contient assez d'éléments. Si ce n'est pas le cas, rééquilibrer le parent avec ses voisins.

La rotation à gauche d'un cran entre deux noeuds voisins se fait en :

déplaçant le séparateur, présent dans le parent, à la fin du noeud gauche.
déplaçant le premier élément du noeud de droite en tant que séparateur dans le parent.

Ce genre d'opération peut être également utilisé pour compresser l'arbre : un arbre destiné à la lecture seule peut être vidé d'un maximum de cases mémoires inutilisées en remplissant au maximum un minimum de noeuds.

Structures de données

Arbre rouge-noir

Un arbre bicolore, ou arbre rouge-noir ou arbre rouge et noir est un type particulier d'arbre binaire de recherche équilibré. Chaque noeud de l'arbre possède en plus de ses données propres un attribut binaire qui est souvent interprété comme sa "couleur" (rouge ou noir). Cet attribut permet de garantir l'équilibre de l'arbre : lors de l'insertion ou de la suppression d'éléments, certaines propriétés sur les relations entre les noeuds et les couleurs doivent être maintenues, ce qui empêche l'arbre de devenir trop déséquilibré, y compris dans le pire des cas. Durant une insertion ou une suppression, les noeuds sont parfois réarrangés ou changent leur couleur afin que ces propriétés soient conservées.

Le principal intérêt des arbres bicolores réside dans le fait que malgré les potentiels réarrangements ou coloriages des noeuds, la complexité (en le nombre d'éléments) des opérations d'insertion, de recherche et de suppression est logarithmique. De plus, cette structure est économe en mémoire puisqu'elle ne requiert qu'un bit supplémentaire d'information par élément par rapport à un arbre binaire classique.

Un arbre bicolore est un cas particulier d'arbre binaire, une structure de donnée couramment utilisée en informatique pour organiser des données pouvant être comparées, par exemple des nombres ou des chaines de caractères.

Les feuilles de l'arbre, c'est-à-dire les noeuds terminaux, ne contiennent aucune donnée. Elles peuvent être simplement représentées sans coût mémoire par des éléments nuls (pointeurs nul en C, valeur NIL, etc.) dans le noeud parent (indiquant que le noeud enfant est une feuille). Il peut être toutefois utile pour simplifier la mise en oeuvre de certains algorithmes que les feuilles soient explicitement représentées soit en les instanciant séparément, soit en utilisant une sentinelle (valeur signifiant la fin de la donnée).

Comme tous les arbres binaires de recherche, les arbres bicolores peuvent être parcourus très efficacement en ordre infixe (ou ordre gauche - racine - droite), ce qui permet de lister les éléments dans l'ordre. La recherche d'un élément se fait en temps logarithmique O(log n), n étant le nombre d'éléments de l'arbre, y compris dans le pire des cas.

Un arbre bicolore est un arbre binaire de recherche dans lequel chaque noeud a un attribut supplémentaire : sa couleur, qui est soit rouge soit noire. En plus des restrictions imposées aux arbres binaires de recherche, les règles suivantes sont utilisées :

Un noeud est soit rouge soit noir ;
La racine est noire ;
Les enfants d'un noeud rouge sont noirs ;
Tous les noeuds ont 2 enfants. Ce sont d'autres noeuds ou des feuilles NIL, qui ne possèdent pas de valeurs et qui sont les seuls noeuds sans enfants. Leur couleur est toujours noire et rentre donc en compte lors du calcul de la hauteur noire.
Le chemin de la racine à n'importe quelle feuille (NIL) contient le même nombre de noeuds noirs. On peut appeler ce nombre de noeuds noirs la hauteur noire.

Ces contraintes impliquent une propriété importante des arbres bicolores : le chemin le plus long possible d'une racine à une feuille (sa hauteur) ne peut être que deux fois plus long que le plus petit possible : dans le cas le plus déséquilibré, le plus court des chemins ne comporte que des noeuds noirs, et le plus long alterne les noeuds rouges et noirs. Un arbre vérifiant ces propriétés est ainsi presque équilibré. Comme les opérations d'insertion, de recherche et de suppression requièrent dans le pire des cas un temps proportionnel à la hauteur de l'arbre, les arbres bicolores restent efficaces, contrairement aux arbres binaires de recherche ordinaires.

Pour comprendre comment ces contraintes garantissent la propriété ci-dessus, il suffit de s'apercevoir qu'aucun chemin ne peut avoir deux noeuds rouges consécutifs à cause de la propriété 3. Le plus petit chemin théorique de la racine à une feuille ne contient alors que des noeuds noirs tandis que le plus grand alterne entre les noeuds rouges et noirs. Et comme d'après la propriété chacun de ces chemins contient le même nombre de noeuds noirs, le plus grand chemin ne peut être deux fois plus grand que le plus petit.

La propriété 2 n'est pas nécessaire. Les seuls cas où la racine pourrait devenir rouge étant les deux cas où sa couleur n'a pas d'importance : soit la racine est le seul noeud, soit elle possède deux fils noirs. Cette propriété est ajouté uniquement pour visualiser plus rapidement l'isomorphisme avec les arbres 2-3-4 : chaque noeud noir et ses éventuels fils rouges représente un noeud d'arbre 2-3-4.

Les arbres bicolores, offrent la meilleure garantie sur le temps d'insertion, de suppression et de recherche dans les cas défavorables. Ceci leur permet non seulement d'être alors utilisables dans des applications en temps réel, mais aussi de servir comme fondement d'autres structures de données à temps d'exécution garanti dans les cas défavorables, par exemple en géométrie algorithmique. L'ordonnanceur du noyau Linux, le Completely Fair Scheduler utilise également un arbre rouge-noir.

Les arbres rouge-noir sont également très utile en programmation fonctionnelle : c'est l'exemple le plus couramment utilisé de structure de données persistante qui peut être utilisée pour construire des tableaux associatifs capables de garder en mémoires les versions précédentes après un changement. Les versions persistantes des arbres rouge-noir requièrent O(log n) en mémoire supplémentaire pour chaque insertion ou suppressions.

La recherche sur un arbre bicolore s'effectue exactement comme dans les arbres binaires de recherche. Cependant, après une insertion ou une suppression, les propriétés de l'arbre bicolore peuvent être violées. La restauration de ces propriétés requiert un petit nombre O(log n) de modifications des couleurs (qui sont très rapides en pratique) et pas plus de trois rotations (deux pour l'insertion). Ceci permet d'avoir une insertion et une suppression en O(log n) mais rend l'implémentation plus complexe à cause du grand nombre de cas particuliers à traiter.

La recherche d'un élément se déroule de la même façon que pour un arbre binaire de recherche : en partant de la racine, on compare la valeur recherchée à celle du noeud courant de l'arbre. Si ces valeurs sont égales, la recherche est terminée et on renvoie le noeud courant. Sinon, on choisit de descendre vers le noeud enfant gauche ou droit selon que la valeur recherchée est inférieure ou supérieure. Si une feuille est atteinte, la valeur recherchée ne se trouve pas dans l'arbre.

La couleur des noeuds de l'arbre n'intervient pas directement dans la recherche. Toutefois à la différence d'un arbre binaire de recherche normal, les arbres rouge-noir garantissent par construction un temps d'exécution de la recherche en O(log n) y compris dans le pire des cas. En effet, un arbre binaire de recherche peut devenir déséquilibré dans les cas défavorables (par exemple si les éléments sont insérés dans l'ordre croissant, l'arbre binaire de recherche dégénère en une liste chainée. La complexité de l'opération dans le pire des cas est donc O(n) pour un arbre binaire potentiellement non équilibré. Au contraire, pour l'arbre rouge-noir, les propriétés bicolores vues ci-dessus garantissent que l'on atteindra un noeud en au plus 2.log n comparaisons, donc en O(log n) opérations.

L'insertion commence de la même manière que sur un arbre binaire classique : en partant de la racine, on compare la valeur insérée à celle d'un noeud courant de l'arbre, et on choisit de descendre vers le noeud enfant gauche ou droit selon que la valeur insérée est inférieure ou supérieure. Le nouveau noeud est inséré lorsque l'on ne peut plus descendre, c'est-à-dire quand le noeud courant est une feuille de l'arbre. Cette feuille est remplacée par le nouveau noeud.

Une fois le nouveau noeud ajouté à l'arbre, il faut vérifier que les propriétés de l'arbre bicolore sont bien respectées et, dans le cas contraire, effectuer des opérations de changement de couleur et des rotations pour les établir. Le noeud inséré est initialement colorié en rouge. Il y a ensuite plusieurs cas possibles pour rétablir les propriétés de l'arbre, à partir du noeud inséré.

Le noeud inséré n'a pas de parent : il est en fait à la racine de l'arbre. La seule correction à apporter consiste à le colorier en noir pour respecter la propriété 2.
Le noeud du parent inséré est noir, alors, l'arbre est valide : la propriété 3 et vérifiée, et la hauteur noire de l'arbre est inchangée puisque le nouveau noeud est rouge. Il n'y a donc rien d'autre à faire.
Le parent du noeud inséré est rouge, alors la propriété 3 est invalide. L'action à effectuer dépend de la couleur de l'oncle du noeud inséré, c'est à dire le "frère" du parent du noeud inséré. En d'autres termes : en partant du noeud inséré (N), on considère son noeud parent (P), puis le noeud parent de P, ou grand parent (G), et enfin l'oncle (U) qui est le fils de G qui n'est pas P. Si l'oncle est rouge, alors le parent et l'oncle sont coloriés en noir, et le grand parent (qui était nécessairement noir) est colorié en rouge. Ce changement de couleur a pu toutefois créer une nouvelle violation des propriétés bicolores plus haut dans l'arbre. Il faut maintenant recommencer la même analyse de cas mais cette fois en partant du noeud grand parent ainsi colorié en rouge.
Dans le cas où l'oncle est noir, il faut effectuer des rotations qui dépendent de la configuration du noeud inséré autour de son parent et de son grand parent, afin de ramener l'équilibre dans l'arbre. Le parent vient prendre la place du grand parent, et le grand parent celle de l'oncle. Le parent devient noir et le grand parent rouge et l'arbre respecte alors les propriétés bicolores.

Le seul cas où la correction ne se termine pas immédiatement est le cas 3, dans lequel on change le grand parent de noir à rouge, ce qui oblige à effectuer une nouvelle vérification du grand parent. Cependant, il est aisé de vérifier que la fonction se termine toujours. Puisque le noeud à vérifier est toujours strictement plus haut que le précédent, on finira inévitablement par se retrouver dans l'un des cas non récursifs (dans le pire des cas, on remontera jusqu'à atteindre la racine de l'arbre, c'est à dire le cas 1). Il y aura donc au plus deux rotations, et un nombre de changements de couleurs inférieur à la moitié de la hauteur de l'arbre, c'est à dire en O(log n). En pratique la probabilité de tomber plusieurs fois de suite sur le cas 3 est exponentiellement décroissante ; en moyenne le coût de la correction des propriétés est donc presque constant.

Structures de données

Tas

Un tas est une structure de données de type arbre tel que pour tous noeuds A et B de l'arbre tels que B soit un fils de A : clé(A)≥clé(B) (ou inversement). Les primitives du tas sont : enfiler et defiler.

Pour enfiler un élément, on le place comme feuille, puis on fait "remonter" l'élément pour maintenir la priorité du tas. L'opération peut être réalisée en O(log n).

Quand on défile un élément d'un tas, c'est toujours celui de priorité maximale. Il correspond donc à la racine du tas. L'opération peut conserver la structure de tas, avec une complexité de O(log n) ; en effet, il ne reste alors qu'à réordonner l'arbre privé de sa racine pour en faire un nouveau tas.

Structures de données

Table de hachage

Une table de hachage est une structure de données qui implémente un type abstrait de tableau associatif. Une table de hachage utilise une fonction de hachage afin de calculer l'index d'un tableau d'emplacements desquels la valeur attendue peut être trouvée. Pendant la recherche, la clef est hachée et le hash résultant indique l'emplacement de la valeur correspondante.

Idéalement, la fonction de hachage assignera chaque clef à un réceptacle unique, mais la plupart des tables de hachage utilisent des fonctions de hachages imparfaites, qui peuvent causer des collisions quand la fonction de hachage attribue un même index pour plus d'une clef. Ces collisions sont alors traitées de diverses manières.

Dans une table de hachage bien dimensionnée, le coût moyen (nombre d'instructions) pour chaque recherche est indépendant du nombre d'élément stockés dans la table. Beaucoup de tables de hachages permettent également des insertions et des suppressions arbitraires de paires clef-valeur, à un coût (amorti) moyen constant par opération.

Dans de nombreuses situations, les tables de hachage sont en moyenne plus efficaces que des arbres de recherche ou de n'importe quelle autre structure de table de recherche. C'est pour cette raison, qu'elles sont largement utilisé dans un large panel de logiciels informatiques, particulièrement les tableaux associatifs, l'indexation des bases de données, les caches, et les ensembles.

L'idée du hachage est de distribuer les entrées (paires clefs/valeurs) à travers un tableau de réceptacles. Étant donné une clef, l'algorithme calcule un index qui suggère où l'entrée peut se trouver :

    index = f(clef, taille_tableau)

Souvent cette opération est réalisée en deux étapes :

    hash = hashfunc(key) index = hash % array_size

Avec cette méthode, le hash est indépendant de la taille du tableau, et est réduit à postériori à un index (un nombre entre 0 et taille_tableau - 1) à l'aide de l'opérateur modulo (%).

Dans le cas où la taille du tableau est une puissance de 2, l'opération de reste est réduite à un masquage, ce qui améliore la performance, mais aussi fait croître le nombre de problèmes si la fonction de hachage est mauvaise.

Une condition basique pour la fonction est de fournir une distribution uniforme des valeurs de hash. Une distribution non-uniforme augmente le nombre de collision est le coût pour les résoudre. L'uniformité est quelques fois difficile à garantir, mais elle peut être évaluée de manière empirique via des tests statistiques.

La distribution doit être uniforme uniquement pour les tailles de tables de l'application. Si l'application utilise un redimensionnement dynamique de la table avec un doublement ou une division par deux de la taille, alors la fonction de hachage doit être uniforme uniquement lorsque la taille est une puissance de deux. Ici l'index peut être calculé comme un intervalle de bits de la fonction de hachage. D'un autre côté, des algorithmes de hachage préfèrent avoir une taille exprimé à l'aide d'un nombre premier. L'opération modulo peut fournir un petit mélange additionnel ; ceci est appréciable notamment pour une mauvaise fonction de hachage.

Pour les schémas d'adressage ouvert, la fonction de hachage doit également éviter le clustering, l'adressage de deux ou de plusieurs clefs à des emplacements consécutifs. Un tel regroupement peut être la cause d'une envolée du coût de recherche, même si le facteur de charge est bas et que les collisions sont rares.

Les fonctions de hachages cryptographiques seraient capable de fournir de bonnes fonctions de hachages quelque soit la taille de la table, soit par réduction modulo ou par masquage de bit. Elles peuvent également être utiles si il existe un risque d'utilisateurs malveillants essayant de saboter un service réseau en envoyant des requêtes destinées à générées un grand nombre de collisions dans les tables de hachage du serveur. Néanmoins, le risque de sabotage peut également être évité par des méthodes moins coûteuses (tels qu'appliquer un sel secret à la donnée, ou utiliser une fonction de hachage universelle). Un inconvénient des fonctions de hachages cryptographiques est qu'elles sont souvent plus lentes à être calculées, ce qui veut dire que dans certains cas où l'uniformité pour n'importe quelle taille n'est pas nécessaire, une fonction de hachage non-cryptographique peut être préférable.

Un hachage k-indépendant offre un moyen de prouver qu'une fonction de hachage n'a pas de mauvais ensembles de clefs pour un type de table de hachage donné. De nombreux résultats de ce type sont connus pour des schémas de résolution de collision.

Si toutes les clefs sont connues à l'avance, une fonction de hachage parfaite peut être utilisée pour créer une table de hachage parfaite sans aucune collision. Si un hachage parfait minimal est utilisé, chaque emplacement dans la table de hachage peut également être utilisé.

Un hachage parfait permet un temps de recherche constant dans tout les cas. Ceci se détache de la majorité des méthodes de chaînage et d'adressage ouvert, où le temps de recherche est bas en moyenne, mais peut être très grand, O(n), par exemple lorsque toutes les clefs sont hachées vers trop peu de valeurs.

Une statistique critique pour une table de hachage est le facteur de charge, défini comme :

Facteur de charge = n/k, où

n est le nombre des entrées occupées dans la table de hachage,
k est le nombre d'emplacements.

Quand le facteur de charge augmente, la table de hachage devient plus lente, et peut même cesser de fonctionner (en fonction de la méthode utilisée). Le propriété attendue de temps constant pour une table de hachage suppose que le facteur de charge soit gardé en deçà d'une certaine limite. Pour un nombre d'emplacement fixe, le temps pour une recherche augmente avec le nombre d'entrées, par conséquent, le temps constant désiré n'est pas atteint. Dans plusieurs implémentations, la solution est de faire croître automatiquement (généralement, doubler) la taille de la table lorsque la limite du facteur de charge est atteinte, forçant de fait, un nouveau hachage de l'ensemble des entrées.

Après le facteur de charge, on peut examiner la variance du nombre d'entrées par emplacement.

Un facteur de charge bas n'est pas forcément bénéfique. Quand le facteur de charge approche 0, la proportion des aires inutilisées dans la table de hachage augmente, mais il n'y a pas nécessairement une réduction dans le coût de recherche.

Les collision de hash sont pratiquement inévitables quand on hache un sous-ensemble aléatoire d'un large ensemble de clefs possibles.

Par conséquent, presque toutes les implémentations de tables de hachages ont des stratégies de résolution de collisions afin de gérer celles-ci. Toutes ces méthodes nécessitent que les clefs soient stockées dans la table, ensemble avec leurs valeurs associées.

Algorithmes de chiffrements

Sous-sections

Algorithmes de chiffrements

Chiffrement symétrique AES

Le standard de chiffrement avancé (AES), aussi connu sous son nom originel Rijndael, est une spécification pour le chiffrement des données électroniques établi par l'institut national des standards et technologies (NIST) en 2001.

AES est un sous-ensemble du chiffrement par bloc Rijndael. Rijndael est une famille de chiffres comprenant différentes clefs et différentes tailles de blocs. Pour AES, NIST a sélectionné trois membres de la famille Rijndael, chacun ayant une taille de bloc de 128 bits, mais trois longueurs de clefs différentes : 128, 192 et 256 bits.

AES est basé sur un principe simple connu sous le nom de réseau de substitution-permutation, et est efficace tant au niveau logiciel que matériel.

AES opère sur un tableau de bits ordonné 4 x 4. La plupart des calculs AES sont effectués dans un champ fini particulier.

La taille de clef utilisée pour un chiffre AES spécifie le nombre de rondes de transformations qui convertissent l'entrée, appelée texte en clair, à la sortie finale, appelée texte chiffré. Les nombres de rondes sont les suivants :

10 rondes pour des clefs de 128 bits.
12 rondes pour des clefs de 192 bits.
14 rondes pour des clefs de 256 bits.

Chaque ronde consiste en plusieurs étapes de calculs, incluant une étape qui dépend de la clef de chiffrement elle même. Un ensemble de rondes inversées sont appliquées pour retransformer le texte chiffré en son texte original en clair à l'aide de la même clef de chiffrement.

Algorithmes de chiffrements

Chiffrement asymétrique RSA

Dans un système de chiffrement à clef publique, la clef de chiffrement est publique et distincte de la clef de déchiffrement, qui est gardée secrète (privée). Un utilisateur RSA créé et publie une clef publique sur la base de deux grand nombres premiers, ainsi qu'une valeur auxiliaire. Les nombres premiers sont gardés secret. Les messages peuvent être chiffrés par n'importe qui, via la clef publique, mais peut uniquement être décodé par quelqu'un connaissant les nombres premiers.

La sécurité du RSA repose sur la difficulté pratique à factoriser le produit de deux grands nombres premiers, le "problème de factorisation".

RSA est un algorithme relativement lent. De ce fait, il n'est généralement pas directement utilisé pour chiffrer les données des utilisateurs. Il est plus souvent utilisé pour transmettre des clefs partagées pour un chiffrement à clef symétrique, qui est ensuite utilisé pour le chiffrement et déchiffrement des données.

La taille des clefs pour le chiffrement RSA varie entre 1024 et 4096 bits avec récemment une recommandation minimale de 2048 bits.

Programmation orientée objet

La programmation orientée objet (POO), ou programmation par objet, est un paradigme de programmation informatique basé sur le concept d'objets, qui peuvent contenir du code et des données : les données sous la forme de champs (attributs ou propriétés), et le code sous la forme de procédures (méthodes).

Une capacité des objets est que ses procédures peuvent accéder et souvent modifier ses propres champs de données (this ou self). En POO, les programmes informatiques sont créés de façon à pouvoir interagir les uns avec les autres. Les langages de POO peuvent être très divers, mais les plus populaires sont basés sur la notion de classe, cela signifie que les objets sont des instances de classes, qui déterminent également leurs types.

Une classe regroupe des membres, méthodes et propriétés (attributs) communs à un ensemble d'objets. La classe déclare, d'une part, des attributs représentant l'état des objets et, d'autres part, des méthodes représentant leur comportement.

Il est possible de restreindre l'ensemble d'objets représenté par une classe A grâce à un mécanisme d'héritage. Dans ce cas, on crée une nouvelle classe B liée à la classe A et qui ajoute de nouvelles propriétés.

Dans la programmation par objets, chaque objet est typé. Le type définit la syntaxe et la sémantique des messages auxquels peut répondre un objet. Il correspond donc, à peu de chose près, à l'interface de l'objet.

Un objet peut appartenir à plus d'un type, c'est le polymorphisme, cela permet d'utiliser des objets de types différents là où est attendu un objet d'un certain type.

Compilation

Un compilateur est un programme qui transforme un code source en code objet. Généralement, le code source est écrit dans un langage de programmation (le langage source), il est de haut niveau d'abstraction, et facilement compréhensible par l'humain. Le code objet est généralement écrit en langage de plus bas niveau (appelé langage cible), par exemple un langage d'assemblage ou langage machine, afin de créer un programme exécutable par une machine.

Un compilateur effectue les opérations suivantes : analyse lexicale, pré traitement (préprocesseur), analyse syntaxique (parsing), analyse sémantique, et génération de code optimisé. La compilation est souvent suivie d'une étape d'édition de liens, pour générer un fichier exécutable.

On distingue deux options de compilation :

Ahead-of-time (AOT), où il faut compiler le programme avant de lancer l'application : la situation traditionnelle.
Compilation à la volée (just-in-time, en abrégé JIT) : cette faculté est apparue dans les années 1980 (par exemple Tcl/Tk)

La tache principale d'un compilateur est de produire un code objet correct qui s'exécutera sur un ordinateur. La plupart des compilateurs permettent d'optimiser le code, c'est-à-dire qu'ils vont chercher à améliorer la vitesse d'exécution, ou réduire l'occupation mémoire du programme.

Un compilateur fonctionne par analyse-synthèse : au lieu de remplacer chaque construction du langage source par une suite équivalente de constructions du langage cible, il commence par analyser le texte source pour en construire une représentation intermédiaire qu'il traduit à son tour en langage cible.

On sépare le compilateur en au moins deux parties : une partie avant (ou frontale), parfois appelée "souche", qui lit le texte source et produit la représentation intermédiaire ; et la partie arrière (ou finale), qui parcours cette représentation pour produire le texte cible. Dans un compilateur idéal, la partie avant est indépendante du langage cible, tandis que la partie arrière est indépendante du langage source (voir Low Level Virtual Machine).

L'implémentation d'un langage de programmation peut être interprétée ou compilée. Cette réalisation est un compilateur ou un interpréteur, et un langage de programmation peut avoir une implémentation compilée, et une autre interprétée.

On parle de compilation si la traduction est faite avant l'exécution, et d'interprétation si la traduction est finie pas à pas, durant l'exécution.

Les premiers compilateurs ont été écrits directement en langage assembleur, un langage symbolique élémentaire correspondant aux instructions du processeur cible et quelques structures de contrôle légèrement plus évoluées. Ce langage symbolique doit être assemblé (et non compilé) et lié pour obtenir une version exécutable. En raison de sa simplicité, un programme simple suffit à le convertir en instruction machines.

Les compilateurs actuels sont généralement écrits dans le langage qu'ils doivent compiler : il ne dépend alors plus d'un autre langage pour être produit.

Dans ce cas, il est complexe de détecter un bogue de compilateur. Le bootstrap oblige donc les programmeurs de compilateurs à contourner les bugs des compilateurs existants.

API

Une Interface de Programmation d'Application (API) est une interface qui définit des interactions entre des applications logicielles diverses. Elle définit le type d'appels ou de requêtes pouvant être exécutés, comment les faire, les formats de données qui doivent être utilisés, les conventions qui en découlent, etc. Elle peut également fournir des mécanismes d'extension de façon à ce que les utilisateurs puissent étendre les fonctionnalités existantes de plusieurs manières et à des degrés variés. Une API peut être entièrement personnalisée, spécifique à un composant, ou construite à partir d'un standard afin de garantir l'interopérabilité. À travers le masquage d'information, les APIs présentent une approche modulaire et permettent aux utilisateurs d'accéder à l'interface indépendamment de son implémentation.

Sous-sections

API

SOAP

SOAP (Simple Object Access Protocol) est une spécification de protocole de messages pour des échanges d'information structurée dans l'implémentation de webs services à travers un réseau informatique. Son objectif est de fournir extensibilité, neutralité, verbosité et indépendance. Elle utilise un ensemble d'information XML pour son format de message, et s'appuie sur des protocoles de la couche application, la plupart du temps HTTP, bien que certains anciens systèmes communiquent via SMTP, pour la négociation et la transmission de messages.

SOAP permet aux développeurs d'invoquer des processus s'exécutant sur des systèmes d'exploitation disparates d'authentifier, d'autoriser, et de communiquer à l'aide du langage de balisage extensible (XML). Puisque les protocoles webs tels que HTTP sont installés et actifs sur tous les systèmes d'exploitation, SOAP permet aux clients d'invoquer des services webs et de recevoir des réponses indépendantes du langage et des plateformes.

SOAP fournit la couche de protocole de messages de la pile de protocoles des webs services. C'est un protocole basé sur le langage XML qui consiste en trois parties :

Une enveloppe, qui définit la structure du message et la façon de le traiter.
Un ensemble de règles d'encodage afin d'exprimer des instances de types de données définis par application.
Une convention pour représenter les appels de procédures et leurs réponses.

SOAP a trois caractéristiques majeures :

l'extensibilité
la neutralité (SOAP peut opérer à travers des protocoles tels que HTTP, SMTP, TCP, UDP)
l'indépendance (SOAP ne contraint en aucune façon le modèle de programmation)

L'architecture SOAP consiste en plusieurs couches de spécifications pour :

le format de message
les motifs d'échange de message (MEP)
les liens au protocole de transport sous-jacent
les modèles de traitement de messages
l'extensibilité du protocole

SOAP a évolué en tant que successeur de XML-RPC, bien qu'il emprunte son transport et la neutralité d'interaction de l'adressage des webs services et l'enveloppe/entête/corps d'autres modèles.

La spécification SOAP peut être grossièrement définie comme étant constituée des 3 composants conceptuels suivants : les concepts de protocole, les concepts d'encapsulation et les concepts de réseau.

SOAP est un ensemble de règles qui formalisent et gouvernent le format et les règles de traitement pour l'information échangé entre l'émetteur et le receveur SOAP.

Les noeuds SOAP sont des machines physiques/logiques avec des unités de traitement utilisées pour transmettre/relayer, recevoir et traiter les messages SOAP. Ils sont analogues aux noeuds d'un réseau.

Les rôles SOAP sont les rôles spécifiques qu'assument chacun des noeuds, à travers le chemin d'un message SOAP. Le rôle du noeud définit l'action que le noeud doit effectuer sur le message qu'il reçoit. Par exemple, un rôle none signifie qu'aucun noeud ne traitera l'entête SOAP en aucune façon et transmettra simplement le message le long de son chemin.

Les liens aux protocoles SOAP sont les interactions du message SOAP travaillant en conjonction des autres protocoles afin de transférer un message SOAP à travers le réseau. Par exemple, un message SOAP peut utiliser TCP comme sous-couche protocolaire pour le transfert de messages. Ces liens sont définis dans le cadre des liens aux protocoles sous-jacent SOAP.

Les fonctionnalités SOAP permettent d'étendre le cadre de message SOAP pour ajouter des fonctions telles que la fiabilité, la sécurité etc. Il existe des règles à suivre lors de l'ajout de fonctionnalités au cadre SOAP.

Les modules SOAP sont une collection de spécifications concernant la sémantique des entêtes SOAP pour décrire une nouvelle fonctionnalité étendue s'ajoutant à SOAP. Un module requiert zéro ou plusieurs fonctionnalités. SOAP a besoin des modules pour adhérer au règles prescrites.

Le message SOAP représente l'information échangée entre 2 noeuds SOAP.

L'enveloppe SOAP est l'ensemble des éléments délimiteurs d'un message XML qui l'identifie comme étant un message SOAP.

Le bloc d'entête SOAP est un bloc de traitement discret contenu dans l'entête qui elle peut en contenir plusieurs. En général, l'information du rôle SOAP est utilisée pour cibler des noeuds du chemin. Un bloc d'entête est dit être ciblé sur un noeud SOAP si le rôle SOAP du bloc d'entête est le nom d'un rôle dans lequel le noeud SOAP opère. Par exemple le bloc d'entête SOAP avec l'attribut de rôle ultimateReceiver est ciblé seulement au noeud destination qui a ce rôle. Un entête avec un attribut de rôle next est ciblé pour chaque intermédiaire ainsi que le noeud destination.

L'entête SOAP est une collection d'un ou de plusieurs blocs d'entêtes ciblés pour chaque receveurs SOAP.

Le corps SOAP contient le corps du message à l'attention du receveur SOAP. L'interprétation et le traitement du corps SOAP est défini par le blocs d'entêtes.

L'erreur SOAP est un élément qui contient l'information d'erreur dans le cas où un noeud SOAP échoue à traiter un message SOAP. Cet élément est contenu dans le corps SOAP en tant qu'élément enfant.

L'émetteur SOAP est un noeud qui transmet un message SOAP.

Le receveur SOAP est un noeud recevant un message SOAP. (Il peut s'agir d'un noeud intermédiaire ou d'un noeud destination)

Le chemin du message SOAP est l'ensemble des noeuds que le message SOAP a traversé pour atteindre le noeud destination.

L'émetteur initial SOAP est le noeud à l'origine de message SOAP à transmettre. C'est la racine du chemin du message SOAP.

L'intermédiaire SOAP est le noeud situé entre l'émetteur initial et la destination SOAP voulue. Il traite les blocs d'entête ciblés sur lui et agit pour relayer un message SOAP vers son ultime receveur SOAP.

L'ultime receveur SOAP est le receveur destinataire du message SOAP. Ce noeud est responsable du traitement du corps du message et des blocs d'entête ciblés sur lui.

La spécification SOAP définit un cadre de messages, qui consiste en :

Le modèle de traitement SOAP, définissant les règles pour traiter un message SOAP.
Le modèle d'extensibilité SOAP, définissant les concepts de fonctionnalités et de modules SOAP.
Le cadre de liens aux protocoles sous-jacents décrivant les règles définissant les liens aux protocoles sous-jacents pouvant être utilisés lors des échanges de messages entre noeuds SOAP.
Le concept de message SOAP définissant la structure d'un message SOAP.

Un message SOAP est un document XML ordinaire contenant les éléments suivants :

Élément	Description	Requis
Enveloppe	Identifie le document XML en tant que message SOAP	Oui
Entête	Contient les informations d'entête	Non
Corps	Contient les informations d'appel et de réponse	Oui
Erreur	Fournit des informations à propos d'erreurs ayant eu lieu lors du traitement du message	Non

À la fois SMTP et HTTP sont des protocoles de la couche application valides en tant que transports pour SOAP, mais HTTP est plus largement utilisé du fait qu'il fonctionne bien avec l'infrastructure internet ; spécifiquement, HTTP fonctionne bien avec les pare-feu réseaux. SOAP peut également être utilisé par dessus HTTPS (qui est le même protocole qu'HTTP au niveau application, mais utilise un protocole de transport chiffré en dessous) avec une authentification simple ou mutuelle ; c'est la méthode utilisée pour fournir une sécurité au niveau des webs services.

L'ensemble des informations XML a été choisi comme format de message standard du fait de son très large usage dans l'industrie et des efforts de développements open source. Typiquement, l'ensemble des informations XML est sérialisé comme du XML.

API

REST

Le transfert d'état de représentations (REST) est un style d'architecture logicielle qui utilise un sous-ensemble d'HTTP. Il est communément utilisé pour créer des applications interactives qui utilisent des services webs. Un service web qui suit ces lignes directrices est appelé RESTful. Un tel service web doit fournir ses ressources webs dans une représentation textuelle et permettre de les lire et de les modifier à l'aide d'un protocole sans état et d'un ensemble d'opérations prédéfinies. Cette approche permet l'interopérabilité entre les systèmes informatiques sur l'Internet qui fournissent ces services. REST est une alternative par exemple au protocole SOAP qui permet d'accéder à un service web.

Des ressources webs étaient définis premièrement sur le web comme étant des documents ou des fichiers identifiés par leur URLs. Aujourd'hui, la définition est bien plus générique et abstraite, et inclut chaque chose, entité, ou action pouvant être identifiée, nommée, adressée, gérée ou exécutée, de quelque manière que ce soit sur le Web. Dans un service web RESTful, les requêtes effectuées à une URI de ressource obtiennent une réponse avec un chargement formaté en HTML, XML, JSON, ou quelque autre format. Par exemple, la réponse peut confirmer que l'état de la ressource a changé. La réponse peut également inclure des liens hypertextes vers des ressources liées. Le protocole le plus commun pour ces requêtes et ces réponses est HTTP. Il fournit des opérations (méthodes HTTP) telles que GET, POST, PUT, et DELETE. En utilisant des protocoles sans état et des opérations standards, les systèmes RESTful essaient de tendre vers la performance, la fiabilité et la capacité à s'étendre en réutilisant des composants pouvant être gérés et mis à jours sans affecter le système dans son entièreté, même en cours d'exécution.

Le but de REST est d'améliorer la performance, la mise à l'échelle, la simplicité, l'adaptabilité, la visibilité, la portabilité, et la fiabilité. Ceci est réalisé à travers le respect des principes de REST tels que l'architecture client-serveur, l'absence d'états, la possibilité de mise en cache, l'utilisation de systèmes multi-couches, le support de code à la demande, et l'usage d'interfaces uniformisées. Ces principes doivent être suivis pour qu'un système soit classifié en tant que système REST.

API

GraphQL

GraphQL est un langage de requêtage et de manipulation de données pour APIs, ainsi qu'un environnement d'exécution permettant de répondre aux requêtes à l'aide de données existantes.

Il fournit une approche au développement d'APIs webs et est souvent comparé à REST et autres architectures de services webs. Il permet aux clients de définir une structure de la donnée requise, et cette même structure de la donnée est retournée par le serveur, prévenant ainsi le retour d'une trop grande quantité de données, mais ceci a des implications sur l'efficacité de la mise en cache web des résultats de requêtes. La flexibilité et la richesse du langage de requêtage ajoute également une complexité qui n'est pas forcément nécessaire pour des APIs simples. Malgré le nom, GraphQL ne fournit pas la richesse des opérations de graphe que l'on peut trouver dans les bases de données orientées graphes tels que Neo4j, ou même certains dialectes de SQL qui supportent les fermetures transitives. Par exemple, une interface GraphQL qui rapporte les parents d'un individu ne peut pas retourner en une seule requête, l'ensemble de ses ancêtres.

GraphQL consiste en un système de types, un langage de requêtage et une sémantique d'exécution, une validation statique et une introspection de type. Il supporte la lecture, l'écriture (mutation), et la souscription à des modifications de la donnée (mis à jour en temps réel -- implémentée le plus souvent à l'aide de websockets). Les serveurs GraphQL sont disponibles pour de nombreux langages de programmations.

API

gRPC

gRPC est un système d'appel de procédures distantes. Il utilise HTTP/2 pour le transport, et protobuf en tant que langage de description d'interface, et fournit des fonctionnalités telles que l'authentification, le streaming bidirectionnel et le contrôle de flux, les liaisons bloquantes ou non bloquantes, l'annulation et les dépassements de délais. Il génère des liaisons entre les clients multi-plateformes et le serveur pour de nombreux langages. Les usages généraux incluent l'interconnexion de services dans un style architectural microservices, ou la connexion de clients mobiles à des services backend.

gRPC supporte l'usage de TLS et d'une authentification basée token. Il y a deux types de certificats : les certificats de canaux et les certificats d'appels.

gRPC utilise protobuf pour encoder la donnée. Contrairement aux APIs HTTP avec JSON, elles obéissent à une spécification stricte.

Système

Introduction

Ce chapitre traite de la partie système du programme PSE.

J'ai essayé de présenter à peu près logiquement et de manière globale mais loin d'être exhaustive, les éléments d'un système d'exploitation (Linux). Pour aller plus loin sur l'ensemble des sujets évoqués on peut aller retrouver la documentation du noyau Linux.

Sections

Processus et mécanismes de communication

Sous-sections

Processus et mécanismes de communication

Multitâche coopératif

Le multitâche coopératif est une forme simple de multitâche où chaque tâche doit explicitement permettre aux autres tâches de s'exécuter. Cette approche simplifie l'architecture du système mais présente plusieurs inconvénients :

Le multitâche coopératif est une forme de couplage fort. Si un des processus ne redonne pas la main à un autre processus, par exemple si le processus est buggé, le système entier peut s'arrêter.
Le partage de ressources (temps CPU, mémoire, accès disque, etc.) peut être inefficace.

Processus et mécanismes de communication

Multitâche préemptif

Le multitâche préemptif désigne la capacité d'un système d'exploitation à exécuter ou arrêter une tâche planifiée en cours.

Un ordonnanceur préemptif présente l'avantage d'une meilleure réactivité du système et de son évolution, mais l'inconvénient vient des situations de compétition (lorsque le processus d'exécution accède à la même ressource avant qu'un autre processus (préempté) ait terminé son utilisation).

Dans un système d'exploitation multitâche préemptif, les processus ne sont pas autorisés à prendre un temps non défini pour s'exécuter dans le processeur. Une quantité de temps définie est attribuée à chaque processus ; si la tâche n'est pas accomplie avant la limite fixée, le processus est renvoyé dans la pile pour laisser place au processus suivant dans la file d'attente, qui est alors exécuté par le processeur. Ce droit de préemption peut tout aussi bien survenir avec des interruptions matérielles.

Certaines tâches peuvent être affectées d'une priorité ; une tâche pouvant être spécifiée comme "préemptible" ou "non préemptible". Une tâche préemptible peut être suspendue (mise à l'état "ready") au profit d'une tâche de priorité plus élevée ou d'une interruption. Une tâche non préemptible ne peut être suspendue qu'au profit d'une interruption. Le temps qui lui est accordé est plus long, et l'attente dans la file d'attente plus courte.

Au fur et à mesure de l'évolution des systèmes d'exploitation, les concepteurs ont quitté la logique binaire "préemptible/non préemptible" au profit de systèmes plus fins de priorités multiples. Le principe est conservé, mais les priorités des programmes sont échelonnées.

Pendant la préemption, l'état du processus (drapeaux, registres et pointeurs d'instruction) est sauvé dans la mémoire. Il doit être rechargé dans le processeur pour que le code soit exécuté à nouveau : c'est la commutation de contexte.

Un système d'exploitation préemptif conserve en permanence la haute main sur les tâches exécutées par le processeur, contrairement à un système d'exploitation non préemptif, ou collaboratif, dans lequel c'est le processus en cours d'exécution qui prend la main et décide seul du moment où il la rend. L'avantage le plus évident d'un système préemptif est qu'il peut en permanence décider d'interrompre un processus, principalement si celui-ci échoue et provoque l'instabilité du système.

Processus et mécanismes de communication

Algorithmes d'ordonnancement

L'ordonnanceur désigne le composant du noyau du système d'exploitation choisissant l'ordre d'exécution des processus sur les processeurs d'un ordinateur.

Un processus a besoin de la ressource processeur pour exécuter des calculs ; il l'abandonne quand se produit une interruption, etc. De nombreux anciens processeurs ne peuvent effectuer qu'un traitement à la fois. Pour les autres, un ordonnanceur reste nécessaire pour déterminer quel processus sera exécuté sur quel processeur (c'est la notion d'affinité, très importante pour ne pas dégrader les performances). Au-delà des classiques processeurs multicoeurs, la notion d'hyperthreading rend la question de l'ordonnancement encore un peu plus complexe.

A un instant donné, il y a souvent davantage de processus à exécuter que de processeurs.

Un des rôles de système d'exploitation et plus précisément de l'ordonnanceur du noyau, est de permettre à tous ces processus de s'exécuter à un moment ou un autre et d'utiliser au mieux le processeur pour l'utilisateur. Pour que chaque tâche s'exécute sans se préoccuper des autres et/ou aussi pour exécuter les tâches selon les contraintes imposées au système, l'ordonnanceur du noyau du système effectue des commutations de contexte de celui-ci.

A intervalles réguliers, le système appelle une procédure d'ordonnancement qui élit le prochain processus à exécuter. Si le nouveau processus est différent de l'ancien, un changement de contexte (opération consistant à sauvegarder le contexte d'exécution de l'ancienne tâche comme les registres du processeur) a lieu. Cette structure de données est généralement appelée PCB (process control block). Le système d'exploitation restaure l'ancien PCB de la tâche élue, qui s'exécute alors en reprenant là où elle s'était arrêtée précédemment.

Du choix de l'algorithme d'ordonnancement dépend le comportement du système. Il existe deux grandes classes d'ordonnancement :

L'ordonnancement en temps partagé présent sur la plupart des ordinateurs "classiques". Par exemple l'ordonnancement "decay" ; qui est celui par défaut sous Unix. Il consiste en un système de priorités adaptatives, par exemple il privilégie les tâches interactives pour que leur temps de réponse soit bon. Une sous-classe de l'ordonnancement en temps partagé sont les ordonnanceurs dits "proportional share", eux sont plus destinés aux stations de calcul et permettent une gestion rigoureuse des ressources. On peut citer notamment "lottery" et "stride".
L'ordonnancement en temps réel qui assure qu'une certaine tâche sera terminée dans un délai donné. Cela est indispensable dans les systèmes embarqués. Un ordonnanceur temps réel est dit optimal pour un système de tâches s'il trouve une solution d'ordonnancement du système lorsque cette solution existe. S'il ne trouve pas de solution à ce système, alors aucun autre ordonnanceur ne peut en trouver une.

Algorithmes d'ordonnancement :

Round-robin (ou méthode du tourniquet) : Une petite unité de temps appelé quantum de temps est définie. La file d'attente est gérée comme une file circulaire. L'ordonnanceur parcourt cette file et alloue un temps processeur à chacun des processus pour un intervalle de temps de l'ordre d'un quantum au maximum. La performance de round-robin dépend fortement du choix du quantum de base.
Rate-monotonic scheduling (RMS) : L'ordonnancement à taux monotone est un algorithme d'ordonnancement temps réel en ligne à priorité constante (statique). Il attribue la priorité la plus forte à la tâche qui possède la plus petite période. RMS est optimal dans le cadre d'un système de tâches périodiques, synchrones, indépendantes et à échéance sur requête avec un ordonnanceur préemptif. De ce fait, il n'est généralement utilisé que pour ordonnancer des tâches vérifiant ces propriétés.
Earliest deadline first scheduling (EDF) : C'est un algorithme d'ordonnancement préemptif à priorité dynamique, utilisé dans les systèmes temps réels. Il attribue une priorité à chaque requête en fonction de l'échéance de cette dernière selon la règle : Plus l'échéance d'une tâche est proche, plus sa priorité est grande. De cette manière, au plus vite le travail doit être réalisé, au plus il a des chances d'être exécuté.
FIFO : Les premiers processus ajoutés à la file seront les premières à être exécutés.
Shortest job first (SJF, ou SJN-Shortest Job Next) : Le choix se fait en fonction du temps d'exécution estimé du processus. Ainsi l'ordonnanceur va laisser passer en priorité le plus court des processus de la file d'attente.
Completely Fair Scheduler (CFS) : L'ordonnanceur des tâches pour le noyau Linux. Il gère l'allocation de ressource processeur pour l'exécution des processus, en maximisant l'utilisation globale CPU tout en optimisant l'interactivité. CFS utilise un arbre rouge-noir implémentant une chronologie des futures exécutions des tâches. En effet, l'arbre trie les processus selon une valeur representative du manque de ces processus en temps d'allocation du processeur, par rapport au temps qu'aurait alloué un processeur dit multitâche idéal. De plus, l'ordonnanceur utilise une granularité temporelle à la nanoseconde, rendant redondante la notion de tranche de temps, les unités atomiques utilisées pour le partage du CPU entre processus. Cette connaissance précise signifie également qu'aucune heuristique (basée sur la statistique, donc pouvant commettre des erreurs) n'est requise pour déterminer l'interactivité d'un processus.

Processus et mécanismes de communication

Synchronisation

En programmation concurrente, la synchronisation se réfère à deux concepts distincts mais liés : la synchronisation de processus et la synchronisation des données. La synchronisation de processus est un mécanisme qui vise à bloquer l'exécution de certains processus à des points précis de leur flux d'exécution, de manière que tous les processus se rejoignent à des étapes relais données, tel que prévu par le programmeur. La synchronisation de données, elle, est un mécanisme qui vise à conserver la cohérence des données telles que vues par différents processus, dans un environnement multitâche. Initialement, la notion de synchronisation est apparue pour la synchronisation de données.

Ces problèmes dits "de synchronisation" et même plus généralement ceux de communication inter-processus dont ils dépendent rendent pratiquement toujours la programmation concurrente plus difficile. Certaines méthodes de programmation, appelées synchronisation non-blocante, cherchent à éviter d'utiliser des verrous, mais elles sont encore plus difficiles à mettre en oeuvre et nécessitent la mise en place de structure de données particulières. La mémoire transactionnelle logicielle en est une.

La synchronisation de processus cherche par exemple à empêcher des programmes d'exécuter la même partie de code en même temps, ou au contraire forcer l'exécution de deux partie de code en même temps. Dans la première hypothèse, le premier processus bloque l'accès à la section critique avant d'y entrer et libère l'accès après y être sorti. Ce mécanisme peut être implémenté de multiples manières.

Ces mécanismes sont par exemple la barrière de synchronisation, l'usage conjoint des sémaphores et des verrous, les spinlock, le moniteur.

Barrière de synchronisation : Permet de garantir qu'un certain nombre de tâches aient passé un point spécifique. Ainsi, chaque tâche qui arrivera sur cette barrière devra attendre jusqu'à ce que le nombre spécifié de tâches soient arrivées à cette barrière.
Sémaphore : Variable partagée par différents "acteurs" qui garantit que ceux-ci ne peuvent accéder de façon séquentielle à travers des opérations atomiques, et constitue la méthode utilisée couramment pour restreindre l'accès à des ressources partagées et synchroniser les processus dans un environnement de programmation concurrente.
Verrous : Permet d'assurer qu'un seul processus accède à une ressource à un instant donné. Un verrou peut être posé pour protéger un accès en lecture et permettra à plusieurs processus de lire, mais aucun d'écrire. On dit alors que c'est un verrou partagé. Un verrou est dit exclusif lorsqu'il interdit toute écriture et toute lecture en dehors du processus qui l'a posé. La granularité d'un verrou constitue l'étendue des éléments qu'il protège. Par exemple dans les bases de données, un verrou peut être posé sur une ligne, un lot de ligne, une table etc.
Spinlocks : Mécanisme simple de synchronisation basé sur l'attente active.
Moniteur : Mécanisme de synchronisation qui permet à plusieurs threads de bénéficier de l'exclusion mutuelle et la possibilités d'attendre (block) l'invalidation d'une condition. Les moniteurs ont également un mécanisme qui permet aux autres threads de signaler que leur condition est validé. Il est constitué d'un mutex et de variables conditionnelles.

La connaissance des dépendances entre les données est fondamentale dans la mise en oeuvre d'algorithmes parallèles, d'autant qu'un calcul peut dépendre de plusieurs calculs préalables. Les conditions de Bernstein permettent de déterminer les conditions sur les données lorsque deux parties de programme peuvent être exécutées en parallèle.

Processus et mécanismes de communication

Signaux

Un signal est une forme de communication entre processus utilisée par les systèmes de type Unix et ceux respectant les standards POSIX. Il s'agit d'une notification asynchrone envoyée à un processus pour lui signaler l'apparition d'un événement. Quand un signal est envoyé à un processus, le système d'exploitation interrompt l'exécution normale de celui-ci. Si le processus possède une routine de traitement pour le signal reçu, il lance son exécution. Dans le cas contraire, il exécute la routine des signaux par défaut.

La norme POSIX (et la documentation de Linux) limite les fonctions directement ou indirectement appelables depuis cette routine de traitements des signaux. Cette norme donne une liste exhaustive de fonctions primitives dites async-signal safe (en pratique les appels systèmes) qui sont les seules à pouvoir être appelées depuis une routine de traitement de signal sans avoir un comportement indéfini. Il est donc suggéré d'avoir une routine de traitement de signal qui positionne simplement un drapeau déclaré volatile sig_atomic_t qui serait testé ailleurs dans le programme.

L'appel système kill(2) permet d'envoyer, si cela est permis, un signal à un processus. La commande kill(1) utilise cet appel système pour faire de même depuis le shell. La fonction raise(3) permet d'envoyer un signal au processus courant.

Les exceptions comme les erreurs de segmentation ou les divisions par zéro génèrent des signaux. Ici les signaux générés seront respectivement SIGSEGV et SIGFPE. Un processus recevant ces signaux se terminera et générera un core dump par défaut.

Le noyau peut générer des signaux pour notifier les processus que quelque chose s'est passé. Par exemple, SIGPIPE est envoyé à un processus qui essaye d'écrire dans un pipe qui a été fermé par celui qui lit. Par défaut, le programme se termine alors. Ce comportement rend la construction de pipeline en shell aisée.

Processus et mécanismes de communication

Socket réseau

Une socket réseau est une structure logicielle comprise dans un noeud réseau qui sert de point d'arrivée pour les données envoyées et reçues à travers le réseau. La structure et les propriétés d'une socket sont définies par une interface de programmation (API) de l'architecture réseau. Les sockets sont créées uniquement durant l'intervalle de temps d'un processus d'une application s'exécutant dans le noeud.

Du fait de la standardisation des protocoles TCP/IP au cours du développement d'Internet, le terme socket réseau est plus communément utilisé dans le contexte de la Suite des protocoles Internets. On parle alors aussi de socket internet. Dans ce contexte, une socket est identifiée extérieurement par les autres machines par son adresse socket, qui est la triade du protocole de transfert, de l'adresse IP et du numéro de port.

Une pile de protocole, habituellement fournie par le système d'exploitation est un ensemble de services permettant aux processus de communiquer à travers un réseau utilisant les protocoles que la pile implémente. Le système d'exploitation fait passer les données utiles des paquets IP entrants à l'application correspondante en lisant l'information de l'adresse socket des entêtes des protocoles IP et transport et en enlevant ces entêtes des données applications.

L'interface de programmation que les programmes utilisent pour communiquer avec la pile de protocole, utilisant les sockets réseaux, est appelée socket API. Les API sockets internet sont généralement basées sur le standard socket de Berkeley. Dans le standard socket de Berkeley, les socket sont une forme de descripteur de fichier (read, write, open, close).

Dans les protocoles internet standards TCP et UDP, une adresse socket est la combinaison d'une adresse IP et d'un numéro de port. Les sockets n'ont pas besoin d'adresse source, mais si un programme lie la socket à une adresse source, la socket peut être utilisée pour recevoir et envoyer des données à cette adresse. Basé sur cette adresse, les sockets internet délivrent les paquets applicatifs entrants au processus applicatif approprié.

Plusieurs types de sockets internet sont disponibles :

Datagram : Des sockets non connectées, qui utilisent le protocole UDP (User Datagram Protocol). Chaque paquet envoyé ou reçu avec un socket datagramme est adressé et routé individuellement. L'ordre ainsi que la fiabilité ne sont pas garantis, par conséquent plusieurs paquets envoyés depuis un processus à un autre peuvent arriver dans n'importe quel ordre ou bien ne pas arriver du tout. Certaines configurations spéciales peuvent être requises pour envoyer en broadcast un socket datagramme.
Stream : Des socket connectés, qui utilisent les protocoles TCP (Transmission Control Protocol), SCTP (Stream Control Transmission Protocol) ou DCCP (Datagram Congestion Control Protocol). Un socket flux fournit un flot de données sans erreurs, séquencé, unique et ininterrompu avec des mécanismes prédéfinis pour créer et détruire des connexions et rapporter des erreurs. Un socket flux transmet des données de manière fiable, ordonnée sans requérir l'établissement préalable d'un canal de communication.
Raw : Permet l'envoie et la réception de paquets IP sans aucun formatage spécifique à un protocole de la couche transport. Avec les autres types de socket, la donnée est automatiquement encapsulée selon le protocole de la couche transport choisi (TCP, UDP etc.), et l'utilisateur du socket n'a pas connaissance de l'existence des entêtes du protocole. Quand on lit d'un socket brut, les entêtes sont généralement inclus. Lorsqu'on transmet des paquets depuis un socket brut, l'addition automatique d'une entête est optionnelle.

Processus et mécanismes de communication

Socket IPC

Un socket de domaine Unix ou socket IPC (inter-process communication) et un point d'arrivée des données de communications qui permet d'échanger des données entre des processus s'exécutant sur le même système d'exploitation hôte. Les types de socket valides dans le domaine UNIX sont :

SOCK_STREAM (à comparer au TCP) - pour un socket orienté flux
SOCK_DGRAM (à comparer à UDP) - pour un socket orienté datagramme qui préserve les limites des messages (comme la plupart des implémentations UNIX, les socket de domaine UNIX datagram sont toujours fiables et ne réordonnent pas les datagrammes)
SOCK_SEQPACKET (à comparer à SCTP) - pour un socket à paquets séquencés orienté connexion, qui préserve les limites des messages, et livre les paquets dans l'ordre d'envoi.

Les sockets de domaine Unix sont une composante standard des systèmes d'exploitation POSIX.

Les interfaces de programmation (API) pour les sockets de domaine Unix sont similaires à celles des sockets internet, mais au lieu d'utiliser un protocole réseau sous-jacent, toutes les communications se placent à l'intérieur du noyau du système d'exploitation. Les socket de domaine Unix peuvent utiliser le système de fichiers comme adresse d'espace de noms. (Certains systèmes d'exploitation, comme Linux, offrent des espaces de noms additionnels.) Les processus référencent les sockets de domaine Unix comme des inodes du système de fichier, ainsi 2 processus peuvent communiquer en ouvrant la même socket.

En plus de permettre l'envoi de données, les processus peuvent envoyer des descripteurs de fichiers à travers une connexion de socket de domaine Unix en utilisant les appels systèmes sendmsg() et recvmsg(). Ceci permet au processus qui envoie d'autoriser le processus qui reçoit à accéder au descripteur de fichier auquel autrement le processus qui reçoit n'a pas accès. Ceci permet d'implémenter une forme rudimentaire de sécurité basée sur l'accessibilité.

Processus et mécanismes de communication

Socket Netlink

La famille de socket Netlink est une interface du noyau Linux utilisée pour des communications inter-processus entre les processus de l'espace utilisateur et du noyau et entre différents processus utilisateurs. La différence entre les sockets Netlink et les socket IPC et qu'au lieu d'utiliser l'espace de noms du système de fichiers, les processus Netlink sont généralement désignés par leurs PIDs.

Netlink fournit une interface socket standard pour les processus utilisateurs, et une API côté noyau pour un usage interne par les modules du noyau.

Processus et mécanismes de communication

Tube anonyme

Un tube anonyme est un mécanisme de gestion de flux de donnée. Ce mécanisme inventé pour Unix est principalement utilisé dans la communication inter-processus. Ouvrir un tube anonyme permet de créer un flux de donnée unidirectionnel FIFO entre un processus et un autre. Ces tubes sont détruits lorsque le processus qui les a créés disparaît.

Ce mécanisme permet la création de filtres.

Pour les système d'exploitation de type Unix, un tube anonyme est créé grâce à un appel système qui retourne un descripteur de fichier à la suite de la création d'un Fork qui permet d'assigner à chacun des processus son rôle de récepteur ou d'émetteur.

Processus et mécanismes de communication

Tube nommé

Un tube nommé est une extension du concept traditionnel de tube des systèmes Unix et Unix-like, c'est l'une des méthode de communication inter-processus (IPC). Un tube traditionnel existe jusqu'à la fin du processus qui l'utilise. Un tube nommé, par contre, peut exister aussi longtemps que le système s'exécute, et dépasser la durée de vie du processus qui l'utilise. Il peut être supprimé s'il n'est plus utilisé. Typiquement, un tube nommé apparait comme un fichier, et généralement des processus s'y attachent pour IPC.

Processus et mécanismes de communication

Passage de messages

Le modèle de passage de messages et une technique permettant de demander l'exécution d'un programme. Le passage de message utilise un modèle objet afin de distinguer la fonction générale de ses implémentations spécifiques. Le programme appelant envoie un message et se fie à l'objet afin de sélectionner et d'exécuter le code approprié. L'utilisation d'une couche intermédiaire, est justifiée par des besoins de distribution et d'encapsulation.

L'encapsulation suit l'idée que les objets logiciels devraient être capables d'invoquer les services d'autres objets sans avoir aucune connaissance spécifique de leurs implémentations. L'encapsulation permet de réduire les lignes de codes ainsi qu'une plus grande maintenabilité des systèmes.

Le passage de messages distribué permet au développeur, à l'aide d'une couche fournissant les services de base de construire des systèmes constitués de sous-systèmes s'exécutant sur des ordinateurs disparates, à différents endroit et à des horaires différents. Lorsqu'un objet distribué envoie un message, la couche message s'occupe de :

Trouver d'où et de quel processus le message est issu.
Sauvegarder le message dans une file si l'objet approprié au traitement du message n'est pas en cours d'exécution et s'occuper de l'envoyer dès que l'objet est disponible. Ainsi que de stocker le résultat si besoin, jusqu'à ce que l'objet qui a envoyé le message est prêt à le recevoir.
Contrôler diverses dépendances transactionnelles pour les transactions distribuées.

Processus et mécanismes de communication

D-Bus

D-Bus est un système de bus de message et un mécanisme de communication inter-processus.

D-Bus fournit à la fois un daemon système et un daemon par-session-de-connexion-utilisateur (pour les IPCs généraux entre applications utilisateurs).

D-Bus permet à des programmes clients de s'enregistrer auprès de lui, afin d'offrir leurs services aux autres programmes. Il leur permet également de savoir quels services sont disponibles. Les programmes peuvent aussi s'enregistrer afin d'être informés d'événements signalés par le noyau, comme le branchement d'un nouveau périphérique.

Gestion de la mémoire centrale

Sous-sections

Gestion de la mémoire centrale

Fichier mappé en mémoire

Un fichier mappé en mémoire est un segment de mémoire virtuelle qui est la copie d'une portion de fichier ou d'une ressource de type fichier. Cette ressource est typiquement un fichier présent sur le disque, mais cela peut également être un périphérique, un objet en mémoire partagée, ou toute autre ressource que le système d'exploitation peut référencer à l'aide d'un descripteur de fichier. Une fois présente en mémoire, cette corrélation entre le fichier et l'espace mémoire permet aux applications de traiter la partie mappée comme s'il s'agissait de la mémoire primaire.

Le bénéfice d'utiliser le mappage en mémoire est d'augmenter les performances d'entrée/sortie notamment sur les fichiers de gros volume. Pour les petits fichiers, les fichiers mappés peuvent engendrer des problèmes de fragmentation interne du fait que les maps mémoires sont toujours aligné sur la taille de la page (généralement 4Ko). Par conséquent, un fichier de 5Ko allouera 8Ko et gâchera 3Ko. Accéder aux fichiers mappés en mémoire est plus rapide que d'utiliser des opérations de lecture et d'écriture directement pour 2 raisons. Premièrement, un appel système est bien plus lent qu'un accès vers la mémoire locale du programme. Deuxièmement, dans la plupart des systèmes d'exploitation la région mémoire mappée est la page cache du noyau, c'est à dire que cela ne nécessite aucune copie en espace utilisateur.

Le processus de mapping mémoire est géré par le gestionnaire de mémoire virtuelle, qui est le même sous-système responsable de la pagination. Les fichiers mappés sont chargés une page entière à la fois. La taille de la page est choisi par le système d'exploitation pour un maximum de performance. Sachant que la pagination est un élément critique du gestionnaire de mémoire virtuelle, le chargement des portions de la taille d'une page d'un fichier en mémoire physique est généralement une fonction système très optimisée.

L'usage le plus commun de fichier mappé en mémoire est le chargement de processus. Lors de la création d'un processus, le système d'exploitation utilise un fichier mappé en mémoire pour faire apparaître le fichier exécutable ainsi que tous les modules chargeable en mémoire pour exécution. La technique la plus utilisée est la demande de pages, le fichier est chargé en mémoire physique par section (chacune d'une page), et seulement quand cette page est référencée. Dans le cas spécifique des exécutables, cela permet à l'OS de charger de manière sélective uniquement les portions de l'image processus qui nécessitent réellement une exécution.

Un autre usage répandu pour les fichiers mappés en mémoire est le partage de fichiers entre processus multiples. Ceci permet d'éviter les fautes de pages ainsi que les violations de segmentation.

Gestion de la mémoire centrale

Mémoire virtuelle

Le principe de mémoire virtuelle repose sur l'utilisation de traduction à la volée des adresses virtuelles vue du logiciel, en adresses physiques de mémoire vive. La mémoire virtuelle permet :

d'utiliser de la mémoire de masse comme extension de la mémoire vive ;
d'augmenter le taux de multiprogrammation ;
de mettre en place des mécanismes de protection de la mémoire ;
de partager la mémoire entre processus.

Gestion de la mémoire centrale

Pagination

Les adresses mémoires émises par le processeur sont des adresses virtuelles, indiquant la position d'un mot dans la mémoire virtuelle. Cette mémoire virtuelle est formée de zones de même taille, appelées pages. Une adresse virtuelle est donc un couple (numéro de page, déplacement dans la page). La taille des pages est une puissance entière de deux, de façon à déterminer sans calcul le déplacement (10 bits de poids faible de l'adresse virtuelle pour des pages de 1024 mots), et le numéro de page (les autres bits). La mémoire vive est également composées de zones de même taille, appelées cadres (frames), dans lesquelles prennent place les pages (un cadre contient une page : taille d'un cadre = taille d'une page). La taille de l'ensemble des cadres en mémoire vive utilisés par un processus est appelé Resident set size. Un mécanisme de traduction (translation) assure la conversion des adresses virtuelles en adresses physiques, en consultant une table des pages (page table) pour connaître le numéro du cadre qui contient la page recherchée. L'adresse physique obtenue est le couple (numéro de cadre, déplacement). Il peut y avoir plus de pages que de cadres (c'est là tout l'intérêt) : les pages qui ne sont pas en mémoire sont stockées sur un autre support (disque), elle seront ramenées dans un cadre quand on en aura besoin.

La table des pages est indexée par le numéro de page. Chaque ligne est appelée "entrée dans la table des pages (pages table entry PTE), et contient le numéro de cadre. La table des pages pouvant être située n'importe où en mémoire, un registre spécial (PTBR pour Page Table Base Register) conserve son adresse.

En pratique, le mécanisme de traduction fait partie d'un circuit électronique appelé MMU (memory management unit) qui contient également une partie de la table des pages, stockée dans une mémoire associative formée de registres rapides. Ceci évite d'avoir à consulter la table des pages (en mémoire) pour chaque accès mémoire.

Gestion de la mémoire centrale

Segmentation

La segmentation est une technique de découpage de la mémoire. Elle est gérée par l'unité de segmentation de l'unité de gestion mémoire (MMU), utilisée sur les systèmes d'exploitation modernes, qui divise la mémoire physique (dans le cas de la segmentation pure) ou la mémoire virtuelle (dans le cas de la segmentation avec pagination) en segments caractérisés par leur adresse de début et leur taille (décalage).

La segmentation permet la séparation des données du programme (entre autres segments) dans des espaces logiquement indépendants facilitant alors la programmation, l'édition de liens et le partage inter-processus. La segmentation permet également d'offrir une plus grande protection grâce au niveau de privilège de chaque segment.

Lorsque l'unité de gestion mémoire (MMU) doit traduire une adresse logique en adresse linéaire, l'unité de segmentation doit dans un premier temps utiliser la première partie de l'adresse, c'est à dire le sélecteur de segment, pour retrouver les caractéristiques du segment (base, limit, DPL, etc.) dans la table de descripteurs (GDT ou LDT). Puis il utilise la valeur de décalage qui référence l'adresse à l'intérieur du segment.

Il existe sur la majorité des processeurs actuels, des registres de segments (CS, DS, SS, etc.) qui contiennent le sélecteur de segment dernièrement utilisé par le processeur qui sont utilisés pour accélérer l'accès à ces sélecteurs.

Sur les processeurs récents, il existe également des registres associés à chaque registre de segment qui contiennent le descripteur de segment associé pour un accès plus rapide aux descripteurs.

Un segment mémoire est un espace d'adressage indépendant défini par deux valeurs :

L'adresse où il commence (aussi appelée base, ou adresse de base)
Sa taille ou son décalage (aussi appelée limite ou offset)

Un segment constitue donc dans la mémoire principale un plage d'adresse continue. Les segments se chevauchent. On peut donc adresser la même zone mémoire avec plusieurs couples segment/offset.

Il existe différents types de segment :

Les segments de données statiques
Les segments de données globales
Les segments de code
Les segments d'état de tâche

Gestion des périphériques

Sous-sections

Gestion des périphériques

Pilotes

Un pilote est un programme qui opère et contrôle un périphérique. Un pilote fournit une interface logicielle au matériel, permettant au système d'exploitation et aux autres programmes d'accéder aux fonctions matérielles sans avoir besoin de connaître en détail le périphérique à utiliser.

Le pilote communique avec le périphérique via le bus informatique auquel celui-ci est connecté. Lorsqu'un programme appelant invoque une routine du pilote, celui-ci va envoyer une commande au périphérique. Une fois que le périphérique renvoie des données au pilote, le pilote peut invoquer des routines du programme à l'origine de l'appel.

Les pilotes sont dépendant du matériel et spécifiques au système d'exploitation. Il fournissent généralement la gestion des interruptions à n'importe quelle interface matérielle asynchrone nécessaire.

Gestion des périphériques

Sysfs

Sysfs est un système de fichiers virtuel qui permet d'exporter depuis l'espace noyau vers l'espace utilisateur des informations sur les périphériques du système et leurs pilotes. Il est également utilisé pour configurer certaines fonctionnalités du noyau.

Pour chaque objet ajouté à l'arbre des modèles de pilotes (pilotes, périphériques, classe de périphériques), un répertoire est créé dans sysfs. La relation parent/enfant est représentée sous la forme de sous-répertoires dans /sys/devices/ (représentant la couche physique). Le sous-répertoire /sys/bus/ est peuplé de liens symboliques, représentant la manière dont chaque périphérique appartient aux différents bus. /sys/class/ montre les périphérique regroupés en classes, comme les périphériques réseau par exemple, pendant que /sys/block/ contient les périphériques de type bloc.

Pour les périphériques et leurs pilotes, des attributs peuvent être créés. Ce sont de simples fichiers, la seule contrainte est qu'ils ne peuvent contenir chacun qu'une seule valeur et/ou n'autoriser le renseignement que d'une valeur (au contraire de certains fichiers de procfs, qui nécessitent d'être longuement parcourus). Ces fichiers sont placés dans le sous-répertoire du pilote correspondant au périphérique. L'utilisation de groupes d'attributs est possible en créant un sous-répertoire peuplé d'attributs.

Sysfs est utilisé par quelques utilitaires pour accéder aux informations concernant le matériel et ses pilotes (des modules du noyau comme udev par exemple). Des scripts ont été écrits pour accéder aux informations obtenues précédemment via procfs, et certains scripts permettent la configuration du matériel et de leur pilote via leurs attributs.

Sysfs s'appuie sur ramfs. Un système de fichiers temporaire très simple monté en RAM.

Gestion des périphériques

Udev

Udev est un gestionnaire de périphérique pour le noyau Linux. Udev gère principalement des noeuds périphériques dans le répertoire /dev/. Udev traite également tous les événements dans l'espace utilisateurs lors de l'ajout ou de la suppression d'un périphérique, ainsi que du chargement des microgiciels.

Les pilotes font parti du noyau Linux, dans le sens où leurs fonctions principales incluent la découverte de périphérique, la détection des changements d'états, et autres fonctions matérielles similaires de bas niveau. Après chargement du pilote de périphérique en mémoire depuis le noyau, les événements détectés sont envoyés au daemon de l'espace utilisateur udevd. C'est le gestionnaire de périphérique, udevd, qui récupère tout ces événements et qui ensuite décide de la suite à donner. A cette fin, udevd dispose d'un ensemble de fichiers de configurations, pouvant être ajustés par l'administrateur suivant ses besoins.

Dans le cas d'un nouvel appareil de stockage USB, udevd est notifié par le noyau qui lui-même notifie le udisksd-daemon. Ce daemon pourra alors monter le système de fichiers.
Dans le cas d'une nouvelle connexion de câble Ethernet à la carte d'interface réseau Ethernet (NIC), udevd est notifié par le noyau qui lui-même notifie le NetworkManager-daemon. Le NetworkManager-daemon pourra alors démarrer le daemon client dhcp pour cette NIC, ou bien configurer la connexion à l'aide d'une configuration manuelle quelconque.

Contrairement aux systèmes traditionnels UNIX, ou les noeuds périphériques contenus dans le répertoire /dev était un ensemble de fichiers statique, le gestionnaire de périphérique Linux udev fournit dynamiquement, uniquement les noeuds des périphériques actuellement disponibles au système :

udev fournit un nommage de périphérique persistant, qui ne dépend pas de, par exemple, l'ordre de connexion des appareils au système.
udev s'exécute entièrement en espace utilisateur. Une conséquence est que udev peut exécuter des programmes arbitraires pour composer un nom pour le périphérique fonction de ses propriétés, avant que le noeud soit créé; d'ailleurs, l'ensemble du processus de nommage est également interruptible et s'exécute avec une priorité basse.

Udev est divisé en trois parties :

La bibliothèque libudev qui permet l'accès aux informations des périphériques; qui est maintenant inclue dans systemd.
Le daemon de l'espace utilisateur udevd qui gère /dev virtuel.
L'utilitaire d'administration en ligne de commande udevadm pour des diagnostics.

Le système reçoit des appels depuis le noyau via des sockets Netlink.

Gestion des périphériques

Bus

Un bus est un système de communication qui permet de transférer des données entre les composants d'un ordinateur ou entre ordinateurs. Cette expression couvre tous les composants matériels (fils, fibre optique, etc.) et logiciels, protocoles de communications inclus. Les bus informatiques modernes peuvent à la fois utiliser des connexions parallèles et séries avec hubs. C'est par exemple le cas de l'USB.

Un bus d'adresses est un bus utilisé pour spécifier une adresse physique. Quand un processeur ou un périphérique bénéficiant d'un accès direct à la mémoire (DMA-enabled) a besoin de lire ou d'écrire en mémoire, il spécifie en emplacement mémoire sur le bus d'adresses (la valeur à lire ou à écrire est alors envoyé sur le bus de données). La largeur du bus d'adresse détermine la quantité de mémoire qu'un système peut adresser.

Accéder un octet individuel requiert généralement d'écrire ou de lire une largeur de bus complète (un mot) à la fois. Dans ce cas, les bits les moins signifiants du bus d'adresses peuvent même ne pas être implémentés - il revient en effet au contrôleur d'isoler l'octet individuel demandé du mot complet transmis.

Gestion des périphériques

Accès direct à la mémoire

L'accès direct à la mémoire (DMA) est un procédé informatique où les données circulant de, ou vers un périphérique sont transférées directement par un contrôleur adapté vers la mémoire principale, sans intervention du microprocesseur si ce n'est pour lancer et conclure le transfert. La conclusion du transfert ou la disponibilité du périphérique peuvent être signalés par interruption.

Éléments de démarrage

Sous-sections

BIOS
UEFI
Partitionnement de la mémoire
MBR
GPT
LVM
RAID
Dm-crypt
LUKS
Chargeur d'amorçage
Initramfs
Noyau
Talon de démarrage UEFI et Image noyau unifiée
Cgroups
Espaces de noms
Systemd
getty
shell

Éléments de démarrage

BIOS

Le BIOS est un microgiciel utilisé pour l'initialisation du matériel pendant le processus de démarrage, et pour fournir des services à l'exécution pour les systèmes d'exploitation et les programmes. Le microgiciel BIOS est préinstallé sur la carte mère, c'est le premier logiciel à s'exécuter lors de la mise sous tension.

Le BIOS dans les PCs modernes initialise et teste les composants matériels du système, et charge un chargeur d'amorçage depuis l'appareil de stockage de masse qui initialise un système d'exploitation.

La plupart des implémentations du BIOS sont spécifiques à un modèle de carte mère, en s'interfaçant avec différents appareil et en particulier le chipset. Anciennement, le microgiciel BIOS était stocké sur une puce ROM de la carte mère. De nos jours, le contenu du BIOS est stocké sur de la mémoire flash de façon à pouvoir être réécrite sans enlever la puce de la carte mère. Ceci permet une mise à jour aisée du BIOS, mais également l'infection de l'ordinateur via des rootkits du BIOS. De plus, si une mise à jour du BIOS échoue cela peut potentiellement rendre la carte mère inutilisable.

L'interface microgicielle extensible unifiée (UEFI) est un successeur du BIOS, il vise à résoudre ses limitations techniques.

Éléments de démarrage

UEFI

L'interface microgicielle extensible unifiée (UEFI) est une spécification qui définit une interface logicielle entre un système d'exploitation et une plateforme microgicielle. UEFI remplace l'ancienne interface microgicielle BIOS dont elle reprend généralement l'ensemble des services. L'UEFI peut supporter les diagnostics et réparations distants, même sans système d'exploitation.

L'interface défini par la spécification EFI inclut des tables de données qui contiennent des informations de plateforme, ainsi que des services de démarrage et d'exécution disponible au chargeur d'amorçage et au système d'exploitation. Le microgiciel UEFI fournit un certain nombre d'avantages techniques par rapport à un système BIOS traditionnel :

La possibilité de démarrer un disque contenant de grandes partitions (plus de 2TB) à l'aide d'une table de partition GUID (GPT)
Un environnement pre-SE flexible, incluant des capacités réseaux, une interface graphique utilisateur, le multi-langage
Un environnement pre-SE 32 ou 64 bits.
Une programmation en langage C
Une architecture modulaire
Une compatibilité

Contrairement au BIOS, UEFI ne s'appuie pas sur des secteurs de démarrage, il définit un gestionnaire de démarrage comme faisant parti des spécifications UEFI. Quand l'ordinateur est allumé, le gestionnaire de démarrage vérifie la configuration de démarrage et en fonction de ses paramètres, exécute ensuite le chargeur d'amorçage spécifié ou noyau de système d'exploitation (généralement chargeur d'amorçage). La configuration de démarrage est définie par des variables stockées en NVRAM, incluant des variables qui indiquent les chemins du système de fichier vers les chargeurs d'amorçages ou noyaux.

Les chargeurs d'amorçage peuvent également être détectés automatiquement par UEFI grâce à des chemins standardisés contenant des fichiers au format .efi.

La spécification UEFI spécifie que les exécutables portables (PE) de Microsoft sont le format d'exécutable standard dans les environnements EFI.

Éléments de démarrage

Partitionnement de la mémoire

Le partitionnement de la mémoire est la création d'une ou plusieurs régions dans la mémoire secondaire, telle que chaque région puisse être gérée séparément. Ces régions sont appelées partitions. C'est généralement la première chose à faire sur un nouveau disque installé, avant qu'un système de fichier soit créé. Le disque stocke l'information sur le positionnement et la taille des partitions dans une aire appelée table de partition que le système d'exploitation lit avant toute autre région du disque. Chaque partition apparait alors comme un disque "logique" du point de vue du système d'exploitation qui fait usage d'une partie du disque réel. Les administrateurs systèmes utilisent alors un programme appelé éditeur de partitions pour créer, retailler, supprimer et manipuler les partitions. Le partitionnement permet l'usage de différents systèmes de fichiers afin de stocker tout types de fichiers. Séparer les données utilisateur des données système permet d'empêcher que la partition système soit pleine ce qui rendrait le système inutilisable. Le partitionnement permet aussi de simplifier la sauvegarde. Un désavantage du partitionnement est qu'il peut être difficile d'allouer la taille adéquate à chacune des partitions, ce qui peut avoir pour conséquence de laisser une partition avec énormément d'espace libre et une autre totalement saturée.

Éléments de démarrage

MBR

Un enregistrement de démarrage maître (MBR) est type spécial de secteur de démarrage situé au commencement d'un périphérique de stockage informatique partitionné tel qu'un disque dur.

Le MBR contient l'information du comment les partitions logiques, contenant le système de fichiers, sont organisées sur ce périphérique. Le MBR contient également du code exécutable pour fonctionner comme chargeur pour un système d'exploitation installé généralement en laissant la main au second étage du chargeur, ou en conjonction avec chacun des enregistrements de démarrage de volume (VBR). Ce code MBR est généralement désigné comme un chargeur d'amorçage.

L'organisation de la table de partition au niveau du MBR limite le maximum d'espace de stockage adressable d'un disque partitionné à 2To. Par conséquent, le schema de partitionnement MBR est progressivement remplacé par le schema de table de partitionnement GUID (GPT).

Le MBR consiste généralement à 512 octets situés sur le premier secteur du disque.

Il peut contenir un(e) ou plusieurs :

Table de partition décrivant les partitions sur un périphérique de stockage. Dans ce contexte, le secteur de démarrage peut également être appelé secteur de partitionnement.
Code de bootstrap : Instructions permettant d'identifier la partition de démarrage configurée, puis charge et exécute son volume d'enregistrement de démarrage (VBR) en tant que chargeur chaîné.
Horodatage disque 32-bits optionnel
Signature disque 32-bits optionnel

Éléments de démarrage

GPT

La table de partition GUID (GPT) est un standard pour la disposition de tables de partitions sur un appareil de stockage informatique, tels que les disques durs ou les SSDs, en utilisant des identifiants uniques universels, aussi connus en tant qu'identifiants uniques globaux (GUIDs). Ce standard fait parti des standards d'interface microgicielle extensible unifiée (UEFI), il peut néanmoins être utilisé pour des systèmes BIOS, du fait des limitations des tables de partitions MBR.

Tous les systèmes d'exploitation récents supportent GPT.

De la même façon que MBR, GPT utilise un adressage de blocs logique (LBA) à la place de l'adressage historique cylindre-tête-secteur (CHS). Le MBR est stocké au niveau de LBA 0, l'entête GPT à LBA 1. L'entête GPT contient un pointeur vers la table de partition (typiquement situé à LBA 2). Chaque entrée dans la table de partition a une taille de 128 octets. Les spécifications UEFI stipulent qu'un minimum de 16 384 octets, soit attribué à la table de partition. Ainsi, sur un disque avec des secteurs de 512 octets, au moins 32 secteurs sont utilisés pour la table de partition, et le premier bloc utilisable est le LBA 34 ou supérieur.

Éléments de démarrage

LVM

La gestion de volumes logiques (LVM) utilise la fonctionnalité du composant device-mapper du noyau linux pour fournir un système de partitions indépendant de l'arrangement des disques sous-jacents. Avec LVM on obtient des partitions virtuelles. Cette abstraction facilite la gestion des volumes de stockage (potentiellement toujours sujette aux limitations du système de fichier).

Ces partitions virtuelles permettent l'ajout et la suppression sans avoir à ce soucier si l'espace contigu est suffisant sur un disque en particulier, sans se faire avoir en essayant de formater un disque en cours d'utilisation (et se demander si le noyau utilise l'ancienne ou la nouvelle table de partition), ou , avoir à déplacer des partitions pour en agrandir une.

Les composants basiques de LVM sont les :

Volumes physiques (PV) : Un noeud de périphérique de bloc Unix, utilisable pour du stockage par LVM. Il accueille une entête LVM.
Groupes de volumes (VG) : Groupe de volumes physiques (PVs) qui sert de contenant aux volumes logiques (LVs). Les extensions physiques (PEs) sont allouées depuis un groupe de volume (VG) pour un volume logique (LV).
Volumes Logiques (LV) : "Partition virtuelle/logique" résidant dans un groupe de volume (VG) et composé d'extensions physiques (PEs). Les Volumes logiques (LVs) sont des périphériques de blocs Unix analogues à des partitions physiques, c'est à dire qu'elles peuvent être directement formatées à l'aide d'un système de fichier.
Extentions physiques (PE) : La plus petite extension contigüe (par défaut 4MiB) dans le volume physique (PV) qui peut être assigné à un volume logique (LV).

LVM permet une plus grande flexibilité comparé à l'utilisation d'une partition de disque dur classique :

Utiliser plusieurs disques comme un seul gros disque.
Avoir des volumes logiques étendus sur plusieurs disques.
Créer de petits volumes logiques et les retailler "dynamiquement" quand ils se remplissent.
Redimensionner des volumes logiques quelque soit leur ordre sur le disque.
Capturer une sauvegarde d'une copie gelée du système de fichier, en gardant une forte disponibilité.
Supporter différentes cibles de device-mapper, incluant le chiffrement de systèmes de fichier transparent et la mise en cache de données fréquemment utilisées. Ceci permet de créer un système avec un ou plusieurs disques physiques (chiffrés avec LUKS) et LVM par dessus pour permettre de redimensionner et de gérer les volumes séparés sans avoir à entrer une clef de nombreuses fois au démarrage.

Les désavantages étant :

Des étapes supplémentaire lors de l'installation du système. Nécessite l'exécution d'un certain nombre de daemons.
Le dual booting avec des SE ne supportant pas LVM (Windows).
Dans le cas de volumes physique qui ne sont pas en RAID-1, RAID-5 ou RAID-6 perdre un disque peut signifier perdre un ou plusieurs volumes logiques si on étale (ou étend) des volumes logiques sur un ensemble de disques non redondants.

Éléments de démarrage

RAID

RAID est une technologie de stockage qui combine plusieurs composants de disques durs (typiquement des disques durs ou leurs partitions) en une unité logique. Selon l'implémentation du RAID, cette unité logique peut être un système de fichier ou une couche transparente additionnelle qui détient plusieurs partitions. Les données sont distribuées sur les disques d'une ou plusieurs manières appelés niveaux de RAID. Le niveau de RAID choisit peut ainsi empêcher des pertes de données dans le cas d'une perte de disque dur, améliorer la performance ou une combinaison des deux.

Il existe de nombreux niveaux de RAID différents ; ceux listés ci-dessous sont les plus communs :

RAID 0 : Entrelacement de disques. Augmente la vitesse de lecture et d'écriture sans redondance.
RAID 1 : Disques en miroir.
RAID 5 : Nécessite au minimum 3 disques et combine la redondance du RAID 1 et les bénéfices de vitesse du RAID 0.
RAID 6 : Nécessite au minimum 4 disques fournit les bénéfices du RAID 5 mais avec la sécurité contre la perte de deux disques.
RAID 1+0 : RAID imbriqué qui combine deux niveaux standards du RAID pour gagner en performance et redondance additionnelle.

Les périphériques de RAID peuvent être gérés de plusieurs façons :

RAID Logiciel : La grappe est gérée par le système d'exploitation soit par :
- Une couche d'abstraction (mdadm);
- Un gestionnaire de volume logique (LVM);
- Un composant du système de fichier (ZFS, Btrfs);
RAID Matériel : La grappe est directement gérée par une carte matérielle dédiée installée dans le PC auxquels les disques sont directement connectés. La logique RAID s'exécute sur un processeur embarqué indépendamment du processeur hôte (CPU). Bien que cette solution soit indépendante du système d'exploitation, cette dernière nécessite un pilote pour fonctionner correctement avec le contrôleur de RAID matériel. La grappe de RAID peut soit être configurée via une interface microgicielle ou, selon le fabricant, à l'aide d'application dédiées après installation du système d'exploitation. La configuration est transparente pour le noyau Linux : il ne voit pas les disques séparément.
FakeRAID : Ce type de raid est correctement appelé RAID microgiciel. La grappe est gérée par un pseudo contrôleur RAID où la logique RAID est implémentée dans une partie microgicielle , mais sans toutes les capacité des contrôleurs RAID matériels.

Éléments de démarrage

Dm-crypt

Dm-crypt est la cible cryptographique du device-mapper. Il s'agit d'un sous-système de chiffrement de disque transparent du noyau Linux. Il est implémenté en tant que cible du device-mapper et peut être emplilé sur d'autres transformations de celui-ci. Il peut ainsi chiffrer des disques, des partitions, des volumes logiciels de RAID, des volumes logiques, ainsi que des fichiers. Il apparaît comme un périphérique de bloc, qui peut être utilisé pour supporter des systèmes de fichiers, du swap ou un volume physique LVM.

Éléments de démarrage

LUKS

LUKS est une spécification de chiffrement de disque. LUKS implémente un format sur disque standard indépendant pour l'utilisation de divers outils. Cela permet une compatibilité et une interopérabilité parmi différents programmes, mais s'assure également qu'ils implémentent une gestion des mots de passe sécurisée et documentée.

LUKS utilise dm-crypt comme backend pour le chiffrement de disque.

Éléments de démarrage

Chargeur d'amorçage

Un chargeur d'amorçage est un logiciel démarré par le microgiciel (BIOS ou UEFI). Il est responsable du chargement du noyau avec les paramètres recommandés et du disque RAM initial (initrd) selon des fichiers de configuration. Dans le cas de l'UEFI, le noyau lui-même peut directement être lancé par l'EFI boot stub qui permet au microgiciel EFI un chargement du noyau en tant qu'exécutable EFI. Un chargeur d'amorçage séparé ou gestionnaire de démarrage peut toujours être utilisé afin d'éditer les paramètres du noyau avant le démarrage.

Un chargeur d'amorçage doit pouvoir accéder au images du noyau et de l'initramfs, autrement le système ne pourra pas démarrer. Par conséquent, il doit typiquement pouvoir accéder à /boot. C'est à dire, qu'il doit pouvoir supporter un ensemble allant des périphériques de blocs, aux périphériques de blocs empilés (LVM, RAID, dm-crypt; LUKS, etc.) jusqu'au système de fichier sur lequel réside les images du(des) noyau(x) et de(des) initramfs.

Le chargement du disque RAM initial peut également inclure un microcode processeur du fabricant qui fournit des mises à jours de sécurité et de stabilité.

Les mises à jour du microcode sont généralement incluses dans le microgiciel de la carte mère et appliquées durant l'initialisation du microgiciel. Du fait que les fabricants des équipements d'origine ne mettaient pas forcément à jour leur microgiciel de manière régulière et que les vieux système ne bénéficiaient d'aucune mise à jour, la possibilité d'appliquer ses mises à jour du microcode processeur a été ajouté au moment du démarrage pour le noyau Linux.

Éléments de démarrage

Initramfs

Une fois que le chargeur d'amorçage a chargé le noyau et les possibles fichiers initramfs et exécute le noyau, le noyau extrait l'initramfs (système de fichier RAM initial) dans le rootfs (système de fichier racine initial, spécifiquement un ramfs ou tmpfs) qui était vide jusqu'alors. La premier initramfs extrait a été inclus dans le binaire du noyau lors de la construction de celui-ci, ensuite de possibles fichiers initramfs externes sont extraits. Par conséquent les initramfs externes surchargent des fichiers portant le même nom dans l'initramfs inclus. Le noyau execute alors init (dans le rootfs) en tant que premier processus. Les prémisses de l'espace utilisateur démarrent.

Les images externes initramfs peuvent être générées à l'aide de mkinitcpio, dracut ou booster.

Le but de l'initramfs est d'amener le système jusqu'au point où il accède au système de fichier racine. Cela signifie que tout module requis pour des périphériques tels qu'IDE, SCSI, SATA, USB/FW (si démarrage depuis un disque externe) doit pouvoir être chargé depuis l'initramfs si il n'est pas inclus dans le noyau ; une fois que les modules sont chargés (soit explicitement via un programme ou un script, ou implicitement via udev), le processus de démarrage continue. Pour cette raison, l'initramfs a uniquement besoin des modules nécessaires à l'accès au système de fichier racine. La majorité des modules sera chargé à postériori par udev, durant le processus d'init (systemd).

Éléments de démarrage

Noyau

Le noyau est un programme informatique au cœur d'un système d'exploitation informatique et a un contrôle complet sur l'ensemble du système. Il s'agit de la partie du code du système d'exploitation qui réside en permanence en mémoire, et facilite les interactions entre composants matériels et logiciels. Un noyau complet contrôle l'ensemble des ressources matérielles (ex. E/S, mémoire, cryptographie) via des pilotes, arbitre les conflit entre processus a propos de ces ressources, et optimise l'utilisation des ressources communes ex. CPU & utilisation des caches, systèmes de fichiers, et sockets réseaux. Sur la majorité des systèmes, le noyau est le premier programme chargé au démarrage (après le chargeur d'amorçage). Il gère le reste du processus de démarrage ainsi que la mémoire, les périphériques, les requêtes d'entrées/sorties (E/S) du logiciel, en les traduisant en instructions de traitements de données pour le processeur.

Le code critique du noyau est généralement chargé dans une aire de la mémoire séparée, qui est protégée des accès via les applications logicielles ou d'autres parties moins critiques d'un système d'exploitation. Le noyau effectue des tâches telles que, l'exécution de processus, la gestions de périphériques matériels tels que le disque dur, et la gestion des interruptions, dans l'espace noyau protégé. Par contraste, des programmes applicatifs tels que des navigateurs, des traitements de texte, ou des lecteurs audio ou vidéo utilisent une aire séparée de la mémoire, l'espace utilisateur. Cette séparation empêche les données utilisateurs et les données noyau d'interférer l'une avec l'autre causant instabilité et lenteurs, empêchant également des applications défectueuses d'affecter d'autres applications ou même le système d'exploitation dans son ensemble.

L'interface noyau est une couche d'abstraction de bas niveau. Quand un processus demande un service au noyau, il doit invoquer un appel système, généralement à travers une fonction englobante.

Il existe différentes architectures de noyau. Les noyaux monolithiques s'exécutent entièrement dans un espace d'adressage unique avec le processeur en mode supervision, principalement pour des questions de rapidité. Les micro-noyaux exécutent la plupart de leurs services dans l'espace utilisateur, de la même manière que les processus utilisateurs, principalement pour des considérations de résilience et de modularité. Le noyau Linux est monolithique, bien qu'également modulaire, puisqu'il peut insérer et supprimer des module noyaux chargeable à l'exécution.

Éléments de démarrage

Talon de démarrage UEFI et Image noyau unifiée

Une image noyau unifiée (UKI) est un exécutable unique qui peut être démarré directement depuis le microgiciel UEFI, ou sourcé automatiquement par les chargeurs d'amorçage avec une configuration légère voire inexistante.

Une image unifiée permet d'inclure :

un talon de démarrage UEFI tel que systemd-stub,
une image noyau,
une image initramfs,
l'interface ligne de commande du noyau,
optionnellement, un écran de démarrage.

Grâce au talon, l'exécutable résultant, et par conséquent tous ses éléments, peuvent être facilement signés afin d'utiliser la fonctionnalité de démarrage sécurisé UEFI (Secure Boot).

Éléments de démarrage

Cgroups

Les cgroups sont une fonctionnalité du noyau Linux qui limite, compte et isole l'utilisation des ressources (CPU, mémoire, entrée/sortie, réseau, etc.) d'une collection de processus.

Ces groupes de contrôle peuvent être utilisés de multiples façons :

En accédant le système de fichier virtuel du cgroup manuellement.
En créant et gérant des groupes à la volée en utilisant des outils tels que cgcreate, cgexec et cgclassify (libcgroup).
A travers le "daemon moteur de règles" qui peut déplacer les processus de certains utilisateurs, groupes de manière automatique ou commander aux cgroups comme cela a été spécifié dans sa configuration.
Indirectement à travers d'autres logiciels utilisant les cgroups, tels que Docker, LXC, libvirt, systemd, etc.

Éléments de démarrage

Espaces de noms

Un espace de noms encapsule dans une abstraction une ressource système globale qui la fait apparaître aux processus contenus dans l'espace de noms qui ont leur propre instance isolée de la ressource globale. Les changements de la ressource globale sont visibles aux autres processus membre de l'espace de noms, mais invisible aux autres processus. Les espaces de noms sont utilisés pour implémenter les conteneurs.

Les types d'espace de noms disponibles dans Linux sont les suivants : Cgroup, IPC, Network, mount, PID, Time, User, UTS.

Éléments de démarrage

Systemd

Systemd est un système et un gestionnaire de service pour les systèmes d'exploitation Linux. Lorsqu'il est exécuté en tant que premier processus au démarrage, il agit comme le système init et met en place et gère les services de l'espace utilisateur. Des instances séparées sont démarrées pour les utilisateurs connectés afin de démarrer leurs services.

D'habitude, systemd n'est pas invoqué directement par l'utilisateur, mais est installé comme le lien symbolique /sbin/init et lancé au début du démarrage.

Lorsqu'il est exécuté en tant qu'instance système, systemd interprète le fichier de configuration system.conf et les fichiers présents dans les répertoires de system.conf.d ; lorsque lancé en tant qu'instance utilisateur, systemd interprète le fichier de configuration user.conf et les fichiers dans les répertoires user.conf.d

Systemd fournit un système de dépendances entre des entités variées appelées "unités" de 11 types différents. Les unités encapsulent des objets utiles pour le démarrage et la gestion du système. La grande majorité des unités sont configurées dans des fichiers de configuration d'unité, néanmoins certaines peuvent être créées automatiquement depuis d'autres configurations, dynamiquement d'un état système ou de façon programmée à l'exécution. Une unité peut être "active" (i.e. démarrée, liée, connectée, etc. selon le type d'unité), ou "inactive" (i.e. stoppée, déliée, déconnectée, etc.) ou bien dans le processus d'activation ou de désactivation, c'est à dire entre les deux états. Un état spécial "échoué" est également disponible, très similaire à "inactive" il se déclenche lorsque le service a échoué d'une certaine façon (le processus a renvoyé un code d'erreur, ou a crashé, une opération a time out, ou après un nombre trop important de redémarrages). Si l'état apparaît, la cause sera tracée pour référence ultérieure. Il est à noté que plusieurs types d'unité peuvent avoir un nombre de sous-états additionnels, qui sont reliés aux 5 états d'unité généraux décrits ici.

Les unités suivantes sont disponibles :

Les unités de services, qui démarrent et contrôlent des daemons et les processus qui les composent.
Les unités de sockets, qui encapsulent des IPC locaux ou des sockets réseaux du système, utiles pour l'activation basée sur des sockets.
Les unités de cibles utilisées afin de grouper des unités, ou de fournir des points de synchronisation connus au démarrage.
Les unités de périphériques qui expose les périphériques de noyau dans systemd et peuvent être utilisées pour de l'activation basée sur des périphériques.
Les unités de montages, pour contrôler les points de montage dans le système de fichiers.
Les unités de montages automatiques, afin d'automatiser les opérations de montage à la demande et le démarrage parallélisé.
Les unités de timers afin de déclencher l'activation d'autres unités sur la base de timers.
Les unités de swap, très similaires aux unités de montages qui encapsulent les partitions mémoires dédiées au swap ou des fichiers du système d'exploitation.
Les unités de chemins qui peuvent être utilisées afin d'activer d'autres service lorsque les objets du système de fichiers changent ou sont modifiés.
Les unités de tranches qui sont utilisées afin de grouper des unités qui gèrent des processus systèmes dans un arbre hiérarchique pour des questions de gestion des ressources.
Les unités de scope similaires aux unités de services mais pour gérer et démarrer des processus externes. Ils sont créés de façon programmée en utilisant les interfaces de bus de systemd.

Units : service, socket, target, device, mount, automount, timer, swap, path, slice, scope

Systemd chargera implicitement et automatiquement les unités depuis le disque - si celles-ci ne sont pas déjà chargées - dès qu'elles seront requises par des opérations. Ainsi, le fait qu'une unité est chargée ou non est invisible aux clients. On utilise `systemctl list-units --all pour lister de manière compréhensive les unités actuellement chargées. N'importe quelle unité pour laquelle aucune de conditions ci-dessus ne s'applique est rapidement déchargée. Il est à noter que quand une unité est déchargée de la mémoire courante ses données sont également libérées. Néanmoins les données ne sont généralement pas perdues, du fait qu'un enregistrement dans le journal de log est généré déclarant les ressources consommées à l'arrêt d'une unité.

Les processus lancés par systemd sont placés dans des cgroups nommés d'après l'unité à laquelle ils appartiennent dans la hiérarchie privée de systemd. systemd fait usage de cela afin de garder efficacement la trace des processus. L'information du Control group est gérée par le noyau, et est accessible dans la hiérarchie du système de fichier (sous /sys/fs/cgroup/systemd/), ou bien dans des outils tels que systemd-cgls.

Systemd contient un système transactionnel minimal : si une unité doit s'activer ou se désactiver, il l'ajoutera avec toutes ses dépendances dans une transaction temporaire. Il vérifiera alors si la transaction est cohérente (i.e. si l'ordonnancement de toutes les unités ne contient pas de boucle). Si ce n'est pas le cas, systemd essaiera de résoudre le problème, et supprimera les jobs non essentiels de la transaction ce qui pourra faire disparaître la boucle. Systemd essaiera également de supprimer les jobs non essentiels qui arrêteraient un service déjà actif. Enfin il vérifiera si les jobs de la transaction contredisent des jobs déjà en attente dans la file et optionnellement annulera la transaction. Si tout a marché et que la transaction est cohérente et minimale dans son impact, elle est fusionnée avec tous les jobs en attente dans la file d'exécution. Cela signifie qu'avant l'exécution d'une opération demandée, systemd vérifiera en premier lieu qu'elle ait un sens, essaiera de résoudre si possible, et échouera uniquement s'il n'est pas possible de la faire fonctionner.

Il est à noter que les transactions sont générées indépendamment de l'état des unités à l'exécution, ce qui a pour conséquence par exemple que si un job de démarrage est requis sur une unité déjà active, il génèrera quand même une transaction et réveillera toute dépendance inactive (et causera par propagation la demande d'autres jobs tels que définis par leurs relations). Ceci du fait que le job enfilé est comparé à l'exécution à l'état de l'unité cible et est marqué comme réussi et complet quand les deux sont satisfaits. Cependant ce job ressort également les autres dépendances du fait de la relation définie et mène donc, dans notre exemple, à l'enfilage des jobs de démarrage de toutes ces unités inactives.

Systemd contient des implémentation natives de tâches diverses faisant parti du processus de démarrage et ayant besoins d'être exécutées. Par exemple, il fixe le nom de l'hôte ou configure le périphérique réseau de loopback. Il sert également à mettre en place et monter plusieurs systèmes de fichiers d'API, tels que /sys/ ou /proc/.

Éléments de démarrage

Getty

Un getty est un nom générique pour un programme qui gère une ligne de terminal et son terminal connecté. Son objectif est de protéger le système d'accès non autorisés. Généralement, chaque processus getty est démarré par systemd et gère une ligne de terminal unique. Typiquement il gére également un certain nombre de consoles virtuelles.

Éléments de démarrage

Shell

Le Shell est un programme qui permet d'interpréter les commandes de l'utilisateur. C'est l'un des tout premiers moyens d'interagir avec un ordinateur. Le shell est généralement plus puissant qu'une interface graphique utilisateur (GUI), dans le sens où il permet d'accéder très efficacement aux fonctionnalités internes du système d'exploitation (OS).

Souvent les outils textuels dont il dispose sont construits de manière à pouvoir être composés. Ainsi de multiples assemblages permettent à la fois une simplicité dans la décomposition des tâches, et une facilité de mise en oeuvre dans l'automatisation.

Les shells peuvent généralement dépendre des OS, sachant qu'il en existe une quantité pour chacun d'entre eux.

Éléments de sécurité

Sous-sections

Éléments de sécurité

Secure Shell

Secure Shell (SSH) est un protocole réseau cryptographique pour opérer des services réseaux de manière sécurisé à travers un réseau non sécurisé. Les application typiques incluent la connexion distante en ligne de commande et l'exécution de commandes distantes, mais n'importe quel service réseau peut être sécurisé via SSH.

Un serveur SSH, écoute par défaut sur le port 22 TCP. Un programme client SSH est généralement utilisé pour établir la connexion vers un daemon sshd qui accepte les connexions distantes.

Éléments de sécurité

OpenSSH

OpenSSH (OpenBSD Secure Shell) est un ensemble de programmes informatiques fournissant des sessions de communications chiffrées à travers un réseau en utilisant le protocole Secure Shell. Il a été créé en tant qu'alternative open source à la suite logicielle propriétaire Secure Shell offerte par SSH Communications Security.

On utilise généralement la suite d'outils OpenSSH suivante :

ssh-keygen pour générer une paire clef publique/clef privée.
ssh-add pour ajouter les identités de clefs privées à l'agent d'authentification ssh-agent.
ssh-agent en tant que service gestionnaire de clefs.
ssh en tant que client du protocole.
sshd en tant que serveur du protocole.

Éléments de sécurité

Netfilter

Netfilter est un framework fournit par le noyau Linux et qui permet diverses opérations en lien avec le réseau pouvant être implémentées sous la forme de gestionnaires configurables. Netfilter offre plusieurs fonctions et opérations pour le filtrage des paquets, la traduction d'adresses et de ports réseaux, ce qui fournit la fonctionnalité requise pour diriger les paquets à travers le réseau et d'interdire à certains l'accès aux lieux sensibles d'un réseau.

Netfilter présente un ensemble de hooks à l'intérieur du noyau Linux, permettant à des modules du noyau spécifiques d'enregistrer des fonctions de rappel avec la pile réseau du noyau. Ces fonctions s'appliquent généralement au traffic sous forme de règles de modification et de filtrage qui sont appelées pour chaque paquet qui traverse le hook respectif dans la pile réseau.

Nftables est un sous-système du noyau Linux et la nouvelle partie de Netfilter qui fournit la classification et le filtrage des paquets réseaux. Elles sont disponibles depuis le noyau Linux 3.13. Nftables se substitue aux iptables, elles présentent les avantages d'une moindre réplication du code et d'une plus grande simplicité d'extension pour de nouveaux protocoles. Nftables est configuré via l'utilitaire d'espace utilisateur nft.

Nftables utilise les blocs de construction de l'infrastructure Netfilter, tels que les hooks existant dans la pile réseau, la connexion au système de traçage, le composant d'enfilage de l'espace utilisateur, et le sous-système de logs.

Le moteur du noyau nftables ajoute une machine virtuelle simpliste au noyau Linux, capable d'exécuter un bytecode pour inspecter un paquet réseau et prendre les décisions concernant la gestion de ce paquet. Elle peut obtenir des données de la part du paquet lui-même, regarder les méta données associées (par exemple l'interface d'entrée), et gérer les données de traçage de connexions. Les opérateurs de comparaison arithmétiques et bits à bits peuvent être utilisés pour prendre des décisions en fonction de ces données. La machine virtuelle est aussi capable de réaliser des manipulations sur des ensembles de données (typiquement des adresses IP), en permettant de remplacer de multiples opérations de comparaisons par un ensemble d'inspections.

Nftables offre une API améliorée côté espace utilisateur qui permet des remplacements atomiques d'une ou plusieurs règles pare-feu dans une seule transaction Netlink. Ceci accélère les changements de configuration pare-feu pour les installations ayant de grands ensembles de règles ; cela peut également permettre d'éviter des situations de compétition durant le changement de règle.

Éléments de sécurité

BPF et eBPF

Le filtre de paquet BSD (BPF) est une architecture de capture de paquets en espace utilisateur. Celle-ci repose sur une machine virtuelle à registre qui fonctionne dans le noyau et permet d'évaluer les règles de filtrage sans recopies des paquets. Ce mécanisme est utilisé par des outils standards comme tcpdump pour sélectionner les paquets à capturer.

Récemment ce mécanisme à évolué vers une version étendue (eBPF) qui est la version moderne d'architecture utilisée :

passage de 2 registres 32 bits à 10 registres 64 bits
possibilité d'appeler certaines fonctions du noyau

eBPF permet d'exécuter des programmes contrôlés (absence de boucles, pointeurs vérifiés etc.) dans l'espace noyau à l'aide d'un compilateur JIT qui transforme le programme BPF en code natif.

Les programmes eBPF peuvent être utilisés pour implémenter des fonctionnalités de supervision, de sécurité et de réseautage hautes performances.

Éléments de sécurité

IDS

Un système de détection d'intrusion (IDS) est un appareil ou une application logicielle qui surveille un réseau ou des systèmes afin de cibler et de détecter des activités malveillantes ou des violations de la politique de sécurité. Chaque activité d'intrusion ou de violation est généralement rapportée soit à un administrateur ou centralisée dans un système de gestion d'événement et d'information de sécurité (SIEM). Un système SIEM combine les sorties de sources multiples et utilise des techniques de filtrage d'alarme afin de distinguer une activité malveillante d'une fausse alarme.

Éléments de sécurité

Contrôle d'accès discrétionnaire et droits

Le contrôle d'accès discrétionnaire (DAC) est un moyen de limiter l'accès aux objets basés sur l'identité des sujets ou des groupes auxquels ils appartiennent. Le contrôle est discrétionnaire car un sujet avec une certaine autorisation d'accès est capable de transmettre cette permission à n'importe quel autre sujet (sauf restriction du contrôle d'accès obligatoire).

Sous linux, les acteurs sont :

l'utilisateur propriétaire (user)
le groupe principal de l'utilisateur (group)
les autres (others)

Les droits usuels s'organisent ainsi :

pour les fichiers :
- r autorise à lire le contenu du fichier
- w autorise à modifier le contenu du fichier
- x autorise l'exécution du fichier.
pour les répertoires :
- r autorise à lister le contenu d'un répertoire
- w autorise la création, renommage et suppression de fichier
- x autorise à traverser (entrer) dans le répertoire.

D'autres droits existent notamment : - t le sticky bit principalement utilisé sur les répertoires et qui permet d'éviter la suppression du répertoire par d'autres utilisateurs bien qu'ils puissent avoir des droits en écriture sur le contenu de ce même répertoire. - s le setuid et setgid qui permettent d'exécuter un fichier avec les mêmes permissions que son propriétaire ou respectivement son groupe. Setgid permet également de modifier le comportement d'un répertoire en fixant le groupe d'un fichier à sa création.

Éléments de sécurité

Listes de contrôle d'accès ACL

Les listes de contrôle d'accès sont une extension du contrôle d'accès discrétionnaire et des droits usuels. Utiles lorsque l'on souhaite attribuer quelques droits particuliers à un utilisateur ou a un groupe.

Éléments de sécurité

SELinux

SELinux (Security Enhanced Linux) est un module de sécurité du noyau Linux qui fournit des politiques de sécurité de contrôle d'accès, dont le contrôle d'accès obligatoire (MAC) en addition au contrôle d'accès discrétionnaire existant (DAC). SELinux répond fondamentalement aux questions telles que :

"Est-ce que le sujet peut faire cette action à cet objet ?" e.g : "Est-ce qu'un serveur web peut accéder aux fichiers dans le répertoire home des utilisateurs ?"

Un noyau Linux intégrant SELinux impose des politiques de contrôles d'accès obligatoire qui confinent les programmes utilisateurs et les services systèmes, ainsi que les accès aux fichiers et aux ressources réseaux. Limiter les privilèges au minimum requis pour fonctionner réduit ou élimine les capacités de ces programmes et daemons à causer des dommages si ceux-ci sont compromis ou défaillants (par exemple via des dépassements de tampons ou des mauvaises configurations). Ce mécanisme de confinement fonctionne indépendamment des mécanismes de contrôle d'accès discrétionnaire traditionnels de Linux. Le concept de super utilisateur n'existe pas, et ne partage pas les raccourcis bien connus des mécanismes de sécurité traditionnels, tel qu'une dépendance aux binaires setuid/setgid.

Lorsqu'une application ou un processus, reconnu comme un sujet, effectue une requête d'accès à un objet, tel qu'un fichier, SELinux vérifie à l'aide d'un cache de vecteur d'accès (AVC), où les permissions des sujets et des objets sont mises en cache.

Si SELinux ne trouve pas matière à trancher à propos de cet accès dans le cache, il envoie une requête au serveur de sécurité. Le serveur de sécurité vérifie le contexte de sécurité de l'application ou du processus et du fichier. Le contexte de sécurité est appliqué depuis la base de données de politiques SELinux. La permission est donnée ou refusée.

Si la permission est refusée, un message "avc: denied" sera visible dans /var/log.messages.

Chaque processus et ressource système a une étiquette spéciale de sécurité appelée contexte SELinux. Un contexte SELinux est un identifiant qui s'abstrait des détails du systèmes et se concentre sur les propriétés de sécurité de l'objet. Cela permet un référencement des objets cohérent dans la politique SELinux mais supprime également toute ambigüité que l'on peut retrouver avec d'autres méthodes d'identification ; par exemple, un fichier peut avoir plusieurs noms de chemins valides sur un système qui utilise des montages liés.

La politique SELinux utilise ces contextes dans une série de règles qui définissent comment un processus peut interagir avec les autres ainsi que les différentes ressources systèmes. Par défaut, la politique ne permet aucune interaction à moins qu'une règle explicite en permette l'accès.

Le contexte SELinux contient plusieurs champs : utilisateur, role, type, et niveau de sécurité. L'information du type SELinux est sans doute la plus importante quand il s'agit de la politique SELinux, du fait que la règle la plus commune de la politique SELinux qui définit les interactions autorisées entre les processus et les ressources systèmes utilise les types SELinux et non le contexte en entier. Le type SELinux finit habituellement par _t (e.g. httpd_t).

Elements de sécurité

Polkit

Polkit est un composant permettant de contrôler les privilèges à travers l'ensemble d'un système de type UNIX. Il fournit un moyen organisé pour des processus non privilégiés de communiquer avec d'autres qui le sont. Polkit fournit un niveau de contrôle d'une politique système centralisée.

Éléments de sécurité

Systemd-logind

Systemd-logind est un service système qui gère les connexions utilisateurs. Il est responsable pour :

Garder la trace des utilisateurs et des sessions, leurs processus et leur état au repos à l'aide des unités slice et scope, ainsi qu'un service gestionnaire par utilisateur.
Générer et gérer les identifiants de session.
Fournir un accès basé sur polkit pour des utilisateurs pour des opérations telles que l'arrêt du système ou la veille.
Implémenter une logique d'inhibition lors de l'arrêt/veille pour les applications.
Gérer les touches d'arrêt/veille.
La gestion multisiège.
La gestion du basculement de session.
L'accès aux périphériques pour les utilisateurs.
L'apparition automatique de gettys sur activation d'une console virtuelle et la gestion du répertoire d'exécution utilisateur.

Les sessions utilisateurs sont enregistrées avec logind via le module PAM pam_systemd.

Éléments de sécurité

PAM

Les modules d'authentification attachables Linux (PAM) fournissent un cadriciel pour une authentification de l'utilisateur sur l'ensemble du système. Cela permet de développer des programmes indépendants du schéma d'authentification. Ces programmes ont besoin que des "modules d'authentification" leurs soient attachés à l'exécution pour fonctionner. Le module d'authentification attaché au programme est à la discrétion de l'administrateur système et dépend de l'installation locale.

Éléments de sécurité

Sudo

Sudo permet à un administrateur système de déléguer une autorité pour permettre certains à utilisateurs -- ou groupes d'utilisateurs -- de passer des commandes en tant que superutilisateur tout en fournissant une piste d'audit des commandes et de leurs arguments.

Sudo accorde une élévation de privilège temporaire à une commande unique.

Sudo peut également être utilisée pour exécuter des commandes en tant qu'autres utilisateurs ; de plus, sudo trace toutes les commandes et les tentatives d'accès échouées dans des logs pour auditions de sécurité.

Éléments de sécurité

Auditd

Le cadriciel d'audit Linux fournit un profil de protection d'accès contrôlés (CAPP) qui collecte de manière fiable des informations concernant des évènements pouvant être pertinent (mais pas forcément) pour la sécurité du système.

L'audit Linux permet de sécuriser le système en fournissant les moyens d'analyser ce qui se passe de façon très détaillé. Néanmoins, il ne fournit pas de sécurité additionnelle en soit et ne protège pas le système de bogues ou de failles. Audit est en revanche utile pour repérer ce genre de problèmes et ainsi d'aider à prendre les mesures de sécurité additionnelles pour les prévenir.

Le cadriciel d'audit fonctionne en écoutant les évènements rapportés par le noyau et en les notant dans un fichier de log.

La commande auditctl permet de définir des règles permettant d'auditer les accès et les appels systèmes (ex. chmod). La recherche et la détection d'anomalies se fait via les commandes ausearch et aureport.

Virtualisation et conteneurisation

Sous-sections

Virtualisation et conteneurisation

Chroot

Chroot est une opération qui modifie le répertoire racine apparent pour le processus en cours d'exécution et pour ses enfants. Un programme qui s'exécute dans ce genre d'environnement modifié ne peut pas accéder les fichiers et les commandes en dehors de cet arbre de répertoire environnemental. Cet environnement modifié s'appelle une prison chroot.

Virtualisation et conteneurisation

Systemd-nspawn

Systemd-nspawn peut être utilisé pour exécuter une commande ou un OS dans un conteneur léger d'espace de noms. Il est plus puissant que chroot puisqu'il virtualise la hiérarchie du système de fichiers, mais aussi l'arbre des processus, les différents sous-systèmes IPC ainsi que le nom de l'hôte et du domaine.

Systemd-nspawn limite l'accès en lecture seule à différentes interfaces du noyau dans le conteneur, telles que /sys, /proc/sys ou /sys/fs/selinux. Les interfaces réseaux et l'horloge système ne peuvent pas être modifiées depuis l'intérieur du conteneur. Les fichiers spéciaux ou fichiers de périphérique ne peuvent pas non plus être créés. Le système hôte ne peut pas être redémarré et des modules du noyau ne peuvent pas être chargés depuis le conteneur.

Les conteneurs ainsi créés peuvent être gérés à l'aide de la commande machinectl.

Virtualisation et conteneurisation

Conteneurisation LXC

LXC est une méthode de virtualisation au niveau du système d'exploitation permettant d'exécuter plusieurs systèmes isolés Linux sur un système hôte de contrôle en utilisant un unique noyau Linux.

Le noyau Linux fournit la fonctionnalité des cgroups qui permet une limitation et une priorisation des ressources (CPU, mémoire, entrées/sorties, réseau, etc.) sans besoin d'aucune machine virtuelle, ainsi que la fonction d'isolation par espace de noms qui permet l'isolation complète d'une application du point de vue de l'environnement opérant, incluant l'arbre des processus, la configuration réseau, les identifiants utilisateurs et les systèmes de fichiers montés.

LXC combine les cgroups du noyau et inclut l'isolation des espaces de nom pour fournir un environnement isolé à des applications.

LXC permet d'exécuter des conteneurs en tant que simple utilisateur sur l'hôte à l'aide des conteneurs dits "non-privilégiés".

Virtualisation et conteneurisation

Conteneurisation Docker

Docker est un ensemble de produits de Plateforme en tant que Service qui utilise la virtualisation au niveau du système d'exploitation pour livrer des logiciels dans des paquets appelé conteneurs. Les conteneurs sont isolés les uns des autres et embarquent leurs propres logiciels, bibliothèques et fichiers de configuration ; ils peuvent communiquer entre eux à travers des canaux bien définis. Tous les conteneurs sont exécuté par un noyau de système d'exploitation unique et par conséquent utilisent moins de ressources que des machines virtuelles.

Docker peut empaqueter une application et ses dépendances dans un conteneur virtuel qui peut s'exécuter sur n'importe quel ordinateur Linux, Windows, ou macOS. Ceci permet à l'application de s'exécuter dans toute une variété d'environnement, par exemple, sur sa propre machine, dans un cloud public ou privé. Quand il s'exécute sur Linux, Docker utilise les mécanismes d'isolation fournis par le noyau (tels que les cgroups et les espaces de noms) et les systèmes de fichiers capables de montage en union, pour permettre aux conteneurs de s'exécuter sur une instance Linux unique, évitant la surcharge du démarrage et de la maintenance de machines virtuelles.

Le support des espaces de nom du noyau Linux permet d'isoler l'environnement système de la vue de l'application comme l'arbre des processus, le réseau, les identifiants utilisateurs et les systèmes de fichiers montés, tandis que les cgroups fournissent la limitation de ressources mémoire et CPU. Docker inclut également sa propre bibliothèque libcontainer permettant d'accéder directement les fonctions de virtualisation fournies par le noyau Linux en plus de l'utilisation d'interfaces de virtualisation telles que libvirt, LXC et systemd-nspawn.

Docker implémente une API de haut niveau pour fournir des conteneurs légers exécutant des processus isolés.

Le logiciel Docker en tant qu'offre de services consiste en trois composants :

Le Logiciel : Le daemon Docker, dockerd, est un processus persistant qui gère les conteneurs Docker ainsi que les objets du conteneur. Le daemon est à l'écoute des requêtes envoyés via l'API du Docker Engine. Et le programme client docker fournit une interface de ligne de commande qui permet d'interagir avec le daemon.
Les objets : Les objets docker sont des entités diverses utilisées pour assembler une application dans Docker. Les classes principales des objets Dockers sont les images, les conteneurs et les services.
- Un conteneur Docker est un environnement encapsulé, standardisé qui exécute des applications. Un conteneur est géré à travers l'API Docker ou la ligne de commande.
- Une image Docker est un modèle en lecture seule utilisée pour construire des conteneurs. Les images sont utilisées pour stocker et envoyer des applications.
- Un service Docker permet une mise à l'échelle des conteneurs sur de multiples daemons. Ceci étant appelé une nuée (swarm), un ensemble de daemon coopérant, communiquant à travers l'API Docker.
Les registres : Un registre Docker est un dépôt d'image Docker. Les clients Docker se connectent aux registres pour cloner (pull) des images à utiliser ou déposer (push) des images qu'ils ont construites. Les dépôts peuvent être publics ou privés. Les deux principaux dépôts publics sont Docker Hub et Docker Cloud. Docker Hub est le registre par défaut ou Docker recherche des images. Des registres Docker permettent également la création de notifications basée sur des évènements.

Le logiciel Docker dispose également d'outils :

Docker Compose qui est un outil qui permet de définir et d'exécuter des applications Docker multi-conteneurs. Il utilise des fichier YAML pour configurer les services de l'application et créé et démarre les processus de tous les conteneurs à l'aide d'une seule commande. L'interface en ligne de commande docker-compose permet aux utilisateurs de passer des commandes sur des ensembles de conteneurs, par exemple pour construire des images, déployer des conteneurs, redémarrer des conteneurs, etc. Les commandes liées à la manipulation d'image, ou les options interactives sont inutiles dans Docker Compose car elle s'adressent à un conteneur unique. Le fichier docker-compose.yml est utiliser pour définir les services de l'application et inclut plusieurs options de configuration. Par exemple, l'option build définit les options de configuration telles que le chemin du Dockerfile, l'option command permet de surcharger les commandes Docker par défaut, etc.
Docker Swarm fournit nativement un fonctionnalité de grappe pour les conteneurs Docker qui transforme un groupe de Docker engine en un unique Docker engine virtuel. L'interface ligne de commande docker swarm permet aux utilisateurs d'exécuter des conteneurs Swarm, de créer des mots-clefs, lister les noeuds de la grappe, etc. L'interface ligne de commande docker node permet aux utilisateurs d'exécuter diverses commandes pour gérer des noeuds dans la nuée, par exemple, lister les noeuds de la nuée, mettre à jour les noeuds, supprimer les noeuds d'une nuée. Docker gère les nuées en utilisant l'algorithme de consensus Raft. Selon Raft, pour qu'une mise à jour se fasse, la majorité des noeuds de la nuée doivent s'accorder sur celle-ci.

Virtualisation et conteneurisation

Orchestrateur Kubernetes

Kubernetes est un système d'orchestration de conteneurs open source permettant d'automatiser le déploiement, la mise à l'échelle et la gestion d'applications informatiques.

Beaucoup de services de cloud offrent des plateformes ou infrastructures en tant que service (PaaS, IaaS) basées sur Kubernetes sur lesquelles Kubernetes peut être déployé comme service fournisseur de plateformes.

Kubernetes définit un ensemble de primitives, qui collectivement fournissent des mécanismes de déploiement, de maintien et de mise à l'échelle d'applications basé sur les ressources CPU, mémoire et autres métriques personnalisées. Kubernetes est lâchement couplé et extensible pour s'accorder à différentes charges de travail. Cette extensibilité est fournit en grande partie par l'API Kubernetes, utilisée par des composants internes ainsi que les extensions et conteneurs exécutés sur Kubernetes. La plateforme exerce son contrôle sur les ressources de calcul et de stockage et définissant ces ressources comme objets, ceux-ci pouvant par la suite être gérés comme tels.

Kubernetes suit l'architecture Maître-Esclave. Les composants de Kubernetes peuvent être divisés entre ceux qui gèrent les noeuds individuels et ceux qui font partie du plan de contrôle.

Le maître Kubernetes est l'unité principale de contrôle du cluster, il gère la charge de travail et dirige les communications à travers le système. Le plan de contrôle de Kubernetes consiste en divers composants, chacun ayant sa propre tâche, pouvant être exécuté soit sur un simple noeud maître, soit sur plusieurs maîtres pour des clusters à haute disponibilité. Les différents composants du plan de contrôle Kubernetes sont les suivants :

etcd : etcd est une base de données clef-valeur, légère, persistante et distribuée qui stocke de manière fiable les données de configuration du cluster, donnant une représentation de l'état global du cluster à l'instant t. etcd est un système qui favorise la cohérence à la disponibilité dans l'éventualité d'une partition réseau. Cette cohérence est cruciale pour ordonnancer correctement les services opérants. Le serveur de l'API Kubernetes utilise l'API de visualisation d'etcd pour surveiller le cluster et déployer des changements configuration critiques ou simplement restaurer n'importe quelle divergence d'état du cluster tels qu'il était déclaré par celui qui l'a déployé.
Le serveur d'API : Le serveur d'API est un composant clé qui sert l'API Kubernetes via des JSON en HTTP, qui fournit à la fois les interfaces internes et externes à Kubernetes. Le serveur d'API traite et valide les requêtes REST et met à jour l'état des objets dans etcd, de fait permettant aux clients de configurer les charges de travail et les conteneurs à travers les noeuds.
L'ordonnanceur : L'ordonnanceur est un composant qui, sur la base de la disponibilité ressource, sélectionne un noeud sur lequel s'exécute un pod non ordonnancé (entité de base géré par l'ordonnanceur). L'ordonnanceur suit l'usage ressource sur chacun des noeuds afin de s'assurer que la charge de travail n'est pas planifiée en excès de la ressource disponible. A cette fin, l'ordonnanceur doit connaître les conditions et disponibilités de la ressource et autres contraintes définies par l'utilisateur, les directives politiques telles que la qualité de service, les conditions d'affinité ou de non-affinité, la localisation des données etc. Le rôle de l'ordonnanceur est d'accorder la ressource disponible à la charge de travail demandée.
Le gestionnaire de contrôle : Un contrôleur est une boucle de réconciliation qui amène l'état courant du cluster vers l'état désiré du cluster, en communicant via le serveur d'API pour créer, mettre à jour et supprimer les ressources qu'il gère (pods, services, extrémités, etc.). Le gestionnaire de contrôle est un processus qui gère un ensemble de contrôleurs du noyau Kubernetes. Un type de contrôleur est un contrôleur de réplication, qui s'occupe de la réplication et de la mise à l'échelle en exécutant un nombre de copies de pods spécifiées à travers le cluster. Il s'occupe également de créer des pods de remplacement, si les noeuds sous-jacents sont en erreur. D'autres contrôleurs qui sont une partie du noyau Kubernetes incluent le contrôleur DaemonSet pour exécuter exactement un pod sur chaque machine (ou sous-ensemble de machines), et un contrôleur de travail pour exécuter des pods jusqu'à fin d'exécution par exemple pour des traitements batchs. L'ensemble des pods qu'un contrôleur gère est déterminé par l'étiquette des sélecteurs faisant partie de la définition du contrôleur.

Un noeud, est une machine où des conteneurs (charge de travail) sont déployés. Chaque noeud à l'intérieur du cluster doit exécuter un environnement d'exécution de conteneurs tel que Docker, ainsi que les composants mentionnés ci-dessous, à des fins de communication avec le maître pour la configuration réseau de ces conteneurs.

Kubelet : Kubelet est responsable de l'état d'exécution de chaque noeud, il s'assure que tous les conteneurs du noeud sont sains. Il prend en charge le démarrage, l'arrêt et la maintenance des conteneurs d'application organisés en pods tels que l'a décidé le plan de contrôle. Kublet surveille l'état d'un pod, s'il n'est pas dans l'état désiré, le pod est redéployé sur le même noeud. Le statut du noeud est relayé sur une période de quelques secondes via des messages au maître. Si le maître détecte un échec de noeud, le contrôleur de réplication observe ce changement de statut et lance des pods sur d'autres noeuds sains.
Kube-proxy : Le Kube-proxy est une implémentation d'un proxy réseau et d'un répartiteur de charge, il prend en charge l'abstraction de service ainsi que d'autres opérations réseau. Il est responsable du routage du traffic vers le conteneur approprié basé sur l'adresse IP et le numéro de port de la requête qui arrive.
Environnement d'exécution de conteneur : Un conteneur réside dans un pod. Le conteneur est le niveau de micro-service le plus bas, qui contient l'application en cours d'exécution, les bibliothèques et leurs dépendances. Ils peuvent également avoir une adresse IP externe.

L'unité d'ordonnancement de base dans Kubernetes est un pod. Un pod est un groupement de composants conteneurisés. Un pod consiste en un ou plusieurs conteneurs garantis de se trouver sur le même noeud.

Chaque pod dans Kubernetes est assigné à une adresse IP unique à l'intérieur du cluster, permettant aux applications d'utiliser des ports sans risques de conflits. A l'intérieur du pod, chaque conteneur peut faire référence à chaque autre sur le localhost, mais un conteneur à l'intérieur d'un pod n'a aucun moyen de s'adresser directement à un autre conteneur dans un autre pod ; pour cela, il doit utiliser l'adresse IP du pod.

Un pod peut définir un volume, tel qu'un répertoire du disque local ou un disque réseau, et l'exposer aux conteneurs du pod. Les pods peuvent être gérés manuellement via l'API Kubernetes, ou leur gestion peut être déléguée à un contrôleur. De tels volumes sont aussi la base des fonctionnalités Kubernetes de ConfigMaps (pour fournir un accès à la configuration à travers le système de fichier visible au conteneur) et Secrets (pour fournir les certificats nécessaires à l'accès sécurisé à des ressources distantes, en donnant uniquement aux conteneurs autorisés, ces certificats sur leur système de fichier visible).

La fonction d'un ReplicaSet est de maintenir un ensemble stable de pods répliqués pouvant être exécutés à tout moment. En tant que tel, il est souvent utilisé pour garantir la disponibilité d'un nombre de pods identiques spécifique.

Les ReplicaSets est également un mécanisme de rassemblement qui permet à Kubernetes de maintenir pour un pod donné un nombre d'instance défini à l'avance. La définition d'un ensemble de réplique utilise un sélecteur, dont l'évaluation résulte en l'évaluation de tous les pods qui lui sont associés.

Un service Kubernetes est un ensemble de pods travaillant de concert, tel une couche d'une application multi-couche. L'ensemble de pods qui constitue un service sont définis par un sélecteur d'étiquette. Kubernetes fournit deux modes de découverte de service, en utilisant des variables d'environnement, ou en utilisant le DNS Kubernetes. La découverte de service assigne un adresse IP fixe et un nom DNS au service, et réparti la charge du traffic en utilisant un DNS round-robin pour les connexions réseaux à cette adresse IP au milieu des pods vérifiant ce sélecteur (même si des erreurs peuvent amener les pods à passer d'une machine à une autre). Par défaut un service est exposé à l'intérieur d'un cluster (par exemple les pods back-end peuvent être groupés en service, recevant des requêtes de la part des pods front-end réparties entre eux), mais un service peut également être exposé en dehors d'un cluster (par exemple pour que les clients puissent accéder aux pods front-end).

Les systèmes de fichier dans le conteneur Kubernetes fournit par défaut un stockage éphémère. Cela signifie qu'un redémarrage du pod effacera toute les données sur ces conteneurs, et par conséquent, cette forme de stockage est, excepté dans le cas d'applications triviales, relativement limitante. Un volume Kubernetes fournit un stockage permanent qui existe pendant la durée d'existence du pod lui-même. Ce stockage peut également être utilisé comme disque partagé pour les conteneurs du pod. Ces volumes sont montés à des points de montages spécifique à l'intérieur du conteneur définit par la configuration du pod, et ne peuvent être montés aux autres volumes ou liés à ceux-ci. Le même volume peut être monté à différent endroits dans l'arbre du système de fichiers par différents conteneurs.

Kubernetes fournit un partitionnement des ressources qu'il gère dans des ensembles disjoints appelés espace de noms. L'usage de ces espaces de noms est destiné aux environnements possédant un grand nombre d'utilisateurs répartis dans plusieurs équipes, ou projets, ou même à séparer des environnements tels que le développement, l'intégration et la production.

Un problème applicatif thématique est de décider ou stocker et gérer les informations de configuration, dont certaines peuvent contenir des données sensibles. Les données de configuration peuvent être relativement hétérogènes comme de petits fichiers de configurations individuels ou de grands fichiers de configuration ou des documents JSON/XML. Kubernetes permet de traiter ce genre de problème à l'aide de deux mécanismes assez proches : "configmaps" et "secrets", les deux permettent des changements de configuration sans nécessiter la reconstruction de l'application. Les données de configmaps et de secrets sont accessibles à chaque objets de l'instance de l'application auxquels ils ont été liés au déploiement. Un secret et/ou un configmaps sont uniquement envoyé à un noeud si un pod sur ce noeud le demande. Kubernetes le gardera en mémoire sur ce noeud. Un fois que le pod qui dépend du secret ou de la configmap est supprimé, la copie en mémoire de tous les secrets et configmaps liés est également supprimée. La donnée est accessible au pod de deux façons : en tant que variables d'environnements (que Kubernetes créé lors du démarrage du pod) ou disponible dans le système de fichier du conteneur visible dans le pod.

La donnée elle même est stockée sur le maître qui est hautement sécurisé et dont personne ne doit avoir d'accès de connexion. La plus grande différence entre un secret et une configmap est que le contenu de la donnée dans un secret est encodé en base 64. Il peut également être chiffré. Les secrets sont souvent utilisés pour stocker des certificats, des mots de passe et des clefs ssh.

Il est très facile de réaliser une mise à l'échelle d'applications sans conditions d'état : Il suffit d'ajouter plus de pods d'exécution - quelque chose que Kubernetes fait très bien. Les charges de travail avec condition d'état sont bien plus difficiles, de fait que l'état doit être conservé si un pod est redémarré, et si l'application doit être redimensionnée alors l'état devra possiblement être redistribué. Les bases de données sont des exemples de charge de travail avec condition d'état. Lors d'une exécution en mode haute disponibilité, beaucoup de bases de données ont la notion d'instance primaire et d'instance(s) secondaires. Dans ce cas la notion d'ordonnancement d'instances est important.

Virtualisation et conteneurisation

Libvirt

Libvirt est une API open-source, ainsi qu'un daemon et un outil de gestion pour gérer des plateformes de virtualisation. Elle peut être utilisée pour gérer KVM, Xen, VMware, ESXi, QEMU et autres technologies de virtualisation. Ces APIs sont utilisées très largement au niveau de la couche d'orchestration des hyperviseurs pour le développement de solutions de clouds.

Virtualisation et conteneurisation

Hyperviseurs

Un hyperviseur est un logiciel, microgiciel ou matériel qui créé et exécute des machines virtuelles. Un ordinateur sur lequel un hyperviseur exécute une ou plusieurs machines virtuelles est appelé hôte, et chaque machine virtuelle est appelée invitée. L'hyperviseur présente le système d'exploitation invité à l'aide d'une plateforme d'exploitation virtuelle et gère l'exécution des systèmes d'exploitations invités. Plusieurs instances de divers systèmes d'exploitation peuvent partager les mêmes ressources matérielles virtualisées. A l'instar des mécanismes de virtualisation implémentés au niveau du système d'exploitation (conteneurs), les systèmes d'exploitations invités ne doivent pas forcément partager un même noyau.

Il existe deux types d'hyperviseurs :

Type-1 natif : Ces hyperviseurs s'exécutent directement sur le matériel de l'hôte pour contrôler le matériel et gérer les systèmes d'exploitation invités.
Type-2 hébergés : Ces hyperviseurs s'exécutent sur un système d'exploitation conventionnel comme n'importe quel autre programme. Un système d'exploitation invité s'exécute en tant que processus de l'hôte. Les hyperviseurs de type-2 créent une abstraction pour les systèmes d'exploitation invités depuis le système d'exploitation hôte.

Cette distinction entre les deux types n'est pas toujours claire. Par exemple KVM et bhyve sont des modules noyau qui transforment le système d'exploitation hôte en hyperviseur de type-1. En même temps, les distributions Linux et FreeBSD sont aussi des systèmes d'exploitations conventionnels, où des applications entrent en concurrence les unes avec les autres pour les ressources VM et ils peuvent être aussi catégorisés comme des hyperviseurs de type-2.

Virtualisation et conteneurisation

Openstack

Openstack est une plateforme libre d'informatique en nuage. Elle est généralement déployée comme Infrastructure en tant que Service (IaaS), à la fois dans des clouds publics et privés où des serveurs virtuels ainsi que d'autres ressources sont mis à disposition des utilisateurs. La plateforme logicielle est faite de composants en relation les uns avec les autres au travers d'un centre de données, contrôlant divers ensembles de matériels comprennant des ressources de traitement, de stockage et de réseautage. Les utilisateurs peuvent gérer la plateforme aux travers, d'une interface de contrôle basée web, d'outils en ligne de commande, ou de services webs RESTfuls.

Données

Introduction

Ce chapitre traite de la partie données du programme PSE.

De la gestion des données structurées (Bases de données), semi-structurées et déstructurées (Big data et lacs de données), avec une approche relativement légère pour deux sujets aussi larges.

Sections

Bases de données

Une base de données est une collection organisée de données stockées et accédées de manière électronique depuis un système informatique. Elles sont généralement développées en utilisant des techniques d'architecture et de modélisation formelles.

Les système de gestion de bases de données (SGBD) est le logiciel qui interagit avec l'utilisateur final, les applications, et la base de données elle-même pour capturer et analyser la donnée. Le logiciel SGBD comprend également les principaux outils d'administration de bases de données.

On peut classifier les système de gestion de bases de données d'après les modèles de bases de données supportés.

Généralement les modèles logiques de données les plus rencontrés sont :

Modèle hiérarchiques : Modèle dans lequel la donnée est organisée dans une structure de type arbre. La donnée est stockée en tant qu'enregistrements connectés les uns aux autres par des liens. Un enregistrement est une collection de champs, avec chaque champs contenant une unique valeur. Le type d'enregistrement définit les champs que l'enregistrement contient.
Modèle réseau : Modèle conçu comme étant une façon flexible de représenter des objets et leurs relations. Sa caractéristique principale est que le schéma, vu comme un graphe dans lequel les types d'objets sont des noeuds et les relations entre types sont des liens, n'est pas restreint à être hiérarchique ou maillé.
Modèle objet : Modèle dans lequel l'information est représentée sous la forme d'objets et utilisés en programmation orientée objet. Les bases de données objets sont différentes des bases de données relationnelles qui sont orientées tables. Les bases de données objet-relationnel sont un hybride des deux approches.
Modèle relationnel : Modèle dans lequel toute donnée est représentée en terme de liste ordonnée finie, groupée dans des relations.

Sous-sections

CRUD
ACID

Bases de données

CRUD

Create Read Update Delete (CRUD) sont quatre opérations basiques de stockage persistant. CRUD est également utilisé quelques fois pour décrire des conventions d'interface utilisateur permettant l'affichage, la recherche et le changement d'informations à l'aide de formulaires et de rapports.

L'acronyme CRUD fait référence à des opérations majeure implémentées par les bases de données. Chaque lettre peut être mis en lien avec une commande SQL standard :

CRUD	SQL
Create	INSERT
Read	SELECT
Update	UPDATE
Delete	DELETE

L'acronyme CRUD peut également apparaître avec les APIs dites RESTful. Chaque lettre de l'acronyme peut être lié à une méthode HTTP :

CRUD	HTTP
Create	PUT
Read	GET
Update	PUT
Delete	DELETE

Bases de données

ACID

Atomicité Consistence Isolation Durabilité (ACID) est un ensemble de propriétés des transactions de bases de données devant permettre de garantir une validité de données malgré les erreurs, pertes d'électricité et autres mésaventures. Dans le contexte des bases de données, une séquence d'opération répondant aux propriétés ACID est appelé transaction.

Les caractéristiques de ces quatre propriétés sont les suivantes :

Atomicité : Les transactions sont souvent composées de déclarations multiples. L'atomicité garantit que chaque transaction est traitée en tant qu'unité, qui soit réussit totalement, soit échoue totalement : si la moindre déclaration constituante échoue, la transaction échoue, la transaction dans son ensemble échoue et la base de donnée reste inchangée. Un système atomique doit garantir l'atomicité dans chaque situation. Par conséquent, une transaction ne peut pas être observée comme étant en progrès par un autre client de la base de données.
Consistence (validité) : La consistence s'assure qu'une transaction peut uniquement amener la base de données d'un état correct vers un autre, en gardant les invariants de la base de données : toute donnée rentrée en base doit être valide selon toutes les règles définies, cela inclut les contraintes, les cascades, les déclenchements, et leurs combinaisons. Cela empêche une corruption de la base de données mais ne garantit pas qu'une transaction soit correcte. L'intégrité référentielle garantit la relation clef primaire - clef étrangère.
Isolation : Les transactions sont souvent exécutées de façon concurrente. L'isolation garantit que l'exécution concurrente de transactions laisse la base de données dans le même état que si ces transactions avaient été exécutées de façon séquentielle.
Durabilité : La durabilité garantit qu'une fois l'exécution de la transaction finie, elle sera toujours enregistrée même dans le cas d'une panne. Cela signifie généralement que les transactions complétées sont enregistrées dans une mémoire non volatile.

Algèbre relationnelle

Voir langage SQL.

Administration SGBDR PostgreSQL

PostgreSQL est un système de gestion de base de données relationnel (SGBDR) libre et open source mettant l'accent sur la notion d'extensibilité ainsi que le respect du standard SQL.

PostgreSQL a pour fonctionnalités des transactions avec les propriétés ACID, des vues misent à jours automatiquement, des vues matérialisées, des déclencheurs, des clefs étrangères, et des procédures stockées. PostgreSQL est construit de façon à gérer tout type de charge de travail, depuis un simple ordinateur jusqu'aux entrepôts de données ou des services webs répondant à de nombreux utilisateurs concurrents.

Sous-sections

Administration SGBDR PostgreSQL

Stockage et réplication

PostgreSQL inclus une réplication binaire basé sur l'import de changements (write-ahead logs (WAL)) pour répliquer des noeuds de manière asynchrone, avec la possibilité d'exécuter des requêtes de lecture seule sur ces noeuds répliqués. Ceci permet de séparer le traffic en lecture sur de multiples noeuds efficacement.

PostgreSQL inclus un mécanisme de réplication synchrone qui garantit que, pour chaque transaction d'écriture, le maître attende jusqu'à ce qu'au moins un noeud répliqué ait écrit la donné dans sa log de transactions. Contrairement à d'autres systèmes de base de données, la durabilité d'une transaction (selon qu'elle soit synchrone ou asynchrone) peut être spécifiée par base de données, par utilisateur, par session ou même par transaction. Cela peut se révéler utile pour des charges qui ne demandent pas de telles garanties, et peut ne pas être recherchée pour l'ensemble des données car cela diminue les performances du fait de la nécessité de confirmation de la transaction pour atteindre la veille synchrone.

Les serveurs de veille peuvent être synchrones ou asynchrones. Des serveurs de veille synchrones peuvent être spécifiés dans la configuration qui détermine quels serveurs sont candidats pour la réplication synchrone. Le premier dans la liste qui diffuse activement sera utilisé comme serveur synchrone courant. Quand il échoue, le système retombe sur le suivant dans la liste.

La réplication multi-maître synchrone n'est par inclus dans PostgreSQL. Postgres-XC basé sur PostgreSQL fournit la réplication multi-maître synchrone. Réplication bidirectionnelle (BDR) est un système de réplication multi-maître asynchrone pour PostgreSQL.

Des outils tels que remgr permettent de gérer des groupes de réplication plus facilement.

PostgreSQL inclus un support pour arbre B et index de tables de hachages, ainsi que quatre méthodes d'accès aux index : les arbres de recherche généralisés (GiST), les index inversés généralisés (GIN), GiST partitionnés espace (SP-GiST) et les index de portée de bloc (BRIN). De plus, des méthodes d'index définis par l'utilisateur peuvent être crées. Les index dans PostgreSQL supporte également les fonctionnalités suivantes :

Les index d'expression peuvent être créés à l'aide d'un index du résultat d'une expression ou fonction, au lieu de la simple valeur d'une colonne.
Les index partiels, qui indexent seulement une partie d'une table, qui peut être créé en ajoutant une clause WHERE à la fin de la déclaration CREATE INDEX. Ceci permet la création d'index plus petits.
Le planificateur est capable d'utiliser des index multiples ensemble pour répondre à des requêtes complexes, en utilisant des opérations temporaire d'index de tableaux de bits en mémoire.
L'indexation des k-proche voisins (KNN-GiST) fournit une recherche efficace des "plus proches valeurs" à celle spécifiée, utile pour trouver des mots similaires, ou des objets proches ou des lieux avec des informations géographiques.
Les balayages uniquement-index permettent souvent au système de récupérer la donnée depuis des index sans jamais avoir à accéder la table principale.

Dans PostgreSQL, un schéma détient tous les objets, à l'exception des rôles et des tablespaces. Les schémas agissent efficacement comme des espaces de noms, permettant à des objets de même noms de coexister dans la même base de données. Par défaut, les bases de données ont un schéma appelé public, mais d'autres schémas peuvent être créés, et le schéma public n'est pas obligatoire.

Un paramètre search_path détermine l'ordre dans lequel PostgreSQL vérifie les schémas les objets sans qualifications (sans schéma préfixé). Par défaut, il est défini à $user, public ($user fait référence à l'utilisateur de la base de données connecté). Ce paramètre peut être changé sur une base de données ou un niveau de rôle, mais il s'agit d'un paramètre de session, il peut être changé librement (de multiples fois) pendant une session client, affectant uniquement cette session.

Les schémas non existants, listés dans search_path sont silencieusement ignorés pendant la recherche d'objets.

De nouveaux objets sont créés dans n'importe quel schéma valide qui apparaît en premier dans le search_path

Une grande variété de types de données natifs sont supportés, incluant :

Booléens
Nombre à précision arbitraire
Caractère (texte, varchar, char)
Binaire
Date/heure (horodatage/heure avec/sans fuseau horaire, date, intervalle)
Monnaie
Énumération
Chaîne de bits
Texte de recherche de type
Composé
HStore
Tableaux
Primitives géométriques
Adresses IPv4 et IPv6
CIDR et adresses MAC
XML
UUID
JSON, JSONB

De plus, les utilisateurs peuvent créer leurs propres types de données qui peut généralement être fait complètement indexable via les infrastructures d'indexation PostgreSQL - GiST, GIN, SP-GiST.

Il existe également un type de données appelé un domaine, qui est le même que n'importe quel type de données mais avec des contraintes optionnelles définies par le créateur de ce domaine. Cela signifie que toute donnée entrée dans une colonne utilisant le domaine devra se conformer aux contraintes définies comme faisant partie du domaine.

Un type qui représente un intervalle de donnée peut être utilisé et est appelé type intervalle. Ces intervalles peuvent être discrets ou continus. Les types inclus disponibles sont les intervalles d'entiers, les nombres décimaux, les horodatages et les dates.

Des types avec intervalles personnalisés peuvent être créés pour faire de nouveau types d'intervalles disponibles, tels que des adresses IP qui utilisent un type inet comme base. Les types intervalle sont aussi compatibles avec des opérateurs existants utilisés pour vérifier des intersections, l'inclusion, etc.

De nouveaux types de la plupart des objets à l'intérieur de la base de données peuvent être créés, tels que :

Distributions
Conversions
Types de données
Domaines de données
Fonctions
Index
Opérateurs
Langages procéduraux

Des tables peuvent être paramétrées pour hériter leurs caractéristiques d'une table parente. Les données d'une table descendante apparaîtront comme existantes dans les tables parentes, à moins que les données ne soit lues depuis la table parente en utilisant le mot clef ONLY. Ajouter une colonne dans la table parente la fera apparaître dans la table descendante.

L'héritage peut être utilisé pour implémenter un partitionnement de table, en utilisant soit des déclencheurs soit des règles pour insérer directement depuis la table parente dans les tables descendante concernées.

L'héritage permet de fournir un moyen de relier les fonctions de généralisation hiérarchiques décrites dans des diagrammes relations entités (ERDs) directement dans la base de données PostgreSQL.

Administration SGBDR PostgreSQL

Contrôle et connectivité

PostgreSQL peut se connecter à d'autres systèmes pour récupérer des données via des encapsulateurs de données étrangères (FDWs). Ils peuvent prendre la forme de n'importe quelle source de données, telle qu'un système de fichier, un autre SGBDR, ou un service web. Cela signifie que des requêtes classiques de base de données peuvent utiliser ces sources de données comme des tables, et même joindre ensemble plusieurs sources de données.

Pour se connecter à des applications, PostgreSQL inclus l'interface libpq (l'interface d'applications C officielle) et ECPG (un système C embarqué). Des bibliothèques tierces pour se connecter à PostgreSQL sont disponibles pour de nombreux langages de programmation.

Des langages procéduraux permettent aux développeurs d'étendre la base de donnée à l'aide de fonctions personnalisées, souvent appelées procédures stockées. Ces fonctions peuvent être utilisées pour construire des déclencheurs de base de données (fonctions invoquées suite à la modification d'une donnée particulière), des types de données personnalisés et des fonctions d'agrégations. Des langages procéduraux peuvent également être invoqués sans définir de fonction en utilisant une commande DO au niveau du SQL.

Les langages sont divisés en deux groupes : les procédures écrites en langage sûr sont exécutées dans des bacs à sable et peuvent être créées et utilisées par n'importe quel utilisateur. Les procédure écrites en langage non sûr sont uniquement créées par des super utilisateurs, du fait qu'elles permettent un court circuit des restrictions de sécurité de la base de données, mais également d'accéder à des ressources externe à la base de données. Quelques langages tel que Perl fournissent à la fois des versions sûre et non sûres.

PostgreSQL fournit un support pour trois langages procéduraux :

SQL (sûr). Des fonctions SQL plus simple peuvent être étendues dans une requête appelante, qui évite la surcharge à l'appel de fonction et permet à l'optimiseur de requête de "voir à l'intérieur" de la fonction.
Langage procédural PostgreSQL (PL/pgSQL)(sûr), qui ressemble au langage procédural Oracle pour langage procédural SQL (PL/SQL) et les modules stockés persistants SQL (SQL/PSM).
C (non sûr), qui permet de charger une ou plusieurs bibliothèques partagées personnalisées en base de données. Les fonctions écrites en C offrent une meilleure performance, mais un bogue dans le code peut faire tomber et corrompre la base de données. La plupart des fonctions incluses sont écrites en C.

De plus, PostgreSQL permet aux langages procéduraux d'être chargés en base de données à l'aide d'extensions. Trois extensions sont incluses dans PostgreSQL pour Perl, Tcl et Python.

Des déclencheurs sont des évènements déclenchés par l'action de déclarations de langage de manipulation de données SQL (DML). La plupart des déclencheurs sont activés uniquement pour des déclarations INSERT ou UPDATE.

Les déclencheurs peuvent être liés à des tables. Ils peuvent être par colonnes et conditionnels, les déclencheurs UPDATE peuvent cibler les colonnes spécifiques d'une table, et les déclencheurs peuvent être exécutés selon un ensemble de conditions spécifiés par une clause WHERE. Les déclencheurs peuvent être liés à des vues en utilisant la condition INSTEAD OF. De multiples déclencheurs sont traités par ordre alphabétique. En plus d'appeler des fonctions écrites en PL/pgSQL natif, les déclencheurs peuvent également invoquer des fonctions écrites dans d'autres langages PL/Python ou PL/Perl.

PostgreSQL fournit un système de messagerie asynchrone qui peut être accédé à travers les commandes NOTIFY, LISTEN et UNLISTEN. Une session peut émettre une commande NOTIFY, avec un canal spécifique à un utilisateur et une charge optionnelle, pour marquer l'occurrence d'un évènement en particulier. D'autres sessions sont capables de détecter ces évènements en soumettant une commande LISTEN, qui permet d'écouter un canal en particulier. Cette fonctionnalité peut être utilisée pour une grande variété de situations, tels que faire savoir à d'autres sessions quand une table a été mise à jour, ou pour des applications séparées de détecter quand une action particulière a été effectuée. Un tel système prévient le besoin de récupération d'informations par les applications et réduit les surcharges inutiles. Les notifications sont pleinement transactionnelles, dans le sens où les messages ne sont pas envoyés tant que la transaction desquels ils proviennent n'a été enregistrée. Cela élimine le problèmes des messages envoyés pour une action en cours qui est ensuite redéroulée en sens inverse.

Beaucoup de connecteurs pour PostgreSQL fournissent un support pour le système de notification (incluant libpq, JDBC, Npgsql, psycopg, Npgsql, psycopg et node.js) pour qu'il puisse être utilisé par des applications internes.

Les règles permettent l'arbre de requêtage d'une requête arrivante d'être réécrit. Des "règles de réécriture de requête" sont liées à une table/classe et "réécrire" le DML arrivant (select, insert, update et/ou delete) en une ou plusieurs requêtes supplémentaires qui soit remplacent la déclaration DML originale soit s'ajoutent à lui. Les réécriture de requêtes ont lieu après l'analyse syntaxique de la déclaration de requête, mais avant la planification de requête.

D'autres fonctionnalités du requêtage incluent :

Transactions
Recherche plein texte
Vues
- Vues matérialisées
- Vues actualisables
- Vues récursives
Joins internes, externes et croisés
Sous-selects
- Sous-requêtes corrélées
Expressions régulières
Expressions de tables communes et expression de table commune inscriptible
Connexions chiffrées via sécurité de couche transport (TLS)
Domaines
Points de sauvegardes
Enregistrement en deux temps
La technique de stockage d'attributs surdimensionnés (TOAST) est utilisée pour stocker de manière transparente de grand attributs de table dans une aire séparée, avec compression automatique.
SQL embarqué est implémenté en utilisant un préprocesseur. Un code SQL est tout d'abord été écrite et embarquée dans du code C. Puis le code est exécuté à travers un préprocesseur ECPG, qui remplace le SQL avec des appels au code de la bibliothèque. Puis le code peut être compilé en utilisant un compilateur C.

Le serveur PostgreSQL fonctionne au niveau des processus (et pas des fils d'exécution), et utilise un processus de système d'exploitation par session de base de données. Des sessions multiples sont automatiquement réparties sur tout les processeurs disponibles par le système d'exploitation. De nombreux types de requêtes peuvent aussi être parallélisés à travers plusieurs processus en arrière plan, pour profiter des nombreux processeurs ou cœurs. Les applications clientes peuvent utiliser des fils d'exécution et créer plusieurs connexions à la base de données depuis chaque fil d'exécution.

Administration SGBDR PostgreSQL

Sécurité

PostgreSQL gère sa sa sécurité interne à l'aide de rôles. Un rôle peut généralement être un utilisateur (un rôle pouvant se connecter), ou un groupe (un rôle duquel d'autres rôles sont membres). Les permissions peuvent être accordées ou révoquées sur tout objet jusqu'au niveau des colonnes, et peuvent également permettre/interdire la création de nouveaux objets au niveau de la base de données, du schéma ou de la table.

La fonctionnalité PostgreSQL SECURITY LABEL permet un sécurité additionnelle; avec un module chargeable inclus permettant un contrôle d'accès obligatoire d'étiquettes (MAC) basé sur la politique de sécurité SELinux.

PostgreSQL supporte nativement un large panel de mécanismes externes d'authentification, tels que :

Mot de passe : soit SCRAM-SHA-256, soit MD5, soit en clair
GSSAPI
SSPI
Kerberos
ident (relie utilisateur système et utilisateur base de données par serveur ident)
peer (relie utilisateur local et utilisateur base de données)
LDAP
- AD
RADIUS
Certificat
PAM

Les méthodes par GSSAPI, SSPI, Kerberos, pees, ident et certificats peuvent également spécifier un fichier "map" qui liste quels utilisateurs vérifiés par le système d'authentification sont autorisés à se connecter spécifiquement en tant qu'utilisateur de base de données.

Ces méthodes sont spécifiées dans le fichier de configuration d'authentification de groupe basé sur l'hôte (pg_hba.conf), qui détermine quelles connexions sont autorisées. Cela permet un contrôle sur quel utilisateur peut se connecter à quelle base de données, depuis quelle adresse IP, intervalle d'adresse IP ou domaine socket, avec quel système d'authentification, et si la connexion doit utiliser la couche de transport de sécurité (TLS)

Big data et lac de données

Le big data désigne les ressources d'informations dont les caractéristiques en terme de volume, de vélocité et de variété imposent l'utilisation de technologies et de méthodes analytiques particulières pour générer de la valeur, et qui dépassent en général les capacités d'une seule et unique machine et nécessitent des traitements parallélisés.

L'explosion quantitative (et souvent redondante) des données numériques permet une nouvelle approche pour analyser le monde. Le volume colossal de données numériques disponibles, implique de mettre en oeuvre de nouveaux ordres de grandeur concernant la capture, le stockage, la recherche, le partage, l'analyse et la visualisation des données, celles-ci proviennent de nombreuses sources numériques : les réseaux sociaux, l'OpenData, le Web, des bases de données privées, publiques à caractère commercial ou scientifique.

La maturité grandissante du concept permet de se différencier de manière plus marqué vis à vis de l'informatique décisionnelle :

L'informatique décisionnelle utilise des outils de mathématiques appliquées ainsi que des statistiques descriptives à l'aide de données à haute densité d'informations pour mesurer, observer des tendances etc. Le big data utilise l'analyse mathématique, l'optimisation, les statistiques inductives ainsi que des concepts d'identification de systèmes non linéaires pour inférer des règles (régressions, relations non linéaires et effets causaux) de larges ensembles de données avec une densité d'information faible afin de révéler des relations et dépendances, ou pour fournir des prédictions de résultats et de comportements.

Le big data peut être décrit par les caractéristiques suivantes :

Volume : La quantité de la donnée générée et stockée. La taille de la donnée détermine la valeur, la potentielle perspicacité, et si elle peut être considérée big data ou non. La taille du big data est généralement supérieure aux térabits et pétabits.
Variété : Le type et la nature de la donnée. Les technologies plus anciennes tels que les SGBDR étaient capable de traiter des données structurées de manière performante et efficace. Néanmoins, les changements du type et de la nature des données structurées à semi-structurées puis déstructurées à mis à l'épreuve les outils et technologies existants. Les technologies big data ont évoluées avec l'intention première de capturer, stocker et traiter la donnée semi-structurée et déstructurée (variété) générée très rapidement (vitesse), et avec une taille immense (volume). Plus récemment, ces outils et technologies sont utilisés pour s'occuper de données structurées mais préférablement pour le stockage. Finalement, le traitement de données structurées était toujours gardé en option, soit en utilisant du big data soit avec des SGBDR traditionnels. Ceci permet d'analyser les données vers un usage efficace des perspicacités cachées exposées par les données collectées via les réseaux sociaux, les fichiers de logs, les capteurs, etc. que le big data dessine depuis du texte, des images, audio, vidéo ; et complète les pièces manquantes via la fusion de données.
Vitesse : La rapidité à laquelle la donnée est générée et traitée pour satisfaire la demande et les nouveaux défis que représentent le chemin de la croissance et du développement. Le big data est souvent disponible en temps réel. En comparaison avec le small data, le big data est produit de façon plus continu. Deux types de vitesses liés au big data sont la fréquence de production et la fréquence de gestion, enregistrement et publication.
Véracité : La véracité et la fiabilité de la donnée, qui fait référence à sa qualité et sa valeur. Le big data ne doit pas être uniquement grand par la taille, mais également fiable afin d'obtenir de la valeur dans son analyse. La qualité de la donnée capturée peut largement varier et affecter la précision de l'analyse.
Valeur : La valeur d'une information qui peut être obtenu par le traitement et l'analyse de grands ensembles de données. La valeur peut aussi être mesurée par une évaluation des autres qualités du big data. La valeur peut aussi représenter la profitabilité de l'information qui est extraite de l'analyse du big data.
Variabilité : La caractéristiques des formats changeants, structure, ou sources de big data. Le big data peut inclure des données structurées ou déstructurées ou encore une combinaison des deux. L'analyse du big data peut intégrer des données brutes de sources multiples. Le traitement des données brutes peut également faire intervenir des transformations de données déstructurées en données structurées.

D'autres caractéristiques du big data sont :

Exhaustivité : Si le système dans son ensemble est capturé (enregistré) ou non. Le big data peut inclure toutes les données depuis les sources ou pas.
Fin et uniquement lexical : Respectivement, la proportion de données spécifiques de chaque élément par élément collecté et si l'élément et ses caractéristiques sont correctement indexés ou identifiés.
Relationnel : Si la donnée collectée contient des champs communs qui pourrait permettre une intersection, ou méta-analyse, de différents ensembles de données.
Extensible : Si de nouveaux champs dans chaque élément de la donnée collectée peuvent être ajoutés ou changés facilement.
Mise à l'échelle : Si la taille du système de stockage big data peut rapidement s'agrandir.

L'architecture du big data est généralement multi-couche. Une architecture parallèle distribuée distribue les données à travers de multiples serveurs, ces exécutions dans des environnements parallèles permet d'améliorer considérablement les temps de traitements. Ce type d'architecture rentre les données dans des systèmes de gestions de bases de données parallèles, qui implémentent l'usage du modèle de programmation MapReduce de Google. Le concept MapReduce fournit un modèle de traitement parallèle. Les requêtes sont réparties et distribuées à travers des noeuds parallèles et traités en parallèle. Les résultats sont ensuite récupérés, rassemblés et fournis. Ce type de framework cherche à rendre transparent le pouvoir de traitement à l'utilisateur final en utilisant des interfaces de serveurs d'applications.

Le lac de données peut permettre à une organisation de changer son fusil d'épaule en passant d'un contrôle centralisé à un modèle partagé pour répondre aux changements dynamiques de la gestion d'information.

Un lac de données est un système ou bibliothèque de données stockées dans leurs formats naturels/bruts, généralement des objets blobs ou des fichiers. Un lac de données est généralement un emplacement de stockage unique de données qui incluent des copies brutes de données système, des données de capteurs, des données sociales etc. et des données transformées utilisées pour des tâches comme la visualisation, l'analyse et l'apprentissage automatique. Un lac de données peut inclure des données structurées de bases de données relationnelles, semi-structurées (CSV, logs, XML, JSON), ou déstructurées (emails, documents, PDFs) et des données binaires (images, audio, vidéo).

Les principaux composants qui caractérisent un écosystème big data sont les suivants :

Des techniques d'analyse de données, telles que les tests A/B, l'apprentissage automatique, et le traitement automatique des langages. Des technologies big data, telles que l'informatique décisionnelle, l'informatique en nuage, et les bases de données.
Une visualisation de la donnée, à travers des diagrammes, des graphes, ou d'autres types d'affichages.

Réseau

Introduction

Ce chapitre traite de la partie réseau du programme PSE.

Sections

Topologie de réseau

Une topologie de réseau est un arrangement d'éléments (liens, noeuds, etc.) dans un réseau de communication.

La topologie de réseau est une structure topologique d'un réseau et peut-être décrite physiquement ou logiquement. Il s'agit d'une application de la théorie des graphes à l'intérieur de laquelle les appareils de communication sont représentés comme des noeuds et les connexions comme des liens ou lignes entre les noeuds. La topologie physique est le placement de divers composants d'un réseau, tandis que la topologie logique illustre les flux de données à l'intérieur d'un réseau. La distance entre noeuds, les interconnexions physiques, les taux de transmission, ou les types de signaux peuvent varier entre deux réseaux différents, néanmoins leurs topologies peuvent être identiques. La topologie physique d'un réseau est un problème particulier à la couche physique du modèle OSI.

Sous-sections

Topologies de réseau

Liens

Le médium de transmission utilisé pour relier des appareils afin de créer un réseau informatique inclut des cables électriques, fibres optiques et ondes radios sont appelés liens. Dans le modèle OSI, ceux-ci sont définis au niveau de la couche physique et de la couche liaison.

Topologies de réseau

Noeuds

Les noeuds d'un réseau sont les points de connexion du médium de transmission aux transmetteurs et receveurs des signaux électriques, optiques ou radio. Ils peuvent être :

Interfaces réseau : Un contrôleur d'interface réseau (NIC) est un matériel fournissant à un ordinateur la capacité d'accéder au média de transmission. Il a la capacité de traiter des informations réseaux de bas niveau. Le NIC répond au traffic qui lui est adressé via une adresse réseau.
Répéteurs et concentrateurs
Commutateurs : Transmet et filtre les datagrammes de la couche lien(2) du modèle OSI.
Routeurs : Transmet et filtre les paquets entre réseaux en traitant l'information de routage inclue dans le datagramme de la couche réseau(3) du modèle OSI.
Modems
Pare-feux

Topologies de réseau

Classification

L'étude de la topologie de réseau reconnait huit topologies basiques :

Point à point : La topologie réseau la plus simple avec un lien dédié entre deux points.
Daisy chain : Accomplie en connectant chaque machine en série à la suivante.
Bus : Chaque noeud est connecté via des connecteurs d'interface à un cable central unique.
Étoile : Chaque noeud périphérique est connecté à un noeud central appelé concentrateur ou commutateur.
Anneau : Daisy chain dans une boucle fermée.
Maille : Chaque noeud est interconnecté partiellement ou totalement avec les autres noeuds du réseau.
Arbre : Collection de réseaux étoiles arrangés hiérarchiquement.
Hybride : Combine plusieurs topologies réseaux.

Modèle OSI

Le modèle OSI (Open Systems Interconnection) est un modèle conceptuel qui caractérise et standardise les fonctions de communication d'un système de télécommunication ou informatique de manière détachée de la structure interne sous-jacente et de la technologie. Le but est de garantir l'interopérabilité des divers systèmes de communication à l'aide de protocoles de communication standards.

Le modèle sépare le flux des données dans un système de communication en sept couches abstraites, de l'implémentation physique de la transmission de bits à travers un médium de communication jusqu'à la plus haute représentation des données d'une application distribuée. Chaque couche intermédiaire fournit un classe de fonctions à la couche supérieure étant elle même servie par la couche en dessous d'elle. Ces classes de fonctionnalités sont réalisées dans le logiciel par des protocoles de communication standardisés.

Couche			Unité de protocole de données (PDU)	protocoles TCP/IP	Fonctions
Couches Hôtes	7	Application	Donnée	NFS	APIs de haut-niveau, partages de ressources, accès de fichiers distants
	6	Présentation		MIME-SSL-TLS-XDR	Traduction de données entre services réseau et une application ; encodage, compression et chiffrement
	5	Session		Sockets(établissement de session TCP/RTP/PPTP)	Gestion de sessions de communications, i.e., échange continu d'information sous la forme de mulptiples va-et-vient de transmissions entre deux noeuds
	4	Transport	Segment, Datagramme	TCP-UDP-SCTP-DCCP	Transmission fiables de segments de données entre points d'un réseau, incluant la segmentation, l'acquittement et le multiplexage
Couches médias	3	Réseau	Paquet	IP-IPsec-ICMP-IGMP-OSPF-RIP	Structurant et gérant un réseau multi-noeuds, incluant l'adressage, le routage et le contrôle du traffic
	2	Liaison	Trame	PPP-SLIP	Transmissions fiables de trames de données entre deux noeuds connectés par une couche physique
	1	Physique	Bit	Bluetooth-CAN bus-Ethernet Physical Layer-SMB-USB Physical Layer	Transmissions et Réceptions de flux de bits à travers un médium physique

Les protocoles de communication permettent à une entité sur un hôte d'interagir avec une entité correspondante sur la même couche dans un hôte différent. La définitions des services, comme le modèle OSI, décrit de manière abstraite la fonction de la couche (N-1) pour la couche (N), ou N est une des sept couches de protocoles opérante sur l'hôte local.

A chaque niveau N, deux entités d'appareils communicants (couches N pairs) échangent des unités de protocole de données (PDUs) par le moyen de la couche protocole N. Chaque PDU contient une charge, appelée unité de service de données (SDU), ainsi que les entêtes et pieds reliés au protocole.

Le processus de données entre deux appareils compatibles OSI communicants est le suivant :

La donnée à transmettre est composée au niveau de la couche la plus haute de l'appareil transmetteur (couche N) dans une unité de protocole de données.
Le PDU est passé à la couche N-1, ou il est reconnu comme une unité de service de données (SDU).
Au niveau de la couche N-1 le SDU est concaténé avec une entête, un pied, ou les deux, produisant un PDU de couche N-1. Il est alors envoyé à la couche N-2.
Le processus continue jusqu'à ce que la couche la plus basse soit atteinte, depuis laquelle la donnée est transmise à l'appareil récepteur.
Au niveau de l'appareil récepteur, la donnée est passée de la couche la plus basse à la couche la plus haute comme une suite de SDUs tandis quelle est pelée successivement de chaque entête ou pied de couche jusqu'à atteindre la couche la plus haute, où la donnée restante est consommée.

Architecture TCP/IP

La suite des protocoles internet est un modèle conceptuel et un ensemble de protocoles de communication utilisés par internet et les réseaux informatiques similaires. Elle est connue plus communément sous le nom d'architecture TCP/IP du fait que les protocoles sur lesquels elles s'appuie sont, le protocole de contrôle de transmission (TCP) et le protocole internet (IP). Son implémentation est une pile de protocoles.

La suite des protocoles internet fournit une communication de données bout en bout en spécifiant comment la donnée doit être empaquetée, adressée, transmise, routée et reçue. Cette fonctionnalité est organisée en quatre couches d'abstraction, qui classifient tous les protocoles rattachés en fonction de l'étendue de leur implication réseau. De la couche la plus basse à la couche la plus haute :

Liaison : contient des méthodes de communications pour des données appartenant à un unique segment réseau (ou lien).
Réseau : fournit l'interconnexion entre réseaux indépendants.
Transport : gère la communication d'hôte à hôte.
Application : fournit l'échange de données inter-processus pour les applications.

Les trois couches les plus hautes du modèle OSI, i.e. la couche application, présentation et session, ne sont pas distinguées séparément dans l'architecture TCP/IP. Néanmoins il n'y a aucune contrainte sur le fait que la pile de protocoles TCP/IP impose une architecture monolithique au dessus de la couche transport. Par exemple le protocole applicatif NFS fonctionne au dessus du protocole de présentation de représentation externe de données (XDR), qui lui-même s'appuie sur le protocole d'appel de procedures distant (RPC). RPC fournit une transmission fiable des enregistrements, de façon qu'il puisse utiliser le protocole de transport UDP de manière sûre.

La fonctionnalité de la couche session peut se retrouver dans des protocoles tels que HTTP et SMTP et de manière encore plus évidente dans Telnet et le protocole d'initialisation de session (SIP). La fonctionnalité de la couche session est également réalisée par la numérotation de port qui appartient à la couche transport de la suite TCP/IP. Les fonctions de la couche présentation est réalisée dans les applications TCP/IP à l'aide du standard MIME dans l'échange de données.

Protocoles

Sous-sections

Protocoles

Couche application

DHCP (Dynamic Host Configuration Protocol) : protocole des gestion réseau utilisé sur des réseaux IP, où un serveur DHCP assigne dynamiquement des adresses IP et autres paramètres de configuration réseaux à chaque appareil, de façon à ce qu'ils puissent communiquer avec d'autres réseaux IP. DHCP utilise le protocole UDP. (Port 67 pour le serveur, 68 pour le client)
DNS (Domain Name System) : système de nommage dynamique et hiérarchisé pour appareils, services et autres ressources connectées à Internet ou un réseau privé. DNS utilise UDP pour les requêtes de moins de 512 octets sinon il utilise TCP. (Port 53)
FTP (File Transfer Protocol) : protocole réseau standard utilisé pour le transfert de fichiers depuis un serveur à un client. FTP est construit sur un modèle d'architecture client-serveur en utilisant des connexions de contrôles et de données séparées entre le client et le serveur. Les utilisateurs FTP peuvent s'authentifier eux-mêmes à l'aide d'un protocole d'authentification en clair, généralement sous la forme d'un nom d'utilisateur et d'un mot de passe, mais ils peuvent se connecter de manière anonyme si le serveur est configuré en ce sens. Pour des transmission sécurisées protégeant le nom d'utilisateur et le mot de passe, et qui chiffrent le contenu, FTP est souvent sécurisé à l'aide de SSL/TLS (FTPS) ou bien remplacé par le protocole de transfert de fichier SSH (SFTP). Le client FTP initie des connexions TCP selon différents modes. (Port 21 pour le serveur)
HTTP (Hypertext Transfer Protocol) : protocole de la couche application pour systèmes d'information distribués, collaboratifs, hypermedia. HTTP est la base de la communication de données pour le World Wide Web, où des documents hypertextes incluent des hyper liens pour d'autres ressources que l'utilisateur peut accéder facilement, par exemple par un click utilisateur ou en tapant à l'écran dans un navigateur web. Le client initie une connexion TCP. (Port 80 ou 8080)
HTTPS (Hypertext Transfer Protocol Secure) : est une extension de HTTP. Il est utilisé pour une communication sécurisé à travers un réseau, et très largement répandu sur Internet. En HTTPS, le protocole de communication est crypté avec la sécurité de la couche transport (TLS) ou, précédemment la couche de sockets sécurisée (SSL). Le protocole est par conséquent désigné également par HTTP sur TLS, ou HTTP sur SSL. (Port 443)
IMAP (Internet Message Access Protocol) : est un protocole Internet standard utilisé par les clients emails pour récupérer les messages d'un serveur de messagerie à travers une connexion TCP/IP. (Port 143 et 993 pour IMAP sur SSL/TLS)
LDAP (Lightwight Directory Access Protocol) : est un protocole applicatif standard permettant d'accéder et de maintenir des répertoires de services d'information distribués à travers un réseau IP. Les répertoires de services jouent un rôle important dans le développement des applications intranets et Internet en permettant le partage d'informations à propos d'utilisateurs, de systèmes, de réseaux, de services, et d'applications à travers le réseau. LDAP utilise TCP et UDP. (Port 389 et 636 pour LDAP sur SSL/TLS)
NFS (Network File System) : est un protocole de système de fichiers distribué qui permet à un ordinateur client d'accéder à des fichiers à travers un réseau informatique. NFS comme de nombreux protocoles est construit au-dessus du protocole ONC/RPC. NFS 3 et 4 utilisent le protocole TCP. (Port 2049 pour NFSv4)
NTP (Network Time Protocol) : est un protocole qui permet de synchroniser l'horloge locale d'ordinateurs sur une référence d'heure. NTP utilse UDP. (Port 123)
ONC/RPC (Open Networking Computing/Remote Procedure Call) : est un système d'appel procedural distant. Il sérialise la donnée à l'aide de la représentation de données externes (XDR), qui permet également le transcodage pour l'accès sur de multiples plateformes. ONC délivre alors la charge XDR à l'aide des protocoles UDP ou TCP. (Port 111)
RIP (Routing Information Protocol) : est un protocole de routage IP de type vecteur s'appuyant sur l'algorithme de détermination des routes décentralisé Bellman-Ford. Il permet à chaque routeur de communiquer aux routeurs voisins. La métrique utilisée est la distance qui sépare un routeur d'un réseau IP déterminé quant au nombre de sauts. RIP utilise UPD. (Port 520)
SIP (Session Initiation Protocol) : est un protocole de signalisation utilisé pour initier, maintenir et terminer des sessions en temps réel, qui inclut des applications de messageries, vocales et vidéo. Les clients SIP utilisent TCP ou UDP. (Port 5060 et 5061 pour SIP sur SSL/TLS)
SMTP (Simple Mail Transfer Protocol) : est un protocole de communication pour la transmission de mail. Les serveurs mails et autres agents de transferts utilisent SMPT pour envoyer et recevoir des messages mails. Les serveurs SMTP utilisent le protocole TCP. (Port 25)
SNMP (Simple Network Management Protocol) : SNMP est un protocole Internet standard utiliser pour collecter et organiser l'information liée aux appareils sur des réseaux IP et pour modifier cette information afin de définir un nouvel état de fonctionnement. Les appareils qui typiquement supportent SNMP sont les modems, les routeurs, les switch, les serveurs, les postes de travail, les imprimantes, etc. SNMP est utilisé très largement pour la gestion et la surveillance réseau. SNMP expose la gestion des données sous la forme de variables sur les systèmes gérés organisées dans une base informationnelle de gestion (MIB) qui décrit le statut de la configuration système. Ces variables peuvent être elles même requêtées à distance (et, dans certaines circonstances manipulées) par des applications de gestion.
SSH (Secure Shell) : est un protocole réseau cryptographique pour des service réseaux sécurisés opérants sur des réseaux non-sécurisés. SSH utilise une architecture client-serveur en connectant un client SSH à un serveur. SSH utilise TCP. (Port 22)
TLS/SSL (Transport Layer Security/Secure Sockets Layer) : sont des protocoles cryptographiques permettant des communications sécurisées à travers un réseau. Le protocole TLS a pour but principal de garantir le caractère privé et l'intégrité de la donnée entre deux applications communicantes ou plus. Une connexion entre un client et un serveur doit quand elle est sécurisé par TLS avoir une ou plusieurs des propriétés suivantes :
- La connexion est privée (ou sécurisée) par un algorithme cryptographique symétrique pour chiffrer les données transmises. Les clefs de cette encryption symmétrique sont générées de manière unique et à chaque connexion, elle sont créées à partir d'un secret partagé négocié au début de la session. Le serveur et le client négocient les détails de l'algorithme cryptographique utilisé avant que le premier octet de données soit échangé. La négociation du secret partagé est à la fois sécurisé (ne peut être attaqué à l'aide d'un connexion intermédiaire) et fiable (aucun attaquant ne peut modifier les communications pendant le processus de négociation sans être détecté).
- L'identité des parties en communication peut être authentifiée via une clef cryptographique publique. Cette authentification est requise pour le serveur et optionnelle pour le client.
- La connexion est fiable du fait que chaque message transmis inclus un message de vérification d'intégrité en utilisant un message de code d'authentification pour prévenir les pertes non-détectées ou l'altération des données durant la transmission. En plus des propriétés ci-dessus, un configuration TLS peut fournir des propriétés de sécurisation supplémentaires telles que la confidentialité persistante, assurant qu'aucune découverte future des clefs cryptographiques ne puisse être utilisée pour déchiffrer une communication TLS enregistrée par le passé.
XDR (External Data Representation) : est un standard de format de sérialisation de données qui se retrouve dans de nombreux protocoles réseau.

Protocoles

Couche transport

TCP (Transmission Control Protocol) : est un des principaux protocoles de la suite des protocoles internet. Il a été développé à l'origine dans l'implémentation réseau initiale pour complémenter le protocole internet (IP). Par conséquent, la suite entière est communément connue sous le nom d'architecture TCP/IP. TCP fournit des flux d'octets vérifiés ordonnés et fiables entre applications s'exécutant sur des hôtes communiquant via un réseau IP. TCP est orienté connexion, et une connexion entre client et serveur est établie avant qu'une donnée puisse être envoyée. Le serveur doit écouter (ouverture passive) les requêtes de connexion des clients avant qu'une connexion soit établie. Un handshaking en trois temps (ouverture active), une retransmission, et une détection d'erreurs permet une grande fiabilité mais ajoute de la latence. Les applications qui ne requièrent pas un service de flux de données fiable peuvent utiliser le protocole datagramme utilisateur (UDP), qui fournit un service datagramme sans connexion qui priorise le temps à la fiabilité. TCP permet d'éviter la congestion réseau. Néanmoins, le TCP est vulnérable aux attaques de déni de service, au piratage de connexion, attaque par veto TCP et redémarrage de la connexion.
UDP (User Datagram Protocol) : est un des protocoles principals de la suite des protocoles internet. UDP utilise un modèle de communication sans connexion très simple à l'aide d'un minimum de mécanismes protocolaires. UDP fournit des sommes de vérification pour l'intégrité des données, et des numéros de ports pour adresser différentes fonctions au niveau de la source et de la destination du datagramme. Il ne contient pas de dialogue d'handshaking et par conséquent expose le programme utilisateur aux problèmes éventuels de fiabilité de la connexion réseau sous-jacente ; il n'y a aucune garantie de livraison, d'ordre ni de double protection. Si une correction d'erreur est nécessaire au niveau de l'interface réseau, une application utilisera plutôt le protocole de contrôle de transmission (TCP) ou le protocole de transmission de contrôle de flux (SCTP) implémentés pour cet usage. UDP est adapté aux usages où ni les contrôles ni les corrections d'erreurs ne sont nécessaires ou sont à la charge de l'application ; UDP évite la surchage d'un tel processus dans la pile de protocole. Les applications temporellement sensibles utilisent souvent UDP du fait qu'il est souvent préférable d'oublier des paquets plutôt que d'attendre des paquets retransmis, ce qui peut ne pas être une option dans un système temps réel.
DCCP (Datagram Congestion Control Protocol) : est un protocole orienté message. DCCP implémente une mise en place de connexion et une déconnexion fiables, une notification de congestion explicite (ECN), un contrôle de congestion, et des fonctionnalités de négociations.
SCTP (Stream Control Transmission Protocol) : est un protocole Internet standard il permet de garder les fonctionnalités orientées message du protocole datagramme utilisateur (UDP), tout en assurant une fiabilité et un ordonnancement des messages ainsi que des contrôles de congestion similaires au protocole de contrôle de transmission (TCP). Contrairement à UDP et TCP, le protocole permet le multi-homing et la redondance des chemins afin d'augmenter la résilience et la fiabilité.
RSVP (Ressource Reservation Protocol) : est un protocole utilisé pour réserver des ressources à travers un réseau en utilisant un modèle de services intégrés. RSVP opère à travers des réseaux IP et fournit une installation initiée par le receveur pour la réservation de ressources pour des flux de données unicast ou multicast. Il est similaire à un protocole de contrôle comme le protocole de messages de contrôles internet (ICMP) ou le protocole de gestion de groupes internet (IGMP).

Protocoles

Couche réseau

IPv4 (Internet Protocol v.4) : est le principal protocole de communication de la suite des protocoles internet en relayant des datagrammes à travers les frontières de réseaux. Ces fonctions de routage permettent l'agrégation de réseaux, qui établit essentiellement Internet. IP a pour fonction de livrer des paquets depuis un hôte source à un hôte destination uniquement via l'adresse IP contenue dans l'entête. A cette fin, IP définit des structures de paquets qui encapsulent la donnée à envoyer. Le protocole définit également les méthodes d'adressage utiliser pour étiqueter le datagramme des informations concernant la source et la destination. IPv4 utilise des adresses de 32-bits qui fournissent un peu plus de 4 milliards d'adresses. Néanmoins une grande partie de ces adresses est réservée pour des méthodes réseaux spéciales.
IPv6 (Internet Protocol v.6) : est la version la plus récente du protocole internet (IP). IPv6 a été développé pour résoudre le problème d'épuisement du nombre d'adresse IPv4. IPv6 utilise des adresses de 128-bits soit 3,4.10^38 adresses. Les deux protocoles ne sont pas interopérable, de fait aucune communication entre eux n'est possible. IPv6 fournit d'autres avantages techniques en plus du plus grand espace d'adressage. En particulier, il permet des méthodes d'allocation d'adresses hiérarchiques qui facilite l'agrégation de routes à travers Internet, limitant l'expansion des tables de routage. L'usage de l'adressage multicast est étendu et simplifié, il contient également d'autres optimisations pour la livraison de services. La mobilité des appareils, la sécurité, et la configuration ont été considérés lors de la création du protocole.
ICMP (Internet Control Message Protocol) : est un protocole de la suite des protocoles internet utilisé par les matériels d'interconnexion pour envoyer des messages d'erreurs et autres informations opérationnelles indiquant la réussite ou l'échec lors d'une communication avec une autre adresse IP. ICMP n'est pas utilisé pour envoyer des données applicatives entre systèmes (à part pour des outils de diagnostics tels ping et traceroute).
ECN (Explicit Congestion Notification) : est une extension du protocole internet (IP) et du protocole de contrôle de transmission (TCP). ECN permet la notification bout en bout d'une congestion réseau sans oublis de paquets. ECN est une fonctionnalité optionnelle.
IGMP (Internet Group Management Protocol) : est un protocole de communication entres hôtes et routeurs adjacents pour établir une appartenance à des groupes de multicasts. IGMP fait partie du multicast IP et permet au réseau de diriger les transmissions multicasts uniquement aux hôtes qui les ont demandées.
IPsec (Internet Protocol Secure) : est une suite de protocoles réseau sécurisée qui authentifie et chiffre les paquets de données pour fournir une communication sécurisée à travers un réseau IP. Elle est utilisé par les réseaux privés virtuels (VPN).

Protocoles

Couche Liaison

ARP (Address Resolution Protocol) : est un protocole de communication utilisé pour découvrir l'adresse de la couche liaison, telle que l'adresse MAC, associée à une une adresse de la couche internet donnée, typiquement, une adresse IP.
NDP (Neighbor Discovery Protocol) : est un protocole de la suite des protocoles internet utilisé avec le protocole internet version 6 (IPv6). Il est responsable de la récupération d'informations diverses requises pour la communication internet, telles que la configuration de connexions locales et les DNS et passerelles utilisées pour communiquer avec des systèmes plus lointains. Le protocole définit 5 paquets ICMPv6 différents pour des fonctions IPv6 similaires aux découvertes et redirection de routeurs d'ARP et de ICMP pour IPv4. Il fournit aussi de nombreuses améliorations en ce qui concerne la robustesse des livraisons de paquets.
OSPF (Open Shortest Path First) : est un protocole de routage pour les réseaux IP.
L2TP (Layer 2 Tunneling Protocol) : est un protocole de tunnellisation utilisé pour créer des réseaux privés virtuels (VPN).
PPP (Point-to-Point Protocol) : est un protocole de communication entre deux routeurs, sans hôte ni aucun autre réseautage entre. Il fournit une authentification de connexion, le chiffrement des transmissions et la compression de données.
STP (Spanning Tree Protocol) : est un protocole qui permet une topologie de réseaux Ethernet sans boucles. Le but étant de prévenir les tempêtes de broadcast. STP permet aussi d'inclure des liens redondants ce qui fournit une tolérance aux pannes en cas d'échec des liens actifs. STP créé un arbre couvrant qui caractérise la relation entre noeuds d'un réseau et désactive les liens qui ne font pas partie de l'arbre couvrant, laissant un unique lien actif entre 2 noeuds.

VLAN

Les LANs virtuels permette de subdiviser un LAN. Linux peut accepter un traffic marqué VLAN et présenter chaque identifiant VLAN comme une interface réseau différente.

Les VLANs permettent :

Séparation des flux
Segmentation, réduction d'un domaine de broadcast
Isolation pour améliorer la sécurité

VPN

Un réseau privé virtuel (VPN) étend un réseau privé à travers un réseau public et permet aux utilisateurs d'envoyer et de recevoir des données à travers des réseaux publics partagés comme si les ordinateurs étaient directement connectés au réseau privé. Les bénéfices d'un VPN incluent une plus grande fonctionnalité, sécurité, et améliore la gestion du réseau privé. Il fournit un accès à des ressources inaccessibles sur le réseau public et est généralement utilisé pour les télétravailleurs. Le chiffrement est commun bien qu'il ne soit pas une partie inhérente d'une connexion VPN.

Un VPN est créé en établissant une connexion virtuelle point à point via l'usage de circuits dédiés ou à l'aide de protocoles tunnels à travers des réseaux existants. Un VPN disponible depuis un Internet public peut fournir certains bénéfices d'un WAN. Pour l'utilisateur, les ressources disponibles dans un réseau privé peuvent être accédées à distance.

Proxy

Dans un réseau informatique, un serveur proxy est un serveur d'application agissant comme intermédiaire entre un client requêtant une ressource et le serveur fournissant cette ressource.

A l'instar d'une connexion directe au serveur, le client dirige cette requête au serveur proxy, qui évalue la requête et traite les transactions réseaux requises. C'est une méthode qui permet de simplifier ou de contrôler la complexité de la requête, ou fournir d'autres avantages tels que la répartition de charge, l'anonymisation ou la sécurité. Les proxys ont été conçus afin d'ajouter une structure et une encapsulation aux systèmes distribués. Un serveur proxy agit alors à la place du client quand celui-ci demande le service, masquant potentiellement la véritable origine de la requête au serveur de ressources.

Un serveur proxy peut se situer sur l'ordinateur local de l'utilisateur, ou à n'importe quel point entre l'ordinateur de l'utilisateur et les serveurs de destination sur Internet. Un serveur proxy qui relaye des requêtes et des réponses non modifiées est appelé une passerelle. Un forward proxy est un proxy tourné vers Internet qui sert à collecter des données d'un grand nombre de sources (dans la plupart des cas n'importe où sur Internet). Un reverse proxy est généralement un proxy tourné vers un réseau interne privé utilisé comme front-end afin de contrôler et de protéger l'accès à un serveur. Un reverse proxy traite aussi typiquement différentes tâches tels que la répartition de charge, l'authentification, le déchiffrement et la mise en cache.

NAS

Un stockage attaché réseau (NAS) est un serveur de stockage informatique de niveau fichier (à l'instar du stockage de niveau bloc) connecté à un réseau informatique fournissant un accès aux données à un groupe de clients hétérogènes. Un NAS est spécialisé dans le service de fichiers soit par son matériel, son logiciel ou sa configuration. Il est souvent fabriqué en tant qu'application matérielle - généralement une réalisation fonctionnelle d'ordinateur spécialisé. Les systèmes NAS contiennent un ou plusieurs disques de stockage, souvent arrangés logiquement dans des conteneurs de stockage redondants ou RAID. Ils fournissent un accès aux fichiers en utilisant des protocoles de partage réseau tels que NFS ou SMB. Les bénéfices potentiels d'un NAS dédié, comparé à un serveur classique servant également des fichiers sont :

Un accès aux données plus rapide
Une facilité d'administration
Une configuration simplifiée.

SAN

Une aire de stockage réseau (SAN) ou stockage réseau est un réseau informatique qui fournit un accès à un stockage de données niveau bloc consolidé. Les SANs sont utilisés principalement afin d'accéder à des périphériques de stockage de données, tels que des baies de disques ou des bibliothèques de bandes magnétiques, depuis des serveurs, de manière à ce que ces périphériques apparaissent au système d'exploitation comme des stockages attachés directement. Un SAN est généralement un réseau dédié aux périphériques de stockages inaccessibles depuis le réseau local (LAN).

MIB

Une base de gestion d'information (MIB) est une base de données utilisée pour gérer les entités d'un réseau de communication. La plupart du temps, elle est associée au protocole SNMP, le terme est également utilisé plus génériquement dans les contextes tels que les modèles de gestion réseau OSI/ISO. Bien que faisant référence à l'ensemble de la collection des informations de gestion disponible sur une entité, le terme est souvent utilisé pour faire référence à un sous ensemble, plus correctement appelé module MIB.

La base de donnée est hiérarchique et chaque entrée est adressée à travers un identifiant d'objet (OID).

Active Directory

Un Active Directory (AD) est un service de répertorisation (nommage) développé par Microsoft pour les domaines réseaux Windows. Il est inclus dans la plupart des systèmes d'exploitation Windows Server comme un ensemble de processus et de services. Initialement, Active Directory était utilisé uniquement pour une gestion du domaine centralisée. Néanmoins Active Directory est finalement devenu un nom parapluie pour un large panel de services de relation/identité basé répertoire.

Un serveur exécutant le service de domaine active directory (AD DS) est appelé le contrôleur de domaine. Il authentifie et autorise tous les utilisateurs et ordinateurs dans un domaine Windows de type réseau, gérant et appliquant les politiques de sécurité pour tous les ordinateurs, installant et mettant à jour le logiciel. Un Active Directory permet la gestion et le stockage d'information, fournit des mécanismes d'autorisation et d'authentification, et établit un cadre pour déployer d'autres services liés : Service de certification, service de fédération d'Active Directory, service LDAP et service de gestion des droits.

Active Directory utilise LDAP, la version Microsoft de Kerberos et DNS.

Samba

Samba est une réimplémentation libre du protocole réseau propriétaire SMB. Samba fournit des services fichiers et d'impression pour divers clients Microsoft Windows et peut s'intégrer avec un serveur de domaine Microsoft Windows, soit en tant que contrôleur de domaine (DC) soit en tant que membre de domaine. Depuis la version 4, il supporte les domaines Microsoft Windows NT et Active Directory.

Logiciels

Introduction

Ce chapitre traite de la partie logiciels du programme PSE.

Sections

Architecture logicielle

Sous-sections

Architecture logicielle

Client serveur

Le modèle client serveur est une structure d'application distribué qui sépare les tâches ou charges de travail entre fournisseurs de ressource ou service, appelés serveurs, et les demandeurs de ce service, appelés clients. Les clients et les serveurs communiquent souvent à travers un réseau informatique sur des matériels séparés, mais les deux peuvent également se trouver sur la même machine. Un serveur hôte exécute un ou plusieurs programmes serveurs, qui partagent leurs ressources avec des clients. Un client ne partage habituellement aucune de ses ressources, mais demande le contenu ou le service au serveur. Par conséquent, les clients initient la session de communication avec les serveurs, qui attendent les requêtes entrantes.

La caractéristique client-serveur décrit la relation de programmes coopérants dans une application. Le composant serveur fournit une fonction ou un service à un ou plusieurs clients, qui initient des requêtes pour de tels services. Les serveurs sont classifiés en fonction du service qu'ils fournissent. Par exemple, un serveur web, sert des pages web pour un serveur de fichier qui sert des fichiers informatiques. Une ressource partagée peut être n'importe quel composant électronique ou logiciel informatique du serveur, des programmes et des données aux processeurs et périphériques de stockages. Le partage des ressources d'un serveur constitue un service.

La condition si un ordinateur est un client, un serveur ou les deux, est déterminé par la nature de l'application qui demande les fonctions du service. Par exemple, un seul ordinateur peut exécuter un serveur web et un logiciel serveur de fichier en même temps pour servir différentes données aux clients effectuant diverses requêtes. Le logiciel client peut aussi communiquer avec un logiciel serveur sur le même ordinateur. La communication entre serveurs tel que la synchronisation de données, est quelques fois appelée communication inter-serveur ou serveur à serveur.

En général, un service est une abstraction de ressources informatiques et un client n'a pas à être concerné du comment le serveur procède tandis qu'il exécute la requête et livre la réponse. Le client doit uniquement comprendre la réponse selon les protocoles applicatifs connus, i.e. le contenu et le formatage de la donnée pour le service requis.

Les clients et les serveurs échangent des messages à l'aide du motif de messagerie requête-réponse. Le client envoie une requête, et le serveur retourne une réponse. Cet échange de message est un exemple de communication inter-processus. Pour communiquer, les ordinateurs doivent avoir un langage commun, et doivent suivre des règles communes qui doivent être définis dans le protocole de communications. Tous les protocoles client-serveur opère au niveau de la couche application. Le protocole de la couche application définit des motifs basiques de dialogue. Pour formaliser un peu plus loin l'échange de données, le serveur peut implémenter une interface de programmation applicative (API). L'API est une couche d'abstraction permettant d'accéder un service. En restreignant la communication à des contenus formatés spécifiquement, cela facilite l'analyse syntaxique. En rendant l'accès à la donnée abstrait, on facilite l'échange de données inter-plateformes.

Un serveur peut recevoir de multiples clients distincts sur une période de temps très courte. Un ordinateur peut uniquement exécuter un nombre limité de tâches à la fois, et s'appuie sur l'ordonnanceur système pour prioriser les requêtes entrantes des clients pour les traiter. Afin de prévenir les abus et une disponibilité maximale, le logiciel serveur peut limiter la disponibilité aux clients. Les attaques de déni de service sont conçues pour exploiter les obligations du serveur à traiter des requêtes en le surchargeant avec un taux de requêtes excessif. Le chiffrement doit être mis en place si des données sensibles sont communiquées entre le client et le serveur.

Architecture logicielle

Trois niveaux

Une architecture à trois niveaux ou architecture trois tiers ajoute un niveau supplémentaire à l'architecture à 2 niveaux, permettant de spécialiser les serveurs dans une tâche précise, ce qui donne un avantage de flexibilité, de sécurité et de performance :

un client qui demande une ressource via une interface utilisateur chargée de la présentation de la ressource ;
un serveur d'application (appelé middleware) qui fournit la ressource, mais en faisant appel aux ressources d'un autre serveur ;
un serveur de données qui fournit au serveur d'application les ressources requises pour répondre au client.

Architecture logicielle

N-tiers

Une architecture à N niveaux ou architecture N-tiers n'ajoute pas de niveaux supplémentaires à l'architecture à 3 niveaux mais introduit la notion d'objets qui offre la possibilité de distribuer les services entre les 3 niveaux selon N couches, permettant ainsi de davantage spécialiser les serveurs.

Architecture logicielle

Modèle-Vue-Contrôleur

Modèle-vue-contrôleur est un motif d'architecture typique utilisé afin de développer des interfaces utilisateur qui sépare la logique liée du programme en trois éléments inter-connectés. Cela est réalisé en séparant les représentations internes de l'information des façons dont l'information est présentée et acceptée par l'utilisateur.

Beaucoup de langages de programmation disposent de quadriciels MVC qui facilitent son implémentation.

Les trois composants du motifs sont :

Le modèle : Le composant central. Il s'agit de la structure de données dynamique de l'application, indépendant de l'interface utilisateur. Il gère directement la donnée, la logique et les règles de l'application. Il reçoit l'entrée utilisateur du contrôleur.
La vue : Une représentation de l'information (un graphique, un diagramme ou une table). Plusieurs vues de la même information sont possibles. C'est la présentation du modèle.
Le contrôleur : Accepte et optionnellement valide les entrées pour le modèle. Il permet l'exécution des intérations sur les objets du modèle de données.

Haute disponibilité

La haute disponibilité est une caractéristique d'un système qui vise à assurer un certain niveau de performance opérationnelle, généralement l'uptime (ou durée de fonctionnement), durant une période plus longue que celle attendue habituellement.

Il existe trois principes de conception système en ingénierie de fiabilité permettant d'atteindre une haute disponibilité :

L'élimination des points de défaillances uniques. Cela signifie ajouter ou construire une redondance dans le système pour que la défaillance d'un composant ne signifie pas la défaillance du système en entier.
Fiabilité des points de croisements. Au niveau des systèmes redondants, le point de croisement lui-même tend à devenir un point de défaillance unique. Les systèmes fiables doivent fournir des points de croisement fiables.
Détection des défaillances lors de leurs occurrences. Si les deux principes ci-dessus sont observés, alors un utilisateur pourra ne jamais voir de défaillance - mais l'activité de maintenance le doit.

Langages de présentation

Voir HTML/CSS.

Construction et automatisation

Sous-sections

Construction et automatisation

Maven

Maven est un outil d'automatisation de construction utilisé généralement pour les projets Java. Maven peut également être utiliser pour construire et gérer des projets dans d'autres langages.

Maven aborde deux aspects de la construction de logiciel : comment le logiciel est construit, et ses dépendances. Contrairement à des outils précédents tels que Ant, il utilise des conventions pour la procédure de construction. Seules les exceptions ont besoin d'être spécifiées. Un fichier XML décrit le projet logiciel en cours de construction, ces dépendances sur d'autres modules externes et composants, l'ordre de construction, les répertoires, et plugins requis. Il embarque des cibles prédéfinies pour exécuter certaines tâches bien définies telles que la compilation de code et la construction de paquets. Maven télécharge dynamiquement des bibliothèques Java et des plugins Maven d'un ou plusieurs dépôts et les stocke dans un cache local. Ce cache local d'artefacts téléchargés peut également être mis à jour à l'aide d'artefacts créés par des projets locaux. Les dépôts publics peuvent également être mis à jour.

Maven est construit en utilisant une architecture de plugins qui permet de faire usage de n'importe quelle application contrôlable via l'entrée standard.

Construction et automatisation

Jenkins

Jenkins est un serveur d'automatisation open source. Il aide à automatiser certaines parties du développement logiciel lié à la construction, le test, et le déploiement, facilitant l'intégration en continu (CI) et la livraison en continu (CD). C'est un système serveur qui fonctionne dans des conteneurs servlets tels que Tomcat. Il supporte des outils de contrôle de version et peut exécuter des projets basés sur Ant et Maven ainsi que des scripts shell arbitraires.

Construction et automatisation

Cobbler

Cobbler est un serveur fournisseur linux qui facilite et automatise l'installation système via le réseau de multiples systèmes d'exploitations informatiques depuis un point central en utilisant des services tels que DHCP, TFTP et DNS. Il peut être configuré pour l'environnement d'exécution pré-démarrage (PXE), réinstallations, et invités virtuels utilisant Xen, KVM ou VMware. Cobbler interagit avec le programme koan pour le support de la réinstallation et de la virtualisation. Koan et Cobbler utilisent libvirt pour s'intégrer avec différents logiciels de virtualisation.

Construction et automatisation

Puppet

Puppet est un outil logiciel de gestion de configuration qui inclut son propre langage de langage déclaratif pour décrire une configuration système. C'est une solution orienté modèle qui nécessite une connaissance limitée en programmation pour son usage.

Construction et automatisation

Ansible

Ansible est un outil logiciel open source de déploiement d'application, gestion de configuration et fournisseur permettant l'infrastructure as code (Iac). Il inclut son propre langage déclaratif pour décrire des configurations systèmes. Ansible est sans agent, se connectant temporairement via SSH pour faire ses opérations.

Construction et automatisation

Vagrant

Vagrant est un produit logiciel open source pour construire et maintenir des environnements de développement logiciels virtuels portables (VirtualBox, KVM, Hyper-V, conteneurs Docker, VMware, et AWS). Il essaie de simplifier la gestion de la configuration de virtualisation afin d'augmenter la productivité de développement.

Construction et automatisation

Terraform

Terraform est un outil logiciel open source d'infrastructure as code. Les utilisateurs définissent et fournissent l'infrastructure en utilisant un langage de configuration déclaratif ou du JSON.

Métrologie et supervision Nagios

Nagios Core est une application informatique open source qui supervise des systèmes, réseaux et infrastructure. Nagios offre des services de supervision et d'alerte pour des serveurs, switch, applications et services. Il alerte les utilisateurs quand les choses se passent mal et les alerte une seconde fois lorsque le problème a été résolu.

Nagios fournit :

Supervision de services réseaux (SMTP, POP3, HTTP, NNTP, ICMP, SNMP, FTP, SSH)
Supervision de ressources hôte (charge processeur, utilisation du disque, logs système) à l'aide d'agents de supervision.
Supervision de matériels (sondes de température, alarmes, etc.) ayant la capacité d'envoyer les données collectées via un réseau à des plugins écrits spécifiquement.
Supervision via des scripts exécutés à distance via l'exécuteur de plugin à distance Nagios.
Supervision à distance via des tunnels chiffrés SSL ou SSH.
Un simple plugin qui permet aux utilisateurs de facilement développer leurs propres vérifications de services selon leurs besoins, en utilisant les outils de leur choix (scripts shell, C++, Perl, Ruby, Python, PHP, C#, etc.)
Des plugins de mise en forme des données disponibles
Vérification de services parallélisée etc.

Environnement

Introduction

Ce chapitre traite de la partie environnement du système d'information du programme PSE.

Sections

Normalisation

Sous-sections

ITIL
COBIT

Normalisation

ITIL

ITIL (Information Technology Infrastructure Library) est un ensemble d'ouvrages recensant les bonnes pratiques de gestion du système d'information.

C'est un référentiel méthodologique très large qui aborde les sujets suivants :

Comment organiser un système d'information ?
Comment améliorer l'efficacité d'un système d'information ?
Comment réduire les risques ?
Comment augmenter la qualité des services informatiques ?

Les recommandations d'ITIL positionnent des blocs organisationnels et des flux d'information.

Normalisation

COBIT

COBIT (Control Objectives for Information and related Technology) est un référentiel de bonnes pratiques d'audit informatique et de gouvernance des systèmes d'information.

Notions générales sur le droit de l'informatique

Sous-sections

Notions générales sur le droit de l'informatique

Protection des données individuelles

Le règlement général sur la protection des données (RGPD) est un règlement de l'Union européenne qui constitue le texte de référence en matière de protection des données à caractère personnel. Il renforce et unifie la protection des données pour les individus au sein de l'Union européenne.

Les principaux objectifs du RGPD sont d'accroître à la fois la protection des personnes concernées par un traitement de leurs données à caractère personnel et la responsabilisation des acteurs de ce traitement. Ces principes pourront être appliqués grâce à l'augmentation du pouvoir des autorités de contrôle.

Notions générales sur le droit de l'informatique

L'usage de la messagerie

Notions générales sur le droit de l'informatique

Rôle de la CNIL

La Commission nationale de l'informatique et des libertés (CNIL) est une autorité administrative indépendante française. La CNIL est chargée de veiller à ce que l'information soit au service du citoyen et qu'elle ne porte atteinte ni à l'identité humaine, ni aux droits de l'homme, ni à la vie privée, ni aux libertés individuelles ou publiques.

Missions Principales

Informer : La CNIL est investie d'une mission générale d'information des personnes sur leurs droits et leurs obligations. Elle aide les citoyens dans l'exercice de leurs droits. Elle établit chaque année un rapport public rendant compte de l'exécution de sa mission.
Réguler : La CNIL régule et recense les fichiers, autorise les traitements les plus sensibles avant leur mise en place. L'avis de la CNIL doit d'ailleurs être sollicité avant toute transmission au Parlement d'un projet de loi relatif à la protection des données personnelles ; il doit aussi être sollicité par le Gouvernement avant d'autoriser les traitements intéressant la sûreté de l'État, la défense ou la sécurité publique. La CNIL établit des normes simplifiées, afin que les traitements les plus courants fassent l'objet de formalités allégées. Elle peut aussi décider de dispenser de toute déclaration des catégories de traitement sans risque pour les libertés individuelles. Elle agit par voie de recommandations.
Protéger : La CNIL doit veiller à ce que les citoyens soient informés des données contenues dans les traitements les concernant et qu'ils puissent y accéder facilement. Elle reçoit et instruit les plaintes des personnes qui rencontrent des difficultés à exercer leurs droits. Elle exerce, pour le compte des citoyens qui le souhaitent, l'accès aux fichiers intéressant la sûreté de l'État, la défense et la sécurité publique, notamment des services de renseignements de la police judiciaire.
Contrôler : La CNIL vérifie que la loi est respectée en contrôlant les traitements informatiques. Elle peut de sa propre initiative se rendre dans tout local professionnel et vérifier sur place et sur pièce les fichiers. La Commission use de ses pouvoirs d'investigation pour instruire les plaintes et disposer d'une meilleure connaissance de certains fichiers. La CNIL surveille par ailleurs la sécurité des système d'information en s'assurant que toutes les précautions sont prises pour empêcher que les données ne soient déformées ou communiquées à des personnes non autorisées.
Sanctionner : Lorsqu'elle constate un manquement à la loi, la CNIL peut, après avoir mis en demeure les intéressés de mettre fin à ce manquement, prononcer diverses sanctions.
Anticiper : La CNIL doit s'attacher à comprendre et anticiper les développements des technologies de l'information afin d'être en mesure d'apprécier les conséquences qui en résulte pour l'exercice des droits et libertés. Elle propose au Gouvernement les mesures législatives ou réglementaires de nature à adapter la protection des libertés et de la vie privée à l'évolution des techniques.

Droits

Droit d'information : Toute personne peut s'adresser directement à un organisme pour savoir si elle est fichée ou pas.
Droit d'accès : Sauf pour les fichiers relevant du droit d'accès indirect, toute personne peut, gratuitement, sur simple demande avoir accès à l'intégralité des informations la concernant sous une forme accessible. Elle peut également obtenir copie moyennant le paiement, le cas échéant, des frais de reproduction.
Droit de rectification et de radiation : Toute personne peut demander directement que les informations détenues sur elles soient rectifiées (si elles sont inexactes), complétées ou clarifiées (si elles sont incomplètes ou équivoques), mises à jour (si elles sont périmées) ou effacées (si ces informations ne pouvaient pas être légalement collectées par l'organisme concerné).
Droit d'opposition : Toute personne peut s'opposer à ce qu'il soit fait un usage des informations la concernant à des fins publicitaires ou de prospection commerciale ou que ces informations la concernant soient cédées à des tiers à telles fins. La personne concernée doit être mise en mesure d'exercer son droit d'opposition à la cession de ses données à des tiers dès leur collecte.
Droit d'accès indirect : Toute personne peut demander à la CNIL de vérifier les informations la concernant éventuellement enregistrées dans des fichiers intéressant la sûreté de l'État, la défense, ou la sécurité publique (droit d'accès indirect). La CNIL mandate l'un de ses membres magistrats (ou anciens magistrats) afin de vérifier leur rectification ou leur suppression. Avec l'accord du responsable du traitement, les information concernant une personne peuvent lui être communiquées.

Obligation des responsables du traitement

Notifier la mise en oeuvre du fichier de ses caractéristiques à la CNIL, sauf cas de dispense prévus par la loi ou par la CNIL.
Mettre les personnes concernées en mesure d'exercer leur droits en les informant.
Assurer la sécurité des informations afin d'empêcher qu'elles soient déformées, endommagées ou que des tiers non autorisés n'y ait accès. La loi prévoit une obligation de mesures techniques et d'organisation, un obligation de moyens, dénuée d'obligation de résultat.
Se soumettre aux contrôles et vérifications sur place de la CNIL et répondre à toute demande de renseignement qu'elle formule dans le cadre de ses missions.

Notions générales sur le droit de l'informatique

Licences

Une licence de logiciel est un contrat par lequel le titulaire des droits d'auteur sur un programme informatique définit avec son cocontractant (exploitant ou utilisateur) les conditions dans lesquelles ce programme peut être utilisé ou modifié.

Une licence peut être :

nominative ou fixe : conçue pour être installée sur un ordinateur particulier.
flottante : fonctionne à l'aide d'un serveur de licences. Celui-ci décompte le nombre de licences utilisées à un instant T sur le réseau.
shareware : ou partagiciel, attribue un droit temporaire et/ou avec des fonctionnalités limitées d'utilisation. Après cette période d'essai, l'utilisateur devra rétribuer l'auteur pour continuer à utiliser le logiciel ou avoir accès à la version complète.
libre : qui donnent le droit d'usage de l'oeuvre, d'étude de l'oeuvre pour en comprendre le fonctionnement ou l'adapter à ces besoins, de modification et de redistribution de l'oeuvre et des oeuvres dérivées, c'est à dire sa diffusion à d'autres usages, y compris commercialement.
propriétaire : ne permet pas légalement ou techniquement, ou par quelque autre moyen que ce soit d'exercer simultanément les quatre libertés logicielles.

Organisation du travail

Méthode agile

Dans le développement logiciel, les pratiques Agile incluent :

une découverte des besoins,
des solutions d'amélioration à travers l'effort collaboratifs d'équipes transverses et auto-organisées avec leurs clients/utilisateurs finaux,
une planification adaptative,
un développement évolutionnaire,
une livraison rapide,
une amélioration en continu,
des réponses flexibles aux changement de besoins,
une capacité et une compréhension des problèmes à résoudre.

Organisation du travail

Devops

Devops est un ensemble de pratiques qui combine développement logiciel (Dev) et informatique technique opérationnelle (Ops). Il a pour but de réduire la durée des cycles de vie des développements systèmes et de permettre une livraison en continu (CD) de logiciel de qualité. Devops est complémentaire du développement logiciel Agile ; certains aspects sont issus de la méthodologie Agile.

Du fait que Devops se veut être une méthode de travail transverse, ceux qui pratiquent la méthodologie utilisent différents ensembles d'outils - appelé chaîne d'outil - plutôt qu'un outil unique. Ces chaînes d'outils doivent correspondre à l'une ou plusieurs des catégories suivantes, qui reflètent les aspects clefs des processus du développement et de la livraison.

Code - le développement et la vérification du code, les outils de gestion du code source, la fusion de code.
Construction - les outils d'intégration continue, le statut de construction.
Test - les outils de tests en continu qui fournissent un retour rapide sur les risques opérationnels.
Empaquetage - Dépôt logiciel, mise à disposition de l'application pré-déploiement.
Publication - gestion des changements, approbation et automatisation des publications.
Configuration - configuration et gestion d'infrastructure, outils d'infrastructure as code.
Surveillance - applications de surveillance des performances, expérience de l'utilisateur final.

Fonctions de PSE

DISI

Veiller à l'optimisation des performances des matériels et à celle du taux de disponibilité du système informatique.
Assurer la gestion des sécurités d'accès et des sauvegardes, ainsi que l'administration des bases de données.
Assurer la mise en oeuvre d'automates d'exploitation et de programmes utilitaires.
Exercer des missions d'assistance et de conseil des équipes d'exploitation.
Exercer un support technique pour les cellules d'assistance directe et pour l'administration des configurations informatiques implantées dans les services locaux.

Service centraux

Participer à la conception technique des systèmes de données et de traitements afin d'optimiser l'usage du système informatique et préparer les modalités de mise en exploitation.
Procéder aux études préalables, aux acquisitions de matériels informatiques et de logiciels système.
Participer aux travaux sur les systèmes gros systèmes, X86, plateformes virtualisées et Cloud.
Gérer les techniques de cette exploitation ainsi que le suivi et l'environnement de cette exploitation.

Plan de secours

Sous-sections

Plan de secours

Plan de continuité d'activité

Un plan de continuité d'activité (PCA), a pour but de garantir la survie de l'entreprise en cas de sinistre important touchant le système informatique. Il s'agit de redémarrer l'activité le plus rapidement possible avec le minimum de perte de données. Ce plan est un des points essentiels de la politique de sécurité informatique d'une entreprise.

Pour qu'un plan de continuité soit réellement adapté aux exigences de l'entreprise, il doit reposer sur une analyse de risque et une analyse d'impact :

L'analyse de risque débute par une identification des menaces sur l'informatique. Les menaces peuvent être internes ou externes à l'entreprise. On déduit ensuite le risque qui découle des menaces identifiées ; on mesure l'impact possible de ces risques. Enfin, on décide de mettre en oeuvre des mesures d'atténuation des risques en se concentrant sur ceux qui ont un impact significatif. Par exemple, si le risque de panne d'un équipement risque de tout paralyser, on installe un équipement redondant. Les mesures d'atténuation de risque qui sont mises en oeuvre diminuent le niveau de risque, mais elles ne l'annulent pas : il subsiste toujours un risque résiduel, qui sera couvert soit par le plan de continuité, soit par d'autres moyens (assurance, voire acceptation du risque).
L'analyse d'impact consiste à évaluer quel est l'impact d'un risque qui se matérialise et à déterminer à partir de quand cet impact est intolérable, généralement parce qu'il met en danger les processus essentiels (donc, la survie) de l'entreprise.L'analyse d'impact se fait sur la base de désastres : on considère des désastres extrêmes voire improbables (par exemple, la destruction totale du bâtiment) et on détermine les impacts financiers, humains, légaux, etc., pour des durées d'interruption de plus en plus longues jusqu'à ce qu'on atteigne l'impact maximal tolérable. Le résultat principal de l'analyse d'impact est donc une donnée temporelle : c'est la durée maximale admissible d'une interruption de chaque processus de l'entreprise. En tenant compte des ressources informatiques (réseaux, serveurs, PCs, etc.) dont chaque processus dépend, on peut déduire le temps maximal d'indisponibilité de chacune de ces ressources, en d'autres termes, le temps maximal après lequel une ressource informatique doit avoir été remise en fonction.

Une analyse de risque réussie est le résultat d'une action collective impliquant tous les acteurs du système d'information : techniciens, utilisateurs et managers.

Il existe plusieurs méthodes pour assurer la continuité de service d'un système d'information. Certaines sont techniques (choix des outils, méthodes de protection d'accès et de sauvegarde des données), d'autres reposent sur le comportement individuel des utilisateurs (extinction des postes informatiques après usage, utilisation raisonnable des capacités de transfert d'informations, respect des mesures de sécurité); sur des règles et connaissances collectives (protection incendie, sécurité d'accès aux locaux, connaissance de l'organisation informatique interne de l'entreprise) et de plus en plus sur des conventions passées avec des prestataires (copie des programmes, mise à disposition de matériel de secours, assistance au dépannage).

Les méthodes se distinguent entre préventives (éviter la discontinuité) et curatives (rétablir la continuité après un sinistre). Les méthodes préventives sont souvent privilégiées, mais décrire les méthodes curatives est une nécessité car aucun système n'est fiable à 100%.

La préservation des données passe par des copies de sauvegarde régulières. Il est important de ne pas stocker ces copies de sauvegarde à côté du matériel informatique, voire dans la même pièce car elles disparaîtraient en même temps que les données à sauvegarder en cas d'incendie, de dégât des eaux, de vol, etc. Lorsqu'il est probable que les sauvegardes disparaissent avec le matériel, le stockage des copies de sauvegarde peut alors être nécessaire dans un autre lieu différent et distant.

L'analyse d'impact a fourni des exigences exprimées en temps maximal de rétablissement des ressources après un désastre (RTO : Recovery Time Objective ou Durée maximale d'interruption admissible) et la perte maximale de données (RPO : Recovery Point Objective ou Perte de données maximale admissible). La stratégie doit garantir que ces exigences seront observées.

Il s'agit de disposer d'un système informatique équivalent à celui pour lequel on veut limiter l'indisponibilité : ordinateurs, périphériques, systèmes d'exploitation, programmes particuliers, etc. Une des solutions consiste à créer et maintenir un site de secours, contenant un système en ordre de marche capable de prendre le relais de système défaillant. Selon que le système de secours sera implanté sur le site d'exploitation ou sur un lieu géographiquement différent, on parlera d'un secours in situ ou déporté.

Pour répondre aux problématiques de recouvrement de désastre, on utilise de plus en plus fréquemment des sites délocalisés, c'est à dire physiquement séparés des utilisateurs de plusieurs centaines de mètres à plusieurs centaines de kilomètres : plus le site est éloigné, moins il risque d'être touché par un désastre affectant le site de production. Mais la solution étant d'autant plus chère, car la bande passante qui permet de transférer des données d'un site vers l'autre est alors généralement plus coûteuse et risque d'être moins performante. Cependant la généralisation des réseaux longues distances et la baisse des coûts de transmission rendent moins contraignante la notion de distance : le coût du site ou la compétence des opérateurs (leur capacité à démarrer le secours rapidement et de rendre l'accès aux utilisateurs) sont d'autres arguments de choix.

Les sites de secours (in situ ou déportés) se classent selon les types suivants :

salle blanche (une salle machine protégée par des procédure d'accès particulières, généralement secourue électriquement). Par extension on parle de salle noire pour une salle blanche entièrement pilotée à distance, sans aucun opérateur à l'intérieur.
site chaud : site de secours où l'ensemble des serveurs et autres systèmes sont allumés, à jour, interconnectés, paramétrés, alimentés à partir des données sauvegardées et prêt à fonctionner. Le site doit aussi fournir l'ensemble des infrastructures pour accueillir l'ensemble du personnel à tout moment et permet une reprise de l'activité dans des délais relativement courts (quelques heures). Un tel site revient quasiment à doubler les capacités informatiques de l'entreprise (on parle de redondance) et présente donc un poids budgétaire non négligeable.
site froid : site de secours qui peut avoir une autre utilisation en temps normal. Les serveurs et autres systèmes sont stockés mais non installés, connectés, etc. Lors d'un sinistre, un important travail doit être effectué pour mettre en service le site ce qui conduit à des temps de reprise long (quelques jours). Mais sont coût de fonctionnement, hors période d'activation est faible voire nul.

Il est aussi possible d'utiliser des systèmes distribués sur plusieurs sites (diminution du risque de panne par effet de foisonnement) ou un site de secours mobile.

Plus les temps de rétablissement garantis sont courts, plus la stratégie est coûteuse. Il faut donc choisir la stratégie qui offre le meilleur équilibre entre le coût et la rapidité de reprise.

D'autre part pour des problème de haute disponibilité on a recours aussi à de la redondance mais de manière plus locale.

Doublement d'alimentation des baies des serveurs
Redondance des disques en utilisant la technologie RAID
Redondance de serveurs avec des systèmes de répartition de charge ou de heartbeat (un serveur demande régulièrement sur le réseau si son homologue est en fonctionnement et lorsque l'autre serveur ne répond pas, le serveur de secours prend le relais).

Il est aussi possible de recourir à un site secondaire de haute disponibilité qui se situe généralement près du site de production (moins de 10km) afin de permettre de les relier avec de la fibre optique et synchroniser les données des deux sites quasiment en temps réel de manière synchrone ou asynchrone selon les technologies utilisées, les besoins et les contraintes techniques.

Quel que soit le degré d'automatisation et de sécurisation d'un système informatique, la composante humaine reste un facteur important. Pour limiter le risque de panne, les acteurs d'un service informatique doivent adopter les comportements les moins risqués pour le système et éventuellement savoir accomplir des gestes techniques.

Pour les utilisateurs, il s'agit :
- de respecter les normes d'utilisation de leurs ordinateurs : n'utiliser que les applications référencées par les mainteneur du SI, ne pas surcharger les réseaux par des communications inutiles, respecter la confidentialité des codes d'accès.
- de savoir reconnaître les symptômes d'une panne (distinguer un blocage d'accès d'un délai de réponse anormalement long par exemple) et savoir en rendre compte le plus vite possible.
Pour les opérateurs du SI, il s'agit d'avoir la meilleure connaissance du système en terme d'architecture (cartographie du SI) et de fonctionnement (en temps réel si possible), de faire régulièrement les sauvegardes et de s'assurer qu'elles sont utilisables.
Pour les responsables, il s'agit de faire les choix entre réalisations internes et prestations externes de manière à couvrir en totalité le champ des actions à conduire en cas de panne, de passer les contrats avec les prestataires, d'organiser les relations entre les opérateurs du SI et les utilisateurs, de décider et mettre en oeuvre les exercices de secours, y compris le retour d'expérience.

Selon la gravité du sinistre et la criticité du système en panne, les mesures de rétablissement seront différentes.

Dans l'hypothèse de la reprise de données, seules des données ont été perdues. L'utilisation des sauvegardes est nécessaire et la méthode consiste à réimplanter le dernier jeu de sauvegardes. Cela peut se faire dans un laps de temps relativement court, si l'on a bien identifié les données à reprendre et si les méthodes et outils de réimplantation sont accessibles et connus.

A un seuil de panne, plus important, une ou des applications sont indisponibles. L'utilisation d'un site de secours est envisageable, le temps de rendre disponible l'application en cause.

Le redémarrage des machines :

provisoire : utilisation des sites de secours
définitif : après dépannage de la machine d'exploitation habituelle, y rebasculer les utilisateurs, en s'assurant de ne pas perdre de données et si possible de ne pas déconnecter les utilisateurs.

Le plan de reprise contient les informations suivantes :

La composition et le rôle des équipes de pilotage du plan de reprise. Ces équipes se situent au niveau stratégique :
1. les dirigeants qui ont autorité pour engager des dépenses ;
2. le porte-parole responsable des contacts avec les tiers ;
3. au niveau tactique, les responsables qui coordonnent les actions ;
4. au niveau opérationnel, les hommes de terrain qui travaillent sur le site sinistré et sur le site de remplacement.

La composition de ces équipes doit être connue et à jour, ainsi que les personnes de remplacement et les moyens de les prévenir. Les membres des équipes doivent recevoir une formation.

Les procédures qui mettent la stratégie en oeuvre. Ceci inclut les procédures d'intervention immédiate ;
Les procédures pour rétablir les services essentiels, y compris le rôle des prestataires externes ;
Les procédures doivent être accessibles aux membres des équipes de pilotage, même en cas d'indisponibilité des bâtiments.

Le plan doit être régulièrement essayé au cours d'exercices. Un exercice peut être une simple revue des procédures, éventuellement un jeu de rôles entre les équipes de pilotage. Un exercice peut aussi être mené en grandeur réelle, mais peut se limiter à la reprise d'une ressource (par exemple un serveur principal), ou à une seule fonction du plan (par exemple la procédure d'intervention immédiate). Le but de l'exercice est multiple :

Vérifier que les procédures permettent d'assurer la continuité d'activité
Vérifier que le plan est complet et réalisable
Maintenir un niveau de compétence suffisant parmi les équipes de pilotage
Évaluer la résistance au stress des équipes de pilotage

Un plan doit aussi être revu et mis à jour régulièrement pour tenir compte de l'évolution de la technologie et des objectifs de l'entreprise. La seule façon efficace de mettre à jour le PCA est d'en sous traiter la maintenance aux métiers afin qu'il soit réactualisé à chaque réunion mensuelle de service.

Plan de secours

Plan de reprise d'activité

Un plan de reprise d'activité (PRA) constitue l'ensemble des procédures documentées lui permettant de rétablir et de reprendre ses activités en s'appuyant sur des mesures temporaires adoptées pour répondre aux exigences métier habituelles après un incident.

Le plan de reprise d'activité comprend les tâche suivantes :

Identification des activités critiques ;
Identification des ressources ;
Identification des solutions pour le maintien des activités critiques.

Introduction au Shell

Introduction

Ce chapitre supplémentaire ne fait pas à proprement parler parti du programme mais est une introduction au shell.

Sections

Qu'est-ce que le shell ?

Les shells peuvent généralement dépendre des OS, sachant qu'il en existe une quantité pour chacun d'entre eux. Dans le cas de Linux, le Bourne Again Shell ou bash est très largement répandu. C'est celui qui va nous intéresser ici.

Quand on ouvre un terminal, une fenêtre s'ouvre affichant un prompt shell. Dans le cadre du bash si aucune personnalisation n'a été faite il se décompose ainsi :

[utilisateur@machine répertoire\ de\ travail]$

Généralement un shell est fait pour passer des commandes, c'est à dire, exécuter des programmes avec ou sans arguments :

$ date
sam. 09 mai 2020 17:36:09 CEST

L'ajout de certains arguments permet de modifier le comportement de certains programmes. La commande echo permet par exemple d'afficher à l'écran les arguments qui la suivent. Un argument est une chaîne de caractère séparée du nom du programme par un espace :

$ echo hello
hello

Si l'on souhaite que l'argument contiennent lui-même un espace, et éviter d'ajouter un deuxième argument il suffit d'entourer la chaîne de guillemets :

$ echo "Hello world!"
Hello world!

On peut également échapper le caractère espace à l'aide d'un antislash :

$ echo Hello\ world!
Hello world!

Exemple pour créer un répertoire Mes photos on écrit : mkdir Mes\ photos

Les chemins

Le shell sait quel programme (dont un certain nombre sont installés avec l'OS) utiliser et où celui-ci se situe dans le système de fichiers à l'aide de ce que l'on appelle une variable d'environnement. Une variable connue et renseignée dès le lancement du shell. Il s'agit de la variable PATH :

$ echo $PATH
/usr/local/sbin:/usr/local/bin:/usr/bin

Il s'agit d'une liste des chemins ordonnée dans lequel le shell va chercher les programmes.

La commande which permet de savoir dans quel répertoire se trouve le programme passé en argument, lequel sera celui exécuté lors de l'appel par ce shell précisément :

$ which echo
/usr/bin/echo

Les chemins sont la description des emplacements des fichiers dans l'architecture du système de fichiers. Sur Linux et MacOS, les répertoires sont séparés par des slash. Le premier slash sur la gauche symbolise le sommet du système de fichiers (celui-ci étant hiérarchique) il est appelé root ou répertoire root, racine en français. Sous Windows les répertoires sont généralement séparés par des antislash et chaque partition est la racine de son propre système de fichier hiérarchique. La partition est généralement désignée par une lettre de l'alphabet (C:\ D:\ etc.).

Il existe 2 types de chemins :

les chemins absolus : à partir de la racine.
les chemins relatifs : à partir du répertoire dans lequel on se situe.

Pour savoir dans quel répertoire on se trouve actuellement il existe la commande pwd pour print working directory (affiche le répertoire de travail) :

$ pwd
/home/hugo

A partir d'ici on peut changer de répertoire de travail avec la commande cd et, en argument un chemin relatif ou absolu :

$ cd /home

$ pwd
/home

Il existe un certain nombre de symboles permettant "d'expanser" des noms de répertoires :

~ : le répertoire de l'utilisateur courant (ie : /home/hugo)
. : le répertoire de travail
.. : le répertoire parent du répertoire de travail
- : l'ancien répertoire de travail

Par exemple :

$ cd ~/test/

$ pwd
/home/hugo/test

$ cd ../../

$ pwd
/home

$ cd -

$ pwd
/home/hugo/test

Cela permet de naviguer plus facilement à l'intérieur du système de fichiers.

Note : Dans le cas de script shell, lors de l'appel d'un programme on évite les chemins relatifs. On préfère travailler avec la variable d'environnement PATH ou bien on donne le chemin absolu.

Lister le contenu d'un répertoire et droits

Par défaut (sans argument) un programme agit sur le répertoire de travail. Il est alors généralement intéressant de savoir que contient ce répertoire. La commande ls permet de lister le contenu d'un répertoire.

$ ls file1  file2  file3

$ ls ../../ bleu rouge vert

Dans le cas de l'utilisation de certains programmes il peut être utile de connaître les arguments que l'utilitaire accepte. La plupart des programmes implémentent des flags et des options. Un des flags les plus utiles est --help :

$ ls --help

permet d'afficher l'aide de la commande ls.

Pour lire les usages, ... signifie 1 ou plus et [ ] signifie que ce qui est dans les crochets est optionnel. En suit généralement une brève description de la commande et à la suite les potentiels flags disponibles.

$ ls -l

permet de lister au format long avec un nombre bien plus important d'information :

le type de fichiers
les droits : utilisateur propriétaire, groupe principal du propriétaire, autres (user, group, others)
le nombre d'inodes (hard links)
l'utilisateur propriétaire
le groupe principal du propriétaire
le mtime (modification time)
le nom du fichier

Les droits s'organisent ainsi :

pour les fichiers

r : read, autorise à lire le contenu du fichier w : write, autorise à modifier le contenu du fichier x : execute, autorise l'exécution du fichier

pour les répertoires

r : read, autorise à lister le contenu du répertoire w : write, autorise la création de fichier, la modification du nom de fichier et la suppression de fichier x : execute, autorise à traverser (entrer) dans le répertoire

Enfin le - présenté par la commande :

$ ls -l

signifie l'absence du droit.

D'autres commandes

La commande mv permet de renommer et/ou (non exclusif) déplacer un fichier:

$ mv fichier_a_renommer ../../nouveau_fichier

La commande cp permet de copier un fichier :

$ cp original ~/copie

La commande rm permet de supprimer un fichier :

$ rm ~/copie

Par défaut la commande rm n'est pas récursive. Pour cela il est nécessaire d'ajouter le flag -r suivi du répertoire. La commande rmdir permet également de supprimer un répertoire mais seulement si celui-ci est déjà vide.

Finalement pour créer un nouveau répertoire on utilise la commande :

$ mkdir Mon\ Repertoire

Pour avoir encore plus d'informations sur une commande on peut se référer aux pages de manuel de celle-ci :

$ man ls

Cela permet généralement d'avoir une meilleure vision de ce que fait la commande, avec une navigation facilitée.

Note : Pour quitter le programme man, il suffit de presser la lettre q.

Pour nettoyer le terminal on peut exécuter la commande :

$ clear

ou plus facilement presser Ctrl + L.

Redirection d'entrée/sortie, descripteurs de fichiers et tubes

Comme il a été évoqué plus haut, l'une des caractéristiques les plus importantes du shell est qu'il permet l'assemblage de multiples programmes via des flux. Cela permet de combiner les fonctionnalités de différents programmes afin d'exécuter une tâche spécifique.

Pour interagir avec ces flux le bash dispose de descripteurs de fichiers ou fd (pour file descriptor). Ceux-ci sont des chiffres utilisés comme référence abstraite vers un fichier ou une ressource d'entrée/sortie (e.g pipe, IPC etc.) Le terme de fichier est ici très large également (physique, virtuel, périphérique etc.)

Par défaut 3 ressources disposant de fd sont ouverts :

le stdin ou (entrée standard) : fd 0, qui est saisi au clavier
le stdout ou (sortie standard) : fd 1, qui est affiché dans le terminal
le stderr ou (erreur standard) : fd 2, qui est affiché dans le terminal

Pour alimenter l'entrée standard à l'aide du contenu d'un fichier, on utilise le chevron gauche :

$ ma_commande < nom_fichier

Pour vider le contenu de la sortie standard dans un fichier, on utilise le chevron droit :

$ ma_commande > nom_fichier

Note : Si aucun chiffre de descripteur ne préfixe les chevrons, ce sera le stdin (0) pour un gauche et le stdout (1) pour un droit.

Dans ce cas précis, uniquement la sortie d'erreur standard sera affichée dans le terminal. Dans ce cas précis également, le contenu préexistant au fichier est écrasé, ce qui peut être pratique si l'on souhaite vider un fichier ou créer un fichier vide on peut exécuter la commande :

$ > nom_fichier

Pour ajouter le flux au fichier on utilise le double chevron :

$ ma_commande >> nom_fichier

Si l'on souhaite conserver cette sortie d'erreur dans un fichier il faut préciser le descripteur de fichier :

$ ma_commande > nom_fichier 2> erreur_log

Et si l'on souhaite simplement ajouter sans écraser :

$ ma_commande >> nom_fichier 2>> erreur_log

Si l'on souhaite rediriger le fd i vers j :

$ i>&j

Par exemple :

$ ma_commande 2>&1 nom_fichier

redirige la stderr vers stdout.

Pour ouvrir un fichier et affecter un descripteur de fichier :

$ exec 3<> nom_fichier

Et pour fermer le fichier :

$ exec 3>&-

Cela permet d'accéder au fichier :

$ exec 3<> nom_fichier

$ read <&3         # Se déplacer d'une ligne vers le bas

$ read -n 3 <&3    # Se déplacer de 3 caractères (en position 4)

$ echo -n . >&3

$ exec 3>&-

Le script ci-dessus permet par exemple de remplacer le 4ème caractère de la deuxième ligne du fichier par un point. La où le shell se distingue réellement, c'est dans l'utilisation de pipe. Cet opérateur | permet de chaîner des programmes de façon à ce que la sortie de l'un devienne l'entrée d'un autre :

$ ls -l / | tail -n1
$ pactl list sink-inputs | rg Volume | awk '{print $5}'

La première commande affiche le dernier item de la liste de fichiers du répertoire /. La deuxième affiche le pourcentage de l'entrée son des destinations (sinks) audio (enceintes, casques etc.) Cela a de multiples avantages notamment pour l'exploitation de fichiers de données.

Une commande conçue pour fonctionner avec l'opérateur pipe est xargs. xargs lit l'entrée standard et passe chaque item en argument à la fonction suivante. Un exemple d'application :

$ ls *.txt | xargs wc -l

La première commande liste l'ensemble des fichiers .txt et wc compte le nombre de ligne de chacun des fichiers passés en argument.

Pour savoir ce qu'une commande peut faire, savoir quelle est son utilisation généralement celle-ci implémente une option --help ou une référence (page) dans le man. Man est une commande qui renvoie une section du manuel système. Pour plus de détail :

$ man man

Appuyer sur q pour quitter.

Pour reprendre l'opérateur | on peut afficher une page man et l'ouvrir au format pdf :

$ man ma_commande -Tpdf | zathura -

Si on le souhaite (et qu'on dispose d'un lecteur pdf)...

Un outil versatile et puissant

Sur la plupart des systèmes Unix-like, il existe un utilisateur root. Cet utilisateur a le droit d'accéder à l'ensemble des fichiers du système sans restriction (écriture, lecture, modification, suppression). Généralement il est dangereux de se connecter en root sur une machine. De ce fait, on préfère donner des droits root à d'autres utilisateurs mais uniquement sur des commandes spécifiques. Pour cela on utilise l'utilitaire sudo.

Par exemple, la luminosité d'un ordinateur portable apparaît dans un fichier système :

/sys/class/backlight/brightness

En écrivant dans ce fichier on peut changer la luminosité de l'écran. Néanmoins, l'écriture doit être faite par root. En effet :

$ sudo find -L /sys/class/backlight --maxdepth 2 -name "*brightness"

$ sudo echo 3 >/sys/class/backlight/brightness

Ne marche pas ! En effet, c'est le shell qui exécute l'écriture via >. sudo sur la commande echo est inutile. Pour contourner le problème on utilise un autre outil pour écrire le fichier :

$ echo 3 | sudo tee /sys/class/blacklight/brightness

Puisque c'est le programme tee qui ouvre /sys pour l'écriture en tant que root, les permissions sont vérifiées. Un nombre de choses intéressantes se trouve sous /sys (contrôle des périphériques, les infos cpu, mémoire etc.)

Scripts shell

La plupart des shells ont un langage de script qui leur est propre. Ce qui fait que le langage de script shell est différent de langages de scripts plus traditionnels c'est qu'il est avant tout fait pour de l'administration système. Créer des commandes pipes, écrire dans des fichiers, lire l'entrée standard etc. Dans cette section, le langage bash étant le plus répandu, c'est celui que nous utiliserons.

Pour assigner des variable en bash, on utilise la syntaxe foo=bar et on accède au contenu de la variable avec $foo. foo = bar ne marche pas puisque le bash l'interprète comme l'appel du programme foo avec 2 arguments = et bar. En général dans les scripts shell le caractère espace sépare les arguments.

Les chaînes de caractères en bash peuvent être définies à l'aide des délimiteurs ' et ", mais ils ne sont pas équivalents. Les chaînes délimitées à l'aide de la simple quote sont des littéraux et ne substituent pas de variables contrairement aux chaînes délimitées à l'aide d'une double quote :

$ foo=bar
$ echo "$foo"
  bar

$ echo '$foo'
  $foo

Comme la plupart des langages de programmation, bash supporte des techniques de contrôle du flux d'exécution tel que if, case, while et for. On peut également définir des fonctions en bash qui peuvent prendre des arguments. Exemple :

mcd () {
    mkdir -p "$1"
    cd "$1"
}

Ici $1 est le premier argument de la fonction. Contrairement aux autres langages de script, bash utilise un nombre assez important de variables spéciales qui font référence à des arguments, codes d'erreurs etc. Voir liste ci-dessous :

$0 - Nom du script
$1 à $9 - Arguments du script. $1 est le premier argument (resp. autres)
$@ - Tous les arguments
$# - Nombre d'arguments
$? - Code retour de la commande précédente (très utile pour une vérification par exemple)
$$ - Identifiant de processus (PID) du shell courant.
$! - Identifiant de processus (PID) de la dernière commande passée en background.
$_ - Dernier argument de la dernière commande. Dans un shell interactif on peut également faire Esc suivi du point.

Les commandes génèrent généralement une sortie via stdout, des erreurs via stderr, et un code retour. Le code retour permet de savoir le résultat d'exécution, qui peut être utilisé à la suite par d'autres scripts ou commandes. Généralement, une valeur de 0 signifie que tout s'est bien passé et tout autre valeur est une erreur.

Néanmoins, ce code peut aussi être utilisé pour des commandes conditionnées en utilisant les opérateurs && (et) et || (ou). Les commandes peuvent également être séparées sur la même ligne avec le ; . La commande true aura toujours un code retour à 0 tandis que false aura toujours un code à 1. Exemples :

false || echo "Oups, raté !"

true || echo "N'est pas affiché"

true && echo "Les choses se sont bien passées."

false && echo "Pas affiché"

false ; echo "Ca marche !"

Parfois on souhaite avoir le contenu de la sortie d'une commande dans une variable. On peut le faire à l'aide d'une substitution de commande. Quand on écrit $(commande) le bash exécutera la commande et substituera son contenu dans le script avant l'exécution de celui-ci. Par exemple, si on écrit :

for file in $(ls)

Le shell appellera dans un premier temps ls et parcourra ses valeurs par la suite.

Le bash permet également de substituer une commande de cette façon :

diff <(ls foo) <(ls bar)

Cette commande montre la différence entre fichiers dans les répertoires foo et bar.

Puisque cela a été relativement rapide, voyons un exemple que montre quelques trucs qu'on peut faire. Le script parcourra les arguments que nous lui donnerons, grep la chaîne foobar, et l'ajoutera comme commentaire ci celle-ci est absente.

#!/bin/bash

echo "Début du programme à $(date)" # Date sera substituée

echo "Exécution du program $0 avec $# arguments avec le pid $$"

for fichier in $@; do
    grep foobar $fichier 2>&1 >/dev/null
    if [[ $? -ne 0 ]]; then
        echo "Le fichier $fichier ne contient pas le mot foobar, ajout en cours !"
        echo "# foobar" >> "$fichier"
    fi
done

Dans le test de comparaison on teste si $? est égal à 0. Bash implémente de nombreuses comparaisons de la sorte (voir man test). Dans un test on essaye généralement d'utiliser les doubles crochets, les chances de faire des erreurs sont moindres. Même si cela n'est pas le standard POSIX.

Lors de l'exécution de scripts, on devra souvent fournir des arguments semblables. Bash rend les choses plus faciles, "étendant" les expressions en supportant des expansions de nom de fichiers :

Joker - On peut utiliser ? et * pour respectivement vérifier 1 ou n'importe quel nombre de caractère. Par exemple, soit les fichiers foo1 foo2, foo10 et bar, la commande rm foo? supprimera foo1 et foo2 alors que rm foo* supprimera tout sauf bar.
Accolades {} - Quand il existe une sous-chaîne commune dans une série de commandes, on peut utiliser les accolades pour étendre automatiquement. Cela peut-être pratique pour déplacer ou convertir des fichiers.

Exemples :

convert image.{png,jpg}
# Deviens
convert image.png image.jpg

cp /chemin/du/projet/{foo,bar,baz}.sh /nouveau_chemin
#Deviens
cp /chemin/du/projet/foo.sh /chemin/du/projet/bar.sh /chemin/du/projet/baz.sh /nouveau_chemin

# On peut également combiner des jokers
mv *{.py,.sh} repertoire

mkdir foo bar
# Après la création de ces 2 répertoire,
# La commande ci-dessous créé les fichiers foo/a foo/b, ...foo/h, bar/a, bar/b, ...
touch {foo, bar}/{a..h}
touch foo/x bar/y
# Montre la différence entre les fichiers contenus dans foo et ceux dans bar
diff <(ls foo) <(ls bar)
# Sors
# < x
# ---
# > y

Les scripts ne doivent pas nécessairement être écrit en bash pour être exécuté depuis le terminal. Exemple, ce script python qui inverse les arguments qu'on lui fournit :

#!/usr/local/bin/python
import sys
for arg in reversed(sys.argv[1:]):
    print(arg)

Le noyau sait exécuter ce script avec le bon interpréteur grâce à l'inclusion du sheebang (la première ligne). C'est une bonne pratique que d'inclure les sheebangs en utilisant la commande env (pour des question de portabilité) : #!/usr/bin/env python env permet de résoudre où se trouve l'interpréteur via la variable d'environnement PATH.

Note : Pour savoir où se trouve la commande exécutée dans le système de fichiers hiérarchique standard, on peut utiliser la commande which.

Quelques différences entre les fonctions shell et les scripts shell à garder en tête sont :

Les fonctions doivent être écrites dans le même langage shell, alors que les scripts n'ont pas cette contrainte. D'où l'utilité du sheebang.
Les fonctions sont chargées une fois que leur définition est lue. Les scripts sont chargés à chaque exécution.
Les fonctions sont exécutées dans le shell courant alors que les scripts exécutent leurs propres processus. Les fonctions peuvent donc modifier des variables d'environnement, par exemple changer le répertoire de travail. A ce titre, les scripts peuvent hériter de variables d'environnement si celles-ci ont été exportées précédemment à l'aide du mot-clef export.
Comme avec n'importe quel langage de programmation, les fonctions sont des outils modulaires permettant une réutilisation et une meilleure clarté du code.

Fiches de préparation PSE