Cours de

Fondement des Systmes dExploitation

Ralis par :

KHAYATI NIZAR Ecole Suprieure de Commerce Electronique Manouba

2004 - 2005

Sommaire :
Chapitre 1 : Chapitre 2 : Chapitre 3 : Chapitre 4 : Chapitre 5 :

Introduction aux systmes dexploitation La gestion des processus La synchronisation des processus La gestion de la mmoire centrale Conception des systmes de gestion de la mmoire centrale

Chapitre 6 : Chapitre 7 :

Systmes de gestion des fichiers Le systme des entres-Sorties

Bibliographie :
Au Cur des Systmes dExploitation des Ordinateurs : Concepts de base et Exercices Rsolus Leila Baccouche, Centre de Publications universitaire 2003.

Principes des Systmes dExploitation Mohamed Said Ouerghi, Centre de Publications universitaire 2003.

Chapitre 1 :

Introduction aux systmes dexploitation

1 Pourquoi un systme d'exploitation ?
Le systme dexploitation est un intermdiaire entre la machine et lutilisateur Avant l'avnement des systmes d'exploitation, la conception d'un programme ncessitait la connaissance parfaite du mode de fonctionnement de la machine. Le programmeur devait grer au moindre dtail le placement des programmes en mmoire en utilisant directement les adresses, l'excution au niveau du processeur savoir le chargement et la terminaison des programmes, l'affichage sur l'cran des rsultats, etc. Cette tache tant trs complexe, peu de programmes pouvaient tre dvelopps. Pour rsoudre ce problme, une couche de logiciel tait dveloppe pour enrober le matriel et le prsenter aux programmeurs comme une machine virtuelle plus facile comprendre et utiliser. Le systme d'exploitation est un gestionnaire de ressources, c'est dire qu'il contrle l'accs toutes les ressources de la machine, l'attribution de ces ressources aux diffrents utilisateurs et la libration de ces ressources lorsqu'elles ne sont plus utilises.

2 Historique des systmes d'exploitation

