7 pages

Catalan

2. Mécanismes d'exécution

Ibba - Fabienne Boyer

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

7 pages

Catalan

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

A propos
Informations
Extrait

Description

u
v
u
u
n
n
n
u
n
n
u
u
u
u
n
n
u
n
v
n
u
n
v
n
u
n
u
u
n
u
u
u
v
n
v
u
n
v
v
u
u
v
n
2. Mécanismes d’exécution
Ce cours a été conçu à partir de… F. Boyer, Laboratoire Lig
Fabienne.Boyer@imag.fr
Cours de E. Berthelot
http://www.iie.cnam.fr/EBerthelot/
Cycle de vie d’un programme Cours de A. Sylberschatz
www.sciences.univ-Notion de processus
nantes.fr/info/perso/permanents/attiogbe/SYSTEME/CoursSysteme.html
Modèle d’exécution d’un processus Cours de A. Griffaut
http://dept-info.labri.fr/~griffault/Enseignement/SE/CoursOrdonnancement des processus
Cours de H. Bouzourfi, D. Donsez
Notion de thread
http://www-adele.imag.fr/~donsez/cours/#se
© 2010, F. Boyer, UJF Cours de Systèmes d’Exploitation – RICM2 1 © 2010, F. Boyer, UJF Cours de Systèmes d’Exploitation – RICM2 2
Notion de processus (1/2) Contexte d’exécution d’un processus
Programme en cours d’exécution Etat courant du processus
Lancé à la demande du système ou d’une application Code du programme exécuté
Créé par un processus père Données statiques et dynamiques
Identifié de manière unique (PID) Informations qui caractérisent l’état dynamique du processus
Compteur de programme (PC / CO)
Etat des registresRegroupe deux unités :
Liste des fichiers ouverts
Unité d'exécution
Variables d’environnement
Flôt de contrôle logique séquentiel (exécute une suite d'instruction)
Image mémoire (état de l’espace d’adressage)
…
Unité d'adressage
Espace d'adressage (mémoire manipulable par les instructions
À sauvegarder lorsque le ...

Sujets

cours

cours de

Informations

Publié par	Ibba
Nombre de lectures	156
Langue	Catalan

Extrait

2. Mécanismes d’exécution F . B o yer, L ab o rato ire L ig F ab ien n e.B o yer@ im ag .fr

Cycle de vie d’un programme n Notion de processus n Modèle d’exécution d’un processus n Ordonnancement des processus n Notion de thread n

Cours de Systèmes d’Exploitation – RICM2

Notion de processus (1/2)

Programme en cours d’exécution n Lancé à la demande du système ou d’une application u Créé par un processus père u Identifié de manière unique (PID) u

Regroupe deux unités : n Unité d'exécution u Flôt de contrôle logique séquentiel (exécute une suite d'instruction) v

Unité d'adressage u Espace d'adressage (mémoire manipulable par les instructions v exécutées) propre au processus

Caractérisé par son contexte n

Cours de Systèmes d’Exploitation – RICM2

Modes d’exécution

Mode utilisateur n Accès réduit à l’espace d’adressage propre au processus u Instructions limitées u Mode superviseur n Toutes les instructions autorisées et toute la mémoire accessible u Superviseur #SuperUser (shell) u Interruptions, déroutements, appels au superviseur n Événements asynchrones u Instruction illégale u Besoin de faire un appel système (par exemple pour manipuler des u données du système)

Cours de Systèmes d’Exploitation – RICM2

Ce cours a été conçu à partir de…

Cours de E. Berthelot n http://www.iie.cnam.fr/EBerthelot/ u Cours de A. Sylberschatz n www.sciences.univ-u nantes.fr/info/perso/permanents/attiogbe/SYSTEME/CoursSysteme.html Cours de A. Griffaut n http://dept-info.labri.fr/~griffault/Enseignement/SE/Cours u Cours de H. Bouzourfi, D. Donsez n http://www-adele.imag.fr/~donsez/cours/#se u

Cours de Systèmes d’Exploitation – RICM2

Contexte d’exécution d’un processus

Etat courant du processus n Code du programme exécuté u Données statiques et dynamiques u Informations qui caractérisent l’état dynamique du processus u Compteur de programme (PC / CO) v Etat des registres v Liste des fichiers ouverts v Variables d’environnement v Image mémoire (état de l’espace d’adressage) v … v

À sauvegarder lorsque le processus est commuté À restaurer lorsque le processus reprend la main

Cours de Systèmes d’Exploitation – RICM2

Cycle de vie d’un processus

terminé tion inexistant élu exéc. prêt actif préempté ppel syst. bloquant fin attent E/S, ..) bloqué

Remarque : certains SE définissent des états supplémentaires (suspendu, …)

