2. Mécanismes d exécution
7 pages
Catalan

2. Mécanismes d'exécution

-

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

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

Informations

Publié par
Nombre de lectures 237
Langue Catalan

Exrait

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
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
Cours de Systèmes d’Exploitation – RICM2
Modes d’exécution
1
3
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)
© 2010, F. Boyer, UJF
Cours de Systèmes d’Exploitation – RICM2
5
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
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
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é
2
4
Remarque : certains SE définissent des états supplémentaires (suspendu, …)
© 2010, F. Boyer, UJF
Cours de Systèmes d’Exploitation – RICM2
6
exécution
Interruption /trap
SE
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
10
Liste fichiers
Image mémoire
Limites mémoire
Table des Processus: PCB [ MAX-PROCESSUS ]
Cours de Systèmes d’Exploitation – RICM2
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
9
7
Cours de Systèmes d’Exploitation – RICM2
11
Cours de Systèmes d’Exploitation – RICM2
© 2010, F. Boyer, UJF
8
© 2010, F. Boyer, UJF
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
12
Cours de Systèmes d’Exploitation – RICM2
Processus P0
© 2010, F. Boyer, UJF
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)
© 2010, F. Boyer, UJF
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
13
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)
© 2010, F. Boyer, UJF
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
0 2427 30 Temps de réponse deP= 24;P= 27;P= 30 n1 2 3 Temps moyen :(24 + 27 + 30)/3 = 27 n Extrait et traduit de Sylberschatz © 2010, F. Boyer, UJF Cours de Systèmes d’Exploitation – RICM2
15
17
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
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
Cours de Systèmes d’Exploitation – RICM2
14
16
18
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
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
Cours de Systèmes d’Exploitation – RICM2
19
21
23
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
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
Access Memory
n errompu
Cours de Systèmes d’Exploitation – RICM2
terminé
20
22
24
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
© 2010, F. Boyer, UJF
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
Cours de Systèmes d’Exploitation – RICM2
25
27
29
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
© 2010, F. Boyer, UJF
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
P
Remarque : un processus est également associé à une unité de protection
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
th1
th1
th2
Gestionnaire de threads Processus B
Noyau
Cours de Systèmes d’Exploitation – RICM2
26
28
30
th2
32
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
© 2010, F. Boyer, UJF
34
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
© 2010, F. Boyer, UJF
A
ordonnanceur
B
ordonnanceur
Parallélisme (-) n Pas de parallélisme réel entre les threads d’un EV u
th2
Proce usA
© 2010, F. Boyer, UJF
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
36
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
© 2010, F. Boyer, UJF
© 2010, F. Boyer, UJF
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
33
31
35
Principes des threads User-level (commutations n gérées au niveau utilisateur)
User-level threads
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
© 2010, F. Boyer, UJF
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
37
39
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
© 2010, F. Boyer, UJF
Cours de Systèmes d’Exploitation – RICM2
41
Modèles de Threads
Many-to-One n Un thread noyauplusieurs threads utilisateurs One-to-One n Un thread noyauun thread utilisateur Many-to-Many n Pool de threads noyauPool de threads utilisateurs
© 2010, F. Boyer, UJF
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
© 2010, F. Boyer, UJF
Cours de Systèmes d’Exploitation – RICM2
38
40
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents