Système d’Exploitation

et
Outils de programmation
Introduction
 Le système d’exploitation (SE) est un
ensemble de programmes qui
 Réalise l’interface entre le matériel de
l’ordinateur et les utilisateurs
 Prend en charge la gestion des
ressources de la machine et le partage de
celles-ci
 physiques: mémoire, unités E/S, UCT...
 Logiques = virtuelles: fichiers et bases de
données partagés, canaux de communication
logiques, virtuels...
 les ressources logiques sont bâties par le
2
logiciel sur les ressources physiques
Pourquoi étudier les SE?

 Logiciel très important…

 tout programme roule sur un SE
 interface usager-ordinateur
 Les SE utilisent beaucoup
d ’algorithmes et structures de données
intéressants
 Les techniques utilisées dans les SE sont
aussi utilisées dans nombreuses autres
applications informatiques
 il faut les connaître 3
Développement de la théorie des SE
 La théorie des SE a été développée surtout
dans les années 1960 (!!)
 A cette époque, il y avait des machines très
peu puissantes avec lesquelles on cherchait
à faire des applications comparables à celles
d’aujourd’hui (mémoire typique: 100-500K!)
 Ces machines devaient parfois desservir des
dizaines d’usagers!
 Dont le besoin de développer des principes
pour optimiser l’utilisation d ’un ordinateur.
 Principes qui sont encore utilisés