Cours de Systèmes d’Exploitation – RICM2

exécution

Interruption /trap

Contrôle des processus

prêt

[initialisation des variables d’envt à partir du fichier de configuration env USERNAME=fabienne PATH=.:/usr/local/bin:/usr/bin:/sbin:/bin PWD=/home/fabienne CLASSPATH et PATH ne sont pas hérités dans le shell fils Il aurait fallu les exporter dans le père pour ce faire

Etat processus, priorité,..

Identifications PC, SP, mep Autres registres

[initialisation des variables d’envt à partir du fichier de configuratio env USERNAME=fabienne PATH=.:/usr/local/bin:/usr/bin:/sbin:/bin PWD=/home/fabienne PATH=$PATH:/usr/lib/jvm/java-6-sun/bin CLASSPATH=. env USERNAME=fabienne PATH=.:/usr/local/bin:/usr/bin:/sbin:/bin:/usr/lib/jvm/java-6-sun/bin PWD=/home/fabienne CLASSPATH=. >xterm &

PCB (Process Control Block): informations requises pour permettre au SE de gérer un processus

Liste fichiers

Image mémoire

Limites mémoire

Table des Processus: PCB [ MAX-PROCESSUS ]

Cours de Systèmes d’Exploitation – RICM2

Opérations de base sur les processus

Les variables d’environnement du shell sont initialisées via des fichiers de n configuration u Fichiers typiques : .login, .logout, .cshrc ou .bash rc, .. Variables typiques : HOME, PATH, TERM, CURRENT-DIR u

Un processus qui crée d’autres processus pour exécuter des commandes (sauf n pour les commandesbuilt-in)

Cours de Systèmes d’Exploitation – RICM2

prêt / bloqué

Cours de Systèmes d’Exploitation – RICM2

Sauve ctxt P1 Charge ctxt P0

Sauve ctxt P0 Charge ctxt P1

Gestion des processus par le SE

exécution

…

Files de processus n File des prêts (Ready queue) u File des bloqués sur E/S (Device queues) u File des bloqués sur conditions de synchronisation (Blocked u queue) ... u

Interruption / trap

exécution

prêt / bloqué

Exemple du shell

Cours de Systèmes d’Exploitation – RICM2

Processus P0

Création /Destruction u Suspension / Activation u Abandon momentané u Attente de la terminaison d’un fils u Commutation (opération de bas niveau) u

Commutation de processus

.bashrc

prêt

Processus P1

Le SE fait migrer les processus entre les files

Usage des processus : exemple du Shell

Les variables sont héritées par un shell fils n Mais elles sont « écrasées » par la relecture des fichiers de configuration u Sauf pour les variables exportées (visibles par les shells secondaires) u u Ex dans bash : export VAR

D’autres variables peuvent être créées ou celles existantes modifiées pour le n shell courant setenv VAR value(ou VAR=value en bash) u Ou bien modifier le fichier de configuration et le « resourcer » (e.g., source .cshrc) u

Allocation du processeur au processus

Ordonnanceur (scheduler) est la partie du n SE qui gère l'allocation du processeur

Critères / Algorithme d’ordonnancement n Équitable (pas de famine) u Efficace u Minimisant les temps d'attente /de réponse des u processus Maximisant le rendement (nombre de travaux par unité u de temps)

Cours de Systèmes d’Exploitation – RICM2

Algorithmes d’ordonnancement (1/2)

En multiprogrammation seule n FIFO / FCFS (First In First out / First Come First Served) u Efficace (utilisation maximale de l’UC) et équitable v

En multiprogrammation + temps partagé n PCTE / SJF (Plus court temps d’exécution / Shortest Job First) u Priorité aux tâches courtes v Impose de connaître le temps d’exécution (estimé en fonction des exécutions v antérieures) Non équitable mais optimal / temps de réponse v

u Tourniquet (Round Robin) avec quantum fixe Chaque processus dispose d'un quantum de temps CPU (10-100 millisecondes), v après lequel il est préempté Efficace (sauf si quantum trop petit), équitable etbon /temps de réponse et v rendement (sauf si quantum trop grand)

Cours de Systèmes d’Exploitation – RICM2

First-Come, First-Served (FCFS)

Processus Temps d'exécution P24 1 P3 2 P3 3 Supposons que les processus arrivent dans n l'ordre :P,P,P 1 2 3 P PP 1 23

Critères d’ordonnancement

Algorithme avec / sans préemption n Transitioninterrompudu cycle de vie autorisée si préemption u (temps partagé) et interdite sinon (multiprogrammation seule) Choix du quantum n Gestion de priorités n Processus systèmes u Processus utilisateurs interactifs u Processus utilisateurs peu interactifs u

Cours de Systèmes d’Exploitation – RICM2

Algorithmes d’ordonnancement (2/2)

Tourniquet avec priorités statiques n Une priorité est associée à un nombre de quantum (1, 2, 4, etc) u Plus la priorité est forte, plus le quantum est petit u Le processus le plus prioritaire est élu u Bon compromis efficacité / rendement u Temps de réponse bons (travaux interactifs prioritaires) u Famine possible u Problèmeºles processus de faible priorité peuvent ne jamais s'exécuter v Solutionº"Aging" – augmenter la priorité d'un processus avec son âge v priorités dynamiques

Tourniquet avec priorités dynamiques n Un paramètre supplémentaire (une durée et un nombre d’interruptions, ou l'âge) u permet de faire passer les processus de priorité P à la priorité P+1 ou inversement Ou bien la priorité P est fonction de la fraction de quantum (f) utilisée (p = 1/f) u Equitable u

Cours de Systèmes d’Exploitation – RICM2

First-Come, First-Served (2/2)

Supposons que les processus arrivent dans l'ordre : P,P,P. 2 3 1

P 2

P 3

P 1

0 36 30 Temps de réponse deP =30; P= 3P =6 n1 2; 3 Temps moyen :(30 + 3 + 6)/3 = 13 n Meilleur que le cas précédent n Traiter les processus courts avant les longs

Extrait et traduit de Sylberschatz

Cours de Systèmes d’Exploitation – RICM2

Shortest-Job-First (SJR)

Associe à chaque processus la durée de son n exécution Deux possibilités : n Non préemptif – une fois que le CPU est alloué à un processus, il ne u peut être préempté. Préemptif – si un nouveau processus arrive avec un temps u d'exécution plus court que celui du processus courant, ce dernier est préempté (algorithme Shortest-Remaining-Time-First (SRTF)) SJF est optimal par rapport au temps de réponse n moyen

Cours de Systèmes d’Exploitation – RICM2

SJF Préemptif

Processus Arrivée Tempsd'exec. P0.0 7 1 P2.0 4 2 P4.0 1 3 P5.0 4 4 SJF (preemptif) n P PP PP P 1 23 24 1

0 1116 2 45 7 Temps de réponse moyen = (16 + 7 + 5 + 11)/4 = 8,25 n

Cours de Systèmes d’Exploitation – RICM2

Algorithmes d’ordonnancement à plusieurs niveaux

Ensemble des processus prêts trop important pour tenir en n mémoire centrale

Certains sont déchargés sur disque, ce qui rend leur activation n plus longue

Le processus élu est toujours pris parmi ceux présents en n mémoire centrale

En parallèle, on utilise un deuxième algorithme n d’ordonnancement pour gérer les déplacement des processus prêts entre le disque et la mémoire centrale

Cours de Systèmes d’Exploitation – RICM2

Exemple: Non-Preemptive SJF

Process ArrivéeTemps d'exéc. P0.0 7 1 P2.0 4 2 P4.0 1 3 P5.0 4 4 SJF (non-preemptif) n P PP P 1 32 4

0 37 812 16 Temps de réponse moyen = (7 + 8 + 12 + 16)/4 = 10,75 n

Cours de Systèmes d’Exploitation – RICM2

Round Robin avec Quantum = 20

Processus P 1 P 2 P 3 P 4

Temps d'exéc. 53 17 68 24

Efficacité et temps de réponse moyen moins n bon que SJF, mais meilleur rendement P P P P P P P P P P 1 2 3 4 1 3 4 1 3 3 0 2037 57 7797 117 121134 154162

Cours de Systèmes d’Exploitation – RICM2

Deux niveaux d’ordonnancement

rêt disquebloqué inexistant déchar é chargé appelbloquant (E/S, ..) actif prêt RAM n exéc.

RAM = Random

Access Memory

n errompu

Cours de Systèmes d’Exploitation – RICM2

terminé

Processus

Flot d’exécution “lourd” n

Contexte volumineux u

Espace protégé Espace d’adressage non accessible depuis un autre processus Partage / échange de données Au moment du fork() Via des segments de mémoire partagée Via des messages Commutations coûteuses

Cours de Systèmes d’Exploitation – RICM2

Processus single-threaded et multi-threaded

Cours de Systèmes d’Exploitation – RICM2

Types dethreads

A .S ylb ersch atz

Besoin de parallélisme au sein d’un espace virtuel : n

Utilisation de threadsUser-level Utilisation de threadsKernel-supported Solutions mixtes

Cours de Systèmes d’Exploitation – RICM2

Notion de thread

Flot d’exécution “léger” n

Contexte allégé u Une partie partagée : mémoire adressable, fichiers ouverts, … v Une partie propre : pile, registres, ... v

Commutations plus rapides Efficacité et facilité d’écriture des applications concurrentes Plusieurs flôts d’exécution Partage de données immédiat

Cours de Systèmes d’Exploitation – RICM2

Historique des threads

Espace Virtuel : unité d’adressage n Processus : unité d’exécution (ordonnancement) n

2 notions historiquement couplées, dissociées avec n les threads

EV PEV

Remarque : un processus est également associé à une unité de protection

Cours de Systèmes d’Exploitation – RICM2

Threadsuser-level

Code de gestion des threads dans une librairie n Pas de modification du noyau n Le gestionnaire de threads ainsi que les threads n s’exécutent au sein d’un processus utilisateur (EV) Examples: POSIX Pthreads, Mach C-threads, Solaris threads

th1 2 Gestionnaire ethreads Processus A

th1

th2

Gestionnaire de threads Processus B

Noyau

Cours de Systèmes d’Exploitation – RICM2

th2

Cours de Systèmes d’Exploitation – RICM2

Appels systèmes bloquants (+) n Pas de blocage des threads d’un EV lors d’un appel système u

Appel bloquant

Principes des threads Kernel-supported (parallélisme n réel possible) Principes des threads User-level (commutations n légères) On peut associer plusieurs threads User-level à un thread kernel-u supported Appels systèmes bloquants gérés ou non par le système u

Processus

ordonnanceur

Parallélisme (-) n Pas de parallélisme réel entre les threads d’un EV u

th2

Proce usA

Noyau

th1 th1 Proces sB

Notion de thread gérée par le noyau n Lorsqu’un thread se bloque, le noyau alloue le n processeur à un autre thread Examples: Windows 95/98/NT/2000, Solaris, Tru64 UNIX, Linux

Threadskernel-supported

Solutions hybrides permettant une commutation légère

Gestionnaire de threads

Modification du noyau pour gérer les appels n systèmes de manière à ne pas bloquer les threads Lorsqu’un thread fait un appel système bloquant, le noyau ne u préempte pas le processeur. Un mécanisme de signaux permet de gérer la fin de l’appel u bloquant. L’ordonnanceur est départagé entre l’espace système et l’espace u utilisateur (ordonnanceurs coopérants).

Cours de Systèmes d’Exploitation – RICM2

Avantages et inconvénients des threadsKernel-supported

Cours de Systèmes d’Exploitation – RICM2

Solutions hybrides permettant une commutation légère (2)

rdonnanceurUser space

Autres solutions hybrides permettant un parallélisme réel

Appels systèmes bloquants (-) n Le processus est bloqué au niveau du noyau u Tous lesthreads sont bloqués tant que l’appel système (I/O) n’est u pas terminé Il n’y a donc pas de multiprogrammation dans un espace virtuel u

Cours de Systèmes d’Exploitation – RICM2

Kernel space

Cours de Systèmes d’Exploitation – RICM2

Avantages et inconvénients des threadsUser-level

Efficacité (+) n La commutation de contexte est rapide u

th1

Principes des threads User-level (commutations n gérées au niveau utilisateur)

User-level threads

Parallélisme réel (+) n N threads d’un EV peuvent s’exécuter sur K processeurs u

Efficacité (-) n Commutation plus chère que pour les threads User-level, car u demande un passage en mode noyau.

Cours de Systèmes d’Exploitation – RICM2

Autres solutions hybrides permettant un parallélisme réel(2)

ordonnanceur

A1 A2

User-level threads

ordonnanceur User space Kernel space B Kernel-supported threads

ordonnanceur

Cours de Systèmes d’Exploitation – RICM2

Modèle de threads

Many-to-many

Cours de Systèmes d’Exploitation – RICM2

Threads Java

A. Sylberschatz

User-level / Kernel-supported, selon l’implémentation n de la JVM (généralement kernel-level) Création n Extension de la classe Thread u Implémentation de l’interface Runnable u

Cours de Systèmes d’Exploitation – RICM2

Modèles de Threads

Many-to-One n Un thread noyauplusieurs threads utilisateurs One-to-One n Un thread noyauun thread utilisateur Many-to-Many n Pool de threads noyauPool de threads utilisateurs

Cours de Systèmes d’Exploitation – RICM2

Principales familles de threads

POSIX threads API (systèmes Unix, threads noyaux) n POSIX Threads (IEEE POSIX 1003.1c-1995 standart) (appelés u Pthreads) DCE Threads u Solaris Threads u

Microsoft-style threads (PCs) n Win32 (Microsoft Windows 95 and Windows NT) u OS/2 threads (IBM) u

Cours de Systèmes d’Exploitation – RICM2