INFO502 : Systèmes d'exploitation

Ce wiki est un complément de cours pour le cours « info-502 : systèmes d'exploitation ». La participation au wiki est fortement encouragée.

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Choisissez un login du style PrenomNom...)

Je vous conseille d'aller lire ce guide pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fautes d'hortographe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

---

---

Auteur du cours

Supports

TD

-- à venir

TP

-- à venir

Introduction

-- ...

Repères historiques

Voici quelques évènements clés dans l'histoire des systèmes d'exploitation. Pour plus de détails, ou pour des compléments sur l'histoire de l'informatique, je vous renvoie sur Wikipedia : "History of operating systems" et "History of computing".

Les premiers ordinateurs ne comportaient pas vraiment de système d'exploitation : c'étaient des opérateurs humains qui géraient tout. (C'était juste après la seconde guerre mondiale, l faut savoir que les langages de programmation n'existaient même pas...) La petite histoire (??) raconte qu'à un moment, les processus pour l'ordinateur de l'université de Cambridge étaient accrochés sur une corde à linge et que c'était la couleur des pinces à linges qui donnait la priorité. (??)

Le passage à la notion de système d'exploitation c'est faite graduellement pour répondre à la complexité de plus en plus grande des ordinateurs et aux demandes des utilisateurs.

