[PDF] INF3600 Systèmes dexploitation

View - Download INF3600 Systèmes dexploitation

Previous PDF

Next PDF

INF3600

Systèmes d'exploitation

Hanifa Boucheneb et Juan Manuel Torres-Moreno

Département de génie informatique

École Polytechnique de Montréal

version 3.90

16 avril 2003

2

Préface

C Edocument représente la formalisation des notes de coursINF3600- Systèmes d"exploitation, enseignéau Départementdegénie informa- tique de l"École Polytechnique de Montréal. Ce texte et les nombreuses applications qu"il contient visent à donner

à l"étudiant

1 une idée, à la fois, assez claire que vaste de ce que sont les systèmes d"exploitation, notamment leur importance dans toute formation en informatique. Il s"adresse indistinctement aux étudiants en génie infor- matique, informatique, génie électrique ou sciences. Le document aborde l"ensemble des thèmes liés aux systèmes d"exploi- tation réels.Lesaspects théoriquesprésentésdans ce document constituent une synthèse des nombreux ouvrages qui existent dans la littérature. Par contre, les aspects pratiques ont systématiquement fait l"objet d"un déve- loppement privilégié bien adapté au matériel utilisé dans nos laboratoires. En effet, ce document est composé de nombreux exemples de programmes qui contribuent à mieux comprendre les fonctionnalités des systèmes d"ex- ploitation. Pour des raisons strictement pédagogiques, et eu égard à la complexité de la matière (l"importance de l"information, la multitude de concepts...)nous avons privilégié une approche de type didactique. C"est ainsi que nous présentons: - Lesconceptsprincipauxetlestechniquesfondamentalesdessystèmes d"exploitation. - Les modules de base d"un système d"exploitation moderne. - Les interactions entre ces modules et les problèmes liés à leurs im- plantations ainsi que les solutions adoptées dans les systèmes mo- dernes.

1. Afin de simplifier le texte, seul le masculin a été utilisé pour désigner toute personne

sans distinction du genre. 3 4 Nous avons utilisé les systèmes d"exploitationUnixetGNU/Linuxpour illustrer nos exemples. Nous suggérons aussi de lectures qui pourront en- richir la matière vue. Ce document est un support pédagogique " vivant » aussi bien pour les enseignants que pour les étudiants. Il est, en effet, appelé à faire l"objet d"une actualisation permanente tant par les suggestions attendues des uns et des autres - à la fois, pour les améliorations à apporter et les exercices - que de la prise en compte de nouvelles réalités. Il va desoi qu"un texten"estjamais exemptd"erreurs,quand bien même on s"entoure de toutes les précautions pour les éviter. Nous serions donc très reconnaissants aux lecteurs de nous signaler toute erreur.

Montréal, automne 2002 | hiver 2003

Hanifa Boucheneb et Juan Manuel Torres-Moreno

Contenu

L Ematériel est divisé en plusieurs chapitres et sections. Tout au long du document, nous présentons des nombreux exemples clairs sur les applications et conséquences de chaque concept. Le Chapitre 1 présente un aperçu rétrospectif des concepts et fonction- nalités des systèmes d"exploitation. Un système d"exploitation est un pro- gramme qui doit permettre aux utilisateurs d"utiliser les fonctionnalités d"un ordinateur. Il doit aussi aider le programmeur à développer des lo- giciels de la façon la plus efficace possible. Dans les grosses machines, il est toujours en exécution. Le système constitue donc une interface entre l"utilisateur et la machine physique. Le Chapitre 2 introduit le système d"exploitation Unix et plus particu- lièrement son clone Linux. Le standard Posix est aussi introduit. La pré- sentation des commandes, processus et fichiers est faite en utilisant des exemples de programmation shell. Le Chapitre 3 défini le concept de processus, puisque tout le logiciel d"un ordinateur est organisé en un certain nombre de processus séquen- tiels. Les threads ou processus légers sont aussi introduits. De nombreux exemples sont présentés et programmés sous le standard Posix. Le Chapitre 4 présente l"ordonnancement ou planification des proces- sus. Dans un système multi-utilisateurs à temps partagé, plusieurs proces- sus peuvent être présents en mémoire centrale en attente d"exécution. Si plusieurs processus sont prêts,le systèmed"exploitation doit gérer l"alloca- tion du processeur aux différents processus à exécuter. On verra donc que c"est l"ordonnanceur qui s"acquitte de cette tâche. problème. Ces processus s"exécutent en parallèle sur un ordinateur (mo- noprocesseur ou multiprocesseurs) ou sur des ordinateurs différents. Ils doivent s"échanger des informations en établissant une vraie communica- tion interprocessus. Nous étudierons les plusieurs moyens de cette com- 5 6 munication: les variables communes, les fichiers communs, les signaux, les messages et les tubes de communication. sieurs processus s"exécutent en parallèle et partagent des objets comme la mémoire, les imprimantes, et d"autres. Le partage d"objets sans précaution particulière peut conduire à des résultatsimprévisibles. La solution au pro- blème s"appelle synchronisation des processus, thème qui sera abordé au

