Cours les fonctions d’un système d’exploitation, tutoriel & guide de travaux pratiques en pdf.

Les Processus

L’analyse du fonctionnement d’un système d’exploitation montre la présence d’un ensemble d’activités multiples, simultanées ou non, et présentant de nombreuses interactions mutuelles. Pour décrire ce fonctionnement, on introduit la notion de processus comme définition d’une activité élémentaire. Un processus est une entité dynamique dre présentant l’exécution d’un programme ; un processus naît, vit et meurt.
Au cours de son existence, un processus n’est jamais totalement isolé des autres : il partage des données ou des ressources matérielles, échange des signaux ou des informations, arrête ou tue d’autre processus, etc. Aussi, l’objet de ce chapître est de préciser la notion de processus, de montrer comment elle est mise en oeuvre et comment est programmée la coordination entre processus.

Définitions

Instructions, processeur, processus

Un programme est une suite ordonnée d’instructions dont la nature est fonction du langage de programmation considéré, et dont l’exécution peut tres complexe. Une instruction est considérée comme indécomposable (indivisible), c’est à dire que l’on s’interdit d’observer le système pendant l’exécution d’une instruction.
Le processeur est l’entité câblée ou non capable d’exécuter une instruction.
Un processus est un programme en cours d’exécution. Un processus est défini par le code et les données du programme, son contexte d’exécution(vecteur d’état) à savoir les informations qu’il utilise explicitement (variables, procédures, ressources, etc.) et les informations utilisées par le système pour gérer l’attribution des ressources (contenus des registres -CI, RI, etc.-, la taille mémoire utilisée, ressources matérielles utilisées). Il est important de se rappeler que le vecteur d’état d’un processus ne peut être observé pendant l’exécution d’une instruction.

Ressource, état d’un processus

Une ressource est une entité pouvant servir à l’exécution d’un travail. Des exemples de ressources sont les organes de la machine (unité centrale, mémoire centrale, périphériques), un fichier, des données, etc.
Un processus est dans un état bloqué s’il lui manque la ou les ressources nécessaires à l’exécution de sa prochaine instruction ; dans le cas contraire le processus est dit actif. Habituellement on distingue deux types de blocage possibles :
– le blocage technologique pour l’absence de ressources,
– le blocage intrinsèque pour un problème de synchronisation.
Lorsque plusieurs processus existent en même tempssur un même système, on dit qu’ils sont parallèles. Il y a deux sortes de parallélisme :
– le parallélisme vrai, où n processus s’exécutent surm processeurs (architecture multiprocesseur),
– le parallélisme simulé, oùn processus s’exécutent sur un processeur qui est successivement attribué à chacun des processus.

Accès aux ressources

Une ressource est dite locale à un processus s’il est le seul à pouvoir l’utiliser ; une ressource locale disparaît à la mort du processus.
Une ressource qui n’est locale à aucun processus est dite globale.
Une ressource est dite partageable avec n points d’accès si cette ressource peut être attribuée, au même instant, à n processus au plus (un fichier ouvert en lecture, les commandes sous UNIX).
Une ressource partageable avec un point d’accès est dite critique (processeur, imprimante, etc.).
On appelle section critique d’un processus, la phase du processus pendant laquelle la ressource critique est utilisée par ce processus.
Un ensemble de processus peut soit entrer en compétition pour l’accès à une ressource, soit fonctionner en coopération pour mener à bien une application. Que l’on soit dans une situation de parallélisme vrai ou simulé (les tranches d’activités des processus sont trop courtes pour être prises en compte dans la programmation), dès l’instant où plusieurs processus ont une ressource en commun, l’ordre dans lequel ils s’exécutent n’est pas indifférent. Il apparaît alors des problèmes de synchronisation et de communication entre les processus.

Exclusion mutuelle

