Systèmes d’exploitation et Programmation système

(RS)

Lucas Nussbaum <lucas.nussbaum@loria.fr>

Supports de cours, TD et TP largement basés sur ceux de
Martin Quinson <martin.quinson@loria.fr>

Telecom Nancy – 2ième année

2016-2017
À propos de ce document
Document diffusé selon les termes de la licence
Licence Creative Commons version 3.0 France (ou ultérieure)
Attribution ; Partage dans les mêmes conditions
http://creativecommons.org/licenses/by-sa/3.0/fr/

Remerciements
I Sacha Krakoviack pour son cours et Bryant et O’Hallaron pour leur livre
I Les (autres) emprunts sont indiqués dans le corps du document

Aspects techniques
I Document LATEX (classe latex-beamer), compilé avec latex-make
I Schémas : Beaucoup de xfig, un peu de inkscape

Site du cours : http://members.loria.fr/lnussbaum/RS/

I TD/TP, exams et projets (sources disponibles aux enseignants sur demande)
(2/210)
À propos de moi. . .
Lucas Nussbaum
I Formation : ingénieur ENSIMAG (2005), Doctorat (2008)
I Depuis 2009 :
I Enseignant-chercheur (Maı̂tre de conférences) à l’univ. de Lorraine
I Principalement en licence professionnelle ASRALL
(Administration de Systèmes, Réseaux et Applications à base de Logiciel Libre)
I Chercheur dans l’équipe MADYNES du LORIA
I Recherche : Systèmes distribués, calcul à haute performance, Cloud

I Contributeur au logiciel libre

Debian (Project Leader 2013-2015, Quality Assurance), Ruby
I Plus d’infos :
I http://members.loria.fr/lnussbaum/ (Lucas.Nussbaum@loria.fr)
(3/210)
Organisation pratique du module

Module en deux parties

I Partie système (intervenant en cours : Lucas Nussbaum)
I 5 cours, 3 TD, 3 TP
I Examen sur table (mi octobre)
I Documents interdits sauf un A4 R/V manuscrit
I un projet (pour novembre)
I Binômes et Git obligatoires
I Le sujet arrive bientôt. . .
I Partie réseaux (intervenant en cours : Isabelle Chrisment)

Implication
I Manipulation : programmez ! Expérimentez !
I Questions bienvenues : pendant/après le cours, par mail, etc.

(4/210)
Pourquoi un cours de système ?
I Quatre concepts fondamentaux de l’Informatique (G. Dowek) :
Information, Machine, Algorithme, Langage
I Les architectures et infrastructures modernes sont complexes
I Wikipedia : 1145 serveurs, 30 900 CPUs
I OVH : 250 000 serveurs
I OpenStack (pile logicielle permettant de créer un Cloud privé)

(5/210)
Pourquoi un cours de système ? (2)
I Noyau Linux (et outils d’observation)

(6/210)
Pourquoi un cours de système ? (3)

I Système dual-socket Intel récent (2x Intel E5-2630v3, 8 cœurs/CPU)

Machine (126GB total)

NUMANode P#0 (63GB) NUMANode P#1 (63GB)

Socket P#0 PCI 1000:005f Socket P#1

L3 (20MB) sda sdb L3 (20MB)

L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB) L2 (256KB)
PCI 8086:154d

L1d (32KB) L1d (32KB) L1d (32KB) L1d (32KB) L1d (32KB) L1d (32KB) L1d (32KB) L1d (32KB) eth2 L1d (32KB) L1d (32KB) L1d (32KB) L1d (32KB) L1d (32KB) L1d (32KB) L1d (32KB) L1d (32KB)

L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB) L1i (32KB)
PCI 8086:154d

Core P#0 Core P#1 Core P#2 Core P#3 Core P#4 Core P#5 Core P#6 Core P#7 eth3 Core P#0 Core P#1 Core P#2 Core P#3 Core P#4 Core P#5 Core P#6 Core P#7

PU P#0 PU P#16 PU P#2 PU P#18 PU P#4 PU P#20 PU P#6 PU P#22 PU P#8 PU P#24 PU P#10 PU P#26 PU P#12 PU P#28 PU P#14 PU P#30 PU P#1 PU P#17 PU P#3 PU P#19 PU P#5 PU P#21 PU P#7 PU P#23 PU P#9 PU P#25 PU P#11 PU P#27 PU P#13 PU P#29 PU P#15 PU P#31

PCI 8086:10fb

eth0

PCI 8086:10fb

eth1

PCI 8086:8d62

PCI 8086:1521

eth4

PCI 8086:1521

eth5

PCI 102b:0534

PCI 8086:8d02

Host: grisou-9.nancy.grid5000.fr

Indexes: physical

Date: Mon 05 Sep 2016 01:38:32 PM CEST

(7/210)
Pourquoi un cours de système ? (4)
Comment les utiliser efficacement ? Comment les concevoir ?
; Performances, sécurité, résilience, efficacité énergétique

Métiers (à la sortie de TELECOM Nancy) :

I IT Operations / Administration système et réseaux
; Assurer le maintien en conditions opérationnelles d’une infrastructure
(suivi des incidents, montées de version, etc.)
I Mais mouvement vers le modèle DevOps (≈Google Site Reliability Engineers)
I Suppression des silos software development vs operations
I Infrastructure as Code
I Itérations rapides, automatisation, tests automatiques
Compétences nécessaires : développement logiciel, compréhension profonde
des systèmes (combinaison très recherchée sur le marché du travail)
I Systèmes embarqués : domotique, industrie automobile, appliances diverses
I Sécurité informatique (souvent lié à des aspects système/réseau)
I Même comme pur développeur, savoir ce qui se passe sous le capot est utile !
(8/210)
Objectif du module
Utiliser efficacement le système d’exploitation
Contenu et objectifs du module
I Grandes lignes du fonctionnement d’un système d’exploitation (OS)
Focus sur UNIX (et Linux) par défaut, mais généralisations
I Concepts clés des OS : processus, fichier, édition de liens, synchronisation
I Utilisation des interfaces système : programmation pratique, interface POSIX
I Programmation système (et non programmation interne du système)
Plutôt du point de vue de l’utilisateur (conception d’OS en RSA)

Motivations
I OS = systèmes complexes les plus courants ; Concepts et abstractions claires
I Impossible de faire un programme efficace sans comprendre l’OS
I Comprendre ceci aide à comprendre les abstractions supérieures

Prérequis : Pratique du langage C et du shell UNIX

(9/210)
Bibliographie succincte (pour cette partie)

Livres
I Bryant, O’Hallaron : Computer Systems, A Programmer’s Perspective.
Autres cours disponibles sur Internet
I Introduction aux systèmes et aux réseaux (S. Krakowiak, Grenoble)
Source de nombreux transparents présentés ici.
http://sardes.inrialpes.fr/~krakowia/Enseignement/L3/SR-L3.html/
I Programmation des systèmes (Ph. Marquet, Lille)
http://www.lifl.fr/~marquet/cnl/pds/
I Operating Systems and System Programming (B. Pfaff, Stanford)
http://cs140.stanford.edu/

Sites d’information
I http://systeme.developpez.com/cours/
Index de cours et tutoriels sur les systèmes

URL du cours : http://members.loria.fr/lnussbaum/RS/

(10/210)
Plan de cette partie du module :

Systèmes d’exploitation et programmation système

1 Introduction
Système d’exploitation : interface du matériel et gestionnaire des ressources.

2 Processus
Processus et programme ; Utilisation des processus UNIX et Réalisation ; Signaux.

3 Fichiers et entrées/sorties
Fichiers et systèmes de fichiers ; Utilisation ; Réalisation.

4 Exécution des programmes

Schémas d’exécution : interprétation (shell) et compilation (liaison et bibliothèques)

5 Synchronisation entre processus

Problèmes classiques (compétition, interblocage, famine) ; Schémas classiques.

6 Programmation concurrente
Qu’est ce qu’un thread ; Modèles d’implémentation ; POSIX threads.

(11/210)
 Premier chapitre
Introduction
Qu’est ce qu’un système d’exploitation ?

Pourquoi UNIX ?

Interfaces du système d’exploitation

Protection des ressources

Conclusion
Qu’est ce qu’un système d’exploitation

Logiciel entre les applications et le matériel

I Offre une interface unifiée aux applications
I Gère (et protège) les ressources

Firefox Emacs VLC

Système d’exploitation

Son

Disques durs
Matériel Cartes graphiques

(13/210)
Évolution des systèmes d’exploitation : Étape 0
À l’origine, pas de système d’exploitation
Une machine, un utilisateur, un logiciel
I Tout au plus une bibliothèque de services standards
Exemples : premières machines, systèmes embarqués (voitures, ascenseurs)
I Complexité conceptuelle réduite . . .
I . . . mais complexité technique accrue : on refait tout à chaque fois (⇒ cher)

Application

OS

Matériel

I Surtout, cela pose un problème d’efficacité :

Si le programme est bloqué (disque, réseau, humain), la machine est inutilisée
(14/210)
Évolution des systèmes d’exploitation : Étape 1
Maximiser le temps d’utilisation du matériel
Une machine, plusieurs logiciels
I Problème fondamental de la précédente solution :
Si le programme est bloqué (disque, réseau, humain), la machine est inutilisée
I Solution : plusieurs processus. Si l’un est bloqué, on exécute les autres.

gcc emacs
OS
Matériel

I Mais que se passe-t-il si un processus :

I Fait une boucle infinie
I Écrit dans la mémoire des autres processus
I Le système doit donc fournir une certaine protection :
⇒ interposition entre les applications et le matériel
(15/210)
Évolution des systèmes d’exploitation : Étape 2
Une machine, plusieurs logiciels, plusieurs utilisateurs
I La solution précédente est chère (en 1970) : il faut une machine par utilisateur.
I Solution : partage de la machine entre utilisateurs
(les utilisateurs tapent moins vite que l’ordinateur ne compile)

Jim Bob
gcc emacs
OS
Matériel

I Mais que se passe-t-il si les utilisateurs sont :

I Trop gourmands ou trop nombreux
I Mal intentionnés
I Le système doit protéger et gérer les ressources
(16/210)
Rôle de l’OS : intermédiaire matériel ↔ applications

Deux fonctions complémentaires

I Adaptation d’interface : offre une interface plus pratique que le matériel
I Dissimule les détails de mise en œuvre (abstraction)
I Dissimule les limitations physiques (taille mémoire) et le partage des ressources

I Gestion des ressources (mémoire, processeur, disque, réseau, affichage, etc.)

I Alloue les ressources aux applications qui le demandent
I Partage les ressources entre les applications
I Protège les applications les unes des autres ; empêche l’usage abusif de
ressources

Firefox Emacs VLC

Système d’exploitation

Son

Disques durs
Matériel Cartes graphiques

(17/210)
Fonctions du système d’exploitation

Organe Entité
physique logique
I Gestion de l’activité
I Déroulement de l’exécution (processus) Processeur Processus
I Événements matériels
I Gestion de l’information
I Accès dynamique (exécution, mémoire) Mémoire Mémoire
I Conservation permanente principale virtuelle
I Partage Disque Fichier

I Gestion des communications Écran

I Interface avec utilisateur clavier, souris Fenêtre
I Impression et périphériques Imprimante
I Réseau Réseau
I Protection
I de l’information
Tous Toutes
I des ressources

(18/210)
 Premier chapitre
Introduction
Qu’est ce qu’un système d’exploitation ?

Pourquoi UNIX ?

Interfaces du système d’exploitation

Protection des ressources

Conclusion
UNIX, POSIX et les autres

Qu’est ce qu’UNIX ? Pourquoi étudier UNIX ?

I Famille de systèmes d’exploitation, nombreuses implémentations
I Impact historique primordial, souvent copié
I Concepts de base simple, interface historique simple
I Des versions sont libres, tradition de code ouvert

Et pourquoi pas Windows ?

I En temps limité, il faut bien choisir ; je connais mieux les systèmes UNIX
I Même s’il y a de grosses différences, les concepts sont comparables
I D’autres cours à l’ESIAL utilisent Windows
occasion d’étudier ce système ; le cours de RS permet d’aller plus vite
I Système plus transparent que Windows : plus facile de comprendre ce qui se
passe sous le capot

(20/210)
Historique

1970 1980 1990 2000 2010

1965 MULTICS : projet de système
ambitieux (Bell Labs)
FreeBSD
closed source
shared source
open source
NetBSD 1969 Bell Labs se retire de
TCP/IP OpenBSD Multics, Début de Unics
BSD Berkeley Software Distribution Open Solaris
Bill Joy
SunOS (Stanford) Solaris (SUN) 1970 Unix projet Bell Labs officiel
Darwin
NextStep
MacOS X
1973 Réécriture en C
Xenix (Microsoft/SCO)
Distribution source aux universités
GNU project
Richard Stallman
Commercialisation par AT&T
Linux

Rewrite Minix
Linus Torvalds
80-90 Unix War : BSD vs. System V
in C Andrew Tannenbaum

Unix Time-Sharing System Plan 9

90-10 Effort de normalisation :
Thompson & Richie (Bell Labs)
System V UnixWare (Univel/SCO)
Posix1(88) processus, signaux, tubes
AT&T
HP-UX Posix1.b(93) semaphores, shared
AIX (IBM)
memory
IRIX (SGI)
Posix1.c (95) threads
OS/360 (for mainframes) z/OS (IBM)

Services For Unix

Posix2 (92) interpreteur
(Microsoft)
Posix :2001, Posix :2004, Posix :2008
Mises à jour
(21/210)
 Premier chapitre
Introduction
Qu’est ce qu’un système d’exploitation ?

Pourquoi UNIX ?

Interfaces du système d’exploitation

Protection des ressources

Conclusion
Notion d’interface
Un service est caractérisé par son interface
I L’interface est l’ensemble des fonctions accessibles aux utilisateurs du service
I Chaque fonction est définie par :
I son format : la description de son mode d’utilisation (syntaxe)
I sa spécification : la description de son effet (sémantique)
I Ces descriptions doivent être :
précises, complètes (y compris les cas d’erreur), non ambigües.

Principe de base : séparation entre interface et mode de réalisation

Avantages :
I Facilite la portabilité
I Transport d’une application utilisant le service sur une autre réalisation
I Passage d’un utilisateur sur une autre réalisation du système
I Les réalisations sont interchangeables facilement

Dans POSIX
I C’est l’interface qui est normalisée, pas l’implémentation
(23/210)
Interfaces d’un système d’exploitation

En général, deux interfaces

I Interface de programmation (Application Programming Interface)
I Utilisable à partir des programmes s’exécutant sous le système
I Composée d’un ensemble d’appels systèmes (procédures spéciales)
I Interface de commande ou interface de l’utilisateur
I Utilisable par un usager humain, sous forme textuelle ou graphique
I Composée d’un ensemble de commandes
I Textuelles (exemple en UNIX : rm *.o)
I Graphiques (exemple : déplacer l’icone d’un fichier vers la corbeille)

Exemple sous UNIX :

Première interface Deuxième interface
de commande de commande

Interface de
Shell 2 Shell 1
programmation
Noyau UNIX

(24/210)
Exemple d’usage des interfaces d’UNIX
while (nb_lus = read(fich1, buf, BUFFSIZE )) {
I Interface de programmation if ((nb_lus == -1) && (errno != EINTR)) {
break; /* erreur */
Ci-contre : programme copiant un } else if (nb_lus > 0) {
fichier dans un autre pos_buff = buf;
a_ecrire = nb_lus;
(read et write : appels système) while (nb_ecrits =
write(fich2,pos_buff,a_ecrire)) {
I Interface de commande if ((nb_ecrits == -1) && (errno != EINTR))
break; /* erreur */
Commande shell : else if (a_ecrire == 0)
break; /* fini */
$ cp fich1 fich2 else if (nb_ecrits > 0) {
recopie fich1 dans fich2 pos_buff += nb_ecrits;
a_ecrire -= nb_ecrits;
} } } }

I Documentation
man 1 <nom> : documentation des commandes (par défaut)
man 2 <nom> : documentation des appels système
man 3 <nom> : documentation des fonctions
d’autres sections, mais plus rares. Voir man 7 man ;)

(25/210)
Découpage en couches du système
Programmes utilisateurs
Utilisateur
Bibliothèques
Niveau utilisateur mode utilisateur
Appel système
I Applications utilisateur Trappe
mode superviseur
I Logiciels de base
I Bibliothèque système Système de Gestion des
Noyau gestion de processus
I Appels de fonction fichiers Contrôle
péripériques
Niveau noyau Contrôle/programmation
I Gestion des processus Matériel Interruption
Périphériques

(c) Philippe Marquet, CC-BY-NC-SA.

I Système de fichier
I Gestion de la mémoire
OS = bibliothèque système + noyau
Niveau matériel (d’où le nom GNU/Linux)
I Firmware, contrôleur, SOC I Ce cours : bibliothèque système
I RSA : le noyau
(26/210)
 Premier chapitre
Introduction
Qu’est ce qu’un système d’exploitation ?

Pourquoi UNIX ?

Interfaces du système d’exploitation

Protection des ressources

Conclusion
Protection des ressources (rapide introduction – cf. RSA)
Méthodes d’isolation des programmes (et utilisateurs) dangereux
I Préemption : ne donner aux applications que ce qu’on peut leur reprendre
I Interposition : pas d’accès direct, vérification de la validité de chaque accès
I Mode privilégié : certaines instructions machines réservées à l’OS
Exemples de ressources protégées
I Processeur : préemption
I Interruptions (matérielles) à intervalles réguliers → contrôle à l’OS
I (l’OS choisit le programme devant s’exécuter ensuite)
I Mémoire : interposition (validité de tout accès mémoire vérifiée au préalable)
I Exécution : mode privilégié (espace noyau) ou normal (espace utilisateur)
I Le CPU bloque certaines instructions assembleur (E/S) en mode utilisateur
programme appel continue
utilisateur syscall Changement de contexte mode bit = 1
exécution
Espace utilisateur
Espace noyau Interruption logicielle
exécute mode bit = 0
syscall

(28/210)
Limites de la protection
Les systèmes réels ont des failles
Les systèmes ne protègent pas de tout
I while true ; do mkdir toto; cd toto; done (en shell)
I while(1) { fork(); } (en C)
I while(1) { char *a=malloc(512); *a=’1’; } (en C)

Réponse classique de l’OS : gel (voire pire)

On suppose que les utilisateurs ne sont pas mal intentionnés (erreur ?)