Chapitre 6.

Les paquets de communication entre processus (Inter Process Commu- nication) IPC qui offre le System V sont composésde trois mécanismes fon- damentaux: les sémaphores, la mémoire partagée et les files de messages. Bien que la communication IPC ne soit pas fondée sur les descripteurs de fichiers, il existe de nombreuses applications qu"en utilisent ces techniques puissantes. Le Chapitre 7 est donc consacré à la communication IPC. L"exécution d"un processus nécessite un ensemble de ressources qui lui sont attribuées par le système d"exploitation. L"utilisation d"une res- source passe par les étapes: demande, utilisation et libération. Des pro- blèmes peuvent survenir lorsque les processus obtiennent des accès exclu- sifs aux ressources. Par exemple, un processusdétient une ressource détient la ressource et attend la ressource. On a une situation d"inter- blocage car attendqui attend. Les deux processus vont attendre indéfiniment. Ce thème sera traité au Chapitre 8. La mémoire principale est le lieu où se trouvent les programmes et les données quand le processeur les exécute. On l"oppose au concept de mé- moire secondaire, représentée par les disques, de plus grande capacité, où les processus peuvent séjourner avant d"être exécutés. La nécessité de gé- rer la mémoire de manière optimale est toujours fondamentale, car en dé- pit de sa grande disponibilité, elle n"est, en général, jamais suffisante. Ceci en raison de la taille continuellement grandissante des programmes. Nous verrons dans le Le Chapitre 9 qu"il y a plusieurs schémas pourla gestionde la mémoire, avec leurs avantages et inconvénients. D"un autre côté, la mé- moire virtuelle est une technique qui permet d"exécuter des programmes dont la taille excède la taille de la mémoire réelle. Avec des techniques adé- quates, comme on verra dans le Chapitre 10, sa taille peut être très supé- rieure à celle de la mémoire physique. Un fichier désigne un ensemble d"informations stockées sur le disque. Le système de fichiers est la partie du système d"exploitation qui se charge de gérer les fichiers. La gestion consiste en la création, la suppression, les accès en lecture et en écriture, le partage de fichiers et leur protection en 7 contrôlant les accès. Ce thème sera consacre au Chapitre 11. Les fichiers de données sur les disques se répartissent dans des blocs de taille fixe. La lecture ou l"écriture d"un élément d"un fichier impliquera donc le transfert du bloc entier qui contient cet élément. Pour un accès ra- pide, on aura donc intérêt à implanter des techniques adéquates de sto- ckage et le partage de fichiers. Le Chapitre 12 traite ces questions. Nous verrons dans le Chapitre 13, que les ordinateurs disposent de pé- riphériques d"Entrées/Sorties (terminaux, disques, imprimantes, équipe- ments de communication, etc.). Le système d"exploitation peut considérer les périphériques comme des fichiers spéciaux, et donc intègre leur gestion au coeur du système de fichiers. Finalement, le Chapitre 14 se veut un aperçu à la réponse de pourquoi les systèmes d"exploitation distribués? Nous verrons que le développe- ment de microprocesseurs puissants et l"invention des réseaux locaux à haut débit ont permis de connecter des plusieurs ordinateurs pour échan- ger de de l"information. Ces ordinateurs connectés par un réseau de com- munication constituentun systèmedistribué. Ainsi, des conceptslogiciel et matériel seront présentés.La programmation des sockets sera présentéeen détail comme brique de base de la communication distribuée. 8

