MINISTERE DE L’ENSEIGNEMENT SUPERIEURE ET DE LA RECHERCHE SCIENTIFIQUE

UNIVERSITE IBN KHALDOUN - TIARET

FACULTÉ MATHEMATIQUES ET INFORMATIQUE
DÉPARTEMENT D’INFORMATIQUE

Système d'exploitation
Synthèse des cours et recueil d 'exercices corrigés
pour le module du système d'exploitation 1

GUIDE DE L 'ÉTUDIANT
Présenté Par :
Dr. Abdelkader OUARED

Cet ouvrage présente de façon pédagogique la synthèse des cours

et des exercices autour des concepts de base du système d'exploitation

Professeur ı Étudiant ı Centre

Pour plus de détails ou de précisions,

Contacter l'auteur:
Abdelkader OUARED Maître de conférence à l'universite Ibn Khaldoun -Tiaret
http://moodle.univ-tiaret.dz/
[email protected]
 Remerciements

Ces trois dernièrs mois ont été pour moi l’occasion de rédiger mon premier livre autour du module
système d’exploitation en cette période difficile de propagation du Covid-19 . Je n’aurai jamais pu
mener cette première experience à terme sans l’appui moral et scientifique de mes chers amis qui m’ont
aidé à m’aménager beaucoup de "parenthèses". Au terme de cette periode de rédaction de livre, je
tiens tout d’abord à exprimer toute ma profonde gratitude aux personnes suivantes :
Ladjel Bellatreche qui n’a ménagé aucun effort en voulant me faire partager sa grande passion de la
recherche. Merci pour son génie qui fait de lui une vraie machine à idées pas toujours facile à suivre -.
J’ai appris beaucoup de choses de lui, et grace a lui je suis passionné par la recherche ,....
Un merci pour M. Abdelhafid chadlipour tous ses efforts afin de me corriger minutieusement le livres
et m’apprendre à les rédiger, pour sa rigueur, la clarté de ses idées ainsi que ses conseils avisés. J’ai
beaucoup appris aux côtés de mes colleagues tant sur le plan humain que scientifiques.
Un merci tout particulier à Yassine Mohammedi, mon adorable "colleague" qui, par son énergie, sa
gentillesse et son humour, m’a toujours redonné espoir et motivation, et ce depuis le premier jour de
mon arrivée à l’UIK.
Mes pensées vont d’abord à mes chers collègues pour leur soutien amical et pour leur professionnalisme :
— "‘Les Colleagues"’ : du département mathématiques et informatique.
— "‘Les Amis"’ : Tayeb, Madjid, Benaouda, Mohamed, Noureddine,Youcef, Amine et Djamel.
Merci au destin de m’avoir permis de croiser les chemins de : Kamel Boukhlfa, Abdelmalek, Selma
Bouarare, Selma Khouri, Amine Roukh, Sabrina, Lahcen, Farsi Mohamed, Soumia Benkrid et Fatima
Zohra pour leur esprit perspicace et généreux dont j’ai beaucoup appris...
Enfin et surtout, j’aimerais remercier ma famille : Ma mère, mon Père Mes frères, Mes soeurs.
Je clos ces remerciements par une pensée à tous ceux qui me sont chers. Que tous ceux et celles que je
n’ai pas mentionnés n’en reçoivent pas moins ma gratitude.

iii
 Table des matières

Liste des figures xi

Liste des tableaux xiv

Partie I Introduction 1

Introduction générale 3

Partie II La liste des exercices 5

Chapitre 1 Introduction aux Systèmes d’Exploitation 7

1.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Synthèse du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Relation entre matériel et logiciel . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Système d’exploitation : Principe . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Appels Système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.4 Evolution des systèmes d’exploitation . . . . . . . . . . . . . . . . . . . . . 9
1.2.5 Classification des SE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 La liste des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.5 Exercice n°5 : Ex : Systèmes Multi-utilisateurs (« time-sharing ») . . . . . 12
1.3.6 Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.7 Exercice n°7 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.8 Exercice n°8 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Chapitre 2 Système de Gestion des Fichiers (SGF) 19

2.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Synthèse du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Notion des Fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Organisations physiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 C’est quoi un SGF ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

v
Table des matières

2.2.4 Techniques d’allocation des blocs physiques . . . . . . . . . . . . . . . . . 22

2.2.4.1 Allocation contiguë . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.4.2 Allocation chainée . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.4.3 Index de blocs hiérarchisés . . . . . . . . . . . . . . . . . . . . . 24
2.3 Les performances d’un SGF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 La liste des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Chapitre 3 Gestion des périphériques : Interruption, Attente Active, et DMA 33

3.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Synthèse du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 Les interruptions en informatique . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.2 Gestion des Entrées Sorties (E/S) . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3 Type d’interruptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.4 Déroulement d’une interruption . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.4.1 Le vecteur d’interruption . . . . . . . . . . . . . . . . . . . . . . 35
3.2.4.2 Le vecteur d’interruption . . . . . . . . . . . . . . . . . . . . . . 36
3.2.4.3 Etapes d’éxécution d’un programme . . . . . . . . . . . . . . . . 36
3.2.5 Attente Active (Polling) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.6 Accès Direct à la Mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3 La liste des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.6 Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.7 Exercice n°7 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Chapitre 4 Gestion des Processus (primitives fork/join) 45

4.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 Synthèse du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.1 Notion de Processus : Qu’est ce qu’un Processus ? . . . . . . . . . . . . . . 46
4.2.2 Tables de Ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.3 Contexte d’un processus (Process Image) . . . . . . . . . . . . . . . . . . . 47
4.2.4 Modes d’exécution des processus . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.5 Etats des processus : Cycle de vie d’un processus . . . . . . . . . . . . . . . 48
4.2.6 Implémentation des processus . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2.7 Opérations sur les processus . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.7.1 Création de processus . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.8 Destruction de processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.9 Processus suspendu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

vi
 4.2.10 Les thread et le parallélisme . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3 La liste des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3.6 Exercice n°6 : Diviser pour calculer plus vite . . . . . . . . . . . . . . . . . 55
4.3.7 Exercice n°7 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3.8 Exercice n°8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Chapitre 5 Ordonnancement des processus (scheduling de l’UC) 61