L’exclusion mutuelle est le problème qui se pose lorsqu’une ressource critique est nécessaire à la continuation de plusieurs processus.
Pour mieux comprendre cette notion d’exclusion mutuelle et les problèmes qui lui sont associés, étudions l’exemple d’un client d’un magasin qui envoie deux commandes séparées pour deux articles différents (le montant de l’argent disponible sur le compte est m, la première facture est d’un montant m1, la seconde d’un montant m2). Le service comptabilité traite ces commandes simultanément grâce au programme informatique suivant :
/* contexte commun */
compte_utilise = FAUX;
compte_client = 1000;
/* corps du programme du processus i */ derniere_facture = mi;
while (compte_utilise == VRAI);
<- /* le problème se situe ici */ compte_utilise = VRAI;
compte_client = compte_client – derniere_facture; compte_utilise = FAUX;
Chacune des factures étant associée à un processusi réalisant une facturation d’un montant mi. Pour l’instant, nous supposerons que les deux processus ont des vitesses quelconques et inconnues. Très simplement, nous avons associé au omptec du client la variable booléenne compte_utilise, commune aux deux processus, et prenant la valeur vraie ou faux selon qu’un processus utilise ou non la ressource « compte client ».
Dans le cas d’une machine multiprocesseurs et avec la variable compte_utilise initialisée à faux, chaque processus accède en mêmetemps à celle-ci et donc la teste avant que l’autre ne lui ait affecté la valeur vraie. Pour chacun des processus, la valeur m du compte est alors lue, et la valeur finale du compte sera égale à m – m1 ou m – m2 (selon que le processus1 ou le processus2 modifie le compte en premier) au lieu d’être égale à m – m1 – m2.
Dans le cas d’une machine monoprocesseur et avec la variable compte_utilise initialisée à faux, le processus1 accède à la variable compte_utilise et la teste, puis se trouve interrompu par le système qui donne la main au processus2. Le processus2 accède alors à la variable compte_utilise et la teste. Par conséquent les deux processus ont testé la variable compte_utilise avant que l’un ou l’autre des processus ne lui aitaffecté la valeur vraie, ce qui conduit à la situation précédemment décrite.
L’analyse de cet exemple montre que le problème décrit vient d’une part du fait qu’un processus peut être interrompu entre deux instructions, et d’autre part que des ressources critiques, lorsqu’elles sont utilisées par un processus, doivent rester inaccessibles aux autres processus. De nombreuses solutions ont été proposée pour résoudre ce problème de l’exclusion mutuelle. Avant d’étudier les principales, définissons les propriétés essentielles que toutes devront respecter :
– à tout instant, un processus au plus peut se trouve r en section critique,
– si plusieurs processus sont bloqués en attente de la ressource critique, alors aucun processus ne se trouve en section critique, et l’un d’eux doit pouvoir y rentrer au bout d’un temps fini,
– si un processus est bloqué hors d’une section critique, ce blocage ne doit pas empêcher l’entrée d’un autre processus dans sa section critique,
– la solution doit être la même pour tous les processu .

Attente active

L’attente active est une solution câblée du problème de l’exclusion mutuelle, et tous les ordinateurs ne disposent pas d’un tel mécanisme. L’emploi d’une unique variable booléenne ne convient pas car, entre le test de la variable booléenne et son affectation par un processus i, un autre processus j avait la possibilité d’accéder à cette variable. La solution la plus immédiate consiste donc à réaliser ces deux opérations simultanément :, la nouvelle opération s’appelant TAS (Test And Set). Cette instruction, agissant sur une variable m, peut se décrire ainsi :
instruction TAS(m)
debut
bloquer l’accès à la cellule mémoire m
lire le contenu de m
si m est faux alors
m <- vrai
compteur_ordinal <- compteur_ordinal + 2
sinon
compteur_ordinal <- compteur_ordinal + 1 fin si
libérer l’accès à la cellule mémoire m
fin
Soit p une variable booléenne indiquant que la ressourcecritique R est occupée ou non ;p est initialisée à faux. L’entrée en section critique est réalisée par E: TAS(p) goto E;
D’après ce qui précède, le processus ne pourra sortir de cette boucle, c’est à dire exécuter l’instruction suivant le branchement, que s’il trouve p à faux pendant l’exécution de l’instruction TAS.
La sortie de la section critique est réalisée par
p <- faux
Sur l’exemple du compte client dans un grand magasin, le programme associé à un processus est le suivant :
/* contexte commun */
compte_utilise = FAUX;
compte_client = 1000;
/* corps du programme du processus i */ derniere_facture = mi;
E : TAS(compte_utilise);
goto E;
compte_client = compte_client – derniere_facture; compte_utilise = FAUX;
Il est important de remarquer que pour programmer l’exclusion mutuelle d’une ressourceR, on a recouru à un mécanisme câblé d’exclusion mutuelleà une autre ressource p. Cette solution est appelée attente active car le processus bloquésur p boucle sur l’instruction de test et monopolise donc le processeur.

