Revision sheet: Gestion efficace des processus et ressources

📋 Plan du Cours

1. Diagramme d’état des processus
2. Ordonnancement FCFS, SJF et SRTF
3. Systèmes interactifs et temps réel
4. Round Robin et priorités
5. Ordonnancement garanti et équitable
6. Multithreading et performances
7. Concurrence et exclusion mutuelle
8. Sémaphores, mutex et classiques
9. Deadlocks et stratégies
10. Systèmes de fichiers et allocations
11. RAID, FAT et répertoires

📖 1. Diagramme d’état des processus

🔑 Notions clés & Définitions

• EX : État où le processus exécute réellement sur le processeur.
• PR (prêt) : État où le processus est prêt à être exécuté et attend une opportunité CPU.
• BL (bloqué) : État où le processus ne progresse pas tant que sa condition d’attente n’est pas satisfaite.
• USR (mode utilisateur) : Mode d’exécution qui caractérise les traitements effectués au niveau utilisateur.
• SYS (mode système) : Mode d’exécution qui caractérise les traitements effectués au niveau du noyau.

📝 Points essentiels

• Les transitions du diagramme incluent chargement, déchargement et déblocage.
• La terminaison mène au processus nommé ZOMBIE.
• La création est associée à l’entrée initiale du processus avant qu’il devienne prêt ou exécutable.
• Le diagramme distingue clairement les exécutions en mode utilisateur et en mode système (USR et SYS).
• Des événements comme communication et allocation apparaissent comme transitions entre états.

💡 Astuce mémo

EX = “Execute”, PR = “Prêt”, BL = “Bloqué”, ZOMBIE = “Fin en attente de nettoyage”.

📖 2. Ordonnancement FCFS, SJF et SRTF

🔑 Notions clés & Définitions

• FCFS : Politique d’ordonnancement qui sert les tâches dans l’ordre d’arrivée.
• FIFO : Structure de file utilisée pour implémenter FCFS.
• SJF : Politique choisissant la tâche ayant la durée estimée la plus courte.
• SRTF : Variante SJF qui choisit la tâche ayant le temps restant estimé le plus faible.
• Famine (starvation) : Situation où certaines tâches peuvent attendre indéfiniment selon la politique.

📝 Points essentiels

• Avec FCFS (FIFO), l’ordonnancement est annoncé équitable mais inefficace sur une charge mixte CPU et I/O bound.
• FCFS ne maximise pas le throughput et ne minimise pas le turnaround dans le cas présenté.
• Pour SJF, le turnaround est minimal seulement si aucune tâche ultérieure n’est plus courte que la tâche courante.
• Le cas SJF avec durées 3, 2, 4, 7, 6 donne un ordre menant à un total de 53 et un turnaround moyen de 10,6.
• Le cas SRTF minimise le turnaround en se basant sur la durée restante estimée.

💡 Astuce mémo

SJF choisit “la plus courte maintenant”, SRTF choisit “la plus courte après maintenant” (restant).

📖 3. Systèmes interactifs et temps réel

🔑 Notions clés & Définitions

• Temps réel : Cadre où le système doit réagir et traiter des événements avec des échéances strictes ou flexibles.
• Échéances hard : Contraintes de délais dont le non-respect est considéré comme intolérable.
• Échéances soft : Contraintes de délais dont le non-respect est tolérable mais doit être minimisé.
• Délai minimal action user→réaction : Métrique cherchant à réduire le temps entre l’action de l’utilisateur et la réponse du système.
• Proportionnalité aux attentes du user : Principe de performance visant à faire correspondre le comportement du système à ce que l’utilisateur anticipe.

📝 Points essentiels

