Academie pro€¦ · Web viewPar : Ben Mahmoud & Shimi- 3 - Guide du cours Ce cours s'adresse aux étudiants de la 1ème année licence technologies de l’informatique, tronc commun

Systèmes d’exploitation 1

Guide du cours

Ce cours s'adresse aux étudiants de la 1ème année licence technologies de

l’informatique, tronc commun. Il sera enseigné en tant que élément constitutif de l’unité

d’enseignement fondamentale « Systèmes 2 ». Il sera assuré pendant 15 semaines à raison

d’une heure et demie de cours et travaux dirigés par semaine. Il comporte quatre leçons.

I. OBJECTIFS DU COURS

Se familiariser avec les concepts et les techniques fondamentales des systèmes

d'exploitation.

Expliquer et analyser le fonctionnement des différents modules du système

d'exploitation.

Utiliser et/ou adapter les techniques et les services du système d'exploitation

pour concevoir des codes plus fiables et plus performants.

II. PRE-REQUIS

ECUE : Systèmes logiques;

ECUE : Algorithmique & Structures de données 1 ;

ECUE : Atelier Systèmes 1

III. BIBLIOGRAPHIE CONSEILLÉE

1. Andrew Tanenbaum, « Systèmes d’exploitation », Edition Pearson 3ème édition,

2008

2. Leila Baccouche, « Au Coeur des Systèmes d’Exploitation des Ordinateurs :

Concepts de base et Exercices Résolus », Centre de Publications universitaire

2003.

3. Mohamed Said Ouerghi, « Principes des Systèmes d’Exploitation », Centre de

Publications universitaire 2003.

4. Samia Bouzefrane, « Les systèmes d’exploitation, Unix, Linux et Windows XP

avec C et Java », Edition DUNOD, 2007

IV. SOMMAIRE DU COURS

Leçon 1 : Principes et histoire des systèmes d’exploitationPar : Ben Mahmoud & Shimi - 1 -


I. Introduction

II. Rappels

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

IV. Historique des systèmes d’exploitation

V. Structuration d’un système d’exploitation

VI. Fonctionnalités d’un système d’exploitation

VII. Conclusion

Leçon 2 : Gestion des processus

I. Introduction

II. Généralités sur les processus

III. Activités des processus

IV. Stratégie d’ordonnancement

V. Les processus sous unix

VI. Conclusion

Leçon 3 : Gestion de la mémoire centrale

I. Introduction

II. Généralités sur la mémoire centrale

III. Méthodes de partitionnement

IV. Les stratégies d’allocation

V. Conclusion

Leçon 4 : Systèmes de gestion des fichiers

I. Introduction

II. Fichiers et répertoires

III. Gestion des disques

IV. Organisation logique des fichiers

V. Organisation physique des fichiers

VI. Conclusion

Par : Ben Mahmoud & Shimi - 2 -


Leçon 1 : Principes et histoire des systèmes

d’exploitation

Objectif généralConnaître l’histoire et les principes de base des systèmes

d’exploitation.

Objectifs

spécifiques

Parcourir l’histoire des ordinateurs.

Parcourir l’histoire des systèmes d’exploitation.

Savoir définir un système d’exploitation par ses différents

rôles.

S’initier aux principes de base d’un système d’exploitation.

Volume horaire Cours : 3h

Mots clésSystème, services, processus, mémoire, fichiers, matériels,

programmes,…



I. Introduction

Dès l’apparition des systèmes d’exploitation, aux années 60, le monde

informatique a connu un large changement dans les méthodes d’utilisation et de

développement des ordinateurs.

Ce premier chapitre introductif mettra l’accent sur l’histoire des systèmes

d’exploitation tout rappelant certaines notions. Ensuite, les principes de base des

systèmes d’exploitation seront décrits afin de mieux comprendre l’utilité des

systèmes.

II. Rappels

1. Définitions

Un ordinateur est une machine de traitement de l’information. Il est capable

d’acquérir de l’information, de la stocker, de la transformer en effectuant des

traitements quelconques, puis de la restituer sous une autre forme. Le mot

informatique vient de la contraction des mots information et automatique.

On appelle information tout ensemble de données. On distingue

généralement différents types d’informations : textes, nombres, sons, images, etc...

Toute information est manipulée sous forme binaire (ou numérique) par l’ordinateur.

Un programme est une suite d’instructions élémentaires, qui vont être

exécutées dans l’ordre par le processeur. Ces instructions correspondent à des

actions très simples, comme additionner deux nombres, lire ou écrire une case

mémoire, etc...

2. Architecture de base d’un ordinateur



Un ordinateur est constitué principalement de 2 éléments essentiels : la

mémoire centrale et le processeur. La mémoire centrale (MC en abrégé) permet de

stocker de l’information (programmes et données), tandis que le processeur exécute

pas à pas les instructions composant les programmes.

2.1. Le processeur

Le processeur est un circuit électronique complexe qui exécute chaque

instruction très rapidement. Toute l’activité de l’ordinateur est cadencée par une

horloge unique, de façon à ce que tous les circuits électroniques travaillent

ensembles. La fréquence de cette horloge s’exprime en MHz (millions de battements

par seconde). Par exemple, un ordinateur “PC Pentium 133” possède un processeur

de type Pentium et une horloge à 133 MHz.

Le processeur est capable d’exécuter des programmes en langage machine,

c’est à dire composés d’instructions très élémentaires suivant un codage précis.

Chaque type de processeur est capable d’exécuter un certain ensemble

d’instructions.

2.2. La mémoire centrale (MC)

La mémoire centrale est divisée en cases de taille fixe (par exemple 8 bits)

utilisées pour stocker instructions et données d’un programme. En principe, la taille

d’une case mémoire pourrait être quelconque ; en fait, la plupart des ordinateurs en

