Concurrence, mémoire et gestion des données (systèmes d'exploitation)

Concurrence et parallélisme — notions de base

BASICS :

Parallélisme

Parallélisme : coexistence de processus exécutés simultanément.

Participation

Participation : parallèles entre les processus connexes qui nécessitent une synchronisation.

Calendrier

Calendrier : correspondance entre l'ordre temporel dérivé du processus de communication entre eux ; il est nécessaire pour assurer l'exclusion mutuelle.

Fils (threads)

FILS : valeur de position dominante et dépendance entre le système d'exploitation et les processus.

Variables partagées

Variables partagées : variables pouvant être mises à jour par deux processus ou plus.

Section critique

Section critique : emplacement du programme où une variable partagée est accédée ou modifiée.

COBEGIN/COEND — primitives de parallélisme

COBEGIN / COEND : primitive — structures de contrôle de la concurrence ou du parallélisme. État composé de paires d'énoncés qui indiquent respectivement la division et la fusion de la ligne de contrôle (COBEGIN / COEND).

Exclusion mutuelle

EXCLUSION MUTUELLE : technique de programmation utilisée pour protéger l'exécution des sections critiques d'un programme.

Types d'algorithmes d'exclusion mutuelle

Attente active (busy waiting)

Attente active : algorithmes qui fondent leur fonctionnement sur une boucle vérifiant si l'accès à la section critique est permis. L'appel en attente est actif car le processus reste bloqué en exécution et entre en concurrence permanente pour le processeur ; pour cette raison, ces algorithmes surchargent inutilement le système. (Maire et d'autres, p. 82)

• Algorithme de Dekker : basé sur une table de dimensions deux (éléments logiques / commutateurs).
• Locks mutex : utilisation d'un verrou nommé (mutex) pour la synchronisation.
• Alternance : usage d'une variable appelée turn (temps) pour la synchronisation.

Attente bloquante (non active)

N'attendez pas ACTIVE : algorithmes basés sur le blocage du processus pour entrer en section critique, évitant la concurrence pour le processeur jusqu'à la libération de la ressource. (Maire et d'autres, p. 82)

• Les feux de circulation : opération basée sur une variable entière utilisée comme demande d'entrée pour une section critique, partagée par tous les processus du système. Conçu par Dijkstra (1965), on l'appelle "feu" en raison de sa capacité à gérer le trafic des processus souhaitant accéder aux données partagées.
• Régions critiques : autorisent l'accès aux données partagées uniquement depuis certaines zones, transparentes au reste du programme. Elles présentent de petits problèmes de planification et ne permettent pas d'effectuer plusieurs opérations de lecture simultanées.
• Condition régions critiques : amélioration par rapport aux anciennes méthodes pour corriger les problèmes de planification.
• Moniteurs : mécanisme où le programmeur n'a pas à prévoir explicitement la synchronisation. Les moniteurs regroupent les données partagées et les fonctions qui opèrent sur ces données dans un seul module. Ils doivent être pris en charge par le langage (par ex. Modula, Ada).
• Compteurs d'événements : basés sur une variable entière avec opérations d'accès permettant de synchroniser les activités sans appliquer l'exclusion mutuelle.
• Messages : mécanisme coopératif où la zone de mémoire partagée est gérée par le système d'exploitation. Un processus envoie un message vers un autre en l'enregistrant dans la mémoire partagée et le destinataire peut le lire.

Communication par messages

Messages (suite) : il existe deux types de communication entre processus :

• Direct : le processus envoie et reçoit des messages directement à/depuis un autre processus.
• Indirect (astuce) : les messages sont envoyés et reçus via des boîtes aux lettres.

Appel à distance : similaire au passage de paramètres dans un appel de procédure : des messages passent d'un processus à un autre ; l'appelant attend la réponse si nécessaire.

Rendez-vous : méthode dérivée des appels à distance, où l'appel n'invoque pas une procédure distante mais synchronise un groupe d'états. Implémentée en Ada.

Mécanismes matériels d'exclusion mutuelle

MÉCANISMES MATÉRIELS : instructions matérielles qui garantissent l'exclusion mutuelle.

Désactiver les interruptions

Désactiver les interruptions : les ordinateurs permettent de désactiver les interruptions ; si un dispositif génère une interruption alors que celles-ci sont désactivées, la reconnaissance et le traitement seront retardés jusqu'à leur réactivation, ce qui assure l'exclusion mutuelle. L'activation et la désactivation d'une interruption se font généralement par une instruction machine.

Test-and-set

Test-and-set : certaines architectures offrent l'instruction test-and-set destinée à faire respecter l'exclusion mutuelle. Toutefois, toutes les architectures n'offrent pas cette instruction et, selon le contexte, elle peut ne pas suffire à assurer un mutex complet.

Verrous (locks)

Lock : basé sur les primitives précédentes ; il a pour but de permettre l'accès à la section critique d'un processus en l'absence d'autres activités concurrentes au sein de cette section critique.

Gestion de la mémoire

Gestion de la mémoire :

• Stockage hiérarchique
• COST
• TEMPS D'ACCÈS
• CAPACITÉ

Stratégies de gestion

Monoprogrammation, mémoire dédiée (sans gestionnaire), monitor (apparition des systèmes d'exploitation), protection des frontières, adressage remappé (statique à la compilation / dynamique à l'exécution), troc, multiprogrammation, protection de la mémoire.

Systèmes avec partitions voisines de taille fixe, partitions voisines de taille variable, fragmentation interne/externe, compactage.

Pagination (Paging)

Page : système de gestion de la mémoire qui divise la mémoire en sections de taille égale appelées cadres ou frames, et le programme en blocs de même taille appelés pages. Cela crée une table de pages. Avec cette stratégie, il n'est pas nécessaire de placer les blocs (pages) contigus dans les cadres.

Segmentation

Segmentation : système de gestion de la mémoire qui supporte la vue logique de l'utilisateur en mémoire physique, basée sur un ensemble de segments identifiés par un numéro et un décalage. La segmentation est réalisée par l'assembleur ou le compilateur.

Paging segment

Paging segment : système de gestion de la mémoire qui segmente la table des pages adaptée à la taille du programme (ex. IBM série 370).

Segmentation avec pagination

Segmentation avec pagination : combinaison où les segments contiennent des tables de pages ; la table de segments indique leurs longueurs (ex. Intel 386, Multics/Honeywell, GE 645).

Mémoire virtuelle

La mémoire virtuelle : système de gestion de la mémoire qui permet l'exécution de programmes partiellement chargés en mémoire principale.

• Chargement : à la demande, en avance.
• Sélection de l'espace (placement).
• Remplacement : FIFO, LRU, LFU.

La mémoire virtuelle : (répété) Charge (demandes, avance), sélection de l'espace (lieu), remplacement (fifo, lru, LFU).

Cache

Cache : également appelé tampon cache. Technique qui utilise des blocs provenant du disque (ou d'un autre stockage secondaire) conservés en mémoire RAM afin d'améliorer les performances du système.

Gestion des documents et évolution des systèmes

GESTION DES DOCUMENTS

Évolution :

• 1950 - 1960 : fichiers séquentiels
• 1960 - 1970 : fichiers séquentiels indexés
• 1970 - 1980 : fichiers à accès aléatoire (Random Access)
• 1980 - 1990 : système de gestion de base de données (SGBD), data marts, entrepôt de données
• 1990 - : systèmes actuels de gestion des bases de données relationnelles/objets (SGBDR/SGBDO), systèmes de fichiers en cluster

Concepts fondamentaux : organisation logique et physique des données

ORGANISATION LOGIQUE ET PHYSIQUE DES DONNÉES :

Description de l'organisation physique et logique des données : unité minimale d'information est le bit, puis octet (byte), caractère, champ, enregistrement, bloc physique, fichier, aire de données, etc.

Définitions importantes

• FIELD (champ clé) : un champ qui identifie l'enregistrement et le distingue des autres, par ex. ID (# CI, série).
• ENREGISTREMENT / BLOC PHYSIQUE : la plus petite quantité de données transférable lors d'une opération E/S entre la mémoire principale et un périphérique (une ligne d'impression, etc.).
• Facteur de blocage : nombre d'enregistrements logiques que peut contenir un bloc physique.
• Champ : élément de base de données contenant une seule valeur ; les champs se distinguent par leur identité, type et longueur (fixe ou variable).
• Enregistrement : collection de domaines connexes traités comme une unité.
• Dossier : collection d'enregistrements similaires avec un nom unique, gérée par l'utilisateur et les applications comme une unité.
• BASE DE DONNÉES : collection de données interreliées et d'un ensemble de programmes permettant l'accès à ces données.
• ANNUAIRE : espace réservé pour l'OS afin de garder la trace des fichiers sur le système.

Qu'est-ce qu'une base de données ?

Qu'est-ce qu'une base de données ?

Un Système de Gestion de Base de Données (SGBD) se compose d'un ensemble de données liées et d'un groupe de programmes pour y accéder. (Korth HF)

C'est un ensemble de documents intégrés et auto-descriptifs. (DM Kroenke)

C'est une collection d'éléments de données liés, traitables par un ou plusieurs systèmes d'application. (Hansen GW)

Pourquoi les bases de données ?

Les SGBD résolvent :

• La redondance et l'incohérence des données (données dupliquées dans plusieurs fichiers).
• L'accès multi-utilisateurs (risque d'incohérence lors de mises à jour multiples).
• Les difficultés d'accès aux données (manque d'applications pour certains rapports).
• Les problèmes de sécurité et d'intégrité (chaque utilisateur a sa vue ; les données doivent satisfaire des contraintes de cohérence).

Data Warehouse, Data Mart et OLAP/OLTP

Data Warehouse : dépôt d'information intégrée destiné à l'analyse et à la recherche ; les données proviennent de sources multiples et de différents types. Un entrepôt contient les données opérationnelles consolidées de plusieurs Data Marts. En général, 80% des données utilisées proviennent de 20% des transactions système.

Data Mart : référentiel de données pour un domaine spécifique de l'entreprise, souvent normalisé et basé sur une architecture de bus, obtenu à partir de bases opérationnelles ; il peut agir comme un entrepôt virtuel.

Online Analytical Processing (OLAP) : outils d'analyse utilisés en entrepôt de données et Data Mart.

Online Transaction Processing (OLTP) : enregistrement des transactions au moment où elles sont générées.

OUTILS CASE : dictionnaire et référentiel d'information comprenant conception et analyse : diagrammes de flux de données, entité-relation, schémas de base de données, conception d'écrans, structures de programmes, algorithmes, référentiel de données.

Objectifs des systèmes de gestion de données

OBJECTIFS :

• Fournir la gestion des dossiers aux usagers et répondre aux demandes de services pour les archives.
• Répondre aux besoins de gestion des données et aux besoins des utilisateurs.
• Assurer la cohérence et la validité des données.
• Protéger les données contre les événements entraînant perte ou destruction.
• Apporter un soutien d'E/S pour un grand nombre de types de périphériques de stockage.
• Optimiser les performances.

Architecture du système de fichiers

DOSSIER ARCHITECTURE SYSTEME :

Au niveau le plus bas, les pilotes de périphériques communiquent directement avec les dispositifs, leurs contrôleurs ou canaux. Chaque pilote est chargé d'initier les opérations d'E/S et de traiter l'achèvement d'une demande.

• Méthode d'accès
• E/S logique
• Contrôleur de base
• Principe du système de fichiers
• Gestionnaire (manager)
• Périphérique

Le système de fichiers de base (ou le niveau d'E/S physique) fournit l'interface principale avec l'environnement extérieur de l'ordinateur : il gère des blocs de données échangés avec le disque ou la bande, place ces blocs dans le stockage secondaire et les met en mémoire tampon. Ce niveau est sans incidence sur le contenu ou la structure logique des fichiers.

Le superviseur d'E/S de base est responsable de l'initiation et de l'achèvement de toutes les E/S. Il contient les structures de contrôle responsables des opérations E/S, de la planification et de l'état des fichiers ; il gère également la sélection du périphérique cible pour l'E/S.

L'E/S logique correspond au système de fichiers qui permet aux utilisateurs et aux applications d'accéder aux documents, offrant une capacité d'E/S sur des enregistrements d'usage général et maintenant les fichiers de base de données.

La méthode d'accès est le niveau de système de fichiers le plus proche de l'utilisateur. Chaque méthode fournit une interface standard entre les applications et les systèmes de fichiers et périphériques. Exemples : indexé, séquentiel, séquentiel indexé, indexation et dispersion (hashing).

Administration de la sécurité

Administration de la sécurité — critères :

• Empêcher l'accès non autorisé (espionnage, vol, sabotage).
• Maintenance du système (matériel et logiciel).
• Minimiser les risques de pertes (incendie, inondation, tremblement de terre, virus).
• Le niveau de sécurité est relatif (en fonction de l'importance pour l'organisation).

Classification de la sécurité

Classification :

• Sécurité extérieure : stratégies et mécanismes pour protéger l'installation sans intervention du système informatique.
• Sécurité intérieure (protection) : stratégies et mécanismes pour protéger le système au moyen des ressources propres du système informatique.
• Sécurité physique : protection contre catastrophes naturelles et accès non autorisé (alarmes incendie, grilles de sécurité, etc.).
• Sécurité administrative : stratégies et mécanismes pour empêcher l'accès logique (contrôle d'accès, pare-feu, codes, parités, Hamming, CRC, checksums).

Sécurité intérieure — principes

La sécurité intérieure se base sur l'authentification (ID utilisateur) et les principes suivants :

• Simple, cohérente et complète.
• L'état par défaut n'est pas accessible.
• Minimiser les privilèges.
• Gestion des mots de passe.
• Quelque chose que l'utilisateur sait.
• Quelque chose que l'utilisateur possède.
• Quelque chose de facile à utiliser et sûr.