OS Flashcards
C’est quoi un OS ?
Ensemble logiciel qui orchestre l’accès aux
ressources matérielles et logicielles d’un ordinateur,
et fourni des services aux programmes.
A quoi sert un OS ?
couche d’abstraction
partage, isolation et protection des ressources
Donner des fonctionalités des OS
Gestion des pilotes de périphériques (drivers)
* Ordonnanceur (scheduler)
* Interruptions
* Système de fichiers (filesystem)
* Gestion multi-utilisateurs
* Sécurité
* Interface (graphique ou non)
Comment parler avec le kernel ?
Avec des syscall CE QUI AMENE A UN CHANGEMENT DE MODE
A quoi servent des protections rings
- Protection hardware
- Niveau de privilège
- Virtualisation
Donner les caracteristiques possibles d’un OS :
Mono vs Multi-tâches
* Plusieurs programmes en « parallèle »
* Mono vs Multi-utilisateurs
* Isolation via droits d’accès (matériel, fichiers, temps de calcul …)
* Temps Réel
* Contraintes et stabilité des temps d’exécution
* Embarqué
* Compacts et demandant peu de ressources.
* Distribué
* Abstrait plusieurs machines en une seule
UNIX a quelle caracteristiques ?
Multi-tâche
Multi-utilisateurs
Donner les deux concepts fondamentaux de linux
Les processus
* programme en cours d’exécution
* Incarnation dynamique d’un programme statique (code)
* Les fichiers
* Utilisés pour quasiment tout représenter
* Hiérarchie mais une seule racine
C’est quoi POSIX ?
Portable Operating System Interface
* Standards pour les interfaces logicielles
* fonctions et structures en C
* Standards pour les interfaces utilisateurs
* Ligne de commande (Bourne Shell)
* Peut être implémenté sur des OS non-UNIX
* C’est le cas de Windows
* Il y a plusieurs versions du standard !
C’est quoi le Virtual File System ?
associer Nom -> Fichier + Méta donné
C’est quoi un I-node ?
Identifié par un numéro d’indexation dans une table système
ilist[inumber] = inode
Contient des métas donnés
Pas d’informations sur la hiérarchie ! (chemin/nom)
Quels sont les types de fichiers en UNIX ?
Régulier: binaire/text (.pdf, .txt, .json, .png, …)
* Répertoire: Liste associant noms et inode
* Spécial: Lecture par bloc / caractère (périphérique)
* Lien symbolique: Référence un autre fichier (par son chemin)
* Tube nommé (pipe): Communication unidirectionnelle (local)
* Socket: Communication bidirectionnelle (distant)
Quelle différence entre les hard link et les soft link ?
Hard link
* Association nom (chemin => inode)
* Incrémente le compteur de liens
* Il pointera toujours vers un fichier
* Fichier réellement supprimé lorsque le compteur tombe à 0
* Soft link
* Association chemin => chemin
* Si le chemin pointé disparait, le soft link ne fonctionne plus (dangling link)
C’est quoi un point de montage ?
répertoire du SF racine où l’on attache un autre SF
Comment identifier de manière unique un fichier ?
numéro d’inode + identifiant du support (device ID)
Donner les fonctionalités d’un système de fichier
- Journalisation
- Redondance multi-disques (RAID)
- Partitions/volumes multi-disques
- Redimensionnement à chaud
- Compression
- Chiffrement
- Gestion des droits d’accès
- Quotas
- Déduplication
- Copy-On-Write (Shadow copy)
C’est quoi le Shell ?
Logiciel permettant d’interagir avec le système d’exploitation (coque)
Donner les avantages du shell
Très commun : le shell « standard »
+ Sa syntaxe sert généralement de base pour d’autres shell
+ Très riche : accès facile aux fichiers, processus, …
+ Bien documenté
Que défini la colling convention ?
La calling convention défini comment le caller parle avec le callee
* Où stocker les valeurs
* Dans quel ordre
Comment partager de la mémoire ?
Avec shm et mmap
Comment créer un processus en C ?
posix_spawn()
Comment copier le processurs courrant en C ? (Sauf PID etc…)
fork/clone
Que fait exec
Remplace tout le processus par un autre programme
* Sauf les file descriptors !
C’est quoi le Loader
Partie de l’OS responsable du chargement d’un processus.
Il doit notamment :
* Valider des droits d’exécution
* Mapper en mémoire du code à exécuter
* Le programme lui-même
* Les bibliothèques dynamiques
* Copier les paramètres de ligne de commande
* Initialiser les registres (SP, BP, …)
* Jumper à l’adresse de début du programme (entrypoint)
* Correspond à modifier l’IP
Que permet wait() ?
Attente de la fin d’un processus enfant
* Récupération du code de retour
* Un processus est considéré comme « zombie » tant que son parent n’a pas
récupéré son code de retour !
C’est quoi un processus zombie ?
Un processus terminé reste dans la table des processus jusqu’à ce
que son parent le « wait », et récupère son code de retour.
C’est quoi un processus orphelin ? Par qui est il adopté ?
Un processus dont le parent se termine avant l’enfant
* C’est un processus « orphelin ».
* Le processus est adopté par
* Le premier un processus marqué comme « subreaper » parmi les ancêtres
* le processus racine init
* Il n’est donc pas orphelin très longtemps !
Donner les états d’un processus
- Running : En cours d’exécution
- Runnable : Mis en pause par l’ordonnanceur
- Uninterruptible : ne se réveille pas en cas de signal
- En général en train de faire de l’I/O
- Interruptible : se réveille en cas de signal
- Stopped : Arrêté par un signal SIGTSTP/SIGSTOP,
peut être réveillé par le signal SIGCONT - Zombie : Processus terminé (soit par lui-même, soit
par un utilisateur) mais qui n’a pas été attendu par
son parent.
C’est quoi l’ordonanceur ?
L’ordonnanceur (scheduler)
est responsable des
changements d’états entre
C’est quoi la préomption ?
Préemption :
L’ordonnanceur force le
changement d’état
Running → Ready
(Tache suspendu au profit d’un autre)
C’est quoi le PCB ?
Structure qui contient les informations d’un processus
* PID, PPID
* Temps CPU accumulé
C’est quoi un Context switch ?
Lorsqu’un processus sort de l’état « Running », il faut sauvegarder son
état actuel pour reprendre son calcul plus tard :
* Changement de mode → kernel
* Sauvegarde
* registres et pointeurs (IP, SP, BP, …)
* PCB
* Mitigations de failles de sécurité Hardware (e.g. Spectre)
* …
* Restauration du process de destination
Expliquer ce qu’est un scheduler Préemptif ?
Le système réquisitionne l’utilisation d’un processeur quand il estime qu’il
faut l’attribuer à un autre processus
* Généralement basé sur un Quantum de temps (a.k.a. time slice)
Expliquer ce qu’est un scheduler Collaboratif ?
Les programmes ont la charge de libérer le processeur (via un Wait/Yield)
Expliquer l’ordonancement FCFS ?
First Come First Served
Expliquer l’ordonancement SJF ?
(Shortest Job First) : Préemptif ou non
Expliquer l’ordonancement Priority ?
FCFS avec une liste par priorité
Expliquer l’ordonancement RR ?
FCFS avec un quantum - Préemptif
Expliquer l’ordonancement CFS ?
Completely Fair Scheduler) Par défaut sur Linux
Quelle est la différence entre la mémoire interne et externe
Interne : accessible depuis le CPU
* Dite « de travail »
* RAM, PCI-express,…
* Externe : les données doivent être copiées en mémoire interne pour
être accédées par le CPU
Avantages de l’adressage virtuel
Pas d’accès à la mémoire d’un autre processus (sauf si partage explicite)
* (taille de l’espace virtuel) ≠ (taille de l’espace physique)
* Pour ne charger en mémoire que le nécessaire
* Ou utiliser plus de mémoire que l’on peut adresser (>4Go avec CPU 32 bits)
* Plusieurs adresses virtuelles → une adresse physique
* Partage/réutilisation de mémoire entre processus
* Pas de problèmes de fragmentation causés par les autres processus
* Mapping de fichiers
* Permet de lire des fichiers comme s’ils étaient en RAM !
C’est quoi la pagination ?
Découpage en blocs de taille fixe
* Adresse = PageNumber x PageSize + Offset
C’est quoi les Segments ?
pace mémoire contigu de taille variable
* Table des segments => Adresse de la base | taille | permissions
* Origine de la segmentation fault
* Plus vraiment utilisé côté HW de nos jours
C’est quoi la page table
TRADUIT ADRESSE VIRTUELLE EN ADRESSE PHYSIQUE
Page Table (structure de donnée)
* Traduction Page Number → Page Frame Number (PFN)
* Peut également contenir des informations sur la page (protection, validité…)
* Chaque processus a ses propres tables
* Changement lors d’un context switch
* La page table peut elle aussi être allouée en mémoire virtuelle
* Permet d’éviter de créer un mapping complet de la mémoire (coûteux)
* Tout ça est de nos jours géré côté hardware par le
MMU (Memory Management Unit)
* La structure dépend donc du CPU (x86 ≠ x64 ≠ ARM ≠ …)
C’est quoi une page fault ?
Exception renvoyée par le MMU, traitée par le kernel (sinon envoie SIGSEGV)
* Si l’adresse est invalide
* Si les droits ne correspondent à l’opération (e.g. écrire dans une page read-only)
* Si on tente d’exécuter une page No-Execute
* Si l’un des bits « Reserved » vaut 1
Le kernel peut utiliser ce mécanisme pour :
* délayer le mapping avec la page physique (on-demand paging)
* charger des bouts de fichiers (file mapping)
* Copy On Write (COW
C’est quoi le TLB ?
Traduire une adresse peut nécessiter 3 indirections !
C’EST UN CACHE
Tableau avec X (16-512) paires Page Number ⇔ Page Frame Number
* Si le numéro de page est déjà présent, on renvoie le numéro de frame
* Sinon, on demande au MMU et stocke le résultat pour après
C’est quoi le Résident / Working set ?
Comme mentionné plus tôt, l’OS n’assigne pas (toujours) directement
une page physique pour une adresse mémoire.
On appelle Resident Set l’ensemble des pages virtuelles ayant un
mapping valide vers une page physique.
RSS (Resident Set Size)
→ C’est la métrique principale à regarder dans ps/top
N’inclue pas la mémoire partagée, ni en général les hugepages
C’est quoi un page file / Swap file
Que se passe-t-il lorsque le système n’a plus assez de mémoire ?
- On choisit des pages à « expulser » (evict) de la mémoire
- On rend la page invalide
- On écrit son contenu sur une mémoire externe : le page file
- Typiquement votre disque dur/SSD
- Si plus de place dans le swap file => « out of memory ! »
- Uniquement si la page est « dirty » ou pas déjà sur le disque
- Lors d’un futur accès
- Page Fault => on recharge les données depuis le disque
Donner des algorithmes de remplacement de page
Aléatoire : Le meurtrier fou, rapide, mais dangereux
* FIFO : Page la plus anciennement chargée
* LRU : Page la plus anciennement utilisée
* Clock : Pseudo LRU basé sur un compteur incrémenté tout
les X ticks si la page a été utilisée depuis le dernier tick
* 2nd chance : On commence par les pages non utilisées, puis fallback
sur un autre algorithme
* Belady: Page qui sera utilisée dans le futur le plus lointain
Utilisé pour comparaison théorique car optima
Donner la définition de parallélisme
Lorsque l’exécution des tâches
est simultanée.
Dans le cas d’un processeur,
ce n’est possible uniquement que
si l’on a plusieurs cores ou SMT.
Donner la définition de concurence
capacité d’un système à gérer plusieurs tâches en même temps, mais pas nécessairement en les exécutant simultanément. Il s’agit de la gestion de plusieurs tâches qui progressent, potentiellement en alternance, dans le temps.
Donner le lien entre parallelisme et concurence
Parallélisme => Concurrence
C’est quoi un Thread ? Quelle propriété ça à par rapport à un processus ?
Un process contient autant de threads qu’il le souhaite.
Les ressources (mémoire et puissance) du processus sont partagées entre les threads
=> Context swtich plus rapide
C’est quoi l’oversubscription ?
Quand un process à trop de thread.
Que fait join ?
C’est pour attendre un autre thread, sinon on peut le détaché si on le syncronise d’une autre manière
C’est quoi une coroutine ?
Thread en plus :
- Légé
- Simple à syncro
Un thread peut switcher d’une coroutune à une autre
Quelle est la différence entre Stackful coroutines et Stackless coroutines ?
- Chaque fibre sauvegarde sa propre stack au complet VS Données copiées pour la reprise de l’exécution
Que fait fork vis à vis des descripteur de fichier ?
Il duplique la table donc pointe sur les même fichers
Que fait fork vis à vis des descripteur de fichier ?
Il ne ferme pas les descripteurs
C’est quoi le Buffering user-land ?
fwrite
Copie les données dans un
buffer du process
Appelle write qu’une fois le
seuil atteint (Evite de couteux syscalls) = Flush
C’est quoi le Cache kernel-land ?
Copie des données dans une
page de cache
Flushé régulièrement
C’est quoi IO rings ?
On a deux file,
App met dans la queue de la submistion queue
Kernel prend dans la tête et l’execute
Kernel met le resultat dans la completion queue
L’app les récupères en tête de la completion queue
C’est quoi une ressource ?
Entité requise par un processus pour s’exécuter
-Matérielle (CPU, RAM, périphérique…)
- Logicielle (variable)
C’est quoi une race condition ?
Situation de compétition entre deux precessus :
RESULATAT DIFFERENT EN FONCTION DE L’ORDRE D’EXECUTION DES PROCESSUS
C’est quoi une ressource critique ?
Si des accès peuvent mener à un état incohérent
C’est quoi une section critique ?
Section de programme où est manipulé une ressource critique
C’est quoi une primitives de synchronisation ?
instruction simple qui permet la synchronisation de processus
C’est quoi Mutual exclusion ?
A tout instant du programme, au plus UNE seule unité d’exécution
peut obtenir et accéder la ressource critique
C’est quoi un mutex ?
Objet permettant de réaliser une exclusion mutuelle. (Lock / Unlock)
C’est quoi un Mutex réentrant ?
Mutex qui autorise un même thread à lock plusieurs fois la même ressource
C’est quoi un deadlock ?
Deux thread :
Un lock A et veut B
Lautre veut A et lock B
C’est quoi une Starvation / Famine ?
Un thread lock A et pleins d’autre thread veulent A
Comment éviter la famine ?
(Multiple)Readers-(Single)Writer lock
C’est quoi un Semaphore ?
Un compteur initialisé à une valeur qui ne doit pas aller en dessous de 0.
Si cette valeur d’init est 1, on l’appelle une binary-semaphore
A voir comme un parking avec un compteur d’emplacements disponibles.
Si 0, j’attends qu’une place se libère, sinon je me gare
C’est quoi une Busy loop ?
Loop qui vérifie en boucle s’il y a des choes à faire => Pas bien car ne s’endort jamais du coup
C’est quoi une condition variable ?
De façon atomique: Libère le mutex + Met le thread courant dans la liste des
threads à réveiller + Endort le thread
Puis une fois réveillé, acquiert à nouveau le mutex
Comment éviter les spurious wakeups ?é
toujours vérifier la condition associée
au réveil !
C’est quoi une priority inversion ?
LP lock A
MP veut taffer donc passe avant LP
HP veut taffer donc passe avant MP mais a besoin de A donc attends.
Résultat : MP est executé avant HP
Comment éviter une priority inversion ?
Priority ceiling
* Si une tache acquiert une ressource, sa priorité devient la priorité la plus
haute
Priority inheritance
* Si un thread tente de lock une ressource déjà lockée, le thread qui la
possède reçoit la plus haute priorité des deux threads.
Priority boost / Random boosting
* On boost la priorité d’un thread resté inactif
C’est quoi une Barrière ?
Aucun ne peux continuer sans attendre les autres
C’est quoi opérations atomiques
Une opération atomique est une opération (ou semble d’opérations) ne pouvant être interrompues avant leur fin.
Que permettent les opérations atomique ?
Permet de faire des structures lockless / lockfree
Les volatiles sont ils utilies avec les threads ?
NON (une variable volatile est une variable sur laquelle aucune optimisation de compilation n’est appliquée)
Méthodes de programmation concurrente
- Message queues (Apache Kafka, RabbitMQ, ActiveMQ …)
- Event loops (Windowing APIs, Javascript, D-Bus…)
- Streaming processing (Kafka Spark, Google Dataflow, Datastreams…)
- Transactions (Base de données, votre CPU, Filesystems…)
- SPMD Single Program Multiple Data (SIMD, ISPC, HLSL, GLSL, CUDA…)
- Task/job systems (task graphs, threadpools, Unity, UE5, …)
C’est quoi IPC ?
Communication Inter-Processus
Pour le partage de données : Fichier / mémoire partagée
Pour la syncro : Signaux, sémaphores, verrous
Pour les deux : Tube