service aujourd’hui utilisent des emplacements mémoire d’un octet (byte en anglais,

soit 8 bits, unité pratique pour coder un caractère par exemple).

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

Selon plusieurs auteurs, un système d’exploitation (SE en abrégé) est défini

comme étant un ensemble de programmes ayant pour tâche de faire fonctionner un



ordinateur. Un système d’exploitation jouera ainsi le rôle d’intermédiaire entre

l’utilisateur et la machine.

On peut dire, à ce stade, que le système d’exploitation joue le rôle d’une

machine virtuelle (par rapport à la machine physique) qui va cacher la complexité du

matériel.

IV. Historique des systèmes d’exploitation

Sans trop détailler l’histoire des systèmes d’exploitation, on va se limiter à une

présentation brève des principales dates donnant lieu à des changements important

dans l’histoire de l’informatique et des systèmes. Cette histoire peut être classée en

cinq générations :

La première génération : le traitement par lots ;

La deuxième génération : la multiprogrammation ;

La troisième génération : le temps partagé ;

La quatrième génération : le temps réel ;

La cinquième génération : les systèmes distribués ;

Activité :

Pour mieux connaître l’histoire des systèmes d’exploitation, je propose aux

étudiants de faire une activité de recherche et une synthèse des différentes

générations mentionnées ci-dessus.

V. Structuration d’un système d’exploitation

On a déjà vu précédemment que le système d’exploitation est un

intermédiaire entre l’utilisateur (qui va utiliser les applications de l’ordinateur) et le

matériel (qui est composé de périphériques et organes internes et externes). Ce rôle



nous mène à dire que le SE est formé d’un ensemble de parties ou couches. La

structuration d’un SE est sa représentation en couches.

Le noyau est la partie essentielle et délicate d’un SE. Il possède les

caractéristiques suivantes :

Réside en mémoire

De petite taille

Gérer le processeur

Gérer la mémoire

Gérer les interruptions

La figure suivante la structuration en couches du SE.


Matériels

Noyau

Autres couches

Utilitaires

Applicatifs

Figure 1 - Structuration en couches d'un SE


VI. Fonctionnalités d’un système d’exploitation

On parle de fonctionnalités pour mentionner les services offerts par le système

d’exploitation pour assurer l’interfaçage entre l’utilisateur et le matériel. Ces services

peuvent être classés en deux catégories comme suit :

1. Gestion des processus

Un processus est une entité créé lors de l’exécution d’un programme. Cet

entité possède un cycle de vie allant de sa création jusqu’à sa terminaison.

Au cours de son cycle de vie, un processus transite d’un état à un autre. Ces

états peuvent être résumés maintenant comme suit :

Créé : un processus vient d’être créé (un programme est lancé en

exécution) ;


Services d’un système d’exploitation

Services communs :Services résidents en MC ;

Gestion des processus ;Gestion de la mémoire ;

Gestion des fichiersGestion des périphériquesGestion de l’interface H/M

Services spécifiques :Services résidents en MSOutils de développementOutils de communication ;

Outils de bureautique ;Outils d’administration ;

Figure 2 – Services d’un SE

Créé

Prêt

Bloqué

Actif

Terminé


Prêt : le processus est en attente d’être exécuté par le processeur ;

Actif : le processus est élu pour exécution ;

Bloqué : le processus est en attente d’un évènement ;

Terminé : le processus achève son exécution.

Le cycle représenté ci-dessus décrit celui des processus dans un système

mono-processeur (un seul processeur) utilisant une stratégie d’ordonnancement

basée sur le partage de temps.

Entre autre, les processus peuvent coopérer entre eux pour réaliser une tâche

commune. Cette coopération nécessite parfois une synchronisation et une

communication inter-processus.

La gestion des processus est l’ensemble des activités relatives au traitement du

processus. Ces activités comportent les opérations suivantes : création,


Figure 3 - Cycle de vie d'un processusFigure 2 - Cycle de vie d'un processus


ordonnancement, activation, terminaison, synchronisation et communication des

processus.

2. Gestion de la mémoire centrale

Nous avons déjà vu que la mémoire centrale est composée de cellules utilisées

pour stocker les données et les instructions d’un programme. En effet, l’exécution

d’un programme se fait en mémoire centrale en allouant un espace suffisant pour en

contenir les données (constantes et variables) et les instructions du code source.

On rappelle que la mémoire centrale est initialement vide avant la mise en

tension de l’ordinateur. Après le démarrage de la machine, le système d’exploitation

occupe initialement une partie de l’espace mémoire dans laquelle résident les

services communs du système. Ensuite, au fur et à mesure de l’utilisation de

l’ordinateur, les applicatifs de l’utilisateur occupent aussi des espaces mémoire. Ces

espaces forment la partie utilisateur de la mémoire centrale.

Le service de gestion de la mémoire centrale peut comporter les actions

suivantes :

Diviser de la mémoire en deux parties ou zones : zone système et zone

utilisateur ;

Allouer les espaces mémoires pour les programmes en exécution ;

Charger les processus dans les espaces alloués ;

Vérifier l’intégrité des espaces mémoire réservés.

3. Gestion des fichiers

Un fichier peut être défini comme étant une unité de stockage logique

de l’information.

Pratiquement, le fichier est le seul et unique moyen logique pour

sauvegarder les données.



Un fichier peut avoir les attributs suivants : nom, taille, type, protection,

date, propriétaire,…

Un fichier peut être classé en deux catégories selon la nature des

informations y contenues : fichiers programmes et fichiers de données.

La gestion des fichiers est l’ensemble des actions relatives à leur existence :

création, édition, recherche, duplication, suppression, impression, compression,…

4. Gestion des périphériques

Un périphérique est un dispositif connecté à l’ordinateur pour assurer des

fonctionnalités à celui-ci. Le périphérique joue un rôle essentiel pour assurer le