4
Évolution historique des SE
 Le début: routines d`E/S, amorçage système
 Systèmes par lots simples
 Systèmes par lots multiprogrammés
 Systèmes à partage de temps
 Ordinateurs personnels
 SE en réseau
 SE répartis
 Les fonctionnalités des systèmes simples se
retrouvent dans les systèmes complexes.
 Les problèmes et solutions qui sont utilisés dans les
systèmes simples se retrouvent souvent dans les
systèmes complexes. 5
Évolution des SE

6
Une synthèse historique
Mainframes et grands serveurs
Multics et beaucoup d’autres
(1960s)

Unix
(1970)
Ordinateurs Personnels
MS-DOS
(1981)
Mac/OS
(1984)

Windows NT Windows
Linux (1988) (1990)
(1991)
Solaris (1995)
Windows 2000
7
Windows XP
Types de systèmes

 Mono utilisateur, monotâche

 (single user, single tasking)
 Mono utilisateur, multitâches
 (single user, multitasking)
 Multi utilisateurs, multitâches

8
Multi utilisateurs, multitâches

 L’utilisateur de la machine peut

interagir avec l’exécution de son
programme =>
 Le but principal poursuivi par les
systèmes interactifs
 Offrir pour chaque exécution le plus petit
temps de réponse possible
 Travail en temps partagé
 Exemple: système Unix ou Linux
9
« Network operating systems »
 SEs en réseau fournissent:

 Partage de fichiers (systèmes client-

serveur)
 Patrons de communication (protocoles)
 Autonomie des ordinateurs

10
Systèmes temps réel

 Liés au contrôle de procédé

 Les exécutions de programmes sont

soumises à des contraintes temporelles

 Exemple: LynxOS, VxWORKS

11
Types de systèmes
 Systèmes embarqués
 Système temps réel dédié pour une
application particulière
 Injection automatique pour une auto
 Programmation micro-onde
 Systèmes distribués - répartis
 il y a un SE qui fonctionne entre
ordinateurs
 l ’usager voit les ressources éloignées
comme si elles étaient locales
12
Services et facilités

 Le SE réalise une couche logicielle

placée entre la machine matérielle et les
applications
 Le SE typique fournis (+ ou -)
 Interface usager-ordinateur
 Gestion des fichiers
 Support des entrées-sorties
 Exécution de programmes: chargement,
exécution (load, run), gestion de la
concurrence
13
Services et facilités

 Détection et traitement d ’erreurs

 Services Réseau et communication
 Gestion de la mémoire
 Gestion de la protection
 Support pour l’administration du système

14
Services et facilités

 Support des entrées-sorties

 Accès aux périphériques, la liaison entre les
appels de haut niveau des programmes
utilisateurs et les opérations de bas niveau
de l’unité d’échange responsable du
périphérique (pilote d’entrées-sorties)
 Logiciels de contrôleur de périphérique ( I/O
device driver), certains sont en ROM

15
Services et facilités

 Services Réseau et communication

(Network and Communications Support
Services)
 Fonctions nécessaire à l’interconnexion de
l’ordinateur dans un réseau (protocole
TCP-IP)
 Programmes d’applications et extension
(ex. E-mail, login, etc.)
 Pilotes pour modems, communication
sans fils, etc.
16
Services et facilités

 Gestion de la protection
 Mécanismes garantissant que les ressources
de système ne peuvent être utilisées que par
les programmes auxquels les droits
nécessaires ont été accordés (protection de
système et la machine des programmes
utilisateurs)
 Protège SE des programmes d’autres utilisateurs
 Protège un utilisateur d’un autre utilisateur
 Empêche les entrées non-autorisées dans le
système (service de login)
17
Services et facilités

 Support pour l’administration du système

 L’administrateur du système:
 Configuration du système
 Ajout ou enlèvement des utilisateurs/privilèges
 S’occupe de la sécurité du système
 Gère le système de fichier
 S’occupe des sauvegardes, installation, mise
à jour des logiciels et de SE
 Optimise le système
18
SE
 SE s’interface avec les applications du
niveau utilisateur par le biais de fonctions
prédéfinies – routines systèmes
 Les appels des routines systèmes peuvent
se faire par biais
 D’un appel système (API)
 D’une commande du langage de commandes
 L’exécution des routines systèmes s’effectue
sous un mode privilégié – mode superviseur
 Un programme utilisateur s’exécute par
défaut selon un mode utilisateur
19
 SE
 Mode utilisateur : le jeu d’instructions utilisables par
le programme est réduit
 Mode superviseur: aucune restriction
 Passage du mode utilisateur au mode superviseur
constitue une commutation de contexte
 Trois causes majeures provoquent le passage du
mode utilisateur au mode superviseur
 Utilisateur appelle une fonction système
 L’exécution d’une opération illicite (trappe ou l’exception)
 La prise en compte d’une interruption par le matériel et
SE
20
 Chargement d’un SE
 Les programmes composant le SE sont
conservés sur un support de masse
 Au démarrage l’ordinateur exécute un code
placé dans une zone de mémoire morte
(ROM), programme d’amorçage ou boot-
strap (test du matériel de la machine,
chargement d’un programme d’amorce plus
sophistiqué)
 Une fois cette amorce placée en mémoire
centrale, elle s’exécute et charge les
programmes du SE.
21
Bootstrapping

Copyright 2010 John Wiley & Sons, Inc. 22

 Le noyau (kernel) du SE
 La partie résidente (toujours en RAM) du SE est appelée
Kernel = noyau
 Les autres parties sont amenées en RAM au besoin
 Contient les fonctionnalités critiques du SE: elles doivent
toujours être prêtes à l ’utilisation
 traitement d ’interruptions
 gestion de UCT
 gestion mémoire
 communication entre processus
 etc.
 À part ça, quoi exactement mettre dans le kernel est une
question pour les concepteurs des SE
 La plupart des fonctionnalités discutées dans ce cours
sont normalement dans le kernel
23
Interface usager-ordinateur
 Types d’interfaces utilisateur
 Interface de ligne de commande
 CLI – Command Line Interface
 Windows command prompt
 UNIX/Linux command prompt
 Interface graphique
 GUI – Graphical User Interface
 Apple Macintosh, Windows, stations de travail Sun, les
différentes versions de Linux

24
 Langage de commandes
 Les ordinateurs modernes ont la possibilité
de regrouper les commandes CLI en
miniprogrammes
 Langage de commandes (scripts)
 Les commandes sont analysées par l’outil
interpréteur de commande qui appelle la routine
système appropriée en assurant le passage des
paramètres
 Chaque SE a son langage de commandes
propre
 JCL (Job Control Language) de SE MVS
 Langage Shell de SE Unix 25
GUI Interface – Windows Vista

Copyright 2010 John Wiley & Sons, Inc. 26

GUI Interface – Linux KDE

Copyright 2010 John Wiley & Sons, Inc. 16-27

27
GUI Interface – MacIntosh OSX

Copyright 2010 John Wiley & Sons, Inc. 16-28

28
GUI vs. CLI
GUI CLI
 Avantages  Avantages
 Facile à apprendre et  Plus flexible et puissant
utiliser  Plus performant pour
utilisateurs expérimentés
 Désavantages  Peut combiner des
 Plus difficile à implémenter commandes
 Plus exigeant en terme de
HW/SW  Désavantages
 Requiert beaucoup de  Plus difficile à apprendre et
mémoire utiliser
 SW est complexe et difficile
à écrire

Copyright 2010 John Wiley & Sons, Inc. 29

Gestion des fichiers
 Allocation des mémoires de masse ainsi
que l’accès aux données stockées
(système de gestion de fichiers et notion
de fichier)
 Assure la conservation des données sur
un support de masse non volatile

30
Système de gestion de fichiers
 Offre à l’utilisateur une unité de stockage
indépendante des propriétés physiques des
supports de conservation: le fichier
 Fichier logique (vue de l’utilisateur)
 Fichier physique
 Assure la correspondance entre le fichier
logique et le fichier physique
 Structure de répertoire

31
Système de gestion de fichiers
 Le fichier logique
 Un type de données standard défini dans les langages
de programmation sur lequel un certain nombre
d’opérations peuvent être réalisées
 Création, ouverture, fermeture, destruction
 Les opérations de création ou d’ouverture effectuent la liaison
du fichier logique avec le fichier physique
 Un ensemble d’enregistrements, un type de données
regroupant des données de type divers liées entre
elles par une certaine sémantique inhérente au
programme qui les manipule

32
Système de gestion de fichiers

 Fichier physique
 Correspond à l’entité allouée sur le
support permanent et contient
physiquement les enregistrements
définis dans le fichier logique
 Le fichier physique est constitué d’un
ensemble de blocs physiques qui
doivent être alloués au fichier logiques

33
Fichier physique
 Différentes méthodes d’allocation de la
mémoire secondaire
 Allocation contiguë
 Allocation par zones
 Allocation par blocs chaînés
 Pour pouvoir allouer des blocs aux
fichiers il faut connaître à tout moment
l’ensemble des blocs libres et donc gérer
l’espace libre sur le disque
 Liste d’espace libre
34
Exemple
 Allocation par blocs chaînes (DOS/Windows)
 L’ensemble des chaînages des blocs de fichiers est
regroupé dans une table FAT(File Allocation Table)
 Nombre d’entrées = Nombre de blocs de données sur
le disque
 Chaque entrée de la table correspond à un bloc du
disque et contient:
 Si le bloc appartient à un fichier et n’est pas le dernier bloc
de ce fichier => le numéro du bloc suivant
 Si le bloc appartient à un fichier et est le dernier bloc de ce
fichier => une valeur de fin de fichier
 Si le bloc n’appartient pas à un fichier => une valeur de bloc
libre

35
Répertoire
 Correspondance fichier logique – fichier physique
 Effectue par le biais d’une table appelée
répertoire qui contient des informations de
gestion des fichiers
 Le nom logique du fichier
 Le type du fichier
 Codé dans son nom logique à l’aide d’une extension
 L’adresse physique du fichier
 Dépend de la méthode d’allocation mise en œuvre sur le
disque
 La taille en octets ou en blocs du fichier
 Le nom du propriétaire
 Les protections appliquées au fichier
36
Répertoire
 Le système de gestion de fichiers offre des
primitives permettant de manipuler les répertoires
 Les différentes structures de répertoires
existantes se distinguent par le nombre de
niveaux
 Structure en arbre est composée d’un répertoire initial (la
racine) et d’un ensemble de nœuds constitués par l’ensemble
de sous-répertoires et d’un ensemble de feuilles qui sont les
fichiers eux-mêmes
 Le nom complet d’un fichier (path name) est
constitué de son nom précédé du chemin dans
la structure de répertoires depuis la racine
37
Partitions
 Gérer des milliers de fichiers dans un seul
ensemble – difficile
 Solution – diviser l’ensemble du système de
gestion de fichiers en morceaux indépendants –
partitions
 Partition constitue un disque virtuel auquel est associé
un répertoire qui référence l’ensemble des fichiers
présents sur la partition
 Chaque partition est repérée par un nom – label
 La partition doit être connectée à l’arborescence de
fichiers de la machine

38
Services et facilités
 Gestion du processeur
 Allocation du processeur aux différents
programmes: ordonnancement
 Selon le type de SE l’algorithme
d’ordonnancement répond à des objectifs différents
 Gestion de la concurrence
 Communication entre plusieurs programmes,
synchronisation de l’accès aux données partagées
(outil de communication et de synchronisation
entre programmes)

39
Notion de Processus
 Définitions

 États d’un processus

 Bloc de contrôle du processus

 Opérations sur les processus

40
Notion de Processus: Définitions

 Un programme en cours d’exécution

auquel est associé un environnement
processeur (PC, registres généraux,
…) et un environnement mémoire
(zone de code, de données et de pile)
appelés contexte du processus
 Instance dynamique d’un programme
et incarne le fil d’exécution de celui-ci
dans un espace d’adressage protégé
41
Notion de Processus: États d’un processus

 Au fur et a mesure qu’un processus

exécute, il est caractérisé par un état
 Lorsque le processus obtient le processeur et
s’exécute, il est dans l’état élu. L’état élu est
l’état d’exécution du processus
Élu

 Lors de l’exécution, le processus peut

demander à accéder à une ressource. Il quitte
alors le processeur et passe dans l’état
bloqué. L’état bloqué est l’état d’attente d’une
ressource autre que le processeur
Bloqué
42
Notion de Processus: États d’un processus

 Lorsque le processus est passé dans l’état

bloqué, le processeur a été alloué à un
autre processus. Le processeur n’est donc
pas forcément libre. Le processus passe
dans l’état prêt. L’état prêt est l’état
d’attente du processeur.

Prêt

43
 Diagramme d’états d’un processus
Transition Prêt –>Élu – opération d’élection
Transition Élu->Bloqué – opération de blocage
Transition Bloqué->Prêt – opération de déblocage Fin
Réveil

Élu En exécution
Élection

En attente du Prêt
processeur

Déblocage
Bloqué Blocage
Création d’un processus = état Prêt 44
 Bloc de contrôle du processus
Identificateur processus
 PCB (Process Control État du processus
Block) – une structure
Compteur ordinal
de description du Contexte pour reprise
processus associé au (registres et pointeurs, piles …)
programme exécutable Chaînage selon les files de
 PCB permet la l’Ordonnanceur
sauvegarde et la Priorité (ordonnancement)
restauration du Informations mémoire
contexte mémoire et (limites et tables
du contexte pages/segments)
processeur lors des Informations sur les ressources
utilisées fichiers ouverts, outils
opérations de de synchronisation, entrées-
commutations de sorties
45
contexte Informations de comptabilisation
Opérations sur les processus

 SE offre les opérations de gestion des

processus
 Opérations pour la gestion des
processus
 Création de processus
 Destruction de processus
 Suspension de l’exécution
 Reprise de l’exécution

46
Opérations sur les processus

 Création de processus
 Un processus peut créer un ou plusieurs
autres processus en invoquant un appel
système de création de processus
 Le processus créateur – processus père
 Les processus créés – processus fils
 Au fil des opérations de création initiées par
les processus, se développe un arbre de
filiation entre processus

47
Opérations sur les processus

 Création de processus
 Les opérations de création de processus
admettent les variantes suivantes selon
les SE
 Le processus créé hérite ou non de données
et du contexte de son processus créateur
 Le processus créé peut s’exécuter
parallèlement à son père. Dans certains
systèmes, le processus père doit attendre la
terminaison de ses fils pour pouvoir reprendre
sa propre exécution
48
Opérations sur les processus
 Destruction de processus
 Processus a terminé son exécution
 Le processus s’autodétruit en appelant une routine
système de fin d’exécution
 Processus commet une erreur irrécouvrable
 Le processus est terminé par le système
 Autre processus demande la destruction du
processus
 Appel à une routine système
 Le contexte du processus est démantelé
 Ressources allouées au processus sont libérées
 Bloc de contrôle est détruit
49
Opérations sur les processus
 Suspension d’exécution –
momentanément arrêter l’exécution
d’un processus pour la reprendre
ultérieurement
 Le contexte du processus est sauvegardé
dans son PCB
 Le processus passe dans l’état bloqué
 Reprise d’exécution
 Transition de déblocage, le processus entre
dans l’état prêt

50
Ordonnancement sur l’unité centrale

 Ordonnancement préemptif et non préemptif

 Entités systèmes responsable de

l’ordonnancement

 Politiques d’ordonnancement

 Exemples
 Ordonnancement sous Linux

51
Ordonnancement sur l’unité centrale

 La fonction d’ordonnancement gère le

partage du processeur entre les
différents processus en attente pour
s’exécuter, c’est-à-dire entre les
différents processus qui sont dans
l’état prêt.

52
Ordonnancement préemptif et
non préemptif

Fin
Réveil

Élu En exécution
Élection

En attente du Prêt Préemption

processeur

Déblocage
Bloqué Blocage

Transition élu->prêt – réquisition du processeur, préemption

53
Ordonnancement préemptif et
non préemptif
 Selon si l’opération de réquisition est autorisée ou non,
l’ordonnancement est qualifié d’ordonnancement
préemptif ou non préemptif
 Ordonnancement non préemptif
 Transition de l’état élu vers l’état prêt est interdite: un processus
quitte le processeur s’il a terminé son exécution ou s’il se bloque

 Ordonnancement préemptif
 La transition de l’état élu vers l’état prêt est autorisée: un processus
quitte le processeur s’il a terminé son exécution, s’il se bloque ou si
le processeur est réquisitionné
54
Déroulement des opérations
d’ordonnancement

Élu Read (données, disque) Prêt

Élection

Bloqué Élu

Prêt Fin d’entrées-sorties

Prêt

Élu
Les opérations d’ordonnancement prennent place lors de tout changement d’états
55
des processus
Entités systèmes responsable de
l’ordonnancement
 Les processus prêts et bloqués sont gérés dans
deux files d’attentes distinctes qui chaînent leur PCB
 Le module Ordonnanceur (scheduler) trie la file des
processus prêts. Le tri s’appuie sur un critère donné
spécifié par la politique d’ordonnancement

 Le répartiteur (dispatcher) alloue un processeur parmi

les processeurs libres (système multiprocesseur) à la
tête de file de la liste des processus prêts

56
Entités systèmes responsable de
l’ordonnancement
Préemption
Prêts
CPU
Répartiteur PCB PCB PCB PCB Ordonnanceur
CPU Classement selon une
politique d’ordonnancement
Élection
CPU
PCB PCB PCB PCB
Blocage Déblocage
Bloqués

Ordonnanceur et répartiteur
57
Politiques d’ordonnancement
 Politique d’ordonnancement détermine
quel sera le prochain processus élu

 Selon si la préemption est autorisée ou

non, la politique d’ordonnancement sera
de type préemptive ou non

 Objectifs d’ordonnancement diffèrent

selon les types de systèmes 58
Politiques d’ordonnancement
 Premier Arrivé, Premier Servi
 Les processus sont élus selon l’ordre dans lequel ils
arrivent dans la file d’attente des processus prêts

 Il n’y a pas de réquisition

 Avantages – Simplicité

 Inconvénient
 Processus de petit temps d’exécution sont pénalisés en terme
de temps de réponse par les processus de grand temps
d’exécution qui se trouvent avant eux dans la file d’attente
59
Politiques d’ordonnancement
 Plus Court d’Abord
 L’ordre d’exécution des processus est fonction de
leur temps d’exécution

 Sans réquisition

 Remédie à l’inconvénient pour PAPS

 Difficulté
 Connaissance a priori des temps d’exécution des
processus

60
Politiques d’ordonnancement
 Politique par priorité
 Chaque processus possède une priorité

 À un instant donné, le processus élu est le processus

prêt de plus forte priorité

 Deux version selon si la réquisition est autorisée ou

non
 Réquisition est admise
 Le processus couramment élu est préempté dès qu’un
processus plus prioritaire devient prêt

– Risque de famine pour les processus de petite priorité

61
 Politiques d’ordonnancement
 Politique du tourniquet (round robin)
 Systèmes en temps partagé
 Le temps est découpé en tranches, quantum de temps (10 – 100 ms)

 Lorsqu’un processus est élu, il s’exécute au plus durant un

quantum de temps. Si le processus n’a pas terminé son
exécution à l’issue du quantum de temps, il est préempté et
il réintègre la file des processus prêts mais en fin de file

 La valeur du quantum – un facteur important de

performance (commutations de contexte)

62
Exemple
 Systèmes actuels – combinaison de deux des
politiques: celles des priorités fixes et celles du
tourniquet
 La file des processus prêts est divisée en autant de
sous files Fi qu’il existe de niveaux de priorité

 Chaque file est gérée en tourniquet avec un quantum Qi

 Pour remédier au problème de famine – mécanisme

d’extinction de priorité
 La priorité d’un processus baisse au cours de son exécution
63
Services et facilités

 Gestion de la concurrence
 Communication entre plusieurs
programmes, synchronisation de
l’accès aux données partagées (outil
de communication et de
synchronisation entre programmes)

64
 Gestion de la concurrence
 Les processus peuvent avoir besoin de
communiquer entre eux pour échanger des
données par le biais
 D’une zone mémoire partagée
 D’un fichier
 En utilisant les outils de communication offerts par le
système d’exploitation
 Les processus ne sont plus indépendants
 Accès concurrents aux ressources logicielles

65
Gestion de la concurrence
 Une ressource désigne toute entité dont a
besoin un processus pour s’exécuter
 Matérielle (le processeur, un périphérique)
 Logicielle (variable)
 Une ressource est caractérisée par
 un état
 libre
 occupée
 Nombre de points d’accès
 Le nombre de processus pouvant l’utiliser en même
temps

66
Gestion de la concurrence
 Ressource critique – ressource ne
pouvant être utilisée que par un seul
processus à la fois
 Processeur, imprimante
 Utilisation d’une ressource
 Allocation de la ressource
 Utilisation
 Restitution de la ressource

67
 Gestion de la concurrence
 Les phases d’allocation et de
restitution d’une ressource doivent
assurer que la ressource est utilisée
conformément à son nombre de points
d’accès
 Étape d’allocation
 Peut bloquer un processus, si tous les
points d’accès sont occupés

68
 Gestion de la concurrence
 Étape de restitution
 Peut entraîner le déblocage d’un autre
processus en attente d’accès
 Synchronisation entre processus doit
garantir une bonne utilisation des
ressources
 Une communication cohérente
 Sans perte de données

69
Services et facilités

 Gestion de la mémoire
 Allocation de la mémoire centrale: principe
de la mémoire virtuelle, à un instant
donné, seules les parties de code et
données utiles à l’exécution sont chargées
en mémoire centrale

70
 Gestion de la mémoire
 La tâche principale de la gestion de la
mémoire est de charger des programmes
en mémoire pour qu’ils soient exécuté par
le CPU
 Mémoire virtuelle
 La taille du programme, des données et de la pile
peut dépasser la mémoire disponible. Le SE
garde en mémoire les parties du programme qui
sont utilisées et stocke le reste dans le disque
 Cette méthode est basée sur deux principes de
gestions, la SEGMENTATION et la PAGINATION
71
 Gestion de la mémoire
 Pagination
 L’espace d’adressage du programme est découpé en
morceaux linéaires de même taille appelés pages
 L’espace de la mémoire physique est lui-même
découpé en morceaux linéaires de même taille appelés
case
 Taille page = case – définie par le matériel (selon SE entre 512
octets et 8192 octets)
 Charger un programme en mémoire centrale - placer
les pages dans les cases disponibles
 Pour connaître à tout moment quelles sont les cases libres en
mémoire centrale, le système maintient une table des cases
 Pour chaque case de la mémoire physique, information
– Libre ou occupée
72
– Si occupée, quelle page et quel processus la possèdent
Pages et Cases (1)

Programme Mémoire

Unité Page Case

Adresse Logique Physique

Taille de
2 to 4KB 2 to 4KB
l’unité
# de bits dans
Quantité Mémoire installée
l’instruction

Copyright 2010 John Wiley & Sons, Inc. 73

Pages et Cases (2)
Pages and Frames A Simple Page Table
Translation

Each program has its

collection of pages.

The total number of

pages can exceed the
number of frames
(physical memory).
Copyright 2010 John Wiley & Sons, Inc. 18-74
74
 Gestion de la mémoire
Page 1 4 Ko Mémoire

Page 2 Case 1
ALLOCATION
Page 3
Page 1 P1 Case 2
Table des cases
Page 4
Page 3 P1 -1 libre
1 P1
Espace d’adressage du processus P1 (16 Ko) Page1 P2 3 P1
1 P2
-1 libre
2 P1
Page 1 Page 2 P1
4 P1
ALLOCATION
Page 4 P1 2 P2
Page 2

Page2 P2 Case 8
Espace d’adressage du processus P2 (7 Ko)
75
Recherche d’une case

Copyright 2010 John Wiley & Sons, Inc. 18-76

76
 Gestion de la mémoire
 Conversion adresse logique – adresse physique
 L’espace d’adressage du processus étant découpé en
pages, les adresses générées dans cet espace
d’adressage sont des adresses paginées (relative au
début de la page)
 L’adresse : <numéro de page p, déplacement d
relativement au début de la page p>
 Une adresse logique de m bits, en considérant des
pages de 2n octets, les m-n premiers bits correspond
au numéro de page p et les n bits restants au
déplacement d dans la page

77
 Gestion de la mémoire
 Conversion adresse logique – adresse physique
 Il fait convertir l’adresse paginée générée au niveau du
processeur en une adresse physique équivalente
 L’adresse physique s’obtient à partir de son adresse
logique en remplaçant le numéro de page p par
l’adresse physique d’implantation de la case contenant
la page p et en ajoutant à cette adresse le
déplacement d du mot dans la page
 MMU (memory management unit) – un dispositif
matériel (partie de CPU), effectue cette conversion

78
Gestion de la mémoire
 Conversion adresse logique – adresse
physique
 Pour toute page il faut connaître dans quelle case
de la mémoire centrale celle-ci a été placée
 Correspondance page – case s’effectue grâce à une
structure – table de pages
 La table des pages – contient autant d’entrées que
de pages dans l’espace d’adressage d’un
processus
 Chaque processus a sa propre table des pages
 Chaque entrée – un couple <numéro de page,
numéro de case physique dans laquelle la page est
chargée> 79
Table de pages

Page Frame
Pages not in main memory:
1 6 page fault when accessed
2 4 Disk
3 1 2 3 4
4 8
5 5 6 7 8
6 10 9 10 11
7 1
8 2
9
10 7
11

Swap space Virtual Memory Pages

Copyright 2010 John Wiley & Sons, Inc. 80
80
Allocation de la mémoire pour 3
processus

Copyright 2010 John Wiley & Sons, Inc. 81

Table de cases
Inverted Page Table for the previous slide
The table represents what is in physical memory

Copyright 2010 John Wiley & Sons, Inc. 18-82

82
Gestion de la mémoire
 Le défaut de page
 Processus tente d’accéder à une page qui n’est pas
en mémoire centrale
 Accès à l’entrée p de la table des pages du processus actif
et test de la valeur du bit de validation V;
 Si la valeur du bit V est à 0, alors il y a défaut de page. Une
opération d’entrées-sorties est lancée pour charger la page
dans la mémoire centrale (l’adresse de la page sur le
disque est stockée dans la tables des pages)
 La page est placée dans une case libre, trouvée par
l’intermédiaire de la table des cases
 La table des pages du processus est mise à jour
 La conversion de l’adresse logique vers l’adresse physique
est reprise
83
Gestion de la mémoire
 Le remplacement de pages
 Traitement d’un défaut de page pour un processus
peut se faire
 Localement à ce processus
 Globalement sur l’ensemble des processus (plus souvent
mis en œuvre)
 Algorithmes de remplacement de pages
 FIFO (First In, First Out)
 LRU ( Least Recently Used)
 LFU (Least Frequently Used)
 MFU (Most Frequently Used)

84
Gestion de la mémoire
Algorithmes de remplacement de pages
 FIFO (First In, First Out)
 La page la plus anciennement chargée qui est
remplacée
 Performances ne sont pas toujours bonnes (l’âge ne
reflète pas d’utilité)
 LRU ( Least Recently Used)
 La page la moins récemment utilisée qui est remplacée
 Localité temporelle
 Le plus utilisé, mais plus coûteuse

85
Gestion de la mémoire
Algorithmes de remplacement de pages
 LFU (Least Frequently Used)
 La page la moins fréquemment utilisée est remplacée
 Problème vis-à-vis des pages abondamment référencées
sur un court laps de temps =>compteur pour ces pages –
elevé => ne sont pas retirées de la mémoire même si elles
ne sont plus jamais référencées
 MFU (Most Frequently Used)
 La page la plus fréquemment utilisée qui est remplacée
 L’argument à la base – une page ayant un petit nombre de
références vient sans doute d’être chargée en mémoire
centrale et doit donc y rester

86
Étapes lors de défaut de page

Copyright 2010 John Wiley & Sons, Inc. 18-87

87
 Gestion de la mémoire
 Conversion adresse logique – adresse physique
 Chaque processus dispose de sa propre table de
pages => chaque opération de commutation de
contexte se traduit par un changement de table des
pages de manière à ce que la table active
corresponde à celle du processus élu
 Deux approches de réalisation de la table des pages
 Structure matérielle réalisée grâce à des registres de la MMU
 Structure logicielle placée en mémoire centrale

88
 Gestion de la mémoire
 Réalisation de la table des pages
 Structure matérielle réalisée grâce à des registres de
la MMU
 Nécessite un accès à la mémoire
 Ne peut convenir que pour de petites tables des pages
 Structure logicielle placée en mémoire centrale
 Deux accès à la mémoire
 Un premier accès permet de lire l’entrée de la table des pages
correspondant à la page p cherchée et délivre une adresse
physique c de case dans la mémoire centrale
 Un second accès est nécessaire à la lecture ou l’écriture de
l’octet recherché à l’adresse c+d
 Réalisation des tables de pages de très grande taille

89
Gestion de la mémoire
 Protection de l’espace d’adressage des
processus
 Des bits de protection sont associés à chaque
page de l’espace d’adressage du processus et
permettent ainsi de définir le type d’accès
autorisés à la page
 Ces bits de protection sont mémorisés pour
chaque page dans la table des pages du
processus
 3 bits sont utilisés - l’autorisation d’accès en
 Lecture – r
 Écriture – w
 Exécution - x
90
Translation d’adresse

Copyright 2010 John Wiley & Sons, Inc. 91

Gestion de la mémoire
 Protection de l’espace d’adressage des
processus
 Lors d’un accès à une page, la cohérence du type
d’accès avec les droits associés à la page est
vérifiée et une trappe est levée par le SE si le type
d’accès réalisé est interdit
 Chaque processus ne peut avoir accès qu’à sa
propre table des pages =>chaque espace
d’adressage est protégé
 Pour que deux processus puissent partager un
ensemble de pages =>référencer cet ensemble
dans sa table des pages respective
92
Gestion de la mémoire

 Pagination
 Pagination multiniveaux
 L’espace d’adressages logiques supporté par les
SE actuels est très grand (de 232 à 264 octets)
 La table des pages d’un processus peut devenir
également de très grande taille et comporter
jusqu’à un million d’entrées
 Il n’est dès lors plus envisageable de charger de
manière contiguë la table des pages d’un processus
 Solution: paginer la table des pages elle-même

93
 Gestion de la mémoire
 Pagination
 Pagination multiniveaux
 L’adresse paginée devient un triplet <hp, p, d>
 hp – l’entrée d’une hypertable des pages
 Chaque entrée correspond à une page contenant une partie de
la table des pages du processus
 p – une entrée de cette partie de la table des pages
 d – un déplacement dans la page p
 L’hypertable des pages est placée en mémoire
centrale et son adresse d’implantation en mémoire
centrale est repérée par un registre matériel de la
MMU
 3 accès à la mémoire
94
Gestion de la mémoire
 Segmentation
 La pagination constitue un découpage de
l’espace d’adressage du processus qui ne
correspond pas à l’image que le programmeur a
de son programme
 Données
 Programme principal
 Procédures séparées
 Pile d’exécution
 La segmentation est un découpage de l’espace
d’adressage qui cherche à conserver le vue du
programmeur

95
 Gestion de la mémoire
 Segmentation
 Lors de la compilation, le compilateur associe un
segment à chaque morceau du programme compilé
 Segment est un ensemble d’emplacement
mémoire consécutifs non sécable
 Les segments d’un même espace d’adressage peuvent
être de taille différente
Segment 1
données 50 Ko
Segment 2 Segment 3
Programme 20 Ko 70 Ko
Fonction X
principale
Segment 4
Pile 25 Ko

96
Vue Utilisateur Segmentation
Segmentation

Copyright 2010 John Wiley & Sons, Inc. 97

Gestion de la mémoire
 Principe de la mémoire virtuelle
 à un instant donné, seules les parties de code et
données utiles à l’exécution sont chargées en
mémoire centrale
 Répartition de la mémoire centrale entre les
processus
 Allocation équitable ou fixe
 Même nombre de cases quelle que soit la taille de l’espace
d’adressage
 Allocation proportionnelle
 Proportionnellement à la taille des processus

98
Gestion de la mémoire
 Le principe de la mémoire virtuelle est
couramment implémenté avec la pagination à
la demande
 Les pages des processus ne sont chargées en
mémoire centrale que lorsque le processeur
demande à y accéder

99
Mémoire Virtuelle vs. Mémoire Cache

 Cache améliore le temps d’accès à la

mémoire
 Mémoire Virtuelle augmente la
quantité de la mémoire considérée
 Indépendante de la configuration et de la
capacité de la mémoire physique

100
Machines virtuelles: le problème et la solution

 Comment permettre de rouler différents

SE sur une seule machine physique?
 Pas évident, car chaque SE demande
accès direct au matériel
 SOLUTION: Un programme qui crée
une couche qui met à disposition
plusieurs machines physiques virtuelles
 Sur chacune, nous pouvons rouler un
SE différent
101
 Machines Virtuelles
 Virtuel en informatique dénote quelque chose qui
n ’est pas réel, n ’est pas du matériel: il est
construit par le logiciel sur la base des ressources
fournies par le matériel
 Une machine virtuelle est une machine créée par
des couche de logiciel
 Elle peut avoir des caractéristiques identiques à la
machine physique du système:
 mêmes instructions, etc.
 Ou elle peut ‘simuler’ une autre machine physique
 p.ex.pour exécuter Microsoft sur Apple
 Plusieurs machines virtuelles peuvent être créées
sur une machine physique donnée! 102
(a) Une seule mach. réelle et un seul noyau
(b) Plus. mach. virtuelles et plus. noyaux

103
 Fonctionnement typique
 Le système VM laisse exécuter normalement
les instructions non privilégiées
 Les appels au système sont exécutés par le
système VM et les résultats sont passés à la
machine virtuelle sur laquelle le processus
exécute

104
 Avantages
 Chaque machine virtuelle peut utiliser
un SE différent!
 En théorie, on peut bâtir des
machines virtuelles sur des machines
virtuelles!
 Protection complète, car les machines
virtuelles sont complètement isolées
les unes des autres
 Un nouveau SE peut être développé
sur une machine virtuelle
 sans déranger les autres 105
Implémentations

 Le concept de VM est très utilisé pour

permettre de rouler un SE sur un autre
 P.ex. SUN, Apple, Linux permettent de
rouler Windows sur leur plateforme,
 Ils doivent fournir à Windows un
environnement que Windows reconnaît
comme son environnement Intel usuel

106
Outils de programmation
 Les outils classiques utilisés dans le
développement d’un programme sont
 Éditeur de texte
 Traducteur
 Compilateur
 Assembleur
 Éditeur de liens
 Débogueur

107
 Outils de programmation
idée

Éditeur de texte

Programme source
Traducteur: compilateur, assembleur
Sous-programmes Sous-programmes
de librairie Programme objet Traduits à part

Éditeur de liens

Programme objet
Chargeur
Programme exécutable
Débogueur

108
Compilateur

 Le rôle du compilateur est de traduire

un fichier programme source en
langage de haut niveau (avec lequel le
programmeur s’est libéré des détails
des instructions machines) en
instructions/langage machine

109
Compilateur

 Le travail du compilateur se divise en

plusieurs phases:
 L’analyse lexicale
 Reconnaissance des mots du langage
 L’analyse syntaxique
 Vérification de la syntaxe
 L’analyse sémantique
 L’optimisation et la génération du code
objet
110
 Compilateur
 Analyse lexicale
 Consiste à lire le programme source et à
produire une séquence d’éléments
syntaxiques (nombres, variables,
identificateurs, opérateurs, etc.)
 Permet d’identifier quelques erreurs
(éléments ≠ langage, nombres illégaux, etc.)

111
 Compilateur
 Analyse syntaxique
 Analyse la suite de symboles issus de
l’analyseur lexical et vérifie si cette suite de
symboles est conforme à la syntaxe du
langage (règles de la grammaire)
 Analyseur syntaxique essaye de construire
l’arbre syntaxique correspondant au
programme. Dans cet arbre les feuilles
correspondent aux symboles issus de
l’analyse lexicale et les nœuds intermédiaires
correspondent aux objets grammaticaux
112
 Compilateur
 Analyse sémantique
 Associer un sens aux différentes phrases du
programme source
 Reconnaître les objets manipulés et analyser leurs
propriétés
 Type de l’objet, sa durée de vie, sa taille et son adresse
 Contrôler que l’utilisation de ces objets se fait de
manière cohérente
 Recherche les erreurs de typage, les déclarations
multiples, absentes ou inutiles, les expressions
incohérentes

113
 Compilateur
 L’optimisation et la génération du code
objet
 Étape ultime de la compilation
 Consiste à produire dans un fichier objet le
code machine équivalent au code du
langage de haut niveau, 3 étapes
 Génération d’un code intermédiaire
 Optimisation de ce code intermédiaire
 Génération du code final

114
 Compilateur
 Génération d’un code intermédiaire
 Consiste à remplacer les phrases
reconnues par des macros plus aisément
manipulables qui ne font pas de référence
aux registres de la machine cible
 Optimisation du code intermédiaire
 Vise à produire un code machine plus
performant
 L’exécution plus rapide
 Un code plus compact dont l’encombrement
mémoire est moindre
115
 Compilateur
 Optimisation du code intermédiaire
 Diverses améliorations, exemples:
 La réduction des expressions constantes
 Simplification des boucles et prés-évaluation des expressions
constantes

 Génération du code final

 Les macros sont remplacées par les instructions
machine correspondantes avec utilisations des registres
et les objets sont remplacés par leur adresse
 Le code obtenu à ce niveau est appelé code relogeable
 Toutes les adresses des objets sont calculées en

considérant que l’adresse du premier octet du code

est égale à 0 116
Éditeur de lien

 Un éditeur de lien est un logiciel qui

permet de combiner plusieurs
programmes objet en un seul
 Pour pouvoir développer de gros
programmes on structure ceux-ci en
modules que l’on traduit
indépendamment

117
 Chargeur
 Le programme objet après édition de
lien doit être chargé en mémoire
centrale pour être exécuter
 Fichier exécutable – fichier relogeable
 Lorsque le chargeur copie le code
exécutable depuis le disque vers la
mémoire centrale, il implante le code dans
un espace libre de la mémoire centrale
avec une adresse quelconque appelée
adresse d’implantation mémoire
118
 Chargeur
 Fichier exécutable – fichier relogeable
 Toutes les adresses calculées dans le
programme exécutable doivent être modifiées
 Opération de translation des adresses
 Ajouter à chaque adresse la valeur de l’adresse
d’implantation mémoire
 Deux types de chargement
 Statique
 L’opération de translation est effectuée au moment du
chargement pour toutes adresses
 Dynamique
 L’opération de translation est effectuée au moment
d’utilisation d’une adresse relogeable au cours de
l’exécution par le processeur 119
Débogueur

 Le débogueur est un logiciel qui facilite

la mise au point détection des erreurs
dans un programme. Il permet de
suivre pas à pas l’exécution d’un
programme en examinant le contenu
de la mémoire et des registres

120