2015 10 02 Sys Exploitation ISET TI1

8/18/2019 2015 10 02 Sys Exploitation ISET TI1

http://slidepdf.com/reader/full/2015-10-02-sys-exploitation-iset-ti1 1/232

TI11-16

Systémed’exploitation 1

Iset Siliana

1IsetSiliana CHaabani Nizar

http://www.academiepro.com/enseignants-104-Chaabani.Nizar.html







P!N d" C#$%S

I. Chapitre 1: Introduction

II. Chapitre 2: Gestion de rocessus

III. Chapitre !: Gestion de la mémoirephysi"ue

I&. Chapitre #: Gestion de la mémoire$irtuelle

&. Chapitre %: Gestion des entrées-sorties&I. Chapitre 6: Gestion des &chiers









Chapitre 1: Introduction

C'est ("oi "n #S) *rands S+st,mes

S+st,mes Personnels S+st,mes "ltiprocesse"rs S+st,mes istrib"s S+st,mes emps %el S+st,mes 2 la main3 istori("e des #Ss et des Concepts !rchitect"re po"r les s+st,mes




C'est ("oi "n #S)

Programme intermdiaire entre l'"tilisate"rd'"n ordinate"r et le matriel

5"t d'"n #S:67c"ter les programmes des "tilisate"rs%endre l'ordinate"r 8s+st,me in9ormati("e

9acile 2 "tiliser

67ploiter le s+st,me in9ormati("e d'"nemani,re e;cace




'uel"ues mots sur les syst(mesd’exploitation

)é&nition$n s+st,me d<e7ploitation 8S6= en anglais: #S >operating s+stem est "n ensemble deprogrammes de gestion d" s+st,me ("i permet degrer les lments 9ondamenta"7 de l<ordinate"r:

e matriel - les logiciels - la mmoire - lesdonnes ? les rsea"7.

@ +pi("ementA "n S+st,me d<67ploitation estcompos

d<"n no+a" = de biblioth,("es d+nami("es = d<"n ensemble d<o"tils s+st,me = de programmes applicati9s de base.




e s+st,me d'e7ploitation

*e noyau





*e noyaugestion des priphri("es 8a" mo+en de pilotes@ gestion des process"s : attrib"tion de la mmoire 2 cha("e process"sordonnancement des process"s 8rpartition d"

temps d'e7c"tion s"r le o" les processe"rss+nchronisation et comm"nication entre

process"s 8serices de s+nchronisationAd'change de messagesA mise en comm"n desegments de mmoireA etc.

@ gestion des Dchiers 8a" mo+en de s+st,mes deDchiers

@ gestion des protocoles rsea" 8CP/IPA IPEA etc.





+utres composantes del’,S@ es ilioth("ues dynami"ues reroupent lesopérations

les pl"s "tilises dans les programmes in9ormati("es? iter la redondance de ces oprations dans to"s les

programmes? certains s+st,mes ne proposent pas de biblioth,("esd+nami("es@ es outils syst(me permettent :? de conDg"rer le s+st,me? de passer le relais a"7 applications proposant des serices

2 "n o" pl"sie"rs "tilisate"rs o" 2 d<a"tres ordinate"rs@ es prorammes applicati/s de ase o0rent des

ser$ices l<"tilisate"r 8calc"latriceA dite"r de te7teAnaigate"r webA etc.




etit retour histori"ue 1(re énération 314#%-14%%5? "bes 2 ides? ablea"7 d'interr"pte"rsA cartes per9ores 2(me énération 314%%-146%5? ransistors? raitements par lots !(me énération 3146%-1475

? Circ"its intgrs? ini-ordinate"rsA 9aible rapport ("alit/pri7 #(me énération 3147-au8ourd’hui5? icroprocesse"rs 8circ"its intgrs




S+st,me d'e7ploitation

8S6Fo"rnit l'inter9ace "sager/machine:as("e les dtails d" matriel a"7

applicationse S6 doit donc traiter ces dtails

ContrGle l'e7c"tion des applicationse 9ait en reprenant priodi("ement le

contrGle de l'$Cit 2 l'$C ("and e7c"ter tel programme

Il doit optimiser l'"tilisation des resso"rces po"rma7imiser la per9ormance d" s+st,me




)i0érents ni$eaux d’unSyst(me




9ernel ode $s. ;ser

ode9ernel mode: ode de

/onctionnement duS.<

? !cces complet ettotal a

to"tes les resso"rcesmaterielle

67ec"te n'importe("'elle

instr"ction ("e lamachine pe"t e7ec"ter

;ser odeode de

/onctionnement detous

les prorammes$ne partie

seulement desinstr"ctions sont

accessibleses instr"ctions ("i

aHectent les I/# sontinaccessibles




=onctions d’un syst(me

d’exploitation*estion de la mmoire*estion des s+st,mes de Dchiers

*estion des process"scanismes de s+nchronisation*estion des priphri("es*estion d" rsea"*estion de la sc"rit.




&"e abstraite d'"n S6




%esso"rces et le"r

gestion%esso"rces:ph+si("es: mmoireA "nits 6/SA $C...ogi("es > irt"elles: Dchiers et bases de

donnes partagsA cana"7 de comm"nicationlogi("esA irt"els...les resso"rces logi("es sont bties par le

logiciel s"r les resso"rces ph+si("es!llocation de resso"rces: gestion de

resso"rcesA le"r aHectation a"7 "sagers ("iles demandentA s"iant certains crit,res




Jol"tion histori("e des

S6e db"t: ro"tines d'6/SA amorKage s+st,meS+st,mes par lots simplesS+st,mes par lots m"ltiprogramms

S+st,mes 2 partage de temps#rdinate"rs personnelsS6 en rsea"S6 rpartis

Les fonctionnalités des systèmes simples seretrouvent dans les systèmes complexes.

Les problèmes et solutions qui sont utilisés dans lessystèmes simples se retrouvent souvent dans lessystèmes complexes.




Syst(mes de traitement par lots(batch) simples

Sont les premiers S6 8mi-L0'"sager so"met "n Mob 8e7: s"r cartes

per9ores 2 "n oprate"r'oprate"r place "n lot de pl"sie"rs Mobs s"r le

dispositi9 de lect"re$n programmeA le monite"rA g,re l<e7c"tion decha("e programme d" lot

e monite"r est to"Mo"rs en mmoire et prt 2tre e7c"t

es "tilitaires d" monite"r sont chargs a"besoin$n se"l programme 2 la 9ois en mmoireA et les

programmes sont e7c"ts en s("encea sortie est normalement s"r "n DchierA

imprimanteA r"ban magnti("eO17IsetSiliana CHaabani Nizar



Schéma émoire d’un Syst(me deTra>tement par lots




S+st,mes 5atch

"ltiprogrammsPl"sie"rs tches sont sim"ltanment en mmoireA et le CP$est m"ltiple7 entre elles= si "ne doit attendre "ne 6/SA "nea"tre tche est choisie




Syst(mes Temps artaé

Sert po"r le pilotage et le contrGle des dro"lementse7ternes 8p.e7. centrale lectri("e

doit garantir des temps de ractions donnes po"r

dessigna"7 e7trie"r "rgents

pl"sie"rs s+st,mes d<e7ploitations n<+ arrient pas

carl<interr"ption de certaines actiits met le s+st,me

dans

"n tat instable




S+st,mes Personnels

Ordinateurs Personnels ? S+st,mes ddis 2"n se"l "tilisate"r

Priphri("es d'6/S ? claierA so"risA cransAimprimanteA O.

Coniialit et interactiit aec l'"tilisate"r Pe"ent to"rner diHrents t+pes d'#S

8indowsA ac#SA $NIEA in"7




S+st,mes Parall,les S+st,mes aec pl"sie"rs CP$s en

comm"nication!"ssi conn"s comme s+st,mes

m"ltiprocesse"rs

Systèmes fortement couplés ? processe"rs

partagent la mmoire et l'horloge=comm"nication a lie" ia la mmoire partage

!antages des s+st,mes parall,les:!"gmentation de la capacit de traitement6conomi("es

olrance a"7 pannes




S+st,mes %partis

%partir la comp"tation s"r pl"sie"rs processe"rsph+si("es Systèmes faiblement couplés ? cha("e processe"r

poss,de sa propre mmoire= les processe"rscomm"ni("ent entre e"7 ia des lignes decomm"nicationA tels des b"sA des lignes de tlphoneAdes rsea"7A etc O

!antages des s+st,mes rpartisPartage des resso"rcesP"issance de comp"tation pl"s grande ? Partage de

charge olrance a"7 pannesComm"nications




S+st,mes %partis 8cont

%e("i,re "ne in9rastr"ct"re rsea" %sea"7 oca"7 8LAN o" %sea"7 arge

6chelle 8WAN

Pe"ent tre des s+st,mes clientserveur o" peertopeer


St t * l d'



Str"ct"re *nrale d'"nClient-Sere"r




S+st,mes emps %el

So"ent "tiliss dans desenironnements spcialissA tels lese7primentations scientiD("esA

l'imagerie mdicaleA les s+st,mesde contrGle ind"strielsA OContraintes de temps bien dDnies

S+st,mes temps rel so"ples o"rigides




S+st,mes 2 la main3

Personal igital !ssistants 8P!s lphones obiles

Contraintes:moire limiteProcesse"rs lents6crans d'a;chage petits




Introduction au syst!e d"e#$loitation

%&# ' (S)*+S,-









.

*+S

/IN9.

/IN N2000

(ac +S .

ni#

Syst!e (ono)utilisateur

.

.

(ulti)utilisateur

.

.

(ono)ce

.

(ulti)ce

.

.

.

.

Exemples '




+ranisation de iciers et r$ertoires

" \ " racine de' l'arb orescence correspondant

à un disque (C: ou A:)

Repertoire1 R2 R3 R4

R6 R R!R#ic$ier1 #ic$ier2

#ic$ier3

. .

.

+ranisation base sur le conce$tdarbres '







Introduction au syst!e (S)*+S

%MicroSoft Disk Operating System,

e *+S: co!!e tout syst!e de#$loitation: contr;le les acti<its delordinateur- Il re des o$rations telles =ue la circulation: laicae: etlentre de donnes entre les di<ers l!ents constitutis du syst!e-

e r;le du *+S est dinter$rter les co!!andes saisies au cla<ier $arlutilisateur-

Ces co!!andes $er!ettent deectuer les tces sui<antes'

>la estion des iciers et des r$ertoires-

>la coniuration du !atriel->lo$ti!isation de la !!oire-

>le#cution des $rora!!es-

> ?




es iciers sous (S)*+S

Sous (S)*+S ca=ue icier $eut @tre aussi <olu!ineu# =ue $ossible:ce$endant le no! =ue <ous lui donnez est sou!is A des restrictions: on ne $euten eet lui donner un no! dune lonueur !a#i!ale de 8 caractres $lus 3 $ourle#tension-

*e $lus: les iciers ne doi<ent contenir =ue les caractres sui<ants'

>lettres de B A

>cires de 0 A 9

>caractres s$ciau# sui<ants' D E F G J K ) L M % ,

&nin: les no!s de iciers ne doi<ent $as contenir'

>de blanc %es$ace,-

>de <irule-

>de barre obli=ue in<erse-

>de $oint %or!is le $oint =ui s$are le no! de le#tension,-33IsetSiliana CHaabani Nizar



es iciers sous (S)*+S

et ils ne doi<ent $as non $lus a$$artenir A la liste de no!srser<s'

C+COF C+N B. C+(1 C+(2 C+(3 C+(4

P1 P2P3 N PQN

Sous (S)*+S: les no!s de ces r$ertoires sont sou!is au#!@!es restrictions de lonueur =ue les iciers %8 caractres $ourle no!,-




Quelques commandes MS-DOS

Q;le ' Bicer le contenu dun r$ertoire

a co!!ande R *IQ R ait la liste des iciers

corres$ondant au# s$ciications $rcises $arl "aru!ent de la co!!ande et donne =uel=uesrenseine!ents sur les iciers-

Qe!ar=ue ' Si on <eut aicer la liste des iciersdont l "e#tension est -t#t T: on en<oie la co!!ande '

C'*IQ U-t#t





Q;le ' Crer un r$ertoire

a co!!ande (O*IQ %(aOe *IQectory,

$eut @tre abre en (*-Il suit de ta$er '

C'(* No! du r$ertoire





Q;le ' &acer un r$ertoire

a co!!ande Q(*IQ %Qe(o<e *IQectory,$eut @tre abre en Q*-

C'Q* No! du Q$ertoireQ;le ' Caner de r$ertoire

a co!!ande RC*R ou encore RCH*IQR

$er!et de $asser dun r$ertoire Alautre %C* $our Cane *irectory,

C'cd No! du Q$ertoire 37IsetSiliana CHaabani Nizar




Q;le ' co$ier un ou une liste de iciers

Synta#e ' C+PV Wicier d$artX Wicier

destinataireX

Il aut $asser en $re!ier aru!ent le no! du

icier A co$ier: et en deu#i!e aru!ent leno! =ue nous <oulons donner A la co$ie-





&#e!$le ' Pour co$ier icier1-t#t T dans lesous r$ertoire Q2 T en lui donnant unnou<eau no! co$ie1-t#t-

" \ " racine de' l'arborescence correspondant

à un disque (C: ou A:)

Repertoire1 R2 R3 R4

R6 R R!R#ic$ier1 #ic$ier2

#ic$ier3

Q$ertoire

courant





Q;le ' Qeno!!er un icier

> a co!!ande Q&NB(& $eut @tre abre

en Q&N

> &#e!$le '

C'ren icier1-t#t surno!-t#t





Q;le ' Su$$ri!er un icier &lle sert A dtruire un icier ou une liste de

icier- +n lui donne co!!e aru!ent le no!d "un icier %et <entuelle!ent son e#tension,ou bien les s$ciications d "une liste de iciersA l "aide des caractres Y T ou U T-

Il est $ossible de su$$ri!er tous les iciers d "un

r$ertoire en une seule ois ' &QBS& U-U&#e!$le'

C'erase No! de icier




dir

cd

cd --

!d ou !Zdir

deltree

co$y: #co$y

!o<e

del

liste le contenu dun r$ertoire

cane de r$ertoire

r$ertoire $arent

cre un nou<eau r$ertoire

su$$ri!e un r$ertoire: ainsi =ue lense!ble de ses sous)r$ertoires-

co$ie de icier

d$lace!ent de icier

su$$ri!e le icier

or!at

el$ aide sur la co!!ande de!ande

or!ate le lecteur de!and

<er donne le nu!ro de <ersion





43IsetSiliana CHaabani Nizar 43IsetSiliana CHaabani Nizar



a commande6E6C$6% Commandes#S et IN#SsConDg %eg6dit S+s6dit

sIn9oQR C inS Ping

IpConDg ssgsPer9mon Charmap 8table des

caract,res

Clean*% 8Netto+age de dis("e C#NF 8Neteeting 7iag 8irectE iagnostics

elpCtr 8Centre d'aide IcwConn1 8!ssistant conne7ion agni9+ 8$tilisation de la lo"pe stSc 8!ssistant de b"rea" 2

distance ab 8Carnet d'adresse #"tloo

67press S9c 8Intgrit des Dchiers T s+st,me U iner 8NV ersion indows




#rdinate"r$n ordinate"r est "ne machine lectroni("e

("i permet l<e7c"tion des programmes$n programme est "n ensemble d<instr"ctions

("i seront trad"ites en signa"7 lectri("es

a sortie de ces programmes est conertie 2no"ea" po"r ("e l<"tilisate"r p"isse lacomprendre

$n ordinate"r est compos a" moins de :

processe"rA carte m,re=mmoire ie= mmoires de masse=priphri("es




rincipes de /onctionnement,rdinateur

nit de contr;leou

nit de co!!ande

nit arit!ti=ueet loi=ue

ounit de traite!ent

ou

nit de calcul

Unité centrale

de traitement

Mémoire

Cache

Instructions

*onnes

Mémoire centraleou principale

Unités d’entrée/sortie

ou d’I/O

Contr;leur de$ri$ri=ues

Carterseau




!"tre reprsentation

P 7

r i $4 7 r i = u e s

[us d "adresses

[us de contr;le

[us de donnes

CP(!oireCentrale

nitd "&\S




rincipes de /onctionnement C;

nit decalcul

rsultat

o$randes

nit arit!ti=ue

et loi=ue

Qeistres

Qe Bdr Qe (ot

QIPC ou C+ nit de

co!!andeDécodeur

]tat Séquenceur

Horloe

(!oire centrale

rsultats!ot!!oire

adresseinstruction


Ca$ I I ^&SI+N *&S PQ+C&SSS et



$n S6 tourne en permanence apr,s son dmarrage aec

l'ordinate"r

il permet le deloppement et l'e7c"tion de no"ea"7

programmes escription le 9onctionnement d'"n S6

Concept fondamental : La décomposition !

e S6 9ait to"rner les programmes "tilisate"rs s"r leprocesse"r

Abstraction du processeur ? !ntroduire la notion

de Processus

Ca$- I I ^&SI+N *&S PQ+C&SSS etHQ&B*S

Partie 1. a *6SI#N 6S P%#C6SS$S










rocessus etterminoloie3aussi appelé 8o? tas@? user

proram5

Concept de process"s: "n programme en

e7c"tion

Poss,de des resso"rces de mmoireA priphri("esA etc

#rdonnancement de process"s

#prations s"r les process"s

Process"s cooprants

Process"s comm"nicants


1 A i d



1. Aotion de rocessus

Qu’est-ce qu’un proramme ?6nsemble de mod"les so"rces/obMets %s"ltat de l<dition de liens 8actions manip"lant des donnes "escription tatique (Code " données)

Que désine le terme processeur ?6ntit matrielle capable d<e7c"ter des instr"ctions W'par9ois '' a"ssi entit logicielle 8interprte"rA ...

Qu’est-ce qu’un processus ?#ntité d#namique représentant l$exécution d$un pro%ramme

sur un processeur créée & un instant donné' a un état qui évolue au cours du

temps et qui dispara(t' en %énéral' au bout d$un temps )ni

Début FinEtat Temps t


$n programme est "ne s"ite d<instr"ctions 8"n obMet stati("e.@ $n process"s est "n programme en e7c"tion et son conte7te 8"n obMetd+nami("e.



Notion de Process"s 8s"ite

$é%nition technique: un processus est l’abstraction du

& pour

l'allocation de la C 8codeA donnesA pile espaced’adressae

l'allocation d" processe"r 8C#A O

'ntért de la notion de processus !bstraction de la notion d<e7c"tion s("entielle %eprsentation des actiits parall,les et de le"rs

interactions ?"nit de str"ct"ration

&emples de processus : <e7c"tion d'"n programme Copie d'"n Dchier s"r dis("e la transmission d '"ne s("ence de donnes s"r "n rsea"




R. Paralllisme et Conc"rrence

Soient de"7 process"s P1 et PR en mmoire centrale 8prts 2 s'e7c"ter

ise en Bu$re concr(te de l’exécution de 1 et 2 :

P1 P2 Exécution séquentielle

(1 processeur)

P1

P2 Exécution parallèle(2 processeurs)

P1

P2

Syst!e

Exécution concurrente

(1 processeur)


Paralllisme et Conc"rrence 8R



Paralllisme et Conc"rrence 8R

ultiprogrammation / Pseudo-parallélisme :

Un SE doit, en général, traiter plusieurs processus en même temps

Il y a un seul processeur (la plupart du temps)

Entrelacemen t des eéc tions

(simuler une eécution parall!le)

" tout moment le SE ne traite #u$un seul processus % la &ois

'a commutation étant tr!s rapide

'es processus utilisateurs sont lancés par un interpr!te de commandes(

Ils peuent eu-mêmes lancer ensuite d$autres processus

P1

P2 P3

P4 P5

Père : processus créateur

Fils : processus créés

!" lancement d" s+st,meA il n'e7iste ("'"n se"l process"s

: l*anc+tre de to"s

Hiérarchie des processus (arborescence)




Q. Process"s en moire Centrale

<tat de la mmoire centrale associ 2 "n process"s est dDni

par le conten" de , sements -le code' la pile et les données et d'"n contete.

Code

Piled"e#cution

*onnes

es se!mentsd’un processus

ement code -- Lecture seulement

Contient les instr"ctions Inariant 8to"te la d"re d<e7c"tion d"

process"s. ement données -- Lecture*&criture

Contient les ariables globales Xdonnes stati("es 8ConstantesA ("i sontinitialises 2 la compilation

+ile d,eécution -- Lecture*&criture

$n programme est constit" d'"nensemble de 9onctions 8procd"res ("is<changent d 'in9ormations

/ontient les variables éc0an%ées 1variables locales

$57IsetSiliana CHaabani Nizar



4. Notion de %esso"rces -- Conte7te d"Processe"r

Contete du processeur:ypoth(ses : 1 se"l processe"r X

pl"sie"rs process"s le processe"r estrser 2 l'"sage d'"n se"l process"s

Contete > Conten" des registresadressables/spcialiss -- ot d,état- +. Pro%ram Status Word 6tat d<e7c"tion : !cti9/!ttente ode de 9onctionnement :

S"perise"r/"tilisate"r as("e d'interr"ption Conte7te accessible en mmoire


C t t d’ é ti d’



Contexte d’exécution d’unprocessus<tat courant du processus Code du proramme exécuté )onnées stati"ues et dynami"ues In/ormations "ui caractérisent l’état

dynami"ue du processus Compteur de proramme 3C D C,5 <tat des reistres *iste des &chiers ou$erts Eariales d’en$ironnement Imae mémoire 3état de l’espace d’adressae5

F sau$earder lors"ue le processus estcommuté

F restaurer lors"ue le processus reprend lamain




#rdonnance"r $C*ans un syst!e !ultitces: le syst!ede#$loitation doit rer lallocation du $rocesseurau# $rocessus- +n $arle dordonnance!ent des

$rocessus


J d



Jtat de process"s

!3PO45AN5 !" 9"r et a mes"re ("'"n process"s e7c"teA ilchange d'tatno"ea": le process"s ient d'tre cre7c"tant-r"nning: le process"s est en train d 'tre

e7c"t par "ne $Cattente-waiting: le process"s est en train d 'attendre "n

nement 8p.e7. la Dn d'"ne opration d'6/Sprt-read+: le process"s est en attente d'tre e7c"t

par "ne $Cterminated: Dn d'e7c"tion




62

L. Conte7te d'"n Process"s 81

Y"and "n process"s n'est pas en e7c"tionA son tatdoit tre sa"egarde dans son descripte"r associ.

Exécuter processus

Changer Etat

Sauvegarder Etat

Y"'est-ce ("'on sa"egarde) e conte7te d" process"s 8in9o.ncessaires 2 la gestion des process"s

Conte#te accessible

&tatd"e#cution

(as=ue d"It

"S#

(ode de

onctionne!ent

C+

PI*

Conte#te du$rocesseur

C+

Bllocation!!oire

Conte#te du$rocessus

Ino-Co!$le!- _

di<ers

Ino-d"ordonnance!ent

Contexte de processus$C"

%"rocess Control $loc&'62IsetSiliana CHaabani Nizar



Conte7te d'"n Process"s 8R

Contexte d’un processus: ensemble de paramètres re%roupés dans

les se%ments du pro%ramme en cours d*exécution - code " données

e S6 dtient "ne tableA contenant la liste de to"s les process"s

cha("e entre consere le descripte"r de process"sA appel /loc

de Contr0le de processus 1/C+ - 3rocess Control loc@5

5CP : str"ct"re de donnes associe 2 l<e7c"tion

de cha("e programme 4eprésente la situation actuelle d $un

processus




Z. 6tat d'"n Process"s

Comm"tation des taches 8passage d '"ne tache 2 "ne a"tre estralis par "n ordonnance"r 8dispatcher/short term sched"ler

PRET !T"F

#$%&'E

DemandedE!S

E!Sterminées

"t ## Tpsdépassé

Commutation

$ouveau processus Terminaison

ttente

2 états d’un processus : actif3 prt3 bloqué acti9 blo(" > action olontaire 8lect"re s"r dis("e blo("e prt > action e7trie"re a" process"s

8resso"rce disponible

prt acti9 > cision de l'allocate"r d" processe"r64IsetSiliana CHaabani Nizar



Le multit0readin%6n 9aitA cha("e process"s pe"t l"i-mme

9onctionner comme le s+st,me d<e7ploitationen lanKant des so"s-tches internes a"process"s

Ces so"s-tches sont nommes [\"7

d<e7c"tion[ [process"s lgers [o" Threads.


rait de e7te



rait de e7teultit0readed

*is=uenoyau

Thread %' re!et en or!e le docu!entThread & ' interaction a<ec l"utilisateur

Thread '' crit $riodi=ue!ent le contenu de la QB( sur le dis=ue

c(avier

Bbsb`sd*ndd`Z`d=H=d`l=d`ldd!Z!*`dl=`d`d=d`d=Z!Zd






)i0érences et

similitudes entrethreads et processus :a comm"nication entre les threads est

plus rapide ("e la comm"nication entreles process"s.

es hreads poss,dent les mmes tats("e les process"s.

e"7 process"s pe"ent traailler s"r "ne

mme donne 8"n tablea" par e7emple enlect"re et en crit"re dans "ne sit"ationde concurrence de e"7 process"s ilen est de mme po"r les threads.




H. écanisme de Commutation 315

pointe"r: les PC5s sont rangs dans des listesencha]nes 82 oir tat de process"s: read+A r"nningA waitingO compte"r programme: le process"s doit

reprendre 2 l 'instr"ction s"iante a"tres registres $Cbornes de mmoire

Dchiers ("'il a o"ert etc.A . man"el




écanisme de Commutation 325

Commutation de processus 4 commutationdes contetes de processus

Y"and l'$C passe de l'e7c"tion d '"n process"s

7

2 l 'e7c"tion d^"n proc 1A il 9a"t mettre 2 Mo"r etsa"egarder le PC5 de 7

reprendre le PC5 de 1? "ui a$ait été sa"egard

aantremettre les registres d '$C tels ("e le compte"rd 'instr"ctions etc. dans la mme sit"ation ("i est

dcrite dans le PC5 de 1


écanisme de Commutation 3!5 --



écanisme de Commutation 3!5 Schéma

IsetSiliana CHaabani Nizar 70IsetSiliana CHaabani Nizar 70

. elations entre rocessus 315 --Compétition



CompétitionIl e7iste entre les process"s "n certain nombre de

relationsA appeles '56&7AC6'85=

ces interactions pe"ent tre de comptition o" decoopration sCompétition

Sit"ation dans la("elle pl"sie"rs process"s doient"tiliser sim"ltanment "ne resso"rce 2 acc,s e7cl"si981 se"l process"s 2 la 9oisA encore appele ressourcecritique.

<xp. '"sage d" processe"r 8pse"do-paralllisme !cc,s 2 "n priphri("e 8imprimante

2 processus en compétition sont dits en

eclusion mutuelle pour cette ressource. 9ne solution possible : Faire attendre les processe"rsdemande"rs ("e l 'occ"pant act"el ait Dni 8FIF#

R )essource

Criti*ue

+%+&

Ordre duti(isation , "ndifférent

+%- +& ou +&- +%


elations entre rocessus 325 --



elations entre rocessus 325 CoopérationCoopération

Sit"ation dans la("elle pl"sie"rs process"scollaborent une tache commune et doient ses#nchroniser po"r raliser cette tache.

e"7 process"s ("i coop,rent pe"ent galement setro"er en e7cl"sion m"t"elle po"r "ne resso"rce

comm"ne.

F

P1 produit un ichier F

P2 iprie

le ichier F +& ne peut s.exécuter *ue si,

+% a terminé son exécution

+% / +&

Synchronisation $n process"s doit attendre ("'"n a"tre process"s ait

9ranchi "n certain point de son e7c"tion point des+nchronisation

Imposer des contraintes de s+nchronisation a"7process"sPrcdence des process"sConditions de 9ranchissement de certains points

criti "es72IsetSiliana CHaabani Nizar

elations entre rocessus 3!5 -- =aire+ttendre un rocessus



+ttendre un rocessus%elations entre de"7 process"s _ Faire attendre "n

process"s

Solution 1: attente acti$e 1 2 60ile -ressouce occupee 4essourceoccupee 7 5rue8 9 :8 ;tiliser

4essource8

4essource occupee 7 5rue84essource

occupee 7 2alse8 ....

r,s pe" conomi("e si pse"do-paralllisme i;c"lt d'"ne sol"tion correcte 8chap. S"iant

Solution 2 : locae du rocessus Process"s blo(" : attente d '"ne resso"rce non disponible

M"s("'a son reil e7plicite par "n a"tre process"s !T"F #$%&'E

Ré*eil

)eprendre exécution

#loca+e

0rr1ter (.exécution


4. Conditions dJ<xécution Concurrente315



315

!"gmenter le degr de m"lti-programmation et

donc le ta"7 d'"tilisation d" processe"r )6tablir les contraintes de prcdence 8relation `Constr"ire "n graphe de prcdence : graphe

ac+cli("e o cha("e n"dA SiA reprsente "ne instr"ction cha("e arc SiS M signiDe ("e l 'instr"ction S M ne po"rra

s<e7c"ter ("e si Si ait termine son e7c"tion.

<xemple : Soit la s("ence d 'instr"ctions

s"iante :S1 lire87SR lire8+SQ z > 7 +S4 crire8z

S% S&

S'

S2




Iset SilianaIset Siliana

IsetSiliana CHaabani Nizar 75

Ca$- I I ^&SI+N *&S PQ+C&SSS etHQ&B*S



1. Introd"ction

R. +pes d'ordonnancement

Q. od,le simple d<ordonnancement

4. Politi("es d'ordonnancement

Or%anisations des )les d$attente

Ordonnancement 2/2S < S=2< 44< priorité<

S452< 3ultiniveaux

L. irarchie d'ordonnancement


HQ&B*SPartie R. #%#NN!NC66N 6S P%#C6SS$S

1. Introduction -- Généralités



1. Introduction Généralités *e S< permet 2 types de décisions sur le processeur :

8rdonnancement des processus : *’ordonnanceur

3scheduler5 choisit "uel est le processus "ui doit tourner +robl;me: )ans "uel ordre les processus sont ser$isKL

par exemple? un processeur et plusieurs processus.

Allocation du processeur : l’allocateur 3dispatcher5 lance

l’exécution du processus choisi par le scheduler ,rdonnanceur -- Scheduler

,8ecti/ :

Sur un inter$alle de temps asseM rand? /aire proresser tous

les processus? tout en ayant? un instant donné? un seul

processus acti/ 3dans le processeur5.

Nle : rendre en chare la commutation de processus? "ui

r(le les transitions d’un état un autre des di0érents

processus.




+pes

d'ordonnancementIl e7iste diHrentes politi("es d<allocation :- aec o" sans priorit

sans : premier arri premier seri 8DrstcomeA Drst

sered : FCFS

a$ec :

@ la priorit pe"t tre D7e o" d+nami("e

@ il pe"t + aoir premptionA o" non


! od(le Simple d’,rdonnancement



!. od(le Simple d’,rdonnancement

7eprésentation de l’ordonnancement des processus

ile des $rocessus $r@tsile des $rocessus $r@ts

'! '! Sceduler dis$atcSceduler dis$atc

er!inaisoner!inaison

*e!ande &\S*e!ande &\S

ile d"attente &\Sile d"attente &\S&\S&\S

rance de te!$s e#$irerance de te!$s e#$ire

orZ un ilsorZ un ilsils s"e#cuteils s"e#cutee#ite#it

Bttente It Bttente ItInterru$tionInterru$tion


#. oliti"ue d’,rdonnancement O



#. oliti"ue d ,rdonnancement ,ranisations des =+s : 9n seul processeur " plusieurs processus

$ne )le d$attente' soit 2A' des process"s prtsPrincipe de cha]nage d'"ne F! : aant/ arri,re/ mi7tePl"sie"rs process"s sont mis dans "ne F!A et le serice

demand le"r est 9o"rni to"r 2 to"rA en 9onction de

crit,res de gestion spciD("es 2 la F!.

ile d"attente des $r@tsile d"attente des $r@ts

'! '!

,ispatcher -,ispatcher -

allocateur allocateur .cheduler-.cheduler- %rdi %rdi

Brri<e Brri<e

RéquisitionRéquisition

34re (a((ocation du processeur5

i( peut ré*uisitionner

Ser<iceSer<icesatisaitsatisait SortieSortie

34re (a F0 , 0rrivée des processus et

(eur p(acement


#. oliti"ues d’ordonnancement O



+lorithmes sans préemption 3sansr("isition 3=C=S=C=S? SP=? riorité5 315

rocessus )urée estimée )ate d’arri$ée

P1 R4 0

PR d 1

PQ 1R R

P4 Q Q

+lorithme =C=S 3=irst Come =irst Ser$ed5 -- remier +rri$é remierSer$i

;n processus s*exécute >usqu*& sa terminaison' sans retrait forcé de laressource. od,le adapt a" partage d" processe"r par des process"s de mme

priorit 8a"c"n priil,ge entre les process"s !ec les algorithmes d<ordonnancement sans r("isitionA "n process"s

aHect a" processe"r ne pe"t pas tre interromp". Facile 2 implanterA mais pe" e;cace 8le choi7 n'est pas li 2 l'"tilisation

de l'$C <xemple

Schmatiser l'e7c"tion des process"s selon le"r ordre d<arrie. Po"r celaAon "tilise le $'A<7A& $& <A566

P1P1 P2P2 P3P3 P4P4

e!$s de <ie des $rocessue!$s de <ie des $rocessu00 2424 3232 4444 4747

6emps de traitement mo#en 4 =(> - @) " (2> - ) " ( ->) " (B

-2)* 4 2D3>D82IsetSiliana CHaabani Nizar




"+lorithmes sans préemption 3=C=S? SP=S P=?riorité5 325 +lorithme SP= -- Shortest Po =irst 8SCF -- Shortest ime to

Completion First : +lorithme du ’’lus Court d’+ord ’’ : S"ppose la connaissance des temps d<e7c"tion : estimation de la

d"re de cha("e process"s en attente es process"s sont disponibles sim"ltanment !lgorithme optimal

8sans premption 67c"ter le process"s le pl"s co"rt inimise le temps mo+en

d<e7c"tion ans le cas o pl"sie"rs process"s poss,dent la mme d"reA lapoliti("e FCFS sera alors "tilise.





"+lorithmes sans préemption 3=C=S? SP=SP=?rioritériorité5 325e principe de cet algorithme consiste 2 attrib"er 2

cha("e process"s "ne ale"r ("i indi("e sa priorit.e processe"r est allo" a" process"s de pl"s ha"te

priorit.$n classement possible des process"s est donn comme

s"it 8des process"s les pl"s prioritaires a"7 process"s les

moins prioritaires :1. Process"s s+st,me.

R. Process"s interacti9s.

Q. Process"s batch.

4. Process"s "tilisate"rs.*Jordonnancement a$ec priorité sans ré"uisition peut

enendrer un prol(me de /amine puis"ue les processusde /aile priorité ris"uent dJattendre indé&niment.





+lorithmes a$ec préemption 3rioritériorité? ?ST=5 315 L,idée de la réquisition est d,interrompre un processus en cours

d,eécution n,importe quel momentE

A chaque processus est assinée ( a"tomati("ement par le S6 /e7terneune priorité Assi%nation statique -- priorits D7es 9acile 2 implanter Assi%nation dynamique : la priorit initiale assigne 2 "n process"s pe"t

tre aM"ste 2 d 'a"tres ale"rs di;cile 2 implanter Pb. de famine ? "n process"s de 9aible priorit pe"t ne Mamais s<e7c"ter

si des process"s pl"s prioritaires se prsentent constamment %ecalc"ler priodi("ement le n"mro de priorit des process"s 8pl"sie"rs

F! la priorit d'"n process"s dcro]t 8croit a" co"rs d" temps po"rne pas blo("er les a"tres F!

rincipe : #n lance le process"s a+ant la pl"s grande priorit

0(gorithme dordonnancement 6 c(asses de priorité 0(gorithme dordonnancement 6 c(asses de priorité




















#. oliti"ues d’ordonnancement O+l ith é ti 3 i i é i ité



+lorithmes a$ec préemption 3rioritériorité? ?ST=5 315

0(gorithme dordonnancement 6 c(asses de priorité 0(gorithme dordonnancement 6 c(asses de priorité


#. oliti"ues d’ordonnancement O +lorithmes a$ecpréemption 3ound oinound oin riorité ST=5 325



préemption 3ound oinound oin? riorité? ST=5 325 L,idée de la réquisition est d,interrompre un processus en cours

d,eécution n,importe quel momentE Alorithme tourniquet -- 77 : l'"n des algorithmes les pl"s "tilises et des

pl"s Dables #rdonnancement selon l'ordre FCFS 6("itable Cha("e process"s poss,de "n ("ant"m de temps pendant le("el il s'e7c"te ors("'"n process"s p"ise son ("ant"m de temps : a" s"iant S'il n'a pas Dni : le process"s passe en ("e"e d" to"rni("et et a" s"iant

&emple : e ("ant"m de tempsA YA est gale 2 R "nits= ("el est le temps detraitement mo+en)

&#cution&#cutionCPCP

P1

(/ unités)

P2

(0 unités)

P/

(2 unités)

P0

(/ unités)

P

(2 unités)

P

(0 unités)P3

(4 unités)

P4

(/ unités)

&

& &

&

& &

&

&


+lorithme Tourni"uet -- ound oin 3suite5



6emps de traitement mo#en 4

@-BC 1 -D 1 -EF 1 -FC, 1 -FG 1 -FEH 1 -FHE 1 -EBI <J 7 D3>D

+robl;me 4 rélae du quantum -petit<%rand8 )xe<variable8 estille m+me pour tous les processus K

Les quanta é%aux rendent les diérents processus é%aux

Muantum trop petit proo("e trop de comm"tations de process"s e changement de conte7te deient cofte"7 8perte de temps

CP$ Muantum trop %rand : a"gmentation d" temps de rponse d'"ne

commande 8mme simple %% dgn,re ers FCFS

4é%la%e correct : arie d'"n s+st,me 8resp. d'"ne charge 2 "n'

"

P1P100 22

P2P2 P3P3 P4P4 P5P5 P6P6 P7P7 P8P8 P1P1 P2P2 P4P4 P5P5 P6P644 66 88 1010 1212 1414 1616 1717 1919 2020 2121 2323

P7P7 P6P62525 2626 e!$s de <iee!$s de <ie

,ia+rae de 5antt (&-2 unités)




!lgorithme o"rni("et aec priorits

*e syst(me de estion poss(de n =+ di0érents ni$eaux de priorités 3R di0érents "uanta5

BB n)1 %% n)

1,,

BB1 % %1,,

BB 0 %% 0,,!P' !P'

Réquisition

rri*ée rri*ée

__

))

PrioritPriorit .cheduler ,ispatcher

TerinaisonTerinaison

0 1 2 ------

n)1

! son arrieA le process"s est rang dans la F! la pl"s prioritaire F!0

Si "n process"s dans F!i p"ise son ("ant"m de temps Yi 80 i n-RA il seraplac dans la F!iX1 8moins prioritaire

;ne 2Ai -C i n ne peut +tre servie que si toutes les 2A > -C > i sontvides

un processus qui a traversé toutes les 2A sans épuiser son temps detraitement reste dans la 2A la moins prioritaire. 95IsetSiliana CHaabani Nizar

a$ec préemption 3ound oin? riorité? ST=ST=5

3!5



3 5

+lorithme ST= 3Shortest emainin Time =irst5 -- SP= a$ecré"uisition

Choisir le process"s dont le temps d<e7c"tion restant est le pl"s co"rt Il + a r("isition selon le crit,re de temps d<e7c"tion restant et l<arrie

d'"n process"s Ncessit de sa"egarder le temps restant

<xemple :rocessus )urée estimée )ate d’arri$ée

P1 d 0

PR L R

PQ L Q

P4 R 4

P1P100 22

P2P2 P4P4 P1P144 66 99 1414 2020

e!$s de <iee!$s de <ie

,ia+rae de 5antt

P2P2 P3P3 P1P1

6emps de traitement mo#en 4 =(>@ - @) " (F ->) " ( -2) " (G-)*4 F3D

hori("ementA X S%F oHre "n minim"m de temps d'attente= - di;cile deprdire le 9"t"r 96IsetSiliana CHaabani Nizar

our T+ 1 ?)onner et comparer le temps moyendJexécution produit par les alorithmesdJ d t



dJordonnancement

a. FIF# 8FCFSA P!PS

b. PC6 8SFAc. to"rni("et aec "n ("ant"m de Ld. !lgorithme S%F 8Shortest %emaining ime First

our T+ 2?)onner le diaramme de Gantt et letemps moyen d’exécution pour unordonnancement de type tourni"uet a$ecpriorités


%. iérarchie d’,rdonnancement 315



L’ensemble des processus prts est-il souHent en mémoire centrale?

$n process"s l"A ("i est s"r dis("eA prend bea"co"p pl"s de temps ("'"n

process"s en %! po"r tre charg. es algorithmes d'ordonnancement comple7es permettent de disting"er

entre R t+pes diHrents: 8rdonnancement court terme (short term schedulin) :

consid,re se"lement les process"s prts en mmoire centrale. 8rdonnancement lon terme (lon term schedulin) : consiste 2

"tiliser "n de"7i,me algorithme d'ordonnancement po"r grer lesW'swapping '' des process"s prts entre le dis("e et la %!

iles d"attente des &\Siles d"attente des &\S

""""Sa$ out"" ProcessusSa$ out"" Processus

ile d"attente des Pr@tsile d"attente des Pr@ts

CC

SortieSortie

&\S&\S

Brri<e Brri<e


%. i rarchie d’,rdonnancement325



3 58rdonnancement multi-niHeau permet de satisfaire :

Faoriser les process"s co"rts Faoriser les process"s W''A ("i ne demandent pas trop l '$Cterminer la nat"re de cha("e process"s le pl"tGt possible et

eHect"er l'ordonnancement correspondant Iiles d’attente sans liens : "n process"s se tro"ant dans dans F! i

ne pe"t se tro"er dans F! M 8M i= il reste dans F!i M"s("'2 ce ("'il setermine'I/# 5o"nd

BB n)1

BB1

BB 0

!P' !P'

Réquisition

__

))

Priorit i#ePriorit i#e


Processus .6stèe

Processus "nteractis

(RR)

(F!F.7.8F)


%. iérarchie d’,rdonnancement 3!5



Iiles d’attente aHec liens : hirarchiser les F!s

BB n)1

BB1

BB 0

!P' !P'

Réquisition


(RR)

(F!F.)

rri*ée ni*eau 9

(F!F.)

rri*ée ni*eau 1

rri*ée ni*eau n1

;n processus dans =+i ne peut tre sélectionné "ue si toutes

les =+ 8 38i5 sont toutes $ides ermettre aux processus de se déplacer d’une =+ une autre

iérarchie descendanteDascendanteDidirectionnelle Chanement dynami"ue dans le comportement des processus Cha"ue =+ a son propre alorithme d’ordonnancement

$escendante IAn- est érée aHec ICI

Ascendante I@ est érée aHec ICI100IsetSiliana CHaabani Nizar




Plan d" chapitre



102

Plan d" chapitre1. Introd"ction

R. Fonctions attend"es

Q. &a-et-ient 8s6appin%

4. moire &irt"elleL. !lgo. de %eplacements de Pages

IsetSiliana CHaabani Nizar


1. Introd"ction



103

1. Introd"ctiona mmoire centrale est "ne resso"rce re("ise par

to"t process"s$n programme doit tre charg dans la mmoire

centrale po"r tre e7c"t"emarrerprocessus-p Allouer-taille-p

5erminerprocessus-p Liberer-oneallouée& -p

Problmati("eProblmati("e

*rer les process"s associs 2 des programmes tropol"mine"7*rer le partage de la mmoire ph+si("e entre diHrents

process"s





104

2. =onctions attendues

onoprogrammation: moire rsere a" S6

moire rsere a" se"l process"s en e7c"tion.

"ltiprogrammation: a "ltiprogrammation amliore le ta"7

d'"tilisation d" CP$ mais re("iert "n bonpartitionnement de la mmoire.

! l'initialisation d" s+st,meA la mmoire estdiise en n partitions de taille D7e.

e pr9renceA des partitions ingales en taille. Comment allo"er les process"s a"7 partitions)

"ne Dle d'attente par partition ?8a "ne Dle d'attente po"r to"tes les partitions ?8b


"ltiprogrammation aec des



105

"ltiprogrammation aec despartitions de taille D7e

Fi(e vide

Fi(e p(eine





Principe de partage de la resso"rce mmoire

Fo"rnir "ne mmoire logi("e 2 cha("eprocess"s 8R

*rer les translations entre les mmoireslogi("es et la mmoire ph+si("e 8liaisons

d<adresses


2.=onctions



attendues

moire ph+si("e: mmoire principale %! de la machine!dresses ph+si("es: les adresses de cette mmoiremoire logi("e: l'espace dâdressage d'"n programme

moire ph+si("e :S"ite contig" de mots -J' E' ,F' EG bits selon processeur

!dressage direct alatoire ailles co"rantes : RLZ ega R 2 4 *iga

moire logi("e :6space logi("ement contig"!dressage direct alatoire de mots aille ma7im"m > R ? 1 8 > la capacit d'adressage





ise en "re des mmoires logi("es a"dess"s de la mmoire ph+si("e Swapping 8partage de la mmoire dans le tempsco"page 8partitionnement"ltiple7age

Il est di;cile de donner 2 cha("e programme sonpropre espace d'adressage sol"tion éallocationdynami"ue

éallocation dynami"ue: mapper l'espaced'adressage de cha("e process"s s"r "ne partiediHrente de la mmoire ph+si("e.




Q e a-et-ient



110

Q. e a et ient

8s6appin%

C’est l’utilisation de la mémoire secondaire : la K sap

%le M Stratgie po"r pallier les pn"ries en mmoire.

6lle consid,re cha("e process"s dans son intgralit: e process"s est dans son intgralit en mmoire

o" est s"pprim intgralement de la mmoire





*e $a-et- 3sUappin



*e $a et$ient

3sUappin5

i. 3a5 + est en

mémoire

ii. 3?c5 et C sont

crées

ou charés

depuis le

dis"ueiii. 3d5 + est

trans/érer sur

le dis"uei$. 3e?/5 ) arri$e?

tandis

"ue s’en $a$. 35 +

re$ient


Les diNérentes techniques deLes diNérentes techniques detiti t d l é ititi t d l é i



partitionnement de la mémoire partitionnement de la mémoirecentralecentrale=onction attendue :!llo"er-zone 8t : taille adresseibrer-zone 8a : adresseA t : taille

,8ecti/s :

#ptimiser l'"tilisation de la mmoire 8limiter la9ragmentation#ptimiser les algorithmes d'allocation / libration

Techni"ues :kones contig"s de taille D7eskones contig"s de taille ariableskones non contig"s de taille D7e 8s+st,mes paginskones non contig"s de taille ariable 8s+st,mes

segments





Qeistre de reloe!ent contient la <aleur de l"adresse

$ysi=ue la $lus $etite le reistre de li!ite contientl"tendue des adresses loi=ues $ossiblesca=ue adresse loi=ue doit @tre $lus $etite =ue la <aleurdu reistre li!ite

!llocation Contig"e



!llocation Contig"e

8Cont.

!llocation 2 pl"sie"rs partitions

5rous ? bloc de mmoire disponible= tro"s de tailleariable disperss dans la mmoire ph+si("e

Y"and "n process"s arrieA on l"i allo"e de lammoire dans "n tro" assez large po"r accomoderses besoins

#S retient de l'in9ormation s"r:a blocs allo"s b blocs libres 8tro"s

+S

$rocess 5

$rocess 8

$rocess 2

+S

$rocess 5

$rocess 2

+S

$rocess 5

$rocess 2

+S

$rocess 5

$rocess 9

$rocess 2

$rocess 9

$rocess10




(odule 7 116

%%&: unit' de estion de 'oire unit' de traduction adresses

(eor* anaeent unit)

=ramentation: mémoire



non utilisée

$n probl,me maMe"r dans lâHectationcontig":Il + a assez d 'espace po"r e7c"ter "n

programmeA mais il est 9ragment de 9aKonnon contig"

a 9ragmentation pe"t tre:

e7terne: lêspace in"tilis est entre partitions interne: l 'espace in"tilis est dans les partitions


"artitions (ixes"artitions (ixes



Mémoire principale

su)di*isée en ré!ionsdistinctes+ partitions

es partitions sont soit

de m,me taille ou de

tailles iné!ales ’importe quel pro!r.

peut ,tre a((ecté une

partition qui soit

su((isamment !rande

(+tallins)118IsetSiliana CHaabani Nizar

0l!orithme de placement pour0l!orithme de placement pourpartitions (ixespartitions (ixes

(+tallins)



partitions (ixespartitions (ixes "artitions de tailles iné!ales+ utilisation

de plusieurs (iles assiner ca=ue $rocessus

A la $artition de la $lus$etite taille $ou<ant lecontenir

1 ile $ar taille de $artition tente de !ini!iser la

ra!entation interne

Probl!e' certaines ilesseront <ides s"il n"y a $as de$rocessus de cette taille %r-e#terne,

8(

12(


0l!orithme de placement pour partitions0l!orithme de placement pour partitions(ixes(ixes



"artitions de tailles iné!ales+

utilisation d’une seule (ile

+n coisit la $lus $etite$artition libre $ou<antcontenir le $rocain$rocessus

le ni<eau de!ulti$rora!!ationau!ente au $roit de lara!entation interne +n $ourrait allouer tro$

de !!oire A un$rora!!e

(+tallins)

8(

12(


"artitions d1namiques+ exemple"artitions d1namiques+ exemple%Stallin!s'%Stallin!s'



%d' Il 1 a un trou de 234 apr5s a*oir char!é 6 processus

e prochain processus pourrait demander plus

Si tous les proc sont )loqués %p.ex. attente d’un é*énement'7 "8 peut

,tre suspendu ou permuté et "39:8;4 peut ,tre char!é.

S<apped out


"artitions d1namiques+ exemple"artitions d1namiques+ exemple %Stallin!s'%Stallin!s'



3e-/5 ror. ## est charé. ;n trou de >> 1 >O V 469V 469 est créé

3framentation eterne5 3-h5 1 se termine ou il est suspendu? 2 est repris sa place:

produisant un autre trou de !27-22#V469... Aous a$ons ! trous petits et proal. inutiles. 46R46R6#V2%69 de

/ramentation externe C,+CT+G<C,+CT+G< pour en /aire un seul trou de2%69


la mémoire centrale comporte 6 =ones li)res mais aucune d>elles n>est

asse= !rande pour contenir un pro!ramme ; de :;?4.




"ourtant l>ensem)le des 6 =ones li)res (orme un espace de :8? @ 8? @

:A? 9 6A?4 su((isant pour le pro!ramme ;.

"our permettre l>allocation du pro!ramme ;7 il (aut donc réunir

l>ensem)le des =ones li)res compacta!e

Compactae



Compactae $ne sol"tion po"r la 9ragmentation e7terne)é&nition : e compactage 8o"

d9ragmentation est "ne opration ralisepar le s+st,me d<e7ploitation consistant 2

dplacer to"tes les pages ers desemplacements contiges po"r aoir "n grandespace libre et minimiser ainsi le nombre detro"s mmoires.

désa$antaestemps de trans9ert programmesbesoin de rtablir to"s les liens entre adresses de

diHrents programmes


Probl,me de l'!llocation



+nami("e=irst-&t: !llo"er le premier bloc assez grandest-&t: !llo"er le pl"s petit bloc assez grand=

doit parco"rir la liste enti,re de blocsA sa"9 si

ordonne par taille. Prod"it des restes de blocsles pl"s petits.Worst-&t: !llo"er le pl"s grand bloc= doit

a"ssi rechercher dans to"te la listeA sa"9 siordonne. Prod"it des restes de blocs les pl"s

larges.

Comment satis9aire "ne re("te de taille n 2 partir d'"ne

liste de blocs

First-Dt et best-Dt sont meille"rs ("e worst-Dt en termes derapidit et "tilisation de la mmoire


67ercice



#n consid,re le schma d<allocation de la

mmoire reprsent par la Fig"re 1 et lesprocess"s !A 5A C et 8c. Ces process"s sontordonns s"iant l<ordonnancement %o"nd%obin aec Y"ant"m gal 2 R. Il est demand

de reprsenter le schma d<allocation mmoireen traitant les de"7 cas s"iants : <allocationDrst Fit =@ @ <allocation 5est Fit =@ <allocationorst Fit.




S+st,mes d<67ploitation

Chapitre R. a *estion de la moire Centrale

Partie II. a moire &irt"elle

Contenu du cours Prsentation a pagination -- trans9ormation des adresses es algorithmes de %emplacement

FIF#/%$/#PI!/N%$


1. résentation



128

8bPectif : fournir un espace d’adressae indépendant decelui de la mémoire ph#sique :

es process"s n'"tilise pas to"s les mmoire allo" et il +'a desprogrammes ("i ncessite "n grand partition po"r e7c"t. a mmoire irt"elle permet d<e7c"ter des programmes dont la

taille e7c,de celle de la mmoire ph+si("e

'espace d'adressage l'espace ph+si("e 'espace d'adressage l'espace ph+si("e7éalisation de la mémoire Hirtuelle () %eprsentation ph+si("e : C X S 8dis("e *estion base s"r les techni("es de pagination

+aination -- +rincipe : l'espace d'adressage irt"el est diis en petites "nits -- P!*6S lW espace d'adressage ph+si("e est a"ssi diis en petites "nits --

C!S6S 89rames es pages et les cases sont de mme tailles


Pagination



129

Pagination

6space d'adressage irt"el est diis en paes. es "nits correspondantes dans la mmoire

ph+si("e sont appeles cadres de paes 8 pa%e

frame. IsetSiliana CHaabani Nizar

R. Pagination -- Principe

l<espace d<adressage d" programme est dco"p en morcea"7 linaires demme de taille : la page



130

mme de taille : la page. <espace de la mmoire ph+si("e est l"i-mme dco"p en morcea"7 linaires

de mme taille : la case. charger "n programme en mmoire centrale consiste 2 placer les pages dans n<importe ("elle case disponible taille case > taille page

Case

Processusen (C

Espacedadressage

7irtue(

3

2

1

0

Dis*ue 8M79

+age

7

654321

0

3

.0

.2

1

..

5e charer que les paes utiles un

instant donné 130IsetSiliana CHaabani Nizar

charger "n programme enmmoire centrale consiste 2placer les pages dans n<importe

("elle case disponible.










Paginationable de Paes

P 1Z bit



134

;:B8 - :88;

3?B2 - ;:B:

? - 3?BA

Processe"r 1Z bits

R1Z adresses

irt"elles et Z4o

moire ph+si("e

de QRo

Page de 4o Nbr pages

irt"elles > Z4/4 >

1Z

Nbr cadres depages > QR/4 >




Trans/ormation des adresses $irtuelles 325

Ce transcodae est e0ectué par des circuits matériels de



136

Ce transcodae est e0ectué par des circuits matériels de

estion : unité de estion de mémoire -- ; 3emory

anaement ;nit5

(!oire Centrale

/P;

$

Carte CP

[- *onnes %lecture\criture,

girtuelle

Pysi=ue

Si l'adresse gnre correspond 2 "ne adresse mmoire ph+si("eA le$ transmet s"r le b"s l'adresse relleA sinon il se prod"it "n$&IA96 $& +A<&

Cha("e table des pages contient les champs ncessaires a"transcodageA aec notamment :

1 bit de prsence 8P 1/0 po"r mar("er la prsence de la page enmmoire ph+si("e 136IsetSiliana CHaabani Nizar

émoire Eirtuelle




P1

P0

émoire Eirtuelle



ans cet e7empleA les pages ont "ne taille de 4o.

'adresse irt"elle 1RRR> 810R41RX4 . ellecorrespond 2 "n dplacement de 4octets dans lapage irt"elle QA

correspondant 2 son to"r 2 la page ph+si("e R.

onc l'adresse ph+si("e correspond 2 "ndplacement de 4 octets dans la page ph+si("e Rsoit: 810R4X4>1Z.

a page irt"elle R n'est pas mappe. onc to"teadresse irt"elle comprise entre 1R et 1RRAdonnera lie" 2 "n dé/aut de pae.

L$accès & une adresse virtuelle correspondant & uneL$accès & une adresse virtuelle corres pondant & une pa%e non mappée donne lieu & un défaut de pa%e. pa%e non mappée donne lieu & un défaut de pa%e.


142 >10R4




12242V3172#Y12

5R#

3Y17

2#5R#V

146

10R4

122H

V10R41R




it de résence et )é/aut de ae



141

P ( NP ( Nf case

00

SE

able des $aes

Case libre

(!oire Centrale

Processus

Qrence† Qed!arrer l"instruction

… Qestaurer la table des $aes

‚ *route!ent%*aut de $ae,

la $ae est sur dis=ue

„ Qa!eneren (C la

$aeabsente

†


<xemple et eprésentation d’une Tale desaes

Codae des R Hirtuelle ou réelle



142

Codae des R Hirtuelle ou réelle on rsere les bits de poids ncessaires po"r coder les

n"mros des pages o" des cases les bits de poids 9aibles codent le dplacement

ar exemple? dans un syst(me ayant unemémoire de !2 o et des paes de %12 octets?

cha"ue taleau des paes de$rait contenir: !2oD %12 V 6# 9 paes

aille8page > 4o= aille8C > 4 cases= aille8process"s > 1Zpages Combien de bits a-t-on besoin po"r reprsenter les q

irt"elles et les q relles)

Chaque processus a sa propre table des paes


e calc"l de l<adresse relle 2 partir de l<adresse irt"elle se ralise ainsi :le n"mro de page irt"elle donne l<entre de la P& dans la("elle se




p g (tro"e le n"mro de page ph+si("e =le dplacement est le mme 8les pages ph+si("es et irt"elles ont la

mme taille =si la page irt"elle n<est pas prsente en m.ph+si("eA prod"it "n d9a"t depage.

Po"r acclrer le process"sA on "tilisedes mémoires associatives ("i recensent les




des mémoires associatives ("i recensent lesderni,res pages "tilises :

!. +lorithmes de emplacement deaes ! la s"ite d'"n d9a"t de pageA le S6 doit retirer "ne page de la C po"r



145

p g A p g plibrer de la place man("ante +robl;me : ("elle page choisir 2 dcharger aDn de rc"prer l'espace

et minimiser le nombre de d9a"ts de pages))é&nition : si "n process"s cherche 2 accder 2 "ne page non prsente en

mmoire centraleA il se prod"it ce ("'on appelle "n dé/aut de pae . ors d<"n d9a"t de pageA la page man("ante est charge dans "ne case

libre

----- a totalit des cases de la mmoire centrale pe"ent tre occ"pes ----- Il 9a"t librer "ne case

+lusieurs alorithmes de remplacements : !latoire Premi,re entreA premi,re sortie ? =I=, %emplacement de la page la moins rcemment "tilise -- *; 8east

%ecentl+ $sed #ptimal %emplacement d '"ne page non rcemment "tilise -- N%$ 8Not %ecentl+

$sed


!lgorithmes de %emplacement 8R

+lorithme aléatoire %andom:



146

+lorithme aléatoire -- %andom: a ictime est choisie a" hasard

=I=, : ors d'"n d9a"t de pageA la page la pl"s anciennement charge est la pageretire po"r tre remplace

Facile 2 implanter %emplacement d'"ne page tr,s r9rence trop de d9a"t de pages

<xemple 1 : S"pposons aoir Q cases et 4 pages aec la cha]ne de r9rences"iante :

! 5 C ! 5 ! 5 C 5

cases\ref. A B C A B D A D B C B

1 A , C

2 - A

3 C -

4 d9a"ts depages


=I=, : la page la pl"s anciennement charge est lapage remplace




3 ra!es: 15 $ae aults

+lorithmes de emplacement 3!5

+lorithme ,ptimal :



148

+lorithme ,ptimal : +rincipe :

choisir comme ictime la page ("i sera r9rence le pl"s tard possible Ncessite la connaissanceA po"r chac"ne des pagesA le nombred'instr"ctions ("i seront e7c"tes aant ("e la page soit r9rence

!lgorithme irralisable dans "n conte7te ''oine'' Connaissance des r9rences ("i seront 9aites

'ntért : permet de comparer les per9ormances des a"tres algorithmes &emple : reprendre e7emple 1 en appli("ant optimal

cases\ref. A B C A B D A D B C B

1 A C

2 -

3 C ,

R d9a"ts depages


+lorithmes de emplacement 3#5 +l ith *; 3* t tl ; d5



149

+lorithme *; 3*east ecently ;sed5 : Principe : remplacer la page la moins rcemment "tilise 8accde

%emplacer la page ("i est reste in"tilise le pl"s de temps $ne bonne appro7imation de l'algorithme optimal hori("ement ralisable mais tr,s cofte"7

Ncessite des dispositi9s matriels partic"liers 8compte"r po"rcha("e r9rence

&emple > : nonc e7emple 1 X la cha]ne de r9rence ! 5 C !5 C ! 5 C

cases\ réf. A B C D A B C D A B C D

1 A , C -

2 - A , C

3 C - A ,

%$ : d9a"ts de

pages#ptimal : )











1R 6F!$ P!*6

!lgorithmes de %emplacement 8L+lorithme A; 3Aot ecently ;sed5 :



153

+lorithme A; 3Aot ecently ;sed5 : 'dée : mar("er les pages r9rences

+rincipe : ! cha("e page sont associes de"7 bits % et :

%>1 cha("e 9ois ("e la page est r9rence8lect"re/crit"reA %>0 sinon

>1 lors("e la page a t modiDe dans la mmoirecentrale

!" lancement d'"n process"sA le S6 met 2 zro % et de to"tes lespages Priodi("ementA le bit % est remis 2 0 po"r diHrencier les pages ("i

n'ont pas t rcemment r9rences des a"tres ors d'"n d9a"t de pageA le S6 retire "ne page a" hasard dont la

ale"r % est la pl"s petite :

% > 00 : non r9renceA non modiDe % > 01 : non r9renceA modiDe % > 10 : r9renceA non modiDe % > 11 : r9renceA modiDe

!lgorithme bas s"r "ne sol"tion matrielle


+lorithmes de emplacement --Conclusion



154

Crit;re de performance:

a taille de la C in\"e bea"co"p s"r les per9ormances ("e l 'algorithme : N'essa+er pas de ra;ner "n algorithmeA mais pl"tGt a"gmenterA si

ncessaireA la taille de la mmoireA et ce aDn de minimiser leremplacement.

Question : est-ce ("e le raMo"t de mmoire rd"it to"Mo"rs le nombre ded9a"ts de pages) #"i po"r se"lement optimal et %$ Non po"r FIF#

&emple 2 : on dispose de Q cases mmoires. !ppli("er FIF# 2 la cha]nede r9rences s"iante :

! 5 C ! 5 6 ! 5 C 6 %aMo"ter 1 case et reprendre l 'algorithme de remplacement FIF#.

Concl"re

+$ti!al+$ti!al Q Q NQ NQ I+\Blatoire I+\Blatoire@ -


4. a moire &irt"elle



155

Principe aille programme X donnes X pile pe"t tre aille

mmoire disponible e S6 consere les parties enco"rs d'"tilisation en mmoire et le reste s"r dis("e.

Y"and "n programme attend le chargement d'"ne

partie de l"i-mme il est en attente d'6/S Pagination

es adresses gnres par "n programmes'appellent des adresses $irtuelles? et 9orment

l'espace d'adressage irt"el. a ; 83emory 3ana%ement ;nit' "nit degestion mmoire 9ait la correspondance entre lesadresses irt"elles et les adresses ph+si("es.


O ables de pagesm"ltiniea"7 Processe"r QRbits page de 4o nombre de



156

m"ltiniea"7 Processe"r QRbitsA page de 4o nombre de

pages > RQR

/ R1R

> RR0

pages: "ne table depages de pl"s ("e "n million d'entres

Sans o"blier ("e cha("e process"s a son

propre espace d'adressage et donc sa propre

table de pages

ables de pages m"ltiniea"7: #n ne garde pas en

mmoire to"tes les tables de pages

ables de pages inerses moire !ssociatie o" 5 85ranslation

LooQaside Ruer : "ne petite table des pages les

pl"s r9rencesIsetSiliana CHaabani Nizar

ables de pages

m"ltiniea"7 Second-le*el pa!e ta)les



157

m"ltiniea"7

B =uoi corres$ond l"adresse

<irtuelle sur 32 bits 0#00403004 Y

Exp(e, une adresse <irtuelle sur 32bits est $artitionne en 3 ca!$s


ables de pagesinersesCas dun processeur :2 bits5 &;:<o



158

inersesde mémoire et page de 2<o


O Str"ct"re d'"neentre de la able des



159

entre de la able despages

"résent/ 0)sent+ 1 bit: indi=ue si la $ae est en !!oire ou non-"rotection+ 1 bit %0' Q/: 1' Q, ou 3 bits %Q/.,-

Modi(ié+ 1 bit: une $ae !odiie doit @tre crite sur le dis=ue-

é(érencé' 1 bit: ca=ue ois =ue la $ae est rrence %lue ou crite, il

est !is A 1-

Cache inhi)é+ 1 bit: $er!et d"iniber le cace $our une $ae-


!lgo de remplacement depages

9a"t de page Ch h 2 i 9 i d l l



160

pages Chercher "ne page 2 incerA po"r 9aire de la place po"rla page 2 charger en mmoire.

Si le bit de la page 2 incer > 1A la page doit tresa"e s"r dis("e.

!lgo. optimal Y"estion de per9ormancesA aDn d'iter le rechargement

de pagesA la page 2 incer doit tre pe" "tilise. Jti("eter cha("e page aec le nombre d'instr"ctions ("i

seront e7c"tes aant ("e cette page ne soit r9rence 6incer la page dont l'ti("ette est la X grande 8onrepo"sse ainsi le d9a"t de page a"ssi tard ("e possible

Cet algo est irralisableA le S6 ne sait pas si la page seraitr9rence o" pas "ltrie"rement. Par contreA po"r "neRme e7c"tionA il est possible d'implanter cet algo.


O !lgo N%$ 8Not4ecently ;sed Principe



161

y % ←1A cha("e 9ois ("e la page est l"e o" crite.

←1A cha("e 9ois ("e la page est modiDe. ! cha("e interr"ptionA % ← 0A aDn de disting"er les

pages rcemment r9rences.

Classes de pages Classe 0: non r9renceA non modiDe Classe 1: non r9renceA modiDe Classe R: r9renceA non modiDe Classe Q: r9renceA modiDe

a classe 1 est obten"e par cons( de l'eHacementd" bit % de la classe Q.

'algo N%$ ire "ne page a" hasard dans la Xbasse classe


O !lgo FIF# 8st !n' stout !lgo. FIF#



162

go # e S6 consere "ne liste de pages co"ramment en

mmoire. 6n cas de d9a"t de pageA la X anciennetant en tte de liste est ince.

8- cet algo pe"t irer des pages importantes. 6n eHetA lapage la X ancienne pe"t tre la page la X "tilise.

!lgo. seconde chance C'est l'algo FIF# modiDA tel ("e le bit % de la page la

X ancienne est inspectA

Si % > 1 de la page en tte de listeA la page est

r9renceA et est place 2 la Dn de la liste aec %←

0 et "n instant de chargement act"alis

Si % > 0A page 2 irer 8ancienne et non r9rence.

8- cet algo dplace constamment des pages de la liste.


O !lgo de l'horlogePae

Pae



163

!lgo de l'horloge C'est l'algo de seconde chance aec "ne liste circ"laire

8horloge et "n pointe"r s"r la page la X ancienne.

Y"and "n d9a"t de page s"rientA la page pointe este7amine: Si 4 > 0A la page est ince SinonA 4 ← 0A le pointe"r aance ers la page s"ianteA e process"s se rp,te M"s("'2 tro"er "ne page aec 4

> 0

Paecare en

$re!ier

care

rce!!ent

&n cas de dautde $ae et B tel

=ue Q h 1


O !lgo %$ 8Least4ecently ;sed Principe



164

yp Cet algo est 9ond s"r l'obseration les pa%es les 1

référencées lors des dernières instructions seront probablement utilisées.

$n d9a"t de page ince la page ("i n'a pas t"tilise pendant le pl"s de temps.

Implantations Compte"r de Z4 bits / cadre de page $n d9a"t de page e7amen de to"s les compte"rs

de la table des pages 2 la recherche d" pl"s petitcompte"r

atrice 8n×

nA n cadres Cell"les initialises 2 0 Y"and "ne page Q est r9renceA to"s les bits de la

range Q ← 1A to"s les bits de la colonne Q ← 0 $n d9a"t de page ince la page dont la range est la

X petiteIsetSiliana CHaabani Nizar



O !lgo de ieillissement Principe



166

Cet algo ncessite "n compte"r/ page 8init: 0 ! cha("e interr"ptionA le S6 e7amine to"tes

les pages en mmoireA et po"r cha("e pageson bit % est aMo"t 2 son compte"rA commes"it: 'abordA le compte"r est dcal d'"n bit 2 droite P"isA le bit % est aMo"t a" bit de poids le pl"s 9ort

8de ga"che $ne page ("i n'a pas t r9rence dep"is 4

tops d'horloge a 4 zros dans son compte"rAet a"ra "ne X petite ale"r ("'"ne page ("in'a pas t r9rence dep"is Q topsd'horloge.

9a"t de page: incer la page dont lecompte"r est le X petit


O !lgo de ieillissement




O !lgo de ieillissements %$ iHrence 1:

Slid R 8 l Q 800100000 t L



168

Slide R ?8e les pages Q 800100000 et L

800101000 n'ont pas t r9rences dep"is Rtops d'horloge %$: a"c"n mo+en de disting"er les R pages

car on ne mmorise ("'"n se"l bit/ interalle detemps

!lgo. &ieillissement: la page Q est ire iHrence R:

e compte"r de l'algo de ieillissement a "nnombre Dni de bits 8 dans l'e7pleA on ne pe"tpas disting"er R pages a+ant la mme al d"compte"r.

ans la prati("e "n compte"r s"r bits ests";sant po"r des tops d'horloge ("i seprod"isent to"tes les R0msA "ne page non

r9rence dep"is 1Z0ms n'est pas tr,s "tiliseIsetSiliana CHaabani Nizar

O !lgo T ensemble detraailU Pagination 2 la demande



169

es pages sont charges 2 la demande etnon 2 l'aance bea"co"p de d9a"ts depage a" db"t

6nsemble de raail C'est l'ensemble de pages e7ploites par le

process"s lors des Q r9rences en mmoireles X rcentes

Il est intressant ("e le S6 mmorisel'ensemble de traail de cha("e process"s

et pré-chare en mmoire l'ensemble detraail d" process"s

6n cas de d9a"t de pageA incer "ne page("i ∉ 2 l'ensemble de traail d" process"s


O !lgo T ensemble detraailU




O !lgo SCloc oring Set Cloc 8ensemble de traail X horloge #ptimisation de l'algo bas s"r l'ens de traail ("i



171

#ptimisation de l algo bas s"r l ens. de traailA ("i

ncessite le parco"rs de to"te la table des pages 2cha("e d9a"t de page. Cha("e entre contient: le 5emps de la dernière

utilisationA le bit 4 et le bit 3. ! cha("e d9a"t de pageA la page pointe est

e7amine: Si 4 > 1A c2d la page a t "tilise pendant le top co"rantA 4 ← 0A m2M d temps et le pointe"r aance d'"ne page.

Si 4 > 0 et a%e τ et 3 > 0' c2d la page ∉ 2 l'ens de traail cadre de page 2 librer

Si 4 > 0 et a%e τ et 3 > 1' c2d la page ∉ 2 l'ens de traail

"ne crit"re s"r dis("e de la page est ordonnanceA lepointe"r aance d'"ne page. !insiA mme si le pointe"rreient 2 son point de dpartA l'crit"re serait termine.





Q.R. Conersion d'"ne !dresse &irt"elle

+rocédure ConHersion -#ntrée ? advirt8 Sortie ? adp0ysique"ébut



173

"ébut index 7 advirt.pa%e 1 adressetable-processus

Si -non index.P < pa%e absente < Alors < "éfaut de pa%e<

c0ar%erpa%e-advirt.pa%e' adressecase index.P 7 index.case 7 adressecase

)nsi

adp0ysique 7 adressecase 1 advirt.deplacement 2in+rocédure charerSpae -# ? pa%e8 S ? case"ébut

Si -Non trouvercaselibre- Alors

c0oisircase&libérer-case&libérer' pa%evictimeSi -pa%evictime.3 Alors ecriredisque-pa%evictime )nsi liredisque-casevoilaliberer' pa%e)nsi

2in


4. !"tres Considrations 81 +olitique d’allocation locale*lobale :



174

%emplacement de la page la pl"s ancienne :

*lobale -- la pl"s ancienne d" s+st,me ocale -- la pl"s ancienne d" process"s 6n gnralA l 'allocation globale prod"it de meille"rs rs"ltats

7edémarrae d’une instruction apr;s le défaut de pae La taille d’une pae? In\"e s"r les tables de pages "tilises par la

$ émoire de .A+

o stocer les pages dloges de la C) s"r "n o" pl"sie"rs dis("es loca"7

partition de swap : X rapideA - de place po"r le S*F Fichier de swap : - rapideA X de place po"r les a"tres Dchiers 6n gnralA le S6 "tilise les de"7 sim"ltanment Pl"sie"rs dis("es > swap en parall,le

s"r "n sere"r 8de dis("es distant : Net PCA EA S5A ...


4. !"tres Considrations 8R &croulement -- thrashin

Si le nombre de process"s est tr,s grandA l'espace propre 2 chac"ni ; il l 2 d d9 d



175

p g A p p pest ins";sant et ils passeront le"r temps 2 grer des d9a"ts de pages

6cro"lement d" s+st,me : "ne ha"te actiit de pagination "n process"s s<cro"le lors("'il passe pl"s de temps 2 paginer("'2 s<e7c"ter

Limiter le risque d,écroulement :

*autde $aes

No!bre de $aes

Bllocation$lus de $ae

Qetrait de $ae

=imite supérieure

=imite inférieure

Si "n process"s proo("e trop de d9a"ts de pages : a" dess"s d '"ne limite s"prie"re : on l"i allo"era pl"s de pages en desso"s d'"ne limite in9rie"re : on l"i en retirera

S'il + a pl"s de pages disponibles et trop de d9a"ts de pagesA on deras"spendre "n des process"s


4. !"tres Considrations 8Q

L’espace de traHail -- .orTin set (.)



176

Lespace de traHail .orTin set (.) > les pages d'"n process"s r9rences s"r "n co"rt instant de temps

$ne allocation optimale : allo"er 2 "n process"s acti9 a"tant de pages ("encessite les d9a"ts de pages seront proo(" lors des changements d'espace de

traail Ce mod,le n'est "tilis ("e po"r la prpagination

+répaination ors d" lancement d '"n process"s o" lors de sa reprise apr,s s"spensionA

on proo("e obligatoirement "n certain nombre de d9a"ts de page 6ssa+er de les limiter -- enregistrer aant s"spension !" lancement d '"n programme les 1eres pages de code seront

raisemblablement e7c"tesConclusions co"page en pages et cases de mme taille es pages d'"n process"s ne sont charges en mmoire ph+si("e ("e

lors("e le process"s + acc,de les pages pe"ent tre mises dans n'importe ("elle case ors("'"n process"s acc,de 2 "ne page non prsente en mmoire ph+si("eAil se prod"it "n 6F!$ 6 P!*6 : la page man("ante est alors charge dans "ne case libre pas de case libreA le s+st,me "tilise "n algorithme de remplacement de

page po"r choisir "ne case 2 librer


Chap. II SNC%#NIS!I#N 6 C#$NIC!I#N6N%6 P%#C6SS$S --IPC



177

1.<xemple introducti/ !nt i8+ +>

i7C8 i7C860ile -iC 60ile -iTC i118 i8

printf-U$P VAVN# Xn$$8 printf-U$PFVAVN# Xn$$8

i ariable T partage U ris("e de con\it d'acc,s es instr"ctions iXX et i? doient s'e7c"ter de

mani,re indiisible

e("el des process"s P1 o" PR gagne) &ont-ils terminer) Si l'"n se termineA est-ce ("el'a"tre termine a"ssi)

6st-ce ("e P1 pe"t commencer)


Prsentation d" probl,me



178

+as d’interaction:

67c"tion dans n'importe ("el ordre67c"tion parall,le o" conc"rrente

'nteractions entre processus:

Ncessit de s+nchroniser 'ordre d'e7c"tion est important Cas partic"lier: 67cl"sion m"t"elle ?srialisation des

e7c"tions

o#ens de s#nchronisation:

atriel: mas("age d'interr"ption et !Sest-!nd-Set ogiciel: erro"sA smaphoresA monite"rsA et passage

par messages




Section criti("e --SC $ne partie d'"n programme o se prod"it "n con\it



180

$ne partie d "n programme o se prod"it "n con\it

d'acc,s. Comment iter ce con\it) 5esoin de contrGler l'entre 2 "ne SC 5esoin de s"pporter l'e7cl"sion m"t"elle dans la SC.

$ne bonne sol"tion a" probl,me de SC doitsatis9aire:1.

&clusion mutuelle: acc,s e7cl"si9: 2 to"t instant"n se"l process"s e7c"te sa SC 8resso"rce partage.R. AHancement et absence de blocae: "n

process"s ("i n'est pas dans sa SC ne doit blo("er "na"tre process"s 2 entrer en SC= c-2d pas d'attente s'iln'+ a pas de comptition

Q. Attente bornée (pas de famine: "ne 9ois lademande d'entre en SC est lanceA le process"s nedoit pas attendre indDniment. a demande estass"re de mani,re ("itableA si possible.

!"c"ne h+poth,se ne doit tre 9aite s"r les itessesrelaties des process"s


Str"ct"re +pi("e d'"nProcess"s



181

Process"s

Soient N $rocessus e#cutant le $rora!!e sui<ant'

Do

?\\ ""&ntrer en SC"" X +ro(ogue

SC

\\ ""Sortir de la SC"" X Epi(ogueSNC

>hi(e 8%9-


Q. Sol"tions Possibles



182

U#poth;ses: &itesses relaties des process"s ("elcon("e et inconn" to"t process"s ("itte sa SC a" bo"t d'"n temps Dni

!perK"

#prationsatomi("e

s de ha"tniea"8!PI

&erro"s Smaphores

onite"rs Send/%eceie

#pratio

ns

) _


Q.1. Sol"tions atriellesP tt 2 l' tili t d'i t di t t



183

Permettre 2 l'"tilisate"r d'interdire momentanment

les interr"ptions 8di;cile et dangere"se!"gmenter l'ensemble des actions atomi("esasquae d’interruptions

Probl,me: les process"s "sers ne pe"ent pas

garantir le test et la modiDcation d'"ne ariableSol"tion: Interdire la comm"tation de process"spendant ("'"n process"s est en SC o" encoremas("er les Its 8le s+st,me pe"t le 9aire en modeS&C par "n appel spciD("e.

as("er It SC

emas("er It


Sol"tions atrielles--!S !S 8est !nd Set Instr"ction spciale cable dont le rGle est



184

!S !S 8est-!nd-Set: Instr"ction spciale cable dont le rGle est

de rendre atomi("e le W'test and set'' d" conten" d'"n mot.!nt 5AS -int val9 int temp8 temp7 val8 <<implantée de manière atomique val 7 8 return temp8:

$ne sol"tion a" probl,me de SC po"r n process"s:!nt verrou 7 C8 void 3utex"ebut-+rocessus +i 9"o 60ile -5AS-Yverrou3utex"ebut-8 8S/ :

3utex2in-8 void 3utex2in-SN/ 9 verrou 7 C8 :60ile -8

Pre"e)


Q.R. Sol"tions ogicielles ?!ttente !ctie s"r "n&erro"Soient de"7 process"s P0 et P1



185

+lorithme1: + "ui le tourZPublic <<Zariables parta%ées

int tour7C8 <<tour 7i si Pi veut entrer en S/+rocessus +i

"o60ile -tour 7 i8 << on fait rienS/

tour 7 -i1[F8SN/W0ile -8montrer ("e c'est "ne 9a"sse sol"tion)

67cl"sion m"t"elles satis9aite!ancement non riD: si P0 est pl"s lent ("e

P1 alors P0 blo("e P1= bien ("'il n'est pas danssa SC

Ncessit d'"ne alternance stricte 8Meton


!lgorithmeR



186

Alorithme>: deu drapeau

Public <<Zariables parta%éesint \a%@FI7@CI8 <<\a%@iI7C si Pi est pr+t pour entrer en S/

+rocessus +i "o\a%@iI 7 860ile -\a%@iI 8 << on fait rienS/

\a%@iI 7 C8SN/W0ile -8

montrer ("e c'est "ne 9a"sse sol"tion)67cl"sion m"t"elles satis9aite!ancement non riD: si les process"s arrient en

mme tempsA c-a-d \agu0v > \agu1v >1$ne raie sol"tion consiste del2 combiner les de"7

dernieres


Sol"tion de Peterson



187

Alorithme2 **pour deu processus

Public <<Zariables parta%éesint \a%@FI7@CI8 <<\a%@iI7C si Pi est pr+t pour entreren S/int tour 7 C8

+rocessus +i "o\a%@iI 7 8tour 7 >8 << > 7 -i1[F860ile -\a%@iI YY tour 77 >

8 << on fait rienS/\a%@iI 7 C8SN/W0ile -8

+reuHe de correction?

Cet algorithme satis9ait les Q conditions de SCA 2dmontrer)*nralisation 2 n process"s: oire algorithme de

5aer+


Q.Q. !ttente actie--Concl"sion



188

Concl"sionSol"tions ("i 9o"rnissent des attentes acties

Ine;cace: il 9a"t ("e le process"s en attentelib,re le processe"r e7plicitement 8e7emple la9onction sleep so"s $ni7.

es process"s de priorit le pe"ent trepries 8inersion de priorit

Sol"tions de blocageSmaphores

onite"rs

Send/%eceie


4. es S6!P#%6S

otiHation : s#nchronisation des processus concurrents $ne approche par attente active n'est pas intressanteA p"is("ele processe"r est immobilis simplement po"r attendre



189

le processe"r est immobilis simplement po"r attendre

*aspillage de la p"issance CP$ disponible $ne approche alternatie > "tilisation de smaphores +rincipe et dé%nition des sémaphores

canisme de s+nchronisation simple et ancien entre desprocess"s conc"rrents e principe est directement hrit des chemins de 9er -- Signalm"ni d'"n bras indi("ant si la oie 9erre est libre o" occ"pe

Smaphore le : le process"s P pe"t contin"er sonchemin Smaphore baiss : il doit attendre M"s("<2 ce ("'"n a"treprocess"s Y le l,e 6iter des collisions en ass"rant l<acc,s e7cl"si9 2 "ncroisement 9err

Inents par le mathmaticien !llemand iMstra 81ZL #.1. Syntaxe et Sémanti"ue $n smaphore S est "ne ariable spciale contenant "n nombreentier 8∈IN et manip"l "ni("ement par Q oprations atomi("es :initialisationA P et &


4.1. S+nta7e et Smanti("e d'"n Smaphore

+ -- passer : +()*.ait()*$on() crmenter la ariable S 82 moins ("'elle ne soit dM2 2 0 $tili 8l dM2 0 bl 8 d l



190

$tilise 8lors("e dM2 0 po"r blo("er 8s"spendre le

process"s appelant M"s("<2 ce ("'"n nement s"rienne. --rel]c0er : ()*inal()*9p() Incrmenter le smaphore de 1 $tilise po"r signaler "n nementA et si possibleA

ractier "n process"s en attente. 'nitialisation de : interprte comme "n nombre

d'a"torisations 8disponibles ("and l'entier est positi9A

attend"es ("and le le nombre est ngati9.$éclaration de sémaphores -- 5otation d’Andres Sem S1A SR= Sem ingreduQv>8uQv 1= S1 > 0= SR > 1= !pres initialisationA les se"les oprations permises sont P et

& P8S : ` attendre8S0= S--=

&8S : ` SXX= émaphores énéral HsE sémaphore binaire : Smaphore gnral : pe"t prendre n 'importe ("elle ale"r

non-ngatie Smaphore binaire : la ale"r pe"t tre "ni("ement 0 o" 1


4.1. S+nta7e et Smanti("e d'"n Smaphore 8s"ite

émaphore associé une %le d’attente --émaphore de blocae! cha("e smaphore est associe "ne %le d’attente



191

! cha("e smaphore est associe "ne %le d attente pour les processus bloqués

Création d’un sémaphore énéraltypedef struct semap0ore 9

int valeur8bcp tete8 :

void P-semap0ore S9 if - STvaleur C 9

insérer ce processus dans la 2A associéeRloquer :

:

void Z-semap0ore S9 if - 11STvaleur 7 C 9

supprimer le processus courant de la 2A

associée & ce sémap0ore4éveiller ::

'"tilisation correcte des smaphores ne doit pasdpendre d'"ne gestion partic"li,re de la Dle d'attente


4.R. $tilisation des Smaphores

es smaphores pe"ent tre "tiliss tant po"r la ralisation des sectionscritiques ("e po"r dierses 9ormes de sync0ronisation conditionnelle

C étiti t 2 C é ti é h i é



192

Compétition entre 2 processus Coopération -- sémaphore pri$é

ariables partaées ariables partaéesSemap0ore 3utex78 Semap0ore Sync 7 C8

+rocessus +i +rocessus +@+rocessus +

4epeat ....... .......

P-3utex8 P-Sync8 Z-Sync8

S#/5!ON /4!5!M;# ....... .......

Z-3utex8until \ase8 Il e7iste "ne relation de prcdence P1 ` P0

Conséquence : $n smaphore est to"Mo"rs initialis 2 "ne ale"r non-ngatie mais

pe"t deenir ngatie apr,s "n certain nombre d<oprations P8S --nombre des process"s en attente.


4.Q. Probl,mes de d+s9onctionnement des smaphores

7emarques : a pl"part des mises en "re des smaphores ass"rent ("e les

process"s en attente sont ractis dans l'ordre dans le("el ils ont ts"spend"s s"r le smaphore



193

s"spend"s s"r le smaphore.

6("it dans l'ordonnancement des process"s es smaphores sont les principales primities de s+nchronisationdans $ni7

$n smaphore est "n mcanisme ("i permet le blocage et le reile7plicite. Serir 2 traiter to"s les paradigmes de la programmation

conc"rrente !"c"ne garantie ("'"ne s+nchronisation est e7empte de probl,mes :

'nterblocae 8eadloc -- attente circ"laire $n process"s est blo(" indDniment s'il est en attente d'"n

nement ("i ne pe"t tre prod"it ("e par le process"s dM2en attente

Considrons R process"s "tilisant R smaphores d'e7cl"sionm"t"elleP PF P-S P-SF

P-SF P-S ... ... Iamine 8staration : des process"s ("i s<e7c"tent indDniment sans

a"c"n changement= certains process"s pe"ent ne Mamais obtenir lesresso"rces


4.4. !ttente actie s. 5locage



194

'attente actie est-elle pl"s cofte"se ("e leblocage)

Coft de blocage contre le coft de manip"lation desDles d 'attente X la comm"tation de conte7te)a d"re de l 'attente)

'attente actie pe"t tre meille"re po"r des sectionscriti("es de co"rtes d"resA pl"s partic"li,rement po"r

les m"ltiprocesse"rsA elle est inconto"rnable.


4.L. Probl,mes Classi("es de S+nchronisations

7endeV-Hous -- +rincipe énéral



195

Point de

rende;*ous

Point de

s6nchronisation

P1 P2 Pn

&ersion simpliDe d" probl,me po"r R process"s8gnralisation -- oir S+nchronisation par smaphores pris :

Semaphores arriee1>0A arrieeR > 0=

+rocessus + +rocessus+>

...... .......

&8arriee1= << si%naler mon arrivée &8arrieeR=

P8arrieeR= << attendre l*arrivée de l$autre 195IsetSiliana CHaabani Nizar

4.L. Probl,mes Classi("es de S+nchronisations 8RProbl,me de Prod"cte"r/Consommate"r 8tampon born



196

Contraintes de s#nchronisation : %elation de prcdence : Prod"cte"r `

Consommate"r Section criti("e 8tampon

tampon plein Prod"cte"r se blo("e tampon ide Consommate"r se

blo("e 67cl"sion m"t"elle a" tampon

gide

Plein

Producteur !onsoateur

N cases




4.L. Probl,mes Classi("esde S+nchronisations 84 Considrons ce probl,me comme tant "n s+st,me de rseration



198

+ 8 Probl,me des ecte"rs/%dacte"rs

Considrons ce probl,me comme tant "n s+st,me de rseration

de billets d'aions o pl"sie"rs process"s tentent de lire et d<criredes in9ormations: #n accepte ("e pl"sie"rs lisent ensemble 8degr d<acc,s 1 #n n'a"torise ("'"n se"l process"s 2 modiDer 8on e7cl"t les

lecte"rs et les a"tres rdacte"rs 67cl"sion m"t"elle 8degr> d<acc,s 1

#n s"ppose ("e les lecte"rs sont prioritaires par rapport a"7

rdacte"rs $n rdacte"r blo(" doit attendre le dernier des lecte"rs po"r("'il p"isse entrer en section criti("e

Solution &ariables partages

Semaphore m"te71>1= < protè%e le compteur des lecteurs<

Semaphore m"te7R>1= < %arantir la priorité des lecteursSemaphore wrt>1= < exclusion mutuelle pour les rédacteurs < int nblect>0= < Nombre de lecteurs actifs <


Sol"tion a" Probl,me des ecte"rs/%dacte"rsaec priorit des lecte"rs par rapport a"7 rdacte"rs

+rocessus Lecteur +rocessus 7édacteur



199

......P-mutex8 < accès exclusif & nblect < P-mutexF8 < priorité des lecteurs<

if -11nblect 77 P-6rt8 < accèsexclusif <

P-6rt8 < bloquer les rédacteurs < &criture

Z-mutex8 < libérer l $utilisation de nblect < Z-6rt8 <libérer l*accès exclusif <

Lecture Z-mutexF8

P-mutex8

if -nblect 77 C < si le dernier lecteur <

Z-6rt8 < autoriser une écriture <

Z-mutex8......


L. es #NI6$%S

otiHation : es smaphores pe"ent tre "tiliss po"r rso"dre 2pe" pr,s n<importe ("el probl,mes d<e7cl"sion m"t"elle o"



2

00

pe" pr,s n<importe ("el probl,mes d<e7cl"sion m"t"elle o"

s+nchronisation ... mais les smaphores poss,dent certainsdsaantages : canisme de bas niea" ("i demande "ne disciplines,re dans la 9aKon dont ils sont "tilissA so"s peined<erre"rs: ("e se passe-t-il si on o"blie d<indi("er "nappel 2 &) o" si on eHect"e "ne action P en trop) e rGle d<"ne opration P o" & 8e7cl"sion m"t"elle)

s+nchronisation conditionnelle) dpend d" t+pe desmaphoreA de la 9aKon dont il est initialis et manip"lpar les diers process"s pas e7plicite

oniteur : canisme de s+nchronisation de ha"t niea"A propospar oare et 5rinch ansen. Forme de mod"le ("i s"pporteA 2 l 'aide de de"7

mcanismes indpendantsA l 'e7cl"sion m"t"elle et las+nchronisation conditionnelle. Concept"ellementA "n monite"r sim"le "ne classe en ##8des ariables partages et les mthodes ("i lesmanip"lent $n monite"r est cens ass"rer "ne e7cl"sion m"t"elle 8"nse"l process"s acti9 dans le monite"r d'acc,s a"7 donnes

("'il contient 200IsetSiliana CHaabani Nizar

L.1. S+nta7e et Smanti("e d'"n onite"r

0I0$ES "arta!ées# dEtat

tructure d’unoniteur



2

01

émantique d’un oniteur 45ype abstrait A mais aec des proprits d'e7cl"sion m"t"elle et

de s+nchronisation lors("e le monite"r est partag par pl"sie"rsprocess"s. #n n'a acc,s ("'a"7 procd"res e7ternesA pas a"7 ariables es procd"res sont e7c"tes en e7cl"sion m"t"elle etdonc les ariables internes sont manip"les en e7cl"sion

m"t"elle #n pe"t bloquer et réveiller des taches. e blocage et le

reil s'e7prime a" mo+en de conditions.

d Etat

# Condition

Points

d<entrée

"rocédures

Externe

s"nterne

s

oniteur


L.1. S+nta7e et Smanti("e d'"n onite"r8s"ite#ntae : la 9orme gnrale d'"ne dclaration de monite"r

:



2

02

:

3onitor nommoniteur 9 < "éclarations des variables <

.....8 < variables d*états < /ondition ... 8 < variables conditions <

< "éclarations des procédures

< Public nomfonction -...9 .... :

Public void nomprocedure -..9 .... :

Private .... -...9 ..... :9 < !nitialisation des variables < :


L.1.1. 67cl"sion "t"elle

hilosophie des moniteurs > sparer de 9aKon claire l 'e7cl"sionm"t"elle de la s+nchronisation conditionnelle 8coopration:



2

03

'e7cl"sion m"t"elle est s"pporte de 9aKon implicite : "n appelApar "n process"sA d'"ne procd"re e7porte par le monite"rass"re ("e la procd"re sera e7c"te de 9aKon eclusiHeA c-2-dAa" pl"s "n appel d'"ne procd"re d" monite"r sera acti9 2 "ninstant donn

le monite"r maintient "ne F! des process"s en attente d<entre. es s+nchronisations conditionnelles doient tre dcrites de

9aKon e7plicite 2 l 'aide de ariables condition 8Condition ariables 6n d 'a"tres termesA l’eclusion mutuelle est automatiqueA sa

mise en "re tant ass"re par le langage 8compilate"rA lalibrairieA o" le s+st,me d 'e7ploitationA pas le programme"r l"i-mme.

Lanaes de prorammation !&! 8le meille"r dclarations en e7cl"sion m"t"elle

8W's+nchronized'' certaines mthodes d '"ne classe.!!L -- t+pe protgA obMet protg T protected U= ainsiA to"tesles procd"res de ces obMets protgs sont e7c"tes en e7cl"sion

m"t"elle.







L.R. Similit"des/iHrence entre P/ait et&/Signal

es oprations Wait et P pe"ent to"tes de"7 aoir po"reHet de s"spendre "n process"s ("i e7c"te cette



206

eHet de s"spendre "n process"s ("i e7c"te cetteopration :Wait s"spend to"Mo"rs le process"sP ne le 9ait ("e si la ale"r d" smaphore est ngatie o"

n"lleSi%nal et Z pe"ent ractier "n process"s s"spend" :

Si%nal n 'a a"c"n eHet si a"c"n process"s n'est s"spend"Aalors ("e E a"ra po"r eHet d'incrmenter la ale"r d"

smaphore si a"c"n process"s n 'est s"spend".'mplantation des moniteurs par des sémaphores :

!ss"rer l 'e7cl"sion m"t"elle a" monite"r mutex 8P entre Z apr,s sortie

! cha("e ariable condition sont associs "n smaphore et"n compte"r

ait 8&8m"te7= P8semcond


<xemple: roducer-consumerMonitor ProducerConsu!er

condition ull: e!$tyinte!er count

procedure $roducer)e!in

<hile true do

ite! h $roduce ite!%,



207

procedure insert%ite!'inteer,)e!in

i count h N ten <ait%ull,insertDite!%ite!,count 'h count _ 1i count h 1 teni count h 1 ten si!nal%e!$ty,

endF

(unction re!o<e' inteer)e!in

i( count h 0 ten <ait%e!$ty,re!o<e h re!o<eDite!

count 'h count ) 1i(i( count h N)1count h N)1 ten si!nal%ull,end

count 'h 0end monitor

ite! h $roduceDite!%,

ProducerConsu!er-insert%ite!,end

procedure consu!er)e!in

<hile true do

ProducerConsu!er-re!o<e%,consu!eDite!%ite!,

end


ecte"rs/%dacte"rs1 & b/ t ( #i $i i t t d #i $i b d



208

1.&n ob/et (par e0. un #ic$ier un enreistreent dans un #ic$ier ou une base de

donn'es toute entire) est parta' entre plusieurs actiit's concurrentes.

2.Certaines actiit's les lecteurs) ne odi#ient pas le contenu de lob/et

contraireent à dautres (les 'criains).

3.5es lecteurs peuent donc acc'der siultan'ent au #ic$ier.

4.&n 'criain au contraire doit acc'der seul au #ic$ier.

".+i le #ic$ier est disponible lecteur et r'dacteur ont la 6e priorit'.

7l e0iste plusieurs ersions classiques du proble.




ecte"rs/%dacte"rs



210

variante n°4 : FIFO.5es deandes daccs à lob/et sont series dans lordre

darri'e. +il * a plusieurs lecteurs cons'cuti#s ils sont

seris enseble.

risque : 5e reroupeent des lecteurs est ine##icace si les

deandes sont lecteur8'criain en alternance.





67emple:ecte"rs/%dacte"rst1pe lectureDcriture h moniteur pri*ate criture' )ooléen pri*ate lecteurs' entier



212

pri*ate accordDlecture:accordDcriture' conditionprocédure dbutDlecturedé)ut

si criture ou accordDcriture-nonD<idealors accordDlecture-ait

(indesilecteurs'h lecteurs _ 1accordDlecture-sinal

(in

procédure inDlecturedé)ut

lecteurs'h lecteurs 1si lecteurs h 0 alors accordDcriture-sinal(indesi

(in

Y


procédure dbutDcrituredé)ut

si lecteurs j 0 ou criturealors accordDcriture-ait

(indesicriture'h <rai



213

criture'h <rai(in

procédure inDcrituredé)ut

criture'h au#si accordDlecture-nonD<ide

alors accordDlecture-sinalsinon accordDcriture-sinal

(indesi

(in

dé)ut Ldu !oniteurM

criture'h au#lecteurs'h 0(in


i!$ort lecture criture



214

i!$ort lectureDcriture

$rocessus lecteur L

lectureDcriture-dbutDlecture k lecture j

lectureDcriture-inDlecture M

$rocessus cri<ainL

lectureDcriture-dbutDcriture

k criture jlectureDcriture-inDcriture M




#prations des SI



Priphri("es d'6/S et la CP$ pe"ent s'e7c"tersim"ltanmentCha("e contrGle"r de priphri("e est en charge

d'"n t+pe partic"lier de priphri("esCha("e contrGle"r de priphri("e a "n tampon

localCP$ trans9,re les donnes de/2 la mmoire

centrale a"/d" tampon local6/S se 9ait d" priphri("e a" tampon local d"

contrGle"re contrGle"r de priphri("e in9orme la CP$ ("'ila Dni l'opration en gnrant "ne interr"ption




Str"ct"re des 6/S&* #nchrones ? !pr,s le db"t de l'6/SA le contrGle ne

reto"rne a" process"s "tilisate"r ("'2 la terminaison de



p (

l'opration d'6/SInstruction Wait ("i 9ait attendre la CP$ M"s("'2 la no"elle

interr"ptionoucle Wait 8contentie"7 s"r l'acc,s mmoire

&* As#nchrones ? !pr,s le db"t de l'6/SA le contrGle reto"rnea" process"s "tilisate"r sans attendre la Dn de l'6/S

Appel s#st;me ? re("te 2 l'#S po"r permettre 2 l'"tilisate"rd'attendre la Dn de l'6/S

6able de tatut de +ériphérique contient "ne entre parpriphri("e d'6/S indi("ant son t+peA son adresseA et son tat

'#S regarde dans cette table d'6/S po"r dterminer l'tat d"priphri("eA po"r + aMo"ter "ne re("teA et po"r re\terl'occ"rrence d'"ne interr"ption


e"7 thodes d'6/SSynchronous Asynchronous




Storage Str"ct"re3émoire Principale ? le se"l mdia de stocage ("e



la CP$ pe"t accder directement3émoire Secondaire ? e7tension de la mmoire

centrale ("i oHre "n espace de stocage persistent"isques 3a%nétiques ? platea"7 co"erts de

matriel magnti("e po"r le stocaged'in9ormationsS"r9ace d" dis("e dcompose logi("ement en

pistesA diises elles-mmes en secte"rs

e contrGle"r de dis("e 9ait l'intermdiaire entre la"e logi("e d" dis("e par l'#S et sa dispositionph+si("e relle


iérarchie des ériphéri"ues deStoc@ae




*a lecture sur ledis"ue



"


Principe? les platea"7 to"rnent 2 tr,s ha"te itesse 8entre



QZ00 et 1L000 to"rs/min? la tte de lect"re \otte a"-dess"s d" platea"grce a" co"ssin d'air ind"it 82 10 nm de las"r9ace

? lect"re / crit"re@ crit"re : le co"rant lectri("e dans la tte gn,re

"n champ magnti("e ("i magntise la s"r9ace@ lect"re : la magntisation d" s"pport ind"it "n

co"rant lectri("e dans la tte


Capacité d’un dis"ue



Taille d’une piste

> nb de secte"rs par piste taille d'"n secte"r

Taille d’un cylindre

> nb de 9aces taille d'"ne piste Taille d’un plateau

> nb de pistes par 9ace taille d'"ne piste R

@ Taille du dis"ue> nb de c+lindres taille d'"n c+lindre

> nb de platea"7 taille d'"n platea"


'u’est-ce "u’un



&chier K$ne s"ite de secte"rs

? l'ordre est essentiel


'u’est-ce "u’un



répertoire K "ne collection de noms de Dchiers X "n acc,s 2 la liste de le"rs secte"rs "n rpertoire est l"i-mme "n Dchier 8rang dans

"ne s"ite de secte"rs

*es temps d’acc(sY"and on demande 2 lire "n secte"rA la carte

d<inter9ace a1. Placer les ttes de lect"re s"r le bon c+lindre

R. !ttendre ("e le secte"r cherch arrie so"s la tteQ. Copier le secte"r s"r la carte d<inter9ace.4. 6no+er les donnes de la carte 2 l<ordinate"r.


Temps de lecture emps de lect"re d'"n secte"r> d"re de 1 to"r / nombre de secte"rs par piste



@ "re constante 8e7 : 0AL ms@ bit> le nombre d<octets l"s par seconde si on lisait sans arrt> le nombre d<octets ("i passent so"s la tte en 1 seconde@ emps de latence

> d"re mo+enne d'attente d'"n secte"r > d"re d'"n 1/R to"r@ 67emple? secte"rs de L1R octetsA QR secte"rs par pisteA R00 to"rs/min@ 1Z o par pisteA 1R0 to"rs / s@ dbit ma7 > 1R0 o/s > 1AL o/s

@ temps de lect"re d'"n secte"r > 1/81R0QR > RAL.10-4s >0ARLms

@ temps de latence > 1/81R0R > 4ARms


Cache



$tilisation d'"ne mmoire tr,s rapide d'acc,spo"r maintenir des in9ormationsderni,rement accdes

5esoin d'"ne politit("e de %estion de cac0ee cache introd"it "n a"tre niea" de

stocage5esoin ("e les donnes stoces 2 pl"sie"rs

niea"7 soient co0érents


Trans/ert d’un <ntier [+\ du )is"ue aueistre




!rchitect"re S+st,me*nraleComposition



$n 8o" pl"sie"rs processe"r8smoireContrGle"rs de priphri("esPriphri("es associs5"s de liaison d'n s+st,me in9ormati("e


67emple : architect"rePenti"m




C+cle de &on Ne"mannScenario



67traction d'"ne instr"ction Stocage dans le registre d'instr"ction codage67traction de donnes ent"elles 8oprandes 67c"tionImplémentation e" d'instr"ctions spciD("e 2 cha("e CP$ $tilisation de registres CP$. %egistres spcia"7 : PC

8Program Co"nterA SP 8Stac PointerA PS 8ProgramStat"s ord

!rchitect"res modernes : pipelinesA CP$ s"per-scalairesA %ISC etc.


InitialisationI,S 3asic Input ,utput System5initialise le matriel 8registres processe"rA



mmoire etc. scanne les b"s 8IS! et PCI d'abord po"r tro"er

"npriphri("e amorKable 8bootable Premier secte"r

> partition actie > de"7i,me T boot loader Uo" s+st,mecharge le s+st,me d'e7ploitation en mmoireSyst(me d’<xploitation

Documents

2015 10 02 Sys Exploitation ISET TI1