Unix was not designed to stop people from doing stupid things,
because that would also stop them from doing clever things.
– Doug Gwyn

Deux types de solutions

Technique : mise en place de quotas
Sociale : “éduquer” les utilisateurs trop gourmands

(29/210)
Résumé du premier chapitre

I Qu’est ce qu’un système d’exploitation ?

I Un intermédiaire entre les applications et le matériel

I Rôles et fonctions du système d’exploitation

I Offrir une interface du matériel unifiée et plus adapté
I Assurer la gestion et la protection des ressources

I Les différentes interfaces d’un système d’exploitation

I Interface de programmation (API)
I Interface de commande (shell, environnement graphique)

I Techniques classiques de protection des ressources

I Préemption
I Interposition
I Mode d’exécution (protégé ou non)

(30/210)
 Deuxième chapitre
Processus
Introduction

Utilisation des processus UNIX

Mémoire virtuelle, environnement
Création des processus dans Unix
Quelques interactions entre processus dans Unix

Réalisation des processus UNIX

Communication par signaux

Principe et utilité
Terminaux, sessions et groupe en Unix
Exemples d’utilisation des signaux

Conclusion
Qu’est ce qu’un processus ?

Définition formelle :
I Entité dynamique représentant l’exécution d’un programme sur un processeur

Du point de vue du système d’exploitation :

I Espace d’adressage (mémoire, contient données + code)
I État interne (compteur d’exécution, fichiers ouverts, etc.)

Exemples de processus :
I L’exécution d’un programme
I La copie d’un fichier sur disque
I La transmission d’une séquence de données sur un réseau

(32/210)
Utilité des processus : simplicité

I L’ordinateur a des activités différentes

I Comment les faire cohabiter simplement ?
I En plaçant chaque activité dans un processus isolé
L’OS s’occupe de chacun de la même façon, chacun ne s’occupe que de l’OS

emacs
DOOM OS
WWWOSls DOOM
emacs WWW
ls

I La décomposition est une réponse classique à la complexité

(33/210)
Ne pas confondre processus et programme

I Programme : I Processus :
Code + données (passif) Programme en cours d’exécution

Pile
int i;
int main() { Tas
printf("Salut\n"); Données int i;
}
Code main()

I Vous pouvez utiliser le même programme que moi,

mais ça ne sera pas le même processus que moi
I Même différence qu’entre classe d’objet et instance d’objet

(34/210)
Utilité des processus : efficacité

I Les communications bloquent les processus

(communication au sens large : réseau, disque ; utilisateur, autre programme)
⇒ recouvrement des calculs et des communications

emacs (attente de l’utilisateur)

gcc
sans recouvrement

emacs temps gagné

gcc (bloqué)
avec recouvrement t

I Parallélisme sur les machines multi-processeurs

(35/210)
Parallélisme et pseudo-parallélisme

Que faire quand deux processus sont prêts à s’exécuter ?

I Si deux processeurs, tout va bien.
I Si non, FCFS ? Mauvaise interactivité !

I Pseudo-parallélisme = chacun son tour

I Autre exécution pseudo-parallèle

Le pseudo-parallélisme
I fonctionne grâce aux interruptions matérielles régulières rendant contrôle à OS
I permet également de recouvrir calcul et communications
On y reviendra.

(36/210)
Relations entre processus

Compétition
I Plusieurs processus veulent accéder à une ressource exclusive
(i.e. ne pouvant être utilisée que par un seul à la fois) :
I Processeur (cas du pseudo-parallélisme)
I Imprimante, carte son
I Une solution possible parmi d’autres :
FCFS : premier arrivé, premier servi (les suivants attendent leur tour)

Coopération
I Plusieurs processus collaborent à une tâche commune
I Souvent, ils doivent se synchroniser :
I p1 produit un fichier, p2 imprime le fichier
I p1 met à jour un fichier, p2 consulte le fichier
I La synchronisation se ramène à :
p2 doit attendre que p1 ait franchi un certain point de son exécution

(37/210)
Faire attendre un processus
Primordial pour les interactions entre processus
Attente active
Processus 1 Processus 2
while (ressource occupée) ressource occupée = true;
{ }; utiliser ressource;
ressource occupée = true; ressource occupée = false;
... ...
I Gaspillage de ressource si pseudo-parallélisme
I Problème d’atomicité (race condition – on y reviendra)

Blocage du processus
I Définition d’un nouvel état de processus : bloqué
(exécution suspendue ; réveil explicite par un autre processus ou par le
système)
blocage ...
actif bloqué sleep(5); /* se bloquer pour 5 secondes */
réveil ...

(38/210)
 Deuxième chapitre
Processus
Introduction

Utilisation des processus UNIX

Mémoire virtuelle, environnement
Création des processus dans Unix
Quelques interactions entre processus dans Unix

Réalisation des processus UNIX

Communication par signaux

Principe et utilité
Terminaux, sessions et groupe en Unix
Exemples d’utilisation des signaux

Conclusion
Processus UNIX

I Processus = exécution d’un programme Adresses hautes

I Commande (du langage de commande) Pile
d’exécution
I Application
Trou dans
l’espace
d’adressage
I Un processus comprend :
I Une mémoire qui lui est propre (mémoire virtuelle) Tas
(cf. malloc)
I Contexte d’exécution (pile, registres du processeur)
Données
globales
I Les processus sont identifiés par leur pid
Code
I Commande ps : liste des processus
I Commande top : montre l’activité du processeur (réservé)
I Primitive getpid() : renvoie le pid du processus
Adresses basses
courant

(40/210)
Environnement d’un processus

I Ensemble de variables accessibles par le processus

(sorte de configuration)
I Principaux avantages :
I L’utilisateur n’a pas à redéfinir son contexte pour chaque programme
Nom de l’utilisateur, de la machine, terminal par défaut, . . .
I Permet de configurer certains éléments
Chemin de recherche des programmes (PATH), shell utilisé, . . .
I Certaines sont prédéfinies par le système (et modifiables par l’utilisateur)
I L’utilisateur peut créer ses propres variables d’environnement
I Interface (dépend du shell) :
Commande tcsh Commande bash Action
setenv printenv affiche toutes les variables définies
setenv VAR <valeur> export VAR=<valeur> attribue la valeur à la variable
echo $VAR echo $VAR affiche le contenu de la variable
I Exemple : export DISPLAY=blaise.loria.fr:0.0 défini le terminal utilisé
I L’interface de programmation sera vue en TD/TP

(41/210)
Vie et mort des processus
Tout processus a un début et une fin
I Début : création par un autre processus
I init est le processus originel : pid=1 (launchd sous mac)
Créé par le noyau au démarrage, il lance les autres processus système
I Fin
I Auto-destruction (à la fin du programme) (par exit)
I Destruction par un autre processus (par kill)
I Destruction par l’OS (en cas de violation de protection et autres)
I Certains processus ne se terminent pas avant l’arrêt de la machine
I Nommés démons (disk and execution monitor → daemon)
I Réalisent des fonctions du système (login utilisateurs, impression, serveur web)

Création de processus dans UNIX

I Dans le langage de commande :
I Chaque commande est exécutée dans un processus séparé
I On peut créer des processus en (pseudo-)parallèle :
$ prog1 & prog2 & # crée deux processus pour exécuter prog1 et prog2
$ prog1 & prog1 & # lance deux instances de prog1
I Par l’API : clonage avec l’appel système fork (cf. transparent suivant)
(42/210)
Création des processus dans Unix (1/3)

Appel système pid t fork()

I Effet : clone le processus appelant

I Le processus créé (fils) est une copie conforme du processus créateur (père)
Copies conformes comme une bactérie qui se coupe en deux
I Ils se reconnaissent par la valeur de retour de fork() :
I Pour le père : le pid du fils (ou –1 si erreur) n=fork() n=235
n=0
I Pour le fils : 0

Exemple :
if (fork() != 0) {
printf("je suis le père, mon PID est %d\n", getpid());
} else {
printf("je suis le fils, mon PID est %d; mon père est %d\n",
getpid(), getppid());
/* en général exec(), (exécution d’un nouveau programme) */
}

(43/210)
Création des processus dans Unix (2/3)

Duplication du processus père ⇒ duplication de l’espace d’adressage

int i=3;
if (fork() != 0) {
printf("je suis le père, mon PID est %d\n", getpid());
i += 4;
} else {
printf("je suis le fils, mon PID est %d; mon père est %d\n",
getpid(), getppid());
i += 9;
}
printf("pour %d, i = %d\n", getpid(), i);

je suis le fils, mon PID est 10271; mon père est 10270
pour 10271, i = 12
je suis le père, mon PID est 10270 i=3 i+=4
pour 10270, i = 7 i+=9

(44/210)
Création des processus dans Unix (3/3)
testClonage.c
int main() {
if (fork() != 0) {
printf("je suis le père, mon PID est %d\n", getpid());
sleep(10) /* blocage pendant 10 secondes */
exit(0);
} else {
printf("je suis le fils, mon PID est %d\n", getpid());
sleep(10) /* blocage pendant 10 secondes */
exit(0);
}
}

$ gcc -o testClonage testClonage.c

$ ./testClonage & ps
je suis le fils, mon PID est 3148
je suis le père, mon PID est 3147 3148
[2] 3147
testClonage
PID TTY TIME CMD 3147
2989 pts/0 00:00:00 bash bash 2989
3147 pts/0 00:00:00 testClonage ps 3149
3148 pts/0 00:00:00 testClonage
printf
3149 pts/0 00:00:00 ps
$

(45/210)
Hiérarchie de processus Unix

1 Processus init

Système

Utilisateur 1 Utilisateur 2

I Quelques appels systèmes utiles :

I getpid() : obtenir le numéro du processus
I getppid() : obtenir le numéro du père
I getuid() : obtenir le numéro d’usager (auquel appartient le processus)

(46/210)
Quelques interactions entre processus (1/2)

Envoyer un signal à un autre processus

I En langage de commande, kill <pid> tue pid (plus de détails plus tard)

Faire attendre un processus

I sleep(n) : se bloquer pendant n secondes
I pause() : se bloquer jusqu’à la réception d’un signal (cf. plus tard)

(47/210)
Quelques interactions entre processus (2/2)

Synchronisation entre un processus père et ses fils

I Fin d’un processus : exit(etat)
etat est un code de fin (convention : 0 si ok, code d’erreur sinon – cf. errno)
I Le père attend la fin de l’un des fils : pid t wait(int *ptr etat)
retour : pid du fils qui a terminé ; code de fin stocké dans ptr etat
I Attendre la fin du fils pid :
pid t waitpid(pid t pid, int *ptr etat, int options)
I Processus zombie : terminé, mais le père n’a pas appelé wait().
Il ne peut plus s’exécuter, mais consomme encore des ressources. À éviter.
zombie
fils fils
bloqué
père père
fork wait fork wait

(48/210)
Faire attendre un processus

Fonction sleep()
I Bloque le processus courant pour le nombre de secondes indiqué
I unsigned int sleep(unsigned int seconds);
I usleep() et nanosleep() offrent meilleures résolutions (micro, nanoseconde)
mais interfaces plus compliquées et pas portables

Exercice : la fonction somnole (à compléter)

Écrire une fonction qui affiche à chaque seconde le temps restant à dormir :
void somnole(unsigned int secondes) {
int i;
Exemple d’affichage : for (i=0; i<secondes; i++) {
Déjà dormi 1 secondes sur 3 printf("Déjà dormi %d secondes sur %d\n",
Déjà dormi 2 secondes sur 3 i, secondes);
Déjà dormi 3 secondes sur 3 sleep(1);
}
}

(49/210)
Exemple de synchronisation entre père et fils
testClone2.c
int main() {
if (fork() != 0) {
printf("je suis le père, mon PID est %d\n", getpid());
while (1) ; /* boucle sans fin sans attendre le fils */
} else {
printf("je suis le fils, mon PID est %d\n", getpid());
sleep(2) /* blocage pendant 2 secondes */
printf("fin du fils\n");
exit(0);
} }

$ gcc -o testClone2 testClone2.c

$ ./testClone2
je suis le fils, mon PID est 3271
je suis le père, mon PID est 3270 Il y a un zombie
fin du fils 3271
->l’utilisateur tape <ctrl-Z> (suspendre) testClone2
Suspended 3270
$ ps bash 2989
PID TTY TIME CMD
2989 pts/0 00:00:00 bash
ps 3272
3270 pts/0 00:00:03 testClone2
3271 pts/0 00:00:00 testClone2 <defunct>
3272 pts/0 00:00:00 ps
$

(50/210)
Autre exemple de synchronisation père fils
testClone3.c
#include <sys/types.h>
#include <sys/wait.h> (suite de testClone3.c)
int main() {
if (fork() != 0) { } else { /* correspond au if (fork() != 0)*/
int statut; pid_t fils; printf("je suis le fils, PID=%d\n",
printf("Le père (%d) attend.\n", getpid()); getpid());
fils = wait(&statut); sleep(2) /* blocage pendant 2 secondes */
if (WIFEXITED(statut)) { printf("fin du fils\n");
printf("%d : fils %d terminé (code %d)\n", exit(1);
getpid(), fils, WEXITSTATUS(statut)); } }
};
exit(0);

$ ./testClone3 Il n’y a pas de zombie

je suis le fils, PID=3312
sleep exit
Le père (3311) attend
fin du fils testClone3 3312
wait
3311: fils 3312 terminé (code 1) 3311
$ ps bash 2989
PID TTY TIME CMD
2989 pts/0 00:00:00 bash ps 3313
3313 pts/0 00:00:00 ps
$

(51/210)
Exécution d’un programme spécifié sous UNIX
Appels systèmes exec
I Pour faire exécuter un nouveau programme par un processus
I Souvent utilisé immédiatement après la création d’un processus :
fork+exec = lancement d’un programme dans un nouveau processus
I Effet : remplace la mémoire virtuelle du processus par le programme
I Plusieurs variantes existent selon le mode de passage des paramètres
(tableau, liste, passage de variables d’environnement)
I C’est aussi une primitive du langage de commande (même effet)

Exemple :
main() {
if (fork() == 0) {

code=execl("/bin/ls", "ls", "-a", 0); /* le fils exécute : /bin/ls -a .. */

if (code != 0) { ... } /* Problème dans l’appel système; cf. valeur de errno */
} else {
wait(NULL); /* le père attend la fin du fils */
}
exit(0);
}

(52/210)
L’exemple du shell

Exécution d’une commande en premier plan

sh sh wait() sh
fork()
(pid père) (pid père) (pid père)

$ commande sh (pid fils)

exec(command) exit()

I 4 syscalls : fork, exec, exit, wait command

(pid fils)

Exécution d’une commande en tâche de fond

sh sh

D’après Philippe Marquet, CC-BY-NC-SA.

fork()
(pid père) (pid père)
$ commande &
sh (pid fils)

I Le shell ne fait pas wait() exec(command) exit()

I Il n’est plus bloqué command

(pid fils)

(53/210)
Résumé du début du deuxième chapitre

I Utilité des processus

I Simplicité (séparation entre les activités)
I Sécurité (séparation entre les activités)
I Efficacité (quand l’un est bloqué, passe à autre chose)
I Interface UNIX
I Création : fork()
I résultat=0 → je suis le fils
I résultat>0 → je suis le père (résultat=pid fils)
I résultat<0 → erreur
I Attendre un fils : deux façons
I wait() : n’importe quel fils
I waitpid() : un fils en particulier
I Processus zombie : un fils terminé dont le père n’a pas fait wait()
I Bloquer le processus courant : deux façons
I Jusqu’au prochain signal : pause()
I Pendant 32 secondes : sleep(32)
I Appel système exec() : remplace l’image du process actuel par le prog spécifié

(54/210)
 Deuxième chapitre
Processus
Introduction

Utilisation des processus UNIX

Mémoire virtuelle, environnement
Création des processus dans Unix
Quelques interactions entre processus dans Unix

Réalisation des processus UNIX

Communication par signaux

Principe et utilité
Terminaux, sessions et groupe en Unix
Exemples d’utilisation des signaux

Conclusion
Réalisation des processus
Processus = mémoire virtuelle + flot d’exécution

L’OS fournit ces deux ressources en allouant les ressources physiques

Objectif maintenant :
En savoir assez sur le fonctionnement de l’OS pour utiliser les processus
Pile
I À propos de mémoire Tas
Données
I Organisation interne de la mémoire virtuelle d’un processus Unix Code

I À propos de processeur
I Pseudo-parallélisme : allocation successive aux processus par tranches de temps

Objectifs repoussés à plus tard :

I Les autres ressources : disque (chapitre 3), réseau (seconde moitié du module)
I Détails de conception sous le capot (module RSA)
(56/210)
Allocation du processeur aux processus
Pseudo-parallélisme
Principe
I Allocation successive aux processus par tranches de temps fixées
(multiplexage du processeur par préemption)
Avantages
I Partage équitable du processeur entre processus (gestion + protection)
I Recouvrement calcul et communications (ou interactions)
Fonctionnement
I Interruptions matérielles (top d’horloge, I/O, . . . ) rendent le contrôle à l’OS
I L’OS ordonnance les processus (choisit le prochain à bénéficier de la ressource)
I Il réalise la commutation de processus pour passer le contrôle à l’heureux élu
I (Comment ? Vous verrez en RSA !)
horloge IO
p1 prêt bloqué I quantum : ≈10ms
p2 exécution (≈ millions d’instructions à 1Ghz)
p3
I temps de commutation : ≈0,5ms
quantum I yield() rend la main volontairement
(57/210)
Structure de la mémoire virtuelle d’un processus
0xefffffff Adresses hautes I Pile : pour la récursivité
MAXINT Cadre0 I Cadres de fonction (frame)
octets Cadre1 Segment
stack I Arguments des fonctions
(4Go/4To) Pile I Adresse de retour
I Variables locales (non statique)
Bibliothèques
Trous dans
l’espace I Bibliothèques dynamiques
d’adressage dynamiques I Code chargé ... dynamiquement
I Intercalé dans l’espace d’adresses
Tas I Données
(cf. malloc) I Tas : malloc()
Segment
data Section
I globales et static (modifiables)
Globales BSS I Variables constantes
Constantes Section I exec lit l’exécutable et initialise la
data
mémoire correspondante
Code Segment Section
text text I Noyau : infos sur le processus
Noyau Sections de “Process Control Block”
l’exécutable
(protégé) Segments du (pid, autorisations, fichiers ouverts, . . . )
0x00000000 Adresses basses processus
(parfois au dessus de la pile)
(58/210)
 Deuxième chapitre
