Cours SE-P1.pdf

Embed Size (px)

Citation preview

  • Cours Systme dexploitation

    Niveau : GL2 / IIA2 / RT2Enseignant : Mona LAROUSSIBureau : 4 A8-28E-mail: [email protected]

    http://www.slideshare.net/secret/mXzhZp1rTxohC6

  • Rfrences bibliographiques

    Leila baccouche, Au cur des systmes dexploitation ; dition CPU. Tunis 2003

    Silberschatz A. Principes appliqus des systmes dexploitations vuibert Paris 99

    Tanenbaum A. Architecture de lordinateur, cours et exercices 4e dition Dunod Paris 2001

    Mohamed said ouerghi, Principe des systmes dexploitation, dition CPU Tunis 2003

  • Plan

    Chapitre 1: Introduction (Matriel, Systme dexploitation) Chapitre 2: Gestion des processus (ordonnancement, tat,

    critres, algorithmes, etc.) Chapitre 3: Communication et synchronisation interprocessus

    (communication, synchronisation, interblocage) Chapitre 4: Gestion de la mmoire (Partition contigu,

    multiprogrammation, pagination, segmentation, etc.) Chapitre 5: Mmoire virtuelle (pagination et segmentation la

    demande) Chapitre 6: Gestion des systmes de fichiers (rpertoire et nom,

    types dobjets, types dinformations, etc.) Chapitre 7: Gestion de priphriques Chapitre 8: Scurit

  • Calendrier des Cours

    COURS Le lundi 11:30 13:00 (RT2) Le mardi de 11:30 13:00( GL2) Le mardi de 9:45 11:15 (IIA2)

  • Chapitre 1: Introduction

    The Osborne 1 - the first commercially successful portable microcomputer.

    released on April 3, 1981 by Osborne Computer Corporation

  • Ordinateur

    Un ordinateur est une machine lectronique qui permet l'excution des programmes

  • Ordinateur (cont.)

    Hardware X Software

    Un programme est un ensemble d'instructions qui seront traduites en signaux lectriques

    La sortie de ces programmes est convertie nouveau pour que l'utilisateur puisse la comprendre

  • Les composants internes

    Un ordinateur est compos au moins de : processeur carte mre mmoire vive mmoires de masse priphriques

  • Processeur C'est le cerveau de l'ordinateur, il contient

    diffrents composants responsables pour l'interprtation des instructions et le calcul

  • Carte Mre

    Elle relie les diffrents composants d'un ordinateur, travers un bus

    La carte mre est aussi responsable de contrler l'accs aux diffrents types d'entre et de sortie

  • La mmoire vive (RAM)

    Pour travailler avec plusieurs donnes, le processeur doit utiliser une mmoire auxiliaire pour sauvegarder temporairement les donnes

    La mmoire RAM (Random Access Memory) est une mmoire volatile, c'est--dire qu'elle ne peut garder des informations que si elle est alimente lectriquement

  • Les mmoires de masse Utiles quand on doit sauvegarder les donnes

    d'une faon persistante (par exemple, quand l'ordinateur est teint) Disque dur, disquette, Cl USB, CD-ROM, etc.

    Plus lentes que la mmoire vive

  • Les priphriques d'entre et sortie

    Ce sont les composants qui permettent l'ordinateur de communiquer avec l'extrieur (utilisateur ou autre ordinateur) Priphriques d'entre : clavier, souris, carte

    rseau, mmoires de masse, etc. Priphriques de sortie : cran, imprimante, carte

    rseau, mmoires de masse, etc.

  • Logiciels (Software)

    Les logiciels le systme

    d'exploitation les applications

    HardwareSystme dexploitation

    Applications

  • Systmes d'exploitations angl. Operating System (OS) Qu'est-ce que c'est?

    Programme assurant la gestion de l'ordinateur et de ses priphriques

    [www.dicofr.com] A quoi ca sert?

    simplifier la vie des utilisateurs et des programmeurs

    grer les ressources de la machine d'une manire efficace

  • Abstraction

    Cacher la complexit des machines pour l'utilisateur afin d'utiliser la machine sans savoir ce qui est derrire

    Abstraction du terme Machine selon Coy: machine relle = Unit centrale + priphriques machine abstraite = machine relle + systme

    d'exploitation machine utilisable = machine abstraite +

    application

  • Exigences un Systme d'exploitation

    Gnralits Satisfaire les utilisateurs et les programmeurs Grer 2D, 3D, vido, audio, rseau, CD, DVD, cl

    USB, ... Plusieurs utilisateurs (itinrants) --> multi-

    utilisateurs tre extensible

    De plus en plus gros et complexe : Efficace, volutif, maintenable

  • Exigences de l'utilisateur

    Faut que a marche ! (comme j'en ai envie ...)

    a imprime pas ...

    = Machine utilisable (machine tendu)

  • Exigences du programmeur

    Simplifier l'accs aux ressources de la machine :

    Mmoire, processeur, priphriques, fichiers, programmes, rseaux, communication interne

    Modle de programmation simple et unifi

    Efficacit dans tous les cas

    = Machine tendue

  • Quelques dfinitions

    Processus Traitement par lots Systmes Multi-tche Systmes Multi-utilisateurs Systmes Multi-processeurs Systmes temps rel Systmes distribus

  • Dfinitions: Processus

    Df.:

    Un processus est un programme lors de l'xcution

    (aspect dynamique d'un programme)

  • Dfinitions:Traitement par lots (Batch processing)

    Un utilisateur donne plusieurscommandes ( Jobs ) dans une queue d'xcution de programmes

    Entirement squentielle p.ex. pour faire plusieurs calculs pendant

    la nuit

    p.ex. autoexec.bat

  • Dfinitions:Systmes Multi-tache (Multitasking)

    Assurer l'xcution de plusieurs programmes en meme temps (c--d. plusieurs processus)

    Chaque processus a besoin du processeur situation concurrente solution: scheduling

  • Dfinitions:Systmes Multi-processeurs systme avec plusieurs processeurs

    parallle vrai multi-tache doit assurer qu'il y a l'xecution d'autant de processus que

    processeurs en meme temps

    contrairement: systme avec un seul processeur quasi-parallle arreter et reprendre les diffrentes processus

    Gestion avec le scheduler (ordonnancement des processus)

  • Dfinitions:Systmes Multi-utilisateurs ( time-sharing )

    permettre a diffrentes personnes de travailler avec un ordinateur en mme temps

    connexion par via le terminal de l'ordinateur lui-mme distance (telnet, ssh, ftp, ...)

    donner l'impression chaque utilisateur qu'il est seul exige une gstion des droits

    de fichiers (pour viter la destruction des fichiers etc.) de processus

  • Dfinitions:Multi-utilisateurs

    Login

    Type: Administrateur ( root ) Groupes Utilisateurs

    pour grer les droits

  • Dfinitions:Systmes Temps rels Sert pour le pilotage et le contrle des droulements

    externes (p.ex. centrale lectrique)

    doit garantir des temps de ractions donnes pour des signaux extrieur urgents

    plusieurs systmes d'exploitations n'y arrivent pas car l'interruption de certaines activits met le systme dans un tat instable

  • Dfinitions:Systmes distribus doit permettre l'xecution d'un seul

    programme sur plusieurs machines

    distribuer les processus et les remettre ensemble

    pour gros calculs, p.ex. inversion de grandes matrices

  • SE: Modle en couches

    Noyau du Systme dexploitation

    Matriel

    Gestion des priphriques (entres/sorties)

    Gestion des fichiers

    Gestion de la mmoire

    Application (Logiciel, p.ex. Microsoft Word)

    Gestion des processus

    PilotePilotePilote

  • Ingrdients

    Gestion de la mmoire Gestion des fichiers Gestion des processus Gestion des priphriques (entres/sorties)

    Contrle des pripheriques via Pilotes (Driver) Quelques logiciels

    Logiciels utilitaires (ls, pwd, format, ...) Logiciels d'application (Bloc-notes, ...) Logiciels de communication (Internet Explorer, ...)

  • Historique (avant les Systmes d'Exploitations)

    1945 - 55 : tubes et interrupteurs Pas de systme d'exploitation

    1955 - 65 : transistors, cartes perfores Traitement par lots

    1965 - 80 : circuits intgrs, disques Multiprogrammation, temps-partag, entres/sorties Unix, version BSD, AT&T, interface POSIX

    1980 -- : ordinateurs personnels (PC) Interface graphique (concept cre vers 1960, Stanford) Rseaux et systmes distribus

    --> Systme d'exploitation ncssaire

  • Systmes d'exploitations

    CP/M (depuis 1974), Digital ResearchUNIX (depuis 1969-1979), premier par

    AT&TMS-DOS (depuis 1981), MicrosoftMacOS (depuis 1984), AppleWindows (depuis 1991), Microsoft Linux (depuis 1992), OpenSource

  • Systmes d'exploitations

    CP/M (depuis 1974), Digital Research Gestion de disque dur, mais pas

    d'arborescence Pas de graphisme Exemple:

    CPU 8088, 2 MHz 64 KO de RAM 5 MO de disque dur

    cf. la loi de Murphy

  • Systmes d'exploitations

    UNIX (depuis 1969-1979), AT&T a servi de modle pour MS-DOS,

    Windows, .. Multi-tche et Multi-utilisateurs

    accs simultan aux fichiers, pripheriques, mmoire, processeurs, ..

    Protection mmoire : aucun programme ne peut faire planter le systme

    systmes de fichiers hirarchique GUI X-Windows

  • Systmes d'exploitations

    MS-DOS (depuis 1981), Microsoft

  • Systmes d'exploitations

    MacOS (depuis 1984), Apple premier GUI

  • Systmes d'exploitation Windows

    Windows 3.11 pas de multitche, pas de multi-utilisateurs

    Windows 95 multi-tche premier systme 32 bit

    Windows 98 Internet integr dans le GUI Plug & Play

    paralllement Windows NT systme d'exploitation rseaux multi-utilisateur

    Windows 2000, et aprs Windows XP jumellage entre systme d'exploitations rseaux et stand-

    alone

  • Systmes d'exploitations

    Linux (depuis 1992), OpenSource finlandais Linus Thorwald Licence GPL (General Public Licence)

    OpenSource Multi-tche et Multi-utilisateurs Distributions

    Red Hat Fedore S.u.S.e Debian Mandrake..

  • Historique

  • Modle en couches

    Noyau du Systme dexploitation

    Matriel

    Gestion des fichiers

    Gestion de la mmoire

    Application (Logiciel, p.ex. Microsoft Word)

    PilotePilotePiloteNoyau du Systme dexploitation

    Matriel

    Gestion des priphriques (entres/sorties)

    Gestion des fichiers

    Gestion de la mmoire

    Application (Logiciel, p.ex. Microsoft Word)

    Gestion des processus

    PilotePilotePilote

  • Modle en couches

    Noyau du Systme dexploitation

    Matriel

    Gestion des fichiers

    Gestion de la mmoire

    Application (Logiciel, p.ex. Microsoft Word)

    PilotePilotePiloteNoyau du Systme dexploitation

    Matriel

    Gestion des priphriques (entres/sorties)

    Gestion des fichiers

    Gestion de la mmoire

    Application (Logiciel, p.ex. Microsoft Word)

    Gestion des processus

    PilotePilotePilote

  • Modle en couches

    Noyau du Systme dexploitation

    Matriel

    Gestion des fichiers

    Gestion de la mmoire

    Application (Logiciel, p.ex. Microsoft Word)

    PilotePilotePiloteNoyau du Systme dexploitation

    Matriel

    Gestion des priphriques (entres/sorties)

    Gestion des fichiers

    Gestion de la mmoire

    Application (Logiciel, p.ex. Microsoft Word)

    Gestion des processus

    PilotePilotePilote

  • 1.2 Rappel sur le fonctionnement de l'UC* appel de sous- programmebranchement et conservation de l'adresse de retourobjectif : pouvoir appeler une squence

    d'instructions de plusieurs endroitsmoyen :conservation de l'adresse de retour (= lecture du

    CO )branchement (= criture du CO )passage de paramtres :convention entre l' appelant et l'appel (sys +lg)

    Chapitre 1. Introduction

  • 1.3 rappels sur les interruptionsinterruption un agent extrieur ( priphrique ou canal)

    interrompt l'UC pour lui faire excuter une partie d'un autre processus

    droutement: mme technique, mais la commutation est due au

    processus en cours ( div par zro, protection mmoire)

    Chapitre 1. Introduction

  • 1.3 rappels sur les interruptionscycle de l'UC avec interruption

    as: adresse sauvegarde COai : adresse 1re instruction excuter sur interruptionIP : boolen vrai ssi interruption prsente IA : boolen vrai ssi traitement interruption autoris

    Chapitre 1. Introduction

  • cycle de l'UC avec interruptionrpter

    RI := Mem[CO];CO :=CO + 1;xcuter (RI);si (IP et IA) alorsdbut

    Mem[as] :=CO;CO :=ai;IP := IA := faux; co=as;

    fin ;jusqu' faux;

    Chapitre 1. Introduction

  • 1.4 rappels sur les E/SE/S = transfert d'informationentre mmoire centrale (et/ou UC) et priphrique

    * une instruction de l'UC initialise ces transfertsavec adresse mmoire, adresse priphrique, sens,

    longueur (plus ou moins explicitement)

    * sur gros ordinateur, un organe autonome le canalconduit ces transferts et prvient l'UC en fin d'E/S .

    Chapitre 1. Introduction

  • 2.1 systmes squentiels avec E/S synchrones2.2 systmes squentiels avec E/S synchrones +"faux" priphriques2.3 systmes squentiels avec E/S asynchrones2.4 systmes avec multi-programmation2.5 systmes multi-processeurs2.6 systmes distribus

    Chapitre 2. Typologie des systmes

  • Phase 1: Les dbuts

    Au dbut, on a observ qu`il y avait des fonctionnalits communes tous les programmes

    il fallait les pr-programmer et les fournir au programmeur moyen d`instructions d` appel: amorage du systme entre/sortie

  • Un ordinateur principal (mainframe)du milieu des annnes 60

    Muse de lhistoire de linformatique http://www.computerhistory.org/

    lecteur de cartes

    rubans

    disques

    UCT (mmoire probablem. autour de 250-500K)

    console oprateur

  • Oui, cartes perforesOui, cartes perfores

    Une ligne de donnes ou de programme tait code dans des trous qui pouvaient tre lus par la machine

  • Oprateur lisant un paquet de cartes perfores

    Source: http://www.tietokonemuseo.saunalahti.fi/eng/kuva_32_eng.htmFinnish Data Processing Museum Association

  • Caractristiques dsirables du matriel (1)

    Protection de la mmoire ne pas permettre aux pgms usager daltrer

    la rgion de la mmoire o se trouve le moniteur

    Minuterie limite le temps qu`une job peut excuter produit une interruption lorsque le temps est

    coul

  • Caractristiques dsirables du matriel (2)

    Instructions privilgies excutables seulement par le moniteur une interruption se produit lorsquun programme usager

    tente de les excuter UCT peut excuter en mode moniteur ou mode usager Les instructions privilgies ne peuvent tre excutes que en

    mode moniteur l usager ne peut excuter que en mode usager seulement le SE ou une interruption peuvent changer de mode

    Interruptions facilitent le transfert de contrle entre le systme

    d exploitation, les oprations d`E/S et les programmes usagers

    Le mode moniteur sera plus souvent appel mode superviseur

  • Les systmes par lots

    Ont t les premiers systmes d`exploitation. Ils sont associs aux concepts suivants:

    langage de contrle de travaux (JCL) systme d exploitation rsident en mmoire

    kernel = noyau

    protection de mmoire instructions privilgies

    modes usager-moniteur interruptions minuterie

    Toutes ces caractristiques se retrouvent dans les systmes daujourdhui

    Encore aujourdhui on parle de jobs par lots quand ils sont excuts squentiellement sans intervention humaine P.ex. salaires, comptabilit dune compagnie

  • Traitement par lots multiprogramm

    Les oprations E/S sont extrmement lentes (compar aux autres instructions)

    Mme avec peu dE/S, un programme passe la majorit de son temps attendre

    Donc: pauvre utilisation de lUCT lorsquun seul pgm usager se trouve en mmoire

    [Stallings]

  • Traitement par lots multiprogramm

    Si la mmoire peut contenir +sieurs pgms, lUCT peut excuter un autre pgm lorsquun pgm attend aprs E/S

    Cest la multiprogrammation

    [Stallings]

  • Plusieurs programmes en mmoire pour la multiprogrammation

  • Exigences pour multiprogrammation

    Interruptions afin de pouvoir excuter dautres jobs lorsquun job attend

    aprs E/S

    Protection de la mmoire: isole les jobs Gestion du matriel

    plusieurs jobs prts tre excutes demandent des ressources:

    UCT, mmoire, units E/S

    Langage pour grer lexcution des travaux: interface entre usager et OS jadis JCL, maintenant shell, command prompt ou

    semblables

  • Spoule ou spooling

    Au lieu d excuter les travaux au fur et mesure quils sont lus, les stocker sur une mmoire secondaire (disque)

    Puis choisir quels programmes excuter et quand Ordonnanceur long terme, discuter

  • quilibre de travaux S`il y a un bon nombre de travaux excuter, on peut chercher

    obtenir un quilibre Travaux qui utilisent peu l`UCT, beaucoup l E/S, sont appels

    tributaires de l`E/S Nous parlons aussi de travaux tributaires de l UCT Le temps d`UCT non utilis par des travaux trib. de l E/S peut

    tre utilis par des travaux trib. de l UCT et vice-versa. L obtention d`un tel quilibre est le but des ordonnanceurs long

    terme et moyen terme ( discuter). Dans les systmes de multiprog. on a souvent coexistence de

    travaux longs et pas urgents avec travaux courts et urgents Le SE donne priorit aux deuximes et excute les premiers

    quand il y a du temps de machine disponible.

  • Phase 3: Systmes temps partag (TSS)

    ordinateur principal (mainframe)

    Terminaux stupides

  • Chaque terminal a sa propre partition de mmoire

  • Systmes temps partag (TSS)

    Le traitement par lots multiprogramm ne supporte pas linteraction avec les usagers excellente utilisation des ressources mais frustration des

    usagers! TSS permet la multiprogrammation de desservir plusieurs

    usagers simultanment

    Le temps d UCT est partag par plusieurs usagers

    Les usagers accdent simultanment et interactivement au systme laide de terminaux

  • Systmes temps partag (TSS) Le temps de rponse humain est lent:

    supposons qu`un usager ncessite, en moyenne, 2 sec du processeur par minute dutilisation

    Environ 30 usagers peuvent donc utiliser le systme sans dlais notable du temps de raction de lordinateur

    Les fonctionnalits du SE dont on a besoin sont les mmes que pour les systmes par lots, plus la communication avec usagers le concept de mmoire virtuelle pour faciliter la

    gestion de mmoiretraitement central des donnes des usagers

  • MULTICS et UNIX

    MULTICS a t un systme TSS des annes 60, trs sophistiqu pour son poque

    Ne russit pas cause de la faiblesse du matriel de son temps

    Quelques unes de ses ides furent reprises dans le systme UNIX

  • Ordinateurs Personnels (PCs)

    Au dbut, les PCs taient aussi simples que les premiers ordinateurs

    Le besoin de grer plusieurs applications en mme temps conduit redcouvrir la multiprogrammation

    Le concept de PC isol volue maintenant vers le concept d ordinateur de rseau (network computer), donc extension des principes des TSS.

  • AujourdhuiAujourdhui

    ordinateur principal (mainframe ou serveur)

    Terminaux intelligents (PCs)

  • Retour aux concepts de TSSRetour aux concepts de TSS

    Plusieurs PC (clients) peuvent tre desservis par un ordi plus puissant (serveur) pour des services qui sont trop complexes pour eux (clients/serveurs, bases de donnes, telecom)

    Les grands serveurs utilisent beaucoup des concepts dvelopps pour les systmes TSS

  • Et puis

    Systmes dexploitation rpartis:

    Le SE excute travers un ensemble de machines qui sont relies par un rseau

    Pas discuts dans ce cours

  • volution des SE

    (fig. mise jour par rapport votre livre)

  • Une synthse historique

    Ordinateurs Personnels

    Mainframes et grands serveurs

    Multics et beaucoup d`autres(1960s)

    Unix (1970)

    MS-DOS(1981)

    Windows(1990)Linux

    (1991)

    Windows NT(1988)

    Windows 2000

    Windows XP

    Solaris (1995)

    Mac/OS(1984)

  • Systmes parallles (tightly coupled) Le petit cot des puces rend possible

    leur composition dans systmes multiprocesseurs

    Les ordinateurs partagent mmoire, horloge, etc.

    Avantages: plus de travail fait (throughput) plus fiable:

    dgradation harmonieuse (graceful degradation)

  • Systmes parallles

    Symtriques Tous les UCTs excutent le mme SE Elles sont fonctionnellement identiques

    Asymtrique Les UCTs ont des fonctionnalits

    diffrentes, par exemple il y a un matre et des esclaves.

    Aujourdhui, tout ordinateur puissant est un systme parallle.

  • Systmes distribus ( = rpartis)

    Les rseaux d ordinateurs sont en pleine mergence...

    Systmes multiprocesseurs faiblement coupls (loosely coupled) consistent d ordinateurs autonomes, qui

    communiquent travers lignes de communication

  • Systmes distribus ( = rpartis)

    SE rpartis il y a un SE qui fonctionne entre ordinateurs l usager voit les ressources loignes

    comme si elles taient locales SE en rseau (network operating

    systems) fournissent: partage de fichiers (systmes client-

    serveur) patrons de communication (protocoles) autonomie des ordinateurs

  • Systmes temps rel

    Doivent ragir ou contrler des vnements externes (p.ex. contrler une usine). Les dlais de raction doivent tre borns

    systmes temps rel souples: les chances sont importantes, mais ne sont pas

    critiques (p.ex. systmes tlphoniques) systmes temps rel rigides (hard):

    le chances sont critiques, p.ex. contrle dune chane d`assemblage graphiques avec animation

  • 88

    Interface utilisateur

    Rle : permet l'utilisateur de dialoguer avec le S.E.

    Moyen : transmet des chanes de caractres (nom des programmes excuter et arguments leur passer).

    Deux possibilits Interprteur de commandes Interface graphique

  • 89

    Interface graphique

    Gnre le texte des commandes par un systme d'icnes et de cases cocher.

    Exemples Windows (Microsoft) Xwindow, Openwin, CDE (Unix)

    Avantage : facilit dutilisation et large accessibilit

    Inconvnient : puissance affaiblie

  • 90

    Interprteur de commandes Lutilisateur tape une commande au clavier

    qui sera ensuite interprte par un programme systme

    Exemples command.com + fichiers .bat (MsDos) sh, csh, tcsh, bash + scripts (Unix)

    Avantage : puissance grce aux fichiers de commandes (branchements, boucles : c'est dj un langage de programmation).

    Inconvnients : Peu convivial.. syntaxe requise.

  • 91

    Protection des fichiers sous Unix

    r(read)

    w(write)

    x(execute)

    a (all)u (user)

    g (group)

    o (others)

    Exemple : rwx r-x r--u g o chmod 754 toto7 5 4

  • 92

    Redirection vers/depuis des fichiers

    Il est possible de : rediriger lentre ou la sortie standards vers un

    fichier en utilisant > , >>, > liste_fichiers cat < liste_fichiers cat < liste_fichiers> resultat

    rediriger la sortie standard dune commande vers lentre standard dune autre commande en utilisant | ls | sort r /*affiche le contenu dun rpertoire tri lenvers*/

  • 93

    Hirarchie des langages

    Langages volus : C, C++, Ada, Java Une instruction C = un ensemble

    d'instructions en langage machine Assembleur : une instruction assembleur

    une instruction en langage machine mais c'est plus lisible.

    Langage machine : format directement lisible par le processeur

  • 94

    Traduction dun programme

    Traducteurs Ce sont des programmes qui transforment

    un code un niveau de la hirarchie (code source) en un code un niveau plus bas, plus prs de la machine (code cible). Certaines erreurs ne sont comprhensibles que si l'on sait comment une instruction est traduite.

    Source CibleTraduction

  • 95

    Programmes et fichiers

    Un programme source (C, assembleur,...) ensemble des instructions qui vont tre traduites

    en un fichier en langage machine directement excutable par le S.E.

    Un programme source peut tre rparti dans plusieurs fichiers (ce qui est souhaitable ds quil devient un peu gros). Notion de projet (en C, C++, JAVA, ) : un

    programme rparti sur plusieurs fichiers

  • 96

    Du code source au programme excutable Le S.E. utilise plusieurs tapes de

    traduction pour transformer du code source (crit en langage volu) en un programme excutable.

    Ces tapes sont (tudies en TD/TP) : Pr-compilation : Source Source Compilation : Source Assembleur Assemblage : Assembleur Langage

    machine Edition des liens : fichier Objet

  • 97

    Pr-Compilation

    Principe : Traitement fichier par fichier o il sagit de

    remplacer les macro-instructions. Le rsultat est encore en langage source.

    Exemples de macro-instruction #define TAILLE 30 // remplacement de toutes les

    occurrences de TAILLE par 30 (expansion)

    #define FOO TAILLE + 3 // FOO sera expans par 30 + 3

    #define MIN(A, B) ((A) > (B)) ? (B) : (A) // MIN (x-y,x+y) sera expans en ( (x-y) > (x+y)) ? (x+y) : (x-y)

  • 98

    Examples (suite)

    #include // le fichier stdio.h l'emplacement des headers standards est copi cet endroit.

    #if VERSION = 4 // code spcifique de la version 4#endif // obligatoire

    #ifdef MAINFILE // code inclure dans le seul fichier principal#endif //obligatoire

  • 99

    Compilation

    La compilation (fichier par fichier) traduit le source en assembleur.

    A cette tape, chaque variable reoit un emplacement mmoire pour stocker sa valeur (ou sa dfinition).

    Toute utilisation de la variable dans la suite du programme est une rfrence.

    Une rfrence est dite externe si elle appelle une variable ou une fonction dont la dfinition se trouve dans un autre fichier source ou un fichier de bibliothque.

  • 100

    Compilation

    Les dclarations dans les headerspermettent de connatre au moins la taille des rfrences externes.

    La position du code assembleur dans le programme complet n'est pas connue, puisqu'on ne sait pas dans quel ordre les diffrents fichiers seront regroups, ni quelle sera la taille des autres fichiers traduits.

    Les rfrences qui ne sont pas encore dfinitivement fixes sont dites relogeables.

  • 101

    Assemblage

    Assemblage (fichier par fichier) : traduction de l'assembleur en langage machine.

    Les rfrences relogeables ou non rsolues sont notes dans un tableau d'en-tte (tableau des rfrences non rsolues)

  • 102

    Edition de liens

    dition de liens (tous les fichiers ensemble) : un fichier objet d'initialisation est ajout (rcupration de la ligne de commande, de l'environnement, certaines routines ou variables de traitement d'erreur, etc.), de mme que les fonctions de bibliothque.

    Tous les fichiers objet sont rassembls en un seul code. Il faut fournir la liste des bibliothques utilises (sauf la bibliothque standard).

  • 103

    Edition de liens

    La plupart des rfrences sont connues, sauf les rfrences absolues (celles qui dpendent de l'adresse de chargement). Le rsultat est un programme excutable.

    On peut aussi faire une dition de lien partielle : plusieurs fichiers objets sont rassembls en un fichier objet plus gros, mais qui n'est pas encore excutable.

  • 104

    Exemples

    En turbo-C, les diffrentes tapes de cration d'un excutable sont accessibles par la fentre de projet, menu contextuel du fichier source (bouton droit)| edit Node Attributes, champ Translator.

    Sous unix, cc enchane sucessivement : le prprocesseur C, le compilateur C, loptimiseur, lassembleur, et lditeur de lien.

  • 105

    Options du cc

    Cet enchanement peut tre contrl grce aux options de la commande cc : cc -c : arrt la fin de la phase de compilation et

    gnration dun fichier objet (.o) cc -S : suppression de la phase dassemblage et

    de la phase ddition de liens, et production dun fichier assembleur (.s)

    cc -O : optimisation pour acclrer la vitesse dexcution du programme

    cc -o nom-fichier : indication du nom du binaire excutable gnr. Quand cette option nest pas prcise, le nom de lexcutable est un a.out.

  • 106

    Exemple On veut utiliser dans un programme

    assembleur la fonction printf du C. Appel printf est ralis par un call far ptr

    printf : appel de procdure standard, mais dans un autre segment de code

    Passage des arguments : Les entiers sont recopis sur la pile. Les chanes sont passes par pointeur far (le

    segment, puis l'offset). Les arguments sont empils en ordre inverse de

    leur appel dans la fonction C. La pile est nettoye dans le programme principal.

  • 107

    DATA segmentx dw 125y dw 12742format db "(%d,%d)"DATA endsCODE segment; printf("(%d,%d)",x,y)push ypush xpush dsmov ax, offset formatpush axcall far ptr _printfadd sp,8CODE ends

  • 108

    Remarques

    A la gnration du code excutable (assemblage, dition de lien) il faut tenir compte de l'appel printf.

    Pour cela, il faut lier les fichiers objet avec la bibliothque standard du C.

  • 109

    Portage sur diffrentes machines et langages machine virtuelle

    Ce qui dpend de la machine ou du S.E. : Le processeur dfinit le langage machine et les

    mnmoniques assembleur. Le systme dfinit le format des excutables. En

    gnral, il fournit un diteur de liens qui dtermine les possibilits d'emploi des rfrences en assembleur.

    Le systme dtermine aussi la liste des appels systme disponibles (fonctions utilisant le matriel, par ex. lecture clavier, disque).

  • 110

    Compatibilit

    Si deux compilateurs de langages diffrents traduisent de la mme faon les noms de variable et de fonction et utilisent des mthodes d'appel de sous-programmes compatibles, on peut lier dans le mme excutable des fichiers objets gnrs par les deux compilateurs.

  • 111

    Portabilit

    Pour disposer du mme langage sur diffrentes machines ou diffrents systmes, on doit chaque fois rcrire le compilateur.

    En pratique, il y a souvent des petites diffrences, ce qui fait que le code passe parfois mal d'un compilateur l'autre.

    Deux solutions ce problme : Premire solution :

    dfinir a priori le compilateur, et porter le mme compilateur sur diffrentes machines.

    C'est le cas de gcc (compilateur C freeware) qui existe l'identique sur la plupart des machines sous Unix (sauf la taille des types de base, qui dpend du processeur).

  • 112

    Portabilit (suite)

    2me solution: Recours une machine virtuelle pour

    garantir la portabilit sur des systmes trs diffrents.

    La technique des machines virtuelles est utilise en particulier par Lisp (List Processor, un des plus anciens

    langages d'intelligence artificielle) et Java.

  • 113

    Machine virtuelle

    On spcifie (dcrit de faon abstraite) une machine avec sa taille de mot, ses registres, ses accs mmoire, son langage machine, son assembleur et son chargeur.

    Il faut alors crire sur chaque type de machine relle et chaque systme d'exploitation un logiciel qui simule la machine virtuelle en respectant scrupuleusement ses spcifications.

  • 114

    Machine virtuelle (suite)

    Tous les compilateurs gnrent le mme code dans le langage de la machine virtuelle, quel que soit le systme et le processeur ce qui facilite l'criture des compilateurs.

    Les programmes compils sur une machine peuvent tre excuts sur une autre sans problme, ce qui est un avantage important.

    Par contre, la machine virtuelle constitue un intermdiaire supplmentaire lors de l'excution, qui est moins rapide que celle d'un excutable dans le langage de la machine relle.

  • 115

    Exemple

    Le JDK sous Dos comporte une machine virtuelle (java.exe), un compilateur/assembleur (javac.exe), un debogueur (jdb.exe), un dsassembleur (javap.exe).

  • Gestion de Processus

    Chapitre 3

  • Concepts importants du ChapitreConcepts importants du Chapitre

    Processus Cration, terminaison, hirarchie

    tats et transitions dtat des processus Process Control Block Commutation de processus

    Sauvegarde, rechargement de PCB Files dattente de processus et PCB Ordonnanceurs court, moyen, long terme Processus communicants

    Producteurs et consommateurs

  • Processus et terminologie(aussi appel job, task, user program)

    Concept de processus: un programme en

    excution

    Possde des ressources de mmoire, priphriques, etc

    Ordonnancement de processus

    Oprations sur les processus

    Processus cooprants

    Processus communicants

  • Cration de processus

    Les processus peuvent crer dautres processus, formant une hirarchie (instruction fork ou semblables)

  • Terminaison de processus

    Un processus excute sa dernire instruction pourrait passer des donnes son parent ses ressources lui sont enleves

    Le parent termine lexcution dun fils (avortement) pour raisons diffrentes le fils a excd ses ressources le fils n`est plus requis

    etc.

  • Arbre de processus en UNIX

  • tat de processus IMPORTANT

    Au fur et a mesure quun processus excute, il change dtat nouveau: le processus vient d tre cr excutant-running: le processus est en train

    d tre excut par l UCT attente-waiting: le processus est en train

    d attendre un vnement (p.ex. la fin d une opration d E/S)

    prt-ready: le processus est en attente dtre excut par l UCT

    terminated: fin d excution

  • Diagramme de transition d`tats d`un processus

    Ordonnanceur = angl. scheduler

  • tats Nouveau, Termin: Nouveau

    Le SE a cr le processus a construit un identificateur pour le processus a construit les tableaux pour grer le processus

    mais ne sest pas encore engag excuter le processus (pas encore admis) pas encore allou des ressources

    La file des nouveaux travaux est souvent appele spoule travaux (job spooler)

    Termin: Le processus n est plus excutable, mais ses

    donnes sont encore requises par le SE (comptabilit, etc.)

  • Transitions entre processus

    Prt Excution Lorsque l ordonnanceur UCT choisit un

    processus pour excution Excution Prt

    Rsultat dune interruption cause par un vnement indpendant du processus Il faut traiter cette interruption, donc le

    processus courant perd lUCT Cas important: le processus puis son intervalle de

    temps (minuterie)

  • Transitions entre processus

    Excution Attente Lorsquun processus fait un appel de

    systme (interruption cause par le processus lui-mme) initie une E/S: doit attendre le rsultat a besoin de la rponse dun autre processus

    Attente Prt lorsque l'vnement attendu se produit

  • Sauvegarde dinformations processus

    En multiprogrammation, un processus excute sur l UCT de faon intermittente

    Chaque fois quun processus reprend l UCT (transition prt excution) il doit la reprendre dans la mme situation o il la laisse (mme contenu de registres UCT, etc.)

    Donc au moment o un processus sort de ltat excution il est ncessaire de sauvegarder ses informations essentielles, quil faudra rcuprer quand il retourne cet tat

  • PCB = Process Control Block: Reprsente la situation actuelle d un processus, pour le reprendre plus tard

    Registres UCT

  • Process Control Block (PCB) IMPORTANT

    pointeur: les PCBs sont rangs dans des listes enchanes ( voir)

    tat de processus: ready, running, waiting compteur programme: le processus doit

    reprendre l instruction suivante autres registres UCT bornes de mmoire fichiers quil a ouvert etc., v. manuel

  • Commutation de processeur Aussi appele commutation de contexte ou context switching

    Quand lUCT passe de lexcution d unprocessus 0 l excution d`un proc 1, il faut mettre jour et sauvegarder le PCB de 0 reprendre le PCB de 1, qui avait t

    sauvegard avant remettre les registres d UCT tels que le

    compteur d instructions etc. dans la mme situation qui est dcrite dans le PCB de 1

  • Commutation de processeur (context switching)

    Il se peut que beaucoup de temps passe avant le retour au processus 0, et que beaucoup dautres proc soient excuts entre temps

  • Le PCB n est pas la seule information sauvegarder

    Il faut aussi sauvegarder l tat des donnes du programme

    Ceci se fait normalement en gardant l image du programme en mmoire primaire ou secondaire (RAM ou disque)

    Le PCB pointera cette image

  • La pile dun processus

    Quand un processus fait appel une procdure, une mthode, etc., il est ncessaire de mettre dans une pile ladresse laquelle le processus doit retourner aprs avoir termin cette procdure, mthode, etc.

    Aussi on met dans cette pile les variables locales de la procdure quon quitte, les paramtres, etc., pour les retrouver au retour

    Chaque lment de cette pile est appel stack frame ou cadre de pile

    Donc il y a normalement une pile dadresses de retour aprs interruption et une pile dadresses de retour aprs appel de procdure Ces deux piles fonctionnent de faon semblable, mais sont

    indpendantes Les informations relatives ces piles (base, pointeur) doivent

    aussi tre sauvegardes au moment de la commutation de contexte

  • La Pile dun processus

    A

    BAppel A Appel B

    PILE

    Donnes P

    Donnes B

    Donnes A

    P

  • Pointeurs de pile processus sauvegarder: base et borne

    cadre 1

    cadre 2

    cadre 3

    cadre 4

    pointeur de base

    pointeur de borne

    La pile fait normal. partie de limage du programme, mais les pointeurs sont normal. des registres dUCT donc il sont sauvegards dans le PCB

  • Rle du matriel et du logiciel dans le traitement dinterruptionsMATRIEL LOGICIEL

    Signal dinterruption gnr

    UCT termine linstruction couranteet dtecte interruption

    Registres dUCT sont sauvegards dans une pile

    UCT saute ladresse trouve dans le vecteur dinterruption

    Infos mises jour etsauvegardes dans PCB

    Le code de traitement de linterruption est excut

    Lordonnanceur choisit unprocessus dans la file prt

    Les registres dUCT sont rechargsavec ce quon avait sauvegard dans PCB pour ce processus,

    qui reprend lexcution

    Les infos relatives ce processus sont rtablies partir de son PCB

    dispatcher

  • Files dattente IMPORTANT

    Les ressources d ordinateur sont souvent limites par rapport aux processus qui en demandent

    Chaque ressource a sa propre file de processus en attente

    un moment donn, un proc ne peut se trouver que dans une seule des diffrentes files du SE

    En changeant dtat, les processus se dplacent d une file l`autre File prt: les processus en tat prt=ready Files associs chaque unit E/S etc.

  • Ce sont les PCBs qui sont dans les files dattente (dont le besoin d un pointeur dans le PCB)

    file prt

    Nous ferons lhypothse que le premier processus dans une file est celui qui utilise la ressource: ici, proc7 excute, proc3 utilise disque 0, etc.

  • Cet ensemble de files inclut donc la table de statut priphriques

    2 fois la mme erreur ici: imprimante devrait tre disque 3

  • Une faon plus synthtique de dcrire la mme situation (pour les devoirs et les examens)

    prt 7 2

    bandmag0

    bandmag1

    disq0 3 14 6

    term0 5

  • Les PCBs ne sont pas dplacs en mmoire pour tre mis dans les diffrentes files: ce sont les pointeurs qui changent.

    ready

    disk unit 0

    . . . PCB4 . . .PCB2 PCB3 PCB5 PCB6 PCB7 PCB14

    term. unit 0

  • Ordonnanceurs (schedulers)

    Programmes qui grent l utilisation de ressources de l`ordinateur

    Trois types d`ordonnanceurs : court terme = ordonnanceur processus:

    slectionne quel processus doit excuter la transition prt excution

    long terme = ordonnanceur travaux: slectionne quels processus peuvent excuter la transition nouveau prt(vnement admitted) (de spoule travaux file prt)

    moyen terme: nous verrons

  • Ordonnanceur travaux = long termeet ordonnanceur processus = court terme

    Ordonnanceur travaux

    Ordonnanceur processus

  • Ordonnanceurs L`ordonnanceur court terme est excut trs

    souvent (millisecondes) doit tre trs efficace

    L`ordonnanceur long terme doit tre excut beaucoup plus rarement: il contrle le niveau de multiprogrammation Un des ses critres pourrait tre la bonne utilisation

    des ressources de lordinateur P.ex. tablir une balance entre travaux lis lUCT

    et ceux lis l E/S

  • Ordonnancement de processus (court terme)

    Disponibilit Ress.

  • Ordonnanceur moyen terme

    Le manque de ressources peut parfois forcer le SE suspendre des processus ils seront plus en concurrence avec les autres pour

    des ressources ils seront repris plus tard quand les ressources

    deviendront disponibles Ces processus sont enlevs de mmoire

    centrale et mis en mmoire secondaire, pour tre repris plus tard `swap out`, `swap in` , va-et-vien

  • Ordonnanceurs Ordonnanceurs courtcourt et et moyen moyen termeterme

    court

    moyen

  • tats de processus dans UNIX Un exemple de diagramme de transitions dtats pour un SE rel

    Kernel, user mode = monitor, user mode

  • Processus cooprants

    Les processus cooprants peuvent affecter mutuellement leur excution

    Avantages de la coopration entre processus: partage de l information efficacit en faisant des tches en parallle modularit la nature du problme pourrait le demander

    P.ex. gestion dvnements indpendants Un proc traite le clavier, un autre traite le modem

  • Le pb du producteur - consommateur

    Un problme classique dans l tude des processus communicants un processus producteur produit des donnes (p.ex.des

    enregistrements d un fichier) pour un processus consommateur

    un pgm dimpression produit des caractres -- consomms par une imprimante

    un assembleur produit des modules objet qui seront consomms par le chargeur

    Ncessit dun tampon pour stocker les items produits (attendant dtre consomms

  • Tampons de communication

    Prod

    Cons

    1 donn

    Prod

    Cons

    1 donn 1 donn1 donn

    Si le tampon est de longueur 1, le producteur et consommateur doivent forcement aller la mme vitesse

    Des tampons de longueur plus grandes permettent une certaine indpendance. P.ex. droite le consommateur a t plus lent

  • Le tampon born (bounded buffer)une structure de donnes fondamentale dans les SE

    b[0] b[1]

    b[7] b[2]

    b[6] b[3]

    b[4]b[5]

    ou

    out: 1re pos. pleine

    in: 1re pos. libre b[0] b[1] b[7]b[2] b[6]b[3] b[4] b[5]

    in: 1re pos. libre

    out: 1re pos. pleine

    bleu: plein, blanc: libre

    Le tampon born se trouve dans la mmoire partage entre consommateur et usager

    lcriture dune nouvelle info dans le tampon, le producteur met jour le pointeur in

    Si le tampon est plein, le prod devra sendormir, il sera plus tard rveill par le consommateur

    Le rle du consommateur est symtrique

  • Utilisation du concept du tampon born

    Les tampons borns sont partout en informatique, et partout dans les SE

    Les files utilises dans un SE sont des tampons borns: Files dattente pour ressources: file prt,

    files pour imprimante, pour disque, etc. Les protocoles de communications

    utilisent des tampons borns: TCP, et autres

    Un client communique avec un serveur par des tampons borns, etc.

  • Ordonnancement Processus

    Chapitre 4

  • Aperu du chapitre

    Concepts de base Critres dordonnancement Algorithmes dordonnancement Ordonnancement de multiprocesseurs Ordonnancement temps rel valuation dalgorithmes

  • Diagramme de transition d`tats d`un processus

  • Files dattente de processus pour ordonnancement

    file prt

    Nous ferons lhypothse que le premier processus dans une file est celui qui utilise la ressource: ici, proc7 excute

  • Concepts de base

    La multiprogrammation vise obtenir une utilisation optimale des ressources, surtout lUCT et aussi un bon temps de rponse pour lusager

    L`ordonnanceur UCT est la partie du SE qui dcide quel processus dans la file ready/prt obtient l UCT quand elle devient libre

    L UCT est la ressource la plus prcieuse dans un ordinateur, donc nous parlons delle Cependant, les principes que nous verrons

    s appliquent aussi l ordonnancement des autres ressources (units E/S, etc).

  • Les cycles dun processus

    Cycles (bursts) dUCT et E/S: lexcution dun processus consiste de squences dexcution sur UCT et dattentes E/S

  • Observation exprimentale: dans un systme typique, nous observerons un grand nombre de court cycles, et un

    petit nombre de long cycles Les programmes tributaires de l UCT auront normalm. un petit nombre de long

    cycles UCT Les programmes tributaires de lE/S auront normalm. un grand nombre de court

    cycles UCT

    Histogramme de dure des cycles UCT

  • Quand invoquer lordonnanceur UCT

    L ordonnanceur UCT doit prendre sa dcision chaque fois que le processus excutant est interrompu, ce-.-d.1. un processus se se prsente en tant que nouveau ou se termine2. un processus excutant devient bloqu en attente3. un processus change dexcutant/running prt/ready4. un processus change de attente prt/ready

    en conclusion, tout vnement dans un systme cause une interruption de lUCT et lintervention de lordonnanceur,

    qui devra prendre une dcision concernant quel proc ou thread aura lUCT aprs

    Premption: on a premption si on enlve lUCT un processus qui lavait et ne la pas laisse de propre initiative P.ex. premption dans le cas 3, pas de premption dans le cas 2

    Plusieurs pbs rsoudre dans le cas de premption, v. manuel

  • Dispatcheur

    Le processus qui donne le contrle au processus choisi par lordonnanceur. Il doit se proccuper de: changer de contexte changer mode usager ramorcer le processus choisi

    Attente de dispatcheur (dispatcher latency) le temps ncessaire pour excuter les fonctions du

    dispatcheur il est souvent nglig, il faut supposer quil soit petit

    par rapport la longueur dun cycle

  • Critres dordonnancement Il y aura normalement plusieurs processus dans la file prt

    Quand lUCT devient disponible, lequel choisir?

    Critres gnraux: Bonne utilisation de lUCT Rponse rapide lusager

    Mais ces critres peuvent tre jugs diffremment...

  • Critres spcifiques dordonnancement

    Utilisation UCT: pourcentage d utilisation Dbit = Throughput: nombre de processus qui

    compltent dans l unit de temps Temps de rotation = turnaround: le temps pris

    par le proc de son arrive sa termin. Temps dattente: attente dans la file prt

    (somme de tout le temps pass en file prt) Temps de rponse (pour les systmes

    interactifs): le temps entre une demande et la rponse

  • Critres dordonnancement: maximiser/minimiser

    Utilisation UCT: pourcentage dutilisation ceci est maximiser

    Dbit = Throughput: nombre de processus qui compltent dans l unit de temps ceci est maximiser

    Temps de rotation (turnaround): temps terminaison moins temps arrive minimiser

    Temps dattente: attente dans la file prt minimiser

    Temps de rponse (pour les systmes interactifs): le temps entre une demande et la rponse minimiser

  • Examinons maintenant plusieurs mthodes dordonnancement et voyons comment elles se comportent par rapport ces critres

  • Premier arrive, premier servi (First come, first serve, FCFS)

    Exemple: Processus Temps de cycleP1 24P2 3P3 3

    Si les processus arrivent au temps 0 dans lordre: P1 , P2 , P3 Le diagramme Gantt est:

    Temps dattente pour P1= 0; P2= 24; P3= 27Temps attente moyen: (0 + 24 + 27)/3 = 17

    P1 P2 P3

    24 27 300

  • Premier arrive, premier servi

    Utilisation UCT = 100% Dbit = 3/30 = 0,1

    3 processus complts en 30 units de temps Temps de rotation moyen: (24+27+30)/3 = 27

    P1 P2 P3

    24 27 300

  • Tenir compte du temps darrive!

    Dans le cas o les processus arrivent moment diffrents, il faut soustraire les temps darrive

    Exercice: rpter les calculs si: P1 arrive temps 0 et dure 24 P2 arrive temps 2 et dure 3 P3 arrive temps 5 et dure 3

    Donc P1 attend 0 comme avant Mais P2 attend 24-2, etc.

    P1 P2 P3

    24 27 300arrive P2

  • FCFS Scheduling (Cont.)Si les mmes processus arrivent 0 mais dans lordre

    P2 , P3 , P1 .Le diagramme de Gantt est:

    Temps dattente pour P1 = 6 P2 = 0 P3 = 3 Temps moyen dattente: (6 + 0 + 3)/3 = 3 Temps de rotation moyen: (3+6+30)/3 = 13 Beaucoup mieux! Donc pour cette technique, les temps peuvent varier grandement

    par rapport lordre darrive de diffrent processus Exercice: calculer aussi le dbit, etc.

    P1P3P2

    63 300

  • Effet daccumulation (convoy effect) dans FCFS

    Supposons un processus tributaire de lUCT et plusieurs tributaires de l`E/S (situation assez normale)

    Les processus tributaires de lE/S attendent pour l UCT: E/S sous-utilise (*)

    Le processus tributaire de lUCT fait une E/S: les autres proc excutent rapidement leur cycle UCT et retournent sur lattente E/S: UCT sous-utilise

    Processus tributaire de lUCT fini son E/S, puis les autres procs aussi : retour la situation (*)

    Donc dans ce sens FCFS favorise les procs tributaires de lUCT Et peut conduire une trs mauvaise utilisation des ressources

    Tant dUCT que de priphriques Une possibilit: interrompre de temps en temps les proc

    tributaires de lUCT pour permettre aux autres procs dexcuter (premption)

  • Plus Court dabord = Shortest Job First (SJF)

    Le processus qui demande moins dUCT part le premier

    Optimal en principe du point de vue du temps dattente moyen (v. le dernier exemple)

    Mais comment savons-nous quel processus demande moins dUCT!

  • SJF avec premption ou non

    Avec premption: si un processus qui dure moins que le restant du processus courant se prsente plus tard, lUCT est enleve au proc courant et donne ce nouveau processus SRTF: shortest remaining-time first

    Sans premption: on permet au processus courant de terminer son cycle Observation: SRTF est logique pour lUCT car le processus

    excutant sera interrompu par larrive du nouveau processus Il est retourn ltat prt

    Il est impossible pour les units qui ne permettent pas de premption p.ex. une unit disque, imprimante

  • Processus Arrive CycleP1 0 7P2 2 4P3 4 1P4 5 4

    SJF (sans premption)

    Temps dattente moyen = (0+(8-2)+(7-4)+(12-5))/4 (0 + 6 + 3 + 7)/4 = 4

    Temps de rotation moyen = 7+(12-2)+(8-4)+(16-5) = 8

    Example de SJF sans premption

    P1 P3 P2

    73 160

    P4

    8 12

    P2 arr. P3 arr. P4 arr

  • Exemple de SJF avec premption

    Processus Arrive CycleP1 0 7P2 2 4P3 4 1P4 5 4

    SJF (premptive)

    Temps moyen d`attente = (9 + 1 + 0 +2)/4 = 3 P1 attend de 2 11, P2 de 4 5, P4 de 5 7

    Temps de rotation moyen = 16+ (7-2) + (5-4) + (11-5) = 7

    P1 P3P2

    42 110

    P4

    5 7

    P2 P1

    16

    P2 arr. P3 arr.P4 arr

  • Tourniquet = Round-Robin (RR)Le plus utilis en pratique

    Chaque processus est allou une tranche de temps (p.ex. 10-100 millisecs.) pour excuter Tranche aussi appele quantum

    Sil excute pour tranche entire sans autres interruptions, il est interrompu par la minuterie et l UCT est donne un autre processus

    Le processus interrompu redevient prt ( la fin de la file) Mthode premptive

    P[0] P[1]

    P[7] P[2]

    P[6] P[3]

    P[4]P[5]

    La file prt est un cercle (dont RR)

  • Performance de tourniquet

    S il y a n processus dans la file prt et la tranche est t, alors chaque processus reoit 1/n du temps UCT dans units de dure max. t

    Si t grand FIFO Si t petit... nous verrons

  • Exemple: Tourniquet tranche = 20

    Processus CycleP1 53P2 17P3 68P4 24

    Observez temps de rotation et temps dattente moyens beaucoup plus levs que SJF mais aucun processus nest favoris

    P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

    0 20 37 57 77 97 117 121 134 154 162

  • Priorits

    Affectation dune priorit chaque processus (p.ex. un nombre entier) souvent les petits chiffres dnotent des

    hautes priorits 0 la plus haute

    LUCT est donne au processus prt avec la plus haute priorit avec ou sans premption il y a une file prt pour chaque priorit

  • Problme possible avec les priorits

    Famine: les processus moins prioritaires narrivent jamais excuter

    Solution: vieillissement: modifier la priorit d un processus en

    fonction de son ge et de son historique d excution

    le processus change de file d`attente Plus en gnral, la modification

    dynamique des priorits est une politique souvent utilise (v. files rtroaction ou retour)

  • Files plusieurs niveaux (multiples)

    La file prt est spare en plusieurs files, p.ex. travaux `darrire-plan` (background - batch) travaux `de premier plan` (foreground - interactive)

    Chaque file a son propre algorithme d ordonnancement, p.ex. FCFS pour arrire-plan tourniquet pour premier plan

    Comment ordonnancer entre files? Priorit fixe chaque file famine possible, ou Chaque file reoit un certain pourcentage de temps UCT,

    p.ex. 80% pour arrire-plan 20% pour premier plan

  • Ordonnancement avec files multiples

  • Files multiples et retour

    Un processus peut passer d une file l autre, p.ex. quand il a pass trop de temps dans une file

    dterminer: nombre de files algorithmes d ordonnancement pour chaque file algorithmes pour dcider quand un proc doit passer

    d une file l`autre algorithme pour dterminer, pour un proc qui

    devient prt, sur quelle file il doit tre mis

  • Files multiples et retour

    PRIO = 0la + leve

    PRIO = 1

    PRIO = 2

  • Exemple de files multiples retour

    Trois files: Q0: tourniquet, tranche = 8 msecs Q1: tourniquet, tranche = 16 msecs Q2: FCFS

    Ordonnancement: Un nouveau processus entre dans Q0, il reoit 8 msecs

    d UCT S il ne finit pas dans les 8 msecs, il est mis dans Q1, il reoit

    16 msecs additionnels S il ne finit pas encore, il est interrompu et mis dans Q2 Si plus tard il commence avoir des cycles plus courts, il

    pourrait retourner Q0 ou Q1

  • En pratique...

    Les mthodes que nous avons vu sont toutes utilises en pratique (sauf plus court servi pur qui est impossible)

    Les SE sophistiqus fournissent au grant du systme une librairie de mthodes, quil peut choisir et combiner au besoin aprs avoir observ le comportement du systme

    Pour chaque mthode, plusieurs params sont disponibles: p.ex. dure des tranches, coefficients, etc.

    Ces mthodes videmment sont importantes seulement pour les ordis qui ont des fortes charges de travail

  • Aussi

    Notre tude des mthodes dordonnancement est thorique, ne considre pas en dtail tous les problmes qui se prsentent dans lordonnancement UCT

    P.ex. les ordonnanceurs UCT ne peuvent pas donner lUCT un processus pour tout le temps dont il a besoin Car en pratique, lUCT sera souvent interrompue par quelque

    vnement externe avant la fin de son cycle Cependant les mmes principes dordonnancement sappliquent

    units qui ne peuvent pas tre interrompues, comme une imprimante, une unit disque, etc.

    Dans le cas de ces units, on pourrait avoir des infos compltes concernant le temps de cycle prvu, etc.

    Aussi, cette tude ne considre pas du tout les temps dexcution de lordonnanceur, du dispatcheur, etc.

  • Systmes temps rel systmes temps rel rigides (hard):

    les chances sont critiques (p.ex. contrle dune chane d`assemblage, animation graphique)

    il est essentiel de connatre la dure des fonctions critiques

    il doit tre possible de garantir que ces fonctions sont effectivement excutes dans ce temps (rservation de ressources)

    ceci demande une structure de systme trs particulire

    systmes temps rel souples (soft): les chances sont importantes, mais ne sont pas

    critiques (p.ex. systmes tlphoniques)

    les processus critiques reoivent la priorit

  • Systmes temps rel:Problmes dattente dans plus. systmes (ex. UNIX)

    Dans UNIX classique il n est pas permis d effectuer changement de contexte pendant un appel du systme - et ces appels peuvent tre longs

    Pour le temps rel il est ncessaire de permettre la premption des appels de systmes ou du noyau en gnral

    Donc ce systme nest pas considr appropri pour le temps rel

    Mais des varits appropries de UNIX ont t conues (p.ex. Solaris)

  • Inversion de priorit et hritage de priorits

    Quand un processus de haute priorit doit attendre pour des processus de moindre priorit (p.ex. a besoin de donnes produites par ces derniers)

    Pour permettre ces derniers de finir rapidement, on peut lui faire hriter la priorit du processus plus prioritaire

  • Synchronisation de Processus

    Chapitre 5

  • Problmes avec concurrence = paralllisme

    Les threads concurrents doivent parfois partager donnes (fichiers ou mmoire commune) et ressources On parle donc de tches coopratives

    Si laccs nest pas contrl, le rsultat de lexcution du programme pourra dpendre de lordre dentrelacement de lexcution des instructions (non-dterminisme).

    Un programme pourra donner des rsultats diffrents et parfois indsirables de fois en fois

  • Un exemple

    Deux threads excutent cette mme procdure et partagent la mme base de donnes

    Ils peuvent tre interrompus nimporte o

    Le rsultat de l excution concurrente de P1 et P2 dpend de l`ordre de leur entrelacement

    M. X demande unerservation davion Base de donnes dit que fauteuil A est disponibleFauteuil A est assign X et marqu occup

  • Vue globale dune excution possible

    M. Guy demande unerservation davion

    Base de donnes dit que fauteuil 30A est disponibleFauteuil 30A est assign Guy et marqu occup

    M. Leblanc demande une rservation davion

    Base de donnes dit que fauteuil 30A est disponible

    Fauteuil 30A est assign Leblanc et marqu occup

    Interruptionou retard

    P1 P2

  • Deux oprations en parallle sur une var a partage(b est priv chaque processus)

    b=a

    b++a=b

    b=ab++a=b

    P1 P2

    Supposons que a soit 0 au dbutP1 travaille sur le vieux a donc le rsultat final sera a=1.Sera a=2 si les deux tches sont excutes lune aprs lautreSi a tait sauvegard quand P1 est interrompu, il ne pourrait pas tre partag avec P2 (il y aurait deux a tandis que nous en voulons une seule)

    interruption

  • 3me exempleThread P1

    static char a;void echo(){

    cin >> a;

    cout > a;cout

  • Autres exemplesDes threads qui travaillent en simultanit sur une

    matrice, par ex. un pour la mettre jour, l`autre pour en extraire des statistiques

    Problme qui affecte le programme du tampon born, v. manuel

    Quand plusieurs threads excutent en parallle, nous ne pouvons pas faire dhypothses sur la vitesse dexcution des threads, ni leur entrelacement Peuvent tre diffrents chaque excution du programme

  • Section Critique

    Partie dun programme dont lexcution de doit pas entrelacer avec autres programmes

    Une fois quun tche y entre, il faut lui permettre de terminer cette section sans permettre autres tches de jouer sur les mmes donnes

  • Le problme de la section critique Lorsquun thread manipule une donne (ou ressource) partage, nous

    disons quil se trouve dans une section critique (SC) (associe cette donne)

    Le problme de la section critique est de trouver un algorithme d`exclusion mutuelle de threads dans l`excution de leur SCs afin que le rsultat de leurs actions ne dpendent pas de lordre dentrelacementde leur excution (avec un ou plusieurs processeurs)

    Lexcution des sections critiques doit tre mutuellement exclusive: tout instant, un seul thread peut excuter une SC pour une var donne (mme lorsquil y a plusieurs processeurs)

    Ceci peut tre obtenu en plaant des instructions spciales dans les sections d`entre et sortie

    Pour simplifier, dornavant nous faisons lhypothse quil ny a qune seule SC dans un programme.

  • Structure du programme Chaque thread doit donc demander une permission

    avant dentrer dans une section critique (SC) La section de code qui effectue cette requte est la

    section dentre La section critique est normalement suivie dune

    section de sortie Le code qui reste est la section restante (SR): non-

    critiquerepeatsection dentresection critiquesection de sortiesection restante

    forever

  • Application

    M. X demande unerservation davionSection dentreBase de donnes dit que fauteuil A est disponibleFauteuil A est assign X et marqu occupSection de sortie

    Section critique

  • Critres ncessaires pour solutions valides

    Exclusion Mutuelle tout instant, au plus un thread peut tre dans une

    section critique (SC) pour une variable donne Non interfrence:

    Si un thread sarrte dans sa section restante, ceci ne devrait pas affecter les autres threads

    Mais on fait l hypothse quun thread qui entre dans une section critique, en sortira.

  • Critres ncessaires pour solutions valides

    Progrs: absence d`interblocage (Chap 8) si un thread demande d`entrer dans une

    section critique un moment o aucun autre thread en fait requte, il devrait tre en mesure dy entrer

  • Aussi ncessaire

    Absence de famine: aucun thread ternellement empch datteindre sa SC

    Difficile obtenir, nous verrons

  • Types de solutions

    Solutions par logiciel des algorithmes dont la validit ne sappuie pas sur

    lexistence d`instruction spciales Solutions fournies par le matriel

    sappuient sur lexistence de certaines instructions (du processeur) spciales

    Solutions fournies pas le SE procure certains appels du systme au programmeur

    Toutes les solutions se basent sur latomicit de laccs la mmoire centrale: une adresse de mmoire ne peut tre affecte que par une instruction la fois, donc par un thread la fois.

    Plus en gnral, toutes les solutions se basent sur l existence dinstructions atomiques, qui fonctionnent comme SCs de base

    Atomicit = indivisibilit

  • Solutions par logiciel(pas pratiques, mais intressantes pour comprendre le pb)

    Nous considrons dabord 2 threads Algorithmes 1 et 2 ne sont pas valides

    Montrent la difficult du problme

    Algorithme 3 est valide (algorithme de Peterson)

    Notation Dbutons avec 2 threads: T0 et T1 Lorsque nous discutons de la tche Ti, Tj dnotera toujours

    lautre tche (i != j)

  • Algorithme 1: threads se donnent mutuellement le tour

    La variable partage turn est initialise 0 ou 1

    La SC de Ti est excute ssi turn = i

    Ti est occup attendre si Tj est dans SC.

    Fonctionne pour lexclusion mutuelle!

    Mais critre du progrs nest pas satisfait car lexcution des SCs doit strictement alterner

    Thread Ti:repeatwhile(turn!=i);

    SCturn = j;

    SRforever

    Ex 1: T0 possde une longue SR et T1 possde une courte SR. Si turn==0, T0 entre dans sa SC et puis sa SR (turn==1). T1 entre dans sa SC et puis sa SR (turn==0), et tente dentrer dans sa SC: refuse! il doit attendre que T0 lui donne le tour.

    Rien faire

  • Thread T0:repeatwhile(turn!=0);

    SCturn = 1;

    SRforever

    Thread T1:repeatwhile(turn!=1);

    SCturn = 0;

    SRforever

    Algorithme 1 vue globale

    Ex 2: Gnralisation n threads: chaque fois, avant quun thread puisse rentrer dans sa section critique, il lui faut attendre que tous les autres aient eu cette chance!

    initialisation de turn 0 ou 1

    Rien faire

  • Algorithme 2 ou lexcs de courtoisie...

    Une variable Boolenne par Thread: flag[0] et flag[1]

    Ti signale quil dsire excuter sa SC par: flag[i] =vrai

    Mais il nentre pas si lautre est aussi intress!

    Exclusion mutuelle ok Progrs pas satisfait: Considrez la squence:

    T0: flag[0] = vrai T1: flag[1] = vrai

    Chaque thread attendra indfiniment pour excuter sa SC: on a un interblocage

    Thread Ti:repeatflag[i] = vrai; while(flag[j]);

    SCflag[i] = faux;

    SRforever rien faire

  • Thread T0:repeatflag[0] = vrai; while(flag[1]);

    SCflag[0] = faux;

    SRforever

    Thread T1:repeatflag[1] = vrai; while(flag[0]);

    SCflag[1] = faux;

    SRforever

    Algorithme 2 vue globale

    T0: flag[0] = vraiT1: flag[1] = vraiinterblocage!

    Aprs vous, monsieur Aprs vous, monsieur

  • Algorithme 3 (dit de Peterson): bon!

    combine les deux ides: flag[i]=intention dentrer; turn= qui le tour

    Initialisation: flag[0] = flag[1] = faux turn = i ou j

    Dsire dexcuter SC est indiqu par flag[i] = vrai

    flag[i] = faux la section de sortie

    Thread Ti:repeatflag[i] = vrai;

    // je veux entrerturn = j;

    // je donne une chance lautre do while (flag[j] && turn==j);

    SCflag[i] = faux;

    SRforever

  • Entrer ou attendre?

    Thread Ti attend si: Tj veut entrer est cest la chance Tj

    flag[j]==vrai et turn==j

    Un thread Ti entre si: Tj ne veut pas entrer ou cest la chance Ti

    flag[j]==faux ou turn==i

    Pour entrer, un thread dpend de lautre quil lui donne la chance!

  • Thread T0:repeatflag[0] = vrai;

    // T0 veut entrer turn = 1; // T0 donne une chance T1

    while(flag[1]&&turn=1);

    SCflag[0] = faux;// T0 ne veut plus entrer

    SRforever

    Thread T1:repeatflag[1] = vrai;

    // T1 veut entrer turn = 0; // T1 donne une chance 0

    while(flag[0]&&turn=0);

    SCflag[1] = faux;// T1 ne veut plus entrer

    SRforever

    Algorithme de Peterson vue globale

  • Scnario pour le changement de contrle

    Thread T0: SC

    flag[0] = faux;// T0 ne veut plus entrer

    SR

    Thread T1:

    flag[1] = vrai;// T1 veut entrer

    turn = 0; // T1 donne une chance T0

    while(flag[0]&&turn=0) ;

    //test faux, entre

    T1 prend la relve, donne une chance T0 mais T0 a dit quil ne veut pas entrer.T1 entre donc dans la SC

  • Autre scnario de changem. de contrleThread T0:

    SCflag[0] = faux;// T0 ne veut plus entrer

    SRflag[0] = vrai;

    // T0 veut entrerturn = 1;

    // T0 donne une chance T1while

    (flag[1]==vrai&&turn=1) ;// test vrai, nentre pas

    Thread T1:

    flag[1] = vrai;// T1 veut entrer

    turn = 0; // T1 donne une chance T0// mais T0 annule cette action

    while(flag[0]&&turn=0) ;

    //test faux, entre

    T0 veut rentrer mais est oblig de donner une chance T1, qui entre

  • Mais avec un petit dcalage, cest encore T0!Thread T0:

    SCflag[0] = faux;// 0 ne veut plus entrer

    RSflag[0] = vrai;

    // 0 veut entrerturn = 1; // 0 donne une chance 1// mais T1 annule cette action

    while(flag[1] && turn=1) ;// test faux, entre

    Thread T1:

    flag[1] = vrai;// 1 veut entrer

    turn = 0; // 1 donne une chance 0

    while(flag[0]&&turn=0);// test vrai, nentre pas

    Si T0 et T1 tentent simultanment dentrer dans SC, seule une valeur pour turn survivra:

    non-dterminisme (on ne sait pas qui gagnera), mais lexclusion fonctionne

  • Donc cet algo. noblige pas une tche dattendre pour dautres qui pourraient ne pas avoir besoin de la SC

    Supposons que T0 soit le seul avoir besoin de la SC, ou que T1 soit lent agir: T0 peut rentrer de suite (flag[1]==faux la dernire fois que T1 est sorti)

    flag[0] = vrai // prend linitiativeturn = 1 // donne une chance lautrewhile flag[1] && turn=1 //test faux, entre

    SCflag[0] = faux // donne une chance lautre

    Cette proprit est dsirable, mais peut causer famine pour T1

  • Algorithme 3: preuve de validit (pas matire dexamen, seulement pour les intresss)

    Exclusion mutuelle est assure car: T0 et T1 sont tous deux dans SC seulement si

    turn est simultanment gal 0 et 1 (impossible)

    Dmontrons que progrs et attente limite sont satisfaits:

    Ti ne peut pas entrer dans SC seulement si en attente dans la boucle while() avec condition: flag[ j] == vrai and turn = j.

    Si Tj ne veut pas entrer dans SC alors flag[ j] = faux et Ti peut alors entrer dans SC

  • Algorithme 3: preuve de validit (cont.)

    Si Tj a effectu flag[ j]=vrai et se trouve dans le while(), alors turn==i ou turn==j

    Si turn==i, alors Ti entre dans SC. turn==j alors Tj entre dans SC mais il fera flag[ j]

    =false la sortie: permettant Ti dentrer CS mais si Tj a le temps de faire flag[ j]=true, il devra

    aussi faire turn=i Puisque Ti ne peut modifier turn lorsque dans le

    while(), Ti entrera SC aprs au plus une entre dans SC par Tj (attente limite)

  • A propos de lchec des threads Si une solution satisfait les 3 critres (EM, progrs et

    attente limite), elle procure une robustesse face lchec dun thread dans sa section restante (SR) un thread qui choue dans sa SR est comme un thread

    ayant une SR infiniment longue... Par contre, aucune solution valide ne procure une

    robustesse face l'chec dun thread dans sa section critique (SC) un thread Ti qui choue dans sa SC nenvoie pas de

    signal aux autres threads: pour eux Ti est encore dans sa SC...

  • Extension >2 threads

    L algorithme de Peterson peut tre gnralis au cas de >2 threads

    Cependant, dans ce cas il y a des algorithmes plus lgants, comme lalgorithme du boulanger, base sur lide de prendre un numro au comptoir... Pas le temps den parler

  • Une leon retenir

    fin que des threads avec des variables partages puissent russir, il est ncessaire que tous les threads impliqus utilisent le mme algorithme de coordination Un protocole commun

  • Critique des solutions par logiciel

    Difficiles programmer! Et comprendre! Les solutions que nous verrons dornavant sont

    toutes bases sur lexistence dinstructions spcialises, qui facilitent le travail.

    Les threads qui requirent lentre dans leur SC sont occups attendre (busy waiting); consommant ainsi du temps de processeur Pour de longues sections critiques, il serait

    prfrable de bloquer les threads qui doivent attendre...

  • Solutions matrielles: dsactivation des interruptions Sur un uniprocesseur:

    exclusion mutuelle est prserve mais lefficacit se dtriore: lorsque dans SC il est impossible dentrelacer lexcution avec dautres threads dans une SR

    Perte dinterruptions Sur un multiprocesseur:

    exclusion mutuelle nest pas prserve

    Une solution qui nest gnralement pas acceptable

    Process Pi:repeatinhiber interruptsection critiquertablir interruptsection restante

    forever

  • Solutions matrielles: instructions machine spcialises

    Normal: pendant quun thread ou processus fait accs une adresse de mmoire, aucun autre ne peut faire accs la mme adresse en mme temps

    Extension: instructions machine excutant plusieurs actions (ex: lecture et criture) sur la mme case de mmoire de manire atomique (indivisible)

    Une instruction atomique ne peut tre excute que par un thread la fois (mme en prsence de plusieurs processeurs)

  • Linstruction test-and-set

    Une version C de test-and-set:

    Un algorithme utilisant testset pour Exclusion Mutuelle:

    Variable partage b est initialise 0

    Le 1er Pi qui met b 1 entre dans SC

    bool testset(int& i){if (i==0) {

    i=1;return true;

    } else {return false;

    }}

    Tche Pi:while testset(b)==false ;

    SC //entre quand vraib=0;

    SR

    Instruction atomique!

  • Linstruction test-and-set (cont.)

    Exclusion mutuelle est assure: si Ti entre dans SC, lautre Tj est occup attendre

    Problme: utilise encore occup attendre Peut procurer facilement lexclusion

    mutuelle mais ncessite algorithmes plus complexes pour satisfaire les autres exigences du problme de la section critique

    Lorsque Ti sort de SC, la slection du Tj qui entrera dans SC est arbitraire: pas de limite sur lattente: possibilit de famine

  • Instruction change

    Certains UCTs (ex: Pentium) offrent une instruction xchg(a,b) qui interchange le contenue de a et b de manire atomique.

    Mais xchg(a,b) souffre des mme lacunes que test-and-set

  • Utilisation de xchg pour exclusion mutuelle (Stallings) Variable partage b est initialise

    0 Chaque Ti possde une variable

    locale k Le Ti pouvant entrer dans SC est

    celui qui trouve b=0 Ce Ti exclue tous les autres en

    assignant b 1 Quand SC est occupe, k et b

    seront 1 pour un autre thread qui cherche entrer

    Mais k est 0 pour le thread qui est dans la SC

    Thread Ti:repeatk = 1while k!=0 xchg(k,b);SCxchg(k,b);SRforever

    usage:

  • Solutions bases sur des instructions fournies par le SE (appels du systme) Les solutions vues jusqu prsent sont

    difficiles programmer et conduisent du mauvais code.

    On voudrait aussi qu`il soit plus facile dviter des erreurs communes, comme interblocages, famine, etc. Besoin dinstruction plus haut niveau

    Les mthodes que nous verrons dornavant utilisent des instructions puissantes, qui sont implantes par des appels au SE (system calls)

  • Smaphores Un smaphore S est un entier qui, sauf pour

    l'Initialisation, est accessible seulement par ces 2 oprations atomiques et mutuellement exclusives: wait(S) (appel P dans le livre) signal(S) (appel V dans le livre)

    Il est partag entre tous les procs qui s`intressent la mme section critique

    Les smaphores seront prsents en deux tapes: smaphores qui sont occups attendre (busy waiting) smaphores qui utilisent des files d attente

    On fait distinction aussi entre smaphores compteurs et smaphores binaires, mais ce derniers sont moins puissants (v. livre).

  • Spinlocks dUnix: Smaphores occups attendre (busy waiting)

    La faon la plus simple dimplanter les smaphores.

    Utiles pour des situations o lattente est brve, ou il y a beaucoup dUCTs

    S est un entier initialis une valeur positive, de faon que un premier thread puisse entrer dans la SC

    Quand S>0, jusqu n threads peuvent entrer

    S ne peut pas tre ngatif

    wait(S):while S=0 ;S--;

    signal(S):S++;

    Attend si no. de threads qui peuvent entrer = 0

    Augmente de 1 le no des threads qui peuvent entrer

  • AtomicitWait: La squence test-dcrment est atomique, mais pas la boucle!

    Signal est atomique.

    Rappel: les sections atomiques ne peuvent pas tre excutes simultanment par diffrent threads

    (ceci peut tre obtenu un utilisant un des mcanismes prcdents)

    S = 0

    atomique S - -

    F

    V

    SC

  • Atomicit et interruptibilit

    S = 0

    atomique S - -

    F

    VS++

    La boucle nest pas atomique pour permettre un autre thread dinterrompre lattente sortant de la SC

    interruptible autre thr.

    SC

    SC

  • Utilisation des smaphores pour sections critiques

    Pour n threads Initialiser S 1 Alors 1 seul thread

    peut tre dans sa SC Pour permettre k

    threads dexcuter SC, initialiser S k

    Thread Ti:repeatwait(S);SC

    signal(S);SR

    forever

  • Thread T1:repeatwait(S);

    SCsignal(S);

    SRforever

    Thread T2:repeatwait(S);SCsignal(S);SR

    forever

    Semaphores: vue globale

    Initialise S >=1

    Peut tre facilement gnralis plus. threads

  • Utilisation des smaphores pour synchronisation de threads On a 2 threads: T1

    et T2 nonc S1 dans T1

    doit tre excut avant nonc S2 dans T2

    Dfinissons un smaphore S

    Initialiser S 0

    Synchronisation correcte lorsque T1 contient:

    S1;signal(S);

    et que T2 contient:wait(S);S2;

  • Interblocage et famine avec les smaphores Famine: un thread peut narriver jamais

    excuter car il ne teste jamais le smaphore au bon moment

    Interblocage: Supposons S et Q initialiss 1

    T0 T1

    wait(S)

    wait(Q)

    wait(Q) wait(S)

  • Smaphores: observations

    Quand S >= 0: Le nombre de threads qui peuvent excuter

    wait(S) sans devenir bloqus = S S threads peuvent entrer dans la SC noter puissance par rapport mcanismes dj vus dans les solutions o S peut tre >1 il faudra avoir un 2me

    sm. pour les faire entrer un la fois (excl. mutuelle)

    Quand S devient > 1, le thread qui entre le premier dans la SC est le premier tester S (choix alatoire) ceci ne sera plus vrai dans la solution

    suivante

    wait(S):while S=0 ;S--;

  • Comment viter lattente occupe et le choix alatoire dans les smaphores Quand un thread doit attendre quun

    smaphore devienne plus grand que 0, il est mis dans une file dattente de threads qui attendent sur le mme smaphore.

    Les files peuvent tre PAPS (FIFO), avec priorits, etc. Le SE contrle l`ordre dans lequel les threads entrent dans leur SC.

    wait et signal sont des appels au SE comme les appels des oprations dE/S.

    Il y a une file d attente pour chaque smaphore comme il y a une file dattente pour chaque unit dE/S.

  • Smaphores sans attente occupe

    Un smaphore S devient une structure de donnes: Une valeur Une liste dattente L

    Un thread devant attendre un smaphore S, est bloqu et ajoutla file dattente S.L du smaphore (v. tat bloqu = attente chap 4).

    signal(S) enlve (selon une politique juste, ex: PAPS/FIFO) un thread de S.L et le place sur la liste des threads prts/ready.

  • Implementation (les botes rprsentent des squences non-interruptibles)

    wait(S): S.value --;if S.value < 0 { // SC occupe

    add this thread to S.L;block // thread mis en tat attente

    (wait)

    }

    signal(S): S.value ++;if S.value 0 { // des threads attendent

    remove a process P from S.L;wakeup(P) // thread choisi devient prt

    }S.value doit tre initialis une valeur non-ngative (dpendant de lapplication, v. exemples)

  • Figure montrant la relation entre le contenu de la file et la valeur de S

    (Stallings)

    Quand S < 0: le nombre de threads qui attendent sur S est = |S|

  • Wait et signal contiennent elles mmes des SC!

    Les oprations wait et signal doivent tre excutes atomiquement (un seul thr. la fois)

    Dans un systme avec 1 seule UCT, ceci peut tre obtenu en inhibant les interruptions quand un thread excute ces oprations

    Normalement, nous devons utiliser un des mcanismes vus avant (instructions spciales, algorithme de Peterson, etc.)

    Lattente occupe dans ce cas ne sera pas trop onreuse car wait et signal sont brefs

  • Problmes classiques de synchronisation

    Tampon born (producteur-consommateur)

    crivains - Lecteurs Les philosophes mangeant

  • Le pb du producteur Le pb du producteur -- consommateurconsommateur

    Un problme classique dans l tude des threads communicantsun thread producteur produit des donnes

    (p.ex.des enregistrements d un fichier) pour un thread consommateur

  • Tampons de communicationTampons de communication

    Prod

    Cons

    1 donn

    Prod

    Cons

    1 donn 1 donn1 donn

    Si le tampon est de longueur 1, le producteur et consommateur doivent forcement aller la mme vitesse

    Des tampons de longueur plus grandes permettent une certaine indpendance. P.ex. droite le consommateur a t plus lent

  • Le tampon born Le tampon born (bounded buffer)(bounded buffer)une structure de donnes fondamentale dans les SEune structure de donnes fondamentale dans les SE

    b[0] b[1]

    b[7] b[2]

    b[6] b[3]

    b[4]b[5]

    ou

    out: 1re pos. pleine

    in: 1re pos. libre b[0] b[1] b[7]b[2] b[6]b[3] b[4] b[5]

    in: 1re pos. libre

    out: 1re pos. pleine

    bleu: plein, blanc: libre

    Le tampon born se trouve dans la mmoire partage entre consommateur et usager

  • Pb de sync entre threads pour le tampon bornPb de sync entre threads pour le tampon born

    tant donn que le prod et le consommateur sont des threads indpendants, des problmes pourraient se produire en permettant accs simultan au tampon

    Les smaphores peuvent rsoudre ce problme

  • Smaphores: rappel. Smaphores: rappel. Soit S un smaphore sur une SC

    il est associ une file d attente S positif: S threads peuvent entrer dans SC S zro: aucun thread ne peut entrer, aucun thread en attente S ngatif: |S| thread dans file d attente

    Wait(S): S - - si aprs S >= 0, thread peut entrer dans SC si S < 0, thread est mis dans file d attente

    Signal(S): S++ si aprs S

  • Solution avec smaphores Un smaphore S pour exclusion

    mutuelle sur laccs au tampon Les smaphores suivants ne font pas lEM

    Un smaphore N pour synchroniser producteur et consommateur sur le nombre dlments consommables dans le tampon

    Un smaphore E pour synchroniser producteur et consommateur sur le nombre despaces libres

  • Solution de P/C: tampon circulaire fini de dimension k

    Initialization: S.count=1; //excl. mut.N.count=0; //esp. pleinsE.count=k; //esp. vides

    Producer:repeatproduce v;wait(E);wait(S);append(v);signal(S);signal(N);

    forever

    Consumer:repeatwait(N);wait(S);w=take();signal(S);signal(E);consume(w);

    foreverSections critiques

    append(v):b[in]=v;In ++ mod k;

    take():w=b[out];Out ++ mod k;return w;

  • Points importants tudierPoints importants tudier

    dgts possibles en inter changeant les instructions sur les smaphores ou en changeant leur initialisation

    Gnralisation au cas de plus. prods et cons

  • 254

    tats sr et non sr

    On dit d'un tat qu'il est sr s'il n'est pas bloqu et qu'il existe un ordonnancement selon lequel chaque processus peut s'excuter jusqu'au bout,

    mme si tous demandent d'un seul coup leur nombre maximum de ressources.

  • 1 si demande(Pi)
  • banquier

  • 5 processus sont actifs (A,B,C,D,E) et il existe 4 catgories de priphriques P1 P4 (exemple : P4 =imprimante). Le tableau de gauche donne les ressources dj alloues et le tableau de droite les ressources qui seront encore demandes pour achever l'excution.

    Un tat est dit sr s'il existe une suite d'tats ultrieurs qui permette tous les processus d'obtenir toutes leurs ressources et de se terminer. L'algorithme suivant dtermine si un tat est sr :

    1. Trouver dans le tableau de droite une ligne L dont les ressources demandes sont toutes infrieures celles de dispo ( Li

  • 2. Supposer que le processus associ L obtient les ressources et se termine. Supprimer sa ligne et actualiser dispo

    3. Rpter 1 et 2 jusqu' ce que tous les processus soient termins (l'tat initial tait donc sr) ou jusqu' un interblocage (l'tat initial n'tait pas sr)

    Ici, par exemple, l'tat actuel est sr car : - on allouera D les ressources demandes et il

    s'achvera - puis on allouera A ou E les ressources demandes

    et A ou E s'achvera - enfin les autres

  • 259

    tats srs et non srs (1)

    Dmonstration que l'tat de (a) est sr

    On suppose quil y a 10 ressources en tout.

  • 260

    tats srs et non srs (2)

    Dmonstration que l'tat de (b) n'est pas sr

    Si A demande et obtient une ressource supplmentaire (figure b) alors on est dans un tat non sur

  • 261

    L'algorithme du banquier pour une ressource unique(Dijkstra 1965)

    3 tats d'allocation de ressource (a) sr (b) sr (c) non sr

  • 262

    L'algorithme du banquier pour plusieurs ressources

    C R

  • 263

    L'algorithme du banquier pour plusieurs ressources

    1. Rechercher une range R dont les demandes de ressources non satisfaites sont infrieur ou gales A

    2. Marquez le processus R comme achev et ajouter toutes ses ressources au vecteur A

    3. Recommencer les tapes 1 et 2 jusqu' ce que tous les processus soient termins (tat sr) o jusqu' ce qu'un interblocage se produise (tat non sr).

    Si B demande un scanner, on peut lui accorder car ltat reste sur

    Si E en demande un aussi alors on ne peut pas lui accorder et il devra patienter.

  • 264

    Prvention des interblocagesS'attaquer la condition de l'exclusion mutuelle

    Certains priphriques (tel que l'imprimante) peuvent tre spools (traits en diffr) seul le dmon d'imprimante peut directement utiliser

    l'imprimante cela limine les interblocages

    Tous les priphriques ne peuvent tre spouls. Principe:

    viter d'attribuer une ressource lorsque cela n'est pas absolument ncessaire

    le plus petit nombre possible de processus peuvent rclamer la ressource

  • 265

    S'attaquer la condition de dtention et d'attente

    Exige que les processus demandent toutes ses ressources avant l'excution le processus n'attend jamais aprs une ressource

    Problmes peut ignorer le nombre de ressources qu'il aura besoin

    (sinon on pourrait utiliser lalgorithme du banquier) les ressources ne sont pas utilises de manire

    optimale

    Variation: un processus doit librer toutes les ressources qu'il

    dtient il obtient ensuite tout ce dont il a besoin en une seule

  • 266

    S'attaquer la condition de non-premption

    Cette option est difficilement ralisable Considrer un processus utilisant une

    imprimante au milieu de la tche rquisitionner l'imprimante !!?? Solution dans ce cas: utiliser

    le disque et ledmon dimpression

  • 267

    S'attaquer la condition de l'attente circulaire (1)

    Ressources ordonnes numriquement

    Un processus peux demander plusieurs ressources mais il doit respecter lordre

    Dans lexemple, si i

  • 268

    Autres considrationLe verrouillage en deux phases

    Mthode utilis pour des applications spcifiques: Exemple: Bases de donnes

    Premire phase Le processus tente de verouiller plusieurs enregistrements

    (un la fois) Si un enregistrement est dj verrouill, il libre les verrous

    et recommence. (aucun vritable travail est effectu)

    Lorsque la premire phase se termine, on commence la seconde effectuer les modifications librer les verrous

    Similaire demander toutes les ressources la fois Cette solution n'est pas toujours possible

    Exemple: systmes temps rel

  • 269

    Les interblocages de communication

    Deux processus se bloquent mutuellement chacun attend que l'autre accomplisse une

    tche Par exemple, A envoie B un message qui

    se perd. A attend la r