5.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Synthèse du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2.1 Rappel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2.2 CPU Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2.3 Allocateur (dispatcher) vs Planificateur (scheduler) . . . . . . . . . . . . . . 62
5.2.4 Les critères de scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2.5 Scheduling Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2.5.1 Algorithme du premier arrivé, premier servi (First come, first
served ou FCFS) . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.2.5.2 Algorithme du travail le plus court d’abord (Shortest Job First ou
SJF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2.5.3 Algorithme avec priorité . . . . . . . . . . . . . . . . . . . . . . 65
5.2.5.4 Algorithme du tourniquet (Round-Robin ou RR) . . . . . . . . . 66
5.2.5.5 Algorithme SRT : temps restant le plus court (Shortest Remaining
Time) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2.5.6 Algorithme avec files multiniveaux . . . . . . . . . . . . . . . . . 68
5.2.5.7 Algorithme avec files multiniveaux avec recyclage (MFQ, Multile-
vel Feedback Queues) . . . . . . . . . . . . . . . . . . . . . . . . 68
5.3 La liste des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.3.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.3.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3.6 Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3.7 Exercice n°7 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.4 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

Chapitre 6 Pagination à la demande 77

6.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2 Synthèse du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.2.1 Execution des programmes informatique . . . . . . . . . . . . . . . . . . . 78
6.2.2 La Gestion de Mémoire (Pourquoi ?) . . . . . . . . . . . . . . . . . . . . . 79
6.2.2.1 Problèmes : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.2.2.2 Principe de la solution . . . . . . . . . . . . . . . . . . . . . . . 80

vii
Table des matières

6.2.3 Swapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.2.4 Adressage Mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2.5 Gestionnaire de la mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2.6 Comment implémenter la mémoire virtuelle ? . . . . . . . . . . . . . . . . 81
6.2.6.1 La pagination de la mémoire ? . . . . . . . . . . . . . . . . . . . 81
6.2.7 Gestion de la mémoire virtuelle : La pagination à la demande . . . . . . . . 83
6.2.8 Représentation des espaces virtuels des processus et de l’espace physique . 84
6.2.9 Détection et traitement d’un défaut de page . . . . . . . . . . . . . . . . . . 85
6.2.10 Remplacement de pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.2.11 Les algorithmes de remplacement . . . . . . . . . . . . . . . . . . . . . . . 85
6.2.11.1 Algorithme FIFO . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.2.11.2 L’algorithme optimal (OPT) . . . . . . . . . . . . . . . . . . . . . 86
6.2.11.3 Algorithme LRU (Least Recently Used) . . . . . . . . . . . . . . . 87
6.3 La liste des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.3.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.3.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.3.6 Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.3.7 Exercice n°7 (Algorithme de l’horloge : liste circulaire) : . . . . . . . . . . 89
6.4 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

Partie III Le corrigé des exercices 93

Chapitre 1 Correction : Introduction aux Systèmes d’Exploitation 97

1.1 Le corrigé des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
1.1.1 Corrigé Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
1.1.2 Corrigé Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
1.1.3 Corrigé Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
1.1.4 Corrigé Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
1.1.5 Corrigé Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
1.1.6 Corrigé Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
1.1.7 Corrigé Exercice n°7 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
1.1.8 Corrigé Exercice n°8 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
1.2 Correction de QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

Chapitre 2 Correction : Système de gestion des fichiers (SGF) 109

2.1 Le corrigé des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
2.1.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
2.1.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
2.1.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
2.1.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
2.1.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
2.2 Correction de QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

Chapitre 3 Corrigé : Gestion des périphériques : Attente Active, Interruption et

viii
DMA 121
3.1 Le corrigé des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
3.1.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
3.1.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.1.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.1.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.1.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.1.6 Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.2 Correction de QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

Chapitre 4 Corrigé : Gestion des Processus (primitives fork/join) 129

4.1 Le corrigé des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.1.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.1.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.1.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
4.1.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
4.1.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.1.6 Exercice n°6 : Diviser pour calculer plus vite . . . . . . . . . . . . . . . . . 132
4.1.7 Exercice n°8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.2 Correction de QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

Chapitre 5 Corrigé : Ordonnancement des processus (scheduling de l’UC) 139

5.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2 Le corrigé des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
5.2.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
5.2.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
5.2.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
5.2.6 Exercice n°7 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
5.3 Correction de QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

Chapitre 6 Corrigé : Pagination à la demande 151

6.1 Le corrigé des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.1.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.1.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.1.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.1.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.1.5 Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6.2 Correction de QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

Bibliographie 159

ix
 Liste des figures

1 Relation entre matériel et logiciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Couches du système d’exploitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Illustration : appels système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 Chronologie simplifiée des premiers systèmes . . . . . . . . . . . . . . . . . . . . . . . 10
5 Organigramme du processus démarrage d’un ordinateur (boot en anglais) . . . . . . . . 12

1 Fichiers comme une abstraction des propriétés physiques des dispositifs de stockage . . 20
2 Bibliothèque standard d’E/S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Organisations physiques des fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4 Stockage des données structurées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5 Composantes du SGF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6 Allocation contiguë . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7 Allocation chainée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
8 Structure de i-node (Exemple : Unix) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1 Gestion des Entrées Sorties (E/S) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2 Mécanisme de rupture de séquence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3 Accès direct à la mémoire (Direct Memory Access) . . . . . . . . . . . . . . . . . . . . . 37
4 Délégation de la gestion de l’échange (Canaux, DMA). . . . . . . . . . . . . . . . . . . . 38

1 Programme vs Processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2 Contexte d’un processus (Process Image) . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3 Relation entre les processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4 Modes d’exécution des processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5 Modes d’exécution des processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6 Le Process Control Block (PCB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
7 Example : PCB de MS Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
8 Exemple de la commande ps (process status) . . . . . . . . . . . . . . . . . . . . . . . . 50
9 Fork and Join Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
10 Les transitions d’un processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
11 Graphes des précédences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
12 L’algorithme Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

1 Cycles d’utilisation CPU et d’attente sur E/S (I/O). . . . . . . . . . . . . . . . . . . . . . 62

xi
Liste des figures

2 Gestion du processeur par le scheduler et le dispatcher . . . . . . . . . . . . . . . . . . 63

3 l’ensemble de processus avec leurs temps du cycle en ms . . . . . . . . . . . . . . . . . 64
4 Calcule des métriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5 Diagramme de Gantt de l’algorithme FCFS . . . . . . . . . . . . . . . . . . . . . . . . . 64
6 Processus avec leurs temps de cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7 Diagramme de Gantt de l’algorithme SJF . . . . . . . . . . . . . . . . . . . . . . . . . . 65
8 Exemple : Algorithme avec priorité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
9 Exemple : Le diagramme de Gantt : Algo. avec priorité . . . . . . . . . . . . . . . . . . 66
10 Exemple : Algorithme avec Algorithme du tourniquet (Round-Robin ou RR) . . . . . . 66
11 Diagramme de Gantt de l’algorithme RR . . . . . . . . . . . . . . . . . . . . . . . . . . 67
12 Les temps d’attente et de restitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
13 Diagramme de Gantt de SRT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
14 Les temps d’attente et de restitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
15 Algorithme avec files multiniveaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
16 Algorithme avec Algorithme avec files multiniveaux avec recyclage (MFQ, Multilevel
Feedback Queues) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
17 Processus, avec la durée du cycle d’UC . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
18 Processus, avec la durée du cycle d’UC . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
19 Processus, avec la durée du cycle d’UC et du périphérique d’E/S. . . . . . . . . . . . . . 72

1 Cycle d’exécution d’une instruction typique . . . . . . . . . . . . . . . . . . . . . . . . 78

2 Les différentes étapes de l’exécution d’un programme . . . . . . . . . . . . . . . . . . . 79
3 Memory Management : échanger des blocs de données de MS->MC . . . . . . . . . . . 79
4 Contrôle et le partage des informations entre les processus . . . . . . . . . . . . . . . . 80
5 Principe de la solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6 Swapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7 Adressage Mémoire : adresses virtuelles et physiques traduites par un IOMMU et un MMU 81
8 Principe de la pagination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
9 Mémoire virtuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
10 Principe de la pagination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
11 Processus de pagination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
12 Processus de pagination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
13 table d’allocation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
14 Les algorithmes de remplacement : Algorithme FIFO. . . . . . . . . . . . . . . . . . . . 86
15 L’anomalie de belady. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
16 L’algorithme optimal (OPT). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
17 Algorithme LRU (Least Recently Used). . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
18 Algorithme de l’horloge. Si la valeur de R=0 on tue la page et une nouvelle page est
insérée, sinon on met R=0 et on avance un tour. . . . . . . . . . . . . . . . . . . . . . . 90

1 SE : Modèle en couches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
2 Architecture Unix/Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3 Appels systèmes (User mode vs. Kernel mode) . . . . . . . . . . . . . . . . . . . . . . . 99
4 La commande strace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

xii
5 Traitement par lots (E/S tamponnées) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6 Organigramme des problèmes de démarrage du système d’exploitation . . . . . . . . . 102

1 Structure des i-node : Exemple : Unix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

2 Illustration de remplacement des pages du buffer. . . . . . . . . . . . . . . . . . . . . . 114

1 Attente active (Polling) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

1 Modèles multithreads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

2 Le graphe de précédence et le pseudo code . . . . . . . . . . . . . . . . . . . . . . . . . 131
3 Graphe de précédence qui correspond au code . . . . . . . . . . . . . . . . . . . . . . . 132

1 FCFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
2 RR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3 SJF non préemptif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4 Diagramme de Gantt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
5 Le calcule le temps d’attente et le temps de résidence. . . . . . . . . . . . . . . . . . . . 144
6 Diagramme de Gantt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

1 Algorithme FIFO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

2 L’algorithme FIFO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
3 L’algorithme optimal (OPT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
4 L’algorithme LRU (Least Recently Used . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
5 L’algorithme LRU (Least Recently Used . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6 Les états d’un processus UNIX. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
7 Le mécanisme de la Gestion de la mémoire virtuelle. . . . . . . . . . . . . . . . . . . . . 156

xiii
 Liste des tableaux

1 Caractéristiques et type du système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 La catégorie de groupe de mots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1 Fréquence d’accés aux Blocs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1 Caractéristiques des modes de communication . . . . . . . . . . . . . . . . . . . . . . . 40

1 Caractéristiques et type du système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

2 La catégorie de groupe de mots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

xiv
Première partie

Introduction

1
 Introduction générale

Préface

Ce cahier est un recueil d’exercices sous forme d’un guide destiné aux étudiants de L2 informatique. Il
regroupe, des questions, exercices et QCM proposés durant les travaux dirigés, les travaux pratiques et
les examens antérieurs pour permettre à l’étudiant de mieux comprendre les notions de bases pendant
ses cours du système d’exploitation. C’est aussi un support utile à nos étudiants en L2-Info pour bien
préparer leurs contrôles continus et examens du Semestre 2.
Faut-il Être connaisseur en système d’exploitation pour être un bon développeur des applications informatique.
? Pourquoi il faut avoir des cours du système d’exploitation ? , j’ai envie de se spécialiser seuelement en
programmation, à été les questions fréquentes de mes étudiants dans les séances de cours et de TD du
module Système d’Exploitation.
Il faut savoir que d’être un bon programmuer, exige de connaitre les concepts fondamentaux des systèmes
exploitations [11] : Processes and Process Management, Threads and Concurrency, Scheduling, Memory
Management, Inter-Process Communication, I/O Management, Virtualization, Distributed File Systems,
Distributed Shared Memory et Cloud Computing.
D’abord, définissons ce qu’est un système d’exploitation. J’ai pris la définition de Richard Stallman, le
« père » du projet GNU [18] et mouvement du logiciel libre (OpenSource) qui a définit un système
d’exploitation (OS) comme un ensemble de logiciels qui gère le matériel informatique et fournit des
services pour les programmes. Ce système masque la complexité matérielle, gère les ressources de calcul
et assure la synchronisation et coopération entre processus, la fiabilité, la protection et la sécurité [1] [3].
Vous devez le connaître le fonctionnement des systèmes d’exploitation en tant que développeur 1 comme :
(1) les abstractions (processus, thread, fichier, socket, mémoire), (2) les mécanismes (créer, planifier,
ouvrir, écrire, allouer) et (3) les politiques du Job (LRU, LFU ) etc. Un développeur doit savoir plus que
les fondamentaux pour avoir une bonne exécution de leur programme et même à sa structure et à son
flux 2 . Lorsque vous écrivez un programme et qu’il s’exécute trop lentement, mais que vous ne voyez
rien de mal avec votre code, où allez-vous chercher une solution ? Comment pourrez-vous déboguer
le problème si vous ne savez pas comment fonctionne le système d’exploitation ? Accédez-vous à trop
de fichiers ? Manque de mémoire et d’échange est très utilisé ? Mais vous ne savez même pas ce qu’est
le swap ! Ou le blocage des E/S ?. Le coeur du cours comprend la programmation simultanée (threads
et synchronisation), la communication inter-processus et une introduction aux systèmes d’exploitation
1. http://www.cs.jhu.edu/~yairamir/cs418/os4/sld013.htm
2. http://en.wikipedia.org/wiki/Deadlock

3
Introduction générale

distribués.
Assurez-vous de lire la section récapitulative de chaque chapitre de mes cours 3 . Aprés regardez également
les exercices à la fin de chaque chapitre.
NB : j’ai pris certains exercices à partir des sources suivantes [6, 9, 5]. Un nombre de ces questions de
révision sont tirées du manuel du Silbershatz Galvin, Operating System Concepts, Addison-Wesley [17].
——————————————————————–
Copyright 2019-2020 : Université Ibn Khaldoun de Tiaret (Algérie).
Tous les droits sont réservés.

3. http://moodle.univ-tiaret.dz/course/view.php?id=77

4
 Deuxième partie

La liste des exercices

5
Chapitre

1
Introduction aux Systèmes d’Exploitation

Sommaire
1.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Synthèse du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Relation entre matériel et logiciel . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Système d’exploitation : Principe . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Appels Système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.4 Evolution des systèmes d’exploitation . . . . . . . . . . . . . . . . . . . . 9
1.2.5 Classification des SE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 La liste des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.5 Exercice n°5 : Ex : Systèmes Multi-utilisateurs (« time-sharing ») . . . . 12
1.3.6 Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.7 Exercice n°7 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.8 Exercice n°8 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

"Voyez la plante, sa forme exprime les souvenirs vivants de toute l’évolution.".

- Rudolf Steiner (1861-1925)

1.1 Objectif

Le but de ces exercices est de mettre en évidence, l’influence de l’évolution historique des systèmes
d’exploitation sur quelques grandeurs caractéristiques de leurs performances.

7
Chapitre 1. Introduction aux Systèmes d’Exploitation

1.2 Synthèse du cours

1.2.1 Relation entre matériel et logiciel

Le matériel represente l’ensemble des composants physiques. Ce matériel (hardware en anglais) est com-
mandé par un programme (logiciel = software). Le "‘software"’ et le "‘hardware"’ sont complémentaires :
— Le "‘hardware"’ a besoin du « software » pour être piloté.
— Le "‘software"’ a besoin du hardware pour être exécuté.
Pour combler l’écart entre les constructions d’un langage et l’interface de la machine physique, il faut
donc non pas une, mais deux couches intermédiaires de logiciel. Le système d’exploitation, au contact
de la machine physique, transforme celle-ci en une machine idéale (virtuelle) fournissant à la couche
supérieure les services d’intendance jugés adéquats. C’est ce que résume la figure ci-dessous (voir
Figure 1).

Figure 1 – Relation entre matériel et logiciel

1.2.2 Système d’exploitation : Principe

En anglais "‘Operating System (OS)"’.

Qu’est-ce que c’est ? "‘Programme assurant la gestion de l’ordinateur et de ses périphériques "‘ [www.
dicofr.com].

A quoi ca sert ? – à simplifier la vie des utilisateurs et des programmeurs – à gérer les ressources de la
machine d’une manière efficace. Autrement dit, cacher la complexité des machines pour l’utilisateur
afin d’utiliser la machine sans savoir ce qui est derrière Abstraction du terme « Machine » selon Coy [8]
— Machine Réelle = Unité centrale + Périphériques (CPU, Mémoire, I/O)
— Machine Abstraite = Machine Réelle + Système d’exploitation
— Machine Utilisable = Machine Abstraite + Application

8
 1.2. Synthèse du cours

Figure 2 – Couches du système d’exploitation

1.2.3 Appels Système

Interfaces aux services offerts par le système d’exploitation, souvent écrits en C/C++. Ces services sont
généralement accessible a travers des bibliothèques de haut-niveau (API 4 ). Les API les plus utilisées :
Win32 API et Java API etc.
L’implémentation d’appels système peut se réalise a travees le passage de paramètres aux appels système
(c-à-d : passage de mode utilisateur vers le mode noyau) à travers de Registres, Blocks de mémoire ou des
Piles (Figure 3).

Figure 3 – Illustration : appels système

1.2.4 Evolution des systèmes d’exploitation

Un système d’exploitation s’évoluera au fil du temps pour des raisons : (i) Mise à niveau du matériel (p.ex.
évolution de support de stockage), (ii) Nouveau type de matériel (p.ex. nouveau dispositif de traitement
-> FPGA (field-programmable gate array) ) et (iii) Nouveau service (p.ex. la multiprogrammation).
— 1945 - 55 : tubes et interrupteurs ( ↑ Ni langage ni système d’exploitation (utilisant des relais
mécaniques )
— 1955 - 65 : transistors, cartes perforées
— Traitement par lots
4. API est un acronyme pour Applications Programming Interface, est un ensemble de définitions et de protocoles qui
facilite la création et l’intégration de logiciels d’applications

9
Chapitre 1. Introduction aux Systèmes d’Exploitation

— 1965 - 80 : circuits intégrés, disques Multiprogrammation, temps-partagé, entrées/sorties Unix,

version BSD, ATT, interface POSIX
— 1980 : ordinateurs personnels (PC) Interface graphique (concept crée vers 1960, Stanford) Réseaux
et systèmes distribués
La Figure 4 schématise quelques étapes marquantes des débuts des systèmes d’exploitation.

Figure 4 – Chronologie simplifiée des premiers systèmes

1.2.5 Classification des SE

— Traitement par lots : Batch Processing System ou système de traitements par lots. c’est le premier
véritable système d’exploitation. Ce système est un programme résident en mémoire centrale.
Les travaux successifs sont regroupés en un seul paquet de cartes inséré dans le lecteur de cartes
par l’opérateur.
— Systèmes Multi-tâche : c’est un système qui assure l’éxécution de plusieurs programmes/appli-
cations en même temps (c-à-d. plusieurs processus). Par conséquent, nous somme tombé dans une
situation concurrente, ou chaque processus a besoin du processeur. Dans cette situation, on parle
de concept de la Multi-programmation. Ce dernier signifier la présence simultanée en mémoire
principale de plusieurs programmes. Cette technique exige une politique dans l’affectation de
processeur (ou scheduler), c-à-d que le processeur pourrait changer d’affectation avant la fin d’un
travail pour satisfaire des contraintes de temps de réponse. La multiprogrammation nécessite
certains mécanismes comme : La protection de la mémoire, le système d’interruption, la gestion et
le partage des ressources,..etc.
— Systèmes Multi-utilisateurs : Permettre a différentes personnes de travailler avec un ordinateur
en même temps connexion par via le terminal de l’ordinateur lui-même à distance (telnet, ssh, ftp,
...) de telle sorte il donner l’impression à chaque utilisateur qu’il est seul. Ce système exige une
gestion des droits de fichiers (pour éviter la destruction des fichiers etc.) de processus. La technique
du Systèmes Multi-utilisateurs ( ou temps partagé) consiste à offrir à chaque utilisateur l’équivalent
d’une machine individuelle, tout en faisant bénéficier des services communs. Il est évident que la
présence de plusieurs utilisateurs dans le système implique aussi la multiprogrammation.
— Systèmes Multi-processeurs : Système avec plusieurs processeurs Parallèle (2 CPU en Mini-
mum), est un système Vrai multi-tâche qui doit assurer qu’il y a l’éxecution d’autant de processus
que processeurs en même temps. Contrairement au système avec un seul processeur qui assure

10
 1.3. La liste des exercices

une exécution en mode quasi-parallèle (pipeline 5 ). Ce mode d’exécution doit arrêter et reprendre
les différentes processus avec la gestion d’ordonnancement des processus "‘scheduler".
— Systèmes temps réel : Sert pour le pilotage et le contrôle des déroulements externes (p.ex.
centrale électrique, systèmes de pilotage des réacteurs nucléaires, systèmes de défense du territoire
). doit garantir des temps de réactions données pour des signaux extérieur urgents Les systèmes
temps réel souples ont des contraintes temporelles moins strictes et ils ne supportent pas le
scheduling d’échéances
— Systèmes distribués (répartie) : Un système reparti est un ensemble de processeurs ne parta-
geant pas de mémoire ou d’horloge. doit permettre l’éxecution d’un seul programme sur plusieurs
machines. Ce système permet de distribuer les processus et les remettre ensemble pour gros
calculs, p.ex. inversion de grandes matrices.
— Les années 80 ont vu le développement de deux technologies : (i) L’apparition des mi-
croprocesseurs et l’accroissement de leurs performances, qui permet de disposer d’une grande
puissance de calcul à des coûts de plus en plus faibles, et (ii) Le développement des techniques
de transmission de données (téléinformatique) et l’intégration progressive de la fonction de
communication dans les systèmes informatiques.

1.3 La liste des exercices

1.3.1 Exercice n°1 :

Les questions suivantes vous donneront une idée sur l’évolution des systèmes d’exploitation (operating
system). Testez vos connaissances en répondant aux questions de la théorie.

1. Qu’est-ce qu’un système d’exploitation ?

2. Qu’est-ce que le fonctionnement en mode double ? Comment le système bascule-t-il entre les
modes ?
3. Qu’est-ce qu’un kernel ?
4. Qu’est-ce qu’une machine virtuelle ?
5. La notion du système d’exploitation peut se présenter comme une coquille.
6. Quels sont les avantages de développer un système d’exploitation comme une série de couches ?
7. Qu’est-ce qu’un shell ?
8. Expliquer le mécanisme des appels systèmes à travers un exemple. Utiliser un petit schéma
illustratif.
9. Quel est l’intérêt des appels système, pourquoi ne pas utiliser des simples appels aux fonctions.
10. Comment peut-on être sûr qu’aucun programme ne peut contourner le mécanisme des appels
systèmes.
11. Comment peut-on améliorer le traitement par lot ?
5. un pipeline (ou chaîne de traitement), est l’élément d’un processeur dans lequel l’exécution des instructions est découpée
en plusieurs étapes.

11
Chapitre 1. Introduction aux Systèmes d’Exploitation

Figure 5 – Organigramme du processus démarrage d’un ordinateur (boot en anglais)

12. Quelle est la différence entre un système multi-programmé et un système multi-processeurs ?

13. Pourquoi peut-on parler de parallélisme quand il n’y a qu’une unité centrale (un seul processeur)
?
14. Que signifie système d’exploitation cloud computing (Cloud OS) ?

↪ voir correction (Section 1.1.1 [page 97]).

1.3.2 Exercice n°2 :

Décrire les fonctions principales de système d’exploitation (SE) :

— Fonction du SE : <Problèmes, Objectives, Contraintes, Solutions>
↪ voir correction (Section 1.1.2 [page 101]).

1.3.3 Exercice n°3 :

Le travail demandé dans cet exercice consiste à créer un organigramme de démarrage d’un PC pour
comprendre du processus de démarrage du système d’exploitaton.
↪ voir correction (Section 1.1.3 [page 101]).

1.3.4 Exercice n°4 :

Indiquer le type de système dans chaque situation dans le Tableau 1 :

Traitement par lots, Systèmes Multi-tâche, Systèmes Multi-utilisateurs (temps partagé), Systèmes Multi-
processeurs, Systèmes temps réel, Systèmes distribués (répartie).
↪ voir correction (Section 1.1.4 [page 101]).

1.3.5 Exercice n°5 : Ex : Systèmes Multi-utilisateurs (« time-sharing »)

Considérons un système en temps partage servant 100 utilisateurs ; admettons que le temps de réflexion
soit en moyenne 9 fois plus long que le temps d’attente. Celui-ci représente alors 10% du temps total, et

12
 1.3. La liste des exercices

Caractéristiques Type de système

Permettre l’exécution d’un seul programme sur plusieurs machines
Sont utilisés uniquement sur les grands ordinateurs (mainframe)
Exécution de plusieurs programmes en même temps
Les programmes sont exécutés en séquence et donc il ne peut pas
exécuter des programmes interactifs.
Gère le partage de la mémoire entre plusieurs CPU mais également
de distribuer la charge de travail
Dans les états d’attente du processus, un autre processus est exécuté.
Il permet à de nombreux utilisateurs d’utiliser le même ordinateur
en même temps.
Un seul processeur qui exécute plusieurs processus différents durant
une même seconde
Contraintes temporelles strictes / ne supportent pas le scheduling d’échéance
Exécution d’un seul programme sur plusieurs machines

Tableau 1 – Caractéristiques et type du système

Catégorie
Lunix, Windows, MAC OS, Solaris Système d’exploitation
Contient des instructions, Tâche, Aspect Dynamique d’un Programme
Thread, Programmation Concurrente, Paralléliser les Traitements
Accès Unifié, Fonctionnement Transparent, Gestionnaire d’Accès
Mode Protégé, Interfaces aux Services, Lien entre Mode Utilisateur
et Mode Noyau
Ordinateur à Programme non Enregistré, Séparation entre le Stockage
et le Processeur est Explicite, Programme en Mémoire
Gestion de Mémoire, Gestion de Processus, Gestion de Fichiers et es E/S

Tableau 2 – La catégorie de groupe de mots

il y a donc en moyenne 10 utilisateurs "‘ actifs "‘. En supposant que l’UC est allouée toutes les 50 ms
(qui est donc le quantum) et qu’une requête élémentaire exige un quantum au plus, calculer le temps de
réponse.
↪ voir correction (Section 1.1.5 [page 103]).

1.3.6 Exercice n°6 :

Chaque groupe de mots ci-dessous appartient à une catégorie. A vous de trouver la catégorie en essayant
d’être le plus précis que possible. La première ligne est un exemple (voir le Tableau 2).
↪ voir correction (Section 1.1.6 [page 103]).

13
Chapitre 1. Introduction aux Systèmes d’Exploitation

1.3.7 Exercice n°7 :

On considère un ordinateur dont les organes périphériques sont un lecteur de cartes (1000 cartes /
minutes) et une imprimante (1000 lignes / minutes). Un travail moyen est ainsi défini : lire 300 cartes,
utiliser le processeur pendant une minute, imprimer 500 lignes.
On suppose que tous les travaux soumis par les usagers ont des caractéristiques identiques à celles de ce
travail moyen. On définit deux mesures des performances du système :

1. le débit moyen D des travaux : nombre de travaux effectués en une heure.

2. le rendement r de l’unité centrale : fraction du temps total d’utilisation de l’unité centrale pendant
lequel elle exécute du travail utile (autre que la gestion des périphériques).

On suppose que les périphériques sont gérés par l’unité centrale. Calculer r et D dans les hypothèses de
fonctionnement suivantes :

1. Le système est exploité en porte ouverte ; la durée d’une session est limitée à 15 mn. On suppose
qu’un usager a besoin de 4 mn pour corriger son programme au vu des résultats, et faire une
nouvelle soumission.

2. Le système est exploité avec un moniteur d’enchaînement séquentiel des travaux.

↪ voir correction (Section 1.1.7 [page 103]).

1.3.8 Exercice n°8 :

Un lot est composé de 50 travaux, que pour simplifier, on suppose tous constitués de 3 phases :
Lecture des cartes (20 secondes), calcul (15 secondes), impression des résultats (5 secondes). Le temps
mis pour passer d’un travail à un autre est négligeable.
Calculer le temps de traitement total du lot et le taux d’utilisation de l’unité centrale pour le calcul dans
les deux cas suivants :

1. L’unité centrale gère les périphériques d’entrée-sortie.

2. Les périphériques sont autonomes et disposent d’un accès direct à la mémoire.

↪ voir correction (Section 1.1.8 [page 105]).

1.4 QCM

Cet exercice est un questionnaire à choix multiples (QCM). Pour chacune des questions suivantes, cocher
la bonne réponse.

14
 1.4. QCM

Question no 1 Dans les années 80, à quelle société Microsoft proposa t-il son système d’exploitation
PC-DOS qui allait ensuite devenir MS-DOS ?

 a. IBM
 b. Amiga
 c. Apple
Question no 2 Que signifie l’acronyme GNU ?

 a. GNU is Not Unique

 b. Grand Noyau UNIX
c. GNU is Not UNIX
 d. N’a aucune signification particulire

Question no 3 Quelles sont les deux grandes branches de système UNIX ? (Plusieurs réponses possibles)

 a. FreeBSD
 b. System V
 c. AIX
 d. Linux

Question no 4 Quel age a Linus Torvals lorsqu’il invente Linux ?

 a. 16 ans
 b. 21 ans
 c. 31 ans
 d. 48 ans

Question no 5 A quelle branche UNIX, le système macOS appartient-il ?

 a. System V
 b. Linux
 c. iOS
 d. BSD

Question no 6 De quel système est inspiré Linux ?

 a. MULTICS (Multiplexed Information and Computing Service)

 b. CTSS (Compatible Time Sharing System)
 c. Minix le système d’exploitation développé par Andrew S. Tanenbaum
 d. UNICS (UNiplexed Information and Computing System)

15
Chapitre 1. Introduction aux Systèmes d’Exploitation

Question no 7 Dans le fichier /etc/passwd, quel(s) shell(s) ne permet(tent) pas d’interpréter des com-
mandes ? (plusieurs réponses sont possibles)

 a. /bin/bash
 b. /bin/false
 c. /sbin/nologin
 d. /bin/zsh

Question no 8 Quelle commande permet de se connecter à un serveur Linux distant ?

 a. cp
 b. scp
 c. sftp
 d. ssh

Question no 9 Un système monotâche : ?

 a. N’utilise pas de système d’exploitation

 b. A pour seule tâche le système d’exploitation
 c. Contient en mémoire le système d’exploitation
 d. Contient en mémoire la tâche en cours d’exécution

Question no 10 Unix est un système : ?

 a. Multitâche
 b. À temps complet
 c. Multi-utilisateur
 d. À temps partagé

Question no 11 Que signifie préempter un processus, une tâche ?

 a. Suspendre son exécution au profit d’un autre processus / une autre tâche.
 b. Arrêter définitivement son exécution au profit d’un autre processus / une autre tâche.
 c. Geler le processus / la tâche pour un temps indéterminé (fini).
 d. Transférer le processus / la tâche en zone de swap

↪ voir correction (Section 1.2 [page 105]).

16
Chapitre

2
Système de Gestion des Fichiers (SGF)

Sommaire
2.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Synthèse du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Notion des Fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Organisations physiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 C’est quoi un SGF ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.4 Techniques d’allocation des blocs physiques . . . . . . . . . . . . . . . . 22
2.3 Les performances d’un SGF . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 La liste des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

"L’organisation induit l’efficacité qui elle-même impacte la qualité du temps personnel".

- Corinne Ghiridlian-hofmann (1960)

2.1 Objectif

Le but de ces exercices est de s’assurer que les étudiants ont bien appris la partie la plus visible d’un
système d’exploitation : le système de gestion de fichiers (SGF) est qui se charge de gérer le stockage et la
manipulation de fichiers (sur une unité de stockage : partition, disque, CD, disquette. Un SGF a pour
principal rôle de gérer les fichiers et d’offrir les primitives pour manipuler ces fichiers.

2.2 Synthèse du cours

2.2.1 Notion des Fichiers

Un fichier est une unité de stockage logique de l’information de différents types, en particulier : texte
,son, image et vidéos. Comme illustre la Figure 1, cette entité est une abstraction des propriétés physiques

19
Chapitre 2. Système de Gestion des Fichiers (SGF)

des dispositifs de stockage. Les fichiers sont utilisés pour représenter des données sur des dispositifs de
stockage (HDD, SSD, Disque USB, DVD/CD etc. ).

Figure 1 – Fichiers comme une abstraction des propriétés physiques des dispositifs de stockage

Cette abstraction facilite la vie des utilisateurs et des programmeurs. Par exemple, si vous êtes un
programmeur en langage C, la bibliothèque standard (stdio) des d’E/S gère des appels système liés aux
intructions d’entrées/sorties (par ex. fopen, fclose) (voir Figure 2).

Figure 2 – Bibliothèque standard d’E/S

2.2.2 Organisations physiques

D’un point de vue logique, le Système de Gestion des Fichiers (SGF) est vue comme une arborescence de
dossiers/ fichiers. La question qui se pose : Comment représenter ces fichiers sur un élément hardware ?
L’unité d’allocation sur le disque dur est le bloc physique. Un bloc physique est composé de 1 à n secteurs.
Par exemple : 1 bloc = 2 secteurs de 512 octets soit 1 kB.
Les opérations de lecture et d’écriture du SGF se font bloc par bloc.
Chargement d’un bloc b :
— si le bloc b est dans le cache, retourner son numéro de slot.
— sinon s’il y a un slot libre dans le cache, chargé le bloc du disque
— sinon choisir un slot à vider (l’écrire sur disque) et le remplacer par b par des stratégies de
remplacement comme LRU (Least Recently Used), FIFO First In First Out, etc (voir Figure 3).

20
 2.2. Synthèse du cours

Figure 3 – Organisations physiques des fichiers

Dans le cas des données structurées, chaque bloc peut contenir un ensemble d’enregistrements, le
Facteur de blockage représente le nombre enregistrement par bloc. L’identification d’un
enregistrment est basé sur la notion de tuple identfier (TID :[N° Bloc , Offset] ). La Figure 4 illustre
le stockage des données structurées dans le support de stockage. Cette technique est utilisée dans
les Système de Gestion de Base de Données (SGBD) [4].

Figure 4 – Stockage des données structurées

2.2.3 C’est quoi un SGF ?

Un Système de gestion de fichiers abrégé FS (File System) est une structure qui permet de stocker,
d’organiser des données sur un support : Disque magnétique (HDD) , SSD, RAM, USB, DVD,...
Un SGF fournit une métode d’organisation des fichiers et des repertoires d’un volume (Il découpe le
volume en blocs (clusters). Exemple des SGFs : SGF de MS Windows ( FAT file allocation table (table
d’allocation de fichiers), FAT16, FAT32, NTFS (new technology file system), SGF de Linux (EXT2 (second
extended file system), EXT3, Ext4), SGF de macOS (HFS (Hierarchical File System), HFS+).
Les tâches d’un SGF peut se résumer aux points suivants :
— Interface conviviale pour manipuler les fichiers.
— Le stockage des fichiers dans le disque dur.
— La gestion d’espace libres sur le disque dur.
— La gestions des fichiers dans un environnement muti-utilisateur.
— Les données d’utilitaire pour le diagnostic, la récupération en cas d’erreurs, l’organisation des
fichiers.
La Figure 5 illustre les composantes du SGF qui sont organisés sous forme des couches :
1. Méthode d’accès : représente modes d’accès aux fichiers : séquentiel, indexé, etc.

21
Chapitre 2. Système de Gestion des Fichiers (SGF)

2. E/S logique : realise un mapping entre les demandes E/S des utilisateurs avec un vocabulaire
physique ( inodes, files, directories, superblocks (partitions) etc.).

3. Superviseur E/S : assure l’échange entre buffer et le Disque.

4. Système de fichiers de base : son rôle est l’ordonnancement des E/S et l’ allocation du buffer.

5. Pilote de périphérique de disque : son rôle est est de communiquer directement avec le support
de stockage.

Figure 5 – Composantes du SGF

2.2.4 Techniques d’allocation des blocs physiques

On distingue différentes méthodes pour allouer un fichier physique :

— Allocation contiguë (séquentielle simple) ;
— Allocation par blocs chaînés ;
— Allocation indexée.

2.2.4.1 Allocation contiguë

Dans ce type d’allocation, les fichiers stockés par blocs contigus sur le disque. Par conséquent, le temps
de positionnement des têtes est minimal. L’entrée du répertoire permet d’associer au nom du fichier
(nom externe au SGF) les informations stockées en interne par le SGF. Comme illustré la Figure 6, l’entrée
de répertoire indique l’adresse du premier bloc et longueur (en nombre de blocs). Donc, l’accès direct
et séquentiel facile à implémenter, il suffit de mémoriser l’adresse du premier bloc. Cette technique
necessite la gestion de l’espace libre on utilisant des techniques comme la Fragmentation externe, BitMap,
Compactage etc. Cette approche est utilisée pour les supports en lecture seule (CD-ROM, DVD-R, etc.).

22
 2.2. Synthèse du cours

Figure 6 – Allocation contiguë

2.2.4.2 Allocation chainée

Elle consiste à allouer des blocs chainés pour représenter un fichier. Chaque bloc se termine par un
pointeur sur le bloc suivant et une entrée de répertoire contient un pointeur sur le premier bloc. Dans
cette situation, le fichier peut désormis être éparpillé sur le disque puisque chaque bloc permet de
retrouver le bloc suivant. Le principe de cette approche est illutré dans la Figure 7.

Figure 7 – Allocation chainée

Les avantages de l’allocation chainée est la gestion dynamique de l’espace, par conséquent, pas de limite
de taille et pas de fragmentation externe puisque tous les blocs peuvent être alloués. L’inconvénient
de cette approche réside dans l’accès au fichier est séquentiel : on commence le parcours à partir du
début du fichier même si on a récemment chargé les blocs , et la fiabilité, c-à-d que une perte de

23
Chapitre 2. Système de Gestion des Fichiers (SGF)

pointeur critique implique on se retrouve dans une autre zone mémoire → la solution est l’usage des
listes doublement chaînées, reproduction du nom de fichier et numéro de bloc dans chaque bloc etc.
Mais d’un autre côté, cette technique coûte très cher en terme de maintenance et de mise a jours des
sources d’information.

2.2.4.3 Index de blocs hiérarchisés

L’ i-node (Index NODE ou noeud d’index en Français) est un concept très ancien (année 50) qui a été
appliqué dans tous les SGF. Un i-node est une structure représentant : a) un processus, b) un espace
d’adressage, c) un fichier, d) une partition, e) un système de fichiers et f) un périphérique.
Le i-node represente un fichier en deux partie : les Métadonnées et le contenu. Les Métadonnées
represente les attributs de fichiers comme le type (le type du fichier, un entier dont la valeur est 0 pour
un fichier et 1 pour un répertoire, Le nombre de liens (voir après), UID (User Identification) : numéro
d’utilisateur du propriétaire, GID (Group Identification) : numéro du groupe propriétaire, Taille du
fichier en octets, Adresses des blocs de données (qui contiennent le fichier), Droits du fichier – Date du
dernier accès, date de la dernière modification, date de création. La Figure 8 illustre la strcture de i-node.

Figure 8 – Structure de i-node (Exemple : Unix)

2.3 Les performances d’un SGF

Les performances d’un système de gestion de fichiers dépendent du compromis entre l’algorithme
d’allocation et la fragmentation que l’on permet (optimisation physique / optimisation logique).
La fiabilité est le résultat direct d’une bonne consistance du système de gestion des fichiers. Il faut
vérifier de temps en temps. Sous UNIX/Linux, la commande fsck permet de :
— Verifier les blocs
— Verifier la consistances des fichiers
La journalisation est une forme d’optmisation qui consiste à retarder dans le temps les opérations,
longues, en modification du systeme de fichiers, car :
— Les disques durs sont trés lents.

24
 2.4. La liste des exercices

— Les mémoires vives (RAM) permettent de stocker beaucoup plus d’information, en quantité et en
temps.
— Les écritures, souvent en petite quantité, prennent énormement de temps en comparaison des
capacités de traitement des machines actuelles

2.4 La liste des exercices

2.4.1 Exercice n°1 :

Testez vos connaissances en répondant aux questions de la théorie.

1. Quel le role de module d’organisation des fichiers ? Quels services fournit-il ?

2. Énumérez les façons d’allouer du stockage. Donnez les avantages de chacun.
3. Qu’est-ce que l’allocation contiguë ?
4. Quelle est la principale difficulté avec l’allocation contiguë ?
5. Explique les méthodes d’allocation d’espace pour les fichiers contigus : best-fit et worst-fit methods
of allocating space for contiguous files.
6. Quel est fragmentation externe dans un système avec des fichiers contigus ?
7. Que veut dire linked allocation ?
8. Décrire le file-allocation table (FAT).
9. Que veut dire allocation indexée ?
10. Quel est le rôle du système de fichiers virtuel.
11. What information is needed for disk I/O ?
12. Qu’est-ce que la planification (scheduling) FCFS avec des disques ?
13. Quel est le problème avec la planification FCFS avec des disques ?
14. Qu’est-ce que la planification (scheduling) SSTF avec des disques ?
15. Quels sont les inconvénients de SSTF ?
16. Quelles sont les techniques d’allocation des blocs physique ? Avantages et Inconvenients ?
17. Rappelez la structure d’un inode UNIX ?
18. Quelle technologie augmente la fiabilité des unités de stockage ?
19. Discuter les avantages et les inconvénients des caches (Buffer) ?
20. Par quelles caractéristiques une clé USB se distingue t-elle d’un disque HDD ?
21. Quelles sont les techniques d’allocation des blocs physique ? Avantages et Inconvenients
22. Rappelez la structure d’un inode UNIX ?
23. Quelle technologie augmente la fiabilité des unités de stockage ?
24. Discuter les avantages et les inconvénients des caches (Buffer) ?
25. Le FAT16 est utilisé par MS-DOS. En FAT16, les numéros de blocs sont écrits sur 16 bits. Si on
suppose que la taille d’un bloc est 32Ko, Calculer la taille maximale adressable ?

25
Chapitre 2. Système de Gestion des Fichiers (SGF)

26. Que signifier Hadoop Distributed File System (HDFS) ?

27. Quel est le rôle NameNode et DataNode dans HDFS ?

↪ voir correction (Section 2.1.1 [page 109]).

2.4.2 Exercice n°2 :

On veut stocker un fichier F avec 6000 articles de taille de 1 KO par article.

1. Combien de bloc a-t-on besoin au minimum pour stocker tout le fichier si la taille de bloc est 32
KO. Supposons que les valeurs de l’attribut clé de fichier sont des entiers avec une distribution
uniforme.
2. Définissez une fonction d’hachage.
↪ voir correction (Section 2.1.2 [page 113]).

2.4.3 Exercice n°3 :

On considère un système de fichiers tel que l’information concernant les blocs de données de chaque
fichier est donc accessible à partir du i-noeud de celui-ci (comme dans UNIX). On supposera que :
— Le système de fichiers utilise des blocs de données de taille fixe 1K (1024 octets) ;
— L’i-noeud de chaque fichier (ou répertoire) contient 12 pointeurs directs sur des blocs de données,
1 pointeur indirect simple, 1 pointeur indirect double et 1 pointeur indirect triple.
— Chaque pointeur (numéro de bloc) est représenté sur 4 octets.

1. Quelle est la plus grande taille de fichier que ce système de fichiers peut supporter ?
2. On considère un fichier contenant 100,000 octets. Combien de blocs de données sont-ils nécessaires
(au total) pour représenter ce fichier sur disque ?

↪ voir correction (Section 2.1.3 [page 113]).

2.4.4 Exercice n°4 :

On considère un système disposant d’un système de fichiers similaire à celui d’UNIX avec une taille
de blocs de données de 4K (4096 octets) et des pointeurs (numéros de blocs) définies sur 4 octets. On
supposera que le i-noeud de chaque fichier compte 12 pointeurs directs, 1 pointeur indirect simple, 1
pointeur indirect double et 1 pointeur indirect triple. On désire créer un fichier contenant un total de
20.000.000 (vingt millions) de caractères (caractères de fin de ligne et de fin de fichier compris).
— Quelle est la fragmentation interne totale sur le disque résultant de la création de ce fichier.
↪ voir correction (Section 2.1.4 [page 113]).

2.4.5 Exercice n°5 :

Soit un fichier stocké dans le disque sous forme de 12 blocs nommés : 1, 2, ..., 12. Les demandes d’E/S
sont représentées comme suit :

26
 2.5. QCM

— D1= 1, 2, 5, 8, 3, 7, 9, 4, 10 ;
— D2= 1, 2, 5, 8 ;
— D3= 1, 2, 5, 8, 3, 7, 9, 4, 10 ;
— D4= 2, 5, 3, 6, 11, 4, 12 ;
— D5= 2, 5, 3, 6, 11.
On suppose que le buffer peut contenir 6 blocs.
a) On utilise une politique de remplacement FIFO (First-In, First-Out), calculer le nombre des E/S de ces
demandes dans l’ordre : D1→D2→D3→D4→D5. Le tableau suivant représente le nombre de références
et la fréquence de chaque bloc dans la charge de demande.

Blocs 1 2 3 4 5 6 7 8 9 10 11 12
Fréquence 3 5 5 3 5 2 2 3 2 2 2 1

Tableau 1 – Fréquence d’accés aux Blocs

b) Calculer le nombre des E/S de ces demandes dans l’ordre précédent, si on utilise l’algorithme LFU.
L’algorithme LFU (Least Frequently Used) se déroule comme suit :
— Remplacer le bloc qui a été référencé le moins souvent,
— pour chaque bloc de la chaîne de référence, nous devons conserver un nombre de références.
— Les références des blocs sont incrémentées à chaque fois qu’un bloc est référencé.
↪ voir correction (Section 2.1.5 [page 114]).

2.5 QCM

Cet exercice est un questionnaire à choix multiples (QCM). Pour chacune des questions suivantes, cocher
la bonne réponse.

Question no 1 Dans le fichier /etc/passwd, quel(s) shell(s) ne permet(tent) pas d’interprter des com-
mandes ? (plusieurs rponses sont possibles)

 a. /bin/bash
 b. /bin/false
 c. /sbin/nologin
 d. /bin/zsh

Question no 2 Pour modifier le comportement d’une commande on utilise :

 a. des fichiers
 b. des options
 c. des rpertoires
 d. des arguments

27
Chapitre 2. Système de Gestion des Fichiers (SGF)

Question no 3 On veut renommer pour notre session la commande kill -9 avec le nom stop_signal.
La commande effectuer est :

 a. rename kill -9 > stop_signal

 b. alias stop_signal=”kill -9”

 c. rename stop_signal=”kill -9”

 d. alias kill -9 > stop_signal

Question no 4 Que fait la commande who | wc -l ?

 a. Elle affiche la liste des utilisateurs connects

 b. Elle jette le r2sultat de la commande who
 c. Elle affiche le nombre des utilisateurs connects
 d. Elle 2choue

Question no 5 L’option -k de la commande man sert 0 :

 a. faire une recherche par mot-clé

 b. créer une nouvelle page du manuel
 c. effacer une page du manuel
 d. rechercher une page sur internet

Question no 6 Que fait la commande !! ?

 a. Affichage de l’avant dernière commande

 b. Exécute la dernière commande
 c. Efface l’historique
 d. Affiche l’historique des commandes

Question no 7 Chaque utilisateur UNIX possède un répertoire qui porte son nom de login. Comment
l’appelle t’on ? :

 a. perso

 b. home

 c. directory

 d. user

28
 2.5. QCM

Question no 8 Quelle commande permet de changer son mot de passe ?

 a. pass
 b. passwd
 c. password
 d. newpass

Question no 9 Que contient le dossier système /mnt sur un système UNIX :

 a. les fichiers de configuration du système

 b. les fichiers du noyaux UNIX
 c. les répertoires de périphériques amovibles
 d. les fichiers spécifiques aux périphériques

Question no 10 Quel alias permet de revenir dans le répertoire personnel et d’en lister le contenu ?

 a. alias go=’cd ; ls’ ;

 b. alias go=’cd . ; ls’ ;
 c. alias go=’cd . ; dir’ ;
 d. alias go=’cd / ; ps’ ;

Question no 11 Que fait la commande ls -F . ?

 a. Elle force l’affichage des fichiers et des répertoires du rpertoire de travail.

 b. Elle compte le nombre de fichiers contenu dans le rpertoire de travail.
 c. Elle affiche les objets contenu du rpertoire de travail en prcisant leur type.
 d. échoue.

Question no 12 Quelle commande permet de renommer le fichier oui en non ?

 a. rn oui non
 b. cp oui non
 c. mv oui non
 d. mp oui non

Question no 13 Les noms de fichier et de répertoire sont sensibles à la casse ?

 a. oui
 b. non
 c. cela dépend de la version du noyau UNIX
 d. non, mais il est possible d’utiliser des chiffres

29
Chapitre 2. Système de Gestion des Fichiers (SGF)

Question no 14 Que permet de faire la commande chgrp dupont essai ?

 a. Elle écrit dupont dans le fichier essai

 b. Elle remplace le nom du groupe du fichier essai par dupont
 c. Elle écrit essai dans le fichier dupont
 d. Elle lit le fichier essai en prenant le nom d’utilisateur dupont

Question no 15 Propriétaire du fichier essai.html, quelle commande dois-je utiliser pour pour retirer
les droits en exécution à tout le monde. ? (Plusieurs réponses possibles)

 a. chmod u+ressai.html

 b. chmod a+x essai.html

 c. chmod ugo-x essai.html

 d. chmod a-x essai.html

Question no 16 La notation octale 724 pour la gestion des droits d’accés correspond à la notation
symbolique :

 a. rwx -w- r-

 b. rwx r-x rw-

 c. rw- r-x r-x

 d. r- -w- rwx

Question no 17 Que represente 640 en termes de droits d’accs ?

 a. Les autres utilisateurs n’ont que les droits en lecture

 b. Les autres utilisateurs n’ont que les droits en écriture
 c. Les autres utilisateurs n’ont que les droits en exécution
 d. Les autres utilisateurs n’ont aucun droit

Question no 18 L’UID de l’utilisateur root est :

 a. 0
 b. 1
 c. true
 d. vrai
↪ voir correction (Section 2.2 [page 114]).

30
Chapitre

3
Gestion des périphériques : Interruption,
Attente Active, et DMA

Sommaire
3.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Synthèse du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 Les interruptions en informatique . . . . . . . . . . . . . . . . . . . . . . 34
3.2.2 Gestion des Entrées Sorties (E/S) . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3 Type d’interruptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.4 Déroulement d’une interruption . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.5 Attente Active (Polling) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.6 Accès Direct à la Mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3 La liste des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.6 Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.7 Exercice n°7 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

"Le bruit est la plus importante des formes d’interruption. C’est non seulement une interruption, mais aussi
une rupture de la pensée".
- rthur Schopenhauer

3.1 Objectif

est de comprendre comment le CPU (Central Processing Unit) communique avec les périphériques
d’entrée-sortie de la machine afin de traiter les interruptions (p.ex. quand l’utilisateur appuie sur une
touche du clavier ;. quand il clique avec la souris ).

33
Chapitre 3. Gestion des périphériques : Interruption, Attente Active, et DMA

3.2 Synthèse du cours

3.2.1 Les interruptions en informatique

Sur une machine, le processeur exécute les programmes chargés en mémoire (ou processus). Une autre
composante peut demander à l’interrompre pour faire temporairement autre chose. Par exemple :
— Périphérique : un paquet réseau arrive, mouvement de la souris
— Gestion d’erreur : erreur arithmétique, instruction invalide ,
— Ô⇒ Il faut donc introduire un mécanisme matériel qui indique au processeur d’arrêter le
traitement courant.
Ce mécanisme s’appelle une interruption

Définition 1 (Définition de l’interruption )

Une interruption (IT) est un mécanisme qui permet d’interrompre l’exécution d’un processus suite à un
événement extérieur ou intérieur et de passer le contrôle à une routine dite "‘routine d’interruption"’ ou
traitement d’interruption.

Un bon système doit réaliser les fonctions suivantes :

— Activer/désactiver le système d’interruption dans son ensemble.
— Masquer/démasquer individuellement une interruption.
— Une interruption masquée n’est pas ignorée, elle est mémorisée , elle n’est pris en compte que
lorsqu’elle est démasquée.
— Etablir une hiérarchie entre les sources d’interruption avec plusieurs niveaux de priorité, si
possible de façon dynamique
— Associer un programme spécifique à chaque interruption.

3.2.2 Gestion des Entrées Sorties (E/S)

On désigne par E/S tout transfert d’information depuis ou vers l’ensemble Processeur/Mémoire centrale.
On distingue le transfert d’information entre divers niveaux de la hiérarchie de la mémoire : registres,
mémoire centrale, disques magnétiques et transfert d’information depuis ou vers le monde extérieur :
périphériques, autres ordinateurs. Dans l’organisation des E/S, nous distinguons 3 types d’organes (voir
Figure 2) : (i) Les périphériques, (ii) Les contrôleurs CTRL (processeur primaire) et (iii) Les canaux (UE).
— Les périphériques : sont les organes qui assurent les opérations d’Entrées et de Sorties (en
abrégé E/S, ou I/O en anglais)
— Un contrôleur : (on dit parfois coupleur) est un dispositif adapté à chaque type de périphérique.
Il se connecte à plusieurs périphériques de même type (mais un seul périphérique peut transférer
à la fois). Il assure les fonctions logiques des E/S. Concrètement, un contrôleur est un processeur
primaire comprenant une petite mémoire (dite tampon ou buffer) et quelques registres spécialisés
— Un canal : Appelé parfois unité d’échange (Direct Memory Access DMA), c’est un processeur
spécialisé dans les opérations d’E/S. Il ne peut pas être lancé que par un processeur central. Il
peut interrompre l’UC. et son rôle est de commander les contrôleurs et les périphériques.

34
 3.2. Synthèse du cours

L’adresse d’un périphérique (memory-mapped I/O (MMIO)) comprend 3 parties : numéro du canal
relié à la mémoire centrale, numéro du contrôleur attaché au canal et numéro du périphérique
attaché au contrôleur.

Figure 1 – Gestion des Entrées Sorties (E/S)

3.2.3 Type d’interruptions

On distingue deux types d’interruption (IT) :

— Interruption Matérielle (IRQ) [Interrupt ReQuest] : déclenchées par un périphérique (lecteur,
clavier, . . . )
— Interruption Interruption Logicielle : permettent à un processus utilisateur de faire un appel au
système (appels au superviseur), dans ce cas l’utilisateur demande au système d’exploitation un
service, ces interruptions est appelées par une instruction à l’intérieur d’un programme (p.ex
overflow , erreur d’adressage, code opération inexistant, problème de parité, division par zéro...)
La commande strace intercepte et affiche les appels systèmes d’un programme dans les systèmes Linux.
Les systèmes Solaris et Mac OS X utilisent la commande dtrace.
Les systèmes Windows ne fournissent pas de telles fonctionnalités.

3.2.4 Déroulement d’une interruption

Nous commencons par definir les concepts clés dans ce processus de déroulement des interruptions.

3.2.4.1 Le vecteur d’interruption

Le Mot d’Etat du Processeur (Processor Status Word, PSW) est l’ensemble des données qui caractérisent
cet état à un instant donné. Il s’agit du contenu de ses registres. Ce dernier Il comporte généralement :
— Informations sur l’état du processeur : État d’exécution : Actif/Attente, Mode d’exécution :
Maître/Esclave, Masque (informations) sur les interruptions.
— Informations sur les données accessibles et les droits : Table des segments, Protection mé-
moire.
— Informations sur le déroulement de l’activité en cours : Compteur ordinal (CO).

35
Chapitre 3. Gestion des périphériques : Interruption, Attente Active, et DMA

Remarque : Le processeur a deux états : attente (Interruption externe) ou actif (éxecution d’une instruc-
tion).

3.2.4.2 Le vecteur d’interruption

Le vecteur d’interruption (VI) est une table qui contient les adresses des routines d’interruption. Les
interruptions sont numérotées et ces numéros (allant de 0 à 255 dans un PC) servent d’index pour
rechercher dans le vecteur d’interruption l’adresse de la routine à exécuter.

3.2.4.3 Etapes d’éxécution d’un programme

L’exécution d’un programme se déroule comme suit :

1. Un programme doit être chargé en Mémoire Centrale (MC).
2. Le processeur charge l’instruction à exécuter à partir de la mémoire dans un registre interne
appelé Registre Instruction (RI).
3. L’adresse de la prochaine instruction/l’instruction en cours à exécuter se trouve dans un registre
spécial appelé Compteur Ordinal (CO).
Si au moment de l’éxecution d’une instruction k, une interruption est arrive, le SE procède comme
illustré dans la Figure 2 :

Figure 2 – Mécanisme de rupture de séquence

3.2.5 Attente Active (Polling)

Une alternative au système des interruptions est le polling. Chaque élément est testé périodiquement
(CPU cycles) pour vérifier s’il demande un service particulier. L’attente active, ou polling est une
technique de programmation que les processus utilisent lorsqu’ils vérifient de façon répétée si une
condition est vraie, comme l’attente d’une entrée ou encore la libération d’un verrou.
Algorithme de scrutation
1. Lorsqu’un périphérique a une commande à exécuter par la CPU, celui-ci vérifie en permanence le bit
occupé de la CPU jusqu’à ce qu’il soit effacé (0).

36
 3.2. Synthèse du cours

2. Lorsque le bit occupé est effacé, le périphérique définit le bit d’écriture dans son registre de commande et
écrit un octet dans le registre de sortie de données.

3. Maintenant, l’appareil active (1) le bit de commande.

4. Lorsque la CPU vérifie le bit de commande prêt du périphérique et la trouve définie (1), elle définit (1) son
bit occupé.

5. La CPU lit ensuite le registre de commande du périphérique et exécute la commande du périphérique.

6. Après exécution de la commande, la CPU efface (0) le bit de commande prêt, le bit d’erreur du périphérique
pour indiquer l’exécution réussie de la commande du périphérique, puis efface (0) son bit occupé pour
indiquer également que la CPU est libre de s’exécuter. la commande d’un autre appareil.

3.2.6 Accès Direct à la Mémoire

Le processeur passe beaucoup de temps à effectuer des instructions de transfert de données. Il y a

beaucoup d’événements d’entrées/sorties nécessitent des transferts de blocs. Pour transférer de grands
blocs de données à grande vitesse, la délégation de la gestion de l’échange par l’Accès Direct à la Mémoire
(DMA :Direct Memory Access). La plupart des ordinateurs possèdent un processeur spécialisé qui gère le
dispositif d’accès à la mémoire.
Le DMA est connecté entre un contrôleur de périphérique et le bus système, permettant ainsi au
périphérique d’accéder à la mémoire sans passer par le CPU (comme illustre la Figure 3).

Figure 3 – Accès direct à la mémoire (Direct Memory Access)

Les étapes de l’échange à la base DMA est illustrée dans la Figure 4 : (1) Le processeur initialise les
registres du DMA en lui envoyant une adresse mémoire et le nombre d’octets à transférer, (2) Le DMA
transfert les données entre un disque et la mémoire, pendant ce temps, l’UC travaille autre tache. Le
DMA doit être le maître du bus, (3) Une fois le transfert terminé, il y a une génération d’une interruption.

37
Chapitre 3. Gestion des périphériques : Interruption, Attente Active, et DMA

Figure 4 – Délégation de la gestion de l’échange (Canaux, DMA).

3.3 La liste des exercices

3.3.1 Exercice n°1 :

1. Qu’est-ce qu’un vecteur d’interruption ?

2. Pourquoi les interruptions (IT) sont-elles parfois désactivées ?
3. Pourquoi certains systèmes prennent-ils en charge les priorités d’interruption ?
4. Quels types d’appareils devraient obtenir les priorités les plus élevées ?
5. Qu’est ce qu’un contrôleur de périphérique ?
6. Comment la CPU communique-t-elle avec un contrôleur d’E/S ?
7. Expliquez comment (et pourquoi) les tampons (buffers) sont utilisés pour les E/S disque.
8. Quelle est la différence entre IRQ et un vecteur d’IT ?
9. Quelles sont les différences entre un déroutement et une IT ?
10. Qu’est-ce qu’une memory-mapped I/O ?
11. Vous êtes responsable de l’écriture d’un pilote de périphérique pour un modem 56Kbps sur votre
PC. En supposant que vous décidez d’utiliser le polling pour la communication entre le SE et
le matériel du modem, expliquer les étapes de l’écriture d’un paquet de données du SE vers le
modem.
12. Décrivez brièvement comment se fait le transfert d’un bloc de disque vers la mémoire, si le
système dispose d’un DMA.
13. Laquelle des instructions suivantes doit être privilégiée ? a. Régler la valeur de l’horloge. b. Lire
l’horloge. c. Effacer la mémoire. d. Accéder au périphérique I/O. e. Désactiver les interruptions. f.
Modifier les entrées du tableau d’état du périphérique. g. Passer du mode utilisateur au mode
noyau.

38
 3.3. La liste des exercices

14. Expliquer pourquoi les interruptions ne sont pas appropriées pour implémenter des primitives de
synchronisation dans les systèmes multiprocesseurs.
15. Expliquez pourquoi les interruptions et la répartition du temps de latence doit être délimitée dans
un système dur en temps réel.

↪ voir correction (Section 3.1.1 [page 121]).

3.3.2 Exercice n°2 :

On considère un ordinateur qui lit ou écrit un mot mémoire de 4 octets en 10 ns. On suppose que lors
d’une IT, il faut recopier les 32 registres du processeur plus le compteur ordinal et le pointeur de pile du
processus. Si l’ordinateur ne traite que des instructions, quel nombre maximal d’ITs peut-il traiter en 1
ms ?
↪ voir correction (Section 3.1.2 [page 123]).

3.3.3 Exercice n°3 :

On suppose qu’une page de texte contient 50 lignes de 80 caractères chacune. On considère une
imprimante qui imprime 6 page/mn. Le temps d’écriture d’un caractère dans le registre de sortie de
l’imprimante étant très court, il est ignoré. Cette impression est gérée par des entrées/ sorties avec IT à
chaque caractère.

Quel est le pourcentage d’occupation du processeur par les ITs si chaque interruption prend 50 µs ?.
↪ voir correction (Section 3.1.3 [page 123]).

3.3.4 Exercice n°4 :

On considère une horloge qui s’exécute à 60 Hz (60 tops par seconde) et on suppose que le gestionnaire
d’IT de l’horloge requiert 2ms par top, y compris le temps de basculement de processus. Quelle est le
pourcentage d’utilisation du processeur réservé à l’horloge ?
↪ voir correction (Section 3.1.4 [page 124]).

3.3.5 Exercice n°5 :

Le temps d’accès d’une mémoire cache est de 120 ns et celle de la mémoire principale 900 ns. On estime
que 80% des demandes de mémoire représentent la lecture et restent 20% pour l’écriture. Le taux de
réussite pour l’accès en lecture est seulement 0,9. Une procédure d’écriture est utilisée.
1. Quel est le temps d’accès moyen du système considéré seulement des cycles réels de mémoire ?
2. Quel est le taux de réussite en tenant compte du cycle d’écriture ?
3. Quel est le temps d’accès moyen du système pour les requêtes de lecture et d’écriture.
↪ voir correction (Section 3.1.5 [page 124]).

39
Chapitre 3. Gestion des périphériques : Interruption, Attente Active, et DMA

3.3.6 Exercice n°6 :

Indiquer le type de communication dans chaque situation dans le Tableau 1 :

Attente
DMA IT
Active
Lorsque le CPU n’est pas complètement chargé,
laquelle des méthodes suivantes de transfert de données est préférée
Le processeur lit le registre d’état du dispositif et vérifie si un indicateur
(ou flag) "terminé" a été défini par le dispositif.
Notifier un processeur lorsqu’un périphérique d’E/S nécessite une attention.
Une plus grande efficacité lorsque le périphérique d’E/S génère beaucoup
de trafic
Le processeur n’a pas besoin de dépenser des cycles interrogeant le dispositif
Il est considéré comme efficace car il supprime le CPU d’être responsable
du transfert de données
Le processeur envoie la commande d’E/S au driver du disque.
Le driver détaille la commande et la traduit au contrôleur.
Il peut y avoir moins de latence entre le moment où le dispositif
est prêt et les données sont transférées.
Déplacer de grandes quantités de données entre les périphériques
d’E/S et la MC.
Peu efficace car "context switching" couteux

Tableau 1 – Caractéristiques des modes de communication

↪ voir correction (Section 3.1.6 [page 124]).

3.3.7 Exercice n°7 :

Sur un ordinateur à base de processeurs Intel x86, cinq périphériques sont reliés aux contrôleurs
d’interruption (PIC) de la manière suivante :
— Périphérique1 relié à l’IRQ1, Périphérique2 relié à l’IRQ3, Périphérique3 relié à l’IRQ8,
— Périphérique4 relié à l’IRQ9, Périphérique5 relié à l’IRQ12.
Ces cinq périphériques transmettent, simultanément, des demandes d’interruption aux contrôleurs
d’interruption.
— a) Donner l’ordre de traitement de ces demandes.
— b) Donner le nombre maximum de périphériques que l’on peut connecter sur une machine ayant
deux contrôleurs d’interruption. Justifier votre réponse.
— c) Donner les différents types d’interruptions des processeurs Intel 80x86.
Considérons la procédure de traitement d’une interruption du clavier suivante :
Procédure traiter_it_clavier
Sauvegarde du contexte ;