Table des matières

1 Introduction 25

1.1 Qu"est ce qu"un système d"exploitation? . . .......... 25

1.1.1 Le système d"exploitation . ............... 26

1.2 Évolution des systèmes d"exploitation............. 27

1.3 Interactions utilisateur/système . . ............... 32

1.4 Appels système .......................... 33

1.4.1 Les processus . . ..................... 33

1.4.2 Les fichiers......................... 34

1.5 Structure d"un système d"exploitation............. 35

1.5.1 Structure en couches................... 35

1.5.2 Structure monolithique . . ............... 36

1.5.3 Micro-kernel........................ 37

1.5.4 Le modèle client/serveur . ............... 37

1.5.5 Machines virtuelles.................... 38

1.6 Exercices.............................. 40

2 Introduction au système Unix/Linux 43

2.1 Bref historique . .......................... 43

2.2 Caractéristiques .......................... 44

2.2.1 Structure d"un système Unix/Linux .......... 45

2.3 Début de session......................... 47

2.3.1 Interpréteurs de commandes.............. 48

2.4 Commandes utiles d"Unix/Linux . ............... 48

2.5 Scripts shell . . .......................... 53

2.6 Editeurs d"Unix .......................... 60

2.7 Utilisateurs............................. 61

2.8 Fichiers et répertoires . . ..................... 61

2.9 Processus.............................. 63

2.10 Exercices.............................. 68

9

10 TABLE DES MATIÈRES

3 Processus et threads 71

3.1 Processus.............................. 71

3.1.1 États d"un processus................... 71

3.1.2 Implantation de processus . ............... 72

3.1.3 Les démons........................ 74

3.1.4 Création et terminaison de processus......... 74

3.2 ServicesPosixpour la gestion de processus .......... 75

3.3 Création de processus . ..................... 75

3.3.1 Création de processus avecsystem()........ 75

3.3.2 Création de processus avecfork().......... 76

3.3.3 La famille des appels systèmeexec.......... 83

3.3.4 Les appels systèmewait(),waitpid()etexit()86

3.3.5 Processus zombie ..................... 88

3.3.6 Commentaire sursystem().............. 90

3.4 Threads............................... 95

3.4.1 Avantages......................... 96

3.4.2 Threads utilisateur et noyau ............... 97

3.5 ServicesPosixde gestion de threads.............. 97

3.6 Threads sous Unix (Solaris 2).................. 106

3.7 Exercices.............................. 111

4 Ordonnancement des processus 113

4.1 Introduction . . .......................... 113

4.2 Types d"ordonnanceurs . ..................... 114

4.3 Objectifs de l"ordonnanceur d"un système multi-utilisateur . 116

4.4 Ordonnanceurs non préemptifs................. 116

4.5 Ordonnanceurs préemptifs................... 119

4.5.1 Ordonnancement du plus petit temps de séjour . . . 120

4.5.2 Ordonnancement circulaire ............... 120

4.5.3 Ordonnancement avec priorité............. 124

4.5.4 Files multiples (quantum variable) . .......... 125

4.6 Ordonnancement à deux niveaux . ............... 126

4.7 Ordonnancement des threads.................. 126

4.8 Cas d"étude . . .......................... 127

4.8.1 MS-DOS .......................... 127

4.8.2 Unix . . .......................... 128

4.8.3 Linux . . .......................... 129

4.9 Exercices.............................. 132

TABLE DES MATIÈRES 11

5 Communication interprocessus 135

5.1 Variables et fichiers communs.................. 135

5.2 Les signaux . . .......................... 136

5.2.1 Services de signaux.................... 137

5.3 Les messages . . .......................... 147