dialogue entre l’ordinateur et son milieu externe. Généralement, lorsqu’on ajoute un

nouveau périphérique à l’ordinateur, on doit installer sur le système un programme

spécifique appelé pilote permettant au système d’exploitation de reconnaître ce

périphérique et de l’utiliser correctement.

Les services de gestion de périphériques peuvent concerner l’installation, le

paramétrage et l’utilisation des périphériques.

5. Gestion de l’interface homme/machine

Le dialogue entre l’utilisateur et l’ordinateur peut être géré physiquement

moyennant les périphériques. La bonne utilisation de ces derniers assure le bon

fonctionnement du système et offre une communication claire et précise.

L’utilisateur peut ainsi communiquer avec la machine à travers des ordres et des

commandes lancées par les périphériques d’entrée et à travers aussi des résultats

aperçus par le biais des périphériques de sortie.

La gestion de l’interface homme/machine définit les moyens et les outils mis en

œuvre afin que l’homme puisse communiquer et contrôler la machine.



6. Services spécifiques

Parmi les services spécifiques d’un SE, on peut citer les tâches d’exploitation

standards de programmation (éditeurs de textes, traducteurs, éditeurs de liens,

compilateurs,…), de gestion de fichiers (formatage de volumes, copies de volumes et

de fichiers, tris de fichiers, conversion de support, archivage de supports,…) , de

gestion de tâches d’administration du système (gestion de mots de passe, gestion et

contrôle des accès , installation de nouvelles applications ou versions d’un logiciel,

outils d’évaluation de performances,…), de gestion de tâches d’un bureau (outils de

communication, outils de bureautique,…),etc.

VII. Conclusion

En résumé de ce chapitre, nous avons essayé de connaître les principes de base

d’un système d’exploitation. Les chapitres suivants seront consacrés à détailler

certains services communs du SE en commençant par la gestion des processus.



Leçon 2 : Gestion des processus

Objectif général Apprendre les notions de bases relatives aux processus.

Objectifs

spécifiques

Comprendre les différents états d’un processus.

Débuter avec les stratégies et les algorithmes

d’ordonnancement.

Etudier les processus sous le système unix.

Volume horaireCours : 3h

TD : 1,5h

Mots clésSystème, services, processus, mémoire, fichiers, matériels,

programmes,…



I. Introduction

La gestion des processus est l’une des fonctionnalités les plus importantes et

critiques d’un système d’exploitation. La gestion des processus rassemble des

activités relatives au traitement du processus. Ce chapitre traitera en premier lieu le

cycle de vie d’un processus. En second lieu, nous verrons les stratégies

d’ordonnancement des processus à travers des algorithmes et des exemples. Nous

traiterons, en dernier lieu, les processus sous le système unix.

II. Généralités sur les processus

1. Définition d’un processus :

Un processus est l’entité créée par le système d’exploitation pour l’exécution

d’un programme. Chaque fois qu’on lance un programme, un processus est créé

durant l’exécution de ce programme.

Un processus est identifié par un numéro unique que l'on appelle le PID

(Process IDentifier)

2. Ressources nécessaires d’un processus :

Une ressource est une entité nécessaire à l’exécution d’un processus. Elle peut

être une ressource matérielle (imprimante, disque, processeur,…) ou bien une

ressource logicielle (fichier, base de données, programme,…).

On distingue les ressources privées et les ressources partageables.

Les ressources privées sont les ressources propres au processus. Pour cela,

elles ne posent pas de problèmes.

Les ressources partageables posent des problèmes d’accès puisque il y-a

compétition entre les processus pour les acquérir.


Créé

Prêt

Bloqué

Actif

Terminé


Une ressource (si elle est bien sûr disponible) est allouée au processus lors de

sa création.

3. Cycle de vie d’un processus :

On rappelle qu’un processus possède un cycle de vie allant de sa naissance à sa

mort passant par divers phases d’activité et d’attente. Ce cycle est appelé aussi un

diagramme d’états-transitions des processus. La figure suivante illustre ce diagramme

dans le cadre d’un système mono processeur avec stratégie de partage de temps

entre les processus.

III. Activités des processus

1. Création d’un processus :

Lors de sa création, un processus reçoit un numéro unique qui sert à le

désigner et qui permet d’accéder à son descriptif le principale problème s’impose est

l’allocation des contextes et des noms des processus

2. Destruction d’un processus :


Figure 4 - Cycle de vie d’un processus


La destruction d’un processus prend lieu lorsqu’on termine d’une façon

normale ou anormale un programme. En conséquent, la libération des ressources qui

lui étaient allouées est un résultat obligatoire. Parmi ces ressources, seul les noms et

le contexte sont directement gérés par le noyau : les autres ressources tel que les

fichiers sont acquises par des mécanismes spécifique réalisés par la gestionnaire de la

mémoire, de fichier,…

3. Suspension d’un processus :

La suspension d’un processus permet à celui-ci de contrôler par exemple

l’activité de son fils, en finissant avec force son exécution. Un autre cas se réalise

lorsqu’un processus demandera explicitement sa suspension momentanée jusqu’à ce

qu’un événement particulier attendu soit signalé. Dans tous les cas le processus

interrompu sera transféré dans une file spécifique à l’événement attendu

4. Reprise d’un processus :

La reprise est une suite éventuelle à la suspension d’un processus. Dans ce cas le

processus appelant réveillera son processus fils suspendu et ce après modification

éventuelle de son contexte.

IV. Stratégie d’ordonnancement :

Un système informatique commun peut posséder un processeur unique ou

plusieurs processeurs. La gestion des processus s’occupe alors de l’allocation des

processeurs aux processus créés.

Une stratégie d’ordonnancement est implémenté réellement moyennant des

algorithmes dites algorithmes d’ordonnancement.


Processeur