• Dans les systèmes interactifs, les utilisateurs peuvent créer des processus et les contraintes fortes sont absentes, ce qui rend le comportement moins strict.
• Des processus infinis peuvent exister en système interactif, ce qui rend l’ordonnancement sensible à la famine.
• Les métriques de l’ordonnanceur en interactif incluent un délai minimal entre action user et réaction système.
• Les propriétés désirables en interactif incluent l’utilisation optimale des ressources (CPU vs I/O) et l’évitement de la starvation.
• En temps réel, la propriété exigée est le respect des échéances strictes (hard deadlines) et la propriété désirée est le respect des échéances flexibles (soft deadlines).

💡 Astuce mémo

Interactif = “répondre vite”; Temps réel = “tenir les délais” (hard) et “bien cadrer les écarts” (soft).

📖 4. Round Robin et priorités

🔑 Notions clés & Définitions

• Round Robin : Politique qui répartit le processeur en donnant à chaque tâche un quantum de temps.
• Quantum : Durée allouée à un processus lors d’un passage de l’ordonnancement.
• File cyclique : Structure cyclique utilisée pour implémenter Round Robin.
• Priority Scheduling : Politique où un niveau de priorité fixe la part de temps CPU attribuée.
• Classes de priorité : Catégories comme timesharing et realtime utilisées pour organiser le scheduling par niveaux.

📝 Points essentiels

• Round Robin est basé sur un quantum et implémentable avec une liste cyclique.
• Round Robin est présenté comme équitable du point de vue de la répartition du processeur sans distinguer l’importance relative des processus.
• En priorités, une priorité élevée correspond à 4 quanta et une priorité faible à 1 quantum.
• Les priorités sont décrites comme dynamiques et reflètent le comportement des processus.
• Le scheduling par priorités favorise l’exécution des processus I/O-bound prêts et vise à recouvrir les latences I/O par du calcul CPU.

💡 Astuce mémo

Round Robin = “tour de rôle”; Priorités = “plus haut = plus de quanta (4 contre 1)”.

📖 5. Ordonnancement garanti et équitable

🔑 Notions clés & Définitions

• Guaranteed Scheduling : Ordonnancement visant une répartition au prorata du nombre de processus avec un délai garanti calculé.
• Délai garanti : Estimation de délai associée à chaque processus basée sur le temps depuis sa création et le nombre de processus.
• ρ (rho) : Rapport utilisé pour décider du moment où un processus peut continuer son exécution (jusqu’à ρ > 1).
• Fair-Share Scheduling : Ordonnancement qui répartit au prorata du nombre d’utilisateurs plutôt que du nombre de processus.
• Pro rata (au prorata) : Principe de partage proportionnel à la quantité de processus ou d’utilisateurs considérée.

📝 Points essentiels

• L’objectif de Guaranteed Scheduling est une répartition au prorata du nombre de processus.
• Le délai garanti est donné comme Temps depuis sa création divisé par le nombre de processus.
• ρ est défini comme Temps nécessaire rapporté au Délai garanti.
• L’algorithme exécute un processus jusqu’à ce que ρ > 1.
• Fair-Share Scheduling répartit au prorata du nombre d’utilisateurs.

💡 Astuce mémo

Garanti = “Temps depuis création / nb processus”; ρ décide “quand arrêter” via seuil 1.

📖 6. Multithreading et performances

🔑 Notions clés & Définitions

• Multithreading : Technique où plusieurs threads s’exécutent au sein d’un même processus pour mieux exploiter parallélisme et latence.
• Throughput : Mesure de performance donnée comme nombre de tâches par heure.
• Création et commutation : Mesures d’efficacité liées au coût de créer des activités et de passer d’une activité à une autre.
• Thread dispatcher : Composant logique chargé d’initialiser et de boucler pour répartir le travail entre threads.
• User-level : Implémentation où l’ordonnancement des threads dépend d’un ordonnanceur utilisateur indépendant de celui de l’OS.

📝 Points essentiels

