Partage du temps et ordonnancement Flashcards
Quelle est la différence entre multitâche et multitraitement/multiprocessing ?
Multitâche = plusieurs processus sur un CPU, multitraitement = plusieurs CPU
Qu’est-ce que le degré de multiprogrammation ?
Nombre de processus chargés en mémoire
Quelle est la différence entre attente active et attente passive ?
Active (polling) = gaspillage CPU
Passive = libère le CPU
Qu’est-ce qu’une commutation de contexte ?
Changement de processus actif sur le CPU
Quels sont les composants d’un contexte de processus ?
- Registres CPU
- État
- Mémoire
- Files d’attente
Qu’est-ce que le PCB (Process Control Block)
Une structure de données du noyau qui représente un processus et son état d’exécution.
Elle contient le PID, fichier exécutable, permissions, mais aussi un TCB
Qu’est-ce que le TCB (Thread Control Block)
Une structure de données du noyau qui représente un VCPU = contexte d’exécution : elle contient une fonction copie du contenu du CPU
Qu’est-ce que la dispatch latency ?
Temps perdu à changer de processus
Quels sont les 5 états d’un processus ?
- New
- Ready
- Running
- Blocked
- Terminated
Dans quel état est un processus qui attend un événement ?
Blocked
Dans quel état est un processus en attente d’exécution ?
Ready
Quelles sont les principales files d’attente des processus?
- Ready Queue
- Disk Queue
- Sleeping Queue
Quelle est la différence entre un processus CPU-bound et I/O-bound ?
CPU-bound = beaucoup de calculs, I/O-bound = beaucoup d’attente E/S
Pourquoi un OS favorise-t-il les processus I/O-bound ?
Pour éviter que le CPU reste inactif
Pourquoi un processus I/O-bound passe-t-il souvent en état bloqué ?
Il attend les réponses des périphériques
Qu’est-ce que l’ordonnancement en OS ?
Décider quel processus exécuter et quand
Quels sont les deux types d’ordonnancement ?
- Préemptif
- Non-préemptif
Quelle est la différence entre ordonnancement préemptif et non-préemptif ?
Préemptif = le noyau peut reprendre le CPU
Non-préemptif = le processus décide
Quelles sont les décisions prises par un ordonnanceur ?
- Quel processus exécuter
- Pour combien de temps
Qu’est-ce que le quantum en ordonnancement ?
Durée maximale d’exécution avant préemption
Quel est le compromis entre durée du quantum et latence du dispatcher ?
Trop court = surcoût
trop long = manque de réactivité
Qu’est-ce que l’algorithme First Come First Served (FCFS) ?
Exécution dans l’ordre d’arrivée (FIFO)
On choisit la tâche qui est arrivée le plus tôt dans la ready queue.
Quel est l’inconvénient du FCFS ?
Effet de convoi (convoy effect) : les petites tâches risquent d’être désavantagées (effet d’accumulation)
Qu’est-ce que la famine (starvation) en ordonnancement ?
Un processus prêt se retrouve à attendre indéfiniment avant de pouvoir être exécuté
Quel algorithme réduit la famine en préemptant les tâches longues ?
Round Robin
Qu’est-ce que l’algorithme Shortest Job First (SJF) ?
Exécute le processus le plus court en premier
Quel est le problème principal de SJF ?
La famine des tâches longues
Qu’est-ce que l’algorithme Shortest Remaining Time First (SRTF) ?
Variante préemptive de SJF : chaque
Quel est l’inconvénient du SRTF ?
La famine est toujours possible
Qu’est-ce que l’algorithme Round Robin (RR) ?
Exécution de chaque processus en tours de rôle avec quantum, préemption lorsqu’une tâche dépasse son quantum
Comment choisir la bonne valeur du quantum en Round Robin ?
Trop court = surcoût en performance
Trop long = manque de réactivité
Qu’est-ce que l’ordonnancement à priorités ?
C’est dans la vraie vie : exécuter les processus avec la priorité la plus haute, on maintient plusieurs ready queue distinctes, et chaque file applique une politique différente
Comment éviter la famine en ordonnancement à priorités ?
Augmenter progressivement la priorité d’un processus en attente
Qu’est-ce que le Multi-Level Feedback Queue (MLFQ) ?
Ordonnancement dynamique avec plusieurs files et ajustement des priorités
Quels sont les critères d’évaluation d’un ordonnanceur ?
- CPU Utilization
- Throughput
- Turnaround Time
- Waiting Time
- Response Time
Qu’est-ce que le Turnaround Time ?
Temps entre l’arrivée et la fin d’un processus
Qu’est-ce que le Waiting Time ?
Temps total passé dans la Ready Queue
Qu’est-ce que le Response Time ?
Temps entre l’arrivée et la première exécution
Quelle loi empirique explique l’intérêt de la multiprogrammation ?
Alternance entre CPU bursts et I/O bursts
Que dit la loi empirique sur les processus en OS ?
Ils sont soit plutôt CPU-bound, soit plutôt I/O-bound
Pourquoi un bon ordonnanceur doit-il connaître la durée des bursts CPU ?
Pour mieux prévoir l’exécution des processus
Quel est l’impact d’un kernel tick sur l’ordonnancement ?
Définit la fréquence des interruptions pour le scheduling
Qu’est-ce qu’un ordonnanceur temps réel ?
Un ordonnanceur avec des priorités fixes et des contraintes strictes
Qu’est-ce que la Ready Queue (ou Run Queue) ?
Les PCB des processus prêts
Quel est le rôle du scheduler ?
Choisir un PCB dans la Ready Queue
Que signifie qu’un processus est compute-bound ou I/O-bound ?
Cela signifie que sa performance dépend beaucoup de la vitesse de calcul du CPU/de la vitesse des E/S
L’ordonnancement de FCFS est-il préemptif ou non ?
Non-préemptif : de plus, aucun risque de famine
Contexte d’exécution
Toutes les informations dont a besoin un processus pour s’exécuter
Dispatcher
Composant logiciel chargé de faire le context switch, en faisant sauvegarde et restauration
Scheduler
Composant logiciel qui choisi vers quel processeur on saute en sortant du noyau
Ordonnancement non-préemptif (=coopératif)
Les applications rendent explicitement la main au noyau, via les appels système bloquants
Ordonnancement préemptif
Permet au noyau de garder le contrôle de la machine : (exemple : un processus n’a rien demandé, mais qu’on lui prend le CPU pour donner à quelqu’un d’autre. En d’autres termes, l’ordonnanceur retire de force le CPU à un processus et le remet dans la Ready Queue).
À quel moment on a une situation de famine ?
Ordonnanceur non-préemptif + tâche infinie
Ordonnanceur préemptif + malchance
Préemption
Le noyau reprend la main à une tâche qui n’était pas prête à rendre la main et remet donc le processus dans la Ready Queue
La famine est possible pour les stratégies…
SJF et SRTF
RR est une variante…
préemptif de FCFS
SRTF est une variante…
préemptive de SJF
Appel bloquant
Lorsque l’on est sur un processus P1, après un syscall dit bloquant, le scheduler rend la main à un autre processus P2 ≠ P1 (ex : sleep, wait, write, read)
Les mécanismes implémentés dans le noyau sont
ISR, les syscall, le context switch, l’ordonnanceur et autres