40
 3.4. QCM

« S : séquence de traitement de l’interruption du clavier » ;

Restauration du contexte ;
Retour au programme interrompu ;
Fin ;
— d) Compléter la procédure ci-dessus pour que l’on puisse exécuter la séquence « S » en mode
interruptible. Toute instruction (assembleur 80x86) rajoutée doit être Justifiée.

3.4 QCM

Cet exercice est un questionnaire à choix multiples (QCM). Pour chacune des questions suivantes, cocher
la bonne réponse.

Question no 1 Interruption Matérielle ?

 a. un paquet réseau arrive

 b. mouvement de la souris
 c. erreur arithmétique
 d. instruction invalide

Question no 2 Une interruption masquée ?

 a. elle est ignorée

 b. elle est mémorisée

Question no 3 Le maillon faible dans un système d’E/S ?

 a. Disque
 b. Mémoire RAM
 c. Cycle CPU

Question no 4 Parmi ces propositions, laquelle est une Interruption Logicielle ?

 a. overflow
 b. erreur d’adressage
 c. code opération inexistant
 d. problème de parité
 e. mouvement de la souris
 f. division par zéro

41
Chapitre 3. Gestion des périphériques : Interruption, Attente Active, et DMA

Question no 5 La commande strace intercepte et affiche les appels systèmes d’un programme ?

 a. overflow
 b. erreur d’adressage
 c. code opération inexistant
 d. problème de parité
 e. mouvement de la souris
 f. division par zéro

Question no 6 La commande qui intercepte et affiche les appels systèmes d’un programme ?

 a. strace
 b. tcpdump
 c. netstat
 d. swapon
 e. nicstat
 f. pidstat

Question no 7 Le mot d’état du processeur (Processor Status Word, PSW), il comporte généralement : ?

 a. État d’exécution : Actif/Attente

 b. Mode d’exécution : Maître/Esclave
 c. Table des segments
 d. Compteur ordinal
 e. Température CPU

↪ voir correction (Section 3.2 [page 125]).

42
Chapitre

4
Gestion des Processus (primitives fork/join)

Sommaire
4.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 Synthèse du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.1 Notion de Processus : Qu’est ce qu’un Processus ? . . . . . . . . . . . . . 46
4.2.2 Tables de Ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.3 Contexte d’un processus (Process Image) . . . . . . . . . . . . . . . . . . 47
4.2.4 Modes d’exécution des processus . . . . . . . . . . . . . . . . . . . . . . 47
4.2.5 Etats des processus : Cycle de vie d’un processus . . . . . . . . . . . . . 48
4.2.6 Implémentation des processus . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2.7 Opérations sur les processus . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.8 Destruction de processus . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.9 Processus suspendu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.10 Les thread et le parallélisme . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3 La liste des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3.6 Exercice n°6 : Diviser pour calculer plus vite . . . . . . . . . . . . . . . . 55
4.3.7 Exercice n°7 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3.8 Exercice n°8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

"Nothing is particularly hard if you divide it into small jobs".

- Henry Ford (1863-1947)

4.1 Objectif

L’approche fork/join a pour objet de traiter de très grandes quantités de données, dans de très nombreuses
tâches, tout en conservant le principe qu’une tâche doit effectuer un « petit » traitement. L’objectif de
ce TD est de transformé des graphes de dépendances sou forme d’un algorithme parallèle.

45
Chapitre 4. Gestion des Processus (primitives fork/join)

4.2 Synthèse du cours

4.2.1 Notion de Processus : Qu’est ce qu’un Processus ?

Le terme processus a été introduit dans les années 60 pour généraliser "‘job concept"’. Le processus
est une instance de programme binaire Différents processus peuvent exécuter différentes instances du
même programme. Au minimum, l’exécution du processus nécessite les ressources suivantes : Mémoire
pour contenir le code de programme et les données. Un ensemble de registres CPU pour supporter
l’exécution.
Remarque : Unité de base d’éxecution dans le système d’exploitation (thread).
La pile (ou Stack) est utilisé pour l’allocation de mémoire statique et le tas (ou Heap) pour l’allocation de
mémoire dynamique, les deux se trouvent dans la RAM de l’ordinateur (voir Figure 1).

Figure 1 – Programme vs Processus

Le système d’exploitation gère gère l’utilisation des resources de processus (processor cycles, main
memory, I/O devices).

4.2.2 Tables de Ressources

La table de ressource contient trois type d’information : Tables de mémoire, Tables d’E/S et Tables de
fichiers.
— Tables de mémoire :
Garder une trace de la mémoire physique et de la mémoire virtuelle par processus Allocation de
l’espace de permutation aux processus Attributs de protection
— Tables d’E/S :
État de l’opération d’E/S en cours Emplacement de mémoire utilisé comme source ou destination
de l’opération
— Tables de fichiers :
Les informations sur l’emplacement et les attributs des fichiers peuvent être gérées par le noyau
Toutes les tables de ressources du SE sont également sujettes à la gestion de la mémoire

46
 4.2. Synthèse du cours

La ? ? présente un exemple de trois processus P1, P2 et P3. Dans cet exemple, P1 utilise la rassource E/S
(I/O), le processeur (CPU) et la mémoire centrale. Donc, in peut dire que P1 est en cours d’éxecution. P2
est une processus en bloquées, il demande une ressource E/S (p.ex lire des données à partir de clavier).
Pn est une processus qui utlise seulement la ressource de la mémoire, donc Pn est élu à l’éxecution.

Figure 2 – Exemple d’utilisation des ressources : E/S, Mémoire et CPU

4.2.3 Contexte d’un processus (Process Image)