Ce n'est qu'au XVIIe sicle qu'apparaissent les premires machines calculer. Le mathmaticien, penseur et crivain Blaise Pascal met au point en 1642 ( l'age de 19 ans) une machine qu'il appelle Pascaline, capable d'effectuer l'addition et la soustraction. Ensuite en 1673, G.W. LEIBNIZ (mathmaticien allemand) met au point la premire calculatrice du monde capable de raliser les 4 oprations. La multiplication et la division, s'effectuaient respectivement par additions et soustractions rptes. Charles BABBAGE (mathmaticien anglais l'universit de Cambridge) conoit en 1822 la machine diffrences qui doit valuer n'importe quelle fonction au moyen de diffrences finies. Onze ans plus tard, il se lance dans la construction de sa machine analytique, capable d'enchaner des oprations arithmtiques de faon autonome. Cette premire ralisation tait entirement mcanique. Elle comportait une mmoire, une unit de calcul et utilisait les cartes perfores pour les entres/sorties. Ada Augusta King, comtesse de Lovelace et fille du grand pote Lord Byron, documente le travail de Babbage et crit des algorithmes pour la machine analytique. C'est en son honneur qu'a t nomm le langage de programmation ADA (driv du PASCAL) conu par un ingnieur franais Bull en 1979. En 1847, Georges BOOLE (mathmaticien anglais) labore la logique algbrique moderne, laquelle servira ultrieurement l'laboration des langages informatiques actuels.

En 1890, Herman HOLLERITH (statisticien amricain), met au point une machine cartes perfores pour le recensement de la population. La compagnie que cre Hollerith en 1896 pour fabriquer ces machines, Tabulating Machine Compagny, devient en 1924 la compagnie IBM (International Business Machines). 2.1 La premire gnration (1945-1955) : Prototypes d'ordinateurs a base de tubes lectroniques vide

Le plus connu des ordinateurs non mcaniques est l'ENIAC (Electronic Numerical Integrator And Computer). Il a t mis au point de 1943 1946. Il pse 30 tonnes, occupe quelques dizaines de m2, comporte 18 000 tubes vide, et ncessite 140 KW d'nergie. Il est capable d'effectuer 5000 additions la seconde. Il avait t conu dans le but d'effectuer des calculs pour l'arme amricaine pendant la guerre, mais fut termin trop tard. Il servit aprs la guerre aux calculs pour la bombe N, et fut utilis jusqu'en 1955. L'ENIAC effectue ses calculs en dcimal. Chaque digit est reprsent par un groupe de dix lampes vide dont une seule la fois est dans l'tat "allum". Il a une mmoire de 20 nombres dcimaux de 10 chiffres. Un inconvnient majeur consiste dans le fait qu'on doit le programmer manuellement l'aide de commutateurs et en enfichant des cbles. En 1947 apparat le premier ordinateur programme enregistr : la machine EDVAC puis viens la machine EDSAC en 1949. Le programme n'est pas cbl, mais est stock en mmoire comme les donnes. L'EDSAC avait une mmoire centrale totale de 4096 mots de 40 bits. D'autres calculateurs l'ont suivi tel que NIVAC (dpartement du recensement amricain) en 1951. En 1953 IBM met en circulation son premier ordinateur lectronique Remarque : Aucun de ces calculateurs ne disposait de systme d'exploitation. 2.2 La deuxime gnration (1955-1960) : Les transistors et le traitement par lots

En 1955, des chercheurs des laboratoires Bell annoncent la cration de TRADIC, le premier ordinateur compos en totalit de transistors. C est pour cette raison que la deuxime gnration commence en 1955. IBM commercialise la srie 7000 en 1959 et la srie 1400 en 1961. Par ailleurs, des langages de programmation comme Fortran (FORmula TRANslator) et LISP (premier langage de l'Intelligence Artificielle), sont mis au point. Le premier disque dur est commercialis par IBM, le RAMAC 305. Il peut stocker 5 MO de donnes. Les systmes d'exploitation sont apparus avec les premiers vrais ordinateurs c'est-dire avec l'apparition du transistor. La machine devient ainsi un ordinateur et on dissocie le programmeur du constructeur. Par ailleurs, on rajoute un nouvel intervenant : l'oprateur. Le programmeur crit son programme (en langage fortran ou assembleur) et le transcrit sur une carte perfore. Les oprateurs sont chargs de donner les cartes lire l'ordinateur, de rcuprer les rsultats et de les communiquer aux programmeurs. Ils doivent galement charger le compilateur adquat qui lui aussi se trouvait sur bande magntique. L'existence de ces oprateurs tait due des raisons de scurit, en effet les ordinateurs de l'poque valant

plusieurs milliers de dollars, ils taient conservs dans des pices air conditionn o seuls les oprateurs taient autoriss pntrer. Cette organisation a engendr une perte de temps norme pour chercher les cartes et restituer les rsultats. Pour cela on opta heureusement pour le traitement par lot afin d'enchaner automatiquement les travaux. 2.3 La troisime gnration (1960-1970): Les circuits intgrs et la multiprogrammation

Le premier circuit intgr est dvelopp en 1958. Le principe consiste fabriquer dans un mme bloc de semi-conducteur, plusieurs composants (rsistances, condensateurs, transistors). Lide tait de concentrer dans un volume le plus rduit possible, un maximum de fonctions logiques, auxquelles l'extrieur pourrait accder grce des connexions rparties tout autour du circuit. De 1958 nos jours, le concept de circuit intgr s'est extraordinairement dvelopp pour donner naissance aux microprocesseurs, (une unit arithmtique et logique, des registres, de la mmoireetc.) La troisime gnration d'ordinateurs est trs riche en vnements, en effet elle a vu la cration de la socit Intel, la naissance du systme Unix et la mise en place du rseau de communication Arpanet anctre d'Internet. Vers le milieu des annes 60, IBM lance la gamme de machines SYSTEM/360 (avec le systme d'exploitation OS/360) qui permet de grer les entres-sorties et d'effectuer des calculs en mme temps. Le langage Pascal est invent en 1968 par Nikhlaus WIRTM. Cette gnration a t marque par la naissance du systme Unix en 1969. Cette gnration introduit la notion de multiprogrammation puisque le processeur peut se partager entre plusieurs tches. Un programme ncessite une arrive de donne partir du clavier ou partir d'une bande magntique. Dans tous les cas, c'est une instruction d'entre-sortie et son excution est trs lente vu la diffrence de vitesse entre le priphrique et le processeur. Ainsi au lieu de rester inactif, le systme d'exploitation fait basculer le processeur vers un autre programme et l'excute. Le processeur petit ainsi avoir un rendement de 100%. 2.4 La quatrime gnration (1971- ) : Les micro-ordinateurs et les systmes d'exploitation actuels

Cette gnration est apparue vers les annes 70 o les nouveaux systmes dexploitation et micro-ordinateurs ne cessent dapparatre. Le premier microprocesseur, le Intel 4004 apparat en 1971. Il est capable de traiter des donnes de 4 bits. Il contient 2300 transistors et peut excuter 60.000 oprations par seconde (frquence de base de 108 KHz). Le 12 Aot 1981, IBM dvoile son premier Personal Computer avec un processeur Intel 8088 et un RAM de 16 KO. En 1983, IBM lance un nouveau micro avec un disque dur intgr de 20 MO.

En 1991, Linus Torvald, 21 ans, tudiant en licence universitaire d'informatique en Finlande, prsente la premire version du systme dexploitation Linux qui va rvolutionner l'informatique au 21ime sicle. Ce systme tait gratuit avec son code source. En 1993, Intel prsente le Pentium l'an d'une famille de processeurs 32 bits. En 1995 Sun Microsystems prsente le langage orient objet, JAVA. Les principaux systmes d'exploitation taient :
-

VMS (Virtual Memory System) MS-DOS : cest le plus connu des premiers systmes d'exploitation pour PC Mac OS : c est le systme d'exploitation de la firme Apple. Il a t livr pour le Macintosh en 1984. C'est un des premiers systmes utiliser la souris et une interface graphique avec plusieurs fentres. Red hat : il adapt aux serveurs et ladministration des rseaux. Mandrake Soft : cest une version facile adaptes aux dbutants La famille des Windows : 95, 98 XP La cinquime gnration (dbut des annes 90) : Les systmes parallles et rpartis

2.5

La communaut informatique relie cette gnration aux innovations en matire de rseaux, la technologie des lasers et les fibres optiques aux innovations ralises au niveau d'Internet. On distingue deux types d'architectures multiprocesseurs : parallles et ceux dits rpartis ou distribus. les systmes dits

Un systme parallle permet de gagner en terme de capacit de traitement. Un programme constitu de n procdures plus ou moins indpendantes peut tre excut par n processeurs ainsi le temps dexcution est divis sur le nombre de processeur. Un systme reparti est compos de plusieurs sites comportant une ou plusieurs machines relies travers un rseau de communication (partage des imprimantes, des disques dures )
Dpartement 1 Dpartement 2

Rseau de communication
Batterie de disques

Calculateur Imprimante

Schma de systme rparti

Le systme acclre lexcution de manire ce que lutilisateur ignore si une partie de son traitement a t excut sur son PC ou sur un autre. La classification des machines se caractrise par ce qu'on appelle le flux d'instructions (le calcul raliser) et le flux de donnes (la donne traiter) :
-

Les systmes SISD (Single Instruction Single Data) : ce sont les PC actuels car ils sont monoprocesseurs. Les systmes SIMD (Single Instruction Multiple Data): rptent le mme calcul sur des milliers de donnes. Les systmes MISD (Multiple Instruction Single Data): reprsentent un cas rare de paralllisme. Les systmes MIMD (Multiple Instruction Multiple Data) : regroupent les machines plusieurs processeurs capables d'excuter plusieurs programmes sur plusieurs donnes. Les systmes parallles etdistribus appartiennent cette catgorie.

3 Fonctions dun systme dexploitation

Un systme dexploitation est un ensemble de pages qui jouent le rle dun intermdiaire entre lutilisateur et le matriel. Il construit une machine virtuelle sur la machine physique plus simple et plus conviviale. Il prend galement en charge la gestion des ressources de lordinateur dont lobjectif dassurer une utilisation plus efficace. 3.1 Les fonctions utilitaires

Tout systme dexploitation comprend des programmes chargs de raliser les travaux dexploitation standards de programmation (diteurs de textes, traducteurs, diteurs de liens, configurateurs, outils de mise au point, gestionnaire de version,), 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 taches dadministration du systme (gestion de mots de passe, gestion et contrle des accs , installation de nouvelles applications ou versions dun logiciel, outils dvaluation de performances,), de gestion de taches dun bureau (outils de communication, outils de bureautique,),etc. 3.2 Gestion du dialogue Homme/Machine

Une commande lanc par un utilisateur peut tre formule de diverses manires : un texte saisir, un choix dans un menu, un double clic sur une icne prsente dans une fentre dapplications, etc.) Pour tre traite par lordinateur, cette commande transite par un processeur (logiciel) spcialise dans linterprtation des commandes. Sin analyse par linterprte peut correspondre soit laffichage dun message derreur, soit au lancement du programme correspondant. Lorsque le traitement dfinitif de la commande est termin, lordinateur est de nouveau prt recevoir un nouvel ordre (une autre commande), cest ce que qui est souvent indiqu par un message prcis du systme, appel souvent prompt (ou invite) systme.

3.3

Gestion de donnes et des fichiers

Un fichier peut se dfinir comme un ensemble (une collection) de donnes de mme nature codes et mmorises, pour les besoins de lutilisateur, sur un disque dur ou sur un autre support de sauvegarde magntique, optique, dun point de vue pratique, le fichier constitue le seul et unique moyen pour sauvegarder des informations contenues dans la mmoire centrale de lordinateur et qui, autrement, seraient perdues lors de larrt de cet ordinateur. Selon la nature des informations contenues dans un fichier normal, on distingue entre les fichiers programmes (.bat, .exe, etc.) et les fichiers donnes (Fichier Word, fichier Excel etc.). La gestions des fichiers est lensemble des actions relatives leur existence : cration, dition, recherche, duplication, suppression, impression, compression, etc. Par extrusion, on peut inclure dans cet ensemble toutes les fonctions de gestion des supports de sauvegarde. Ces fonctions incluent par exemple le formatage des supports (initialisation ou rinitialisation) et leur maintenance (vrification de leur tat et ventuellement tentative de rcupration des informations perdues). La gestion des donnes englobe les fonctions lies lutilisation des fichiers et leur partage mais aussi la scurit (protection par mot de passe, dfinition de droits daccs, etc.) et la confidentialit (cryptage par cl publique ou priv, etc.) des informations quils contiennent. 3.4 Gestions des priphriques et des entres-sorties physiques

Les units priphriques peuvent tre vus comme tant des lments permettant lordinateur de dialoguer avec son milieu extrieur (des utilisateurs, des serveurs sur un rseau, etc.) ou encore comme des possibilits dextension de la mmoire centrale (en particulier pour raliser une mmoire virtuelle utilisant un disque comme zone de va-etvient). La gestion des priphriques regroupe lensemble des actions relatives leur emploi. Ces fonctions concernent, dune part, le paramtrage (ou la configuration logicielle) de ces priphriques et, dautre part, leur utilisation proprement dite (envoi de signaux destination des priphriques de sortie et rception de ceux par les priphriques dentr, ralisation doprations de transferts de donnes, etc.). La gestion des entres-sorties physiques sur les priphriques doit permettre dignorer le plus grand nombre possible des diffrences qui existent entre les mmes types dunits proposes par plusieurs constructeurs. Autrement dit, il faut que le gestionnaire dentrssorties puisse rendre transparente lutilisateur les lments caractristiques des priphriques, en lui fournissant un modle virtuel auquel il peut sadresser. Il existe deux types de priphriques :
-

Les priphriques en mode caractre (cran, clavier, souris, imprimante, modem) pour lesquels lunit de transfert est 1 O. Les priphriques en mode bloc (lecteur de disque, disquette, CDRom) pour lesquels le type de transfert est un bloc de caractre (512 O pour une disquette et 4 KO pour un disque dur)

3.5

Gestion de la mmoire centrale

Pour faire excuter un programme, il est ncessaire de lui allouer un espace en mmoire centrale. Cette mmoire doit alors englober les donnes du programme (les constantes qui le composent). Cependant, pour pouvoir lexcuter, le recours au systme dexploitation ou du moins de son noyau est ncessaire. Ce dernier est galement un programme, il lui faut donc de lespace mmoire. Une premire tache de gestionnaire de la mmoire consiste alors rpartir la mmoire vive en deux types despaces : un espace utilisateur et un espace systme, et maintenir lintgrit de ces espaces. Une fois charge en mmoire centrale, limage du programme donne lieu la dfinition dun processus prt tre excut. Zone Systme dexploitation Code du Programme A
Rfrence une donne locale

Rfrence sans le privilge systme

Espace utilisateurs

Donnes du programme A
Rfrence sans autorisation

Code du Programme B
Rfrence une donne partage

Donnes du programme B

Dcoupage et protection de la mmoire 3.6 Gestion du processus et de lunit centrale

Au cours de son excution, un processus peut passer par divers tats caractristiques : cre (inactif), prt (ligible), en excution (lu), bloqu (en attente pour laccs une ressource non disponible ou de loccurrence dun vnement attendu), termin (normalement ou non).

Prt
Cration du processus

Election

Suspension

Actif Cre
Activation Blocage Arrt

Termin

Bloqu

Cycle de vie des processus Un processus a ncessairement besoin de ressources pour accomplir son activit. Quelle soit matrielle (registres de processeur, units priphriques, etc.) ou logicielle (fichiers, buffers dentre/sortie, etc.), une ressource peut tre classe selon son type parmi : les ressources prives ou les ressources partageables. Seules les ressources partageables peuvent poser quelques problmes lors des demandes daccs simultanes. Il faut donc grer correctement la comptition entre les processus en leur attribuant des droits daccs ces ressources et en mettant en place une stratgie quitable dallocation. A remarquer que lon dit dune ressource quelle est critique lorsque son degr daccs est limit un processus la fois.

4 Structuration des systmes

La structure type dun systme dexploitation est un ensemble de couches successives permettant dtablir un dialogue entre les programmes utilisateurs et le matriel constitutif de lordinateur. Une telle structure peut tre reprsent par un noyau autour duquel sont greffs des couches logicielles permettant de raliser un systme opratoire (on parle alors dune machine virtuelle). Le but du noyau du systme est de crer un environnement daccueil pour le processus ; ceci implique le support des interruptions, le partage du processeur central entre les processus, et un mcanisme assurant la synchronisation et la communication des processus.

Gestionnaire des interruptions Microprocesseur et Autres units

Logiciel de base

NOYAU Matriel Autres couches Utilitaires APPLICATIFS

Gestionnaire de la mmoire

Applications utilisateur Gestionnaire de fichiers

Outils de communication

Structuration en couches La gestion des interruptions est la partie du noyau systme charge de rpondre aux signaux (vnements) extrieurs (interruptions) et intrieurs (droutements). Sa fonction est de deux ordres : dterminer la source dinterruption et rpondre linterruption.

scheduler

Diverses listes des processus en attente

File dattente des processus prts dispatcher

Processeur central

Modules de gestion du processeur central

Le dispatcher soccupe de la sauvegarde du contexte du processus en cours, de lextraction du contexte du processus le plus adquat et du transfert du contrle ladresse dsigne par le compteur ordinal du processus restaur. Le scheduler dtermine quel processus doit tre excut. Il suffit pour cela dordonner les processus prts selon un critre donn qui dtermine leur priorit. Le processus lu sera celui qui se situe, selon lordre de priorit, en tte de la file des processus prts. Lorsquune interruption survient le processus actif peut perdre la main au profit (des modules du systme dexploitation et par la suite) dun processus parmi la liste des processus prts. Les liaisons entre le gestionnaire dinterruption et le dispatcher sont reprsentes par lensemble dactions suivantes :
Processus actif

Arrive dune interruption

Gestionnaire dinterruption

Identifier linterruption Prise en charge de linterruption Modifier ventuellement ltat du processus

Entre dans une routine de prise en charge

Routine de prise en charge

Traitement de linterruption

Module Dispatcher

Est-il ncessaire de basculer le processus ? Si non Ractiver le processus interrompu Si oui Sauvegarder le contexte du processus en cours Restaurer le contexte du processus lu (par le scheduler partir de la file des prts) Transfrer le contrle au niveau processus

Actions entreprendre lors dune interruption

Chapitre 2 :

La gestion des processus

1 Ressources ncessaires un processus
Quelle soit matrielle ou logicielle, une ressource est une entit ncessaire lexcution dun processus. On peut la classer selon deux types : les ressources prives et les ressources partageables. Seules les ressources partageables posent des problmes daccs puisquil y a comptition entre les processus pour les acqurir. On dfinit dans ce cadre des droits daccs et une stratgie dallocation/libration. A remarquer que lon parle dune ressource critique lorsque son degr daccs est limit un processus la fois. Dans ce cadre prcis, laccs la ressource critique se fait en exclusion mutuelle et le fragment du programme dans lequel la ressource critique est utilise sappelle une section critique.

2 Relations inter-processus
Les processus peuvent tre compltement indpendants, dans le sens o ils ne possdent pas de ressources communes et ne partagent pas un objectif de ralisation commun. Par contre, ds quils partagent des ressources ou ds quils ont des activits lies, les processus sont dits en cooptition (coopration + comptition). Cette cooptition peut tre dcrite de deux manires : 2.1 Cas dune comptition pour lacquisition dune ressource

Si la ressource est gre par un allocateur (processus particulier disposant de divers privilges vis--vis de la gestion de la ressource). La coordination entre les processus utilisateurs de la ressource est alors rgle par lallocateur selon le schma suivant :
-

Au niveau du processus demandeur on dispose de deux types de requtes adresses lallocateur : une requte dallocation suivie une requte de libration, Au niveau de lallocateur on trouve la dfinition dun service rendre sous certaines conditions vrifier

Process Pi acqurir (Rj) ; utiliser (Rj) ; librer (Rj) ; End Pi

Allocator Rj if occup (Rj) then bloquer Pi) else honorer (Pi) fi; ... End Rj

Si la ressource nest pas gre par un processus spcifique alors des rgles dutilisation sont difies et tous les processus sans exception sappliqueront les suivre la lettre. Ce type de solutions entre processus citoyens implique le respect par toutes des mmes rgles au mme moment. La forme la plus simple des rgles dutilisation dune ressource en partage est la dfinition dun tour de rle. 2.2 Cas de la coopration en prsence de processus ayant des activits logiquement lies

Si des processus doivent sattendre pour avancer sur leur excution respective, des outils synchronisation pure ncessaire pour dcrire ces comportements (mise en place de rendez vous, signalisation dvnements attendus par dautres, etc.)
Process Pi attendre (Pj) ; End Pi Process Pj signaler (Pi) ; End Pj

Si des processus exigent, au cours de leur excution, des donnes qui sont produites par dautres, des outils de communication seront ncessaires pour accomplir lenvoi et la rception de ces donnes.

Process Pi envoyer (Pj, mess) End Pi

Process Pj recvoir (Pi, mess) End Pj

3 Stratgies dordonnancement
Un systme informatique mmoire commune peut possder un processeur unique (systme centralis) ou plusieurs processeurs (lorsquon est dans le cas dun multiprocesseur). Il peut galement tre compos de plusieurs machines indpendantes mais connectes un rseau local ou distant systme rparti). La gestion des processus soccupe alors de lallocation des processeurs aux processus cres avec ses deux possibilits : avec et sans rquisition. 3.1 Gestion de la file selon le mode tourniquet