L’objectif d’un algorithme d’ordonnancement est d’optimiser une des grandes

temporelles suivantes, sachant que l’on intéresse par ailleurs au taux de l’utilisation

de l’unité centrale et au débit moyen :

- Le temps de traitement moyen décrit la moyenne des intervalles de temps

séparant la soumission et l’accomplissement d’un processus.

TTM= ∑processus

❑

(datede find ' exécution−date d' arrivée)❑❑ nombrede processus

- Le temps d’attente moyen est le temps est la moyenne des durées de temps

que les processus ont passé dans la file d’attente des processus à l’état prêt.

TAM= ∑processus

❑

(date début d ' exécution−date d ' arrivée)❑❑ nombre de processus

1. Algorithme d’ordonnancement sans réquisition :

a. Ordonnancement FCFS (first come first served)

On l’appelle aussi FIFO (pour first in first out) ou premier arrivé premier servi.

Cet algorithme traite les processus selon l’ordre de leur soumission (date arrivée)

sans prendre compte de leur temps d’exécution. L’organisation de la file d’attente

des processus prêt est donc tout simplement FIFO.

Terminé

File d’attente « prêt »

b. Ordonnancement SJF (shortest job first)

SJF, ou la plus courte durée d’exécution, choisit les processus ayant le plus court

temps d’exécution sans réellement tenir compte de leur date d’arrivée. Cet

algorithme est non implémentable à cause de l’aspect statistique de ses calculs.


… P4 P

3

P2 P

1


Néanmoins, il est intéressant en vue d’étudier des performances de l’algorithme

d’ordonnancement réellement mis en œuvre par le système

c. Ordonnancement avec tourniquet ou Round Robin

On procède ici à un recyclage des processus sur le processeur tant que les

processus ne sont pas terminés.

Lorsque un processus est élu on lui attribue une tanche de temps fixe appelé

quantum laquelle il s’exécute Au bout de ce temps on ne poursuit plus l’exécution

du processus on lui retire donc le processeur et on le réinsère dans la file des

processus prêt. Là il devra attendre sa prochaine élection.

Terminé

File d’attente « prêt »

Si le quantum n’est pas épuisé,

alors retour à la file d’attente

2. Application

Soit la liste des processus suivante :

Processus P1 P2 P3 P4

Date d’arrivée 0 1 2 3

Durée d’exécution 5 4 2 2

Pour chaque stratégie d’ordonnancement : FCFS, SJF, Round Robin déterminer les

grandeurs suivantes : le temps de traitement moyen TTM et le temps d’attente

moyen TAM.


Processeur… P4 P

3

P2 P

1


a. Stratégie FCFS

Afin de calculer les deux grandeurs TTM et TAM, nous devons tout d’abord

tracer le diagramme de GANTT qui représente le graphique d’occupation du

processeur selon la politique d’allocation.

Diagramme de GANTT :

P1 P2 P3 P4

0 5 9 11 13 temps

Donc :

TTM = ((5-0)+(9-1)+(11-2)+(13-3)) / 4 = 32 / 4 = 8

TAM = ((0-0)+(5-1)+(9-2)+(11-3)) / 4 = 19 / 4 = 4,75

b. Stratégie SJF


P3 P4 P2 P1

2 4 6 10 15 temps

Donc :

TTM = ((4-2)+(6-3)+(10-1)+(15-0)) / 4 = 29 / 4 = 7,25

TAM = ((2-2)+(4-3)+(6-1)+(10-0)) / 4 = 16 / 4 = 4

c. Stratégie tourniquet

On suppose ici que le quantum est égal à 1. C'est-à-dire que chaque processus

possède un intervalle de temps qui vaut 1 unité de temps durant laquelle il est élu

par l’ordonnanceur pour exécution.




P1 P2 P3 P4 P1 P2 P3 P4 P1 P2 P1 P2 P1

0 1 2 3 4 5 …………………………………………. 11 12 13 temps

Donc :

TTM = ((13-0)+(12-1)+(7-2)+(8-3)) / 4 = 34 / 4 = 8,25

TAM = ((3+3+1+1)+(3+3+1)+(3)+(3)) / 4 = 21 / 4 = 5,25

V. Les processus sous unix

1. Contexte d'un processus :

On distingue des processus utilisateurs et des processus système. Ces derniers :

- ne sont sous le contrôle d'aucun terminal

- ont comme propriétaire le super utilisateur (processus démons). Ils restent

résidents en MC en attente d'une requête

- ils assurent des services généraux accessibles à tous les utilisateurs

- ils peuvent être créés au lancement du système ou à des dates fixées par

l'administrateur.

Un processus peut s'exécuter dans deux modes différents :

- mode utilisateur (user mode) : le processus n'accède qu'à son espace

d'adressage et n'exécute que des instructions ordinaires du programme

chargé.

- mode noyau ou système (kernel mode) : le processus exécute des

instructions n'appartenant pas au programme, mais au noyau. Il accède à

des données externes à son espace d'adressage. On peut passer en mode

noyau soit par une interruption appropriée, soit par la réalisation d'un



appel système par le processus lui-même (exemple : requête de lecture au

clavier dans le programme)

2. Structure d'un processus sous unix

Le noyau gère une table des processus, listable par la commande ps avec une

entrée par processus, et contenant des informations sur celui-ci. Cette entrée est

allouée à la création du processus et retirée à son achèvement.

Un processus est identifié par un pid (process identifier), entier de 0 à 32767

retourné par le noyau. Il est caractérisé aussi par sa priorité, son propriétaire et son

groupe propriétaire, son terminal de rattachement.

3. Ordonnancement d'un processus

L'ordonnanceur ou scheduler (gestionnaire des ressources et d'enchaînement des

processus) gère plusieurs processus concurremment et autorise le multitâche par