C’est l’ensemble des informations que les actions du processus peuvent consulter ou modifier (voir
la Figure 2). Ces informations sont : 1. Contexte du processeur (mot d’état et registres généraux) ; 2.
Contexte du mémoire : c’est l’espace de travail qui comprend : (Les segments procédures, Les segments
données, Les piles d’exécution) et 3. Ensembles d’attributs du processus : (Nom : nom interne désignant
le bloc de contrôle de processus ou PCB (de l’anglais process control block) du processus, qui sera discuté
plus tard, Priorité : en fonction du scheduling et Droits : opérations permises par le processus.

Figure 3 – Contexte d’un processus (Process Image)

47
Chapitre 4. Gestion des Processus (primitives fork/join)

4.2.4 Modes d’exécution des processus

Afin d’exécuter des programmes, il faut mettre à leur disposition les ressources nécessaires à leur
exécution : le processeur , l’espace mémoire et les données nécessaires. La relations entre processus
peuvent être selon trois type d’interaction sur les ressources (Figure 3) : (i) chaque processus dispose de
son propre espace mémoire, (ii) ne pas perturber les autres (sécurité) et (iii) différents flots d’exécution
partagent les même ressources des processus.
Cette intéraction engendre trois mode execution, comme illustre la Figure 5 : séquentiel, pseudo-
parallélisme et parallélisme réel (respectivement schéma 1, 2, 3 de la Figure 5).

Figure 4 – Relation entre les processus

Figure 5 – Modes d’exécution des processus

4.2.5 Etats des processus : Cycle de vie d’un processus

Les états standards se retrouvent dans la majorité des systèmes d’exploitation récents : "‘initialisation"’
est le tout premier état d’un processus. Il passe ensuite en "‘Prêt"’ ou "‘En attente"’ s’il doit être exécuté
ou non par le processeur. En fonction du nombre de processeurs équipés sur un ordinateur, de nombreux
processus peuvent être en attente (les processus prêts à être exécutés sont rangés dans une "‘file"’).
Lorsqu’ils sont en cours d’exécution, les processus sont considérés en "‘élu"’ ou "‘en exécution"’ et
"‘Endormi"’ ou "‘Bloqué "‘ si ce n’est pas le cas. Si le processus est terminé, il est simplement dit comme
étant "’Terminé"’ (voir Figure 5).

48
 4.2. Synthèse du cours

Figure 6 – Modes d’exécution des processus

4.2.6 Implémentation des processus

Le Process Control Block (PCB) est une structure de de données qui contient toutes les informations
nécessaires à la bonne exécution du processus. Les PCB sont stockés dans une table des processus (voir
la Figure 6).

Figure 7 – Le Process Control Block (PCB)

En bref, le PCB sert simplement de référentiel pour toute information pouvant varier d’un processus à
l’autre.
— État du processus : L’état peut être nouveau, prêt à fonctionner, en attente, arrêté, etc.
— Compteur de programme : Le compteur indique l’adresse de la prochaine instruction à exécuter
pour ce processus.
— Registres du processeur : Les registres varient en nombre et en type, selon l’architecture de
l’ordinateur. Ils comprennent des accumulateurs, des registres d’index, des pointeurs de pile et des
registres à usage général, ainsi que toutes les informations de code de condition. Avec le compteur
de programme, ces informations d’état doivent être sauvegardées lorsqu’une interruption se
produit, pour permettre au processus de se poursuivre correctement par la suite.
— Informations de planification du processeur : Ces informations incluent une priorité de
processus, des pointeurs vers des files d’attente de planification et tout autre paramètre de
planification.
— Informations sur la gestion de la mémoire : Ces informations peuvent inclure des informa-

49
Chapitre 4. Gestion des Processus (primitives fork/join)

tions telles que la valeur des registres de base et de limite, les tables de pages ou les tables de
segments, selon le système de mémoire utilisé par le système d’exploitation.
— Informations sur l’état des E/S : ses informations incluent la liste des périphériques d’E/S
alloués au processus, une liste des fichiers ouverts, etc.

Figure 8 – Example : PCB de MS Windows

4.2.7 Opérations sur les processus

Un processus est vu comme un objet par le système d’exploitation qui possède un identificateur unique
(PID). Les opérations qui peuvent s’appliquer les processus sont : Création, Destruction, Blocage, Réveil,
Activation, Désactivation et Suspension. Un noyau de système se compose de toutes ces opérations.

4.2.7.1 Création de processus

Cette opération consiste à : (1) Allouer un descripteur à un processus (PCB), (2) Affecter un identificateur
unique au processus (PID) et (3)Initialiser le descripteur (PCB) (programme à exécuter, pile d’exécution,
mémoire centrale utilisé par le programme et les données du processus, état du processus, priorité du
processus, autres ressources, etc.). La Figure 8 illustre une exemple de la commande ps (abréviation de «
process status ») affiche les processus machines en cours d’exécution.

Figure 9 – Exemple de la commande ps (process status)

50
 4.2. Synthèse du cours

4.2.8 Destruction de processus

La destruction d’un processus ne peut être effectuée que par le processus père ou un processus système.
Cette opération consiste à : Libérer les ressources occupées par le processus, Détruire ou non la descen-
dance du processus (Unix ne détruit pas les processus fils), Libérer son descripteur (PCB), qui pourra
être réutilisé et le PID est supprimé mais ne peut plus être réutilisé.
Les causes de la destruction de processus peuvent être : Arrêt volontaire, Erreur ou Erreur fatale.

4.2.9 Processus suspendu

Le processeur est plus rapide que I/O, alors tous les processus puissent attendre le périphérique d’E /S.
Échangez ces processus sur disque (Swap) pour libérer plus de mémoire et utiliser le processeur sur plus
de processus. L’état bloqué devient l’état de suspension quand il est échangé sur le disque.
Deux nouveaux états peuvent être considéré : Blocked/Suspend et Ready/Suspend. Les raisons est
suite à des evenement comme le Swapping (L’SE doit libérer de l’espace Pour exécuter le processus
(état prêt)) ou bien causes du système d’exploitation (Le système d’exploitation suspendue le processus
défectueux ou à cause d’un problème).

4.2.10 Les thread et le parallélisme

Un thread (appelée aussi processus léger ou activité) est un fil d’instructions (un chemin d’exécution) à
l’intérieur d’un processus. Un thread est donc une portion de code capable de s’exécuter en parallèle à
d’autres traitements. Les threads nessisite une commutation de contexte moins coûteuse. La commutation
de contexte ne nécessite pas un travail de gestion mémoire (on utilise le même espace d’adresses du
processus qui contient le thread).
Les mécanismes pour effectuer plusieurs tâches de façon concurrente, appelé fork et join. Plusieurs
librairies implémentent cette idée : (Intel Thread Building Blocks [19], Microsoft Task Parallel Library 6 ,
Java 7 ForkJoin [12]).
Nous pouvons maintenant poser des questions de nature plus algorithmique :

1. Comment utiliser ces mécanismes pour obtenir un gain de performance ?

2. Comment prédire le gain de performance que l’on peut espérer ?

Le principe du Framework Fork and Join consiste à décomposer une tâche en sous tâches, suivant le
paradigme diviser pour régner. Cette technique aussi utilisé par MapReduce 7 . Ce framework permet
d’obtenir un gain de performance et une contraintes de dépendances entre tâches (voir la Figure 9).

6. https://www.microsoftpressstore.com/articles/article.aspx?p=2224038&seqNum=7
7. MapReduce est un patron d’architecture de développement informatique, inventé par Google, dans lequel sont effectués
des calculs parallèles, et souvent distribués, de données potentiellement très volumineuses, typiquement supérieures en taille à
1 téraoctet.

51
 Chapitre 4. Gestion des Processus (primitives fork/join)

Figure 10 – Fork and Join Framework

Le code Liste 4.1 illuste le programme parallèle de la figure (a) présenté dans l’exercice de la section
4.2.3 du chapitre 4.
1

2 N1=2, n2=3 ;
3 S1 ;
4 Fork L1 ;
5 S2 ;
6 S5 ;
7 Fork L3 ;
8 S7 ;
9 Goto L4
10 L1 : fork L 2 ;
11 S3 ;
12 L3 : join n1 ;
13 S6 ;
14 Goto L4 ;
15 L2 : S4 ;
16 L4 : join n2 ;
17 S8 ;

Listing 4.1 – le programme parallèle FORK/JOIN (a)

Le framework Fork/Join a été introduit dans Java 1.7 pour implémenter facilement les algorithmes de
division et de conquête avec la prise en charge de processeurs multi-cœur. L’Algorithme 4.1 illustre le
principe de calcule de suite de fibonacci par un programme de Nested fork-join.

Algorithme 4.1 Fibonacci Recursive (Le programme de Nested fork-join)

function FIB(n)

si n < 2 alors
retourner n ;
a=fork FIB(n-1) ;
b=fork FIB(n-2) ;
join ;
retourner (a+b) ;

L’Algorithme 4.1 illustre le principe de calcule de suite de fibonacci par un programme de Nested fork-join.

52
 4.3. La liste des exercices

1 import static java.time.temporal.ChronoUnit.MILLIS ;

2

3 class Fibonacci extends RecursiveTask<Integer>{

4

5 int num ;
6 Fibonacci(int n){
7 num = n ;
8 }
9

10 @Override
11 protected Integer compute() {
12 if(num <= 1)
13 return num ;
14

15 Fibonacci fib1 = new Fibonacci(num-1) ;

16 fib1.fork() ;
17 Fibonacci fib2 = new Fibonacci(num-2) ;
18 fib2.fork() ;
19

20 return fib1.join()+ fib2.join() ;

21 }
22 }
23

24 public class ForkJoinFibonaaciEx {

25

26 public static void main(String[] arg){

27 LocalTime before = LocalTime.now() ;
28 int processors = Runtime.getRuntime().availableProcessors() ;
29 System.out.println("Available core : "+processors) ;
30 ForkJoinPool pool = new ForkJoinPool(processors) ;
31 System.out.println("Inside ForkJoin for number 50 : "+pool.invoke(new Fibonacci(50))) ;
32 LocalTime after = LocalTime.now() ;
33 System.out.println("Total time taken : "+MILLIS.between(before, after)) ;
34 }
35 }

Listing 4.2 – Programme JAVA montre l’usage des primitives fork() et pipe()

4.3 La liste des exercices

4.3.1 Exercice n°1 :

Testez vos connaissances en répondant aux questions de la théorie.

1. Qu’est-ce qu’un processus ? Quelle est la différence entre un processus et un programme ?
2. Qu’est-ce qu’un thread ?
3. En quoi un thread diffère-t-il d’un processus ?

53
Chapitre 4. Gestion des Processus (primitives fork/join)

4. Comment les threads peuvent-ils être utiles en Java ?

5. Décrivez les 3 modèles multithreads : plusieurs à un, un à un, plusieurs à plusieurs.

↪ voir correction (Section 4.1.5 [page 132]).

4.3.2 Exercice n°2 :

Complétez le schéma suivant (voir Figure 10) décrivant les transitions d’un processus, en commentant les
étiquettes 1, 2, 3, 4, 5, 6 et en précisant quels sont les événements qui provoquent chacune des transitions.

Figure 11 – Les transitions d’un processus

↪ voir correction (Section 4.1.2 [page 130]).

4.3.3 Exercice n°3 :

Donner le graphe de précédence et le pseudo code qui correspond à la formule suivante :

y = 2 ∗ ((a + b) ÷ (c − d ) + (e ∗ f )) + ((a + b) ∗ (c − d )) (1)

↪ voir correction (Section 4.1.3 [page 131]).

4.3.4 Exercice n°4 :

Donner le programme parallèle en utilisant les primitives (Fork/Join) pour les deux graphes des précé-
dences suivants ( voir Figure 11) :

54
 4.3. La liste des exercices

(a) (b)

Figure 12 – Graphes des précédences

↪ voir correction (Section 4.1.4 [page 131]).

4.3.5 Exercice n°5 :

Soit le pseudo-code suivant :

1 begin
2 parbegin
3 lire(a)
4 lire(b)
5 parend ;
6 parbegin
7 c :=a*a
8 begin
9 d :=a*b ;
10 e :=d*a ;
11 end
12 parend ;
13 e :=c+d+e
14 end.

↪ voir correction (Section 4.1.5 [page 132]).

4.3.6 Exercice n°6 : Diviser pour calculer plus vite

Programmer en langage C, à l’aide des fonctions C fork et pipe (ou bien Java 7 : fork/join ), le graphe de
parallélisation maximale G permettant de calcluer la suite de Fibonacci.

55
 Chapitre 4. Gestion des Processus (primitives fork/join)

Ce problème est à l’origine de la suite dont le nième terme correspond au nombre de paires de lapins au
nième mois. En notant Fn le nombre de couples de lapin au début du mois n et en posant F 1 = F 2 = 1,
Fibonacci déduit ainsi la relation de récurrence suivante :

F1 = 1
F2 = 1
...
Fn = Fn−2 + Fn−1

↪ voir correction (Section 4.1.6 [page 132]).

4.3.7 Exercice n°7 :

Donner le graphe de précédence qui correspond au code suivant :

1 x=2 ; y=2 ; z=2 ;
2 p1 ;
3 Fork L1 ; p2
4 Fork L2 ; p3
5 goto L3 ; P4
6 L1 : p2 ;
7 fork L3 ; p4 ;
8 goto L5
9 L3 : join (x)
10 P4 ;
11 L4 : join(y)
12 s6 ;
13 Quit() ;
14 L2 : P3 ;
15 L5 : join(y)
16 P5 ;
17 goto L4
18 L2 : P3 ;
19 L5 : join(y)
20 P5 ;
21 goto L4

1. Donner le graphe de précédence qui correspond au code au-dessus.

2. Indiquer les domaines de lecture et écriture des différentes tâches

4.3.8 Exercice n°8

On considère l’algorithme tri par fusion (Sort-Merge) pour expliquer les concepts du Fork/Join, qui est
un algorithme Divide and Conquer (diviser pour régner). Diviser pour régner est une technique qui
consiste à diviser un problème en son sous-ensemble de problèmes jusqu’à ce que nous atteignions la

56
 4.4. QCM

forme la plus simple de ce problème. Ensuite, le problème sera résolu récursivement en résolvant d’abord
les sous-problèmes. Par exemple, pour trier un tableau 38, 27, 43, 3, 9, 82, 10, nous le divisons d’abord
en deux morceaux 38, 27, 43, 3 et 9, 82, 10 ( Figure 12). Divisez-le ensuite pour obtenir quatre tableaux
avec deux éléments sur chacun d’eux. Continuez le même processus jusqu’à ce que vous obteniez des
tableaux avec des éléments uniques. Une fois que vous obtenez ces tableaux, commencez à fusionner en
comparant les éléments des tableaux adjacents.
Ecrire un programme avec le framework fork/join en Java pour un problème tri par fusion qui peut être
divisé en parties plus petites et résolu en parallèle.

Figure 13 – L’algorithme Merge Sort

↪ voir correction (Section 4.1.7 [page 134]).

4.4 QCM

Cet exercice est un questionnaire à choix multiples (QCM). Pour chacune des questions suivantes, cocher
la bonne réponse.

Question no 1 Que fait la commande !2 ?

 a. Elle tue le processus

 b. Elle rend la main à l’utilisateur dans 2 secondes
 c. Elle donne des informations sur le processus
 d. Elle répète la 2eme commande de l’historique

57
Chapitre 4. Gestion des Processus (primitives fork/join)

Question no 2 Quelle commande permet de passer en arrire-plan une commande dj lance ?

 a. bg

 b. fg

 c. &

 d. ap

Question no 3 On veut renommer pour notre session la commande kill -9 avec le nom stop_signal.
La commande effectuer est :

 a. rename kill -9 > stop_signal

 b. alias stop_signal=”kill -9”

 c. rename stop_signal=”kill -9”

 d. alias kill -9 > stop_signal

Question no 4 Que fait la commande !! ?

 a. Affichage de l’avant dernière commande

 b. Exécute la dernière commande
 c. Efface l’historique
 d. Affiche l’historique des commandes

Question no 5 Quelle est la commande permettant la visualisation dynamique des processus ?

 a. ps -dyn

 b. vs -p

 c. top

 d. ps -d

Question no 6 L’UID de l’utilisateur root est :

 a. 0
 b. 1
 c. true
 d. vrai

Question no 7 Quelle commande pemet de tuer le processus ayant pour identifiant le numro 5023 ?

 a. stop 5023

 b. ps -s 5023

 c. kill -9 5023

 d. stop -9 5023

58
 4.4. QCM

↪ voir correction (Section 4.2 [page 135]).

59
Chapitre

5
Ordonnancement des processus (scheduling de
l’UC)

Sommaire
5.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Synthèse du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2.1 Rappel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2.2 CPU Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2.3 Allocateur (dispatcher) vs Planificateur (scheduler) . . . . . . . . . . . . 62
5.2.4 Les critères de scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2.5 Scheduling Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.3 La liste des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.3.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.3.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3.6 Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3.7 Exercice n°7 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.4 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

"Spending time with God is the key to our strength and success in all areas of life. Be sure that you never try
to work God into your schedule, but always work your schedule around Him".
- Joyce Meyer

5.1 Objectif

Le but de ces exercices est d’examiné quelques algorithmes d’ordonnancement : premier arrivé, premier
servi (First Come, First Served), l’algorithme du travail le plus court d’abord (Shortest Job First), l’al-
gorithme avec priorité et l’algorithme du tourniquet (Round Robin) suivant des critères de scheduling
comme : Utilisation CPU, Débit (throughput), Temps de retournement (Restitution), Temps d’attente et
Temps de réponse (response time).

61
Chapitre 5. Ordonnancement des processus (scheduling de l’UC)

5.2 Synthèse du cours

En informatique, l’ordonnancement est la méthode par laquelle les threads, les processus ou les flux
de données ont accès aux ressources du système (par exemple, le temps du processeur (cycle CPU), la
bande passante des communications). Cela se fait habituellement pour atteindre une qualité de service
(QoS) cible.

5.2.1 Rappel

Dans un système uniprocessus, un seul processus est exécuté à la fois, d’autres processus doivent attendre
le temps de CPU L’exécution d’un processus consiste en des cycles d’utilisation CPU et d’attente sur
E/S (I/O). Comment continuer à exécuter des processus tout le temps ? pour une utilisation maximale
de l’UC Solution : Multi programmation La présence simultanée, en mémoire principale, de plusieurs
programmes. Affectation de processeur
La multiprogrammation nécessite le mécanisme d’ordonnancement.

Figure 1 – Cycles d’utilisation CPU et d’attente sur E/S (I/O).

5.2.2 CPU Scheduling

Le système d’exploitation gère une collection de processus. Si un système a plus de processus et un seul
CPU il faut diviser le temps CPU entre différents processus. C’est ce qu’on appelle CPU Scheduling.
Le scheduling de l’UC permet de décider quel processus dans la file d’attente des processus prêts
doit être alloué à l’UC.

5.2.3 Allocateur (dispatcher) vs Planificateur (scheduler)

Le Planificateur (scheduler) gère la file d’attente. Il analyse les demandes qui arrivent et les place dans
la file. L’Allocateur (dispatcher) suit l’activité du processeur, il choisit la requête à traiter et l’extrait

62
 5.2. Synthèse du cours

de la file. Il gère donc l’allocation du processeur. Il peut le réquisitionner en fonction de la priorité

des processus demandeurs et du temps déjà consommé par celui qui est en cours d’exécution (voir la
Figure 2.

Figure 2 – Gestion du processeur par le scheduler et le dispatcher

On peut classer l’ordonnancement en deux type : non préemptif et préemptif. Dans l’ordonnancement
non préemptif, un processus conservait le contrôle de l’UC jusqu’à ce qu’il se bloque ou qu’il se termine.
correspond parfaitement aux systèmes de traitements par lots. Dans l’ordonnancement préemptif,
l’ordonnanceur (dispatcher de ordonnancement) peut préempter (interrompre) un processus avant qu’il
se bloque ou se termine, afin d’attribuer l’UC à un autre processus.

5.2.4 Les critères de scheduling

— Utilisation CPU –Maintenir le CPU le plus utilisé possible.

— Débit –(throughput) C’est le nombre de processus qui terminent leur exécution par unité de temps
(1000 par heure, ou 10 par seconde ?).
— Temps de retournement (Restitution) –(turnaround time) Temps nécessaire pour exécuter un
processus (depuis la soumission jusqu’‘a la terminaison).
— Temps d’attente –(waiting time) Temps qu’un processus passe dans la file ready.
— Temps de réponse –(response time) Temps entre la soumission d’une requête et la première réponse
(et non la sortie finale).
On cherche à maximiser l’utilisation du CPU et le débit, et à minimiser les temps de retournement,
attente et réponse. On peut chercher à optimiser la moyenne ou bien le minimum/maximum
Question : Si n processus doivent être ordonnancés sur une unité centrale, combien d’ordonnancements
différents peut-on avoir ?, Donner une formule en fonction de n.

5.2.5 Scheduling Algorithms

Les algorithmes classiques proposés pour résoudre les problèmes d’ordonnancement sont :
— Premier arrivé, premier servi (First Come, First Served)
— Algorithme du travail le plus court d’abord (Shortest Job First)
— Algorithme avec priorité
— Algorithme du tourniquet (Round Robin)
— Algorithme temps restant le plus court (SRT : Shortest Remaining Time)

63
Chapitre 5. Ordonnancement des processus (scheduling de l’UC)

— Algorithme avec files multiniveaux

— Algorithme avec files multiniveaux avec recyclage (MFQ, Multilevel Feedback Queues)

5.2.5.1 Algorithme du premier arrivé, premier servi (First come, first served ou FCFS)

Soit l’ensemble de processus avec leurs temps du cycle en ms :

Figure 3 – l’ensemble de processus avec leurs temps du cycle en ms

Soit les temps d’attente et de restitution sont les suivants (Figure 4) :

Figure 4 – Calcule des métriques

Si les processus arrivent dans l’ordre p1, p2, p3, on obtient le diagramme de Gantt suivant :

Figure 5 – Diagramme de Gantt de l’algorithme FCFS

— Le temps d’attente moyen sera : Tma= (0+24+27)/3 = 17 ms

— Si l’ordre d’arrivée était p2,p3,p1, on aurait eu un temps moyen
— Tma= (0+3+6)/3 = 3 ms seulement !
— Ainsi, le temps moyen d’attente est variable dans la politique FCFS
Les avantages et les inconvénients de l’algorithme FCFS :
⊕ : Facile à comprendre
⊕ : Facile à programmer des files d’attente simples
⊕ : Le cas de bloquer ou d’ajouter de nouveau processus nécessite simplement de l’attacher à la queue
de la file d’attente
⊖ : Le temps d’attente moyen est souvent assez long
⊖ : Petit processus attend un grand processus
⊖ : Ne convient pas au partage du temps

64
 5.2. Synthèse du cours

5.2.5.2 Algorithme du travail le plus court d’abord (Shortest Job First ou SJF)

On associe à chaque processus la longueur de son prochain cycle d’UC. Quand l’UC est libre, on l’assigne
au processus qui possède le prochain cycle d’UC le plus petit. Si deux processus on la même longueur, le
scheduling FCFS est utilisé pour trancher.
Exemple : On considère l’ensemble suivant de processus arrivant au temps 0 avec les cycles suivants

Figure 6 – Processus avec leurs temps de cycle

Si les processus arrivent dans l’ordre p1, p2, p3, on obtient le diagramme de Gantt suivant :

Figure 7 – Diagramme de Gantt de l’algorithme SJF

— Le temps d’attente moyen est : Tma= (0+3+9+16)/4 = 7 ms

— Avec un algorithme FCFS, le temps d’attente : Tma= 10,25 ms.
Les avantages et les inconvénients de l’algorithme FCFS :
⊕ : On favorise les processus courts ce qui augmente le débit de processus traités et donc la réactivité.
⊖ : Risques de famine (un processus trop long pourrait ne jamais être exécuté s’il y a toujours un plus
court).

L’algorithme SJF offre un temps d’attente minimal pour un ensemble de processus donné.

5.2.5.3 Algorithme avec priorité

L’algorithme SJF est un cas particulier d’une famille d’algorithme avec des priorités. On associe à chaque
processus un priorité et l’UC est allouée au processus de plus haute priorité. Les processus ayant la
même priorité sont schedulés dans un ordre FCFS.
Un algorithme SJF est simplement un algorithme avec des priorités. Plus le cycle d’UC est grand, plus la
priorité est petite et vice-versa.
En général, les priorités s’étalent sur un nombre de numéros (de 0 à 7 ou de 0 à 4095). Les priorités
hautes ont des numéros bas, en général (comme c’est le cas dans le système UNIX). D’autres systèmes
utilisent les numéros bas pour les priorités basses.
Exemple :

65
Chapitre 5. Ordonnancement des processus (scheduling de l’UC)

Figure 8 – Exemple : Algorithme avec priorité

Le diagramme de Gantt est :

Figure 9 – Exemple : Le diagramme de Gantt : Algo. avec priorité

Le temps moyen d’attente est : Tma= 8,2 ms.

Les avantages et les inconvénients de l’algorithme priorité :
⊕ : Simplicité
⊕ : le temps augmente -> augmenter la priorité d’un processus
⊕ : Adapté aux applications avec des temps et des ressources variables
⊖ : Si le système se bloque finalement, tous les processus de faible priorité se perdent
⊖ : Blocage indéfini ou famine.

5.2.5.4 Algorithme du tourniquet (Round-Robin ou RR)

Il a été conçu pour les systèmes en temps partagé. Il ressemble à l’algorithme FCFS mais on peut
réquisitionner pour commuter entre les processus. On définit une unité de temps, le quantum (entre 10 et
100 ms). La file d’attente des processus prêts est traitée comme un file circulaire. Le scheduleur parcourt
la file d’attente en allouant l’UC à chaque processus pendant un intervalle de temps allant jusqu’à un
quantum (ou tranche de temps). La file d’attente est gérée comme une file FIFO. Le scheduleur de l’UC
sort le premier processus de la file, configure une horloge pour qu’elle interrompe après 1 quantum et
expédie le processus.
Exemple :

Figure 10 – Exemple : Algorithme avec Algorithme du tourniquet (Round-Robin ou RR)

Si le quantum = 4 ms, alors le premier processus obtient les 4 premières ms. Puisqu’il demande 20 ms
supplémentaires, il est interrompu après la première tranche de temps et l’UC est allouée au processus
p2. puisque p2 n’a pas besoin de 4 ms, il part avant l’expiration du quantum. L’UC est ensuite allouée à

66
 5.2. Synthèse du cours

p3. une fois que chaque processus a reçu 1 tranche de temps, l’UC est renvoyée au processus p1. On
obtient le diagramme de Gantt suivant :

Figure 11 – Diagramme de Gantt de l’algorithme RR

Les temps d’attente et de restitution sont résumés dans le tableau suivant :

Figure 12 – Les temps d’attente et de restitution

— Le temps moyen d’attente est : Tma = 17/3=5,66 ms.

— Ici le temps d’arrivée est égal à 0. Si cela n’était pas le cas, il faut le prévoir dans les soustractions
dans le tableau précédent.
— L’algorithme RR n’alloue pas l’UC à un processus plus d’une tranche de temps. Il effectue donc une
réquisition lorsque le cycle d’UC dépasse le quantum (le processus revient dans la file d’attente
des processus prêts)
Les avantages et les inconvénients de l’algorithme RR : :
⊕ : Simple et facile à implémenter.
⊕ : Chaque processus a la même chance d’exécution
⊕ : Gestion de tous les processus sans priorité
⊕ : Sans famine
⊖ : Dépend de la longueur de la tranche de temps. ⊖ : même FCFS, si la tranche de temps est infiniment
grande la fréquente commutation de contexte.

5.2.5.5 Algorithme SRT : temps restant le plus court (Shortest Remaining Time)

Une version préemptive de l’algorithme SJF s’appelle algorithme SRT (Shortest Remaining Time, temps
restant le plus court) : chaque fois qu’un nouveau processus est introduit dans la file de processus à
scheduler, le scheduleur compare la valeur estimée de temps de traitement restant à celle du processus
en cours de scheduling. Si le temps de traitement du nouveau processus est inférieur, le processus en
cours de scheduling est préempté.
L’algorithme SRT favorise les processus courts.

67
Chapitre 5. Ordonnancement des processus (scheduling de l’UC)

Figure 13 – Diagramme de Gantt de SRT

Les temps d’attente et de restitution sont résumés dans le tableau suivant :

Figure 14 – Les temps d’attente et de restitution

Temps d’attente pour P1=11-2=9 ; P2=5-4=1 ; P3+4-4=0 ; P4=7-5=2

5.2.5.6 Algorithme avec files multiniveaux

On définit des classes de processus et on associe à chacune des classes une priorité et une stratégie
d’ordonnancement. Le processeur est alloué aux processus de la classe la plus prioritaire. On ne change
de file que si la file la plus prioritaire est vide. Un processus ne peut pas changer de classe.

Figure 15 – Algorithme avec files multiniveaux

Ce type de scheduling est intéressant dans le cas où les processus ne sont pas tous identiques et ont des
besoins en ressources différents (par exemple : les processus système, les processus utilisateurs, ...etc).

5.2.5.7 Algorithme avec files multiniveaux avec recyclage (MFQ, Multilevel Feedback
Queues)

Dans un scheduling multiniveau et feedback, un processus peut changer de file. Il est intéressant d’utiliser
le feedback dans le cas où on doit suivre le comportement des processus et décider si on doit changer le
niveau d’un processus soit à la baisse , soit à la hausse, en fonction de l’utilisation des ressources. Par
exemple, il est recommandé de "dégrader" un processus qui utilise trop longtemps le processeur pour
éviter qu’il pénalise le reste des processus. MM.png

68
 5.3. La liste des exercices

Figure 16 – Algorithme avec Algorithme avec files multiniveaux avec recyclage (MFQ, Multilevel
Feedback Queues)

Les éléments mentionnés ci-dessus sont les différentes CPU scheduling utilisées dans le présent.
Ces algorithmes sont hérités en fonction de l’exigence du processeur.

5.3 La liste des exercices

5.3.1 Exercice n°1 :

Testez vos connaissances en répondant aux questions de la théorie.

1. Quelle est la différence entre les I/O-bound jobs et CPU-bound jobs ?
2. Que veut dire la multiprogramming ?
3. Qu’est ce qu’un système temps partagé (time-sharing) ? Quels sont les principaux avantages de
système temps partagé ?
4. Comment le partage du temps est-il généralement mis en œuvre ?
5. C’est quoi PCB ?
6. C’est quoi le swapping ?
7. C’est quoi la commutatuon de contexte ( context switch) ? Que fait le noyau lors d’un changement
de contexte ?
8. Que se passe-t-il au cours de terminaison d’un processus ?
9. Qu’est-ce qu’un CPU burst ? Qu’est-ce qu’un I/O burst ?
10. Que signifie preemptive ? Non-Non-preemptive ?
11. Qu’est-ce que le dispatcher ? Qu’est ce que ça fait ?
12. Quels critères de performance pourraient être sélectionnés pour évaluer les algorithmes d’ordon-
nancement ?
13. C’est quoi le débit ( throughput) ?
14. C’est quoi FCFS ? Quels sont ses avantages / inconvénients ?
15. C’est quoi SJF ? Quels sont ses avantages / inconvénients ?

69
Chapitre 5. Ordonnancement des processus (scheduling de l’UC)

16. À quoi sert le time quantum ?

17. Comment le quantum doit-il être lié au temps du changement de contexte ?
18. Comment le quantum de temps doit-il être lié aux temps de CPU burst ?
19. C’est quoi : multilevel feedback queues ? Quelles sont les caractéristiques déterminantes ? Comment
ces files d’attente sont-elles utilisées sous Linux ?
↪ voir correction (Section 5.2.1 [page 139]).

5.3.2 Exercice n°2 :

Envisager l’ensemble suivant de processus, avec la durée du cycle d’UC donnée en millisecondes.

Processus Temps du Cycle Priorité

P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2

Tous les processus sont arrivés à l’instant 0 dans l’ordre du tableau.

1. dessiner les diagrammes de Gantt illustrant l’exécution de ces processus selon les algorithmes
FCFS, SJF, priorité (avec et sans préemption) et RR (quantum=1ms).
2. quel est le temps de restitution de chaque processus pour chaque algorithme ?
3. quel est le temps d’attente de chaque processus pour chaque algorithme ?
4. lequel des schedulings obtient -il le temps moyen d’attente minimal sur tous les processus ?
Pour plus d’information sur les trois algorithmes voir la référence [16].
↪ voir correction (Section 5.2.2 [page 142]).

5.3.3 Exercice n°3 :

Une commutation de contexte prend c unités et la durée moyenne de la phase de calcul d’un processus
est p unités de temps.
1. Calculer le taux d’utilisation du processeur en fonction de c, p et de la valeur q du quantum (p>q),
lorsque l’algorithme d’ordonnancement round-robin est utilisé.
2. Etudier en particulier les cas où q tend vers l’infini et q tend vers 0 (zéro).
↪ voir correction (Section 5.2.3 [page 143]).

5.3.4 Exercice n°4 :

Considérons un système d’exploitation ayant 2 classes de processus. Les processus de la classe1 sont
plus prioritaires que les processus de la classe2. Chaque classe de processus a son propre algorithme
d’ordonnancement du processeur.

70
 5.3. La liste des exercices

Figure 17 – Processus, avec la durée du cycle d’UC

Figure 18 – Processus, avec la durée du cycle d’UC

A tout instant un processus moins prioritaire peut être interrompu par un autre processus plus prioritaire
que lui. Le processus interrompu (processus qui était actif) est inséré en tête de sa file. A la fin d’une
opération d’entrée/sortie :
1. Le processus interrompu est inséré en tête de sa file.
2. Le processus concerné par l’opération d’entrée/sortie est inséré en tête de sa file.
3. L’ordonnanceur choisit le processus le plus prioritaire.
Une opération d’entrée/sortie dure en moyenne 10 ms. On dispose de 2 périphériques (F0 et F1) qui
peuvent être partagés par les différents processus. Sur un périphérique donné, les opérations d’entrées/-
sorties sont effectuées séquentiellement.

1. Calculer le temps d’attente et le temps de résidence de chacun des processus.

2. Calculer le taux d’utilisation du processeur dans l’intervalle de temps [t0, fin du dernier processus].

↪ voir correction (Section 5.2.4 [page 144]).

5.3.5 Exercice n°5 :

Tenez compte des informations suivantes ( Figure 19) et tracez le diagramme de synchronisation (Gantt)
pour le processeur et le serveur d’E/S à l’aide de l’algorithme FCFS pour la planification du processeur.
↪ voir correction (Section 5.2.5 [page 144]).

5.3.6 Exercice n°6 :

Considérez un système d’exploitation qui ordonnance les processus selon l’algorithme du tourniquet
(RR). La file des processus prêts contient des pointeurs vers les entrées de la table des processus (les
descripteurs des processus).

71
Chapitre 5. Ordonnancement des processus (scheduling de l’UC)

Figure 19 – Processus, avec la durée du cycle d’UC et du périphérique d’E/S.

Supposez que le système d’exploitation est composé de deux unités de contrôle (deux processeurs
CPU1 et CPU2) et d’une unité d’E/S. Chaque processeur exécute l’algorithme du tourniquet avec un
quantum de trois unités de temps (qt = 3). Tous les processus prêts sont dans une même file d’attente. La
commutation de contexte est supposée de durée nulle. Considérez trois processus A, B et C décrits dans
le tableau suivant :

Processus Instant d’arrivée Temps d’éxecution

A 0 4 unités de CPU, 2 unités d’E/S, 2 unités de CPU
B 2 3 unités de CPU, 4 unités d’E/S, 2 unités de CPU
C 3,5 5 unités de CPU

La première ligne signifie que le processus A arrive dans le système à l’instant 0, son exécution nécessite
dans l’ordre 4 unités de temps CPU, 2 unités de temps d’E/S et 2 unités de temps CPU. Au départ le
processus A est élu par le processeur CPU1. Si plusieurs événements surviennent en même temps, vous
supposerez les priorités suivantes :
— Le CPU1 a la priorité d’accès à la file des processus prêts par rapport au CPU2.
— A la fin d’un quantum, le processus non terminé en cours est suspendu uniquement si la file des
processus prêts n’est pas vide. Le traitement réalisé à la fin d’un quantum est plus prioritaire que
celui d’une fin d’E/S qui, à son tour, est plus prioritaire que l’arrivée de nouveaux processus dans
le système.
a) Donnez les diagrammes de Gantt montrant l’allocation des deux processeurs, de l’unité d’E/S et
l’évolution des états des files d’attente (celle des processus prêts et celle des processus en attente de
l’unité d’E/S).
b) Calculez le temps moyen de séjour.

