Code Scheduling Algorithms
Fonctionnement global
L'algorithme FIFO fonctionne selon ces principes:
1. Premier arrivé, premier servi: Les processus sont exécutés dans l'ordre strict de leur
arrivée 1
2. Non-préemptif: Une fois qu'un processus commence, il s'exécute jusqu'à completion
3. Gestion des temps morts: Si aucun processus n'est disponible (CPU idle), l'horloge
avance jusqu'à l'arrivée du prochain processus
Structure de base
package [Link];
import [Link].*;
Définit le package et importe les classes nécessaires des utilitaires Java.
Classe principale
public class SchedulingAlgorithms {
Déclaration de la classe principale qui contient les algorithmes d'ordonnancement.
Classe Process
static class Process {
String name;
int arrivalTime;
int burstTime;
public Process(String name, int arrivalTime, int burstTime) {
[Link] = name;
[Link] = arrivalTime;
[Link] = burstTime;
}
}
Classe interne statique représentant un processus avec:
o name: identifiant du processus
o arrivalTime: temps d'arrivée dans la file d'attente
o burstTime: durée d'exécution nécessaire
o Constructeur pour initialiser ces valeurs
Algorithme FIFO (First-In-First-Out)
public static void fifo(List<Process> processes) {
[Link]("Ordonnancement FIFO :");
[Link]([Link](p -> [Link]));
int currentTime = 0;
for (Process p : processes) {
if (currentTime < [Link]) {
currentTime = [Link];
}
[Link]([Link] + " commence à " + currentTime);
currentTime += [Link]; 2
}
}
1. Trie les processus par temps d'arrivée
2. Initialise l'horloge à 0
3. Pour chaque processus:
o Si l'horloge est inférieure au temps d'arrivée, avance l'horloge
o Affiche le début d'exécution
o Ajoute le temps d'exécution à l'horloge.
public static void fifo(List<Process> processes) {
4. Déclaration de la méthode:
o public static: méthode accessible sans instance de classe et disponible
globalement
o void: ne retourne aucune valeur
o fifo: nom de la méthode
o List<Process> processes: prend en paramètre une liste d'objets Process
[Link]("Ordonnancement FIFO :");
2. Affichage d'en-tête:
o Affiche un message indiquant le début de l'ordonnancement FIFO
[Link]([Link](p -> [Link]));
3. Tri des processus:
o Trie la liste des processus par leur temps d'arrivée (arrivalTime) en ordre
croissant
o Utilise un comparateur qui extrait la valeur arrivalTime de chaque processus
o Résultat: les processus sont ordonnés du premier arrivé au dernier arrivé
int currentTime = 0;
4. Initialisation du temps:
o Initialise une variable currentTime à 0 pour simuler l'horloge du système
for (Process p : processes) {
5. Boucle sur les processus:
o Pour chaque processus dans la liste triée (dans l'ordre d'arrivée)
if (currentTime < [Link]) {
currentTime = [Link];
}
6. Gestion des temps d'arrivée:
o Si l'horloge actuelle est inférieure au temps d'arrivée du processus:
Cela signifie que le CPU était inactif
On avance l'horloge directement au temps d'arrivée du processus
o Sinon, le processus est exécuté immédiatement 3
[Link]([Link] + " commence à " + currentTime);
7. Affichage du début d'exécution:
o Affiche le nom du processus et le moment où il commence à s'exécuter
currentTime += [Link];
8. Mise à jour du temps:
o Ajoute le temps d'exécution (burstTime) du processus à l'horloge actuelle
o Simule ainsi l'exécution complète du processus avant de passer au suivant
}
}
Algorithme SJF (Shortest Job First)
Fonctionnement Global
1. Initialisation : Les processus sont dans waiting.
2. Transfert vers readyQueue : Dès qu'un processus arrive (arrivalTime ≤
currentTime), il est déplacé.
3. Sélection du plus court : Le processus avec le plus petit burstTime est choisi.
4. Exécution : Le processus s'exécute jusqu'à la fin (pas de préemption).
5. Répétition : Le cycle continue jusqu'à ce que tous les processus soient traités.
Algorithme SJF (Shortest Job First)
public static void sjf(List<Process> processes) {
[Link]("Ordonnancement SJF :");
List<Process> readyQueue = new ArrayList<>();
List<Process> waiting = new ArrayList<>(processes);
int currentTime = 0;
while (![Link]() || ![Link]()) {
for (Iterator<Process> it = [Link](); [Link](); ) {
Process p = [Link]();
if ([Link] <= currentTime) {
[Link](p);
[Link]();
}
}
if ([Link]()) {
currentTime++;
continue;
}
[Link]([Link](p -> [Link]));
Process next = [Link](0);
[Link]([Link] + " commence à " + currentTime); 4
currentTime += [Link];
}
}
1. Initialise deux listes: processus en attente et prêts
2. Tant qu'il reste des processus:
o Transfère les processus arrivés dans la file des prêts
o Si aucun processus prêt, avance le temps
o Sinon, prend le processus le plus court et l'exécute
L'algorithme SJF (Shortest Job First) est un algorithme d'ordonnancement des processus qui
donne la priorité aux tâches ayant le temps d'exécution le plus court. Voici une explication
ligne par ligne du code :
1. Déclaration de la Méthode
public static void sjf(List<Process> processes) {
public static : La méthode est accessible sans instanciation de la classe.
void : Ne retourne aucune valeur.
sjf : Nom de la méthode.
List<Process> processes : Prend en entrée une liste de processus (Process).
2. Initialisation des Structures de Données
[Link]("Ordonnancement SJF :");
List<Process> readyQueue = new ArrayList<>();
List<Process> waiting = new ArrayList<>(processes);
int currentTime = 0;
Affichage : Indique le début de l'ordonnancement SJF.
readyQueue : Une liste pour stocker les processus prêts à s'exécuter (déjà arrivés).
waiting : Une copie de la liste originale pour les processus en attente d'arrivée.
currentTime : Simule l'horloge du système (initialisée à 0).
3. Boucle Principale
while (![Link]() || ![Link]()) {
Condition : Continue tant qu'il reste des processus en attente (waiting) ou prêts
(readyQueue).
But : Traiter tous les processus jusqu'à ce qu'ils soient tous exécutés.
5
4. Transfert des Processus Arrivés vers la File des Prêts
for (Iterator<Process> it = [Link](); [Link](); ) {
Process p = [Link]();
if ([Link] <= currentTime) {
[Link](p);
[Link]();
}
}
Parcours de waiting : Vérifie chaque processus en attente.
Condition [Link] <= currentTime : Si le processus est arrivé (arrivalTime
≤ temps actuel), il est transféré dans readyQueue.
[Link]() : Supprime le processus de waiting pour éviter de le retraiter.
5. Gestion du CPU Idle (Si Aucun Processus Prêt)
if ([Link]()) {
currentTime++;
continue;
}
Cas où readyQueue est vide : Aucun processus n'est prêt à s'exécuter.
Incrémentation du temps (currentTime++) : Simule l'attente jusqu'à l'arrivée d'un
nouveau processus.
continue : Passe à l'itération suivante sans exécuter le reste du code.
6. Sélection du Processus le Plus Court
[Link]([Link](p -> [Link]));
Process next = [Link](0);
Tri de readyQueue : Ordonne les processus par burstTime (du plus court au plus long).
remove(0) : Récupère et supprime le premier processus (le plus court) de la file.
7. Exécution du Processus
[Link]([Link] + " commence à " + currentTime);
currentTime += [Link];
Affichage : Affiche le nom du processus et son temps de début.
Mise à jour de currentTime : Ajoute le burstTime du processus pour simuler son
exécution.
6
L'algorithme Round Robin (RR) est un algorithme d'ordonnancement utilisé dans les systèmes
d'exploitation pour gérer l'exécution des processus dans un environnement multitâche. Il est basé
sur un principe d'équité, où chaque processus reçoit une tranche de temps fixe appelée quantum
pour s'exécuter, avant de passer au processus suivant dans une file d'attente circulaire.
Algorithme RR (Round Robin)
Fonctionnement global de l'algorithme
6. Initialisation : Trie les processus par temps d'arrivée et prépare la file d'attente.
7. Ajout des processus : À chaque itération, ajoute les processus arrivés au temps actuel
dans la file.
8. Exécution : Exécute le premier processus de la file pour un temps égal au minimum entre
le quantum et son temps restant.
9. Rotation : Si le processus n'est pas terminé, il est replacé en fin de file. Sinon, il est retiré.
10. Avancement du temps : Si aucun processus n'est prêt, le temps est incrémenté jusqu'à
l'arrivée d'un nouveau processus.
11. Fin : La boucle s'arrête lorsque tous les processus sont terminés et qu'aucun nouveau
processus n'arrive.
public static void rr(List<Process> processes, int quantum) {
[Link]("Ordonnancement Round Robin (quantum = " + quantum +
") :");
Queue<Process> queue = new LinkedList<>();
Map<String, Integer> remaining = new HashMap<>();
int currentTime = 0;
int index = 0;
[Link]([Link](p -> [Link]));
while (![Link]() || index < [Link]()) {
while (index < [Link]() && [Link](index).arrivalTime
<= currentTime) {
[Link]([Link](index));
[Link]([Link](index).name,
[Link](index).burstTime);
index++;
}
if ([Link]()) {
currentTime++;
continue;
}
Process p = [Link]();
int rem = [Link]([Link]);
int exec = [Link](quantum, rem);
[Link]([Link] + " s'exécute de " + currentTime + " à " +
(currentTime + exec));
currentTime += exec;
rem -= exec; 7
if (rem > 0) {
[Link]([Link], rem);
while (index < [Link]() &&
[Link](index).arrivalTime <= currentTime) {
[Link]([Link](index));
[Link]([Link](index).name,
[Link](index).burstTime);
index++;
}
[Link](p);
}
}
}
1. Utilise une file et une map pour suivre le temps restant
2. Ajoute les processus arrivés dans la file
3. Exécute chaque processus pour un quantum ou jusqu'à fin
4. Si le processus n'est pas fini, le remet en file
Structure du code et explication ligne par ligne
Signature de la méthode
public static void rr(List<Process> processes, int quantum)
Entrées :
o processes : Une liste d'objets Process, où chaque processus a au moins trois
attributs :
name : Nom ou identifiant du processus.
arrivalTime : Temps d'arrivée du processus.
burstTime : Temps total d'exécution requis par le processus.
o quantum : La durée maximale allouée à chaque processus par cycle d'exécution.
Objectif : Simuler l'ordonnancement des processus selon l'algorithme RR et afficher les
intervalles d'exécution.
Initialisation
[Link]("Ordonnancement Round Robin (quantum = " + quantum + ")
:");
Queue<Process> queue = new LinkedList<>();
Map<String, Integer> remaining = new HashMap<>();
int currentTime = 0;
int index = 0;
Affiche un message indiquant que l'algorithme RR est utilisé avec le quantum spécifié.
queue : Une file d'attente (FIFO) pour stocker les processus prêts à être exécutés.
remaining : Une map qui associe le nom de chaque processus à son temps d'exécution 8
restant (initialement égal à burstTime).
currentTime : Temps actuel dans la simulation, commençant à 0.
index : Index pour parcourir la liste des processus dans l'ordre de leur arrivée.
Tri des processus
[Link]([Link](p -> [Link]));
Trie la liste des processus par ordre croissant de leur temps d'arrivée (arrivalTime). Cela
garantit que les processus sont considérés dans l'ordre où ils arrivent dans le système.
Boucle principale
while (![Link]() || index < [Link]()) {
La boucle continue tant que :
o Il reste des processus dans la file d'attente (queue non vide), ou
o Il reste des processus non encore ajoutés à la file (index < [Link]()).
Ajout des processus arrivés
while (index < [Link]() && [Link](index).arrivalTime <=
currentTime) {
[Link]([Link](index));
[Link]([Link](index).name, [Link](index).burstTime);
index++;
}
Parcourt la liste des processus pour ajouter ceux dont le temps d'arrivée (arrivalTime)
est inférieur ou égal au temps actuel (currentTime).
Chaque processus ajouté est :
o Placé dans la file d'attente ([Link]).
o Enregistré dans remaining avec son temps d'exécution total (burstTime).
Incrémente index pour passer au processus suivant.
Gestion du cas où la file est vide
if ([Link]()) {
currentTime++;
continue;
}
Si la file est vide (aucun processus prêt à s'exécuter), le temps est incrémenté
(currentTime++) pour avancer jusqu'à l'arrivée du prochain processus.
Passe à l'itération suivante de la boucle principale.
9
Exécution d'un processus
Process p = [Link]();
int rem = [Link]([Link]);
int exec = [Link](quantum, rem);
[Link]([Link] + " s'exécute de " + currentTime + " à " +
(currentTime + exec));
currentTime += exec;
rem -= exec;
Récupère le prochain processus de la file ([Link]()).
Récupère le temps d'exécution restant pour ce processus (rem).
Calcule le temps d'exécution pour ce cycle : soit le quantum, soit le temps restant, selon le
minimum ([Link](quantum, rem)).
Affiche l'exécution du processus avec l'intervalle de temps [currentTime,
currentTime + exec].
Met à jour :
o currentTime en ajoutant le temps d'exécution (exec).
o rem en soustrayant le temps exécuté.
Gestion du processus après exécution
if (rem > 0) {
[Link]([Link], rem);
while (index < [Link]() && [Link](index).arrivalTime <=
currentTime) {
[Link]([Link](index));
[Link]([Link](index).name,
[Link](index).burstTime);
index++;
}
[Link](p);
}
Si le processus n'a pas terminé (rem > 0) :
o Met à jour le temps restant dans remaining.
o Ajoute à la file tout nouveau processus arrivé pendant l'exécution du processus
courant (même logique que précédemment).
o Replace le processus courant à la fin de la file ([Link](p)) pour qu'il soit
réexécuté plus tard.
Si rem == 0, le processus est terminé et n'est pas remis dans la file.
10
Algorithme Random Scheduling Technique
public static void rascte(List<Process> processes) {
[Link]("Ordonnancement rascte (Random Scheduling Technique)
:");
List<Process> readyQueue = new ArrayList<>();
List<Process> waiting = new ArrayList<>(processes);
int currentTime = 0;
Random rand = new Random();
while (![Link]() || ![Link]()) {
for (Iterator<Process> it = [Link](); [Link](); ) {
Process p = [Link]();
if ([Link] <= currentTime) {
[Link](p);
[Link]();
}
}
if ([Link]()) {
currentTime++;
continue;
}
int idx = [Link]([Link]());
Process next = [Link](idx);
[Link]([Link] + " commence à " + currentTime);
currentTime += [Link];
}
}
Similaire à SJF mais choisit le processus suivant aléatoirement
Méthode main
public static void main(String[] args) {
List<Process> processes = [Link](
new Process("P1", 0, 5),
new Process("P2", 1, 3),
new Process("P3", 2, 8),
new Process("P4", 3, 6)
);
fifo(new ArrayList<>(processes));
[Link]();
sjf(new ArrayList<>(processes));
[Link]();
rr(new ArrayList<>(processes), 3);
[Link]();
rascte(new ArrayList<>(processes));
}
11
Crée une liste de processus de test
Exécute chaque algorithme avec ces processus
Crée de nouvelles ArrayList pour éviter les modifications sur la liste originale
Code Complet
package [Link];
import [Link].*;
public class SchedulingAlgorithms { 12
/**
* Classe représentant un processus.
*/
static class Process {
String name;
int arrivalTime;
int burstTime;
public Process(String name, int arrivalTime, int burstTime) {
[Link] = name;
[Link] = arrivalTime;
[Link] = burstTime;
}
}
/**
* Algorithme FIFO (First-In-First-Out)
*/
public static void fifo(List<Process> processes) {
[Link]("Ordonnancement FIFO :");
[Link]([Link](p -> [Link]));
int currentTime = 0;
for (Process p : processes) {
if (currentTime < [Link]) {
currentTime = [Link];
}
[Link]([Link] + " commence à " + currentTime);
currentTime += [Link];
}
}
/**
* Algorithme SJF (Shortest Job First)
*/
public static void sjf(List<Process> processes) {
[Link]("Ordonnancement SJF :");
List<Process> readyQueue = new ArrayList<>();
List<Process> waiting = new ArrayList<>(processes);
int currentTime = 0;
while (![Link]() || ![Link]()) {
for (Iterator<Process> it = [Link](); [Link](); ) {
Process p = [Link]();
if ([Link] <= currentTime) {
[Link](p);
[Link]();
}
}
if ([Link]()) {
currentTime++;
continue; 13
}
[Link]([Link](p -> [Link]));
Process next = [Link](0);
[Link]([Link] + " commence à " + currentTime);
currentTime += [Link];
}
}
/**
* Algorithme RR (Round Robin)
*/
public static void rr(List<Process> processes, int quantum) {
[Link]("Ordonnancement Round Robin (quantum = " + quantum +
") :");
Queue<Process> queue = new LinkedList<>();
Map<String, Integer> remaining = new HashMap<>();
int currentTime = 0;
int index = 0;
[Link]([Link](p -> [Link]));
while (![Link]() || index < [Link]()) {
while (index < [Link]() && [Link](index).arrivalTime
<= currentTime) {
[Link]([Link](index));
[Link]([Link](index).name,
[Link](index).burstTime);
index++;
}
if ([Link]()) {
currentTime++;
continue;
}
Process p = [Link]();
int rem = [Link]([Link]);
int exec = [Link](quantum, rem);
[Link]([Link] + " s'exécute de " + currentTime + " à " +
(currentTime + exec));
currentTime += exec;
rem -= exec;
if (rem > 0) {
[Link]([Link], rem);
// Ajouter les nouveaux processus arrivés pendant l'exécution
while (index < [Link]() &&
[Link](index).arrivalTime <= currentTime) {
[Link]([Link](index));
[Link]([Link](index).name,
[Link](index).burstTime);
index++;
}
[Link](p);
} 14
}
}
/**
* Algorithme Random Scheduling Technique
*/
public static void rascte (List<Process> processes) {
[Link]("Ordonnancement Random Scheduling Technique :");
List<Process> readyQueue = new ArrayList<>();
List<Process> waiting = new ArrayList<>(processes);
int currentTime = 0;
Random rand = new Random();
while (![Link]() || ![Link]()) {
for (Iterator<Process> it = [Link](); [Link](); ) {
Process p = [Link]();
if ([Link] <= currentTime) {
[Link](p);
[Link]();
}
}
if ([Link]()) {
currentTime++;
continue;
}
int idx = [Link]([Link]());
Process next = [Link](idx);
[Link]([Link] + " commence à " + currentTime);
currentTime += [Link];
}
}
/**
* Exemple d'utilisation des algorithmes.
*/
public static void main(String[] args) {
List<Process> processes = [Link](
new Process("P1", 0, 5),
new Process("P2", 1, 3),
new Process("P3", 2, 8),
new Process("P4", 3, 6)
);
fifo(new ArrayList<>(processes));
[Link]();
sjf(new ArrayList<>(processes));
[Link]();
rr(new ArrayList<>(processes), 3);
[Link]();
rascte(new ArrayList<>(processes));
} 15