partage de temps. Il attribue des quanta de temps. A l'expiration de son quantum de

temps, le processus actif, s'il n'est pas terminé, sera obligé de relâcher le processeur.

Un autre processus est alors élu et attribué au processeur. Le processus suspendu

reprend son exécution quand son tour arrive à nouveau pour disposer du processeur.

Sous UNIX, l'horloge de l'ordonnanceur délivre 100 tops, ou cycles mineurs, par

seconde et un quantum, ou cycle majeur, correspond à plusieurs tops (par exemple

100, soit 1 seconde).

Un processus peut prendre l'un des 9 états décrits dans /usr/include/sys/proc.h),

parmi lesquels :

- actif : en mode utilisateur (pas de droit d'accès aux ressources du système)

ou en mode système (ou noyau)



- activable ou prêt à exécuter : en mémoire ou en zone de swap. Il est

éligible par l'ordonnanceur. Ces deux états sont codés R

- bloqué : en attente d'un événement (horloge, montage d'un disque,

résultat d'un autre processus, ...), en mémoire ou en zone de swap. Il ne

consomme pas de temps CPU. Il repasse à l'état activable dès que les

conditions le permettent. non prêt : en création ou zombie (désigné par Z,

le processus est achevé, mais son père n'en a pas encore connaissance). Il

ne consomme pas de temps CPU.

Figure 7 : Cycle de vie d’un processus sous unix

- 1 : le processus créé par fork a acquis les ressources nécessaires à son

exécution

- 2 : le processus vient d'être élu par l'ordonnanceur

- 3 : le processus revient d'un appel système ou d'une interruption

- 4 : le processus a réalisé un appel système ou une interruption est

survenue

- 5 : le processus se met en attente d'un événement (libération de ressource,

terminaison de processus par wait). Il ne consomme pas de temps UCPar : Ben Mahmoud & Shimi - 22 -


- 6 : l'événement attendu par le processus s'est produit

- 7 : conséquence d'un signal particulier

- 8 : réveil du processus par le signal de continuation

- 9 : le processus s'achève par exit, mais son père n'a pas pris connaissance

de sa terminaison. Il ne consomme pas de temps UC et ne mobilise que la

ressource table des processus

VI. Conclusion

Ce chapitre était consacré à la gestion des processus. Après avoir été élu par

l’ordonnanceur, un processus se charge en mémoire centrale pour s’exécuter. La

mémoire centrale représente le lieu d’exécution des processus. Le prochain chapitre

traitera en détail la gestion de la mémoire centrale.




Travaux Dirigés N° 1

Exercice 1

Dans un système monoprocesseur, on considère les processus suivants:

Processus Date d’arrivée Durée d’exécution

P1 0 8

P2 1 2

P3 2 4

P4 3 5

P5 3 6

1- Dessiner le diagramme de GANTT pour les politiques d’allocation suivantes:

a) Premier arrivé premier servi (FCFS)

b) Le plus court d’abord (SJF)

c) Tourniquet (Round Robin) avec quantum = 1

d) Tourniquet (Round Robin) avec quantum = 2

2- Calculer le temps d’exécution de chaque processus pour chacune des politiques

d’allocation.

3- Calculer le temps d’attente de chaque processus pour chacune des politiques d’allocation.

Exercice 2

On considère 4 processus, A, B, C, D. On suppose que l’exécution des processus

nécessite :

Pour A : 4 unités de temps

Pour B : 6 unités de temps

Pour C : 5 unités de temps

Pour D : 2 unité de temps

On suppose que :

A se présente en premier, à l’instant 0,

B se présente à l’instant 1,

C se présente à l’instant 3,



D se présente à l’instant 5.

Dans chacun des cas suivants, montrez comment les 4 processus vont utiliser le

processeur, déterminez le temps de traitement moyen et le temps d’attente moyen :

a. Si l’ordonnanceur fonctionne selon Premier Arrivée Premier Servi.

b. Si l’ordonnanceur fonctionne selon la plus courte durée d’exécution.

c. Si l’ordonnanceur utilise l'algorithme du tourniquet, avec un quantum de 2.



Leçon 3 : Gestion de la mémoire

Objectif généralConnaître quelques services de gestion de la mémoire

centrale.

Objectifs

spécifiques

Comprendre le principe d’utilisation de la mémoire

centrale.

Décrire les méthodes de partitionnement de la mémoire

centrale.

Connaître les stratégies d’allocation de la mémoire centrale.

Volume horaireCours : 1,5h

TD : 1,5h

Mots clés Mémoire centrale, zone, partitions, allocation,…



I. Introduction

Sans mémoire centrale, le système d’exploitation ne pourra jamais s’exécuter

et l’ordinateur ne fonctionnera pas. La mémoire centrale est l’espace d’exécution de

tous les programmes y compris le système d’exploitation.

Dans ce chapitre, nous verrons comment la mémoire centrale est partitionnée

et comment les programmes utilisateurs et systèmes sont affectés aux espaces

mémoire.

II. Généralités sur la mémoire centrale

Le service de gestion de la mémoire centrale divise de la mémoire en deux

zones : zone système qui contient les processus du système d’exploitation et zone

utilisateur qui contient les processus utilisateur.

zone système

zone utilisateurs

Figure 8 : Partitionnement de la mémoire centrale

Le gestionnaire de mémoire gère l'allocation de l'espace mémoire au système et aux

différents processus en cours d'exécution. Parmi ses tâches :

connaître les parties libres et occupées de la mémoire,

allouer de la mémoire aux processus qui en ont besoin,

récupérer la mémoire utilisée par un processus lorsque celui-ci se termine

traiter le « va-et-vient » entre le disque et la mémoire principale lorsque

cette dernière ne peut pas contenir tous les processus.Par : Ben Mahmoud & Shimi - 27 -