5.3.7 Exercice n°7 :

Ecrire un algorithme (pseudocode) pour de l’ordonnancement Round Robin (RR). On supprose que le
quantum est fixée à 2 secondes pour chaque processus utilisateur avant le prochain processus utilisateur,
prenez le contrôle du CPU. La préemption (lorsque le processus change d’état) est ajoutée entre les
processus. Si un processus utilisateur dépasse le quantum qu’il est préempté et remis sur la file d’attente
Ready. Si la tranche de temps est trop grande - dégénère en FCFS (premier arrivé, premier servi) et peut
entraîner l’effet de convoi où un processus conserve le CPU jusqu’à il libère ; moins de changement de
contexte. Si la tranche de temps est trop petite - plus de changement de contexte pour / vers de nouveaux
processus
↪ voir correction (Section 5.2.6 [page 145]).

72
 5.4. QCM

5.4 QCM

Cet exercice est un questionnaire à choix multiples (QCM). Pour chacune des questions suivantes, cocher
la bonne réponse.

Question no 1 Quelle méthode correspond mode de traitement des éléments d’une file d’attente (calculs
d’un ordinateur, stocks) ?

 a. FOFI
 b. FIFE
 c. FIFO

Question no 2 Dans quel(s) état(s) peut se retrouver un processus juste après une préemption ?

 a. bloqué
 b. éligible
 c. élu

Question no 3 Dans quel(s) état(s) peut se retrouver un processus juste après une préemption ?

 a. bloqué
 b. éligible
 c. élu

Question no 4 Dans ordonnanceur Multilevel Feedback ?

 a. le quantum des files moins prioritaires peut être plus court

 b. le quantum des files moins prioritaires peut être plus long
 c. le quantum de toutes les files peut être identique
 d. le quantum peut varier entre des processus d’une même file

Question no 5 Dans un ordonnanceur Multilevel Feedback, dans quelle condition un processus vatil
descendre d’un niveau ?

 a. il consomme la totalité de son quantum

 b. il ne consomme pas la totalité de son quantum
 c. il y a trop de processus à son niveau
 d. il y a trop peu de processus au niveau inférieur

Question no 6 La multiprogrammation nécessite le mécanisme d’ordonnancement ?

 a. Vrai
 b. Faux

73
Chapitre 5. Ordonnancement des processus (scheduling de l’UC)

Question no 7 L’ordonnancement non préemptif ?

 a. un processus conservait le contrôle de l’UC jusqu’à ce qu’il se bloque ou qu’il se termine.

 b. correspond parfaitement aux systèmes de traitements par lots.
 c. L’ordonnanceur (dispatcher de ordonnancement) peut préempter (interrompre) un processus
avant qu’il se bloque ou se termine, afin d’attribuer l’UC à un autre processus

Question no 8 Algorithme du tourniquet (Round-Robin ou RR), Il a été conçu pour les systèmes en
temps partagé ?

 a. Vrai
 b. Faux

Question no 9 Un système d’exploitation « temps réel »... (une seule réponse) ?

 a. exécute ses appels systèmes de manière asynchrone

 b. garanti le temps de réponse des appels système
 c. permet de connaître à l’avance le temps de réponse des appels système
 d. minimise le temps de réponse des appels système

Question no 10 Un processus Zombie est un processus ?

 a. qui a perdu son père

 b. qui a terminé son exécution en erreur
 c. qui a terminé son exécution et qui attend la prise en compte de cette fin par son père

Question no 11 Quels sont les états de processus qui peuvent être en mémoire secondaire ?

 a. Élu
 b. Prêt
 c. Bloqué
 d. Terminer
 e. Nouveau
↪ voir correction (Section 5.3 [page 146]).

74
Chapitre

6
Pagination à la demande

Sommaire
6.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2 Synthèse du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.2.1 Execution des programmes informatique . . . . . . . . . . . . . . . . . . 78
6.2.2 La Gestion de Mémoire (Pourquoi ?) . . . . . . . . . . . . . . . . . . . . 79
6.2.3 Swapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.2.4 Adressage Mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2.5 Gestionnaire de la mémoire . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2.6 Comment implémenter la mémoire virtuelle ? . . . . . . . . . . . . . . . 81
6.2.7 Gestion de la mémoire virtuelle : La pagination à la demande . . . . . . . 83
6.2.8 Représentation des espaces virtuels des processus et de l’espace physique 84
6.2.9 Détection et traitement d’un défaut de page . . . . . . . . . . . . . . . . 85
6.2.10 Remplacement de pages . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.2.11 Les algorithmes de remplacement . . . . . . . . . . . . . . . . . . . . . . 85
6.3 La liste des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.3.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.3.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.3.6 Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.3.7 Exercice n°7 (Algorithme de l’horloge : liste circulaire) : . . . . . . . . . 89
6.4 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

"Il est difficile de remédier à notre propre tristesse parce que nous en sommes complices. Il est difficile de
remédier à celle des autres parce que nous en sommes captifs".
- Jean Baudrillard (1980-1985)

6.1 Objectif

Comprendre les mécanismes de gestion de la mémoire virtuelle de swapping, de la pagination et de la

segmentation.
Exécution d’un programme

77
Chapitre 6. Pagination à la demande

6.2 Synthèse du cours

6.2.1 Execution des programmes informatique

Dans une éxecution des programmes informatique, le cycle d’exécution d’une instruction typique se
déroule comme suit :

1. Extraction d’une instruction de la mémoire ;

2. L’instruction est décodée ;

3. Elle provoque, éventuellement, l’extraction d’opérandes de la mémoire ;

4. Une fois l’instruction exécutée sur les opérandes ;

5. Les résultats peuvent être réenregistrés en mémoire.

Figure 1 – Cycle d’exécution d’une instruction typique

Le Code Source ou le Programme est écrit dans un langage de programmation (par ex. C, C++, Java etc.).
La compilation de ce programe génère un Module Object, qui est des fichiers non exécutable. On charge
les les modules Objet et les Bibl. dans la mémoire centrale (MC). Aprés le chargement, le systèle assure
la fonction de l’allocation et l’adressage. Durant l’éxecution de programme, on peux faire appel ainsi
que les fichiers des bibliothèques dynamiques DLLs (Dynamic Link Library ). Le sortie de ce processus
est un fichier executable (voir la Figure 2).
Il existe plusieurs techniques de gestion de la mémoire. Selon l’architecture de la machine.

78
 6.2. Synthèse du cours

Figure 2 – Les différentes étapes de l’exécution d’un programme

6.2.2 La Gestion de Mémoire (Pourquoi ?)

La mémoire aujourd’hui et devient moins chère, mais les applications exigent plus et plus de mémoire. La
gestion de mémoire (Memory Management) est une module qui assure l’échange des blocs de données
de la mémoire secondaire vers la mémoire centrale (voir la Figure 3). Notez que les E/S de mémoire
sont lentes par rapport au CPU. Donc le système d’exploitation doit Maximiser l’efficacité de la CPU et
Minimiser le temps d’échange.

Figure 3 – Memory Management : échanger des blocs de données de MS->MC

6.2.2.1 Problèmes :

Les problème dans gestion de la mémoire revient aux :

— Le Problème de capacité de MC
— Cohabitation entre les processus
— Libérer pour avoir un espace adjacent ?
Le contrôle et le partage des informations entre les processus concerne les informations critiques. Dans
ce cas , le système d’exploitation doit empêcher une modification de certaines informations (voir la

79
Chapitre 6. Pagination à la demande

Figure 5).

Figure 4 – Contrôle et le partage des informations entre les processus

Exigence de gestion de la mémoire : Lagestion de la mémoire doit exiger cetaines mécanismes :

Réallocation, Protection, Contrôle de Partage, Organisation logique, et Organisation physique.
↑ La solution est le Principe de la solution c’est la Mémoire virtuelle.
La mémoire virtuelle est une technique autorisant l’exécution de processus pouvant ne pas être
complètement en mémoire. Avec cette technique, on pourra exécuter des programmes qui
peuvent être plus grands que la mémoire physique.

6.2.2.2 Principe de la solution

Idées Générales : un espace de mémoire virtuelle par processus, @ Virtuelles et @ Physiques, et l’échanges
transparents avec le disque.

Figure 5 – Principe de la solution

6.2.3 Swapping

Le swapping ou échange consiste à déplacer temporairement des processus entre la mémoire centrale et
la mémoire auxiliaire (disques). L’objectif visé étant soit de libérer de l’espace mémoire pour de nouveaux
processus, soit de réduire le taux de multiprogrammation.
Un espace swap (zone d’échange) est donc créé sur le disque. Unix : (/swap). Windows (pagefile.sys).

80
 6.2. Synthèse du cours

Figure 6 – Swapping

6.2.4 Adressage Mémoire

Une adresse générée par l’UC est dite adresse logique (relative). La conversion entre une adresse
virtuelle (logique) en une adresse réelle (physique) est réalisée par la MMU (Memory Management Unit),
ou unité de gestion mémoire. Notez que le MMU est un dispositif matériel.

Figure 7 – Adressage Mémoire : adresses virtuelles et physiques traduites par un IOMMU et un MMU

6.2.5 Gestionnaire de la mémoire

C’est un module système dont la fonction est de gérer la mémoire principale. Les principales fonctions
d’un gestionnaire de la mémoire sont les suivantes : Allouer / libérer l’espace de la mémoire principale,
Charger / décharger(sauvegarder) les programmes des processus, Protéger les programmes et les données
des processus, Partager des programmes et/ou des données entre plusieurs processus

6.2.6 Comment implémenter la mémoire virtuelle ?

La mémoire virtuelle est un terme utilisé pour décrire comment les systèmes d’exploitation gèrent la
RAM disponible :
La Gestion de Mémoire est assurée par deux techniques : 1) la Pagination et 2) la Segmentation.

6.2.6.1 La pagination de la mémoire ?

Principe de la pagination :
La pagination consiste à diviser l’espace d’adressage logique en unités ou blocs appelés pages. La
mémoire physique est également découpée en blocs ou unités de même taille que les pages, appelés
cases ou cadres de page (pages frames). Les pages, des processus (espaces virtuels), qui ne sont pas

81
Chapitre 6. Pagination à la demande

chargées dans des cases de mémoire physique sont stockées en mémoire secondaire (disque). La partie
du disque (mémoire secondaire) réservée à la pagination est découpée en blocs de même taille que les
pages (certains systèmes charge toutes les pages du programme en mémoire secondaire).
Frames = blocs physiques, Pages = blocs logiques.
La taille des Frames et des Pages est définie par le matériel (puissance de 2 pour faciliter les calculs)

Figure 8 – Principe de la pagination

Traduction des adresses virtuelles en adresses physiques : Il est à rappeler que la traduction d’une
adresse virtuelle en adresse physique est réalisée par un dispositif matériel appelé "unité de gestion
mémoire" (MMU). Dans un système à mémoire paginée l’adresse virtuelle est composée de : Un numéro
de page virtuelle (p bits de poids forts : gauche), Un déplacement à l’intérieur de la page (d bits de poids
faibles : droite).
Taille de la page = 2d ; Chaque adresse générée par l’UC (sur m bits) est structurée comme suit :

Figure 9 – Mémoire virtuelle

le Principe de la pagination consiste à établir la correspondance entre <page virtuelle> et <page physique>
(ou case) On utilise une table que l’on appelle table de pages. Contient le numéro de case (adresse
physique)

82
 6.2. Synthèse du cours

Figure 10 – Principe de la pagination

Processus de pagination : le système dispose d’une table de cadres de page qui indique l’état (libre ou
occupé) du cadre de page, occupé par quelle page, de quel processus.

Figure 11 – Processus de pagination

Protection de la mémoire paginée :

A chaque page sont associés des bits de protection qui font partie de table de pages. La protection peut
être : Page en lecture/écriture, Page en lecture seule, Page en lecture/exécution.
Exemple : IBM/370 : 4 bits/page
Le partage du code et des données (partage de pages) et la pagination permet de partager, entre plusieurs
processus, des pages de code ou de données.

6.2.7 Gestion de la mémoire virtuelle : La pagination à la demande

Dans cette section, nous présentons la stratégie de chargement c-à-d : quand le système charge-t-il les
pages en mémoire principale ?, et nous présentons aussi la stratégie de remplacement qui répond aux
questions suivantes : Comment le système choisit-il les pages qui doivent être retirées de la mémoire
principale, lorsque aucune case n’est plus disponible ? Pour le choix d’une page, on peut tenir compte
des informations sur l’utilisation passée des pages présentes en mémoire principale.

83
Chapitre 6. Pagination à la demande

6.2.8 Représentation des espaces virtuels des processus et de l’espace physique

L’espace virtuel d’un processus est défini par : la table de pages, la table auxiliaire ou secondaire et la
Mémoire secondaire ou zone de swap.

Figure 12 – Processus de pagination

Représentation de l’espace physique

L’espace physique est représenté à l’aide d’une table que l’on appelle table d’allocation. Cette table
a autant d’entrées que de cases dans la mémoire principale (en plus de cette table, on utilise une table
de bits : un bit par case ou une liste des cases libres). Lorsqu’une case est allouée à une page virtuelle
d’un processus donné ; on met, dans l’entrée correspondante de la table d’allocation, le numéro de cette
page et le numéro du processus auquel elle appartient ou l’adresse de l’entrée de la table auxiliaire qui
correspond à cette page

Figure 13 – table d’allocation.

Représentation des espaces virtuels des processus

L’espace virtuel d’un processus est défini par :
— la table de pages,
— la table auxiliaire ou secondaire
— et la Mémoire secondaire ou zone de swap.
a) La table de pages : Elle est utilisée directement par le mécanisme de traduction des adresses (MMU).
Une entrée de la table de pages contient des informations telles que : Numéro de case mémoire corres-
pondant à la page ; Bits de protection : page en lecture/écriture, en lecture, lecture/exécution ; les les

84
 6.2. Synthèse du cours

bits de protection peuvent être utilisés comme "‘Bit de validité "‘ : page utilisée ou pas par le processus
(un processus utilise une partie seulement de l’espace virtuel) ; "‘Bit de présence"’ : page chargée en
mémoire centrale ou non ; "‘Bit de Modification"’ : page modifiée ou non depuis le dernier chargement ;
"‘Bit de référence"’ : page référencée ou non.
Lorsqu’un défaut de pages se produit, le système doit charger la page correspondante depuis la mémoire
secondaire (disque) dans une case de la mémoire principale. Il doit donc disposer d’une table que l’on
appelle table auxiliaire qui décrit l’image disque de l’espace virtuel d’un processus. On peut ajouter une
adresse disque par entrée (page) de la table de pages.
b) La table auxiliaire ou secondaire : Elle contient autant d’entrées qu’il y a de pages dans l’espace
virtuel considéré. Chaque entrée de cette table donne l’adresse de la page en mémoire secondaire réservée
à la pagination (adresse disque). Cette table est également utilisée lorsque l’on doit recopier une case
contenant une page modifiée. A un instant donné, il y a autant de couples (table de pages, table auxiliaire)
que d’espaces virtuels définis. Un seul de ces espaces est accessible au processeur (U.C.) : l’espace du
processus actif.
c) Mémoire secondaire ou zone de swap ( ou disque de pagination) : Elle est découpée en blocs
de même taille que les pages et contenant l’image de l’espace virtuel (programmes, les données, piles)
des processus.

6.2.9 Détection et traitement d’un défaut de page

Ce processus se déroule comme suit :

1. Détection de défaut de page

— Un défaut de page est détecté lors de la traduction d’une adresse virtuelle en adresse réelle, en
accédant à la table de pages et en testant le bit de présence (test réalisé par le MMU) :
— Bit de présence = 1 : prendre le numéro de case contenu dans cette entrée.
— Bit de présence = 0 : la page n’est pas présente en mémoire centrale, donc déroutement pour
défaut de page.

2. Traitement des défauts de page.

6.2.10 Remplacement de pages

Quand il y a un défaut de page, on doit allouer une case pour charger la page référencée. S’il n’existe
pas de page, on choisit une parmi celles qui sont présentes en mémoire et on affecte sa case à la page
référencée. La page sélectionnée au moyen d’un algorithme de remplacement est appelée "page victime".

6.2.11 Les algorithmes de remplacement

Dans cette section, nous présentons les algorithmes de remplacement.

85
Chapitre 6. Pagination à la demande

6.2.11.1 Algorithme FIFO

C’est l’algorithme de remplacement le plus simple. Quand on veut remplacer une page, on choisit la
page la plus ancienne Implémentation Chaque fois que l’on charge une page en mémoire centrale, on
met (on enfile) le numéro de cette page dans une file gérée en FIFO (premier entré premier sorti).

Figure 14 – Les algorithmes de remplacement : Algorithme FIFO.

L’anomalie de belady : Considérons la chaîne de référence suivante : Ω : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

On peut constater sur la figure ci-après que le nombre de défauts de page f(Ω , 4) est supérieur à celui de
f(Ω ,3) : f(Ω ,4)=10 et f(Ω ,3)=9. C’est l’anomalie de Belady : le nombre de défauts de page croit quand le
nombre de cases augmente ( f(Ω ,4) > f(Ω ,3) ).

Figure 15 – L’anomalie de belady.

6.2.11.2 L’algorithme optimal (OPT)

Un algorithme de remplacement optimal minimise le taux de défauts de page. Cet algorithme choisit la
page qui ne sera plus utilisée ou la page qui sera utilisée le plus tard possible. Cet algorithme suppose
une connaissance de l’ensemble de la chaîne de références ; il est donc irréalisable en temps réel. Il
permet d’évaluer, par comparaison, les autres algorithmes.

Figure 16 – L’algorithme optimal (OPT).

86
 6.3. La liste des exercices

6.2.11.3 Algorithme LRU (Least Recently Used)

L’algorithme LRU (moins récemment utilisée) choisit la page qui n’a pas été utilisée depuis longtemps
(ou la page ayant fait l’objet d’une référence la plus tardive). Cette classe d’algorithme est appelée
algorithme à pile ou "‘stack algorithms"’.

Figure 17 – Algorithme LRU (Least Recently Used).

LRU choisit la page qui n’a pas été référencée depuis longtemps. OPT choisit la page qui ne sera
pas référencée pendant longtemps (qui sera référencée le plus tard possible).

En général, on utilise une pile. Une approche consiste à garder les numéros de pages référencées
dans une pile.
Implémentation de la pile. La pile est implémentée à l’aide d’une liste avec double chaînage. On
utilise deux pointeurs : Un pointeur « sommet » pour empiler et un pointeur « base » pour retirer
un élément de la base
Nous pouvons citer d’autre algorithmes de remplacement :
— L’algorithme de l’horloge
— LFU (ou NFU) : Least Frequently Used/moins fréquemment utilisée
— L’algorithme du vieillissement (Aging)
— Les algorithmes de remplacement Algorithme de seconde chance

6.3 La liste des exercices

6.3.1 Exercice n°1 :

Testez vos connaissances en répondant aux questions de la théorie.

1. Qu’est-ce que la mémoire virtuelle ?

2. Énumère les avantages de n’avoir qu’une partie d’un programme en mémoire.
3. Qu’est-ce que la pagination à la demande ?
4. Pourquoi y a-t-il un valid/invalid bit ? Où est-il conservé ?
5. Qu’est-ce qu’un défaut de page ?
6. Enumérer la liste des étapes à suivre pour traiter un défaut de page.
7. Qu’est-ce que le remplacement de page ?
8. Quels critères utiliser pour choisir un politique de remplacement de page ?

87
Chapitre 6. Pagination à la demande

9. Quelle est l’anomalie de Belady ?

10. Qu’est-ce que la fragmentation interne ?
11. Qu’est-ce que la fragmentation externe ?
12. Quelle est la différence entre une page et un frame ?
13. Que contient le tableau des pages ?
14. Qu’est-ce qu’un TLB ?
15. Qu’est-ce que la segmentation ?
16. Qu’est-ce que espace d’adressage logique ?
17. Qu’est-ce que espace d’adressage physique ?
18. La pagination et la segmentation peuvent-elles être combinées dans un seul système d’exploita-
tion ? Énumérez deux façons ?

↪ voir correction (Section 6.1.1 [page 151]).

6.3.2 Exercice n°2 :

Dans un système de pagination à la demande on dispose de 4 cases mémoire (pages réelles ou physiques)
initialement vides et on utilise le remplacement local. Parmi ces algorithmes de remplacement de pages :
FIFO, LRU (moins récemment utilisée), OPT (optimal) et Horloge ; quel est l’algorithme qui provoque
8 défauts de pages, après son exécution avec la chaîne de références mémoires suivante : 7, 0, 1, 2 , 0
, 3, 0, 4, 2, 3 , 0 , 3 ,2 , 1, 2, 0 , 1, 7 , 0, 1. Justifier votre réponse en donnant l’état de la mémoire après
l’exécution de cet algorithme.
↪ voir correction (Section 6.1.2 [page 153]).

6.3.3 Exercice n°3 :

Si on applique l’algorithme de remplacement de pages "‘Horloge"’ ; Quel est le nombre de défauts de

pages, après son exécution avec la chaîne de références mémoires suivante : 7, 0, 1, 2 , 0 , 3, 0, 4, 2, 3 , 0 ,
3 ,2 , 1, 2, 0 , 1, 7 , 0, 1
↪ voir correction (Section 6.1.3 [page 154]).

6.3.4 Exercice n°4 :

Un processus a un espace virtuel de 1024 mots. Ce processus référence les adresses virtuelles suivantes
de son espace virtuel : 901, 050, 127, 128, 129, 130, 150, 260, 261, 263, 060, 061, 062, 403, 404, 068, 524,
525, 526, 300, 301, 400, 404, 68, 450, 383, 255, 380, 127, 255, 1023, 120, 200.
1. Donner la chaîne de références, sachant que la taille de page est de 128 mots.
2. Le processus dispose de 384 mots en mémoire centrale. Calculer le nombre de défauts de pages,
pour la chaîne de références précédente, en utilisant l’algorithme de seconde chance. Les cases
mémoires sont initialement vides.

88
 6.3. La liste des exercices

6.3.5 Exercice n°5 :

Considérer le tableau à deux dimensions suivant : Var A : array[1..100, 1..100] of integer ; On dispose
d’une mémoire paginée, avec des tailles de page de 200 mots. Le programme (le code) manipulant la
matrice se trouve dans la page 0. Le tableau A est stocké en mémoire ligne par ligne. Un entier occupe un
mot. Pour 3 cases, combien de défauts de pages sont générés avec les boucles suivantes d’initialisation
du tableau, en utilisant l’algorithme de remplacement LRU et en supposant que le programme se trouve
dans la première case et les deux autres cases sont initialement vides. La page 0 ne peut pas être choisie
lors d’un remplacement de page.
Initialisation (a) Initialisation (b)
For j := 1 to 100 do For i := 1 to 100 do
For i := 1 to 100 do For j := 1 to 100 do
A[i,j] := 0 ; A[i,j] := 0 ;

↪ voir correction ( ? ? [page ? ?]).

6.3.6 Exercice n°6 :

Soit les deux figures suivantes :

— Expliquer le schéma en décrivant le mécanisme de ce système en commentant les étiquettes ( ? ?).
— Complétez le schéma suivant décrivant les principaux états d’un processus Unix et les différentes
transitions d’un état à un autre sous forme <Etati, Etat j> hom Transition (voir la Figure 18b).

(a) (b)

↪ voir correction ( ? ? [page ? ?]).

6.3.7 Exercice n°7 (Algorithme de l’horloge : liste circulaire) :

Peut être vue comme une queue circulaire où on avance sur les pages qui ont le bit à 1 (en le positionnant
à zéro) jusqu’à ce que l’on trouve une page avec le bit d’utilisation à zéro. Ceci est connu sous le nom de
l’algorithme de l’horloge. Dans cet algorithme , les pages en mémoire sont mémorisées dans une liste
circulaire en forme d’horloge (figure 1). Un indicateur pointe sur la page la plus ancienne. Lorsqu’un

89
Chapitre 6. Pagination à la demande

Figure 18 – Algorithme de l’horloge. Si la valeur de R=0 on tue la page et une nouvelle page est insérée,
sinon on met R=0 et on avance un tour.

défaut de page se produit, la page pointée par l’indicateur est examinée. Si le bit R de la page pointée par
l’indicateur est à 0, la page est retirée, la nouvelle page est insérée à sa place et l’indicateur avance d’une
position. Sinon, il est mis à 0 et l’indicateur avance d’une position. Cette opération est répétée jusqu’à
ce qu’une page ayant R égal à 0 soit trouvée. À noter que lorsqu’une page est ajoutée, on met son bit de
référence à 1 Cet algorithme est aussi appelé algorithme de la seconde chance. On remarquera qu’il a
pour effet de donner une seconde chance aux pages qui ont été référencées depuis la dernière exécution
de l’algorithme. Ce n’est que si toutes les pages ont été référencées que l’on revient à la première page
pour l’expulser.
La Figure 18 illustre l’Algorithme de l’horloge. Si la valeur de R=0 on tue la page et une nouvelle page
est insérée, sinon on met R=0 et on avance un tour.

6.4 QCM

Cet exercice est un questionnaire à choix multiples (QCM). Pour chacune des questions suivantes, cocher
la bonne réponse.

Question no 1 Que permet le concept de mémoire virtuelle ?

 a. de gérer une partie de l’espace disque (mémoire secondaire) comme s’il s’agissait de mémoire
principale.
 b. d’exécuter des tâches qui ne peuvent physiquement tenir complètement en mémoire principale.
 c. d’utiliser efficacement les caches mémoires L1 et L2.
 d. d’augmenter la vitesse de commutation lors de la préemption des tâches

Question no 2 Une adresse générée par l’UC est dite ?

 a. adresse logique (relative).

 b. adresse physique (relative).

90
 6.4. QCM

Question no 3 La conversion entre une adresse virtuelle (logique) en une adresse réelle (physique) est
réalisée par ?

 a. MMU (Memory Management Unit)

 b. CPU ( Central Processing Unit)

Question no 4 L’espace virtuel d’un processus est défini par : ?

 a. la table de pages.
 b. la table auxiliaire ou secondaire.
 c. la Mémoire secondaire ou zone de swap.

