Introduction

Référence

Le livre

Operating Systems: Three Easy Pieces

Le code

Dépôt github à cloner :

https://github.com/remzi-arpacidusseau/ostep-code

git clone https://github.com/remzi-arpacidusseau/ostep-code
cd ostep-code
cd intro
make

Les outils

Ligne de commande

Les pseudo-systèmes de fichiers

Pas de vrais fichiers sur le disque : le noyau les génère à la lecture.

Exécution simultanée

Le programme

int main(int argc, char *argv[])
{
    char *str = argv[1];

    while (1) {
      printf("%s\n", str);
      Spin(1);
    }
    return 0;
}

Exécution simultanée

cat /proc/cpuinfo
./cpu 1 & ./cpu 2 & ./cpu 3 & ./cpu 4 &

# résultat de l'exécution...
# Les programmes s'exécutent "ensemble"
# 1 2 3 4 1 3 2 4 1 3 2 4 1 3 4 2 ...
./cpu 1 & ./cpu 2 & ./cpu 3 & ./cpu 4 &\
./cpu 5 & ./cpu 6 & ./cpu 7 & ./cpu 8 &\
./cpu 9 & ./cpu A & ./cpu B & ./cpu C &\
./cpu D &

# résultat de l'exécution...
# Les programmes s'exécutent "ensemble"
# On a des variations de l'ordre des sorties

Pour “tuer” ces processus : kill PID1 PID2 ...

Killall (à installer)

sudo apt update
sudo apt install psmisc
killall cpu

Conclusion

cat /proc/cpuinfo | grep processor | wc -l donne le nombre de “processeurs” (coeurs) du système

On a été capables de faire tourner plus de programmes en même temps qu’il n’y a de processeurs. Le système a donc une méthode pour “partager” le processeur entre les différents programmes.

Espace mémoire

Le code

int main(int argc, char *argv[]) {
    int *p;
    p = malloc(sizeof(int));
    assert(p != NULL);
    printf("(%d) addr pointed to by p: %p\n", (int) getpid(), p);

    *p = atoi(argv[1]); // assign value to addr stored in p
    while (1) {
      Spin(1);
      *p = *p + 1;
      printf("(%d) value of p: %d\n", getpid(), *p);
    }
    return 0;
}

Exécution

$ ./mem 100 & ./mem 200

# (2710) addr pointed to by p: 0x555555756260
# (2711) addr pointed to by p: 0x555555756260
# (2710) value of p: 101
# (2711) value of p: 201

Conclusion

Dans chaque processus, le pointeur p contient la même adresse 1, or les valeurs pointées par p dans chaque programme sont différentes.

Le système a donc une méthode pour “virtualiser” la mémoire : chaque processus manipule des adresses virtuelles, que le système traduit vers des adresses physiques différentes. Chaque processus a sa propre mémoire.

Simultanéité

Le code

volatile int counter = 0;
int loops;

void *worker(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        counter++;
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    loops = atoi(argv[1]);
    pthread_t p1, p2;
    printf("Initial value : %d\n", counter);
    Pthread_create(&p1, NULL, worker, NULL);
    Pthread_create(&p2, NULL, worker, NULL);
    Pthread_join(p1, NULL);
    Pthread_join(p2, NULL);
    printf("Final value   : %d\n", counter);
    return 0;
}

Exécution


./threads 100
# Initial value : 0
# Final value   : 200
./threads 100000
# Initial value : 0
# Final value   : 141148 (variable)

Conclusion

Ici, ce ne sont pas deux processus mais deux threads (processus légers) d’un même processus : contrairement aux processus, ils partagent la même mémoire.

Les deux threads tournent simultanément en accédant à une ressource partagée (l’espace mémoire counter).

La valeur de counter est lue, incrémentée et réécrite de manière non atomique. Dans ce cas on peut avoir des situations de compétition (race conditions).

counter contient 20
T1: lecture (registre = 20)
T2: lecture (registre = 20)
T1: incrémentation (registre = 21)
T2: incrémentation (registre = 21)
T1: écriture (counter = 21)
T2: écriture (counter = 21)