Le « Va-et-vient » est une technique qui consiste à déplacer les zones de la mémoire

sur le disque afin d’avoir de zones libres.

La partie suivante du cours traitera les schémas de partitionnement possibles de

la mémoire centrale ainsi que les stratégies d’allocation des espaces mémoires aux

différents processus demandant de l’espace.

III. Méthodes de partitionnement :

Le partitionnement de la mémoire consiste à diviser l’espace en des partitions de

taille fixe ou de taille variable. Dans notre cours, nous allons s’intéresser au

partitionnement de la mémoire dans le cadre de la multiprogrammation. Le cas des

systèmes mono-programmés ne sera pas traité puisque les processus sont exécutés

séquentiellement et un à la fois.

1. Partitions fixes :

Dans ce schéma de partitionnement, l’espace mémoire est divisée en un certain

nombre de zones de taille fixe, appelées des partitions. Une partition peut accueillir, à

un instant donné, un programme et un seul. La taille du programme est en tout cas

plus petite ou égale à celle de la partition choisie.



Figure 9 : Espace mémoire découpé en partitions fixes

2. Partitions variables :

Ici les parties de l’espace mémoire sont de tailles variables. La zone mémoire

allouée à un processus redevient libre après la distribution du processus. Ces espaces

forment des partitions (de tailles) variables.

Figure 10 : Placement initial en mémoire

La figure précédente montre la répartition initiale des processus dans l’espace

mémoire. Il est supposé que la taille de cette mémoire totalise 100 unités (exprimées

en Kilo ou Méga-octets), que le système d’exploitation nécessite 30% de cet espace

et que le reste est à partager entre les processus utilisateurs. Les processus sont

ordonnés dans une file d’attente selon leurs dates d’arrivées.

Lorsque certains processus se terminent, l’espace mémoire devient une

alternance de zones libres et de zones occupées de taille variable. La figure suivante

décrit une situation à l’issue de laquelle il y aura une formation d’un trou. Par : Ben Mahmoud & Shimi - 29 -


Figure 11 : Formation des trous

Pour remédier à l’augmentation du nombre de trous, une solution consiste à

grouper les zones libres selon deux techniques :

Concaténation des trous juxtaposés ;

Compactage des trous et de l’espace libre en un seul espace.

IV. Les stratégies d’allocation :

L’allocation d’un espace libre à un processus peut s’effectué selon plusieurs

stratégies.

1. Stratégie First-Fit :

Il s’agit de choisir, pour satisfaire une demande, le premier trou, dans l’ordre des

adresses, dont la taille est supérieure ou égale à la demande (autrement dit, on

cherche à allouer le premier trou qui convient). La figure suivante est un exemple

d’allocation selon ce principe.



Figure 12 : Stratégie First fit

2. Stratégie Best-Fit :

Il s’agit de choisir, pour satisfaire une demande, le plus petit trou dont la taille soit

suffisante pour répondre à la demande. On peut ainsi espérer ne pas fragmenter les

gros trous afin de satisfaire les demandes gourmandes en espace mémoire. La figure

suivante est un exemple d’allocation selon ce principe.



Figure 12 : Stratégie Best fit

3. Stratégie Worst-Fit :

Il s’agit de choisir, pour satisfaire une demande, le plus grand trou dont la taille

est largement supérieure à la demande. On peut ainsi espérer aboutir à un restant

dont la taille est suffisante pour satisfaire les petites demandes en espace mémoire.

La figure suivante est un exemple d’allocation selon ce principe.



Figure 13 : Stratégie Worst fit

V. Conclusion

Maintenant, nous avons vu deux services communs du système d’exploitation et

qui sont en étroite relation. Un autre concept est aussi important et sera abordé dans

le cadre du chapitre suivant, c’est le fichier.





Exercice 1

Dans le cadre d’un schéma de partitionnement de la mémoire centrale, on suppose

une allocation de type partition variable. La mémoire centrale est structurée de la façon

suivante :

Système

Libre (300K)

occupé

Libre (100K)

occupé

Libre (200K)

occupé

Libre (500K)

On suppose avoir la séquence suivante des demandes d’allocation : 150k, 200k, 100k, 300k,

150K. Donner l’état final de la mémoire avec les techniques First-fit, Best-fit et Worst-fit.

Conclure.

Exercice 2

On Considère les 5 processus du tableau suivant :

Processus Date d’arrivée Durée d’exécution Taille en MC

P1 0 8 200

P2 2 10 500

P3 4 13 250

P4 10 15 350

P5 11 6 600

On considère aussi une mémoire centrale structurée de la façon suivante :

Système

Libre (300K)

occupé

Libre (700K)



occupé

Libre (500K)

occupé

Libre (200K)

occupé

Libre (300K)

Donnez sous forme de diagrammes de temps l’évolution de l’état de la mémoire et de la file

de haut niveau, aux différentes étapes de traitement de ces processus, sous les hypothèses

suivantes :

Le mode d’allocation des trous pour la mémoire centrale est First Fit ;

L’ordonnancement des processus fonctionne selon la stratégie Premier Arrivé,

Premier Servi.



Leçon 4 : Système de gestion de fichiers

Objectif général Connaître les notions de base relatives aux fichiers.

Objectifs

spécifiques

Etudier le concept fichier et le concept fichier.

Comprendre la structure d’un disque et les opérations y liées.

Connaître l’organisation logique des fichiers.

Connaître l’organisation physique des fichiers.

Volume horaireCours : 1,5h

TD : 1,5h

Mots clésfichier, répertoire, disque dur, formatage, partitionnement,

organisation, blocs,…



I. Introduction

Un fichier est vu comme une suite d'articles ou d'enregistrements logiques

d'un type donné qui ne peuvent être manipulés qu'au travers d'opérations

spécifiques. Cette 3ème leçon comporte une description physique et logique des