Processus
Introduction

Utilisation des processus UNIX

Mémoire virtuelle, environnement
Création des processus dans Unix
Quelques interactions entre processus dans Unix

Réalisation des processus UNIX

Communication par signaux

Principe et utilité
Terminaux, sessions et groupe en Unix
Exemples d’utilisation des signaux

Conclusion
Communication inter-processus (IPC) dans Unix

Aspect central de la programmation système

Moyens de communication entre processus sous Unix

I Signaux : suite de cette séance
I Fichiers et tubes (pipes, FIFOs) : partie 3.
I Files de messages : pas étudié [cette année]
I Mémoire partagée et sémaphores : partie 5.
I Sockets (dans les réseaux, mais aussi en local) : fin du semestre

(60/210)
Signaux

Définition : événement asynchrone

I Émis par l’OS ou un processus
I Destiné à un (ou plusieurs) processus

Intérêts et limites
I Simplifient le contrôle d’un ensemble de processus (comme le shell)
I Pratiques pour traiter des événements liés au temps
I Mécanisme de bas niveau à manipuler avec précaution
(risque de perte de signaux en particulier)

Comparaison avec les interruptions matérielles :

I Analogie : la réception déclenche l’exécution d’un gestionnaire (handler )
I Différences : interruption reçue par processeur ; signal reçu par processus
Certains signaux traduisent la réception d’une interruption (on y revient)

(61/210)
Fonctionnement des signaux
1) Arrivée du signal

processus

4) Retour de l’exécution au point d’interruption

2) Déroutement de l’exécution

3) Exécution du gestionnaire

Remarques (on va détailler)

I On ne peut évidement signaler que ses propres processus (même uid)
I Différents signaux, identifiés par un nom symbolique (et un entier)
I Gestionnaire par défaut pour chacun
I Gestionnaire vide ⇒ ignoré
I On peut changer le gestionnaire (sauf exceptions)
I On peut bloquer un signal : mise en attente, délivré qu’après déblocage
I Limites aux traitements possibles dans le gestionnaire (ex : pas de signal())
(62/210)
Quelques exemples de signaux
Nom symbolique Cause/signification Par défaut
SIGINT frappe du caractère <ctrl-c> terminaison
SIGTSTP frappe du caractère <ctrl-z> suspension
SIGSTOP blocage d’un processus (*) suspension
SIGCONT continuation d’un processus stoppé reprise
SIGTERM demande de terminaison terminaison
SIGKILL terminaison immédiate (*) terminaison
SIGSEGV erreur de segmentation terminaison
(violation de protection mémoire) +core dump
SIGALRM top d’horloge (réglée avec alarm) teminaison
SIGCHLD terminaison d’un fils ignoré
SIGUSR1 pas utilisés par le système terminaison
SIGUSR2 (disponibles pour l’utilisateur) terminaison
I KILL et STOP : ni bloquables ni ignorables ; gestionnaire non modifiable.
I Valeurs numériques associées (ex : SIGKILL=9), mais pas portable
I Voir man 7 signal pour d’autres signaux (section 7 du man : conventions)
core dump : copie image mémoire sur disque (premières mémoires : toriques → core ; dump=vidanger)

(63/210)
États d’un signal

Signal pendant (pending )

I Arrivé au destinataire, mais pas encore traité

Signal traité
I Le gestionnaire a commencé (et peut-être même fini)

Pendant, mais pas traité ? Est-ce possible ?

I Il est bloqué, càd retardé : il sera délivré lorsque débloqué
I Lors de l’exécution du gestionnaire d’un signal, ce signal est bloqué

Attention : au plus un signal pendant de chaque type

I L’information est codée sur un seul bit
I S’il arrive un autre signal du même type, le second est perdu

(64/210)
 Deuxième chapitre
Processus
Introduction

Utilisation des processus UNIX

Mémoire virtuelle, environnement
Création des processus dans Unix
Quelques interactions entre processus dans Unix

Réalisation des processus UNIX

Communication par signaux

Principe et utilité
Terminaux, sessions et groupe en Unix
Exemples d’utilisation des signaux

Conclusion
États d’un travail

Entrée clavier
Commande Commande &

Travail en Travail en
fg %<job>
premier plan arrière-plan
Ctrl-C

Signaux fg %<job> bg %<job>

Ctrl-Z Travail
suspendu

I Travail (job) = (groupe de) processus lancé par une commande au shell
I Seul le travail en premier plan peut recevoir des signaux du clavier
I Les autres sont manipulés par des commandes

(66/210)
Terminaux, sessions et groupes en Unix

I Concept important pour comprendre les signaux sous Unix (détaillé plus tard)

I Une session est associée à un terminal, donc au login d’un utilisateur par shell
Le processus de ce shell est le leader de la session.
I Plusieurs groupes de processus par session. On dit plusieurs travaux (jobs)
I Au plus un travail interactif (avant-plan, foreground)
Interagissent avec l’utilisateur via le terminal, seuls à pouvoir lire le terminal
I Plusieurs travaux en arrière plan (background)
Lancés avec & ; Exécution en travail de fond
I Signaux SIGINT (frappe de <ctrl-c>) et SIGTSTP (frappe de <ctrl-z>)
sont passés au groupe interactif et non aux groupes d’arrière-plan

(67/210)
Exemple avec les sessions et groupes Unix
loop.c
int main() {
printf"processus %d, groupe %d\n", getpid(), getpgrp());
while(1) ;
}

$ loop & loop & ps $ bg %1

processus 10468, groupe 10468 [1] loop &
[1] 10468 $ fg %2
processus 10469, groupe 10469 loop
[2] 10469 [frappe de control-C]
PID TTY TIME CMD $ ps
5691 pts/0 00:00:00 bash PID TTY TIME CMD
10468 pts/0 00:00:00 loop 5691 pts/0 00:00:00 bash
10469 pts/0 00:00:00 loop 10468 pts/0 00:02:53 loop
10470 pts/0 00:00:00 ps 10474 pts/0 00:00:00 ps
$ fg %1 $ [frappe de control-C]
loop $ ps
[frappe de control-Z] PID TTY TIME CMD
Suspended 5691 pts/0 00:00:00 bash
$ jobs 10468 pts/0 00:02:57 loop
[1] + Suspended loop 10475 pts/0 00:00:00 ps
[2] - Running loop $

(68/210)
Exemple de travaux

Shell

Commande Commande &

Commande &

pid=5123 p5 pid=5600 p4 pid=5804

p1 pgid=5123 pgid=5600 pgid=5804

p2 p3 p6 pid=5610
pgid=5600
pid=5124 pid=5125
pgid=5123 pgid=5123

I Signaux ctrl-c et ctrl-z adressés à tous les processus du groupe jaune

I Commandes shell fg, bg et stop pour travaux bleus

(69/210)
 Deuxième chapitre
Processus
Introduction

Utilisation des processus UNIX

Mémoire virtuelle, environnement
Création des processus dans Unix
Quelques interactions entre processus dans Unix

Réalisation des processus UNIX

Communication par signaux

Principe et utilité
Terminaux, sessions et groupe en Unix
Exemples d’utilisation des signaux

Conclusion
Envoyer un signal à un autre processus

Interfaces
I Langage de commande : kill -NOM victime

#include <signal.h>
I Appel système :
int kill(pid_t victime, int sig);

Sémantique : à qui est envoyé le signal ?

I Si victime > 0, au processus tel que pid = victime
I Si victime = 0, à tous les processus du même groupe (pgid) que l’émetteur
I Si victime = −1 :
I Si super-utilisateur, à tous les processus sauf système et émetteur
I Si non, à tous les processus dont l’utilisateur est propriétaire
I Si victime < −1, aux processus tels que pgid = |victime| (tout le groupe)

(71/210)
Redéfinir le gestionnaire associé à un signal (POSIX)
Structure à utiliser pour décrire un gestionnaire
struct sigaction {
void (*sa handler)(int); /* gestionnaire, interface simple */
void (* sa_sigaction) (int, siginfo_t *, void *); /* gestionnaire, interface complète */
sigset t sa mask; /* signaux à bloquer pendant le traitement */
int sa flags; /* options */
}

I Gestionnaires particuliers : sig dfl : action par défaut ; sig ign : ignorer signal
I Deux types de gestionnaires
I sa handler() connait le numéro du signal
I sa sigaction() a plus d’infos
Primitive à utiliser pour installer un nouveau gestionnaire
#include <signal.h>
int sigaction(int sig, const struct sigaction *newaction, struct sigaction *oldaction);

I Voir man sigaction pour les détails

Autre interface existante : ANSI C

I Peut-être un peu plus simple, mais bien moins puissante et pas thread-safe
(72/210)
Exemple 1 : traitement d’une interruption du clavier
I Par défaut, Ctrl-C tue le processus ; pour survivre : il suffit de redéfinir le
gestionnaire de SIGINT
test-int.c
#include <signal.h>
void handler(int sig) { /* nouveau gestionnaire */
printf("signal SIGINT reçu !\n");
exit(0); $ ./test-int
} [frappe de ctrl-c]
int main() { signal SIGINT reçu !
struct sigaction nvt,old; $
memset(&nvt, 0, sizeof(nvt));
nvt.sa_handler = &handler;
sigaction(SIGINT, &nvt, &old); /*installe le gestionnaire*/
pause (); /* attend un signal */
printf("Ceci n’est jamais affiché.\n");;
}

Exercice : modifier ce programme pour qu’il continue après un ctrl-c

Note : il doit rester interruptible, i.e. on doit pouvoir le tuer d’un ctrl-c de plus
#include ¡signal.h¿ int main() {
struct sigaction nvt,old ;
void handler(int sig) { nvt.sa handler = handler ; sigaction(SIGINT, &nvt, &old) ;
printf(”signal SIGINT reçu !\n”) ; pause () ;
} nvt.sa handler = SIG DFL ; sigaction(SIGINT, &nvt, &old) ;
while (1) ; }

(73/210)
Exemple 2 : temporisation
unsigned int alarm(unsigned int nb sec)
I nb sec > 0 : demande l’envoi de SIGALRM après environ nb sec secondes
I nb sec = 0 : annulation de toute demande précédente
I Retour : nombre de secondes restantes sur l’alarme précédente
I Attention, sleep() réalisé avec alarm() ⇒ mélange dangereux

#include <signal.h>
void handler(int sig) {
printf("Entrez un nombre avant 5 sec:");
printf("trop tard !\n");
alarm(5);
exit(1);
scanf("%d", &reponse);
}
restant = alarm(0);
int main() {
printf("bien reçu (en %d secondes)\n",
struct sigaction nvt,old;
5 - restant);
int reponse,restant;
exit (0);
memset(&nvt, 0, sizeof(nvt));
}
nvt.sa_handler = handler;
sigaction(SIGALRM, &nvt, &old);

5s trop tard ! < 5s désarme le minuteur

bien reçu (en 2 secondes)
attente entrée attente
entrée clavier

(74/210)
Exemple 3 : synchronisation père-fils

I Fin ou suspension d’un processus ⇒ sigchld automatique à son père

I Traitement par défaut : ignorer ce signal

I Application : wait() pour éviter les zombies mangeurs de ressources

C’est ce que fait le processus init (celui dont le pid est 1)

#include <signal.h>
void handler(int sig) { /* nouveau gestionnaire */
pid t pid;
int statut;
pid = waitpid(-1, &statut, 0); /* attend un fils quelconque */
return;
}
int main() {
struct sigaction nvt,old;
memset(&nvt, 0, sizeof(nvt));
nvt.sa_handler = &handler;
sigaction(SIGCHLD, &nvt, &old); /* installe le gestionnaire */
... <création d’un certain nombre de fils> ...
exit (0);
}

(75/210)
Résumé de la fin du deuxième chapitre

I Quelques définitions
I pgid : groupe de processus ; un par processus lancé par shell (et tous ses fils)
I Travail d’avant-plan, d’arrière-plan : lancé avec ou sans &
I Communication par signaux
I Envoyer un signal <NOM> à <victime> :
I Langage commande : kill -NOM victime
I API : kill(pid t victime, int sig)
victime > 0 : numéro du pid visé
victime = 0 : tous les process de ce groupe
victime = −1 : tous les process accessibles
victime < −1 : tous les process du groupe abs(victime)
I Changer le gestionnaire d’un signal : sigaction (en POSIX)
I Exemples de signaux
I sigint, sigstop : Interaction avec le travail de premier plan (ctrl-c, ctrl-z)
I sigterm, sigkill : demande de terminaison, fin brutale
I sigalarm : temporisation
I sigchld : relations père-fils

(76/210)
 Troisième chapitre

Fichiers et entrées/sorties
Fichiers et systèmes de fichiers
Introduction
Désignation des fichiers

Interface d’utilisation des fichiers

Interface en langage de commande
Interface de programmation
Flots d’entrée/sortie et tubes

Réalisation des fichiers

Implantation des fichiers
Manipulation des répertoires
Protection des fichiers

Conclusion
Fichiers

Définitions
I Fichier : un ensemble d’informations groupées pour conservation et utilisation
I Système de gestion de fichiers (SGF) : partie de l’OS conservant les fichiers et
permettant d’y accéder

Fonctions d’un SGF

I Conservation permanente des fichiers (ie, après la fin des processus, sur disque)
I Organisation logique et désignation des fichiers
I Partage et protection des fichiers
I Réalisation des fonctions d’accès aux fichiers

(78/210)
Unix et les fichiers

Les fichiers jouent un rôle central dans Unix

I Support des données

I Support des programmes exécutables
I Communication avec l’utilisateur : fichiers de config, stdin, stdout
I Communication entre processus : sockets, tubes, etc.
I Interface du noyau : /proc
I Interface avec le matériel : périphériques dans /dev

(79/210)
Désignation des fichiers

Désignation symbolique (nommage) : Organisation hiérarchique

I Noeuds intermédiaires : répertoires (directory – ce sont aussi des fichiers)
I Noeuds terminaux : fichiers simples
I Nom absolu d’un fichier : le chemin d’accès depuis la racine

Exemples de chemins absolus :

usr bin etc home
/
/bin local bin prog1 jim bob
/usr/local/bin/prog
/home/bob/conf/main.tex code conf
prog2 prog3
/home/jim/code/main.c
main.c main.tex

(80/210)
Raccourcis pour simplifier la désignation
Noms relatifs au répertoire courant
I Depuis /home/bob, conf/main.tex = /home/bob/conf/main.tex

Abréviations
I Répertoire père : depuis /home/bob, ../jim/code = /home/jim/code
I Répertoire courant : depuis /bin, ./prog1 = /bin/prog1
I Depuis n’importe où, ∼bob/ = /home/bob/ et ∼/ = /home/<moi>/

Liens symboliques
bin etc home
Depuis /home/jim
I Création du lien : ln -s cible nom du lien jim bob
prog1
Exemple : ln -s /bin/prog1 monprog
I /home/jim/prog1 désigne /bin/prog1 code monprog
I Si la cible est supprimée, le lien devient invalide
Liens durs : ln cible nom
I Comme un lien symbolique, mais copies indifférenciables (ok après rm cible)
I Interdit pour les répertoires (cohérence de l’arbre)
(81/210)
Règles de recherche des exécutables

I Taper le chemin complet des exécutable (/bin/ls) est lourd

I ⇒ on tape le nom sans le chemin et le shell cherche
I Variable environnement PATH : liste de répertoires à examiner successivement
/usr/local/bin:/usr/local/sbin:/sbin:/usr/sbin:/bin:/usr/bin:/usr/bin/X11
I Commande which indique quelle version est utilisée
Exercice : Comment exécuter un script nommé gcc dans le répertoire courant ?
I Solution 1 : export PATH=”. :$PATH” ; gcc <bla>
I Solution 2 : ./gcc <bla>

(82/210)
Utilisations courantes des fichiers
I Unix : fichiers = suite d’octets sans structure interprétée par utilisateur
I Windows : différencie fichiers textes (où \n est modifié) des fichiers binaires
Programmes exécutables
I Commandes du système ou programmes créés par un utilisateur
I Exemple : gcc -o test test.c ; ./test
Produit programme exécutable dans fichier test ; exécute le programme test
I Question : pourquoi ./test ? (car test est un binaire classique : )
if test $n -le 0;

Fichiers de données
I Documents, images, programmes sources, etc.
I Convention : le suffixe indique la nature du contenu
Exemples : .c (programme C), .o (binaire translatable, cf. plus loin), .h (entête
C), .gif (un format d’images), .pdf (Portable Document Format), etc.
Remarque : ne pas faire une confiance aveugle à l’extension (cf. man file)
Fichiers temporaires servant pour la communication
I Ne pas oublier de les supprimer après usage
I On peut aussi utiliser des tubes (cf. plus loin)
(83/210)
 Troisième chapitre

Fichiers et entrées/sorties
Fichiers et systèmes de fichiers
Introduction
Désignation des fichiers

Interface d’utilisation des fichiers

Interface en langage de commande
Interface de programmation
Flots d’entrée/sortie et tubes

Réalisation des fichiers

Implantation des fichiers
Manipulation des répertoires
Protection des fichiers

Conclusion
Utilisation des fichiers dans le langage de commande

Créer un fichier
I Souvent créés par applications (éditeur, compilateur, etc), pas par shell
I On peut néanmoins créer explicitement un fichier (cf plus loin, avec flots)

Quelques commandes utiles

créer un répertoire mkdir <nom du répertoire> (initialement vide)
détruire un fichier rm <nom du fichier> (option -i : interactif)
détruire un répertoire rmdir <rep> s’il est vide ; rm -r <rep> sinon
chemin absolu du répertoire courant pwd (print working directory )
contenu du répertoire courant ls (list – ls -l plus complet)

Expansion des noms de fichiers (globbing )

I * désigne n’importe quelle chaı̂ne de caractères :
rm *.o : détruit tous les fichiers dont le nom finit par .o
ls *.c : donne la liste de tous les fichiers dont le nom finit par .c

(85/210)
Interface de programmation POSIX des fichiers