Les sémaphores

Les sémaphores sont une des solutions les plus élégantes au problème de l’exclusion mutuelle. Un sémaphore s est constitué d’une variablees et d’une file d’attentefs. Lors de la création du sémaphore, es reçoit une valeur positive ou nulle et ss est vide. On ne peut agir sur un sémaphore qu’au travers des deux primitives indivisibles suivantes :
Ps
début
es <- es – 1
si es < 0 alors etatr <- bloqué
mettre le processus r dans la file fs fin si
fin
Vs
début
es <- es + 1
si es • 0 alors
sortir un processus q de la file fs
etatq <- actif
fin si
fin
Un sémaphore est donc un dispositif qui thésauriseun certain nombre d’autorisation de passage (es est ce nombre) et qui gère une file de processus en attente de passer. L’opération Ps correspond à une demande de passage, tandis que l’opération Vs est une autorisation de passage. Afin de ne pas retomber dans les travers précédents, le système devra, pour un sémaphore s, assurer l’exclusion mutuelle de es et fs, ainsi que l’indivisibilité des procéduresPs et Vs.
L’exclusion mutuelle sera réalisée grâce à un sémaphore appelémutex (mutuelle exclusion), initialisé ainsi :
fmutex <- vide emutex <- 1
et utilisé comme ceci :
Pmutex
instructions formant la section critique Vmutex
Comme on peut le constater, dès lors qu’un processu désire utiliser une ressource critique, il doit obligatoirement réaliser l’opérationPmutex avant. Deux cas se présentent :
– le processus décrémente d’une unité la variablemutex, et comme personne n’utilise la ressource critique, la valeur de emutex qui était égale à1 passe à 0 ; la procédurePmutex se termine.
– le processus décrémente d’une unité la variablemutex, et comme un processus utilise la ressource critique, la valeur de emutex devient ou reste négative ; le processus demandeur est alors mis dans la file d’attente fmutex et la procédure Pmutex se termine.
La libération de la ressource critique se fait obligatoirement par la procédure Vmutex. Deux cas se présentent :
– le processus incrémente d’une unité la variableemutex, et comme personne d’autre n’a émis le désir d’utiliser la ressourceritique,c la valeur de emutex qui était égale à0 passe à 1 ; la procédureVmutex se termine.
– le processus incrémente d’une unité la variableemutex, comme d’autres processus ont émis le désir d’utiliser la ressourcecritique, la valeur de emutex est négative et l’on sort donc de la file d’attente l’un des processus demandeurs pour le rendre actif ; la procédureVmutex se termine.
A titre d’exemple, nous reprendrons la gestion du compte client pour trois processus P1, P2,
P3 exécutant le programme suivant :
derniere_facture = ni;
P(compte_utilise);
compte_client = compte_client – derniere_facture; V(compte_utilise);

Synchronisation entre processus

Dans le cadre de la réalisation d’une tâche par plusieurs processus, il existe des relations qui fixent leur déroulement dans le temps. L’ensemble de ces relations est généralement désigné par le terme de synchronisation.
Le problème de la synchronisation consiste donc à définir un mécanisme permettant à un processus actif :
– d’en bloquer un autre ou de se bloquer lui-même enattendant un signal d’un autre processus,
– d’activer un autre processus en lui transmettant éventuellement de l’information. Deux techniques sont envisageables pour résoudre ceproblème de synchronisation :
– l’action directe qui consiste pour un processus à agir sur un autre processus en le désignant par son identité. On utilise généralementdeux primitives ayant pour argument l’identité du processus à bloquer ou à activer.
– l’action indirecte qui met en jeu, non plus l’identité du processus, mais un ou plusieurs objets intermédiaires connus des processu coopérants, et manipulables par eux uniquement au travers de primitives spécifiques.

Synchronisation par sémaphores privés