fichiers, des supports de stockage des fichiers et des systèmes de fichiers.

II. Fichiers et répertoires

1. Le concept fichier

Un fichier est un objet abstrait à partir duquel on peut lire et écrire des

informations sans se soucier de l’emplacement physique du contenu du fichier.

On peut classer les fichiers selon les types suivants :

Fichier classique

ASCII : peut être affiché et imprimé sans modification, facile à modifier

par un éditeur de texte, exemple : .txt, .html, .bat

Binaire de données : nécessite un programme décodeur, contiennent

souvent des données structurées, exemple : .doc, .excel, .gif

Binaire exécutable : possède une structure binaire qui définie les

composantes d’un programme exécutable.

Fichier spéciaux d’E/S divisé en fichier spéciaux octet et fichier spéciaux bloc

octet : terminaux, imprimantes, réseaux

bloc : disque (exemple /etc/hdd1)

Les catalogues : fichiers spéciaux dont le contenu permet de cataloguer

l’arborescence des fichiers sur le disque.

Un fichier peut être créé de deux façons :



Soit par l’utilisateur dans la plupart des cas ;

Soit par le système. Certains fichiers sont générés par les systèmes ou certains

outils tels que les compilateurs.

2. Le concept répertoire

Lorsque le nombre de fichiers devient élevé, le système d’exploitation a besoin

d’une organisation afin de structurer ces fichiers et de pouvoir y accéder rapidement.

Cette organisation est effectuée par le biais de répertoires ou catalogues. Un

répertoire est une entité crée pour l’organisation des fichiers. En effet on peut

enregistrer un grand nombre de fichiers sur un disque dur.

Un répertoire est considéré comme un fichier puisqu’il est stocké sur le disque

et est destiné à contenir des fichiers.

III. Gestion des disques

1. Présentation

Un disque dur est un support de stockage des données. Un disque dur contient

un axe central autour duquel les plateaux tournent à une vitesse de rotation

constante. Toutes les têtes de lecture/écriture sont reliées à une armature qui se

déplace à la surface des plateaux, avec une à deux têtes par plateau (une tête par

face utilisée). L’armature déplace les têtes radialement à travers les plateaux pendant

qu’ils tournent, permettant ainsi d’accéder à la totalité de leur surface.

Chaque plateau (possédant le plus souvent 2 surfaces utilisables) est composé

de pistes concentriques séparées les unes des autres. Les pistes situées à une même

distance de l’axe de rotation forment un cylindre. La piste est divisée en secteurs

(aussi appelés blocs) contenant les données.

Pour accéder à un bloc du disque, il faut trois coordonnées :Par : Ben Mahmoud & Shimi - 38 -


Le numéro de la piste (détermine la position du bras portant l’ensemble

des têtes) ;

le numéro de la tête de lecture (choix de la surface) ;

le numéro du bloc (ou secteur) sur cette piste (détermine à partir de

quel endroit il faut commencer à lire les données).

Figure 14 : Structuration d’un disque dur

Si on veut déterminer la taille d’un disque, on aura besoin des informations

suivantes :

Le nombre de cylindres

Le nombre de pistes par cylindre (=nombre de têtes)

Le nombre de secteurs par piste

nombre de secteurs du disque = nombres de tete * nombres de cylindre *

nombre de secteurs par cylindre

taille du disque = nombre de secteurs du disque * taille d’un secteur

2. Partitionnement

Un disque peut être décomposé en partitions. Chaque partition peut contenir

un système de fichiers (données et structures de contrôle).



L’information sur le partitionnement d’un disque est stockée dans son premier

secteur (secteur zéro), le MBR (Master Boot Record).

Deux types de partitionnement :

Primaire : On peut créer jusqu’à 4 partitions primaires sur un même disque.

Etendue : est un moyen de diviser une partition primaire en sous-partitions

(une ou plusieurs partitions logiques qui se comportent comme les

partitions primaires, mais sont créées différemment (pas de secteurs de

démarrage)).

Dans un même disque, on peut avoir un ensemble de partitions, contenant

chacune un système de fichier (par exemple Windows et Linux).

3. Formatage

Le formatage est l'action de formater, c'est-à-dire de préparer un support de

données informatique (disquette, disque dur, etc.) en y inscrivant un système de

fichiers, de façon à ce qu'il soit reconnu par le système d'exploitation de l'ordinateur.

On distingue deux types de formatage : le formatage bas niveau (ou physique)

consiste à réécrire la table d'allocation des clusters, pour chaque plateau. Ceci

permet de réorganiser l'architecture du disque et ainsi d'isoler les clusters

défectueux.

Par contre, le formatage haut niveau, appelé également formatage logique

s'effectue après le formatage de bas niveau, il crée un système de fichiers sur le

disque, qui va permettre à un système d'exploitation d'utiliser l'espace disque pour

stocker et utiliser des fichiers.

IV. Organisation logique des fichiers :

Un fichier est considéré comme un ensemble d’articles dont la structuration et

la manière d’y accéder sont modélisées logiquement par l’utilisateur. On distingue



alors deux méthodes d’organisation logiques des fichiers selon qu’on veuille accéder

aux données séquentiellement ou directement.

1. Organisation séquentielle :

L’accès aux données d’un fichier se fera d’une façon séquentielle. Ce type

d’organisation peut être adapté aussi bien par des mémoires secondaires à accès

exclusivement séquentiel (exemple : les bandes magnétiques) que par des mémoires

à accès direct (exemples : les disques durs).

Dans un fichier, on regroupe les données d’une même entité logique

(exemple : un étudiant parmi les étudiants d’un institut) dans un même article. Les

composants d’un article sont alors des champs de type simple (exemple : le CIN de

l’étudiant) ou d’un type composé (exemple : l’adresse de l’étudiant avec un nom de

rue, un code postal et un nom de ville).