Les premier systèmes d'exploitation datent probablement de 1956. Ils permettaient simplement d'exécuter un nouveau programme lorsque le précédent était terminé. Les ordinateurs d'IBM de la famille System/360 ont ensuite eu toute une série de systèmes d'exploitation plus ou moins similaires : OS/360, DOS/360 (rien à voir avec MS-DOS), TSS/360... C'est à cette époque qu'est apparu la notion de multiprogrammation (possibilité d'avoir plusieurs processus entrelacés.) C'est également au début des années 60 qu'on a commencé à voir des systèmes avec temps partagé : plusieurs utilisateurs pouvaient utiliser un ordinateur. Le système Multics a été, à ce niveau comme à d'autres, assez révolutionnaire. Multics a été utilisé jusqu'en 2000 !

Multics n'était par contre pas approprié pour les mini-ordinateurs où le nombre d'utilisateur est relativement restreint. En 1969, Ken Thomson a développé une variante simplifié de Multix : Unix...

Ce n'est qu'un peu plus tard (1979) que la première version de DOS (86-DOS ou QDOS) apparaît. 86-DOS sera racheté par Microsoft un 1980...

Liens et compléments :

• Timeline of operating systems
• généalogie des systèmes Unix : Unix History
• généalogie de Windows : Windows History
• généalogie des systèmes non-Unix : timeline of non-Unix operating systems

Vue d'ensemble

Ce cours reste assez généraliste et essaie de regarder les principales fonction d'un système d'exploitation. Les systèmes de type Unix (Linux) sera un exemple privilégié. À cause de leur complexité intrinsèque, les évolutions modernes (architectures multicoeur ou multiprocesseur, ...) seront en partie ignorée dans un premier temps.

Les problèmes fins de communication entres processus ne seront que très peu abordés, car ils font l'objet d'un cours séparé (info604) pour la filière info.

Nous allons suivre l'ordre classique consistant à regarder :

1. les processus
2. la mémoire
3. les entrées / sorties

La fin du cours dépendra du temps restant...

Les processus

Un processus est simplement un programme « en exécution ». À tout instant, un ordinateur de bureau contemporain contient de nombreux processus qui doivent partager le (les) processeur(s) pour donner l'impression qu'ils s'exécutent « en même temps ». Un des rôles du système d'exploitation consiste à décider dans quel ordre les processus vont effectivement pouvoir utiliser le processus.

La mémoire

La mémoire est, comme le processeur, une ressource partagée par les différents processus. Il faut donc gérer la quantité de mémoire allouée et utilisée pour que les processus n'aient pas à s'occuper de ceci. Un des concepts fondamentaux est celui de mémoire virtuelle. Ceci permet d'offrir un espace mémoire pour chacun des processus de manière transparente.

Les entrées / sorties

Un ordinateur n'est pas (plus) un système indépendant du reste du monde : il interagit avec l'extérieur à travers des périphériques d'entrées/sorties (clavier / écran / souris / ...). La gestion de ces périphériques pose un ensemble de problèmes que nous aborderons brièvement...

...

Une fois ces notions vues, nous regarderons peut-être les problèmes de sécurité, de multimédia ou des architectures multiprocesseurs.

Préliminaires

Quoi ?

Les ordinateurs, ou plus simplement les micro contrôleurs sont des circuits électroniques avec une puce « processeur ». Le développement d'applications n'est pas facile si on se place au niveau électronique et que l'on parle directement au CPU. Pour faciliter la vie des programmeurs, plusieurs couches d'abstraction sont nécessaires. La première se place au niveau matériel et s'occupe directement des problèmes électroniques ou de très bas niveau. Il s'agit du firmware. Il répond par exemple aux questions comme :

• qu'elle est l'amplitude des signaux envoyés par l'horloge ?
• est-ce que l'UC possède un pipeline ?
• ...

Un firmware est donc forcement très lié au matériel sur lequel il tourne.

La couche suivante est le système d'exploitation à proprement parler. Dans le cas que vous connaissez le mieux (ordinateur personnel), le système d'exploitation fournit une interface pour :

• exécuter un programme
• exécuter plusieurs programmes « en même temps »
• gérer les ressources (temps processeur, mémoire disponible, entrées / sorties)
• les opérations sur les fichiers
• offrir des garanties de sécurité en installant un coffre de sécurité ignifuge certifié S60DIS

Où ?

On trouve des systèmes d'exploitation partout :

• dans les ordinateurs personnels (Linux, BSD, MacOS, Solaris, Windows, ChromeOS (?))
• dans les PDA (PalmOS, ...)
• dans les téléphones portables (Android, OpenMoko,Symbian,)
• console de jeux
• lecteur MP3 (Rockbox, ...)
• les microcontroleurs « avancés »

Comment ?

Langage de programmation

Le système d'exploitation se situe entre le firmware (très bas niveau) et l'utilisateur. La nécessité d'accéder à ces ressources de très bas niveau implique que les langages de haut niveaux (Java, Ada, Python, ...) ne sont pas du tout adaptés à l'écriture des systèmes d'exploitation. Le langage le plus utilisé reste à ce jours le langage C : Linux, BSD, MacOS, Windows, ... sont tous écrits pour leur plus grande partie en C.

Vous avez normalement un cours de C en parallèle, et les TPs utiliseront le langage C. (La référence sur le langage C reste à mon goût le livre de Kernighan et Ritchie : « the C Programming language ». (Disponible en francais à la BU sous le titre « Le langage C : norme Ansi ».) Il existe de nombreux autres livres / documents sur la programmation C comme le polycopié de Bernard Cassagne « introduction au langage C ».

Les premiers systèmes d'exploitation étaient écrits directement en langage machine, ou bien en langage d'assembleur ; et les systèmes actuels comportent encore quelques parties de très bas niveau en langage d'assemblage...

Notion d'appel système, norme POSIX

La programmation de haut niveau en C est assez différente de la programmation système. De nombreuses fonctions C utilisent en fait des « appels système », c'est à dire des appels de fonctionnalités propres du système d'exploitation. Les appels système typiques sont :

• les fonctions relatives aux fichiers (création, suppression, modification...)
• les fonctions relatives à la gestion de la mémoire
• les fonctions relatives aux processus (fork)
• ...

De nombreux système d'exploitation proposent une interface POSIX (« Portable Operating System Interface for Unix »). Cette norme définit entre autres un ensemble de fonctions pour utiliser les appels systèmes. Le nombre de ces fonctions est relativement faible : une centaine ; et chacune correspond en gros à un appel système. Certaines de ces fonctions ne sont pas définies directement dans le système d'exploitation, mais dans des librairies. Pour Linux, il s'agit en général de la librairie Glibc (GNU C Library).

Par exemple, la fonction open (qui permet d'ouvrir un fichier) correspond exactement à un appel système ; alors que la fonction malloc (qui permet d'allouer dynamiquement de la mémoire dans le tas) peut générer plusieurs appels système (brk et sbrk).

Pour visualiser les appels systèmes effectués par un programme sous Linux, vous pouvez utilisez l'utilitaire strace ou ltrace. Par exemple, dans le shell :

 $ strace -e trace=file ls -l 2> trace

permet de récupérer tous les appels systèmes relatifs aux fichiers lors de l'appel à ls -l. La liste des appels système est redirigée dans le fichier trace qui contiendra par exemple des lignes telles que

lstat64("Desktop", {st_mode=S_IFDIR|0700, st_size=4096, ...}) = 0
lgetxattr("Desktop", "security.selinux", 0x8cc08e0, 255) = -1 ENODATA (No data available)

dénotant ainsi un appel aux appels système lstat64 et lgetxattr...

Les principaux systèmes compatibles POSIX sont :

• Linux
• BSD (et variantes)
• Mac OS X
• Solaris

De nombreux appels systèmes sont disponibles directement (sans avoir besoin d'écrire un programme C) à travers le shell. Exécuté dans un terminal, le shell permet, en première approximation, de passer directement des commandes au système d'exploitation. (La norme POSIX définit également un ensemble de fonctions du shell. Il est donc relativement aisé de changer de système d'exploitation tant qu'on reste dans les systèmes compatibles POSIX.)

Windows d'un autre côté utilise l'interface Win32 API, qui définit plusieurs milliers de fonctions. La plupart de ces fonctions peuvent utiliser plusieurs appels système...

Les systèmes d'exploitation qui utilisent l'API Win32 sont :

• Windows, depuis Windows95.

Il est possible d'installer un environnement compatible POSIX sur une machine Windows grâce à Cygwin. (C'est d'ailleurs fortement conseillé si vous ne voulez pas installer une version de Linux ou BSD sur votre ordinateur personnel...)

Mode noyau / mode utilisateur

La partie fondamentale du système d'exploitation est le noyau (kernel en anglais). C'est la couche de plus bas niveau.

Les fonctionnalités de très bas niveau offertes par le noyau peuvent facilement planter l'ordinateur. Il faut donc une politique de restriction pour que tous les programmes ne puissent y accéder dans leur totalité. On parle de

• mode noyau
• mode utilisateur

Dans le mode utilisateur, on ne peut accéder à ces fonctionnalités qu'a travers les appels systèmes ; dans le mode noyau, on peut tout faire... Bien entendu, un appel système doit passer momentanément en mode noyau pour pouvoir exécuter les commandes pertinentes, puis il repasse automatiquement en mode utilisateur.

La définition d'un appel système pourrait donc être « fonctionnalité atomique nécessitant un passage en mode noyau ».

Noyau, noyau monolithique, micro-noyau

La partie principale du système d'exploitation. C'est lui qui gère les ressources, les entrées / sorties, la communication entre processus, ... Les deux architectures principales pour un noyau sont :

• noyau monolithique
• micro-noyau

La plupart des systèmes actuels sont basés sur un noyau monolithique (Linux, BSD, Mac OS X, Solaris, Windows).

Les noyaux monolithiques sont parfois décrits comme « sans vraie structure » : une grosse soupe où cohabitent toutes les fonctionnalités du système d'exploitation. L'idée d'avoir un système unique qui gère tout est effectivement peu attirante et peut poser quelques problèmes de génie logiciel... Un noyau monolithique est donc la couche entre le matériel et les programmes utilisateurs. Pour éviter de compiler des noyaux énormes, les noyaux monolithiques actuels utilisent en plus la notion de module. Ce sont des morceaux du noyau qu'on peut charger ou décharger au besoin. Si l'interface est connue, ces modules peuvent éventuellement être en binaire, ce qui permet d'utiliser des modules propriétaires avec un noyau libre. Sous Linux, la commande

$ lsmod

permet d'obtenir la liste des modules chargés dans le noyau.

Les micro-noyaux d'un autre coté sont basés sur la remarque que seule une toute petite partie du noyau accède effectivement au matériel. Seule cette petite partie nécessite donc des privilèges et effectue des appels système. Le reste du système d'exploitation peut être programmé en mode utilisateur, « au dessus » de cette partie. Par exemple, le micro noyau offrira la possibilité de charger un nouveau processus, mais l'ordonnanceur (qui choisit quel processus devra être chargé) ne fera pas partie du micro-noyau. On parle parfois de services / serveurs au dessus du micro-noyau. Ceci permet d'avoir un noyau bas niveau beaucoup plus petit. Bien que ceci soit une bonne idée, et que les micro-noyaux puissent fournir de meilleurs garanties de sécurité, peu de noyaux sont effectivement des micro-noyaux. Un des problèmes est qu'un tel micro-noyau est un peu plus lent que ses cousins monolithiques. La raison principale est que dans le cas d'un micro-noyau, un appel système nécessite en fait des communications inter-processus. Andrew Tanenbaum est un fervent défenseur des micro-noyaux.

Une autre architecture possible est d'utiliser des couches successives, chacune avec des privilèges réduits. Le système Multics avait cette architecture. Par exemple, dans le système THE (1965), les couches étaient les suivantes :

1. noyau bas niveau, multiprogrammation
2. allocation de la mémoire pour les processus
3. IPC (communication inter processus)
4. entrées / sorties (buffer, etc.)
5. programmes utilisateurs (compilation, exécution, ...)
6. utilisateur (Dijkstra a annoté la description de cette couche par « not implemented by us »)

Une dernière catégorie de noyau est la catégorie des machines virtuelles. Ces noyaux sont un peu à part, car il s'agit d'émuler un système d'exploitation ou du matériel particulier à l'intérieur d'un autre système d'exploitation ou matériel. Le mode noyau de la machine virtuelle est en fait dans le mode utilisateur du noyau original...

Les processus

Introduction

Allez hop commençons par une petite définition du type wikipédia :

Un processus (en anglais, process), en informatique, est défini par :

• un ensemble d'instructions à exécuter (un programme) ;
• un espace mémoire pour les données de travail ;
• éventuellement, d'autres ressources, comme des descripteurs de fichiers, des ports réseau, etc.

Un ordinateur équipé d'un système d'exploitation à temps partagé est capable d'exécuter plusieurs processus de façon « quasi- simultanée ». Par analogie avec les télécommunications, on nomme multiplexage (A. Tanenbaum parle de multiprogrammation) ce procédé. S'il y a plusieurs processeurs, le système essaie de répartir les processus de manière équitable sur les processeurs disponibles.

Le processus doit être imaginé comme quelque chose qui prend du temps, donc qui a un début et (parfois) une fin. De nombreux processus ne se terminent normalement jamais : système d'exploitation, serveurs web, serveurs mail, ... D'autres processus plus légers qui ne se terminent pas sont les daemon (acronyme a posteriori de "disk and execution monitor") du monde Unix.

Certains processus sont démarrés très tôt lors de la séquence de boot. Le système d'exploitation est un tel processus. Sinon, les processus sont normalement démarrés grâce à un appel système à partir d'un autre processus. L'utilisateur peut par exemple demander explicitement un nouveau processus (sous POSIX, grâce à un fork puis exec) ; mais la plupart du temps, il le fera à travers une application, par exemple en double-cliquant sur l'icône d'un programme dans l'explorateur de fichiers.

Le système d'exploitation est chargé d'allouer les ressources (mémoires, temps processeur, entrées/sorties) nécessaires aux processus et d'assurer que le fonctionnement d'un processus n'interfère pas avec celui des autres (isolation).

Pas sûr d'avoir tout compris ? Ce n'est pas grave, essayons autrement.

Définition : un processus est un programme en train de s'exécuter.

Cette définition implique en particulier que un programme (navigateur Firefox par exemple) peut correspondre à

• zéro processus si on ne l'a pas lancé,
• un processus si on l'a lancé,
• plusieurs processus si on l'a lancé plusieurs fois.

(Remarque : pour un programme comme Firefox, il y a fort à parier que l'exécution d'une seule instance de Firefox génère de multiples sous-processus...)

Que se passe-t-il quand je démarre une application?

L'ordinateur à une nouvelle tâche à accomplir, les instructions correspondantes sont donc envoyées au processeur. Comme il a plusieurs choses à faire le choix des instructions à exécuter n'est pas forcement simple. Il faut faire en sorte de partager le processeur entre les différentes tâches de manière équitable : c'est la fameuse gestion des processus.

Ceci permet de réaliser plusieurs activités en ~même temps~. Grâce à la gestion des processus on peut regarder un film (obtenu par des moyens tout à fait légaux cela va de soit), tout en jouant à la dame de pique.

(et dire que certain(e)s affirment que l'homme est mono tâche)

Plusieurs processus indépendants peuvent être actifs en même temps, mais sauf si l'ordinateur possède suffisamment de processeurs, on ne peut pas les exécuter simultanément. L'impression que plusieurs programmes s'exécutent en même temps vient simplement du fait que le processeur alterne rapidement entre eux. Comme le temps d'exécution d'une instruction par le processeur est très court, de l'ordre de la nano-seconde, le processeur peut réaliser plusieurs centaines de millions d'instructions par seconde. Ainsi, une tranche de temps de quelques fractions de seconde, partagée entre plusieurs processus, donne à l'échelle macroscopique l'illusion de la simultanéité.

En résumé : un système d'exploitation doit la plupart du temps traiter plusieurs tâches en même temps, et comme il n'a, en général, qu'un seul processeur, il devra contourner ce problème grâce à un pseudo-parallélisme. Il traite une tâche à la fois, s'interrompt et passe à la suivante. La commutation de tâches étant très rapide, il donne l'illusion d'effectuer un traitement simultané.

La table des processus

L'information sur les processus est conservé par le système dans une structure de données appelée table des processus. Cette table contient toutes les informations nécessaires à la gestion des processus :

• état du processus
• PID
• droits
• répertoire de travail
• pointeur vers la pile
• priorités
• ...

Sous Linux, on peut accéder à ces informations à travers le système de fichiers virtuel "Procfs". Il suffit d'aller dans le répertoire /proc/.

Création d'un processus

Pour les système POSIX, la création d'un processus est très simple : on utilise la fonction fork(). En C, le prototype de la fonction se trouve dans le fichier d'entêtes unistd.h.

Cette fonction prend 0 argument et permet de faire la chose suivante : elle crée un nouveau processus qui est une copie conforme du processus appelant. La seule différence visible entre l'ancien et le nouveau processus est que les processus ont un numéro (PID) différent. Pour le processus appelant, il peut obtenir le PID du nouveau processus en regardant la valeur de retour de fork. Pour le nouveau processus, cette valeur vaudra 0, et il devra utiliser la fonction getpid() pour obtenir son numéro.

Le processus appelant est appelé le père alors que le nouveau processus est appelé le fils.

Notez que l'espace mémoire du processus est dupliqué plutôt que partagé. Ceci veut dire que les processus ne peuvent pas communiquer en utilisant leur variables... Par contre, les descripteurs de fichiers du fils sont hérités directement de ceux du père ; ils peuvent donc essayer de communiquer en passant par ces fichiers. (Mais cela pose de nombreux problèmes de synchronisation.)

Voici par exemple un petit programme C qui lance un processus fils:

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

int main() {

  int pid ;
  int pid_fils ;

  pid = getpid();
  printf("> Le processus %i démarre...\n", pid);

  pid_fils = fork();

  if(pid_fils) {
    printf(" >> Je suis le père (pid du fils = %i).\n",pid_fils);
  } else {
    printf(" >> Je suis le fils.\n");
  }

  return(0);

}

Après compilation, voici un exemple d'exécution du programme résultant :

$ ./pere_fils
> Le processus 8248 démarre...
 >> Je suis le fils.
 >> Je suis le père (pid du fils = 8249).

Voici un autre exemple d'exécution :

$ ./pere_fils
> Le processus 8269 démarre...
 >> Je suis le père (pid du fils = 8270).
 >> Je suis le fils.

Notez que les numéros sont différents, et que l'ordre d'affichage n'est pas le même. Cela vient de l'ordonnancement des deux processus qui peut différer.

La technique consistant à faire

pid = fork();
if (pid) { /* le père */
  ...
} else { /* le fils */
  ...
}

montre que malgré le fait que les processus soient identiques à l'origine, on peut faire beaucoup de chose.

Remarque : fork() n'est pas directement un appel système, mais une fonction qui utilise l'appel système clone(). Cet appel système ne fait pas partie de la norme POSIX...

La deuxième technique utilisée dans les systèmes POSIX consiste à utiliser fork() pour dupliquer le processus, puis à complètement remplacer le fils par un nouveau processus. La fonction correspondante est la fonction execv :

pid = fork();
if (pid) { /* le père */
  ...
} else { /* le fils */
  execv("/usr/bin/...", argv);
  ...
}

La fonction execv prend 2 arguments : une chaîne contenant le chemin d'accès à un programme, et un tableau d'arguments à donner au programme. (C'est un peu plus compliqué que ça : le premier élément du tableau est le nom du programme, et le tableau doit se terminer par un pointeur NULL.)

Une dernière fonction importante est la fonction wait(pid) qui permet à un processus d'attendre l'arrêt du processus pid.

-- ...

L'API WIN32 possède de nombreuses fonctions avec des fonctionnalités similaires. Par exemple, la fonction CreateProcess permet de créer un nouveau processus (comme un fork suivi d'un exec), mais elle nécessite ... 10 arguments !

---

Un autre moyen de créer des processus est d'utiliser des 'processus légers' appelés Thread. Ces processus légers partage seulement une partie de la mémoire, ce qui en pratique est plus rapide pour simuler un parallélisme. On passe alors par une autre fonction. Sous GNU/Linux, lors de l'écriture d'un programme écrit en C il faut utiliser la bibliothèque pthread.h et lors de la compilation, faire un lien vers celle ci, en utilisant le paramètre -lpthread.

Arborescence des processus dans les systèmes POSIX

Nous avons vu que la fonction fork() permet de créer un processus fils. Le père connaît le PID de son fils : il lui est donné par la fonction fork(). Comme le fils peut lui même créer des processus fils, on obtient rapidement une arborescence de processus.

Vous pouvez visualiser cette arborescence à partir d'un terminal avec la commande pstree (l'option -p permet de demander l'affichage des PID)

$ pstree -p
init(1)─┬─acpid(25425)
        ├─atd(14365)
        ├─console-kit-dae(3632)─┬─{console-kit-dae}(3633)
        │                       ├─{console-kit-dae}(3641)
...
        ├─cron(14315)
        ├─dbus-daemon(15590)
        ├─dbus-daemon(3511)
...
        ├─getty(4095)
        ├─getty(4096)
        ├─getty(4097)
        ├─getty(4098)
        ├─getty(4099)
        ├─gpm(3528)
...
        ├─kded4(15769)
        ├─kdeinit4(15766)───klauncher(15767)
        ├─kdm(15564)─┬─Xorg(15566)
        │            └─kdm(15573)───sh(15608)─┬─conky(15751)
        │                                     ├─fluxbox(15703)───firefox-bin(6063)─┬─{firefox-bin}(6064)
        │                                     │                                    ├─{firefox-bin}(6065)
...
        │                                     ├─ssh-agent(15698)
        │                                     ├─unclutter(15742)
        │                                     ├─wicd-client(15749)
        │                                     └─xscreensaver(15683)
...
        ├─rsyslogd(6850)─┬─{rsyslogd}(6140)
        │                └─{rsyslogd}(6141)
        ├─screen(4427)─┬─bash(4428)───pstree(9307)
        │              ├─bash(4429)───man(7952)───pager(7965)
        │              ├─bash(4430)───vi(30568)
        │              ├─bash(18395)───vi(28512)
        │              └─mutt(8763)
...

Le processus init est l'ancêtre de tout les processus, il a toujours 1 comme PID.

Remarque : sous Windows, les processus ne sont pas organisé en arborescence...

Mort d'un processus dans un système POSIX

Un processus peut se terminer pour plusieurs raisons :

• volontairement, grâce à la fonction exit() (POSIX) ou ExitProcess() (Windows),
• à cause d'une erreur,
• en recevant un signal d'un autre processus, grâce à la fonction kill() (POSIX) ou TerminateProcess() (Windows).

Lorsqu'un processus se termine, plusieurs choix sont possibles :

• que fait-on de ses fils ?
• que fait-on de son père ?

Linux fait la chose suivante : quand un processus s'arrête,

• tous ces fils s'arrêtent,
• son père reçoit un signal le prévenant que son fils vient de mourir.

Pour que le père puisse recevoir le signal correspondant, il faut qu'il utilise la fonction wait() ou waitpid(). Tant que le parent existe et qu'il n'a pas reçu le signal disant qu'un de ces fils est mort, le processus fils n'est pas entièrement supprimé : il devient un zombie. (Il n'occupe plus vraiment de place en mémoire, mais le système garde juste suffisamment d'information pour pouvoir prévenir le père si celui ci demande l'état du fils.)

Remarque : les processus Windows ne sont pas organisés sous forme d'arborescence. Chaque processus peut surveiller l'état d'un autre processus, s'il connaît son PID. Il n'y a donc pas de notion de processus zombie sous Windows.

Voici un petit programme C qui crée un processus fils, ne fait rien pendant 20 secondes, puis demande l'état de son fils :

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

int main() {
  int pid ;
  int pid_fils ;
  int w;

  pid = getpid();
  printf("> Le processus %i démarre...\n", pid);
 
  pid_fils = fork();

  if(pid_fils) {
    printf(" >> Je suis le père (pid du fils = %i).\n",pid_fils);
    printf(" >> Je suis le père et j'attends un peu.\n");
    sleep(20);
    printf(" >> Je suis le père et je demande l'état de mon fils.\n");
    wait(&w);
    printf(" >> Mon fils est mort (signal %i).\n", w);
    while(1) sleep(1);
  } else {
    printf(" >> Je suis le fils.\n");
    while (1) sleep(1);
    exit(0);
  }
  return(0);
}

Si on tue le processus fils pendant que le père ne fait rien, le processus fils devient un zombie. Dès que le père fait le wait, il reçoit la valeur du signal qui a terminé le processus et le zombie disparaît.

Si on ne tue pas le processus fils, le père n'exécutera jamais le printf(" >> Mon fils est mort...);.

Remarque : dans un système POSIX, lorsqu'un processus meurt, ses fils deviennent orphelins. Il continuent leur exécution mais sont adopté par init (PID : 1). Dans certains cas lorsque le processus est arrêté, il envoie explicitement un signal SIGTERM pour tuer ses processus fils. C'est par exemple ce qui arrive lorsqu'on lance des application à partir d'un terminal et que l'on quitte le terminal en question...

États d'un processus

On peut imaginer un SE dans lequel les processus pourraient être dans trois états :

• en cours d'exécution,
• bloqué : il attend un événement extérieur pour pouvoir continuer (par exemple une ressource; lorsque la ressource est disponible, il passe à l'état "prêt")
• prêt : suspendu provisoirement pour permettre l'exécution d'un autre processus.

Dans un système avec un unique processeur, au plus un processus peut se trouver dans l'état en cours d'exécution. Par contre, il peut y avoir de nombreux processus dans l'état bloqué ou dans l'état prêt.

Un processus peut passer d'un état à l'autre :

1. de en exécution à bloqué lorsqu'une ressource n'est pas disponible (entrées / sortie par exemple),
2. de bloqué à prêt si la ressource ayant provoqué le blocage devient disponible,
3. de en exécution à prêt si le système décide de suspendre l'exécution du processus,
4. de prêt à en exécution si le système décide de lancer l'exécution du processus.

On peut résumer ceci par le graphe de transitions suivant :

Les transition manquantes ne sont pas possible directement mais doivent passer par des transition intermédiaires.

On peut ajouter 2 états :

• nouveau pour un processus qui vient d'être créé,
• terminé pour un processus qui vient de se terminé.

Dans les systèmes type ordinateur de bureau, le passage de nouveau à prêt est automatique mais dans des systèmes temps réel, un processus peut parfois attendre dans cet état.

L'état terminé est en général passager. Par exemple, lorsqu'un processus terminé est un zombie, le processus n'est conservé que dans la table des processus. La mémoire utilisé par le processus est libérée. La question de savoir si ceci est véritablement un état du processus est donc essentiellement une question de vocabulaire.

exercice : ajouter les états nouveau et terminé et les transitions correspondantes au graphe précédent. Identifiez des situations provoquant les transitions possibles entre états.

Ordonnancement des processus

Nous avons vu qu'il pouvait y avoir de nombreux processus dans la table de processus (environ 150 sur mon ordinateur en ce moment même). Parmi ces processus, un seul (sur une machine à un processeur) peut se trouver dans l'état en exécution. C'est au système d'exploitation de décider qui, à un moment donnée, doit se trouver dans cet état. La partie du système faisant ceci s'appelle ordonnanceur (ou scheduler en anglais). En utilisant le contenu de la table des processus et éventuellement d'autres informations, ordonnanceur doit donc gérer les transitions entre états de tous les processus, et envoyer l'information nécessaire aux composants adéquat du noyau.

Comme d'habitude, l'ordonnanceur doit faire des compromis entre :

• la vitesse,
• l'utilisation de la mémoire,
• l'optimalité de la solution proposée.

Remarque : l'ordonnanceur est lui même un processus (ou un morceau de processus dans le cas des noyaux monolithiques).

Ordonnancement non préemptif

FIFO. L'algorithme d'ordonnancement le plus facile est probablement celui de type FIFO : premier arrivé, premier servi. Autrement dit, on préempte premier processus arrivé, et on l'exécute jusqu'à la fin. La seul structure de donnée est donc simplement une file.

Plus court temps d'exécution. Dans certain cas, on peut prévoir a l'avance le temps processeur dont aura besoin un processus pour s'exécuter. On peut alors choisir le processus le plus court et l'exécuter en premier. Ceci a en général tendance à diminuer le temps d'attente moyen d'un processus ; mais si des processus courts sont crées régulièrement, on peut assister à une famine : un processus peut ne jamais s'exécuter.

exercice : trouver une suite de processus qui provoque une famine.

Ces deux exemples sont acceptables pour un traitement par lots (batch) par exemple pour des calculs numériques. Ils ne sont par contre pas du tout adaptés pour un ordinateur personnel ou un système temps réels. (Pas de multiprogrammation.)

Ordonnancement préemptif

Pour pouvoir donner l'illusion de simultanéité, les processus sont en général exécutés par tranches de temps spécifiées à l'avance (time slice en anglais). Au bout de ce temps, le noyau reçoit une interruption et examine les processus. Il peut décider de continuer le processus courant, ou bien le remplacer par un autre processus. on parle de préemption.

Windows 3.1 ou MacOS 9 étaient des systèmes collaboratifs car les processus devaient explicitement laisser la main aux autres processus. Tous les systèmes d'exploitation modernes sont maintenant préemptifs. On parle maintenant de système préemptif lorsque la préemption peut s'effectuer même sur des processus en mode noyau. On parle parfois de noyau préemptible lorsque que les opérations en mode noyau sont elle même préemptibles.

Tourniquet. L'algorithme le plus simple est probablement celui du tourniquet (round Robin en anglais). C'est une variante de l'algorithme FIFO vu plus haut, mais qui préempte le processus courant au bout d'un moment. Si ce processus est encore en exécution, on le remet à la fin de la file des processus.

Le temps imparti à chaque processus ne doit pas être trop court (sinon, le changement de contexte prend trop de temps par rapport à l'exécution des processus) ni trop long (sinon, on perd l'illusion de parallélisme, et un processus bloqué risque d'occuper le processeur pendant trop longtemps).

Voici ce qu'on peut trouver dans le livre "Understanding the Linux kernel" :

The choice of quantum duration is always a compromise. The rule of thumb adopted by Linux is: choose a duration as long as possible, while keeping good system response time.

(extrait du chapitre "Process Scheduling").

Tourniquet avec priorité. Tous les processus ne naissent pas égaux : certains ont une importance plus élevée (les processus systèmes par exemple). Dans un cas comme le précédent, tous les processus ont le même statut... Pour corriger ce problème, on utilise parfois un algorithme similaire, mais on choisit le premier processus de priorité la plus élevé possible. Plutôt que de parcourir la file à sa rechercher, on utilise en fait plusieurs files : une pour chaque priorité.

Il faut faire attention car les processus de priorité basse risquent de ne jamais être exécutés (famine)... Par exemple, on peut diminuer petit à petit la priorité des processus qu'on exécute...

Une autre solution pour gérer les priorité en évitant certaines famines est d'exécuter toutes les files, mais pas en proportion égale. Par exemple, on choisit un processus dans les piles de priorité 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, ... De cette manière, les processus de la première file sont exécutés 2 fois plus de fois que ceux de la file 2, et 4 fois plus de fois que ceux de la file 3.

exercice : donnez un algorithme pour générer la suite précédente pour un nombre donné de files. Il faut que la file i soit utilisée 2 fois plus souvent que la pile i+1.

Répartition garantie. Chaque tache reçoit la même proportion du processeur, et chaque utilisateur reçoit la même proportion également.

tirage aléatoire. À chaque étape, on tire un "billet" au hasard, et le processus qui a le "billet gagnant" s'exécute.

Principe de priorité : Les processus qui ont été définit comme prioritaire on plus de "billet" à leur nom et ont donc plus de chance d'être tiré.

NB : POSIX définit une commande "nice" qui permet e donner à un processus un priorité plus faible (et par conséquent, nice -x augmente cette priorité). Il est évident que tout le monde ne doit pas pouvoir utiliser cette commande, il vaut mieux que l'administrateur se réserve ce droit

Ordonnancement équitable.

La mémoire

Introduction

RAM = Random Acces Memory. C'est ce que l'on appelle couramment la mémoire vive, elle peut être modifié à l'infini et sert à stocker temporairement les fichiers que l'ordinateur exécute.

ROM = Read Only Memory. On l'appelle aussi mémoire fixe ou mémoire morte, dès que l'on enregistre, le contenu d'une mémoire ROM ne peut pas être modifié (ex: un CD-ROM).

Gestion de la mémoire :

Lors du boot du PC, le système est chargé en mémoire. Tout processus créé est aussi chargé dans la mémoire.

Lorsque l'on créé uns seul processus, il est plus pratique de le charger en "bas" de la mémoire, à partir de la première case de l'espace mémoire. Puis les nouveaux processus peuvent être charger par dessus. Ainsi la machine comprend où commence l'espace mémoire.

Problèmes : 1 - l'espace d'adressage ne commence pas à 0; 2 - un processus peut demander dynamiquement de la mémoire; 3 - avec un accès direct, un processus peut faire "planter" un autre.

==> Il faut avoir une couche d'abstraction au-dessus de la mémoire physique.

Espaces d'adressage

Et si l'on créait des espaces d'adressage distincts pour chaque processus ? Par exemple : chaque processus utilise des adresse de 0 à n de la mémoire, on converti alors ces adresses en adresses physiques.

Certains des premiers processeurs avaient deux registres supérieurs :

- une Base => adresse physique du début de l'espace d'adressage

- une Limite => adresse physique de fin de l'espace d'adressage

Par exemple, lors de l'exécution d'un processus l'accès à une case "a" se transforme en l'accès à la Base+a et un test pour vérifier que : a+Base < Limite.

Malgré tout, ceci ne résout pas les problèmes liés au fait que des processus sont créés et disparaissent, réclament ou libèrent de la mémoire.

Va-et-vient (swapping)

Idée

Et si pour gérer tout cela on utilisait une mémoire auxiliaire (disque), pour stocker l'état de la mémoire de processus.

La mémoire vue par les processus ne correspond pas à la mémoire physique. À un instant donné, certains processus peuvent se retrouver sur le disque (dans le SWAP).

Quand un processus apparait, on lui cherche un morceau d'espace libre dans la mémoire.

gestion de la mémoire

• tableau de bits
• liste chaînée

Allocation

• first fit : utilise le premier bloc trouvé dans la mémoire dont la taille est égale ou supérieure au besoin.
• next fit : recherche un bloc disponible dont la taille convient exactement au besoin, et sinon utilise un bloc de taille supérieure.
• best fit : utilise le bloc le plus grand disponible.
• worst fit : first fit + recherche du bloc suivant à partir de la dernière case allouée.

Mémoire virtuelle

Idée

On ne garde pas tout le processus en mémoire physique.

Ceci permet d'offrir une mémoire virtuelle beaucoup plus grande que la mémoire réelle (physique).

L'espace d'adressage du processus est découpé en 'pages' de taille constante (sous GNU/Linux : 4Ko).

Il s'agit de mémoire virtuelle.

La mémoire virtuelle est découpée en 'cadres de page' de même taille que les pages. Idéalement, chaque page est dans un cadre. Les pages ne sont pas forcément dans des cadres consécutifs. Toutes les pages ne sont pas forcément dans des cadres : certaines peuvent être dans la swap.

Pagination

La traduction des adresses est plus complexe.

Si un processus fait référence à l'adresse 'a' :

1 - si une page est de taille "p" l'adresse "a" se trouve dans la page [a/p]

2 - l'adresse est à l'octet a%p dans cette page

3 - si la page [a/p] est dans le cadre n

L'adresse physique correspondant à "a" est (m*p)+(a%p).

Comme les adresse sont écrites en base 2 et que la taille d'une page est une puissance de 2, le quotient et le modulo s'obtiennent très facilement.

Si lors de l'étape 3, on réalise que la page n'est pas dans le cadre, on obtient un 'défaut de page'.

Dans ce cas, il faut trouver un cadre libre (ou en libérer un) et recopier la page en question à partir de la swap. Le processus est bloqué pendant ce temps.

Table des pages

Le système garde l'information sur les pages dans la table des pages, chaque entrée est de la forme :

Remarque :

Sous GNU/Linux, une page fait 4Ko soit environ $2^{12}$ octets.

Si on a un système d'exploitation sous 32 bits, la mémoire virtuelle contient $2^{32}$ octets, soit environ un million de pages.

Comme le nombre de pages est grand, chercher des informations prend du temps. Avec la mémoire virtuelle, chaque instruction est transformée en plusieurs instructions. Même si la table des pages est en mémoire, on y accède très souvent.

La plupart des processus accède tout le temps aux mêmes pages.

On rajoute un système pour accélérer l'accès à ces pages.

-> Le TLB :Translation Lookaside Buffer Partie matérielle du MMU (Memory Magement Unit).

Le TLB contient un petit nombre de la table des pages (moins de 64 pages) à accès ultra rapide -> ne contient que des pages en mémoire. Quand on fait référence à une adresse, on regarde en premier dans le TLB. Si une page n'est pas dans le TLB, on la cherche dans la table et on la met dans le TLB, pour les utilisations ultérieures (Remarque : il choisit une page à supprimer du TLB).

On parle du soft-miss quand une page est en mémoire mais n'est pas dans le TLB.

On parle de hard-miss dans la page n'est pas en mémoire (ou défaut de page).

Remplacement des pages

Algorithmes de remplacement de pages

Suite à une défaut de page , il faut recopier une page dans un cache, et il faut donc parfois supprimer une page de la mémoire.

-> Laquelle supprime-t'on ?

Algorithme optimal qui minimise le nombre de défaut de pages.

-> c'est compliqué et lent

-> on ne connait pas l'ordre des demandes de pages

Remplacement 'NRU' : Not recently Used

Idée

On remplace une page qui n'a pas été utilisée 'récemment'.

-> On utilise le bit de référencement ou d'accès en lecture

-> Régulièrement (interruptions horloge), on remet ce bit à 0

On choisit un cadre à supprimer par ordre de préférence :

- Bit référence 0 Bit écriture 0

- Bit référence 0 Bit écriture 1

- Bit référence 1 Bit écriture 0

- Bit référence 1 Bit écriture 1

FIFO

-> Pas bien

Algorithme de la seconde chance

Idée FIFO, mais on laisse une seconde chance aux pages références.

FIFO, si le dernier cadre a son bit de référence à 1, on remet le cadre en début de file avec son bit de référence à 0.

Tailles des pages

- Il faut choisir des pages pas trop grosses/petites pour éviter la fragmentation 'interne' (une page utilisée à moitié).

- Quand on accède à une page en swap on passe beaucoup de temps à chercher la page.

Les systèmes de fichiers

L'unité d'information crée par un processus est un fichier.

Comment ?

• Un support (disque, bande magnétique, etc..) peut être vue comme de la mémoire avec :

* une taille de bloc fixe

* une opération "read (a)" pour lire le bloc a

* une opération "write (a,b)" pour écrire b dans le bloc a

Une fichier n'est pas uniquement une suite d'octets. On veut organiser les fichiers de manière logique :

-> chaque fichier a (au moins) un nom

-> les fichiers ont organisés en arborescence dans des répertoires.

En général, le nom d'un fichier comporte une extension .ext (DOS 8.3) L'extension n'est qu'une partie du nom.

$file <nom_du_fichier>

Maintenant il y a une limite de taille du nom (255 caractères).

Comment stocker un fichier ?

- octets consécutifs sur le disque :

Avantage : rapide et simple, si on ne supprime pas

Inconvénient : si on supprime ou modifie -> c'est lent

-> Ce n'est pas utilisé pour les disques durs mais dans les CDs, DVDs, etc..

- suite de blocs -> (liste chainée) de blocs

Inconvénients :

- plus complexe d'accéder au milieu du fichier

- le pointeur prend quelques octets

Remarque : on a souvent besoin d'accéder à des plages de taille $2^{n}$

La taille d'un bloc de données (sans le pointeur) n'est pas une puissance de 2.

Pour corriger, on peut stocker les pointeurs dans un tableau à l'extérieur du fichier.

Cette taille doit être stocké en mémoire pour un accès rapide. Suivant la taille du bloc, on peut facilement atteindre une taille de 600mo pour un disque dur de 200Go.

-> Pas raisonnable

- Inode (index des nœuds)

On garde une taille des fichiers qui contient

- entête (information sur le fichier) sauf le nom

- adresse de blocs de données, un nombre fixe

- adresse d'un bloc qui contient des adresses de données

Le numéro d'une case (et donc d'un fichier) s'appelle un inode.

La table des inodes des fichiers ouverts est stockée en mémoire. Sa taille est proportionnelle au nombre de fichiers ouverts.

Remarque : la taille des blocs doit être

- ni trop petit (perte du temps pour la lecture sur le disque)

- ni trop gros (perte d'espace sur le dernier bloc)

Gestion des répertoires

- Un répertoire est donné par des informations (nom, date, etc...) et la liste de ces fichiers.

Attention : le nom des fichiers peut être long, on risque de perdre de la place.

Par exemple, on garde un tableau avec des numéros d'inode et un pointeur vers le nom de fichier.

Remarque : avec cette représentation, un fichier "physique" peut se trouver dans plusieurs répertoires.

On parle de lien physique entre les fichiers.

Sous Unix, la commande pour crée un lien physique est ln:

Attention : Il ne faut pas confondre un lien physique avec un lien symbolique.

Un lien symbolique est un nouveau fichier qui pointe sur un autre fichier (par son chemin d'accès).

- rajoute un inode

-> Il y a une direction.

Un lien physique ne peut exister que sur une unique partition.

Un lien symbolique peut pointeur n'importe où.

Remarque : une partition ressemble en général à :

Secteur de boot | Super bloc Information sur le FileSystem | Gestion espace libre |Taille inode | ....

Le système d'exploitation offre des fonctions "haut niveau" pour accéder aux fichiers.

Les fonctions principales sont : create(); delete(); open(); read(); write(); append();

Systèmes de fichiers journalisés

Toutes les équations sont écrites dans un journal et on efface après compilation.

Au démarrage, on commence par faire les opérations du journal (NTFS, Ext 3/4, ReiserFS).

Références

• le livre « Systèmes d'exploitation » de Andrew Tanenbaum est disponible à la BU
• la page du projet SOS
• la norme POSIX:2004
• l'API win32
• Commentary on the Sixth Edition UNIX Operating System