La synchronisation par sémaphore privés est un mécanisme d’action indirecte. Un sémaphore s est un sémaphore privé d’un processus, si seul ce processus peut exécuter l’opération P(s) ; les autres processus pouvant agir sur le sémaphore s uniquement par l’opération V(s).
La synchronisation par sémaphore privé pose alors comme principe qu’un signal d’activation sera envoyé par la primitive V, et attendu par la primitive P. Ainsi un processus, dont l’évolution dépend de l’émission d’un signal par un autre processus, se bloque, au moyen d’une primitive P, derrière son sémaphore privé initialisé à zéro.e L signal de réveil de ce processus bloqué est obtenu en faisant exécuter par un autre processus une opération V sur le même sémaphore.
Par exemple, soit p un processus dont l’évolution dépend de l’émission d’un signal envoyé par un processus q : en introduisant le sémaphore signal initialisé à zéro, la solution du problème se programme comme suit :
processus p processus q
debut debut
Ip1; Ip2; … Ipn; Iq1; Iq2; … Iqn;
P(signal) V(signal)
… ; … ;
fin fin
Deux situations sont possibles :
– le processus p est déjà bloqué sur la primitiveP(signal) lorsque le processus q exécute la primitiveV(signal), alors le réveil devient effectif ;
– le processus p est actif (il exécute par exemple l’instruction Ipn) lorsque le processus q exécute la primitive V(signal), alors le signal est mémorisé (le sémaphore passe à 1) et lorsque le processus p exécutera la primitive P(signal) il ne se bloquera pas.

Problème des Philosophes et des Spaghetti

Il est possible de combiner l’emploi des sémaphores d’exclusion mutuelle et des sémaphores privés, pour réaliser des modèles de synchronisation plus complexes. D’une manière générale, dès qu’un processus p, pour poursuivre ou non son évolution, a besoin de connaître la valeur de certaines variables d’état, qui peuvent être modifiées par d’autres processus (un processus q par exemple), il ne peut les consulter que dans une section critique. Comme il ne peut se bloquer à l’intérieur de celle-ci, le schéma suivant est utilisé :
P(mutex)
modification et test des variables d’état
si on peut continuer alors V(sempriv) fin si
V(mutex)
P(sempriv)
Si le test des variables d’état indique que le processus p peut continuer, alors en exécutant l’opérationV(sempriv), il se donne un droit de passage, et à la sortie d e la section critique il ne se bloquera pas sur l’opération P(sempriv). Dans le cas contraire, l’opération V(sempriv) est sautée, et le processus p se bloque à la sortie de sa section critique sur l’opérationP(sempriv) puisque le sémaphore était initialisé 0à.
L’activation par un autre processus (le processus q par exemple) s’écrit :
P(mutex)
modification et test des variables d’état, suivi éventuellement d’une opération V sur le sémaphore privé sempriv V(mutex)

Chapitre 1 / Généralités
1. Historique des systèmes d’exploitations
2. Fonctions d’un système d’exploitation
3. Le système UNIX
3.1 Présentation et Structure du système UNIX
3.2 Les fichiers sous UNIX
3.3 La redirection des entrées-sorties
3.4 Quelques commandes
Chapitre 2 / Les Processus
1. Définitions
1.1 Instructions, processeur, processus
1.2 Ressource, état d’un processus
1.3 Accès aux ressources
2. Exclusion mutuelle
2.1 Attente active
2.2 Les sémaphores
3. Synchronisation entre processus
3.1 Synchronisation par sémaphores privés
3.2 Problème des Philosophes et des Spaghetti
4. Les processus sous Unix
4.1 Généralités
4.2 Création de processus
4.3 Synchronisation de processus
Chapitre 3 / Gestion des processus
1. Contexte d’un processus
1.1 Informations utilisées par le processus
1.2 Informations utilisées par le système
2. Le parallélisme
3. Allocation du processeur réel
3.1 Définition du problème
3.2 Le distributeur
3.3 Changement de contexte entre deux processus
3.4 Stratégie d’allocation du processeur
Chapitre 4 / Allocation de la mémoire
1. Définitions
1.1 Espace mémoire réel / espace mémoire virtuel
1.2 Mémoire virtuelle
1.3 Mémoire uniforme / Mémoire hiérarchisée
2. Un cas de gestion de mémoire uniforme : le PC
3. Gestion de la mémoire hiérarchisée
3.1 Le Va et Vient (Swapping)
3.2 La pagination
3.3 La segmentation
Chapitre 5 / La mémoire secondaire
1. Etude du disque magnétique
1.1 Structure physique d’un disque
1.2 Le pilote du disque
2. Le système de gestion des fichiers
2.1 La notion de fichier
2.2 L’organisation du disque et la sauvegarde des fichiers
3. Le système de gestion de fichiers d’UNIX
3.1 La structure arborescente
3.2 Les types de fichiers
3.3 Organisation du disque
Bibliographie
1. Systèmes d’exploitation
2. UNIX