Question no 5 L’algorithme LRU choisit la page qui n’a pas été référencée depuis longtemp ?

 a. Vrai.
 b. Faux.

Question no 6 L’algorithme OPT choisit la page qui ne sera pas référencée pendant longtemps (qui
sera référencée le plus tard possible) ?

 a. Vrai.
 b. Faux.

Question no 7 L’implémentation de LRU à l’aide de : ?

 a. File.
 b. Pile.

Question no 8 Un espace swap (zone d’échange) est donc créé sur : ?

 a. le disque.
 b. la Mémoire principale.

↪ voir correction (Section 6.2 [page 155]).

91
 Troisième partie

Le corrigé des exercices

93
Chapitre

1
Correction : Introduction aux Systèmes
d’Exploitation

Sommaire
1.1 Le corrigé des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
1.1.1 Corrigé Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
1.1.2 Corrigé Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
1.1.3 Corrigé Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
1.1.4 Corrigé Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
1.1.5 Corrigé Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
1.1.6 Corrigé Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
1.1.7 Corrigé Exercice n°7 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
1.1.8 Corrigé Exercice n°8 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
1.2 Correction de QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

"Voyez la plante, sa forme exprime les souvenirs vivants de toute l’évolution.".

- Rudolf Steiner (1861-1925)

1.1 Le corrigé des exercices

1.1.1 Corrigé Exercice n°1 :

1. Qu’est-ce qu’un système d’exploitation ?

"‘Un système d’exploitation (SE) est un programme assurant la gestion de l’ordinateur et de ses périphé-
riques"’ 8 . Le SE à simplifier la vie des utilisateurs et des programmeurs – à gérer les ressources de la
machine d’une manière efficace.
2. Qu’est-ce que le fonctionnement en mode double ? Comment le système bascule-t-il entre
les modes ?
Un système d’exploitation fonctionne en deux Modes d’éxécutions : (1) Mode utilisateur et (2) Mode
noyau. Le système bascule par de passage de paramètres aux appels système à travers des Registres, des
blocs de mémoire et des piles.
3. Qu’est-ce qu’un kernel ?

8. www.dicofr.com

97
Chapitre 1. Correction : Introduction aux Systèmes d’Exploitation

Un noyau de système d’exploitation, ou simplement noyau, ou kernel en anglais, est une des parties
fondamentales de certains systèmes ”exploitation. Il gère les ressources de l’ordinateur et permet aux
différents composants matériels et logiciels de communiquer entre eux.
4. Qu’est-ce qu’une machine virtuelle ?
Un SE c’est l’Abstraction de la machine physique (Abstraction du terme « Machine » selon Coy 9 .
— Machine réelle = Unité centrale + périphériques (CPU, Mémoire, I/O)
— Machine abstraite = machine réelle + système d’exploitation
— Machine utilisable = machine abstraite + application
5. La notion du système d’exploitation peut se présenter comme une coquille ?
Le noyau du SE est un ensemble de modules : Gestion des processus, Gestion des fichiers, Gestion de la
mémoire et Gestion des périphériques (entrées/sorties). La figure Figure 1 illustre le SE sous forme par
un modèle en couches.

Figure 1 – SE : Modèle en couches

6. Qu’est-ce qu’un shell ?

Le "‘shell"’ (interpréteur de commandes) est l’interface entre l’utilisateur et le système d’exploitation
(voir Section 1.1.1). Le shell est ainsi chargé de faire l’intermédiaire entre le système d’exploitation et
l’utilisateur grâce aux lignes de commandes saisies par ce dernier. Son rôle consiste ainsi à lire la ligne de
commande, interpréter sa signification, exécuter la commande, puis retourner le résultat sur les sorties.
7. Expliquer le mécanisme des appels systèmes à travers un exemple. Utiliser un petit schéma
illustratif ?
Un appel système est un moyen de communiquer directement avec le noyau de la machine (voir Figure 3).
8. Quel est l’intérêt des appels système, pourquoi ne pas utiliser des simples appels aux fonc-
tions ?
Ceci permet de garantir :

9. http://www.fsg.rnu.tn/imgsite/cours/Syst%C3%A9meExploitation-Chap1.pdf)

98
 1.1. Le corrigé des exercices

Figure 2 – Architecture Unix/Linux

Figure 3 – Appels systèmes (User mode vs. Kernel mode)

— la sécurité des données car le noyau interdira à un utilisateur d’ouvrir les fichiers auxquels il n’a
pas accès.
— l’intégrité des données sur le disque. Un utilisateur ne peut pas par mégarde effacer un secteur
du disque ou modifier son contenu. Les appels système peuvent être vus comme les portes d’une
discothèque. Un gardien se trouve à l’intérieur de la maison et vérifie systématiquement les
laissez-passer avant d’ouvrir.
9. Comment peut-on être sûr qu’aucun programme ne peut contourner le mécanisme des
appels systèmes ?
La commande strace intercepte et affiche les appels systèmes d’un programme. Strace est un outil de
débogage sous Linux pour surveiller les appels système utilisés par un programme (voir Figure 4) .
10. Quels sont les avantages de développer un système d’exploitation comme une série de
couches ?

99
Chapitre 1. Correction : Introduction aux Systèmes d’Exploitation

Figure 4 – La commande strace

Figure 5 – Traitement par lots (E/S tamponnées)

Les avantages de développer un système d’exploitation comme une série de couche sont : (i) Il rend le
débogage plus facile et (ii) aide à obtenir la conception correcte pour une évolution future.
11. Comment peut-on améliorer le traitement par lot ?
En 1956, IBM a introduit le premier disque dur (HDD). L’arrivée sur le marché des unités de disques est
introduit dans Traitement par lots la notion des E/S tamponnées (voir figure Figure 5) qui consiste a
stocker dans le disque les programmes et leur résultats. Les jobs sont lus et stockés sur disque au fur et à
mesure de leur soumission aux opérateurs : C’est la notion de SPOOLING [20] (Simulatneous Peripheral
Operation On-Line). Le SPOOL consiste à créer des fichiers-disque qui correspondent aux jobs soumis et
qui sont utilisés par le moniteur au moment de l’exécution, à la place des supports d’informations lents.
12. Quelle est la différence entre un système multi-programmé et un système multi-
processeurs ?
Un système d’exploitation multi-programmé (ou multitâche) est capable d’exécuter plusieurs programmes

100
 1.1. Le corrigé des exercices

simultanément. Il existe deux types de fonctionnement multitâche : le multitâche préemptif et le

multitâche coopératif, le premier étant globalement le plus rationnel et le plus efficace. En multitâche
préemptif, un module du système d’exploitation se charge de partager de façon équilibrée le temps de
calcul entre les différents programmes actifs. Le multitâche partage le temps mais il agit seulement sur
un processeur (pseudo-parallélisme [2]) mais un système multi-processeurs possédant plusieurs cœurs
physiques fonctionnant simultanément (parallélisme réel).
13. Pourquoi peut-on parler de parallélisme quand il n’y a qu’une unité centrale (un seul
processeur) ?
La solution est la Multi programmation qui offre la capacité de la présence simultanée, en mémoire
principale, de plusieurs programmes. On se basant sur l’affectation de processeur. Notez que, le processeur
pourrait changer d’affectation avant la fin d’un travail pour satisfaire des contraintes du temps de réponse.
14. Que signifie système d’exploitation cloud computing (Cloud OS) ?
Un système d’exploitation cloud est un type de système d’exploitation conçu pour fonctionner dans
des environnements de cloud computing et de virtualisation. Un système d’exploitation cloud gère
le fonctionnement, l’exécution et les processus des machines virtuelles, des serveurs virtuels et de
l’infrastructure virtuelle.

1.1.2 Corrigé Exercice n°2 :

Les fonctions principales de système d’exploitation (SE) est présenté dans le tableau suivant :
P : Processus, IT : interruption, MC : Mémoire Centrale, FIFO : First In, First Out, RR : Round-robin,
SJF :Shortest Job First, DMA : Direct memory access, UC : L’unité centrale, CPU : Central Processing
Unit.

1.1.3 Corrigé Exercice n°3 :

Le démarrage, qui est l’abréviation de bootstrap, fait référence au processus de chargement d’une image
du système d’exploitation dans la mémoire de l’ordinateur et de démarrage du système d’exploitation.
Chaque PC a un programme BIOS (Basic Input Output System) stocké dans la ROM (Read Only Memory).
Après la mise sous tension ou après une réinitialisation, le processeur du PC commence à exécuter le
BIOS. Tout d’abord, le BIOS effectue un POST (Power-on Self Test) pour vérifier le bon fonctionnement
du matériel du système. Il recherche ensuite un périphérique à démarrer. La Figure 6 présente un
Organigramme des problèmes de démarrage du système d’exploitation.

1.1.4 Corrigé Exercice n°4 :

(Réponse : on trouve 0,5 seconde).

101
Chapitre 1. Correction : Introduction aux Systèmes d’Exploitation

Figure 6 – Organigramme des problèmes de démarrage du système d’exploitation

102
 1.1. Le corrigé des exercices

Fonction du SE Problèmes Objectives Contraintes Solutions

-Allocation
Stocker d’une manière contiguë ;
Comment implémenter
La gestion Manipulation des persistante - Allocation
la notion
des fichiers fichiers et des dossiers et éfficace chaînées ;
de fichier par le SE ?
dans le disque - Allocation
indexée
- IT
-Activer / désactiver IT - Priorités - Attente Active
La gestion des Communiquer le CPU
-Masquer / démasquer IT - Temporisation (Polling)
périphériques et les périphériques E/S
-Etablir une hiérarchie IT - Ignorer une IT - Direct Memory
Access (DMA)
Problème de capacité
Des processus
de MC, Cohabitation -Maximiser l’efficacité
pouvant
Gestion entre les P de la CPU - Pagination
ne pas être
de la Mémoire Contrôle/Partage -Minimiser le temps - Segmentation
complètement
des infor. d’échange
en mémoire.
entre les processus
La présence
simultanée FIFO
Comment continuer en MC de SJF
Ordonnancement Utilisation
à exécuter des processus plusieurs P. RR
des processus maximale de l’UC
tout le temps ? Affectation de CPU
Satisfaire des contraintes ..
de temps de réponse.

1.1.5 Corrigé Exercice n°5 :

Dans le tableau 1, nous indiquons le type de système dans chaque situation : Traitement par lots
(TL), Systèmes Multi-tâche (MT), Systèmes Multi-utilisateurs (temps partagé) (MU), Systèmes Multi-
processeurs (MP), Systèmes temps réel (TR), Systèmes distribués (répartie) (D).

1.1.6 Corrigé Exercice n°6 :

Chaque groupe de mots ci-dessous appartient à une catégorie. A vous de trouver la catégorie en essayant
d’être le plus précis que possible. La première ligne est un exemple (voir le Tableau ? ?).

1.1.7 Corrigé Exercice n°7 :

A.1 - Le système est exploité avec en porte ouverte (pour l’economie d’energie).
Il faut 0,3 mn et 0,5 mn pour lire 300 cartes et imprimer 500 lignes. Le temps pour un passage est :
0,3+1+0,5=1,8 mn.
Comme entre deux passages l’usager a besoin de 4mn pour corriger, le nombre de passage n satisfait :
1,8.n + 4.(n-1) ≤ 15 ⇒ n=3 d’où r=1*3/15=0,2 et D=3.4=12 job/S (r=traitement/temps_global)
On peux servir 3 utilisateurs dans 15m/ 3/ (15=1/4) [echelle c’est la munite]
A.2 - Le système est exploité avec un moniteur d’enchaînement séquentiel des travaux.

103
Chapitre 1. Correction : Introduction aux Systèmes d’Exploitation

Caractéristiques Type du système

Permettre l’exécution d’un seul programme sur plusieurs machines D
Sont utilisés uniquement sur les grands ordinateurs (mainframe) MU
Exécution de plusieurs programmes en même temps MT,MU,MP
Les programmes sont exécutés en séquence et donc il ne peut pas
TL
exécuter des programmes interactifs.
Gère le partage de la mémoire entre plusieurs CPU mais également
MU, MT
de distribuer la charge de travail
Dans les états d’attente du processus, un autre processus est exécuté. MU,MT
Il permet à de nombreux utilisateurs d’utiliser le même ordinateur
MU
en même temps.
Un seul processeur qui exécute plusieurs processus différents durant
MU,MT
une même seconde
Contraintes temporelles strictes / ne supportent pas le scheduling d’échéance TR
Exécution d’un seul programme sur plusieurs machines D

Tableau 1 – Caractéristiques et type du système

Catégorie
Lunix, Windows, MAC OS, Solaris Système d’exploitation
Contient des instructions, Tâche, Aspect Dynamique d’un Programme Processus
Thread, Programmation Concurrente, Paralléliser les Traitements Multi-Programmation
Accès Unifié, Fonctionnement Transparent, Gestionnaire d’Accès Middleware
Mode Protégé, Interfaces aux Services, Lien entre Mode Utilisateur
Appel au superviseur
et Mode Noyau
Ordinateur à Programme non Enregistré, Séparation entre le Stockage
Arch. de Von Neumann
et le Processeur est Explicite, Programme en Mémoire
Gestion de Fichiers, Gestion des E/S, Gestion de Mémoire, Gestion de Processus Fonctions du SE

Tableau 2 – La catégorie de groupe de mots

104
 1.2. Correction de QCM

Le temps de passage est le même sans attente entre deux passages ⇒ D = 60/1,8 = 33 et r = 33/60 = 0,55
Durée du traitement = 20+15+5 = 40 s. r = 15/40=0,375.
2°) Les périphériques sont autonomes et disposent d’un accès direct à la mémoire.
Durée du traitement = 20 (le temps le plus long puisque temps transfert en mémoire =0), r = 15/20 = 0,75.

1.1.8 Corrigé Exercice n°8 :

1- L’unité centrale gère les périphériques d’entrée-sortie (E/S).

Durée du traitement = 20+15+5=40s, r=15/40=0,375
2- Les périphériques sont autonomes et disposent d’un accès direct à la mémoire.
Durée du traitement = 20 (le temps le plus long puisque temps transfert en mémoire =0), r=15/20=0,75

1.2 Correction de QCM

Cet exercice est un questionnaire à choix multiples (QCM). Pour chacune des questions suivantes, cocher
la bonne réponse.

Question no 1 Dans les années 80, à quelle société Microsoft proposa t-il son système d’exploitation
PC-DOS qui allait ensuite devenir MS-DOS ?

 a. IBM
b. Amiga
 c. Apple
Question no 2 Que signifie l’acronyme GNU ?

 a. GNU is Not Unique

 b. Grand Noyau UNIX
c. GNU is Not UNIX
 d. N’a aucune signification particulire

Question no 3 Quelles sont les deux grandes branches de système UNIX ? (Plusieurs réponses possibles)

a. FreeBSD
b. System V
 c. AIX
 d. Linux

105
Chapitre 1. Correction : Introduction aux Systèmes d’Exploitation

Question no 4 Quel age a Linus Torvals lorsqu’il invente Linux ?

 a. 16 ans
b. 21 ans
 c. 31 ans
 d. 48 ans

Question no 5 A quelle branche UNIX, le système macOS appartient-il ?

 a. System V
 b. Linux
 c. iOS
d. BSD

Question no 6 De quel système est inspiré Linux ?

 a. MULTICS (Multiplexed Information and Computing Service)

 b. CTSS (Compatible Time Sharing System)
c. Minix le système d’exploitation développé par Andrew S. Tanenbaum
 d. UNICS (UNiplexed Information and Computing System)

Question no 7 Dans le fichier /etc/passwd, quel(s) shell(s) ne permet(tent) pas d’interpréter des com-
mandes ? (plusieurs réponses sont possibles)

 a. /bin/bash
b. /bin/false
c. /sbin/nologin
 d. /bin/zsh

Question no 8 Quelle commande permet de se connecter à un serveur Linux distant ?

 a. cp
 b. scp
 c. sftp
d. ssh

Question no 9 Un système monotâche : ?

 a. N’utilise pas de système d’exploitation

 b. A pour seule tâche le système d’exploitation
 c. Contient en mémoire le système d’exploitation
 d. Contient en mémoire la tâche en cours d’exécution

106
 1.2. Correction de QCM

Question no 10 Unix est un système : ?

 a. Multitâche
 b. À temps complet
 c. Multi-utilisateur
 d. À temps partagé

Question no 11 Que signifie préempter un processus, une tâche ?

 a. Suspendre son exécution au profit d’un autre processus / une autre tâche.
 b. Arrêter définitivement son exécution au profit d’un autre processus / une autre tâche.
 c. Geler le processus / la tâche pour un temps indéterminé (fini).
 d. Transférer le processus / la tâche en zone de swap

107
Chapitre

2
Correction : Système de gestion des fichiers
(SGF)

Sommaire
2.1 Le corrigé des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
2.1.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
2.1.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
2.1.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
2.1.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
2.1.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
2.2 Correction de QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

"L’organisation induit l’efficacité qui elle-même impacte la qualité du temps personnel".

- Corinne Ghiridlian-hofmann (1960)

2.1 Le corrigé des exercices

2.1.1 Exercice n°1 :

Testez vos connaissances en répondant aux questions de la théorie.

1 : Quel le role de module d’organisation des fichiers ? Quels services fournit-il ?
Le module d’organisation des fichier permet d’implémenter le type d’abstraction (un fichier) sur un
support de stockage.
Services fournit par ce module :
— Interface conviviale pour manipuler les fichiers
— Le stockage des fichiers dans le disque dur
— La gestion d’espace libres sur le disque dur
— La gestions des fichiers dans un environnement muti-utilisateur
— Les données d’utilitaire pour le diagnostic, la récupération en cas d’erreurs, l’organisation des
fichiers
2 : Énumérez les façons d’allouer du stockage.
— Allocation contiguë (séquentielle simple) ;
— Allocation par blocs chaînés ;
— Allocation indexée.

109
Chapitre 2. Correction : Système de gestion des fichiers (SGF)

3 : Qu’est-ce que l’allocation contiguë ?

Les fichiers sont stockés par des blocs contigus sur le disque. L’entrée d’un répertoire dans un système
qui applique l’allocation séquentielle a la structure suivante : l’adresse du premier bloc et longueur (en
nombre de blocs).
4 : Quelle est la principale difficulté avec l’allocation contiguë ?
Trop d’espace : fragmentation interne.
Pas assez d’espace : déplacement du fichier est coûteu et pas toujours possible.
5 : Expliquez les méthodes d’allocation d’espace pour les fichiers contigus : best-fit et worst-fit
methods of allocating space for contiguous files.
Best Fit : Le programme est mis dans le bloc de mémoire le plus petit dont la taille est suffisamment
grande pour l’espace requis.
Worse Fit : Le programme est mis dans le bloc de mémoire le plus grand.
6 : Quel est fragmentation externe dans un système avec des fichiers contigus ?
La fragmentation externe survient lorsque la mémoire libre est séparé en petits blocs et est entrecoupé
par la mémoire allouée.
7 : Que veut dire linked allocation ?
Un fichier est une chaîne non contiguë de blocs disque. Chaque bloc se termine par un pointeur sur le
bloc suivant.
8 : Décrire le file-allocation table (FAT).
Le FAT16 est utilisé par MS-DOS 10 (MicroSoft-Disk Operating System). En FAT16, les numéros de blocs
sont écrits sur 16 bits. Si on suppose que la taille d’un bloc est 32Ko, Calculer la taille maximale adressable
?
9 : Que veut dire une allocation indexée ?
Le inode (noeud index) est une structure de données dans un système de fichiers de type Unix qui
décrit un système de fichiers objet tel qu’un fichier ou un répertoire . Chaque inode les attributs et
l’ emplacement du bloc disque (s) des données de l’objet. Attributs de l’ objet du système de fichiers
peuvent inclure des métadonnées (temps de la dernière modification, l’ accès, de modification), ainsi que
le propriétaire et autorisation des données.
10 : Quel est le rôle du système de fichiers virtuel.
Le système de fichier virtuel (SFV) est la vue homogène de tous les SGF réels. Il est défini en interne en
terme de structures de représentations et d’opérations de manipulations de ces structures. Le système de
tampons mémoire qui contiennent les blocs disque (le cache). Le disque abstrait est une vue homogène
des tous les disques supportés par l’installation. Il définit un ensemble d’opérations d’accès disques
élémentaires indépendantes des périphériques physiques eux-mêmes .
11 : Quelles informations sont nécessaires pour les E/S disque ?

10. MS-DOS (abréviation de Microsoft Disk Operating System) est le système d’exploitation de type DOS développé par
Microsoft pour l’IBM PC d’abord, puis pour les compatibles PC. Il s’agit d’un système fonctionnant en mode réel, monotâche
et mono-utilisateur, et équipé par défaut d’une interface en ligne de commande

110
 2.1. Le corrigé des exercices

Longueur moyenne de file d’attente du disque , la latence et les vitesses lecture/écriture.

12 : Qu’est-ce que la planification (scheduling) FCFS avec des disques ?
FCFS (Premier arrivé, premier servi) est l’algorithme de planification de disque le plus simple. Cet
algorithme reçoit les requêtes dans l’ordre d’arrivée dans la file d’attente du disque.
13 : Quel est le problème avec la planification FCFS avec des disques ?
FCFS généralement, il ne fournit pas le service le plus rapide.
14 : Qu’est-ce que la planification (scheduling) SSTF avec des disques ?
SSTF (Shortest Seek Time First) est l’algorithme de planification qui sélectionne la requête la plus proche
de la position courante de la tête.
15 : Quels sont les inconvénients de SSTF ?
SSTF est une forme de scheduling pouvant causer la famine de certaines requêtes.
16. Quelles sont les techniques d’allocation des blocs physique ? Avantages et Inconvenients
?
Il exist trois différentes méthodes pour allouer un fichier physique : Allocation contiguë, Allocation par
blocs chaînés et Allocation indexée.
— Allocation contiguë (séquentielle simple) ;
— Avantages : Trop d’espace : Temps de positionnement des têtes est minimal, Accès direct et
séquentiel facile à implémenter : il suffit de mémoriser l’adresse du premier bloc.
— Inconvenients : fragmentation interne, pas assez d’espace : déplacement (coûteux) du fichier.
— Allocation par blocs chaînés ;
— Avantages : Pas de fragmentation externe puisque tous les blocs peuvent être alloués, Pas de
limite de taille.
— Inconvenients : Accès au fichier est séquentiel : On commence le parcours à partir du début
du fichier même si on a récemment chargé les blocs, problème de fiabilité : perte de pointeur
critique.
— Allocation indexée.
— Avantages : Extension des fichiers, les blocs de données ne contiennent pas les pointeurs,
accès direct facile.
— Inconvenients : Occupation de la mémoire centrale par la FAT [14], Problème des disques de
grande capacité.
17. Rappelez la structure d’un inode UNIX ?
La structure d’I-Node est utilisée par le système de gestion de fichier ext3fs d’Unix ou GNU/Linux (ext3fs
pour third extented file system). Un nœud d’index est constitué d’attributs décrivant le fichier ou le
répertoire et d’adresses de blocs contenant des données (voir Figure 1). Cette structure possède plusieurs
entrées, elle permet au système de disposer d’un certain nombre de données sur le fichier :
— le type (le type du fichier, un entier dont la valeur est 0 pour un fichier et 1 pour un répertoire,
— Le nombre de liens (voir après),
— UID (User Identification) : numéro d’utilisateur du propriétaire
— GID (Group Identification) : numéro du groupe propriétaire
— Taille du fichier en octets

111
Chapitre 2. Correction : Système de gestion des fichiers (SGF)

Figure 1 – Structure des i-node : Exemple : Unix

— Adresses des blocs de données (qui contiennent le fichier)

— Droits du fichier
— Date du dernier accès
— date de la dernière modification
— date de création
— Pointeurs directs/indirects sur des blocs de données.
Pour plus de détail, voir la référence [13].
18. Quelle technologie augmente la fiabilité des unités de stockage ?
Le RAID [7] (Redundant Array of Independent Disks) est un ensemble de techniques de virtualisation
du stockage permettant de répartir des données sur plusieurs disques durs afin d’améliorer soit les
performances, soit la sécurité ou la tolérance aux pannes de l’ensemble du ou des systèmes.
19. Discuter les avantages et les inconvénients des caches (Buffer) ?
— Avantages : Caching minimise les opérations de l’entrée-sortie de disque.
— inconvénients : la taille du buffer est limité Ô⇒ Besoin d’un algorithme de remplacement de
page.
20. Le FAT16 est utilisé par MS-DOS. En FAT16, les numéros de blocs sont écrits sur 16 bits. Si
on suppose que la taille d’un bloc est 32Ko, Calculer la taille maximale adressable ?
Avec FAT16 : la taille maximale de 216 , soit 65 536 clusters de taille fixe. La maximale adressable= 216 x
32 = 2 gigaoctet (Go).
21. Que signifier Hadoop Distributed File System (HDFS) ?
Le système de fichiers distribués Hadoop (HDFS) est le principal système de stockage de données utilisé
par les applications Hadoop 11 . Il utilise une architecture NameNode et DataNode pour implémenter
un système de fichiers distribué qui fournit un accès hautes performances aux données à travers des
clusters Hadoop hautement évolutifs.

11. Hadoop est un framework libre et open source écrit en Java destiné à faciliter la création d’applications distribuées (au
niveau du stockage des données et de leur traitement) et échelonnables (scalables) permettant aux applications de travailler
avec des milliers de nœuds et des pétaoctets de données.

112
 2.1. Le corrigé des exercices

22. Quel est le rôle NameNode et DataNode dans HDFS ? ?

NameNode : (store metadata, Managing FS namespace, check availability and replication).
DataNode : (stroring data, replication creating, deleting job, send report (defaut time 3 sec) )

2.1.2 Exercice n°2 :

Combien de bloc a-t-on besoin au minimum pour stocker tout le fichier si la taille de bloc est 32 KO.
Taille du fichier : T aille f = Nbr Enr * T aille Enr = 6000*1= 6000.
T aill e f
Nombre du blocs : Nbr Blocs = T aill eb = 6000
32 ≃ 188, avec T ailleb : Taille du bloc.
Définission d’une fonction d’hachage :
Soit h une fonction qui retourne le numéro du bloc qui coresspond à une clé d’entrée n :
h : E Ð→ F
On propose une fonction de hachage sous forme factorielle h(n)=n !. Cette fonction calcul de la factorielle
d’un entier naturel dont la valeur est comprise dans l’intervalle 0 ≤ h(n) ≤ 187.

2.1.3 Exercice n°3 :

a) Chaque bloc de données peut contenir 256 pointeurs (numéros de blocs). Il faut : - (12 * 1k) pour
direct,
- (256 * 1K) pour ind. simple,
- (256 *256 * 1K) pour ind. double,
- (256 * 256 * 256 * 1K) pour ind. Triple
Taille = (12 * 1K) + (256 * 1K) + (256 * 256 * 1K) + (256 * 256 *256 * 1K) = (12 + 256 + 256*256 + 256*256*256)
K = 16,843,020 K octets.
b) Si on considère un fichier contenant 100,000 octets, on voit que :
100,000 = 97 * 1024 + 672. Il faudra donc 98 blocs pour conserver les données de ce fichier.
L’i-noeud ne dispose que de 12 pointeurs directs, il va donc falloir utiliser des blocs supplémentaires
(98-12=86) pour conserver le reste des données. Comme 86<256, ces blocs de données seront accessibles
à partir du pointeur indirect simple du i-noeud.
Une partie d’un bloc sera nécessaire pour conserver les 86 pointeurs sur des blocs de données. Le nombre
total de blocs utilisés est donc 98+1 = 99.

2.1.4 Exercice n°4 :

Notre fichier compte 20,000,000 = 4882 * 4096 + 3328 octets. Il faudra donc 4883 blocs pour conserver
les données de ce fichier. Il faudra aussi leur ajouter des blocs qui vont être utilisés pour stocker des
pointeurs vers ces blocs de données. On effectue donc le calcul suivant (sur les blocs) :
— Le fichier compte 4883 blocs de données.
— Les pointeurs directs de l’i-noeud permettent d’accéder à 12 de ces blocs. Il reste donc 4871 blocs
de données pour lesquels l’accès se fera à travers l’un des liens indirects.