5.3.1 Tubes de communication . ............... 147

5.3.2 Tubes sans nom . ..................... 147

5.3.3 Tubes de communication nommés . .......... 154

5.4 Sockets............................... 158

5.5 Exercices.............................. 160

6 Synchronisation des processus 165

6.1 Introduction . . .......................... 165

6.2 Objets et sections critiques.................... 166

6.3 Masquage des interruptions................... 168

6.4 Exclusion mutuelle par attente active.............. 169

6.4.1 Les variables de verrouillage.............. 169

6.4.2 L"alternance........................ 170

6.4.3 Solution de Peterson................... 171

6.4.4 L"instruction TSL ..................... 173

6.4.5 Commentaires sur l"attente active . .......... 174

6.5 PrimitivesSLEEPetWAKEUP.................. 175

6.6 Problème du producteur et du consommateur........ 176

6.6.1 Critique des solutions précédentes . .......... 178

6.7 Sémaphores . . .......................... 178

6.8 ServicesPosixsur les sémaphores . ............... 179

6.8.1 Problème des philosophes . ............... 184

6.8.2 Problème des rédacteurs et des lecteurs........ 189

6.9 Compteurs d"événements.................... 194

6.9.1 Producteur/consommateur ............... 194

6.10 Moniteurs............................. 196

6.10.1 Producteur/consommateur ............... 196

6.11 Échanges de messages . ..................... 197

6.12 Producteur/consommateur par tubes............. 197

6.13 Exclusion mutuelle (mutex) de threads............. 199

6.14 Sémaphores avec System V (Solaris).............. 204

6.15 Exercises.............................. 213

12 TABLE DES MATIÈRES

7 Communications IPC System V 219

7.1 Files de messages......................... 219

7.1.1 Génération des clés.................... 220

7.1.2 Fonctions de manipulation de files . .......... 221

7.1.3 Monitorisation . ..................... 226

7.2 Structure de messages . ..................... 227

7.2.1 Buffer de message.................... 227

7.2.2msgdu noyau . . ..................... 228

7.2.3ipc_permdu noyau................... 229

7.3 Mémoire partagée......................... 236

7.4 Sémaphores . . .......................... 240

7.5 Exercices.............................. 249

8 Interblocages 251

8.1 Les processus et les ressources.................. 251

8.2 Définition d"un interblocage................... 252

8.2.1 Conditions nécessaires pour l"interblocage . . . . . . 254

8.3 Graphe d"allocation des ressources ............... 255

8.3.1 Réduction du graphe d"allocation des ressources . . . 256

8.4 Traitement des interblocages................... 257

8.5 La détection et la reprise ..................... 258

8.5.1 Algorithme de détection des interblocages . . . . . . 259

8.5.2 La reprise des interblocages ............... 260

8.6 L"évitement des interblocages.................. 261

8.6.1 Algorithme du banquier . . ............... 261

8.7 La prévention des interblocages . . ............... 262

8.8 Exercices.............................. 264

9 Gestion de la mémoire 269

9.1 Introduction . . .......................... 269

9.1.1 Rappels sur la compilation ............... 269

9.1.2 La gestion de la mémoire . ............... 271

9.2 Système monoprogrammé.................... 272

9.2.1 Machine nue........................ 272

9.2.2 Moniteur résident.................... 272

9.3 Système multiprogrammé.................... 274

9.3.1 Translation des adresses . . ............... 275

9.4 Swapping............................. 276

9.5 Partitions fixes sans va-et-vient . . ............... 277

9.5.1 Registres limite . ..................... 278

TABLE DES MATIÈRES 13

9.5.2 Registres de base et limite . ............... 278

9.5.3 Fragmentation . ..................... 280

9.5.4 Files d"entrée . . ..................... 280

9.6 Partitions variables et va-et-vient . ............... 283

9.6.1 Gestion de la mémoire par table de bits........ 286

9.6.2 Gestion de la mémoire par liste chaînée........ 287

9.6.3 Algorithme utilisant deux listes séparées....... 289

9.6.4 Gestion de la mémoire par subdivision........ 289