• Les motivations incluent qu’une activité bloquée permet d’exécuter une autre activité et que la création/commutation est rapide.
• L’exécution décrite du processus (au sens initial) est présentée comme purement séquentielle.
• Pour améliorer les performances, le cours cite augmenter le throughput, réduire le délai ouverture→fermeture, et répartir sur plusieurs processeurs/coeurs.
• En user-level, la préemption entre threads est difficile et un blocage d’un thread bloque le processus.
• En kernel-level, un blocage d’un thread ne signifie pas blocage du processus et l’OS peut choisir un thread prêt, y compris d’un autre processus.

💡 Astuce mémo

User-level : “pas trop préemptif et blocage se propage”; Kernel-level : “préemptive par l’OS et moins de propagation”.

📖 7. Concurrence et exclusion mutuelle

🔑 Notions clés & Définitions

• Concurrence : Situation où plusieurs activités accèdent simultanément à des ressources ou à des variables partagées.
• Race Condition : Problème où l’interleaving des opérations sur une donnée partagée change le résultat observé.
• Interleavings : Ordres possibles d’exécution de fragments d’instructions qui peuvent diverger entre exécutions.
• Exclusion mutuelle : Propriété garantissant qu’au plus un thread se trouve dans la section critique à un instant donné.
• Section critique : Zone de code qui manipule un objet partagé et doit être protégée par des règles d’accès.

📝 Points essentiels

• Les interleavings différents peuvent produire des résultats différents lorsqu’une opération lit puis manipule une variable partagée.
• La race condition décrite survient quand une interruption intervient entre un “read” et une modification de la même variable.
• Une section critique délimite le code manipulant l’objet partagé et régule les entrées dans cette zone.
• Les critères requis incluent l’exclusion mutuelle, l’absence d’attente injustifiée, l’absence de famine, et une indépendance vis-à-vis de la vitesse et du nombre de processeurs.
• Le cours suppose une absence d’exécution out-of-order du processeur pour raisonner sur les solutions.

💡 Astuce mémo

Race condition = “le même objet partagé, mais des ordres différents” → résultat change.

📖 8. Sémaphores, mutex et classiques

🔑 Notions clés & Définitions

• Sémaphore : Mécanisme de synchronisation basé sur une variable entière et une file d’attente pour threads bloqués.
• Sémaphore avec down/wait : Opération atomique qui prend une ressource et peut bloquer si elle n’est pas disponible.
• Sémaphore avec up/signal : Opération atomique qui libère une ressource et réveille un thread bloqué s’il y en a un.
• Mutex : Version particulière du sémaphore avec propriété de propriétaire, servant à garantir une exclusion mutuelle.
• Producteur-consommateur : Modèle classique où un producteur produit et un consommateur consomme via un buffer partagé.

📝 Points essentiels

• Le sémaphore est décrit avec $0 \le s \le S$ et une liste d’attente pour les threads bloqués.
• L’opération PROBERN(S) est atomique et bloque si la ressource n’est pas disponible, sinon elle décrémente $S$ d’une unité.
• L’opération VERHOGEN(S) est atomique et incrémente $S$ d’une unité si personne n’attend, sinon elle débloque un thread.
• Un mutex est propriétaire et ne peut pas être libéré par un autre thread, contrairement au sémaphore.
• Dans producteur-consommateur (buffer non borné), le consommateur est bloqué si aucun produit n’est disponible et le mutex protège insertion/extraction.

💡 Astuce mémo

Sémaphore : “libre si $s>0$, sinon j’attends”; Mutex : “1 propriétaire, 1 à la fois, libération contrôlée”.

📖 9. Deadlocks et stratégies

🔑 Notions clés & Définitions

• Deadlock : Blocage où des threads attendent chacun des ressources détenues par d’autres, formant un cycle.
• Autruche (algorithme de l’autruche) : Stratégie citée pour traiter les deadlocks, sans détail chiffré dans la source fournie.
• Détection et résolution : Approche de traitement où l’on repère un deadlock puis on tente de le résoudre.
• Stratégie d’évitement : Approche qui cherche à éviter l’apparition de deadlocks avant qu’ils se produisent.
• Invalidation d’une condition : Principe de prévention qui casse une des conditions nécessaires au deadlock.