Cette mthode consiste slectionner le processus qui est en tte de la file dattente. La mise dun processus dans cette file se fait la queue. Cette file est alimente, dune part partir des files dattente des processus bloqus pour lesquels la condition de blocage vient dtre leve, dautre part, les processus ayant subi une rquisition et finalement les processus nouvellement cres.
Rquisition File dattente des processus prts Nouveaux

Processeur

Termin

En Attente

Prts

Stratgies dallocation selon le mode Tourniquet 3.2 Gestion de la file en introduisant en plus des priorits

Cette mthode consiste affecter chaque processus soit une priorit statique (avant donc le lancement du programme qui lui correspond) soit une priorit dynamique (dtermine en fonction du comportement du processus au cours de son excution) et utiliser celle-ci pour dcider de lemplacement dans une file dattente o enfiler le processus sortant.
En Attente Prts Rquisition

File dattente des processus prts

Processeur

Termin

Stratgie dallocation avec rquisition 3.3 Gestion dune file plusieurs niveaux

Cette mthode consiste introduire un nouveau processus dans la file dattente de priorit haute et dplacer tout processus rquisitionn dans une file dattente de plus basse priorit. Lextraction dun processus prt activer se fait partir de la file non vide de plus haute priorit.
Rquisition

File dattente P3

Processeur
File dattente P2 Nouveaux File dattente P1

Termin

Stratgie dallocation par niveaux

4 Algorithme dordonnancement
Lobjectif dun algorithme dordonnancement est doptimiser une des grandeurs temporelles suivantes, sachant que lon sintresse par ailleurs lutilisation de lunit centrale et corollairement au dbit moyen (en nombre de processus traits par unit de temps sur cette unit centrale) :
-

Le temps de traitement moyen (turaround time) dcrit la moyenne des intervalles de temps sparant la soumission et laccomplissement dun processus, Le temps de rponse maximum (response time) est dfini comme tant le maximum des dures sparant soumission et accomplissement dun processus.

Pour reprsenter schmatiquement lvolution dans le temps des processus, on recourt habituellement des digrammes de Gantt.
Exemple :

Supposons qu linstant 0, nous disposons au niveau du systme considr de deux processeurs Pr1 et Pr2 libre et dune liste de 6 les processus ltat prt tels que dcrits par la table suivante : Processus P1 P2 P3 P4 P5 P6 Dure Estime 2 3 2 4 5 1 Date Arrive 0 2 2 5 0 9

La stratgie adopte pour le placement des processus sur les processeurs est fixe. Par exemple : P1, P3 et P4 sur Pr1 P2, P5 et P6 sur Pr2 En partant de ces faits, essayons donc de schmatiser lordonnancement des processus par un diagramme de Gantt matrialisant loccupation des processeurs dans un axe temporel dfini partit de la date 0 o figureront dventuelles zones hachures indiquant linactivit du processeur. Le premier diagramme de Gantt est relatif une allocation sans recyclage.

Processeur Pr1 Processeur Pr2 Axe temps

P1 P5

P1 P5

P3 P5

P3 P5 P5

P4 P2

P4 P2

P4 P2

P4 P6

Gantt sans possibilit de recyclage

Le second diagramme de Gantt explicite la possibilit de recycler les processus aprs avoir consomm la tranche de temps gale 1 qui leur a t attribue.

Processeur Pr1 Processeur Pr2 Axe temps

P1 P5

P1 P5

P3 P2

P3 P5 P2

P4 P5

P4 P2

P4 P5

P4 P6

Gantt avec possibilit de recyclage

4.1

Algorithme dordonnancement sans rquisition

4.1.1 Algorithme FCFS (First Come First Served)

FCFS traite les processus dans lordre de leur soumission (date darriv) sans considration aucune de leur temps dexcution. Lorganisation de la file dattente des processus prts est donc tout simplement du FIFO.
Exemple :

Processus P1 P2 P3 P4

Dure Estime 8 4 5 9

Date Arrive 0 1 2 3

Diagramme de Gantt en supposant quon dispose dun processeur unique P1 P2 P3 P4

12

17

26

Temps de traitement moyen = [ ( 8 - 0 ) +( 12 1 ) + ( 17 2 ) + ( 26 3 ) ] / 4 = 14,25 = [Temps de Terminaison] [Date darrive]

4.1.2 Algorithme SPN (Shortest Process Next)

SPN choisit de faon prioritaire les processus ayant le plus court temps dexcution sans rellement tenir compte de leur date darrive. Cet algorithme est connu est galement sous le nom : SJF pour Shortest Job First.
Exemple :

Processus P1 P2 P3 P4

Dure Estime 10 05 15 03

Date Arrive 0 2 3 4

Diagramme de Gantt en supposant un unique processeur et quon est linstant 5. P4 P2 P1 P3

13

23

38

Temps de traitement moyen = [ ( 8 4 ) +( 13 2 ) + ( 23 0 ) + ( 38 3 ) ] / 4 = 18,25

4.2

Algorithme dordonnancement avec rquisition

4.2.1 Algorithme RR (Round Robin)

RR dcrit une stratgie dite du tourquinet o on procde un recyclage des processus sur le processeur tant que ceux ci ne se sont pas termins. Lorsquun processus est lu, on lui attribue une tranche de temps fixe, appel quantum, pendant laquelle il sexcute. Au bout de ce temps, on ne poursuit plus lexcution du processus, on lui retire donc le processeur et on le rinsre dans la file des processus prts. L, il devra attendre sa prochaine lection. Ainsi, le processus se voit attribuer successivement plusieurs tranches de temps avant datteindre sa terminaison.
Exemple :

Processus P1 P2 P3

Dure Estime 30 05 02

Date Arrive 0 1 2

(i) Diagramme de Gantt en supposant un unique processeur et un quantum = 1. P 1 P 2 P 3 P 1 P 2 P 3 P 1 P 2 P 1 P 2 P 1 P 2 P 1 P 1

0 1

12

37

Temps de traitement moyen = [(37 0) + (12 1) + (6 2)] / 3 = 18,33 (ii) Diagramme de Gantt en supposant un unique processeur et un quantum = 1. P1 P2 P3 P1 P1

10

15

17

27

37

Temps de traitement moyen = [ ( 37 0 ) +( 15 1 ) + ( 17 2 ) ] / 3 = 23

4.2.2 Algorithme SRT (Shortest Remaining Time)

SRT choisit le processus dont le temps dexcution restant est le plus court. Ici, on procde comme dans le cas de la stratgie du tourquinet lattribution dun quantum fixe audel duquel on cherche lire le processus le plus court en terme de temps dexcution

restant pour atteindre sa terminaison.

4.2.3 Algorithme bas sur les priorits

Les algorithmes fonds sur les priorits attribues par le systme dexploitation aux processus choisissent les processus les plus prioritaires sans prise en considration dune manire gnrale des donnes dure dexcution et date darrive des processus. Remarquons que pour des raisons videntes, laffectation dynamique de priorits, par exemple aprs chaque quantum de temps, est une solution couramment utilise puisquelle permet de rsoudre les ventuels risques de famine.
Exemple :

Processus P1 P2 P3

Dure Estime 5 8 4

Date Arrive 0 0 0

Priorit 1 5 3

(i) Priorits statiques : Supposons un unique processeur, des priorits statiques (la valeur 1 correspond la plus basse priorit) et une valeur de quantum = 1. Diagramme de Gantt P2 P3 P1

12

17

Temps de traitement moyen = ( 17 + 8 + 12 ) / 3 = 12,33 (ii) Priorits dynamiques : Supposons un unique processeur, des priorits dynamiques (la valeur initiale dune priorit est diminue par exemple de 1 chaque cycle) et une valeur de quantum = 1. Diagramme de Gantt

P 2

P 2

P 3

P 2

P 3

P 2

P 1

P 3

P 2

P 1

P 3

P 2

P 1

P 2

P 1

P 2

P 1

9 10 11 12 13 14 15

16

Temps de traitement moyen = ( 17 + 16 + 11 ) / 3 = 14,66

4.3

Une brve comparaison entre les algorithmes d'ordonnancement

On ne peut se baser sur un chantillon de 5 processus pour tablir une comparaison entre ces algorithmes, toutefois nous pouvons mettre quelques remarques.

Iln'existe pas d'algorithme idal sur tous les plans. Les critres de choix dpendent des besoins et des attentes. A premire vue l'algorithme du SJF semble obtenir les temps de rponse et d'attente les plus faibles. Toutefois Si l'on souhaite que les processus commencent dlivrer leurs rsultats assez rapidement il faut opter pour l'algorithme du tourniquet. Par ailleurs tous les processus sembleront servis de manire quitable. Si toutefois les processus se distinguent par des priorits, l'algorithme d'ordonnancement avec priorit s'impose.

Chapitre 3 :

La synchronisation des processus

1 Notion de section critique et d'exclusion mutuelle
Une section critique est une partie du processus o peut avoir lieu un conflit d'accs. Elle contient des instructions utilisant des variables ou des ressources partages par d'autres processus. On rentre en section critique, par une section d'entre qui permet de mettre en oeuvre une condition et on la quitte par une section de sortie. Si cette section est excute en entier, les problmes sont rsolus. On parle d'exclusion mutuelle quand un seul processus la fois a le droit de rentrer en section critique (la condition d'entre ne permet qu' un seul processus de passer). Le terme utilis est l'accs en exclusion mutuelle une ressource ou une variable. Si une ressource a t accde par un premier processus et qu'il est interrompu, aucun autre processus ne peut y accder tant qu'elle n'a pas t libre par le premier processus. Il faut donc attendre que le processus reprenne son excution et qu'il libre la ressource.
Processus
. . .

< Section restante> < Section dentre> < Section critique> < Section de sortie>

1.1

Algorithme dalternance
Dclaration Tour 1 Processus = P1, P2 Fin dclaration Processus P1 Rpter <SR> Tant que tour = 2 faire rien <SC> Tour 2 Fin rpter Processus P2 Rpter <SR> Tant que tour = 1 faire rien <SC> Tour 1 Fin rpter

Les deux processus P1 et P2 partagent une seule variable (Tour) qui peut prendre la variable 1 et 2. La section dentre consiste consulter la valeur de tour et lexcution de la section critique nest autoris pour le processus que si la valeur de Tour = i. Lorsque le processus a termin sa <SC>, il excute sa section de sortie en affectant Tour le numro de lautre processus pour lui permettre dentrer dans sa propre <SC>.
Dclaration D1, D2 Processus = P1, P2 Fin dclaration Processus P1 <SR> D1 vrai Tant que D2 faire rien <SC> D1 faux Processus P2 <SR> D2 vrai Tant que D1 faire rien <SC> D2 faux

1.2

Les Smaphores

Un smaphore est une variable qui permet de compter le nombre de processus en attente l'entre d'une section critique. Un smaphore est un objet du langage de programmation ou du systme, il peut tre considr comme un entier. On distingue des smaphores binaires qui peuvent prendre les valeurs O ou 1 et les smaphores n-aires. Les smaphores binaires sont utiliss pour raliser de l'exclusion mutuelle. Q nant aux smaphores n-aires, ils ont pour rle de spcifier un nombre d'accs maximal une ressource (en lecture bien entendu). Conjointement au smaphore, deux primitives indivisibles P et V, mettent en oeuvre les sections d'entre et de sortie. Elles permettent de dcrmenter et d'incrmenter le smaphore. Leur origine provient des termes hollandais Proberen et Verhogen. Certains emploient une mtaphore pour ces primitives, ainsi P signifierait Puis-je et V Vas-y. P(S) permet de prendre le smaphore et quivaut crire
Si S > O Finsi Alors s = s - 1 Sinon s'endormir

Si le smaphore est binaire, en l'initialisant 1, on ne permet qu'une seule excution de la section critique la fois. V(S) permet de librer le smaphore et un processus bloqu s'il y en a
Si un processus est bloqu sur S Finsi Alors le librer Sinon s =s+1

Le fait de vrifier s'il existe des processus en attente du smaphore avant d~incrmenter sa valeur permet de respecter l'ordre dans lequel les processus se sont bloqus au niveau de l'accs cette section critique. Un processus a typiquement les instructions suivantes :
Faire Instructions P(S) Section critique V(S) Instructions Fin

Un processus bloqu est plac dans la file des processus en attente, une fois libr il passe dans celle des prts. Si nous voulons modliser le type smaphore nous pouvons le faire de la manire suivante :
Type smaphore = structure Valeur : entier Tte : Liste d'attente

/* liste de blocs de contexte des processus */ /* en attente d'entrer en section critique */

Fin structure

Exemple : Donner une solution en utilisant les smaphores pour rsoudre le problme producteur-consommateur dans le cas dun seul producteur, un seul consommateur et un seul cas.

vide 0
Producteur <SR> P (vide) 0 Produire Mettre V (plein) 1 Fin prod

plein 1
Consommateur <SR> P (plein) 0 Retirer Consommer V (vide) 1 Fin cons

1.3

Les moniteurs

Un moniteur est un ensemble de procdures, de variables et de structures de donnes regroupes dans un module spcial et gres par le compilateur11. Un programmeur dsirant mettre en oeuvre une section critique se contentera de la reporter dans des procdures du moniteur. Une fois les procdures dfinies, elles pourront tre appeles par les processus mais en aucun cas un processus n~aura connaissance ni accs la structure interne des procdures. Le compilateur vrifie avant d'excuter le processus Si un autre processus est actif dans le moniteur. Etant donn que cette vrification est reporte sur le compilateur, on carte le risque d'erreur engendr par l'inversion des P et V pour les smaphores. Les moniteurs utilisent deux primitives Wait et Signal afin de bloquer les processus sur la ralisation dune condition et pouvoir ensuite les rveiller.
Exemple : Appliquer les moniteurs sur le mme exemple. Fonction moniteur Condition : plein, vide Int Cpt Void mettre ( ) Si Cpt = N alors wait (plein) Sinon mettre (objet) ; Cpt ++ ; Finsi Fin mettre Void retirer Si Cpt = 0 alors wait (vide) Sinon retire (objet) Cpt -- ; Finsi Si Cpt = N 1 alors signaler (plein) Fin si Fin retirer Fin moniteur

Producteur <SR> Production (objet) Moniteur . mettre ( ) . Fin prod

Consommateur <SR> Moniteur . retirer ( ) Consommer (objet) . Fin cons

Exemple : Rsoudre le problme consommateur/producteur dans N cases en utilisant les smaphores

Producteur <SR> P (vide) Produire (objet) P (exmut) Deposer (obj) V (exmut) V (plein) Fin prod Consommateur <SR> P (plein) P (exmut) Retirer (obj) V (exmut) Consommer (obj) V (vide) Fin consommateur

plein = 0 vide = N excmut = 1

Chapitre 4 :

La gestion de la mmoire centrale

Introduction
La gestion de la mmoire implique la connaissance des zones libres et occupes, l'allocation de mmoire au processus, la rcupration de celle-ci la fin de l'excution..

1 Adressage absolu
Quand une adresse est absolue, elle ne ncessite aucun traitement pour obtenir une adresse physique. Les adresses physiques sont utilises telles quelles par l'unit centrale car les adresses logiques et physiques sont quivalentes. On ne peut pas dplacer le programme en mmoire centrale. En revanche dans ce cas, le programme doit toujours tre charg aux mmes adresses, faute de quoi il ne pourra sexcuter, moins d1effectuer une nouvelle tape d'ditions des liens. Les programmes correspondants sont dits non relogeables.

Adressage relatif

Cest un adressage qui est relatif la premire adresse attribue au programme excutable. Toutes les adresses doivent tre converties ou traduites en partant de cette adresse. On peut ainsi changer de zone mmoire d'une excution l'autre. Un tel programme est dit relogeable. La conversion des adresses est lie au mode d'allocation appliqu : contigu ou non. En mode contigu, une adresse relative qui vaut 100 doit tre considre comme 100 + l'adresse de dbut du fichier gnr par l'diteur de liens. En mode non contigu, le programme est partag entre plusieurs zones disperses dans la mmoire et le mcanisme de gestion de la mmoire doit trouver la zone et ensuite l'adresse.

3 Les stratgies d'allocation de la mmoire

On distingue essentiellement deux modes de gestion de la mmoire centrale : le mode contigu et celui non contigu. Quand un programme est charg en mmoire centrale partir du disque, le systme d1exploitation lui alloue une zone mmoire dans laquelle il le place. Selon le mode de gestion de la mmoire, le programme sera plac dans une seule zone (allocation contigu) ou rparti entre plusieurs zones (allocation non contigu). Par ailleurs la zone de mmoire alloue un programme est de taille limite, or tout programme est amen augmenter de taille lors de son excution. On distingue alors des systmes qui utilisent des zones de taille fixe et d1autres qui

permettent au programme de s'tendre sur l'espace avoisinant Si celui-ci est libre. Ceci nous ramne quatre modes de gestion de la mmoire centrale: contigu, non contigu, fixe et variable.

4 Allocation contigu en mmoire centrale

Une partition est un emplacement de la mmoire de taille limit, qui est dcrit par une adresse de dbut et une adresse de fin. On distingue les partitions fixes et celles variables. 4.1 Les partitions de taille fixe Dans le cas des partitions fixes, la mmoire est dcoupe dune manire fixe.
Exemple de dcoupage de la mmoire en partitions de taille fixe: 10K 10K 20K 20K 20K 100K 100K 100K

Chaque processus est suppos occuper la plus petite partition qui peut le contenir. Tout espace inutilis dans la partition est perdu car on ne cumule pas des espaces appartenant des partitions voisines. On distingue plusieurs stratgies pour le choix du processus et celui de la partition, parmi lesquelles on peut citer :
-

Stratgie de la premire zone libre (First Fit): la premire partition ayant une taille suffisante
P1

P4

P2

P3

Stratgie du meilleur ajustement (best fit) : la plus petite partition de taille suffisante
P1 50

P2 P3 P4
-

70 200 32
30 60 50 40 800 400

Stratgie prventive du worst fit : qui alloue une grande partition plutt qu'une petite afin de garder des petites zones libres.
P1 50

P2 P3 P4

70 200 32
15 60 10 40 80 400

Le principal inconvnient de l'allocation par partition de taille fixe est la saturation, un

programme peut rapidement occuper l'ensemble de la partition. Il occupe ainsi toute la mmoire centrale. 4.2 Les partitions de taille variable