9.7 Allocation d"espace de va-et-vient ............... 290

9.8 Projection de fichiers en mémoire . ............... 291

9.9 ServicesPosixde projection de fichiers............. 291

9.9.1 Projection d"un fichier.................. 292

9.9.2 Libération de la projection . ............... 292

9.10 Note sur MS-DOS......................... 295

9.11 Exercices.............................. 296

10 Mémoire virtuelle 299

10.1 Introduction . . .......................... 299

10.2 Pagination pure .......................... 301

10.2.1 Unité de gestion de la mémoire (MMU)........ 302

10.2.2 Accès à la table de pages . . ............... 306

10.3 Algorithmes de remplacement de page............. 308

10.3.1 Remplacement de page optimal . . .......... 308

10.3.2 Remplacement de la page non récemment utilisée . . 309

10.3.3 Remplacement de page FIFO.............. 309

10.3.4 Remplacement de page de l"horloge .......... 310

10.3.5 Remplacement de la page la moins récemment utilisée 311

10.4 Nombre de cases allouées à un processus . .......... 311

10.4.1 Anomalie de Belady................... 311

10.5 Écroulement du système ..................... 312

10.6 Retour sur instructions . ..................... 312

10.7 Segmentation . .......................... 312

10.8 Segmentation paginée . ..................... 313

10.9 Mémoire cache .......................... 314

10.10Cas d"étude . . .......................... 314

10.10.1 Unix . . .......................... 314

10.10.2 Linux . . .......................... 316

10.10.3 MS-DOS .......................... 320

10.11Exercises.............................. 321

14 TABLE DES MATIÈRES

11 Système de fichiers 323

11.1 Introduction . . .......................... 323

11.1.1 Qu"est ce qu"un fichier? . . ............... 323

11.1.2 Cycle de vie d"un fichier . . ............... 324

11.1.3 Types de fichiers ..................... 324

11.2 Accès aux fichiers......................... 325

11.2.1 Attributs des fichiers................... 325

11.2.2 i-noeuds .......................... 326

11.3 ServicesPosixsur les fichiers.................. 326

11.3.1 Transfert rapide de données ............... 344

11.4 Répertoires............................. 346

11.5 ServicesPosixsur les répertoires . ............... 346

11.6 Répertoires sur Unix System V . . ............... 350

11.7 Exercises.............................. 353

12 Stockage et partage de fichiers 355

12.1 Stockage des fichiers . . ..................... 355

12.1.1 Allocation contiguë.................... 355

12.1.2 Liste chaînée........................ 356

12.1.3 Table d"i-noeuds . ..................... 357

12.2 Le système de fichiers/proc.................. 358

12.3 Partage de fichiers......................... 361

12.3.1 Liens physiques . ..................... 362

12.3.2 Liens symboliques.................... 364

quotesdbs_dbs20.pdfusesText_26

[PDF] Introduction aux systèmes informatiques Eduardo Sanchez - Anciens Et Réunions

[PDF] Introduction aux systèmes informatiques Socrative Rôle - e - Espèces En Voie De Disparition

[PDF] Introduction aux systèmes pile à combustible - Le Style Et La Mode

[PDF] Introduction aux systèmes répartis - France

[PDF] Introduction aux tableaux personnalisés avec SPSS Tables

[PDF] Introduction aux Théories de la Gravitation Cours: Physique Master 1 - Cigares

[PDF] introduction aux travaux pratiques : mesures et incertitudes

[PDF] Introduction Ce présent chapitre décrit le système d`échappement - Gas-Oil

[PDF] Introduction Ceux qui ont tant soit peu étudié les sciences

[PDF] introduction Changer les noms des rues de Paris

[PDF] INTRODUCTION CHAPITRE 1 : LA NOTION D`IMPÔT CHAPITRE 2

[PDF] Introduction Chauffage Climatisation Surpression

[PDF] introduction consignes de securite importantes - Euro

[PDF] Introduction course : Network Overview www.enac.fr - Anciens Et Réunions

[PDF] Introduction dans l`alimentation des tout-petits - Cartes De Crédit