Interface système
I Dans l’interface de programmation, un fichier est représenté par descripteur
Les descripteurs sont de (petits) entiers (indice dans des tables du noyau)
I Il faut ouvrir un fichier avant usage :
fd = open("/home/toto/fich", O RDONLY, 0);
I Ici, ouverture en lecture seule (écriture interdite)
I Autres modes : o rdwrite, o wronly
I fd stocke le descripteur alloué par le système (ou –1 si erreur)
I Fichier créé s’il n’existe pas (cf. aussi creat(2))
I man 2 open pour plus de détails
I Il faut fermer les fichiers après usage :
close (fd)
I Descripteur fd plus utilisable ; le système peut réallouer ce numéro

Interface standard
I Il existe une autre interface, plus simple (on y revient)

(86/210)
 Interface de programmation POSIX : read()

L’objet fichier
I Chaque fichier a un pointeur courant : tête de lecture/écriture logique
I Les lectures et écritures le déplacent implicitement
I On peut le déplacer explicitement (avec lseek() – voir plus loin)

Lecture normale (read()) S’il n’y a pas assez de données :

p=read(fd, buf, 6) lecture tronquée (short read)
avant après avant après

fichier fd abcdef fd abcdef fichier fd ijkl fd ijkl

copie tampon buf DQSGET buf ijkl ET

tampon buf DQSGET buf abcdef copie partielle
p ? p 6 p ? p 4

(87/210)
Interface de programmation POSIX : lseek()

Objectif
I Permet de déplacer le pointeur de fichier explicitement

Exemples
lseek(fd, 30, seek cur) lseek(fd, 71, seek set)
0 21 51 62 0 21 62 71
fd fd

avant après avant après

+30 octets depuis position courante place le pointeur à la position 71

I Le pointeur peut être placé après la fin du fichier

(88/210)
Interface de programmation POSIX : write()
I Écriture dans les conditions normales :
p=write(fd, buf, 6)
avant après

fichier fd 0123456789 fd 0123456abc def

tampon buf abcdef buf abcdef
copie
p ? p 6

Le fichier a été rallongé

I Si un lseek() a déplacé le pointeur après la fin, remplissage avec des zéros

fichier fd 0123456789 fd0123456789 \0 abc

tampon buf abc
copie

I Possibilité d’écriture tronquée (short-write) si le disque est plein, ou si

descripteur est un tube ou une socket (cf. plus loin)
(89/210)
Différentes interfaces d’usage des fichiers
Interface POSIX système
I Appels systèmes open, read, write, lseek et close.
I Utilisation délicate : lecture/écriture tronquée, traitement d’erreur, etc.
I Meilleures performances après réglages précis

Bibliothèque C standard
I Fonctions fopen, fscanf, fprintf et fclose.
I Plus haut niveau (utilisation des formats d’affichage)
I Meilleures performances sans effort (POSIX : perfs au tournevis)
I Un syscall ≈ 1000 instructions ⇒ écritures dans un tampon pour les grouper
#include <stdio.h>
#include <stdio.h>
FILE *fd = fopen("mon fichier","w");
FILE *fd = fopen("mon fichier","w");
if (fd != NULL) {
if (fd != NULL) {
char toto[50];
fprintf(fd,"Résultat %d\n", entier);
fscanf(fd,"%s%d",toto, &entier);
fprintf(fd,"un autre %f\n", reel);
fscanf(fd,"%s%s%f",toto,toto, &reel);
fclose(fd);
fclose(fd);
}
}
(90/210)
Fichiers et flots d’entrée sortie

Sous Unix, tout est un fichier

I Les périphériques sont représentés par des fichiers dans /dev
I Tout processus est créé avec des flots d’entrée/sortie standard :
I stdin : entrée standard (connecté au terminal)
I stdout : sortie standard (connecté à l’écran)
I stderr : sortie d’erreur (connecté à l’écran)
I Ces flots sont associés aux descripteurs 0, 1 et 2
I Ils peuvent être fermés ou redirigés vers des vrais fichiers

entrée normale
0 stdin clavier
sortie normale
1 stdout écran
sortie erreurs 2 stderr écran

(91/210)
Flots et interface de commande

Rediriger les flots en langage de commande : < et >

cat fich # écrit le contenu de fich sur la sortie standard (l’affiche à l’écran)
cat fich > fich1 # copie fich dans fich1 (qui est créé s’il n’existe pas)
./prog1 < entrée # exécute prog en écrivant le contenu de entrée sur son entrée standard

Tubes (pipes) : moyen de communication inter-processus

I Branche la sortie standard d’un processus sur l’entrée standard d’un autre
I Exemple : cat *.c | grep var
I crée deux processus : cat *.c et grep var
I connecte la sortie du premier à l’entrée du second à travers un tube
stdout stdin
cat *.c tube grep var

Exercice : que fait la commande suivante ?

cat f1 f2 f3 | grep toto | wc -l > resultat
Compte les occurences de toto dans les trois fichiers, et écrit le décompte dans le
fichier resultat

(92/210)
Interface de programmation des tubes
Appel système pipe()
I Crée un tube : deux descripteurs (l’entrée et la sortie du tube)
int fd[2];
pipe(fd);

I Ce qui est écrit sur l’entrée (fd[1]) est disponible sur la sortie (fd[0])
par défaut, cela permet de se parler à soi-même :)
Mnemotechnique : On lit sur 0 (stdin), et on écrit sur 1 (stdout)

I Application classique : communication père–fils

père fils
processus père fils

fd[0] fd[0] fd[0] fd[0] fd[0]

fd[1] fd[1] fd[1] fd[1] fd[1]

tube tube tube

Après pipe(fd) Après fork() Après fermeture des
les descripteurs sont copiés descripteurs inutiles

(93/210)
Programmation d’un tube père/fils
#define BUFSIZE 10
int main(void) {
char bufin[BUFSIZE] = "empty"; père fils
char bufout[ ] = "hello";
pid t childpid;
empty bufin empty
int fd[2]; hello bufout hello
pipe(fd); fd[0]
if (fork() > 0) { /* père */
close(fd[0]); fd[1]
write(fd[1], bufout, strlen(bufout)+1);
} else { /* fils */
close(fd[1]); write tube read
read(fd[0], bufin, BUFSIZE);
} $ ./parentwritepipe
printf("[%d]: bufin = %.*s, bufout = %s\n", [29196]: bufin=empty, bufout=hello
getpid(), BUFSIZE, bufin, bufout); [29197]: bufin=hello, bufout=hello
return 0; $
}

Exercice : modifier le programme pour tenir compte des lectures/écritures tronquées

int todo = strlen(bufout)+1, done; int done=0; bufin[0]=’a’;
char *p=bufout; while (bufin[done]) {
while (todo) { done += read(fd[0],
done = write(fd[1],p,todo); bufin+done,
todo -= done; p += done; } BUFSIZE-done); }
(94/210)
Capacité d’un tube
write(fd, &BUFF, TAILLE) : écriture d’au plus TAILLE caractères
I S’il n’y a plus de lecteur :
I Écriture inutile : on ne peut pas ajouter de lecteurs après la création du tube
I Signal SIGPIPE envoyé à l’écrivain (mortel par défaut)
I Sinon si le tube n’est pas plein : Écriture atomique
I Sinon : Écrivain bloqué tant que tous les caractères n’ont pas été écrits
(tant qu’un lecteur n’a pas consommé certains caractères)
read(fd, &BUFF, TAILLE) : lecture d’au plus TAILLE caractères
I Si le tube contient n caractères : Lecture de min(n, TAILLE ) caractères.
I Sinon s’il n’il a plus d’écrivains : Fin de fichier ; read renvoie 0.
I Sinon : Lecteur bloqué jusqu’à ce que le tube ne soit plus vide
(jusqu’à ce qu’un écrivain ait produit suffisamment de caractères)
Parenthèse : Opérations non-bloquantes
I Drapeau O NONBLOCK ⇒ read/write ne bloquent plus jamais :
I Retournent -1 (et errno=EAGAIN) si elles auraient dû bloquer
I fnctl(fd, F SETFL, fcntl(fd[1], F GETFL) | O NONBLOCK);
(95/210)
Tubes nommés (FIFOs)

I Problème des tubes : seulement entre descendants car passage par clonage
I Solution : tubes nommés (même principe, mais nom de fichier symbolique)
#include <sys.types.h>
#include <sys/stat.h>
int mkfifo(char *nom, mode t mode);

I renvoie 0 si OK, -1 si erreur

I mode est numérique (on y revient)

I Après création, un processus l’ouvre en lecture, l’autre en écriture

I Il faut connecter les deux extrémités avant usage (bloquant sinon)

I la commande mkfifo(1) existe aussi

(96/210)
Copie de descripteurs : dup() et dup2()

ls > fich
I Cette commande inscrit dans fich ce que ls aurait écrit.
I Comment ça marche ?
On utilise les appels systèmes dup() et dup2() pour copier un descripteur :

Initialement fd=open(”fich”) dup2(fd,1) close(fd)

0 stdin 0 stdin 0 stdin 0 stdin
1 stdout 1 stdout 1 ”fich” 1 ”fich”
2 stderr 2 stderr 2 stderr 2 stderr
copie
fd ”fich” fd ”fich”

I Appel système dup(fd) duplique fd dans le premier descripteur disponible

I Appel système dup2(fd1, fd2) recopie le descripteur fd1 dans fd2
on dit “dup to”, duplicate to somewhere

(97/210)
L’exemple du shell

Création d’un tube entre deux commandes

$ commande1 | commande2

sh sh sh wait() sh
pipe(fd) fork() fork() close(fd[0])
(pidp) stdout (pidp) stdin close(fd[1]) wait() (pidp)

(c) Philippe Marquet, CC-BY-NC-SA.

sh (pidf1) (pidf2) sh
stdout tty stdin

close(fd[0]) fd close(fd[1])

sh fd[1] fd[0] sh

dup2() dup2()

sh stdout stdin sh

exec(command1) exec(command2)

stdout stdin
command1 command2
(pidf1) (pidf2)

exit() exit()

I (Un peu touffu, mais pas si compliqué à la réflexion :)

I Si on oublie des close(), les lecteurs ne s’arrêtent pas (reste des écrivains)
(98/210)
Projection mémoire
Motivation
I Adresser le fichier dans l’espace d’adressage virtuel
Pratique pour sérialiser des données complexes de mémoire vers disque
I Le fichier n’est pas lu/écrit au chargement, mais à la demande

Réalisation
#include <sys/mman.h>

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);

I addr : où le mettre, quand on sait. NULL très souvent

I prot : protection (PROT EXEC, PROT READ, PROT WRITE, PROT NONE)
I flags : visibilité (MAP SHARED entre processus ; MAP PRIVATE copy-on-write, etc)
I fd, offset : Quel fichier, quelle partie projeter.
I Retourne l’adresse (virtuelle) du début du block
(99/210)
 Troisième chapitre

Fichiers et entrées/sorties
Fichiers et systèmes de fichiers
Introduction
Désignation des fichiers

Interface d’utilisation des fichiers

Interface en langage de commande
Interface de programmation
Flots d’entrée/sortie et tubes

Réalisation des fichiers

Implantation des fichiers
Manipulation des répertoires
Protection des fichiers

Conclusion
Représentation physique et logique d’un fichier

Représentation physique d’un fichier

I Le disque est découpé en clusters (taille classique : 4ko)
I Les fichiers sont écrits dans un ou plusieurs clusters
I Un seul fichier par cluster

Structure de données pour la gestion interne des fichiers

I Chaque fichier sur disque est décrit par un inode
Structure d’un inode :
Meta-données

Type fichier
Propriétaire et groupe I Pointeurs et tables d’indirection
Droits d’accès
contiennent adresses de clusters
Taille (octets)
Dates (création, modif) I ≈ 10 blocs adressés directement
Pointeurs directs ⇒ accès efficace petits fichiers
Données

Pointeurs indirects (les plus nombreux)

Pointeurs indirects
I stat(2) : accès à ces info

(101/210)
Noms symboliques et inodes
I Les inodes sont rangés dans une table au début de la partition
I On peut accéder aux fichiers en donnant leur inode (cf. ls -i pour le trouver)
I Les humains préfèrent les noms symboliques aux numéros d’identification
⇒ notion de répertoire, sous forme d’arborescence (chainage avec racine)
I Les répertoires sont stockés sous forme de fichiers  normaux
I Chaque entrée d’un répertoire associe nom symbolique ↔ numéro d’inode
un répertoire
fich1 12415 table des inodes
rep1 6754
fich2 2362
rep2 26261
fich3 63663

rep2
main.c 46326
util.c 8432
util.h 8361

(102/210)
Manipulation de répertoires

Appels systèmes opendir, readdir et closedir

I Équivalent de open, read et close pour les répertoires
Exemple : Implémentation de ls -i .
#include <stdio.h>
#include <sys/types.h>
#include <dirent.h>

int main() {
DIR *dirp;
struct dirent *dp;

dirp = opendir(".");
while ((dp = readdir(dirp)) != NULL) {
printf ("%s\t%d\n", dp->d name, dp->d ino);
}
closedir(dirp);
}

I On pourrait compléter cette implémentation avec stat(2)

(103/210)
Protection des fichiers : généralités

Définition (générale) de la sécurité

I confidentialité : informations accessibles aux seuls usagers autorisés
I intégrité : pas de modifications indésirées
I contrôle d’accès : qui a le droit de faire quoi
I authentification : garantie qu’un usager est bien celui qu’il prétend être

Comment assurer la sécurité

I Définition d’un ensemble de règles (politiques de sécurité) spécifiant la
sécurité d’une organisation ou d’une installation informatique
I Mise en place de mécanismes de protection pour faire respecter ces règles

Règles d’éthique
I Protéger ses informations confidentielles (comme les projets et TP notés !)
I Ne pas tenter de contourner les mécanismes de protection (c’est la loi)
I Règles de bon usage avant tout :
La possibilité technique de lire un fichier ne donne pas le droit de le faire

(104/210)
Protection des fichiers sous Unix
Sécurité des fichiers dans Unix
I Trois types d’opérations sur les fichiers : lire (r), écrire (w), exécuter (x)
I Trois classes d’utilisateurs vis à vis d’un fichier :
propriétaire du fichier ; membres de son groupe ; les autres
rwx rwx rwx
propriétaire groupe autres
Granularité plus fine avec les Access Control List (pas étudiés ici)
I Pour les répertoires, r = ls, w = créer des éléments et x = cd.
I ls -l pour consulter les droits ; chmod pour les modifier

Mécanisme de délégation
I Problème : programme dont l’exécution nécessite des droits que n’ont pas les
usagers potentiels (exemple : gestionnaire d’impression, d’affichage)
I Solution (setuid ou setgid) : ce programme s’exécute toujours sous l’identité
du propriétaire du fichier ; identité utilisateur momentanément modifiée
identité réelle (celle de départ) vs identité effective (celle après setuid)
(105/210)
Résumé du troisième chapitre

I Désignation des fichiers

I Chemin relatif vs. chemin absolu :
I $PATH :
I Utilisation des fichiers
I Interface de bas niveau : open, read, write, close
Problèmes : I/O tronquée, perfs par manque de tampon
I Interface standard : fopen, fprintf, fscanf, fclose
I Trois descripteurs par défaut :
I Rediriger les flots en shell : <, > et |
I Tubes, tubes nommés et redirection en C : pipe(), mkfifo(), dup() et dup2()
I Réalisation et manipulation des fichiers et répertoires
I Notion d’inode :
I Manipulation des répertoires : opendir, readdir, closedir
I Quelques notions et rappels de protection des fichiers

(106/210)
 Quatrième chapitre
Exécution des programmes
Schémas d’exécution

Interprétation
Principe de fonctionnement d’un interpréteur
Exemple d’interpréteur : le shell

Compilation et édition de liens

Principes de la compilation
Liaison, éditeur de liens et définitions multiples en C
Bibliothèques statiques et dynamiques

Conclusion
Schémas d’exécution d’un programme

I Programme (impératif) : suite d’instructions, d’actions successives

I Exécution : faire réaliser ces actions par une machine dans un état initial pour
l’amener à un état final
I Langage [de la] machine : suite de 0 et de 1, difficile pour humains
I Langues humaines ambiguës et complexes, inaccessibles aux machines
⇒ les humains utilisent des langages informatiques traduits en langage machine

Convertir les langages informatiques en langage machine

I Compilation : conversion à priori, génération d’un fichier binaire exécutable
depuis un fichier source par un compilateur
I Interprétation : programme auxiliaire (interpréteur) traduit au fur et à mesure
interpréteur ≈ simulateur de machine virtuelle ayant un autre langage machine
I Mixte : compilation pour une machine intermédiaire
+ interprétation par une machine virtuelle

(108/210)
Compilation et interprétation
Principe Programme Chaque instruction
Phase de Phase instruction I
compilation d’exécution
compil
source compilateur objet suite
exécution d’instructions
Compilation Machine Machine Machine traduisant I
virtuelle physique ( ?) physique actions
exécution

Phase
source d’interprétation instruction I
programme
Interprétation interpréteur actions simulant
l’effet de I
Machine
physique
exécution

Exemples
I Compilation : C, C++, Fortran, Ada, assembleur
I Interprétation : shell Unix, Tcltk, PostScript, langage machine
I Autre : Lisp (les deux), Java/Scala (machine virtuelle), Python (interprétation ou
machine virtuelle), Ocaml (interprétation, compilation ou machine virtuelle)
I On peut faire de la compilation croisée voire pire
(109/210)
Compilation et interprétation : comparaison

Compilation Interprétation
, Efficacité / Efficacité
I Génère du code machine natif I 10 à 100 fois plus lent
I Ce code peut être optimisé I appel de sous-programmes
I pas de gain sur les boucles
/ Mise au point , Mise au point
I Lien erreur ↔ source complexe I Lien instruction ↔ exécution trivial
I Trace et observation simples
/ Cycle de développement , Cycle de développement
I cycle complet à chaque modification : I cycle très court :
compilation, édition de liens, modifier et réexécuter
exécution

I L’interprétation regagne de l’intérêt avec la puissance des machines modernes

I On peut parfois (eclipse/Visual) recharger à chaud du code compilé

(110/210)
Schéma mixte d’exécution
Objectifs
I Combiner les avantages de la compilation et de l’interprétation
I Gagner en portabilité sans trop perdre en performances

Principe
I Définir une machine virtuelle (qui n’existe donc pas)
I Écrire un simulateur de cette machine virtuelle
I Écrire un compilateur du langage source vers le langage machine virtuel

Exemple : Java inventé pour être (le langage d’internet)

I Programmes (applets) téléchargés doivent fonctionner sur toutes les machines
.java javac .class
I Phase de compilation et objets
source compilateur objet
indépendents de machine physique
JVM actions
I Portage sur une nouvelle machine :
Machine
écrire une JVM pour elle physique