113
Chapitre 2. Correction : Système de gestion des fichiers (SGF)

— Le pointeur de lien indirect simple pointe sur un bloc qui contient 1024 numéros de blocs (pointeurs
vers des blocs de données). Nous avons donc ajouté 1 bloc de pointeurs, et il reste 4871 - 1024 =
3847 blocs à traiter.
— Le pointeur de lien indirect double permet d’accéder à 1024*1024 blocs, ce qui est plus que suffisant.
Il suffit d’utiliser 4 blocs de données pour stocker les 3847 pointeurs de blocs permettant d’accéder
aux données restantes.
Fragmentation interne :
— L’espace alloué mais non utilisé :
— 4 octets sur l’i-noeud (indirection triple non utilisé)
— (1024-4)*4 = 4080 octets dans le bloc sur lequel pointe le pointeur indirect double.
— ( 4096-3847)*4 = 996 octets dans le dernier bloc de pointeurs alloué.
— Finalement, 768 octets dans le dernier bloc de données. La fragmentation interne totale sur le
disque est donc de 5848 octets.

2.1.5 Exercice n°5 :

Pour cet exercice, je vous donne des directives pour calculer le nombre des E/S avec les deux algorithmes
FIFO et LFU. Un fichier est un ensemble de blocs, pour le chargement d’un bloc b : si le bloc b est dans
le cache, retourner son numéro de slot. sinon s’il y a un slot libre dans le cache, chargé le bloc du
disque, sinon choisir un slot à vider (l’écrire sur disque) et le remplacer par b selon une Stratégies de
remplacement (par ex. FIFO). La Figure 2 montre une illustration de remplacement des pages du buffer.

Figure 2 – Illustration de remplacement des pages du buffer.

2.2 Correction de QCM

Cet exercice est un questionnaire à choix multiples (QCM). Pour chacune des questions suivantes, cocher
la bonne réponse.

114
 2.2. Correction de QCM

Question no 1 Dans le fichier /etc/passwd, quel(s) shell(s) ne permet(tent) pas d’interprter des com-
mandes ? (plusieurs réponses sont possibles)

 a. /bin/bash
b. /bin/false
c. /sbin/nologin
 d. /bin/zsh

Question no 2 Pour modifier le comportement d’une commande on utilise :

 a. des fichiers
b. des options
 c. des rpertoires
 d. des arguments

Question no 3 On veut renommer pour notre session la commande kill -9 avec le nom stop_signal.
La commande effectuer est :

 a. rename kill -9 > stop_signal

b. alias stop_signal=”kill -9”

 c. rename stop_signal=”kill -9”

 d. alias kill -9 > stop_signal

Question no 4 Que fait la commande who | wc -l ?

 a. Elle affiche la liste des utilisateurs connects

 b. Elle jette le r2sultat de la commande who
c. Elle affiche le nombre des utilisateurs connects
 d. Elle 2choue

Question no 5 L’option -k de la commande man sert 0 :

a. faire une recherche par mot-clé

 b. créer une nouvelle page du manuel
 c. effacer une page du manuel
 d. rechercher une page sur internet

115
Chapitre 2. Correction : Système de gestion des fichiers (SGF)

Question no 6 Que fait la commande !! ?

 a. Affichage de l’avant dernière commande

b. Exécute la dernière commande
 c. Efface l’historique
 d. Affiche l’historique des commandes

Question no 7 Chaque utilisateur UNIX possède un répertoire qui porte son nom de login. Comment
l’appelle t’on ? :

 a. perso

b. home

 c. directory

 d. user

Question no 8 Quelle commande permet de changer son mot de passe ?

 a. pass
b. passwd
 c. password
 d. newpass

Question no 9 Que contient le dossier système /mnt sur un système UNIX :

 a. les fichiers de configuration du système

 b. les fichiers du noyaux UNIX
c. les répertoires de périphériques amovibles
 d. les fichiers spécifiques aux périphériques

Question no 10 Quel alias permet de revenir dans le répertoire personnel et d’en lister le contenu ?

a. alias go=’cd ; ls’ ;

 b. alias go=’cd . ; ls’ ;
 c. alias go=’cd . ; dir’ ;
 d. alias go=’cd / ; ps’ ;

Question no 11 Que fait la commande ls -F . ?

 a. Elle force l’affichage des fichiers et des répertoires du rpertoire de travail.

 b. Elle compte le nombre de fichiers contenu dans le rpertoire de travail.
c. Elle affiche les objets contenu du rpertoire de travail en prcisant leur type.
 d. échoue.

116
 2.2. Correction de QCM

Question no 12 Quelle commande permet de renommer le fichier oui en non ?

 a. rn oui non
 b. cp oui non
c. mv oui non
 d. mp oui non

Question no 13 Les noms de fichier et de répertoire sont sensibles à la casse ?

a. oui
 b. non
 c. cela dépend de la version du noyau UNIX
 d. non, mais il est possible d’utiliser des chiffres

Question no 14 Que permet de faire la commande chgrp dupont essai ?

 a. Elle écrit dupont dans le fichier essai

b. Elle remplace le nom du groupe du fichier essai par dupont
 c. Elle écrit essai dans le fichier dupont
 d. Elle lit le fichier essai en prenant le nom d’utilisateur dupont

Question no 15 Propriétaire du fichier essai.html, quelle commande dois-je utiliser pour pour retirer
les droits en exécution à tout le monde. ? (Plusieurs réponses possibles)

 a. chmod u+ressai.html

 b. chmod a+x essai.html

c. chmod ugo-x essai.html

d. chmod a-x essai.html

Question no 16 La notation octale 724 pour la gestion des droits d’accés correspond à la notation
symbolique :

a. rwx -w- r-

 b. rwx r-x rw-

 c. rw- r-x r-x

 d. r- -w- rwx

117
Chapitre 2. Correction : Système de gestion des fichiers (SGF)

Question no 17 Que represente 640 en termes de droits d’accs ?

 a. Les autres utilisateurs n’ont que les droits en lecture

 b. Les autres utilisateurs n’ont que les droits en écriture
 c. Les autres utilisateurs n’ont que les droits en exécution
d. Les autres utilisateurs n’ont aucun droit

Question no 18 L’UID de l’utilisateur root est :

a. 0
 b. 1
 c. true
 d. vrai

118
Chapitre

3
Corrigé : Gestion des périphériques : Attente
Active, Interruption et DMA

Sommaire
3.1 Le corrigé des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
3.1.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
3.1.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.1.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.1.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.1.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.1.6 Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.2 Correction de QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

"Le bruit est la plus importante des formes d’interruption. C’est non seulement une interruption, mais aussi
une rupture de la pensée".
- rthur Schopenhauer

3.1 Le corrigé des exercices

3.1.1 Exercice n°1 :

1. Qu’est-ce qu’un vecteur d’interruption ?

Le vecteur d’interruption est une table qui contient les adresses des routines d’interruption. Les
interruptions sont numérotées et ces numéros (allant de 0 à 255 dans un PC) servent d’index pour
rechercher dans le vecteur d’interruption l’adresse de la routine à exécuter.
2. Pourquoi les interruptions sont-elles parfois désactivées ?
L’interruption peut être masquée (désactivée) ou ne pas être exécutée parce qu’une autre interrup-
tion de priorité supérieure ou égale est en cours.
3. Pourquoi certains systèmes prennent-ils en charge les priorités d’interruption ?
L’interruption est mise de côté pour être exécutée ultérieurement ou l’interruption de priorité
plus grande exige un temps de réponse critique et elle ne peut pas être retardée (Pour garantir un
bon temps de réponse).
4. Quels types d’appareils devraient obtenir les priorités les plus élevées ?

121
Chapitre 3. Corrigé : Gestion des périphériques : Attente Active, Interruption et DMA

5. Qu’est ce qu’un contrôleur de périphérique ?

Un contrôleur (on dit parfois coupleur) est un dispositif adapté à chaque type de périphérique. Il
se connecte à plusieurs périphériques de même type (mais un seul périphérique peut transférer à
la fois). Il assure les fonctions logiques des E/S.
6. Comment le CPU communique-t-elle avec un contrôleur d’E/S ?
Avec trois modes de communication : Déroulement d’une IT, Attente Active (Polling), Direct Memory
Access (DMA).
7. Expliquez comment (et pourquoi) les tampons (buffers) sont utilisés pour les E/S disque.
Cache de tampons (buffer cache) de la base de données : met en mémoire cache les blocs de
données extraits de le disque afin de minimiser les opérations des E/S.
8. Quelle est la différence entre IRQ et un vecteur d’IT ?
Dans un ordinateur , une requête d’interruption (ou IRQ [15] ) est un signal matériel envoyé
au processeur qui arrête temporairement un programme en cours d’exécution et permet à un
programme spécial.
Un Vecteur d’IT : table de mapping entre numeor IT et traitement de IT.
9. Quelles sont les différences entre un déroutement et une IT ?
- IT souvent designe un événement materiel qui interrompre le CPU.
- Déroutement represente les erreures semanitque qui crash l’application (div par zeo, debordement
de buffer (overflow).
10. Qu’est-ce qu’une memory-mapped I/O ?
Chaque disposotf d’E/S est représenté en mémoire par une adresse logique. L’dresse d’un périphé-
rique comprend 3 parties : numéro du canal relié à la mémoire centrale, numéro du contrôleur
attaché au canal et numéro du périphérique attaché au contrôleur.
11. Vous êtes responsable de l’écriture d’un pilote de périphérique pour un modem 56Kbps
sur votre PC. En supposant que vous décidez d’utiliser le polling pour la communication
entre le SE et le matériel du modem, expliquer les étapes de l’écriture d’un paquet de
données du SE vers le modem.
L’attente active, ou polling est une technique de programmation que les processus utilisent
lorsqu’ils vérifient de façon répétée si une condition est vraie, comme l’attente d’une entrée ou
encore la libération d’un verrou (voir Figure 1).
Etapes :
(a) Le programme consulte le periphrique selon leur frequence.
(b) Soit en interrogeant un indicateur d’état dans l’interface de l’appareil, soit en attendant
que l’appareil envoie une demande d’interruption.
(c) les processus doivent être vérifiés de façon répétée si une condition est vraie, comme
l’attente d’une entrée ou encore la libération d’un verrou.
(d) Chaque élément est testé périodiquement pour vérifier s’il ne nécessite pas un service
particulier.
(e) l’unité centrale n’était pas obligé de perdre le temps dans les boucles d’attente et a été
sollicitée par les différents dispositifs qui étaient choisis à faire.

122
 3.1. Le corrigé des exercices

Figure 1 – Attente active (Polling)

12. Décrivez brièvement comment se fait le transfert d’un bloc de disque vers la mémoire,
si le système dispose d’un DMA ?
Le processeur envoie la commande d’E/S au driver du disque. Le driver détaille la commande et la
traduit au contrôleur. Le contrôleur prépare les données en copiant les données du disque vers le
buffer du disque. Le dispos itif DMA envoie les données prépare directement vers la mémoire (sa
ns passer par le processeur). A la fin du transfert , une interruption est générée pour informer le
processeur que le transfer t est terminé.

13. Laquelle des instructions suivantes doit être privilégiée ?

b. Lire l’horloge (IT).

3.1.2 Exercice n°2 :

Calcul du nombre maximal d’ITs peut-il traiter en 1 ms :

Nbr r eдist r e = 32 + le compteur ordinal + le pointeur de pile= 34 registre.
T emps IT = 34*10*2 = 680 ms
On a : 1 ms = 1000 000 ns.
Nbr IT = 1000000
680 = 1470 interruptions (IT) en 1 ms

3.1.3 Exercice n°3 :

Calcul du nombre pourcentage d’occupation du processeur par les ITs si chaque interruption prend 50
µs.
Pour 6 pages Ð→ le temps d’interruption (IT) : T emps IT = 50*80*50*106 Secondes (s) =1,2 s.
1,2
Pourcentage d’occupation (le taux d’occupation) : Occ IT = 60 = 0,02 = 2%.

123
Chapitre 3. Corrigé : Gestion des périphériques : Attente Active, Interruption et DMA

Attente
DMA IT
Active
Lorsque le CPU n’est pas complètement chargé,
X
laquelle des méthodes suivantes de transfert de données est préférée
Le processeur lit le registre d’état du dispositif et vérifie si un indicateur
X
(ou flag) "terminé" a été défini par le dispositif.
Notifier un processeur lorsqu’un périphérique d’E/S nécessite une attention. X
Une plus grande efficacité lorsque le périphérique d’E/S génère beaucoup
X
de trafic
Le processeur n’a pas besoin de dépenser des cycles interrogeant le dispositif X
Il est considéré comme efficace car il supprime le CPU d’être responsable
X
du transfert de données
Le processeur envoie la commande d’E/S au driver du disque.
X
Le driver détaille la commande et la traduit au contrôleur.
Il peut y avoir moins de latence entre le moment où le dispositif
X
est prêt et les données sont transférées.
Déplacer de grandes quantités de données entre les périphériques
X
d’E/S et la MC.
Peu efficace car "context switching" couteux X

3.1.4 Exercice n°4 :

Calcule de pourcentage d’utilisation du processeur réservé à l’horloge :

T emps I T
Pourcentage= ratios rapport = T empsC P U

60 T Ð→ 1 Seconds (sec)
Calcule du T emps IT T empsC PU =?
60∗2
On a : 1 top =2ms Ð→ 60 TOP/sec= 1000 = 12% .
L’interprétation du résultat : L’horloge doit fournir un signal régulier pour synchroniser tout le
fonctionnement du processeur. Le taux d’utilisation de CPU par l’horloge est signifiable (12%).

3.1.5 Exercice n°5 :

— Quel est le temps d’accès moyen du système considéré seulement des cycles réels de mémoire ?
— 0.9 x 120 + 0.1 x 11000 = 108 + 110 = 218 nsec.
— Quel est le taux de réussite en tenant compte du cycle d’écriture ?
— cache access memory access= 0.2 x 900 + 0.8 x 200 = 180 + 100 = 280 nsec..
— Quel est le temps d’accès moyen du système pour les requêtes de lecture et d’écriture.
— write access = Hit ratio = 0.8 x 0.9 = 0.72

3.1.6 Exercice n°6 :

Indiquer le type de communication dans chaque situation dans le tableau suivant :

124
 3.2. Correction de QCM

3.2 Correction de QCM

Cet exercice est un questionnaire à choix multiples (QCM). Pour chacune des questions suivantes, cocher
la bonne réponse.

Question no 1 Interruption Matérielle ?

 a. un paquet réseau arrive

b. mouvement de la souris
 c. erreur arithmétique
 d. instruction invalide

Question no 2 Une interruption masquée ?

 a. elle est ignorée

b. elle est mémorisée

Question no 3 Le maillon faible dans un système d’E/S ?

a. Disque
 b. Mémoire RAM
 c. Cycle CPU

Question no 4 Parmi ces propositions, laquelle est une Interruption Logicielle ?

a. overflow
b. erreur d’adressage
c. code opération inexistant
d. problème de parité
 e. mouvement de la souris
f. division par zéro

Question no 5 La commande strace intercepte et affiche les appels systèmes d’un programme ?

a. overflow
b. erreur d’adressage
c. code opération inexistant
d. problème de parité
 e. mouvement de la souris
f. division par zéro

125
Chapitre 3. Corrigé : Gestion des périphériques : Attente Active, Interruption et DMA

Question no 6 La commande qui intercepte et affiche les appels systèmes d’un programme ?

a. strace (voir ? ?)
 b. tcpdump
 c. netstat
 d. swapon
 e. nicstat
 f. pidstat

Question no 7 Le mot d’état du processeur (Processor Status Word, PSW), il comporte généralement : ?

a. État d’exécution : Actif/Attente

b. Mode d’exécution : Maître/Esclave
c. Table des segments
d. Compteur ordinal
 e. Température CPU

126
Chapitre

4
Corrigé : Gestion des Processus (primitives
fork/join)

Sommaire
4.1 Le corrigé des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.1.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.1.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.1.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
4.1.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
4.1.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.1.6 Exercice n°6 : Diviser pour calculer plus vite . . . . . . . . . . . . . . . . 132
4.1.7 Exercice n°8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.2 Correction de QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

"Nothing is particularly hard if you divide it into small jobs".

- Henry Ford (1863-1947)

4.1 Le corrigé des exercices

4.1.1 Exercice n°1 :

Testez vos connaissances en répondant aux questions de la théorie.

Qu’est-ce qu’un processus ? Quelle est la différence entre un processus et un programme ?
Le processus un terme a été introduit dans les années 60 pour généraliser "‘job concept"’. Un processus
c’est l’aspect dynamique du programme (description statique).
Qu’est-ce qu’un thread ?
Un thread (appelée aussi processus léger ou activité) est un fil d’instructions (un chemin d’exécution) à
l’intérieur d’un processus.
En quoi un thread diffère-t-il d’un processus ?
Un thread est donc une portion de code capable de s’exécuter en parallèle à d’autres traitements. Dans
le cas de thread, la commutation de contexte moins coûteuse c-à-d ne nécessite pas un travail de gestion
mémoire.
Comment les threads peuvent-ils être utiles en Java ?

129
Chapitre 4. Corrigé : Gestion des Processus (primitives fork/join)

Les threads fonctionnent comme les processus : ils ont des états (bloqué, prêt, en exécution), se partagent
l’UC et un seul thread est actif (en exécution) à la fois. Chaque thread dans un processus possède son
propre compteur d’instructions et sa propre pile. Les threads peuvent créer des fils. Si un thread est
bloqué, un autre peut s’exécuter.
Décrivez les 3 modèles multithreads : plusieurs à un, un à un, plusieurs à plusieurs.
Le modèle un à un mappe chacun des threads utilisateur sur un thread du noyau. Cela signifie que
de nombreux threads peuvent s’exécuter en parallèle sur des multiprocesseurs et que d’autres threads
peuvent s’exécuter lorsqu’un thread effectue un appel système bloquant. Le modèle plusieurs à un
mappe de nombreux threads utilisateur à un seul thread noyau. Ce modèle est assez efficace car l’espace
utilisateur gère la gestion des threads. Le modèle plusieurs à plusieurs mappe de nombreux threads
utilisateur à un nombre égal ou inférieur de threads du noyau. Le nombre de threads du noyau dépend
de l’application ou de la machine.

Figure 1 – Modèles multithreads

4.1.2 Exercice n°2 :

Nous décrivant les transitions d’un processus, en commentant les étiquettes 1, 2, 3, 4, 5, 6 et en précisant
quels sont les événements qui provoquent chacune des transitions :

1. Nouveau Ð→ Prêt : Chargement de processus en mémoire centale.

2. En Execution Ð→ Prêt : La commutation de contexte dans la mémoire centale lorsque le pro-

cessus en cours est interrompu pour une raison quelconque (fin de quantum, préemption due à
l’arrivée d’un processus plus prioritaire, ...).

3. En Execution Ð→ En Attente : Opération d’E/S provoque la sauvegarde du contexte du proces-

sus interrompu (compteur ordinal, contenu des registres et des variables, liste des fichiers ouverts,
...etc).

4. En Attente Ð→ Prêt : Fin d’opération d’E/S qui implique la restauration du contexte du processus
chargé

5. Fin Execution= Terminé : Arrêt volontaire, Erreur, Erreur fatale.

130
 4.1. Le corrigé des exercices

4.1.3 Exercice n°3 :

La Figure 2 présente le graphe de précédence et le pseudo code qui correspond à la formule suivante :

y = 2 ∗ ((a + b) ÷ (c − d ) + (e ∗ f )) + ((a + b) ∗ (c − d )) (1)

Figure 2 – Le graphe de précédence et le pseudo code

4.1.4 Exercice n°4 :

Le code Liste 4.1 illuste le programme parallèle de la figure (a) présenté dans l’exercice de la section
4.2.3 du chapitre 4.
1

2 N1=2, n2=3 ;
3 S1 ;
4 Fork L1 ;
5 S2 ;
6 S5 ;
7 Fork L3 ;
8 S7 ;
9 Goto L4
10 L1 : fork L 2 ;
11 S3 ;
12 L3 : join n1 ;
13 S6 ;
14 Goto L4 ;
15 L2 : S4 ;
16 L4 : join n2 ;
17 S8 ;

Listing 4.1 – le programme parallèle FORK/JOIN (a)

Le code Liste 4.2 illuste le programme parallèle de la figure (b) présenté dans l’exercice de la section
4.2.3 du chapitre 4.
1 S1 ;
2 count := 3 ;
3 FORK L1 ;

131
 Chapitre 4. Corrigé : Gestion des Processus (primitives fork/join)

4 S2 ;
5 S4 ;
6 FORK L2 ;
7 S5 ;
8 GO TO L3 ;
9 L2 : S6 ;
10 GO TO L3 ;
11 L1 : S3 ;
12 L3 : JOIN count ;
13 S7 ;

Listing 4.2 – le programme parallèle FORK/JOIN (b)

Note : statement "L1 : S3" is not necessary GOTO L3 since L3 comes next step count := 3 (in degree of 3)
at S7

4.1.5 Exercice n°5 :

Le graphe de précédence qui correspond au code :

Figure 3 – Graphe de précédence qui correspond au code

4.1.6 Exercice n°6 : Diviser pour calculer plus vite

Le framework Fork/Join a été introduit dans Java 1.7 pour implémenter facilement les algorithmes de
division et de conquête avec la prise en charge de processeurs multicœurs. L’Algorithme 4.1 illustre le
principe de calcule de suite de fibonacci par un programme de Nested fork-join.
1 import static java.time.temporal.ChronoUnit.MILLIS ;
2

132
 4.1. Le corrigé des exercices

Algorithme 4.1 Fibonacci Recursive (Le programme de Nested fork-join)

function FIB(n)

si n < 2 alors
retourner n ;
a=fork FIB(n-1) ;
b=fork FIB(n-2) ;
join ;
retourner (a+b) ;

3 class Fibonacci extends RecursiveTask<Integer>{

4

5 int num ;
6 Fibonacci(int n){
7 num = n ;
8 }
9

10 @Override
11 protected Integer compute() {
12 if(num <= 1)
13 return num ;
14

15 Fibonacci fib1 = new Fibonacci(num-1) ;

16 fib1.fork() ;
17 Fibonacci fib2 = new Fibonacci(num-2) ;
18 fib2.fork() ;
19

20 return fib1.join()+ fib2.join() ;

21 }
22 }
23

24 public class ForkJoinFibonaaciEx {

25

26 public static void main(String[] arg){

27 LocalTime before = LocalTime.now() ;
28 int processors = Runtime.getRuntime().availableProcessors() ;
29 System.out.println("Available core : "+processors) ;
30 ForkJoinPool pool = new ForkJoinPool(processors) ;
31 System.out.println("Inside ForkJoin for number 50 : "+pool.invoke(new Fibonacci(50))) ;
32 LocalTime after = LocalTime.now() ;
33 System.out.println("Total time taken : "+MILLIS.between(before, after)) ;
34 }
35 }

Listing 4.3 – Programme JAVA montre l’usage des primitives fork() et pipe()

133
 Chapitre 4. Corrigé : Gestion des Processus (primitives fork/join)

4.1.7 Exercice n°8

L’Algorithme 4.1 illustre le principe du tri par fusion pour un tableau avec 100 000 000 entiers aléatoires.

1 public class SingleThreadArraySort {

2 // From Java 7 ’_’ can be used to separate digits.
3 public static final int ARRAY_SIZE = 10_000_000 ;
4 public static void main(String[] args) {
5 long startTime ;
6 long endTime ;
7 int[] array = createArray(ARRAY_SIZE) ;
8 MergeSort mergeSort = new MergeSort(array) ;
9 // Get the current time before sorting
10 startTime = System.currentTimeMillis() ;
11 mergeSort.sort() ;
12 // Get the current time after sorting
13 endTime = System.currentTimeMillis() ;
14 System.out.println("Time taken : " +
15 (endTime - startTime) + " millis") ;
16 }
17 // createArray method here...
18 }
19 class MergeSort {
20 private int array[] ;
21 public MergeSort(int[] array) {
22 this.array = array ;
23 }
24 public void sort() {
25 sort(0, array.length - 1) ;
26 }
27 /**
28 * Sort the array using divide and conquer algorithm.
29 */
30 private void sort(int left, int right) {
31 if (left < right) {
32 int mid = (left + right) / 2 ;
33 sort(left, mid) ;
34 sort(mid + 1, right) ;
35 merge(left, mid, right) ;
36 }
37 }
38 // merge method here...
39 }
40 \label{uml2erdd}

Listing 4.4 – Programme JAVA de tri par fusion avec l’usage des primitives fork() et pipe()

134
 4.2. Correction de QCM

4.2 Correction de QCM

Cet exercice est un questionnaire à choix multiples (QCM). Pour chacune des questions suivantes, cocher
la bonne réponse.

Question no 1 Que fait la commande !2 ?

 a. Elle tue le processus

 b. Elle rend la main à l’utilisateur dans 2 secondes
 c. Elle donne des informations sur le processus
d. Elle répète la 2ème commande de l’historique

Question no 2 Quelle commande permet de passer en arrire-plan une commande déjà lancée ?

a. bg

 b. fg

 c. &

 d. ap

Question no 3 On veut renommer pour notre session la commande kill -9 avec le nom stop_signal.
La commande effectuer est :

 a. rename kill -9 > stop_signal

b. alias stop_signal=”kill -9”

 c. rename stop_signal=”kill -9”

 d. alias kill -9 > stop_signal

Question no 4 Que fait la commande !! ?

 a. Affichage de l’avant dernière commande

b. Exécute la dernire commande
 c. Efface l’historique
 d. Affiche l’historique des commandes

Question no 5 Quelle est la commande permettant la visualisation dynamique des processus ?

 a. ps -dyn

 b. vs -p

c. top

 d. ps -d

135
Chapitre 4. Corrigé : Gestion des Processus (primitives fork/join)

Question no 6 L’UID de l’utilisateur root est :

a. 0
 b. 1
 c. true
 d. vrai

Question no 7 Quelle commande pemet de tuer le processus ayant pour identifiant le numro 5023 ?

 a. stop 5023

 b. ps -s 5023

c. kill -9 5023

 d. stop -9 5023

136
Chapitre

5
Corrigé : Ordonnancement des processus
(scheduling de l’UC)

Sommaire
5.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2 Le corrigé des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
5.2.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
5.2.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
5.2.5 Exercice n°5 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
5.2.6 Exercice n°7 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
5.3 Correction de QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

"Spending time with God is the key to our strength and success in all areas of life. Be sure that you never try
to work God into your schedule, but always work your schedule around Him".
- Joyce Meyer

5.1 Objectif

Le but de ces exercices est de mettre en évidence, sur un système simplifié à l’extrême, l’influence
de l’évolution historique des systèmes d’exploitation sur quelques grandeurs caractéristiques de leurs
performances.

5.2 Le corrigé des exercices

5.2.1 Exercice n°1 :

Testez vos connaissances en répondant aux questions de la théorie.

1 : Quelle est la différence entre les I/O-bound jobs et CPU-bound jobs ?
Dans un système uniprocessus, un seul processus est exécuté à la fois, d’autres processus doivent attendre
le temps de CPU. L’exécution d’un processus consiste en des cycles d’utilisation CPU et d’attente sur
E/S (I/O).

139
Chapitre 5. Corrigé : Ordonnancement des processus (scheduling de l’UC)

2 :Que veut dire la multiprogramming ?

La présence simultanée, en mémoire principale, de plusieurs programmes.
3 : Qu’est ce qu’un système temps partagé (time-sharing) ? Quels sont les principaux avantages
de système temps partagé ?
Il faut diviser le temps CPU entre différents processus.
4 : Comment le partage du temps est-il généralement mis en œuvre ?
On se basant sur l’affectation du processeur.
5 : C’est quoi PCB ?
Le Process Control Block (PCB) est une structure de de données qui contient toutes les informations
nécessaires à la bonne exécution du processus. Les PCB sont stockés dans une table des processus
6 : C’est quoi le swapping ?
Le SE doit libérer de l’espace Pour exécuter le processus (état prêt).
7 : C’est quoi la commutatuon de contexte ( context switch) ? Que fait le noyau lors d’un chan-
gement de contexte ?
Une commutation de contexte (context switch) en informatique consiste à sauvegarder l’état d’un
processus pour restaurer à la place celui d’un autre dans le cadre de l’ordonnancement d’un système
d’exploitation multitâche.
8 : Que se passe-t-il au cours du terminaison d’un processus ?
Ce processus quitte le processeur et libère toutes ses ressources.
9 : Qu’est-ce qu’un CPU burst ? Qu’est-ce qu’un I/O burst ?
Execution découpée en CPU burst et I/O burst. CPU burst est la preoccupation de CPU et I/O burst est
l’attente d’un périphérique.
10 : Que signifie preemptive ? Non-Non-preemptive ?
L’ordonnancement non préemptif : un processus conservait le contrôle de l’UC jusqu’à ce qu’il se bloque
ou qu’il se termine. correspond parfaitement aux systèmes de traitements par lots.
L’ordonnancement préemptif : L’ordonnanceur (dispatcher de ordonnancement) peut préempter (inter-
rompre) un processus avant qu’il se bloque ou se termine, afin d’attribuer l’UC à un autre processus.
11 : Qu’est-ce que le dispatcher ? ? Qu’est ce que ça fait ?
Le dispatcher suit l’activité du processeur, il choisit la requête à traiter et l’extrait de la file. Il gère donc
l’allocation du processeur Il peut le réquisitionner en fonction de la priorité des processus demandeurs
et du temps déjà consommé par celui qui est en cours d’exécution.
12 : Quels critères de performance pourraient être sélectionnés pour évaluer les algorithmes
d’ordonnancement ?
— Utilisation CPU –Maintenir le CPU le plus utilisé possible.
— Débit –(throughput) C’est le nombre de processus qui terminent leur exécution par unité de temps
(1000 par heure, ou 10 par seconde ?).

140
 5.2. Le corrigé des exercices

— Temps de retournement (Restitution) –(turnaround time) Temps nécessaire pour exécuter un

processus (depuis la soumission jusqu’‘a la terminaison).
— Temps d’attente –(waiting time) Temps qu’un processus passe dans la file ready.
— Temps de réponse –(response time) Temps entre la soumission d’une requête et la première
réponse (et non la sortie finale).
13 : C’est quoi le débit ( throughput) ?
Débit –(throughput) C’est le nombre de processus qui terminent leur exécution par unité de temps (1000
par heure, ou 10 par seconde ?).
14 : C’est quoi FCFS ? Quels sont ses avantages / inconvénients ?
Avantages :
-Facile à comprendre -Facile à programmer des files d’attente simples -Le cas de bloquer ou d’ajouter de
nouveau processus nécessite simplement de l’attacher à la queue de la file d’attente
Inconvénients :
- Le temps d’attente moyen est souvent assez long -Petit processus attend un grand processus -Ne
convient pas au partage du temps
15 : C’est quoi SJF ? Quels sont ses avantages / inconvénients ?
Avantages :
On favorise les processus courts ce qui augmente le débit de processus traités et donc la réactivité
Inconvénients :
Risques de famine (un processus trop long pourrait ne jamais être exécuté s’il y a toujours un plus court)
16 : À quoi sert le time quantum ?
Le scheduleur parcourt la file d’attente en allouant l’UC à chaque processus pendant un intervalle de
temps allant jusqu’à un quantum (ou tranche de temps).
17 : Comment le quantum doit-il être lié au temps du changement de contexte ?
premier processus de la file, configure une horloge pour qu’elle interrompe après 1 quantum et expédie
le processus.
18 : Comment le quantum de temps doit-il être lié aux temps de CPU burst ?
en allouant l’UC à chaque processus pendant un intervalle de temps allant jusqu’à un quantum (ou
tranche de temps).
19 : C’est quoi : multilevel feedback queues ? Quelles sont les caractéristiques déterminantes ?
Comment ces files d’attente sont-elles utilisées sous Linux ?
On définit des classes de processus et on associe à chacune des classes une priorité et une stratégie
d’ordonnancement. Le processeur est alloué aux processus de la classe la plus prioritaire. On ne change
de file que si la file la plus prioritaire est vide. Un processus ne peut pas changer de classe.
Ce type de scheduling est intéressant dans le cas où les processus ne sont pas tous identiques et ont des
besoins en ressources différents (par exemple : les processus système, les processus utilisateurs, ...etc).

141
Chapitre 5. Corrigé : Ordonnancement des processus (scheduling de l’UC)

dans un scheduling multiniveau et feedback, un processus peut changer de file. Il est intéressant d’utiliser
le feedback dans le cas où on doit suivre le comportement des processus et décider si on doit changer le
niveau d’un processus soit à la baisse , soit à la hausse, en fonction de l’utilisation des ressources. Par
exemple, il est recommandé de "dégrader" un processus qui utilise trop longtemps le processeur pour
éviter qu’il pénalise le reste des processus

5.2.2 Exercice n°2 :

1. Quels sont les temps de restitution de chaque processus ?

2. Quels sont les temps d’attente de chaque processus ?

3. Lequel des algorithmes donne-t-il le temps d’attente moyen minimal ?

Figure 1 – FCFS

Figure 2 – RR

142
 5.2. Le corrigé des exercices

Figure 3 – SJF non préemptif

5.2.3 Exercice n°3 :

Taux d’utilisation du processeur : taux Taux = (temps utilisé par les processus utilisateur)/ temps total
a) La commutation du temps consommé par le système pour l’activation d’un processus
b) Algorithme sans réquisition ou algorithme avec réquisition et p>= q : on fait une seule commutation
:

Taux = p/(c+p)
c) Algorithme avec réquisition (ex : Round Robin) avec q<p
Nombre de quanta : n = p/q
Pour chaque quantum de temps on fait une commutation (c)

Temps total = nc + p
Taux = p /(nc +p)
p = nq : on remplace p par sa valeur Ð→ taux = nq/(nc +nq) Ð→
Taux = q/(c+q)
— Si q tend vers 0 Ð→ taux tend 0 : mauvaise utilisation du processeur, le système passe son temps
à faire des commutations.
— Si q tend vers l’infini Ð→ taux vend vers 1 ; on fait une seule commutation équivalent à algorithme
sans réquisition (ex : FIFO).
Conclusion : Il faut bien choisir le quantum de temps.

143
Chapitre 5. Corrigé : Ordonnancement des processus (scheduling de l’UC)

5.2.4 Exercice n°4 :

1) La Figure 4 illustre le diagramme de Gantt correspondant au résultat de l’ordonnancement.

Figure 4 – Diagramme de Gantt

2) La Figure 5 présente le calcule le temps d’attente et le temps de résidence de chacun des processus et
le taux d’utilisation du processeur dans l’intervalle de temps [t0, fin du dernier processus].

Figure 5 – Le calcule le temps d’attente et le temps de résidence.

3) Taux d’utilisation du processeur [t0, t0+110] = (32+22+28+18)/(100-0) = 100/110=0.909

5.2.5 Exercice n°5 :

La Figure 6 illustre le diagramme de Gantt correspondant au résultat de l’ordonnancement.

Figure 6 – Diagramme de Gantt

144
 5.2. Le corrigé des exercices

Temps d’exécution (TempsExe) : Temps d’attente (TempsAtt) : Temps de réponse (TempsRep) :

Utilisation du processeur = (35 / 35) * 100 = 100 %
Débit = 4 / 35=0.11
TempsExeA = 34 − 0 = 34
TempsExeB = 27 − 2 = 25
TempsExeC = 29 − 3 = 26
TempsExeD = 35 − 7 = 28
TempsExeAV G = (34 + 25 + 26 + 28)~4 = 28.25
TempsAttA = (0 − 0) + (15 − 8) + (30 − 23) = 14
TempsAttB = (4 − 2) + (19 − 13) = 12
TempsAttC = (12 − 3) + (27 − 15) = 21
TempsAttD = (14 − 7) + (29 − 16) + (34 − 31) = 23
TempsAttAV G = (14 + 12 + 21 + 23)~4 = 17.3
(TempsRepA = 0 − 0 = 0
(TempsRepB = 4 − 2 = 2
(TempsRepC = 12 − 3 = 9
(TempsRepD = 14 − 7 = 7
TempsRepAV G = (0 + 2 + 9 + 7) ÷ 4 = 4.5

5.2.6 Exercice n°7 :

J’arrive avec une liste de processus et j’applique l’algorithme d’ordonnancement Round-robin (RR) :
Je vérifie si un processus est déjà en cours d’exécution (si le CPUQ = 1) ? Sinon, je suppose que le CPU
est inactif et mèttre un processus sur le CPUQ et décrémenter le compteur de temps (Temps du Cycle).
Ensuite, je vérifie si un processus est terminé ? Si c’est le cas, je retire le processus du CPUQ et émets un
nouveau traiter et décrémenter le compteur de temps (Temps du Cycle).
Sinon
— Si le processus n’est PAS terminé, je vérifie si le temps est écoulé ? Si c’est le cas et que le READYQ
(la file d’attente Ready) est supérieur à zéro, je (1) supprime le processus du CPUQ et le réinsère
sur le READYQ, (2) réinitialiser le compteur quantique de temps, (3) émettre le prochain processus
disponible sur le CPUQ et (4) la valeur du compteur est décrémenté.
Sinon
— Si le processus n’est PAS terminé et qu’il n’y a aucun processus sur le READYQ, je (1)
réinitialise le quantum temporel, (2) exécute et (3) la valeur du compteur est décrémenté.
— Sinon
— Enfin, si son quantum n’a pas expiré, je (1) exécuter et (2) la valeur du compteur est

145
Chapitre 5. Corrigé : Ordonnancement des processus (scheduling de l’UC)

décrémenté.
On reviens et exécute jusqu’à ce qu’il n’y ait plus de processus.

Algorithme 5.1 L‘algorithme Round-Robin (RR).

Entrée : P : Un ensemble de processus ;
Entrée : La tranche de temps (ou quantum de temps) est fixée à 2 secondes pour chaque processus
utilisateur ;
Sortie : planification de tâches en round-robin. Round-robin (RR) ;
1 : si countQueue(CPUQUEUE) == 1 alors ▷ le processus est terminé
2: retirer le CPU à un processus ;
3: si countQueue(READYQUEUE) > 0 alors
4: émettre le processus dans le CPU ;
5: décrémenter le temps d’exécution restant de processus en cours ;
6: sinon ▷ process has not completed
7: si headqueue[CPUQUEUE] time quantum == 0 alors ▷ time’s up
8: si countQueue(READYQUEUE) > 0 alors
9: supprimer le processus de CPUQ et l’insérer dans READYQUEUE ;
10 : réinitialiser le compteur de temps ;
11 : émettre le prochain processus disponible sur le CPU ;
12 : décrémenter le temps d’exécution restant de processus en cours ;
13 : sinon ▷ aucun processus dans la file d’attente prête
14 : réinitialiser le compteur de temps ;
15 : exécuter ;
16 : décrémenter le temps d’exécution restant de processus en cours ;
17 : ▷ le quantum n’a pas expiré
18 : exécuter ;
19 : décrémenter le temps d’exécution restant de processus en cours ;
20 : ▷ Le processeur est inactif
21 : si (countQueue(READYQUEUE) > 0 alors
22 : émettre le processus dans le CPU ;
23 : décrémenter le temps d’exécution restant de processus en cours ;
24 : fin si
25 : fin si
26 : fin si
27 : fin si
28 : fin si
29 :
30 :
31 : retourner Round − robinschedulinд ; =0

5.3 Correction de QCM

Cet exercice est un questionnaire à choix multiples (QCM). Pour chacune des questions suivantes, cocher
la bonne réponse.

146
 5.3. Correction de QCM

Question no 1 Quelle méthode correspond mode de traitement des éléments d’une file d’attente (calculs
d’un ordinateur, stocks) ?

 a. FOFI
 b. FIFE
c. FIFO

Question no 2 Dans quel(s) état(s) peut se retrouver un processus juste après une préemption ?

 a. bloqué
 b. éligible
c. élu

Question no 3 Dans quel(s) état(s) peut se retrouver un processus juste après une préemption ?

 a. bloqué
 b. éligible
c. élu

Question no 4 Dans ordonnanceur Multilevel Feedback ?

 a. le quantum des files moins prioritaires peut être plus court

 b. le quantum des files moins prioritaires peut être plus long
 c. le quantum de toutes les files peut être identique
d. le quantum peut varier entre des processus d’une même file

Question no 5 Dans un ordonnanceur Multilevel Feedback, dans quelle condition un processus vatil
descendre d’un niveau ?

 a. il consomme la totalité de son quantum

 b. il ne consomme pas la totalité de son quantum
 c. il y a trop de processus à son niveau
d. il y a trop peu de processus au niveau inférieur

Question no 6 La multiprogrammation nécessite le mécanisme d’ordonnancement ?

 a. Vrai
 b. Faux

147
Chapitre 5. Corrigé : Ordonnancement des processus (scheduling de l’UC)

Question no 7 L’ordonnancement non préemptif ?

a. un processus conservait le contrôle de l’UC jusqu’à ce qu’il se bloque ou qu’il se termine.

b. correspond parfaitement aux systèmes de traitements par lots.
 c. L’ordonnanceur (dispatcher de ordonnancement) peut préempter (interrompre) un processus
avant qu’il se bloque ou se termine, afin d’attribuer l’UC à un autre processus

Question no 8 Algorithme du tourniquet (Round-Robin ou RR), Il a été conçu pour les systèmes en
temps partagé ?

a. Vrai
 b. Faux

Question no 9 Un système d’exploitation « temps réel »... (une seule réponse) ?

 a. exécute ses appels systèmes de manière asynchrone

 b. garanti le temps de réponse des appels système
 c. permet de connaître à l’avance le temps de réponse des appels système
d. minimise le temps de réponse des appels système

Question no 10 Un processus Zombie est un processus ?

 a. qui a perdu son père

b. qui a terminé son exécution en erreur
 c. qui a terminé son exécution et qui attend la prise en compte de cette fin par son père

Question no 11 Quels sont les états de processus qui peuvent être en mémoire secondaire ?

 a. Élu
 b. Prêt
c. Bloqué
 d. Terminer
 e. Nouveau

148
Chapitre

6
Corrigé : Pagination à la demande

Sommaire
6.1 Le corrigé des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.1.1 Exercice n°1 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.1.2 Exercice n°2 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.1.3 Exercice n°3 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.1.4 Exercice n°4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.1.5 Exercice n°6 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6.2 Correction de QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

"Nothing is particularly hard if you divide it into small jobs".

- Henry Ford (1863-1947)

6.1 Le corrigé des exercices

6.1.1 Exercice n°1 :

Testez vos connaissances en répondant aux questions de la théorie.

1 : Qu’est-ce que la mémoire virtuelle ?
2 : La mémoire virtuelle est une technique autorisant l’exécution de processus pouvant ne pas être
complètement en mémoire.
3 : Énumère les avantages d’avoir qu’une partie d’un programme en mémoire.
Avec cette technique, on pourra exécuter des programmes qui peuvent être plus grands que la mémoire
physique.
4 : Qu’est-ce que la pagination à la demande ?
La pagination consiste à diviser l’espace d’adressage logique en unités ou blocs appelés pages. La mémoire
physique est également découpée en blocs ou unités de même taille que les pages, appelés cases ou
cadres de page (pages frames). secondaire (disque). Les pages, des processus (espaces virtuels), qui ne
sont pas chargées dans des cases de mémoire physique sont stockées en mémoire secondaire (disque).
Partage du code et des données (partage de pages) : La pagination permet de partager, entre plusieurs
processus, des pages de code ou de données.

151
Chapitre 6. Corrigé : Pagination à la demande

5 : Pourquoi y a-t-il un valid/invalid bit ? Où est-il conservé ?

6 : Bits de protection : page en lecture/écriture, en lecture, lecture/exécution ; les les bits de protection
peuvent être utilisés comme "‘Bit de validité"’ : page utilisée ou pas par le processus (un processus utilise
une partie seulement de l’espace virtuel) ;
7 : Qu’est-ce qu’un défaut de page ?
Lorsqu’un défaut de pages se produit, le système doit charger la page correspondante depuis la mémoire
secondaire (disque) dans une case de la mémoire principale.
8 : Enumérer la liste des étapes à suivre pour traiter un défaut de page.
Quand il y a un défaut de page, on doit allouer une case pour charger la page référencée. S’il n’existe
pas de page, on choisit une parmi celles qui sont présentes en mémoire et on affecte sa case à la page
référencée. La page sélectionnée au moyen d’un algorithme de remplacement est appelée "page victime".
10 : Qu’est-ce que le remplacement de page ?
La stratégie de remplacement répond à la question suivante : Comment le système choisit-il les pages
qui doivent être retirées de la mémoire principale, lorsque aucune case n’est plus disponible ? Pour le
choix d’une page, on peut tenir compte des informations sur l’utilisation passée des pages présentes en
mémoire principale.
12 : Quels critères utiliser pour choisir un politique de remplacement de page ?
La première page, la page moins récemment utilisée, la page qui n’a pas été référencée depuis longtemps
13 : Quelle est l’anomalie de Belady ?
C’est le nombre de défauts de page croit quand le nombre de cases augmente.
14 : Qu’est-ce que la fragmentation interne ?
Dans la fragmentation interne, le bloc de mémoire affecté à un processus est plus grand que nécessaire.
Par conséquent, certaines parties de la mémoire restent inutilisées. Cet espace ne peut pas être utilisé
pour un autre processus.
15 : Qu’est-ce que la fragmentation externe ?
Si l’espace mémoire total est suffisant pour résider un processus, mais qu’il n’est pas continu, il n’est
toujours pas possible d’utiliser cet espace pour un processus. Ce type de fragmentation est appelé
fragmentation externe.
16 : Quelle est la différence entre une page et un frame ?
La pagination consiste à diviser l’espace d’adressage logique en unités ou blocs appelés pages. La
mémoire physique est également découpée en blocs ou unités de même taille que les pages, appelés
cases ou cadres de page (pages frames).
17 : Que contient le tableau des pages ?
La table de pages contient le numéro de case (adresse physique).
18 : Qu’est-ce qu’un TLB ?
TLB ou translation lookaside buffer, est une mémoire cache du processeur utilisée par l’unité de gestion

152
 6.1. Le corrigé des exercices

mémoire (MMU) dans le but d’accélérer la traduction des adresses virtuelles en adresses physiques.
19 : Qu’est-ce que la segmentation ?
La segmentation est une technique de découpage de la mémoire. Elle est gérée par l’unité de segmentation
de l’unité de gestion mémoire (dite MMU, Memory Management Unit), utilisée sur les systèmes d’exploi-
tation modernes, qui divise la mémoire physique ou la mémoire virtuelle en segments caractérisés par
leur adresse de début et leur taille.
20 :Qu’est-ce que espace d’adressage logique ?
L’espace virtuel d’un processus est défini par : la table de pages, la table auxiliaire ou secondaire et la
Mémoire secondaire ou zone de swap
21 : Qu’est-ce que espace d’adressage physique ?
Elle est découpée en blocs de même taille que les pages et contenant l’image de l’espace virtuel (pro-
grammes, les données, piles) des processus.
23 : La pagination et la segmentation peuvent-elles être combinées dans un seul système d’ex-
ploitation ? Énumérez deux façons ?
Oui.

6.1.2 Exercice n°2 :

Calcul du nombre de défaut de page :

— FIFO : 15 défauts de page.
— OPT : 9 défauts de page.
— LRU : 12 défauts de page.
C’est l’algorithme de remplacement le plus simple. Quand on veut remplacer une page, on choisit la
page la plus ancienne Implémentation Chaque fois que l’on charge une page en mémoire centrale, on
met (on enfile) le numéro de cette page dans une file gérée en FIFO (premier entré premier sorti).

Figure 1 – Algorithme FIFO

Un algorithme de remplacement optimal minimise le taux de défauts de page. Cet algorithme choisit la
page qui ne sera plus utilisée ou la page qui sera utilisée le plus tard possible. Cet algorithme suppose
une connaissance de l’ensemble de la chaîne de références ; il est donc irréalisable en temps réel. Il
permet d’évaluer, par comparaison, les autres algorithmes.
L’algorithme LRU (moins récemment utilisée) choisit la page qui n’a pas été utilisée depuis longtemps

153
Chapitre 6. Corrigé : Pagination à la demande

Figure 2 – L’algorithme FIFO

Figure 3 – L’algorithme optimal (OPT)

(ou la page ayant fait l’objet d’une référence la plus tardive). Cette classe d’algorithme est appelée
algorithme à pile ou «stack algorithms ».

Figure 4 – L’algorithme LRU (Least Recently Used

6.1.3 Exercice n°3 :

Algorithme de l’horloge :
— *la couleur rouge indique la position du pointeur.
— Le nombre de défauts de pages est : 14

6.1.4 Exercice n°4 :

Initialisation (a) Initialisation (b)

For j := 1 to 100 do For i := 1 to 100 do
For i := 1 to 100 do For j := 1 to 100 do

154
 6.2. Correction de QCM

Figure 5 – L’algorithme LRU (Least Recently Used

A[i,j] := 0 ; A[i,j] := 0 ;

Taille du tableau : 100*100 = 10000 entiers ; Ð→ 10000/200 = 50 pages.

Une ligne 100 entier Ð→ 2 lignes par pages
Séquence a) : la matrice est traitée colonne par colonne.
Pour une colonne on parcourt toutes les lignes (100 lignes par colonne),
Une page contient deux lignes, donc on fait un défaut de pages toutes les deux lignes Ð→
100/2= 50 défauts de pages par colonne.
Le nombre de défaut de pages est égal 100*50 Ð→ 5000 DP
Séquence b) : la matrice est traitée ligne par ligne
Une page contient deux lignes ; on fait un défaut toutes les deux lignes.
Le nombre de défaut de pages est égal 100/2 Ð→ 50 DP

6.1.5 Exercice n°6 :

La Figure 6 illustre le mécanisme de la Gestion de la mémoire virtuelle (La pagination à la demande).

La Figure 7 illustre les principaux états d’un processus UNIX.

6.2 Correction de QCM

Cet exercice est un questionnaire à choix multiples (QCM). Pour chacune des questions suivantes, cocher
la bonne réponse.

Question no 1 Que permet le concept de mémoire virtuelle ?

a. de gérer une partie de l’espace disque (mémoire secondaire) comme s’il s’agissait de mémoire
principale.
b. d’exécuter des tâches qui ne peuvent physiquement tenir complètement en mémoire principale.
 c. d’utiliser efficacement les caches mémoires L1 et L2.
 d. d’augmenter la vitesse de commutation lors de la préemption des tâches

155
Chapitre 6. Corrigé : Pagination à la demande

Figure 6 – Les états d’un processus UNIX.

Figure 7 – Le mécanisme de la Gestion de la mémoire virtuelle.

Question no 2 Une adresse générée par l’UC est dite ?

a. adresse logique (relative).

 b. adresse physique (relative).

156
 6.2. Correction de QCM

Question no 3 La conversion entre une adresse virtuelle (logique) en une adresse réelle (physique) est
réalisée par ?

a. MMU (Memory Management Unit) (voir [10])

 b. CPU ( Central Processing Unit)

Question no 4 L’espace virtuel d’un processus est défini par : ?

a. la table de pages.
b. la table auxiliaire ou secondaire.
c. la Mémoire secondaire ou zone de swap.

Question no 5 L’algorithme LRU choisit la page qui n’a pas été référencée depuis longtemp ?

a. Vrai.
 b. Faux.

Question no 6 L’algorithme OPT choisit la page qui ne sera pas référencée pendant longtemps (qui
sera référencée le plus tard possible) ?

a. Vrai.
 b. Faux.

Question no 7 L’implémentation de LRU à l’aide de : ?

 a. File.
b. Pile.

Question no 8 Un espace swap (zone d’échange) est donc créé sur : ?

a. le disque.
 b. la Mémoire principale.

157
 Bibliographie

[1] A. Bensoussan, C. T. Clingen et R. C. Daley. « The Multics virtual memory : concepts and design ». In :
Communications of the ACM 15.5 (1972), p. 308–318 (cf. p. 3).
[2] J Berthelin et B Cousin. « Manuel d’utilisation de l’environnement pour le pseudo-parallèlisme (version
1.0) ». In : Paris, Octobre (1988) (cf. p. 101).
[3] A. D. Birrell et B. J. Nelson. « Implementing remote procedure calls ». In : Proceedings of the ninth ACM
symposium on Operating systems principles. 1983, p. 3 (cf. p. 3).
[4] M. W. Blasgen et K. P. Eswaran. « Storage and access in relational data bases ». In : IBM Systems Journal
16.4 (1977), p. 363–377 (cf. p. 21).
[5] P. Borne, P. Vanheeghe et E. Duflos. Automatisation des processus dans l’espace d’état : Cours et exercices
corrigés. T. 19. Editions Technip, 2007 (cf. p. 4).
[6] S. Bouzefrane. LES SYSTEMES D’EXPLOITATION : COURS ET EXERCICES CORRIGES UNIX, LINUX et
WINDOWS XP avec C et JAVA. 2003 (cf. p. 4).
[7] C.-W. Chou. Housing assembly for extractable redundant array of independent disks. US Patent 6,392,884.
2002 (cf. p. 112).
[8] W. Coy. « Soft Engines—Mass-Produced Software for Working People ? » In : Software development and
reality construction. Springer, 1992, p. 269–279 (cf. p. 8).
[9] J. Delacroix. Linux-4e éd. : Programmation système et réseau-Cours et exercices corrigés. Dunod, 2016
(cf. p. 4).
[10] Z. Ebrahim. Method and apparatus for implementing hardware protection domains in a system with no
memory management unit (MMU). US Patent 5,987,557. 1999 (cf. p. 157).
[11] G. C. Hunt, G. Cermak et R. J. Stets Jr. Operating system application programming interfaces and methods
of using operating systems. US Patent 7,334,235. 2008 (cf. p. 3).
[12] D. Lea. « A java fork/join framework ». In : Proceedings of the ACM 2000 conference on Java Grande. 2000,
p. 36–43 (cf. p. 51).
[13] M. K. McKusick et al. « A fast file system for UNIX ». In : ACM Transactions on Computer Systems (TOCS)
2.3 (1984), p. 181–197 (cf. p. 112).
[14] S. Patel et Y. N. Gopalan. Transaction-safe FAT file system improvements. US Patent 7,363,540. 2008 (cf.
p. 111).
[15] T. Petazzoni. « Gestion des interruptions ». In : (2008) (cf. p. 122).
[16] A. P. U. Siahaan. « Comparison analysis of CPU scheduling : FCFS, SJF and Round Robin ». In : Interna-
tional Journal of Engineering Development and Research 4.3 (2016), p. 124–132 (cf. p. 70).
[17] A. Silberschatz, P. B. Galvin et G. Gagne. Operating system concepts essentials. John Wiley & Sons, Inc.,
2014 (cf. p. 4).
[18] R. M. Stallman. « Le système d’exploitation du projet GNU et le mouvement du logiciel libre ». In :
Behlendorf et alii 1999 (1999), p. 61–82 (cf. p. 3).
[19] B. D. Veerasamy et G. Nasira. « Java Native Intel Thread Building Blocks for Win32 Platform ». In : Asian
Journal of Information Technology 13.8 (2014), p. 431–437 (cf. p. 51).
[20] Z. Wang et al. Print job spooling and distribution system. US Patent 7,593,125. 2009 (cf. p. 100).

159
BIBLIOGRAPHIE

1. https://www.baeldung.com/java-fork-join

2. https://www.javahelps.com/2015/01/forkjoin-framework.html

3. https://stackoverflow.com/questions/2814838/how-do-i-write-tasks-parallel-code

4. https://www.whoishostingthis.com/resources/os-development/

160