📝 Points essentiels

• Un deadlock nécessite C1 exclusion mutuelle, C2 détention R1 et attente R2, C3 absence de préemption, et C4 cycle de détention et d’attente.
• La source illustre un cycle de dépendance avec $T1$ détenant $R1$, $T2$ détenant $R2$, et $T3$ détenant $R3$.
• La stratégie d’évitement et la détection sont listées parmi les options relatives aux deadlocks.
• La prévention structurelle invalide une condition parmi C1 à C4, par exemple C4 via un ordre strict de prise des ressources.
• Une autre solution invalide C2 en utilisant un suivi d’états (PENSE, AFFAM, MANGE) et un mutex global pour la table.

💡 Astuce mémo

Deadlock = C1+C2+C3+C4; casser C4 (ordre) ou casser C2 (règles d’état) supprime le cycle.

📖 10. Systèmes de fichiers et allocations

🔑 Notions clés & Définitions

• Noeud de fichier : Entrée logique représentant un fichier dans l’organisation arborescente du système.
• Noeud de répertoire : Entrée logique représentant un répertoire dans l’arborescence du système.
• Chemin complet : Identifiant d’un nœud obtenu en décrivant la position dans l’arborescence.
• Allocation contiguë : Méthode où chaque fichier occupe un ensemble de blocs consécutifs défini par premier bloc et nombre de blocs.
• Allocation chainée : Méthode où chaque bloc contient un pointeur vers le bloc suivant pour former la chaîne du fichier.

📝 Points essentiels

• Les opérations doivent offrir plusieurs garanties sur les données : pérennité, protection d’accès, efficacité, et résistance aux pannes.
• Une arborescence combine noeuds de fichier et noeuds de répertoire, et l’identification se fait par chemin complet.
• En allocation contiguë, la lecture se fait en une seule passe mais l’extension peut exiger un déplacement des données.
• En allocation chainée, un pointeur dans chaque bloc supprime la fragmentation externe mais ajoute un overhead.
• Pour i-nœuds, l’accès nécessite charger l’i-nœud et la structure encode des blocs directs et des niveaux supplémentaires d’encodage.

💡 Astuce mémo

Contigu = “tout d’un bloc”; Chaînée = “pointeurs entre blocs”; i-nœud = “carte d’adressage”.

📖 11. RAID, FAT et répertoires

🔑 Notions clés & Définitions

• RAID : Technique qui combine plusieurs disques pour améliorer performance et/ou tolérance aux pannes.
• RAID-0 : Niveau RAID basé sur le stripping, alternant des strips entre disques.
• RAID-1 : Niveau RAID basé sur le mirroring, répliquant des strips entre disques.
• RAID-4 : Niveau RAID avec un disque additionnel stockant des strips de parité.
• FAT (File Allocation Table) : Table utilisée par le système de fichiers pour chaîner l’allocation des clusters.

📝 Points essentiels

• RAID-0 alterne les strips entre disques tandis que RAID-1 réplique les strips entre disques.
• RAID-4 utilise un disque dédié pour stocker des strips de parité (par ou exclusif binaire).
• RAID-5 répartit la parité entre au moins 3 disques, plutôt que de la placer tout sur un seul disque.
• Dans la FAT-16, un cluster libre vaut 0x0000 et un cluster “fin de chaîne” est indiqué par 0xFFF8 à 0xFFFF.
• Un répertoire FAT encode des entrées de 32 octets incluant nom court (ASCII), extension, flags, dates, attributs étendus et le premier cluster ainsi que la taille max 2^32 soit 4 GiB.

💡 Astuce mémo

RAID = “0 = découpe”, “1 = miroir”, “4 = parité dédiée”, “5 = parité répartie”.

📊 Tableaux de synthèse

FCFS vs SJF vs SRTF

Politique	Base de choix	Risque	Effet sur turnaround
FCFS	Ordre d’arrivée	Aucun starvation mentionné dans le cours	Énoncé comme ne minimisant pas le turnaround
SJF	Durée estimée	Famine si arrivée continuelle de courtes tâches	Minimise le turnaround (sous condition d’absence de tâche ultérieure plus courte)
SRTF	Durée restante estimée	Famine (lié à SJF)	Minimise le turnaround

⚠️ Pièges & confusions fréquents

1. Confondre PR (prêt) et BL (bloqué) : PR attend une opportunité CPU alors que BL attend une condition à satisfaire.
2. Croire que FCFS maximise le throughput : le cours dit au contraire qu’il ne le maximise pas sur une charge mixte CPU et I/O bound.
3. Oublier la condition associée à SJF : le cours limite la minimisation du turnaround si aucune tâche ultérieure n’est plus courte.
4. Confondre Round Robin et priorités : Round Robin ne tient pas compte d’une importance relative, tandis que les priorités modifient le nombre de quanta.
5. Mélanger mutex et sémaphore : un mutex a un propriétaire et ne se libère pas par un autre thread, contrairement au sémaphore.
6. Croire que l’absence de famine est automatique : elle dépend des conditions requises et de la solution choisie pour l’exclusion mutuelle.
7. Confondre allocation contiguë et chainée : contiguë peut nécessiter déplacement à l’extension, alors que chainée ajoute un pointeur et un overhead.

✅ Checklist Examen

1. Identifier les états du diagramme (EX, PR, BL, ZOMBIE, USR, SYS, EM, HM) et au moins une transition associée (création, chargement, déchargement, déblocage, terminaison).
2. Décrire FCFS : FIFO, équité entre tâches, et ses limites (throughput et turnaround) en présence de charge mixte CPU et I/O bound.
3. Calculer un turnaround moyen à partir des temps cumulés fournis pour FCFS ou SJF (inclure la division par le nombre de tâches).
4. Expliquer SJF : base sur durée estimée, risque de famine, inéquité envers longues tâches, et la condition d’absence de tâche ultérieure plus courte.
5. Décrire SRTF : base sur durée restante estimée, risque de famine, et effet attendu sur le turnaround.
6. Lister les points clés d’un système interactif : multi-utilisateurs/processus, contraintes fortes absentes, propriétés désirables (équité, usage optimal, éviter starvation) et métriques (délai user→réaction, proportionnalité).
7. Différencier Round Robin et Priority Scheduling : quantum/liste cyclique et équité, puis priorités avec 4 quanta vs 1 quantum et objectifs I/O-bound.
8. Appliquer Guaranteed Scheduling : formule du délai garanti (temps depuis création / nombre de processus), définition de ρ, et règle d’exécution jusqu’à ρ > 1.
9. Décrire le critère d’ordonnançabilité en temps réel avec la somme ∑(Ci/Pi) ≤ 1 et conclure sur l’accumulation si elle est violée.
10. Comparer user-level et kernel-level en multithreading : préemption et effet d’un blocage de thread sur le processus.
11. Énoncer les conditions requises d’exclusion mutuelle (C1 exclusion mutuelle, absence d’attente injustifiée, absence de famine, indépendance vitesse/nombre) et le rôle de la section critique.
12. Expliquer le sémaphore avec down/wait et up/signal : comportement quand S==0 et quand S>0 et rôle de la liste d’attente.
13. Différencier mutex et sémaphore : propriétaire, libération par un autre thread possible ou non, et l’idée d’une variable m entre 0 et 1.
14. Retenir les 4 conditions nécessaires au deadlock (C1-C4) et une stratégie d’invalidation : ordre des baguettes (C4) ou états protégés (invalidation de C2).