Il est clair que le nombre de partitions, ainsi que leur taille varient dynamiquement au fur et mesure que les processus sont crs ou termins. Si un processus ncessite davantage de mmoire car il en a allou dynamiquement pour certaines variables, le systme d'exploitation peut augmenter la taille de sa partition en lui attribuant des partitions voisines s'il en existe. Le cas chant, le recours est le mme que pour les partitions fixes, savoir que le programme est dplac ou bien des processus voisins sont dplacs.

5 Allocation non contigu en mmoire centrale

Cest le mode d'allocation qui est appliqu par les systmes actuels, ainsi un fichier peut tre charg des adresses disperses en mmoire. La correspondance entre les adresses est ralise au cours de l'excution. La mmoire peut tre alloue par zones de taille fixe ou variable. Quand toutes les zones ont la mme taille, on parle de page et de systmes pagins. Quand leur taille peut varier, on parle de segments et de systmes segments. On peut combiner les deux modes, par exemple avoir des segments composs de pages.

6 Gestion de la mmoire appliquant le va et vient

La taille de la mmoire centrale est limite et trs faible compare celle du disque dur. La mmoire centrale est frquemment sature et dans ce cas, il n'existe que deux alternatives : le systme se plante affichant un message d'erreur l'utilisateur ou le systme vacue certains programmes de la mmoire et les place sur une zone bien prcise du disque. Ensuite, il charge d'autres programmes partir du disque en mmoire centrale et les excute. On a vu apparatre plusieurs techniques qui ont donn naissance aux fondements de la gestion actuelle des mmoires centrales : le premier est le va et vient (swapping en anglais). Cette technique s'est rpandue avec l'poque du temps partag o il fallait excuter plusieurs processus par utilisateur. Quand un processus a fini son quantum de temps et quil existe plus de processus que la mmoire ne peut contenir, il est dplac sur le disque par un processus appel swapper. Il faut ce stade prciser que le processus est transfr en entier. C'est l'ordonnanceur en collaboration avec le swapper qui est charg de le ramener une fois que son excution approche. Pour l'utilisateur ceci est transparent. Cette solution, suppose qu'une partie du disque dur complte la mmoire centrale, on l'appelle zone de swap, et elle ne sert qu' sauvegarder les processus dlogs de la mmoire centrale.

7 La mmoire virtuelle
Le swapping ne rsout pas le problme de certains programmes trop grands pour tre contenus en mmoire centrale. On a ainsi vu apparatre un nouveau mode de gestion de la mmoire bas sur la notion de mmoire virtuelle. Elle reprsente le second mode appliqu afin d'excuter des programmes volumineux (en plus du swapping). On parle de mmoire virtuelle car elle a une taille irrelle, bien plus grande que la mmoire physique et elle permet aux programmes d'avoir des tailles plus grandes que celle de la mmoire centrale, tout simplement. La taille des programmes, des donnes et de la pile peut dpasser la mmoire disponible, le systme d'exploitation garde en mmoire les parties qui sont utilises et stocke le reste sur le disque. On voit ainsi que la mmoire virtuelle s'inspire du swapping. En supposant qu'une partie du disque dur est intgre la mmoire centrale, on peut disposer d'un espace d'adresses logiques plus grand. Bien entendu, les adresses physiques sont limites par la taille de la mmoire centrale. La mmoire virtuelle ncessite des systmes d'exploitation qui permettent la gestion des adresses logiques ainsi que la correspondance des adresses logiques sur les adresses physiques. L'espace d'adressage du processus est un espace d'adressage virtuel dont les adresses varient de 0 une adresse maximale fixe qui est la mme pour tous les processus. La taille de la mmoire virtuelle est fixe par la taille des registres, la plupart des machines ont des registres de 32 bits donc les adresses logiques sont entre 0 et 232 soit un espace d'adressage de 4 Go. La mmoire virtuelle est indpendante du mode de gestion pagin ou segment. Dans un systme pagin, l'espace virtuel sera partag en pages et dans un systme segment, il sera dcompos en segment.

8 Les systmes pagins

8.1 La pagination

L'ensemble de la mmoire logique (l'espace d'adressage) d'un programme est dcompos en pages numrotes partir de 0. La mmoire centrale ou physique est dcompose en cases numrotes de la mme manire. L'espace d'adressage logique d'un programme ne devient concret qu'une fois plac en mmoire centrale. Quand le systme n'applique pas de mmoire virtuelle, on a le mme nombre de cases et de pages. Un programme est charg du disque dur en mmoire centrale quand le systme affecte une case pour contenir la page. 8.2 Conversion des adresses

Une adresse logique AL est donne sous la forme suivante (x,y), x indique la page et y le dplacement au sein de cette page.

Cette reprsentation vite que l'adresse logique soit trs grande puisque le dplacement ne dpasse pas la taille de la page. Ainsi, Si les pages ont une taille de 4 KO, chacune peut contenir 4096 adresses. De la sorte l'adresse logique 22480 devient (5,2000). Le calcul de l'adresse physique AP se fait de la manire suivante : le systme d'exploitation commence par trouver l'emplacement de la page x en mmoire centrale (la case correspondante), ensuite il effectue un dplacement de y par rapport la premire adresse dans cette case, en effet les pages et les cases sont de mme taille.

9 Les systmes segments

9.1 La segmentation

A la diffrence des systmes pagins, la mmoire est alloue par partitions de tailles variables appels segments. Un segment a une taille qui peut varier (crotre ou dcrotre) au cours de l'excution. Tout comme les systmes partags, un segment est charg du disque vers la mmoire centrale pour tre plac une adresse prcise pouvant le contenir car de taille suffisante. Si le segment a besoin de crotre, il le fera sur l'espace avoisinant. Dans un espace d'adressage donn il n'y a aucune restriction sur le nombre de segments. 9.2 Conversion des adresses

Le compilateur gnre des adresses appartenant des segments. Chaque adresse logique peut tre crit sous la forme (S,D) ; S pour designer le numro de segment et D pour designer le dplacement dans le segment. La procdure de conversion suit le cheminement suivant : on commence par retrouver l'emplacement du segment en mmoire centrale grce la table de correspondance . Ensuite au sein du segment, on effectue un dplacement de d pour accder l'adresse physique. Chaque programme dispose de sa table de correspondance. De mme que dans un systme pagin, on vrifie d'abord si le segment est en mmoire. En revanche, On distingue un test supplmentaire qu'il faut raliser, savoir qu'on vrifie que le dplacement est bien infrieur la taille du segment autrement la conversion retournerait une adresse contenue dans un autre segment qui peut ne pas appartenir ce programme.
Exemple : Soit ladresse logique = 9035 9035 (2,843) Soit le secteur S de taille T Si d < T Alors AP = adresse deb +d Si d >T alors Erreur de dpassement de secteur

On peut passer d'un systme segment un systme pagin Si la taille T est la mme pour tous les segments, on a alors des pages de taille T.

Chapitre 5 :

Conception des systmes de gestion de la mmoire centrale

1 Conception des systmes pagins
1.1 Allocation et libration de cases

Dans les systmes pagins, le principal traitement est celui du remplacement des pages, en effet l'allocation et la restitution des cases ne sont pas complexes, tant donn que toutes les cases ont la mme taille, donc n'importe quelle case convient lorsqu'il s'agit de charger une page en mmoire. Le systme d'exploitation peut utiliser une structure statique ou dynamique pour conserver les numros de cases libres. La structure statique sera une table de bits, o chaque bit reprsentera une case. Il faut parcourir la table la recherche de bits reprsentant des cases vides ( la recherche des 0 par exemple). Cette table aura au maximum la taille de la mmoire centrale divise par la taille d'une case. La structure dynamique fait en sorte quil faut lier les numros de cases libres entre eux. Cette liste peut tre conserve dans un ordre tri afin que les processus ne soit pas trop parpills en mmoire. 1.2 Remplacement de pages

La mmoire tant de taille faible, elle peut rapidement tre sature. Pour cette raison, on a souvent recours au remplacement de pages, d'autant plus qu'on applique la mmoire virtuelle qui introduit un nombre trs lev de pages. Nous rappelons qu'une page est remplace si le processeur rclame une information situe dans une page qui nest pas charge en mmoire centrale et qu'il n'existe aucune case libre pour y charger cette dernire. Assez souvent il peut y avoir confusion entre dfaut de page et remplacement de page. Le dfaut de page peut entraner un remplacement si le systme d'exploitation ne trouve aucune case de libre. 1.3 Les algorithmes de remplacement de pages

1.3.1 L'algorithme de remplacement d'une page selon FIFO

La politique FIFO permet de remplacer est celle qui a t charge en mmoire depuis le plus long temps.

Exemple :

Soit la chane de rfrence suivante : 1 2 3 7 5 2 3 4 165 MC = 3 cases Calculez le nombre de dfaut de page en appliquant FIFO 1 2 3 7 2 3 7 5 3 7 5 2 3 5 2 3 4 2 3 4 1 6 4 1 6 5 1

1 2

. 1 1 2 1 2 3 . 1 2 3 7 5 2 3 7 5 2 3 7 5 2 3 7 5 4 3 7 5 4 1 6 5 4 1 6 5 4 1 6

1.3.2 Lalgorithme (Lost Recently Used)

Cette stratgie est base sur la supposition suivante : une page qui a t utilise plusieurs fois rcemment va encore ltre lavenir et une page qui ne la pas t ne le sera pas. Cette supposition nest pas toujours possible mais qui soutient si on considre la cas des boucles, des variables et des tableaux.
Application : Appliquer LRU sur cette chane en utilisant : A / B / 0 1 2 3 3 cases 4 cases 1 3 4 0 1 0 4 0 1

1er Cas 1 0 1 0 1 2 . 2ieme Cas 1 1 2 1 2 3 . 1 2 3 7 5 2 3 7 5 2 3 7 5 2 3 7 5 2 3 4 1 2 3 4 1 5 3 4 1 6 5 4 3 1 2 3 1 2 3 1 2 3 1 4 3 0 4 1 0 4 1 0 4 1 0 4 2 0 4 2 1 4

1.3.3 Lalgorithme optimal

Il consiste remplacer la page qui ne sera jamais rfrence ou qui sera rfrenc dans le futur le plus lointain
Application : . 0 0 1 0 1 2 . Remarque : 0 1 2 3 0 1 2 3 0 1 2 4 0 1 2 4 0 1 2 4 0 1 2 4 0 1 2 4 3 1 2 4 Appliquer lalgorithme optimal sur cette chane 0 1 2 3 1 3 4 0 1 2 4 1 0 1 3

En cas darrt, on choisit la page ayant le plus petit numro

1.3.4 L'algorithme de l'horloge