(111/210)
 Quatrième chapitre
Exécution des programmes
Schémas d’exécution

Interprétation
Principe de fonctionnement d’un interpréteur
Exemple d’interpréteur : le shell

Compilation et édition de liens

Principes de la compilation
Liaison, éditeur de liens et définitions multiples en C
Bibliothèques statiques et dynamiques

Conclusion
Principe de fonctionnement d’un interpréteur

Définition de la machine virtuelle

I Éléments du pseudo-processeur (analogie avec processeur physique)
I pseudo-registres : zones de mémoire réservées
I pseudo-instructions : réalisées par une bibliothèque de programmes

I Structures d’exécution Initialisation

programme
I allocation des variables
I pile d’exécution
Lire instruction suivante
Cycle d’interprétation Données
(état) Exécuter instruction
I Analogie avec cycle processeur
Instruction de
I Pseudo-compteur ordinal (PC) terminaison ?
fin

(113/210)
Exemple d’interpréteur : le shell

Définition
I Programme interface entre OS et utilisateur interactif shell
OS
Interpréteur le langage commande (→ appels Matériel
systèmes)
I Mot à mot, shell=coquille, car ça  englobe l’OS
I Il existe plusieurs shells (sh, csh, tcsh, bash, zsh, etc.)

Fonctions principales d’un shell

I Interpréteur commandes des usagers ; accès aux fonctions de l’OS
I Création et exécution de processus
I Accès aux fichiers et entrées / sorties
I Utilisation d’autres outils (éditeur, compilateur, navigateur, etc.)
I Gestionnaire de tâches : travaux en mode interactif ou en tâche de fond
I Personnaliser l’environnement de travail : variables d’environnement
I Scripting : programmation en langage de commande (if, while, etc.)

(114/210)
 Quatrième chapitre
Exécution des programmes
Schémas d’exécution

Interprétation
Principe de fonctionnement d’un interpréteur
Exemple d’interpréteur : le shell

Compilation et édition de liens

Principes de la compilation
Liaison, éditeur de liens et définitions multiples en C
Bibliothèques statiques et dynamiques

Conclusion
Composition de programmes

Les programmes ne s’exécutent jamais seuls

I Applications modernes = assemblage de modules (conception et évolution ,)
I Applications modernes utilisent des bibliothèques de fonctions


I Cf. programmation objet et prolongement  par composants (en par, 3a)

P Q
P utilise (importe) Appel de proc Q fournit (exporte)
proc proc proc

Problème : la liaison
I Un programme P appelle une procédure proc définie dans Q
I Appel de routine en assembleur : jump à une adresse donnée
I Question : quelle adresse associer à proc dans le code machine de P ?
I Réponse : on sait pas tant que le code machine de Q est inconnu (pourquoi ?)
I Solution : Dans P, liaison entre proc et son adresse faite après compilation
Édition de liens

(116/210)
Cycle de vie d’un programme compilé

I Compilation en programme objet absolu

I Adresses (des routines) en mémoire fixées

source compilateur prog. objet

absolu

I Compilation en programme objet translatable

I Adresses définies à une translation près

, On peut donc regrouper plusieurs objets translatables dans un seul gros

/ Ce n’est pas exécutable (le CPU ne translate pas)
⇒ chargeur convertit code translatable (combinable) en code absolu (exécutable)

source compilateur prog. objet chargeur prog. objet

translatable absolu

I Exemples
I gcc -c prog.c ⇒ prog.o = programme objet translatable
I gcc -o prog prog.c ⇒ prog programme objet absolu (compilo + chargeur)

(117/210)
Édition de liens

source (.c) objet translatable (.o)

