Franck Cassez
CNRS/IRCCyN (UMR CNRS 6597)
BP 92101
1 rue de la No¨e
44321 Nantes Cedex 3 France
Janvier 2004
Ecole Centrale Nantes
1 Introduction
2 Processus Unix
3 Ordonnancement sous Unix
4 Gestion de la mémoire
5 Séquence de boot pour Unix
1 Introduction
Historique
Posix : Vers un Unix standard
Architecture d’un système Unix
2 Processus Unix
3 Ordonnancement sous Unix
4 Gestion de la mémoire
5 Séquence de boot pour Unix
1962 : Time-sharing (CTSS), implémenté à Dartmouth (MIT) succés dans la communauté scientifique
1962 : Time-sharing (CTSS), implémenté à Dartmouth (MIT) succés dans la communauté scientifique
1965 : MIT + Bell-Labs + General Electric : MULTICS
MULTiplexed Information & Computing Services
Projet très ambitieux, nombreuses idées nouvelles, ..., pas un succés commercial
1962 : Time-sharing (CTSS), implémenté à Dartmouth (MIT) succés dans la communauté scientifique
1965 : MIT + Bell-Labs + General Electric : MULTICS
MULTiplexed Information & Computing Services
Projet très ambitieux, nombreuses idées nouvelles, ..., pas un succés commercial parallèlement : développement de micro-computers,
ex. DEC PDP-1, -11
1962 : Time-sharing (CTSS), implémenté à Dartmouth (MIT) succés dans la communauté scientifique
1965 : MIT + Bell-Labs + General Electric : MULTICS
MULTiplexed Information & Computing Services
Projet très ambitieux, nombreuses idées nouvelles, ..., pas un succés commercial parallèlement : développement de micro-computers, ex. DEC PDP-1, -11
Bell Labs ?, G.E. ? Honeywell ? SCO
1962 : Time-sharing (CTSS), implémenté à Dartmouth (MIT) succés dans la communauté scientifique
1965 : MIT + Bell-Labs + General Electric : MULTICS
MULTiplexed Information & Computing Services
Projet très ambitieux, nombreuses idées nouvelles, ..., pas un succés commercial parallèlement : développement de micro-computers, ex. DEC PDP-1, -11
Bell Labs ?, G.E. ? Honeywell ? SCO
1968 : Ken Thompson (Bell Labs) développe une version light de MULTICS : UNICS (UNiplexed ...)
maintenant : Unix
1962 : Time-sharing (CTSS), implémenté à Dartmouth (MIT) succés dans la communauté scientifique
1965 : MIT + Bell-Labs + General Electric : MULTICS
MULTiplexed Information & Computing Services
Projet très ambitieux, nombreuses idées nouvelles, ..., pas un succés commercial parallèlement : développement de micro-computers, ex. DEC PDP-1, -11
Bell Labs ?, G.E. ? Honeywell ? SCO
1968 : Ken Thompson (Bell Labs) développe une version light de MULTICS : UNICS (UNiplexed ...) maintenant : Unix
1970 : D. Ritchie (Bell Labs) + Thompson = Unix + C
1970 : D. Ritchie (Bell Labs) + Thompson = Unix + C
1970 : D. Ritchie (Bell Labs) + Thompson = Unix + C
1974 : publication de The Unix Timesharing System, Comm. of the ACM, july.
Ritchie & Thompson : ACM Turing Award en 1984
1970 : D. Ritchie (Bell Labs) + Thompson = Unix + C
1974 : publication de The Unix Timesharing System, Comm. of the ACM, july.
Ritchie & Thompson : ACM Turing Award en 1984
Code source disponible pour les universités Bell Labs = System III, V vs. Berkeley = 4.4BSD BSD : mémoire virtuelle, pagination, ...
1970 : D. Ritchie (Bell Labs) + Thompson = Unix + C
1974 : publication de The Unix Timesharing System, Comm. of the ACM, july.
Ritchie & Thompson : ACM Turing Award en 1984
Code source disponible pour les universités Bell Labs = System III, V vs. Berkeley = 4.4BSD BSD : mémoire virtuelle, pagination, ...
fin des années 80 : System V R3 et 4.3BSD
1970 : D. Ritchie (Bell Labs) + Thompson = Unix + C
1974 : publication de The Unix Timesharing System, Comm. of the ACM, july.
Ritchie & Thompson : ACM Turing Award en 1984
Code source disponible pour les universités Bell Labs = System III, V vs. Berkeley = 4.4BSD BSD : mémoire virtuelle, pagination, ...
fin des années 80 : System V R3 et 4.3BSD 1987 : Minix : Unix pour l’enseignement
1970 : D. Ritchie (Bell Labs) + Thompson = Unix + C
1974 : publication de The Unix Timesharing System, Comm. of the ACM, july.
Ritchie & Thompson : ACM Turing Award en 1984
Code source disponible pour les universités Bell Labs = System III, V vs. Berkeley = 4.4BSD BSD : mémoire virtuelle, pagination, ...
fin des années 80 : System V R3 et 4.3BSD
1987 : Minix : Unix pour l’enseignement
1991 : Linux
1965 1968 1974 1980 1987 1991
System III, V
Univ. California NetBSD
Berkeley
MINIX LINUX
Fait : il existe différentes versions d’Unix
System V, 4.4BSD, , FreeBSD, Solaris, Linux, OpenBSD, NetBSD, ...
Posix = Portable Operating Systems (IEEE)
Définit les System Calls que doit fournir une implémentation d’Unix
Dans ce cas : Posix compliant
but : interopérabilité
P = programme écrit en utilisant les System Calls Posix alors P est exécutable sur tout Unix qui est Posix compliant
1 Introduction
2 Processus Unix
Création de processus
Sémantique du fork
Implémentation des processus
Un Shell simplifié
Etats d’un processus
3 Ordonnancement sous Unix
4 Gestion de la mémoire
5 Séquence de boot pour Unix
Daemon : processus crées au démarrage du système
exemples : cron, sendmail, paging etc Processus : création par System Call = fork
1 pid=fork();
2 i f (pid<0) {
3 error_treatment(); /? s i pb : pas assez place . . . ?/
4 }
5 else i f (pid>0) {
6 prog_for_parent(); /? code pour l e parent ?/
7 }
8 else {
9 prog_for_child(); /? code pour l e f i l s ?/
10 }
Processus père
pid=fork();
i f (pid<0) {
error_treatment(); /? s
}
else i f (pid>0) { prog_for_parent();
}
else {
prog_for_child();
}
Processus père Process fils: 478
pid=478 pid=fork(); pid=0pid=fork();
i f (pid<0) { i f (pid<0) {
error_treatment(); /? s error_treatment(); /? s
} }
else i f (pid>0) { else i f (pid>0) {
prog_for_parent(); prog_for_parent();
} }
else { else {
prog_for_child(); prog_for_child();
} }
Pour chaque processus, informations dans 2 tables :
Table des Processus
| Info. d'ordonnancement: priorité, CPU usage, etc |
| Info. mémoire: pointeur vers table des pages ou segments |
Zone proc
Pour chaque processus, informations dans 2 tables :
Table des Processus
| Info. d'ordonnancement: priorité, CPU usage, etc |
| Info. mémoire: pointeur vers table des pages ou segments |
Zone proc
Pour chaque processus, informations dans 2 tables :
Table des Processus Infos Utilisateurs
| Info. d'ordonnancement: priorité, CPU usage, etc | ||
| Info. mémoire: pointeur vers table des pages ou segments | Info sur System Call: paramètres, résultats etc | |
| Infos diverses: limitations pour le processus, max. | ||
| pages, etc |
Zone proc Zone u
Pour chaque processus, informations dans 2 tables :
Table des Processus Infos Utilisateurs
| Info. d'ordonnancement: priorité, CPU usage, etc | ||
| Info. mémoire: pointeur vers table des pages ou segments | Info sur System Call: paramètres, résultats etc | |
| Infos diverses: limitations pour le processus, max. | ||
| pages, etc |
Zone proc Zone u
peut être swappée
1 while (true) {
2 prompt();
3 lire_commande(command,parameters);
4
5 pid=fork(); /? fork pour f a i r e la commande ?/
6 i f (pid<0) {
7 printf(‘‘impossible de faire la commande’’);
8 break;
9 }
10
11 i f (pid!=0) {
12 waitpid(-1,&status,0); /? l e parent attend ?/
13 }
14 else { /? l e f i l s f a i t la commande ?/
15 execve(command,parameters,0);
16 }
17 }
commande ls (pid!=0) {
waitpid(-1,&status,0);
1 Introduction
2 Processus Unix
3 Ordonnancement sous Unix
Type de systèmes visés
Principes de l’ordonnanceur Unix
Round-Robin multi-niveaux
Priorités dynamiques
4 Gestion de la mémoire
5 Séquence de boot pour Unix
Types de processus supportés
Système typique =? différents types de processus :
Système typique =? différents types de processus :
Interactifs : éditeurs, Shell, interface graphique;
?-CPU court, réponse rapide
Système typique =? différents types de processus :
Interactifs : éditeurs, Shell, interface graphique; ?-CPU court, réponse rapide
Batch : compilateurs, programmes de calcul;
?-CPU long, minimiser temps exécutiontemps transit
Système typique =? différents types de processus :
Interactifs : éditeurs, Shell, interface graphique; ?-CPU court, réponse rapide
Batch : compilateurs, programmes de calcul;
?-CPU long, minimiser temps exécutiontemps transit
Real-time : les autres; video, etc; deadlines ou besoins CPU réguliers
Système typique =? différents types de processus :
Interactifs : éditeurs, Shell, interface graphique; ?-CPU court, réponse rapide
Batch : compilateurs, programmes de calcul;
?-CPU long, minimiser temps exécutiontemps transit
Real-time : les autres; video, etc; deadlines ou besoins CPU réguliers
Ordonnanceur Unix :
processus interactifs et batch principes : favoriser les processus interactifs + équilibrer le temps CPU donnés aux processus batchs
Scheduler : ordonnance les processus qui sont en mémoire un processus bloqué (attente d’une E/S) n’est pas en mémoire (swappé)
Swapper : contrôle le passage mémoire ?? disque assure que tous les processus seront un jour en mémoire
=? éviter la famine
Scheduler : ordonnance les processus qui sont en mémoire un processus bloqué (attente d’une E/S) n’est pas en mémoire (swappé)
Swapper : contrôle le passage mémoire ?? disque assure que tous les processus seront un jour en mémoire
=? éviter la famine
Scheduler :
round-robin à étages; Quantum ? 100ms chaque étage ? niveaux de priorité (disjoints)
Priorité :
< 0 pour le mode SuperUser
? 0 pour le mode User
toutes les secondes =? recalcul de la priorité
priorité calculée par :
prio = CPU-Usage + nice + base (1)
priorité calculée par :
prio = CPU-Usage + nice + base (1)
CPU-Usage : usage CPU moyen récent (nombre de ticks) dans quelques secondes précédentes nice : ? [?20,20], fixé par le processus
nice = System Call
base : si une E/S (etc) attendue par un processus P se termine, P est débloqué et base = valeur associée à la cause de l’attente
priorité calculée par :
prio = CPU-Usage + nice + base (1)
CPU-Usage =? si un processus utilise beaucoup de CPU il est pénalisé
priorité calculée par :
prio = CPU-Usage + nice + base (1)
CPU-Usage =? si un processus utilise beaucoup de CPU il est pénalisé
Facteur de dégradation dans le CPU-Usage : soit C le dernier CPU-Usage
on définit : ki+1 = ki+2C , k0 = premier CPU-Usage calcul itératif : k := k+2C
remplacement de CPU-Usage par k dans equation (1)
préemptif en round-robin multi-niveaux
(noyau ne peut être préempté)
préemptif en round-robin multi-niveaux (noyau ne peut être préempté) simple et efficace
préemptif en round-robin multi-niveaux (noyau ne peut être préempté) simple et efficace favorise les processus “I/O bound” :
processus attendant une I/O est bloqué en mode SuperUser vise à faire quitter le mode SuperUser rapidement
préemptif en round-robin multi-niveaux (noyau ne peut être préempté) simple et efficace favorise les processus “I/O bound” :
processus attendant une I/O est bloqué en mode SuperUser vise à faire quitter le mode SuperUser rapidement
équilibre CPU pour les processus “CPU bound” :
Facteur de dégradation ( =? pas de famine)
préemptif en round-robin multi-niveaux (noyau ne peut être préempté) simple et efficace favorise les processus “I/O bound” :
processus attendant une I/O est bloqué en mode SuperUser vise à faire quitter le mode SuperUser rapidement
équilibre CPU pour les processus “CPU bound” : Facteur de dégradation ( =? pas de famine) pas de garantie de temps de réponse
=? pas un OS temps-réel
1 Introduction
2 Processus Unix
3 Ordonnancement sous Unix
4 Gestion de la mémoire
Mémoire virtuelle des processus
Le Swapper
Pagination sous Unix
Pagination sous Linux
5 Séquence de boot pour Unix
possibilité de partager des segments
possibilité de partager des segments
memory-mapped file : fichier = portion de le l’espace virtuel d’un processus
read/write + rapide, partage (ex : librairies partagées)
Systems Calls : mmap et munmap
possibilité de partager des segments
memory-mapped file : fichier = portion de le l’espace virtuel d’un processus
read/write + rapide, partage (ex : librairies partagées) Systems Calls : mmap et munmap demande mémoire par un processus : System Call : brk malloc en C utilise brk
swap out
swap in
swap out
swap in
Swap out quand manque de mémoire sur fork, brk, ou débordement de pile
swap out
swap in
Swap out quand manque de mémoire sur fork, brk, ou débordement de pile choix d’une victime :
? processus bloqués : critère C = prio + temps résidence victime = le plus grand C sinon : parmi les non bloqués, victime = plus grand C
swap out
swap in
Swap in : toutes les 4-5 secondes
Swapper cherche un processus prêt sur le disque
swap out
swap in
Swap in : toutes les 4-5 secondes
Swapper cherche un processus prêt sur le disque critère de choix : temps le plus long sur le disque
swap out
swap in
Swap in : toutes les 4-5 secondes
Swapper cherche un processus prêt sur le disque critère de choix : temps le plus long sur le disque éventuellement swap out d’un autre processus
swap out
swap in
Swapper : swap in (toutes les 4-5 secs) + swap out (à la demande)
Changement de comportement quand : plus de processus swappés trop de processus en mémoire (Thrashing) min. de 2 sec. en mémoire avant de swapper un processus
toutes les 250 msec. le pagedaemon est activé Algorithme :
nombre de cases libres ?lotsfree? si oui : sleep
sinon : transférer des pages sur le disque but : avoir des pages libres constamment
toutes les 250 msec. le pagedaemon est activé Algorithme :
nombre de cases libres ?lotsfree? si oui : sleep
sinon : transférer des pages sur le disque but : avoir des pages libres constamment
Algorithme de traitement de défaut basé : sur “seconde chance” (ou “Clock Algorithm”)
Si nombre de pages très grand????
Si le taux de défaut de pages est très grand : appel au swapper si ? des processus idle depuis ? ? 20sec. swap out le moins actif récemment (max. idle time) sinon parmi les 4 plus gros processus (taille mémoire) swap out le plus vieux (en mémoire) si nécessaire plusieurs processus peuvent être swappés
Si le taux de défaut de pages est très grand : appel au swapper si ? des processus idle depuis ? ? 20sec. swap out le moins actif récemment (max. idle time) sinon parmi les 4 plus gros processus (taille mémoire) swap out le plus vieux (en mémoire)
si nécessaire plusieurs processus peuvent être swappés
Variantes de l’algorihtme (System V) :
Clock Algorithm avec : n passages avant de libérer une page libère moins vite mais plus proche du Working Set
Au lieu de lotsfree : deux valeurs min et max
si # pages libres ? min : libère des pages jusqu’à max atteint
Evite instabililté du précédent
Pagination 3 niveaux adresse sur 32 bits : 3GB + 1GB (SuperUser mode) adresse virtuelle :
Linux supporte chargement à la demande de drivers etc
Linux supporte chargement à la demande de drivers etc
=? augmentation de la taille du noyau
Linux supporte chargement à la demande de drivers etc
=? augmentation de la taille du noyau
Mémoire physique est gérée par Buddy System binaire
Linux supporte chargement à la demande de drivers etc
=? augmentation de la taille du noyau
Mémoire physique est gérée par Buddy System binaire
Problème : fragmentation interne
Linux supporte chargement à la demande de drivers etc
=? augmentation de la taille du noyau
Mémoire physique est gérée par Buddy System binaire
Problème : fragmentation interne autre niveau d’allocation mémoire ...
kswapd = daemon (gère les défauts de page) toutes les secondes le kswpad s’active si assez pages libres, sleep
Algorithme de kswpad ...... maximum 6 “essais” renvoie d’une page qui est dans le cache des pages non récemment utilisées clock algorithm libération d’une page partagée non utilisée renvoie d’une page d’un processus utilisateur clock algorithm
1 Introduction
2 Processus Unix
3 Ordonnancement sous Unix
4 Gestion de la mémoire
5 Séquence de boot pour Unix
chargement du premier secteur du disque de boot et exécution programme de 512 octets : chargement du programme boot à une adresse mémoire fixe (haute)
chargement du premier secteur du disque de boot et exécution programme de 512 octets : chargement du programme boot à une adresse mémoire fixe (haute) boot lit le répertoire root (peut lire le filesystem) et charge en mémoire basse le kernel
chargement du premier secteur du disque de boot et exécution programme de 512 octets : chargement du programme boot à une adresse mémoire fixe (haute) boot lit le répertoire root (peut lire le filesystem) et charge en mémoire basse le kernel boot effectue ensuite un goto pour exécuter le kernel (programme écrit en assembleur, dépendant de la machine)
But : détecter capacité mémoire, CPU, paging system etc
chargement du premier secteur du disque de boot et exécution programme de 512 octets : chargement du programme boot à une adresse mémoire fixe (haute) boot lit le répertoire root (peut lire le filesystem) et charge en mémoire basse le kernel boot effectue ensuite un goto pour exécuter le kernel (programme écrit en assembleur, dépendant de la machine) But : détecter capacité mémoire, CPU, paging system etc kernel termine par lancer la boucle main (OS) Les messages de main sont écrits dans un buffer
chargement du premier secteur du disque de boot et exécution programme de 512 octets : chargement du programme boot à une adresse mémoire fixe (haute) boot lit le répertoire root (peut lire le filesystem) et charge en mémoire basse le kernel boot effectue ensuite un goto pour exécuter le kernel (programme écrit en assembleur, dépendant de la machine) But : détecter capacité mémoire, CPU, paging system etc kernel termine par lancer la boucle main (OS) Les messages de main sont écrits dans un buffer allocation des structures mémoire de l’OS : table des pages, des processus, coremap etc etc
chargement du premier secteur du disque de boot et exécution programme de 512 octets : chargement du programme boot à une adresse mémoire fixe (haute) boot lit le répertoire root (peut lire le filesystem) et charge en mémoire basse le kernel boot effectue ensuite un goto pour exécuter le kernel (programme écrit en assembleur, dépendant de la machine) But : détecter capacité mémoire, CPU, paging system etc kernel termine par lancer la boucle main (OS) Les messages de main sont écrits dans un buffer allocation des structures mémoire de l’OS : table des pages, des processus, coremap etc etc probing des périphériques
chargement du premier secteur du disque de boot et exécution programme de 512 octets : chargement du programme boot à une adresse mémoire fixe (haute) boot lit le répertoire root (peut lire le filesystem) et charge en mémoire basse le kernel boot effectue ensuite un goto pour exécuter le kernel (programme écrit en assembleur, dépendant de la machine) But : détecter capacité mémoire, CPU, paging system etc kernel termine par lancer la boucle main (OS) Les messages de main sont écrits dans un buffer allocation des structures mémoire de l’OS : table des pages, des processus, coremap etc etc probing des périphériques chargement des drivers des périphériques détectés fabrication du processus PID = 0
fabrication du processus PID = 0 programmation de l’horloge, mount du root filesystem et création des processus init (1) et pagedaemon (2) suivant les paramètres init fait : mode single user : fork un processus qui fait un exec du shell et attend qu’il se termine mode normal : fork un processus qui fait :
fabrication du processus PID = 0 programmation de l’horloge, mount du root filesystem et création des processus init (1) et pagedaemon (2) suivant les paramètres init fait : mode single user : fork un processus qui fait un exec du shell et attend qu’il se termine mode normal : fork un processus qui fait :
un exec de /etc/rc
But : mount le reste du filesystem, démarre des daemons
fabrication du processus PID = 0 programmation de l’horloge, mount du root filesystem et création des processus init (1) et pagedaemon (2) suivant les paramètres init fait : mode single user : fork un processus qui fait un exec du shell et attend qu’il se termine mode normal : fork un processus qui fait :
un exec de /etc/rc
But : mount le reste du filesystem, démarre des daemons lit /etc/ttys : pour chaque terminal : fork et exécution du programme getty
(prompte avec login :)
fabrication du processus PID = 0 programmation de l’horloge, mount du root filesystem et création des processus init (1) et pagedaemon (2) suivant les paramètres init fait : mode single user : fork un processus qui fait un exec du shell et attend qu’il se termine mode normal : fork un processus qui fait :
un exec de /etc/rc
But : mount le reste du filesystem, démarre des daemons lit /etc/ttys : pour chaque terminal : fork et exécution du programme getty
(prompte avec login :) si un login est tapé : getty termine en faisant un exec de
/bin/login (qui demande le password)
fabrication du processus PID = 0 programmation de l’horloge, mount du root filesystem et création des processus init (1) et pagedaemon (2) suivant les paramètres init fait : mode single user : fork un processus qui fait un exec du shell et attend qu’il se termine mode normal : fork un processus qui fait :
un exec de /etc/rc
But : mount le reste du filesystem, démarre des daemons lit /etc/ttys : pour chaque terminal : fork et exécution du programme getty
(prompte avec login :) si un login est tapé : getty termine en faisant un exec de
/bin/login (qui demande le password) si login correct, login fait un exec du shell
James L. Perterson and Abraham Silberschatz.
Operating Systems Concepts.
John Wiley & Sons Inc, 6th edition, April 2002.
952 pages.
ISBN : 0471262722.
Andrew S. Tanenbaum.
Modern Operating Systems.
Prentice-Hall, second edition, 2002.
Uresh Vahalia.
Unix Internals – The New Frontiers.
Prentice-Hall, 1996.
ISBN :0-13-101908-2.
Dennis Ritchie and Ken Thompson.
The Unix Timesharing System.
Communications of the ACM, pp. 225–233, july 1974.
