Files d'attente d'ordonnancement des processus
Le système d'exploitation maintient tous les PCB (Process Control Blocks) dans des files d'attente d'ordonnancement. Le SE maintient une file d'attente séparée pour chacun des états de processus et les PCB de tous les processus dans le même état d'exécution sont placés dans la même file d'attente.
Plusieurs processus existent simultanément dans le système. Tous les processus ont des besoins différents. Certains peuvent avoir besoin de l'unité centrale pour l'exécution, tandis que d'autres peuvent avoir besoin de périphériques d'entrée/sortie. Comme les ressources sont limitées, certains processus peuvent avoir besoin d'attendre.
Pendant qu'ils attendent, en fonction de leurs besoins, ils sont placés dans différents types de files d'attente. Lorsqu'un processus passe par différents états, il reste également dans différentes files d'attente.
Lorsque l'état d'un processus est modifié, son PCB est dissocié de sa file d'attente actuelle et déplacé vers sa nouvelle file d'attente d'état.
Les principales files d'attente d'ordonnancement
Le système d'exploitation maintient les importantes files d'attente d'ordonnancement de processus suivantes :
File d'attente des tâches (Job Queue)
Cette file d'attente conserve tous les processus du système, quels que soient leur état et leur emplacement (en mémoire ou sur disque).
Lorsqu'un nouveau processus est créé, il est d'abord placé dans cette file d'attente.
File d'attente prête (Ready Queue)
Cette file conserve un ensemble de tous les processus résidant dans la mémoire principale, prêts et en attente d'exécution.
Un nouveau processus est toujours placé dans cette file après sa création et son chargement en mémoire.
Les processus dans cette file n'attendent que le CPU.
Files d'attente des périphériques (Device Queues)
Les processus qui sont bloqués en raison de l'indisponibilité d'un périphérique d'E/S constituent cette file d'attente.
Il existe généralement une file d'attente distincte pour chaque périphérique (disque, imprimante, clavier, etc.).
Lorsqu'une opération d'E/S est terminée, le processus est replacé dans la file d'attente prête.
Schéma des files d'attente et transitions
Figure : Organisation et transitions entre les différentes files d'attente
┌─────────────────┐
│ Nouveau processus│
└─────────┬───────┘
│
▼
┌─────────────────┐
│ File d'attente │
│ prête │◄─────────────────────┐
└─────────┬───────┘ │
│ │
│ (Ordonnanceur) │
▼ │
┌─────────────────┐ Fin E/S ┌────┴───────┐
│ En cours │────────────────►│ File │
│ d'exécution │ │ d'attente │
└─────────┬───────┘◄────────────────│périphérique│
│ Requête E/S └────┬───────┘
│ │
│ (Terminaison) │
▼ │
┌─────────────────┐ │
│ Processus │ │
│ terminé │ │
└─────────────────┘───────────────────────┘
Gestion des files d'attente
Il existe différentes politiques que le système d'exploitation utilise pour gérer chaque file d'attente. Le planificateur du système d'exploitation décide comment déplacer les processus entre la file d'attente prête et la file d'attente d'exécution, ce qui n'autorise qu'une seule entrée par cœur de processeur sur le système.
- Planificateur à long terme (Job Scheduler) : Sélectionne les processus à charger en mémoire depuis la file des tâches.
- Planificateur à court terme (CPU Scheduler) : Sélectionne le prochain processus à exécuter depuis la file prête.
- Planificateur à moyen terme : Gère le swapping (échange) entre mémoire et disque.
Modèle du processus à deux états
Il existe deux états dans le modèle de processus à deux états, à savoir l'état d'exécution et l'état de non-exécution.
Un nouveau processus entre dans le système en état d'exécution, après sa création. C'est l'état où le processus utilise effectivement le CPU.
Caractéristiques :
- Un seul processus par cœur de CPU peut être dans cet état à un instant donné.
- Le processus exécute ses instructions.
- Il quitte cet état soit par terminaison, soit par interruption (passage en attente ou retour en file prête).
Les processus non en cours d'exécution sont stockés dans une file d'attente jusqu'à ce que leur tour d'exécution arrive.
Caractéristiques :
- Chaque entrée de la file d'attente pointe vers un processus particulier.
- La file d'attente peut être implémentée à l'aide d'une liste chaînée.
- Les processus dans cet état peuvent être prêts (Ready) ou en attente (Waiting).
Fonctionnement du modèle à deux états
- Un nouveau processus est créé et placé dans l'état d'exécution.
- Lorsqu'un processus est interrompu (par exemple, par une horloge ou une priorité plus élevée), ce processus est transféré dans la file d'attente (état non-exécution).
- Si le processus est terminé ou interrompu définitivement, il est écarté du système.
- Dans les deux cas (interruption ou terminaison d'un autre), le répartiteur (dispatcher) sélectionne ensuite un processus dans la file d'attente pour l'exécuter.
Diagramme du modèle à deux états
┌─────────────┐ ┌─────────────┐
│ Running │◄───────►│ Not Running │
│ (Exécution) │ │ (File d'attente)│
└─────────────┘ └─────────────┘
│ ▲
│ │
└────────────────────────┘
(Dispatch)
Implémentation des files d'attente
Les files d'attente de processus sont généralement implémentées à l'aide de listes chaînées de PCB (Process Control Blocks).
// Structure simplifiée d'un PCB
typedef struct PCB {
int pid; // Identifiant du processus
int etat; // État courant
struct PCB* suivant; // Pointeur vers le prochain PCB dans la file
// ... autres informations (registres, priorité, etc.)
} PCB;
// Structure d'une file d'attente
typedef struct FileAttente {
PCB* tete; // Premier processus de la file
PCB* queue; // Dernier processus de la file
int taille; // Nombre de processus dans la file
} FileAttente;Gestion des files d'attente
On considère un système avec les processus suivants et leurs états :
| Processus | État | Ressource attendue |
|---|---|---|
| P1 | En cours d'exécution | - |
| P2 | Prêt | - |
| P3 | En attente | Disque |
| P4 | Prêt | - |
| P5 | En attente | Imprimante |
| P6 | En attente | Disque |
Questions :
- Dans quelle(s) file(s) d'attente se trouve chaque processus ?
- Si P1 termine son exécution, quel processus sera sélectionné par le répartiteur ?
- Si le disque termine une opération, quels processus sont concernés et où vont-ils ?
- Représentez l'état des files d'attente après que P1 a été interrompu et que P2 a commencé son exécution.
- Files d'attente par processus :
- P1 : File d'exécution (Running) - pas vraiment une file, c'est le processus actif.
- P2, P4 : File d'attente prête (Ready Queue).
- P3, P6 : File d'attente du périphérique Disque.
- P5 : File d'attente du périphérique Imprimante.
- Si P1 termine : Le répartiteur sélectionnera le prochain processus dans la file d'attente prête. Selon la politique d'ordonnancement (souvent FIFO ou priorité), ce pourrait être P2 (premier arrivé) ou celui avec la plus haute priorité.
- Fin d'opération disque : Les processus P3 et P6 (en attente de disque) sont déplacés de la file d'attente du disque vers la file d'attente prête. Ils attendront maintenant leur tour pour le CPU.
- État après interruption de P1 et exécution de P2 :
- P1 passe de Running → Ready (placé en fin de file prête) - P2 passe de Ready → Running - File prête : [P4, P1] (ordre dépendant de la politique) - File disque : [P3, P6] - File imprimante : [P5]
- Le système d'exploitation maintient des files d'attente distinctes pour chaque état de processus.
- Les principales files sont : file des tâches (tous les processus), file prête (prêts à exécuter), et files des périphériques (en attente d'E/S).
- Les PCB sont déplacés d'une file à l'autre lorsque l'état du processus change.
- Le modèle à deux états simplifie la vision en distinguant seulement exécution et non-exécution.
- Dans le modèle à deux états, les processus non exécutés sont stockés dans une file d'attente unique.
- Le répartiteur (dispatcher) est responsable de la sélection du prochain processus depuis la file prête.
- Les files d'attente sont généralement implémentées comme des listes chaînées de PCB.
- La gestion des files d'attente est fondamentale pour l'ordonnancement et la multiprogrammation.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.