La solution est d’utiliser des méthodes d’exclusion mutuelle (mutex) ou des opérations atomiques.

Gestion des processus

Notion de processus

Définition

Un programme est un ensemble d’instructions machine et de données. Un processus est un programme en cours d’exécution

Lancement d’un processus

Deux appels systèmes :

On a donc un arbre des processus, avec des relations père/fils, des processus frères…

Le premier processus

Voir l’arbre des processus :

ps afx
pstree
ps -ef   # colonne PPID = PID du père

Ordonnancement

Stratégie

Lorsque plusieurs processus doivent tourner sur un processeur, comment organiser leur exécution ?

Sans interruption du processus :

Avec interruption du processus : ordonnancement préemptif utilisant context switch / timer interrupts

Le tourniquet (round robin)

Exemple, quantum = 2 : P1 (durée 5, arrive à t=0), P2 (durée 3, t=1), P3 (durée 2, t=2)

t 0 1 2 3 4 5 6 7 8 9
élu P1 P1 P2 P2 P3 P3 P1 P1 P2 P1

Ce tableau est un chronogramme (classique au bac : FIFO, SJF, tourniquet, priorités).

Les états d’un processus

L’OS est responsable des changements d’état des processus (élection, blocage…)

# Utiliser la commande top pour suivre les processus en cours
top

Les transitions entre états

Un processus bloqué ne redevient jamais directement élu : il repasse par prêt.

Priorité

La décision d’élection de l’ordonnanceur des tâches fait aussi intervenir un niveau de priorité : nice

Si plusieurs processus sont en concurrence pour l’élection, le processus le moins “nice” bénéficiera de la plus grande quantité de processeur.

man nice
man renice

Exemple : le programme

import sys
import datetime
print("Waiting to start")
i=0
while i < 10000000:
    i+=1
i=0
start = datetime.datetime.now()
while i < 100000000:
    i+=1
    if i%1000000 == 0:
        print(datetime.datetime.now(),sys.argv[1], i)
print("Done ", sys.argv[1], "in", datetime.datetime.now() - start)

Exemple : exécution

# Deux priorités différentes (19 = la plus basse)
nice -n 0 python3 loop.py A & nice -n 19 python3 loop.py B &

# Done  A in 0:00:18.003129
# Done  B in 0:00:18.680570

Presque aucune différence : sur un processeur multi-cœurs, A et B tournent chacun sur un cœur différent, ils ne sont pas en concurrence.

Exemple : tous les cœurs occupés

# On occupe d'abord tous les cœurs à 100 % (6 cœurs => 6 cpu)
./cpu 1 > /dev/null & ./cpu 2 > /dev/null &\
./cpu 3 > /dev/null & ./cpu 4 > /dev/null &\
./cpu 5 > /dev/null & ./cpu 6 > /dev/null &

# puis on relance A et B : ils sont maintenant en concurrence
nice -n 0 python3 loop.py A & nice -n 19 python3 loop.py B &

# cette fois, B (le plus "nice") finit bien après A

killall cpu   # ne pas oublier d'arrêter les programmes cpu

Autant de ./cpu que de cœurs (voir /proc/cpuinfo plus haut).

Partage de ressources

Mécanisme de blocage

Un processus accédant à une ressource non partageable peut la bloquer (acquisition d’un mutex)

Interblocage

https://fr.wikipedia.org/wiki/Interblocage

Deux mutex (M1 et M2), deux processus légers (P1 et P2) et la séquence d’opération suivante :

Dans cette situation, les deux processus sont définitivement bloqués.

Repérer et éviter un interblocage

Pour repérer un interblocage : dessiner qui détient quoi et qui attend quoi. S’il y a un cycle (P1 attend P2 qui attend P1), il y a interblocage.

Solution :

Exercices de bac

Sujets

Exercices de bac

Extraits des annales (liens sur le site web) :

  1. En situation complètement réelle, les processus n’ont pas exactement la même adresse, pour éviter certains types d’attaques, les adresses mémoires sont aléatoires. On peut désactiver ce comportement avec echo 0 | sudo tee /proc/sys/kernel/randomize_va_space, ce qui a été fait pour cette démo.↩︎