int main () {
... compil
P proc(x) utilisation
objet translatable (.o) binaire exécutable
...

Table symboles appel de

proc proc
Édition Chargeur
source (.c) objet translatable (.o) de liens
void exécution de
proc (int i) { compil proc
Q ... définition
}

Table symboles
proc

I L’éditeur de lien et le chargeur sont souvent regroupé dans le même utilitaire :

ld

(118/210)
Exemples de commandes de compilation

I La commande gcc invoque compilateur, éditeur de liens et chargeur

gcc prog.c → a.out = binaire exécutable
gcc -o prog prog.c → prog = binaire exécutable
gcc -c prog.c → prog.o = binaire translatable

I Si un programme est composé prog1.c et prog2.c, alors :

gcc prog1.c prog2.c → binaire exécutable complet dans a.out
gcc -c prog1.c prog2.c → prog1.o et prog2.o = 2 objets translatables
gcc -o prog prog.o prog1.o → prog depuis objets translatables

(119/210)
Quelques problèmes de l’édition de liens
Théorie relativement simple...
I Définition manquante
$ gcc -o prog prog1.c prog2.c prog3.c
... /tmp/cckdgmLh.o(.text+0x19):
proc(x); In function ‘main’:
... undefined reference to ‘proc’
/* pas de définition de proc */ collect2: ld returned 1 exit status
$

I Définitions multiples
...
proc(x); $ gcc -o prog prog1.c prog2.c prog3.c
... $
int proc; /* déf. comme entier */
...
void proc(int x) {
... /* déf. comme fonction */
} I Pas de message d’erreur !
I Que se passe-t-il ?

... pratique souvent déroutante

(120/210)
Définitions multiples en C

Deux catégories de symboles externes

I Symboles externes : visible de l’éditeur de liens (hors de toute fonction)
I Symbole fort :
I définition de procédures
I variables globales initialisée
I Symbole faible :
I déclaration de procédures en avance (sans le corps de fonction)
I variables globales non-initialisée

Règles de l’éditeur de liens pour les définitions multiples

I deux symboles forts : interdit ! (erreur détectée)
I un symbole fort et plusieurs faibles : le fort est retenu
I plusieurs symboles faibles : choix aléatoire

(121/210)
Pièges des définitions multiples
Module A Module B
int proc(int i) { int proc(int i) {
Deux symboles forts : interdit
int x; int x;
int p1(int i) { int p2(int i) {
Deux symboles faibles
désignent le même objet
int x; /* 4o */ double x; /* 8o */
int y; /* 4o */ Deux symboles faibles.
int p1(int i) { int p2(int i) {
Modifier B.x écrase A.y ! !
int x=3;
double x;
int y;
int p2(int i) {
A.x fort ; B.x faible ;
int p1(int i) {
Modifier B.x écrase encore A.y ! !
I Contrôle de types strict entre modules pas obligatoire en C
⇒ Déclaration explicite des références externes nécessaire
Exercice : que se passe-t-il dans l’exemple précédent (deux pages avant) ?
int proc = symbole faible ; void proc(int x) = symbole fort, c’est lui qui est choisi
(mais comportement étrange quand on change int proc)

(122/210)
Déclarations des variables externes
I Règle 1 : utiliser des entête (.h) pour unifier les déclarations
I Règle 2 : éviter les variables globales autant que possible !
I déclarer static toute variable hors des fonctions (visibilité = fichier courant)
I Règle 3 : bon usage des globales (si nécessaire)
I chaque globale déclarée fortement dans un module M
I extern dans tous les autres (avec son type)
I Seulement consultation depuis l’extérieur, modification seulement depuis M
Fonctions dans M pour la modifier depuis ailleurs, au besoin (setters)
I Règle 4 : bon usage des fonctions
I déclaration explicite des fonctions externes (avec signature)
I mot clé extern optionnel : la signature (ou prototype) suffit
Fichier un.c Fichier deux.c Fichier trois.c
int x; extern int x; extern double y;
extern double y; double y; int f(int i);
static int z;
int f(int i) {... }
static int g(int i) {... }
/* x: écriture /* x: lecture /* x: invisible
y: lecture y: écriture y: lecture
z: écriture z: non-référençable z: non-référençable
f: accessible f: invisible f: accessible
g: accessible */ g: non-référençable */ g: non-référençable */

(123/210)
Exercices : (à compléter)
Module A Module B Que se passe-t-il ?
int f(int i) { ... } static double f=4.5; Pas de problème
f.B static ⇒ invisible d’ailleurs
#include <stdio.h>
Ca marche (et affiche 0x55).
void p2(void);
int main() {
char main; Link sans soucis : main.B est faible,
p2();
void p2() {
il est écrasé
return 0;
}
printf("Ox%x\n", Execution : ref(main.B) =
main);
}
def(main.A), et 0x55 est l’adresse du
main() à gauche
Exercice : pourquoi chaque programme doit contenir une fonction main() ?
car par convention, exec() passe le controle à une fonction de ce nom

Exercice : que se passe-t-il quand main() fait return ou exit()

main : la fonction qui a invoqué main() reprend le contrôle. Elle appelle exit()
exit : exit() aussi ; libc reprend le contrôle, termine le processus et prévient l’OS

(124/210)
Cycle de vie d’un programme : résumé

pile

gcc -c prog1.c
source binaire translatable

binaire exécutable
prog1.c prog1.o

copie
gcc -o prog prog1.o prog2.o prog (fork+exec) text
data
source binaire translatable

prog2.c prog2.o
prog <params>

gcc -c prog2.c

(125/210)
 Quatrième chapitre
Exécution des programmes
Schémas d’exécution

Interprétation
Principe de fonctionnement d’un interpréteur
Exemple d’interpréteur : le shell

Compilation et édition de liens

Principes de la compilation
Liaison, éditeur de liens et définitions multiples en C
Bibliothèques statiques et dynamiques

Conclusion
Bibliothèques

I Bibliothèque = recueil de fonctions utilisées dans divers programmes

I Ne pas réinventer la roue ; réutilisation du code
I Exemples : atoi, printf, malloc, random, strcmp, sin, cos, floor, etc.

Divers moyens de rendre ce service :

I Réalisation par le compilateur :
I Compilateur Pascal remplace appels fonctions standards par code correspondant

/ Changer le compilateur pour changer ce code

I Approche par binaire translatable :
I Le code de toutes les fonctions standards placé dans un /usr/lib/libc.o

/ Plusieurs Mo à chaque fois, même si inutilisé

I Approche par collections de binaires translatables :
I Code chaque fonction dans un binaire translatable différent

/ gcc toto.c /usr/lib/printf.o /usr/lib/scanf.o ... (un peu lourd)

I Approche par archives de binaires translatables (bibliothèques statiques) :
I Concaténation de tous les .o dans un fichier, et l’éditeur de lien choisi

(127/210)
Bibliothèques statiques
I /usr/lib/libc.a : bibliothèque standard du langage C (printf, strcpy, etc.)
I /usr/lib/libm.a : bibliothèque mathématique (cos, sin, floor, etc.)

Utilisation :
I Passer bibliothèques utilisées à l’éditeur de lien (libc.a ajoutée par défaut)
gcc -o prog prog.c /usr/lib/libm.a
I L’éditeur de liens ne copie que les  fonctions effectivement utilisées
I Notation abrégée : -l<nom> équivalent à /usr/lib/lib<nom>.a
Exemple : gcc -o prog prog.c -lsocket (inclut /usr/lib/libsocket.a)
I Chemin de recherche : Variable LIBPATH, ajout avec gcc -L<rep>

Format et création
I Archives de binaires translatables
I Manipulées par ar(1)
ar rcs libamoi.a fonct1.o fonct2.o fonct3.o
I Remarque : historiquement, tar est une version particulière de ar
(128/210)
Dépendances entre bibliothèques statiques

I Difficulté lorsqu’une bibliothèque utilise une autre bibliothèque

I L’ordre des -ltoto lors de l’appel à l’éditeur de liens devient important car :
I Éditeur de liens ne copie que les objets nécessaires, pas toute l’archive
I Il ne parcourt ses arguments qu’une seule fois
I Règle : déclaration de fonction doit être placée après son premier usage
Exercice : quelle(s) commande(s) fonctionne(nt)/échoue(nt) ? Pourquoi ?
prog.c utilise machin() de libmachin.a, et machin() utilise truc() de libtruc.a
I gcc -o prog prog.c -ltruc -lmachin : référence à truc() indéfinie
I gcc -o prog prog.c -lmachin -ltruc : fonctionne

Exercice : que faire en cas de dépendances circulaires ?

faire figurer une bibliothèque deux fois pour casser le cycle

(129/210)
Bibliothèques dynamiques
I Défauts des bibliothèques statiques :
I Code dupliqué dans chaque processus les utilisant
I Liaison à la compilation (nouvelle version de bibliothèque ⇒ recompilation)
I Solution : Bibliothèques dynamiques :
Partage du code entre applications et chargement dynamique
I Exemples : Windows : DLL (dynamically linkable library) ; Unix : .so (shared object)

I Bibliothèques partagées à plus d’un titre :

sur disque (un seul .so) et en mémoire (physique, du moins)
I Chargement dynamique :
/ Impose une édition de lien au lancement (ldd(1) montre les dépendances)
, Mise à jour des bibliothèques simplifiée (mais attention au DLHell)
Versionner les bibliothèques (et même les symboles) n’est pas trivial
, Mécanisme de base pour les greffons (plugins)
, Même possible d’exécuter du code au chargement/déchargement !
void chargement(void) attribute ((constructor)) {...}
void alafin(void) attribute ((destructor)) {...}
(130/210)
Bibliothèques dynamiques

Construction
I gcc -shared -fPIC -o libpart.so fonct1.c fonct2.c fonct3.c
I -fPIC (compil.) : demande code repositionnable (Position Independent Code)
I -shared (éd. liens) : demande objet dynamique

Outils (voir les pages de man)

I ar : construire des archives/bibliothèques
I strings : voir les chaines affichables
I strip : supprimer la table des symboles
I nm : lister les symboles
I size : taille de chaque section d’un fichier elf
I readelf : afficher la structure complète et tous les entêtes d’un elf (nm+size)
I objdump : tout montrer (même le code desassemblé)
I ldd : les bibliothèques dynamiques dont l’objet dépend, et où elles sont prises

(131/210)
Chargement dynamique de greffons sous linux
Greffon (plugin) :
I Bout de code chargeable dans une application pour l’améliorer
→ Choisir l’implémentation d’une fonctionnalité donnée (affichage, encodage)
→ Ajouter des fonctionnalités (mais bien plus dur, nécessite API dynamique)

Compiler du code utilisant des greffons :

I gcc -rdynamic -ldl autres options

Exercice : Pourquoi ce -ldl ?

Pour charger une bibliothèque nommée dl (dynamic library)

Interface de programmation sous UNIX modernes (Linux et Mac OSX)

#include <dlfcn.h>
void *dlopen(const char *filename, int flag); /* charge un greffon */
void *dlsym(void *handle, const char *symbole); /* retourne pointeur vers symbole */
int dlclose(void *handle); /* ferme un greffon */
char *dlerror(void); /* affiche la cause de la dernière erreur rencontrée */
.
(132/210)
Exemple de greffon sous linux
chargeur.c
#include <unistd.h>
#include <stdio.h>
module un.c
#include <errno.h> int mon_main() {
#include <dlfcn.h> printf("Je suis le module UN.\n");
int main(int argc, char * argv[]) { }
char path[256], *erreur = NULL;
int (*mon_main)(); module deux.c
void *module;
/* Charge le module */ int mon_main() {
module = dlopen(argv[1], RTLD_NOW); printf("Je suis le module DEUX.\n");
if (!module) { }
fprintf (stderr, "%s\n", dlerror());
exit(1); $ gcc -shared -fPIC -o un.so module_un.c
} $ gcc -shared -fPIC -o deux.so module_deux.c
/* Retrouve la fonction d’entrée */ $ gcc -o chargeur chargeur.c -rdynamic -ldl
mon_main = dlsym(module, "mon_main"); $ ./chargeur ./un.so
erreur = dlerror(); Je suis le module UN.
if (erreur != NULL) { $ ./chargeur ./deux.so
perror(erreur); Je suis le module DEUX.
exit(1); $ ldd chargeur
} libdl.so.2 => /lib/i686/cmov/libdl.so.2 (0xb7f
/* Appelle cette fonction */ libc.so.6 => /lib/i686/cmov/libc.so.6 (0xb7e70
(*mon_main)(); /lib/ld-linux.so.2 (0xb7fd1000)
/* Ferme tout */ $ nm chargeur | grep mon_main
dlclose(module); $
return 0;
}
(133/210)
Bibliothèques dynamiques et portabilité
Chaque système a sa propre interface
I Solaris, Linux, MacOSX et BSD : dlopen (celle qu’on a vu, par SUN)
I HP-UX : shl load
I Win{16,32,64} : LoadLibrary
I BeOS : load add on

libtool offre une interface portable

I nommé libltdl (LibTool Dynamic Loading library)
I Il permet également de compiler une bibliothèque dynamique de façon portable
I Associé à autoconf (usage peu aisé ; compilation depuis UNIX principalement)

Interface (fonctions de base : similaires à dlopen)

#include <ltdl.h>
lt dlhandle lt dlopen(const char *filename);
lt ptr t lt dlsym(lt dlhandle handle, const char *name);
int lt dlclose(lt dlhandle handle);
const char *lt dlerror(void);
int lt dlinit(void);
int lt dlexit(void);
.
(134/210)
Schéma général d’exécution de programmes

bibliothèque
binaire statique
translatable
Compilateur
éditeur
générateur binaire de liens
pré-processeur de code translatable

programme
chargeur
arbre
analyseur syntaxique
bibliothèque binaire
dynamique exécutable

générateur machine
traducteur interpréteur de code physique

Actions code Actions

intermédiaire interpréteur

Actions

(135/210)
Résumé du quatrième chapitre

Schémas d’exécution. Problème :

I Interprétation : peu efficace
I Compilation : mise au point, cycle complet à chaque modif
I Autres approches : machine virtuelle (Java)

Bibliothèques et liaison. Pourquoi :

I Éditeur de lien : assembler les ”modules”
I Définitions multiples en C
I Bibliothèques statiques
I Pourquoi : collection de fonctions
I Comment : archive ar
I Avantages et défaut : simple, mais duplique le code dans les binaires
I Bibliothèques dynamiques
I Pourquoi : partage du code entre applications
I Comment : edition de liens au lancement

(136/210)
 Cinquième chapitre
Synchronisation entre processus
Introduction : notions de base
Condition de compétition et exclusion mutuelle
Exclusion mutuelle par verrouillage de fichiers
Notion d’interblocage
Exclusion mutuelle par attente active
Problèmes de synchronisation (résumé)
Sémaphores et schémas de synchronisation
Sémaphores
Exclusion mutuelle
Cohorte
Rendez-vous
Producteurs / Consommateurs
Lecteurs / Rédacteurs
Autres outils de synchronisation
Moniteurs
Synchronisations POSIX
compare-and-swap
Conclusion
Problème de l’exclusion mutuelle
Exemple : deux banques modifient un compte en même temps
Agence Nancy Agence Karlsruhe
1. courant = get account(1867A) 1. aktuelles = get account(1867A)
2. nouveau = courant + 10 2. neue = aktuelles - 10
3. update account (1867A, nouveau) 3. update account(1867A, neue)

I variables partagées + exécutions parallèles entremêlées ⇒ différents résultats :

I ( 0 ; ? ; ?) N1( 0 ; 0 ; ? ) N2( 0 ;10 ; ? ) N3(10 ;10 ; ?)
→ compte inchangé
K1(10 ;10 ;10)K2(10 ;10 ;0) K3( 0 ;10 ; 0)
I (0 ; ? ; ?)N1 (0 ;0 ; ?) K1 (0 ;0 ;0) N2(0 ;10 ;0)
→ compte –= 10
K2(0 ;10 ;-10) N3(10 ;10 ;-10) K3(-10 ;10 ;-10)
I (0 ; ? ; ?)K1 (0 ; ? ;0) N1 (0 ;0 ;0) K2(0 ;0 ;-10)
→ compte += 10
N2(0 ;10 ;-10) K3(-10 ;10 ;-10)N3(10 ;10 ;-10)

C’est une condition de compétition (race condition)

I Solution : opérations atomiques ; pas d’exécutions entremêlées
I Cette opération est une section critique à exécuter en exclusion mutuelle

(138/210)
Réalisation d’une section critique
Schéma général
Processus 1 Processus 2
... ...
entrée en section critique entrée en section critique
section critique section critique
sortie de section critique sortie de section critique
... ...

I Exclusion mutuelle garantie par les opérations

(entrée en section critique) et (sortie de section critique)

Réalisation
I Attente active : processus à l’entrée section critique boucle un test d’entrée
I Inefficace (sur mono-processeur)
I Parfois utilisé dans conditions praticulière dans le noyau
I Primitives spéciales : fournies par le système
I Primitives générales : sémaphores, mutex (on y revient)
I Mécanismes spécifiques : comme verrouillage de fichiers (idem)
I Les primitives doivent être atomiques...

(139/210)
Exclusion mutuelle par verrouillage de fichiers
I Verrouiller une ressource garanti un accès exclusif à la ressource
I Unix permet de verrouiller les fichiers
I Appels systèmes de verrouillage/déverrouillage (noms symboliques) :
I verrouille(fich) : verrouille fich avec accès exclusif
I déverrouille(fich) : déverrouille fich
I Propriétés :
I Opérations atomiques (assuré par l’OS)
I Verrouillage par au plus un processus
I Tentative de verrouillage d’un fichier verrouillé ⇒ blocage du processus
I Deverrouillage ⇒ réveille d’un processus en attente du verrou (et un seul)
... ...
verrouille(fich); verrouille(fich);
accès à fich (section critique); accès à fich (section critique);
deverrouille(fich); deverrouille(fich);
... ...

verrouille deverrouille verrouille deverrouille

P0
section critique blocage section critique

blocage section critique

P1
verrouille deverrouille verrouille deverrouille

(140/210)
Verrouillage partagé

I Sémantique sur les fichiers : écritures exclusives, lectures concurrentes

I Nouvelle opération : ver-part (verrouillage partagé)

Nouveau verrouille Nouveau ver-part

Déjà réalisé possible ? possible ?
verrouille(f) non non
ver-part(f) non oui

I Tentative de verrouillage d’un fichier verrouillé ⇒ blocage du processus

I Déverrouillage ⇒ réveille d’un processus en attente du verrou (et un seul)

(141/210)
Verrouillage de fichier sous Unix

Opérations disponibles
I Deux types de verrous : exclusifs ou partagés
I Deux modes de verrouillage :
I Impératif (mandatory ) : bloque les accès incompatibles avec verrous présents
(mode décrit précédemment – pas POSIX)
I Consultatif (advisory ) : ne bloque que la pose de verrous incompatibles
I Tous les verrous d’un fichier sont de même mode
I Deux primitives :
I fcntl : générale et complexe
I lockf : enveloppe plus simple, mais mode exclusif seulement (pas partagé)
I Possibilité de verrouiller fichier entier ou une partie

(142/210)
Interface du verrouillage de fichier sous Unix
#include <unistd.h>
int lockf(int fd, int commande, off t taille);

I fd : descripteur du fichier à verrouiller

I commande : mode de verrouillage
I F ULOCK : déverrouiller
I F LOCK : verrouillage exclusif
I F TLOCK : verrouillage exclusif avec test (ne bloque jamais, retourne une erreur)
I F TEST : test seulement
I taille : spécifie la partie à verrouiller
I = 0 : fichier complet
I > 0 : taille octets après position courante
I < 0 : taille octets avant position courante

I Verrouillage consultatif et exclusif seulement

Utiliser fcntl pour verrouillage impératif et/ou partagé
I Retour : 0 si succès, -1 sinon (cf. errno)

(143/210)
Exemple de verrouillage de fichiers Unix
testlock.c
#include <unistd.h>
int main (void) {
int fd;
fd = open("toto", O_RDWR); /* doit exister */ $ testlock & testlock &
while (1) { 15545: verrouille le fichier
if (lockf(fd, F_TLOCK, 0) == 0) { [4] 15545
printf("%d: verrouille le fichier\n", 15546: déjà verrouillé...
getpid()); [5] 15546
sleep(5); $ 15546: déjà verrouillé...
if (lockf(fd, F_ULOCK, 0) == 0) 15546: déjà verrouillé...
printf("%d: déverrouille le fichier\n", 15545: déverrouille le fichier
getpid()); 15546: verrouille le fichier
return; 15546: déverrouille le fichier
} else { $
printf("%d: déjà verrouillé...\n",
getpid());
sleep (2);
}
}
}

Exercice : que se passe-t-il si on remplace F TLOCK par F LOCK ?

15546 bloque jusqu’à ce que 15545 déverrouille le fichier
(et n’affiche rien entre temps)
(144/210)
L’exemple des banques revisité
Rappel du problème
Agence Nancy Agence Karlsruhe
1. courant = get account(1867A) 1. aktuelles = get account(1867A)
2. nouveau = courant + 10 2. neue = aktuelles - 10
3. update account (1867A, nouveau) 3. update account(1867A, neue)

Implémentation avec le verrouillage de fichier UNIX

Agence Nancy Agence Karlsruhe
int fd = open("fichier partagé", O RDWR); int fd = open("fichier partagé", O RDWR);
lockf(fd, T LOCK, 0); lockf(fd, T LOCK, 0);
1. courant = get account(1867A) 1. aktuelles = get account(1867A)
2. nouveau = courant + 10 2. neue = aktuelles - 10
3. update account (1867A, nouveau) 3. update account(1867A, neue)
lockf(fd, T ULOCK, 0); lockf(fd, T ULOCK, 0);

Remarques
I Fichier partagé entre deux banques difficile à réaliser
I Autres solutions techniques pour les systèmes distribués ; l’idée reste la même
(145/210)
Notion d’interblocage
Utilisation simultanée de plusieurs verrous ⇒ problème potentiel
Situation Déroulement
I Deux processus verrouillent deux fichiers Exécution (pseudo-)parallèle
Processus 1 Processus 2
I Première possibilité :
... ... 1a ; 1b ; 2a ; 2b
verrouille (f1) /* 1A */ verrouille (f2) /* 2A */
accès à f1 accès à f2 I Seconde possibilité :
... ... 2a ; 2b ; 1a ; 1b
verrouille (f2) /* 1B */ verrouille (f1) /* 2B */
accès à f1 et f2 accès à f1 et f2 I Troisième possibilité :
deverrouille (f2) deverrouille (f2)
deverrouille (f1) deverrouille (f1) 1a ; 2a ; 1b ; 2b

Exécution de 1a ;2a ;1b ;2b

verrouille(f1) verrouille(f2)
I P1 et P2 sont bloqués ad vitam eternam :
P1
interblocage
I P1 attend le deverrouille(f2) de P2
P2 I P2 attend le deverrouille(f1) de P1
verrouille(f2) verrouille(f1)
I C’est un interblocage (deadlock)
(146/210)
Situation d’interblocage

Définition
I Plusieurs processus bloqués dans l’attente d’une action de l’un des autres
I Impossible de sortir d’un interblocage sans intervention extérieure

Conditions d’apparitions
I Plusieurs processus en compétition pour les mêmes ressources
I Cycle dans la chaı̂ne des attentes

Exemple : carrefour lyonnais un vendredi à 18h

Exercice : quelles sont les ressources ?
1 chaque quart du carrefour
4
2
3 Exercice : comment sortir de l’interblocage ?
impossible (sans bate de baseball)

(147/210)
Situation réelle d’interblocage

(148/210)
Comment prévenir l’interblocage ?
Solution 1 : réservation globale
I Demandes en bloc de toutes les ressources nécessaires
I Inconvénient : réduit les possibilités de parallélisme
I Analogie du carrefour : mettre des feux tricolores (et les respecter)
Solution 2 : requêtes ordonnées
I Tous les processus demandent les ressources dans le même ordre
I Interblocage alors impossible
I Analogie du carrefour : construire un rond-point
verrouille (f1) verrouille (f1)
verrouille (f2) verrouille (f2)
accès à f1 et f2 accès à f1 et f2
deverrouille (f2) deverrouille (f2)
deverrouille (f1) deverrouille (f1)

Solution 3 : modification de l’algorithme

I Modifier code utilisateur pour rendre impossible l’interblocage
I Analogie du carrefour : construire un pont au dessus du carrefour
(149/210)
Sortir de l’interblocage (quand on a pas su prévenir)

Impossible sans perdre quelque chose

Possibilités de guérison
I Faire revenir un processus en arrière
I Nécessite d’avoir un point de reprise (checkpoint)
I Travail depuis dernier point de reprise perdu
I Tuer l’un des processus pour casser le cycle

Conclusion
I Prévention et guérison sont tous les deux coûteux
I Prévention : l’application doit faire attention
I Guérison : détection + pertes dues au retour en arrière
I La meilleure solution dépend de la situation

(150/210)
Section critique par attente active

Principe (rappel)
I On demande tant qu’on a pas obtenu

Défaut
I Manque d’efficacité car gaspillage de ressources

Avantage
I Implémentable sans primitive de l’OS ni du matériel
⇒ utilisé dans certaines parties de l’OS, par exemple

Attention, ce n’est pas si simple à faire

(151/210)
Réalisation d’une section critique par attente active

I Hypothèses : atomicité d’accès et de modifications de variables

V ne change pas au milieu de V==1 ni de V=1 (raisonnable sur monoprocesseur)

Solution FAUSSE numéro 1 Demande alternance stricte :

while (tour != MOI); /* attente active */ Entrer deux fois de suite dans SC()
SC(); /* section critique */ impossible (même si seul processeur)
tour = 1-MOI; /* soyons fair-play */
C’est une famine
Solution FAUSSE numéro 2
Pas d’exclusion mutuelle (compétition) :
while(flag[1-MOI]); /*attendre autre*/
flag[MOI] = VRAI; /*annonce entrer*/ P0 teste flag[1] et trouve faux
SC(); P1 teste flag[0] et trouve faux
flag[MOI] = FAUX; /*débloque autre*/
Les deux entrent dans SC()
Solution FAUSSE numéro 3
Possibilité d’interblocage :
flag[MOI]=VRAI; /*annonce entrer avant*/
while (flag[1-MOI]); /*attendre l’autre*/ P0 : flag[0] ← VRAI
SC(); P1 : flag[1] ← VRAI
flag[MOI] = FAUX; /*débloque autre*/
Les deux entrent dans leur boucle

(152/210)
Algorithme correct d’attente active
1. flag[MOI] = VRAI; /* Annonce ^
etre intéressé */
2. tour = 1-MOI; /* mais on laisse la priorité à l’autre */
3. while ((flag[1-MOI]==VRAI) /* on entre si l’autre ne veut pas entrer */
&& (tour == 1-MOI)); /* ou s’il nous a laissé la priorité */
4. CS();
5. flag[MOI] = FAUX; /* release */

Progression du processus 0
FF1 FV1 FV0 FV0 FF?
ligne 5

CS() VF1 VV1 VV0 VF1

ligne 3
VV0
VF1 VV1 VV1 VF1
ligne 2
VV1
VF? VV? VV0 VV0 VF0
ligne 1
FF? FV? FV0 FV0 FF0
ligne 1 ligne 2 ligne 3 CS() ligne 5
Progression du processus 1
GL Peterson. A New Solution to Lamport’s Concurrent Programming Problem. 1983. (lire l’article)
http://en.wikipedia.org/wiki/Peterson’s_algorithm
I Ceci est un diagramme de transition (rarement aussi régulier)
(153/210)
Problèmes de synchronisation (résumé)

I Condition de compétition (race condition)

I Définition : le résultat change avec l’ordre des instructions
I Difficile à corriger car difficile à reproduire (ordre aléatoire)
I Également type de problème de sécurité :
I Un programme crée un fichier temporaire, le remplit puis utilise le contenu
I L’attaquant crée le fichier avant le programme pour contrôler le contenu
I Interblocage (deadlock)
I Définition : un groupe de processus bloqués en attente mutuelle
I Évitement parfois difficile (correction de l’algorithme)
I Détection assez simple, mais pas de guérison sans perte
I Famine (starvation)
I Définition : un processus attend indéfiniment une ressource pourtant libre
I Servir équitablement les processus demandeurs

(154/210)
 Cinquième chapitre
Synchronisation entre processus
Introduction : notions de base
Condition de compétition et exclusion mutuelle
Exclusion mutuelle par verrouillage de fichiers
Notion d’interblocage
Exclusion mutuelle par attente active
Problèmes de synchronisation (résumé)
Sémaphores et schémas de synchronisation
Sémaphores
Exclusion mutuelle
Cohorte
Rendez-vous
Producteurs / Consommateurs
Lecteurs / Rédacteurs
Autres outils de synchronisation
Moniteurs
Synchronisations POSIX
compare-and-swap
Conclusion
Sémaphore : outil de base pour la synchronisation
Cohorte : généralisation de l’exclusion mutuelle
I Ressource partagée par au plus N utilisateurs
I Exemples :
I Parking payant
I Serveur informatique
P(v) V(v)
Sémaphore
I Objet composé :
I D’une variable : valeur de la sémaphore (nombre de places restantes)
I D’une file d’attente : liste des processus bloqués sur la sémaphore
I Primitives associées :
I Initialisation (avec une valeur positive ou nulle)
I Prise (P, Probeer, down, wait) = demande d’autorisation (puis-je ?)
Si valeur = 0, blocage du processus ; Si non, valeur = valeur − 1
I Validation (V, Verhoog, up, signal) = fin d’utilisation (vas-y)
Si valeur = 0 et processus bloqué, déblocage d’un processus ;
Si non, valeur = valeur + 1
E.W. Dijkstra. Solution of a Problem in Concurrent Programming Control. 1965. (lire l’article)
(156/210)
Schémas de synchronisation
Situations usuelles se retrouvant lors de coopérations inter-processus
I Exclusion mutuelle : ressource accessible par une seule entitée à la fois
I Compte bancaire ; Carte son
I Problème de cohorte : ressource partagée par au plus N utilisateurs
I Un parking souterrain peut accueillir 500 voitures (pas une de plus)
I Un serveur doom peut accueillir 2000 joueurs
I Rendez-vous : des processus collaborant doivent s’attendre mutuellement
I Roméo et Juliette ne peuvent se prendre la main que s’ils se rencontrent
I Le GIGN doit entrer en même temps par le toit, la porte et la fenêtre
I Processus devant échanger des informations entre les étapes de l’algorithme
I Producteurs/Consommateurs : un processus doit attendre la fin d’un autre
I Une Formule 1 ne repart que quand tous les mécaniciens ont le bras levé
I Réception de données sur le réseau puis traitement
I Lecteurs/Rédacteurs : notion d’accès exclusif entre catégories d’utilisateurs
I Sur une section de voie unique, tous les trains doivent rouler dans le même sens
I Un fichier pouvant être lu par plusieurs, si personne ne le modifie
I Tâches de maintenance (défragmentation) quand pas de tâches interactives
Comment résoudre ces problèmes avec les sémaphores ?
(157/210)
Exclusion mutuelle par sémaphore

Très simple

Initialisation
sem=semaphore(1)

Agence Nancy Agence Karlsruhe

P(sem) P(sem)
courant = get account(1867A) aktuelles = get account(1867A)
nouveau = courant + 1000 neue = aktuelles - 1000
update account (1867A, nouveau) update account(1867A, neue)
V(sem) V(sem)

(158/210)
Cohortes et sémaphores

Sémaphore inventée pour cela

Initialisation Garer sa voiture

sem=semaphore(3) /* nombre de places */ P(sem)
poser sa voiture au parking
aller faire les courses
Reprendre la voiture
V(sem)
partir

Exercice : quelle est la valeur de sem.v ici ?

1, et ça sera 0 quand cette voiture sera rentrée

P(v) V(v)

(159/210)
Rendez-vous et sémaphores
I Envoi de signal
I Un processus indique quelque chose à un autre (disponibilité donnée)
Initialisation Processus 1 Processus 2
... ...
top=semaphore(0)
calcul(info) P(top) /*Bloque en attente*/
V(top) utilisation(info)
... ...

I top = sémaphore privée (initialisée à 0)

utilisée pour synchro avec quelqu’un, pas sur une ressource
I Rendez-vous entre deux processus
I Les processus s’attendent mutuellement

Initialisation Processus romeo Processus juliette

roméo=semaphore(0) P(romeo) /*se bloque*/ V(romeo) /*libère R*/
juliette=semaphore(0) V(juliette) /*libère J*/ P(juliette) /*bloque*/

I Rendez-vous entre trois processus et plus

I On parle de barrière de synchronisation
I La solution précédente est généralisable, mais un peu lourde
I Souvent une primitive du système
(160/210)
Producteurs et consomateurs
Contrôle de flux entre producteur(s) et consommateur(s) par tampon
Principe
I Situation initiale : tampon vide (pas de lecture possible)
I Après une production :
I Une autre production :
I Encore une production : (plus de production possible)
I Une consommation : (production de nouveau possible)

Réalisation
Initialisation Producteur Consommateur
placeDispo=semaphore(N) répéter répéter
infoPrete=semaphore(0) calcul(info) P(infoPrete)
P(placeDispo) extraire(info)
déposer(info) V(placeDispo)
V(infoPrete) utiliser(info)

I Le tampon doit être circulaire pour traiter données dans l’ordre de production
I Attention aux compétitions entre producteurs (idem entre consommateurs)

(161/210)
Lecteurs et rédacteurs
Contrôle d’accès exclusif entre catégories d’utilisateurs

I Accès simultané de plusieurs lecteurs

I Accès exclusif d’un seul rédacteur, également exclusif de tout lecteur
I Schéma assez classique (fichier sur disque, zone mémoire, etc.)

Première solution
Initialisation Lecteur Rédacteur
lecteur=semaphore(1) P(lecteur) P(rédacteur)
rédacteur=semaphore(1) NbLect = NbLect + 1 lecturesEtEcritures()
NbLect=0 si NbLect == 1 alors V(rédacteur)
P(rédacteur)
V(lecteur)
lectures()
P(lecteur)
NbLect = NbLect - 1
si NbLect == 0 alors
V(rédacteur)
V(lecteur)

I Problème : famine potentielle des rédacteurs

(162/210)
Lecteurs et rédacteurs sans famine
Initialisation Lecteur Rédacteur
lecteur=semaphore(1) P(fifo) P(fifo)
rédacteur=semaphore(1) P(lecteur) P(rédacteur)
fifo=semaphore(1) NbLect = NbLect + 1 V(fifo)
NbLect=0 si NbLect == 1 alors lecturesEtEcritures()
P(rédacteur) V(rédacteur)
V(lecteur)
V(fifo)
lectures()
P(lecteur)
NbLect = NbLect - 1
si NbLect == 0 alors
V(rédacteur)
V(lecteur)

Exercice : pourquoi cette nouvelle sémaphore empêche la famine des rédacteurs ?

car tout le monde est bloqué dessus en arrivant
avant, les lecteurs pouvaient doubler les redacteurs car ils ne P(redacteur) pas
Exercice : montrer que les lecteurs peuvent encore partager l’accès
L’accès concurrent est placé apres le V(fifo), rien n’a changé à ce niveau

(163/210)
 Cinquième chapitre
Synchronisation entre processus
Introduction : notions de base
Condition de compétition et exclusion mutuelle
Exclusion mutuelle par verrouillage de fichiers
Notion d’interblocage
Exclusion mutuelle par attente active
Problèmes de synchronisation (résumé)
Sémaphores et schémas de synchronisation
Sémaphores
Exclusion mutuelle
Cohorte
Rendez-vous
Producteurs / Consommateurs
Lecteurs / Rédacteurs
Autres outils de synchronisation
Moniteurs
Synchronisations POSIX
compare-and-swap
Conclusion
Moniteur
Problème des sémaphores
I Tous les processus doivent les utiliser correctement
I Mauvais comportement d’un seul ⇒ problème pour l’ensemble
I Oubli d’un P(mutex) : CS pas respectée
I Oubli d’un V(mutex) : deadlock (Deni de Service – DoS)
I Causes possibles :
I Erreur de programmation
I Programme malveillant
Solution : le moniteur (synchronized en Java)
I Sorte d’objet contenant :
I Des variables partagées (privées)
I Une sémaphore protectrice
I Des méthodes d’accès
I Le compilateur ajoute les appels à la sémaphore pour protéger les méthodes
I Erreur impossible car usage seulement à travers l’API protégée
C.A.R. Hoare. Monitors: An Operating System Structuring Concept. 1974. (lire l’article)

(165/210)
L’exemple des banques avec un moniteur Java

public class compteBanquaire {

private int balance;
compteBanquaire() {
balance = 0;
}

void synchronized modifie(int montant) {

balance = balance + montant;
}
}

La méthode est invoquable par un thread au plus (en exclusion mutuelle)

La complexité est laissée au compilateur

(166/210)
Synchroniser conjointement des méthodes Java

public class compteBanquaire {

private int balance;
compteBanquaire() { balance = 0; }

void synchronized ajoute(int montant)

throws Exception {
if (montant<0) {
throw new Exception("Montant négatif");
} else {
balance = balance + montant;
Invocations sérialisées au sein de l’objet
} I Entre threads
}
I Entre les méthodes du même objet
void synchronized retire(int montant) I Pas entre les instances
throws Exception {
if (montant<0) { (invocations parallèles sur 6= objets)
throw new Exception("Montant négatif");
} else if (balance - montant < 0) {
throw new Exception("Solde insuffisant");
} else {
balance = balance - montant;
}
}

(167/210)
Synchronisation explicite en Java
Parfois, on veut contrôler finement la synchronisation
I synchroniser un morceau de la méthode, pas toute la méthode
I deux groupes de méthodes en exclusion mutuelle par groupe, mais pas globale
class Tutu {
synchronized void addObj(Object o){}
}class Toto { I Moniteur de Toto acquis dans addName
Tutu myTutu;
synchronized void addName(String n){ I Invocation de Tutu.addObj
nameCount++;
myTutu.addObj(name); ⇒ Moniteur Tutu verrouillé
} } ; deadlock toto ↔ tutu possible

class Tutu {
synchronized void addObj(Object o){} Verrouillage d’une partie de la méthode :
}class Toto {
Tutu myTutu; I Il faut spécifier l’objet verrouillé (ici : this)
void addName(String n){
synchronized(this) { I Verrou relaché avant Tutu.addObj
nameCount++;
} myTutu.addObj(name);
⇒ plus de deadlock possible
} } (attention à d’éventuelles compétitions)
Les verrous Java sont réentrants : Reprendre le même verrou n’est pas bloquant
(168/210)
Moniteurs et conditions
Moniteurs ne permettent pas d’attendre un événement
I Comparable au P() sur sémaphore à 0 (cf. place libérée sur le parking)
I Nouveau type de variable : condition x; (sorte de file d’attente)
I Primitives associées :
I x.wait() : Entre dans la file d’attente associée
I x.notify() : Libère un processus en attente (ou noop si personne n’attend)
I En Java, chaque objet a une condition implicite associée

Exemple : lecteur/écrivain synchronized int dequeue() {

int recu;
class Channel {
private int contenu; while (!plein) {
private boolean plein; try {
Channel() { plein = false; } wait();
synchronized void enqueue(int val) { } catch (InterruptedException e){}
while (plein) { }
try { recu = contenu;
wait(); full = false;
} catch (InterruptedException e){} notifyAll();
} return recu;
contenu = val; plein = true; }
notifyAll(); }
}
(169/210)
Synchronisations POSIX
Les sémaphores
I Font partie de System V, mais également de POSIX

Les verrous : mutex (mutual exclusion)

I Comme une sémaphore de capacité 1 (un processus prend le verrou)
I Sémantique plus simple / pauvre
I Standard = interface ; multiples implémentations (Linux : futex ; BSD : spinlock)
I Mutex réentrants : impossible de faire un deadlock avec soi-même

Les variables de condition

I Pour envoyer un événement aux gens qui l’attendent (ça les débloque)
I signal() débloque un seul processus ; broadcast() débloque tout le monde.
I Par rapport aux sémaphores : message perdu si personne n’est encore bloqué
I Usage assez complexe : il faut protéger chaque variable par un mutex

On y revient dans le prochain chapitre

(170/210)
compare-and-swap

Autre problème des sémaphores, moniteurs and co

I C’est bloquant : seul un algorithme peut agir en même temps
I Si on cherche non-bloquant, il faut des opérations atomiques
Compare-And-Swap (instructions binaires CAS et CAS2)
I Opération atomique : tentative de modification d’une variable partagée
I Si la valeur partagée est ce que je pense, je change la variable
Si non, je suis informé de la nouvelle valeur partagée
int CAS(int*adresse, int *ancienne val, int nouvelle val) {
if (*adresse == *ancienne val) {
*adresse = nouvelle val;
return TRUE;
} else {
*ancienne val = *adresse;
return FALSE;
} }

I Brique de base pour implémenter les sémaphores dans l’OS

I Recherche (actuelle) : structures partagées  Lock-free  et  Wait-free 

John D. Valois. Lock-Free Linked Lists Using Compare-and-Swap. 1995. (lire l’article)
(171/210)
Résumé du cinquième chapitre
Problèmes à éviter lors des synchronisations (et définitions)
I Interblocage : groupe de processus en attente mutuelle
I Compétition : le résultat dépend de l’ordre d’exécution
I Famine : un processus n’obtient pas la ressource car les autres l’en empêchent
Les sémaphores
I Principe : distributeur de jetons
I Opérations :
I initialisation : mettre des jetons dans la boite
I P : prendre un jeton (ou bloquer s’il y en a plus)
I V : rendre un jeton pris
Schémas de synchronisation classiques
I Exclusion mutuelle : Ressource utilisée par au plus un utilisateur
I Cohorte : Ressource partagée entre au plus N utilisateurs
I Rendez-vous : un processus attend un autre, ou attente mutuelle
I Producteurs/consommateurs : utilisation après création
I Lecteurs/rédacteurs : concurrence entre catégories d’utilisateurs
(172/210)
Résumé du cinquième chapitre (suite)

Moniteurs
I Principe : Objet auto-protégé par sémaphore
I Avantage : Pas d’erreur de manipulation possible
I Usage en Java : synchronized

Variable de condition
I Principe : Comme une sémaphore privée pour la communication entre threads
I Avantage : Permet le passage de relai entre threads
I Usage en Java : wait()/notifyAll()

CAS (Compare-And-Swap)
I Principe : Tentative de modif. si personne n’a modifié depuis dernière lecture
I Avantages : Implementer les sémaphores ; algo lock-free

(173/210)
Conclusion générale
Il n’y a pas de magie noire dans l’ordinateur
I Même un OS est finalement assez simple, avec des idées très générales
I Concepts : processus, mémoire, système de fichiers, pseudo-parallélisme
I Idées : interposition, préemption, tout-est-fichier, bibliothèque de fonctions
I Synchro : compétition, interblocage, famine. Sémaphore, mutex, moniteur . . .

Indispensable pour comprendre l’ordinateur

I 1% d’entre vous vont coder dans l’OS, 5% vont coder si bas niveau
I Mais ces connaissances restent indispensables pour comprendre la machine
I Programmer efficace en Java demande de comprendre le tas et les threads
I Les problèmes de synchro restent assez similaires dans les couches hautes

Ce que nous n’avons pas vu

I Le chapitre sur les threads, du moins pas dans de bonnes conditions
I L’implémentation de l’OS (cf. RSA) et des machines virtuelles
I High Perf Computing : Message-passing, cache-aware, out-of-core, parallélisme
I Recherche en OS : Virtualisation, synchro wait-free, spec formelle, (exokernels)
(174/210)
 Sixième chapitre
Programmer avec les threads
Introduction aux threads
Comparaison entre threads et processus
Avantages et inconvénients des threads
Design d’applications multi-threadées

Modèles de threads
Threads utilisateur ou noyau, modèles M:1, 1:1 et M:N
Études de cas

Programmer avec les Pthreads

Gestion des threads
Mutexes, sémaphores POSIX et variables de condition

Conclusion
Qu’est ce qu’un thread

Définition d’un thread

I Techniquement : un flot d’exécution pouvant être ordonnancé par l’OS
I En pratique : une procédure s’exécutant indépendemment du main
I Mot français : fil d’exécution ou processus léger (lightweight process)

Programme multi-threadé
I Un programme contenant diverses fonctions et procédures
I Ces procédures peuvent être exécutées simultanément et/ou indépendamment

(176/210)
Comparaison de processus et threads (1/2)

Processus classique (ou lourd)

Processus UNIX contient diverses informations : Memoire Meta−informations
du processus pour l’OS
I PID, PGID, UID, GID
I L’environnement Stack Pointer
routine1 Prog Counter
I Répertoire courant Pile var1 Registres
var2
I Pointeur d’instruction (PC)
text
main()
I Registres (code) routine1()
I Pile routine2()
process id
user id
I Tas data tableauA group id
(globales) tableauB
I Descripteurs de fichier fichiers
verrous
I Gestionnaires de signaux Tas sockets
I Bibliothèques partagées
Processus classique
I Outils d’IPC (tubes, sémaphores,
shmem, etc)

(177/210)
Comparaison de processus et threads (2/2)

Processus légers
routine2 Stack Pointer
I Plusieurs threads coexistent dans le Prog Counter
Pile varA
même processus lourd varB Registres
I Ils sont ordonnançables séparément
Stack Pointer
I Informations spécifiques routine1
Prog Counter
Pile var1 Registres
I Pile
var2
I Registres
I Priorité (d’ordonnancement) text
main()
I Données spécifiques (code) routine1()
I Liste des signaux bloqués routine2()
process id
user id
I Le reste est partagé data tableauA group id
I Si un thread ferme un fichier, (globales) tableauB
fichiers
il est fermé pour tous verrous
I Si un thread fait exit(), Tas sockets
tout s’arrête
I Globales et pointeurs vers le tas : Processus legers
variables partagées (à synchroniser)

(178/210)
Processus vs. thread en résumé
I Processus : environnement d’exécution pour les threads au sein de l’OS
État vis-à-vis de l’OS (fichiers ouverts) et de la machine (mémoire)
I Processus = Thread + Espace d’adressage

Code Données Fichiers Code Données Fichiers

Process−specific
Registres Pile Registres Registres Registres
Thread−specific
Pile Pile Pile

Processus mono−thread Processus multi−threads

L’espace d’adressage est passif ; le thread est actif

(179/210)
Pourquoi processus dits légers ?

Les threads contiennent moins de choses

I Partagent la plupart des ressources du processus lourd
I Ne dupliquent que l’indispensable
I ⇒ 2 threads dans 1 processus consomment moins de mémoire que 2 processus

Les threads sont plus rapides à créer

fork() threads
Machine real user sys real user sys
Celeron 2GHz 4.479s 0.364s 3.756s 1.606s 0.380s 0.388s
AMD64 2.5GHz (4CPU) 7.006s 0.936s 6.244s 0.903s 0.300s 0.640s

Les communications inter-threads sont rapides

I Bus PCI (donc, carte réseau) : 128 Mb/s
I Copie de mémoire (Tubes ; Passage message sur SMP) : 0,3 Gb/s
I Mémoire vers CPU (Pthreads) : 4 Gb/s

(180/210)
Usage des threads

Pourquoi utiliser les threads

I Objectif principal : gagner du temps (threads moins gourmands que processus)

Quand utiliser les threads

I Pour un recouvrement calcul/communication
I Pour avoir différentes tâches de priorité différentes
ordonnancement temps réel  mou
I Pour gérer des événements asynchrones
Tâches indépendantes activées par des événements de fréquence irrégulière
Exemple : Serveur web peut répondre à plusieurs requêtes en parallèle
I Pour tirer profit des systèmes SMP ou CMP (multi-cœurs)

(181/210)
Quand (pourquoi) ne pas utiliser les threads
Problèmes du partage de la mémoire
I Risque de corruption mémoire (risque de compétition)
I Besoin de synchronisation (risque d’interblocage)
⇒ Communication inter-threads rapide mais dangereuse
I Segfault d’un thread → mort de tous
I Casse l’abstraction en modules indépendants
I Extrêmement difficile à debugger (dépendances temporelles ; pas d’outils)
Programmeurs
Débutants Magiciens
Programmer avec les threads, Programmeurs Visual Basic
Programmeurs C
c’est enlever les gardes-fous de l’OS Programmeurs C++
pour gagner du temps Programmeurs threads

(Why Threads are a Bad Idea, USENIX96)

Obtenir de bonnes performances est très difficile

I Verrouillage simple (moniteurs) amène peu de concurrence
I Verrouillage fin augmente la complexité (concurrence pas facilement meilleure)
(182/210)
Design d’applications multi-threadées

Applications candidates
I Applis organisées en tâches indépendantes s’exécutant indépendamment
I Toutes routines pouvant s’exécuter en (pseudo-)parallèle sont candidates
I Interface interactive (; latence indésirable) avec des calculs ou du réseau

Dans l’exemple, routine1() et routine2() sont candidates

Routine1() Routine2() RoutineFinale()

Routine2() Routine1() RoutineFinale()

R2 R1 RoutineFinale()

Routine1() RoutineFinale()
Routine2()

(183/210)
Code réentrant et threads-safeness
Code réentrant
I Définition : Peut être appelé récursivement ou depuis plusieurs endroits
I Ne pas maintenir d’état entre les appels
I Contre-exemple : strtok, rand (strtok r est réentrante)
I Ne pas renvoyer un pointeur vers une statique
I Contre-exemple : ctime (ctime r est réentrante)

Code thread-safe
I Définition : Fonctionne même si utilisé de manière concurente
I Si le code n’est pas réentrant, il faut le protéger par verrous
Problème des dépendances
I Votre code est thread-safe, mais vos bibliothèques le sont-elles ?
I La libc est réentrante (sous linux modernes)
I Exemple de errno : chaque thread a maintenant son propre errno
I Pour le reste, il faut vérifier (voire, supposer qu’il y a un problème)
I En cas de problème, il faut protéger les appels grâce à un verrou explicite
(184/210)
Patterns classiques avec les threads

Maitre/esclaves
I Un thread centralise le travail à faire et le distribue aux esclaves
I Pool d’esclaves statique ou dynamique
I Exemple : serveur web

Pipeline
I La tâche est découpée en diverses étapes successives
Chaque thread réalise une étape et passe son résultat au suivant
I Exemple : traitement multimédia (streaming)

Peer to peer
I Comme un maitre/esclaves, mais le maitre participe au travail

(185/210)
 Sixième chapitre
Programmer avec les threads
Introduction aux threads
Comparaison entre threads et processus
Avantages et inconvénients des threads
Design d’applications multi-threadées

Modèles de threads
Threads utilisateur ou noyau, modèles M:1, 1:1 et M:N
Études de cas

Programmer avec les Pthreads

Gestion des threads
Mutexes, sémaphores POSIX et variables de condition

Conclusion
Implantation des threads : Modèle M:1
Tous les threads d’un processus mappés sur un seul thread noyau
Service implémenté dans une bibliothèque spécifique
I Gestion des threads au niveau utilisateur
I Avantages :
Espace utilisateur
I Pas besoin de modifier le noyau Processus Processus Processus
I Rapides pour créer un thread, et pour
changer de contexte
I Portables entre OS
Ordonnanceur Ordonnanceur Ordonnanceur
I Inconvénients :
I Ordonnancement limité à celui d’un
processus système Ordonnanceur

⇒ Erreurs d’ordonnancement Espace noyau

I Appel bloquant dans un thread Processeur(s)

⇒ blocage de tous
I Pas de parallélisme (D’après F. Silber)

(dommage pour les SMP)

⇒ Efficace, mais pas de concurrence
I Exemples : Fibres Windows, Java Green Threads, GNU pth (portable thread)

(187/210)
Modèle 1:1
Chaque thread utilisateur mappé sur un thread noyau
Modification du noyau pour un support aux threads
I Gestion des threads au niveau système (LightWeight Process – LWP)
I Avantages Espace utilisateur

I Appel bloquant dans un thread Processus Processus Processus

⇒ exécution d’un autre

I Parallélisme possible
I Ordonnancement du noyau plus approprié
I Inconvénients
I Besoin d’appels systèmes spécifiques
(clone() pour la création sous linux) Ordonnanceur

I Commutation réalisée par le noyau Espace noyau

⇒ changements de contexte (coûteux) Processeur(s)

⇒ Concurrence importante, mais moins efficace (D’après F. Silber)

(nombre total de threads souvent borné)
I Exemples : Windows 95/98/NT/2000, OS/2, Linux, Solaris 9+

(188/210)
Modèle M:N
M threads utilisateur mappés sur N threads noyau (M ≥ N ≥ 1)
Services utilisateur basés sur des services noyau

I Coopération entre l’ordonnanceur noyau et un ordonnanceur utilisateur

I Avantages : le meilleur des deux mondes
Espace utilisateur
I Threads noyaux plus basiques et efficaces Processus Processus Processus
I Threads utilisateurs plus flexibles
I Moins de changement de contexte
I Pas d’erreur d’ordonnancement
Ordonnanceur Ordonnanceur Ordonnanceur
I Inconvénients :
I Extrêmement difficile à implémenter
I Un peu usine à gaz :
Ordonnanceur
I modèle théorique plus pur
Espace noyau
I implémentations complexes
I efficacité parfois discutable Processeur(s)

I Concurrence importante, bonne efficacité ( ?) (D’après F. Silber)

I Exemples : Solaris avant v9, IRIX, HP-UX

(189/210)
Études de cas (1/3)

Pthreads
I POSIX threads : norme standardisé par IEEE POSIX 1003.1c (1995)
I Ensemble de types et fonctions C dont la sémantique est spécifiée
I Seulement une API : implémentation sous tous les UNIX (et même Windows)
Threads Solaris
I Modèle M:N
I Threads intermédiaires (LWP)
Threads Windows 2000
I Modèle 1:1 pour les WinThreads
I Modèle M:1 pour les fibres (l’OS ne voit pas les fibres)
Threads Java
I Extension de la classe Thread ; Implantation de l’interface Runnable
I Implémentation dépend de la JVM utilisée

(190/210)
Études de cas (2/3)
Threads sous linux
I Threads mappé sur des tâches (tasks)
I Appel système clone() pour duppliquer une tâche (fork() implémenté avec ça)
Plusieurs bibliothèques implémentant le standard Pthreads
I Depuis 1996 : LinuxThreads
I Modèle 1:1, par Xavier Leroy (INRIA, créateur d’Ocaml)
I Pas complètement POSIX (gestion des signaux, synchronisation)
I ≈ 1000 threads au maximum
I Next Generation POSIX Threads
I Modèle M:N, par IBM ; abandonné

; NPTL avançait plus vite

; M:N induisait une complexité trop importante
I Maintenant Native POSIX Thread Library
I Modèle 1:1, par Ulrich Drepper (acteur principal libc, chez Red Hat)
I Totalement conforme à POSIX
I Bénéficie des fonctionnalités du noyau Linux 2.6 (ordonnancement O(1))
I Création de 100 000 threads en 2 secondes (contre 15 minutes sans)
(191/210)
Études de cas (3/3)

Possibilités de quelques systèmes d’exploitations

1 seul espace plusieurs espaces
d’adressage d’adressage
1 seul thread MS/DOS Unix
par espace d’adressage Macintosh (OS9) traditionnels
plusieurs threads Systèmes Win/NT, Linux, Solaris
par espace d’adressage embarqués HP-UP, OS/2, Mach, VMS

(192/210)
 Sixième chapitre
Programmer avec les threads
Introduction aux threads
Comparaison entre threads et processus
Avantages et inconvénients des threads
Design d’applications multi-threadées

Modèles de threads
Threads utilisateur ou noyau, modèles M:1, 1:1 et M:N
Études de cas

Programmer avec les Pthreads

Gestion des threads
Mutexes, sémaphores POSIX et variables de condition

Conclusion
Généralités sur l’interface Pthreads
Trois grandes catégories de fonctions / types de données
Gestion des threads
I Créer des threads, les arrêter, contrôler leurs attributs, etc.
Synchronisation par mutex (mutual exclusion)
I Créer, détruire verrouiller, déverrouiller des mutex ; Contrôler leurs attributs
Variables de condition :
I Communications entre threads partageant un mutex
I Les créer, les détruire, attendre dessus, les signaler ; Contrôler leurs attributs

Préfixe d’identificateur Groupe

pthread Threads eux-mêmes et diverses fonctions
pthread attr Attributs des threads
pthread mutex Mutexes
pthread cond Variables de condition
... ...

(194/210)
L’interface Pthreads en pratique
I Types de données sont structures opaques, fonctions d’accès spécifiques
I L’interface compte 60 fonctions, nous ne verrons pas tout
I Il faut charger le fichier d’entête pthread.h dans les sources
I Il faut spécifier l’option -pthread à gcc

thread-ex1.c
#include <pthread.h>
void *hello( void *arg ) {
int *id = (int*)arg;
printf("%d: hello world \n", *id); $ gcc -pthread -o thread-ex1 thread-ex1.c
pthread_exit(NULL); $ ./thread-exemple1
} Crée thread 1
int main (int argc, char *argv[ ]) { Crée thread 2
pthread_t thread[3]; Crée thread 3
int id[3]={1,2,3}; 1 : hello world
int i; 2 : hello world
3 : hello world
for (i=0;i<3;i++) { $
printf("Crée thread %d\n",i);
pthread_create(&thread[i], NULL,
hello, (void *)&id[i]);
}
pthread_exit(NULL);
}
.
(195/210)
Identification et création des threads
Identifier les threads
I pthread t : équivalent du pid t (c’est une structure opaque)
I pthread t pthread self () : identité du thread courant
I int pthread equal (pthread t, pthread t) : test d’égalité

Créer de nouveaux threads

I Le programme est démarré avec un seul thread, les autres sont créés à la main
I int pthread create(identité, attributs, fonction, argument) ;
I identité : [pthread t*] identifieur unique du nouveau thread (rempli par l’appel)
I attributs : Pour modifier les attributs du thread (NULL → attributs par défaut)
I fonction : [void *(*)(void *)] Fonction C à exécuter (le main du thread)
I argument : argument à passer à la fonction. Doit être transtypé en void*
I retour : 0 si succès, errno en cas de problème
Exercice : Comment savoir dans quel ordre vont démarrer les threads créés ?
On peut pas, ca dépend des fois (gare aux races conditions)

Exercice : Comment passer deux arguments à la fonction ?

en définissant une structure
(196/210)
Exemple FAUX de passage d’arguments
thread-faux1.c
#include <pthread.h>
void *hello( void *id ) {
printf("%d: hello world \n", (char *) id);
pthread_exit(NULL);
}

int main (int argc, char *argv[ ]) {

pthread_t th[3];
int i;

for (i=0;i<3;i++) {
printf("Crée thread %d\n",i);
pthread_create(&th[i], NULL, hello, (void *)&i);
}

pthread_exit(NULL);
}
.

Exercice : Quel est le problème ?

On transforme i en globale inter-thread, et sa valeur peut donc être changée dans
le thread lanceur avant le démarrage du thread utilisateur. C’est une belle condition
de compétition.

(197/210)
Exemple de passage d’arguments complexes
int main(int argc, char *argv[ ]) {
pthread_t threads[NUM_THREADS];
int rc, t, sum=0;
#include <pthread.h>
#include <stdio.h>
char *messages[NUM_THREADS] = {
#include <stdlib.h>
"EN: Hello World!", "FR: Bonjour, le monde!",
#define NUM_THREADS 8
"SP: Hola al mundo", "RU: Zdravstvytye, mir!",
"DE: Guten Tag, Welt!", "Klingon: Nuq neH!",
typedef struct data {
"JP: Sekai e konnichiwa!",
int thread_id,sum;
"Latin: Orbis, te saluto!" };
char *msg;
} data_t;
for(t=0;t<NUM_THREADS;t++) {
sum = sum + t;
data_t data_array[NUM_THREADS];
thread_data_array[t].thread_id = t;
thread_data_array[t].sum = sum;
void *PrintHello(void *arg) {
thread_data_array[t].message = messages[t];
data_t *mine = (data_t *)arg;
printf("Creating thread %d\n", t);
rc = pthread_create(&threads[t], NULL,
sleep(1);
PrintHello,
printf("Thread %d: %s Sum=%d\n",
(void*)&thread_data_array[t]);
mine->thread_id,
if (rc) {
mine->msg,
printf("ERROR; _create() returned %d\n", rc);
mine->sum);
exit(-1);
pthread_exit(NULL);
}
}
}
pthread_exit(NULL);
}

(198/210)
Terminaison des threads

Causes de terminaison des threads

I Le thread termine sa fonction initiale
I Le thread appelle la routine pthread exit()
I Le thread est tué par un autre thread appelant pthread cancel()
I Tout le processus se termine à cause d’un exit, exec ou return du main()

Terminer le thread courant

I void pthread exit(void *retval) ;
I retval : valeur de retour du thread (optionnel)
I Pour récupérer code de retour, un autre thread doit utiliser pthread join()

(199/210)
Attendre la fin d’un thread

Joindre un thread
I int pthread join ( pthread t, void ** )
I Le thread A joint le thread B : A bloque jusqu’à la fin de B
I Utile pour la synchronisation (rendez-vous)
I Second argument reçois un pointeur vers la valeur retour du pthread exit()
I Similaire au wait() après fork()
(mais pas besoin d’être le créateur pour joindre un thread)

Détacher un thread
I int pthread detach ( pthread t )
I Détacher un thread revient à dire que personne ne le joindra à sa fin
I Le système libère ses ressources au plus vite
I Évite les threads zombies quand on ne veut ni synchro ni code retour
I On ne peut pas ré-attacher un thread détaché

(200/210)
Attributs des threads
C’est le second argument du create
Les fonctions associées
I Création et destruction d’un objet à passer en argument à create :
I int pthread attr init ( pthread attr t * )
I int pthread attr destroy ( pthread attr t * )
I Lecture : int pthread attr getX ( const pthread attr t *, T * )
I Mise à jour : int pthread attr setX ( pthread attr t *, T )
Attributs existants
I detachstate (int) : PTHREAD CREATE [JOINABLE|DETACHED]
I schedpolicy (int)
I SCHED OTHER : Ordonnancement classique
I SCHED RR : Round-Robin (chacun son tour)
I SCHED FIFO : Temps réel
I schedparam (int) : priorité d’ordonnancement
I stackaddr (void*) et stacksize (size t) pour régler la pile
I inheritsched, scope
(201/210)
Exemple de gestion des threads

#include <pthread.h>
for(t=0;t<NUM_THREADS;t++) {
#include <stdio.h>
printf("Creating thread %d\n", t);
#include <stdlib.h>
if ((rc = pthread_create(&thread[t], &attr,
#define NUM_THREADS 3
travail, NULL))) {
printf("ERREUR de _create() : %d\n", rc);
void *travail(void *null) {
exit(-1);
int i;
}}
double result=0.0;
/* Libère l’attribut */
for (i=0; i<1000000; i++)
pthread_attr_destroy(&attr);
result = result + (double)random();
/* Attend les autres */
printf("Resultat = %e\n",result);
for(t=0;t<NUM_THREADS;t++) {
pthread_exit(NULL);
if ((rc = pthread_join(thread[t],
}
/*pas de retour attendu*/NULL))) {
printf("ERREUR de _join() : %d\n", rc);
int main(int argc, char *argv[ ]) {
exit(-1);
pthread_t thread[NUM_THREADS];
}
pthread_attr_t attr;
printf("Rejoint thread %d. (ret=%d)\n",
int rc, t;
t, status);
/* Initialise et modifie l’attribut */
}
pthread_attr_init(&attr);
pthread_exit(NULL);
pthread_attr_setdetachstate(&attr,
}
PTHREAD_CREATE_JOINABLE);

(202/210)
 Sixième chapitre
Programmer avec les threads
Introduction aux threads
Comparaison entre threads et processus
Avantages et inconvénients des threads
Design d’applications multi-threadées

Modèles de threads
Threads utilisateur ou noyau, modèles M:1, 1:1 et M:N
Études de cas

Programmer avec les Pthreads

Gestion des threads
Mutexes, sémaphores POSIX et variables de condition

Conclusion
Les mutex Pthreads

Interface de gestion
I Type de donnée : pthread mutex t
I Création :
I statique : pthread mutex t mutex = PTHREAD MUTEX INITIALIZER ;
I dynamique : pthread mutex init(pthread mutex t *, pthread mutexattr t *) ;
Premier argument : adresse de (pointeur vers) la variable à initialiser
I Destruction : pthread mutex destroy(mutex) (doit être déverrouillé)
I (pas d’attributs POSIX, mais il y en a dans certaines implémentations)

Interface d’usage
I pthread mutex lock(mutex) Bloque jusqu’à obtention du verrou
I pthread mutex trylock(mutex) Obtient le verrou ou renvoie EBUSY
I pthread mutex unlock(mutex) Libère le verrou

(204/210)
Usage des mutex

Les mutex sont un gentlemen’s agreement

Thread 1 Thread 2 Thread 3

Lock Lock
A = 2 A = A+1 A = A*B
Unlock Unlock

I Thread 3 crée une condition de compétition même si les autres sont disciplinés
(cf. les verrous consultatifs sur les fichiers)
I Pas d’équivalent des verrous impératifs sur la mémoire
I Pas de moniteurs dans PThreads (durs à implémenter en C)

(205/210)
Sémaphores POSIX
I On parle ici de l’interface POSIX, pas de celle IPC Système V
I #include <semaphore.h>
I Type : sem t

Interface de gestion
I int sem init(sem t *sem, int pshared, unsigned int valeur)
pshared !=0 ⇒ sémaphore partagée entre plusieurs processus (pas sous linux)
I int sem destroy(sem t * sem) (personne ne doit être bloqué dessus)

Interface d’usage
I int sem wait(sem t * sem) réalise un P()
I int sem post(sem t * sem) réalise un V()
I int sem trywait(sem t * sem) P() ou renvoie EAGAIN pour éviter blocage
I int sem getvalue(sem t * sem, int * sval)
(206/210)
Variables de condition
Interface de gestion
I Type de donnée : pthread cond t
I Création :
I statique : pthread cond t cond = PTHREAD COND INITIALIZER ;
I dynamique : int pthread cond init(pthread cond t *, pthread condattr t *)

I Destruction : int pthread cond destroy(pthread cond t *)

I Il n’y a pas d’attributs POSIX (ni linux) pour les conditions

Rappel du principe des conditions

I Cf. conditions Java (wait() et notifyAll())
I Autre mécanisme de synchronisation.
I mutex : solution pratique pour l’exclusion mutuelle
I sémaphore : solution pratique pour les cohortes
I condition : solution pratique pour les rendez-vous
I compare-and-swap : solution pour la synchronisation non-bloquante

(207/210)
Exemple d’usage des conditions
Thread principal
(1) Déclare et initialise une globale requérant une synchronisation (ex : compteur)
(1) Déclare et initialise une variable de condition et un mutex associé
(1) Crée deux threads (A et B) pour faire le travail
Thread A Thread B
(2) Travaille jusqu’au rendez-vous (2) Fait des choses
(point où B doit remplir une (3) Verrouille le mutex
condition, compteur > 0 par ex)
(3) Modifie la globale attendue par A
(2) Verrouille mutex et consulte variable
(3) Si la condition est atteinte, signale A
(2) Attend la condition de B
(3) Déverrouille le mutex
ça libère le mutex (pour B) et gèle A
(4) Au signal, réveil
mutex automagiquement repris
(4) Déverrouille explicitement
Thread principal : (5) Rejoint les deux threads puis continue
(208/210)
Les conditions POSIX

Interface d’usage
I pthread cond signal(pthread cond t *) Débloque un éventuel thread bloqué
I pthread cond wait(pthread cond t *, pthread mutex t *) Bloque tant que la
condition n’est pas réalisée
I pthread cond timedwait(pthread cond t*, pthread mutex t*,struct timespec*)
Bloque au plus tard jusqu’à la date spécifiée
I pthread cond broadcast(pthread cond t *) Réveille tous les bloqués (sont
encore bloqués par mutex)
Pièges des conditions
I Risque d’interblocage ou de pas de blocage si protocole du mutex pas suivi
I Différence sémantique avec sémaphore :
I Si sem==0, alors V(sem) ⇒ sem := 1
I Signaler une condition que personne n’attend : noop (info perdue)

(209/210)
Résumé du sixième chapitre
I Définition de threads (vs. processus) : proc=espace
d’adressage+meta-données OS ; thread=fil d’exécution
I Avantages et inconvénients : Ca va plus vite, mais c’est plus dangereux
I Schémas d’implémentations :
I Modèle M:1 : M threads par processus (portable et rapide, pas parallèle)

I Modèle 1:1 : Threads gérés par l’OS directement (plus dur à implémenter, plus
efficace en pratique)
I Modèle M:N : Gestion conjointe (modèle théorique meilleur, difficile à faire
efficacement)
I Les fonctions principales de l’interface POSIX :
I pthread create : crée un nouveau thread
I pthread exit : termine le thread courant
I pthread join : attend la fin du thread et récupère son errcode
I pthread detach : indique que personne ne rejoindra ce thread
I mutex {lock,unlock,*}: usage des mutex
I sem {wait,post,*}: usage des sémaphore
I cond {wait,signal,*}: usage des conditions

(210/210)