e1 e2 …. ei ei-1 en X

Figure 15 : Description schématique d’un fichier séquentiel

2. Organisation à un accès direct :

La représentation des articles d’un fichier dans une organisation à accès direct

doit permettre selon les besoins un accès tantôt séquentiel et tantôt direct (voir

même calculé). Seules des mémoires secondaires du genre disque dur permettent

l’accès direct aux données. La figure suivante schématise une telle organisation.


Succ


fichierclé Info

.

.

.

.

.

.

Figure 16 : Organisation d’un fichier à un accès direct

Pour pouvoir accéder directement à un quelconque article du fichier, on doit

supposer l’existence d’une donnée qui permette de le désigner en tant que tel. Cette

donné est une clé d’accès.

Clé Autres Champs d’informations

Figure 17 : Article d’un fichier à un accès direct

V. Organisation physique des fichiers :

La mémoire centrale est composée d’un ensemble fini d’unités d’allocation

appelées blocs et qu’un fichier occupe dans cette mémoire un segment logique

constitué d’un certain nombre de blocs (par exemple 5 secteurs pour un fichier

renfermant 2320 octets si la taille d’un bloc vaut 512 octets).

1. Blocs contigus :


k

Clé Recherche


Dans une implantation contiguë, chaque fichier occupe un certain nombre de

blocs consécutifs. La simplicité d’une telle organisation présente un avantage certain

pour les fichiers dont le nombre et la taille ne changent pas et dont l’accès est

séquentiel. En effet, il suffirait pour localiser un fichier, de mémoriser pour chaque

fichier un nombre (celui des blocs occupés) et l’adresse de son premier bloc.

Malheureusement, cette technique d’implantation présente un inconvénient

majeur que constitue la fragmentation de l’espace mémoire.

nomautres info.

NbreBloc=3

Adr. 1er

blocBloc 1

descripteur du fichier Bloc 2Bloc 3

Espacemémoire

Figure 18 : Blocs contigus en mémoire secondaire

2. Blocs chaînés :

Dans une implantation chaînée, les blocs sont liés entre eux. Cette information

supplémentaire sur le chaînage doit être sauvegardée dans le descripteur du fichier

ou dans le bloc mémoire. On mémorise aussi dans le descripteur du fichier l’adresse

du premier bloc alloué et éventuellement celui du dernier bloc.

3. Représentation des blocs par des tables d’implantation :



Pour pallier l’inefficacité des méthodes précédentes pour le cas des accès

directs, l’idée est de rassembler toutes les adresses dans une table d’implantation.

Ces adresse rassemblées peuvent se présenter sous plusieurs formes ; une table

unique, des tables chaînes ou encore des tables à plusieurs niveaux.

a. Tables d’implantation unique :

Dans le cas d’une table unique, toutes les adresses des blocs alloués au fichier

se trouvent dans le descripteur du fichier. Ceci amène à limiter la taille du fichier au

nombre d’entrées de la table d’implantation.

Figure 19 : Représentation de blocs par une table unique

b. Tables d’implantation chaînées :

Dans ce cas, chaque table d’implantation doit indiquer le nombre de blocs

accessibles, un lien de chaînage vers une autre table d’implantation et des pointeurs

vers les blocs de données du fichier.



Figure 20 : Représentation de blocs par des tables chaînés

c. Tables d’implantation à plusieurs niveaux :

Pour des tables d’implantation de grandes tailles, il est serait préférable

d’organiser les tables selon une structure hiérarchique en limitant les niveaux à deux

ou trois. Ceci améliore nettement les temps d’accès aux données car la recherche est

plus rapide.



Figure 7.8: Représentation de blocs par des tables multi-niveaux

VI. Conclusion

Nous avons essayé, dans ce chapitre, de présenter quelques concepts liés au

fichier. D’autres concepts seront traités dans le cadre du cous système d’exploitation

2 enseigné au cours de la 3ème année.





Exercice 1

Soit un disque dur ayant les caractéristiques suivantes :

Caractéristique Performance

Taille d’un secteur 512 octets

Nombre de plateaux 5

Nombre de têtes 10

Nombre de cylindres 100 000

Nombre de secteurs par piste 4 000

Quelle est la capacité d’une piste, d’un cylindre, d’une surface, et du disque ?

Exercice 2

Soit le fichier td3.doc décrit avec le système MS-DOS par l’entrée suivante :

ds.doc … … 4

Etant donné le descripteur du fichier suivant :

Numéro du bloc

Valeur Description

2 0 ………………………………….3 0 ………………………………….4 5 ………………………………….5 7 ………………………………….6 0 ………………………………….7 8 ………………………………….8 EOF ………………………………….9 0 ………………………………….10 11 ………………………………….11 12 ………………………………….12 0 ………………………………….13 EOF ………………………………….

EOF : signifie le bloc de fin de fichier.

1. Quelle est la taille du fichier « td3.doc » en nombre de blocs utilisés ?

2. Complétez la colonne description par l’état du bloc (occupé ou libre).



Bibliographie

1. Andrew Tanenbaum, « Systèmes d’exploitation », Edition Pearson 3ème édition,

2008.

2. Leila Baccouche, « Au Coeur des Systèmes d’Exploitation des Ordinateurs :

Concepts de base et Exercices Résolus », Centre de Publications universitaire

2003.

3. Mohamed Said Ouerghi, « Principes des Systèmes d’Exploitation », Centre de

Publications universitaire 2003.

4. Samia Bouzefrane, « Les systèmes d’exploitation, Unix, Linux et Windows XP

avec C et Java », Edition DUNOD, 2007.


Documents

Academie pro€¦ · Web viewPar : Ben Mahmoud & Shimi- 3 - Guide du cours Ce cours s'adresse aux étudiants de la 1ème année licence technologies de l’informatique, tronc commun