Application : Appliquer sur la mme chane en utilisant : A / B / 0 1 2 3 3 cases 4 cases 1 3 4 0 1 0 4 0 1

1er Cas 0 0 1 0 1 2 3 1 2 3 1 2 3 1 4 3 0 4 1 0 4 1 0 4 1 0 2 1 4 2 1 4 2 1 4 0 1 4 0 1 3 0

Il permet de remplacer la page ayant le bit de rfrence (R=0=. A chaque nouvelle rfrence (R=1) au bout de trois temps dhorloge (trois oprations de remplacement) le bit R=0. En cas dgalit de bit entre plusieurs pages, on fait recours lalgorithme FIFO.
Exemple : 0 0 1 0 1 2 . 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 4 1 0 3 4 1 0 3 4 1 0 2 4 1 0 2

4 1 0 2

4 1 0 2

4 1 0 3

2 Conception des systmes segments

2.1 Allocation et rcupration des segments

Dans les systmes pagins, le principal traitement est bas sur les politiques de remplacement de pages alors que dans les systmes segments aucun algorithme nest dfini. Tout dabord, en ce qui concerne ltape de recherche dune zone libre, dans le systme pagin, il suffit de trouver une case libre alors que dans un systme segment, il faut chercher un segment de taille suffisante. On suppose donc que les structures grant lespace libre en mmoire ne sont pas les mmes puisquil faut connatre la taille de chaque zone. 2.2 Structure de donnes pour la gestion des segments libres en mmoire

On distingue plusieurs manires de grer les espaces libres en mmoire centrale, les plus connues tant la liste chane et la table de bits introduites lors de la prsentation de la gestion du disque dur. La table de bits ne peut s'appliquer pour des systmes segments car on a besoin de connatre les adresses de dbut et de fin du segment en plus de son occupation. Une structure de table n'est pas envisageable car on ignore le nombre de segments en mmoire. Initialement la mmoire centrale est fractionne au fur et mesure que des segments logiques y sont placs et librs.

3 La segmentation avec pagination

Les segments tant trs volumineux compars au pages, au lieu de dplacer un segment entier sur le disque en cas de besoin, on a eu recours la segmentation pagine afin de ne retirer qu'une partie des segments. L'intrt de ce choix est dict par la taille que peut prendre un segment tant donne que le temps de recopie sur le disque est important. Chaque segment est dcoup en pages de longueurs fixes. Le nombre de pages sera diffrent d'un segment un autre selon la taille du segment. Le tait de disposer de pages ncessite une table pour dcrire ces pages : on utilise ainsi une table des segments et une table des page pour chaque segment. 3.1 Conversion des adresses

Une adresse logique la forme (S, P, D) un numro de Segment, un numro de Page et un Dplacement. Le numro de segment permet de retrouver son adresse de dbut grce la table
des segments. Le numro de page permet en accdant la table des pages de savoir si la page est en mmoire et auquel cas dans quelle case.

Il faut toutefois prciser que chaque segment dispose de sa propre table des pages puisqu'il constitue un espace d'adressage part entire.

Chapitre 6 :

Systmes de gestion des fichiers

Introduction
Le systme de gestion de fichiers (SGF) est la partie la plus visible dun systme dexploitation. Le systme de fichiers est un lment essentiel des systmes dexploitation moderne : il permet daccder divers priphriques tels que le disque dur, le lecteur de disquette, de CD-ROM et de DVD. Le SGF a pour principal rle de grer les fichiers et doffrir des primitives pour les manipuler. La mmoire secondaire de lordinateur est constitue de supports magntiques tels que les disques. Pour le systme dexploitation, un support magntique contient des fichiers et il a pour charge dtablir une correspondance entre cette notion logique de fichier et le secteur physique sur lequel le fichier est recopi. On rappelle que physiquement, ce sont des bits qui sont inscrits sur les supports et que le systme dexploitation permet de manipuler ces bits en les prsentant sous forme de fichiers lutilisateur. Chaque fichier a un nom qui permet de le reconnatre.

1 Le codage des donnes

Chaque support de stockage que ce soit le disque situ dans le botier de la disquette ou un des plateaux dans le disque dur, est recouvert dune fine couche magntique destine au stockage des informations. Ce sont les variations dun champ magntique qui permettent de lire et dcrire sur le support. Sur un support magntique, on crit des informations en binaires donc constitues de 0 et de 1. Ce qui facilite le codage car ces valeurs sont codes en utilisant des impulsions. Il ny aurait pas eu le systme binaire, on nose imaginer comment on aurait fait pour coder les chiffres de 0 9.

2 Le formatage dun support magntique

Il faut prciser quil existe deux types de formatage : un formatage de bas niveau opr lusine et un formatage de haut niveau que lutilisateur peut effectuer autant de fois quil le souhaite.

2.1

Le formatage de bas niveau

Il est ralis en usine et il consiste tracer les pistes et les secteurs sur les plateaux. Il faut prciser que selon le formatage, les pistes peuvent toutes avoir la mme taille de donnes ou non. Un formatage standard dfinira des pistes de mme taille, en laissant tout simplement des zones inoccupes. Un formatage plus complexe, donnera un nombre de plus en plus petit de secteurs par pistes au fur et mesure quon se dirige vers le centre. 2.2 Le formatage de haut niveau

Le formatage de haut niveau consiste organiser les pistes et les secteurs dune manire comprhensible par le systme dexploitation. Avant dutiliser une disquette il faut la formater, et nul nignore quune disquette formate sous Dos ne peut tre lue sous Unix. Cela est plus clair prsent car chaque systme organise ses pistes et ses secteurs sa manire. Si lon veut tre plus prcis, un systme dexploitation peut dcider que lunit dallocation nest pas le secteur mais un ensemble de secteurs. Par exemple un secteur peut tre lu en mme temps que celui qui est en dessous sur lautre face de plateau. Le systme dexploitation peut alors dcider de les allouer en mme temps un fichier. Lors du formatage de haut niveau, le systme dexploitation cre les structures quil va utiliser pour grer et organiser les fichiers et les rpertoires.

3 Le partitionnement du disque
Le partitionnement dun disque dur consiste le diviser en partitions. La partition est une zone du disque qui peut tre considre comme un disque logique part. chaque partition peut recevoir un systme dexploitation diffrent. La commande externe DOS FDISK permet de partitionner un disque dur en plusieurs lecteurs et de spcifier pour chacun la taille et le type de systme de fichiers. On distingue des logiciels de partitionnement tel que Magic partition qui a le mrite, en plus du partitionnement, de pouvoir restructurer la taille dune partition en la rduisant ou en laugmentant. La plupart des systmes dexploitation fournissent un administrateur de disques avec lequel on peut crer et grer des partitions. Une fois le disque partitionn, chaque partition doit tre formate pour le systme dexploitation qui va la grer.
Remarque : Une partition est destine recevoir un systme dexploitation, des logiciels ou des fichiers. Lutilisateur peut choisir le systme de fichiers quil souhaite condition quil soit compatible avec le systme install sur la machine. Les plus connus sont les systmes FAT16 (File Allocation Table), NTFS et FAT32. Exemple : FAT16 : Le systme dexploitation Ms-Dos utilise ce systme, c'est--dire que les numros de clusters scrivent sur 16 bits. (Un cluster est un ensemble de secteurs et le nombre de secteurs varie dun systme dexploitation un autre).

FAT32 est pris en charge par Windows 95 et les versions qui ont suivis. Les numros de clusters scrivent sur 32 bits et les partitions peuvent atteindre 2 TO. Avec les nouveaux disques, la limite des 2 GO est vite devenue compltement absurde. NTFS fourni avec NT (NT File System) est conu pour grer des disques avec une capacit suprieure 400 MO. Il autorise les noms de fichiers longs. Quand un volume est format avec NTFS, il est possible de choisir la taille dun cluster : 512 octets, 1024 ou 2048 octets.

4 Le concept de fichier
Un systme de fichiers est la partie la plus visible du systme dexploitation, il doit par consquent se doter dune interface simple manipuler. Il est clair que le systme dexploitation doit prsenter le stockage des donnes sur le disque dune manire plus simple aux utilisateurs. De ce fait, on retrouve dans SGF la notion de fichier et de rpertoire. Un fichier est une unit de stockage logique mise la disposition des utilisateurs pour lenregistrement de leurs donnes : cest lunit dallocation. Le systme dexploitation tablit la correspondance entre le fichier et le systme binaire utilis lors du stockage de manire transparente pour les utilisateurs. Dans un fichier on peut crire du texte, des images, des calculs, des programmes Les fichiers sont gnralement crs par les utilisateurs. Toutefois certains fichiers sont gnrs par le systme ou certains outils comme les compilateurs. Afin de diffrencier les fichiers entre eux, chaque fichier a un ensemble dattributs qui le dcrivent ? Parmi ceux-ci on retrouve : le nom, lextension, la date et lheure de sa cration ou de sa dernire modification, la taille, la protection. Certains attributs sont indiqus par lutilisateur, dautres sont complts par le systme dexploitation.

5 Le concept de rpertoire
Un rpertoire est une entit cre pour lorganisation des fichiers. En effet, on peut enregistrer des milliers, voire des millions de fichiers sur un disque dur et il devient alors impossible de sy retrouver. Avec la multitude des fichiers crs, le systme dexploitation a besoin dune organisation afin de structurer ces fichiers et de pouvoir y accder rapidement. Cette organisation est ralise au moyen de rpertoires galement appels catalogues ou directory. Un rpertoire est lui-mme un fichier puisquil est stock sur le disque et est destins contenir des fichiers. On distingue plusieurs structures pour les rpertoires : la structure plate un niveau, la structure deux niveaux et la structure arborescente quon appelle ainsi car elle rappelle la structure de larbre gnalogique. Dans la structure plate, on dispose de plusieurs rpertoires mais chacun deux ne peut contenir que des fichiers. Dans la structure deux niveaux, chaque utilisateur dispose de son propre rpertoire dans lequel il peut conserver des fichiers et des rpertoires. Cependant ces sous-rpertoires ne peuvent contenir que des fichiers. La structure arborescente contient un nombre arbitraire de niveaux et chaque rpertoire peut contenir des fichiers et des sous rpertoires. On introduit ici la notion de chemin partir de la racine.

Du point de vue du SGF, un rpertoire est un fichier qui dispose dune structure logique : il est considr comme un tableau qui possde une entre par fichier. Lentre du rpertoire permet dassocier au nom du fichier qui est un nom externe, les informations stockes en interne par le SGF.

6 Les taches dun SGF

Un systme de gestion de fichiers effectue gnralement les taches suivantes :
-

La donne dune interface conviviale pour manipuler les fichiers : tant la partie la plus visible du systme dexploitation le SGF doit offrir des commandes et des attributs simples pour manipuler et dcrire les fichiers Le stockage des fichiers sur le disque dur La gestion de lespace libre sur le disque dur La gestion des fichiers dans un environnement multi-utilisateurs La donne dutilitaires pour le diagnostic, la rcupration en cas derreurs, lorganisation des fichiers.

7 Lorganisation des fichiers sur le disque

7.1 Techniques dallocation des blocs sur le disque

7.1.1 Allocation contigu

Cest le mode dallocation le plus implicite, pour chaque fichier enregistrer le systme recherche une zone suffisamment grande pour accueillir le fichier. Le fichier sera constitu de plusieurs blocs contigus. En apparence le principal avantage de cette mthode est la rapidit lors de laccs. Les inconvnients de cette mthode sont :
-

La difficult de prvoir la taille quil faut rserver pour le fichier. La perte despace sur le disque : si nous prvoyons trop despace, le fichier risque de ne pas lutiliser en entier.

7.1.2 Allocation chaine

Elle consiste allouer des blocs chans entre eux aux fichiers. Un fichier peut dsormais tre parpill sur le disque puisque chaque bloc permet de retrouver le bloc suivant. Les avantages de cette mthode sont llimination de la fragmentation externe puisque tous les blocs peuvent tre allous. Par ailleurs, elle ne ncessite pas de structure de donnes spciale. En revanche, les inconvnients sont aussi multiples :

Laccs au fichier est squentiel. On doit toujours commencer le parcours partir du dbut du fichier mme si on a rcemment charg les blocs. La perte dun chanage entrane la perte de tout le reste du fichier.

7.1.3 Allocation indexe

Tous les inconvnients de lallocation chane peuvent tre rsolus dune manire simple : il suffit de retirer les pointeurs des blocs et de les placer dans un structure de donnes garde en mmoire centrale ainsi linformation sur les numros de blocs peut tre obtenue tout moment. 7.2 La cration dun fichier par le systme dexploitation Un fichier et un rpertoire sont tous les deux cres en suivant les mmes tapes :
-

La cration dune structure de donnes pour dcrire le fichier. Tout fichier doit tre dcrit afin que le systme puisse le connatre et le reconnatre. La cration du fichier proprement dit. Cela consiste allouer au fichier un certain nombre de blocs sur le disque selon sa taille. Le contenu dun bloc sera diffrent selon quil sagit dun fichier ou dun rpertoire. Structure de donnes pour les fichiers et les rpertoires

7.3

7.3.1 Le systme dexploitation MS-DOS

Le rpertoire racine

MS-DOS utilise une structure de donnes : le rpertoire racine afin de contenir les fichiers et les rpertoires. Le rpertoire racine est enregistr sur le disque dur un emplacement fixe. Chaque disque format avec MS-DOS contient un rpertoire racine et des sous-rpertoires. Tous ces rpertoires ont la mme structure et chaque entre dun rpertoire a une taille de 32 octets et la structure suivante :
Nom du fichier La FAT Attributs Adresse du premier bloc du fichier ou du rpertoire

Cest un tableau connu sous le nom de table dallocation des fichiers FAT (File Allocation Table). MS-DOS ne gre pas individuellement les blocs, il alloue aux fichiers des clusters qui sont constitus dun ensemble de secteurs. Selon lexemple cit ci-dessous, lentre du rpertoire indique que le fichier commence au cluster numro 2. En consultant ce tableau, nous retrouvons la suite des

numros de clusters qui composent le prog.c : 5 6.

Numro du cluster Soit le fichier prog.c dcrit par lentre suivante dans le rpertoire racine 2 3 4

Valeur 5 0 0 6 FFFFh 8 FFFFh 0 0 0 0 0 0 0 0 0

Prog.c

5 6 7 8 9 10 11 12 13 14 15 16 17

Structure de la FAT
7.3.2 Le systme dexploitation Unix

Le systme Unix utilise une structure de donnes bien particulire qui lui est propre afin de dcrire les fichiers : cest le nud dindex appel en anglais I-Node. Un nud dindex est constitu dattributs dcrivant le fichier ou le rpertoire et dadresses de blocs contenant des donnes, il occupe 64 octets. Cette structure permet au systme de disposer dun certain nombre de donnes sur le fichier :
-

La taille, Lidentit du propritaire, du groupe et les droits daccs au fichier, Les dates de cration, de dernire consultation et de dernire modification, Le nombre de rfrences existant pour ce fichier dans le systme, Ladresse de blocs physiques. Ces blocs physiques contiennent soit les donnes du fichier, soit ladresse dautre blocs physiques (on parle alors de bloc dindirection).

Bloc dindirection simple 256 adresses de blocs sur le disque Bloc dindirection simple Taille Date de cration Compteur de liens UID GID Adr 1 Adresse sur le disque du premier bloc associ au fichier Adr 2 Adr 10 PS PD PT Bloc dindirection triple 256 adresses de blocs dindirection simples Bloc dindirection double

256 adresses de blocs dindirection doubles Bloc dindirection double Bloc dindirection simple

Structure dun I-Node

7.3.3 Le systme dexploitation Windows NT

Le systme dexploitation Windows NT propose plusieurs systmes de gestion de fichiers qui lui est propre : NTFS NT File System et les systmes FAT16 et FAT32. NTFS utilise une structure de donnes organise en table nomme Master File Table MFT pour grer les fichiers (table des fichiers matre). Elle contient des informations dtailles sur les fichiers et les rpertoires. Lorsque ces derniers ont une taille rduite, elle contient les fichiers et les rpertoires eux-mmes. Chaque entre peut contenir 2KO dinformations. Cette valeur assez leve permet de stocker dans une entre un fichier si sa taille est infrieure 1,5 KO (en supposant que les 500 octets restants sont utiliss pour dcrire le fichier). Lavantage de cette organisation est laccs direct au fichier. Quand les fichiers sont volumineux, lentre incluse en pointeur vers des clusters contenant les donnes. Les fichiers sont dcrits par NTFS laide des attributs suivants :
-

Le nom du fichier Un entte de description

Un descripteur de scurit Les donnes

entte

attributs

Nom du fichier

donnes

Attributs de scurit

Structure dune entre de la MFT Lorsquil sagit dun rpertoire, le champ donnes dcrit un ensemble de fichiers et conserve pour chaque fichier le nom du fichier et le numro de lentre o il est plac. Les grands rpertoires quant eux ont dans leur champ donnes un pointeur vers un cluster qui stocke les noms des fichiers ainsi que leur numros.
<TP-SE,48> <RAPPORTS, 49> <TP-VB, 31> <[Link], 218> <[Link], 228> <[Link], 229> <prog.c, 312> <# # # #>

entte attributs

TP

Chapitre 7 :

Le systme des entres-Sorties

Introduction
Les entres-sorties sont une composante principale de l'ordinateur puisqu'une grande partie d'entre elles est en relation avec l'utilisateur. Pour cela leur interface doit tre simplifie au maximum par les systmes d'exploitation. Un priphrique se commande et c'est la tche du systme d'exploitation de fournir une couche appele systme d'entre-sortie dont le rle est de contrler le ou les priphriques jusqu'au moindre dtail tout en offrant des commandes de haut niveau pour les utilisateurs.

1 Fonctionnement des priphriques

1.1 Structure d'un priphrique

Un priphrique est compos du priphrique lui-mme et de composants lectroniques pour le commander donc d'une partie mcanique et d'une autre lectronique. A titre d'exemple, dans un disque dur les plateaux, les ttes de lecture/criture, le bras ainsi que le moteur constituent la partie mcanique. La partie lectronique est appele contrleur de priphrique. On l'appelle ainsi car elle contrle le priphrique la place du processeur. Le contrleur est une carte compose de circuits qu'on relie au priphrique. Sans contrleur, le processeur devrait se charger lui-mme de tous les priphriques. Un mme contrleur peut grer plusieurs priphriques de mme type. 1.2 Les types de priphriques

Il existe globalement deux types de priphriques : les priphriques bloc et les priphriques caractres. Les priphriques bloc effectuent un adressage par bloc, c'est--dire la quantit minimale manipule est le bloc. Le disque dur est un priphrique bloc. Les priphriques caractre manipulent un flot de caractres. Ils ne permettent pas dadresser une zone directement puisque laccs est squentiel. Nous citons les terminaux et les imprimantes, on ncrit pas au milieu de la page ou de lcran sans commencer partir du dbut.
Remarque : Certains priphriques ne rentrent dans aucune de ces catgories. Lhorloge ne manipule ni bloc ni caractre.

1.3

Les contrleurs de priphriques

En ralit, le processeur ne communique pas directement avec les priphriques : ceux-ci sont relis des contrleurs de priphriques et c'est avec eux que le processeur dialogue. Par exemple Si le processeur veut crire une donne sur le disque dur, il le demande au contrleur de disque dur et c'est ce dernier qui se dbrouille pour effectivement satisfaire la demande du processeur. Le processeur transmet alors la donne crire au contrleur, qui la stocke et la transmet au disque dur le moment venu. Ce relais de l'information par des contrleurs permet dj de sabstraire des spcificits des priphriques : une partie de ces spcificits n'est connue que du contrleur. Cela permet par exemple de dvelopper des priphriques trs diffrents les uns des autres sans qu'il y ait de problme majeur pour les insrer dans un ordinateur. Cela permet aussi de renouveler les priphriques d'un ordinateur sans avoir rinstaller le systme. On distingue plusieurs contrleurs dans un ordinateur, les plus connus sont le contrleur de disque, le contrleur de mmoire RAM, de mmoire cache, le contrleur de carte vido, le contrleur de clavier, d'cran, le contrleur de bus. Nous concluons de ces exemples que le contrleur effectue principalement les tches suivantes :
-

recevoir les requtes d'entre-sortie effectuer effectuer l'entre-sortie en plusieurs tapes Si cela est ncessaire traduire les ordres du systme en des signaux comprhensibles par le priphrique : identifier les caractristiques du priphrique, effectuer les calculs ncessaires la ralisation de l'entre/sortie. corriger les ventuelles erreurs.

Pour ce faire la carte du contrleur se compose d'un circuit intgr pour la commande lectronique, de registres destins accueillir les commandes excuter et stocker temporairement les donnes avant leur transfert en mmoire centrale et vice-versa. 1.4 Interaction entre le systme d'exploitation et le contrleur

Le systme d'exploitation dialogue avec le contrleur travers le bus. Il lui transmet les paramtres de l'entre/sortie et ce dernier les stocke dans ses registres. Le contrleur une fois qu'il a reu l'information, gnre les signaux adquats, en effet le rle du contrleur est de transformer les signaux compris par l'unit centrale en signaux lectriques compris par le priphrique et vice-versa. Le systme d'exploitation place des commandes et des paramtres dans les registres, par exemple : read, write. Une fois que la commande est accepte par le contrleur, il peut excuter la commande : le processeur n'a plus besoin d'intervenir et peut s'occuper d'une autre tche. Une fois que le contrleur a fini, le processeur reprend le contrle et le systme d'exploitation prend la main, il va aller tester les rsultats du droulement de l'entre-sortie travers le contenu des registres.

2 Le sous-systme dentre-sortie
2.1 La couche systme

Le principal objectif de cette couche est de fournir une interface uniforme la couche au dessus savoir les programmes utilisateurs en leur cachant le lien avec le matriel. Une requte dentre-sortie va tre construite par la cration dun IOCB (input output control block). Cest une structure qui contient des informations dcrivant lentre-sortie parmi lesquelles :
-

Le type dopration lecture ou criture, Ce quon appelle la longueur de lentre-sortie c'est--dire le nombre de caractres transfrer par exemple, Ladresse dune zone tampon en mmoire destine accueillir les donnes. Dautres informations complmentaires Les pilotes priphriques

2.2

On distingue gnralement un pilote par type de priphrique. Il est noter que dsormais, la plupart des pilotes sont ralises par le fabriquant plutt que par les concepteurs du systme, de part le trop grand nombre de priphriques diffrents. Ces pilotes sont chargs par le systme au dmarrage et sont exploits de la mme faon que les autres, en ce qui concerne la partie grant le matriel. Tout comme le systme dexploitation est le seul connatre ladresse du priphrique, son tour le pilote est le seul connatre les paramtres ajuster c'est--dire les caractristiques du priphrique. Un pilote de priphrique est constitu de routines qui sappellent les unes les autres. Le rle du pilote est dcrit ci-dessous :
-

Traduire la requte partir de lIOCB en termes concrets. Lancer le contrleur et se mettre de la fin de lentre-sortie. Une fois lentre sortie termine, le priphrique gnre une interruption. La procdure de traitement des interruptions est lance. Elle va identifier la source de linterruption, elle saura donc quelle est lunit qui a gnr linterruption et par consquent le traitement entreprendre et le pilote associ sont rveills. Il vrifie le statut de lentre-sortie. Il traite les erreurs non rsolues par le contrleur, par exemple il effectue une nouvelle tentative. Si lentre-sortie ne sest toujours pas ralise, il informe la couche systme qui informe son tour le processus appelant.

3 Etude de cas : le priphrique disque dur

3.1 L'entrelacement des blocs

Lorsque le contrleur effectue une entre-sortie DMA, il met un certain temps pour transfrer le secteur lu vers la mmoire. Or durant ce temps, le disque continue de tourner. Si le contrleur ne peut effectuer une entre et une sortie en parallle, le secteur suivant ne peut tre lu durant le transfert vers la mmoire. Si le temps de transfert vers la mmoire est gal au temps de lecture d'un secteur du disque, il faut deux rotations du disque afin de lire toute une piste. Le secteur de numro suivant ne doit passer sous la tte de lecture qu'une fois que le contrleur a fini le transfert du secteur prcdent. Une solution serait que les numros de secteurs ne soient pas conscutifs, afin que le secteur suivant ne dfile sous la tte qu'une fois la fin du transfert. On appelle entrelacement le lait de sauter des numros de secteurs afin que le contrleur puisse les lire dans un ordre normal. Cette numrotation spciale est ralise au formatage du disque en tenant compte du facteur d'entrelacement. Un facteur d'entrelacement de 1 dsigne le saut d'un secteur chaque fois. Ce facteur est li au temps ncessaire au contrleur pour effectuer son transfert vers la mmoire. Il est clair que si le contrleur met plus de temps, il faut prvoir un facteur de 2. La figure suivante illustre un disque avec les numros de secteurs numrots de 0 11. Sans entrelacement aprs un tour complet le contrleur n'aura pu lire que les secteurs n 0 2 4 6 8 10. Au tour suivant, il lira les secteurs 1 3 5 7 9 11. Avec un facteur simple, le contrleur laissera passer un secteur et lira le suivant. Avec un facteur dentrelacement double, il laissera passer deux secteurs pour lire le secteur suivant.

3.2

Notion de cache disque

Certains concepteurs ont eu l'ide d'appliquer le principe du cache pour le contenu d'une piste. Quand les requtes d'entres-sorties sont trs nombreuses, il devient frquent d'avoir des accs des secteurs voisins donc appartenant une mme piste. Le principe du cache pour les pistes est de copier le contenu de toute la piste dans le cache. Ainsi des requtes futures pour des secteurs de cette piste viteront d'accder au disque. Le cache fait partie du contrleur.

De nos jours les contrleurs sont tellement rapides, qu'en un seul accs ils peuvent recopier toute la piste dans leur zone tampon. 3.3 La prise en compte des erreurs

Les erreurs doivent tre traites par le composant le plus proche du priphrique, donc par Je contrleur. Parmi les erreurs qui peuvent survenir, nous citons :
-

Les erreurs de positionnement du bras : le contrleur peut se tromper dans les paramtres qu'il utilise pour accder une piste donne. Les erreurs de programmation : Si le pilote demande au contrleur d'accder une piste ou un secteur qui n'existe pas le contrleur doit tre capable de dceler l'erreur et de la signaler. La rencontre d'un bloc endommag : Le contrleur doit ne pas l'utiliser ou en utiliser un autre Les erreurs de lecture : elles peuvent tre dues la prsence d'une poussire sur la surface du plateau. Ordonnancement des requtes d'entres-sorties

3.4

Quand on doit effectuer un transfert de ou vers le disque dur, le temps total cumul dpend du temps ncessaire pour positionner la tte de lecture/criture sur le bon cylindre (appel temps de recherche) et du temps pass attendre que le secteur passe sous la tte afin de lire les octets (appel temps de rotation, en moyenne la moiti d1un tour) et enfin le temps pour le transfert. 3.5 Algorithme FIFO Comme l'indique son nom, la requte arrive en premier est excute en premier.
Exemple : Si la tte est positionne dans le cylindre 10 et on souhaite lire les secteurs appartenant aux pistes 1, 9, 8, 26, 13, 23. Dans ce cas, le bras va effectuer un dplacement qui va couvrir 9 + 8 + 1 + 18 + 13 + 10 = 59 cylindres.

3.6

Algorithme Plus court dplacement ou plus court temps de recherche (PCD)

Cet algorithme s'appelle en anglais SSTF (Shortest Seek Time First). Le contrleur sert la requte qui est la plus proche de celle qui vient d'tre traite. Si l'on ordonnance ces requtes en essayant de minimiser les dplacements par rapport la position courante, on obtient un accs dans cet ordre 10, 9, 8, 13, 23, 26, 1 soit un dplacement qui couvre 1 + 1 + 5 + 10 + 3 + 25 = 45 cylindres, ce qui reprsente une amlioration notable par rapport

FIFO. Cet algorithme peut provoquer des situations de famine si la plupart des requtes se situent dans un mme espace et qu'il existe une ou deux requtes plus loin, celles-ci ne seront traites que trs tard. Par consquent, cet algorithme n'est pas quitable. 3.7 Ordonnancement selon l'algorithme de l'ascenseur (SCAN)

Cet algorithme est utilis galement pour les ascenseurs dans les grands buildings, o on sert les requtes en maintenant un seul sens de dplacement (vers le haut ou le bas pour les ascenseurs> vers l'extrieur o vers l'intrieur (pour les disques) jusqu' ce qu'il n'y ait plus de requtes dans le sens choisi. Cet algorithme garantit une certaine quit. On dit qu'il applique un balayage de bout en bout et est connu sous le nom de SCAN. Le pilote mmorise un bit de sens (haut ou bas) qui indique la direction que le contrleur doit privilgier. Ainsi, il traite toutes les requtes dans un sens, puis, quand il n'y a plus de requte dans ce sens (le bras est donc vers une extrmit), on inverse le bit et on traite les requtes situes de l'autre ct du bras. On est donc sr de traiter rapidement toutes les requtes. Pour cet exemple, supposons que le sens de dplacement du bras tait vers l'intrieur. Servir les requtes 1, 9, 8, 13, 26, 23 en partant de la 10 va donner l'ordre suivant 10 13 23 26 9 8 1 soit un dplacement de 3 + 10 + 3 + 17 +1 + 7 = 41 cylindres. La diffrence n'est pas trs significative mais l'avantage de cet algorithme est qu'il est indpendant du nombre des requtes et quitable. Le dplacement du bras est gal maximum deux fois le nombre de cylindres. Donc deux fois le temps ncessaire pour aller du cylindre du centre vers celui le plus l'extrieur. On distingue une autre variante cet algorithme qui est connue Sous le nom de CSCAN. Elle consiste parcourir les cylindres toujours dans le mme sens. Aprs le dernier cylindre, le bras retourne au premier. Le temps de rponse s en trouve un petit peu amlior. 10, 1, 8, 9, 13, 23, 26 soit un dplacement de 9 + 7 + 1 + 4 +10 + 3 = 34 cylindres.
Exemple : On considre un disque dur prsentant 160 pistes (de 0 159). On suppose que la tte de lecture/ecriture est positionne dans la piste n et que le dernier accs au 50 disque a t effectu en piste 80 et que les requtes arrivent dans cet ordre : 100, 40, 60, 120, 56, 30, 75, 2, 90, 140, 45. Question : Quel serait le dplacement total de la tte lecture/criture aprs avoir accder toutes ces pistes si lalgorithme de planification de dplacement est a- SSTF PCD b- SCAN Ascenseur c- C-SCAN (balayage interne) d- FCFS PAPS aFCFS : 100, 40, 60, 120, 56, 30, 75, 2, 90, 140, 45 Dplacement : 50 + 60 + 20 + 60 + 64 + 26 + 45 + 73 + 88 + 50 + 95 b- SSIF : 50 45 40 30 56 60 75 90 100 120 140 2

Dplacement : 5 + 5 + 10 + 26 + 4 + 15 + 15 + 10 + 20 + 20 + 138 = 268 cSCAN : 50 / 45 / 40 / 80 / 2 / 56 / 60 / 75 / 90 / 100 / 120 / 140 Dplacement : 5 + 5 + 10 + 28 + 54 + 4 + 15 + 10 + 20 + 20 = 186 d- [Link] : 0, 2, 30, 40, 45, 56, 60, 75, 90, 100, 120, 140